ibalance.c

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

/*
 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */

#include <linux/config.h>
#include <asm/uaccess.h>
#include <linux/string.h>
#include <linux/sched.h>
#include <linux/reiserfs_fs.h>

/* this is one and only function that is used outside (do_balance.c) */
int	balance_internal (
			  struct tree_balance * ,
			  int,
			  int,
			  struct item_head * ,
			  struct buffer_head ** 
			  );

/* 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
						)
{
    memset (dest_bi, 0, sizeof (struct buffer_info));
    memset (src_bi, 0, sizeof (struct buffer_info));
    /* define dest, src, dest parent, dest position */
    switch (shift_mode) {
    case INTERNAL_SHIFT_FROM_S_TO_L:	/* used in internal_shift_left */
	src_bi->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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->tb = tb;
	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 (tb->tb_sb, "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 (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 * ih;
    struct disk_child new_dc[2];
    struct disk_child * dc;
    int i;

    if (count <= 0)
	return;

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

    RFALSE( count > 2,
	    "too many children (%d) are to be inserted", count);
    RFALSE( B_FREE_SPACE (cur) < count * (KEY_SIZE + DC_SIZE),
	    "no enough free space (%d), needed %d bytes", 
	    B_FREE_SPACE (cur), count * (KEY_SIZE + DC_SIZE));

    /* prepare space for count disk_child */
    dc = B_N_CHILD(cur,to+1);

    memmove (dc + count, dc, (nr+1-(to+1)) * DC_SIZE);

    /* copy to_be_insert disk children */
    for (i = 0; i < count; i ++) {
	put_dc_size( &(new_dc[i]), MAX_CHILD_SIZE(bh[i]) - B_FREE_SPACE(bh[i]));
	put_dc_block_number( &(new_dc[i]), bh[i]->b_blocknr );
    }
    memcpy (dc, new_dc, DC_SIZE * count);

  
    /* prepare space for count items  */
    ih = B_N_PDELIM_KEY (cur, ((to == -1) ? 0 : to));

    memmove (ih + count, ih, (nr - to) * KEY_SIZE + (nr + 1 + count) * DC_SIZE);

    /* copy item headers (keys) */
    memcpy (ih, inserted, KEY_SIZE);
    if ( count > 1 )
	memcpy (ih + 1, inserted + 1, KEY_SIZE);

    /* sizes, item number */
    set_blkh_nr_item( blkh, blkh_nr_item(blkh) + count );
    set_blkh_free_space( blkh,
                        blkh_free_space(blkh) - count * (DC_SIZE + KEY_SIZE ) );

    do_balance_mark_internal_dirty (cur_bi->tb, cur,0);

    /*&&&&&&&&&&&&&&&&&&&&&&&&*/
    check_internal (cur);
    /*&&&&&&&&&&&&&&&&&&&&&&&&*/

    if (cur_bi->bi_parent) {
	struct disk_child *t_dc = B_N_CHILD (cur_bi->bi_parent,cur_bi->bi_position);
	put_dc_size( t_dc, dc_size(t_dc) + (count * (DC_SIZE + KEY_SIZE)));
	do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent, 0);

	/*&&&&&&&&&&&&&&&&&&&&&&&&*/
	check_internal (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 (
						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;

  RFALSE( cur == NULL, "buffer is 0");
  RFALSE( del_num < 0,
          "negative number of items (%d) can not be deleted", del_num);
  RFALSE( first_p < 0 || first_p + del_num > B_NR_ITEMS (cur) + 1 || first_i < 0,
          "first pointer order (%d) < 0 or "
          "no so many pointers (%d), only (%d) or "
          "first key order %d < 0", first_p, 
          first_p + del_num, B_NR_ITEMS (cur) + 1, first_i);
  if ( del_num == 0 )
    return;

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

  if ( first_p == 0 && del_num == nr + 1 ) {
    RFALSE( first_i != 0, "1st deleted key must have order 0, not %d", first_i);
    make_empty_node (cur_bi);
    return;
  }

  RFALSE( first_i + del_num > B_NR_ITEMS (cur),
          "first_i = %d del_num = %d "
          "no so many keys (%d) in the node (%b)(%z)",
          first_i, del_num, first_i + del_num, cur, cur);


  /* 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_item( blkh, blkh_nr_item(blkh) - del_num );
  set_blkh_free_space( blkh,
                    blkh_free_space(blkh) + (del_num * (KEY_SIZE + DC_SIZE) ) );

  do_balance_mark_internal_dirty (cur_bi->tb, cur, 0);
  /*&&&&&&&&&&&&&&&&&&&&&&&*/
  check_internal (cur);
  /*&&&&&&&&&&&&&&&&&&&&&&&*/
 
  if (cur_bi->bi_parent) {
    struct disk_child *t_dc;
    t_dc = B_N_CHILD (cur_bi->bi_parent, cur_bi->bi_position);
    put_dc_size( t_dc, dc_size(t_dc) - (del_num * (KEY_SIZE + DC_SIZE) ) );

    do_balance_mark_internal_dirty (cur_bi->tb, cur_bi->bi_parent,0);
    /*&&&&&&&&&&&&&&&&&&&&&&&&*/
    check_internal (cur_bi->bi_parent);
    /*&&&&&&&&&&&&&&&&&&&&&&&&*/   
  }
}


/* delete n node pointers and items starting from given position */
static void  internal_delete_childs (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 (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 (
					  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);

  RFALSE( dest == NULL || src == NULL, 
	  "src (%p) or dest (%p) buffer is 0", src, dest);
  RFALSE( last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
	  "invalid last_first parameter (%d)", last_first);
  RFALSE( nr_src < cpy_num - 1, 
	  "no so many items (%d) in src (%d)", cpy_num, nr_src);
  RFALSE( cpy_num < 0, "cpy_num less than 0 (%d)", cpy_num);
  RFALSE( cpy_num - 1 + B_NR_ITEMS(dest) > (int)MAX_NR_KEY(dest),
	  "cpy_num (%d) + item number in dest (%d) can not be > MAX_NR_KEY(%d)",
	  cpy_num, B_NR_ITEMS(dest), MAX_NR_KEY(dest));

  if ( cpy_num == 0 )
    return;

	/* coping */
  blkh = B_BLK_HEAD(dest);
  nr_dest = blkh_nr_item(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_item( blkh, blkh_nr_item(blkh) + (cpy_num - 1 ) );
  set_blkh_free_space( blkh,
      blkh_free_space(blkh) - (KEY_SIZE * (cpy_num - 1) + DC_SIZE * cpy_num ) );

  do_balance_mark_internal_dirty (dest_bi->tb, dest, 0);