reiserfscore/lbalance.c

/*
 * Copyright 1996-2004 by Hans Reiser, licensing governed by 
 * reiserfsprogs/README
 */

#include "includes.h"


/* these are used in do_balance.c */

/* leaf_move_items
   leaf_shift_left
   leaf_shift_right
   leaf_delete_items
   leaf_insert_into_buf
   leaf_paste_in_buffer
   leaf_cut_from_buffer
   leaf_paste_entries
   */


extern struct tree_balance init_tb;
extern int init_item_pos;
extern int init_pos_in_item;
extern int init_mode;



/* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
static void leaf_copy_dir_entries (reiserfs_filsys_t * fs,
			           struct buffer_info * dest_bi, struct buffer_head * source, 
				   int last_first, int item_num, int from, int copy_count)
{
    struct buffer_head * dest = dest_bi->bi_bh;
    int item_num_in_dest;		/* either the number of target item,
					   or if we must create a new item,
					   the number of the item we will
					   create it next to */
    struct item_head * ih;
    struct reiserfs_de_head * deh;
    int copy_records_len;			/* length of all records in item to be copied */
    char * records;

    ih = B_N_PITEM_HEAD (source, item_num);

    /* length of all record to be copied and first byte of the last of them */
    deh = B_I_DEH (source, ih);
    if (copy_count) {
	copy_records_len = (from ? get_deh_location (&deh[from - 1]) : get_ih_item_len (ih)) - 
	    get_deh_location (&deh[from + copy_count - 1]);
	records = source->b_data + get_ih_location (ih) + get_deh_location (&deh[from + copy_count - 1]);
    } else {
	copy_records_len = 0;
	records = 0;
    }

    /* when copy last to first, dest buffer can contain 0 items */
    item_num_in_dest = (last_first == LAST_TO_FIRST) ? (( B_NR_ITEMS(dest) ) ? 0 : -1) : (B_NR_ITEMS(dest) - 1);

    /* if there are no items in dest or the first/last item in dest is not item of the same directory */
    if ( (item_num_in_dest == - 1) ||
	 (last_first == FIRST_TO_LAST && are_items_mergeable (B_N_PITEM_HEAD (dest, item_num_in_dest), ih, dest->b_size) == 0) ||
	 (last_first == LAST_TO_FIRST && are_items_mergeable (ih, B_N_PITEM_HEAD (dest, item_num_in_dest), dest->b_size) == 0)) {
	/* create new item in dest */
	struct item_head new_ih;

	/* form item header */
	memcpy (&new_ih.ih_key, &ih->ih_key, KEY_SIZE);

	/* calculate item len */
	set_ih_item_len (&new_ih, DEH_SIZE * copy_count + copy_records_len);
	set_ih_entry_count (&new_ih, 0);
    
	if (last_first == LAST_TO_FIRST) {
	    /* form key by the following way */
	    if (from < get_ih_entry_count (ih)) {
		set_key_offset_v1 (&new_ih.ih_key, get_deh_offset (&deh[from]));
	    } else {
		/* no entries will be copied to this item in this function */
		set_key_offset_v1 (&new_ih.ih_key, MAX_KEY1_OFFSET);
	    }
	    set_key_uniqueness (&new_ih.ih_key, DIRENTRY_UNIQUENESS);
	}
	set_ih_key_format (&new_ih, get_ih_key_format (ih));
	set_ih_flags (&new_ih, get_ih_flags (ih));
    
	/* insert item into dest buffer */
	leaf_insert_into_buf (fs, dest_bi, (last_first == LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest), &new_ih, NULL, 0);
    } else {
	/* prepare space for entries */
	leaf_paste_in_buffer (fs, dest_bi, (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0, 0xffff /*MAX_US_INT */,
			      DEH_SIZE * copy_count + copy_records_len, records, 0);
    }
  
    item_num_in_dest = (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest)-1) : 0;
  
    leaf_paste_entries (dest_bi->bi_bh, item_num_in_dest,
			(last_first == FIRST_TO_LAST) ? get_ih_entry_count (B_N_PITEM_HEAD (dest, item_num_in_dest)) : 0,
			copy_count, deh + from, records,
			DEH_SIZE * copy_count + copy_records_len
	);
}


/* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or 
   part of it or nothing (see the return 0 below) from SOURCE to the end 
   (if last_first) or beginning (!last_first) of the DEST */
