?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
ACPI: pci_root: simplify list traversals
[linux-2.6/linux-acpi-2.6.git] / fs / reiserfs / lbalance.c
blob381750a155f62d544ac6286896e314b43b5404ac
1 /*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
5 #include <asm/uaccess.h>
6 #include <linux/string.h>
7 #include <linux/time.h>
8 #include <linux/reiserfs_fs.h>
9 #include <linux/buffer_head.h>
10
11 /* these are used in do_balance.c */
12
13 /* leaf_move_items
14 leaf_shift_left
15 leaf_shift_right
16 leaf_delete_items
17 leaf_insert_into_buf
18 leaf_paste_in_buffer
19 leaf_cut_from_buffer
20 leaf_paste_entries
21 */
22
23 /* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
24 static void leaf_copy_dir_entries(struct buffer_info *dest_bi,
25 struct buffer_head *source, int last_first,
26 int item_num, int from, int copy_count)
27 {
28 struct buffer_head *dest = dest_bi->bi_bh;
29 int item_num_in_dest; /* either the number of target item,
30 or if we must create a new item,
31 the number of the item we will
32 create it next to */
33 struct item_head *ih;
34 struct reiserfs_de_head *deh;
35 int copy_records_len; /* length of all records in item to be copied */
36 char *records;
37
38 ih = B_N_PITEM_HEAD(source, item_num);
39
40 RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item");
41
42 /* length of all record to be copied and first byte of the last of them */
43 deh = B_I_DEH(source, ih);
44 if (copy_count) {
45 copy_records_len = (from ? deh_location(&(deh[from - 1])) :
46 ih_item_len(ih)) -
47 deh_location(&(deh[from + copy_count - 1]));
48 records =
49 source->b_data + ih_location(ih) +
50 deh_location(&(deh[from + copy_count - 1]));
51 } else {
52 copy_records_len = 0;
53 records = NULL;
54 }
55
56 /* when copy last to first, dest buffer can contain 0 items */
57 item_num_in_dest =
58 (last_first ==
59 LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest)
60 - 1);
61
62 /* if there are no items in dest or the first/last item in dest is not item of the same directory */
63 if ((item_num_in_dest == -1) ||
64 (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) ||
65 (last_first == LAST_TO_FIRST
66 && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key,
67 B_N_PKEY(dest,
68 item_num_in_dest))))
69 {
70 /* create new item in dest */
71 struct item_head new_ih;
72
73 /* form item header */
74 memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
75 put_ih_version(&new_ih, KEY_FORMAT_3_5);
76 /* calculate item len */
77 put_ih_item_len(&new_ih,
78 DEH_SIZE * copy_count + copy_records_len);
79 put_ih_entry_count(&new_ih, 0);
80
81 if (last_first == LAST_TO_FIRST) {
82 /* form key by the following way */
83 if (from < I_ENTRY_COUNT(ih)) {
84 set_le_ih_k_offset(&new_ih,
85 deh_offset(&(deh[from])));
86 /*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE); */
87 } else {
88 /* no entries will be copied to this item in this function */
89 set_le_ih_k_offset(&new_ih, U32_MAX);
90 /* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */
91 }
92 set_le_key_k_type(KEY_FORMAT_3_5, &(new_ih.ih_key),
93 TYPE_DIRENTRY);
94 }
95
96 /* insert item into dest buffer */
97 leaf_insert_into_buf(dest_bi,
98 (last_first ==
99 LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest),
100 &new_ih, NULL, 0);
101 } else {
102 /* prepare space for entries */
103 leaf_paste_in_buffer(dest_bi,
104 (last_first ==
105 FIRST_TO_LAST) ? (B_NR_ITEMS(dest) -
106 1) : 0, MAX_US_INT,
107 DEH_SIZE * copy_count + copy_records_len,
108 records, 0);
109 }
110
111 item_num_in_dest =
112 (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0;
113
114 leaf_paste_entries(dest_bi, item_num_in_dest,
115 (last_first ==
116 FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD(dest,
117 item_num_in_dest))
118 : 0, copy_count, deh + from, records,
119 DEH_SIZE * copy_count + copy_records_len);
120 }
121
122 /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or
123 part of it or nothing (see the return 0 below) from SOURCE to the end
124 (if last_first) or beginning (!last_first) of the DEST */
125 /* returns 1 if anything was copied, else 0 */
126 static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
127 struct buffer_head *src, int last_first,
128 int bytes_or_entries)
129 {
130 struct buffer_head *dest = dest_bi->bi_bh;
131 int dest_nr_item, src_nr_item; /* number of items in the source and destination buffers */
132 struct item_head *ih;
133 struct item_head *dih;
134
135 dest_nr_item = B_NR_ITEMS(dest);
136
137 if (last_first == FIRST_TO_LAST) {
138 /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
139 or of different types ) then there is no need to treat this item differently from the other items
140 that we copy, so we return */
141 ih = B_N_PITEM_HEAD(src, 0);
142 dih = B_N_PITEM_HEAD(dest, dest_nr_item - 1);
143 if (!dest_nr_item
144 || (!op_is_left_mergeable(&(ih->ih_key), src->b_size)))
145 /* there is nothing to merge */
146 return 0;
147
148 RFALSE(!ih_item_len(ih),
149 "vs-10010: item can not have empty length");
150
151 if (is_direntry_le_ih(ih)) {
152 if (bytes_or_entries == -1)
153 /* copy all entries to dest */
154 bytes_or_entries = ih_entry_count(ih);
155 leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0,
156 bytes_or_entries);
157 return 1;
158 }
159
160 /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
161 part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
162 */
163 if (bytes_or_entries == -1)
164 bytes_or_entries = ih_item_len(ih);
165
166 #ifdef CONFIG_REISERFS_CHECK
167 else {
168 if (bytes_or_entries == ih_item_len(ih)
169 && is_indirect_le_ih(ih))
170 if (get_ih_free_space(ih))
171 reiserfs_panic(sb_from_bi(dest_bi),
172 "vs-10020",
173 "last unformatted node "
174 "must be filled "
175 "entirely (%h)", ih);
176 }
177 #endif
178
179 /* merge first item (or its part) of src buffer with the last
180 item of dest buffer. Both are of the same file */
181 leaf_paste_in_buffer(dest_bi,
182 dest_nr_item - 1, ih_item_len(dih),
183 bytes_or_entries, B_I_PITEM(src, ih), 0);
184
185 if (is_indirect_le_ih(dih)) {
186 RFALSE(get_ih_free_space(dih),
187 "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
188 ih);
189 if (bytes_or_entries == ih_item_len(ih))
190 set_ih_free_space(dih, get_ih_free_space(ih));
191 }
192
193 return 1;
194 }
195
196 /* copy boundary item to right (last_first == LAST_TO_FIRST) */
197
198 /* ( DEST is empty or last item of SOURCE and first item of DEST
199 are the items of different object or of different types )
200 */
201 src_nr_item = B_NR_ITEMS(src);
202 ih = B_N_PITEM_HEAD(src, src_nr_item - 1);
203 dih = B_N_PITEM_HEAD(dest, 0);
204
205 if (!dest_nr_item || !op_is_left_mergeable(&(dih->ih_key), src->b_size))
206 return 0;
207
208 if (is_direntry_le_ih(ih)) {
209 if (bytes_or_entries == -1)
210 /* bytes_or_entries = entries number in last item body of SOURCE */
211 bytes_or_entries = ih_entry_count(ih);
212
213 leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
214 src_nr_item - 1,
215 ih_entry_count(ih) - bytes_or_entries,
216 bytes_or_entries);
217 return 1;
218 }
219
220 /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST;
221 part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST;
222 don't create new item header
223 */
224
225 RFALSE(is_indirect_le_ih(ih) && get_ih_free_space(ih),
226 "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
227 ih);
228
229 if (bytes_or_entries == -1) {
230 /* bytes_or_entries = length of last item body of SOURCE */
231 bytes_or_entries = ih_item_len(ih);
232
233 RFALSE(le_ih_k_offset(dih) !=
234 le_ih_k_offset(ih) + op_bytes_number(ih, src->b_size),
235 "vs-10050: items %h and %h do not match", ih, dih);
236
237 /* change first item key of the DEST */
238 set_le_ih_k_offset(dih, le_ih_k_offset(ih));
239
240 /* item becomes non-mergeable */
241 /* or mergeable if left item was */
242 set_le_ih_k_type(dih, le_ih_k_type(ih));
243 } else {
244 /* merge to right only part of item */
245 RFALSE(ih_item_len(ih) <= bytes_or_entries,
246 "vs-10060: no so much bytes %lu (needed %lu)",
247 (unsigned long)ih_item_len(ih),
248 (unsigned long)bytes_or_entries);
249
250 /* change first item key of the DEST */
251 if (is_direct_le_ih(dih)) {
252 RFALSE(le_ih_k_offset(dih) <=
253 (unsigned long)bytes_or_entries,
254 "vs-10070: dih %h, bytes_or_entries(%d)", dih,
255 bytes_or_entries);
256 set_le_ih_k_offset(dih,
257 le_ih_k_offset(dih) -
258 bytes_or_entries);
259 } else {
260 RFALSE(le_ih_k_offset(dih) <=
261 (bytes_or_entries / UNFM_P_SIZE) * dest->b_size,
262 "vs-10080: dih %h, bytes_or_entries(%d)",
263 dih,
264 (bytes_or_entries / UNFM_P_SIZE) * dest->b_size);
265 set_le_ih_k_offset(dih,
266 le_ih_k_offset(dih) -
267 ((bytes_or_entries / UNFM_P_SIZE) *
268 dest->b_size));
269 }
270 }
271
272 leaf_paste_in_buffer(dest_bi, 0, 0, bytes_or_entries,
273 B_I_PITEM(src,
274 ih) + ih_item_len(ih) - bytes_or_entries,
275 0);
276 return 1;
277 }
278
279 /* copy cpy_mun items from buffer src to buffer dest
280 * last_first == FIRST_TO_LAST means, that we copy cpy_num items beginning from first-th item in src to tail of dest
281 * last_first == LAST_TO_FIRST means, that we copy cpy_num items beginning from first-th item in src to head of dest
282 */
283 static void leaf_copy_items_entirely(struct buffer_info *dest_bi,
284 struct buffer_head *src, int last_first,
285 int first, int cpy_num)
286 {
287 struct buffer_head *dest;
288 int nr, free_space;
289 int dest_before;
290 int last_loc, last_inserted_loc, location;
291 int i, j;
292 struct block_head *blkh;
293 struct item_head *ih;
294
295 RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST,
296 "vs-10090: bad last_first parameter %d", last_first);
297 RFALSE(B_NR_ITEMS(src) - first < cpy_num,
298 "vs-10100: too few items in source %d, required %d from %d",
299 B_NR_ITEMS(src), cpy_num, first);
300 RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items");
301 RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items");
302
303 dest = dest_bi->bi_bh;
304
305 RFALSE(!dest, "vs-10130: can not copy negative amount of items");
306
307 if (cpy_num == 0)
308 return;
309
310 blkh = B_BLK_HEAD(dest);
311 nr = blkh_nr_item(blkh);
312 free_space = blkh_free_space(blkh);
313
314 /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */
315 dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;
316
317 /* location of head of first new item */
318 ih = B_N_PITEM_HEAD(dest, dest_before);
319
320 RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE,
321 "vs-10140: not enough free space for headers %d (needed %d)",
322 B_FREE_SPACE(dest), cpy_num * IH_SIZE);
323
324 /* prepare space for headers */
325 memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE);
326
327 /* copy item headers */
328 memcpy(ih, B_N_PITEM_HEAD(src, first), cpy_num * IH_SIZE);
329
330 free_space -= (IH_SIZE * cpy_num);
331 set_blkh_free_space(blkh, free_space);
332
333 /* location of unmovable item */
334 j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1);
335 for (i = dest_before; i < nr + cpy_num; i++) {
336 location -= ih_item_len(ih + i - dest_before);
337 put_ih_location(ih + i - dest_before, location);
338 }
339
340 /* prepare space for items */
341 last_loc = ih_location(&(ih[nr + cpy_num - 1 - dest_before]));
342 last_inserted_loc = ih_location(&(ih[cpy_num - 1]));
343
344 /* check free space */
345 RFALSE(free_space < j - last_inserted_loc,
346 "vs-10150: not enough free space for items %d (needed %d)",
347 free_space, j - last_inserted_loc);
348
349 memmove(dest->b_data + last_loc,
350 dest->b_data + last_loc + j - last_inserted_loc,
351 last_inserted_loc - last_loc);
352
353 /* copy items */
354 memcpy(dest->b_data + last_inserted_loc,
355 B_N_PITEM(src, (first + cpy_num - 1)), j - last_inserted_loc);
356
357 /* sizes, item number */
358 set_blkh_nr_item(blkh, nr + cpy_num);
359 set_blkh_free_space(blkh, free_space - (j - last_inserted_loc));
360
361 do_balance_mark_leaf_dirty(dest_bi->tb, dest, 0);
362
363 if (dest_bi->bi_parent) {
364 struct disk_child *t_dc;
365 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
366 RFALSE(dc_block_number(t_dc) != dest->b_blocknr,
367 "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu",
368 (long unsigned)dest->b_blocknr,
369 (long unsigned)dc_block_number(t_dc));
370 put_dc_size(t_dc,
371 dc_size(t_dc) + (j - last_inserted_loc +
372 IH_SIZE * cpy_num));
373
374 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
375 0);
376 }
377 }
378
379 /* This function splits the (liquid) item into two items (useful when
380 shifting part of an item into another node.) */
381 static void leaf_item_bottle(struct buffer_info *dest_bi,
382 struct buffer_head *src, int last_first,
383 int item_num, int cpy_bytes)
384 {
385 struct buffer_head *dest = dest_bi->bi_bh;
386 struct item_head *ih;
387
388 RFALSE(cpy_bytes == -1,
389 "vs-10170: bytes == - 1 means: do not split item");
390
391 if (last_first == FIRST_TO_LAST) {
392 /* if ( if item in position item_num in buffer SOURCE is directory item ) */
393 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
394 leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
395 item_num, 0, cpy_bytes);
396 else {
397 struct item_head n_ih;
398
399 /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST
400 part defined by 'cpy_bytes'; create new item header; change old item_header (????);
401 n_ih = new item_header;
402 */
403 memcpy(&n_ih, ih, IH_SIZE);
404 put_ih_item_len(&n_ih, cpy_bytes);
405 if (is_indirect_le_ih(ih)) {
406 RFALSE(cpy_bytes == ih_item_len(ih)
407 && get_ih_free_space(ih),
408 "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
409 (long unsigned)get_ih_free_space(ih));
410 set_ih_free_space(&n_ih, 0);
411 }
412
413 RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size),
414 "vs-10190: bad mergeability of item %h", ih);
415 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
416 leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
417 B_N_PITEM(src, item_num), 0);
418 }
419 } else {
420 /* if ( if item in position item_num in buffer SOURCE is directory item ) */
421 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
422 leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
423 item_num,
424 I_ENTRY_COUNT(ih) - cpy_bytes,
425 cpy_bytes);
426 else {
427 struct item_head n_ih;
428
429 /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST
430 part defined by 'cpy_bytes'; create new item header;
431 n_ih = new item_header;
432 */
433 memcpy(&n_ih, ih, SHORT_KEY_SIZE);
434
435 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
436
437 if (is_direct_le_ih(ih)) {
438 set_le_ih_k_offset(&n_ih,
439 le_ih_k_offset(ih) +
440 ih_item_len(ih) - cpy_bytes);
441 set_le_ih_k_type(&n_ih, TYPE_DIRECT);
442 set_ih_free_space(&n_ih, MAX_US_INT);
443 } else {
444 /* indirect item */
445 RFALSE(!cpy_bytes && get_ih_free_space(ih),
446 "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
447 set_le_ih_k_offset(&n_ih,
448 le_ih_k_offset(ih) +
449 (ih_item_len(ih) -
450 cpy_bytes) / UNFM_P_SIZE *
451 dest->b_size);
452 set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
453 set_ih_free_space(&n_ih, get_ih_free_space(ih));
454 }
455
456 /* set item length */
457 put_ih_item_len(&n_ih, cpy_bytes);
458
459 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
460
461 leaf_insert_into_buf(dest_bi, 0, &n_ih,
462 B_N_PITEM(src,
463 item_num) +
464 ih_item_len(ih) - cpy_bytes, 0);
465 }
466 }
467 }
468
469 /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
470 If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
471 From last item copy cpy_num bytes for regular item and cpy_num directory entries for
472 directory item. */
473 static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
474 int last_first, int cpy_num, int cpy_bytes)
475 {
476 struct buffer_head *dest;
477 int pos, i, src_nr_item, bytes;
478
479 dest = dest_bi->bi_bh;
480 RFALSE(!dest || !src, "vs-10210: !dest || !src");
481 RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
482 "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
483 RFALSE(B_NR_ITEMS(src) < cpy_num,
484 "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
485 cpy_num);
486 RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);
487
488 if (cpy_num == 0)
489 return 0;
490
491 if (last_first == FIRST_TO_LAST) {
492 /* copy items to left */
493 pos = 0;
494 if (cpy_num == 1)
495 bytes = cpy_bytes;
496 else
497 bytes = -1;
498
499 /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
500 i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
501 cpy_num -= i;
502 if (cpy_num == 0)
503 return i;
504 pos += i;
505 if (cpy_bytes == -1)
506 /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
507 leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
508 pos, cpy_num);
509 else {
510 /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
511 leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
512 pos, cpy_num - 1);
513
514 /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
515 leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
516 cpy_num + pos - 1, cpy_bytes);
517 }
518 } else {
519 /* copy items to right */
520 src_nr_item = B_NR_ITEMS(src);
521 if (cpy_num == 1)
522 bytes = cpy_bytes;
523 else
524 bytes = -1;
525
526 /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
527 i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);
528
529 cpy_num -= i;
530 if (cpy_num == 0)
531 return i;
532
533 pos = src_nr_item - cpy_num - i;
534 if (cpy_bytes == -1) {
535 /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
536 leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
537 pos, cpy_num);
538 } else {
539 /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
540 leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
541 pos + 1, cpy_num - 1);
542
543 /* copy part of the item which number is pos to the begin of the DEST */
544 leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
545 cpy_bytes);
546 }
547 }
548 return i;
549 }
550
551 /* there are types of coping: from S[0] to L[0], from S[0] to R[0],
552 from R[0] to L[0]. for each of these we have to define parent and
553 positions of destination and source buffers */
554 static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
555 struct buffer_info *dest_bi,
556 struct buffer_info *src_bi,
557 int *first_last,
558 struct buffer_head *Snew)
559 {
560 memset(dest_bi, 0, sizeof(struct buffer_info));
561 memset(src_bi, 0, sizeof(struct buffer_info));
562
563 /* define dest, src, dest parent, dest position */
564 switch (shift_mode) {
565 case LEAF_FROM_S_TO_L: /* it is used in leaf_shift_left */
566 src_bi->tb = tb;
567 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
568 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
569 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0); /* src->b_item_order */
570 dest_bi->tb = tb;
571 dest_bi->bi_bh = tb->L[0];
572 dest_bi->bi_parent = tb->FL[0];
573 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
574 *first_last = FIRST_TO_LAST;
575 break;
576
577 case LEAF_FROM_S_TO_R: /* it is used in leaf_shift_right */
578 src_bi->tb = tb;
579 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
580 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
581 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
582 dest_bi->tb = tb;
583 dest_bi->bi_bh = tb->R[0];
584 dest_bi->bi_parent = tb->FR[0];
585 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
586 *first_last = LAST_TO_FIRST;
587 break;
588
589 case LEAF_FROM_R_TO_L: /* it is used in balance_leaf_when_delete */
590 src_bi->tb = tb;
591 src_bi->bi_bh = tb->R[0];
592 src_bi->bi_parent = tb->FR[0];
593 src_bi->bi_position = get_right_neighbor_position(tb, 0);
594 dest_bi->tb = tb;
595 dest_bi->bi_bh = tb->L[0];
596 dest_bi->bi_parent = tb->FL[0];
597 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
598 *first_last = FIRST_TO_LAST;
599 break;
600
601 case LEAF_FROM_L_TO_R: /* it is used in balance_leaf_when_delete */
602 src_bi->tb = tb;
603 src_bi->bi_bh = tb->L[0];
604 src_bi->bi_parent = tb->FL[0];
605 src_bi->bi_position = get_left_neighbor_position(tb, 0);
606 dest_bi->tb = tb;
607 dest_bi->bi_bh = tb->R[0];
608 dest_bi->bi_parent = tb->FR[0];
609 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
610 *first_last = LAST_TO_FIRST;
611 break;
612
613 case LEAF_FROM_S_TO_SNEW:
614 src_bi->tb = tb;
615 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
616 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
617 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
618 dest_bi->tb = tb;
619 dest_bi->bi_bh = Snew;
620 dest_bi->bi_parent = NULL;
621 dest_bi->bi_position = 0;
622 *first_last = LAST_TO_FIRST;
623 break;
624
625 default:
626 reiserfs_panic(sb_from_bi(src_bi), "vs-10250",
627 "shift type is unknown (%d)", shift_mode);
628 }
629 RFALSE(!src_bi->bi_bh || !dest_bi->bi_bh,
630 "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
631 shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
632 }
633
634 /* copy mov_num items and mov_bytes of the (mov_num-1)th item to
635 neighbor. Delete them from source */
636 int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
637 int mov_bytes, struct buffer_head *Snew)
638 {
639 int ret_value;
640 struct buffer_info dest_bi, src_bi;
641 int first_last;
642
643 leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
644 &first_last, Snew);
645
646 ret_value =
647 leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
648 mov_bytes);
649
650 leaf_delete_items(&src_bi, first_last,
651 (first_last ==
652 FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) -
653 mov_num), mov_num, mov_bytes);
654
655 return ret_value;
656 }
657
658 /* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1)
659 from S[0] to L[0] and replace the delimiting key */
660 int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
661 {
662 struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
663 int i;
664
665 /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */
666 i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL);
667
668 if (shift_num) {
669 if (B_NR_ITEMS(S0) == 0) { /* number of items in S[0] == 0 */
670
671 RFALSE(shift_bytes != -1,
672 "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
673 shift_bytes);
674 #ifdef CONFIG_REISERFS_CHECK
675 if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
676 print_cur_tb("vs-10275");
677 reiserfs_panic(tb->tb_sb, "vs-10275",
678 "balance condition corrupted "
679 "(%c)", tb->tb_mode);
680 }
681 #endif
682
683 if (PATH_H_POSITION(tb->tb_path, 1) == 0)
684 replace_key(tb, tb->CFL[0], tb->lkey[0],
685 PATH_H_PPARENT(tb->tb_path, 0), 0);
686
687 } else {
688 /* replace lkey in CFL[0] by 0-th key from S[0]; */
689 replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);
690
691 RFALSE((shift_bytes != -1 &&
692 !(is_direntry_le_ih(B_N_PITEM_HEAD(S0, 0))
693 && !I_ENTRY_COUNT(B_N_PITEM_HEAD(S0, 0)))) &&
694 (!op_is_left_mergeable
695 (B_N_PKEY(S0, 0), S0->b_size)),
696 "vs-10280: item must be mergeable");
697 }
698 }
699
700 return i;
701 }
702
703 /* CLEANING STOPPED HERE */
704
705 /* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
706 int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
707 {
708 // struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
709 int ret_value;
710
711 /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */
712 ret_value =
713 leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL);
714
715 /* replace rkey in CFR[0] by the 0-th key from R[0] */
716 if (shift_num) {
717 replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
718
719 }
720
721 return ret_value;
722 }
723
724 static void leaf_delete_items_entirely(struct buffer_info *bi,
725 int first, int del_num);
726 /* If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
727 If not.
728 If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of
729 the first item. Part defined by del_bytes. Don't delete first item header
730 If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of
731 the last item . Part defined by del_bytes. Don't delete last item header.
732 */
733 void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
734 int first, int del_num, int del_bytes)
735 {
736 struct buffer_head *bh;
737 int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);
738
739 RFALSE(!bh, "10155: bh is not defined");
740 RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d",
741 del_num);
742 RFALSE(first < 0
743 || first + del_num > item_amount,
744 "10165: invalid number of first item to be deleted (%d) or "
745 "no so much items (%d) to delete (only %d)", first,
746 first + del_num, item_amount);
747
748 if (del_num == 0)
749 return;
750
751 if (first == 0 && del_num == item_amount && del_bytes == -1) {
752 make_empty_node(cur_bi);
753 do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0);
754 return;
755 }
756
757 if (del_bytes == -1)
758 /* delete del_num items beginning from item in position first */
759 leaf_delete_items_entirely(cur_bi, first, del_num);
760 else {
761 if (last_first == FIRST_TO_LAST) {
762 /* delete del_num-1 items beginning from item in position first */
763 leaf_delete_items_entirely(cur_bi, first, del_num - 1);
764
765 /* delete the part of the first item of the bh
766 do not delete item header
767 */
768 leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes);
769 } else {
770 struct item_head *ih;
771 int len;
772
773 /* delete del_num-1 items beginning from item in position first+1 */
774 leaf_delete_items_entirely(cur_bi, first + 1,
775 del_num - 1);
776
777 if (is_direntry_le_ih
778 (ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh) - 1)))
779 /* the last item is directory */
780 /* len = numbers of directory entries in this item */
781 len = ih_entry_count(ih);
782 else
783 /* len = body len of item */
784 len = ih_item_len(ih);
785
786 /* delete the part of the last item of the bh
787 do not delete item header
788 */
789 leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1,
790 len - del_bytes, del_bytes);
791 }
792 }
793 }
794
795 /* insert item into the leaf node in position before */
796 void leaf_insert_into_buf(struct buffer_info *bi, int before,
797 struct item_head *inserted_item_ih,
798 const char *inserted_item_body, int zeros_number)
799 {
800 struct buffer_head *bh = bi->bi_bh;
801 int nr, free_space;
802 struct block_head *blkh;
803 struct item_head *ih;
804 int i;
805 int last_loc, unmoved_loc;
806 char *to;
807
808 blkh = B_BLK_HEAD(bh);
809 nr = blkh_nr_item(blkh);
810 free_space = blkh_free_space(blkh);
811
812 /* check free space */
813 RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
814 "vs-10170: not enough free space in block %z, new item %h",
815 bh, inserted_item_ih);
816 RFALSE(zeros_number > ih_item_len(inserted_item_ih),
817 "vs-10172: zero number == %d, item length == %d",
818 zeros_number, ih_item_len(inserted_item_ih));
819
820 /* get item new item must be inserted before */
821 ih = B_N_PITEM_HEAD(bh, before);
822
823 /* prepare space for the body of new item */
824 last_loc = nr ? ih_location(&(ih[nr - before - 1])) : bh->b_size;
825 unmoved_loc = before ? ih_location(ih - 1) : bh->b_size;
826
827 memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
828 bh->b_data + last_loc, unmoved_loc - last_loc);
829
830 to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
831 memset(to, 0, zeros_number);
832 to += zeros_number;
833
834 /* copy body to prepared space */
835 if (inserted_item_body)
836 memmove(to, inserted_item_body,
837 ih_item_len(inserted_item_ih) - zeros_number);
838 else
839 memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number);
840
841 /* insert item header */
842 memmove(ih + 1, ih, IH_SIZE * (nr - before));
843 memmove(ih, inserted_item_ih, IH_SIZE);
844
845 /* change locations */
846 for (i = before; i < nr + 1; i++) {
847 unmoved_loc -= ih_item_len(&(ih[i - before]));
848 put_ih_location(&(ih[i - before]), unmoved_loc);
849 }
850
851 /* sizes, free space, item number */
852 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
853 set_blkh_free_space(blkh,
854 free_space - (IH_SIZE +
855 ih_item_len(inserted_item_ih)));
856 do_balance_mark_leaf_dirty(bi->tb, bh, 1);
857
858 if (bi->bi_parent) {
859 struct disk_child *t_dc;
860 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
861 put_dc_size(t_dc,
862 dc_size(t_dc) + (IH_SIZE +
863 ih_item_len(inserted_item_ih)));
864 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
865 }
866 }
867
868 /* paste paste_size bytes to affected_item_num-th item.
869 When item is a directory, this only prepare space for new entries */
870 void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num,
871 int pos_in_item, int paste_size,
872 const char *body, int zeros_number)
873 {
874 struct buffer_head *bh = bi->bi_bh;
875 int nr, free_space;
876 struct block_head *blkh;
877 struct item_head *ih;
878 int i;
879 int last_loc, unmoved_loc;
880
881 blkh = B_BLK_HEAD(bh);
882 nr = blkh_nr_item(blkh);
883 free_space = blkh_free_space(blkh);
884
885 /* check free space */
886 RFALSE(free_space < paste_size,
887 "vs-10175: not enough free space: needed %d, available %d",
888 paste_size, free_space);
889
890 #ifdef CONFIG_REISERFS_CHECK
891 if (zeros_number > paste_size) {
892 struct super_block *sb = NULL;
893 if (bi && bi->tb)
894 sb = bi->tb->tb_sb;
895 print_cur_tb("10177");
896 reiserfs_panic(sb, "vs-10177",
897 "zeros_number == %d, paste_size == %d",
898 zeros_number, paste_size);
899 }
900 #endif /* CONFIG_REISERFS_CHECK */
901
902 /* item to be appended */
903 ih = B_N_PITEM_HEAD(bh, affected_item_num);
904
905 last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
906 unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
907
908 /* prepare space */
909 memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
910 unmoved_loc - last_loc);
911
912 /* change locations */
913 for (i = affected_item_num; i < nr; i++)
914 put_ih_location(&(ih[i - affected_item_num]),
915 ih_location(&(ih[i - affected_item_num])) -
916 paste_size);
917
918 if (body) {
919 if (!is_direntry_le_ih(ih)) {
920 if (!pos_in_item) {
921 /* shift data to right */
922 memmove(bh->b_data + ih_location(ih) +
923 paste_size,
924 bh->b_data + ih_location(ih),
925 ih_item_len(ih));
926 /* paste data in the head of item */
927 memset(bh->b_data + ih_location(ih), 0,
928 zeros_number);
929 memcpy(bh->b_data + ih_location(ih) +
930 zeros_number, body,
931 paste_size - zeros_number);
932 } else {
933 memset(bh->b_data + unmoved_loc - paste_size, 0,
934 zeros_number);
935 memcpy(bh->b_data + unmoved_loc - paste_size +
936 zeros_number, body,
937 paste_size - zeros_number);
938 }
939 }
940 } else
941 memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
942
943 put_ih_item_len(ih, ih_item_len(ih) + paste_size);
944
945 /* change free space */
946 set_blkh_free_space(blkh, free_space - paste_size);
947
948 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
949
950 if (bi->bi_parent) {
951 struct disk_child *t_dc =
952 B_N_CHILD(bi->bi_parent, bi->bi_position);
953 put_dc_size(t_dc, dc_size(t_dc) + paste_size);
954 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
955 }
956 }
957
958 /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
959 does not have free space, so it moves DEHs and remaining records as
960 necessary. Return value is size of removed part of directory item
961 in bytes. */
962 static int leaf_cut_entries(struct buffer_head *bh,
963 struct item_head *ih, int from, int del_count)
964 {
965 char *item;
966 struct reiserfs_de_head *deh;
967 int prev_record_offset; /* offset of record, that is (from-1)th */
968 char *prev_record; /* */
969 int cut_records_len; /* length of all removed records */
970 int i;
971
972 /* make sure, that item is directory and there are enough entries to
973 remove */
974 RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
975 RFALSE(I_ENTRY_COUNT(ih) < from + del_count,
976 "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
977 I_ENTRY_COUNT(ih), from, del_count);
978
979 if (del_count == 0)
980 return 0;
981
982 /* first byte of item */
983 item = bh->b_data + ih_location(ih);
984
985 /* entry head array */
986 deh = B_I_DEH(bh, ih);
987
988 /* first byte of remaining entries, those are BEFORE cut entries
989 (prev_record) and length of all removed records (cut_records_len) */
990 prev_record_offset =
991 (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih));
992 cut_records_len = prev_record_offset /*from_record */ -
993 deh_location(&(deh[from + del_count - 1]));
994 prev_record = item + prev_record_offset;
995
996 /* adjust locations of remaining entries */
997 for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--)
998 put_deh_location(&(deh[i]),
999 deh_location(&deh[i]) -
1000 (DEH_SIZE * del_count));
1001
1002 for (i = 0; i < from; i++)
1003 put_deh_location(&(deh[i]),
1004 deh_location(&deh[i]) - (DEH_SIZE * del_count +
1005 cut_records_len));
1006
1007 put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
1008
1009 /* shift entry head array and entries those are AFTER removed entries */
1010 memmove((char *)(deh + from),
1011 deh + from + del_count,
1012 prev_record - cut_records_len - (char *)(deh + from +
1013 del_count));
1014
1015 /* shift records, those are BEFORE removed entries */
1016 memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
1017 prev_record, item + ih_item_len(ih) - prev_record);
1018
1019 return DEH_SIZE * del_count + cut_records_len;
1020 }
1021
1022 /* when cut item is part of regular file
1023 pos_in_item - first byte that must be cut
1024 cut_size - number of bytes to be cut beginning from pos_in_item
1025
1026 when cut item is part of directory
1027 pos_in_item - number of first deleted entry
1028 cut_size - count of deleted entries
1029 */
1030 void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
1031 int pos_in_item, int cut_size)
1032 {
1033 int nr;
1034 struct buffer_head *bh = bi->bi_bh;
1035 struct block_head *blkh;
1036 struct item_head *ih;
1037 int last_loc, unmoved_loc;
1038 int i;
1039
1040 blkh = B_BLK_HEAD(bh);
1041 nr = blkh_nr_item(blkh);
1042
1043 /* item head of truncated item */
1044 ih = B_N_PITEM_HEAD(bh, cut_item_num);
1045
1046 if (is_direntry_le_ih(ih)) {
1047 /* first cut entry () */
1048 cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
1049 if (pos_in_item == 0) {
1050 /* change key */
1051 RFALSE(cut_item_num,
1052 "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
1053 cut_item_num);
1054 /* change item key by key of first entry in the item */
1055 set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
1056 /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */
1057 }
1058 } else {
1059 /* item is direct or indirect */
1060 RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
1061 RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
1062 "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
1063 (long unsigned)pos_in_item, (long unsigned)cut_size,
1064 (long unsigned)ih_item_len(ih));
1065
1066 /* shift item body to left if cut is from the head of item */
1067 if (pos_in_item == 0) {
1068 memmove(bh->b_data + ih_location(ih),
1069 bh->b_data + ih_location(ih) + cut_size,
1070 ih_item_len(ih) - cut_size);
1071
1072 /* change key of item */
1073 if (is_direct_le_ih(ih))
1074 set_le_ih_k_offset(ih,
1075 le_ih_k_offset(ih) +
1076 cut_size);
1077 else {
1078 set_le_ih_k_offset(ih,
1079 le_ih_k_offset(ih) +
1080 (cut_size / UNFM_P_SIZE) *
1081 bh->b_size);
1082 RFALSE(ih_item_len(ih) == cut_size
1083 && get_ih_free_space(ih),
1084 "10205: invalid ih_free_space (%h)", ih);
1085 }
1086 }
1087 }
1088
1089 /* location of the last item */
1090 last_loc = ih_location(&(ih[nr - cut_item_num - 1]));
1091
1092 /* location of the item, which is remaining at the same place */
1093 unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
1094
1095 /* shift */
1096 memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1097 unmoved_loc - last_loc - cut_size);
1098
1099 /* change item length */
1100 put_ih_item_len(ih, ih_item_len(ih) - cut_size);
1101
1102 if (is_indirect_le_ih(ih)) {
1103 if (pos_in_item)
1104 set_ih_free_space(ih, 0);
1105 }
1106
1107 /* change locations */
1108 for (i = cut_item_num; i < nr; i++)
1109 put_ih_location(&(ih[i - cut_item_num]),
1110 ih_location(&ih[i - cut_item_num]) + cut_size);
1111
1112 /* size, free space */
1113 set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
1114
1115 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1116
1117 if (bi->bi_parent) {
1118 struct disk_child *t_dc;
1119 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
1120 put_dc_size(t_dc, dc_size(t_dc) - cut_size);
1121 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1122 }
1123 }
1124
1125 /* delete del_num items from buffer starting from the first'th item */
1126 static void leaf_delete_items_entirely(struct buffer_info *bi,
1127 int first, int del_num)
1128 {
1129 struct buffer_head *bh = bi->bi_bh;
1130 int nr;
1131 int i, j;
1132 int last_loc, last_removed_loc;
1133 struct block_head *blkh;
1134 struct item_head *ih;
1135
1136 RFALSE(bh == NULL, "10210: buffer is 0");
1137 RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
1138
1139 if (del_num == 0)
1140 return;
1141
1142 blkh = B_BLK_HEAD(bh);
1143 nr = blkh_nr_item(blkh);
1144
1145 RFALSE(first < 0 || first + del_num > nr,
1146 "10220: first=%d, number=%d, there is %d items", first, del_num,
1147 nr);
1148
1149 if (first == 0 && del_num == nr) {
1150 /* this does not work */
1151 make_empty_node(bi);
1152
1153 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1154 return;
1155 }
1156
1157 ih = B_N_PITEM_HEAD(bh, first);
1158
1159 /* location of unmovable item */
1160 j = (first == 0) ? bh->b_size : ih_location(ih - 1);
1161
1162 /* delete items */
1163 last_loc = ih_location(&(ih[nr - 1 - first]));
1164 last_removed_loc = ih_location(&(ih[del_num - 1]));
1165
1166 memmove(bh->b_data + last_loc + j - last_removed_loc,
1167 bh->b_data + last_loc, last_removed_loc - last_loc);
1168
1169 /* delete item headers */
1170 memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1171
1172 /* change item location */
1173 for (i = first; i < nr - del_num; i++)
1174 put_ih_location(&(ih[i - first]),
1175 ih_location(&(ih[i - first])) + (j -
1176 last_removed_loc));
1177
1178 /* sizes, item number */
1179 set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
1180 set_blkh_free_space(blkh,
1181 blkh_free_space(blkh) + (j - last_removed_loc +
1182 IH_SIZE * del_num));
1183
1184 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1185
1186 if (bi->bi_parent) {
1187 struct disk_child *t_dc =
1188 B_N_CHILD(bi->bi_parent, bi->bi_position);
1189 put_dc_size(t_dc,
1190 dc_size(t_dc) - (j - last_removed_loc +
1191 IH_SIZE * del_num));
1192 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1193 }
1194 }
1195
1196 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
1197 void leaf_paste_entries(struct buffer_info *bi,
1198 int item_num,
1199 int before,
1200 int new_entry_count,
1201 struct reiserfs_de_head *new_dehs,
1202 const char *records, int paste_size)
1203 {
1204 struct item_head *ih;
1205 char *item;
1206 struct reiserfs_de_head *deh;
1207 char *insert_point;
1208 int i, old_entry_num;
1209 struct buffer_head *bh = bi->bi_bh;
1210
1211 if (new_entry_count == 0)
1212 return;
1213
1214 ih = B_N_PITEM_HEAD(bh, item_num);
1215
1216 /* make sure, that item is directory, and there are enough records in it */
1217 RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
1218 RFALSE(I_ENTRY_COUNT(ih) < before,
1219 "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
1220 I_ENTRY_COUNT(ih), before);
1221
1222 /* first byte of dest item */
1223 item = bh->b_data + ih_location(ih);
1224
1225 /* entry head array */
1226 deh = B_I_DEH(bh, ih);
1227
1228 /* new records will be pasted at this point */
1229 insert_point =
1230 item +
1231 (before ? deh_location(&(deh[before - 1]))
1232 : (ih_item_len(ih) - paste_size));
1233
1234 /* adjust locations of records that will be AFTER new records */
1235 for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--)
1236 put_deh_location(&(deh[i]),
1237 deh_location(&(deh[i])) +
1238 (DEH_SIZE * new_entry_count));
1239
1240 /* adjust locations of records that will be BEFORE new records */
1241 for (i = 0; i < before; i++)
1242 put_deh_location(&(deh[i]),
1243 deh_location(&(deh[i])) + paste_size);
1244
1245 old_entry_num = I_ENTRY_COUNT(ih);
1246 put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
1247
1248 /* prepare space for pasted records */
1249 memmove(insert_point + paste_size, insert_point,
1250 item + (ih_item_len(ih) - paste_size) - insert_point);
1251
1252 /* copy new records */
1253 memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1254 paste_size - DEH_SIZE * new_entry_count);
1255
1256 /* prepare space for new entry heads */
1257 deh += before;
1258 memmove((char *)(deh + new_entry_count), deh,
1259 insert_point - (char *)deh);
1260
1261 /* copy new entry heads */
1262 deh = (struct reiserfs_de_head *)((char *)deh);
1263 memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
1264
1265 /* set locations of new records */
1266 for (i = 0; i < new_entry_count; i++) {
1267 put_deh_location(&(deh[i]),
1268 deh_location(&(deh[i])) +
1269 (-deh_location
1270 (&(new_dehs[new_entry_count - 1])) +
1271 insert_point + DEH_SIZE * new_entry_count -
1272 item));
1273 }
1274
1275 /* change item key if necessary (when we paste before 0-th entry */
1276 if (!before) {
1277 set_le_ih_k_offset(ih, deh_offset(new_dehs));
1278 /* memcpy (&ih->ih_key.k_offset,
1279 &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
1280 }
1281 #ifdef CONFIG_REISERFS_CHECK
1282 {
1283 int prev, next;
1284 /* check record locations */
1285 deh = B_I_DEH(bh, ih);
1286 for (i = 0; i < I_ENTRY_COUNT(ih); i++) {
1287 next =
1288 (i <
1289 I_ENTRY_COUNT(ih) -
1290 1) ? deh_location(&(deh[i + 1])) : 0;
1291 prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0;
1292
1293 if (prev && prev <= deh_location(&(deh[i])))
1294 reiserfs_error(sb_from_bi(bi), "vs-10240",
1295 "directory item (%h) "
1296 "corrupted (prev %a, "
1297 "cur(%d) %a)",
1298 ih, deh + i - 1, i, deh + i);
1299 if (next && next >= deh_location(&(deh[i])))
1300 reiserfs_error(sb_from_bi(bi), "vs-10250",
1301 "directory item (%h) "
1302 "corrupted (cur(%d) %a, "
1303 "next %a)",
1304 ih, i, deh + i, deh + i + 1);
1305 }
1306 }
1307 #endif
1308
1309 }
Linux ACPI git tree (mirror)