自学教程：C++ B_NR_ITEMS函数代码示例

static struct key * _get_rkey (struct path * path){    int pos, offset = path->path_length;    struct buffer_head * bh;    if (offset < FIRST_PATH_ELEMENT_OFFSET)	die ("_get_rkey: illegal offset in the path (%d)", offset);    while (offset-- > FIRST_PATH_ELEMENT_OFFSET) {	if (! buffer_uptodate (PATH_OFFSET_PBUFFER (path, offset)))	    die ("_get_rkey: parent is not uptodate");	/* Parent at the path is not in the tree now. */	if (! B_IS_IN_TREE (bh = PATH_OFFSET_PBUFFER (path, offset)))	    die ("_get_rkey: buffer on the path is not in tree");	/* Check whether position in the parrent is correct. */	if ((pos = PATH_OFFSET_POSITION (path, offset)) > B_NR_ITEMS (bh))	    die ("_get_rkey: invalid position (%d) in the path", pos);	/* Check whether parent at the path really points to the child. */	if (B_N_CHILD_NUM (bh, pos) != PATH_OFFSET_PBUFFER (path, offset + 1)->b_blocknr)	    die ("_get_rkey: invalid block number (%d). Must be %d",		 B_N_CHILD_NUM (bh, pos), PATH_OFFSET_PBUFFER (path, offset + 1)->b_blocknr);		/* Return delimiting key if position in the parent is not the last one. */	if (pos != B_NR_ITEMS (bh))	    return B_N_PDELIM_KEY (bh, pos);    }        /* there is no right delimiting key */    return 0;}

/* this can be invoked both to shift from S to L and from R to S */static void internal_shift_left(int mode,	/* INTERNAL_FROM_S_TO_L | INTERNAL_FROM_R_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;	internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,				       &d_key_position, &cf);	/*printk("pointer_amount = %d/n",pointer_amount); */	if (pointer_amount) {		/* insert delimiting key from common father of dest and src to node dest into position B_NR_ITEM(dest) */		internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf,				    d_key_position);		if (B_NR_ITEMS(src_bi.bi_bh) == pointer_amount - 1) {			if (src_bi.bi_position /*src->b_item_order */  == 0)				replace_key(tb, cf, d_key_position,					    src_bi.					    bi_parent /*src->b_parent */ , 0);		} else			replace_key(tb, cf, d_key_position, src_bi.bi_bh,				    pointer_amount - 1);	}	/* last parameter is del_parameter */	internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,				     pointer_amount, 0);}

/* this prints internal nodes (4 keys/items in line) (dc_number,   dc_size)[k_dirid, k_objectid, k_offset, k_uniqueness](dc_number,   dc_size)...*/static int print_internal(struct buffer_head *bh, int first, int last){	struct reiserfs_key *key;	struct disk_child *dc;	int i;	int from, to;	if (!B_IS_KEYS_LEVEL(bh))		return 1;	check_internal(bh);	if (first == -1) {		from = 0;		to = B_NR_ITEMS(bh);	} else {		from = first;		to = last < B_NR_ITEMS(bh) ? last : B_NR_ITEMS(bh);	}	reiserfs_printk("INTERNAL NODE (%ld) contains %z/n", bh->b_blocknr, bh);	dc = B_N_CHILD(bh, from);	reiserfs_printk("PTR %d: %y ", from, dc);	for (i = from, key = B_N_PDELIM_KEY(bh, from), dc++; i < to;	     i++, key++, dc++) {		reiserfs_printk("KEY %d: %k PTR %d: %y ", i, key, i + 1, dc);		if (i && i % 4 == 0)			printk("/n");	}	printk("/n");	return 0;}

