Lines Matching refs:tb
28 struct tree_balance *tb,
41 src_bi->tb = tb;
42 src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
43 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
44 src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
45 dest_bi->tb = tb;
46 dest_bi->bi_bh = tb->L[h];
47 dest_bi->bi_parent = tb->FL[h];
48 dest_bi->bi_position = get_left_neighbor_position(tb, h);
49 *d_key = tb->lkey[h];
50 *cf = tb->CFL[h];
53 src_bi->tb = tb;
54 src_bi->bi_bh = tb->L[h];
55 src_bi->bi_parent = tb->FL[h];
56 src_bi->bi_position = get_left_neighbor_position(tb, h);
57 dest_bi->tb = tb;
58 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
59 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
61 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
62 *d_key = tb->lkey[h];
63 *cf = tb->CFL[h];
68 src_bi->tb = tb;
69 src_bi->bi_bh = tb->R[h];
70 src_bi->bi_parent = tb->FR[h];
71 src_bi->bi_position = get_right_neighbor_position(tb, h);
72 dest_bi->tb = tb;
73 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
74 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
75 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
76 *d_key = tb->rkey[h];
77 *cf = tb->CFR[h];
81 src_bi->tb = tb;
82 src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
83 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
84 src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
85 dest_bi->tb = tb;
86 dest_bi->bi_bh = tb->R[h];
87 dest_bi->bi_parent = tb->FR[h];
88 dest_bi->bi_position = get_right_neighbor_position(tb, h);
89 *d_key = tb->rkey[h];
90 *cf = tb->CFR[h];
94 dest_bi->tb = tb;
95 dest_bi->bi_bh = tb->L[h];
96 dest_bi->bi_parent = tb->FL[h];
97 dest_bi->bi_position = get_left_neighbor_position(tb, h);
101 dest_bi->tb = tb;
102 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
103 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
104 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
108 dest_bi->tb = tb;
109 dest_bi->bi_bh = tb->R[h];
110 dest_bi->bi_parent = tb->FR[h];
111 dest_bi->bi_position = get_right_neighbor_position(tb, h);
115 reiserfs_panic(tb->tb_sb, "ibalance-1",
180 do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);
191 do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
257 do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);
268 do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
365 do_balance_mark_internal_dirty(dest_bi->tb, dest, 0);
378 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
468 do_balance_mark_internal_dirty(dest_bi->tb, dest, 0);
475 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
493 struct tree_balance *tb,
500 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,
515 replace_key(tb, cf, d_key_position,
519 replace_key(tb, cf, d_key_position, src_bi.bi_bh,
534 static void internal_shift1_left(struct tree_balance *tb,
541 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
565 struct tree_balance *tb,
573 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,
585 RFALSE(src_bi.bi_bh != PATH_H_PBUFFER(tb->tb_path, h) /*tb->S[h] */ ||
586 dest_bi.bi_bh != tb->R[h],
587 "src (%p) must be == tb->S[h](%p) when it disappears",
588 src_bi.bi_bh, PATH_H_PBUFFER(tb->tb_path, h));
590 if (tb->CFL[h])
591 replace_key(tb, cf, d_key_position, tb->CFL[h],
592 tb->lkey[h]);
594 replace_key(tb, cf, d_key_position, src_bi.bi_bh,
609 static void internal_shift1_right(struct tree_balance *tb,
616 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
632 static void balance_internal_when_delete(struct tree_balance *tb,
637 struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
640 insert_num = tb->insert_size[h] / ((int)(DC_SIZE + KEY_SIZE));
643 bi.tb = tb;
645 bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
646 bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
650 RFALSE(tb->blknum[h] > 1,
651 "tb->blknum[%d]=%d when insert_size < 0", h, tb->blknum[h]);
655 if (tb->lnum[h] == 0 && tb->rnum[h] == 0) {
656 if (tb->blknum[h] == 0) {
668 if (!tb->L[h - 1] || !B_NR_ITEMS(tb->L[h - 1]))
669 new_root = tb->R[h - 1];
671 new_root = tb->L[h - 1];
675 PUT_SB_ROOT_BLOCK(tb->tb_sb, new_root->b_blocknr);
676 /*REISERFS_SB(tb->tb_sb)->s_rs->s_tree_height --; */
677 PUT_SB_TREE_HEIGHT(tb->tb_sb,
678 SB_TREE_HEIGHT(tb->tb_sb) - 1);
680 do_balance_mark_sb_dirty(tb,
681 REISERFS_SB(tb->tb_sb)->s_sbh,
690 reiserfs_invalidate_buffer(tb, tbSh);
697 if (tb->L[h] && tb->lnum[h] == -B_NR_ITEMS(tb->L[h]) - 1) {
699 RFALSE(tb->rnum[h] != 0,
700 "invalid tb->rnum[%d]==%d when joining S[h] with L[h]",
701 h, tb->rnum[h]);
703 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, n + 1);
704 reiserfs_invalidate_buffer(tb, tbSh);
710 if (tb->R[h] && tb->rnum[h] == -B_NR_ITEMS(tb->R[h]) - 1) {
711 RFALSE(tb->lnum[h] != 0,
712 "invalid tb->lnum[%d]==%d when joining S[h] with R[h]",
713 h, tb->lnum[h]);
715 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, n + 1);
717 reiserfs_invalidate_buffer(tb, tbSh);
722 if (tb->lnum[h] < 0) {
723 RFALSE(tb->rnum[h] != 0,
724 "wrong tb->rnum[%d]==%d when borrow from L[h]", h,
725 tb->rnum[h]);
726 internal_shift_right(INTERNAL_SHIFT_FROM_L_TO_S, tb, h,
727 -tb->lnum[h]);
732 if (tb->rnum[h] < 0) {
733 RFALSE(tb->lnum[h] != 0,
734 "invalid tb->lnum[%d]==%d when borrow from R[h]",
735 h, tb->lnum[h]);
736 internal_shift_left(INTERNAL_SHIFT_FROM_R_TO_S, tb, h, -tb->rnum[h]); /*tb->S[h], tb->CFR[h], tb->rkey[h], tb->R[h], -tb->rnum[h]); */
741 if (tb->lnum[h] > 0) {
742 RFALSE(tb->rnum[h] == 0 || tb->lnum[h] + tb->rnum[h] != n + 1,
743 "invalid tb->lnum[%d]==%d or tb->rnum[%d]==%d when S[h](item number == %d) is split between them",
744 h, tb->lnum[h], h, tb->rnum[h], n);
746 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, tb->lnum[h]); /*tb->L[h], tb->CFL[h], tb->lkey[h], tb->S[h], tb->lnum[h]); */
747 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
748 tb->rnum[h]);
750 reiserfs_invalidate_buffer(tb, tbSh);
754 reiserfs_panic(tb->tb_sb, "ibalance-2",
755 "unexpected tb->lnum[%d]==%d or tb->rnum[%d]==%d",
756 h, tb->lnum[h], h, tb->rnum[h]);
760 static void replace_lkey(struct tree_balance *tb, int h, struct item_head *key)
762 RFALSE(tb->L[h] == NULL || tb->CFL[h] == NULL,
764 tb->L[h], tb->CFL[h]);
766 if (B_NR_ITEMS(PATH_H_PBUFFER(tb->tb_path, h)) == 0)
769 memcpy(internal_key(tb->CFL[h], tb->lkey[h]), key, KEY_SIZE);
771 do_balance_mark_internal_dirty(tb, tb->CFL[h], 0);
775 static void replace_rkey(struct tree_balance *tb, int h, struct item_head *key)
777 RFALSE(tb->R[h] == NULL || tb->CFR[h] == NULL,
779 tb->R[h], tb->CFR[h]);
780 RFALSE(B_NR_ITEMS(tb->R[h]) == 0,
782 B_NR_ITEMS(tb->R[h]));
784 memcpy(internal_key(tb->CFR[h], tb->rkey[h]), key, KEY_SIZE);
786 do_balance_mark_internal_dirty(tb, tb->CFR[h], 0);
803 int balance_internal(struct tree_balance *tb,
811 struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
816 * else it is tb->S[h]->b_item_order
827 PROC_INFO_INC(tb->tb_sb, balance_at[h]);
830 (tbSh) ? PATH_H_POSITION(tb->tb_path,
831 h + 1) /*tb->S[h]->b_item_order */ : 0;
837 insert_num = tb->insert_size[h] / ((int)(KEY_SIZE + DC_SIZE));
849 balance_internal_when_delete(tb, h, child_pos);
854 if (tb->lnum[h] > 0) {
860 n = B_NR_ITEMS(tb->L[h]); /* number of items in L[h] */
861 if (tb->lnum[h] <= child_pos) {
863 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
864 tb->lnum[h]);
865 child_pos -= tb->lnum[h];
866 } else if (tb->lnum[h] > child_pos + insert_num) {
868 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
869 tb->lnum[h] - insert_num);
871 bi.tb = tb;
872 bi.bi_bh = tb->L[h];
873 bi.bi_parent = tb->FL[h];
874 bi.bi_position = get_left_neighbor_position(tb, h);
876 /*tb->L[h], tb->S[h-1]->b_next */
889 internal_shift1_left(tb, h, child_pos + 1);
891 k = tb->lnum[h] - child_pos - 1;
892 bi.tb = tb;
893 bi.bi_bh = tb->L[h];
894 bi.bi_parent = tb->FL[h];
895 bi.bi_position = get_left_neighbor_position(tb, h);
897 /*tb->L[h], tb->S[h-1]->b_next, */
901 replace_lkey(tb, h, insert_key + k);
913 do_balance_mark_internal_dirty(tb, tbSh, 0);
922 /* tb->lnum[h] > 0 */
923 if (tb->rnum[h] > 0) {
930 if (n - tb->rnum[h] >= child_pos)
932 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
933 tb->rnum[h]);
934 else if (n + insert_num - tb->rnum[h] < child_pos) {
936 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
937 tb->rnum[h] - insert_num);
940 bi.tb = tb;
941 bi.bi_bh = tb->R[h];
942 bi.bi_parent = tb->FR[h];
943 bi.bi_position = get_right_neighbor_position(tb, h);
945 /*tb->R[h],tb->S[h-1]->b_next */
947 tb->rnum[h] - 1,
955 internal_shift1_right(tb, h, n - child_pos + 1);
957 k = tb->rnum[h] - n + child_pos - 1;
958 bi.tb = tb;
959 bi.bi_bh = tb->R[h];
960 bi.bi_parent = tb->FR[h];
961 bi.bi_position = get_right_neighbor_position(tb, h);
963 /*tb->R[h], tb->R[h]->b_child, */
967 replace_rkey(tb, h, insert_key + insert_num - k - 1);
973 dc = B_N_CHILD(tb->R[h], 0);
983 do_balance_mark_internal_dirty(tb, tb->R[h], 0);
990 RFALSE(tb->blknum[h] > 2, "blknum can not be > 2 for internal level");
991 RFALSE(tb->blknum[h] < 0, "blknum can not be < 0");
993 if (!tb->blknum[h]) { /* node S[h] is empty now */
997 reiserfs_invalidate_buffer(tb, tbSh);
1004 struct buffer_head *tbSh_1 = PATH_H_PBUFFER(tb->tb_path, h - 1);
1007 if (tb->blknum[h] != 1)
1011 tbSh = get_FEB(tb);
1022 tb->insert_size[h] -= DC_SIZE;
1025 do_balance_mark_internal_dirty(tb, tbSh, 0);
1032 PATH_OFFSET_PBUFFER(tb->tb_path, ILLEGAL_PATH_ELEMENT_OFFSET) =
1036 PUT_SB_ROOT_BLOCK(tb->tb_sb, tbSh->b_blocknr);
1037 PUT_SB_TREE_HEIGHT(tb->tb_sb, SB_TREE_HEIGHT(tb->tb_sb) + 1);
1038 do_balance_mark_sb_dirty(tb, REISERFS_SB(tb->tb_sb)->s_sbh, 1);
1041 if (tb->blknum[h] == 2) {
1046 S_new = get_FEB(tb);
1050 dest_bi.tb = tb;
1054 src_bi.tb = tb;
1056 src_bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
1057 src_bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
1090 /*S_new,tb->S[h-1]->b_next, */
1129 do_balance_mark_internal_dirty(tb, S_new, 0);
1146 bi.tb = tb;
1148 bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
1149 bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
1151 /* ( tb->S[h-1]->b_parent == tb->S[h] ) ? tb->S[h-1]->b_next : tb->S[h]->b_child->b_next, */