fs/reiserfs/lbalance.c

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