/* preallocated blocks don't need to be run through journal_mark_freed */
static void reiserfs_free_prealloc_block (struct reiserfs_transaction_handle *th,
        struct inode *inode, b_blocknr_t block) {
    RFALSE(!th->t_super, "vs-4060: trying to free block on nonexistent device");
    RFALSE(is_reusable (th->t_super, block, 1) == 0, "vs-4070: can not free such block");
    BUG_ON (!th->t_trans_id);
    _reiserfs_free_block(th, inode, block, 1) ;
}

/* Replace delimiting key of buffers S[h] and R[h] by the given key.*/
static void replace_rkey(struct tree_balance *tb, int h, struct item_head *key)
{
	RFALSE(tb->R[h] == NULL || tb->CFR[h] == NULL,
	       "R[h](%p) and CFR[h](%p) must exist in replace_rkey",
	       tb->R[h], tb->CFR[h]);
	RFALSE(B_NR_ITEMS(tb->R[h]) == 0,
	       "R[h] can not be empty if it exists (item number=%d)",
	       B_NR_ITEMS(tb->R[h]));

	memcpy(B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]), key, KEY_SIZE);

	do_balance_mark_internal_dirty(tb, tb->CFR[h], 0);
}

/* Insert n_src'th key of buffer src before n_dest'th key of buffer dest. */
static void internal_insert_key(struct buffer_info *dest_bi,
				/* insert key before key with n_dest number */
				int dest_position_before,
				struct buffer_head *src, int src_position)
{
	struct buffer_head *dest = dest_bi->bi_bh;
	int nr;
	struct block_head *blkh;
	struct reiserfs_key *key;

	RFALSE(dest == NULL || src == NULL,
	       "source(%p) or dest(%p) buffer is 0", src, dest);
	RFALSE(dest_position_before < 0 || src_position < 0,
	       "source(%d) or dest(%d) key number less than 0",
	       src_position, dest_position_before);
	RFALSE(dest_position_before > B_NR_ITEMS(dest) ||
	       src_position >= B_NR_ITEMS(src),
	       "invalid position in dest (%d (key number %d)) or in src (%d (key number %d))",
	       dest_position_before, B_NR_ITEMS(dest),
	       src_position, B_NR_ITEMS(src));
	RFALSE(B_FREE_SPACE(dest) < KEY_SIZE,
	       "no enough free space (%d) in dest buffer", B_FREE_SPACE(dest));

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

	/* prepare space for inserting key */
	key = internal_key(dest, dest_position_before);
	memmove(key + 1, key,
		(nr - dest_position_before) * KEY_SIZE + (nr + 1) * DC_SIZE);

	/* insert key */
	memcpy(key, internal_key(src, src_position), KEY_SIZE);

	/* Change dirt, free space, item number fields. */

	set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
	set_blkh_free_space(blkh, blkh_free_space(blkh) - KEY_SIZE);

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

	if (dest_bi->bi_parent) {
		struct disk_child *t_dc;
		t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
		put_dc_size(t_dc, dc_size(t_dc) + KEY_SIZE);

		do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
					       0);
	}
}

void reiserfs_free_block (struct reiserfs_transaction_handle *th,
                          struct inode *inode, b_blocknr_t block,
                          int for_unformatted)
{
    struct super_block * s = th->t_super;

    BUG_ON (!th->t_trans_id);

    RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
    RFALSE(is_reusable (s, block, 1) == 0, "vs-4071: can not free such block");
    /* mark it before we clear it, just in case */
    journal_mark_freed(th, s, block) ;
    _reiserfs_free_block(th, inode, block, for_unformatted) ;
}

/* Insert d_key'th (delimiting) key from buffer cfr to head of dest.
 * Copy n node pointers and n - 1 items from buffer src to buffer dest.
 * Replace  d_key'th key in buffer cfr.
 * Delete n items and node pointers from buffer src.
 */