/* returns 1 if anything was copied, else 0 */
static int leaf_copy_boundary_item (reiserfs_filsys_t * fs,
                                    struct buffer_info * dest_bi, struct buffer_head * src, int last_first,
				    int bytes_or_entries)
{
    struct buffer_head * dest = dest_bi->bi_bh;
    int dest_nr_item, src_nr_item; /* number of items in the source and destination buffers */
    struct item_head * ih;
    struct item_head * dih;
  
    dest_nr_item = B_NR_ITEMS(dest);
  
    if ( last_first == FIRST_TO_LAST ) {
	/* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
	   or of different types ) then there is no need to treat this item differently from the other items
	   that we copy, so we return */
	ih = B_N_PITEM_HEAD (src, 0);
	dih = B_N_PITEM_HEAD (dest, dest_nr_item - 1);
	if (!dest_nr_item || (are_items_mergeable (dih, ih, src->b_size) == 0))
	    /* there is nothing to merge */
	    return 0;
      
	if ( I_IS_DIRECTORY_ITEM(ih) ) {
	    if ( bytes_or_entries == -1 )
		/* copy all entries to dest */
		bytes_or_entries = get_ih_entry_count(ih);
	    leaf_copy_dir_entries (fs, dest_bi, src, FIRST_TO_LAST, 0, 0, bytes_or_entries);
	    return 1;
	}
      
	/* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
	   part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
	*/
	if ( bytes_or_entries == -1 )
	    bytes_or_entries = get_ih_item_len (ih);

	/* merge first item (or its part) of src buffer with the last
	   item of dest buffer. Both are of the same file */
	leaf_paste_in_buffer (fs, dest_bi, dest_nr_item - 1, get_ih_item_len (dih),
		bytes_or_entries, B_I_PITEM(src,ih), 0);
      
	if (I_IS_INDIRECT_ITEM(dih)) {
	    if (bytes_or_entries == get_ih_item_len (ih))
		//dih->u.ih_free_space = ih->u.ih_free_space;
		set_ih_free_space (dih, get_ih_free_space (ih));
	}
    
	return 1;
    }
  

    /* copy boundary item to right (last_first == LAST_TO_FIRST) */

    /* ( DEST is empty or last item of SOURCE and first item of DEST
       are the items of different object or of different types )
    */
    src_nr_item = B_NR_ITEMS (src);
    ih = B_N_PITEM_HEAD (src, src_nr_item - 1);
    dih = B_N_PITEM_HEAD (dest, 0);

    if (!dest_nr_item || are_items_mergeable (ih, dih, src->b_size) == 0)
	return 0;
  
    if ( I_IS_DIRECTORY_ITEM(ih)) {
	if ( bytes_or_entries == -1 )
	    /* bytes_or_entries = entries number in last item body of SOURCE */
	    bytes_or_entries = get_ih_entry_count(ih);
    
	leaf_copy_dir_entries (fs, dest_bi, src, LAST_TO_FIRST, src_nr_item - 1, get_ih_entry_count(ih) - bytes_or_entries, 
			       bytes_or_entries);
	return 1;
    }

    /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST;
       part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST;
       don't create new item header
    */
  
    if ( bytes_or_entries == -1 ) {
	/* bytes_or_entries = length of last item body of SOURCE */
	bytes_or_entries = get_ih_item_len (ih);

	/* change first item key of the DEST */
	//dih->ih_key.k_offset = ih->ih_key.k_offset;
	set_offset (key_format (&dih->ih_key), &dih->ih_key, get_offset (&ih->ih_key));

	/* item becomes non-mergeable */
	/* or mergeable if left item was */
	//dih->ih_key.k_uniqueness = ih->ih_key.k_uniqueness;
	set_type (key_format (&dih->ih_key), &dih->ih_key, get_type (&ih->ih_key));
    } else {
	/* merge to right only part of item */
	/* change first item key of the DEST */
	if ( I_IS_DIRECT_ITEM(dih) ) {
	    //dih->ih_key.k_offset -= bytes_or_entries;
	    set_offset (key_format (&dih->ih_key), &dih->ih_key, get_offset (&dih->ih_key) - bytes_or_entries);
	} else {
	    //dih->ih_key.k_offset -= ((bytes_or_entries/UNFM_P_SIZE)*dest->b_size);
	    set_offset (key_format (&dih->ih_key), &dih->ih_key, 
			get_offset (&dih->ih_key) - ((bytes_or_entries/UNFM_P_SIZE)*dest->b_size));
	}
    }
  
    leaf_paste_in_buffer (fs, dest_bi, 0, 0, bytes_or_entries, B_I_PITEM(src,ih) + get_ih_item_len (ih) - bytes_or_entries, 0);
    return 1;
}


/* copy cpy_mun items from buffer src to buffer dest
 * last_first == FIRST_TO_LAST means, that we copy cpy_num  items beginning from first-th item in src to tail of dest
 * last_first == LAST_TO_FIRST means, that we copy cpy_num  items beginning from first-th item in src to head of dest
 */
static void leaf_copy_items_entirely (reiserfs_filsys_t * fs, struct buffer_info * dest_bi, 
                                      struct buffer_head * src, int last_first,
				      int first, int cpy_num)
{
    struct buffer_head * dest;
    int nr;
    int dest_before;
    int last_loc, last_inserted_loc, location;
    int i, j;
    struct block_head * blkh;
    struct item_head * ih;

    dest = dest_bi->bi_bh;

    if (cpy_num == 0)
	return;

    blkh = B_BLK_HEAD(dest);
    nr = get_blkh_nr_items (blkh);
  
    /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */
    dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;

    /* location of head of first new item */
    ih = B_N_PITEM_HEAD (dest, dest_before);

    /* prepare space for headers */
    memmove (ih + cpy_num, ih, (nr-dest_before) * IH_SIZE);

    /* copy item headers */
    memcpy (ih, B_N_PITEM_HEAD (src, first), cpy_num * IH_SIZE);

    set_blkh_free_space (blkh, get_blkh_free_space (blkh) - IH_SIZE * cpy_num);

    /* location of unmovable item */
    j = location = (dest_before == 0) ? dest->b_size : get_ih_location (ih-1);
    for (i = dest_before; i < nr + cpy_num; i ++) {
	location -= get_ih_item_len (&ih[i-dest_before]);
	set_ih_location (&ih[i-dest_before], location);
    }

    /* prepare space for items */
    last_loc = get_ih_location (&ih[nr+cpy_num-1-dest_before]);
    last_inserted_loc = get_ih_location (&ih[cpy_num-1]);

    /* check free space */
    memmove (dest->b_data + last_loc,
	     dest->b_data + last_loc + j - last_inserted_loc,
	     last_inserted_loc - last_loc);

    /* copy items */
    memcpy (dest->b_data + last_inserted_loc, B_N_PITEM(src,(first + cpy_num - 1)),
	    j - last_inserted_loc);

    /* sizes, item number */
    set_blkh_nr_items (blkh, get_blkh_nr_items (blkh) + cpy_num);
    set_blkh_free_space (blkh, 
			 get_blkh_free_space (blkh) - (j - last_inserted_loc));
  
    mark_buffer_dirty (dest);

    if (dest_bi->bi_parent) {
	struct disk_child * dc;
	dc = B_N_CHILD (dest_bi->bi_parent, dest_bi->bi_position);
	set_dc_child_size (dc, get_dc_child_size (dc) + j - last_inserted_loc + IH_SIZE * cpy_num);
	mark_buffer_dirty(dest_bi->bi_parent);
    }
}


