fs/reiserfs/lbalance.c

0001 /*
0002  * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
0003  */
0004
0005 #include <linux/uaccess.h>
0006 #include <linux/string.h>
0007 #include <linux/time.h>
0008 #include "reiserfs.h"
0009 #include <linux/buffer_head.h>
0010
0011 /*
0012  * copy copy_count entries from source directory item to dest buffer
0013  * (creating new item if needed)
0014  */
0015 static void leaf_copy_dir_entries(struct buffer_info *dest_bi,
0016                   struct buffer_head *source, int last_first,
0017                   int item_num, int from, int copy_count)
0018 {
0019     struct buffer_head *dest = dest_bi->bi_bh;
0020     /*
0021      * either the number of target item, or if we must create a
0022      * new item, the number of the item we will create it next to
0023      */
0024     int item_num_in_dest;
0025
0026     struct item_head *ih;
0027     struct reiserfs_de_head *deh;
0028     int copy_records_len;   /* length of all records in item to be copied */
0029     char *records;
0030
0031     ih = item_head(source, item_num);
0032
0033     RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item");
0034
0035     /*
0036      * length of all record to be copied and first byte of
0037      * the last of them
0038      */
0039     deh = B_I_DEH(source, ih);
0040     if (copy_count) {
0041         copy_records_len = (from ? deh_location(&deh[from - 1]) :
0042                     ih_item_len(ih)) -
0043             deh_location(&deh[from + copy_count - 1]);
0044         records =
0045             source->b_data + ih_location(ih) +
0046             deh_location(&deh[from + copy_count - 1]);
0047     } else {
0048         copy_records_len = 0;
0049         records = NULL;
0050     }
0051
0052     /* when copy last to first, dest buffer can contain 0 items */
0053     item_num_in_dest =
0054         (last_first ==
0055          LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest)
0056                                    - 1);
0057
0058     /*
0059      * if there are no items in dest or the first/last item in
0060      * dest is not item of the same directory
0061      */
0062     if ((item_num_in_dest == -1) ||
0063         (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) ||
0064         (last_first == LAST_TO_FIRST
0065          && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key,
0066                              leaf_key(dest,
0067                                   item_num_in_dest))))
0068     {
0069         /* create new item in dest */
0070         struct item_head new_ih;
0071
0072         /* form item header */
0073         memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
0074         put_ih_version(&new_ih, KEY_FORMAT_3_5);
0075         /* calculate item len */
0076         put_ih_item_len(&new_ih,
0077                 DEH_SIZE * copy_count + copy_records_len);
0078         put_ih_entry_count(&new_ih, 0);
0079
0080         if (last_first == LAST_TO_FIRST) {
0081             /* form key by the following way */
0082             if (from < ih_entry_count(ih)) {
0083                 set_le_ih_k_offset(&new_ih,
0084                            deh_offset(&deh[from]));
0085             } else {
0086                 /*
0087                  * no entries will be copied to this
0088                  * item in this function
0089                  */
0090                 set_le_ih_k_offset(&new_ih, U32_MAX);
0091                 /*
0092                  * this item is not yet valid, but we
0093                  * want I_IS_DIRECTORY_ITEM to return 1
0094                  * for it, so we -1
0095                  */
0096             }
0097             set_le_key_k_type(KEY_FORMAT_3_5, &new_ih.ih_key,
0098                       TYPE_DIRENTRY);
0099         }
0100
0101         /* insert item into dest buffer */
0102         leaf_insert_into_buf(dest_bi,
0103                      (last_first ==
0104                       LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest),
0105                      &new_ih, NULL, 0);
0106     } else {
0107         /* prepare space for entries */
0108         leaf_paste_in_buffer(dest_bi,
0109                      (last_first ==
0110                       FIRST_TO_LAST) ? (B_NR_ITEMS(dest) -
0111                             1) : 0, MAX_US_INT,
0112                      DEH_SIZE * copy_count + copy_records_len,
0113                      records, 0);
0114     }
0115
0116     item_num_in_dest =
0117         (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0;
0118
0119     leaf_paste_entries(dest_bi, item_num_in_dest,
0120                (last_first ==
0121                 FIRST_TO_LAST) ? ih_entry_count(item_head(dest,
0122                                       item_num_in_dest))
0123                : 0, copy_count, deh + from, records,
0124                DEH_SIZE * copy_count + copy_records_len);
0125 }
0126
0127 /*
0128  * Copy the first (if last_first == FIRST_TO_LAST) or last
0129  * (last_first == LAST_TO_FIRST) item or part of it or nothing
0130  * (see the return 0 below) from SOURCE to the end (if last_first)
0131  * or beginning (!last_first) of the DEST
0132  */
0133 /* returns 1 if anything was copied, else 0 */
0134 static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
0135                    struct buffer_head *src, int last_first,
0136                    int bytes_or_entries)
0137 {
0138     struct buffer_head *dest = dest_bi->bi_bh;
0139     /* number of items in the source and destination buffers */
0140     int dest_nr_item, src_nr_item;
0141     struct item_head *ih;
0142     struct item_head *dih;
0143
0144     dest_nr_item = B_NR_ITEMS(dest);
0145
0146     /*
0147      * if ( DEST is empty or first item of SOURCE and last item of
0148      * DEST are the items of different objects or of different types )
0149      * then there is no need to treat this item differently from the
0150      * other items that we copy, so we return
0151      */
0152     if (last_first == FIRST_TO_LAST) {
0153         ih = item_head(src, 0);
0154         dih = item_head(dest, dest_nr_item - 1);
0155
0156         /* there is nothing to merge */
0157         if (!dest_nr_item
0158             || (!op_is_left_mergeable(&ih->ih_key, src->b_size)))
0159             return 0;
0160
0161         RFALSE(!ih_item_len(ih),
0162                "vs-10010: item can not have empty length");
0163
0164         if (is_direntry_le_ih(ih)) {
0165             if (bytes_or_entries == -1)
0166                 /* copy all entries to dest */
0167                 bytes_or_entries = ih_entry_count(ih);
0168             leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0,
0169                           bytes_or_entries);
0170             return 1;
0171         }
0172
0173         /*
0174          * copy part of the body of the first item of SOURCE
0175          * to the end of the body of the last item of the DEST
0176          * part defined by 'bytes_or_entries'; if bytes_or_entries
0177          * == -1 copy whole body; don't create new item header
0178          */
0179         if (bytes_or_entries == -1)
0180             bytes_or_entries = ih_item_len(ih);
0181
0182 #ifdef CONFIG_REISERFS_CHECK
0183         else {
0184             if (bytes_or_entries == ih_item_len(ih)
0185                 && is_indirect_le_ih(ih))
0186                 if (get_ih_free_space(ih))
0187                     reiserfs_panic(sb_from_bi(dest_bi),
0188                                "vs-10020",
0189                                "last unformatted node "
0190                                "must be filled "
0191                                "entirely (%h)", ih);
0192         }
0193 #endif
0194
0195         /*
0196          * merge first item (or its part) of src buffer with the last
0197          * item of dest buffer. Both are of the same file
0198          */
0199         leaf_paste_in_buffer(dest_bi,
0200                      dest_nr_item - 1, ih_item_len(dih),
0201                      bytes_or_entries, ih_item_body(src, ih), 0);
0202
0203         if (is_indirect_le_ih(dih)) {
0204             RFALSE(get_ih_free_space(dih),
0205                    "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
0206                    ih);
0207             if (bytes_or_entries == ih_item_len(ih))
0208                 set_ih_free_space(dih, get_ih_free_space(ih));
0209         }
0210
0211         return 1;
0212     }
0213
0214     /* copy boundary item to right (last_first == LAST_TO_FIRST) */
0215
0216     /*
0217      * (DEST is empty or last item of SOURCE and first item of DEST
0218      * are the items of different object or of different types)
0219      */
0220     src_nr_item = B_NR_ITEMS(src);
0221     ih = item_head(src, src_nr_item - 1);
0222     dih = item_head(dest, 0);
0223
0224     if (!dest_nr_item || !op_is_left_mergeable(&dih->ih_key, src->b_size))
0225         return 0;
0226
0227     if (is_direntry_le_ih(ih)) {
0228         /*
0229          * bytes_or_entries = entries number in last
0230          * item body of SOURCE
0231          */
0232         if (bytes_or_entries == -1)
0233             bytes_or_entries = ih_entry_count(ih);
0234
0235         leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
0236                       src_nr_item - 1,
0237                       ih_entry_count(ih) - bytes_or_entries,
0238                       bytes_or_entries);
0239         return 1;
0240     }
0241
0242     /*
0243      * copy part of the body of the last item of SOURCE to the
0244      * begin of the body of the first item of the DEST; part defined
0245      * by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body;
0246      * change first item key of the DEST; don't create new item header
0247      */
0248
0249     RFALSE(is_indirect_le_ih(ih) && get_ih_free_space(ih),
0250            "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
0251            ih);
0252
0253     if (bytes_or_entries == -1) {
0254         /* bytes_or_entries = length of last item body of SOURCE */
0255         bytes_or_entries = ih_item_len(ih);
0256
0257         RFALSE(le_ih_k_offset(dih) !=
0258                le_ih_k_offset(ih) + op_bytes_number(ih, src->b_size),
0259                "vs-10050: items %h and %h do not match", ih, dih);
0260
0261         /* change first item key of the DEST */
0262         set_le_ih_k_offset(dih, le_ih_k_offset(ih));
0263
0264         /* item becomes non-mergeable */
0265         /* or mergeable if left item was */
0266         set_le_ih_k_type(dih, le_ih_k_type(ih));
0267     } else {
0268         /* merge to right only part of item */
0269         RFALSE(ih_item_len(ih) <= bytes_or_entries,
0270                "vs-10060: no so much bytes %lu (needed %lu)",
0271                (unsigned long)ih_item_len(ih),
0272                (unsigned long)bytes_or_entries);
0273
0274         /* change first item key of the DEST */
0275         if (is_direct_le_ih(dih)) {
0276             RFALSE(le_ih_k_offset(dih) <=
0277                    (unsigned long)bytes_or_entries,
0278                    "vs-10070: dih %h, bytes_or_entries(%d)", dih,
0279                    bytes_or_entries);
0280             set_le_ih_k_offset(dih,
0281                        le_ih_k_offset(dih) -
0282                        bytes_or_entries);
0283         } else {
0284             RFALSE(le_ih_k_offset(dih) <=
0285                    (bytes_or_entries / UNFM_P_SIZE) * dest->b_size,
0286                    "vs-10080: dih %h, bytes_or_entries(%d)",
0287                    dih,
0288                    (bytes_or_entries / UNFM_P_SIZE) * dest->b_size);
0289             set_le_ih_k_offset(dih,
0290                        le_ih_k_offset(dih) -
0291                        ((bytes_or_entries / UNFM_P_SIZE) *
0292                         dest->b_size));
0293         }
0294     }
0295
0296     leaf_paste_in_buffer(dest_bi, 0, 0, bytes_or_entries,
0297                  ih_item_body(src,
0298                        ih) + ih_item_len(ih) - bytes_or_entries,
0299                  0);
0300     return 1;
0301 }
0302
0303 /*
0304  * copy cpy_mun items from buffer src to buffer dest
0305  * last_first == FIRST_TO_LAST means, that we copy cpy_num items beginning
0306  *                             from first-th item in src to tail of dest
0307  * last_first == LAST_TO_FIRST means, that we copy cpy_num items beginning
0308  *                             from first-th item in src to head of dest
0309  */
0310 static void leaf_copy_items_entirely(struct buffer_info *dest_bi,
0311                      struct buffer_head *src, int last_first,
0312                      int first, int cpy_num)
0313 {
0314     struct buffer_head *dest;
0315     int nr, free_space;
0316     int dest_before;
0317     int last_loc, last_inserted_loc, location;
0318     int i, j;
0319     struct block_head *blkh;
0320     struct item_head *ih;
0321
0322     RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST,
0323            "vs-10090: bad last_first parameter %d", last_first);
0324     RFALSE(B_NR_ITEMS(src) - first < cpy_num,
0325            "vs-10100: too few items in source %d, required %d from %d",
0326            B_NR_ITEMS(src), cpy_num, first);
0327     RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items");
0328     RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items");
0329
0330     dest = dest_bi->bi_bh;
0331
0332     RFALSE(!dest, "vs-10130: can not copy negative amount of items");
0333
0334     if (cpy_num == 0)
0335         return;
0336
0337     blkh = B_BLK_HEAD(dest);
0338     nr = blkh_nr_item(blkh);
0339     free_space = blkh_free_space(blkh);
0340
0341     /*
0342      * we will insert items before 0-th or nr-th item in dest buffer.
0343      * It depends of last_first parameter
0344      */
0345     dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;
0346
0347     /* location of head of first new item */
0348     ih = item_head(dest, dest_before);
0349
0350     RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE,
0351            "vs-10140: not enough free space for headers %d (needed %d)",
0352            B_FREE_SPACE(dest), cpy_num * IH_SIZE);
0353
0354     /* prepare space for headers */
0355     memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE);
0356
0357     /* copy item headers */
0358     memcpy(ih, item_head(src, first), cpy_num * IH_SIZE);
0359
0360     free_space -= (IH_SIZE * cpy_num);
0361     set_blkh_free_space(blkh, free_space);
0362
0363     /* location of unmovable item */
0364     j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1);
0365     for (i = dest_before; i < nr + cpy_num; i++) {
0366         location -= ih_item_len(ih + i - dest_before);
0367         put_ih_location(ih + i - dest_before, location);
0368     }
0369
0370     /* prepare space for items */
0371     last_loc = ih_location(&ih[nr + cpy_num - 1 - dest_before]);
0372     last_inserted_loc = ih_location(&ih[cpy_num - 1]);
0373
0374     /* check free space */
0375     RFALSE(free_space < j - last_inserted_loc,
0376            "vs-10150: not enough free space for items %d (needed %d)",
0377            free_space, j - last_inserted_loc);
0378
0379     memmove(dest->b_data + last_loc,
0380         dest->b_data + last_loc + j - last_inserted_loc,
0381         last_inserted_loc - last_loc);
0382
0383     /* copy items */
0384     memcpy(dest->b_data + last_inserted_loc,
0385            item_body(src, (first + cpy_num - 1)),
0386            j - last_inserted_loc);
0387
0388     /* sizes, item number */
0389     set_blkh_nr_item(blkh, nr + cpy_num);
0390     set_blkh_free_space(blkh, free_space - (j - last_inserted_loc));
0391
0392     do_balance_mark_leaf_dirty(dest_bi->tb, dest, 0);
0393
0394     if (dest_bi->bi_parent) {
0395         struct disk_child *t_dc;
0396         t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
0397         RFALSE(dc_block_number(t_dc) != dest->b_blocknr,
0398                "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu",
0399                (long unsigned)dest->b_blocknr,
0400                (long unsigned)dc_block_number(t_dc));
0401         put_dc_size(t_dc,
0402                 dc_size(t_dc) + (j - last_inserted_loc +
0403                          IH_SIZE * cpy_num));
0404
0405         do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
0406                            0);
0407     }
0408 }
0409
0410 /*
0411  * This function splits the (liquid) item into two items (useful when
0412  * shifting part of an item into another node.)
0413  */
0414 static void leaf_item_bottle(struct buffer_info *dest_bi,
0415                  struct buffer_head *src, int last_first,
0416                  int item_num, int cpy_bytes)
0417 {
0418     struct buffer_head *dest = dest_bi->bi_bh;
0419     struct item_head *ih;
0420
0421     RFALSE(cpy_bytes == -1,
0422            "vs-10170: bytes == - 1 means: do not split item");
0423
0424     if (last_first == FIRST_TO_LAST) {
0425         /*
0426          * if ( if item in position item_num in buffer SOURCE
0427          * is directory item )
0428          */
0429         ih = item_head(src, item_num);
0430         if (is_direntry_le_ih(ih))
0431             leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
0432                           item_num, 0, cpy_bytes);
0433         else {
0434             struct item_head n_ih;
0435
0436             /*
0437              * copy part of the body of the item number 'item_num'
0438              * of SOURCE to the end of the DEST part defined by
0439              * 'cpy_bytes'; create new item header; change old
0440              * item_header (????); n_ih = new item_header;
0441              */
0442             memcpy(&n_ih, ih, IH_SIZE);
0443             put_ih_item_len(&n_ih, cpy_bytes);
0444             if (is_indirect_le_ih(ih)) {
0445                 RFALSE(cpy_bytes == ih_item_len(ih)
0446                        && get_ih_free_space(ih),
0447                        "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
0448                        (long unsigned)get_ih_free_space(ih));
0449                 set_ih_free_space(&n_ih, 0);
0450             }
0451
0452             RFALSE(op_is_left_mergeable(&ih->ih_key, src->b_size),
0453                    "vs-10190: bad mergeability of item %h", ih);
0454             n_ih.ih_version = ih->ih_version;   /* JDM Endian safe, both le */
0455             leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
0456                          item_body(src, item_num), 0);
0457         }
0458     } else {
0459         /*
0460          * if ( if item in position item_num in buffer
0461          * SOURCE is directory item )
0462          */
0463         ih = item_head(src, item_num);
0464         if (is_direntry_le_ih(ih))
0465             leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
0466                           item_num,
0467                           ih_entry_count(ih) - cpy_bytes,
0468                           cpy_bytes);
0469         else {
0470             struct item_head n_ih;
0471
0472             /*
0473              * copy part of the body of the item number 'item_num'
0474              * of SOURCE to the begin of the DEST part defined by
0475              * 'cpy_bytes'; create new item header;
0476              * n_ih = new item_header;
0477              */
0478             memcpy(&n_ih.ih_key, &ih->ih_key, KEY_SIZE);
0479
0480             /* Endian safe, both le */
0481             n_ih.ih_version = ih->ih_version;
0482
0483             if (is_direct_le_ih(ih)) {
0484                 set_le_ih_k_offset(&n_ih,
0485                            le_ih_k_offset(ih) +
0486                            ih_item_len(ih) - cpy_bytes);
0487                 set_le_ih_k_type(&n_ih, TYPE_DIRECT);
0488                 set_ih_free_space(&n_ih, MAX_US_INT);
0489             } else {
0490                 /* indirect item */
0491                 RFALSE(!cpy_bytes && get_ih_free_space(ih),
0492                        "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
0493                 set_le_ih_k_offset(&n_ih,
0494                            le_ih_k_offset(ih) +
0495                            (ih_item_len(ih) -
0496                             cpy_bytes) / UNFM_P_SIZE *
0497                            dest->b_size);
0498                 set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
0499                 set_ih_free_space(&n_ih, get_ih_free_space(ih));
0500             }
0501
0502             /* set item length */
0503             put_ih_item_len(&n_ih, cpy_bytes);
0504
0505             /* Endian safe, both le */
0506             n_ih.ih_version = ih->ih_version;
0507
0508             leaf_insert_into_buf(dest_bi, 0, &n_ih,
0509                          item_body(src, item_num) +
0510                         ih_item_len(ih) - cpy_bytes, 0);
0511         }
0512     }
0513 }
0514
0515 /*
0516  * If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE
0517  * to DEST.  If cpy_bytes not equal to minus one than copy cpy_num-1 whole
0518  * items from SOURCE to DEST.  From last item copy cpy_num bytes for regular
0519  * item and cpy_num directory entries for directory item.
0520  */
0521 static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
0522                int last_first, int cpy_num, int cpy_bytes)
0523 {
0524     struct buffer_head *dest;
0525     int pos, i, src_nr_item, bytes;
0526
0527     dest = dest_bi->bi_bh;
0528     RFALSE(!dest || !src, "vs-10210: !dest || !src");
0529     RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
0530            "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
0531     RFALSE(B_NR_ITEMS(src) < cpy_num,
0532            "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
0533            cpy_num);
0534     RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);
0535
0536     if (cpy_num == 0)
0537         return 0;
0538
0539     if (last_first == FIRST_TO_LAST) {
0540         /* copy items to left */
0541         pos = 0;
0542         if (cpy_num == 1)
0543             bytes = cpy_bytes;
0544         else
0545             bytes = -1;
0546
0547         /*
0548          * copy the first item or it part or nothing to the end of
0549          * the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes))
0550          */
0551         i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
0552         cpy_num -= i;
0553         if (cpy_num == 0)
0554             return i;
0555         pos += i;
0556         if (cpy_bytes == -1)
0557             /*
0558              * copy first cpy_num items starting from position
0559              * 'pos' of SOURCE to end of DEST
0560              */
0561             leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
0562                          pos, cpy_num);
0563         else {
0564             /*
0565              * copy first cpy_num-1 items starting from position
0566              * 'pos-1' of the SOURCE to the end of the DEST
0567              */
0568             leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
0569                          pos, cpy_num - 1);
0570
0571             /*
0572              * copy part of the item which number is
0573              * cpy_num+pos-1 to the end of the DEST
0574              */
0575             leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
0576                      cpy_num + pos - 1, cpy_bytes);
0577         }
0578     } else {
0579         /* copy items to right */
0580         src_nr_item = B_NR_ITEMS(src);
0581         if (cpy_num == 1)
0582             bytes = cpy_bytes;
0583         else
0584             bytes = -1;
0585
0586         /*
0587          * copy the last item or it part or nothing to the
0588          * begin of the DEST
0589          * (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes));
0590          */
0591         i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);
0592
0593         cpy_num -= i;
0594         if (cpy_num == 0)
0595             return i;
0596
0597         pos = src_nr_item - cpy_num - i;
0598         if (cpy_bytes == -1) {
0599             /*
0600              * starting from position 'pos' copy last cpy_num
0601              * items of SOURCE to begin of DEST
0602              */
0603             leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
0604                          pos, cpy_num);
0605         } else {
0606             /*
0607              * copy last cpy_num-1 items starting from position
0608              * 'pos+1' of the SOURCE to the begin of the DEST;
0609              */
0610             leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
0611                          pos + 1, cpy_num - 1);
0612
0613             /*
0614              * copy part of the item which number is pos to
0615              * the begin of the DEST
0616              */
0617             leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
0618                      cpy_bytes);
0619         }
0620     }
0621     return i;
0622 }
0623
0624 /*
0625  * there are types of coping: from S[0] to L[0], from S[0] to R[0],
0626  * from R[0] to L[0]. for each of these we have to define parent and
0627  * positions of destination and source buffers
0628  */
0629 static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
0630                        struct buffer_info *dest_bi,
0631                        struct buffer_info *src_bi,
0632                        int *first_last,
0633                        struct buffer_head *Snew)
0634 {
0635     memset(dest_bi, 0, sizeof(struct buffer_info));
0636     memset(src_bi, 0, sizeof(struct buffer_info));
0637
0638     /* define dest, src, dest parent, dest position */
0639     switch (shift_mode) {
0640     case LEAF_FROM_S_TO_L:  /* it is used in leaf_shift_left */
0641         src_bi->tb = tb;
0642         src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
0643         src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
0644
0645         /* src->b_item_order */
0646         src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
0647         dest_bi->tb = tb;
0648         dest_bi->bi_bh = tb->L[0];
0649         dest_bi->bi_parent = tb->FL[0];
0650         dest_bi->bi_position = get_left_neighbor_position(tb, 0);
0651         *first_last = FIRST_TO_LAST;
0652         break;
0653
0654     case LEAF_FROM_S_TO_R:  /* it is used in leaf_shift_right */
0655         src_bi->tb = tb;
0656         src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
0657         src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
0658         src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
0659         dest_bi->tb = tb;
0660         dest_bi->bi_bh = tb->R[0];
0661         dest_bi->bi_parent = tb->FR[0];
0662         dest_bi->bi_position = get_right_neighbor_position(tb, 0);
0663         *first_last = LAST_TO_FIRST;
0664         break;
0665
0666     case LEAF_FROM_R_TO_L:  /* it is used in balance_leaf_when_delete */
0667         src_bi->tb = tb;
0668         src_bi->bi_bh = tb->R[0];
0669         src_bi->bi_parent = tb->FR[0];
0670         src_bi->bi_position = get_right_neighbor_position(tb, 0);
0671         dest_bi->tb = tb;
0672         dest_bi->bi_bh = tb->L[0];
0673         dest_bi->bi_parent = tb->FL[0];
0674         dest_bi->bi_position = get_left_neighbor_position(tb, 0);
0675         *first_last = FIRST_TO_LAST;
0676         break;
0677
0678     case LEAF_FROM_L_TO_R:  /* it is used in balance_leaf_when_delete */
0679         src_bi->tb = tb;
0680         src_bi->bi_bh = tb->L[0];
0681         src_bi->bi_parent = tb->FL[0];
0682         src_bi->bi_position = get_left_neighbor_position(tb, 0);
0683         dest_bi->tb = tb;
0684         dest_bi->bi_bh = tb->R[0];
0685         dest_bi->bi_parent = tb->FR[0];
0686         dest_bi->bi_position = get_right_neighbor_position(tb, 0);
0687         *first_last = LAST_TO_FIRST;
0688         break;
0689
0690     case LEAF_FROM_S_TO_SNEW:
0691         src_bi->tb = tb;
0692         src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
0693         src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
0694         src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
0695         dest_bi->tb = tb;
0696         dest_bi->bi_bh = Snew;
0697         dest_bi->bi_parent = NULL;
0698         dest_bi->bi_position = 0;
0699         *first_last = LAST_TO_FIRST;
0700         break;
0701
0702     default:
0703         reiserfs_panic(sb_from_bi(src_bi), "vs-10250",
0704                    "shift type is unknown (%d)", shift_mode);
0705     }
0706     RFALSE(!src_bi->bi_bh || !dest_bi->bi_bh,
0707            "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
0708            shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
0709 }
0710
0711 /*
0712  * copy mov_num items and mov_bytes of the (mov_num-1)th item to
0713  * neighbor. Delete them from source
0714  */
0715 int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
0716             int mov_bytes, struct buffer_head *Snew)
0717 {
0718     int ret_value;
0719     struct buffer_info dest_bi, src_bi;
0720     int first_last;
0721
0722     leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
0723                    &first_last, Snew);
0724
0725     ret_value =
0726         leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
0727                 mov_bytes);
0728
0729     leaf_delete_items(&src_bi, first_last,
0730               (first_last ==
0731                FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) -
0732                          mov_num), mov_num, mov_bytes);
0733
0734     return ret_value;
0735 }
0736
0737 /*
0738  * Shift shift_num items (and shift_bytes of last shifted item if
0739  * shift_bytes != -1) from S[0] to L[0] and replace the delimiting key
0740  */
0741 int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
0742 {
0743     struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
0744     int i;
0745
0746     /*
0747      * move shift_num (and shift_bytes bytes) items from S[0]
0748      * to left neighbor L[0]
0749      */
0750     i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL);
0751
0752     if (shift_num) {
0753         /* number of items in S[0] == 0 */
0754         if (B_NR_ITEMS(S0) == 0) {
0755
0756             RFALSE(shift_bytes != -1,
0757                    "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
0758                    shift_bytes);
0759 #ifdef CONFIG_REISERFS_CHECK
0760             if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
0761                 print_cur_tb("vs-10275");
0762                 reiserfs_panic(tb->tb_sb, "vs-10275",
0763                            "balance condition corrupted "
0764                            "(%c)", tb->tb_mode);
0765             }
0766 #endif
0767
0768             if (PATH_H_POSITION(tb->tb_path, 1) == 0)
0769                 replace_key(tb, tb->CFL[0], tb->lkey[0],
0770                         PATH_H_PPARENT(tb->tb_path, 0), 0);
0771
0772         } else {
0773             /* replace lkey in CFL[0] by 0-th key from S[0]; */
0774             replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);
0775
0776             RFALSE((shift_bytes != -1 &&
0777                 !(is_direntry_le_ih(item_head(S0, 0))
0778                   && !ih_entry_count(item_head(S0, 0)))) &&
0779                    (!op_is_left_mergeable
0780                 (leaf_key(S0, 0), S0->b_size)),
0781                    "vs-10280: item must be mergeable");
0782         }
0783     }
0784
0785     return i;
0786 }
0787
0788 /* CLEANING STOPPED HERE */
0789
0790 /*
0791  * Shift shift_num (shift_bytes) items from S[0] to the right neighbor,
0792  * and replace the delimiting key
0793  */
0794 int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
0795 {
0796     int ret_value;
0797
0798     /*
0799      * move shift_num (and shift_bytes) items from S[0] to
0800      * right neighbor R[0]
0801      */
0802     ret_value =
0803         leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL);
0804
0805     /* replace rkey in CFR[0] by the 0-th key from R[0] */
0806     if (shift_num) {
0807         replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
0808
0809     }
0810
0811     return ret_value;
0812 }
0813
0814 static void leaf_delete_items_entirely(struct buffer_info *bi,
0815                        int first, int del_num);
0816 /*
0817  * If del_bytes == -1, starting from position 'first' delete del_num
0818  * items in whole in buffer CUR.
0819  *   If not.
0820  *   If last_first == 0. Starting from position 'first' delete del_num-1
0821  *   items in whole. Delete part of body of the first item. Part defined by
0822  *   del_bytes. Don't delete first item header
0823  *   If last_first == 1. Starting from position 'first+1' delete del_num-1
0824  *   items in whole. Delete part of body of the last item . Part defined by
0825  *   del_bytes. Don't delete last item header.
0826 */
0827 void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
0828                int first, int del_num, int del_bytes)
0829 {
0830     struct buffer_head *bh;
0831     int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);
0832
0833     RFALSE(!bh, "10155: bh is not defined");
0834     RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d",
0835            del_num);
0836     RFALSE(first < 0
0837            || first + del_num > item_amount,
0838            "10165: invalid number of first item to be deleted (%d) or "
0839            "no so much items (%d) to delete (only %d)", first,
0840            first + del_num, item_amount);
0841
0842     if (del_num == 0)
0843         return;
0844
0845     if (first == 0 && del_num == item_amount && del_bytes == -1) {
0846         make_empty_node(cur_bi);
0847         do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0);
0848         return;
0849     }
0850
0851     if (del_bytes == -1)
0852         /* delete del_num items beginning from item in position first */
0853         leaf_delete_items_entirely(cur_bi, first, del_num);
0854     else {
0855         if (last_first == FIRST_TO_LAST) {
0856             /*
0857              * delete del_num-1 items beginning from
0858              * item in position first
0859              */
0860             leaf_delete_items_entirely(cur_bi, first, del_num - 1);
0861
0862             /*
0863              * delete the part of the first item of the bh
0864              * do not delete item header
0865              */
0866             leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes);
0867         } else {
0868             struct item_head *ih;
0869             int len;
0870
0871             /*
0872              * delete del_num-1 items beginning from
0873              * item in position first+1
0874              */
0875             leaf_delete_items_entirely(cur_bi, first + 1,
0876                            del_num - 1);
0877
0878             ih = item_head(bh, B_NR_ITEMS(bh) - 1);
0879             if (is_direntry_le_ih(ih))
0880                 /* the last item is directory  */
0881                 /*
0882                  * len = numbers of directory entries
0883                  * in this item
0884                  */
0885                 len = ih_entry_count(ih);
0886             else
0887                 /* len = body len of item */
0888                 len = ih_item_len(ih);
0889
0890             /*
0891              * delete the part of the last item of the bh
0892              * do not delete item header
0893              */
0894             leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1,
0895                          len - del_bytes, del_bytes);
0896         }
0897     }
0898 }
0899
0900 /* insert item into the leaf node in position before */
0901 void leaf_insert_into_buf(struct buffer_info *bi, int before,
0902               struct item_head * const inserted_item_ih,
0903               const char * const inserted_item_body,
0904               int zeros_number)
0905 {
0906     struct buffer_head *bh = bi->bi_bh;
0907     int nr, free_space;
0908     struct block_head *blkh;
0909     struct item_head *ih;
0910     int i;
0911     int last_loc, unmoved_loc;
0912     char *to;
0913
0914     blkh = B_BLK_HEAD(bh);
0915     nr = blkh_nr_item(blkh);
0916     free_space = blkh_free_space(blkh);
0917
0918     /* check free space */
0919     RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
0920            "vs-10170: not enough free space in block %z, new item %h",
0921            bh, inserted_item_ih);
0922     RFALSE(zeros_number > ih_item_len(inserted_item_ih),
0923            "vs-10172: zero number == %d, item length == %d",
0924            zeros_number, ih_item_len(inserted_item_ih));
0925
0926     /* get item new item must be inserted before */
0927     ih = item_head(bh, before);
0928
0929     /* prepare space for the body of new item */
0930     last_loc = nr ? ih_location(&ih[nr - before - 1]) : bh->b_size;
0931     unmoved_loc = before ? ih_location(ih - 1) : bh->b_size;
0932
0933     memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
0934         bh->b_data + last_loc, unmoved_loc - last_loc);
0935
0936     to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
0937     memset(to, 0, zeros_number);
0938     to += zeros_number;
0939
0940     /* copy body to prepared space */
0941     if (inserted_item_body)
0942         memmove(to, inserted_item_body,
0943             ih_item_len(inserted_item_ih) - zeros_number);
0944     else
0945         memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number);
0946
0947     /* insert item header */
0948     memmove(ih + 1, ih, IH_SIZE * (nr - before));
0949     memmove(ih, inserted_item_ih, IH_SIZE);
0950
0951     /* change locations */
0952     for (i = before; i < nr + 1; i++) {
0953         unmoved_loc -= ih_item_len(&ih[i - before]);
0954         put_ih_location(&ih[i - before], unmoved_loc);
0955     }
0956
0957     /* sizes, free space, item number */
0958     set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
0959     set_blkh_free_space(blkh,
0960                 free_space - (IH_SIZE +
0961                       ih_item_len(inserted_item_ih)));
0962     do_balance_mark_leaf_dirty(bi->tb, bh, 1);
0963
0964     if (bi->bi_parent) {
0965         struct disk_child *t_dc;
0966         t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
0967         put_dc_size(t_dc,
0968                 dc_size(t_dc) + (IH_SIZE +
0969                          ih_item_len(inserted_item_ih)));
0970         do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
0971     }
0972 }
0973
0974 /*
0975  * paste paste_size bytes to affected_item_num-th item.
0976  * When item is a directory, this only prepare space for new entries
0977  */
0978 void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num,
0979               int pos_in_item, int paste_size,
0980               const char *body, int zeros_number)
0981 {
0982     struct buffer_head *bh = bi->bi_bh;
0983     int nr, free_space;
0984     struct block_head *blkh;
0985     struct item_head *ih;
0986     int i;
0987     int last_loc, unmoved_loc;
0988
0989     blkh = B_BLK_HEAD(bh);
0990     nr = blkh_nr_item(blkh);
0991     free_space = blkh_free_space(blkh);
0992
0993     /* check free space */
0994     RFALSE(free_space < paste_size,
0995            "vs-10175: not enough free space: needed %d, available %d",
0996            paste_size, free_space);
0997
0998 #ifdef CONFIG_REISERFS_CHECK
0999     if (zeros_number > paste_size) {
1000         struct super_block *sb = NULL;
1001         if (bi && bi->tb)
1002             sb = bi->tb->tb_sb;
1003         print_cur_tb("10177");
1004         reiserfs_panic(sb, "vs-10177",
1005                    "zeros_number == %d, paste_size == %d",
1006                    zeros_number, paste_size);
1007     }
1008 #endif              /* CONFIG_REISERFS_CHECK */
1009
1010     /* item to be appended */
1011     ih = item_head(bh, affected_item_num);
1012
1013     last_loc = ih_location(&ih[nr - affected_item_num - 1]);
1014     unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
1015
1016     /* prepare space */
1017     memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
1018         unmoved_loc - last_loc);
1019
1020     /* change locations */
1021     for (i = affected_item_num; i < nr; i++)
1022         put_ih_location(&ih[i - affected_item_num],
1023                 ih_location(&ih[i - affected_item_num]) -
1024                 paste_size);
1025
1026     if (body) {
1027         if (!is_direntry_le_ih(ih)) {
1028             if (!pos_in_item) {
1029                 /* shift data to right */
1030                 memmove(bh->b_data + ih_location(ih) +
1031                     paste_size,
1032                     bh->b_data + ih_location(ih),
1033                     ih_item_len(ih));
1034                 /* paste data in the head of item */
1035                 memset(bh->b_data + ih_location(ih), 0,
1036                        zeros_number);
1037                 memcpy(bh->b_data + ih_location(ih) +
1038                        zeros_number, body,
1039                        paste_size - zeros_number);
1040             } else {
1041                 memset(bh->b_data + unmoved_loc - paste_size, 0,
1042                        zeros_number);
1043                 memcpy(bh->b_data + unmoved_loc - paste_size +
1044                        zeros_number, body,
1045                        paste_size - zeros_number);
1046             }
1047         }
1048     } else
1049         memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
1050
1051     put_ih_item_len(ih, ih_item_len(ih) + paste_size);
1052
1053     /* change free space */
1054     set_blkh_free_space(blkh, free_space - paste_size);
1055
1056     do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1057
1058     if (bi->bi_parent) {
1059         struct disk_child *t_dc =
1060             B_N_CHILD(bi->bi_parent, bi->bi_position);
1061         put_dc_size(t_dc, dc_size(t_dc) + paste_size);
1062         do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1063     }
1064 }
1065
1066 /*
1067  * cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
1068  * does not have free space, so it moves DEHs and remaining records as
1069  * necessary. Return value is size of removed part of directory item
1070  * in bytes.
1071  */
1072 static int leaf_cut_entries(struct buffer_head *bh,
1073                 struct item_head *ih, int from, int del_count)
1074 {
1075     char *item;
1076     struct reiserfs_de_head *deh;
1077     int prev_record_offset; /* offset of record, that is (from-1)th */
1078     char *prev_record;  /* */
1079     int cut_records_len;    /* length of all removed records */
1080     int i;
1081
1082     /*
1083      * make sure that item is directory and there are enough entries to
1084      * remove
1085      */
1086     RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
1087     RFALSE(ih_entry_count(ih) < from + del_count,
1088            "10185: item contains not enough entries: entry_count = %d, from = %d, to delete = %d",
1089            ih_entry_count(ih), from, del_count);
1090
1091     if (del_count == 0)
1092         return 0;
1093
1094     /* first byte of item */
1095     item = bh->b_data + ih_location(ih);
1096
1097     /* entry head array */
1098     deh = B_I_DEH(bh, ih);
1099
1100     /*
1101      * first byte of remaining entries, those are BEFORE cut entries
1102      * (prev_record) and length of all removed records (cut_records_len)
1103      */
1104     prev_record_offset =
1105         (from ? deh_location(&deh[from - 1]) : ih_item_len(ih));
1106     cut_records_len = prev_record_offset /*from_record */  -
1107         deh_location(&deh[from + del_count - 1]);
1108     prev_record = item + prev_record_offset;
1109
1110     /* adjust locations of remaining entries */
1111     for (i = ih_entry_count(ih) - 1; i > from + del_count - 1; i--)
1112         put_deh_location(&deh[i],
1113                  deh_location(&deh[i]) -
1114                  (DEH_SIZE * del_count));
1115
1116     for (i = 0; i < from; i++)
1117         put_deh_location(&deh[i],
1118                  deh_location(&deh[i]) - (DEH_SIZE * del_count +
1119                               cut_records_len));
1120
1121     put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
1122
1123     /* shift entry head array and entries those are AFTER removed entries */
1124     memmove((char *)(deh + from),
1125         deh + from + del_count,
1126         prev_record - cut_records_len - (char *)(deh + from +
1127                              del_count));
1128
1129     /* shift records, those are BEFORE removed entries */
1130     memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
1131         prev_record, item + ih_item_len(ih) - prev_record);
1132
1133     return DEH_SIZE * del_count + cut_records_len;
1134 }
1135
1136 /*
1137  * when cut item is part of regular file
1138  *      pos_in_item - first byte that must be cut
1139  *      cut_size - number of bytes to be cut beginning from pos_in_item
1140  *
1141  * when cut item is part of directory
1142  *      pos_in_item - number of first deleted entry
1143  *      cut_size - count of deleted entries
1144  */
1145 void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
1146               int pos_in_item, int cut_size)
1147 {
1148     int nr;
1149     struct buffer_head *bh = bi->bi_bh;
1150     struct block_head *blkh;
1151     struct item_head *ih;
1152     int last_loc, unmoved_loc;
1153     int i;
1154
1155     blkh = B_BLK_HEAD(bh);
1156     nr = blkh_nr_item(blkh);
1157
1158     /* item head of truncated item */
1159     ih = item_head(bh, cut_item_num);
1160
1161     if (is_direntry_le_ih(ih)) {
1162         /* first cut entry () */
1163         cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
1164         if (pos_in_item == 0) {
1165             /* change key */
1166             RFALSE(cut_item_num,
1167                    "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
1168                    cut_item_num);
1169             /* change item key by key of first entry in the item */
1170             set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
1171         }
1172     } else {
1173         /* item is direct or indirect */
1174         RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
1175         RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
1176                "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
1177                (long unsigned)pos_in_item, (long unsigned)cut_size,
1178                (long unsigned)ih_item_len(ih));
1179
1180         /* shift item body to left if cut is from the head of item */
1181         if (pos_in_item == 0) {
1182             memmove(bh->b_data + ih_location(ih),
1183                 bh->b_data + ih_location(ih) + cut_size,
1184                 ih_item_len(ih) - cut_size);
1185
1186             /* change key of item */
1187             if (is_direct_le_ih(ih))
1188                 set_le_ih_k_offset(ih,
1189                            le_ih_k_offset(ih) +
1190                            cut_size);
1191             else {
1192                 set_le_ih_k_offset(ih,
1193                            le_ih_k_offset(ih) +
1194                            (cut_size / UNFM_P_SIZE) *
1195                            bh->b_size);
1196                 RFALSE(ih_item_len(ih) == cut_size
1197                        && get_ih_free_space(ih),
1198                        "10205: invalid ih_free_space (%h)", ih);
1199             }
1200         }
1201     }
1202
1203     /* location of the last item */
1204     last_loc = ih_location(&ih[nr - cut_item_num - 1]);
1205
1206     /* location of the item, which is remaining at the same place */
1207     unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
1208
1209     /* shift */
1210     memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1211         unmoved_loc - last_loc - cut_size);
1212
1213     /* change item length */
1214     put_ih_item_len(ih, ih_item_len(ih) - cut_size);
1215
1216     if (is_indirect_le_ih(ih)) {
1217         if (pos_in_item)
1218             set_ih_free_space(ih, 0);
1219     }
1220
1221     /* change locations */
1222     for (i = cut_item_num; i < nr; i++)
1223         put_ih_location(&ih[i - cut_item_num],
1224                 ih_location(&ih[i - cut_item_num]) + cut_size);
1225
1226     /* size, free space */
1227     set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
1228
1229     do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1230
1231     if (bi->bi_parent) {
1232         struct disk_child *t_dc;
1233         t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
1234         put_dc_size(t_dc, dc_size(t_dc) - cut_size);
1235         do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1236     }
1237 }
1238
1239 /* delete del_num items from buffer starting from the first'th item */
1240 static void leaf_delete_items_entirely(struct buffer_info *bi,
1241                        int first, int del_num)
1242 {
1243     struct buffer_head *bh = bi->bi_bh;
1244     int nr;
1245     int i, j;
1246     int last_loc, last_removed_loc;
1247     struct block_head *blkh;
1248     struct item_head *ih;
1249
1250     RFALSE(bh == NULL, "10210: buffer is 0");
1251     RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
1252
1253     if (del_num == 0)
1254         return;
1255
1256     blkh = B_BLK_HEAD(bh);
1257     nr = blkh_nr_item(blkh);
1258
1259     RFALSE(first < 0 || first + del_num > nr,
1260            "10220: first=%d, number=%d, there is %d items", first, del_num,
1261            nr);
1262
1263     if (first == 0 && del_num == nr) {
1264         /* this does not work */
1265         make_empty_node(bi);
1266
1267         do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1268         return;
1269     }
1270
1271     ih = item_head(bh, first);
1272
1273     /* location of unmovable item */
1274     j = (first == 0) ? bh->b_size : ih_location(ih - 1);
1275
1276     /* delete items */
1277     last_loc = ih_location(&ih[nr - 1 - first]);
1278     last_removed_loc = ih_location(&ih[del_num - 1]);
1279
1280     memmove(bh->b_data + last_loc + j - last_removed_loc,
1281         bh->b_data + last_loc, last_removed_loc - last_loc);
1282
1283     /* delete item headers */
1284     memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1285
1286     /* change item location */
1287     for (i = first; i < nr - del_num; i++)
1288         put_ih_location(&ih[i - first],
1289                 ih_location(&ih[i - first]) + (j -
1290                                  last_removed_loc));
1291
1292     /* sizes, item number */
1293     set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
1294     set_blkh_free_space(blkh,
1295                 blkh_free_space(blkh) + (j - last_removed_loc +
1296                              IH_SIZE * del_num));
1297
1298     do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1299
1300     if (bi->bi_parent) {
1301         struct disk_child *t_dc =
1302             B_N_CHILD(bi->bi_parent, bi->bi_position);
1303         put_dc_size(t_dc,
1304                 dc_size(t_dc) - (j - last_removed_loc +
1305                          IH_SIZE * del_num));
1306         do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1307     }
1308 }
1309
1310 /*
1311  * paste new_entry_count entries (new_dehs, records) into position
1312  * before to item_num-th item
1313  */
1314 void leaf_paste_entries(struct buffer_info *bi,
1315             int item_num,
1316             int before,
1317             int new_entry_count,
1318             struct reiserfs_de_head *new_dehs,
1319             const char *records, int paste_size)
1320 {
1321     struct item_head *ih;
1322     char *item;
1323     struct reiserfs_de_head *deh;
1324     char *insert_point;
1325     int i;
1326     struct buffer_head *bh = bi->bi_bh;
1327
1328     if (new_entry_count == 0)
1329         return;
1330
1331     ih = item_head(bh, item_num);
1332
1333     /*
1334      * make sure, that item is directory, and there are enough
1335      * records in it
1336      */
1337     RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
1338     RFALSE(ih_entry_count(ih) < before,
1339            "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
1340            ih_entry_count(ih), before);
1341
1342     /* first byte of dest item */
1343     item = bh->b_data + ih_location(ih);
1344
1345     /* entry head array */
1346     deh = B_I_DEH(bh, ih);
1347
1348     /* new records will be pasted at this point */
1349     insert_point =
1350         item +
1351         (before ? deh_location(&deh[before - 1])
1352          : (ih_item_len(ih) - paste_size));
1353
1354     /* adjust locations of records that will be AFTER new records */
1355     for (i = ih_entry_count(ih) - 1; i >= before; i--)
1356         put_deh_location(&deh[i],
1357                  deh_location(&deh[i]) +
1358                  (DEH_SIZE * new_entry_count));
1359
1360     /* adjust locations of records that will be BEFORE new records */
1361     for (i = 0; i < before; i++)
1362         put_deh_location(&deh[i],
1363                  deh_location(&deh[i]) + paste_size);
1364
1365     put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
1366
1367     /* prepare space for pasted records */
1368     memmove(insert_point + paste_size, insert_point,
1369         item + (ih_item_len(ih) - paste_size) - insert_point);
1370
1371     /* copy new records */
1372     memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1373            paste_size - DEH_SIZE * new_entry_count);
1374
1375     /* prepare space for new entry heads */
1376     deh += before;
1377     memmove((char *)(deh + new_entry_count), deh,
1378         insert_point - (char *)deh);
1379
1380     /* copy new entry heads */
1381     deh = (struct reiserfs_de_head *)((char *)deh);
1382     memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
1383
1384     /* set locations of new records */
1385     for (i = 0; i < new_entry_count; i++) {
1386         put_deh_location(&deh[i],
1387                  deh_location(&deh[i]) +
1388                  (-deh_location
1389                   (&new_dehs[new_entry_count - 1]) +
1390                   insert_point + DEH_SIZE * new_entry_count -
1391                   item));
1392     }
1393
1394     /* change item key if necessary (when we paste before 0-th entry */
1395     if (!before) {
1396         set_le_ih_k_offset(ih, deh_offset(new_dehs));
1397     }
1398 #ifdef CONFIG_REISERFS_CHECK
1399     {
1400         int prev, next;
1401         /* check record locations */
1402         deh = B_I_DEH(bh, ih);
1403         for (i = 0; i < ih_entry_count(ih); i++) {
1404             next =
1405                 (i <
1406                  ih_entry_count(ih) -
1407                  1) ? deh_location(&deh[i + 1]) : 0;
1408             prev = (i != 0) ? deh_location(&deh[i - 1]) : 0;
1409
1410             if (prev && prev <= deh_location(&deh[i]))
1411                 reiserfs_error(sb_from_bi(bi), "vs-10240",
1412                            "directory item (%h) "
1413                            "corrupted (prev %a, "
1414                            "cur(%d) %a)",
1415                            ih, deh + i - 1, i, deh + i);
1416             if (next && next >= deh_location(&deh[i]))
1417                 reiserfs_error(sb_from_bi(bi), "vs-10250",
1418                            "directory item (%h) "
1419                            "corrupted (cur(%d) %a, "
1420                            "next %a)",
1421                            ih, i, deh + i, deh + i + 1);
1422         }
1423     }
1424 #endif
1425
1426 }