linux/fs/reiserfs/lbalance.c
<<
>>
Prefs
   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) */
  24static 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 */
 126static 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 */
 282static 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.) */
 380static 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. */
 472static 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 */
 553static 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 || !dest_bi->bi_bh,
 630               "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
 631               shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
 632}
 633
 634/* copy mov_num items and mov_bytes of the (mov_num-1)th item to
 635   neighbor. Delete them from source */
 636int 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 */
 660int 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 */
 706int 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
 724static 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*/
 733void 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 */
 796void 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 */
 870void 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. */
 959static 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    */
1027void 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 */
1123static 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 */
1194void 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}
1302