/* This function splits the (liquid) item into two items (useful when
   shifting part of an item into another node.) */
static void leaf_item_bottle (reiserfs_filsys_t * fs,
			      struct buffer_info * dest_bi, struct buffer_head * src, int last_first,
			      int item_num, int cpy_bytes)
{
    struct buffer_head * dest = dest_bi->bi_bh;
    struct item_head * ih;
  
    if ( last_first == FIRST_TO_LAST ) {
	/* if ( if item in position item_num in buffer SOURCE is directory item ) */
	if (I_IS_DIRECTORY_ITEM(ih = B_N_PITEM_HEAD(src,item_num)))
	    leaf_copy_dir_entries (fs, dest_bi, src, FIRST_TO_LAST, item_num, 0, cpy_bytes);
	else {
	    struct item_head n_ih;
      
	    /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST 
	       part defined by 'cpy_bytes'; create new item header; change old item_header (????);
	       n_ih = new item_header;
	    */
	    memcpy (&n_ih, ih, IH_SIZE);
	    set_ih_item_len (&n_ih, cpy_bytes);
	    if (I_IS_INDIRECT_ITEM(ih)) {
		//n_ih.u.ih_free_space = 0;
		set_ih_free_space (&n_ih, 0);;
	    }

	    //n_ih.ih_version = ih->ih_version;
	    set_ih_key_format (&n_ih, get_ih_key_format (ih));
	    set_ih_flags (&n_ih, get_ih_flags (ih));
	    leaf_insert_into_buf (fs, dest_bi, B_NR_ITEMS(dest), &n_ih, B_N_PITEM (src, item_num), 0);
	}
    } else {
	/*  if ( if item in position item_num in buffer SOURCE is directory item ) */
	if (I_IS_DIRECTORY_ITEM(ih = B_N_PITEM_HEAD (src, item_num)))
	    leaf_copy_dir_entries (fs, dest_bi, src, LAST_TO_FIRST, item_num, get_ih_entry_count(ih) - cpy_bytes, cpy_bytes);
	else {
	    struct item_head n_ih;
      
	    /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST 
	       part defined by 'cpy_bytes'; create new item header;
	       n_ih = new item_header;
	    */
	    memcpy (&n_ih, ih, SHORT_KEY_SIZE);
      
	    if (I_IS_DIRECT_ITEM(ih)) {
		//n_ih.ih_key.k_offset = ih->ih_key.k_offset + ih->ih_item_len - cpy_bytes;
		set_offset (key_format (&ih->ih_key), &n_ih.ih_key, get_offset (&ih->ih_key) + get_ih_item_len (ih) - cpy_bytes);
		//n_ih.ih_key.k_uniqueness = TYPE_DIRECT;
		set_type (key_format (&ih->ih_key), &n_ih.ih_key, TYPE_DIRECT);
		//n_ih.u.ih_free_space = USHRT_MAX;
		set_ih_free_space (&n_ih, USHRT_MAX);
	    } else {
		/* indirect item */
		//n_ih.ih_key.k_offset = ih->ih_key.k_offset + (ih->ih_item_len - cpy_bytes) / UNFM_P_SIZE * dest->b_size;
		set_offset (key_format (&ih->ih_key), &n_ih.ih_key,
			    get_offset (&ih->ih_key) + (get_ih_item_len (ih) - cpy_bytes) / UNFM_P_SIZE * dest->b_size);
		//n_ih.ih_key.k_uniqueness = TYPE_INDIRECT;
		set_type (key_format (&ih->ih_key), &n_ih.ih_key, TYPE_INDIRECT);
		//n_ih.u.ih_free_space = ih->u.ih_free_space;
		set_ih_free_space (&n_ih, get_ih_free_space (ih));
	    }
      
	    /* set item length */
	    set_ih_item_len (&n_ih, cpy_bytes);
	    //n_ih.ih_version = ih->ih_version;
	    set_ih_key_format (&n_ih, get_ih_key_format (ih));
	    set_ih_flags (&n_ih, get_ih_flags (ih));
	    leaf_insert_into_buf (fs, dest_bi, 0, &n_ih, B_N_PITEM(src,item_num) + get_ih_item_len (ih) - cpy_bytes, 0);
	}
    }
}


/* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
   If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
   From last item copy cpy_num bytes for regular item and cpy_num directory entries for
   directory item. */