static void internal_shift_right(int mode,	/* INTERNAL_FROM_S_TO_R | INTERNAL_FROM_L_TO_S */
				 struct tree_balance *tb,
				 int h, int pointer_amount)
{
	struct buffer_info dest_bi, src_bi;
	struct buffer_head *cf;
	int d_key_position;
	int nr;

	internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,
				       &d_key_position, &cf);

	nr = B_NR_ITEMS(src_bi.bi_bh);

	if (pointer_amount > 0) {
		/* insert delimiting key from common father of dest and src to dest node into position 0 */
		internal_insert_key(&dest_bi, 0, cf, d_key_position);
		if (nr == pointer_amount - 1) {
			RFALSE(src_bi.bi_bh != PATH_H_PBUFFER(tb->tb_path, h) /*tb->S[h] */ ||
			       dest_bi.bi_bh != tb->R[h],
			       "src (%p) must be == tb->S[h](%p) when it disappears",
			       src_bi.bi_bh, PATH_H_PBUFFER(tb->tb_path, h));
			/* when S[h] disappers replace left delemiting key as well */
			if (tb->CFL[h])
				replace_key(tb, cf, d_key_position, tb->CFL[h],
					    tb->lkey[h]);
		} else
			replace_key(tb, cf, d_key_position, src_bi.bi_bh,
				    nr - pointer_amount);
	}

	/* last parameter is del_parameter */
	internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST,
				     pointer_amount, 0);
}

/* Does the buffer contain a disk block which is in the tree. */
inline int B_IS_IN_TREE(const struct buffer_head *bh)
{

	RFALSE(B_LEVEL(bh) > MAX_HEIGHT,
	       "PAP-1010: block (%b) has too big level (%z)", bh, bh);

	return (B_LEVEL(bh) != FREE_LEVEL);
}

/* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom
   of the path, and going upwards.  We must check the path's validity at each step.  If the key is not in
   the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this
   case we return a special key, either MIN_KEY or MAX_KEY. */
static inline const struct reiserfs_key *get_lkey(const struct treepath *chk_path,
						  const struct super_block *sb)
{
	int position, path_offset = chk_path->path_length;
	struct buffer_head *parent;

	RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET,
	       "PAP-5010: invalid offset in the path");

	/* While not higher in path than first element. */
	while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {

		RFALSE(!buffer_uptodate
		       (PATH_OFFSET_PBUFFER(chk_path, path_offset)),
		       "PAP-5020: parent is not uptodate");

		/* Parent at the path is not in the tree now. */
		if (!B_IS_IN_TREE
		    (parent =
		     PATH_OFFSET_PBUFFER(chk_path, path_offset)))
			return &MAX_KEY;
		/* Check whether position in the parent is correct. */
		if ((position =
		     PATH_OFFSET_POSITION(chk_path,
					  path_offset)) >
		    B_NR_ITEMS(parent))
			return &MAX_KEY;
		/* Check whether parent at the path really points to the child. */
		if (B_N_CHILD_NUM(parent, position) !=
		    PATH_OFFSET_PBUFFER(chk_path,
					path_offset + 1)->b_blocknr)
			return &MAX_KEY;
		/* Return delimiting key if position in the parent is not equal to zero. */
		if (position)
			return B_N_PDELIM_KEY(parent, position - 1);
	}
	/* Return MIN_KEY if we are in the root of the buffer tree. */
	if (PATH_OFFSET_PBUFFER(chk_path, FIRST_PATH_ELEMENT_OFFSET)->
	    b_blocknr == SB_ROOT_BLOCK(sb))
		return &MIN_KEY;
	return &MAX_KEY;
}

/* Drop the reference to each buffer in a path */
void pathrelse(struct treepath *search_path)
{
	int path_offset = search_path->path_length;

	RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
	       "PAP-5090: invalid path offset");

	while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET)
		brelse(PATH_OFFSET_PBUFFER(search_path, path_offset--));

	search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
}

/* This works by looking at the left and right delimiting keys for the buffer in the last path_element in
   the path.  These delimiting keys are stored at least one level above that buffer in the tree. If the
   buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in
   this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */
