do_balan.c

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

				pos_in_item += get_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.bi_bh = tb->L[0];
		    bi.bi_parent = tb->FL[0];
		    bi.bi_position = get_left_neighbor_position (tb, 0);
		    leaf_paste_in_buffer (tb->tb_fs, &bi, n + item_pos - ret_val, pos_in_item, tb->insert_size[0],
					  body, zeros_number);

		    /* if appended item is directory, paste entry */
		    pasted = B_N_PITEM_HEAD (tb->L[0], n + item_pos - ret_val);
		    if (I_IS_DIRECTORY_ITEM (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 (I_IS_INDIRECT_ITEM (pasted))
			set_ih_free_space (pasted, 0);

		    tb->insert_size[0] = 0;
		    zeros_number = 0;
		}
		break;
	    default:    /* cases d and t */
		reiserfs_panic ("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] */
		    loff_t old_key_comp, old_len, r_zeros_number;
		    const char * r_body;
		    loff_t multiplyer;

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

		    /* Remember key component and item length */
		    old_key_comp = get_offset (&ih->ih_key);
		    old_len = get_ih_item_len (ih);

		    multiplyer = is_indirect_ih(ih) ? tb->tb_fs->fs_blocksize / UNFM_P_SIZE : 1;
		    /* Calculate key component and item length to insert into R[0] */
		    //ih->ih_key.k_offset += (old_len - tb->rbytes);
		    set_offset (key_format (&ih->ih_key), &ih->ih_key, old_key_comp +
		    	(old_len - tb->rbytes) * multiplyer );

		    set_ih_item_len (ih, tb->rbytes);
		    /* Insert part of the item into R[0] */
		    bi.bi_bh = tb->R[0];
		    bi.bi_parent = tb->FR[0];
		    bi.bi_position = get_right_neighbor_position (tb, 0);
		    if (old_len - tb->rbytes > zeros_number ) {
			r_zeros_number = 0;
			r_body = body + old_len - tb->rbytes - zeros_number;
		    }
		    else { /* zeros_number is always 0 */
			r_body = body;
			r_zeros_number = zeros_number - old_len - tb->rbytes;
			zeros_number -= r_zeros_number;
		    }

		    leaf_insert_into_buf (tb->tb_fs, &bi, 0, ih, r_body, r_zeros_number);

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

		    /* Calculate key component and item length to insert into S[0] */
		    //ih->ih_key.k_offset = old_key_comp;
		    set_offset (key_format (&ih->ih_key), &ih->ih_key, old_key_comp);

		    set_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.bi_bh = tb->R[0];
		    bi.bi_parent = tb->FR[0];
		    bi.bi_position = get_right_neighbor_position (tb, 0);
		    leaf_insert_into_buf (tb->tb_fs, &bi, item_pos - n + tb->rnum[0] - 1, ih, body, zeros_number);

		    /* If we insert new item in the begin of R[0] change the right delimiting key */
		    if ( item_pos - n + tb->rnum[0] - 1 == 0 ) {
			replace_key (tb->tb_fs, tb->CFR[0],tb->rkey[0],tb->R[0],0);
		    }
		    zeros_number = 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 ( I_IS_DIRECTORY_ITEM (B_N_PITEM_HEAD(tbS0, item_pos))) {
			/* we append to directory item */
			int entry_count;

			entry_count = get_ih_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;

			    /* 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.bi_bh = tb->R[0];
			    bi.bi_parent = tb->FR[0];
			    bi.bi_position = get_right_neighbor_position (tb, 0);
			    leaf_paste_in_buffer (tb->tb_fs, &bi, 0, paste_entry_position,
						  tb->insert_size[0],body,zeros_number);
			    /* 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_fs, 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;
			struct key * key;

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

			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;

			{
			    unsigned long temp_rem = n_rem;
			
			    if (is_indirect_key(B_N_PKEY(tb->R[0],0)))
				temp_rem = (n_rem / UNFM_P_SIZE) * tb->tb_fs->fs_blocksize;

			    //B_N_PKEY(tb->R[0],0)->k_offset += n_rem;
			    key = B_N_PKEY(tb->R[0],0);
			    set_offset (key_format (key), key, get_offset (key) + temp_rem);

			    //B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])->k_offset += n_rem;
			    key = B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0]);
			    set_offset (key_format (key), key, get_offset (key) + temp_rem);
                        }

			mark_buffer_dirty (tb->CFR[0]);

			/* Append part of body into R[0] */
			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_number ) {
			    r_zeros_number = 0;
			    r_body = body + n_rem - zeros_number;
			}
			else {
			    r_body = body;
			    r_zeros_number = zeros_number - n_rem;
			    zeros_number -= r_zeros_number;
			}

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

			if (I_IS_INDIRECT_ITEM(B_N_PITEM_HEAD(tb->R[0],0))) {
			    set_ih_free_space (B_N_PITEM_HEAD(tb->R[0],0), 0);
			}

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

		    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.bi_bh = tb->R[0];
			bi.bi_parent = tb->FR[0];
			bi.bi_position = get_right_neighbor_position (tb, 0);
			leaf_paste_in_buffer(tb->tb_fs, &bi,item_pos - n + tb->rnum[0], pos_in_item,
					     tb->insert_size[0],body, zeros_number);
		    }

		    /* paste new entry, if item is directory item */
		    pasted = B_N_PITEM_HEAD(tb->R[0], item_pos - n + tb->rnum[0]);
		    if (I_IS_DIRECTORY_ITEM (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 ) {
			    /* update delimiting keys */
			    replace_key (tb->tb_fs, tb->CFR[0],tb->rkey[0],tb->R[0],0);
			}
		    }

		    if (I_IS_INDIRECT_ITEM (pasted))
			set_ih_free_space (pasted, 0);
		    zeros_number = 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 ("PAP-12175: balance_leaf: rnum > 0: unexpectable mode: %s(%d)",
			    (flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
	}
    
    }	/* tb->rnum[0] > 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 */
        /* 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_fs, "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]));
            mark_buffer_dirty (tb->CFL[0]);
        }
        
	reiserfs_invalidate_buffer(tb,tbS0, 1);									
	return 0;
    }


    /* Fill new nodes that appear in place of S[0] */

    /* I am told that this copying is because we need an array to enable
       the looping code. -Hans */
    snum[0] = tb->s1num,
	snum[1] = tb->s2num;
    sbytes[0] = tb->s1bytes;
    sbytes[1] = tb->s2bytes;
    for( i = tb->blknum[0] - 2; i >= 0; i-- ) {
	/* here we shift from S to S_new nodes */
	S_new[i] = get_FEB(tb);

	/* set block_head's level to leaf level */
	set_blkh_level (B_BLK_HEAD (S_new[i]), DISK_LEAF_NODE_LEVEL);

	n = B_NR_ITEMS(tbS0);
	
	switch (flag) {
	case M_INSERT:   /* insert item */

	    if ( n - snum[i] < item_pos ) {
		/* new item or it's part falls to first new node S_new[i]*/
		if ( item_pos == n - snum[i] + 1 && sbytes[i] != -1 ) {
		    /* part of new item falls into S_new[i] */
		    int old_key_comp, old_len, r_zeros_number;
		    const char * r_body;
		    loff_t multiplyer;

		    /* Move snum[i]-1 items from S[0] to S_new[i] */
		    leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i] - 1, -1, S_new[i]);

		    /* Remember key component and item length */
		    old_key_comp = get_offset (&ih->ih_key);
		    old_len = get_ih_item_len (ih);
		    multiplyer = is_indirect_ih(ih) ? tb->tb_fs->fs_blocksize / UNFM_P_SIZE : 1;

		    /* Calculate key component and item length to insert into S_new[i] */
		    //ih->ih_key.k_offset += (old_len - sbytes[i]);
		    set_offset (key_format (&ih->ih_key), &ih->ih_key, old_key_comp +
		    	(old_len - sbytes[i]) * multiplyer);

		    set_ih_item_len (ih, sbytes[i]);

		    /* Insert part of the item into S_new[i] before 0-th item */
		    bi.bi_bh = S_new[i];
		    bi.bi_parent = 0;
		    bi.bi_position = 0;

		    if ( old_len - sbytes[i] > zeros_number ) {
			r_zeros_number = 0;
			r_body = body + (old_len - sbytes[i]) - zeros_number;
		    }
		    else {
			r_body = body;
			r_zeros_number = zeros_number - (old_len - sbytes[i]);
			zeros_number -= r_zeros_number;
		    }

		    leaf_insert_into_buf (tb->tb_fs, &bi, 0, ih, r_body, r_zeros_number);

		    /* Calculate key component and item length to insert into S[i] */
		    //ih->ih_key.k_offset = old_key_comp;
		    set_offset (key_format (&ih->ih_key), &ih->ih_key, old_key_comp);
		    set_ih_item_len (ih, old_len - sbytes[i]);
		    tb->insert_size[0] -= sbytes[i];
		}
		else /* whole new item falls into S_new[i] */
		{
		    /* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
		    leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i] - 1, sbytes[i], S_new[i]);

		    /* Insert new item into S_new[i] */
		    bi.bi_bh = S_new[i];
		    bi.bi_parent = 0;
		    bi.bi_position = 0;
		    leaf_insert_into_buf (tb->tb_fs, &bi, item_pos - n + snum[i] - 1, ih, body, zeros_number);
		    zeros_number = tb->insert_size[0] = 0;
		}
	    }

	    else /* new item or it part don't falls into S_new[i] */
	    {
		leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);
	    }
	    break;

	case M_PASTE:   /* append item */

	    if ( n - snum[i] <= item_pos )  /* pasted item or part if it falls to S_new[i] */
	    {
		if ( item_pos == n - snum[i] && sbytes[i] != -1 )
		{ /* we must shift part of the appended item */
		    struct item_head * aux_ih;

		    if ( I_IS_DIRECTORY_ITEM (aux_ih = B_N_PITEM_HEAD(tbS0,item_pos))) {
			/* we append to directory item */

			int entry_count;
		
			entry_count = get_ih_entry_count(aux_ih);

			if ( entry_count - sbytes[i] < pos_in_item  && pos_in_item <= entry_count ) {