static int leaf_copy_items (reiserfs_filsys_t * fs,
                            struct buffer_info * dest_bi, struct buffer_head * src,
			    int last_first, int cpy_num,
			    int cpy_bytes)
{
    struct buffer_head * dest;
    int pos, i, src_nr_item, bytes;

    dest = dest_bi->bi_bh;
    if ( cpy_num == 0 )
	return 0;
 
    if ( last_first == FIRST_TO_LAST ) {
	/* copy items to left */
	pos = 0;
	if ( cpy_num == 1 )
	    bytes = cpy_bytes;
	else
	    bytes = -1;
   
	/* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
	i = leaf_copy_boundary_item (fs, dest_bi, src, FIRST_TO_LAST, bytes);
	cpy_num -= i;
	if ( cpy_num == 0 )
	    return i;
	pos += i;
	if ( cpy_bytes == -1 )
	    /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
	    leaf_copy_items_entirely(fs, dest_bi, src, FIRST_TO_LAST, pos, cpy_num);
	else {
	    /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
	    leaf_copy_items_entirely(fs, dest_bi, src, FIRST_TO_LAST, pos, cpy_num-1);
	     
	    /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
	    leaf_item_bottle (fs, dest_bi, src, FIRST_TO_LAST, cpy_num+pos-1, cpy_bytes);
	} 
    } else {
	/* copy items to right */
	src_nr_item = B_NR_ITEMS (src);
	if ( cpy_num == 1 )
	    bytes = cpy_bytes;
	else
	    bytes = -1;
   
	/* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
	i = leaf_copy_boundary_item (fs, dest_bi, src, LAST_TO_FIRST, bytes);
   
	cpy_num -= i;
	if ( cpy_num == 0 )
	    return i;
   
	pos = src_nr_item - cpy_num - i;
	if ( cpy_bytes == -1 ) {
	    /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
	    leaf_copy_items_entirely(fs, dest_bi, src, LAST_TO_FIRST, pos, cpy_num);
	} else {
	    /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
	    leaf_copy_items_entirely(fs, dest_bi, src, LAST_TO_FIRST, pos+1, cpy_num-1);

	    /* copy part of the item which number is pos to the begin of the DEST */
	    leaf_item_bottle (fs, dest_bi, src, LAST_TO_FIRST, pos, cpy_bytes);
	}
    }
    return i;
}


/* there are types of coping: from S[0] to L[0], from S[0] to R[0],
   from R[0] to L[0]. for each of these we have to define parent and
   positions of destination and source buffers */
static void leaf_define_dest_src_infos (int shift_mode, struct tree_balance * tb, struct buffer_info * dest_bi,
					struct buffer_info * src_bi, int * first_last,
					struct buffer_head * Snew)
{
    /* define dest, src, dest parent, dest position */
    switch (shift_mode) {
    case LEAF_FROM_S_TO_L:    /* it is used in leaf_shift_left */
	src_bi->bi_bh = PATH_PLAST_BUFFER (tb->tb_path);
	src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
	src_bi->bi_position = PATH_H_B_ITEM_ORDER (tb->tb_path, 0);	/* src->b_item_order */
	dest_bi->bi_bh = tb->L[0];
	dest_bi->bi_parent = tb->FL[0];
	dest_bi->bi_position = get_left_neighbor_position (tb, 0);
	*first_last = FIRST_TO_LAST;
	break;

    case LEAF_FROM_S_TO_R:  /* it is used in leaf_shift_right */
	src_bi->bi_bh = PATH_PLAST_BUFFER (tb->tb_path);
	src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
	src_bi->bi_position = PATH_H_B_ITEM_ORDER (tb->tb_path, 0);
	dest_bi->bi_bh = tb->R[0];
	dest_bi->bi_parent = tb->FR[0];
	dest_bi->bi_position = get_right_neighbor_position (tb, 0);
	*first_last = LAST_TO_FIRST;
	break;

    case LEAF_FROM_R_TO_L:  /* it is used in balance_leaf_when_delete */
	src_bi->bi_bh = tb->R[0];
	src_bi->bi_parent = tb->FR[0];
	src_bi->bi_position = get_right_neighbor_position (tb, 0);
	dest_bi->bi_bh = tb->L[0];
	dest_bi->bi_parent = tb->FL[0];
	dest_bi->bi_position = get_left_neighbor_position (tb, 0);
	*first_last = FIRST_TO_LAST;
	break;
    
    case LEAF_FROM_L_TO_R:  /* it is used in balance_leaf_when_delete */
	src_bi->bi_bh = tb->L[0];
	src_bi->bi_parent = tb->FL[0];
	src_bi->bi_position = get_left_neighbor_position (tb, 0);
	dest_bi->bi_bh = tb->R[0];
	dest_bi->bi_parent = tb->FR[0];
	dest_bi->bi_position = get_right_neighbor_position (tb, 0);
	*first_last = LAST_TO_FIRST;
	break;

    case LEAF_FROM_S_TO_SNEW:
	src_bi->bi_bh = PATH_PLAST_BUFFER (tb->tb_path);
	src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
	src_bi->bi_position = PATH_H_B_ITEM_ORDER (tb->tb_path, 0);
	dest_bi->bi_bh = Snew;
	dest_bi->bi_parent = 0;
	dest_bi->bi_position = 0;
	*first_last = LAST_TO_FIRST;
	break;
    
    default:
	reiserfs_panic (0, "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)", shift_mode);
    }
}




/* copy mov_num items and mov_bytes of the (mov_num-1)th item to
   neighbor. Delete them from source */
