Lines Matching refs:h
26 int h, in internal_define_dest_src_infos() argument
37 src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h); in internal_define_dest_src_infos()
38 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h); in internal_define_dest_src_infos()
39 src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1); in internal_define_dest_src_infos()
41 dest_bi->bi_bh = tb->L[h]; in internal_define_dest_src_infos()
42 dest_bi->bi_parent = tb->FL[h]; in internal_define_dest_src_infos()
43 dest_bi->bi_position = get_left_neighbor_position(tb, h); in internal_define_dest_src_infos()
44 *d_key = tb->lkey[h]; in internal_define_dest_src_infos()
45 *cf = tb->CFL[h]; in internal_define_dest_src_infos()
49 src_bi->bi_bh = tb->L[h]; in internal_define_dest_src_infos()
50 src_bi->bi_parent = tb->FL[h]; in internal_define_dest_src_infos()
51 src_bi->bi_position = get_left_neighbor_position(tb, h); in internal_define_dest_src_infos()
53 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h); in internal_define_dest_src_infos()
54 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h); in internal_define_dest_src_infos()
55 …dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1); /* dest position is analog of dest->b_… in internal_define_dest_src_infos()
56 *d_key = tb->lkey[h]; in internal_define_dest_src_infos()
57 *cf = tb->CFL[h]; in internal_define_dest_src_infos()
62 src_bi->bi_bh = tb->R[h]; in internal_define_dest_src_infos()
63 src_bi->bi_parent = tb->FR[h]; in internal_define_dest_src_infos()
64 src_bi->bi_position = get_right_neighbor_position(tb, h); in internal_define_dest_src_infos()
66 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h); in internal_define_dest_src_infos()
67 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h); in internal_define_dest_src_infos()
68 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1); in internal_define_dest_src_infos()
69 *d_key = tb->rkey[h]; in internal_define_dest_src_infos()
70 *cf = tb->CFR[h]; in internal_define_dest_src_infos()
75 src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h); in internal_define_dest_src_infos()
76 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h); in internal_define_dest_src_infos()
77 src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1); in internal_define_dest_src_infos()
79 dest_bi->bi_bh = tb->R[h]; in internal_define_dest_src_infos()
80 dest_bi->bi_parent = tb->FR[h]; in internal_define_dest_src_infos()
81 dest_bi->bi_position = get_right_neighbor_position(tb, h); in internal_define_dest_src_infos()
82 *d_key = tb->rkey[h]; in internal_define_dest_src_infos()
83 *cf = tb->CFR[h]; in internal_define_dest_src_infos()
88 dest_bi->bi_bh = tb->L[h]; in internal_define_dest_src_infos()
89 dest_bi->bi_parent = tb->FL[h]; in internal_define_dest_src_infos()
90 dest_bi->bi_position = get_left_neighbor_position(tb, h); in internal_define_dest_src_infos()
95 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h); in internal_define_dest_src_infos()
96 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h); in internal_define_dest_src_infos()
97 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1); in internal_define_dest_src_infos()
102 dest_bi->bi_bh = tb->R[h]; in internal_define_dest_src_infos()
103 dest_bi->bi_parent = tb->FR[h]; in internal_define_dest_src_infos()
104 dest_bi->bi_position = get_right_neighbor_position(tb, h); in internal_define_dest_src_infos()
464 int h, int pointer_amount) in internal_shift_left() argument
470 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi, in internal_shift_left()
501 int h, int pointer_amount) in internal_shift1_left() argument
507 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, in internal_shift1_left()
528 int h, int pointer_amount) in internal_shift_right() argument
535 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi, in internal_shift_right()
544 RFALSE(src_bi.bi_bh != PATH_H_PBUFFER(tb->tb_path, h) /*tb->S[h] */ || in internal_shift_right()
545 dest_bi.bi_bh != tb->R[h], in internal_shift_right()
547 src_bi.bi_bh, PATH_H_PBUFFER(tb->tb_path, h)); in internal_shift_right()
549 if (tb->CFL[h]) in internal_shift_right()
550 replace_key(tb, cf, d_key_position, tb->CFL[h], in internal_shift_right()
551 tb->lkey[h]); in internal_shift_right()
568 int h, int pointer_amount) in internal_shift1_right() argument
574 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, in internal_shift1_right()
590 int h, int child_pos) in balance_internal_when_delete() argument
594 struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h); in balance_internal_when_delete()
597 insert_num = tb->insert_size[h] / ((int)(DC_SIZE + KEY_SIZE)); in balance_internal_when_delete()
602 bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h); in balance_internal_when_delete()
603 bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1); in balance_internal_when_delete()
607 RFALSE(tb->blknum[h] > 1, in balance_internal_when_delete()
608 "tb->blknum[%d]=%d when insert_size < 0", h, tb->blknum[h]); in balance_internal_when_delete()
612 if (tb->lnum[h] == 0 && tb->rnum[h] == 0) { in balance_internal_when_delete()
613 if (tb->blknum[h] == 0) { in balance_internal_when_delete()
625 if (!tb->L[h - 1] || !B_NR_ITEMS(tb->L[h - 1])) in balance_internal_when_delete()
626 new_root = tb->R[h - 1]; in balance_internal_when_delete()
628 new_root = tb->L[h - 1]; in balance_internal_when_delete()
639 if (h > 1) in balance_internal_when_delete()
651 if (tb->L[h] && tb->lnum[h] == -B_NR_ITEMS(tb->L[h]) - 1) { /* join S[h] with L[h] */ in balance_internal_when_delete()
653 RFALSE(tb->rnum[h] != 0, in balance_internal_when_delete()
655 h, tb->rnum[h]); in balance_internal_when_delete()
657 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, n + 1); in balance_internal_when_delete()
663 if (tb->R[h] && tb->rnum[h] == -B_NR_ITEMS(tb->R[h]) - 1) { /* join S[h] with R[h] */ in balance_internal_when_delete()
664 RFALSE(tb->lnum[h] != 0, in balance_internal_when_delete()
666 h, tb->lnum[h]); in balance_internal_when_delete()
668 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, n + 1); in balance_internal_when_delete()
674 if (tb->lnum[h] < 0) { /* borrow from left neighbor L[h] */ in balance_internal_when_delete()
675 RFALSE(tb->rnum[h] != 0, in balance_internal_when_delete()
676 "wrong tb->rnum[%d]==%d when borrow from L[h]", h, in balance_internal_when_delete()
677 tb->rnum[h]); in balance_internal_when_delete()
679 internal_shift_right(INTERNAL_SHIFT_FROM_L_TO_S, tb, h, in balance_internal_when_delete()
680 -tb->lnum[h]); in balance_internal_when_delete()
684 if (tb->rnum[h] < 0) { /* borrow from right neighbor R[h] */ in balance_internal_when_delete()
685 RFALSE(tb->lnum[h] != 0, in balance_internal_when_delete()
687 h, tb->lnum[h]); in balance_internal_when_delete()
688 …internal_shift_left(INTERNAL_SHIFT_FROM_R_TO_S, tb, h, -tb->rnum[h]); /*tb->S[h], tb->CFR[h], tb->… in balance_internal_when_delete()
692 if (tb->lnum[h] > 0) { /* split S[h] into two parts and put them into neighbors */ in balance_internal_when_delete()
693 RFALSE(tb->rnum[h] == 0 || tb->lnum[h] + tb->rnum[h] != n + 1, in balance_internal_when_delete()
695 h, tb->lnum[h], h, tb->rnum[h], n); in balance_internal_when_delete()
697 …internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, tb->lnum[h]); /*tb->L[h], tb->CFL[h], tb->l… in balance_internal_when_delete()
698 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, in balance_internal_when_delete()
699 tb->rnum[h]); in balance_internal_when_delete()
707 h, tb->lnum[h], h, tb->rnum[h]); in balance_internal_when_delete()
711 static void replace_lkey(struct tree_balance *tb, int h, struct item_head *key) in replace_lkey() argument
713 RFALSE(tb->L[h] == NULL || tb->CFL[h] == NULL, in replace_lkey()
715 tb->L[h], tb->CFL[h]); in replace_lkey()
717 if (B_NR_ITEMS(PATH_H_PBUFFER(tb->tb_path, h)) == 0) in replace_lkey()
720 memcpy(B_N_PDELIM_KEY(tb->CFL[h], tb->lkey[h]), key, KEY_SIZE); in replace_lkey()
722 do_balance_mark_internal_dirty(tb, tb->CFL[h], 0); in replace_lkey()
726 static void replace_rkey(struct tree_balance *tb, int h, struct item_head *key) in replace_rkey() argument
728 RFALSE(tb->R[h] == NULL || tb->CFR[h] == NULL, in replace_rkey()
730 tb->R[h], tb->CFR[h]); in replace_rkey()
731 RFALSE(B_NR_ITEMS(tb->R[h]) == 0, in replace_rkey()
733 B_NR_ITEMS(tb->R[h])); in replace_rkey()
735 memcpy(B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]), key, KEY_SIZE); in replace_rkey()
737 do_balance_mark_internal_dirty(tb, tb->CFR[h], 0); in replace_rkey()
741 int h, /* level of the tree */ in balance_internal() argument
760 struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h); in balance_internal()
769 RFALSE(h < 1, "h (%d) can not be < 1 on internal level", h); in balance_internal()
771 PROC_INFO_INC(tb->tb_sb, balance_at[h]); in balance_internal()
775 h + 1) /*tb->S[h]->b_item_order */ : 0; in balance_internal()
779 insert_num = tb->insert_size[h] / ((int)(KEY_SIZE + DC_SIZE)); in balance_internal()
785 RFALSE(h > 1 && (insert_num > 1 || insert_num < -1), in balance_internal()
787 insert_num, h); in balance_internal()
791 balance_internal_when_delete(tb, h, child_pos); in balance_internal()
796 if (tb->lnum[h] > 0) { in balance_internal()
800 n = B_NR_ITEMS(tb->L[h]); /* number of items in L[h] */ in balance_internal()
801 if (tb->lnum[h] <= child_pos) { in balance_internal()
803 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, in balance_internal()
804 tb->lnum[h]); in balance_internal()
806 child_pos -= tb->lnum[h]; in balance_internal()
807 } else if (tb->lnum[h] > child_pos + insert_num) { in balance_internal()
809 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, in balance_internal()
810 tb->lnum[h] - insert_num); in balance_internal()
816 bi.bi_bh = tb->L[h]; in balance_internal()
817 bi.bi_parent = tb->FL[h]; in balance_internal()
818 bi.bi_position = get_left_neighbor_position(tb, h); in balance_internal()
830 internal_shift1_left(tb, h, child_pos + 1); in balance_internal()
832 k = tb->lnum[h] - child_pos - 1; in balance_internal()
834 bi.bi_bh = tb->L[h]; in balance_internal()
835 bi.bi_parent = tb->FL[h]; in balance_internal()
836 bi.bi_position = get_left_neighbor_position(tb, h); in balance_internal()
842 replace_lkey(tb, h, insert_key + k); in balance_internal()
861 if (tb->rnum[h] > 0) { in balance_internal()
865 if (n - tb->rnum[h] >= child_pos) in balance_internal()
868 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, in balance_internal()
869 tb->rnum[h]); in balance_internal()
870 else if (n + insert_num - tb->rnum[h] < child_pos) { in balance_internal()
874 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, in balance_internal()
875 tb->rnum[h] - insert_num); in balance_internal()
879 bi.bi_bh = tb->R[h]; in balance_internal()
880 bi.bi_parent = tb->FR[h]; in balance_internal()
881 bi.bi_position = get_right_neighbor_position(tb, h); in balance_internal()
885 tb->rnum[h] - 1, in balance_internal()
893 internal_shift1_right(tb, h, n - child_pos + 1); in balance_internal()
895 k = tb->rnum[h] - n + child_pos - 1; in balance_internal()
897 bi.bi_bh = tb->R[h]; in balance_internal()
898 bi.bi_parent = tb->FR[h]; in balance_internal()
899 bi.bi_position = get_right_neighbor_position(tb, h); in balance_internal()
905 replace_rkey(tb, h, insert_key + insert_num - k - 1); in balance_internal()
908 dc = B_N_CHILD(tb->R[h], 0); in balance_internal()
918 do_balance_mark_internal_dirty(tb, tb->R[h], 0); in balance_internal()
925 RFALSE(tb->blknum[h] > 2, "blknum can not be > 2 for internal level"); in balance_internal()
926 RFALSE(tb->blknum[h] < 0, "blknum can not be < 0"); in balance_internal()
928 if (!tb->blknum[h]) { /* node S[h] is empty now */ in balance_internal()
939 struct buffer_head *tbSh_1 = PATH_H_PBUFFER(tb->tb_path, h - 1); in balance_internal()
942 if (tb->blknum[h] != 1) in balance_internal()
948 set_blkh_level(blkh, h + 1); in balance_internal()
957 tb->insert_size[h] -= DC_SIZE; in balance_internal()
976 if (tb->blknum[h] == 2) { in balance_internal()
983 set_blkh_level(B_BLK_HEAD(S_new), h + 1); in balance_internal()
991 src_bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h); in balance_internal()
992 src_bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1); in balance_internal()
1077 bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h); in balance_internal()
1078 bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1); in balance_internal()