1/* 2 * Copyright 2000-2002 by Hans Reiser, licensing governed by reiserfs/README 3 */ 4 5#include <linux/config.h> 6#include <asm/uaccess.h> 7#include <linux/string.h> 8#include <linux/sched.h> 9#include <linux/reiserfs_fs.h> 10 11/* this is one and only function that is used outside (do_balance.c) */ 12int balance_internal ( 13 struct tree_balance * , 14 int, 15 int, 16 struct item_head * , 17 struct buffer_head ** 18 ); 19 20/* modes of internal_shift_left, internal_shift_right and internal_insert_childs */ 21#define INTERNAL_SHIFT_FROM_S_TO_L 0 22#define INTERNAL_SHIFT_FROM_R_TO_S 1 23#define INTERNAL_SHIFT_FROM_L_TO_S 2 24#define INTERNAL_SHIFT_FROM_S_TO_R 3 25#define INTERNAL_INSERT_TO_S 4 26#define INTERNAL_INSERT_TO_L 5 27#define INTERNAL_INSERT_TO_R 6 28 29static void internal_define_dest_src_infos ( 30 int shift_mode, 31 struct tree_balance * tb, 32 int h, 33 struct buffer_info * dest_bi, 34 struct buffer_info * src_bi, 35 int * d_key, 36 struct buffer_head ** cf 37 ) 38{ 39 memset (dest_bi, 0, sizeof (struct buffer_info)); 40 memset (src_bi, 0, sizeof (struct buffer_info)); 41 /* define dest, src, dest parent, dest position */ 42 switch (shift_mode) { 43 case INTERNAL_SHIFT_FROM_S_TO_L: /* used in internal_shift_left */ 44 src_bi->tb = tb; 45 src_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); 46 src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); 47 src_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); 48 dest_bi->tb = tb; 49 dest_bi->bi_bh = tb->L[h]; 50 dest_bi->bi_parent = tb->FL[h]; 51 dest_bi->bi_position = get_left_neighbor_position (tb, h); 52 *d_key = tb->lkey[h]; 53 *cf = tb->CFL[h]; 54 break; 55 case INTERNAL_SHIFT_FROM_L_TO_S: 56 src_bi->tb = tb; 57 src_bi->bi_bh = tb->L[h]; 58 src_bi->bi_parent = tb->FL[h]; 59 src_bi->bi_position = get_left_neighbor_position (tb, h); 60 dest_bi->tb = tb; 61 dest_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); 62 dest_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); 63 dest_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); /* dest position is analog of dest->b_item_order */ 64 *d_key = tb->lkey[h]; 65 *cf = tb->CFL[h]; 66 break; 67 68 case INTERNAL_SHIFT_FROM_R_TO_S: /* used in internal_shift_left */ 69 src_bi->tb = tb; 70 src_bi->bi_bh = tb->R[h]; 71 src_bi->bi_parent = tb->FR[h]; 72 src_bi->bi_position = get_right_neighbor_position (tb, h); 73 dest_bi->tb = tb; 74 dest_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); 75 dest_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); 76 dest_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); 77 *d_key = tb->rkey[h]; 78 *cf = tb->CFR[h]; 79 break; 80 81 case INTERNAL_SHIFT_FROM_S_TO_R: 82 src_bi->tb = tb; 83 src_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); 84 src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); 85 src_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); 86 dest_bi->tb = tb; 87 dest_bi->bi_bh = tb->R[h]; 88 dest_bi->bi_parent = tb->FR[h]; 89 dest_bi->bi_position = get_right_neighbor_position (tb, h); 90 *d_key = tb->rkey[h]; 91 *cf = tb->CFR[h]; 92 break; 93 94 case INTERNAL_INSERT_TO_L: 95 dest_bi->tb = tb; 96 dest_bi->bi_bh = tb->L[h]; 97 dest_bi->bi_parent = tb->FL[h]; 98 dest_bi->bi_position = get_left_neighbor_position (tb, h); 99 break; 100 101 case INTERNAL_INSERT_TO_S: 102 dest_bi->tb = tb; 103 dest_bi->bi_bh = PATH_H_PBUFFER (tb->tb_path, h); 104 dest_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, h); 105 dest_bi->bi_position = PATH_H_POSITION (tb->tb_path, h + 1); 106 break; 107 108 case INTERNAL_INSERT_TO_R: 109 dest_bi->tb = tb; 110 dest_bi->bi_bh = tb->R[h]; 111 dest_bi->bi_parent = tb->FR[h]; 112 dest_bi->bi_position = get_right_neighbor_position (tb, h); 113 break; 114 115 default: 116 reiserfs_panic (tb->tb_sb, "internal_define_dest_src_infos: shift type is unknown (%d)", shift_mode); 117 } 118} 119 120 121 122/* Insert count node pointers into buffer cur before position to + 1. 123 * Insert count items into buffer cur before position to. 124 * Items and node pointers are specified by inserted and bh respectively. 125 */ 126static void internal_insert_childs (struct buffer_info * cur_bi, 127 int to, int count, 128 struct item_head * inserted, 129 struct buffer_head ** bh 130 ) 131{ 132 struct buffer_head * cur = cur_bi->bi_bh; 133 struct block_head * blkh; 134 int nr; 135 struct key * ih; 136 struct disk_child new_dc[2]; 137 struct disk_child * dc; 138 int i; 139 140 if (count <= 0) 141 return; 142 143 blkh = B_BLK_HEAD(cur); 144 nr = blkh_nr_item(blkh); 145 146 RFALSE( count > 2, 147 "too many children (%d) are to be inserted", count); 148 RFALSE( B_FREE_SPACE (cur) < count * (KEY_SIZE + DC_SIZE), 149 "no enough free space (%d), needed %d bytes", 150 B_FREE_SPACE (cur), count * (KEY_SIZE + DC_SIZE)); 151 152 /* prepare space for count disk_child */ 153 dc = B_N_CHILD(cur,to+1); 154 155 memmove (dc + count, dc, (nr+1-(to+1)) * DC_SIZE); 156 157 /* copy to_be_insert disk children */ 158 for (i = 0; i < count; i ++) { 159 put_dc_size( &(new_dc[i]), MAX_CHILD_SIZE(bh[i]) - B_FREE_SPACE(bh[i])); 160 put_dc_block_number( &(new_dc[i]), bh[i]->b_blocknr ); 161 } 162 memcpy (dc, new_dc, DC_SIZE * count); 163 164 165 /* prepare space for count items */ 166 ih = B_N_PDELIM_KEY (cur, ((to == -1) ? 0 : to)); 167 168 memmove (ih + count, ih, (nr - to) * KEY_SIZE + (nr + 1 + count) * DC_SIZE); 169 170 /* copy item headers (keys) */ 171 memcpy (ih, inserted, KEY_SIZE); 172 if ( count > 1 ) 173 memcpy (ih + 1, inserted + 1, KEY_SIZE); 174 175 /* sizes, item number */ 176 set_blkh_nr_item( blkh, blkh_nr_item(blkh) + count ); 177 set_blkh_free_space( blkh, 178 blkh_free_space(blkh) - count * (DC_SIZE + KEY_SIZE ) ); 179 180 do_balance_mark_internal_dirty (cur_bi->tb, cur,0); 181 182 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 183 check_internal (cur); 184 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 185 186 if (cur_bi->bi_parent) { 187 struct disk_child *t_dc = B_N_CHILD (cur_bi->bi_parent,cur_bi->bi_position); 188 put_dc_size( t_dc, dc_size(t_dc) + (count * (DC_SIZE + KEY_SIZE))); 189 do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent, 0); 190 191 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 192 check_internal (cur_bi->bi_parent); 193 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 194 } 195 196} 197 198 199/* Delete del_num items and node pointers from buffer cur starting from * 200 * the first_i'th item and first_p'th pointers respectively. */ 201static void internal_delete_pointers_items ( 202 struct buffer_info * cur_bi, 203 int first_p, 204 int first_i, 205 int del_num 206 ) 207{ 208 struct buffer_head * cur = cur_bi->bi_bh; 209 int nr; 210 struct block_head * blkh; 211 struct key * key; 212 struct disk_child * dc; 213 214 RFALSE( cur == NULL, "buffer is 0"); 215 RFALSE( del_num < 0, 216 "negative number of items (%d) can not be deleted", del_num); 217 RFALSE( first_p < 0 || first_p + del_num > B_NR_ITEMS (cur) + 1 || first_i < 0, 218 "first pointer order (%d) < 0 or " 219 "no so many pointers (%d), only (%d) or " 220 "first key order %d < 0", first_p, 221 first_p + del_num, B_NR_ITEMS (cur) + 1, first_i); 222 if ( del_num == 0 ) 223 return; 224 225 blkh = B_BLK_HEAD(cur); 226 nr = blkh_nr_item(blkh); 227 228 if ( first_p == 0 && del_num == nr + 1 ) { 229 RFALSE( first_i != 0, "1st deleted key must have order 0, not %d", first_i); 230 make_empty_node (cur_bi); 231 return; 232 } 233 234 RFALSE( first_i + del_num > B_NR_ITEMS (cur), 235 "first_i = %d del_num = %d " 236 "no so many keys (%d) in the node (%b)(%z)", 237 first_i, del_num, first_i + del_num, cur, cur); 238 239 240 /* deleting */ 241 dc = B_N_CHILD (cur, first_p); 242 243 memmove (dc, dc + del_num, (nr + 1 - first_p - del_num) * DC_SIZE); 244 key = B_N_PDELIM_KEY (cur, first_i); 245 memmove (key, key + del_num, (nr - first_i - del_num) * KEY_SIZE + (nr + 1 - del_num) * DC_SIZE); 246 247 248 /* sizes, item number */ 249 set_blkh_nr_item( blkh, blkh_nr_item(blkh) - del_num ); 250 set_blkh_free_space( blkh, 251 blkh_free_space(blkh) + (del_num * (KEY_SIZE + DC_SIZE) ) ); 252 253 do_balance_mark_internal_dirty (cur_bi->tb, cur, 0); 254 /*&&&&&&&&&&&&&&&&&&&&&&&*/ 255 check_internal (cur); 256 /*&&&&&&&&&&&&&&&&&&&&&&&*/ 257 258 if (cur_bi->bi_parent) { 259 struct disk_child *t_dc; 260 t_dc = B_N_CHILD (cur_bi->bi_parent, cur_bi->bi_position); 261 put_dc_size( t_dc, dc_size(t_dc) - (del_num * (KEY_SIZE + DC_SIZE) ) ); 262 263 do_balance_mark_internal_dirty (cur_bi->tb, cur_bi->bi_parent,0); 264 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 265 check_internal (cur_bi->bi_parent); 266 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 267 } 268} 269 270 271/* delete n node pointers and items starting from given position */ 272static void internal_delete_childs (struct buffer_info * cur_bi, 273 int from, int n) 274{ 275 int i_from; 276 277 i_from = (from == 0) ? from : from - 1; 278 279 /* delete n pointers starting from `from' position in CUR; 280 delete n keys starting from 'i_from' position in CUR; 281 */ 282 internal_delete_pointers_items (cur_bi, from, i_from, n); 283} 284 285 286/* copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer dest 287* last_first == FIRST_TO_LAST means, that we copy first items from src to tail of dest 288 * last_first == LAST_TO_FIRST means, that we copy last items from src to head of dest 289 */ 290static void internal_copy_pointers_items ( 291 struct buffer_info * dest_bi, 292 struct buffer_head * src, 293 int last_first, int cpy_num 294 ) 295{ 296 /* ATTENTION! Number of node pointers in DEST is equal to number of items in DEST * 297 * as delimiting key have already inserted to buffer dest.*/ 298 struct buffer_head * dest = dest_bi->bi_bh; 299 int nr_dest, nr_src; 300 int dest_order, src_order; 301 struct block_head * blkh; 302 struct key * key; 303 struct disk_child * dc; 304 305 nr_src = B_NR_ITEMS (src); 306 307 RFALSE( dest == NULL || src == NULL, 308 "src (%p) or dest (%p) buffer is 0", src, dest); 309 RFALSE( last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST, 310 "invalid last_first parameter (%d)", last_first); 311 RFALSE( nr_src < cpy_num - 1, 312 "no so many items (%d) in src (%d)", cpy_num, nr_src); 313 RFALSE( cpy_num < 0, "cpy_num less than 0 (%d)", cpy_num); 314 RFALSE( cpy_num - 1 + B_NR_ITEMS(dest) > (int)MAX_NR_KEY(dest), 315 "cpy_num (%d) + item number in dest (%d) can not be > MAX_NR_KEY(%d)", 316 cpy_num, B_NR_ITEMS(dest), MAX_NR_KEY(dest)); 317 318 if ( cpy_num == 0 ) 319 return; 320 321 /* coping */ 322 blkh = B_BLK_HEAD(dest); 323 nr_dest = blkh_nr_item(blkh); 324 325 /*dest_order = (last_first == LAST_TO_FIRST) ? 0 : nr_dest;*/ 326 /*src_order = (last_first == LAST_TO_FIRST) ? (nr_src - cpy_num + 1) : 0;*/ 327 (last_first == LAST_TO_FIRST) ? (dest_order = 0, src_order = nr_src - cpy_num + 1) : 328 (dest_order = nr_dest, src_order = 0); 329 330 /* prepare space for cpy_num pointers */ 331 dc = B_N_CHILD (dest, dest_order); 332 333 memmove (dc + cpy_num, dc, (nr_dest - dest_order) * DC_SIZE); 334 335 /* insert pointers */ 336 memcpy (dc, B_N_CHILD (src, src_order), DC_SIZE * cpy_num); 337 338 339 /* prepare space for cpy_num - 1 item headers */ 340 key = B_N_PDELIM_KEY(dest, dest_order); 341 memmove (key + cpy_num - 1, key, 342 KEY_SIZE * (nr_dest - dest_order) + DC_SIZE * (nr_dest + cpy_num)); 343 344 345 /* insert headers */ 346 memcpy (key, B_N_PDELIM_KEY (src, src_order), KEY_SIZE * (cpy_num - 1)); 347 348 /* sizes, item number */ 349 set_blkh_nr_item( blkh, blkh_nr_item(blkh) + (cpy_num - 1 ) ); 350 set_blkh_free_space( blkh, 351 blkh_free_space(blkh) - (KEY_SIZE * (cpy_num - 1) + DC_SIZE * cpy_num ) ); 352 353 do_balance_mark_internal_dirty (dest_bi->tb, dest, 0); 354 355 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 356 check_internal (dest); 357 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 358 359 if (dest_bi->bi_parent) { 360 struct disk_child *t_dc; 361 t_dc = B_N_CHILD(dest_bi->bi_parent,dest_bi->bi_position); 362 put_dc_size( t_dc, dc_size(t_dc) + (KEY_SIZE * (cpy_num - 1) + DC_SIZE * cpy_num) ); 363 364 do_balance_mark_internal_dirty (dest_bi->tb, dest_bi->bi_parent,0); 365 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 366 check_internal (dest_bi->bi_parent); 367 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 368 } 369 370} 371 372 373/* Copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer dest. 374 * Delete cpy_num - del_par items and node pointers from buffer src. 375 * last_first == FIRST_TO_LAST means, that we copy/delete first items from src. 376 * last_first == LAST_TO_FIRST means, that we copy/delete last items from src. 377 */ 378static void internal_move_pointers_items (struct buffer_info * dest_bi, 379 struct buffer_info * src_bi, 380 int last_first, int cpy_num, int del_par) 381{ 382 int first_pointer; 383 int first_item; 384 385 internal_copy_pointers_items (dest_bi, src_bi->bi_bh, last_first, cpy_num); 386 387 if (last_first == FIRST_TO_LAST) { /* shift_left occurs */ 388 first_pointer = 0; 389 first_item = 0; 390 /* delete cpy_num - del_par pointers and keys starting for pointers with first_pointer, 391 for key - with first_item */ 392 internal_delete_pointers_items (src_bi, first_pointer, first_item, cpy_num - del_par); 393 } else { /* shift_right occurs */ 394 int i, j; 395 396 i = ( cpy_num - del_par == ( j = B_NR_ITEMS(src_bi->bi_bh)) + 1 ) ? 0 : j - cpy_num + del_par; 397 398 internal_delete_pointers_items (src_bi, j + 1 - cpy_num + del_par, i, cpy_num - del_par); 399 } 400} 401 402/* Insert n_src'th key of buffer src before n_dest'th key of buffer dest. */ 403static void internal_insert_key (struct buffer_info * dest_bi, 404 int dest_position_before, /* insert key before key with n_dest number */ 405 struct buffer_head * src, 406 int src_position) 407{ 408 struct buffer_head * dest = dest_bi->bi_bh; 409 int nr; 410 struct block_head * blkh; 411 struct key * key; 412 413 RFALSE( dest == NULL || src == NULL, 414 "source(%p) or dest(%p) buffer is 0", src, dest); 415 RFALSE( dest_position_before < 0 || src_position < 0, 416 "source(%d) or dest(%d) key number less than 0", 417 src_position, dest_position_before); 418 RFALSE( dest_position_before > B_NR_ITEMS (dest) || 419 src_position >= B_NR_ITEMS(src), 420 "invalid position in dest (%d (key number %d)) or in src (%d (key number %d))", 421 dest_position_before, B_NR_ITEMS (dest), 422 src_position, B_NR_ITEMS(src)); 423 RFALSE( B_FREE_SPACE (dest) < KEY_SIZE, 424 "no enough free space (%d) in dest buffer", B_FREE_SPACE (dest)); 425 426 blkh = B_BLK_HEAD(dest); 427 nr = blkh_nr_item(blkh); 428 429 /* prepare space for inserting key */ 430 key = B_N_PDELIM_KEY (dest, dest_position_before); 431 memmove (key + 1, key, (nr - dest_position_before) * KEY_SIZE + (nr + 1) * DC_SIZE); 432 433 /* insert key */ 434 memcpy (key, B_N_PDELIM_KEY(src, src_position), KEY_SIZE); 435 436 /* Change dirt, free space, item number fields. */ 437 438 set_blkh_nr_item( blkh, blkh_nr_item(blkh) + 1 ); 439 set_blkh_free_space( blkh, blkh_free_space(blkh) - KEY_SIZE ); 440 441 do_balance_mark_internal_dirty (dest_bi->tb, dest, 0); 442 443 if (dest_bi->bi_parent) { 444 struct disk_child *t_dc; 445 t_dc = B_N_CHILD(dest_bi->bi_parent,dest_bi->bi_position); 446 put_dc_size( t_dc, dc_size(t_dc) + KEY_SIZE ); 447 448 do_balance_mark_internal_dirty (dest_bi->tb, dest_bi->bi_parent,0); 449 } 450} 451 452 453 454/* Insert d_key'th (delimiting) key from buffer cfl to tail of dest. 455 * Copy pointer_amount node pointers and pointer_amount - 1 items from buffer src to buffer dest. 456 * Replace d_key'th key in buffer cfl. 457 * Delete pointer_amount items and node pointers from buffer src. 458 */ 459/* this can be invoked both to shift from S to L and from R to S */ 460static void internal_shift_left ( 461 int mode, /* INTERNAL_FROM_S_TO_L | INTERNAL_FROM_R_TO_S */ 462 struct tree_balance * tb, 463 int h, 464 int pointer_amount 465 ) 466{ 467 struct buffer_info dest_bi, src_bi; 468 struct buffer_head * cf; 469 int d_key_position; 470 471 internal_define_dest_src_infos (mode, tb, h, &dest_bi, &src_bi, &d_key_position, &cf); 472 473 /*printk("pointer_amount = %d\n",pointer_amount);*/ 474 475 if (pointer_amount) { 476 /* insert delimiting key from common father of dest and src to node dest into position B_NR_ITEM(dest) */ 477 internal_insert_key (&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf, d_key_position); 478 479 if (B_NR_ITEMS(src_bi.bi_bh) == pointer_amount - 1) { 480 if (src_bi.bi_position/*src->b_item_order*/ == 0) 481 replace_key (tb, cf, d_key_position, src_bi.bi_parent/*src->b_parent*/, 0); 482 } else 483 replace_key (tb, cf, d_key_position, src_bi.bi_bh, pointer_amount - 1); 484 } 485 /* last parameter is del_parameter */ 486 internal_move_pointers_items (&dest_bi, &src_bi, FIRST_TO_LAST, pointer_amount, 0); 487 488} 489 490/* Insert delimiting key to L[h]. 491 * Copy n node pointers and n - 1 items from buffer S[h] to L[h]. 492 * Delete n - 1 items and node pointers from buffer S[h]. 493 */ 494/* it always shifts from S[h] to L[h] */ 495static void internal_shift1_left ( 496 struct tree_balance * tb, 497 int h, 498 int pointer_amount 499 ) 500{ 501 struct buffer_info dest_bi, src_bi; 502 struct buffer_head * cf; 503 int d_key_position; 504 505 internal_define_dest_src_infos (INTERNAL_SHIFT_FROM_S_TO_L, tb, h, &dest_bi, &src_bi, &d_key_position, &cf); 506 507 if ( pointer_amount > 0 ) /* insert lkey[h]-th key from CFL[h] to left neighbor L[h] */ 508 internal_insert_key (&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf, d_key_position); 509 /* internal_insert_key (tb->L[h], B_NR_ITEM(tb->L[h]), tb->CFL[h], tb->lkey[h]);*/ 510 511 /* last parameter is del_parameter */ 512 internal_move_pointers_items (&dest_bi, &src_bi, FIRST_TO_LAST, pointer_amount, 1); 513 /* internal_move_pointers_items (tb->L[h], tb->S[h], FIRST_TO_LAST, pointer_amount, 1);*/ 514} 515 516 517/* Insert d_key'th (delimiting) key from buffer cfr to head of dest. 518 * Copy n node pointers and n - 1 items from buffer src to buffer dest. 519 * Replace d_key'th key in buffer cfr. 520 * Delete n items and node pointers from buffer src. 521 */ 522static void internal_shift_right ( 523 int mode, /* INTERNAL_FROM_S_TO_R | INTERNAL_FROM_L_TO_S */ 524 struct tree_balance * tb, 525 int h, 526 int pointer_amount 527 ) 528{ 529 struct buffer_info dest_bi, src_bi; 530 struct buffer_head * cf; 531 int d_key_position; 532 int nr; 533 534 535 internal_define_dest_src_infos (mode, tb, h, &dest_bi, &src_bi, &d_key_position, &cf); 536 537 nr = B_NR_ITEMS (src_bi.bi_bh); 538 539 if (pointer_amount > 0) { 540 /* insert delimiting key from common father of dest and src to dest node into position 0 */ 541 internal_insert_key (&dest_bi, 0, cf, d_key_position); 542 if (nr == pointer_amount - 1) { 543 RFALSE( src_bi.bi_bh != PATH_H_PBUFFER (tb->tb_path, h)/*tb->S[h]*/ || 544 dest_bi.bi_bh != tb->R[h], 545 "src (%p) must be == tb->S[h](%p) when it disappears", 546 src_bi.bi_bh, PATH_H_PBUFFER (tb->tb_path, h)); 547 /* when S[h] disappers replace left delemiting key as well */ 548 if (tb->CFL[h]) 549 replace_key (tb, cf, d_key_position, tb->CFL[h], tb->lkey[h]); 550 } else 551 replace_key (tb, cf, d_key_position, src_bi.bi_bh, nr - pointer_amount); 552 } 553 554 /* last parameter is del_parameter */ 555 internal_move_pointers_items (&dest_bi, &src_bi, LAST_TO_FIRST, pointer_amount, 0); 556} 557 558/* Insert delimiting key to R[h]. 559 * Copy n node pointers and n - 1 items from buffer S[h] to R[h]. 560 * Delete n - 1 items and node pointers from buffer S[h]. 561 */ 562/* it always shift from S[h] to R[h] */ 563static void internal_shift1_right ( 564 struct tree_balance * tb, 565 int h, 566 int pointer_amount 567 ) 568{ 569 struct buffer_info dest_bi, src_bi; 570 struct buffer_head * cf; 571 int d_key_position; 572 573 internal_define_dest_src_infos (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, &dest_bi, &src_bi, &d_key_position, &cf); 574 575 if (pointer_amount > 0) /* insert rkey from CFR[h] to right neighbor R[h] */ 576 internal_insert_key (&dest_bi, 0, cf, d_key_position); 577 /* internal_insert_key (tb->R[h], 0, tb->CFR[h], tb->rkey[h]);*/ 578 579 /* last parameter is del_parameter */ 580 internal_move_pointers_items (&dest_bi, &src_bi, LAST_TO_FIRST, pointer_amount, 1); 581 /* internal_move_pointers_items (tb->R[h], tb->S[h], LAST_TO_FIRST, pointer_amount, 1);*/ 582} 583 584 585/* Delete insert_num node pointers together with their left items 586 * and balance current node.*/ 587static void balance_internal_when_delete (struct tree_balance * tb, 588 int h, int child_pos) 589{ 590 int insert_num; 591 int n; 592 struct buffer_head * tbSh = PATH_H_PBUFFER (tb->tb_path, h); 593 struct buffer_info bi; 594 595 insert_num = tb->insert_size[h] / ((int)(DC_SIZE + KEY_SIZE)); 596 597 /* delete child-node-pointer(s) together with their left item(s) */ 598 bi.tb = tb; 599 bi.bi_bh = tbSh; 600 bi.bi_parent = PATH_H_PPARENT (tb->tb_path, h); 601 bi.bi_position = PATH_H_POSITION (tb->tb_path, h + 1); 602 603 internal_delete_childs (&bi, child_pos, -insert_num); 604 605 RFALSE( tb->blknum[h] > 1, 606 "tb->blknum[%d]=%d when insert_size < 0", h, tb->blknum[h]); 607 608 n = B_NR_ITEMS(tbSh); 609 610 if ( tb->lnum[h] == 0 && tb->rnum[h] == 0 ) { 611 if ( tb->blknum[h] == 0 ) { 612 /* node S[h] (root of the tree) is empty now */ 613 struct buffer_head *new_root; 614 615 RFALSE( n || B_FREE_SPACE (tbSh) != MAX_CHILD_SIZE(tbSh) - DC_SIZE, 616 "buffer must have only 0 keys (%d)", n); 617 RFALSE( bi.bi_parent, "root has parent (%p)", bi.bi_parent); 618 619 /* choose a new root */ 620 if ( ! tb->L[h-1] || ! B_NR_ITEMS(tb->L[h-1]) ) 621 new_root = tb->R[h-1]; 622 else 623 new_root = tb->L[h-1]; 624 /* switch super block's tree root block number to the new value */ 625 PUT_SB_ROOT_BLOCK( tb->tb_sb, new_root->b_blocknr ); 626 //tb->tb_sb->u.reiserfs_sb.s_rs->s_tree_height --; 627 PUT_SB_TREE_HEIGHT( tb->tb_sb, SB_TREE_HEIGHT(tb->tb_sb) - 1 ); 628 629 do_balance_mark_sb_dirty (tb, tb->tb_sb->u.reiserfs_sb.s_sbh, 1); 630 /*&&&&&&&&&&&&&&&&&&&&&&*/ 631 if (h > 1) 632 /* use check_internal if new root is an internal node */ 633 check_internal (new_root); 634 /*&&&&&&&&&&&&&&&&&&&&&&*/ 635 tb->tb_sb->s_dirt = 1; 636 637 /* do what is needed for buffer thrown from tree */ 638 reiserfs_invalidate_buffer(tb, tbSh); 639 return; 640 } 641 return; 642 } 643 644 if ( tb->L[h] && tb->lnum[h] == -B_NR_ITEMS(tb->L[h]) - 1 ) { /* join S[h] with L[h] */ 645 646 RFALSE( tb->rnum[h] != 0, 647 "invalid tb->rnum[%d]==%d when joining S[h] with L[h]", 648 h, tb->rnum[h]); 649 650 internal_shift_left (INTERNAL_SHIFT_FROM_S_TO_L, tb, h, n + 1); 651 reiserfs_invalidate_buffer(tb, tbSh); 652 653 return; 654 } 655 656 if ( tb->R[h] && tb->rnum[h] == -B_NR_ITEMS(tb->R[h]) - 1 ) { /* join S[h] with R[h] */ 657 RFALSE( tb->lnum[h] != 0, 658 "invalid tb->lnum[%d]==%d when joining S[h] with R[h]", 659 h, tb->lnum[h]); 660 661 internal_shift_right (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, n + 1); 662 663 reiserfs_invalidate_buffer(tb,tbSh); 664 return; 665 } 666 667 if ( tb->lnum[h] < 0 ) { /* borrow from left neighbor L[h] */ 668 RFALSE( tb->rnum[h] != 0, 669 "wrong tb->rnum[%d]==%d when borrow from L[h]", h, tb->rnum[h]); 670 /*internal_shift_right (tb, h, tb->L[h], tb->CFL[h], tb->lkey[h], tb->S[h], -tb->lnum[h]);*/ 671 internal_shift_right (INTERNAL_SHIFT_FROM_L_TO_S, tb, h, -tb->lnum[h]); 672 return; 673 } 674 675 if ( tb->rnum[h] < 0 ) { /* borrow from right neighbor R[h] */ 676 RFALSE( tb->lnum[h] != 0, 677 "invalid tb->lnum[%d]==%d when borrow from R[h]", 678 h, tb->lnum[h]); 679 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]);*/ 680 return; 681 } 682 683 if ( tb->lnum[h] > 0 ) { /* split S[h] into two parts and put them into neighbors */ 684 RFALSE( tb->rnum[h] == 0 || tb->lnum[h] + tb->rnum[h] != n + 1, 685 "invalid tb->lnum[%d]==%d or tb->rnum[%d]==%d when S[h](item number == %d) is split between them", 686 h, tb->lnum[h], h, tb->rnum[h], n); 687 688 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]);*/ 689 internal_shift_right (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, tb->rnum[h]); 690 691 reiserfs_invalidate_buffer (tb, tbSh); 692 693 return; 694 } 695 reiserfs_panic (tb->tb_sb, "balance_internal_when_delete: unexpected tb->lnum[%d]==%d or tb->rnum[%d]==%d", 696 h, tb->lnum[h], h, tb->rnum[h]); 697} 698 699 700/* Replace delimiting key of buffers L[h] and S[h] by the given key.*/ 701void replace_lkey ( 702 struct tree_balance * tb, 703 int h, 704 struct item_head * key 705 ) 706{ 707 RFALSE( tb->L[h] == NULL || tb->CFL[h] == NULL, 708 "L[h](%p) and CFL[h](%p) must exist in replace_lkey", 709 tb->L[h], tb->CFL[h]); 710 711 if (B_NR_ITEMS(PATH_H_PBUFFER(tb->tb_path, h)) == 0) 712 return; 713 714 memcpy (B_N_PDELIM_KEY(tb->CFL[h],tb->lkey[h]), key, KEY_SIZE); 715 716 do_balance_mark_internal_dirty (tb, tb->CFL[h],0); 717} 718 719 720/* Replace delimiting key of buffers S[h] and R[h] by the given key.*/ 721void replace_rkey ( 722 struct tree_balance * tb, 723 int h, 724 struct item_head * key 725 ) 726{ 727 RFALSE( tb->R[h] == NULL || tb->CFR[h] == NULL, 728 "R[h](%p) and CFR[h](%p) must exist in replace_rkey", 729 tb->R[h], tb->CFR[h]); 730 RFALSE( B_NR_ITEMS(tb->R[h]) == 0, 731 "R[h] can not be empty if it exists (item number=%d)", 732 B_NR_ITEMS(tb->R[h])); 733 734 memcpy (B_N_PDELIM_KEY(tb->CFR[h],tb->rkey[h]), key, KEY_SIZE); 735 736 do_balance_mark_internal_dirty (tb, tb->CFR[h], 0); 737} 738 739 740int balance_internal (struct tree_balance * tb, /* tree_balance structure */ 741 int h, /* level of the tree */ 742 int child_pos, 743 struct item_head * insert_key, /* key for insertion on higher level */ 744 struct buffer_head ** insert_ptr /* node for insertion on higher level*/ 745 ) 746 /* if inserting/pasting 747 { 748 child_pos is the position of the node-pointer in S[h] that * 749 pointed to S[h-1] before balancing of the h-1 level; * 750 this means that new pointers and items must be inserted AFTER * 751 child_pos 752 } 753 else 754 { 755 it is the position of the leftmost pointer that must be deleted (together with 756 its corresponding key to the left of the pointer) 757 as a result of the previous level's balancing. 758 } 759*/ 760{ 761 struct buffer_head * tbSh = PATH_H_PBUFFER (tb->tb_path, h); 762 struct buffer_info bi; 763 int order; /* we return this: it is 0 if there is no S[h], else it is tb->S[h]->b_item_order */ 764 int insert_num, n, k; 765 struct buffer_head * S_new; 766 struct item_head new_insert_key; 767 struct buffer_head * new_insert_ptr = NULL; 768 struct item_head * new_insert_key_addr = insert_key; 769 770 RFALSE( h < 1, "h (%d) can not be < 1 on internal level", h); 771 772 PROC_INFO_INC( tb -> tb_sb, balance_at[ h ] ); 773 774 order = ( tbSh ) ? PATH_H_POSITION (tb->tb_path, h + 1)/*tb->S[h]->b_item_order*/ : 0; 775 776 /* Using insert_size[h] calculate the number insert_num of items 777 that must be inserted to or deleted from S[h]. */ 778 insert_num = tb->insert_size[h]/((int)(KEY_SIZE + DC_SIZE)); 779 780 /* Check whether insert_num is proper **/ 781 RFALSE( insert_num < -2 || insert_num > 2, 782 "incorrect number of items inserted to the internal node (%d)", 783 insert_num); 784 RFALSE( h > 1 && (insert_num > 1 || insert_num < -1), 785 "incorrect number of items (%d) inserted to the internal node on a level (h=%d) higher than last internal level", 786 insert_num, h); 787 788 /* Make balance in case insert_num < 0 */ 789 if ( insert_num < 0 ) { 790 balance_internal_when_delete (tb, h, child_pos); 791 return order; 792 } 793 794 k = 0; 795 if ( tb->lnum[h] > 0 ) { 796 /* shift lnum[h] items from S[h] to the left neighbor L[h]. 797 check how many of new items fall into L[h] or CFL[h] after 798 shifting */ 799 n = B_NR_ITEMS (tb->L[h]); /* number of items in L[h] */ 800 if ( tb->lnum[h] <= child_pos ) { 801 /* new items don't fall into L[h] or CFL[h] */ 802 internal_shift_left (INTERNAL_SHIFT_FROM_S_TO_L, tb, h, tb->lnum[h]); 803 /*internal_shift_left (tb->L[h],tb->CFL[h],tb->lkey[h],tbSh,tb->lnum[h]);*/ 804 child_pos -= tb->lnum[h]; 805 } else if ( tb->lnum[h] > child_pos + insert_num ) { 806 /* all new items fall into L[h] */ 807 internal_shift_left (INTERNAL_SHIFT_FROM_S_TO_L, tb, h, tb->lnum[h] - insert_num); 808 /* internal_shift_left(tb->L[h],tb->CFL[h],tb->lkey[h],tbSh, 809 tb->lnum[h]-insert_num); 810 */ 811 /* insert insert_num keys and node-pointers into L[h] */ 812 bi.tb = tb; 813 bi.bi_bh = tb->L[h]; 814 bi.bi_parent = tb->FL[h]; 815 bi.bi_position = get_left_neighbor_position (tb, h); 816 internal_insert_childs (&bi,/*tb->L[h], tb->S[h-1]->b_next*/ n + child_pos + 1, 817 insert_num,insert_key,insert_ptr); 818 819 insert_num = 0; 820 } else { 821 struct disk_child * dc; 822 823 /* some items fall into L[h] or CFL[h], but some don't fall */ 824 internal_shift1_left(tb,h,child_pos+1); 825 /* calculate number of new items that fall into L[h] */ 826 k = tb->lnum[h] - child_pos - 1; 827 bi.tb = tb; 828 bi.bi_bh = tb->L[h]; 829 bi.bi_parent = tb->FL[h]; 830 bi.bi_position = get_left_neighbor_position (tb, h); 831 internal_insert_childs (&bi,/*tb->L[h], tb->S[h-1]->b_next,*/ n + child_pos + 1,k, 832 insert_key,insert_ptr); 833 834 replace_lkey(tb,h,insert_key + k); 835 836 /* replace the first node-ptr in S[h] by node-ptr to insert_ptr[k] */ 837 dc = B_N_CHILD(tbSh, 0); 838 put_dc_size( dc, MAX_CHILD_SIZE(insert_ptr[k]) - B_FREE_SPACE (insert_ptr[k])); 839 put_dc_block_number( dc, insert_ptr[k]->b_blocknr ); 840 841 do_balance_mark_internal_dirty (tb, tbSh, 0); 842 843 k++; 844 insert_key += k; 845 insert_ptr += k; 846 insert_num -= k; 847 child_pos = 0; 848 } 849 } /* tb->lnum[h] > 0 */ 850 851 if ( tb->rnum[h] > 0 ) { 852 /*shift rnum[h] items from S[h] to the right neighbor R[h]*/ 853 /* check how many of new items fall into R or CFR after shifting */ 854 n = B_NR_ITEMS (tbSh); /* number of items in S[h] */ 855 if ( n - tb->rnum[h] >= child_pos ) 856 /* new items fall into S[h] */ 857 /*internal_shift_right(tb,h,tbSh,tb->CFR[h],tb->rkey[h],tb->R[h],tb->rnum[h]);*/ 858 internal_shift_right (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, tb->rnum[h]); 859 else 860 if ( n + insert_num - tb->rnum[h] < child_pos ) 861 { 862 /* all new items fall into R[h] */ 863 /*internal_shift_right(tb,h,tbSh,tb->CFR[h],tb->rkey[h],tb->R[h], 864 tb->rnum[h] - insert_num);*/ 865 internal_shift_right (INTERNAL_SHIFT_FROM_S_TO_R, tb, h, tb->rnum[h] - insert_num); 866 867 /* insert insert_num keys and node-pointers into R[h] */ 868 bi.tb = tb; 869 bi.bi_bh = tb->R[h]; 870 bi.bi_parent = tb->FR[h]; 871 bi.bi_position = get_right_neighbor_position (tb, h); 872 internal_insert_childs (&bi, /*tb->R[h],tb->S[h-1]->b_next*/ child_pos - n - insert_num + tb->rnum[h] - 1, 873 insert_num,insert_key,insert_ptr); 874 insert_num = 0; 875 } 876 else 877 { 878 struct disk_child * dc; 879 880 /* one of the items falls into CFR[h] */ 881 internal_shift1_right(tb,h,n - child_pos + 1); 882 /* calculate number of new items that fall into R[h] */ 883 k = tb->rnum[h] - n + child_pos - 1; 884 bi.tb = tb; 885 bi.bi_bh = tb->R[h]; 886 bi.bi_parent = tb->FR[h]; 887 bi.bi_position = get_right_neighbor_position (tb, h); 888 internal_insert_childs (&bi, /*tb->R[h], tb->R[h]->b_child,*/ 0, k, insert_key + 1, insert_ptr + 1); 889 890 replace_rkey(tb,h,insert_key + insert_num - k - 1); 891 892 /* replace the first node-ptr in R[h] by node-ptr insert_ptr[insert_num-k-1]*/ 893 dc = B_N_CHILD(tb->R[h], 0); 894 put_dc_size( dc, MAX_CHILD_SIZE(insert_ptr[insert_num-k-1]) - 895 B_FREE_SPACE (insert_ptr[insert_num-k-1])); 896 put_dc_block_number( dc, insert_ptr[insert_num-k-1]->b_blocknr ); 897 898 do_balance_mark_internal_dirty (tb, tb->R[h],0); 899 900 insert_num -= (k + 1); 901 } 902 } 903 904 /** Fill new node that appears instead of S[h] **/ 905 RFALSE( tb->blknum[h] > 2, "blknum can not be > 2 for internal level"); 906 RFALSE( tb->blknum[h] < 0, "blknum can not be < 0"); 907 908 if ( ! tb->blknum[h] ) 909 { /* node S[h] is empty now */ 910 RFALSE( ! tbSh, "S[h] is equal NULL"); 911 912 /* do what is needed for buffer thrown from tree */ 913 reiserfs_invalidate_buffer(tb,tbSh); 914 return order; 915 } 916 917 if ( ! tbSh ) { 918 /* create new root */ 919 struct disk_child * dc; 920 struct buffer_head * tbSh_1 = PATH_H_PBUFFER (tb->tb_path, h - 1); 921 struct block_head * blkh; 922 923 924 if ( tb->blknum[h] != 1 ) 925 reiserfs_panic(0, "balance_internal: One new node required for creating the new root"); 926 /* S[h] = empty buffer from the list FEB. */ 927 tbSh = get_FEB (tb); 928 blkh = B_BLK_HEAD(tbSh); 929 set_blkh_level( blkh, h + 1 ); 930 931 /* Put the unique node-pointer to S[h] that points to S[h-1]. */ 932 933 dc = B_N_CHILD(tbSh, 0); 934 put_dc_block_number( dc, tbSh_1->b_blocknr ); 935 put_dc_size( dc, (MAX_CHILD_SIZE (tbSh_1) - B_FREE_SPACE (tbSh_1))); 936 937 tb->insert_size[h] -= DC_SIZE; 938 set_blkh_free_space( blkh, blkh_free_space(blkh) - DC_SIZE ); 939 940 do_balance_mark_internal_dirty (tb, tbSh, 0); 941 942 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 943 check_internal (tbSh); 944 /*&&&&&&&&&&&&&&&&&&&&&&&&*/ 945 946 /* put new root into path structure */ 947 PATH_OFFSET_PBUFFER(tb->tb_path, ILLEGAL_PATH_ELEMENT_OFFSET) = tbSh; 948 949 /* Change root in structure super block. */ 950 PUT_SB_ROOT_BLOCK( tb->tb_sb, tbSh->b_blocknr ); 951 PUT_SB_TREE_HEIGHT( tb->tb_sb, SB_TREE_HEIGHT(tb->tb_sb) + 1 ); 952 do_balance_mark_sb_dirty (tb, tb->tb_sb->u.reiserfs_sb.s_sbh, 1); 953 tb->tb_sb->s_dirt = 1; 954 } 955 956 if ( tb->blknum[h] == 2 ) { 957 int snum; 958 struct buffer_info dest_bi, src_bi; 959 960 961 /* S_new = free buffer from list FEB */ 962 S_new = get_FEB(tb); 963 964 set_blkh_level( B_BLK_HEAD(S_new), h + 1 ); 965 966 dest_bi.tb = tb; 967 dest_bi.bi_bh = S_new; 968 dest_bi.bi_parent = 0; 969 dest_bi.bi_position = 0; 970 src_bi.tb = tb; 971 src_bi.bi_bh = tbSh; 972 src_bi.bi_parent = PATH_H_PPARENT (tb->tb_path, h); 973 src_bi.bi_position = PATH_H_POSITION (tb->tb_path, h + 1); 974 975 n = B_NR_ITEMS (tbSh); /* number of items in S[h] */ 976 snum = (insert_num + n + 1)/2; 977 if ( n - snum >= child_pos ) { 978 /* new items don't fall into S_new */ 979 /* store the delimiting key for the next level */ 980 /* new_insert_key = (n - snum)'th key in S[h] */ 981 memcpy (&new_insert_key,B_N_PDELIM_KEY(tbSh,n - snum), 982 KEY_SIZE); 983 /* last parameter is del_par */ 984 internal_move_pointers_items (&dest_bi, &src_bi, LAST_TO_FIRST, snum, 0); 985 /* internal_move_pointers_items(S_new, tbSh, LAST_TO_FIRST, snum, 0);*/ 986 } else if ( n + insert_num - snum < child_pos ) { 987 /* all new items fall into S_new */ 988 /* store the delimiting key for the next level */ 989 /* new_insert_key = (n + insert_item - snum)'th key in S[h] */ 990 memcpy(&new_insert_key,B_N_PDELIM_KEY(tbSh,n + insert_num - snum), 991 KEY_SIZE); 992 /* last parameter is del_par */ 993 internal_move_pointers_items (&dest_bi, &src_bi, LAST_TO_FIRST, snum - insert_num, 0); 994 /* internal_move_pointers_items(S_new,tbSh,1,snum - insert_num,0);*/ 995 996 /* insert insert_num keys and node-pointers into S_new */ 997 internal_insert_childs (&dest_bi, /*S_new,tb->S[h-1]->b_next,*/child_pos - n - insert_num + snum - 1, 998 insert_num,insert_key,insert_ptr); 999 1000 insert_num = 0; 1001 } else { 1002 struct disk_child * dc; 1003 1004 /* some items fall into S_new, but some don't fall */ 1005 /* last parameter is del_par */ 1006 internal_move_pointers_items (&dest_bi, &src_bi, LAST_TO_FIRST, n - child_pos + 1, 1); 1007 /* internal_move_pointers_items(S_new,tbSh,1,n - child_pos + 1,1);*/ 1008 /* calculate number of new items that fall into S_new */ 1009 k = snum - n + child_pos - 1; 1010 1011 internal_insert_childs (&dest_bi, /*S_new,*/ 0, k, insert_key + 1, insert_ptr+1); 1012 1013 /* new_insert_key = insert_key[insert_num - k - 1] */ 1014 memcpy(&new_insert_key,insert_key + insert_num - k - 1, 1015 KEY_SIZE); 1016 /* replace first node-ptr in S_new by node-ptr to insert_ptr[insert_num-k-1] */ 1017 1018 dc = B_N_CHILD(S_new,0); 1019 put_dc_size( dc, (MAX_CHILD_SIZE(insert_ptr[insert_num-k-1]) - 1020 B_FREE_SPACE(insert_ptr[insert_num-k-1])) ); 1021 put_dc_block_number( dc, insert_ptr[insert_num-k-1]->b_blocknr ); 1022 1023 do_balance_mark_internal_dirty (tb, S_new,0); 1024 1025 insert_num -= (k + 1); 1026 } 1027 /* new_insert_ptr = node_pointer to S_new */ 1028 new_insert_ptr = S_new; 1029 1030 RFALSE(( buffer_locked(S_new) || atomic_read (&(S_new->b_count)) != 1) && 1031 (buffer_locked(S_new) || atomic_read(&(S_new->b_count)) > 2 || 1032 !(buffer_journaled(S_new) || buffer_journal_dirty(S_new))), 1033 "cm-00001: bad S_new (%b)", S_new); 1034 1035 // S_new is released in unfix_nodes 1036 } 1037 1038 n = B_NR_ITEMS (tbSh); /*number of items in S[h] */ 1039 1040 if ( 0 <= child_pos && child_pos <= n && insert_num > 0 ) { 1041 bi.tb = tb; 1042 bi.bi_bh = tbSh; 1043 bi.bi_parent = PATH_H_PPARENT (tb->tb_path, h); 1044 bi.bi_position = PATH_H_POSITION (tb->tb_path, h + 1); 1045 internal_insert_childs ( 1046 &bi,/*tbSh,*/ 1047 /* ( tb->S[h-1]->b_parent == tb->S[h] ) ? tb->S[h-1]->b_next : tb->S[h]->b_child->b_next,*/ 1048 child_pos,insert_num,insert_key,insert_ptr 1049 ); 1050 } 1051 1052 1053 memcpy (new_insert_key_addr,&new_insert_key,KEY_SIZE); 1054 insert_ptr[0] = new_insert_ptr; 1055 1056 return order; 1057 } 1058 1059 1060 1061