Lines Matching defs:n_h
779 static int get_empty_nodes(struct tree_balance *p_s_tb, int n_h)
782 *p_s_Sh = PATH_H_PBUFFER(p_s_tb->tb_path, n_h);
794 (n_h) of the balancing analysis.
802 by all of the levels of the tree below n_h. */
803 /* blknum includes S[n_h], so we subtract 1 in this calculation */
805 n_counter < n_h; n_counter++)
812 n_amount_needed = (p_s_Sh) ? (p_s_tb->blknum[n_h] - 1) : 1;
895 static int is_left_neighbor_in_cache(struct tree_balance *p_s_tb, int n_h)
902 if (!p_s_tb->FL[n_h]) /* Father of the left neighbor does not exist. */
906 p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1);
910 !B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
912 !buffer_uptodate(p_s_tb->FL[n_h]),
914 p_s_father, p_s_tb->FL[n_h]);
917 n_left_neighbor_position = (p_s_father == p_s_tb->FL[n_h]) ?
918 p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->FL[n_h]);
921 B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position);
953 int n_h,
964 n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);
966 /* Starting from F[n_h] go upwards in the tree, and look for the common
967 ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
1034 LEFT_PARENTS) ? (p_s_tb->lkey[n_h - 1] =
1036 1) : (p_s_tb->rkey[n_h -
1045 n_h + 1) == IO_ERROR)
1057 RFALSE(B_LEVEL(*pp_s_father) != n_h + 1,
1074 static int get_parents(struct tree_balance *p_s_tb, int n_h)
1079 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
1086 decrement_bcount(p_s_tb->FL[n_h]);
1087 decrement_bcount(p_s_tb->CFL[n_h]);
1088 decrement_bcount(p_s_tb->FR[n_h]);
1089 decrement_bcount(p_s_tb->CFR[n_h]);
1090 p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] =
1091 p_s_tb->CFR[n_h] = NULL;
1103 p_s_tb->lkey[n_h] = n_position - 1;
1109 if ((n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
1115 decrement_bcount(p_s_tb->FL[n_h]);
1116 p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
1117 decrement_bcount(p_s_tb->CFL[n_h]);
1118 p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */
1124 /* Get parent FR[n_h] of R[n_h]. */
1126 /* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
1127 if (n_position == B_NR_ITEMS(PATH_H_PBUFFER(p_s_path, n_h + 1))) {
1128 /* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
1129 Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
1130 not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
1132 get_far_parent(p_s_tb, n_h + 1, &p_s_curf, &p_s_curcf,
1136 /* Current node is not the last child of its parent F[n_h]. */
1142 p_s_tb->rkey[n_h] = n_position;
1145 decrement_bcount(p_s_tb->FR[n_h]);
1146 p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */
1148 decrement_bcount(p_s_tb->CFR[n_h]);
1149 p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */
1884 static int get_direct_parent(struct tree_balance *p_s_tb, int n_h)
1889 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
1930 /* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
1931 * of S[n_h] we
1932 * need in order to balance S[n_h], and get them if necessary.
1936 static int get_neighbors(struct tree_balance *p_s_tb, int n_h)
1939 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1);
1944 PROC_INFO_INC(p_s_sb, get_neighbors[n_h]);
1946 if (p_s_tb->lnum[n_h]) {
1947 /* We need left neighbor to balance S[n_h]. */
1948 PROC_INFO_INC(p_s_sb, need_l_neighbor[n_h]);
1951 RFALSE(p_s_bh == p_s_tb->FL[n_h] &&
1957 p_s_tb->FL[n_h]) ? p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->
1958 FL[n_h]);
1959 n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position);
1965 PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
1969 RFALSE(!B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
1970 n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) ||
1971 B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) !=
1974 RFALSE(!n_h &&
1980 decrement_bcount(p_s_tb->L[n_h]);
1981 p_s_tb->L[n_h] = p_s_bh;
1984 if (p_s_tb->rnum[n_h]) { /* We need right neighbor to balance S[n_path_offset]. */
1985 PROC_INFO_INC(p_s_sb, need_r_neighbor[n_h]);
1988 RFALSE(p_s_bh == p_s_tb->FR[n_h] &&
1995 (p_s_bh == p_s_tb->FR[n_h]) ? p_s_tb->rkey[n_h] + 1 : 0;
1996 n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position);
2002 PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
2005 decrement_bcount(p_s_tb->R[n_h]);
2006 p_s_tb->R[n_h] = p_s_bh;
2008 RFALSE(!n_h
2322 int n_ret_value, n_h, n_item_num = PATH_LAST_POSITION(p_s_tb->tb_path);
2397 /* Starting from the leaf level; for all levels n_h of the tree. */
2398 for (n_h = 0; n_h < MAX_HEIGHT && p_s_tb->insert_size[n_h]; n_h++) {
2399 if ((n_ret_value = get_direct_parent(p_s_tb, n_h)) != CARRY_ON) {
2404 check_balance(n_op_mode, p_s_tb, n_h, n_item_num,
2410 get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2413 if (n_h != MAX_HEIGHT - 1)
2414 p_s_tb->insert_size[n_h + 1] = 0;
2421 if ((n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2425 if ((n_ret_value = get_empty_nodes(p_s_tb, n_h)) != CARRY_ON) {
2430 if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h)) {
2434 RFALSE(p_s_tb->blknum[n_h] != 1,
2437 if (n_h < MAX_HEIGHT - 1)
2438 p_s_tb->insert_size[n_h + 1] = 0;
2439 } else if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1)) {
2440 if (p_s_tb->blknum[n_h] > 1) {
2441 /* The tree needs to be grown, so this node S[n_h]
2443 and a new node (S[n_h+1]) will be created to
2446 RFALSE(n_h == MAX_HEIGHT - 1,
2449 p_s_tb->insert_size[n_h + 1] =
2451 KEY_SIZE) * (p_s_tb->blknum[n_h] - 1) +
2453 } else if (n_h < MAX_HEIGHT - 1)
2454 p_s_tb->insert_size[n_h + 1] = 0;
2456 p_s_tb->insert_size[n_h + 1] =
2457 (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1);