linux/fs/reiserfs/lbalance.c
<<
>>
Prefs
   1/*
   2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
   3 */
   4
   5#include <linux/uaccess.h>
   6#include <linux/string.h>
   7#include <linux/time.h>
   8#include "reiserfs.h"
   9#include <linux/buffer_head.h>
  10
  11/*
  12 * copy copy_count entries from source directory item to dest buffer
  13 * (creating new item if needed)
  14 */
  15static void leaf_copy_dir_entries(struct buffer_info *dest_bi,
  16                                  struct buffer_head *source, int last_first,
  17                                  int item_num, int from, int copy_count)
  18{
  19        struct buffer_head *dest = dest_bi->bi_bh;
  20        /*
  21         * either the number of target item, or if we must create a
  22         * new item, the number of the item we will create it next to
  23         */
  24        int item_num_in_dest;
  25
  26        struct item_head *ih;
  27        struct reiserfs_de_head *deh;
  28        int copy_records_len;   /* length of all records in item to be copied */
  29        char *records;
  30
  31        ih = item_head(source, item_num);
  32
  33        RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item");
  34
  35        /*
  36         * length of all record to be copied and first byte of
  37         * the last of them
  38         */
  39        deh = B_I_DEH(source, ih);
  40        if (copy_count) {
  41                copy_records_len = (from ? deh_location(&deh[from - 1]) :
  42                                    ih_item_len(ih)) -
  43                    deh_location(&deh[from + copy_count - 1]);
  44                records =
  45                    source->b_data + ih_location(ih) +
  46                    deh_location(&deh[from + copy_count - 1]);
  47        } else {
  48                copy_records_len = 0;
  49                records = NULL;
  50        }
  51
  52        /* when copy last to first, dest buffer can contain 0 items */
  53        item_num_in_dest =
  54            (last_first ==
  55             LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest)
  56                                                               - 1);
  57
  58        /*
  59         * if there are no items in dest or the first/last item in
  60         * dest is not item of the same directory
  61         */
  62        if ((item_num_in_dest == -1) ||
  63            (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) ||
  64            (last_first == LAST_TO_FIRST
  65             && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key,
  66                                                         leaf_key(dest,
  67                                                                  item_num_in_dest))))
  68        {
  69                /* create new item in dest */
  70                struct item_head new_ih;
  71
  72                /* form item header */
  73                memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
  74                put_ih_version(&new_ih, KEY_FORMAT_3_5);
  75                /* calculate item len */
  76                put_ih_item_len(&new_ih,
  77                                DEH_SIZE * copy_count + copy_records_len);
  78                put_ih_entry_count(&new_ih, 0);
  79
  80                if (last_first == LAST_TO_FIRST) {
  81                        /* form key by the following way */
  82                        if (from < ih_entry_count(ih)) {
  83                                set_le_ih_k_offset(&new_ih,
  84                                                   deh_offset(&deh[from]));
  85                        } else {
  86                                /*
  87                                 * no entries will be copied to this
  88                                 * item in this function
  89                                 */
  90                                set_le_ih_k_offset(&new_ih, U32_MAX);
  91                                /*
  92                                 * this item is not yet valid, but we
  93                                 * want I_IS_DIRECTORY_ITEM to return 1
  94                                 * for it, so we -1
  95                                 */
  96                        }
  97                        set_le_key_k_type(KEY_FORMAT_3_5, &new_ih.ih_key,
  98                                          TYPE_DIRENTRY);
  99                }
 100
 101                /* insert item into dest buffer */
 102                leaf_insert_into_buf(dest_bi,
 103                                     (last_first ==
 104                                      LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest),
 105                                     &new_ih, NULL, 0);
 106        } else {
 107                /* prepare space for entries */
 108                leaf_paste_in_buffer(dest_bi,
 109                                     (last_first ==
 110                                      FIRST_TO_LAST) ? (B_NR_ITEMS(dest) -
 111                                                        1) : 0, MAX_US_INT,
 112                                     DEH_SIZE * copy_count + copy_records_len,
 113                                     records, 0);
 114        }
 115
 116        item_num_in_dest =
 117            (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0;
 118
 119        leaf_paste_entries(dest_bi, item_num_in_dest,
 120                           (last_first ==
 121                            FIRST_TO_LAST) ? ih_entry_count(item_head(dest,
 122                                                                          item_num_in_dest))
 123                           : 0, copy_count, deh + from, records,
 124                           DEH_SIZE * copy_count + copy_records_len);
 125}
 126
 127/*
 128 * Copy the first (if last_first == FIRST_TO_LAST) or last
 129 * (last_first == LAST_TO_FIRST) item or part of it or nothing
 130 * (see the return 0 below) from SOURCE to the end (if last_first)
 131 * or beginning (!last_first) of the DEST
 132 */
 133/* returns 1 if anything was copied, else 0 */
 134static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
 135                                   struct buffer_head *src, int last_first,
 136                                   int bytes_or_entries)
 137{
 138        struct buffer_head *dest = dest_bi->bi_bh;
 139        /* number of items in the source and destination buffers */
 140        int dest_nr_item, src_nr_item;
 141        struct item_head *ih;
 142        struct item_head *dih;
 143
 144        dest_nr_item = B_NR_ITEMS(dest);
 145
 146        /*
 147         * if ( DEST is empty or first item of SOURCE and last item of
 148         * DEST are the items of different objects or of different types )
 149         * then there is no need to treat this item differently from the
 150         * other items that we copy, so we return
 151         */
 152        if (last_first == FIRST_TO_LAST) {
 153                ih = item_head(src, 0);
 154                dih = item_head(dest, dest_nr_item - 1);
 155
 156                /* there is nothing to merge */
 157                if (!dest_nr_item
 158                    || (!op_is_left_mergeable(&ih->ih_key, src->b_size)))
 159                        return 0;
 160
 161                RFALSE(!ih_item_len(ih),
 162                       "vs-10010: item can not have empty length");
 163
 164                if (is_direntry_le_ih(ih)) {
 165                        if (bytes_or_entries == -1)
 166                                /* copy all entries to dest */
 167                                bytes_or_entries = ih_entry_count(ih);
 168                        leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0,
 169                                              bytes_or_entries);
 170                        return 1;
 171                }
 172
 173                /*
 174                 * copy part of the body of the first item of SOURCE
 175                 * to the end of the body of the last item of the DEST
 176                 * part defined by 'bytes_or_entries'; if bytes_or_entries
 177                 * == -1 copy whole body; don't create new item header
 178                 */
 179                if (bytes_or_entries == -1)
 180                        bytes_or_entries = ih_item_len(ih);
 181
 182#ifdef CONFIG_REISERFS_CHECK
 183                else {
 184                        if (bytes_or_entries == ih_item_len(ih)
 185                            && is_indirect_le_ih(ih))
 186                                if (get_ih_free_space(ih))
 187                                        reiserfs_panic(sb_from_bi(dest_bi),
 188                                                       "vs-10020",
 189                                                       "last unformatted node "
 190                                                       "must be filled "
 191                                                       "entirely (%h)", ih);
 192                }
 193#endif
 194
 195                /*
 196                 * merge first item (or its part) of src buffer with the last
 197                 * item of dest buffer. Both are of the same file
 198                 */
 199                leaf_paste_in_buffer(dest_bi,
 200                                     dest_nr_item - 1, ih_item_len(dih),
 201                                     bytes_or_entries, ih_item_body(src, ih), 0);
 202
 203                if (is_indirect_le_ih(dih)) {
 204                        RFALSE(get_ih_free_space(dih),
 205                               "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
 206                               ih);
 207                        if (bytes_or_entries == ih_item_len(ih))
 208                                set_ih_free_space(dih, get_ih_free_space(ih));
 209                }
 210
 211                return 1;
 212        }
 213
 214        /* copy boundary item to right (last_first == LAST_TO_FIRST) */
 215
 216        /*
 217         * (DEST is empty or last item of SOURCE and first item of DEST
 218         * are the items of different object or of different types)
 219         */
 220        src_nr_item = B_NR_ITEMS(src);
 221        ih = item_head(src, src_nr_item - 1);
 222        dih = item_head(dest, 0);
 223
 224        if (!dest_nr_item || !op_is_left_mergeable(&dih->ih_key, src->b_size))
 225                return 0;
 226
 227        if (is_direntry_le_ih(ih)) {
 228                /*
 229                 * bytes_or_entries = entries number in last
 230                 * item body of SOURCE
 231                 */
 232                if (bytes_or_entries == -1)
 233                        bytes_or_entries = ih_entry_count(ih);
 234
 235                leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
 236                                      src_nr_item - 1,
 237                                      ih_entry_count(ih) - bytes_or_entries,
 238                                      bytes_or_entries);
 239                return 1;
 240        }
 241
 242        /*
 243         * copy part of the body of the last item of SOURCE to the
 244         * begin of the body of the first item of the DEST; part defined
 245         * by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body;
 246         * change first item key of the DEST; don't create new item header
 247         */
 248
 249        RFALSE(is_indirect_le_ih(ih) && get_ih_free_space(ih),
 250               "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
 251               ih);
 252
 253        if (bytes_or_entries == -1) {
 254                /* bytes_or_entries = length of last item body of SOURCE */
 255                bytes_or_entries = ih_item_len(ih);
 256
 257                RFALSE(le_ih_k_offset(dih) !=
 258                       le_ih_k_offset(ih) + op_bytes_number(ih, src->b_size),
 259                       "vs-10050: items %h and %h do not match", ih, dih);
 260
 261                /* change first item key of the DEST */
 262                set_le_ih_k_offset(dih, le_ih_k_offset(ih));
 263
 264                /* item becomes non-mergeable */
 265                /* or mergeable if left item was */
 266                set_le_ih_k_type(dih, le_ih_k_type(ih));
 267        } else {
 268                /* merge to right only part of item */
 269                RFALSE(ih_item_len(ih) <= bytes_or_entries,
 270                       "vs-10060: no so much bytes %lu (needed %lu)",
 271                       (unsigned long)ih_item_len(ih),
 272                       (unsigned long)bytes_or_entries);
 273
 274                /* change first item key of the DEST */
 275                if (is_direct_le_ih(dih)) {
 276                        RFALSE(le_ih_k_offset(dih) <=
 277                               (unsigned long)bytes_or_entries,
 278                               "vs-10070: dih %h, bytes_or_entries(%d)", dih,
 279                               bytes_or_entries);
 280                        set_le_ih_k_offset(dih,
 281                                           le_ih_k_offset(dih) -
 282                                           bytes_or_entries);
 283                } else {
 284                        RFALSE(le_ih_k_offset(dih) <=
 285                               (bytes_or_entries / UNFM_P_SIZE) * dest->b_size,
 286                               "vs-10080: dih %h, bytes_or_entries(%d)",
 287                               dih,
 288                               (bytes_or_entries / UNFM_P_SIZE) * dest->b_size);
 289                        set_le_ih_k_offset(dih,
 290                                           le_ih_k_offset(dih) -
 291                                           ((bytes_or_entries / UNFM_P_SIZE) *
 292                                            dest->b_size));
 293                }
 294        }
 295
 296        leaf_paste_in_buffer(dest_bi, 0, 0, bytes_or_entries,
 297                             ih_item_body(src,
 298                                       ih) + ih_item_len(ih) - bytes_or_entries,
 299                             0);
 300        return 1;
 301}
 302
 303/*
 304 * copy cpy_mun items from buffer src to buffer dest
 305 * last_first == FIRST_TO_LAST means, that we copy cpy_num items beginning
 306 *                             from first-th item in src to tail of dest
 307 * last_first == LAST_TO_FIRST means, that we copy cpy_num items beginning
 308 *                             from first-th item in src to head of dest
 309 */
 310static void leaf_copy_items_entirely(struct buffer_info *dest_bi,
 311                                     struct buffer_head *src, int last_first,
 312                                     int first, int cpy_num)
 313{
 314        struct buffer_head *dest;
 315        int nr, free_space;
 316        int dest_before;
 317        int last_loc, last_inserted_loc, location;
 318        int i, j;
 319        struct block_head *blkh;
 320        struct item_head *ih;
 321
 322        RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST,
 323               "vs-10090: bad last_first parameter %d", last_first);
 324        RFALSE(B_NR_ITEMS(src) - first < cpy_num,
 325               "vs-10100: too few items in source %d, required %d from %d",
 326               B_NR_ITEMS(src), cpy_num, first);
 327        RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items");
 328        RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items");
 329
 330        dest = dest_bi->bi_bh;
 331
 332        RFALSE(!dest, "vs-10130: can not copy negative amount of items");
 333
 334        if (cpy_num == 0)
 335                return;
 336
 337        blkh = B_BLK_HEAD(dest);
 338        nr = blkh_nr_item(blkh);
 339        free_space = blkh_free_space(blkh);
 340
 341        /*
 342         * we will insert items before 0-th or nr-th item in dest buffer.
 343         * It depends of last_first parameter
 344         */
 345        dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;
 346
 347        /* location of head of first new item */
 348        ih = item_head(dest, dest_before);
 349
 350        RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE,
 351               "vs-10140: not enough free space for headers %d (needed %d)",
 352               B_FREE_SPACE(dest), cpy_num * IH_SIZE);
 353
 354        /* prepare space for headers */
 355        memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE);
 356
 357        /* copy item headers */
 358        memcpy(ih, item_head(src, first), cpy_num * IH_SIZE);
 359
 360        free_space -= (IH_SIZE * cpy_num);
 361        set_blkh_free_space(blkh, free_space);
 362
 363        /* location of unmovable item */
 364        j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1);
 365        for (i = dest_before; i < nr + cpy_num; i++) {
 366                location -= ih_item_len(ih + i - dest_before);
 367                put_ih_location(ih + i - dest_before, location);
 368        }
 369
 370        /* prepare space for items */
 371        last_loc = ih_location(&ih[nr + cpy_num - 1 - dest_before]);
 372        last_inserted_loc = ih_location(&ih[cpy_num - 1]);
 373
 374        /* check free space */
 375        RFALSE(free_space < j - last_inserted_loc,
 376               "vs-10150: not enough free space for items %d (needed %d)",
 377               free_space, j - last_inserted_loc);
 378
 379        memmove(dest->b_data + last_loc,
 380                dest->b_data + last_loc + j - last_inserted_loc,
 381                last_inserted_loc - last_loc);
 382
 383        /* copy items */
 384        memcpy(dest->b_data + last_inserted_loc,
 385               item_body(src, (first + cpy_num - 1)),
 386               j - last_inserted_loc);
 387
 388        /* sizes, item number */
 389        set_blkh_nr_item(blkh, nr + cpy_num);
 390        set_blkh_free_space(blkh, free_space - (j - last_inserted_loc));
 391
 392        do_balance_mark_leaf_dirty(dest_bi->tb, dest, 0);
 393
 394        if (dest_bi->bi_parent) {
 395                struct disk_child *t_dc;
 396                t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
 397                RFALSE(dc_block_number(t_dc) != dest->b_blocknr,
 398                       "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu",
 399                       (long unsigned)dest->b_blocknr,
 400                       (long unsigned)dc_block_number(t_dc));
 401                put_dc_size(t_dc,
 402                            dc_size(t_dc) + (j - last_inserted_loc +
 403                                             IH_SIZE * cpy_num));
 404
 405                do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
 406                                               0);
 407        }
 408}
 409
 410/*
 411 * This function splits the (liquid) item into two items (useful when
 412 * shifting part of an item into another node.)
 413 */
 414static void leaf_item_bottle(struct buffer_info *dest_bi,
 415                             struct buffer_head *src, int last_first,
 416                             int item_num, int cpy_bytes)
 417{
 418        struct buffer_head *dest = dest_bi->bi_bh;
 419        struct item_head *ih;
 420
 421        RFALSE(cpy_bytes == -1,
 422               "vs-10170: bytes == - 1 means: do not split item");
 423
 424        if (last_first == FIRST_TO_LAST) {
 425                /*
 426                 * if ( if item in position item_num in buffer SOURCE
 427                 * is directory item )
 428                 */
 429                ih = item_head(src, item_num);
 430                if (is_direntry_le_ih(ih))
 431                        leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
 432                                              item_num, 0, cpy_bytes);
 433                else {
 434                        struct item_head n_ih;
 435
 436                        /*
 437                         * copy part of the body of the item number 'item_num'
 438                         * of SOURCE to the end of the DEST part defined by
 439                         * 'cpy_bytes'; create new item header; change old
 440                         * item_header (????); n_ih = new item_header;
 441                         */
 442                        memcpy(&n_ih, ih, IH_SIZE);
 443                        put_ih_item_len(&n_ih, cpy_bytes);
 444                        if (is_indirect_le_ih(ih)) {
 445                                RFALSE(cpy_bytes == ih_item_len(ih)
 446                                       && get_ih_free_space(ih),
 447                                       "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
 448                                       (long unsigned)get_ih_free_space(ih));
 449                                set_ih_free_space(&n_ih, 0);
 450                        }
 451
 452                        RFALSE(op_is_left_mergeable(&ih->ih_key, src->b_size),
 453                               "vs-10190: bad mergeability of item %h", ih);
 454                        n_ih.ih_version = ih->ih_version;       /* JDM Endian safe, both le */
 455                        leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
 456                                             item_body(src, item_num), 0);
 457                }
 458        } else {
 459                /*
 460                 * if ( if item in position item_num in buffer
 461                 * SOURCE is directory item )
 462                 */
 463                ih = item_head(src, item_num);
 464                if (is_direntry_le_ih(ih))
 465                        leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
 466                                              item_num,
 467                                              ih_entry_count(ih) - cpy_bytes,
 468                                              cpy_bytes);
 469                else {
 470                        struct item_head n_ih;
 471
 472                        /*
 473                         * copy part of the body of the item number 'item_num'
 474                         * of SOURCE to the begin of the DEST part defined by
 475                         * 'cpy_bytes'; create new item header;
 476                         * n_ih = new item_header;
 477                         */
 478                        memcpy(&n_ih, ih, SHORT_KEY_SIZE);
 479
 480                        /* Endian safe, both le */
 481                        n_ih.ih_version = ih->ih_version;
 482
 483                        if (is_direct_le_ih(ih)) {
 484                                set_le_ih_k_offset(&n_ih,
 485                                                   le_ih_k_offset(ih) +
 486                                                   ih_item_len(ih) - cpy_bytes);
 487                                set_le_ih_k_type(&n_ih, TYPE_DIRECT);
 488                                set_ih_free_space(&n_ih, MAX_US_INT);
 489                        } else {
 490                                /* indirect item */
 491                                RFALSE(!cpy_bytes && get_ih_free_space(ih),
 492                                       "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
 493                                set_le_ih_k_offset(&n_ih,
 494                                                   le_ih_k_offset(ih) +
 495                                                   (ih_item_len(ih) -
 496                                                    cpy_bytes) / UNFM_P_SIZE *
 497                                                   dest->b_size);
 498                                set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
 499                                set_ih_free_space(&n_ih, get_ih_free_space(ih));
 500                        }
 501
 502                        /* set item length */
 503                        put_ih_item_len(&n_ih, cpy_bytes);
 504
 505                        /* Endian safe, both le */
 506                        n_ih.ih_version = ih->ih_version;
 507
 508                        leaf_insert_into_buf(dest_bi, 0, &n_ih,
 509                                             item_body(src, item_num) +
 510                                                ih_item_len(ih) - cpy_bytes, 0);
 511                }
 512        }
 513}
 514
 515/*
 516 * If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE
 517 * to DEST.  If cpy_bytes not equal to minus one than copy cpy_num-1 whole
 518 * items from SOURCE to DEST.  From last item copy cpy_num bytes for regular
 519 * item and cpy_num directory entries for directory item.
 520 */
 521static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
 522                           int last_first, int cpy_num, int cpy_bytes)
 523{
 524        struct buffer_head *dest;
 525        int pos, i, src_nr_item, bytes;
 526
 527        dest = dest_bi->bi_bh;
 528        RFALSE(!dest || !src, "vs-10210: !dest || !src");
 529        RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
 530               "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
 531        RFALSE(B_NR_ITEMS(src) < cpy_num,
 532               "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
 533               cpy_num);
 534        RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);
 535
 536        if (cpy_num == 0)
 537                return 0;
 538
 539        if (last_first == FIRST_TO_LAST) {
 540                /* copy items to left */
 541                pos = 0;
 542                if (cpy_num == 1)
 543                        bytes = cpy_bytes;
 544                else
 545                        bytes = -1;
 546
 547                /*
 548                 * copy the first item or it part or nothing to the end of
 549                 * the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes))
 550                 */
 551                i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
 552                cpy_num -= i;
 553                if (cpy_num == 0)
 554                        return i;
 555                pos += i;
 556                if (cpy_bytes == -1)
 557                        /*
 558                         * copy first cpy_num items starting from position
 559                         * 'pos' of SOURCE to end of DEST
 560                         */
 561                        leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
 562                                                 pos, cpy_num);
 563                else {
 564                        /*
 565                         * copy first cpy_num-1 items starting from position
 566                         * 'pos-1' of the SOURCE to the end of the DEST
 567                         */
 568                        leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
 569                                                 pos, cpy_num - 1);
 570
 571                        /*
 572                         * copy part of the item which number is
 573                         * cpy_num+pos-1 to the end of the DEST
 574                         */
 575                        leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
 576                                         cpy_num + pos - 1, cpy_bytes);
 577                }
 578        } else {
 579                /* copy items to right */
 580                src_nr_item = B_NR_ITEMS(src);
 581                if (cpy_num == 1)
 582                        bytes = cpy_bytes;
 583                else
 584                        bytes = -1;
 585
 586                /*
 587                 * copy the last item or it part or nothing to the
 588                 * begin of the DEST
 589                 * (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes));
 590                 */
 591                i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);
 592
 593                cpy_num -= i;
 594                if (cpy_num == 0)
 595                        return i;
 596
 597                pos = src_nr_item - cpy_num - i;
 598                if (cpy_bytes == -1) {
 599                        /*
 600                         * starting from position 'pos' copy last cpy_num
 601                         * items of SOURCE to begin of DEST
 602                         */
 603                        leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
 604                                                 pos, cpy_num);
 605                } else {
 606                        /*
 607                         * copy last cpy_num-1 items starting from position
 608                         * 'pos+1' of the SOURCE to the begin of the DEST;
 609                         */
 610                        leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
 611                                                 pos + 1, cpy_num - 1);
 612
 613                        /*
 614                         * copy part of the item which number is pos to
 615                         * the begin of the DEST
 616                         */
 617                        leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
 618                                         cpy_bytes);
 619                }
 620        }
 621        return i;
 622}
 623
 624/*
 625 * there are types of coping: from S[0] to L[0], from S[0] to R[0],
 626 * from R[0] to L[0]. for each of these we have to define parent and
 627 * positions of destination and source buffers
 628 */
 629static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
 630                                       struct buffer_info *dest_bi,
 631                                       struct buffer_info *src_bi,
 632                                       int *first_last,
 633                                       struct buffer_head *Snew)
 634{
 635        memset(dest_bi, 0, sizeof(struct buffer_info));
 636        memset(src_bi, 0, sizeof(struct buffer_info));
 637
 638        /* define dest, src, dest parent, dest position */
 639        switch (shift_mode) {
 640        case LEAF_FROM_S_TO_L:  /* it is used in leaf_shift_left */
 641                src_bi->tb = tb;
 642                src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 643                src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 644
 645                /* src->b_item_order */
 646                src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
 647                dest_bi->tb = tb;
 648                dest_bi->bi_bh = tb->L[0];
 649                dest_bi->bi_parent = tb->FL[0];
 650                dest_bi->bi_position = get_left_neighbor_position(tb, 0);
 651                *first_last = FIRST_TO_LAST;
 652                break;
 653
 654        case LEAF_FROM_S_TO_R:  /* it is used in leaf_shift_right */
 655                src_bi->tb = tb;
 656                src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 657                src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 658                src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
 659                dest_bi->tb = tb;
 660                dest_bi->bi_bh = tb->R[0];
 661                dest_bi->bi_parent = tb->FR[0];
 662                dest_bi->bi_position = get_right_neighbor_position(tb, 0);
 663                *first_last = LAST_TO_FIRST;
 664                break;
 665
 666        case LEAF_FROM_R_TO_L:  /* it is used in balance_leaf_when_delete */
 667                src_bi->tb = tb;
 668                src_bi->bi_bh = tb->R[0];
 669                src_bi->bi_parent = tb->FR[0];
 670                src_bi->bi_position = get_right_neighbor_position(tb, 0);
 671                dest_bi->tb = tb;
 672                dest_bi->bi_bh = tb->L[0];
 673                dest_bi->bi_parent = tb->FL[0];
 674                dest_bi->bi_position = get_left_neighbor_position(tb, 0);
 675                *first_last = FIRST_TO_LAST;
 676                break;
 677
 678        case LEAF_FROM_L_TO_R:  /* it is used in balance_leaf_when_delete */
 679                src_bi->tb = tb;
 680                src_bi->bi_bh = tb->L[0];
 681                src_bi->bi_parent = tb->FL[0];
 682                src_bi->bi_position = get_left_neighbor_position(tb, 0);
 683                dest_bi->tb = tb;
 684                dest_bi->bi_bh = tb->R[0];
 685                dest_bi->bi_parent = tb->FR[0];
 686                dest_bi->bi_position = get_right_neighbor_position(tb, 0);
 687                *first_last = LAST_TO_FIRST;
 688                break;
 689
 690        case LEAF_FROM_S_TO_SNEW:
 691                src_bi->tb = tb;
 692                src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
 693                src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
 694                src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
 695                dest_bi->tb = tb;
 696                dest_bi->bi_bh = Snew;
 697                dest_bi->bi_parent = NULL;
 698                dest_bi->bi_position = 0;
 699                *first_last = LAST_TO_FIRST;
 700                break;
 701
 702        default:
 703                reiserfs_panic(sb_from_bi(src_bi), "vs-10250",
 704                               "shift type is unknown (%d)", shift_mode);
 705        }
 706        RFALSE(!src_bi->bi_bh || !dest_bi->bi_bh,
 707               "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
 708               shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
 709}
 710
 711/*
 712 * copy mov_num items and mov_bytes of the (mov_num-1)th item to
 713 * neighbor. Delete them from source
 714 */
 715int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
 716                    int mov_bytes, struct buffer_head *Snew)
 717{
 718        int ret_value;
 719        struct buffer_info dest_bi, src_bi;
 720        int first_last;
 721
 722        leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
 723                                   &first_last, Snew);
 724
 725        ret_value =
 726            leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
 727                            mov_bytes);
 728
 729        leaf_delete_items(&src_bi, first_last,
 730                          (first_last ==
 731                           FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) -
 732                                                 mov_num), mov_num, mov_bytes);
 733
 734        return ret_value;
 735}
 736
 737/*
 738 * Shift shift_num items (and shift_bytes of last shifted item if
 739 * shift_bytes != -1) from S[0] to L[0] and replace the delimiting key
 740 */
 741int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
 742{
 743        struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
 744        int i;
 745
 746        /*
 747         * move shift_num (and shift_bytes bytes) items from S[0]
 748         * to left neighbor L[0]
 749         */
 750        i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL);
 751
 752        if (shift_num) {
 753                /* number of items in S[0] == 0 */
 754                if (B_NR_ITEMS(S0) == 0) {
 755
 756                        RFALSE(shift_bytes != -1,
 757                               "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
 758                               shift_bytes);
 759#ifdef CONFIG_REISERFS_CHECK
 760                        if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
 761                                print_cur_tb("vs-10275");
 762                                reiserfs_panic(tb->tb_sb, "vs-10275",
 763                                               "balance condition corrupted "
 764                                               "(%c)", tb->tb_mode);
 765                        }
 766#endif
 767
 768                        if (PATH_H_POSITION(tb->tb_path, 1) == 0)
 769                                replace_key(tb, tb->CFL[0], tb->lkey[0],
 770                                            PATH_H_PPARENT(tb->tb_path, 0), 0);
 771
 772                } else {
 773                        /* replace lkey in CFL[0] by 0-th key from S[0]; */
 774                        replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);
 775
 776                        RFALSE((shift_bytes != -1 &&
 777                                !(is_direntry_le_ih(item_head(S0, 0))
 778                                  && !ih_entry_count(item_head(S0, 0)))) &&
 779                               (!op_is_left_mergeable
 780                                (leaf_key(S0, 0), S0->b_size)),
 781                               "vs-10280: item must be mergeable");
 782                }
 783        }
 784
 785        return i;
 786}
 787
 788/* CLEANING STOPPED HERE */
 789
 790/*
 791 * Shift shift_num (shift_bytes) items from S[0] to the right neighbor,
 792 * and replace the delimiting key
 793 */
 794int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
 795{
 796        int ret_value;
 797
 798        /*
 799         * move shift_num (and shift_bytes) items from S[0] to
 800         * right neighbor R[0]
 801         */
 802        ret_value =
 803            leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL);
 804
 805        /* replace rkey in CFR[0] by the 0-th key from R[0] */
 806        if (shift_num) {
 807                replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
 808
 809        }
 810
 811        return ret_value;
 812}
 813
 814static void leaf_delete_items_entirely(struct buffer_info *bi,
 815                                       int first, int del_num);
 816/*
 817 * If del_bytes == -1, starting from position 'first' delete del_num
 818 * items in whole in buffer CUR.
 819 *   If not.
 820 *   If last_first == 0. Starting from position 'first' delete del_num-1
 821 *   items in whole. Delete part of body of the first item. Part defined by
 822 *   del_bytes. Don't delete first item header
 823 *   If last_first == 1. Starting from position 'first+1' delete del_num-1
 824 *   items in whole. Delete part of body of the last item . Part defined by
 825 *   del_bytes. Don't delete last item header.
 826*/
 827void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
 828                       int first, int del_num, int del_bytes)
 829{
 830        struct buffer_head *bh;
 831        int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);
 832
 833        RFALSE(!bh, "10155: bh is not defined");
 834        RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d",
 835               del_num);
 836        RFALSE(first < 0
 837               || first + del_num > item_amount,
 838               "10165: invalid number of first item to be deleted (%d) or "
 839               "no so much items (%d) to delete (only %d)", first,
 840               first + del_num, item_amount);
 841
 842        if (del_num == 0)
 843                return;
 844
 845        if (first == 0 && del_num == item_amount && del_bytes == -1) {
 846                make_empty_node(cur_bi);
 847                do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0);
 848                return;
 849        }
 850
 851        if (del_bytes == -1)
 852                /* delete del_num items beginning from item in position first */
 853                leaf_delete_items_entirely(cur_bi, first, del_num);
 854        else {
 855                if (last_first == FIRST_TO_LAST) {
 856                        /*
 857                         * delete del_num-1 items beginning from
 858                         * item in position first
 859                         */
 860                        leaf_delete_items_entirely(cur_bi, first, del_num - 1);
 861
 862                        /*
 863                         * delete the part of the first item of the bh
 864                         * do not delete item header
 865                         */
 866                        leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes);
 867                } else {
 868                        struct item_head *ih;
 869                        int len;
 870
 871                        /*
 872                         * delete del_num-1 items beginning from
 873                         * item in position first+1
 874                         */
 875                        leaf_delete_items_entirely(cur_bi, first + 1,
 876                                                   del_num - 1);
 877
 878                        ih = item_head(bh, B_NR_ITEMS(bh) - 1);
 879                        if (is_direntry_le_ih(ih))
 880                                /* the last item is directory  */
 881                                /*
 882                                 * len = numbers of directory entries
 883                                 * in this item
 884                                 */
 885                                len = ih_entry_count(ih);
 886                        else
 887                                /* len = body len of item */
 888                                len = ih_item_len(ih);
 889
 890                        /*
 891                         * delete the part of the last item of the bh
 892                         * do not delete item header
 893                         */
 894                        leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1,
 895                                             len - del_bytes, del_bytes);
 896                }
 897        }
 898}
 899
 900/* insert item into the leaf node in position before */
 901void leaf_insert_into_buf(struct buffer_info *bi, int before,
 902                          struct item_head * const inserted_item_ih,
 903                          const char * const inserted_item_body,
 904                          int zeros_number)
 905{
 906        struct buffer_head *bh = bi->bi_bh;
 907        int nr, free_space;
 908        struct block_head *blkh;
 909        struct item_head *ih;
 910        int i;
 911        int last_loc, unmoved_loc;
 912        char *to;
 913
 914        blkh = B_BLK_HEAD(bh);
 915        nr = blkh_nr_item(blkh);
 916        free_space = blkh_free_space(blkh);
 917
 918        /* check free space */
 919        RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
 920               "vs-10170: not enough free space in block %z, new item %h",
 921               bh, inserted_item_ih);
 922        RFALSE(zeros_number > ih_item_len(inserted_item_ih),
 923               "vs-10172: zero number == %d, item length == %d",
 924               zeros_number, ih_item_len(inserted_item_ih));
 925
 926        /* get item new item must be inserted before */
 927        ih = item_head(bh, before);
 928
 929        /* prepare space for the body of new item */
 930        last_loc = nr ? ih_location(&ih[nr - before - 1]) : bh->b_size;
 931        unmoved_loc = before ? ih_location(ih - 1) : bh->b_size;
 932
 933        memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
 934                bh->b_data + last_loc, unmoved_loc - last_loc);
 935
 936        to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
 937        memset(to, 0, zeros_number);
 938        to += zeros_number;
 939
 940        /* copy body to prepared space */
 941        if (inserted_item_body)
 942                memmove(to, inserted_item_body,
 943                        ih_item_len(inserted_item_ih) - zeros_number);
 944        else
 945                memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number);
 946
 947        /* insert item header */
 948        memmove(ih + 1, ih, IH_SIZE * (nr - before));
 949        memmove(ih, inserted_item_ih, IH_SIZE);
 950
 951        /* change locations */
 952        for (i = before; i < nr + 1; i++) {
 953                unmoved_loc -= ih_item_len(&ih[i - before]);
 954                put_ih_location(&ih[i - before], unmoved_loc);
 955        }
 956
 957        /* sizes, free space, item number */
 958        set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
 959        set_blkh_free_space(blkh,
 960                            free_space - (IH_SIZE +
 961                                          ih_item_len(inserted_item_ih)));
 962        do_balance_mark_leaf_dirty(bi->tb, bh, 1);
 963
 964        if (bi->bi_parent) {
 965                struct disk_child *t_dc;
 966                t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
 967                put_dc_size(t_dc,
 968                            dc_size(t_dc) + (IH_SIZE +
 969                                             ih_item_len(inserted_item_ih)));
 970                do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
 971        }
 972}
 973
 974/*
 975 * paste paste_size bytes to affected_item_num-th item.
 976 * When item is a directory, this only prepare space for new entries
 977 */
 978void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num,
 979                          int pos_in_item, int paste_size,
 980                          const char *body, int zeros_number)
 981{
 982        struct buffer_head *bh = bi->bi_bh;
 983        int nr, free_space;
 984        struct block_head *blkh;
 985        struct item_head *ih;
 986        int i;
 987        int last_loc, unmoved_loc;
 988
 989        blkh = B_BLK_HEAD(bh);
 990        nr = blkh_nr_item(blkh);
 991        free_space = blkh_free_space(blkh);
 992
 993        /* check free space */
 994        RFALSE(free_space < paste_size,
 995               "vs-10175: not enough free space: needed %d, available %d",
 996               paste_size, free_space);
 997
 998#ifdef CONFIG_REISERFS_CHECK
 999        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 */
1072static 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 */
1145void 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 */
1240static 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 */
1314void 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, old_entry_num;
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        old_entry_num = ih_entry_count(ih);
1366        put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
1367
1368        /* prepare space for pasted records */
1369        memmove(insert_point + paste_size, insert_point,
1370                item + (ih_item_len(ih) - paste_size) - insert_point);
1371
1372        /* copy new records */
1373        memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1374               paste_size - DEH_SIZE * new_entry_count);
1375
1376        /* prepare space for new entry heads */
1377        deh += before;
1378        memmove((char *)(deh + new_entry_count), deh,
1379                insert_point - (char *)deh);
1380
1381        /* copy new entry heads */
1382        deh = (struct reiserfs_de_head *)((char *)deh);
1383        memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
1384
1385        /* set locations of new records */
1386        for (i = 0; i < new_entry_count; i++) {
1387                put_deh_location(&deh[i],
1388                                 deh_location(&deh[i]) +
1389                                 (-deh_location
1390                                  (&new_dehs[new_entry_count - 1]) +
1391                                  insert_point + DEH_SIZE * new_entry_count -
1392                                  item));
1393        }
1394
1395        /* change item key if necessary (when we paste before 0-th entry */
1396        if (!before) {
1397                set_le_ih_k_offset(ih, deh_offset(new_dehs));
1398        }
1399#ifdef CONFIG_REISERFS_CHECK
1400        {
1401                int prev, next;
1402                /* check record locations */
1403                deh = B_I_DEH(bh, ih);
1404                for (i = 0; i < ih_entry_count(ih); i++) {
1405                        next =
1406                            (i <
1407                             ih_entry_count(ih) -
1408                             1) ? deh_location(&deh[i + 1]) : 0;
1409                        prev = (i != 0) ? deh_location(&deh[i - 1]) : 0;
1410
1411                        if (prev && prev <= deh_location(&deh[i]))
1412                                reiserfs_error(sb_from_bi(bi), "vs-10240",
1413                                               "directory item (%h) "
1414                                               "corrupted (prev %a, "
1415                                               "cur(%d) %a)",
1416                                               ih, deh + i - 1, i, deh + i);
1417                        if (next && next >= deh_location(&deh[i]))
1418                                reiserfs_error(sb_from_bi(bi), "vs-10250",
1419                                               "directory item (%h) "
1420                                               "corrupted (cur(%d) %a, "
1421                                               "next %a)",
1422                                               ih, i, deh + i, deh + i + 1);
1423                }
1424        }
1425#endif
1426
1427}
1428