/* 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 print_path (struct tree_balance * tb, struct path * path){    int h = 0;    struct buffer_head * bh;        if (tb) {	while (tb->insert_size[h]) {	    bh = PATH_H_PBUFFER (path, h);	    printk ("block %lu (level=%d), position %d/n", bh ? bh->b_blocknr : 0,		    bh ? B_LEVEL (bh) : 0, PATH_H_POSITION (path, h));	    h ++;	}  } else {      int offset = path->path_length;      struct buffer_head * bh;      printk ("Offset    Bh     (b_blocknr, b_count) Position Nr_item/n");      while ( offset > ILLEGAL_PATH_ELEMENT_OFFSET ) {	  bh = PATH_OFFSET_PBUFFER (path, offset);	  printk ("%6d %10p (%9lu, %7d) %8d %7d/n", offset, 		  bh, bh ? bh->b_blocknr : 0, bh ? atomic_read (&(bh->b_count)) : 0,		  PATH_OFFSET_POSITION (path, offset), bh ? B_NR_ITEMS (bh) : -1);	  	  offset --;      }  }}

int is_leaf_bad (struct buffer_head * bh){    int i;    struct item_head * ih;    int bad = 0;    assert (is_leaf_node (bh));    for (i = 0, ih = B_N_PITEM_HEAD (bh,  0); i < B_NR_ITEMS (bh); i ++, ih ++) {	if (is_bad_item (bh, ih, B_I_PITEM (bh, ih))) {	    fsck_log ("is_leaf_bad: block %lu: %d-th item (%H) is bad/n",		      bh->b_blocknr, i, ih);	    bad = 1;	    continue;	}	if (i && bad_pair (fs, bh, i)) {	    fsck_log ("is_leaf_bad: block %luL %d-th item (%H) and "		      "the next one (%H) are in wrong order/n",		     bh->b_blocknr, i - 1, ih - 1, ih);	    bad = 1;	}    }    return bad;}

static void compare_neighboring_leaves_after_all (void){    struct item_head * left = B_N_PITEM_HEAD(g_left, B_NR_ITEMS (g_left) - 1);    struct item_head * right = B_N_PITEM_HEAD(g_right, 0);    /*  struct key * left = B_N_PKEY (g_left, B_NR_ITEMS (g_left) - 1);	struct key * right = B_N_PKEY (g_right, 0);*/        /*      if (comp_keys (&left->ih_key, B_PRIGHT_DELIM_KEY (g_left)) != SECOND_GREATER)      die ("compare_neighboring_leaves_after_all: invalid right delimiting key");    */    if (comp_keys (&left->ih_key, B_N_PKEY (g_right, 0)) != -1/*SECOND_GREATER*/)	die ("compare_neighboring_leaves_after_all: left key is greater than the right one");        if (//comp_le_keys (B_PRIGHT_DELIM_KEY (g_left), g_dkey) != KEYS_IDENTICAL ||	comp_keys (g_dkey, B_N_PKEY (g_right, 0))) {	reiserfs_panic (0, "compare_neighboring_leaves_after all: invalid delimiting keys from left to right (%k %k)",			g_dkey, B_N_PKEY (g_right, 0));    }        if (!not_of_one_file (&left->ih_key, &right->ih_key)) {	// items of one file: check offset correctness	if (is_direct_ih (left) || is_indirect_ih (left))	    //if (get_offset(&right->ih_key) != get_offset(&left->ih_key) + get_bytes_number (g_left, left /*B_NR_ITEMS (g_left) - 1*/, 0, CHECK_FREE_BYTES))	    if (get_offset(&right->ih_key) != get_offset(&left->ih_key) + get_bytes_number (left, g_left->b_size))		die ("compare_neighboring_leaves_after all: hole between items or items are overlapped");    }    is_there_unaccessed_items (g_left);    }

static void check_internal_block_head (struct buffer_head * bh){    struct block_head * blkh;        blkh = B_BLK_HEAD (bh);    if (!(B_LEVEL (bh) > DISK_LEAF_NODE_LEVEL && B_LEVEL (bh) <= MAX_HEIGHT))	reiserfs_panic (0, "vs-6025: check_internal_block_head: invalid level %z", bh);    if (B_NR_ITEMS (bh) > (bh->b_size - BLKH_SIZE) / IH_SIZE)	reiserfs_panic (0, "vs-6030: check_internal_block_head: invalid item number %z", bh);    if (B_FREE_SPACE (bh) != 	bh->b_size - BLKH_SIZE - KEY_SIZE * B_NR_ITEMS (bh) - DC_SIZE * (B_NR_ITEMS (bh) + 1))	reiserfs_panic (0, "vs-6040: check_internal_block_head: invalid free space %z", bh);}

static void compare_neighboring_leaves_in_pass1 (void){    struct key * left = B_N_PKEY (g_left, B_NR_ITEMS (g_left) - 1);    if (comp_keys (left, B_N_PKEY (g_right, 0)) != -1/*SECOND_GREATER*/)	die ("compare_neighboring_leaves_in_pass1: left key is greater, that the right one");        if (/*comp_keys (B_PRIGHT_DELIM_KEY (g_left), g_dkey) == FIRST_GREATER ||*/	comp_keys (g_dkey, B_N_PKEY (g_right, 0))) {	reiserfs_panic (0, "compare_neighboring_leaves_in_pass1: dkey %k, first key in right %k",			g_dkey, B_N_PKEY (g_right, 0));    }        check_items (g_left);        /*&&&&&&&&&&&&&&&&&&&&&&&&&&      for (i = 0, ih = B_N_PITEM_HEAD (g_left, i); i < B_NR_ITEMS (g_left); i ++, ih ++)      if (is_item_accessed (ih) == YES)      die ("compare_neighboring_leaves_in_pass1: item marked as accessed in g_left");      for (i = 0, ih = B_N_PITEM_HEAD (g_right, i); i < B_NR_ITEMS (g_right); i ++, ih ++)      if (is_item_accessed (ih) == YES)      die ("compare_neighboring_leaves_in_pass1: item marked as accessed in g_right");      &&&&&&&&&&&&&&&&&&&&&&&&&&&*/    }

int is_internal_bad (struct buffer_head * bh){    struct key * key;    int i;      if (!is_internal_node(bh))	return 0;    for (i = 0; i < B_NR_ITEMS (bh); i ++) {	key = B_N_PDELIM_KEY (bh, i);	if (//key->k_dir_id >= key->k_objectid ||	    le32_to_cpu(key->u.k_offset_v1.k_uniqueness) != V1_DIRENTRY_UNIQUENESS &&            le32_to_cpu(key->u.k_offset_v1.k_uniqueness) != V1_DIRECT_UNIQUENESS &&	    le32_to_cpu(key->u.k_offset_v1.k_uniqueness) != V1_INDIRECT_UNIQUENESS &&            le32_to_cpu(key->u.k_offset_v1.k_uniqueness) != V1_SD_UNIQUENESS &&	    offset_v2_k_type( &(key->u.k_offset_v2) ) != TYPE_DIRENTRY &&            offset_v2_k_type( &(key->u.k_offset_v2) ) != TYPE_DIRECT &&	    offset_v2_k_type( &(key->u.k_offset_v2) ) != TYPE_INDIRECT &&            offset_v2_k_type( &(key->u.k_offset_v2) ) != TYPE_STAT_DATA //&&	    //	key->u.k_offset_v1.k_uniqueness != V1_ANY_UNIQUENESS && key->u.k_offset_v2.k_type != TYPE_ANY		    )	    return 1;    }    return 0;}

/* 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. */static void internal_move_pointers_items(struct buffer_info *dest_bi,					 struct buffer_info *src_bi,					 int last_first, int cpy_num,					 int del_par){	int first_pointer;	int first_item;	internal_copy_pointers_items(dest_bi, src_bi->bi_bh, last_first,				     cpy_num);	if (last_first == FIRST_TO_LAST) {	/* shift_left occurs */		first_pointer = 0;		first_item = 0;		/* delete cpy_num - del_par pointers and keys starting for pointers with first_pointer,		   for key - with first_item */		internal_delete_pointers_items(src_bi, first_pointer,					       first_item, cpy_num - del_par);	} else {		/* shift_right occurs */		int i, j;		i = (cpy_num - del_par ==		     (j =		      B_NR_ITEMS(src_bi->bi_bh)) + 1) ? 0 : j - cpy_num +		    del_par;		internal_delete_pointers_items(src_bi,					       j + 1 - cpy_num + del_par, i,					       cpy_num - del_par);	}}

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

static voidsprintf_block_head(char *buf, struct buf *bp){	sprintf(buf, "level=%d, nr_items=%d, free_space=%d rdkey ",	    B_LEVEL(bp), B_NR_ITEMS(bp), B_FREE_SPACE(bp));}

void print_disk_tree (int block_nr){    struct buffer_head * bh;    bh = bread (g_sb.s_dev, block_nr, g_sb.s_blocksize);    if (B_IS_KEYS_LEVEL (bh)) {	int i;	struct disk_child * dc;	g_stat_info.nr_internals ++;	print_block (bh, print_mode (), -1, -1);      	dc = B_N_CHILD (bh, 0);	for (i = 0; i <= B_NR_ITEMS (bh); i ++, dc ++)	    print_disk_tree (dc->dc_block_number);    } else if (B_IS_ITEMS_LEVEL (bh)) {	g_stat_info.nr_leaves ++;	print_block (bh, print_mode (), -1, -1);    } else {	print_block (bh, print_mode (), -1, -1);	die ("print_disk_tree: bad block type");    }    brelse (bh);}

static int _search_by_key (reiserfs_filsys_t fs, struct key * key, struct path * path){    struct buffer_head * bh;    unsigned long block = SB_ROOT_BLOCK (fs);    struct path_element * curr;    int retval;        path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;    while (1) {	curr = PATH_OFFSET_PELEMENT (path, ++ path->path_length);	bh = curr->pe_buffer = bread (fs->s_dev, block, fs->s_blocksize);        if (bh == 0) {	    path->path_length --;	    pathrelse (path);	    return ITEM_NOT_FOUND;	}	retval = _bin_search (key, B_N_PKEY (bh, 0), B_NR_ITEMS (bh),			      is_leaf_node (bh) ? IH_SIZE : KEY_SIZE, &(curr->pe_position), comp_keys);	if (retval == ITEM_FOUND) {	    /* key found, return if this is leaf level */	    if (is_leaf_node (bh)) {		path->pos_in_item = 0;		return ITEM_FOUND;	    }	    curr->pe_position ++;	} else {	    /* key not found in the node */	    if (is_leaf_node (bh))		return ITEM_NOT_FOUND;	}	block = B_N_CHILD_NUM (bh, curr->pe_position);    }    printf ("search_by_key: you can not get here/n");    return ITEM_NOT_FOUND;}

/* Get delimiting key of the buffer at the path and its right neighbor. */const struct key *get_rkey(const struct path *p_s_chk_path,    const struct reiserfs_sb_info *p_s_sbi){	struct buf *p_s_parent;	int n_position, n_path_offset = p_s_chk_path->path_length;	while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {		/* Parent at the path is not in the tree now. */		if (!B_IS_IN_TREE(p_s_parent =		    PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)))			return (&MIN_KEY);		/* Check whether position in the parent is correct. */		if ((n_position = PATH_OFFSET_POSITION(p_s_chk_path,		    n_path_offset)) >		    B_NR_ITEMS(p_s_parent))			return (&MIN_KEY);		/*		 * Check whether parent at the path really points to the		 * child.		 */		if (B_N_CHILD_NUM(p_s_parent, n_position) !=		    (PATH_OFFSET_PBUFFER(p_s_chk_path,					 n_path_offset + 1)->b_blkno		     / btodb(p_s_sbi->s_blocksize)))			return (&MIN_KEY);		/*		 * Return delimiting key if position in the parent is not		 * the last one.		 */		if (n_position != B_NR_ITEMS(p_s_parent))			return (B_N_PDELIM_KEY(p_s_parent, n_position));	}	/* Return MAX_KEY if we are in the root of the buffer tree. */	if ((PATH_OFFSET_PBUFFER(p_s_chk_path,	    FIRST_PATH_ELEMENT_OFFSET)->b_blkno	    / btodb(p_s_sbi->s_blocksize)) == SB_ROOT_BLOCK(p_s_sbi))		return (&MAX_KEY);	return (&MIN_KEY);}

void check_leaf(struct buffer_head *bh){	int i;	struct item_head *ih;	if (!bh)		return;	check_leaf_block_head(bh);	for (i = 0, ih = B_N_PITEM_HEAD(bh, 0); i < B_NR_ITEMS(bh); i++, ih++)		op_check_item(ih, B_I_PITEM(bh, ih));}

/* Get delimiting key of the buffer at the path and its right neighbor. */inline const struct reiserfs_key *get_rkey(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-5030: invalid offset in the path");	while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {		RFALSE(!buffer_uptodate		       (PATH_OFFSET_PBUFFER(chk_path, path_offset)),		       "PAP-5040: 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 &MIN_KEY;		/* Check whether position in the parent is correct. */		if ((position =		     PATH_OFFSET_POSITION(chk_path,					  path_offset)) >		    B_NR_ITEMS(parent))			return &MIN_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 &MIN_KEY;		/* Return delimiting key if position in the parent is not the last one. */		if (position != B_NR_ITEMS(parent))			return B_N_PDELIM_KEY(parent, position);	}	/* Return MAX_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 &MAX_KEY;	return &MIN_KEY;}

/* Get delimiting key of the buffer at the path and its right neighbor. */inline	struct  key * get_rkey  (    struct path         * p_s_chk_path,    struct super_block  * p_s_sb    ) {    int                   n_position,	n_path_offset = p_s_chk_path->path_length;    struct buffer_head  * p_s_parent;#ifdef CONFIG_REISERFS_CHECK    if ( n_path_offset < FIRST_PATH_ELEMENT_OFFSET )	reiserfs_panic(p_s_sb,"PAP-5030: get_rkey: illegal offset in the path");#endif    while ( n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET ) {#ifdef CONFIG_REISERFS_CHECK	if ( ! buffer_uptodate(PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )	    reiserfs_panic(p_s_sb, "PAP-5040: get_rkey: parent is not uptodate");#endif	/* Parent at the path is not in the tree now. */	if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )	    return &MIN_KEY;	/* Check whether position in the parrent is correct. */	if ( (n_position = PATH_OFFSET_POSITION(p_s_chk_path, n_path_offset)) > B_NR_ITEMS(p_s_parent) )	    return &MIN_KEY;	/* Check whether parent at the path really points to the child. */	if ( B_N_CHILD_NUM(p_s_parent, n_position) !=	     PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset + 1)->b_blocknr )	    return &MIN_KEY;	/* Return delimiting key if position in the parent is not the last one. */	if ( n_position != B_NR_ITEMS(p_s_parent) )	    return B_N_PDELIM_KEY(p_s_parent, n_position);    }    /* Return MAX_KEY if we are in the root of the buffer tree. */    if ( PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==	 SB_ROOT_BLOCK (p_s_sb) )	return &MAX_KEY;    return  &MIN_KEY;}

/* only directory item can be fatally bad */static int is_leaf_bad_xx (struct buffer_head * bh){    int i;    struct item_head * ih;    if (!is_leaf_node (bh))	return 0;    for (i = 0, ih = B_N_PITEM_HEAD (bh,  0); i < B_NR_ITEMS (bh); i ++, ih ++)	if (is_bad_item (bh, ih, B_I_PITEM (bh, ih))) {	    return 1;	}    return 0;}

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

/* 'upper' item is correct if 'upper + 2' exists and its key is greater than   key of 'upper' */static int upper_correct (struct buffer_head * bh, struct item_head * upper,			  int upper_item_num){    if (upper_item_num + 2 < B_NR_ITEMS (bh)) {	if (comp_keys (&upper->ih_key, &(upper + 2)->ih_key) != -1)	    /* item-num's item is out of order of order */	    return 0;	return 1;    }        /* there is no item above the "bad pair" */    return 2;}

/* %z */static int print_block_head (FILE * stream,			     const struct printf_info *info,			     const void *const *args){    const struct buffer_head * bh;    char * buffer;    int len;    bh = *((const struct buffer_head **)(args[0]));    len = asprintf (&buffer, "level=%d, nr_items=%d, free_space=%d rdkey",		    B_LEVEL (bh), B_NR_ITEMS (bh), node_free_space (bh));    FPRINTF;}

static void reiserfsck_check_tree (int dev, int block, int size, check_function_t comp_func){    struct buffer_head * bh;    int what_node;        bh = bread (dev, block, size);    if (bh == 0)        reiserfs_panic("reiserfsck_check_tree: unable to read %lu block on device 0x%x/n",                block, dev);    if (!B_IS_IN_TREE (bh)) {	reiserfs_panic (0, "reiserfsck_check_tree: buffer (%b %z) not in tree", bh, bh);    }        what_node = who_is_this (bh->b_data, bh->b_size);    if (what_node != THE_LEAF && what_node != THE_INTERNAL)	die ("Not formatted node");    if (!is_block_used (bh->b_blocknr))	die ("Not marked as used");    if (is_leaf_node (bh) && is_leaf_bad_xx (bh))	die ("Bad leaf");    if (is_internal_node(bh) && is_internal_bad (bh))	die ("bad internal");        if (is_internal_node (bh)) {	int i;	struct disk_child * dc;		dc = B_N_CHILD (bh, 0);	for (i = 0; i <= B_NR_ITEMS (bh); i ++, dc ++) {	    reiserfsck_check_tree (dev, dc_block_number(dc), size, comp_func);	    g_dkey = B_N_PDELIM_KEY (bh, i);	}    } else if (is_leaf_node (bh)) {	g_right = bh;	if (g_left != 0 && g_dkey != 0) {	    comp_func ();	    brelse (g_left);	}	g_left = g_right;	return;    } else {	reiserfs_panic ("reiserfsck_check_tree: block %lu has bad block type (%b)",			bh->b_blocknr, bh);    }    brelse (bh);}

static void check_items (struct buffer_head * bh){    int i;    struct item_head * ih;    for (i = 0; i < B_NR_ITEMS (bh); i++)    {	ih = B_N_PITEM_HEAD (bh, i);		if (is_direntry_ih (ih))	    check_directory_item (ih, bh);	    }}

void print_path (struct tree_balance * tb, struct path * path){    int offset = path->path_length;    struct buffer_head * bh;    printf ("Offset    Bh     (b_blocknr, b_count) Position Nr_item/n");    while ( offset > ILLEGAL_PATH_ELEMENT_OFFSET ) {	bh = PATH_OFFSET_PBUFFER (path, offset);	printf ("%6d %10p (%9lu, %7d) %8d %7d/n", offset, 		bh, bh ? bh->b_blocknr : 0, bh ? bh->b_count : 0,		PATH_OFFSET_POSITION (path, offset), bh ? B_NR_ITEMS (bh) : -1);		offset --;    }}

static void is_there_unaccessed_items (struct buffer_head * bh){    int i;    struct item_head * ih;        ih = B_N_PITEM_HEAD (bh, 0);    for (i = 0; i < B_NR_ITEMS (bh); i ++, ih ++) {	if (is_objectid_used (fs, ih->ih_key.k_objectid) == 0)	    die ("is_there_unaccessed_items: %lu is not marked as used", ih->ih_key.k_objectid);		if (!is_item_reachable (ih)) {	    die ("is_there_unaccessed_items: block %lu - unaccessed item found",		 bh->b_blocknr);	}    }}

/* it always shifts from S[h] to L[h] */static void internal_shift1_left(struct tree_balance *tb,				 int h, int pointer_amount){	struct buffer_info dest_bi, src_bi;	struct buffer_head *cf;	int d_key_position;	internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,				       &dest_bi, &src_bi, &d_key_position, &cf);	/* insert lkey[h]-th key  from CFL[h] to left neighbor L[h] */	if (pointer_amount > 0)		internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf,				    d_key_position);	/* last parameter is del_parameter */	internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,				     pointer_amount, 1);}

static void reiserfsck_check_cached_tree (int dev, int block, int size){    struct buffer_head * bh;    int what_node;    bh =  find_buffer(dev, block, size);    if (bh == 0)	return;    if (!buffer_uptodate (bh)) {	die ("reiserfsck_check_cached_tree: found notuptodate buffer");    }    bh->b_count ++;        if (!B_IS_IN_TREE (bh)) {	die ("reiserfsck_check_cached_tree: buffer (%b %z) not in tree", bh, bh);    }    what_node = who_is_this (bh->b_data, bh->b_size);    if ((what_node != THE_LEAF && what_node != THE_INTERNAL) ||	!is_block_used (bh->b_blocknr) ||	(is_leaf_node (bh) && is_leaf_bad (bh)) ||	(is_internal_node(bh) && is_internal_bad (bh)))	die ("reiserfsck_check_cached_tree: bad node in the tree");    if (is_internal_node (bh)) {	int i;	struct disk_child * dc;		dc = B_N_CHILD (bh, 0);	for (i = 0; i <= B_NR_ITEMS (bh); i ++, dc ++) {	    reiserfsck_check_cached_tree (dev, dc_block_number(dc), size);	    g_dkey = B_N_PDELIM_KEY (bh, i);	}    } else if (is_leaf_node (bh)) {	brelse (bh);	return;    } else {	reiserfs_panic ("reiserfsck_check_cached_tree: block %lu has bad block type (%b)",			bh->b_blocknr, bh);    }    brelse (bh);}