Lines Matching refs:h
77 static void create_virtual_node(struct tree_balance *tb, int h) in create_virtual_node() argument
84 Sh = PATH_H_PBUFFER(tb->tb_path, h); in create_virtual_node()
88 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h]; in create_virtual_node()
91 if (h) { in create_virtual_node()
202 static void check_left(struct tree_balance *tb, int h, int cur_free) in check_left() argument
212 if (h > 0) { in check_left()
213 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); in check_left()
221 tb->lnum[h] = 0; in check_left()
282 static void check_right(struct tree_balance *tb, int h, int cur_free) in check_right() argument
292 if (h > 0) { in check_right()
293 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); in check_right()
301 tb->rnum[h] = 0; in check_right()
318 tb->rnum[h] = vn->vn_nr_item; in check_right()
365 static int get_num_ver(int mode, struct tree_balance *tb, int h, in get_num_ver() argument
395 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE), in get_num_ver()
398 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h)); in get_num_ver()
406 if (h > 0) { in get_num_ver()
587 static void set_parameters(struct tree_balance *tb, int h, int lnum, in set_parameters() argument
591 tb->lnum[h] = lnum; in set_parameters()
592 tb->rnum[h] = rnum; in set_parameters()
593 tb->blknum[h] = blk_num; in set_parameters()
595 if (h == 0) { /* only for leaf level */ in set_parameters()
605 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum); in set_parameters()
606 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum); in set_parameters()
608 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb); in set_parameters()
609 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb); in set_parameters()
714 if (h)\
721 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
726 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
729 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
734 if (h)\
740 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
745 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
748 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
855 static int get_lfree(struct tree_balance *tb, int h) in get_lfree() argument
860 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || in get_lfree()
861 (l = tb->FL[h]) == NULL) in get_lfree()
865 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1; in get_lfree()
877 static int get_rfree(struct tree_balance *tb, int h) in get_rfree() argument
882 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || in get_rfree()
883 (r = tb->FR[h]) == NULL) in get_rfree()
887 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1; in get_rfree()
1164 struct tree_balance *tb, int h) in can_node_be_removed() argument
1166 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h); in can_node_be_removed()
1167 int levbytes = tb->insert_size[h]; in can_node_be_removed()
1172 if (tb->CFR[h]) in can_node_be_removed()
1173 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]); in can_node_be_removed()
1178 ((!h in can_node_be_removed()
1181 ((!h && r_key in can_node_be_removed()
1183 + ((h) ? KEY_SIZE : 0)) { in can_node_be_removed()
1186 if (!h) in can_node_be_removed()
1190 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in can_node_be_removed()
1194 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]); in can_node_be_removed()
1212 static int ip_check_balance(struct tree_balance *tb, int h) in ip_check_balance() argument
1252 Sh = PATH_H_PBUFFER(tb->tb_path, h); in ip_check_balance()
1253 levbytes = tb->insert_size[h]; in ip_check_balance()
1257 if (!h) in ip_check_balance()
1260 switch (n_ret_value = get_empty_nodes(tb, h)) { in ip_check_balance()
1262 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in ip_check_balance()
1274 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */ in ip_check_balance()
1280 rfree = get_rfree(tb, h); in ip_check_balance()
1281 lfree = get_lfree(tb, h); in ip_check_balance()
1283 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) == in ip_check_balance()
1288 create_virtual_node(tb, h); in ip_check_balance()
1295 check_left(tb, h, lfree); in ip_check_balance()
1302 check_right(tb, h, rfree); in ip_check_balance()
1306 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) { in ip_check_balance()
1316 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + in ip_check_balance()
1318 tb->rnum[h]); in ip_check_balance()
1319 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, in ip_check_balance()
1325 RFALSE(h && in ip_check_balance()
1326 (tb->lnum[h] >= vn->vn_nr_item + 1 || in ip_check_balance()
1327 tb->rnum[h] >= vn->vn_nr_item + 1), in ip_check_balance()
1329 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) || in ip_check_balance()
1330 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))), in ip_check_balance()
1335 if (!h && is_leaf_removable(tb)) in ip_check_balance()
1343 if (!h) in ip_check_balance()
1345 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in ip_check_balance()
1372 lpar = tb->lnum[h]; in ip_check_balance()
1373 rpar = tb->rnum[h]; in ip_check_balance()
1380 nver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1381 0, -1, h ? vn->vn_nr_item : 0, -1, in ip_check_balance()
1384 if (!h) { in ip_check_balance()
1388 nver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1402 lnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1403 lpar - ((h || tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1404 -1, h ? vn->vn_nr_item : 0, -1, in ip_check_balance()
1406 if (!h) { in ip_check_balance()
1409 lnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1425 rnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1427 h ? (vn->vn_nr_item - rpar) : (rpar - in ip_check_balance()
1433 if (!h) { in ip_check_balance()
1436 rnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1453 lrnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1454 lpar - ((h || tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1456 h ? (vn->vn_nr_item - rpar) : (rpar - in ip_check_balance()
1462 if (!h) { in ip_check_balance()
1465 lrnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1484 RFALSE(h && in ip_check_balance()
1485 (tb->lnum[h] != 1 || in ip_check_balance()
1486 tb->rnum[h] != 1 || in ip_check_balance()
1488 || h != 1), "vs-8230: bad h"); in ip_check_balance()
1490 set_parameters(tb, h, tb->lnum[h], tb->rnum[h], in ip_check_balance()
1494 set_parameters(tb, h, in ip_check_balance()
1495 tb->lnum[h] - in ip_check_balance()
1497 tb->rnum[h] - in ip_check_balance()
1506 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1, in ip_check_balance()
1528 if (is_left_neighbor_in_cache(tb, h)) { in ip_check_balance()
1555 static int dc_check_balance_internal(struct tree_balance *tb, int h) in dc_check_balance_internal() argument
1565 Sh = PATH_H_PBUFFER(tb->tb_path, h); in dc_check_balance_internal()
1566 Fh = PATH_H_PPARENT(tb->tb_path, h); in dc_check_balance_internal()
1573 create_virtual_node(tb, h); in dc_check_balance_internal()
1577 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1583 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1); in dc_check_balance_internal()
1587 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) in dc_check_balance_internal()
1591 rfree = get_rfree(tb, h); in dc_check_balance_internal()
1592 lfree = get_lfree(tb, h); in dc_check_balance_internal()
1595 check_left(tb, h, lfree); in dc_check_balance_internal()
1596 check_right(tb, h, rfree); in dc_check_balance_internal()
1602 if (tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1610 h)) == in dc_check_balance_internal()
1611 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; in dc_check_balance_internal()
1612 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / in dc_check_balance_internal()
1614 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, in dc_check_balance_internal()
1619 if (tb->rnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1627 h)) == in dc_check_balance_internal()
1629 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / in dc_check_balance_internal()
1631 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, in dc_check_balance_internal()
1637 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1642 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - in dc_check_balance_internal()
1643 tb->rnum[h] + vn->vn_nr_item + 1) / 2 - in dc_check_balance_internal()
1644 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]); in dc_check_balance_internal()
1645 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, in dc_check_balance_internal()
1651 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1657 if (tb->lnum[h] >= vn->vn_nr_item + 1) in dc_check_balance_internal()
1658 if (is_left_neighbor_in_cache(tb, h) in dc_check_balance_internal()
1659 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) { in dc_check_balance_internal()
1666 h)) == in dc_check_balance_internal()
1667 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; in dc_check_balance_internal()
1668 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE + in dc_check_balance_internal()
1670 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1); in dc_check_balance_internal()
1675 if (tb->rnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1682 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1); in dc_check_balance_internal()
1683 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE + in dc_check_balance_internal()
1685 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1); in dc_check_balance_internal()
1690 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1694 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + in dc_check_balance_internal()
1696 tb->rnum[h]); in dc_check_balance_internal()
1697 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, in dc_check_balance_internal()
1703 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root"); in dc_check_balance_internal()
1706 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) { in dc_check_balance_internal()
1710 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + in dc_check_balance_internal()
1712 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1716 set_parameters(tb, h, 0, in dc_check_balance_internal()
1717 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item + in dc_check_balance_internal()
1735 static int dc_check_balance_leaf(struct tree_balance *tb, int h) in dc_check_balance_leaf() argument
1754 levbytes = tb->insert_size[h]; in dc_check_balance_leaf()
1763 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_leaf()
1767 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) in dc_check_balance_leaf()
1771 rfree = get_rfree(tb, h); in dc_check_balance_leaf()
1772 lfree = get_lfree(tb, h); in dc_check_balance_leaf()
1774 create_virtual_node(tb, h); in dc_check_balance_leaf()
1784 check_left(tb, h, lfree); in dc_check_balance_leaf()
1785 check_right(tb, h, rfree); in dc_check_balance_leaf()
1789 …if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_… in dc_check_balance_leaf()
1790 !tb->FR[h]) { in dc_check_balance_leaf()
1792 RFALSE(!tb->FL[h], in dc_check_balance_leaf()
1796 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1); in dc_check_balance_leaf()
1802 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1); in dc_check_balance_leaf()
1812 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_leaf()
1829 static int dc_check_balance(struct tree_balance *tb, int h) in dc_check_balance() argument
1831 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)), in dc_check_balance()
1834 if (h) in dc_check_balance()
1835 return dc_check_balance_internal(tb, h); in dc_check_balance()
1837 return dc_check_balance_leaf(tb, h); in dc_check_balance()
1860 int h, in check_balance() argument
1878 if (tb->insert_size[h] > 0) in check_balance()
1880 return ip_check_balance(tb, h); in check_balance()
1883 return dc_check_balance(tb, h); in check_balance()