fix_node.c

嵌入式系统设计与实验教材二源码linux内核移植与编译

      /* 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 = dc_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 = dc_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 = dc_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 = dc_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 */
  RFALSE( !tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");

  /* 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 S+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 occurred; 
 *	        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 maxsize,
      n_ret_value;
  /* S0 is the node whose balance is currently being checked,
     and F0 is its father.  */
  struct buffer_head * S0, * F0;
  int lfree, rfree /* free space in L and R */;

  S0 = PATH_H_PBUFFER (tb->tb_path, 0);
  F0 = PATH_H_PPARENT (tb->tb_path, 0);

  levbytes = tb->insert_size[h];

  maxsize = MAX_CHILD_SIZE(S0); 	/* maximal possible size of an item */

  if ( ! F0 )
    {  /* S[0] is the root now. */

      RFALSE( -levbytes >= maxsize - B_FREE_SPACE (S0),
	      "vs-8240: attempt to create empty buffer tree");

      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 space of neighbors */
  rfree = get_rfree (tb, h);
  lfree = get_lfree (tb, h);		

  create_virtual_node (tb, h);

  /* if 3 leaves can be merge to one, set parameters and return */
  if (are_leaves_removable (tb, lfree, rfree))
    return CARRY_ON;

  /* determine maximal number of items we can shift to the left/right  neighbor
     and the maximal number of bytes that can flow to the left/right neighbor
     from the left/right most liquid item that cannot be shifted from S[0] entirely
     */
  check_left (tb, h, lfree);
  check_right (tb, h, rfree);   

  /* check whether we can merge S with left neighbor. */
  if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
    if (is_left_neighbor_in_cache (tb,h) ||
	((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) || /* S can not be merged with R */
	!tb->FR[h]) {
      
      RFALSE( !tb->FL[h], "vs-8245: dc_check_balance_leaf: FL[h] must exist");

      /* set parameter to merge S[0] with its left neighbor */
      set_parameters (tb, h, -1, 0, 0, NULL, -1, -1);
      return CARRY_ON;
    }

  /* check whether we can merge S[0] with right neighbor. */
  if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
    set_parameters (tb, h, 0, -1, 0, NULL, -1, -1);
    return CARRY_ON;
  }
  
  /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
  if (is_leaf_removable (tb))
    return CARRY_ON;
  
  /* Balancing is not required. */
  tb->s0num = vn->vn_nr_item;
  set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
  return NO_BALANCING_NEEDED;
}



/* Check whether current node S[h] is balanced when Decreasing its size by
 * Deleting or Cutting.
 * 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	d - delete, c - cut.
 * Returns:	1 - schedule occurred; 
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
static int dc_check_balance (struct tree_balance * tb, int h)
{
 RFALSE( ! (PATH_H_PBUFFER (tb->tb_path, h)), "vs-8250: S is not initialized");

 if ( h )
   return dc_check_balance_internal (tb, h);
 else
   return dc_check_balance_leaf (tb, h);
}



/* Check whether current node S[h] is balanced.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *
 *	tb	tree_balance structure:
 *
 *              tb is a large structure that must be read about in the header file
 *              at the same time as this procedure if the reader is to successfully
 *              understand this procedure
 *
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	i - insert, p - paste, d - delete, c - cut.
 * Returns:	1 - schedule occurred; 
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
static int check_balance (int mode, 
			  struct tree_balance * tb,
			  int h, 
			  int inum,
			  int pos_in_item,
			  struct item_head * ins_ih,
			  const void * data
			  )
{
  struct virtual_node * vn;

  vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
  vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
  vn->vn_mode = mode;
  vn->vn_affected_item_num = inum;
  vn->vn_pos_in_item = pos_in_item;
  vn->vn_ins_ih = ins_ih;
  vn->vn_data = data;

  RFALSE( mode == M_INSERT && !vn->vn_ins_ih,
	  "vs-8255: ins_ih can not be 0 in insert mode");

 if ( tb->insert_size[h] > 0 )
   /* Calculate balance parameters when size of node is increasing. */
   return ip_check_balance (tb, h);

 /* Calculate balance parameters when  size of node is decreasing. */
 return dc_check_balance (tb, h);
}



/* Check whether parent at the path is the really parent of the current node.*/
static int  get_direct_parent(
              struct tree_balance * p_s_tb,
              int                   n_h
            ) {
    struct buffer_head  * p_s_bh;
    struct path         * p_s_path      = p_s_tb->tb_path;
    int                   n_position,
	n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
    
    /* We are in the root or in the new root. */
    if ( n_path_offset <= FIRST_PATH_ELEMENT_OFFSET ) {
	
	RFALSE( n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
		"PAP-8260: illegal offset in the path");

	if ( PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
	     SB_ROOT_BLOCK (p_s_tb->tb_sb) ) {
	    /* Root is not changed. */
	    PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
	    PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
	    return CARRY_ON;
	}
	return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */
    }

    if ( ! B_IS_IN_TREE(p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)) )
	return REPEAT_SEARCH; /* Parent in the path is not in the tree. */

    if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1)) > B_NR_ITEMS(p_s_bh) )
	return REPEAT_SEARCH;
    
    if ( B_N_CHILD_NUM(p_s_bh, n_position) != PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr )
	/* Parent in the path is not parent of the current node in the tree. */
	return REPEAT_SEARCH;

    if ( buffer_locked(p_s_bh) ) {
	__wait_on_buffer(p_s_bh);
	if ( FILESYSTEM_CHANGED_TB (p_s_tb) )
	    return REPEAT_SEARCH;
    }

    return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node.  */
}


/* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
 * of S[n_h] we
 * need in order to balance S[n_h], and get them if necessary.
 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked;
 *	        CARRY_ON - schedule didn't occur while the function worked;
 */
static int  get_neighbors(
	            struct tree_balance * p_s_tb,
	            int 		  n_h
	          ) {
    int		 	n_child_position,
	n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1);
    unsigned long		n_son_number;
    struct super_block  *	p_s_sb = p_s_tb->tb_sb;
    struct buffer_head  * p_s_bh;


    PROC_INFO_INC( p_s_sb, get_neighbors[ n_h ] );

    if ( p_s_tb->lnum[n_h] ) {
	/* We need left neighbor to balance S[n_h]. */
	PROC_INFO_INC( p_s_sb, need_l_neighbor[ n_h ] );
	p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
	
	RFALSE( p_s_bh == p_s_tb->FL[n_h] && 
		! PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset),
		"PAP-8270: invalid position in the parent");

	n_child_position = ( p_s_bh == p_s_tb->FL[n_h] ) ? p_s_tb->lkey[n_h] : B_NR_ITEMS (p_s_tb->FL[n_h]);
	n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position);
	p_s_bh = reiserfs_bread(p_s_sb, n_son_number, p_s_sb->s_blocksize);
	if (!p_s_bh)
	    return IO_ERROR;
	if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) {
	    decrement_bcount(p_s_bh);
	    PROC_INFO_INC( p_s_sb, get_neighbors_restart[ n_h ] );
	    return REPEAT_SEARCH;
	}
	
	RFALSE( ! B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
                n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) ||
	        B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) !=
                p_s_bh->b_blocknr, "PAP-8275: