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