Lines Matching +full:h +full:- +full:- +full:- +full:- +full:-
5 #include <linux/uaccess.h>
6 #include <linux/string.h>
7 #include <linux/time.h>
8 #include "reiserfs.h"
9 #include <linux/buffer_head.h>
29 int h, 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()
60 /* dest position is analog of dest->b_item_order */ 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()
131 struct buffer_head *cur = cur_bi->bi_bh; in internal_insert_childs()
153 memmove(dc + count, dc, (nr + 1 - (to + 1)) * DC_SIZE); in internal_insert_childs()
158 MAX_CHILD_SIZE(bh[i]) - B_FREE_SPACE(bh[i])); in internal_insert_childs()
159 put_dc_block_number(&new_dc[i], bh[i]->b_blocknr); in internal_insert_childs()
164 ih = internal_key(cur, ((to == -1) ? 0 : to)); in internal_insert_childs()
167 (nr - to) * KEY_SIZE + (nr + 1 + count) * DC_SIZE); in internal_insert_childs()
177 blkh_free_space(blkh) - count * (DC_SIZE + in internal_insert_childs()
180 do_balance_mark_internal_dirty(cur_bi->tb, cur, 0); in internal_insert_childs()
186 if (cur_bi->bi_parent) { in internal_insert_childs()
188 B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position); in internal_insert_childs()
191 do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent, in internal_insert_childs()
195 check_internal(cur_bi->bi_parent); in internal_insert_childs()
209 struct buffer_head *cur = cur_bi->bi_bh; in internal_delete_pointers_items()
245 memmove(dc, dc + del_num, (nr + 1 - first_p - del_num) * DC_SIZE); in internal_delete_pointers_items()
248 (nr - first_i - del_num) * KEY_SIZE + (nr + 1 - in internal_delete_pointers_items()
252 set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num); in internal_delete_pointers_items()
257 do_balance_mark_internal_dirty(cur_bi->tb, cur, 0); in internal_delete_pointers_items()
262 if (cur_bi->bi_parent) { in internal_delete_pointers_items()
264 t_dc = B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position); in internal_delete_pointers_items()
266 dc_size(t_dc) - (del_num * (KEY_SIZE + DC_SIZE))); in internal_delete_pointers_items()
268 do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent, in internal_delete_pointers_items()
271 check_internal(cur_bi->bi_parent); in internal_delete_pointers_items()
281 i_from = (from == 0) ? from : from - 1; in internal_delete_childs()
291 * copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer
307 struct buffer_head *dest = dest_bi->bi_bh; in internal_copy_pointers_items()
320 RFALSE(nr_src < cpy_num - 1, in internal_copy_pointers_items()
323 RFALSE(cpy_num - 1 + B_NR_ITEMS(dest) > (int)MAX_NR_KEY(dest), in internal_copy_pointers_items()
335 /*src_order = (last_first == LAST_TO_FIRST) ? (nr_src - cpy_num + 1) : 0; */ in internal_copy_pointers_items()
337 nr_src - cpy_num + 1) : (dest_order = in internal_copy_pointers_items()
345 memmove(dc + cpy_num, dc, (nr_dest - dest_order) * DC_SIZE); in internal_copy_pointers_items()
350 /* prepare space for cpy_num - 1 item headers */ in internal_copy_pointers_items()
352 memmove(key + cpy_num - 1, key, in internal_copy_pointers_items()
353 KEY_SIZE * (nr_dest - dest_order) + DC_SIZE * (nr_dest + in internal_copy_pointers_items()
357 memcpy(key, internal_key(src, src_order), KEY_SIZE * (cpy_num - 1)); in internal_copy_pointers_items()
360 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + (cpy_num - 1)); in internal_copy_pointers_items()
362 blkh_free_space(blkh) - (KEY_SIZE * (cpy_num - 1) + in internal_copy_pointers_items()
365 do_balance_mark_internal_dirty(dest_bi->tb, dest, 0); in internal_copy_pointers_items()
371 if (dest_bi->bi_parent) { in internal_copy_pointers_items()
373 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position); in internal_copy_pointers_items()
375 dc_size(t_dc) + (KEY_SIZE * (cpy_num - 1) + in internal_copy_pointers_items()
378 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent, in internal_copy_pointers_items()
381 check_internal(dest_bi->bi_parent); in internal_copy_pointers_items()
388 * Copy cpy_num node pointers and cpy_num - 1 items from buffer src to
390 * Delete cpy_num - del_par items and node pointers from buffer src.
402 internal_copy_pointers_items(dest_bi, src_bi->bi_bh, last_first, in internal_move_pointers_items()
409 * delete cpy_num - del_par pointers and keys starting for in internal_move_pointers_items()
410 * pointers with first_pointer, for key - with first_item in internal_move_pointers_items()
413 first_item, cpy_num - del_par); in internal_move_pointers_items()
417 i = (cpy_num - del_par == in internal_move_pointers_items()
419 B_NR_ITEMS(src_bi->bi_bh)) + 1) ? 0 : j - cpy_num + in internal_move_pointers_items()
423 j + 1 - cpy_num + del_par, i, in internal_move_pointers_items()
424 cpy_num - del_par); in internal_move_pointers_items()
434 struct buffer_head *dest = dest_bi->bi_bh; in internal_insert_key()
458 (nr - dest_position_before) * KEY_SIZE + (nr + 1) * DC_SIZE); in internal_insert_key()
466 set_blkh_free_space(blkh, blkh_free_space(blkh) - KEY_SIZE); in internal_insert_key()
468 do_balance_mark_internal_dirty(dest_bi->tb, dest, 0); in internal_insert_key()
470 if (dest_bi->bi_parent) { in internal_insert_key()
472 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position); in internal_insert_key()
475 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent, in internal_insert_key()
482 * Copy pointer_amount node pointers and pointer_amount - 1 items from
494 int h, int pointer_amount) in internal_shift_left() argument
500 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi, in internal_shift_left()
513 if (B_NR_ITEMS(src_bi.bi_bh) == pointer_amount - 1) { in internal_shift_left()
514 if (src_bi.bi_position /*src->b_item_order */ == 0) in internal_shift_left()
517 bi_parent /*src->b_parent */ , 0); in internal_shift_left()
520 pointer_amount - 1); in internal_shift_left()
529 * Insert delimiting key to L[h].
530 * Copy n node pointers and n - 1 items from buffer S[h] to L[h].
531 * Delete n - 1 items and node pointers from buffer S[h].
533 /* it always shifts from S[h] to L[h] */
535 int h, int pointer_amount) in internal_shift1_left() argument
541 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, in internal_shift1_left()
544 /* insert lkey[h]-th key from CFL[h] to left neighbor L[h] */ in internal_shift1_left()
556 * Copy n node pointers and n - 1 items from buffer src to buffer dest.
566 int h, int pointer_amount) in internal_shift_right() argument
573 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi, in internal_shift_right()
584 if (nr == pointer_amount - 1) { 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()
587 "src (%p) must be == tb->S[h](%p) when it disappears", in internal_shift_right()
588 src_bi.bi_bh, PATH_H_PBUFFER(tb->tb_path, h)); in internal_shift_right()
589 /* when S[h] disappers replace left delemiting key as well */ 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()
595 nr - pointer_amount); in internal_shift_right()
604 * Insert delimiting key to R[h].
605 * Copy n node pointers and n - 1 items from buffer S[h] to R[h].
606 * Delete n - 1 items and node pointers from buffer S[h].
608 /* it always shift from S[h] to R[h] */
610 int h, int pointer_amount) in internal_shift1_right() argument
616 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, in internal_shift1_right()
619 /* insert rkey from CFR[h] to right neighbor R[h] */ in internal_shift1_right()
633 int h, int child_pos) 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()
642 /* delete child-node-pointer(s) together with their left item(s) */ 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()
648 internal_delete_childs(&bi, child_pos, -insert_num); 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()
657 /* node S[h] (root of the tree) is empty now */ in balance_internal_when_delete()
662 MAX_CHILD_SIZE(tbSh) - DC_SIZE, 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()
676 /*REISERFS_SB(tb->tb_sb)->s_rs->s_tree_height --; */ 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()
681 REISERFS_SB(tb->tb_sb)->s_sbh, in balance_internal_when_delete()
685 if (h > 1) in balance_internal_when_delete()
696 /* join S[h] with L[h] */ 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()
700 "invalid tb->rnum[%d]==%d when joining S[h] with L[h]", 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()
709 /* join S[h] with R[h] */ 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()
712 "invalid tb->lnum[%d]==%d when joining S[h] with R[h]", 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()
721 /* borrow from left neighbor L[h] */ 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()
724 "wrong tb->rnum[%d]==%d when borrow from L[h]", h, 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()
731 /* borrow from right neighbor R[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()
734 "invalid tb->lnum[%d]==%d when borrow from R[h]", in balance_internal_when_delete()
735 h, tb->lnum[h]); in balance_internal_when_delete()
736 …_left(INTERNAL_SHIFT_FROM_R_TO_S, tb, h, -tb->rnum[h]); /*tb->S[h], tb->CFR[h], tb->rkey[h], tb->R… in balance_internal_when_delete()
740 /* split S[h] into two parts and put them into neighbors */ 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()
743 … "invalid tb->lnum[%d]==%d or tb->rnum[%d]==%d when S[h](item number == %d) is split between them", in balance_internal_when_delete()
744 h, tb->lnum[h], h, tb->rnum[h], n); in balance_internal_when_delete()
746 …t_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, tb->lnum[h]); /*tb->L[h], tb->CFL[h], tb->lkey[h], tb->S… 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()
754 reiserfs_panic(tb->tb_sb, "ibalance-2", in balance_internal_when_delete()
755 "unexpected tb->lnum[%d]==%d or tb->rnum[%d]==%d", in balance_internal_when_delete()
756 h, tb->lnum[h], h, tb->rnum[h]); in balance_internal_when_delete()
759 /* Replace delimiting key of buffers L[h] and S[h] by the given key.*/
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()
763 "L[h](%p) and CFL[h](%p) must exist in replace_lkey", 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()
774 /* Replace delimiting key of buffers S[h] and R[h] by the given key.*/
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()
778 "R[h](%p) and CFR[h](%p) must exist in replace_rkey", 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()
781 "R[h] can not be empty if it exists (item number=%d)", 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()
792 * child_pos is the position of the node-pointer in S[h] that
793 * pointed to S[h-1] before balancing of the h-1 level;
804 int h, /* level of the tree */ in balance_internal() argument
811 struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h); in balance_internal()
815 * we return this: it is 0 if there is no S[h], in balance_internal()
816 * else it is tb->S[h]->b_item_order in balance_internal()
825 RFALSE(h < 1, "h (%d) can not be < 1 on internal level", 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()
831 h + 1) /*tb->S[h]->b_item_order */ : 0; in balance_internal()
834 * Using insert_size[h] calculate the number insert_num of items in balance_internal()
835 * that must be inserted to or deleted from S[h]. in balance_internal()
837 insert_num = tb->insert_size[h] / ((int)(KEY_SIZE + DC_SIZE)); in balance_internal()
840 RFALSE(insert_num < -2 || insert_num > 2, in balance_internal()
843 RFALSE(h > 1 && (insert_num > 1 || insert_num < -1), in balance_internal()
844 …"incorrect number of items (%d) inserted to the internal node on a level (h=%d) higher than last i… in balance_internal()
845 insert_num, h); in balance_internal()
849 balance_internal_when_delete(tb, h, child_pos); in balance_internal()
854 if (tb->lnum[h] > 0) { in balance_internal()
856 * shift lnum[h] items from S[h] to the left neighbor L[h]. in balance_internal()
857 * check how many of new items fall into L[h] or CFL[h] after 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()
862 /* new items don't fall into L[h] or CFL[h] */ 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()
867 /* all new items fall into L[h] */ 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()
870 /* insert insert_num keys and node-pointers into L[h] */ 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()
876 /*tb->L[h], tb->S[h-1]->b_next */ in balance_internal()
886 * some items fall into L[h] or CFL[h], in balance_internal()
889 internal_shift1_left(tb, h, child_pos + 1); in balance_internal()
890 /* calculate number of new items that fall into L[h] */ in balance_internal()
891 k = tb->lnum[h] - child_pos - 1; 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()
897 /*tb->L[h], tb->S[h-1]->b_next, */ in balance_internal()
901 replace_lkey(tb, h, insert_key + k); in balance_internal()
904 * replace the first node-ptr in S[h] by in balance_internal()
905 * node-ptr to insert_ptr[k] in balance_internal()
909 MAX_CHILD_SIZE(insert_ptr[k]) - in balance_internal()
911 put_dc_block_number(dc, insert_ptr[k]->b_blocknr); in balance_internal()
918 insert_num -= k; in balance_internal()
922 /* tb->lnum[h] > 0 */ in balance_internal()
923 if (tb->rnum[h] > 0) { in balance_internal()
924 /*shift rnum[h] items from S[h] to the right neighbor R[h] */ in balance_internal()
929 n = B_NR_ITEMS(tbSh); /* number of items in S[h] */ in balance_internal()
930 if (n - tb->rnum[h] >= child_pos) in balance_internal()
931 /* new items fall into S[h] */ 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()
935 /* all new items fall into R[h] */ 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()
939 /* insert insert_num keys and node-pointers into R[h] */ 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()
945 /*tb->R[h],tb->S[h-1]->b_next */ in balance_internal()
946 child_pos - n - insert_num + in balance_internal()
947 tb->rnum[h] - 1, in balance_internal()
954 /* one of the items falls into CFR[h] */ in balance_internal()
955 internal_shift1_right(tb, h, n - child_pos + 1); in balance_internal()
956 /* calculate number of new items that fall into R[h] */ in balance_internal()
957 k = tb->rnum[h] - n + child_pos - 1; 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()
963 /*tb->R[h], tb->R[h]->b_child, */ in balance_internal()
967 replace_rkey(tb, h, insert_key + insert_num - k - 1); in balance_internal()
970 * replace the first node-ptr in R[h] by in balance_internal()
971 * node-ptr insert_ptr[insert_num-k-1] in balance_internal()
973 dc = B_N_CHILD(tb->R[h], 0); in balance_internal()
976 [insert_num - k - 1]) - in balance_internal()
978 [insert_num - k - 1])); in balance_internal()
980 insert_ptr[insert_num - k - in balance_internal()
981 1]->b_blocknr); in balance_internal()
983 do_balance_mark_internal_dirty(tb, tb->R[h], 0); in balance_internal()
985 insert_num -= (k + 1); in balance_internal()
989 /** Fill new node that appears instead of S[h] **/ 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()
994 RFALSE(!tbSh, "S[h] is equal NULL"); 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()
1008 reiserfs_panic(NULL, "ibalance-3", "One new node " in balance_internal()
1010 /* S[h] = empty buffer from the list FEB. */ in balance_internal()
1013 set_blkh_level(blkh, h + 1); in balance_internal()
1015 /* Put the unique node-pointer to S[h] that points to S[h-1]. */ in balance_internal()
1018 put_dc_block_number(dc, tbSh_1->b_blocknr); in balance_internal()
1020 (MAX_CHILD_SIZE(tbSh_1) - B_FREE_SPACE(tbSh_1))); in balance_internal()
1022 tb->insert_size[h] -= DC_SIZE; in balance_internal()
1023 set_blkh_free_space(blkh, blkh_free_space(blkh) - DC_SIZE); 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()
1048 set_blkh_level(B_BLK_HEAD(S_new), h + 1); 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()
1059 n = B_NR_ITEMS(tbSh); /* number of items in S[h] */ in balance_internal()
1061 if (n - snum >= child_pos) { in balance_internal()
1064 /* new_insert_key = (n - snum)'th key in S[h] */ in balance_internal()
1065 memcpy(&new_insert_key, internal_key(tbSh, n - snum), in balance_internal()
1070 } else if (n + insert_num - snum < child_pos) { in balance_internal()
1074 * new_insert_key = (n + insert_item - snum)'th in balance_internal()
1075 * key in S[h] in balance_internal()
1078 internal_key(tbSh, n + insert_num - snum), in balance_internal()
1083 snum - insert_num, 0); in balance_internal()
1086 * insert insert_num keys and node-pointers in balance_internal()
1090 /*S_new,tb->S[h-1]->b_next, */ in balance_internal()
1091 child_pos - n - insert_num + in balance_internal()
1092 snum - 1, in balance_internal()
1104 n - child_pos + 1, 1); in balance_internal()
1106 k = snum - n + child_pos - 1; in balance_internal()
1111 /* new_insert_key = insert_key[insert_num - k - 1] */ in balance_internal()
1112 memcpy(&new_insert_key, insert_key + insert_num - k - 1, in balance_internal()
1115 * replace first node-ptr in S_new by node-ptr in balance_internal()
1116 * to insert_ptr[insert_num-k-1] in balance_internal()
1122 (insert_ptr[insert_num - k - 1]) - in balance_internal()
1124 [insert_num - k - 1]))); in balance_internal()
1126 insert_ptr[insert_num - k - in balance_internal()
1127 1]->b_blocknr); in balance_internal()
1131 insert_num -= (k + 1); in balance_internal()
1137 || buffer_dirty(S_new), "cm-00001: bad S_new (%b)", in balance_internal()
1143 n = B_NR_ITEMS(tbSh); /*number of items in S[h] */ 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()
1151 …/* ( tb->S[h-1]->b_parent == tb->S[h] ) ? tb->S[h-1]->b_next : tb->S[h]->b_child->b_next… in balance_internal()