static inline int key_in_buffer(struct treepath *chk_path,	/* Path which should be checked.  */
				const struct cpu_key *key,	/* Key which should be checked.   */
				struct super_block *sb
    )
{

	RFALSE(!key || chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET
	       || chk_path->path_length > MAX_HEIGHT,
	       "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)",
	       key, chk_path->path_length);
	RFALSE(!PATH_PLAST_BUFFER(chk_path)->b_bdev,
	       "PAP-5060: device must not be NODEV");

	if (comp_keys(get_lkey(chk_path, sb), key) == 1)
		/* left delimiting key is bigger, that the key we look for */
		return 0;
	/*  if ( comp_keys(key, get_rkey(chk_path, sb)) != -1 ) */
	if (comp_keys(get_rkey(chk_path, sb), key) != 1)
		/* key must be less than right delimitiing key */
		return 0;
	return 1;
}

				/* I wonder if it would be less modest
                                   now that we use journaling. -Hans */
void reiserfs_free_block (struct reiserfs_transaction_handle *th, unsigned long block)
{
    struct super_block * s = th->t_super;
    struct reiserfs_super_block * rs;
    struct buffer_head * sbh;
    struct buffer_head ** apbh;
    int nr, offset;

  RFALSE(!s, "vs-4060: trying to free block on nonexistent device");
  RFALSE(is_reusable (s, block, 1) == 0, "vs-4070: can not free such block");

  PROC_INFO_INC( s, free_block );

  rs = SB_DISK_SUPER_BLOCK (s);
  sbh = SB_BUFFER_WITH_SB (s);
  apbh = SB_AP_BITMAP (s);

  get_bit_address (s, block, &nr, &offset);

  /* mark it before we clear it, just in case */
  journal_mark_freed(th, s, block) ;

  reiserfs_prepare_for_journal(s, apbh[nr], 1 ) ;

  /* clear bit for the given block in bit map */
  if (!reiserfs_test_and_clear_le_bit (offset, apbh[nr]->b_data)) {
      reiserfs_warning ("vs-4080: reiserfs_free_block: "
			"free_block (%04x:%lu)[dev:blocknr]: bit already cleared\n", 
	    s->s_dev, block);
  }
  journal_mark_dirty (th, s, apbh[nr]);

  reiserfs_prepare_for_journal(s, sbh, 1) ;
  /* update super block */
  set_sb_free_blocks( rs, sb_free_blocks(rs) + 1 );

  journal_mark_dirty (th, s, sbh);
  s->s_dirt = 1;
}

/* Replace delimiting key of buffers L[h] and S[h] by the given key.*/
static void replace_lkey(struct tree_balance *tb, int h, struct item_head *key)
{
	RFALSE(tb->L[h] == NULL || tb->CFL[h] == NULL,
	       "L[h](%p) and CFL[h](%p) must exist in replace_lkey",
	       tb->L[h], tb->CFL[h]);

	if (B_NR_ITEMS(PATH_H_PBUFFER(tb->tb_path, h)) == 0)
		return;

	memcpy(B_N_PDELIM_KEY(tb->CFL[h], tb->lkey[h]), key, KEY_SIZE);

	do_balance_mark_internal_dirty(tb, tb->CFL[h], 0);
}

/* Drop the reference to each buffer in a path and restore
 * dirty bits clean when preparing the buffer for the log.
 * This version should only be called from fix_nodes() */
void pathrelse_and_restore(struct super_block *sb,
			   struct treepath *search_path)
{
	int path_offset = search_path->path_length;

	RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
	       "clm-4000: invalid path offset");

	while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
		struct buffer_head *bh;
		bh = PATH_OFFSET_PBUFFER(search_path, path_offset--);
		reiserfs_restore_prepared_buffer(sb, bh);
		brelse(bh);
	}
	search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
}

/* Unreserve @blocks amount of blocks in fs pointed by @sb */
void reiserfs_release_claimed_blocks(
    struct super_block *sb, /* super block of
							  filesystem where
							  blocks should be
							  reserved */
    int blocks /* How much to unreserve */
)
{

    /* Fast case, if unreservation is zero - exit immediately. */
    if ( !blocks )
        return;

    spin_lock(&REISERFS_SB(sb)->bitmap_lock);
    REISERFS_SB(sb)->reserved_blocks -= blocks;
    spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
    RFALSE( REISERFS_SB(sb)->reserved_blocks < 0, "amount of blocks reserved became zero?");
}

/* returns 1 if it finds an indirect item and gets valid hint info
 * from it, otherwise 0
 */