int leaf_move_items (int shift_mode, struct tree_balance * tb, 
		     int mov_num, int mov_bytes, struct buffer_head * Snew)
{
    int ret_value;
    struct buffer_info dest_bi, src_bi;
    int first_last;

    leaf_define_dest_src_infos (shift_mode, tb, &dest_bi, &src_bi, &first_last, Snew);

    ret_value = leaf_copy_items (tb->tb_fs, &dest_bi, src_bi.bi_bh, first_last, mov_num, mov_bytes);

    leaf_delete_items (tb->tb_fs, &src_bi, first_last, (first_last == FIRST_TO_LAST) ? 0 : 
		       (B_NR_ITEMS(src_bi.bi_bh) - mov_num), mov_num, mov_bytes);

  
    return ret_value;
}


/* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1)
   from S[0] to L[0] and replace the delimiting key */
int leaf_shift_left (struct tree_balance * tb, int shift_num, int shift_bytes)
{
    struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
    int i;

    /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */
    i = leaf_move_items (LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, 0);

    if ( shift_num ) {
	if (B_NR_ITEMS (S0) == 0) { 
	    /* everything is moved from S[0] */
	    if (PATH_H_POSITION (tb->tb_path, 1) == 0)
		replace_key(tb->tb_fs, tb->CFL[0], tb->lkey[0], PATH_H_PPARENT (tb->tb_path, 0), 0);
	} else {
	    /* replace lkey in CFL[0] by 0-th key from S[0]; */
	    replace_key(tb->tb_fs, tb->CFL[0], tb->lkey[0], S0, 0);
      
	}
    }
  
    return i;
}





/* CLEANING STOPPED HERE */




/* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
int leaf_shift_right (struct tree_balance * tb, int shift_num, int shift_bytes)
{
    int ret_value;

    /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */
    ret_value = leaf_move_items (LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, 0);

    /* replace rkey in CFR[0] by the 0-th key from R[0] */
    if (shift_num) {
	replace_key(tb->tb_fs, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
    }

    return ret_value;
}



static void leaf_delete_items_entirely (reiserfs_filsys_t * sb,
					/*struct reiserfs_transaction_handle *th,*/
					struct buffer_info * bi,
					int first,
					int del_num);
/*  If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
    If not. 
    If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of
    the first item. Part defined by del_bytes. Don't delete first item header
    If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of
    the last item . Part defined by del_bytes. Don't delete last item header.
*/
void leaf_delete_items (reiserfs_filsys_t * fs,
			struct buffer_info * cur_bi,
			int last_first, 
			int first, int del_num, int del_bytes)
{
    struct buffer_head * bh;
    int item_amount = B_NR_ITEMS (bh = cur_bi->bi_bh);
    
    if ( del_num == 0 )
	return;
    
    if ( first == 0 && del_num == item_amount && del_bytes == -1 ) {
	make_empty_node (cur_bi);
	mark_buffer_dirty (bh);
	return;
    }
    
    if ( del_bytes == -1 )
	/* delete del_num items beginning from item in position first */
	leaf_delete_items_entirely (fs, cur_bi, first, del_num);
    else {
	if ( last_first == FIRST_TO_LAST ) {
	    /* delete del_num-1 items beginning from item in position first  */
	    leaf_delete_items_entirely (fs, cur_bi, first, del_num-1);
	    
	    /* delete the part of the first item of the bh do not
	       delete item header */
	    leaf_cut_from_buffer (fs, cur_bi, 0, 0, del_bytes);
	} else  {
	    struct item_head * ih;
	    int len;
	    
	    /* delete del_num-1 items beginning from item in position first+1  */
	    leaf_delete_items_entirely (fs, cur_bi, first+1, del_num-1);
	    
	    if (I_IS_DIRECTORY_ITEM(ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh)-1))) 	/* the last item is directory  */
	        /* len = numbers of directory entries in this item */
	        len = get_ih_entry_count(ih);
	    else
		/* len = body len of item */
 	        len = get_ih_item_len (ih);
	    
	    /* delete the part of the last item of the bh 
	       do not delete item header
	    */
	    leaf_cut_from_buffer (fs, cur_bi, B_NR_ITEMS(bh) - 1, len - del_bytes, del_bytes);
	}
    }
}


