Lines Matching refs:h
32 int h, in internal_define_dest_src_infos() argument
45 src_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); in internal_define_dest_src_infos()
46 src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); in internal_define_dest_src_infos()
47 src_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); in internal_define_dest_src_infos()
49 dest_bi->bi_bh = tb->L[h]; in internal_define_dest_src_infos()
50 dest_bi->bi_parent = tb->FL[h]; in internal_define_dest_src_infos()
51 dest_bi->bi_position = get_left_neighbor_position (tb, h); in internal_define_dest_src_infos()
52 *d_key = tb->lkey[h]; in internal_define_dest_src_infos()
53 *cf = tb->CFL[h]; in internal_define_dest_src_infos()
57 src_bi->bi_bh = tb->L[h]; in internal_define_dest_src_infos()
58 src_bi->bi_parent = tb->FL[h]; in internal_define_dest_src_infos()
59 src_bi->bi_position = get_left_neighbor_position (tb, h); in internal_define_dest_src_infos()
61 dest_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); in internal_define_dest_src_infos()
62 dest_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); in internal_define_dest_src_infos()
63 …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()
64 *d_key = tb->lkey[h]; in internal_define_dest_src_infos()
65 *cf = tb->CFL[h]; in internal_define_dest_src_infos()
70 src_bi->bi_bh = tb->R[h]; in internal_define_dest_src_infos()
71 src_bi->bi_parent = tb->FR[h]; in internal_define_dest_src_infos()
72 src_bi->bi_position = get_right_neighbor_position (tb, h); in internal_define_dest_src_infos()
74 dest_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); in internal_define_dest_src_infos()
75 dest_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); in internal_define_dest_src_infos()
76 dest_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); in internal_define_dest_src_infos()
77 *d_key = tb->rkey[h]; in internal_define_dest_src_infos()
78 *cf = tb->CFR[h]; in internal_define_dest_src_infos()
83 src_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); in internal_define_dest_src_infos()
84 src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); in internal_define_dest_src_infos()
85 src_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); in internal_define_dest_src_infos()
87 dest_bi->bi_bh = tb->R[h]; in internal_define_dest_src_infos()
88 dest_bi->bi_parent = tb->FR[h]; in internal_define_dest_src_infos()
89 dest_bi->bi_position = get_right_neighbor_position (tb, h); in internal_define_dest_src_infos()
90 *d_key = tb->rkey[h]; in internal_define_dest_src_infos()
91 *cf = tb->CFR[h]; in internal_define_dest_src_infos()
96 dest_bi->bi_bh = tb->L[h]; in internal_define_dest_src_infos()
97 dest_bi->bi_parent = tb->FL[h]; in internal_define_dest_src_infos()
98 dest_bi->bi_position = get_left_neighbor_position (tb, h); in internal_define_dest_src_infos()
103 dest_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); in internal_define_dest_src_infos()
104 dest_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); in internal_define_dest_src_infos()
105 dest_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); in internal_define_dest_src_infos()
110 dest_bi->bi_bh = tb->R[h]; in internal_define_dest_src_infos()
111 dest_bi->bi_parent = tb->FR[h]; in internal_define_dest_src_infos()
112 dest_bi->bi_position = get_right_neighbor_position (tb, h); in internal_define_dest_src_infos()
463 int h, in internal_shift_left() argument
471 internal_define_dest_src_infos (mode, tb, h, &dest_bi, &src_bi, &d_key_position, &cf); in internal_shift_left()
497 int h, in internal_shift1_left() argument
505 …internal_define_dest_src_infos (INTERNAL_SHIFT_FROM_S_TO_L, tb, h, &dest_bi, &src_bi, &d_key_posit… in internal_shift1_left()
525 int h, in internal_shift_right() argument
535 internal_define_dest_src_infos (mode, tb, h, &dest_bi, &src_bi, &d_key_position, &cf); in internal_shift_right()
543 RFALSE( src_bi.bi_bh != PATH_H_PBUFFER (tb->tb_path, h)/*tb->S[h]*/ || in internal_shift_right()
544 dest_bi.bi_bh != tb->R[h], in internal_shift_right()
546 src_bi.bi_bh, PATH_H_PBUFFER (tb->tb_path, h)); in internal_shift_right()
548 if (tb->CFL[h]) in internal_shift_right()
549 replace_key (tb, cf, d_key_position, tb->CFL[h], tb->lkey[h]); in internal_shift_right()
565 int h, in internal_shift1_right() argument
573 …internal_define_dest_src_infos (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, &dest_bi, &src_bi, &d_key_posit… in internal_shift1_right()
588 int h, int child_pos) in balance_internal_when_delete() argument
592 struct buffer_head * tbSh = PATH_H_PBUFFER (tb->tb_path, h); in balance_internal_when_delete()
595 insert_num = tb->insert_size[h] / ((int)(DC_SIZE + KEY_SIZE)); in balance_internal_when_delete()
600 bi.bi_parent = PATH_H_PPARENT (tb->tb_path, h); in balance_internal_when_delete()
601 bi.bi_position = PATH_H_POSITION (tb->tb_path, h + 1); in balance_internal_when_delete()
605 RFALSE( tb->blknum[h] > 1, in balance_internal_when_delete()
606 "tb->blknum[%d]=%d when insert_size < 0", h, tb->blknum[h]); in balance_internal_when_delete()
610 if ( tb->lnum[h] == 0 && tb->rnum[h] == 0 ) { in balance_internal_when_delete()
611 if ( tb->blknum[h] == 0 ) { in balance_internal_when_delete()
620 if ( ! tb->L[h-1] || ! B_NR_ITEMS(tb->L[h-1]) ) in balance_internal_when_delete()
621 new_root = tb->R[h-1]; in balance_internal_when_delete()
623 new_root = tb->L[h-1]; in balance_internal_when_delete()
631 if (h > 1) in balance_internal_when_delete()
644 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()
646 RFALSE( tb->rnum[h] != 0, in balance_internal_when_delete()
648 h, tb->rnum[h]); in balance_internal_when_delete()
650 internal_shift_left (INTERNAL_SHIFT_FROM_S_TO_L, tb, h, n + 1); in balance_internal_when_delete()
656 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()
657 RFALSE( tb->lnum[h] != 0, in balance_internal_when_delete()
659 h, tb->lnum[h]); in balance_internal_when_delete()
661 internal_shift_right (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, n + 1); in balance_internal_when_delete()
667 if ( tb->lnum[h] < 0 ) { /* borrow from left neighbor L[h] */ in balance_internal_when_delete()
668 RFALSE( tb->rnum[h] != 0, in balance_internal_when_delete()
669 "wrong tb->rnum[%d]==%d when borrow from L[h]", h, tb->rnum[h]); in balance_internal_when_delete()
671 internal_shift_right (INTERNAL_SHIFT_FROM_L_TO_S, tb, h, -tb->lnum[h]); in balance_internal_when_delete()
675 if ( tb->rnum[h] < 0 ) { /* borrow from right neighbor R[h] */ in balance_internal_when_delete()
676 RFALSE( tb->lnum[h] != 0, in balance_internal_when_delete()
678 h, tb->lnum[h]); in balance_internal_when_delete()
679 …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()
683 if ( tb->lnum[h] > 0 ) { /* split S[h] into two parts and put them into neighbors */ in balance_internal_when_delete()
684 RFALSE( tb->rnum[h] == 0 || tb->lnum[h] + tb->rnum[h] != n + 1, in balance_internal_when_delete()
686 h, tb->lnum[h], h, tb->rnum[h], n); in balance_internal_when_delete()
688 …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()
689 internal_shift_right (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, tb->rnum[h]); in balance_internal_when_delete()
696 h, tb->lnum[h], h, tb->rnum[h]); in balance_internal_when_delete()
703 int h, in replace_lkey() argument
707 RFALSE( tb->L[h] == NULL || tb->CFL[h] == NULL, in replace_lkey()
709 tb->L[h], tb->CFL[h]); in replace_lkey()
711 if (B_NR_ITEMS(PATH_H_PBUFFER(tb->tb_path, h)) == 0) in replace_lkey()
714 memcpy (B_N_PDELIM_KEY(tb->CFL[h],tb->lkey[h]), key, KEY_SIZE); in replace_lkey()
716 do_balance_mark_internal_dirty (tb, tb->CFL[h],0); in replace_lkey()
723 int h, in replace_rkey() argument
727 RFALSE( tb->R[h] == NULL || tb->CFR[h] == NULL, in replace_rkey()
729 tb->R[h], tb->CFR[h]); in replace_rkey()
730 RFALSE( B_NR_ITEMS(tb->R[h]) == 0, in replace_rkey()
732 B_NR_ITEMS(tb->R[h])); in replace_rkey()
734 memcpy (B_N_PDELIM_KEY(tb->CFR[h],tb->rkey[h]), key, KEY_SIZE); in replace_rkey()
736 do_balance_mark_internal_dirty (tb, tb->CFR[h], 0); in replace_rkey()
741 int h, /* level of the tree */ in balance_internal() argument
761 struct buffer_head * tbSh = PATH_H_PBUFFER (tb->tb_path, h); in balance_internal()
770 RFALSE( h < 1, "h (%d) can not be < 1 on internal level", h); in balance_internal()
772 PROC_INFO_INC( tb -> tb_sb, balance_at[ h ] ); in balance_internal()
774 order = ( tbSh ) ? PATH_H_POSITION (tb->tb_path, h + 1)/*tb->S[h]->b_item_order*/ : 0; in balance_internal()
778 insert_num = tb->insert_size[h]/((int)(KEY_SIZE + DC_SIZE)); in balance_internal()
784 RFALSE( h > 1 && (insert_num > 1 || insert_num < -1), in balance_internal()
786 insert_num, h); in balance_internal()
790 balance_internal_when_delete (tb, h, child_pos); in balance_internal()
795 if ( tb->lnum[h] > 0 ) { in balance_internal()
799 n = B_NR_ITEMS (tb->L[h]); /* number of items in L[h] */ in balance_internal()
800 if ( tb->lnum[h] <= child_pos ) { in balance_internal()
802 internal_shift_left (INTERNAL_SHIFT_FROM_S_TO_L, tb, h, tb->lnum[h]); in balance_internal()
804 child_pos -= tb->lnum[h]; in balance_internal()
805 } else if ( tb->lnum[h] > child_pos + insert_num ) { in balance_internal()
807 internal_shift_left (INTERNAL_SHIFT_FROM_S_TO_L, tb, h, tb->lnum[h] - insert_num); in balance_internal()
813 bi.bi_bh = tb->L[h]; in balance_internal()
814 bi.bi_parent = tb->FL[h]; in balance_internal()
815 bi.bi_position = get_left_neighbor_position (tb, h); in balance_internal()
824 internal_shift1_left(tb,h,child_pos+1); in balance_internal()
826 k = tb->lnum[h] - child_pos - 1; in balance_internal()
828 bi.bi_bh = tb->L[h]; in balance_internal()
829 bi.bi_parent = tb->FL[h]; in balance_internal()
830 bi.bi_position = get_left_neighbor_position (tb, h); in balance_internal()
834 replace_lkey(tb,h,insert_key + k); in balance_internal()
851 if ( tb->rnum[h] > 0 ) { in balance_internal()
855 if ( n - tb->rnum[h] >= child_pos ) in balance_internal()
858 internal_shift_right (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, tb->rnum[h]); in balance_internal()
860 if ( n + insert_num - tb->rnum[h] < child_pos ) in balance_internal()
865 internal_shift_right (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, tb->rnum[h] - insert_num); in balance_internal()
869 bi.bi_bh = tb->R[h]; in balance_internal()
870 bi.bi_parent = tb->FR[h]; in balance_internal()
871 bi.bi_position = get_right_neighbor_position (tb, h); in balance_internal()
872 …l_insert_childs (&bi, /*tb->R[h],tb->S[h-1]->b_next*/ child_pos - n - insert_num + tb->rnum[h] - 1, in balance_internal()
881 internal_shift1_right(tb,h,n - child_pos + 1); in balance_internal()
883 k = tb->rnum[h] - n + child_pos - 1; in balance_internal()
885 bi.bi_bh = tb->R[h]; in balance_internal()
886 bi.bi_parent = tb->FR[h]; in balance_internal()
887 bi.bi_position = get_right_neighbor_position (tb, h); in balance_internal()
890 replace_rkey(tb,h,insert_key + insert_num - k - 1); in balance_internal()
893 dc = B_N_CHILD(tb->R[h], 0); in balance_internal()
898 do_balance_mark_internal_dirty (tb, tb->R[h],0); in balance_internal()
905 RFALSE( tb->blknum[h] > 2, "blknum can not be > 2 for internal level"); in balance_internal()
906 RFALSE( tb->blknum[h] < 0, "blknum can not be < 0"); in balance_internal()
908 if ( ! tb->blknum[h] ) in balance_internal()
920 struct buffer_head * tbSh_1 = PATH_H_PBUFFER (tb->tb_path, h - 1); in balance_internal()
924 if ( tb->blknum[h] != 1 ) in balance_internal()
929 set_blkh_level( blkh, h + 1 ); in balance_internal()
937 tb->insert_size[h] -= DC_SIZE; in balance_internal()
956 if ( tb->blknum[h] == 2 ) { in balance_internal()
964 set_blkh_level( B_BLK_HEAD(S_new), h + 1 ); in balance_internal()
972 src_bi.bi_parent = PATH_H_PPARENT (tb->tb_path, h); in balance_internal()
973 src_bi.bi_position = PATH_H_POSITION (tb->tb_path, h + 1); in balance_internal()
1043 bi.bi_parent = PATH_H_PPARENT (tb->tb_path, h); in balance_internal()
1044 bi.bi_position = PATH_H_POSITION (tb->tb_path, h + 1); in balance_internal()