static int get_left_neighbor(reiserfs_blocknr_hint_t *hint)
{
    struct path * path;
    struct buffer_head * bh;
    struct item_head * ih;
    int pos_in_item;
    __u32 * item;
    int ret = 0;

    if (!hint->path)		/* reiserfs code can call this function w/o pointer to path
				 * structure supplied; then we rely on supplied search_start */
        return 0;

    path = hint->path;
    bh = get_last_bh(path);
    RFALSE( !bh, "green-4002: Illegal path specified to get_left_neighbor");
    ih = get_ih(path);
    pos_in_item = path->pos_in_item;
    item = get_item (path);

    hint->search_start = bh->b_blocknr;

    if (!hint->formatted_node && is_indirect_le_ih (ih)) {
        /* for indirect item: go to left and look for the first non-hole entry
           in the indirect item */
        if (pos_in_item == I_UNFM_NUM (ih))
            pos_in_item--;
//	    pos_in_item = I_UNFM_NUM (ih) - 1;
        while (pos_in_item >= 0) {
            int t=get_block_num(item,pos_in_item);
            if (t) {
                hint->search_start = t;
                ret = 1;
                break;
            }
            pos_in_item --;
        }
    }

    /* does result value fit into specified region? */
    return ret;
}

/* it searches for a window of zero bits with given minimum and maximum lengths in one bitmap
 * block; */
static int scan_bitmap_block (struct reiserfs_transaction_handle *th,
                              int bmap_n, int *beg, int boundary, int min, int max, int unfm)
{
    struct super_block *s = th->t_super;
    struct reiserfs_bitmap_info *bi=&SB_AP_BITMAP(s)[bmap_n];
    int end, next;
    int org = *beg;

    BUG_ON (!th->t_trans_id);

    RFALSE(bmap_n >= SB_BMAP_NR (s), "Bitmap %d is out of range (0..%d)",bmap_n, SB_BMAP_NR (s) - 1);
    PROC_INFO_INC( s, scan_bitmap.bmap );
    /* this is unclear and lacks comments, explain how journal bitmaps
       work here for the reader.  Convey a sense of the design here. What
       is a window? */
    /* - I mean `a window of zero bits' as in description of this function - Zam. */

    if ( !bi ) {
        reiserfs_warning (s, "NULL bitmap info pointer for bitmap %d", bmap_n);
        return 0;
    }
    if (buffer_locked (bi->bh)) {
        PROC_INFO_INC( s, scan_bitmap.wait );
        __wait_on_buffer (bi->bh);
    }

    while (1) {
cont:
        if (bi->free_count < min)
            return 0; // No free blocks in this bitmap

        /* search for a first zero bit -- beggining of a window */
        *beg = reiserfs_find_next_zero_le_bit
               ((unsigned long*)(bi->bh->b_data), boundary, *beg);

        if (*beg + min > boundary) {
            /* search for a zero bit fails or the rest of bitmap block
            			      * cannot contain a zero window of minimum size */
            return 0;
        }

        if (unfm && is_block_in_journal(s,bmap_n, *beg, beg))
            continue;
        /* first zero bit found; we check next bits */
        for (end = *beg + 1;; end ++) {
            if (end >= *beg + max || end >= boundary || reiserfs_test_le_bit (end, bi->bh->b_data)) {
                next = end;
                break;
            }
            /* finding the other end of zero bit window requires looking into journal structures (in
             * case of searching for free blocks for unformatted nodes) */
            if (unfm && is_block_in_journal(s, bmap_n, end, &next))
                break;
        }

        /* now (*beg) points to beginning of zero bits window,
         * (end) points to one bit after the window end */
        if (end - *beg >= min) { /* it seems we have found window of proper size */
            int i;
            reiserfs_prepare_for_journal (s, bi->bh, 1);
            /* try to set all blocks used checking are they still free */
            for (i = *beg; i < end; i++) {
                /* It seems that we should not check in journal again. */
                if (reiserfs_test_and_set_le_bit (i, bi->bh->b_data)) {
                    /* bit was set by another process
                     * while we slept in prepare_for_journal() */
                    PROC_INFO_INC( s, scan_bitmap.stolen );
                    if (i >= *beg + min)	{
                        /* we can continue with smaller set of allocated blocks,
                        		   * if length of this set is more or equal to `min' */
                        end = i;
                        break;
                    }
                    /* otherwise we clear all bit were set ... */
                    while (--i >= *beg)
                        reiserfs_test_and_clear_le_bit (i, bi->bh->b_data);
                    reiserfs_restore_prepared_buffer (s, bi->bh);
                    *beg = org;
                    /* ... and search again in current block from beginning */
                    goto cont;
                }
            }
            bi->free_count -= (end - *beg);
            journal_mark_dirty (th, s, bi->bh);

            /* free block count calculation */
            reiserfs_prepare_for_journal (s, SB_BUFFER_WITH_SB(s), 1);
            PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
            journal_mark_dirty (th, s, SB_BUFFER_WITH_SB(s));

            return end - (*beg);
        } else {
            *beg = next;
        }
    }
}