/* insert item into the leaf node in position before */
void leaf_insert_into_buf (reiserfs_filsys_t * s,
			   struct buffer_info * bi,
			   int before,
			   struct item_head * inserted_item_ih,
			   const char * inserted_item_body,
			   int zeros_number
			   )
{
    struct buffer_head * bh = bi->bi_bh;
    int nr;
    struct block_head * blkh;
    struct item_head * ih;
    int i;
    int last_loc, unmoved_loc;
    char * to;

    blkh = B_BLK_HEAD (bh);
    nr = get_blkh_nr_items (blkh);

    /* get item new item must be inserted before */
    ih = B_N_PITEM_HEAD (bh, before);

    /* prepare space for the body of new item */
    last_loc = nr ? get_ih_location (&ih[nr - before - 1]) : bh->b_size;
    unmoved_loc = before ? get_ih_location (ih-1) : bh->b_size;

    memmove (bh->b_data + last_loc - get_ih_item_len (inserted_item_ih), 
	     bh->b_data + last_loc, unmoved_loc - last_loc);

    to = bh->b_data + unmoved_loc - get_ih_item_len (inserted_item_ih);
    memset (to, 0, zeros_number);
    to += zeros_number;

    /* copy body to prepared space */
    if (inserted_item_body)
	//if (mem_mode == REISERFS_USER_MEM)
	//  copy_from_user (to, inserted_item_body, inserted_item_ih->ih_item_len - zeros_number);
	//else {
	memmove (to, inserted_item_body, get_ih_item_len (inserted_item_ih) - zeros_number);
    //}
    else
	memset(to, '\0', get_ih_item_len (inserted_item_ih) - zeros_number);
  
    /* insert item header */
    memmove (ih + 1, ih, IH_SIZE * (nr - before));
    memmove (ih, inserted_item_ih, IH_SIZE);
  
    /* change locations */
    for (i = before; i < nr + 1; i ++) {
	unmoved_loc -= get_ih_item_len (&ih[i-before]);
	set_ih_location (&ih[i-before], unmoved_loc);
    }
  
    /* sizes, free space, item number */
    set_blkh_nr_items (blkh, get_blkh_nr_items (blkh) + 1);
    set_blkh_free_space (blkh, get_blkh_free_space (blkh) -
			 (IH_SIZE + get_ih_item_len (inserted_item_ih)));

    mark_buffer_dirty(bh) ;

    if (bi->bi_parent) { 
	struct disk_child * dc;

	dc = B_N_CHILD (bi->bi_parent, bi->bi_position);
	set_dc_child_size (dc, get_dc_child_size (dc) + IH_SIZE + get_ih_item_len (inserted_item_ih));
	mark_buffer_dirty(bi->bi_parent) ;
    }

    if (is_a_leaf(bh->b_data, bh->b_size) != THE_LEAF)
	reiserfs_panic ("leaf_insert_into_buf: bad leaf %lu: %b", bh->b_blocknr, bh);
}


/* paste paste_size bytes to affected_item_num-th item. 
   When item is a directory, this only prepare space for new entries */
void leaf_paste_in_buffer (reiserfs_filsys_t * fs,
			   struct buffer_info * bi,
			   int affected_item_num,
			   int pos_in_item,
			   int paste_size,
			   const char * body,
			   int zeros_number)
{
    struct buffer_head * bh = bi->bi_bh;
    int nr;
    struct block_head * blkh;
    struct item_head * ih;
    int i;
    int last_loc, unmoved_loc;


    blkh = B_BLK_HEAD (bh);
    nr = get_blkh_nr_items (blkh);

    /* item to be appended */
    ih = B_N_PITEM_HEAD(bh, affected_item_num);

    last_loc = get_ih_location (&ih[nr - affected_item_num - 1]);
    unmoved_loc = affected_item_num ? get_ih_location (ih-1) : bh->b_size;  

    /* prepare space */
    memmove (bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
	     unmoved_loc - last_loc);


    /* change locations */
    for (i = affected_item_num; i < nr; i ++)
	set_ih_location (&ih[i-affected_item_num], get_ih_location (&ih[i-affected_item_num]) - paste_size);

    if ( body ) {
	if (!I_IS_DIRECTORY_ITEM(ih)) {
	    //if (mem_mode == REISERFS_USER_MEM) {
	    //memset (bh->b_data + unmoved_loc - paste_size, 0, zeros_number);
	    //copy_from_user (bh->b_data + unmoved_loc - paste_size + zeros_number, body, paste_size - zeros_number);
	    //} else 
	    {
		if (!pos_in_item) {
		    /* shift data to right */
		    memmove (bh->b_data + get_ih_location (ih) + paste_size, 
			     bh->b_data + get_ih_location (ih), get_ih_item_len (ih));
		    /* paste data in the head of item */
		    memset (bh->b_data + get_ih_location (ih), 0, zeros_number);
		    memcpy (bh->b_data + get_ih_location (ih) + zeros_number, body, paste_size - zeros_number);
		} else {
		    memset (bh->b_data + unmoved_loc - paste_size, 0, zeros_number);
		    memcpy (bh->b_data + unmoved_loc - paste_size + zeros_number, body, paste_size - zeros_number);
		}
	    }
	}
    }
    else
	memset(bh->b_data + unmoved_loc - paste_size,'\0',paste_size);

    set_ih_item_len (ih, get_ih_item_len (ih) + paste_size);

    /* change free space */
    set_blkh_free_space (blkh, get_blkh_free_space (blkh) - paste_size);

    mark_buffer_dirty(bh) ;

    if (bi->bi_parent) { 
	struct disk_child * dc;

	dc = B_N_CHILD (bi->bi_parent, bi->bi_position);
	set_dc_child_size (dc, get_dc_child_size (dc) + paste_size);
	mark_buffer_dirty(bi->bi_parent);
    }
    if (is_a_leaf(bh->b_data, bh->b_size) != THE_LEAF)
	reiserfs_panic ("leaf_paste_in_buffer: bad leaf %lu: %b", bh->b_blocknr, bh);
}


/* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
   does not have free space, so it moves DEHs and remaining records as
   necessary. Return value is size of removed part of directory item
   in bytes. */
