lbalance.c

ARM 嵌入式 系统 设计与实例开发 实验教材 二源码

/* 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 (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;
  RFALSE( !dest || !src, "vs-10210: !dest || !src");
  RFALSE( last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
	  "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
  RFALSE( B_NR_ITEMS(src) < cpy_num,
	  "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src), cpy_num);
  RFALSE( cpy_num < 0,"vs-10240: cpy_num < 0 (%d)", cpy_num);

 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 (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 (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 (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 (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 (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 (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 (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 (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)
{
    memset (dest_bi, 0, sizeof (struct buffer_info));
    memset (src_bi, 0, sizeof (struct buffer_info));

    /* 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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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);
    }
    RFALSE( src_bi->bi_bh == 0 || dest_bi->bi_bh == 0,
	    "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
	    shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
}




/* 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 (&dest_bi, src_bi.bi_bh, first_last, mov_num, mov_bytes);

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

  
  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) { /* number of items in S[0] == 0 */

      RFALSE( shift_bytes != -1,
	      "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)", 
	      shift_bytes);
#ifdef CONFIG_REISERFS_CHECK
      if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
	print_cur_tb ("vs-10275");
	reiserfs_panic (tb->tb_sb, "vs-10275: leaf_shift_left: balance condition corrupted (%c)", tb->tb_mode);
      }
#endif

      if (PATH_H_POSITION (tb->tb_path, 1) == 0)
	replace_key (tb, 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->CFL[0], tb->lkey[0], S0, 0);
      
      RFALSE( (shift_bytes != -1 &&
              !(is_direntry_le_ih (B_N_PITEM_HEAD (S0, 0))
                && !I_ENTRY_COUNT (B_N_PITEM_HEAD (S0, 0)))) &&
	      (!op_is_left_mergeable (B_N_PKEY (S0, 0), S0->b_size)),
	      "vs-10280: item must be mergeable");
    }
  }
  
  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
	)
{
  //  struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
  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->CFR[0], tb->rkey[0], tb->R[0], 0);

  }

  return ret_value;
}



static void leaf_delete_items_entirely (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 (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);

    RFALSE( !bh, "10155: bh is not defined");
    RFALSE( del_num < 0, "10160: del_num can not be < 0. del_num==%d", del_num);
    RFALSE( first < 0 || first + del_num > item_amount,
	    "10165: invalid number of first item to be deleted (%d) or "
	    "no so much items (%d) to delete (only %d)", 
	    first, first + del_num, item_amount);

    if ( del_num == 0 )
	return;

    if ( first == 0 && del_num == item_amount && del_bytes == -1 ) {
	make_empty_node (cur_bi);
	do_balance_mark_leaf_dirty (cur_bi->tb, bh, 0);
	return;
    }

    if ( del_bytes == -1 )
	/* delete del_num items beginning from item in position first */
	leaf_delete_items_entirely (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 (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 (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 (cur_bi, first+1, del_num-1);

	    if (is_direntry_le_ih (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 = ih_entry_count(ih);
	    else
	        /* len = body len of item */
		len = ih_item_len(ih);

	    /* delete the part of the last item of the bh 
	       do not delete item header
	    */
	    leaf_cut_from_buffer (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 (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, free_space;
    struct block_head * blkh;
    struct item_head * ih;
    int i;
    int last_loc, unmoved_loc;
    char * to;


    blkh = B_BLK_HEAD(bh);
    nr = blkh_nr_item(blkh);
    free_space = blkh_free_space( blkh );

    /* check free space */
    RFALSE( free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
            "vs-10170: not enough free space in block %z, new item %h",
            bh, inserted_item_ih);
    RFALSE( zeros_number > ih_item_len(inserted_item_ih),
	    "vs-10172: zero number == %d, item length == %d",
            zeros_number, ih_item_len(inserted_item_ih));


    /* 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 ? ih_location( &(ih[nr - before - 1]) ) : bh->b_size;
    unmoved_loc = before ? ih_location( ih-1 ) : bh->b_size;


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

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

    /* copy body to prepared space */
    if (inserted_item_body)
	memmove (to, inserted_item_body, ih_item_len(inserted_item_ih) - zeros_number);
    else
	memset(to, '\0', 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 -= ih_item_len( &(ih[i-before]));
	put_ih_location( &(ih[i-before]), unmoved_loc );
    }
  
    /* sizes, free space, item number */
    set_blkh_nr_item( blkh, blkh_nr_item(blkh) + 1 );
    set_blkh_free_space( blkh,
                    free_space - (IH_SIZE + ih_item_len(inserted_item_ih ) ) );
    do_balance_mark_leaf_dirty (bi->tb, bh, 1);

    if (bi->bi_parent) { 
	struct disk_child *t_dc;
	t_dc = B_N_CHILD (bi->bi_parent, bi->bi_position);
	put_dc_size( t_dc, dc_size(t_dc) + (IH_SIZE + ih_item_len(inserted_item_ih)));
	do_balance_mark_internal_dirty (bi->tb, bi->bi_parent, 0);
    }
}


/* 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 (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, free_space;
    struct block_head * blkh;
    struct item_head * ih;
    int i;
    int last_loc, unmoved_loc;