Lines Matching refs:h
78 static void create_virtual_node(struct tree_balance *tb, int h) in create_virtual_node() argument
85 Sh = PATH_H_PBUFFER(tb->tb_path, h); in create_virtual_node()
89 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h]; in create_virtual_node()
92 if (h) { in create_virtual_node()
203 static void check_left(struct tree_balance *tb, int h, int cur_free) in check_left() argument
213 if (h > 0) { in check_left()
214 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); in check_left()
222 tb->lnum[h] = 0; in check_left()
283 static void check_right(struct tree_balance *tb, int h, int cur_free) in check_right() argument
293 if (h > 0) { in check_right()
294 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); in check_right()
302 tb->rnum[h] = 0; in check_right()
319 tb->rnum[h] = vn->vn_nr_item; in check_right()
366 static int get_num_ver(int mode, struct tree_balance *tb, int h, in get_num_ver() argument
396 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE), in get_num_ver()
399 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h)); in get_num_ver()
407 if (h > 0) { in get_num_ver()
585 static void set_parameters(struct tree_balance *tb, int h, int lnum, in set_parameters() argument
589 tb->lnum[h] = lnum; in set_parameters()
590 tb->rnum[h] = rnum; in set_parameters()
591 tb->blknum[h] = blk_num; in set_parameters()
593 if (h == 0) { /* only for leaf level */ in set_parameters()
603 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum); in set_parameters()
604 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum); in set_parameters()
606 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb); in set_parameters()
607 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb); in set_parameters()
712 if (h)\
719 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
724 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
727 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
732 if (h)\
738 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
743 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
746 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
779 static int get_empty_nodes(struct tree_balance *tb, int h) in get_empty_nodes() argument
782 *Sh = PATH_H_PBUFFER(tb->tb_path, h); in get_empty_nodes()
805 counter < h; counter++) in get_empty_nodes()
812 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1; in get_empty_nodes()
854 static int get_lfree(struct tree_balance *tb, int h) in get_lfree() argument
859 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || in get_lfree()
860 (l = tb->FL[h]) == NULL) in get_lfree()
864 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1; in get_lfree()
876 static int get_rfree(struct tree_balance *tb, int h) in get_rfree() argument
881 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || in get_rfree()
882 (r = tb->FR[h]) == NULL) in get_rfree()
886 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1; in get_rfree()
897 static int is_left_neighbor_in_cache(struct tree_balance *tb, int h) in is_left_neighbor_in_cache() argument
905 if (!tb->FL[h]) in is_left_neighbor_in_cache()
909 father = PATH_H_PBUFFER(tb->tb_path, h + 1); in is_left_neighbor_in_cache()
913 !B_IS_IN_TREE(tb->FL[h]) || in is_left_neighbor_in_cache()
915 !buffer_uptodate(tb->FL[h]), in is_left_neighbor_in_cache()
917 father, tb->FL[h]); in is_left_neighbor_in_cache()
920 left_neighbor_position = (father == tb->FL[h]) ? in is_left_neighbor_in_cache()
921 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]); in is_left_neighbor_in_cache()
924 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position); in is_left_neighbor_in_cache()
956 int h, in get_far_parent() argument
967 path_offset = PATH_H_PATH_OFFSET(path, h); in get_far_parent()
1041 LEFT_PARENTS) ? (tb->lkey[h - 1] = in get_far_parent()
1043 1) : (tb->rkey[h - in get_far_parent()
1052 h + 1) == IO_ERROR) in get_far_parent()
1064 RFALSE(B_LEVEL(*pfather) != h + 1, in get_far_parent()
1081 static int get_parents(struct tree_balance *tb, int h) in get_parents() argument
1086 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h); in get_parents()
1093 brelse(tb->FL[h]); in get_parents()
1094 brelse(tb->CFL[h]); in get_parents()
1095 brelse(tb->FR[h]); in get_parents()
1096 brelse(tb->CFR[h]); in get_parents()
1097 tb->FL[h] = NULL; in get_parents()
1098 tb->CFL[h] = NULL; in get_parents()
1099 tb->FR[h] = NULL; in get_parents()
1100 tb->CFR[h] = NULL; in get_parents()
1112 tb->lkey[h] = position - 1; in get_parents()
1118 if ((ret = get_far_parent(tb, h + 1, &curf, in get_parents()
1124 brelse(tb->FL[h]); in get_parents()
1125 tb->FL[h] = curf; /* New initialization of FL[h]. */ in get_parents()
1126 brelse(tb->CFL[h]); in get_parents()
1127 tb->CFL[h] = curcf; /* New initialization of CFL[h]. */ in get_parents()
1136 if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) { in get_parents()
1141 get_far_parent(tb, h + 1, &curf, &curcf, in get_parents()
1150 tb->rkey[h] = position; in get_parents()
1153 brelse(tb->FR[h]); in get_parents()
1155 tb->FR[h] = curf; in get_parents()
1157 brelse(tb->CFR[h]); in get_parents()
1159 tb->CFR[h] = curcf; in get_parents()
1171 struct tree_balance *tb, int h) in can_node_be_removed() argument
1173 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h); in can_node_be_removed()
1174 int levbytes = tb->insert_size[h]; in can_node_be_removed()
1179 if (tb->CFR[h]) in can_node_be_removed()
1180 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]); in can_node_be_removed()
1185 ((!h in can_node_be_removed()
1188 ((!h && r_key in can_node_be_removed()
1190 + ((h) ? KEY_SIZE : 0)) { in can_node_be_removed()
1193 if (!h) in can_node_be_removed()
1197 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in can_node_be_removed()
1201 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]); in can_node_be_removed()
1219 static int ip_check_balance(struct tree_balance *tb, int h) in ip_check_balance() argument
1259 Sh = PATH_H_PBUFFER(tb->tb_path, h); in ip_check_balance()
1260 levbytes = tb->insert_size[h]; in ip_check_balance()
1264 if (!h) in ip_check_balance()
1267 switch (ret = get_empty_nodes(tb, h)) { in ip_check_balance()
1269 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in ip_check_balance()
1281 if ((ret = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */ in ip_check_balance()
1287 rfree = get_rfree(tb, h); in ip_check_balance()
1288 lfree = get_lfree(tb, h); in ip_check_balance()
1290 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) == in ip_check_balance()
1295 create_virtual_node(tb, h); in ip_check_balance()
1302 check_left(tb, h, lfree); in ip_check_balance()
1309 check_right(tb, h, rfree); in ip_check_balance()
1313 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) { in ip_check_balance()
1323 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + in ip_check_balance()
1325 tb->rnum[h]); in ip_check_balance()
1326 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, in ip_check_balance()
1332 RFALSE(h && in ip_check_balance()
1333 (tb->lnum[h] >= vn->vn_nr_item + 1 || in ip_check_balance()
1334 tb->rnum[h] >= vn->vn_nr_item + 1), in ip_check_balance()
1336 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) || in ip_check_balance()
1337 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))), in ip_check_balance()
1342 if (!h && is_leaf_removable(tb)) in ip_check_balance()
1350 if (!h) in ip_check_balance()
1352 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in ip_check_balance()
1379 lpar = tb->lnum[h]; in ip_check_balance()
1380 rpar = tb->rnum[h]; in ip_check_balance()
1387 nver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1388 0, -1, h ? vn->vn_nr_item : 0, -1, in ip_check_balance()
1391 if (!h) { in ip_check_balance()
1395 nver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1409 lnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1410 lpar - ((h || tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1411 -1, h ? vn->vn_nr_item : 0, -1, in ip_check_balance()
1413 if (!h) { in ip_check_balance()
1416 lnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1432 rnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1434 h ? (vn->vn_nr_item - rpar) : (rpar - in ip_check_balance()
1440 if (!h) { in ip_check_balance()
1443 rnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1460 lrnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1461 lpar - ((h || tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1463 h ? (vn->vn_nr_item - rpar) : (rpar - in ip_check_balance()
1469 if (!h) { in ip_check_balance()
1472 lrnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1491 RFALSE(h && in ip_check_balance()
1492 (tb->lnum[h] != 1 || in ip_check_balance()
1493 tb->rnum[h] != 1 || in ip_check_balance()
1495 || h != 1), "vs-8230: bad h"); in ip_check_balance()
1497 set_parameters(tb, h, tb->lnum[h], tb->rnum[h], in ip_check_balance()
1501 set_parameters(tb, h, in ip_check_balance()
1502 tb->lnum[h] - in ip_check_balance()
1504 tb->rnum[h] - in ip_check_balance()
1513 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1, in ip_check_balance()
1535 if (is_left_neighbor_in_cache(tb, h)) { in ip_check_balance()
1562 static int dc_check_balance_internal(struct tree_balance *tb, int h) in dc_check_balance_internal() argument
1572 Sh = PATH_H_PBUFFER(tb->tb_path, h); in dc_check_balance_internal()
1573 Fh = PATH_H_PPARENT(tb->tb_path, h); in dc_check_balance_internal()
1580 create_virtual_node(tb, h); in dc_check_balance_internal()
1584 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1590 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1); in dc_check_balance_internal()
1594 if ((ret = get_parents(tb, h)) != CARRY_ON) in dc_check_balance_internal()
1598 rfree = get_rfree(tb, h); in dc_check_balance_internal()
1599 lfree = get_lfree(tb, h); in dc_check_balance_internal()
1602 check_left(tb, h, lfree); in dc_check_balance_internal()
1603 check_right(tb, h, rfree); in dc_check_balance_internal()
1609 if (tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1617 h)) == in dc_check_balance_internal()
1618 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; in dc_check_balance_internal()
1619 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / in dc_check_balance_internal()
1621 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, in dc_check_balance_internal()
1626 if (tb->rnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1634 h)) == in dc_check_balance_internal()
1636 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / in dc_check_balance_internal()
1638 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, in dc_check_balance_internal()
1644 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1649 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - in dc_check_balance_internal()
1650 tb->rnum[h] + vn->vn_nr_item + 1) / 2 - in dc_check_balance_internal()
1651 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]); in dc_check_balance_internal()
1652 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, in dc_check_balance_internal()
1658 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1664 if (tb->lnum[h] >= vn->vn_nr_item + 1) in dc_check_balance_internal()
1665 if (is_left_neighbor_in_cache(tb, h) in dc_check_balance_internal()
1666 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) { in dc_check_balance_internal()
1673 h)) == in dc_check_balance_internal()
1674 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; in dc_check_balance_internal()
1675 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE + in dc_check_balance_internal()
1677 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1); in dc_check_balance_internal()
1682 if (tb->rnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1689 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1); in dc_check_balance_internal()
1690 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE + in dc_check_balance_internal()
1692 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1); in dc_check_balance_internal()
1697 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1701 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + in dc_check_balance_internal()
1703 tb->rnum[h]); in dc_check_balance_internal()
1704 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, in dc_check_balance_internal()
1710 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root"); in dc_check_balance_internal()
1713 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) { in dc_check_balance_internal()
1717 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + in dc_check_balance_internal()
1719 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1723 set_parameters(tb, h, 0, in dc_check_balance_internal()
1724 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item + in dc_check_balance_internal()
1742 static int dc_check_balance_leaf(struct tree_balance *tb, int h) in dc_check_balance_leaf() argument
1761 levbytes = tb->insert_size[h]; in dc_check_balance_leaf()
1770 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_leaf()
1774 if ((ret = get_parents(tb, h)) != CARRY_ON) in dc_check_balance_leaf()
1778 rfree = get_rfree(tb, h); in dc_check_balance_leaf()
1779 lfree = get_lfree(tb, h); in dc_check_balance_leaf()
1781 create_virtual_node(tb, h); in dc_check_balance_leaf()
1791 check_left(tb, h, lfree); in dc_check_balance_leaf()
1792 check_right(tb, h, rfree); in dc_check_balance_leaf()
1796 …if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_… in dc_check_balance_leaf()
1797 !tb->FR[h]) { in dc_check_balance_leaf()
1799 RFALSE(!tb->FL[h], in dc_check_balance_leaf()
1803 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1); in dc_check_balance_leaf()
1809 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1); in dc_check_balance_leaf()
1819 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_leaf()
1836 static int dc_check_balance(struct tree_balance *tb, int h) in dc_check_balance() argument
1838 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)), in dc_check_balance()
1841 if (h) in dc_check_balance()
1842 return dc_check_balance_internal(tb, h); in dc_check_balance()
1844 return dc_check_balance_leaf(tb, h); in dc_check_balance()
1867 int h, in check_balance() argument
1885 if (tb->insert_size[h] > 0) in check_balance()
1887 return ip_check_balance(tb, h); in check_balance()
1890 return dc_check_balance(tb, h); in check_balance()
1894 static int get_direct_parent(struct tree_balance *tb, int h) in get_direct_parent() argument
1899 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h); in get_direct_parent()
1948 static int get_neighbors(struct tree_balance *tb, int h) in get_neighbors() argument
1951 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1); in get_neighbors()
1956 PROC_INFO_INC(sb, get_neighbors[h]); in get_neighbors()
1958 if (tb->lnum[h]) { in get_neighbors()
1960 PROC_INFO_INC(sb, need_l_neighbor[h]); in get_neighbors()
1963 RFALSE(bh == tb->FL[h] && in get_neighbors()
1969 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb-> in get_neighbors()
1970 FL[h]); in get_neighbors()
1971 son_number = B_N_CHILD_NUM(tb->FL[h], child_position); in get_neighbors()
1979 PROC_INFO_INC(sb, get_neighbors_restart[h]); in get_neighbors()
1983 RFALSE(!B_IS_IN_TREE(tb->FL[h]) || in get_neighbors()
1984 child_position > B_NR_ITEMS(tb->FL[h]) || in get_neighbors()
1985 B_N_CHILD_NUM(tb->FL[h], child_position) != in get_neighbors()
1988 RFALSE(!h && in get_neighbors()
1994 brelse(tb->L[h]); in get_neighbors()
1995 tb->L[h] = bh; in get_neighbors()
1999 if (tb->rnum[h]) { /* We need right neighbor to balance S[path_offset]. */ in get_neighbors()
2000 PROC_INFO_INC(sb, need_r_neighbor[h]); in get_neighbors()
2003 RFALSE(bh == tb->FR[h] && in get_neighbors()
2010 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0; in get_neighbors()
2011 son_number = B_N_CHILD_NUM(tb->FR[h], child_position); in get_neighbors()
2019 PROC_INFO_INC(sb, get_neighbors_restart[h]); in get_neighbors()
2022 brelse(tb->R[h]); in get_neighbors()
2023 tb->R[h] = bh; in get_neighbors()
2025 RFALSE(!h in get_neighbors()
2333 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path); in fix_nodes() local
2413 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) { in fix_nodes()
2414 ret = get_direct_parent(tb, h); in fix_nodes()
2418 ret = check_balance(op_mode, tb, h, item_num, in fix_nodes()
2423 ret = get_neighbors(tb, h); in fix_nodes()
2426 if (h != MAX_HEIGHT - 1) in fix_nodes()
2427 tb->insert_size[h + 1] = 0; in fix_nodes()
2434 ret = get_neighbors(tb, h); in fix_nodes()
2440 ret = get_empty_nodes(tb, h); in fix_nodes()
2444 if (!PATH_H_PBUFFER(tb->tb_path, h)) { in fix_nodes()
2448 RFALSE(tb->blknum[h] != 1, in fix_nodes()
2451 if (h < MAX_HEIGHT - 1) in fix_nodes()
2452 tb->insert_size[h + 1] = 0; in fix_nodes()
2453 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) { in fix_nodes()
2454 if (tb->blknum[h] > 1) { in fix_nodes()
2460 RFALSE(h == MAX_HEIGHT - 1, in fix_nodes()
2463 tb->insert_size[h + 1] = in fix_nodes()
2465 KEY_SIZE) * (tb->blknum[h] - 1) + in fix_nodes()
2467 } else if (h < MAX_HEIGHT - 1) in fix_nodes()
2468 tb->insert_size[h + 1] = 0; in fix_nodes()
2470 tb->insert_size[h + 1] = in fix_nodes()
2471 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1); in fix_nodes()