ibalance.c

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

/*
 * Copyright 1996-2004 by Hans Reiser, licensing governed by 
 * reiserfsprogs/README
 */

#include "includes.h"


/* modes of internal_shift_left, internal_shift_right and internal_insert_childs */
#define INTERNAL_SHIFT_FROM_S_TO_L 0
#define INTERNAL_SHIFT_FROM_R_TO_S 1
#define INTERNAL_SHIFT_FROM_L_TO_S 2
#define INTERNAL_SHIFT_FROM_S_TO_R 3
#define INTERNAL_INSERT_TO_S 4
#define INTERNAL_INSERT_TO_L 5
#define INTERNAL_INSERT_TO_R 6

static void	internal_define_dest_src_infos (
						int shift_mode,
						struct tree_balance * tb,
						int h,
						struct buffer_info * dest_bi,
						struct buffer_info * src_bi,
						int * d_key,
						struct buffer_head ** cf
						)
{
  /* define dest, src, dest parent, dest position */
  switch (shift_mode) {
  case INTERNAL_SHIFT_FROM_S_TO_L:	/* used in internal_shift_left */
    src_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h);
    src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h);
    src_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1);
    dest_bi->bi_bh = tb->L[h];
    dest_bi->bi_parent = tb->FL[h];
    dest_bi->bi_position = get_left_neighbor_position (tb, h);
    *d_key = tb->lkey[h];
    *cf = tb->CFL[h];
    break;
  case INTERNAL_SHIFT_FROM_L_TO_S:
    src_bi->bi_bh = tb->L[h];
    src_bi->bi_parent = tb->FL[h];
    src_bi->bi_position = get_left_neighbor_position (tb, h);
    dest_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h);
    dest_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h);
    dest_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); /* dest position is analog of dest->b_item_order */
    *d_key = tb->lkey[h];
    *cf = tb->CFL[h];
    break;

  case INTERNAL_SHIFT_FROM_R_TO_S:	/* used in internal_shift_left */
    src_bi->bi_bh = tb->R[h];
    src_bi->bi_parent = tb->FR[h];
    src_bi->bi_position = get_right_neighbor_position (tb, h);
    dest_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h);
    dest_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h);
    dest_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1);
    *d_key = tb->rkey[h];
    *cf = tb->CFR[h];
    break;
  case INTERNAL_SHIFT_FROM_S_TO_R:
    src_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h);
    src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h);
    src_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1);
    dest_bi->bi_bh = tb->R[h];
    dest_bi->bi_parent = tb->FR[h];
    dest_bi->bi_position = get_right_neighbor_position (tb, h);
    *d_key = tb->rkey[h];
    *cf = tb->CFR[h];
    break;

  case INTERNAL_INSERT_TO_L:
    dest_bi->bi_bh = tb->L[h];
    dest_bi->bi_parent = tb->FL[h];
    dest_bi->bi_position = get_left_neighbor_position (tb, h);
    break;

  case INTERNAL_INSERT_TO_S:
    dest_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h);
    dest_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h);
    dest_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1);
    break;

  case INTERNAL_INSERT_TO_R:
    dest_bi->bi_bh = tb->R[h];
    dest_bi->bi_parent = tb->FR[h];
    dest_bi->bi_position = get_right_neighbor_position (tb, h);
    break;

  default:
      reiserfs_panic ("internal_define_dest_src_infos", "shift type is unknown (%d)", shift_mode);
  }
}



/* Insert 'count' node pointers into buffer cur before position 'to' + 1.
 * Insert count items into buffer cur before position to.
 * Items and node pointers are specified by inserted and bh respectively.
 */ 
static void internal_insert_childs (reiserfs_filsys_t * fs, 
				    struct buffer_info * cur_bi,
				    int to, int count,
				    struct item_head * inserted,
				    struct buffer_head ** bh)
{
    struct buffer_head * cur = cur_bi->bi_bh;
    struct block_head * blkh;
    int nr;
    struct key * key;
    struct disk_child new_dc[2];
    struct disk_child * dc;
    int i;
    int from;
    
    if (count <= 0)
	return;
    
    blkh = B_BLK_HEAD (cur);
    nr = get_blkh_nr_items (blkh);
    
    /* prepare space for count disk_child */
    dc = B_N_CHILD (cur,to+1);
    
    memmove (dc + count, dc, (nr+1-(to+1)) * DC_SIZE);
    
    /* make disk child array for insertion */
    for (i = 0; i < count; i ++) {
	set_dc(new_dc + i, MAX_CHILD_SIZE(bh[i]->b_size) - 
	       get_blkh_free_space (B_BLK_HEAD (bh[i])),
	       bh[i]->b_blocknr);
	/*
	set_dc_child_size (new_dc + i,
			   MAX_CHILD_SIZE(bh[i]->b_size) - 
			   get_blkh_free_space (B_BLK_HEAD (bh[i])));
	set_dc_child_blocknr (new_dc + i, bh[i]->b_blocknr);*/
    }
    memcpy (dc, new_dc, DC_SIZE * count);
    
    /* prepare space for 'count' items  */
    from = ((to == -1) ? 0 : to);
    key = B_N_PDELIM_KEY (cur, from);
    
    memmove (key + count, key, (nr - from/*to*/) * KEY_SIZE + (nr + 1 + count) * DC_SIZE);

    /* copy keys */
    memcpy (key, inserted, KEY_SIZE);
    if ( count > 1 )
	memcpy (key + 1, inserted + 1, KEY_SIZE);
    
    /* sizes, item number */
    set_blkh_nr_items (blkh, nr + count);
    set_blkh_free_space (blkh, get_blkh_free_space (blkh) - count * (DC_SIZE + KEY_SIZE));

