Merge git://git.kernel.org/pub/scm/linux/kernel/git/sam/kbuild
[linux-2.6] / fs / reiserfs / lbalance.c
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->bi_bh, 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(NULL,
172                                                        "vs-10020: leaf_copy_boundary_item: "
173                                                        "last unformatted node must be filled entirely (%h)",
174                                                        ih);
175                 }
176 #endif
177
178                 /* merge first item (or its part) of src buffer with the last
179                    item of dest buffer. Both are of the same file */
180                 leaf_paste_in_buffer(dest_bi,
181                                      dest_nr_item - 1, ih_item_len(dih),
182                                      bytes_or_entries, B_I_PITEM(src, ih), 0);
183
184                 if (is_indirect_le_ih(dih)) {
185                         RFALSE(get_ih_free_space(dih),
186                                "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
187                                ih);
188                         if (bytes_or_entries == ih_item_len(ih))
189                                 set_ih_free_space(dih, get_ih_free_space(ih));
190                 }
191
192                 return 1;
193         }
194
195         /* copy boundary item to right (last_first == LAST_TO_FIRST) */
196
197         /* ( DEST is empty or last item of SOURCE and first item of DEST
198            are the items of different object or of different types )
199          */
200         src_nr_item = B_NR_ITEMS(src);
201         ih = B_N_PITEM_HEAD(src, src_nr_item - 1);
202         dih = B_N_PITEM_HEAD(dest, 0);
203
204         if (!dest_nr_item || !op_is_left_mergeable(&(dih->ih_key), src->b_size))
205                 return 0;
206
207         if (is_direntry_le_ih(ih)) {
208                 if (bytes_or_entries == -1)
209                         /* bytes_or_entries = entries number in last item body of SOURCE */
210                         bytes_or_entries = ih_entry_count(ih);
211
212                 leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
213                                       src_nr_item - 1,
214                                       ih_entry_count(ih) - bytes_or_entries,
215                                       bytes_or_entries);
216                 return 1;
217         }
218
219         /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST;
220            part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST;
221            don't create new item header
222          */
223
224         RFALSE(is_indirect_le_ih(ih) && get_ih_free_space(ih),
225                "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
226                ih);
227
228         if (bytes_or_entries == -1) {
229                 /* bytes_or_entries = length of last item body of SOURCE */
230                 bytes_or_entries = ih_item_len(ih);
231
232                 RFALSE(le_ih_k_offset(dih) !=
233                        le_ih_k_offset(ih) + op_bytes_number(ih, src->b_size),
234                        "vs-10050: items %h and %h do not match", ih, dih);
235
236                 /* change first item key of the DEST */
237                 set_le_ih_k_offset(dih, le_ih_k_offset(ih));
238
239                 /* item becomes non-mergeable */
240                 /* or mergeable if left item was */
241                 set_le_ih_k_type(dih, le_ih_k_type(ih));
242         } else {
243                 /* merge to right only part of item */
244                 RFALSE(ih_item_len(ih) <= bytes_or_entries,
245                        "vs-10060: no so much bytes %lu (needed %lu)",
246                        (unsigned long)ih_item_len(ih),
247                        (unsigned long)bytes_or_entries);
248
249                 /* change first item key of the DEST */
250                 if (is_direct_le_ih(dih)) {
251                         RFALSE(le_ih_k_offset(dih) <=
252                                (unsigned long)bytes_or_entries,
253                                "vs-10070: dih %h, bytes_or_entries(%d)", dih,
254                                bytes_or_entries);
255                         set_le_ih_k_offset(dih,
256                                            le_ih_k_offset(dih) -
257                                            bytes_or_entries);
258                 } else {
259                         RFALSE(le_ih_k_offset(dih) <=
260                                (bytes_or_entries / UNFM_P_SIZE) * dest->b_size,
261                                "vs-10080: dih %h, bytes_or_entries(%d)",
262                                dih,
263                                (bytes_or_entries / UNFM_P_SIZE) * dest->b_size);
264                         set_le_ih_k_offset(dih,
265                                            le_ih_k_offset(dih) -
266                                            ((bytes_or_entries / UNFM_P_SIZE) *
267                                             dest->b_size));
268                 }
269         }
270
271         leaf_paste_in_buffer(dest_bi, 0, 0, bytes_or_entries,
272                              B_I_PITEM(src,
273                                        ih) + ih_item_len(ih) - bytes_or_entries,
274                              0);
275         return 1;
276 }
277
278 /* copy cpy_mun items from buffer src to buffer dest
279  * last_first == FIRST_TO_LAST means, that we copy cpy_num  items beginning from first-th item in src to tail of dest
280  * last_first == LAST_TO_FIRST means, that we copy cpy_num  items beginning from first-th item in src to head of dest
281  */
282 static void leaf_copy_items_entirely(struct buffer_info *dest_bi,
283                                      struct buffer_head *src, int last_first,
284                                      int first, int cpy_num)
285 {
286         struct buffer_head *dest;
287         int nr, free_space;
288         int dest_before;
289         int last_loc, last_inserted_loc, location;
290         int i, j;
291         struct block_head *blkh;
292         struct item_head *ih;
293
294         RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST,
295                "vs-10090: bad last_first parameter %d", last_first);
296         RFALSE(B_NR_ITEMS(src) - first < cpy_num,
297                "vs-10100: too few items in source %d, required %d from %d",
298                B_NR_ITEMS(src), cpy_num, first);
299         RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items");
300         RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items");
301
302         dest = dest_bi->bi_bh;
303
304         RFALSE(!dest, "vs-10130: can not copy negative amount of items");
305
306         if (cpy_num == 0)
307                 return;
308
309         blkh = B_BLK_HEAD(dest);
310         nr = blkh_nr_item(blkh);
311         free_space = blkh_free_space(blkh);
312
313         /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */
314         dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;
315
316         /* location of head of first new item */
317         ih = B_N_PITEM_HEAD(dest, dest_before);
318
319         RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE,
320                "vs-10140: not enough free space for headers %d (needed %d)",
321                B_FREE_SPACE(dest), cpy_num * IH_SIZE);
322
323         /* prepare space for headers */
324         memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE);
325
326         /* copy item headers */
327         memcpy(ih, B_N_PITEM_HEAD(src, first), cpy_num * IH_SIZE);
328
329         free_space -= (IH_SIZE * cpy_num);
330         set_blkh_free_space(blkh, free_space);
331
332         /* location of unmovable item */
333         j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1);
334         for (i = dest_before; i < nr + cpy_num; i++) {
335                 location -= ih_item_len(ih + i - dest_before);
336                 put_ih_location(ih + i - dest_before, location);
337         }
338
339         /* prepare space for items */
340         last_loc = ih_location(&(ih[nr + cpy_num - 1 - dest_before]));
341         last_inserted_loc = ih_location(&(ih[cpy_num - 1]));
342
343         /* check free space */
344         RFALSE(free_space < j - last_inserted_loc,
345                "vs-10150: not enough free space for items %d (needed %d)",
346                free_space, j - last_inserted_loc);
347
348         memmove(dest->b_data + last_loc,
349                 dest->b_data + last_loc + j - last_inserted_loc,
350                 last_inserted_loc - last_loc);
351
352         /* copy items */
353         memcpy(dest->b_data + last_inserted_loc,
354                B_N_PITEM(src, (first + cpy_num - 1)), j - last_inserted_loc);
355
356         /* sizes, item number */
357         set_blkh_nr_item(blkh, nr + cpy_num);
358         set_blkh_free_space(blkh, free_space - (j - last_inserted_loc));
359
360         do_balance_mark_leaf_dirty(dest_bi->tb, dest, 0);
361
362         if (dest_bi->bi_parent) {
363                 struct disk_child *t_dc;
364                 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
365                 RFALSE(dc_block_number(t_dc) != dest->b_blocknr,
366                        "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu",
367                        (long unsigned)dest->b_blocknr,
368                        (long unsigned)dc_block_number(t_dc));
369                 put_dc_size(t_dc,
370                             dc_size(t_dc) + (j - last_inserted_loc +
371                                              IH_SIZE * cpy_num));
372
373                 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
374                                                0);
375         }
376 }
377
378 /* This function splits the (liquid) item into two items (useful when
379    shifting part of an item into another node.) */
380 static void leaf_item_bottle(struct buffer_info *dest_bi,
381                              struct buffer_head *src, int last_first,
382                              int item_num, int cpy_bytes)
383 {
384         struct buffer_head *dest = dest_bi->bi_bh;
385         struct item_head *ih;
386
387         RFALSE(cpy_bytes == -1,
388                "vs-10170: bytes == - 1 means: do not split item");
389
390         if (last_first == FIRST_TO_LAST) {
391                 /* if ( if item in position item_num in buffer SOURCE is directory item ) */
392                 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
393                         leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
394                                               item_num, 0, cpy_bytes);
395                 else {
396                         struct item_head n_ih;
397
398                         /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST 
399                            part defined by 'cpy_bytes'; create new item header; change old item_header (????);
400                            n_ih = new item_header;
401                          */
402                         memcpy(&n_ih, ih, IH_SIZE);
403                         put_ih_item_len(&n_ih, cpy_bytes);
404                         if (is_indirect_le_ih(ih)) {
405                                 RFALSE(cpy_bytes == ih_item_len(ih)
406                                        && get_ih_free_space(ih),
407                                        "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
408                                        (long unsigned)get_ih_free_space(ih));
409                                 set_ih_free_space(&n_ih, 0);
410                         }
411
412                         RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size),
413                                "vs-10190: bad mergeability of item %h", ih);
414                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
415                         leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
416                                              B_N_PITEM(src, item_num), 0);
417                 }
418         } else {
419                 /*  if ( if item in position item_num in buffer SOURCE is directory item ) */
420                 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
421                         leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
422                                               item_num,
423                                               I_ENTRY_COUNT(ih) - cpy_bytes,
424                                               cpy_bytes);
425                 else {
426                         struct item_head n_ih;
427
428                         /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST 
429                            part defined by 'cpy_bytes'; create new item header;
430                            n_ih = new item_header;
431                          */
432                         memcpy(&n_ih, ih, SHORT_KEY_SIZE);
433
434                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
435
436                         if (is_direct_le_ih(ih)) {
437                                 set_le_ih_k_offset(&n_ih,
438                                                    le_ih_k_offset(ih) +
439                                                    ih_item_len(ih) - cpy_bytes);
440                                 set_le_ih_k_type(&n_ih, TYPE_DIRECT);
441                                 set_ih_free_space(&n_ih, MAX_US_INT);
442                         } else {
443                                 /* indirect item */
444                                 RFALSE(!cpy_bytes && get_ih_free_space(ih),
445                                        "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
446                                 set_le_ih_k_offset(&n_ih,
447                                                    le_ih_k_offset(ih) +
448                                                    (ih_item_len(ih) -
449                                                     cpy_bytes) / UNFM_P_SIZE *
450                                                    dest->b_size);
451                                 set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
452                                 set_ih_free_space(&n_ih, get_ih_free_space(ih));
453                         }
454
455                         /* set item length */
456                         put_ih_item_len(&n_ih, cpy_bytes);
457
458                         n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
459
460                         leaf_insert_into_buf(dest_bi, 0, &n_ih,
461                                              B_N_PITEM(src,
462                                                        item_num) +
463                                              ih_item_len(ih) - cpy_bytes, 0);
464                 }
465         }
466 }
467
468 /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
469    If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
470    From last item copy cpy_num bytes for regular item and cpy_num directory entries for
471    directory item. */
472 static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
473                            int last_first, int cpy_num, int cpy_bytes)
474 {
475         struct buffer_head *dest;
476         int pos, i, src_nr_item, bytes;
477
478         dest = dest_bi->bi_bh;
479         RFALSE(!dest || !src, "vs-10210: !dest || !src");
480         RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
481                "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
482         RFALSE(B_NR_ITEMS(src) < cpy_num,
483                "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
484                cpy_num);
485         RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);
486
487         if (cpy_num == 0)
488                 return 0;
489
490         if (last_first == FIRST_TO_LAST) {
491                 /* copy items to left */
492                 pos = 0;
493                 if (cpy_num == 1)
494                         bytes = cpy_bytes;
495                 else
496                         bytes = -1;
497
498                 /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
499                 i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
500                 cpy_num -= i;
501                 if (cpy_num == 0)
502                         return i;
503                 pos += i;
504                 if (cpy_bytes == -1)
505                         /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
506                         leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
507                                                  pos, cpy_num);
508                 else {
509                         /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
510                         leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
511                                                  pos, cpy_num - 1);
512
513                         /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
514                         leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
515                                          cpy_num + pos - 1, cpy_bytes);
516                 }
517         } else {
518                 /* copy items to right */
519                 src_nr_item = B_NR_ITEMS(src);
520                 if (cpy_num == 1)
521                         bytes = cpy_bytes;
522                 else
523                         bytes = -1;
524
525                 /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
526                 i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);
527
528                 cpy_num -= i;
529                 if (cpy_num == 0)
530                         return i;
531
532                 pos = src_nr_item - cpy_num - i;
533                 if (cpy_bytes == -1) {
534                         /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
535                         leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
536                                                  pos, cpy_num);
537                 } else {
538                         /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
539                         leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
540                                                  pos + 1, cpy_num - 1);
541
542                         /* copy part of the item which number is pos to the begin of the DEST */
543                         leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
544                                          cpy_bytes);
545                 }
546         }
547         return i;
548 }
549
550 /* there are types of coping: from S[0] to L[0], from S[0] to R[0],
551    from R[0] to L[0]. for each of these we have to define parent and
552    positions of destination and source buffers */
553 static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
554                                        struct buffer_info *dest_bi,
555                                        struct buffer_info *src_bi,
556                                        int *first_last,
557                                        struct buffer_head *Snew)
558 {
559         memset(dest_bi, 0, sizeof(struct buffer_info));
560         memset(src_bi, 0, sizeof(struct buffer_info));
561
562         /* define dest, src, dest parent, dest position */
563         switch (shift_mode) {
564         case LEAF_FROM_S_TO_L:  /* it is used in leaf_shift_left */
565                 src_bi->tb = tb;
566                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
567                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
568                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);      /* src->b_item_order */
569                 dest_bi->tb = tb;
570                 dest_bi->bi_bh = tb->L[0];
571                 dest_bi->bi_parent = tb->FL[0];
572                 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
573                 *first_last = FIRST_TO_LAST;
574                 break;
575
576         case LEAF_FROM_S_TO_R:  /* it is used in leaf_shift_right */
577                 src_bi->tb = tb;
578                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
579                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
580                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
581                 dest_bi->tb = tb;
582                 dest_bi->bi_bh = tb->R[0];
583                 dest_bi->bi_parent = tb->FR[0];
584                 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
585                 *first_last = LAST_TO_FIRST;
586                 break;
587
588         case LEAF_FROM_R_TO_L:  /* it is used in balance_leaf_when_delete */
589                 src_bi->tb = tb;
590                 src_bi->bi_bh = tb->R[0];
591                 src_bi->bi_parent = tb->FR[0];
592                 src_bi->bi_position = get_right_neighbor_position(tb, 0);
593                 dest_bi->tb = tb;
594                 dest_bi->bi_bh = tb->L[0];
595                 dest_bi->bi_parent = tb->FL[0];
596                 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
597                 *first_last = FIRST_TO_LAST;
598                 break;
599
600         case LEAF_FROM_L_TO_R:  /* it is used in balance_leaf_when_delete */
601                 src_bi->tb = tb;
602                 src_bi->bi_bh = tb->L[0];
603                 src_bi->bi_parent = tb->FL[0];
604                 src_bi->bi_position = get_left_neighbor_position(tb, 0);
605                 dest_bi->tb = tb;
606                 dest_bi->bi_bh = tb->R[0];
607                 dest_bi->bi_parent = tb->FR[0];
608                 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
609                 *first_last = LAST_TO_FIRST;
610                 break;
611
612         case LEAF_FROM_S_TO_SNEW:
613                 src_bi->tb = tb;
614                 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
615                 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
616                 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
617                 dest_bi->tb = tb;
618                 dest_bi->bi_bh = Snew;
619                 dest_bi->bi_parent = NULL;
620                 dest_bi->bi_position = 0;
621                 *first_last = LAST_TO_FIRST;
622                 break;
623
624         default:
625                 reiserfs_panic(NULL,
626                                "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)",
627                                shift_mode);
628         }
629         RFALSE(src_bi->bi_bh == 0 || dest_bi->bi_bh == 0,
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,
678                                                "vs-10275: leaf_shift_left: balance condition corrupted (%c)",
679                                                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                 print_cur_tb("10177");
893                 reiserfs_panic(NULL,
894                                "vs-10177: leaf_paste_in_buffer: ero number == %d, paste_size == %d",
895                                zeros_number, paste_size);
896         }
897 #endif                          /* CONFIG_REISERFS_CHECK */
898
899         /* item to be appended */
900         ih = B_N_PITEM_HEAD(bh, affected_item_num);
901
902         last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
903         unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
904
905         /* prepare space */
906         memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
907                 unmoved_loc - last_loc);
908
909         /* change locations */
910         for (i = affected_item_num; i < nr; i++)
911                 put_ih_location(&(ih[i - affected_item_num]),
912                                 ih_location(&(ih[i - affected_item_num])) -
913                                 paste_size);
914
915         if (body) {
916                 if (!is_direntry_le_ih(ih)) {
917                         if (!pos_in_item) {
918                                 /* shift data to right */
919                                 memmove(bh->b_data + ih_location(ih) +
920                                         paste_size,
921                                         bh->b_data + ih_location(ih),
922                                         ih_item_len(ih));
923                                 /* paste data in the head of item */
924                                 memset(bh->b_data + ih_location(ih), 0,
925                                        zeros_number);
926                                 memcpy(bh->b_data + ih_location(ih) +
927                                        zeros_number, body,
928                                        paste_size - zeros_number);
929                         } else {
930                                 memset(bh->b_data + unmoved_loc - paste_size, 0,
931                                        zeros_number);
932                                 memcpy(bh->b_data + unmoved_loc - paste_size +
933                                        zeros_number, body,
934                                        paste_size - zeros_number);
935                         }
936                 }
937         } else
938                 memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
939
940         put_ih_item_len(ih, ih_item_len(ih) + paste_size);
941
942         /* change free space */
943         set_blkh_free_space(blkh, free_space - paste_size);
944
945         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
946
947         if (bi->bi_parent) {
948                 struct disk_child *t_dc =
949                     B_N_CHILD(bi->bi_parent, bi->bi_position);
950                 put_dc_size(t_dc, dc_size(t_dc) + paste_size);
951                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
952         }
953 }
954
955 /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
956    does not have free space, so it moves DEHs and remaining records as
957    necessary. Return value is size of removed part of directory item
958    in bytes. */
959 static int leaf_cut_entries(struct buffer_head *bh,
960                             struct item_head *ih, int from, int del_count)
961 {
962         char *item;
963         struct reiserfs_de_head *deh;
964         int prev_record_offset; /* offset of record, that is (from-1)th */
965         char *prev_record;      /* */
966         int cut_records_len;    /* length of all removed records */
967         int i;
968
969         /* make sure, that item is directory and there are enough entries to
970            remove */
971         RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
972         RFALSE(I_ENTRY_COUNT(ih) < from + del_count,
973                "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
974                I_ENTRY_COUNT(ih), from, del_count);
975
976         if (del_count == 0)
977                 return 0;
978
979         /* first byte of item */
980         item = bh->b_data + ih_location(ih);
981
982         /* entry head array */
983         deh = B_I_DEH(bh, ih);
984
985         /* first byte of remaining entries, those are BEFORE cut entries
986            (prev_record) and length of all removed records (cut_records_len) */
987         prev_record_offset =
988             (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih));
989         cut_records_len = prev_record_offset /*from_record */  -
990             deh_location(&(deh[from + del_count - 1]));
991         prev_record = item + prev_record_offset;
992
993         /* adjust locations of remaining entries */
994         for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--)
995                 put_deh_location(&(deh[i]),
996                                  deh_location(&deh[i]) -
997                                  (DEH_SIZE * del_count));
998
999         for (i = 0; i < from; i++)
1000                 put_deh_location(&(deh[i]),
1001                                  deh_location(&deh[i]) - (DEH_SIZE * del_count +
1002                                                           cut_records_len));
1003
1004         put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
1005
1006         /* shift entry head array and entries those are AFTER removed entries */
1007         memmove((char *)(deh + from),
1008                 deh + from + del_count,
1009                 prev_record - cut_records_len - (char *)(deh + from +
1010                                                          del_count));
1011
1012         /* shift records, those are BEFORE removed entries */
1013         memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
1014                 prev_record, item + ih_item_len(ih) - prev_record);
1015
1016         return DEH_SIZE * del_count + cut_records_len;
1017 }
1018
1019 /*  when cut item is part of regular file
1020         pos_in_item - first byte that must be cut
1021         cut_size - number of bytes to be cut beginning from pos_in_item
1022  
1023    when cut item is part of directory
1024         pos_in_item - number of first deleted entry
1025         cut_size - count of deleted entries
1026     */
1027 void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
1028                           int pos_in_item, int cut_size)
1029 {
1030         int nr;
1031         struct buffer_head *bh = bi->bi_bh;
1032         struct block_head *blkh;
1033         struct item_head *ih;
1034         int last_loc, unmoved_loc;
1035         int i;
1036
1037         blkh = B_BLK_HEAD(bh);
1038         nr = blkh_nr_item(blkh);
1039
1040         /* item head of truncated item */
1041         ih = B_N_PITEM_HEAD(bh, cut_item_num);
1042
1043         if (is_direntry_le_ih(ih)) {
1044                 /* first cut entry () */
1045                 cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
1046                 if (pos_in_item == 0) {
1047                         /* change key */
1048                         RFALSE(cut_item_num,
1049                                "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
1050                                cut_item_num);
1051                         /* change item key by key of first entry in the item */
1052                         set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
1053                         /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */
1054                 }
1055         } else {
1056                 /* item is direct or indirect */
1057                 RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
1058                 RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
1059                        "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
1060                        (long unsigned)pos_in_item, (long unsigned)cut_size,
1061                        (long unsigned)ih_item_len(ih));
1062
1063                 /* shift item body to left if cut is from the head of item */
1064                 if (pos_in_item == 0) {
1065                         memmove(bh->b_data + ih_location(ih),
1066                                 bh->b_data + ih_location(ih) + cut_size,
1067                                 ih_item_len(ih) - cut_size);
1068
1069                         /* change key of item */
1070                         if (is_direct_le_ih(ih))
1071                                 set_le_ih_k_offset(ih,
1072                                                    le_ih_k_offset(ih) +
1073                                                    cut_size);
1074                         else {
1075                                 set_le_ih_k_offset(ih,
1076                                                    le_ih_k_offset(ih) +
1077                                                    (cut_size / UNFM_P_SIZE) *
1078                                                    bh->b_size);
1079                                 RFALSE(ih_item_len(ih) == cut_size
1080                                        && get_ih_free_space(ih),
1081                                        "10205: invalid ih_free_space (%h)", ih);
1082                         }
1083                 }
1084         }
1085
1086         /* location of the last item */
1087         last_loc = ih_location(&(ih[nr - cut_item_num - 1]));
1088
1089         /* location of the item, which is remaining at the same place */
1090         unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
1091
1092         /* shift */
1093         memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1094                 unmoved_loc - last_loc - cut_size);
1095
1096         /* change item length */
1097         put_ih_item_len(ih, ih_item_len(ih) - cut_size);
1098
1099         if (is_indirect_le_ih(ih)) {
1100                 if (pos_in_item)
1101                         set_ih_free_space(ih, 0);
1102         }
1103
1104         /* change locations */
1105         for (i = cut_item_num; i < nr; i++)
1106                 put_ih_location(&(ih[i - cut_item_num]),
1107                                 ih_location(&ih[i - cut_item_num]) + cut_size);
1108
1109         /* size, free space */
1110         set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
1111
1112         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1113
1114         if (bi->bi_parent) {
1115                 struct disk_child *t_dc;
1116                 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
1117                 put_dc_size(t_dc, dc_size(t_dc) - cut_size);
1118                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1119         }
1120 }
1121
1122 /* delete del_num items from buffer starting from the first'th item */
1123 static void leaf_delete_items_entirely(struct buffer_info *bi,
1124                                        int first, int del_num)
1125 {
1126         struct buffer_head *bh = bi->bi_bh;
1127         int nr;
1128         int i, j;
1129         int last_loc, last_removed_loc;
1130         struct block_head *blkh;
1131         struct item_head *ih;
1132
1133         RFALSE(bh == NULL, "10210: buffer is 0");
1134         RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
1135
1136         if (del_num == 0)
1137                 return;
1138
1139         blkh = B_BLK_HEAD(bh);
1140         nr = blkh_nr_item(blkh);
1141
1142         RFALSE(first < 0 || first + del_num > nr,
1143                "10220: first=%d, number=%d, there is %d items", first, del_num,
1144                nr);
1145
1146         if (first == 0 && del_num == nr) {
1147                 /* this does not work */
1148                 make_empty_node(bi);
1149
1150                 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1151                 return;
1152         }
1153
1154         ih = B_N_PITEM_HEAD(bh, first);
1155
1156         /* location of unmovable item */
1157         j = (first == 0) ? bh->b_size : ih_location(ih - 1);
1158
1159         /* delete items */
1160         last_loc = ih_location(&(ih[nr - 1 - first]));
1161         last_removed_loc = ih_location(&(ih[del_num - 1]));
1162
1163         memmove(bh->b_data + last_loc + j - last_removed_loc,
1164                 bh->b_data + last_loc, last_removed_loc - last_loc);
1165
1166         /* delete item headers */
1167         memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1168
1169         /* change item location */
1170         for (i = first; i < nr - del_num; i++)
1171                 put_ih_location(&(ih[i - first]),
1172                                 ih_location(&(ih[i - first])) + (j -
1173                                                                  last_removed_loc));
1174
1175         /* sizes, item number */
1176         set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
1177         set_blkh_free_space(blkh,
1178                             blkh_free_space(blkh) + (j - last_removed_loc +
1179                                                      IH_SIZE * del_num));
1180
1181         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1182
1183         if (bi->bi_parent) {
1184                 struct disk_child *t_dc =
1185                     B_N_CHILD(bi->bi_parent, bi->bi_position);
1186                 put_dc_size(t_dc,
1187                             dc_size(t_dc) - (j - last_removed_loc +
1188                                              IH_SIZE * del_num));
1189                 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1190         }
1191 }
1192
1193 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
1194 void leaf_paste_entries(struct buffer_head *bh,
1195                         int item_num,
1196                         int before,
1197                         int new_entry_count,
1198                         struct reiserfs_de_head *new_dehs,
1199                         const char *records, int paste_size)
1200 {
1201         struct item_head *ih;
1202         char *item;
1203         struct reiserfs_de_head *deh;
1204         char *insert_point;
1205         int i, old_entry_num;
1206
1207         if (new_entry_count == 0)
1208                 return;
1209
1210         ih = B_N_PITEM_HEAD(bh, item_num);
1211
1212         /* make sure, that item is directory, and there are enough records in it */
1213         RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
1214         RFALSE(I_ENTRY_COUNT(ih) < before,
1215                "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
1216                I_ENTRY_COUNT(ih), before);
1217
1218         /* first byte of dest item */
1219         item = bh->b_data + ih_location(ih);
1220
1221         /* entry head array */
1222         deh = B_I_DEH(bh, ih);
1223
1224         /* new records will be pasted at this point */
1225         insert_point =
1226             item +
1227             (before ? deh_location(&(deh[before - 1]))
1228              : (ih_item_len(ih) - paste_size));
1229
1230         /* adjust locations of records that will be AFTER new records */
1231         for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--)
1232                 put_deh_location(&(deh[i]),
1233                                  deh_location(&(deh[i])) +
1234                                  (DEH_SIZE * new_entry_count));
1235
1236         /* adjust locations of records that will be BEFORE new records */
1237         for (i = 0; i < before; i++)
1238                 put_deh_location(&(deh[i]),
1239                                  deh_location(&(deh[i])) + paste_size);
1240
1241         old_entry_num = I_ENTRY_COUNT(ih);
1242         put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
1243
1244         /* prepare space for pasted records */
1245         memmove(insert_point + paste_size, insert_point,
1246                 item + (ih_item_len(ih) - paste_size) - insert_point);
1247
1248         /* copy new records */
1249         memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1250                paste_size - DEH_SIZE * new_entry_count);
1251
1252         /* prepare space for new entry heads */
1253         deh += before;
1254         memmove((char *)(deh + new_entry_count), deh,
1255                 insert_point - (char *)deh);
1256
1257         /* copy new entry heads */
1258         deh = (struct reiserfs_de_head *)((char *)deh);
1259         memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
1260
1261         /* set locations of new records */
1262         for (i = 0; i < new_entry_count; i++) {
1263                 put_deh_location(&(deh[i]),
1264                                  deh_location(&(deh[i])) +
1265                                  (-deh_location
1266                                   (&(new_dehs[new_entry_count - 1])) +
1267                                   insert_point + DEH_SIZE * new_entry_count -
1268                                   item));
1269         }
1270
1271         /* change item key if necessary (when we paste before 0-th entry */
1272         if (!before) {
1273                 set_le_ih_k_offset(ih, deh_offset(new_dehs));
1274 /*      memcpy (&ih->ih_key.k_offset, 
1275                        &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
1276         }
1277 #ifdef CONFIG_REISERFS_CHECK
1278         {
1279                 int prev, next;
1280                 /* check record locations */
1281                 deh = B_I_DEH(bh, ih);
1282                 for (i = 0; i < I_ENTRY_COUNT(ih); i++) {
1283                         next =
1284                             (i <
1285                              I_ENTRY_COUNT(ih) -
1286                              1) ? deh_location(&(deh[i + 1])) : 0;
1287                         prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0;
1288
1289                         if (prev && prev <= deh_location(&(deh[i])))
1290                                 reiserfs_warning(NULL,
1291                                                  "vs-10240: leaf_paste_entries: directory item (%h) corrupted (prev %a, cur(%d) %a)",
1292                                                  ih, deh + i - 1, i, deh + i);
1293                         if (next && next >= deh_location(&(deh[i])))
1294                                 reiserfs_warning(NULL,
1295                                                  "vs-10250: leaf_paste_entries: directory item (%h) corrupted (cur(%d) %a, next %a)",
1296                                                  ih, i, deh + i, deh + i + 1);
1297                 }
1298         }
1299 #endif
1300
1301 }