static int leaf_cut_entries (struct buffer_head * bh,
			     struct item_head * ih, 
			     int from, int del_count)
{
    char * item;
    struct reiserfs_de_head * deh;
    int prev_record_offset;	/* offset of record, that is (from-1)th */
    char * prev_record;		/* */
    int cut_records_len;		/* length of all removed records */
    int i;
    int entry_count;


    /* first byte of item */
    item = B_I_PITEM (bh, ih);

    /* entry head array */
    deh = B_I_DEH (bh, ih);
    entry_count = get_ih_entry_count (ih);

    if (del_count == 0) {
	int shift;
	int last_location;

	last_location = get_deh_location (deh + entry_count - 1);
	shift = last_location - DEH_SIZE * entry_count;
	
	memmove (deh + entry_count, item + last_location,
		 get_ih_item_len (ih) - last_location);
	for (i = 0; i < entry_count; i ++)
	    set_deh_location (&deh[i], get_deh_location (&deh[i]) - shift);

	return shift;
    }

    /* first byte of remaining entries, those are BEFORE cut entries
       (prev_record) and length of all removed records (cut_records_len) */
    prev_record_offset = (from ? get_deh_location (&deh[from - 1]) : get_ih_item_len (ih));
    cut_records_len = prev_record_offset/*from_record*/ - get_deh_location (&deh[from + del_count - 1]);
    prev_record = item + prev_record_offset;


    /* adjust locations of remaining entries */
    for (i = get_ih_entry_count (ih) - 1; i > from + del_count - 1; i --) {
	set_deh_location (deh + i, get_deh_location (deh + i) - (DEH_SIZE * del_count));
    }

    for (i = 0; i < from; i ++) {
	set_deh_location (deh + i, get_deh_location (deh + i) - (DEH_SIZE * del_count + cut_records_len));
    }

    set_ih_entry_count (ih, get_ih_entry_count (ih) - del_count);

    /* shift entry head array and entries those are AFTER removed entries */
    memmove ((char *)(deh + from),
	     deh + from + del_count, 
	     prev_record - cut_records_len - (char *)(deh + from + del_count));
  
    /* shift records, those are BEFORE removed entries */
    memmove (prev_record - cut_records_len - DEH_SIZE * del_count,
	     prev_record, item + get_ih_item_len (ih) - prev_record);

    return DEH_SIZE * del_count + cut_records_len;
}


/*  when cut item is part of regular file
        pos_in_item - first byte that must be cut
        cut_size - number of bytes to be cut beginning from pos_in_item
 
   when cut item is part of directory
        pos_in_item - number of first deleted entry
        cut_size - count of deleted entries
    */
void leaf_cut_from_buffer (reiserfs_filsys_t * fs,
			   struct buffer_info * bi, int cut_item_num,
			   int pos_in_item, int cut_size)
{
    int nr;
    struct buffer_head * bh = bi->bi_bh;
    struct block_head * blkh;
    struct item_head * ih;
    int last_loc, unmoved_loc;
    int i;

    blkh = B_BLK_HEAD (bh);
    nr = get_blkh_nr_items (blkh);

    /* item head of truncated item */
    ih = B_N_PITEM_HEAD (bh, cut_item_num);

    if (I_IS_DIRECTORY_ITEM (ih)) {
        /* first cut entry ()*/
        cut_size = leaf_cut_entries (bh, ih, pos_in_item, cut_size);
        if (pos_in_item == 0) {
            /* change item key by key of first entry in the item */
	    set_key_offset_v1 (&ih->ih_key, get_deh_offset (B_I_DEH (bh, ih)));
            /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE);*/
	}
    } else {
        /* item is direct or indirect */
        /* shift item body to left if cut is from the head of item */
        if (pos_in_item == 0) {
	    memmove (bh->b_data + get_ih_location (ih),
		     bh->b_data + get_ih_location (ih) + cut_size,
		     get_ih_item_len (ih) - cut_size);

            /* change key of item */
            if (I_IS_DIRECT_ITEM(ih)) {
                //ih->ih_key.k_offset += cut_size;
                set_offset (key_format (&ih->ih_key), &ih->ih_key, get_offset (&ih->ih_key) + cut_size);
            } else {
                //ih->ih_key.k_offset += (cut_size / UNFM_P_SIZE) * bh->b_size;
                set_offset (key_format (&ih->ih_key), &ih->ih_key, 
			    get_offset (&ih->ih_key) + (cut_size / UNFM_P_SIZE) * bh->b_size);
	    }
	}
    }
  

    /* location of the last item */
    last_loc = get_ih_location (&ih[nr - cut_item_num - 1]);

    /* location of the item, which is remaining at the same place */
    unmoved_loc = cut_item_num ? get_ih_location (ih-1) : bh->b_size;


    /* shift */
    memmove (bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
	       unmoved_loc - last_loc - cut_size);

    /* change item length */
    set_ih_item_len (ih, get_ih_item_len (ih) - cut_size);
  
    if (I_IS_INDIRECT_ITEM(ih)) {
        if (pos_in_item)
            //ih->u.ih_free_space = 0;
            set_ih_free_space (ih, 0);
    }

    /* change locations */
    for (i = cut_item_num; i < nr; i ++) {
	set_ih_location (&ih[i-cut_item_num], get_ih_location (&ih[i-cut_item_num]) + cut_size);
    }

    /* size, free space */
    set_blkh_free_space (blkh, get_blkh_free_space (blkh) + cut_size);

    mark_buffer_dirty(bh);
    
    if (bi->bi_parent) {
	struct disk_child * dc;

	dc = B_N_CHILD (bi->bi_parent, bi->bi_position);
	set_dc_child_size (dc, get_dc_child_size (dc) - cut_size);
	mark_buffer_dirty(bi->bi_parent);
    }
    if (is_a_leaf(bh->b_data, bh->b_size) != THE_LEAF &&
	is_a_leaf(bh->b_data, bh->b_size) != HAS_IH_ARRAY)
	reiserfs_panic ("leaf_cut_from_buffer: bad leaf %lu: %b",
			bh->b_blocknr, bh);
}


