fix_node.c

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

       /* Since we are working on internal nodes, and our internal nodes have
	  fixed size entries, then we can balance by the number of items
	  rather than the space they consume.  In this routine we set the left
	  node equal to the right node, allowing a difference of less than or
	  equal to 1 child pointer. */
	to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 - 
	    (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
	set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);
	return CARRY_ON;
    }
    
    /* all contents of S[0] can be moved into its neighbors S[0] will be
       removed after balancing. */
    if (!h && is_leaf_removable (tb))
       return CARRY_ON;
    
    
    /* why do we perform this check here rather than earlier??
       Answer: we can win 1 node in some cases above. Moreover we
       checked it above, when we checked, that S[0] is not removable
       in principle */
    if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
	if ( ! h )
	 tb->s0num = vn->vn_nr_item;
	set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
	return NO_BALANCING_NEEDED;
    }
    
    
    {
	int lpar, rpar, nset, lset, rset, lrset;
	/* 
	 * regular overflowing of the node
	 */

	/* get_num_ver works in 2 modes (FLOW & NO_FLOW) lpar, rpar - number
	   of items we can shift to left/right neighbor (including splitting
	   item) nset, lset, rset, lrset - shows, whether flowing items give
	   better packing */
#define FLOW 1
#define NO_FLOW 0	/* do not any splitting */
	
     /* we choose one the following */
#define NOTHING_SHIFT_NO_FLOW	0
#define NOTHING_SHIFT_FLOW	5
#define LEFT_SHIFT_NO_FLOW	10
#define LEFT_SHIFT_FLOW		15
#define RIGHT_SHIFT_NO_FLOW	20
#define RIGHT_SHIFT_FLOW	25
#define LR_SHIFT_NO_FLOW	30
#define LR_SHIFT_FLOW		35


	lpar = tb->lnum[h];
	rpar = tb->rnum[h];
	

	/* calculate number of blocks S[h] must be split into when nothing is
	   shifted to the neighbors, as well as number of items in each part
	   of the split node (s012 numbers), and number of bytes (s1bytes) of
	   the shared drop which flow to S1 if any */
	nset = NOTHING_SHIFT_NO_FLOW;
	nver = get_num_ver (vn->vn_mode, tb, h,
			    0, -1, h?vn->vn_nr_item:0, -1, 
			    snum012, NO_FLOW);
	
	if (!h)	{
	    int nver1;
	    
	    /* note, that in this case we try to bottle between S[0] and S1
               (S1 - the first new node) */
	    nver1 = get_num_ver (vn->vn_mode, tb, h, 
				 0, -1, 0, -1, 
				 snum012 + NOTHING_SHIFT_FLOW, FLOW);
	    if (nver > nver1)
		nset = NOTHING_SHIFT_FLOW, nver = nver1;
	}
	
	
	/* calculate number of blocks S[h] must be split into when l_shift_num
	   first items and l_shift_bytes of the right most liquid item to be
	   shifted are shifted to the left neighbor, as well as number of
	   items in each part of the split node (s012 numbers), and number
	   of bytes (s1bytes) of the shared drop which flow to S1 if any */
	lset = LEFT_SHIFT_NO_FLOW;
	lnver = get_num_ver (vn->vn_mode, tb, h, 
			     lpar - (( h || tb->lbytes == -1 ) ? 0 : 1), -1, h ? vn->vn_nr_item:0, -1,
			     snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
	if (!h)	{
	    int lnver1;
	    
	    lnver1 = get_num_ver (vn->vn_mode, tb, h, 
				  lpar - ((tb->lbytes != -1) ? 1 : 0), tb->lbytes, 0, -1,
				  snum012 + LEFT_SHIFT_FLOW, FLOW);
	    if (lnver > lnver1)
		lset = LEFT_SHIFT_FLOW, lnver = lnver1;
	}
	
	
	/* calculate number of blocks S[h] must be split into when r_shift_num
	   first items and r_shift_bytes of the left most liquid item to be
	   shifted are shifted to the right neighbor, as well as number of
	   items in each part of the splitted node (s012 numbers), and number
	   of bytes (s1bytes) of the shared drop which flow to S1 if any */
	rset = RIGHT_SHIFT_NO_FLOW;
	rnver = get_num_ver (vn->vn_mode, tb, h, 
			     0, -1, h ? (vn->vn_nr_item-rpar) : (rpar - (( tb->rbytes != -1 ) ? 1 : 0)), -1, 
			     snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
	if (!h)	{
	    int rnver1;
	    
	    rnver1 = get_num_ver (vn->vn_mode, tb, h, 
				  0, -1, (rpar - ((tb->rbytes != -1) ? 1 : 0)), tb->rbytes, 
				  snum012 + RIGHT_SHIFT_FLOW, FLOW);
	    
	    if (rnver > rnver1)
		rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
	}
	
	
	/* calculate number of blocks S[h] must be split into when items are
	   shifted in both directions, as well as number of items in each part
	   of the splitted node (s012 numbers), and number of bytes (s1bytes)
	   of the shared drop which flow to S1 if any */
	lrset = LR_SHIFT_NO_FLOW;
	lrnver = get_num_ver (vn->vn_mode, tb, h, 
			      lpar - ((h || tb->lbytes == -1) ? 0 : 1), -1, h ? (vn->vn_nr_item-rpar):(rpar - ((tb->rbytes != -1) ? 1 : 0)), -1,
			      snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
	if (!h)	{
	    int lrnver1;
	    
	    lrnver1 = get_num_ver (vn->vn_mode, tb, h, 
				   lpar - ((tb->lbytes != -1) ? 1 : 0), tb->lbytes, (rpar - ((tb->rbytes != -1) ? 1 : 0)), tb->rbytes,
				   snum012 + LR_SHIFT_FLOW, FLOW);
	    if (lrnver > lrnver1)
		lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
	}
	
	
	
	/* Our general shifting strategy is:
	   1) to minimized number of new nodes;
	   2) to minimized number of neighbors involved in shifting;
	   3) to minimized number of disk reads; */
	
	/* we can win TWO or ONE nodes by shifting in both directions */
	if (lrnver < lnver && lrnver < rnver) {
	    if (lrset == LR_SHIFT_FLOW)
		set_parameters (tb, h, tb->lnum[h], tb->rnum[h], lrnver, snum012 + lrset,
				tb->lbytes, tb->rbytes);
	    else
		set_parameters (tb, h, tb->lnum[h] - ((tb->lbytes == -1) ? 0 : 1), 
				tb->rnum[h] - ((tb->rbytes == -1) ? 0 : 1), lrnver, snum012 + lrset, -1, -1);
	    
	    return CARRY_ON;
	}
	
	/* if shifting doesn't lead to better packing then don't shift */
	if (nver == lrnver) {
	    set_parameters (tb, h, 0, 0, nver, snum012 + nset, -1, -1);
	    return CARRY_ON;
	}

	/* now we know that for better packing shifting in only one direction
	   either to the left or to the right is required */

	/*  if shifting to the left is better than shifting to the right */
	if (lnver < rnver) {
	    SET_PAR_SHIFT_LEFT;
	    return CARRY_ON;
	}

	/* if shifting to the right is better than shifting to the left */
	if (lnver > rnver) {
	    SET_PAR_SHIFT_RIGHT;
	    return CARRY_ON;
	}

	/* now shifting in either direction gives the same number of nodes and
	   we can make use of the cached neighbors */
	if (is_left_neighbor_in_cache (tb,h)) {
	    SET_PAR_SHIFT_LEFT;
	    return CARRY_ON;
	}
	
	/* shift to the right independently on whether the right neighbor in
           cache or not */
	SET_PAR_SHIFT_RIGHT;
	return CARRY_ON;
    }
}


/* Check whether current node S[h] is balanced when Decreasing its size by
 * Deleting or Cutting for INTERNAL node of internal tree.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	i - insert, p - paste;
 * Returns:	1 - schedule occured; 
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 *
 * Note: Items of internal nodes have fixed size, so the balance condition for
 * the internal part of internal tree is as for the B-trees.
 */
static int dc_check_balance_internal (struct tree_balance * tb, int h)
{
    struct virtual_node * vn = tb->tb_vn;

  /* Sh is the node whose balance is currently being checked,
     and Fh is its father.  */
    struct buffer_head * Sh, * Fh;
    int n_ret_value;
    int lfree, rfree /* free space in L and R */;

    Sh = PATH_H_PBUFFER (tb->tb_path, h); 
    Fh = PATH_H_PPARENT (tb->tb_path, h); 

    /* using tb->insert_size[h], which is negative in this case,
       create_virtual_node calculates: new_nr_item = number of items node
       would have if operation is performed without balancing (new_nr_item); */
    create_virtual_node (tb, h);

    if ( ! Fh ) {
	/* S[h] is the root. */
	if ( vn->vn_nr_item > 0 ) {
	    set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
	    return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
	}
	/* new_nr_item == 0.
	 * Current root will be deleted resulting in
	 * decrementing the tree height. */
	set_parameters (tb, h, 0, 0, 0, NULL, -1, -1);
	return CARRY_ON;
    }
    
    if ( (n_ret_value = get_parents(tb,h)) != CARRY_ON )
	return n_ret_value;
    
    /* get free space of neighbors */
    rfree = get_rfree (tb, h);
    lfree = get_lfree (tb, h);
    
    /* determine maximal number of items we can fit into neighbors */

    check_left (tb, h, lfree);
    check_right (tb, h, rfree);
    
    if ( vn->vn_nr_item >= MIN_NR_KEY(Sh) ) {
	/* Balance condition for the internal node is valid. In this case we
	 * balance only if it leads to better packing. */
	if ( vn->vn_nr_item == MIN_NR_KEY(Sh) ) {
	    /* Here we join S[h] with one of its neighbors, which is
	     * impossible with greater values of new_nr_item. */
	    if ( tb->lnum[h] >= vn->vn_nr_item + 1 ) {
		/* All contents of S[h] can be moved to L[h]. */
		int n;
		int order_L;
		
		order_L = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
		n = get_dc_child_size (B_N_CHILD(tb->FL[h],order_L)) / (DC_SIZE + KEY_SIZE);
		set_parameters (tb, h, -n-1, 0, 0, NULL, -1, -1);
		return CARRY_ON;
	    }
	    
	    if ( tb->rnum[h] >= vn->vn_nr_item + 1 ) {
		/* All contents of S[h] can be moved to R[h]. */
		int n;
		int order_R;
		
		order_R = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==B_NR_ITEMS(Fh)) ? 0 : n + 1;
		n = get_dc_child_size (B_N_CHILD(tb->FR[h],order_R)) / (DC_SIZE + KEY_SIZE);
		set_parameters (tb, h, 0, -n-1, 0, NULL, -1, -1);
		return CARRY_ON;   
	    }
	}
	
	if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
	    /* All contents of S[h] can be moved to the neighbors (L[h] &
               R[h]). */
	    int to_r;
	    
	    to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 - 
		(MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
	    set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);
	    return CARRY_ON;
	}
	
	/* Balancing does not lead to better packing. */
	set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
	return NO_BALANCING_NEEDED;
    }
    
    /* Current node contain insufficient number of items. Balancing is
       required.  Check whether we can merge S[h] with left neighbor. */
    if (tb->lnum[h] >= vn->vn_nr_item + 1)
	if (is_left_neighbor_in_cache (tb,h) || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
	    int n;
	    int order_L;
	    
	    order_L = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
	    n = get_dc_child_size (B_N_CHILD(tb->FL[h],order_L)) / (DC_SIZE + KEY_SIZE);
	    set_parameters (tb, h, -n-1, 0, 0, NULL, -1, -1);
	    return CARRY_ON;
	}
    
    /* Check whether we can merge S[h] with right neighbor. */
    if (tb->rnum[h] >= vn->vn_nr_item + 1) {
	int n;
	int order_R;
	
	order_R = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==B_NR_ITEMS(Fh)) ? 0 : (n + 1);
	n = get_dc_child_size (B_N_CHILD(tb->FR[h],order_R)) / (DC_SIZE + KEY_SIZE);
	set_parameters (tb, h, 0, -n-1, 0, NULL, -1, -1);
	return CARRY_ON;   
    }
    
    /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
    if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
	int to_r;
	
	to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 - 
	    (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
	set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);
	return CARRY_ON;
    }
    
    /* For internal nodes try to borrow item from a neighbor */
    /* Borrow one or two items from caching neighbor */
    if (is_left_neighbor_in_cache (tb,h) || !tb->FR[h]) {
	int from_l;
		
	from_l = (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + 1) / 2 -  (vn->vn_nr_item + 1);
	set_parameters (tb, h, -from_l, 0, 1, NULL, -1, -1);
	return CARRY_ON;
    }
    
    set_parameters (tb, h, 0, -((MAX_NR_KEY(Sh)+1-tb->rnum[h]+vn->vn_nr_item+1)/2-(vn->vn_nr_item+1)), 1, 
		    NULL, -1, -1);
    return CARRY_ON;
}


/* Check whether current node S[h] is balanced when Decreasing its size by
 * Deleting or Truncating for LEAF node of internal tree.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	i - insert, p - paste;
 * Returns:	1 - schedule occured; 
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
static int dc_check_balance_leaf (struct tree_balance * tb, int h)
{
    struct virtual_node * vn = tb->tb_vn;

    /* Number of bytes that must be deleted from (value is negative if bytes
       are deleted) buffer which contains node being balanced.  The mnemonic
       is that the attempted change in node space used level is levbytes
       bytes. */
    int levbytes;
    /* the maximal item size */
    int n_ret_value;
    /* F0 is the parent of the node whose balance is currently being checked */
    struct buffer_head * F0;
    int lfree, rfree /* free space in L and R */;
    
    F0 = PATH_H_PPARENT (tb->tb_path, 0);

    levbytes = tb->insert_size[h];

    if ( ! F0 ) {
	/* S[0] is the root now. */
	set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
	return NO_BALANCING_NEEDED;
    }
    
    if ( (n_ret_value = get_parents(tb,h)) != CARRY_ON )
	return n_ret_value;
    
    /* get free