do_balan.c

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

			pos_in_item -= tb->lbytes;
		    }
		    else {
			/* regular object */
			RFALSE( tb->lbytes <= 0,
			        "PAP-12095: there is nothing to shift to L[0]. lbytes=%d",
				tb->lbytes);
			RFALSE( pos_in_item != ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)),
                                "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d",
				ih_item_len(B_N_PITEM_HEAD(tbS0,item_pos)), pos_in_item);

			if ( tb->lbytes >= pos_in_item ) {
			    /* appended item will be in L[0] in whole */
			    int l_n;

			    /* this bytes number must be appended to the last item of L[h] */
			    l_n = tb->lbytes - pos_in_item;

			    /* Calculate new insert_size[0] */
			    tb->insert_size[0] -= l_n;

			    RFALSE( tb->insert_size[0] <= 0,
				    "PAP-12105: there is nothing to paste into L[0]. insert_size=%d",
				    tb->insert_size[0]);
			    ret_val =  leaf_shift_left(tb,tb->lnum[0], 
						       ih_item_len(B_N_PITEM_HEAD(tbS0,item_pos)));
			    /* Append to body of item in L[0] */
			    bi.tb = tb;
			    bi.bi_bh = tb->L[0];
			    bi.bi_parent = tb->FL[0];
			    bi.bi_position = get_left_neighbor_position (tb, 0);
			    leaf_paste_in_buffer(
				&bi,n + item_pos - ret_val,
				ih_item_len( B_N_PITEM_HEAD(tb->L[0],n+item_pos-ret_val)),
				l_n,body, zeros_num > l_n ? l_n : zeros_num
				);

			    RFALSE( l_n && 
				    is_indirect_le_ih(B_N_PITEM_HEAD
						      (tb->L[0],
						       n + item_pos - ret_val)),
				    "PAP-12110: pasting more than 1 unformatted node pointer into indirect item");

			    /* 0-th item in S0 can be only of DIRECT type when l_n != 0*/
			    {
			      int version;

			      version = ih_version (B_N_PITEM_HEAD (tbS0, 0));
			      set_le_key_k_offset (version, B_N_PKEY (tbS0, 0), 
						   le_key_k_offset (version, B_N_PKEY (tbS0, 0)) + l_n);
			      version = ih_version (B_N_PITEM_HEAD(tb->CFL[0],tb->lkey[0]));
			      set_le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0]),
						   le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0])) + l_n);
			    }

			    /* Calculate new body, position in item and insert_size[0] */
			    if ( l_n > zeros_num ) {
				body += (l_n - zeros_num);
				zeros_num = 0;
			    }
			    else
				zeros_num -= l_n;
			    pos_in_item = 0;	

			    RFALSE( comp_short_le_keys 
				    (B_N_PKEY(tbS0,0),
				     B_N_PKEY(tb->L[0],B_NR_ITEMS(tb->L[0])-1)) ||
				
				    !op_is_left_mergeable 
				    (B_N_PKEY (tbS0, 0), tbS0->b_size) ||
				    !op_is_left_mergeable
				    (B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0]), 
				     tbS0->b_size),
				    "PAP-12120: item must be merge-able with left neighboring item");
			}
			else /* only part of the appended item will be in L[0] */
			{
			    /* Calculate position in item for append in S[0] */
			    pos_in_item -= tb->lbytes;

			    RFALSE( pos_in_item <= 0,
				    "PAP-12125: no place for paste. pos_in_item=%d", pos_in_item);

			    /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
			    leaf_shift_left(tb,tb->lnum[0],tb->lbytes);
			}
		    }
		}
		else /* appended item will be in L[0] in whole */
		{
		    struct item_head * pasted;

			if ( ! item_pos  && op_is_left_mergeable (B_N_PKEY (tbS0, 0), tbS0->b_size) )
			{ /* if we paste into first item of S[0] and it is left mergable */
			    /* then increment pos_in_item by the size of the last item in L[0] */
			    pasted = B_N_PITEM_HEAD(tb->L[0],n-1);
			    if ( is_direntry_le_ih (pasted) )
				pos_in_item += ih_entry_count(pasted);
			    else
				pos_in_item += ih_item_len(pasted);
			}

		    /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
		    ret_val = leaf_shift_left(tb,tb->lnum[0],tb->lbytes);
		    /* Append to body of item in L[0] */
		    bi.tb = tb;
		    bi.bi_bh = tb->L[0];
		    bi.bi_parent = tb->FL[0];
		    bi.bi_position = get_left_neighbor_position (tb, 0);
		    leaf_paste_in_buffer (&bi, n + item_pos - ret_val, pos_in_item, tb->insert_size[0],
					  body, zeros_num);

		    /* if appended item is directory, paste entry */
		    pasted = B_N_PITEM_HEAD (tb->L[0], n + item_pos - ret_val);
		    if (is_direntry_le_ih (pasted))
			leaf_paste_entries (
			    bi.bi_bh, n + item_pos - ret_val, pos_in_item, 1, 
			    (struct reiserfs_de_head *)body, body + DEH_SIZE, tb->insert_size[0]
			    );
		    /* if appended item is indirect item, put unformatted node into un list */
		    if (is_indirect_le_ih (pasted))
			set_ih_free_space (pasted, ((struct unfm_nodeinfo*)body)->unfm_freespace);
		    tb->insert_size[0] = 0;
		    zeros_num = 0;
		}
		break;
	    default:    /* cases d and t */
		reiserfs_panic (tb->tb_sb, "PAP-12130: balance_leaf: lnum > 0: unexpectable mode: %s(%d)",
				(flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
	    }
	} else { 
	    /* new item doesn't fall into L[0] */
	    leaf_shift_left(tb,tb->lnum[0],tb->lbytes);
	}
    }	/* tb->lnum[0] > 0 */

    /* Calculate new item position */
    item_pos -= ( tb->lnum[0] - (( tb->lbytes != -1 ) ? 1 : 0));

    if ( tb->rnum[0] > 0 ) {
	/* shift rnum[0] items from S[0] to the right neighbor R[0] */
	n = B_NR_ITEMS(tbS0);
	switch ( flag ) {

	case M_INSERT:   /* insert item */
	    if ( n - tb->rnum[0] < item_pos )
	    { /* new item or its part falls to R[0] */
		if ( item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1 )
		{ /* part of new item falls into R[0] */
		    int old_key_comp, old_len, r_zeros_number;
		    const char * r_body;
		    int version;
		    loff_t offset;

		    RFALSE( !is_direct_le_ih (ih),
			    "PAP-12135: only direct item can be split. (%h)", 
			    ih);

		    leaf_shift_right(tb,tb->rnum[0]-1,-1);

		    version = ih_version(ih);
		    /* Remember key component and item length */
                    old_key_comp = le_ih_k_offset( ih );
		    old_len = ih_item_len(ih);

		    /* Calculate key component and item length to insert into R[0] */
                    offset = le_ih_k_offset( ih ) + (old_len - tb->rbytes );
                    set_le_ih_k_offset( ih, offset );
		    put_ih_item_len( ih, tb->rbytes);
		    /* Insert part of the item into R[0] */
		    bi.tb = tb;
		    bi.bi_bh = tb->R[0];
		    bi.bi_parent = tb->FR[0];
		    bi.bi_position = get_right_neighbor_position (tb, 0);
		    if ( offset - old_key_comp > zeros_num ) {
			r_zeros_number = 0;
			r_body = body + offset - old_key_comp - zeros_num;
		    }
		    else {
			r_body = body;
			r_zeros_number = zeros_num - (offset - old_key_comp);
			zeros_num -= r_zeros_number;
		    }

		    leaf_insert_into_buf (&bi, 0, ih, r_body, r_zeros_number);

		    /* Replace right delimiting key by first key in R[0] */
		    replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0);

		    /* Calculate key component and item length to insert into S[0] */
                    set_le_ih_k_offset( ih, old_key_comp );
		    put_ih_item_len( ih, old_len - tb->rbytes );

		    tb->insert_size[0] -= tb->rbytes;

		}
		else /* whole new item falls into R[0] */
		{					  
		    /* Shift rnum[0]-1 items to R[0] */
		    ret_val = leaf_shift_right(tb,tb->rnum[0]-1,tb->rbytes);
		    /* Insert new item into R[0] */
		    bi.tb = tb;
		    bi.bi_bh = tb->R[0];
		    bi.bi_parent = tb->FR[0];
		    bi.bi_position = get_right_neighbor_position (tb, 0);
		    leaf_insert_into_buf (&bi, item_pos - n + tb->rnum[0] - 1, ih, body, zeros_num);

		    if ( item_pos - n + tb->rnum[0] - 1 == 0 ) {
			replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0);

		    }
		    zeros_num = tb->insert_size[0] = 0;
		}
	    }
	    else /* new item or part of it doesn't fall into R[0] */
	    {
		leaf_shift_right(tb,tb->rnum[0],tb->rbytes);
	    }
	    break;

	case M_PASTE:   /* append item */

	    if ( n - tb->rnum[0] <= item_pos )  /* pasted item or part of it falls to R[0] */
	    {
		if ( item_pos == n - tb->rnum[0] && tb->rbytes != -1 )
		{ /* we must shift the part of the appended item */
		    if ( is_direntry_le_ih (B_N_PITEM_HEAD(tbS0, item_pos)))
		    { /* we append to directory item */
			int entry_count;

			RFALSE( zeros_num,
				"PAP-12145: illegal parametr in case of a directory");
			entry_count = I_ENTRY_COUNT(B_N_PITEM_HEAD(tbS0, item_pos));
			if ( entry_count - tb->rbytes < pos_in_item )
			    /* new directory entry falls into R[0] */
			{
			    int paste_entry_position;

			    RFALSE( tb->rbytes - 1 >= entry_count || 
				    ! tb->insert_size[0],
				    "PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
				    tb->rbytes, entry_count);
			    /* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
			    leaf_shift_right(tb,tb->rnum[0],tb->rbytes - 1);
			    /* Paste given directory entry to directory item */
			    paste_entry_position = pos_in_item - entry_count + tb->rbytes - 1;
			    bi.tb = tb;
			    bi.bi_bh = tb->R[0];
			    bi.bi_parent = tb->FR[0];
			    bi.bi_position = get_right_neighbor_position (tb, 0);
			    leaf_paste_in_buffer (&bi, 0, paste_entry_position,
						  tb->insert_size[0],body,zeros_num);
			    /* paste entry */
			    leaf_paste_entries (
				bi.bi_bh, 0, paste_entry_position, 1, (struct reiserfs_de_head *)body, 
				body + DEH_SIZE, tb->insert_size[0]
				);								
						
			    if ( paste_entry_position == 0 ) {
				/* change delimiting keys */
				replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0);
			    }

			    tb->insert_size[0] = 0;
			    pos_in_item++;
			}
			else /* new directory entry doesn't fall into R[0] */
			{
			    leaf_shift_right(tb,tb->rnum[0],tb->rbytes);
			}
		    }
		    else /* regular object */
		    {
			int n_shift, n_rem, r_zeros_number;
			const char * r_body;

			/* Calculate number of bytes which must be shifted from appended item */
			if ( (n_shift = tb->rbytes - tb->insert_size[0]) < 0 )
			    n_shift = 0;

			RFALSE(pos_in_item != ih_item_len(B_N_PITEM_HEAD (tbS0, item_pos)),
			       "PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
                               pos_in_item, ih_item_len( B_N_PITEM_HEAD(tbS0,item_pos)));

			leaf_shift_right(tb,tb->rnum[0],n_shift);
			/* Calculate number of bytes which must remain in body after appending to R[0] */
			if ( (n_rem = tb->insert_size[0] - tb->rbytes) < 0 )
			    n_rem = 0;
			
			{
			  int version;
			  
			  version = ih_version (B_N_PITEM_HEAD (tb->R[0],0));
			  set_le_key_k_offset (version, B_N_PKEY(tb->R[0],0), 
					       le_key_k_offset (version, B_N_PKEY(tb->R[0],0)) + n_rem);
			  set_le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0]), 
					       le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) + n_rem);
			}