/* delete del_num items from buffer starting from the first'th item */
static void leaf_delete_items_entirely (reiserfs_filsys_t * fs,
					struct buffer_info * bi,
					int first, int del_num)
{
    struct buffer_head * bh = bi->bi_bh;
    int nr;
    int i, j;
    int last_loc, last_removed_loc;
    struct block_head * blkh;
    struct item_head * ih;

    if (del_num == 0)
	return;
    
    blkh = B_BLK_HEAD (bh);
    nr = get_blkh_nr_items (blkh);

    if (first == 0 && del_num == nr) {
	/* this does not work */
	make_empty_node (bi);
	
	mark_buffer_dirty(bh);
	return;
    }
    
    ih = B_N_PITEM_HEAD (bh, first);
    
    /* location of unmovable item */
    j = (first == 0) ? bh->b_size : get_ih_location (ih-1);
    
    /* delete items */
    last_loc = get_ih_location (&ih[nr - 1 - first]);
    last_removed_loc = get_ih_location (&ih[del_num-1]);
    
    memmove (bh->b_data + last_loc + j - last_removed_loc,
	     bh->b_data + last_loc, last_removed_loc - last_loc);
    
    /* delete item headers */
    memmove (ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
    
    /* change item location */
    for (i = first; i < nr - del_num; i ++) {
	set_ih_location (&ih[i-first], get_ih_location (&ih[i-first]) + j - last_removed_loc);
    }
    
    /* sizes, item number */
    set_blkh_nr_items (blkh, get_blkh_nr_items (blkh)/*nr*/ - del_num);
    set_blkh_free_space (blkh, get_blkh_free_space (blkh) + j - last_removed_loc + IH_SIZE * del_num);
    
    mark_buffer_dirty(bh);
    
    if (bi->bi_parent) {
	struct disk_child * dc;

	dc = B_N_CHILD (bi->bi_parent, bi->bi_position);
	set_dc_child_size (dc, get_dc_child_size (dc) - 
	    (j - last_removed_loc + IH_SIZE * del_num));
	mark_buffer_dirty(bi->bi_parent);
    }
    if (is_a_leaf(bh->b_data, bh->b_size) != THE_LEAF &&
	is_a_leaf(bh->b_data, bh->b_size) != HAS_IH_ARRAY)
	reiserfs_panic ("leaf_delete_items_entirely: bad leaf %lu: %b", bh->b_blocknr, bh);
}





/* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
void leaf_paste_entries (struct buffer_head * bh,
			 int item_num, int before, int new_entry_count,
			 struct reiserfs_de_head * new_dehs,
			 const char * records, int paste_size)
{
    struct item_head * ih;
    char * item;
    struct reiserfs_de_head * deh;
    char * insert_point;
    int i, old_entry_num;

    if (new_entry_count == 0)
        return;

    ih = B_N_PITEM_HEAD(bh, item_num);

    /* first byte of dest item */
    item = B_I_PITEM (bh, ih);

    /* entry head array */
    deh = B_I_DEH (bh, ih);

    /* new records will be pasted at this point */
    insert_point = item + (before ? get_deh_location (&deh[before - 1]) : (get_ih_item_len (ih) - paste_size));

    /* adjust locations of records that will be AFTER new records */
    for (i = get_ih_entry_count (ih) - 1; i >= before; i --)
	set_deh_location (deh + i, get_deh_location (deh + i) + DEH_SIZE * new_entry_count);

    /* adjust locations of records that will be BEFORE new records */
    for (i = 0; i < before; i ++)
	set_deh_location (deh + i, get_deh_location (deh + i) + paste_size);

    old_entry_num = get_ih_entry_count (ih);
    //I_ENTRY_COUNT(ih) += new_entry_count;
    set_ih_entry_count (ih, old_entry_num + new_entry_count);

    /* prepare space for pasted records */
    memmove (insert_point + paste_size, insert_point, item + (get_ih_item_len (ih) - paste_size) - insert_point);

    /* copy new records */
    memcpy (insert_point + DEH_SIZE * new_entry_count, records,
	    paste_size - DEH_SIZE * new_entry_count);
  
    /* prepare space for new entry heads */
    deh += before;
    memmove ((char *)(deh + new_entry_count), deh, insert_point - (char *)deh);

    /* copy new entry heads */
    memcpy (deh, new_dehs, DEH_SIZE * new_entry_count);

    /* set locations of new records */
    for (i = 0; i < new_entry_count; i ++)
	set_deh_location (deh + i,
			  get_deh_location (deh + i) + (- get_deh_location (&new_dehs[new_entry_count - 1]) +
							insert_point + DEH_SIZE * new_entry_count - item));


    /* change item key if neccessary (when we paste before 0-th entry */
    if (!before)
	set_key_offset_v1 (&ih->ih_key, get_deh_offset (new_dehs));
}



/* wrappers for operations on one separated node */

void delete_item (reiserfs_filsys_t * fs,
		  struct buffer_head * bh, int item_num)
{
    struct buffer_info bi;

    bi.bi_bh = bh;
    bi.bi_parent = 0;
    bi.bi_position = 0;
    leaf_delete_items_entirely (fs, &bi, item_num, 1);
}


void cut_entry (reiserfs_filsys_t * fs, struct buffer_head * bh,
		int item_num, int entry_num, int del_count)
{
    struct buffer_info bi;

    bi.bi_bh = bh;
    bi.bi_parent = 0;
    bi.bi_position = 0;
    leaf_cut_from_buffer (fs, &bi, item_num, entry_num, del_count);
}