+ k = 0;
+ if (tb->lnum[h] > 0) {
+ /* shift lnum[h] items from S[h] to the left neighbor L[h].
+ check how many of new items fall into L[h] or CFL[h] after
+ shifting */
+ n = B_NR_ITEMS(tb->L[h]); /* number of items in L[h] */
+ if (tb->lnum[h] <= child_pos) {
+ /* new items don't fall into L[h] or CFL[h] */
+ internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
+ tb->lnum[h]);
+ /*internal_shift_left (tb->L[h],tb->CFL[h],tb->lkey[h],tbSh,tb->lnum[h]); */
+ child_pos -= tb->lnum[h];
+ } else if (tb->lnum[h] > child_pos + insert_num) {
+ /* all new items fall into L[h] */
+ internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
+ tb->lnum[h] - insert_num);
+ /* internal_shift_left(tb->L[h],tb->CFL[h],tb->lkey[h],tbSh,
+ tb->lnum[h]-insert_num);
+ */
+ /* insert insert_num keys and node-pointers into L[h] */
+ bi.tb = tb;
+ bi.bi_bh = tb->L[h];
+ bi.bi_parent = tb->FL[h];
+ bi.bi_position = get_left_neighbor_position(tb, h);
+ internal_insert_childs(&bi,
+ /*tb->L[h], tb->S[h-1]->b_next */
+ n + child_pos + 1,
+ insert_num, insert_key,
+ insert_ptr);
+
+ insert_num = 0;
+ } else {
+ struct disk_child *dc;
+
+ /* some items fall into L[h] or CFL[h], but some don't fall */
+ internal_shift1_left(tb, h, child_pos + 1);
+ /* calculate number of new items that fall into L[h] */
+ k = tb->lnum[h] - child_pos - 1;
+ bi.tb = tb;
+ bi.bi_bh = tb->L[h];
+ bi.bi_parent = tb->FL[h];
+ bi.bi_position = get_left_neighbor_position(tb, h);
+ internal_insert_childs(&bi,
+ /*tb->L[h], tb->S[h-1]->b_next, */
+ n + child_pos + 1, k,
+ insert_key, insert_ptr);
+
+ replace_lkey(tb, h, insert_key + k);
+
+ /* replace the first node-ptr in S[h] by node-ptr to insert_ptr[k] */
+ dc = B_N_CHILD(tbSh, 0);
+ put_dc_size(dc,
+ MAX_CHILD_SIZE(insert_ptr[k]) -
+ B_FREE_SPACE(insert_ptr[k]));
+ put_dc_block_number(dc, insert_ptr[k]->b_blocknr);
+
+ do_balance_mark_internal_dirty(tb, tbSh, 0);
+
+ k++;
+ insert_key += k;
+ insert_ptr += k;
+ insert_num -= k;
+ child_pos = 0;
+ }
+ }
+ /* tb->lnum[h] > 0 */
+ if (tb->rnum[h] > 0) {
+ /*shift rnum[h] items from S[h] to the right neighbor R[h] */
+ /* check how many of new items fall into R or CFR after shifting */
+ n = B_NR_ITEMS(tbSh); /* number of items in S[h] */
+ if (n - tb->rnum[h] >= child_pos)
+ /* new items fall into S[h] */
+ /*internal_shift_right(tb,h,tbSh,tb->CFR[h],tb->rkey[h],tb->R[h],tb->rnum[h]); */
+ internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
+ tb->rnum[h]);
+ else if (n + insert_num - tb->rnum[h] < child_pos) {
+ /* all new items fall into R[h] */
+ /*internal_shift_right(tb,h,tbSh,tb->CFR[h],tb->rkey[h],tb->R[h],
+ tb->rnum[h] - insert_num); */
+ internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
+ tb->rnum[h] - insert_num);
+
+ /* insert insert_num keys and node-pointers into R[h] */
+ bi.tb = tb;
+ bi.bi_bh = tb->R[h];
+ bi.bi_parent = tb->FR[h];
+ bi.bi_position = get_right_neighbor_position(tb, h);
+ internal_insert_childs(&bi,
+ /*tb->R[h],tb->S[h-1]->b_next */
+ child_pos - n - insert_num +
+ tb->rnum[h] - 1,
+ insert_num, insert_key,
+ insert_ptr);
+ insert_num = 0;
+ } else {
+ struct disk_child *dc;
+
+ /* one of the items falls into CFR[h] */
+ internal_shift1_right(tb, h, n - child_pos + 1);
+ /* calculate number of new items that fall into R[h] */
+ k = tb->rnum[h] - n + child_pos - 1;
+ bi.tb = tb;
+ bi.bi_bh = tb->R[h];
+ bi.bi_parent = tb->FR[h];
+ bi.bi_position = get_right_neighbor_position(tb, h);
+ internal_insert_childs(&bi,
+ /*tb->R[h], tb->R[h]->b_child, */
+ 0, k, insert_key + 1,
+ insert_ptr + 1);
+
+ replace_rkey(tb, h, insert_key + insert_num - k - 1);
+
+ /* replace the first node-ptr in R[h] by node-ptr insert_ptr[insert_num-k-1] */
+ dc = B_N_CHILD(tb->R[h], 0);
+ put_dc_size(dc,
+ MAX_CHILD_SIZE(insert_ptr
+ [insert_num - k - 1]) -
+ B_FREE_SPACE(insert_ptr
+ [insert_num - k - 1]));
+ put_dc_block_number(dc,
+ insert_ptr[insert_num - k -
+ 1]->b_blocknr);
+
+ do_balance_mark_internal_dirty(tb, tb->R[h], 0);
+
+ insert_num -= (k + 1);
+ }
+ }