    mark_buffer_dirty (cur);
    
    if (cur_bi->bi_parent) {
	dc = B_N_CHILD (cur_bi->bi_parent,cur_bi->bi_position);
	set_dc_child_size (dc, get_dc_child_size (dc) + count * (DC_SIZE + KEY_SIZE));
	mark_buffer_dirty (cur_bi->bi_parent);
    }
    
}


/* Delete del_num items and node pointers from buffer cur starting from *
 * the first_i'th item and first_p'th pointers respectively.		*/
static void internal_delete_pointers_items (reiserfs_filsys_t * fs,
					    struct buffer_info * cur_bi,
					    int first_p, int first_i, 
					    int del_num)
{
    struct buffer_head * cur = cur_bi->bi_bh;
    int nr;
    struct block_head * blkh;
    struct key * key;
    struct disk_child * dc;

    if ( del_num == 0 )
	return;

    blkh = B_BLK_HEAD(cur);
    nr = get_blkh_nr_items (blkh);

    if ( first_p == 0 && del_num == nr + 1 ) {
	make_empty_node (cur_bi);
	return;
    }

    /* deleting */
    dc = B_N_CHILD (cur, first_p);

    memmove (dc, dc + del_num, (nr + 1 - first_p - del_num) * DC_SIZE);
    key = B_N_PDELIM_KEY (cur, first_i);
    memmove (key, key + del_num, (nr - first_i - del_num) * KEY_SIZE + (nr + 1 - del_num) * DC_SIZE);


    /* sizes, item number */
    set_blkh_nr_items (blkh, get_blkh_nr_items (blkh) - del_num);
    set_blkh_free_space (blkh, get_blkh_free_space (blkh) +
			 del_num * (KEY_SIZE +  DC_SIZE));

    mark_buffer_dirty (cur);
 
    if (cur_bi->bi_parent) {
	dc = B_N_CHILD (cur_bi->bi_parent, cur_bi->bi_position);
	set_dc_child_size (dc, get_dc_child_size (dc) - del_num * (KEY_SIZE +  DC_SIZE));
	mark_buffer_dirty (cur_bi->bi_parent);
    }
}


/* delete n node pointers and items starting from given position */
static void internal_delete_childs (reiserfs_filsys_t * fs,
				    struct buffer_info * cur_bi, 
				    int from, int n)
{
    int i_from;
    
    i_from = (from == 0) ? from : from - 1;
    
    /* delete n pointers starting from `from' position in CUR;
       delete n keys starting from 'i_from' position in CUR;
    */
    internal_delete_pointers_items (fs, cur_bi, from, i_from, n);
}


/* copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer dest
* last_first == FIRST_TO_LAST means, that we copy first items from src to tail of dest
 * last_first == LAST_TO_FIRST means, that we copy last items from src to head of dest 
 */
static void internal_copy_pointers_items (reiserfs_filsys_t * fs,
					  struct buffer_info * dest_bi,
					  struct buffer_head * src,
					  int last_first, int cpy_num)
{
    /* ATTENTION! Number of node pointers in DEST is equal to number of items in DEST *
     * as delimiting key have already inserted to buffer dest.*/
    struct buffer_head * dest = dest_bi->bi_bh;
    int nr_dest, nr_src;
    int dest_order, src_order;
    struct block_head * blkh;
    struct key * key;
    struct disk_child * dc;

    nr_src = B_NR_ITEMS (src);

    if ( cpy_num == 0 )
	return;

    /* coping */
    blkh = B_BLK_HEAD (dest);
    nr_dest = get_blkh_nr_items (blkh);

    /*dest_order = (last_first == LAST_TO_FIRST) ? 0 : nr_dest;*/
    /*src_order = (last_first == LAST_TO_FIRST) ? (nr_src - cpy_num + 1) : 0;*/
    (last_first == LAST_TO_FIRST) ?	(dest_order = 0, src_order = nr_src - cpy_num + 1) :
	(dest_order = nr_dest, src_order = 0);

    /* prepare space for cpy_num pointers */
    dc = B_N_CHILD (dest, dest_order);

    memmove (dc + cpy_num, dc, (nr_dest - dest_order) * DC_SIZE);

	/* insert pointers */
    memcpy (dc, B_N_CHILD (src, src_order), DC_SIZE * cpy_num);


    /* prepare space for cpy_num - 1 item headers */
    key = B_N_PDELIM_KEY(dest, dest_order);
    memmove (key + cpy_num - 1, key,
	     KEY_SIZE * (nr_dest - dest_order) + DC_SIZE * (nr_dest + cpy_num));


    /* insert headers */
    memcpy (key, B_N_PDELIM_KEY (src, src_order), KEY_SIZE * (cpy_num - 1));

    /* sizes, item number */
    set_blkh_nr_items (blkh, get_blkh_nr_items (blkh) + cpy_num - 1);
    set_blkh_free_space (blkh, get_blkh_free_space (blkh) -
			 (KEY_SIZE * (cpy_num - 1) + DC_SIZE * cpy_num));

    mark_buffer_dirty (dest);
    if (dest_bi->bi_parent) {
	dc = B_N_CHILD(dest_bi->bi_parent,dest_bi->bi_position);
	set_dc_child_size (dc, get_dc_child_size (dc) + KEY_SIZE * (cpy_num - 1) + DC_SIZE * cpy_num);
	mark_buffer_dirty (dest_bi->bi_parent);
    }

}


/* Copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer dest.
 * Delete cpy_num - del_par items and node pointers from buffer src.
 * last_first == FIRST_TO_LAST means, that we copy/delete first items from src.
 * last_first == LAST_TO_FIRST means, that we copy/delete last items from src.