80 static void create_virtual_node (struct tree_balance * tb, int h)  in create_virtual_node()  argument
87     Sh = PATH_H_PBUFFER (tb->tb_path, h);  in create_virtual_node()
90     vn->vn_size = MAX_CHILD_SIZE (Sh) - B_FREE_SPACE (Sh) + tb->insert_size[h];  in create_virtual_node()
93     if (h) {  in create_virtual_node()
195 static void check_left (struct tree_balance * tb, int h, int cur_free)  in check_left()  argument
205     if (h > 0) {	  in check_left()
206 	tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);  in check_left()
214 	tb->lnum[h] = 0;  in check_left()
274 static void check_right (struct tree_balance * tb, int h, int cur_free)  in check_right()  argument
284     if (h > 0) {  in check_right()
285 	tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);  in check_right()
293 	tb->rnum[h] = 0;  in check_right()
308 	tb->rnum[h] = vn->vn_nr_item;  in check_right()
355 static int get_num_ver (int mode, struct tree_balance * tb, int h,  in get_num_ver()  argument
387     RFALSE( tb->insert_size[h] < 0  || (mode != M_INSERT && mode != M_PASTE),  in get_num_ver()
390     max_node_size = MAX_CHILD_SIZE (PATH_H_PBUFFER (tb->tb_path, h));  in get_num_ver()
398     if (h > 0) {  in get_num_ver()
557 static void set_parameters (struct tree_balance * tb, int h, int lnum,  in set_parameters()  argument
561   tb->lnum[h] = lnum;  in set_parameters()
562   tb->rnum[h] = rnum;  in set_parameters()
563   tb->blknum[h] = blk_num;  in set_parameters()
565   if (h == 0)  in set_parameters()
578   PROC_INFO_ADD( tb -> tb_sb, lnum[ h ], lnum );  in set_parameters()
579   PROC_INFO_ADD( tb -> tb_sb, rnum[ h ], rnum );  in set_parameters()
581   PROC_INFO_ADD( tb -> tb_sb, lbytes[ h ], lb );  in set_parameters()
582   PROC_INFO_ADD( tb -> tb_sb, rbytes[ h ], rb );  in set_parameters()
685 if (h)\
692 	      set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
697      set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
700      set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
706 if (h)\
712    set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
717      set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
720      set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
850 static int get_lfree (struct tree_balance * tb, int h)  in get_lfree()  argument
855     if ((f = PATH_H_PPARENT (tb->tb_path, h)) == 0 || (l = tb->FL[h]) == 0)  in get_lfree()
859 	order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) - 1;  in get_lfree()
872 static int get_rfree (struct tree_balance * tb, int h)  in get_rfree()  argument
877   if ((f = PATH_H_PPARENT (tb->tb_path, h)) == 0 || (r = tb->FR[h]) == 0)  in get_rfree()
881       order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) + 1;  in get_rfree()
1152 …nt can_node_be_removed (int mode, int lfree, int sfree, int rfree, struct tree_balance * tb, int h)  in can_node_be_removed()  argument
1154     struct buffer_head * Sh = PATH_H_PBUFFER (tb->tb_path, h);  in can_node_be_removed()
1155     int levbytes = tb->insert_size[h];  in can_node_be_removed()
1160     if ( tb->CFR[h] )  in can_node_be_removed()
1161 	r_key = B_N_PDELIM_KEY(tb->CFR[h],tb->rkey[h]);  in can_node_be_removed()
1166 	- (( ! h && op_is_left_mergeable (&(ih->ih_key), Sh->b_size) ) ? IH_SIZE : 0)  in can_node_be_removed()
1167 	- (( ! h && r_key && op_is_left_mergeable (r_key, Sh->b_size) ) ? IH_SIZE : 0)  in can_node_be_removed()
1168 	+ (( h ) ? KEY_SIZE : 0))  in can_node_be_removed()
1172 	    if ( ! h )  in can_node_be_removed()
1174 	    set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);  in can_node_be_removed()
1178     PROC_INFO_INC( tb -> tb_sb, can_node_be_removed[ h ] );  in can_node_be_removed()
1198 static int ip_check_balance (struct tree_balance * tb, int h)  in ip_check_balance()  argument
1238     Sh = PATH_H_PBUFFER (tb->tb_path, h);  in ip_check_balance()
1239     levbytes = tb->insert_size[h];  in ip_check_balance()
1243 	if ( ! h )  in ip_check_balance()
1245 	switch ( n_ret_value = get_empty_nodes (tb, h) )  {  in ip_check_balance()
1247 	    set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);  in ip_check_balance()
1258     if ( (n_ret_value = get_parents (tb, h)) != CARRY_ON ) /* get parents of S[h] neighbors. */  in ip_check_balance()
1264     rfree = get_rfree (tb, h);  in ip_check_balance()
1265     lfree = get_lfree (tb, h);  in ip_check_balance()
1267     if (can_node_be_removed (vn->vn_mode, lfree, sfree, rfree, tb, h) == NO_BALANCING_NEEDED)  in ip_check_balance()
1271     create_virtual_node (tb, h);  in ip_check_balance()
1278     check_left (tb, h, lfree);  in ip_check_balance()
1285     check_right (tb, h, rfree);  in ip_check_balance()
1290     if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {  in ip_check_balance()
1299 	to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 -   in ip_check_balance()
1300 	    (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);  in ip_check_balance()
1301 	set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);  in ip_check_balance()
1306     RFALSE( h &&   in ip_check_balance()
1307 	    ( tb->lnum[h] >= vn->vn_nr_item + 1 ||   in ip_check_balance()
1308 	      tb->rnum[h] >= vn->vn_nr_item + 1),  in ip_check_balance()
1310     RFALSE( ! h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||  in ip_check_balance()
1311 		    (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1)) ),  in ip_check_balance()
1316     if (!h && is_leaf_removable (tb))  in ip_check_balance()
1325 	if ( ! h )  in ip_check_balance()
1327 	set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);  in ip_check_balance()
1356 	lpar = tb->lnum[h];  in ip_check_balance()
1357 	rpar = tb->rnum[h];  in ip_check_balance()
1365 	nver = get_num_ver (vn->vn_mode, tb, h,  in ip_check_balance()
1366 			    0, -1, h?vn->vn_nr_item:0, -1,   in ip_check_balance()
1369 	if (!h)  in ip_check_balance()
1374 	    nver1 = get_num_ver (vn->vn_mode, tb, h,   in ip_check_balance()
1389 	lnver = get_num_ver (vn->vn_mode, tb, h,   in ip_check_balance()
1390 			     lpar - (( h || tb->lbytes == -1 ) ? 0 : 1), -1, h ? vn->vn_nr_item:0, -1,  in ip_check_balance()
1392 	if (!h)  in ip_check_balance()
1396 	    lnver1 = get_num_ver (vn->vn_mode, tb, h,   in ip_check_balance()
1411 	rnver = get_num_ver (vn->vn_mode, tb, h,   in ip_check_balance()
1412 			     0, -1, h ? (vn->vn_nr_item-rpar) : (rpar - (( tb->rbytes != -1 ) ? 1 : 0)), -1,   in ip_check_balance()
1414 	if (!h)  in ip_check_balance()
1418 	    rnver1 = get_num_ver (vn->vn_mode, tb, h,   in ip_check_balance()
1433 	lrnver = get_num_ver (vn->vn_mode, tb, h,   in ip_check_balance()
1434 …lpar - ((h || tb->lbytes == -1) ? 0 : 1), -1, h ? (vn->vn_nr_item-rpar):(rpar - ((tb->rbytes != -1…  in ip_check_balance()
1436 	if (!h)  in ip_check_balance()
1440 	    lrnver1 = get_num_ver (vn->vn_mode, tb, h,   in ip_check_balance()
1457 	    RFALSE( h &&   in ip_check_balance()
1458 		    (tb->lnum[h] != 1 ||   in ip_check_balance()
1459 		     tb->rnum[h] != 1 ||   in ip_check_balance()
1460 		     lrnver != 1 || rnver != 2 || lnver != 2 || h != 1),  in ip_check_balance()
1463 		set_parameters (tb, h, tb->lnum[h], tb->rnum[h], lrnver, snum012 + lrset,  in ip_check_balance()
1466 		set_parameters (tb, h, tb->lnum[h] - ((tb->lbytes == -1) ? 0 : 1),   in ip_check_balance()
1467 				tb->rnum[h] - ((tb->rbytes == -1) ? 0 : 1), lrnver, snum012 + lrset, -1, -1);  in ip_check_balance()
1475 	    set_parameters (tb, h, 0, 0, nver, snum012 + nset, -1, -1);  in ip_check_balance()
1500 	if (is_left_neighbor_in_cache (tb,h))  in ip_check_balance()
1529 static int dc_check_balance_internal (struct tree_balance * tb, int h)  in dc_check_balance_internal()  argument
1540   Sh = PATH_H_PBUFFER (tb->tb_path, h);   in dc_check_balance_internal()
1541   Fh = PATH_H_PPARENT (tb->tb_path, h);   in dc_check_balance_internal()
1548   create_virtual_node (tb, h);  in dc_check_balance_internal()
1554 	  set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);  in dc_check_balance_internal()
1560       set_parameters (tb, h, 0, 0, 0, NULL, -1, -1);  in dc_check_balance_internal()
1564   if ( (n_ret_value = get_parents(tb,h)) != CARRY_ON )  in dc_check_balance_internal()
1569   rfree = get_rfree (tb, h);  in dc_check_balance_internal()
1570   lfree = get_lfree (tb, h);  in dc_check_balance_internal()
1573   check_left (tb, h, lfree);  in dc_check_balance_internal()
1574   check_right (tb, h, rfree);  in dc_check_balance_internal()
1583 	  if ( tb->lnum[h] >= vn->vn_nr_item + 1 )  in dc_check_balance_internal()
1589 	      order_L = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;  in dc_check_balance_internal()
1590 	      n = dc_size(B_N_CHILD(tb->FL[h],order_L)) / (DC_SIZE + KEY_SIZE);  in dc_check_balance_internal()
1591 	      set_parameters (tb, h, -n-1, 0, 0, NULL, -1, -1);  in dc_check_balance_internal()
1595 	  if ( tb->rnum[h] >= vn->vn_nr_item + 1 )  in dc_check_balance_internal()
1601 	      order_R = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==B_NR_ITEMS(Fh)) ? 0 : n + 1;  in dc_check_balance_internal()
1602 	      n = dc_size(B_N_CHILD(tb->FR[h],order_R)) / (DC_SIZE + KEY_SIZE);  in dc_check_balance_internal()
1603 	      set_parameters (tb, h, 0, -n-1, 0, NULL, -1, -1);  in dc_check_balance_internal()
1608       if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)  in dc_check_balance_internal()
1613 	  to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 -   in dc_check_balance_internal()
1614 	    (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);  in dc_check_balance_internal()
1615 	  set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);  in dc_check_balance_internal()
1620       set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);  in dc_check_balance_internal()
1626   if (tb->lnum[h] >= vn->vn_nr_item + 1)  in dc_check_balance_internal()
1627     if (is_left_neighbor_in_cache (tb,h) || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h])  in dc_check_balance_internal()
1632 	order_L = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;  in dc_check_balance_internal()
1633 	n = dc_size(B_N_CHILD(tb->FL[h],order_L)) / (DC_SIZE + KEY_SIZE);  in dc_check_balance_internal()
1634 	set_parameters (tb, h, -n-1, 0, 0, NULL, -1, -1);  in dc_check_balance_internal()
1639   if (tb->rnum[h] >= vn->vn_nr_item + 1)  in dc_check_balance_internal()
1644       order_R = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==B_NR_ITEMS(Fh)) ? 0 : (n + 1);  in dc_check_balance_internal()
1645       n = dc_size(B_N_CHILD(tb->FR[h],order_R)) / (DC_SIZE + KEY_SIZE);  in dc_check_balance_internal()
1646       set_parameters (tb, h, 0, -n-1, 0, NULL, -1, -1);  in dc_check_balance_internal()
1651   if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)  in dc_check_balance_internal()
1655       to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 -   in dc_check_balance_internal()
1656 	(MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);  in dc_check_balance_internal()
1657       set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);  in dc_check_balance_internal()
1662   RFALSE( !tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");  in dc_check_balance_internal()
1665   if (is_left_neighbor_in_cache (tb,h) || !tb->FR[h])  in dc_check_balance_internal()
1669       from_l = (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + 1) / 2 -  (vn->vn_nr_item + 1);  in dc_check_balance_internal()
1670       set_parameters (tb, h, -from_l, 0, 1, NULL, -1, -1);  in dc_check_balance_internal()
1674 …set_parameters (tb, h, 0, -((MAX_NR_KEY(Sh)+1-tb->rnum[h]+vn->vn_nr_item+1)/2-(vn->vn_nr_item+1)),…  in dc_check_balance_internal()
1693 static int dc_check_balance_leaf (struct tree_balance * tb, int h)  in dc_check_balance_leaf()  argument
1713   levbytes = tb->insert_size[h];  in dc_check_balance_leaf()
1723       set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);  in dc_check_balance_leaf()
1727   if ( (n_ret_value = get_parents(tb,h)) != CARRY_ON )  in dc_check_balance_leaf()
1731   rfree = get_rfree (tb, h);  in dc_check_balance_leaf()
1732   lfree = get_lfree (tb, h);		  in dc_check_balance_leaf()
1734   create_virtual_node (tb, h);  in dc_check_balance_leaf()
1744   check_left (tb, h, lfree);  in dc_check_balance_leaf()
1745   check_right (tb, h, rfree);     in dc_check_balance_leaf()
1749     if (is_left_neighbor_in_cache (tb,h) ||  in dc_check_balance_leaf()
1751 	!tb->FR[h]) {  in dc_check_balance_leaf()
1753       RFALSE( !tb->FL[h], "vs-8245: dc_check_balance_leaf: FL[h] must exist");  in dc_check_balance_leaf()
1756       set_parameters (tb, h, -1, 0, 0, NULL, -1, -1);  in dc_check_balance_leaf()
1762     set_parameters (tb, h, 0, -1, 0, NULL, -1, -1);  in dc_check_balance_leaf()
1772   set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);  in dc_check_balance_leaf()
1791 static int dc_check_balance (struct tree_balance * tb, int h)  in dc_check_balance()  argument
1793  RFALSE( ! (PATH_H_PBUFFER (tb->tb_path, h)), "vs-8250: S is not initialized");  in dc_check_balance()
1795  if ( h )  in dc_check_balance()
1796    return dc_check_balance_internal (tb, h);  in dc_check_balance()
1798    return dc_check_balance_leaf (tb, h);  in dc_check_balance()
1823 			  int h,   in check_balance()  argument
1843  if ( tb->insert_size[h] > 0 )  in check_balance()
1845    return ip_check_balance (tb, h);  in check_balance()
1848  return dc_check_balance (tb, h);  in check_balance()