lbalance.c

reiserfsprogs-3.6.19.tar.gz 源码 给有需要的人！

    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);