/*		  k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
		  k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;*/
			do_balance_mark_internal_dirty (tb, tb->CFR[0], 0);

			/* Append part of body into R[0] */
			bi.tb = tb;
			bi.bi_bh = tb->R[0];
			bi.bi_parent = tb->FR[0];
			bi.bi_position = get_right_neighbor_position (tb, 0);
			if ( n_rem > zeros_num ) {
			    r_zeros_number = 0;
			    r_body = body + n_rem - zeros_num;
			}
			else {
			    r_body = body;
			    r_zeros_number = zeros_num - n_rem;
			    zeros_num -= r_zeros_number;
			}

			leaf_paste_in_buffer(&bi, 0, n_shift, tb->insert_size[0] - n_rem, r_body, r_zeros_number);

			if (is_indirect_le_ih (B_N_PITEM_HEAD(tb->R[0],0))) {

			    RFALSE( n_rem,
				    "PAP-12160: paste more than one unformatted node pointer");

			    set_ih_free_space (B_N_PITEM_HEAD(tb->R[0],0), ((struct unfm_nodeinfo*)body)->unfm_freespace);
			}

			tb->insert_size[0] = n_rem;
			if ( ! n_rem )
			    pos_in_item ++;
		    }
		}
		else /* pasted item in whole falls into R[0] */
		{
		    struct item_head * pasted;

		    ret_val = leaf_shift_right(tb,tb->rnum[0],tb->rbytes);
		    /* append item in R[0] */
		    if ( pos_in_item >= 0 ) {
			bi.tb = tb;
			bi.bi_bh = tb->R[0];
			bi.bi_parent = tb->FR[0];
			bi.bi_position = get_right_neighbor_position (tb, 0);
			leaf_paste_in_buffer(&bi,item_pos - n + tb->rnum[0], pos_in_item,
					     tb->insert_size[0],body, zeros_num);
		    }

		    /* paste new entry, if item is directory item */
		    pasted = B_N_PITEM_HEAD(tb->R[0], item_pos - n + tb->rnum[0]);
		    if (is_direntry_le_ih (pasted) && pos_in_item >= 0 ) {
			leaf_paste_entries (
			    bi.bi_bh, item_pos - n + tb->rnum[0], pos_in_item, 1, 
			    (struct reiserfs_de_head *)body, body + DEH_SIZE, tb->insert_size[0]
			    );
			if ( ! pos_in_item ) {

			    RFALSE( item_pos - n + tb->rnum[0],
				    "PAP-12165: directory item must be first item of node when pasting is in 0th position");

			    /* update delimiting keys */
			    replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0);
			}
		    }

		    if (is_indirect_le_ih (pasted))
			set_ih_free_space (pasted, ((struct unfm_nodeinfo*)body)->unfm_freespace);
		    zeros_num = tb->insert_size[0] = 0;
		}
	    }
	    else /* new item doesn't fall into R[0] */
	    {
		leaf_shift_right(tb,tb->rnum[0],tb->rbytes);
	    }
	    break;
	default:    /* cases d and t */
	    reiserfs_panic (tb->tb_sb, "PAP-12175: balance_leaf: rnum > 0: unexpectable mode: %s(%d)",
			    (flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
	}
    
    }	/* tb->rnum[0] > 0 */


    RFALSE( tb->blknum[0] > 3,
	    "PAP-12180: blknum can not be %d. It must be <= 3",  tb->blknum[0]);
    RFALSE( tb->blknum[0] < 0,
	    "PAP-12185: blknum can not be %d. It must be >= 0",  tb->blknum[0]);

    /* if while adding to a node we discover that it is possible to split
       it in two, and merge the left part into the left neighbor and the
       right part into the right neighbor, eliminating the node */
    if ( tb->blknum[0] == 0 ) { /* node S[0] is empty now */

	RFALSE( ! tb->lnum[0] || ! tb->rnum[0],
	        "PAP-12190: lnum and rnum must not be zero");
	/* if insertion was done before 0-th position in R[0], right
	   delimiting key of the tb->L[0]'s and left delimiting key are
	   not set correctly */
	if (tb->CFL[0]) {
	    if (!tb->CFR[0])
		reiserfs_panic (tb->tb_sb, "vs-12195: balance_leaf: CFR not initialized");
	    copy_key (B_N_PDELIM_KEY (tb->CFL[0], tb->lkey[0]), B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]));
	    do_balance_mark_internal_dirty (tb, tb->CFL[0], 0);
	}