int balance_internal(struct tree_balance *tb,	/* tree_balance structure               */
		     int h,	/* level of the tree                    */
		     int child_pos, struct item_head *insert_key,	/* key for insertion on higher level    */
		     struct buffer_head **insert_ptr	/* node for insertion on higher level */
    )
    /* if inserting/pasting
       {
       child_pos is the position of the node-pointer in S[h] that        *
       pointed to S[h-1] before balancing of the h-1 level;              *
       this means that new pointers and items must be inserted AFTER *
       child_pos
       }
       else
       {
       it is the position of the leftmost pointer that must be deleted (together with
       its corresponding key to the left of the pointer)
       as a result of the previous level's balancing.
       }
     */
{
	struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
	struct buffer_info bi;
	int order;		/* we return this: it is 0 if there is no S[h], else it is tb->S[h]->b_item_order */
	int insert_num, n, k;
	struct buffer_head *S_new;
	struct item_head new_insert_key;
	struct buffer_head *new_insert_ptr = NULL;
	struct item_head *new_insert_key_addr = insert_key;

	RFALSE(h < 1, "h (%d) can not be < 1 on internal level", h);

	PROC_INFO_INC(tb->tb_sb, balance_at[h]);

	order =
	    (tbSh) ? PATH_H_POSITION(tb->tb_path,
				     h + 1) /*tb->S[h]->b_item_order */ : 0;

	/* Using insert_size[h] calculate the number insert_num of items
	   that must be inserted to or deleted from S[h]. */
	insert_num = tb->insert_size[h] / ((int)(KEY_SIZE + DC_SIZE));

	/* Check whether insert_num is proper * */
	RFALSE(insert_num < -2 || insert_num > 2,
	       "incorrect number of items inserted to the internal node (%d)",
	       insert_num);
	RFALSE(h > 1 && (insert_num > 1 || insert_num < -1),
	       "incorrect number of items (%d) inserted to the internal node on a level (h=%d) higher than last internal level",
	       insert_num, h);

	/* Make balance in case insert_num < 0 */
	if (insert_num < 0) {
		balance_internal_when_delete(tb, h, child_pos);
		return order;
	}

	k = 0;
	if (tb->lnum[h] > 0) {
		/* shift lnum[h] items from S[h] to the left neighbor L[h].
		   check how many of new items fall into L[h] or CFL[h] after
		   shifting */
		n = B_NR_ITEMS(tb->L[h]);	/* number of items in L[h] */
		if (tb->lnum[h] <= child_pos) {
			/* new items don't fall into L[h] or CFL[h] */
			internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
					    tb->lnum[h]);
			/*internal_shift_left (tb->L[h],tb->CFL[h],tb->lkey[h],tbSh,tb->lnum[h]); */
			child_pos -= tb->lnum[h];
		} else if (tb->lnum[h] > child_pos + insert_num) {
			/* all new items fall into L[h] */
			internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
					    tb->lnum[h] - insert_num);
			/*                  internal_shift_left(tb->L[h],tb->CFL[h],tb->lkey[h],tbSh,
			   tb->lnum[h]-insert_num);
			 */
			/* insert insert_num keys and node-pointers into L[h] */
			bi.tb = tb;
			bi.bi_bh = tb->L[h];
			bi.bi_parent = tb->FL[h];
			bi.bi_position = get_left_neighbor_position(tb, h);
			internal_insert_childs(&bi,
					       /*tb->L[h], tb->S[h-1]->b_next */
					       n + child_pos + 1,
					       insert_num, insert_key,
					       insert_ptr);

			insert_num = 0;
		} else {
			struct disk_child *dc;

			/* some items fall into L[h] or CFL[h], but some don't fall */
			internal_shift1_left(tb, h, child_pos + 1);
			/* calculate number of new items that fall into L[h] */
			k = tb->lnum[h] - child_pos - 1;
			bi.tb = tb;
			bi.bi_bh = tb->L[h];
			bi.bi_parent = tb->FL[h];
			bi.bi_position = get_left_neighbor_position(tb, h);
			internal_insert_childs(&bi,
					       /*tb->L[h], tb->S[h-1]->b_next, */
					       n + child_pos + 1, k,
//.........这里部分代码省略.........

/* makes object identifier unused */
void reiserfs_release_objectid(struct reiserfs_transaction_handle *th,
			       __u32 objectid_to_release)
{
	struct super_block *s = th->t_super;
	struct reiserfs_super_block *rs = SB_DISK_SUPER_BLOCK(s);
	__le32 *map = objectid_map(s, rs);
	int i = 0;

	BUG_ON(!th->t_trans_id);
	//return;
	check_objectid_map(s, map);

	reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1);
	journal_mark_dirty(th, s, SB_BUFFER_WITH_SB(s));

	/* start at the beginning of the objectid map (i = 0) and go to
	   the end of it (i = disk_sb->s_oid_cursize).  Linear search is
	   what we use, though it is possible that binary search would be
	   more efficient after performing lots of deletions (which is
	   when oids is large.)  We only check even i's. */
	while (i < sb_oid_cursize(rs)) {
		if (objectid_to_release == le32_to_cpu(map[i])) {
			/* This incrementation unallocates the objectid. */
			//map[i]++;
			le32_add_cpu(&map[i], 1);

			/* Did we unallocate the last member of an odd sequence, and can shrink oids? */
			if (map[i] == map[i + 1]) {
				/* shrink objectid map */
				memmove(map + i, map + i + 2,
					(sb_oid_cursize(rs) - i -
					 2) * sizeof(__u32));
				//disk_sb->s_oid_cursize -= 2;
				set_sb_oid_cursize(rs, sb_oid_cursize(rs) - 2);

				RFALSE(sb_oid_cursize(rs) < 2 ||
				       sb_oid_cursize(rs) > sb_oid_maxsize(rs),
				       "vs-15005: objectid map corrupted cur_size == %d (max == %d)",
				       sb_oid_cursize(rs), sb_oid_maxsize(rs));
			}
			return;
		}

		if (objectid_to_release > le32_to_cpu(map[i]) &&
		    objectid_to_release < le32_to_cpu(map[i + 1])) {
			/* size of objectid map is not changed */
			if (objectid_to_release + 1 == le32_to_cpu(map[i + 1])) {
				//objectid_map[i+1]--;
				le32_add_cpu(&map[i + 1], -1);
				return;
			}

			/* JDM comparing two little-endian values for equality -- safe */
			if (sb_oid_cursize(rs) == sb_oid_maxsize(rs)) {
				/* objectid map must be expanded, but there is no space */
				PROC_INFO_INC(s, leaked_oid);
				return;
			}

			/* expand the objectid map */
			memmove(map + i + 3, map + i + 1,
				(sb_oid_cursize(rs) - i - 1) * sizeof(__u32));
			map[i + 1] = cpu_to_le32(objectid_to_release);
			map[i + 2] = cpu_to_le32(objectid_to_release + 1);
			set_sb_oid_cursize(rs, sb_oid_cursize(rs) + 2);
			return;
		}
		i += 2;
	}

	reiserfs_error(s, "vs-15011", "tried to free free object id (%lu)",
		       (long unsigned)objectid_to_release);
}

/* Delete insert_num node pointers together with their left items
 * and balance current node.*/
static void balance_internal_when_delete(struct tree_balance *tb,
					 int h, int child_pos)
{
	int insert_num;
	int n;
	struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
	struct buffer_info bi;

	insert_num = tb->insert_size[h] / ((int)(DC_SIZE + KEY_SIZE));

	/* delete child-node-pointer(s) together with their left item(s) */
	bi.tb = tb;
	bi.bi_bh = tbSh;
	bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
	bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);

	internal_delete_childs(&bi, child_pos, -insert_num);

	RFALSE(tb->blknum[h] > 1,
	       "tb->blknum[%d]=%d when insert_size < 0", h, tb->blknum[h]);

	n = B_NR_ITEMS(tbSh);

	if (tb->lnum[h] == 0 && tb->rnum[h] == 0) {
		if (tb->blknum[h] == 0) {
			/* node S[h] (root of the tree) is empty now */
			struct buffer_head *new_root;

			RFALSE(n
			       || B_FREE_SPACE(tbSh) !=
			       MAX_CHILD_SIZE(tbSh) - DC_SIZE,
			       "buffer must have only 0 keys (%d)", n);
			RFALSE(bi.bi_parent, "root has parent (%p)",
			       bi.bi_parent);

			/* choose a new root */
			if (!tb->L[h - 1] || !B_NR_ITEMS(tb->L[h - 1]))
				new_root = tb->R[h - 1];
			else
				new_root = tb->L[h - 1];
			/* switch super block's tree root block number to the new value */
			PUT_SB_ROOT_BLOCK(tb->tb_sb, new_root->b_blocknr);
			//REISERFS_SB(tb->tb_sb)->s_rs->s_tree_height --;
			PUT_SB_TREE_HEIGHT(tb->tb_sb,
					   SB_TREE_HEIGHT(tb->tb_sb) - 1);

			do_balance_mark_sb_dirty(tb,
						 REISERFS_SB(tb->tb_sb)->s_sbh,
						 1);
			/*&&&&&&&&&&&&&&&&&&&&&& */
			if (h > 1)
				/* use check_internal if new root is an internal node */
				check_internal(new_root);
			/*&&&&&&&&&&&&&&&&&&&&&& */

			/* do what is needed for buffer thrown from tree */
			reiserfs_invalidate_buffer(tb, tbSh);
			return;
		}
		return;
	}

	if (tb->L[h] && tb->lnum[h] == -B_NR_ITEMS(tb->L[h]) - 1) {	/* join S[h] with L[h] */

		RFALSE(tb->rnum[h] != 0,
		       "invalid tb->rnum[%d]==%d when joining S[h] with L[h]",
		       h, tb->rnum[h]);

		internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, n + 1);
		reiserfs_invalidate_buffer(tb, tbSh);

		return;
	}

	if (tb->R[h] && tb->rnum[h] == -B_NR_ITEMS(tb->R[h]) - 1) {	/* join S[h] with R[h] */
		RFALSE(tb->lnum[h] != 0,
		       "invalid tb->lnum[%d]==%d when joining S[h] with R[h]",
		       h, tb->lnum[h]);

		internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, n + 1);

		reiserfs_invalidate_buffer(tb, tbSh);
		return;
	}

	if (tb->lnum[h] < 0) {	/* borrow from left neighbor L[h] */
		RFALSE(tb->rnum[h] != 0,
		       "wrong tb->rnum[%d]==%d when borrow from L[h]", h,
		       tb->rnum[h]);
		/*internal_shift_right (tb, h, tb->L[h], tb->CFL[h], tb->lkey[h], tb->S[h], -tb->lnum[h]); */
		internal_shift_right(INTERNAL_SHIFT_FROM_L_TO_S, tb, h,
				     -tb->lnum[h]);
		return;
	}

	if (tb->rnum[h] < 0) {	/* borrow from right neighbor R[h] */
		RFALSE(tb->lnum[h] != 0,
		       "invalid tb->lnum[%d]==%d when borrow from R[h]",
//.........这里部分代码省略.........

int reiserfs_check_path(struct treepath *p)
{
	RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET,
	       "path not properly relsed");
	return 0;
}

/* 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 reiserfs_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);

	/*&&&&&&&&&&&&&&&&&&&&&&&& */
	check_internal(dest);
	/*&&&&&&&&&&&&&&&&&&&&&&&& */

	if (dest_bi->bi_parent) {
		struct disk_child *t_dc;
		t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
		put_dc_size(t_dc,
			    dc_size(t_dc) + (KEY_SIZE * (cpy_num - 1) +
					     DC_SIZE * cpy_num));

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

}