Back to home page

OSCL-LXR
 
 

     

0001 /*
0002  * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
0003  */
0004 
0005 #include <linux/uaccess.h>
0006 #include <linux/string.h>
0007 #include <linux/time.h>
0008 #include "reiserfs.h"
0009 #include <linux/buffer_head.h>
0010 
0011 /* this is one and only function that is used outside (do_balance.c) */
0012 int balance_internal(struct tree_balance *,
0013              int, int, struct item_head *, struct buffer_head **);
0014 
0015 /*
0016  * modes of internal_shift_left, internal_shift_right and
0017  * internal_insert_childs
0018  */
0019 #define INTERNAL_SHIFT_FROM_S_TO_L 0
0020 #define INTERNAL_SHIFT_FROM_R_TO_S 1
0021 #define INTERNAL_SHIFT_FROM_L_TO_S 2
0022 #define INTERNAL_SHIFT_FROM_S_TO_R 3
0023 #define INTERNAL_INSERT_TO_S 4
0024 #define INTERNAL_INSERT_TO_L 5
0025 #define INTERNAL_INSERT_TO_R 6
0026 
0027 static void internal_define_dest_src_infos(int shift_mode,
0028                        struct tree_balance *tb,
0029                        int h,
0030                        struct buffer_info *dest_bi,
0031                        struct buffer_info *src_bi,
0032                        int *d_key, struct buffer_head **cf)
0033 {
0034     memset(dest_bi, 0, sizeof(struct buffer_info));
0035     memset(src_bi, 0, sizeof(struct buffer_info));
0036     /* define dest, src, dest parent, dest position */
0037     switch (shift_mode) {
0038 
0039     /* used in internal_shift_left */
0040     case INTERNAL_SHIFT_FROM_S_TO_L:
0041         src_bi->tb = tb;
0042         src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
0043         src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
0044         src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
0045         dest_bi->tb = tb;
0046         dest_bi->bi_bh = tb->L[h];
0047         dest_bi->bi_parent = tb->FL[h];
0048         dest_bi->bi_position = get_left_neighbor_position(tb, h);
0049         *d_key = tb->lkey[h];
0050         *cf = tb->CFL[h];
0051         break;
0052     case INTERNAL_SHIFT_FROM_L_TO_S:
0053         src_bi->tb = tb;
0054         src_bi->bi_bh = tb->L[h];
0055         src_bi->bi_parent = tb->FL[h];
0056         src_bi->bi_position = get_left_neighbor_position(tb, h);
0057         dest_bi->tb = tb;
0058         dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
0059         dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
0060         /* dest position is analog of dest->b_item_order */
0061         dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
0062         *d_key = tb->lkey[h];
0063         *cf = tb->CFL[h];
0064         break;
0065 
0066     /* used in internal_shift_left */
0067     case INTERNAL_SHIFT_FROM_R_TO_S:
0068         src_bi->tb = tb;
0069         src_bi->bi_bh = tb->R[h];
0070         src_bi->bi_parent = tb->FR[h];
0071         src_bi->bi_position = get_right_neighbor_position(tb, h);
0072         dest_bi->tb = tb;
0073         dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
0074         dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
0075         dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
0076         *d_key = tb->rkey[h];
0077         *cf = tb->CFR[h];
0078         break;
0079 
0080     case INTERNAL_SHIFT_FROM_S_TO_R:
0081         src_bi->tb = tb;
0082         src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
0083         src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
0084         src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
0085         dest_bi->tb = tb;
0086         dest_bi->bi_bh = tb->R[h];
0087         dest_bi->bi_parent = tb->FR[h];
0088         dest_bi->bi_position = get_right_neighbor_position(tb, h);
0089         *d_key = tb->rkey[h];
0090         *cf = tb->CFR[h];
0091         break;
0092 
0093     case INTERNAL_INSERT_TO_L:
0094         dest_bi->tb = tb;
0095         dest_bi->bi_bh = tb->L[h];
0096         dest_bi->bi_parent = tb->FL[h];
0097         dest_bi->bi_position = get_left_neighbor_position(tb, h);
0098         break;
0099 
0100     case INTERNAL_INSERT_TO_S:
0101         dest_bi->tb = tb;
0102         dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
0103         dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
0104         dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
0105         break;
0106 
0107     case INTERNAL_INSERT_TO_R:
0108         dest_bi->tb = tb;
0109         dest_bi->bi_bh = tb->R[h];
0110         dest_bi->bi_parent = tb->FR[h];
0111         dest_bi->bi_position = get_right_neighbor_position(tb, h);
0112         break;
0113 
0114     default:
0115         reiserfs_panic(tb->tb_sb, "ibalance-1",
0116                    "shift type is unknown (%d)",
0117                    shift_mode);
0118     }
0119 }
0120 
0121 /*
0122  * Insert count node pointers into buffer cur before position to + 1.
0123  * Insert count items into buffer cur before position to.
0124  * Items and node pointers are specified by inserted and bh respectively.
0125  */
0126 static void internal_insert_childs(struct buffer_info *cur_bi,
0127                    int to, int count,
0128                    struct item_head *inserted,
0129                    struct buffer_head **bh)
0130 {
0131     struct buffer_head *cur = cur_bi->bi_bh;
0132     struct block_head *blkh;
0133     int nr;
0134     struct reiserfs_key *ih;
0135     struct disk_child new_dc[2];
0136     struct disk_child *dc;
0137     int i;
0138 
0139     if (count <= 0)
0140         return;
0141 
0142     blkh = B_BLK_HEAD(cur);
0143     nr = blkh_nr_item(blkh);
0144 
0145     RFALSE(count > 2, "too many children (%d) are to be inserted", count);
0146     RFALSE(B_FREE_SPACE(cur) < count * (KEY_SIZE + DC_SIZE),
0147            "no enough free space (%d), needed %d bytes",
0148            B_FREE_SPACE(cur), count * (KEY_SIZE + DC_SIZE));
0149 
0150     /* prepare space for count disk_child */
0151     dc = B_N_CHILD(cur, to + 1);
0152 
0153     memmove(dc + count, dc, (nr + 1 - (to + 1)) * DC_SIZE);
0154 
0155     /* copy to_be_insert disk children */
0156     for (i = 0; i < count; i++) {
0157         put_dc_size(&new_dc[i],
0158                 MAX_CHILD_SIZE(bh[i]) - B_FREE_SPACE(bh[i]));
0159         put_dc_block_number(&new_dc[i], bh[i]->b_blocknr);
0160     }
0161     memcpy(dc, new_dc, DC_SIZE * count);
0162 
0163     /* prepare space for count items  */
0164     ih = internal_key(cur, ((to == -1) ? 0 : to));
0165 
0166     memmove(ih + count, ih,
0167         (nr - to) * KEY_SIZE + (nr + 1 + count) * DC_SIZE);
0168 
0169     /* copy item headers (keys) */
0170     memcpy(ih, inserted, KEY_SIZE);
0171     if (count > 1)
0172         memcpy(ih + 1, inserted + 1, KEY_SIZE);
0173 
0174     /* sizes, item number */
0175     set_blkh_nr_item(blkh, blkh_nr_item(blkh) + count);
0176     set_blkh_free_space(blkh,
0177                 blkh_free_space(blkh) - count * (DC_SIZE +
0178                                  KEY_SIZE));
0179 
0180     do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);
0181 
0182     /*&&&&&&&&&&&&&&&&&&&&&&&& */
0183     check_internal(cur);
0184     /*&&&&&&&&&&&&&&&&&&&&&&&& */
0185 
0186     if (cur_bi->bi_parent) {
0187         struct disk_child *t_dc =
0188             B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position);
0189         put_dc_size(t_dc,
0190                 dc_size(t_dc) + (count * (DC_SIZE + KEY_SIZE)));
0191         do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
0192                            0);
0193 
0194         /*&&&&&&&&&&&&&&&&&&&&&&&& */
0195         check_internal(cur_bi->bi_parent);
0196         /*&&&&&&&&&&&&&&&&&&&&&&&& */
0197     }
0198 
0199 }
0200 
0201 /*
0202  * Delete del_num items and node pointers from buffer cur starting from
0203  * the first_i'th item and first_p'th pointers respectively.
0204  */
0205 static void internal_delete_pointers_items(struct buffer_info *cur_bi,
0206                        int first_p,
0207                        int first_i, int del_num)
0208 {
0209     struct buffer_head *cur = cur_bi->bi_bh;
0210     int nr;
0211     struct block_head *blkh;
0212     struct reiserfs_key *key;
0213     struct disk_child *dc;
0214 
0215     RFALSE(cur == NULL, "buffer is 0");
0216     RFALSE(del_num < 0,
0217            "negative number of items (%d) can not be deleted", del_num);
0218     RFALSE(first_p < 0 || first_p + del_num > B_NR_ITEMS(cur) + 1
0219            || first_i < 0,
0220            "first pointer order (%d) < 0 or "
0221            "no so many pointers (%d), only (%d) or "
0222            "first key order %d < 0", first_p, first_p + del_num,
0223            B_NR_ITEMS(cur) + 1, first_i);
0224     if (del_num == 0)
0225         return;
0226 
0227     blkh = B_BLK_HEAD(cur);
0228     nr = blkh_nr_item(blkh);
0229 
0230     if (first_p == 0 && del_num == nr + 1) {
0231         RFALSE(first_i != 0,
0232                "1st deleted key must have order 0, not %d", first_i);
0233         make_empty_node(cur_bi);
0234         return;
0235     }
0236 
0237     RFALSE(first_i + del_num > B_NR_ITEMS(cur),
0238            "first_i = %d del_num = %d "
0239            "no so many keys (%d) in the node (%b)(%z)",
0240            first_i, del_num, first_i + del_num, cur, cur);
0241 
0242     /* deleting */
0243     dc = B_N_CHILD(cur, first_p);
0244 
0245     memmove(dc, dc + del_num, (nr + 1 - first_p - del_num) * DC_SIZE);
0246     key = internal_key(cur, first_i);
0247     memmove(key, key + del_num,
0248         (nr - first_i - del_num) * KEY_SIZE + (nr + 1 -
0249                                del_num) * DC_SIZE);
0250 
0251     /* sizes, item number */
0252     set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
0253     set_blkh_free_space(blkh,
0254                 blkh_free_space(blkh) +
0255                 (del_num * (KEY_SIZE + DC_SIZE)));
0256 
0257     do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);
0258     /*&&&&&&&&&&&&&&&&&&&&&&& */
0259     check_internal(cur);
0260     /*&&&&&&&&&&&&&&&&&&&&&&& */
0261 
0262     if (cur_bi->bi_parent) {
0263         struct disk_child *t_dc;
0264         t_dc = B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position);
0265         put_dc_size(t_dc,
0266                 dc_size(t_dc) - (del_num * (KEY_SIZE + DC_SIZE)));
0267 
0268         do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
0269                            0);
0270         /*&&&&&&&&&&&&&&&&&&&&&&&& */
0271         check_internal(cur_bi->bi_parent);
0272         /*&&&&&&&&&&&&&&&&&&&&&&&& */
0273     }
0274 }
0275 
0276 /* delete n node pointers and items starting from given position */
0277 static void internal_delete_childs(struct buffer_info *cur_bi, int from, int n)
0278 {
0279     int i_from;
0280 
0281     i_from = (from == 0) ? from : from - 1;
0282 
0283     /*
0284      * delete n pointers starting from `from' position in CUR;
0285      * delete n keys starting from 'i_from' position in CUR;
0286      */
0287     internal_delete_pointers_items(cur_bi, from, i_from, n);
0288 }
0289 
0290 /*
0291  * copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer
0292  * dest
0293  * last_first == FIRST_TO_LAST means that we copy first items
0294  *                             from src to tail of dest
0295  * last_first == LAST_TO_FIRST means that we copy last items
0296  *                             from src to head of dest
0297  */
0298 static void internal_copy_pointers_items(struct buffer_info *dest_bi,
0299                      struct buffer_head *src,
0300                      int last_first, int cpy_num)
0301 {
0302     /*
0303      * ATTENTION! Number of node pointers in DEST is equal to number
0304      * of items in DEST  as delimiting key have already inserted to
0305      * buffer dest.
0306      */
0307     struct buffer_head *dest = dest_bi->bi_bh;
0308     int nr_dest, nr_src;
0309     int dest_order, src_order;
0310     struct block_head *blkh;
0311     struct reiserfs_key *key;
0312     struct disk_child *dc;
0313 
0314     nr_src = B_NR_ITEMS(src);
0315 
0316     RFALSE(dest == NULL || src == NULL,
0317            "src (%p) or dest (%p) buffer is 0", src, dest);
0318     RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
0319            "invalid last_first parameter (%d)", last_first);
0320     RFALSE(nr_src < cpy_num - 1,
0321            "no so many items (%d) in src (%d)", cpy_num, nr_src);
0322     RFALSE(cpy_num < 0, "cpy_num less than 0 (%d)", cpy_num);
0323     RFALSE(cpy_num - 1 + B_NR_ITEMS(dest) > (int)MAX_NR_KEY(dest),
0324            "cpy_num (%d) + item number in dest (%d) can not be > MAX_NR_KEY(%d)",
0325            cpy_num, B_NR_ITEMS(dest), MAX_NR_KEY(dest));
0326 
0327     if (cpy_num == 0)
0328         return;
0329 
0330     /* coping */
0331     blkh = B_BLK_HEAD(dest);
0332     nr_dest = blkh_nr_item(blkh);
0333 
0334     /*dest_order = (last_first == LAST_TO_FIRST) ? 0 : nr_dest; */
0335     /*src_order = (last_first == LAST_TO_FIRST) ? (nr_src - cpy_num + 1) : 0; */
0336     (last_first == LAST_TO_FIRST) ? (dest_order = 0, src_order =
0337                      nr_src - cpy_num + 1) : (dest_order =
0338                                   nr_dest,
0339                                   src_order =
0340                                   0);
0341 
0342     /* prepare space for cpy_num pointers */
0343     dc = B_N_CHILD(dest, dest_order);
0344 
0345     memmove(dc + cpy_num, dc, (nr_dest - dest_order) * DC_SIZE);
0346 
0347     /* insert pointers */
0348     memcpy(dc, B_N_CHILD(src, src_order), DC_SIZE * cpy_num);
0349 
0350     /* prepare space for cpy_num - 1 item headers */
0351     key = internal_key(dest, dest_order);
0352     memmove(key + cpy_num - 1, key,
0353         KEY_SIZE * (nr_dest - dest_order) + DC_SIZE * (nr_dest +
0354                                    cpy_num));
0355 
0356     /* insert headers */
0357     memcpy(key, internal_key(src, src_order), KEY_SIZE * (cpy_num - 1));
0358 
0359     /* sizes, item number */
0360     set_blkh_nr_item(blkh, blkh_nr_item(blkh) + (cpy_num - 1));
0361     set_blkh_free_space(blkh,
0362                 blkh_free_space(blkh) - (KEY_SIZE * (cpy_num - 1) +
0363                              DC_SIZE * cpy_num));
0364 
0365     do_balance_mark_internal_dirty(dest_bi->tb, dest, 0);
0366 
0367     /*&&&&&&&&&&&&&&&&&&&&&&&& */
0368     check_internal(dest);
0369     /*&&&&&&&&&&&&&&&&&&&&&&&& */
0370 
0371     if (dest_bi->bi_parent) {
0372         struct disk_child *t_dc;
0373         t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
0374         put_dc_size(t_dc,
0375                 dc_size(t_dc) + (KEY_SIZE * (cpy_num - 1) +
0376                          DC_SIZE * cpy_num));
0377 
0378         do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
0379                            0);
0380         /*&&&&&&&&&&&&&&&&&&&&&&&& */
0381         check_internal(dest_bi->bi_parent);
0382         /*&&&&&&&&&&&&&&&&&&&&&&&& */
0383     }
0384 
0385 }
0386 
0387 /*
0388  * Copy cpy_num node pointers and cpy_num - 1 items from buffer src to
0389  * buffer dest.
0390  * Delete cpy_num - del_par items and node pointers from buffer src.
0391  * last_first == FIRST_TO_LAST means, that we copy/delete first items from src.
0392  * last_first == LAST_TO_FIRST means, that we copy/delete last items from src.
0393  */
0394 static void internal_move_pointers_items(struct buffer_info *dest_bi,
0395                      struct buffer_info *src_bi,
0396                      int last_first, int cpy_num,
0397                      int del_par)
0398 {
0399     int first_pointer;
0400     int first_item;
0401 
0402     internal_copy_pointers_items(dest_bi, src_bi->bi_bh, last_first,
0403                      cpy_num);
0404 
0405     if (last_first == FIRST_TO_LAST) {  /* shift_left occurs */
0406         first_pointer = 0;
0407         first_item = 0;
0408         /*
0409          * delete cpy_num - del_par pointers and keys starting for
0410          * pointers with first_pointer, for key - with first_item
0411          */
0412         internal_delete_pointers_items(src_bi, first_pointer,
0413                            first_item, cpy_num - del_par);
0414     } else {        /* shift_right occurs */
0415         int i, j;
0416 
0417         i = (cpy_num - del_par ==
0418              (j =
0419               B_NR_ITEMS(src_bi->bi_bh)) + 1) ? 0 : j - cpy_num +
0420             del_par;
0421 
0422         internal_delete_pointers_items(src_bi,
0423                            j + 1 - cpy_num + del_par, i,
0424                            cpy_num - del_par);
0425     }
0426 }
0427 
0428 /* Insert n_src'th key of buffer src before n_dest'th key of buffer dest. */
0429 static void internal_insert_key(struct buffer_info *dest_bi,
0430                 /* insert key before key with n_dest number */
0431                 int dest_position_before,
0432                 struct buffer_head *src, int src_position)
0433 {
0434     struct buffer_head *dest = dest_bi->bi_bh;
0435     int nr;
0436     struct block_head *blkh;
0437     struct reiserfs_key *key;
0438 
0439     RFALSE(dest == NULL || src == NULL,
0440            "source(%p) or dest(%p) buffer is 0", src, dest);
0441     RFALSE(dest_position_before < 0 || src_position < 0,
0442            "source(%d) or dest(%d) key number less than 0",
0443            src_position, dest_position_before);
0444     RFALSE(dest_position_before > B_NR_ITEMS(dest) ||
0445            src_position >= B_NR_ITEMS(src),
0446            "invalid position in dest (%d (key number %d)) or in src (%d (key number %d))",
0447            dest_position_before, B_NR_ITEMS(dest),
0448            src_position, B_NR_ITEMS(src));
0449     RFALSE(B_FREE_SPACE(dest) < KEY_SIZE,
0450            "no enough free space (%d) in dest buffer", B_FREE_SPACE(dest));
0451 
0452     blkh = B_BLK_HEAD(dest);
0453     nr = blkh_nr_item(blkh);
0454 
0455     /* prepare space for inserting key */
0456     key = internal_key(dest, dest_position_before);
0457     memmove(key + 1, key,
0458         (nr - dest_position_before) * KEY_SIZE + (nr + 1) * DC_SIZE);
0459 
0460     /* insert key */
0461     memcpy(key, internal_key(src, src_position), KEY_SIZE);
0462 
0463     /* Change dirt, free space, item number fields. */
0464 
0465     set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
0466     set_blkh_free_space(blkh, blkh_free_space(blkh) - KEY_SIZE);
0467 
0468     do_balance_mark_internal_dirty(dest_bi->tb, dest, 0);
0469 
0470     if (dest_bi->bi_parent) {
0471         struct disk_child *t_dc;
0472         t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
0473         put_dc_size(t_dc, dc_size(t_dc) + KEY_SIZE);
0474 
0475         do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
0476                            0);
0477     }
0478 }
0479 
0480 /*
0481  * Insert d_key'th (delimiting) key from buffer cfl to tail of dest.
0482  * Copy pointer_amount node pointers and pointer_amount - 1 items from
0483  * buffer src to buffer dest.
0484  * Replace  d_key'th key in buffer cfl.
0485  * Delete pointer_amount items and node pointers from buffer src.
0486  */
0487 /* this can be invoked both to shift from S to L and from R to S */
0488 static void internal_shift_left(
0489                 /*
0490                  * INTERNAL_FROM_S_TO_L | INTERNAL_FROM_R_TO_S
0491                  */
0492                 int mode,
0493                 struct tree_balance *tb,
0494                 int h, int pointer_amount)
0495 {
0496     struct buffer_info dest_bi, src_bi;
0497     struct buffer_head *cf;
0498     int d_key_position;
0499 
0500     internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,
0501                        &d_key_position, &cf);
0502 
0503     /*printk("pointer_amount = %d\n",pointer_amount); */
0504 
0505     if (pointer_amount) {
0506         /*
0507          * insert delimiting key from common father of dest and
0508          * src to node dest into position B_NR_ITEM(dest)
0509          */
0510         internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf,
0511                     d_key_position);
0512 
0513         if (B_NR_ITEMS(src_bi.bi_bh) == pointer_amount - 1) {
0514             if (src_bi.bi_position /*src->b_item_order */  == 0)
0515                 replace_key(tb, cf, d_key_position,
0516                         src_bi.
0517                         bi_parent /*src->b_parent */ , 0);
0518         } else
0519             replace_key(tb, cf, d_key_position, src_bi.bi_bh,
0520                     pointer_amount - 1);
0521     }
0522     /* last parameter is del_parameter */
0523     internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,
0524                      pointer_amount, 0);
0525 
0526 }
0527 
0528 /*
0529  * Insert delimiting key to L[h].
0530  * Copy n node pointers and n - 1 items from buffer S[h] to L[h].
0531  * Delete n - 1 items and node pointers from buffer S[h].
0532  */
0533 /* it always shifts from S[h] to L[h] */
0534 static void internal_shift1_left(struct tree_balance *tb,
0535                  int h, int pointer_amount)
0536 {
0537     struct buffer_info dest_bi, src_bi;
0538     struct buffer_head *cf;
0539     int d_key_position;
0540 
0541     internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
0542                        &dest_bi, &src_bi, &d_key_position, &cf);
0543 
0544     /* insert lkey[h]-th key  from CFL[h] to left neighbor L[h] */
0545     if (pointer_amount > 0)
0546         internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf,
0547                     d_key_position);
0548 
0549     /* last parameter is del_parameter */
0550     internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,
0551                      pointer_amount, 1);
0552 }
0553 
0554 /*
0555  * Insert d_key'th (delimiting) key from buffer cfr to head of dest.
0556  * Copy n node pointers and n - 1 items from buffer src to buffer dest.
0557  * Replace  d_key'th key in buffer cfr.
0558  * Delete n items and node pointers from buffer src.
0559  */
0560 static void internal_shift_right(
0561                  /*
0562                   * INTERNAL_FROM_S_TO_R | INTERNAL_FROM_L_TO_S
0563                   */
0564                  int mode,
0565                  struct tree_balance *tb,
0566                  int h, int pointer_amount)
0567 {
0568     struct buffer_info dest_bi, src_bi;
0569     struct buffer_head *cf;
0570     int d_key_position;
0571     int nr;
0572 
0573     internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,
0574                        &d_key_position, &cf);
0575 
0576     nr = B_NR_ITEMS(src_bi.bi_bh);
0577 
0578     if (pointer_amount > 0) {
0579         /*
0580          * insert delimiting key from common father of dest
0581          * and src to dest node into position 0
0582          */
0583         internal_insert_key(&dest_bi, 0, cf, d_key_position);
0584         if (nr == pointer_amount - 1) {
0585             RFALSE(src_bi.bi_bh != PATH_H_PBUFFER(tb->tb_path, h) /*tb->S[h] */ ||
0586                    dest_bi.bi_bh != tb->R[h],
0587                    "src (%p) must be == tb->S[h](%p) when it disappears",
0588                    src_bi.bi_bh, PATH_H_PBUFFER(tb->tb_path, h));
0589             /* when S[h] disappers replace left delemiting key as well */
0590             if (tb->CFL[h])
0591                 replace_key(tb, cf, d_key_position, tb->CFL[h],
0592                         tb->lkey[h]);
0593         } else
0594             replace_key(tb, cf, d_key_position, src_bi.bi_bh,
0595                     nr - pointer_amount);
0596     }
0597 
0598     /* last parameter is del_parameter */
0599     internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST,
0600                      pointer_amount, 0);
0601 }
0602 
0603 /*
0604  * Insert delimiting key to R[h].
0605  * Copy n node pointers and n - 1 items from buffer S[h] to R[h].
0606  * Delete n - 1 items and node pointers from buffer S[h].
0607  */
0608 /* it always shift from S[h] to R[h] */
0609 static void internal_shift1_right(struct tree_balance *tb,
0610                   int h, int pointer_amount)
0611 {
0612     struct buffer_info dest_bi, src_bi;
0613     struct buffer_head *cf;
0614     int d_key_position;
0615 
0616     internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
0617                        &dest_bi, &src_bi, &d_key_position, &cf);
0618 
0619     /* insert rkey from CFR[h] to right neighbor R[h] */
0620     if (pointer_amount > 0)
0621         internal_insert_key(&dest_bi, 0, cf, d_key_position);
0622 
0623     /* last parameter is del_parameter */
0624     internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST,
0625                      pointer_amount, 1);
0626 }
0627 
0628 /*
0629  * Delete insert_num node pointers together with their left items
0630  * and balance current node.
0631  */
0632 static void balance_internal_when_delete(struct tree_balance *tb,
0633                      int h, int child_pos)
0634 {
0635     int insert_num;
0636     int n;
0637     struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
0638     struct buffer_info bi;
0639 
0640     insert_num = tb->insert_size[h] / ((int)(DC_SIZE + KEY_SIZE));
0641 
0642     /* delete child-node-pointer(s) together with their left item(s) */
0643     bi.tb = tb;
0644     bi.bi_bh = tbSh;
0645     bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
0646     bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
0647 
0648     internal_delete_childs(&bi, child_pos, -insert_num);
0649 
0650     RFALSE(tb->blknum[h] > 1,
0651            "tb->blknum[%d]=%d when insert_size < 0", h, tb->blknum[h]);
0652 
0653     n = B_NR_ITEMS(tbSh);
0654 
0655     if (tb->lnum[h] == 0 && tb->rnum[h] == 0) {
0656         if (tb->blknum[h] == 0) {
0657             /* node S[h] (root of the tree) is empty now */
0658             struct buffer_head *new_root;
0659 
0660             RFALSE(n
0661                    || B_FREE_SPACE(tbSh) !=
0662                    MAX_CHILD_SIZE(tbSh) - DC_SIZE,
0663                    "buffer must have only 0 keys (%d)", n);
0664             RFALSE(bi.bi_parent, "root has parent (%p)",
0665                    bi.bi_parent);
0666 
0667             /* choose a new root */
0668             if (!tb->L[h - 1] || !B_NR_ITEMS(tb->L[h - 1]))
0669                 new_root = tb->R[h - 1];
0670             else
0671                 new_root = tb->L[h - 1];
0672             /*
0673              * switch super block's tree root block
0674              * number to the new value */
0675             PUT_SB_ROOT_BLOCK(tb->tb_sb, new_root->b_blocknr);
0676             /*REISERFS_SB(tb->tb_sb)->s_rs->s_tree_height --; */
0677             PUT_SB_TREE_HEIGHT(tb->tb_sb,
0678                        SB_TREE_HEIGHT(tb->tb_sb) - 1);
0679 
0680             do_balance_mark_sb_dirty(tb,
0681                          REISERFS_SB(tb->tb_sb)->s_sbh,
0682                          1);
0683             /*&&&&&&&&&&&&&&&&&&&&&& */
0684             /* use check_internal if new root is an internal node */
0685             if (h > 1)
0686                 check_internal(new_root);
0687             /*&&&&&&&&&&&&&&&&&&&&&& */
0688 
0689             /* do what is needed for buffer thrown from tree */
0690             reiserfs_invalidate_buffer(tb, tbSh);
0691             return;
0692         }
0693         return;
0694     }
0695 
0696     /* join S[h] with L[h] */
0697     if (tb->L[h] && tb->lnum[h] == -B_NR_ITEMS(tb->L[h]) - 1) {
0698 
0699         RFALSE(tb->rnum[h] != 0,
0700                "invalid tb->rnum[%d]==%d when joining S[h] with L[h]",
0701                h, tb->rnum[h]);
0702 
0703         internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, n + 1);
0704         reiserfs_invalidate_buffer(tb, tbSh);
0705 
0706         return;
0707     }
0708 
0709     /* join S[h] with R[h] */
0710     if (tb->R[h] && tb->rnum[h] == -B_NR_ITEMS(tb->R[h]) - 1) {
0711         RFALSE(tb->lnum[h] != 0,
0712                "invalid tb->lnum[%d]==%d when joining S[h] with R[h]",
0713                h, tb->lnum[h]);
0714 
0715         internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, n + 1);
0716 
0717         reiserfs_invalidate_buffer(tb, tbSh);
0718         return;
0719     }
0720 
0721     /* borrow from left neighbor L[h] */
0722     if (tb->lnum[h] < 0) {
0723         RFALSE(tb->rnum[h] != 0,
0724                "wrong tb->rnum[%d]==%d when borrow from L[h]", h,
0725                tb->rnum[h]);
0726         internal_shift_right(INTERNAL_SHIFT_FROM_L_TO_S, tb, h,
0727                      -tb->lnum[h]);
0728         return;
0729     }
0730 
0731     /* borrow from right neighbor R[h] */
0732     if (tb->rnum[h] < 0) {
0733         RFALSE(tb->lnum[h] != 0,
0734                "invalid tb->lnum[%d]==%d when borrow from R[h]",
0735                h, tb->lnum[h]);
0736         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]); */
0737         return;
0738     }
0739 
0740     /* split S[h] into two parts and put them into neighbors */
0741     if (tb->lnum[h] > 0) {
0742         RFALSE(tb->rnum[h] == 0 || tb->lnum[h] + tb->rnum[h] != n + 1,
0743                "invalid tb->lnum[%d]==%d or tb->rnum[%d]==%d when S[h](item number == %d) is split between them",
0744                h, tb->lnum[h], h, tb->rnum[h], n);
0745 
0746         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]); */
0747         internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
0748                      tb->rnum[h]);
0749 
0750         reiserfs_invalidate_buffer(tb, tbSh);
0751 
0752         return;
0753     }
0754     reiserfs_panic(tb->tb_sb, "ibalance-2",
0755                "unexpected tb->lnum[%d]==%d or tb->rnum[%d]==%d",
0756                h, tb->lnum[h], h, tb->rnum[h]);
0757 }
0758 
0759 /* Replace delimiting key of buffers L[h] and S[h] by the given key.*/
0760 static void replace_lkey(struct tree_balance *tb, int h, struct item_head *key)
0761 {
0762     RFALSE(tb->L[h] == NULL || tb->CFL[h] == NULL,
0763            "L[h](%p) and CFL[h](%p) must exist in replace_lkey",
0764            tb->L[h], tb->CFL[h]);
0765 
0766     if (B_NR_ITEMS(PATH_H_PBUFFER(tb->tb_path, h)) == 0)
0767         return;
0768 
0769     memcpy(internal_key(tb->CFL[h], tb->lkey[h]), key, KEY_SIZE);
0770 
0771     do_balance_mark_internal_dirty(tb, tb->CFL[h], 0);
0772 }
0773 
0774 /* Replace delimiting key of buffers S[h] and R[h] by the given key.*/
0775 static void replace_rkey(struct tree_balance *tb, int h, struct item_head *key)
0776 {
0777     RFALSE(tb->R[h] == NULL || tb->CFR[h] == NULL,
0778            "R[h](%p) and CFR[h](%p) must exist in replace_rkey",
0779            tb->R[h], tb->CFR[h]);
0780     RFALSE(B_NR_ITEMS(tb->R[h]) == 0,
0781            "R[h] can not be empty if it exists (item number=%d)",
0782            B_NR_ITEMS(tb->R[h]));
0783 
0784     memcpy(internal_key(tb->CFR[h], tb->rkey[h]), key, KEY_SIZE);
0785 
0786     do_balance_mark_internal_dirty(tb, tb->CFR[h], 0);
0787 }
0788 
0789 
0790 /*
0791  * if inserting/pasting {
0792  *   child_pos is the position of the node-pointer in S[h] that
0793  *   pointed to S[h-1] before balancing of the h-1 level;
0794  *   this means that new pointers and items must be inserted AFTER
0795  *   child_pos
0796  * } else {
0797  *   it is the position of the leftmost pointer that must be deleted
0798  *   (together with its corresponding key to the left of the pointer)
0799  *   as a result of the previous level's balancing.
0800  * }
0801  */
0802 
0803 int balance_internal(struct tree_balance *tb,
0804              int h, /* level of the tree */
0805              int child_pos,
0806              /* key for insertion on higher level    */
0807              struct item_head *insert_key,
0808              /* node for insertion on higher level */
0809              struct buffer_head **insert_ptr)
0810 {
0811     struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
0812     struct buffer_info bi;
0813 
0814     /*
0815      * we return this: it is 0 if there is no S[h],
0816      * else it is tb->S[h]->b_item_order
0817      */
0818     int order;
0819     int insert_num, n, k;
0820     struct buffer_head *S_new;
0821     struct item_head new_insert_key;
0822     struct buffer_head *new_insert_ptr = NULL;
0823     struct item_head *new_insert_key_addr = insert_key;
0824 
0825     RFALSE(h < 1, "h (%d) can not be < 1 on internal level", h);
0826 
0827     PROC_INFO_INC(tb->tb_sb, balance_at[h]);
0828 
0829     order =
0830         (tbSh) ? PATH_H_POSITION(tb->tb_path,
0831                      h + 1) /*tb->S[h]->b_item_order */ : 0;
0832 
0833     /*
0834      * Using insert_size[h] calculate the number insert_num of items
0835      * that must be inserted to or deleted from S[h].
0836      */
0837     insert_num = tb->insert_size[h] / ((int)(KEY_SIZE + DC_SIZE));
0838 
0839     /* Check whether insert_num is proper * */
0840     RFALSE(insert_num < -2 || insert_num > 2,
0841            "incorrect number of items inserted to the internal node (%d)",
0842            insert_num);
0843     RFALSE(h > 1 && (insert_num > 1 || insert_num < -1),
0844            "incorrect number of items (%d) inserted to the internal node on a level (h=%d) higher than last internal level",
0845            insert_num, h);
0846 
0847     /* Make balance in case insert_num < 0 */
0848     if (insert_num < 0) {
0849         balance_internal_when_delete(tb, h, child_pos);
0850         return order;
0851     }
0852 
0853     k = 0;
0854     if (tb->lnum[h] > 0) {
0855         /*
0856          * shift lnum[h] items from S[h] to the left neighbor L[h].
0857          * check how many of new items fall into L[h] or CFL[h] after
0858          * shifting
0859          */
0860         n = B_NR_ITEMS(tb->L[h]);   /* number of items in L[h] */
0861         if (tb->lnum[h] <= child_pos) {
0862             /* new items don't fall into L[h] or CFL[h] */
0863             internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
0864                         tb->lnum[h]);
0865             child_pos -= tb->lnum[h];
0866         } else if (tb->lnum[h] > child_pos + insert_num) {
0867             /* all new items fall into L[h] */
0868             internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
0869                         tb->lnum[h] - insert_num);
0870             /* insert insert_num keys and node-pointers into L[h] */
0871             bi.tb = tb;
0872             bi.bi_bh = tb->L[h];
0873             bi.bi_parent = tb->FL[h];
0874             bi.bi_position = get_left_neighbor_position(tb, h);
0875             internal_insert_childs(&bi,
0876                            /*tb->L[h], tb->S[h-1]->b_next */
0877                            n + child_pos + 1,
0878                            insert_num, insert_key,
0879                            insert_ptr);
0880 
0881             insert_num = 0;
0882         } else {
0883             struct disk_child *dc;
0884 
0885             /*
0886              * some items fall into L[h] or CFL[h],
0887              * but some don't fall
0888              */
0889             internal_shift1_left(tb, h, child_pos + 1);
0890             /* calculate number of new items that fall into L[h] */
0891             k = tb->lnum[h] - child_pos - 1;
0892             bi.tb = tb;
0893             bi.bi_bh = tb->L[h];
0894             bi.bi_parent = tb->FL[h];
0895             bi.bi_position = get_left_neighbor_position(tb, h);
0896             internal_insert_childs(&bi,
0897                            /*tb->L[h], tb->S[h-1]->b_next, */
0898                            n + child_pos + 1, k,
0899                            insert_key, insert_ptr);
0900 
0901             replace_lkey(tb, h, insert_key + k);
0902 
0903             /*
0904              * replace the first node-ptr in S[h] by
0905              * node-ptr to insert_ptr[k]
0906              */
0907             dc = B_N_CHILD(tbSh, 0);
0908             put_dc_size(dc,
0909                     MAX_CHILD_SIZE(insert_ptr[k]) -
0910                     B_FREE_SPACE(insert_ptr[k]));
0911             put_dc_block_number(dc, insert_ptr[k]->b_blocknr);
0912 
0913             do_balance_mark_internal_dirty(tb, tbSh, 0);
0914 
0915             k++;
0916             insert_key += k;
0917             insert_ptr += k;
0918             insert_num -= k;
0919             child_pos = 0;
0920         }
0921     }
0922     /* tb->lnum[h] > 0 */
0923     if (tb->rnum[h] > 0) {
0924         /*shift rnum[h] items from S[h] to the right neighbor R[h] */
0925         /*
0926          * check how many of new items fall into R or CFR
0927          * after shifting
0928          */
0929         n = B_NR_ITEMS(tbSh);   /* number of items in S[h] */
0930         if (n - tb->rnum[h] >= child_pos)
0931             /* new items fall into S[h] */
0932             internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
0933                          tb->rnum[h]);
0934         else if (n + insert_num - tb->rnum[h] < child_pos) {
0935             /* all new items fall into R[h] */
0936             internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
0937                          tb->rnum[h] - insert_num);
0938 
0939             /* insert insert_num keys and node-pointers into R[h] */
0940             bi.tb = tb;
0941             bi.bi_bh = tb->R[h];
0942             bi.bi_parent = tb->FR[h];
0943             bi.bi_position = get_right_neighbor_position(tb, h);
0944             internal_insert_childs(&bi,
0945                            /*tb->R[h],tb->S[h-1]->b_next */
0946                            child_pos - n - insert_num +
0947                            tb->rnum[h] - 1,
0948                            insert_num, insert_key,
0949                            insert_ptr);
0950             insert_num = 0;
0951         } else {
0952             struct disk_child *dc;
0953 
0954             /* one of the items falls into CFR[h] */
0955             internal_shift1_right(tb, h, n - child_pos + 1);
0956             /* calculate number of new items that fall into R[h] */
0957             k = tb->rnum[h] - n + child_pos - 1;
0958             bi.tb = tb;
0959             bi.bi_bh = tb->R[h];
0960             bi.bi_parent = tb->FR[h];
0961             bi.bi_position = get_right_neighbor_position(tb, h);
0962             internal_insert_childs(&bi,
0963                            /*tb->R[h], tb->R[h]->b_child, */
0964                            0, k, insert_key + 1,
0965                            insert_ptr + 1);
0966 
0967             replace_rkey(tb, h, insert_key + insert_num - k - 1);
0968 
0969             /*
0970              * replace the first node-ptr in R[h] by
0971              * node-ptr insert_ptr[insert_num-k-1]
0972              */
0973             dc = B_N_CHILD(tb->R[h], 0);
0974             put_dc_size(dc,
0975                     MAX_CHILD_SIZE(insert_ptr
0976                            [insert_num - k - 1]) -
0977                     B_FREE_SPACE(insert_ptr
0978                          [insert_num - k - 1]));
0979             put_dc_block_number(dc,
0980                         insert_ptr[insert_num - k -
0981                                1]->b_blocknr);
0982 
0983             do_balance_mark_internal_dirty(tb, tb->R[h], 0);
0984 
0985             insert_num -= (k + 1);
0986         }
0987     }
0988 
0989     /** Fill new node that appears instead of S[h] **/
0990     RFALSE(tb->blknum[h] > 2, "blknum can not be > 2 for internal level");
0991     RFALSE(tb->blknum[h] < 0, "blknum can not be < 0");
0992 
0993     if (!tb->blknum[h]) {   /* node S[h] is empty now */
0994         RFALSE(!tbSh, "S[h] is equal NULL");
0995 
0996         /* do what is needed for buffer thrown from tree */
0997         reiserfs_invalidate_buffer(tb, tbSh);
0998         return order;
0999     }
1000 
1001     if (!tbSh) {
1002         /* create new root */
1003         struct disk_child *dc;
1004         struct buffer_head *tbSh_1 = PATH_H_PBUFFER(tb->tb_path, h - 1);
1005         struct block_head *blkh;
1006 
1007         if (tb->blknum[h] != 1)
1008             reiserfs_panic(NULL, "ibalance-3", "One new node "
1009                        "required for creating the new root");
1010         /* S[h] = empty buffer from the list FEB. */
1011         tbSh = get_FEB(tb);
1012         blkh = B_BLK_HEAD(tbSh);
1013         set_blkh_level(blkh, h + 1);
1014 
1015         /* Put the unique node-pointer to S[h] that points to S[h-1]. */
1016 
1017         dc = B_N_CHILD(tbSh, 0);
1018         put_dc_block_number(dc, tbSh_1->b_blocknr);
1019         put_dc_size(dc,
1020                 (MAX_CHILD_SIZE(tbSh_1) - B_FREE_SPACE(tbSh_1)));
1021 
1022         tb->insert_size[h] -= DC_SIZE;
1023         set_blkh_free_space(blkh, blkh_free_space(blkh) - DC_SIZE);
1024 
1025         do_balance_mark_internal_dirty(tb, tbSh, 0);
1026 
1027         /*&&&&&&&&&&&&&&&&&&&&&&&& */
1028         check_internal(tbSh);
1029         /*&&&&&&&&&&&&&&&&&&&&&&&& */
1030 
1031         /* put new root into path structure */
1032         PATH_OFFSET_PBUFFER(tb->tb_path, ILLEGAL_PATH_ELEMENT_OFFSET) =
1033             tbSh;
1034 
1035         /* Change root in structure super block. */
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);
1039     }
1040 
1041     if (tb->blknum[h] == 2) {
1042         int snum;
1043         struct buffer_info dest_bi, src_bi;
1044 
1045         /* S_new = free buffer from list FEB */
1046         S_new = get_FEB(tb);
1047 
1048         set_blkh_level(B_BLK_HEAD(S_new), h + 1);
1049 
1050         dest_bi.tb = tb;
1051         dest_bi.bi_bh = S_new;
1052         dest_bi.bi_parent = NULL;
1053         dest_bi.bi_position = 0;
1054         src_bi.tb = tb;
1055         src_bi.bi_bh = tbSh;
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);
1058 
1059         n = B_NR_ITEMS(tbSh);   /* number of items in S[h] */
1060         snum = (insert_num + n + 1) / 2;
1061         if (n - snum >= child_pos) {
1062             /* new items don't fall into S_new */
1063             /*  store the delimiting key for the next level */
1064             /* new_insert_key = (n - snum)'th key in S[h] */
1065             memcpy(&new_insert_key, internal_key(tbSh, n - snum),
1066                    KEY_SIZE);
1067             /* last parameter is del_par */
1068             internal_move_pointers_items(&dest_bi, &src_bi,
1069                              LAST_TO_FIRST, snum, 0);
1070         } else if (n + insert_num - snum < child_pos) {
1071             /* all new items fall into S_new */
1072             /*  store the delimiting key for the next level */
1073             /*
1074              * new_insert_key = (n + insert_item - snum)'th
1075              * key in S[h]
1076              */
1077             memcpy(&new_insert_key,
1078                    internal_key(tbSh, n + insert_num - snum),
1079                    KEY_SIZE);
1080             /* last parameter is del_par */
1081             internal_move_pointers_items(&dest_bi, &src_bi,
1082                              LAST_TO_FIRST,
1083                              snum - insert_num, 0);
1084 
1085             /*
1086              * insert insert_num keys and node-pointers
1087              * into S_new
1088              */
1089             internal_insert_childs(&dest_bi,
1090                            /*S_new,tb->S[h-1]->b_next, */
1091                            child_pos - n - insert_num +
1092                            snum - 1,
1093                            insert_num, insert_key,
1094                            insert_ptr);
1095 
1096             insert_num = 0;
1097         } else {
1098             struct disk_child *dc;
1099 
1100             /* some items fall into S_new, but some don't fall */
1101             /* last parameter is del_par */
1102             internal_move_pointers_items(&dest_bi, &src_bi,
1103                              LAST_TO_FIRST,
1104                              n - child_pos + 1, 1);
1105             /* calculate number of new items that fall into S_new */
1106             k = snum - n + child_pos - 1;
1107 
1108             internal_insert_childs(&dest_bi, /*S_new, */ 0, k,
1109                            insert_key + 1, insert_ptr + 1);
1110 
1111             /* new_insert_key = insert_key[insert_num - k - 1] */
1112             memcpy(&new_insert_key, insert_key + insert_num - k - 1,
1113                    KEY_SIZE);
1114             /*
1115              * replace first node-ptr in S_new by node-ptr
1116              * to insert_ptr[insert_num-k-1]
1117              */
1118 
1119             dc = B_N_CHILD(S_new, 0);
1120             put_dc_size(dc,
1121                     (MAX_CHILD_SIZE
1122                      (insert_ptr[insert_num - k - 1]) -
1123                      B_FREE_SPACE(insert_ptr
1124                           [insert_num - k - 1])));
1125             put_dc_block_number(dc,
1126                         insert_ptr[insert_num - k -
1127                                1]->b_blocknr);
1128 
1129             do_balance_mark_internal_dirty(tb, S_new, 0);
1130 
1131             insert_num -= (k + 1);
1132         }
1133         /* new_insert_ptr = node_pointer to S_new */
1134         new_insert_ptr = S_new;
1135 
1136         RFALSE(!buffer_journaled(S_new) || buffer_journal_dirty(S_new)
1137                || buffer_dirty(S_new), "cm-00001: bad S_new (%b)",
1138                S_new);
1139 
1140         /* S_new is released in unfix_nodes */
1141     }
1142 
1143     n = B_NR_ITEMS(tbSh);   /*number of items in S[h] */
1144 
1145     if (0 <= child_pos && child_pos <= n && insert_num > 0) {
1146         bi.tb = tb;
1147         bi.bi_bh = tbSh;
1148         bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
1149         bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
1150         internal_insert_childs(&bi, /*tbSh, */
1151                        /*          ( tb->S[h-1]->b_parent == tb->S[h] ) ? tb->S[h-1]->b_next :  tb->S[h]->b_child->b_next, */
1152                        child_pos, insert_num, insert_key,
1153                        insert_ptr);
1154     }
1155 
1156     insert_ptr[0] = new_insert_ptr;
1157     if (new_insert_ptr)
1158         memcpy(new_insert_key_addr, &new_insert_key, KEY_SIZE);
1159 
1160     return order;
1161 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!