fs/reiserfs/lbalance.c

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