1 /*- 2 * Copyright (c) 1990, 1993, 1994 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Mike Olson. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * @(#)bt_split.c 8.9 (Berkeley) 7/26/94 37 */ 38 39 #include <sys/types.h> 40 41 #include <limits.h> 42 #include <stdio.h> 43 #include <stdlib.h> 44 #include <string.h> 45 46 #include <db.h> 47 #include "btree.h" 48 49 static int bt_broot __P((BTREE *, PAGE *, PAGE *, PAGE *)); 50 static PAGE *bt_page 51 __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t)); 52 static int bt_preserve __P((BTREE *, pgno_t)); 53 static PAGE *bt_psplit 54 __P((BTREE *, PAGE *, PAGE *, PAGE *, indx_t *, size_t)); 55 static PAGE *bt_root 56 __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t)); 57 static int bt_rroot __P((BTREE *, PAGE *, PAGE *, PAGE *)); 58 static recno_t rec_total __P((PAGE *)); 59 60 #ifdef STATISTICS 61 u_long bt_rootsplit, bt_split, bt_sortsplit, bt_pfxsaved; 62 #endif 63 64 /* 65 * __BT_SPLIT -- Split the tree. 66 * 67 * Parameters: 68 * t: tree 69 * sp: page to split 70 * key: key to insert 71 * data: data to insert 72 * flags: BIGKEY/BIGDATA flags 73 * ilen: insert length 74 * skip: index to leave open 75 * 76 * Returns: 77 * RET_ERROR, RET_SUCCESS 78 */ 79 int 80 __bt_split(t, sp, key, data, flags, ilen, argskip) 81 BTREE *t; 82 PAGE *sp; 83 const DBT *key, *data; 84 int flags; 85 size_t ilen; 86 u_int32_t argskip; 87 { 88 BINTERNAL *bi; 89 BLEAF *bl, *tbl; 90 DBT a, b; 91 EPGNO *parent; 92 PAGE *h, *l, *r, *lchild, *rchild; 93 indx_t nxtindex; 94 u_int16_t skip; 95 u_int32_t n, nbytes, nksize; 96 int parentsplit; 97 char *dest; 98 99 /* 100 * Split the page into two pages, l and r. The split routines return 101 * a pointer to the page into which the key should be inserted and with 102 * skip set to the offset which should be used. Additionally, l and r 103 * are pinned. 104 */ 105 skip = argskip; 106 h = sp->pgno == P_ROOT ? 107 bt_root(t, sp, &l, &r, &skip, ilen) : 108 bt_page(t, sp, &l, &r, &skip, ilen); 109 if (h == NULL) 110 return (RET_ERROR); 111 112 /* 113 * Insert the new key/data pair into the leaf page. (Key inserts 114 * always cause a leaf page to split first.) 115 */ 116 h->linp[skip] = h->upper -= ilen; 117 dest = (char *)h + h->upper; 118 if (F_ISSET(t, R_RECNO)) 119 WR_RLEAF(dest, data, flags) 120 else 121 WR_BLEAF(dest, key, data, flags) 122 123 /* If the root page was split, make it look right. */ 124 if (sp->pgno == P_ROOT && 125 (F_ISSET(t, R_RECNO) ? 126 bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR) 127 goto err2; 128 129 /* 130 * Now we walk the parent page stack -- a LIFO stack of the pages that 131 * were traversed when we searched for the page that split. Each stack 132 * entry is a page number and a page index offset. The offset is for 133 * the page traversed on the search. We've just split a page, so we 134 * have to insert a new key into the parent page. 135 * 136 * If the insert into the parent page causes it to split, may have to 137 * continue splitting all the way up the tree. We stop if the root 138 * splits or the page inserted into didn't have to split to hold the 139 * new key. Some algorithms replace the key for the old page as well 140 * as the new page. We don't, as there's no reason to believe that the 141 * first key on the old page is any better than the key we have, and, 142 * in the case of a key being placed at index 0 causing the split, the 143 * key is unavailable. 144 * 145 * There are a maximum of 5 pages pinned at any time. We keep the left 146 * and right pages pinned while working on the parent. The 5 are the 147 * two children, left parent and right parent (when the parent splits) 148 * and the root page or the overflow key page when calling bt_preserve. 149 * This code must make sure that all pins are released other than the 150 * root page or overflow page which is unlocked elsewhere. 151 */ 152 while ((parent = BT_POP(t)) != NULL) { 153 lchild = l; 154 rchild = r; 155 156 /* Get the parent page. */ 157 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 158 goto err2; 159 160 /* 161 * The new key goes ONE AFTER the index, because the split 162 * was to the right. 163 */ 164 skip = parent->index + 1; 165 166 /* 167 * Calculate the space needed on the parent page. 168 * 169 * Prefix trees: space hack when inserting into BINTERNAL 170 * pages. Retain only what's needed to distinguish between 171 * the new entry and the LAST entry on the page to its left. 172 * If the keys compare equal, retain the entire key. Note, 173 * we don't touch overflow keys, and the entire key must be 174 * retained for the next-to-left most key on the leftmost 175 * page of each level, or the search will fail. Applicable 176 * ONLY to internal pages that have leaf pages as children. 177 * Further reduction of the key between pairs of internal 178 * pages loses too much information. 179 */ 180 switch (rchild->flags & P_TYPE) { 181 case P_BINTERNAL: 182 bi = GETBINTERNAL(rchild, 0); 183 nbytes = NBINTERNAL(bi->ksize); 184 break; 185 case P_BLEAF: 186 bl = GETBLEAF(rchild, 0); 187 nbytes = NBINTERNAL(bl->ksize); 188 if (t->bt_pfx && !(bl->flags & P_BIGKEY) && 189 (h->prevpg != P_INVALID || skip > 1)) { 190 tbl = GETBLEAF(lchild, NEXTINDEX(lchild) - 1); 191 a.size = tbl->ksize; 192 a.data = tbl->bytes; 193 b.size = bl->ksize; 194 b.data = bl->bytes; 195 nksize = t->bt_pfx(&a, &b); 196 n = NBINTERNAL(nksize); 197 if (n < nbytes) { 198 #ifdef STATISTICS 199 bt_pfxsaved += nbytes - n; 200 #endif 201 nbytes = n; 202 } else 203 nksize = 0; 204 } else 205 nksize = 0; 206 break; 207 case P_RINTERNAL: 208 case P_RLEAF: 209 nbytes = NRINTERNAL; 210 break; 211 default: 212 abort(); 213 } 214 215 /* Split the parent page if necessary or shift the indices. */ 216 if (h->upper - h->lower < nbytes + sizeof(indx_t)) { 217 sp = h; 218 h = h->pgno == P_ROOT ? 219 bt_root(t, h, &l, &r, &skip, nbytes) : 220 bt_page(t, h, &l, &r, &skip, nbytes); 221 if (h == NULL) 222 goto err1; 223 parentsplit = 1; 224 } else { 225 if (skip < (nxtindex = NEXTINDEX(h))) 226 memmove(h->linp + skip + 1, h->linp + skip, 227 (nxtindex - skip) * sizeof(indx_t)); 228 h->lower += sizeof(indx_t); 229 parentsplit = 0; 230 } 231 232 /* Insert the key into the parent page. */ 233 switch (rchild->flags & P_TYPE) { 234 case P_BINTERNAL: 235 h->linp[skip] = h->upper -= nbytes; 236 dest = (char *)h + h->linp[skip]; 237 memmove(dest, bi, nbytes); 238 ((BINTERNAL *)dest)->pgno = rchild->pgno; 239 break; 240 case P_BLEAF: 241 h->linp[skip] = h->upper -= nbytes; 242 dest = (char *)h + h->linp[skip]; 243 WR_BINTERNAL(dest, nksize ? nksize : bl->ksize, 244 rchild->pgno, bl->flags & P_BIGKEY); 245 memmove(dest, bl->bytes, nksize ? nksize : bl->ksize); 246 if (bl->flags & P_BIGKEY && 247 bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR) 248 goto err1; 249 break; 250 case P_RINTERNAL: 251 /* 252 * Update the left page count. If split 253 * added at index 0, fix the correct page. 254 */ 255 if (skip > 0) 256 dest = (char *)h + h->linp[skip - 1]; 257 else 258 dest = (char *)l + l->linp[NEXTINDEX(l) - 1]; 259 ((RINTERNAL *)dest)->nrecs = rec_total(lchild); 260 ((RINTERNAL *)dest)->pgno = lchild->pgno; 261 262 /* Update the right page count. */ 263 h->linp[skip] = h->upper -= nbytes; 264 dest = (char *)h + h->linp[skip]; 265 ((RINTERNAL *)dest)->nrecs = rec_total(rchild); 266 ((RINTERNAL *)dest)->pgno = rchild->pgno; 267 break; 268 case P_RLEAF: 269 /* 270 * Update the left page count. If split 271 * added at index 0, fix the correct page. 272 */ 273 if (skip > 0) 274 dest = (char *)h + h->linp[skip - 1]; 275 else 276 dest = (char *)l + l->linp[NEXTINDEX(l) - 1]; 277 ((RINTERNAL *)dest)->nrecs = NEXTINDEX(lchild); 278 ((RINTERNAL *)dest)->pgno = lchild->pgno; 279 280 /* Update the right page count. */ 281 h->linp[skip] = h->upper -= nbytes; 282 dest = (char *)h + h->linp[skip]; 283 ((RINTERNAL *)dest)->nrecs = NEXTINDEX(rchild); 284 ((RINTERNAL *)dest)->pgno = rchild->pgno; 285 break; 286 default: 287 abort(); 288 } 289 290 /* Unpin the held pages. */ 291 if (!parentsplit) { 292 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 293 break; 294 } 295 296 /* If the root page was split, make it look right. */ 297 if (sp->pgno == P_ROOT && 298 (F_ISSET(t, R_RECNO) ? 299 bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR) 300 goto err1; 301 302 mpool_put(t->bt_mp, lchild, MPOOL_DIRTY); 303 mpool_put(t->bt_mp, rchild, MPOOL_DIRTY); 304 } 305 306 /* Unpin the held pages. */ 307 mpool_put(t->bt_mp, l, MPOOL_DIRTY); 308 mpool_put(t->bt_mp, r, MPOOL_DIRTY); 309 310 /* Clear any pages left on the stack. */ 311 return (RET_SUCCESS); 312 313 /* 314 * If something fails in the above loop we were already walking back 315 * up the tree and the tree is now inconsistent. Nothing much we can 316 * do about it but release any memory we're holding. 317 */ 318 err1: mpool_put(t->bt_mp, lchild, MPOOL_DIRTY); 319 mpool_put(t->bt_mp, rchild, MPOOL_DIRTY); 320 321 err2: mpool_put(t->bt_mp, l, 0); 322 mpool_put(t->bt_mp, r, 0); 323 __dbpanic(t->bt_dbp); 324 return (RET_ERROR); 325 } 326 327 /* 328 * BT_PAGE -- Split a non-root page of a btree. 329 * 330 * Parameters: 331 * t: tree 332 * h: root page 333 * lp: pointer to left page pointer 334 * rp: pointer to right page pointer 335 * skip: pointer to index to leave open 336 * ilen: insert length 337 * 338 * Returns: 339 * Pointer to page in which to insert or NULL on error. 340 */ 341 static PAGE * 342 bt_page(t, h, lp, rp, skip, ilen) 343 BTREE *t; 344 PAGE *h, **lp, **rp; 345 indx_t *skip; 346 size_t ilen; 347 { 348 PAGE *l, *r, *tp; 349 pgno_t npg; 350 351 #ifdef STATISTICS 352 ++bt_split; 353 #endif 354 /* Put the new right page for the split into place. */ 355 if ((r = __bt_new(t, &npg)) == NULL) 356 return (NULL); 357 r->pgno = npg; 358 r->lower = BTDATAOFF; 359 r->upper = t->bt_psize; 360 r->nextpg = h->nextpg; 361 r->prevpg = h->pgno; 362 r->flags = h->flags & P_TYPE; 363 364 /* 365 * If we're splitting the last page on a level because we're appending 366 * a key to it (skip is NEXTINDEX()), it's likely that the data is 367 * sorted. Adding an empty page on the side of the level is less work 368 * and can push the fill factor much higher than normal. If we're 369 * wrong it's no big deal, we'll just do the split the right way next 370 * time. It may look like it's equally easy to do a similar hack for 371 * reverse sorted data, that is, split the tree left, but it's not. 372 * Don't even try. 373 */ 374 if (h->nextpg == P_INVALID && *skip == NEXTINDEX(h)) { 375 #ifdef STATISTICS 376 ++bt_sortsplit; 377 #endif 378 h->nextpg = r->pgno; 379 r->lower = BTDATAOFF + sizeof(indx_t); 380 *skip = 0; 381 *lp = h; 382 *rp = r; 383 return (r); 384 } 385 386 /* Put the new left page for the split into place. */ 387 if ((l = (PAGE *)malloc(t->bt_psize)) == NULL) { 388 mpool_put(t->bt_mp, r, 0); 389 return (NULL); 390 } 391 #ifdef PURIFY 392 memset(l, 0xff, t->bt_psize); 393 #endif 394 l->pgno = h->pgno; 395 l->nextpg = r->pgno; 396 l->prevpg = h->prevpg; 397 l->lower = BTDATAOFF; 398 l->upper = t->bt_psize; 399 l->flags = h->flags & P_TYPE; 400 401 /* Fix up the previous pointer of the page after the split page. */ 402 if (h->nextpg != P_INVALID) { 403 if ((tp = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) { 404 free(l); 405 /* XXX mpool_free(t->bt_mp, r->pgno); */ 406 return (NULL); 407 } 408 tp->prevpg = r->pgno; 409 mpool_put(t->bt_mp, tp, MPOOL_DIRTY); 410 } 411 412 /* 413 * Split right. The key/data pairs aren't sorted in the btree page so 414 * it's simpler to copy the data from the split page onto two new pages 415 * instead of copying half the data to the right page and compacting 416 * the left page in place. Since the left page can't change, we have 417 * to swap the original and the allocated left page after the split. 418 */ 419 tp = bt_psplit(t, h, l, r, skip, ilen); 420 421 /* Move the new left page onto the old left page. */ 422 memmove(h, l, t->bt_psize); 423 if (tp == l) 424 tp = h; 425 free(l); 426 427 *lp = h; 428 *rp = r; 429 return (tp); 430 } 431 432 /* 433 * BT_ROOT -- Split the root page of a btree. 434 * 435 * Parameters: 436 * t: tree 437 * h: root page 438 * lp: pointer to left page pointer 439 * rp: pointer to right page pointer 440 * skip: pointer to index to leave open 441 * ilen: insert length 442 * 443 * Returns: 444 * Pointer to page in which to insert or NULL on error. 445 */ 446 static PAGE * 447 bt_root(t, h, lp, rp, skip, ilen) 448 BTREE *t; 449 PAGE *h, **lp, **rp; 450 indx_t *skip; 451 size_t ilen; 452 { 453 PAGE *l, *r, *tp; 454 pgno_t lnpg, rnpg; 455 456 #ifdef STATISTICS 457 ++bt_split; 458 ++bt_rootsplit; 459 #endif 460 /* Put the new left and right pages for the split into place. */ 461 if ((l = __bt_new(t, &lnpg)) == NULL || 462 (r = __bt_new(t, &rnpg)) == NULL) 463 return (NULL); 464 l->pgno = lnpg; 465 r->pgno = rnpg; 466 l->nextpg = r->pgno; 467 r->prevpg = l->pgno; 468 l->prevpg = r->nextpg = P_INVALID; 469 l->lower = r->lower = BTDATAOFF; 470 l->upper = r->upper = t->bt_psize; 471 l->flags = r->flags = h->flags & P_TYPE; 472 473 /* Split the root page. */ 474 tp = bt_psplit(t, h, l, r, skip, ilen); 475 476 *lp = l; 477 *rp = r; 478 return (tp); 479 } 480 481 /* 482 * BT_RROOT -- Fix up the recno root page after it has been split. 483 * 484 * Parameters: 485 * t: tree 486 * h: root page 487 * l: left page 488 * r: right page 489 * 490 * Returns: 491 * RET_ERROR, RET_SUCCESS 492 */ 493 static int 494 bt_rroot(t, h, l, r) 495 BTREE *t; 496 PAGE *h, *l, *r; 497 { 498 char *dest; 499 500 /* Insert the left and right keys, set the header information. */ 501 h->linp[0] = h->upper = t->bt_psize - NRINTERNAL; 502 dest = (char *)h + h->upper; 503 WR_RINTERNAL(dest, 504 l->flags & P_RLEAF ? NEXTINDEX(l) : rec_total(l), l->pgno); 505 506 h->linp[1] = h->upper -= NRINTERNAL; 507 dest = (char *)h + h->upper; 508 WR_RINTERNAL(dest, 509 r->flags & P_RLEAF ? NEXTINDEX(r) : rec_total(r), r->pgno); 510 511 h->lower = BTDATAOFF + 2 * sizeof(indx_t); 512 513 /* Unpin the root page, set to recno internal page. */ 514 h->flags &= ~P_TYPE; 515 h->flags |= P_RINTERNAL; 516 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 517 518 return (RET_SUCCESS); 519 } 520 521 /* 522 * BT_BROOT -- Fix up the btree root page after it has been split. 523 * 524 * Parameters: 525 * t: tree 526 * h: root page 527 * l: left page 528 * r: right page 529 * 530 * Returns: 531 * RET_ERROR, RET_SUCCESS 532 */ 533 static int 534 bt_broot(t, h, l, r) 535 BTREE *t; 536 PAGE *h, *l, *r; 537 { 538 BINTERNAL *bi; 539 BLEAF *bl; 540 u_int32_t nbytes; 541 char *dest; 542 543 /* 544 * If the root page was a leaf page, change it into an internal page. 545 * We copy the key we split on (but not the key's data, in the case of 546 * a leaf page) to the new root page. 547 * 548 * The btree comparison code guarantees that the left-most key on any 549 * level of the tree is never used, so it doesn't need to be filled in. 550 */ 551 nbytes = NBINTERNAL(0); 552 h->linp[0] = h->upper = t->bt_psize - nbytes; 553 dest = (char *)h + h->upper; 554 WR_BINTERNAL(dest, 0, l->pgno, 0); 555 556 switch (h->flags & P_TYPE) { 557 case P_BLEAF: 558 bl = GETBLEAF(r, 0); 559 nbytes = NBINTERNAL(bl->ksize); 560 h->linp[1] = h->upper -= nbytes; 561 dest = (char *)h + h->upper; 562 WR_BINTERNAL(dest, bl->ksize, r->pgno, 0); 563 memmove(dest, bl->bytes, bl->ksize); 564 565 /* 566 * If the key is on an overflow page, mark the overflow chain 567 * so it isn't deleted when the leaf copy of the key is deleted. 568 */ 569 if (bl->flags & P_BIGKEY && 570 bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR) 571 return (RET_ERROR); 572 break; 573 case P_BINTERNAL: 574 bi = GETBINTERNAL(r, 0); 575 nbytes = NBINTERNAL(bi->ksize); 576 h->linp[1] = h->upper -= nbytes; 577 dest = (char *)h + h->upper; 578 memmove(dest, bi, nbytes); 579 ((BINTERNAL *)dest)->pgno = r->pgno; 580 break; 581 default: 582 abort(); 583 } 584 585 /* There are two keys on the page. */ 586 h->lower = BTDATAOFF + 2 * sizeof(indx_t); 587 588 /* Unpin the root page, set to btree internal page. */ 589 h->flags &= ~P_TYPE; 590 h->flags |= P_BINTERNAL; 591 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 592 593 return (RET_SUCCESS); 594 } 595 596 /* 597 * BT_PSPLIT -- Do the real work of splitting the page. 598 * 599 * Parameters: 600 * t: tree 601 * h: page to be split 602 * l: page to put lower half of data 603 * r: page to put upper half of data 604 * pskip: pointer to index to leave open 605 * ilen: insert length 606 * 607 * Returns: 608 * Pointer to page in which to insert. 609 */ 610 static PAGE * 611 bt_psplit(t, h, l, r, pskip, ilen) 612 BTREE *t; 613 PAGE *h, *l, *r; 614 indx_t *pskip; 615 size_t ilen; 616 { 617 BINTERNAL *bi; 618 BLEAF *bl; 619 CURSOR *c; 620 RLEAF *rl; 621 PAGE *rval; 622 void *src; 623 indx_t full, half, nxt, off, skip, top, used; 624 u_int32_t nbytes; 625 int bigkeycnt, isbigkey; 626 627 /* 628 * Split the data to the left and right pages. Leave the skip index 629 * open. Additionally, make some effort not to split on an overflow 630 * key. This makes internal page processing faster and can save 631 * space as overflow keys used by internal pages are never deleted. 632 */ 633 bigkeycnt = 0; 634 skip = *pskip; 635 full = t->bt_psize - BTDATAOFF; 636 half = full / 2; 637 used = 0; 638 for (nxt = off = 0, top = NEXTINDEX(h); nxt < top; ++off) { 639 if (skip == off) { 640 nbytes = ilen; 641 isbigkey = 0; /* XXX: not really known. */ 642 } else 643 switch (h->flags & P_TYPE) { 644 case P_BINTERNAL: 645 src = bi = GETBINTERNAL(h, nxt); 646 nbytes = NBINTERNAL(bi->ksize); 647 isbigkey = bi->flags & P_BIGKEY; 648 break; 649 case P_BLEAF: 650 src = bl = GETBLEAF(h, nxt); 651 nbytes = NBLEAF(bl); 652 isbigkey = bl->flags & P_BIGKEY; 653 break; 654 case P_RINTERNAL: 655 src = GETRINTERNAL(h, nxt); 656 nbytes = NRINTERNAL; 657 isbigkey = 0; 658 break; 659 case P_RLEAF: 660 src = rl = GETRLEAF(h, nxt); 661 nbytes = NRLEAF(rl); 662 isbigkey = 0; 663 break; 664 default: 665 abort(); 666 } 667 668 /* 669 * If the key/data pairs are substantial fractions of the max 670 * possible size for the page, it's possible to get situations 671 * where we decide to try and copy too much onto the left page. 672 * Make sure that doesn't happen. 673 */ 674 if (skip <= off && 675 used + nbytes + sizeof(indx_t) >= full || nxt == top - 1) { 676 --off; 677 break; 678 } 679 680 /* Copy the key/data pair, if not the skipped index. */ 681 if (skip != off) { 682 ++nxt; 683 684 l->linp[off] = l->upper -= nbytes; 685 memmove((char *)l + l->upper, src, nbytes); 686 } 687 688 used += nbytes + sizeof(indx_t); 689 if (used >= half) { 690 if (!isbigkey || bigkeycnt == 3) 691 break; 692 else 693 ++bigkeycnt; 694 } 695 } 696 697 /* 698 * Off is the last offset that's valid for the left page. 699 * Nxt is the first offset to be placed on the right page. 700 */ 701 l->lower += (off + 1) * sizeof(indx_t); 702 703 /* 704 * If splitting the page that the cursor was on, the cursor has to be 705 * adjusted to point to the same record as before the split. If the 706 * cursor is at or past the skipped slot, the cursor is incremented by 707 * one. If the cursor is on the right page, it is decremented by the 708 * number of records split to the left page. 709 */ 710 c = &t->bt_cursor; 711 if (F_ISSET(c, CURS_INIT) && c->pg.pgno == h->pgno) { 712 if (c->pg.index >= skip) 713 ++c->pg.index; 714 if (c->pg.index < nxt) /* Left page. */ 715 c->pg.pgno = l->pgno; 716 else { /* Right page. */ 717 c->pg.pgno = r->pgno; 718 c->pg.index -= nxt; 719 } 720 } 721 722 /* 723 * If the skipped index was on the left page, just return that page. 724 * Otherwise, adjust the skip index to reflect the new position on 725 * the right page. 726 */ 727 if (skip <= off) { 728 skip = 0; 729 rval = l; 730 } else { 731 rval = r; 732 *pskip -= nxt; 733 } 734 735 for (off = 0; nxt < top; ++off) { 736 if (skip == nxt) { 737 ++off; 738 skip = 0; 739 } 740 switch (h->flags & P_TYPE) { 741 case P_BINTERNAL: 742 src = bi = GETBINTERNAL(h, nxt); 743 nbytes = NBINTERNAL(bi->ksize); 744 break; 745 case P_BLEAF: 746 src = bl = GETBLEAF(h, nxt); 747 nbytes = NBLEAF(bl); 748 break; 749 case P_RINTERNAL: 750 src = GETRINTERNAL(h, nxt); 751 nbytes = NRINTERNAL; 752 break; 753 case P_RLEAF: 754 src = rl = GETRLEAF(h, nxt); 755 nbytes = NRLEAF(rl); 756 break; 757 default: 758 abort(); 759 } 760 ++nxt; 761 r->linp[off] = r->upper -= nbytes; 762 memmove((char *)r + r->upper, src, nbytes); 763 } 764 r->lower += off * sizeof(indx_t); 765 766 /* If the key is being appended to the page, adjust the index. */ 767 if (skip == top) 768 r->lower += sizeof(indx_t); 769 770 return (rval); 771 } 772 773 /* 774 * BT_PRESERVE -- Mark a chain of pages as used by an internal node. 775 * 776 * Chains of indirect blocks pointed to by leaf nodes get reclaimed when the 777 * record that references them gets deleted. Chains pointed to by internal 778 * pages never get deleted. This routine marks a chain as pointed to by an 779 * internal page. 780 * 781 * Parameters: 782 * t: tree 783 * pg: page number of first page in the chain. 784 * 785 * Returns: 786 * RET_SUCCESS, RET_ERROR. 787 */ 788 static int 789 bt_preserve(t, pg) 790 BTREE *t; 791 pgno_t pg; 792 { 793 PAGE *h; 794 795 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 796 return (RET_ERROR); 797 h->flags |= P_PRESERVE; 798 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 799 return (RET_SUCCESS); 800 } 801 802 /* 803 * REC_TOTAL -- Return the number of recno entries below a page. 804 * 805 * Parameters: 806 * h: page 807 * 808 * Returns: 809 * The number of recno entries below a page. 810 * 811 * XXX 812 * These values could be set by the bt_psplit routine. The problem is that the 813 * entry has to be popped off of the stack etc. or the values have to be passed 814 * all the way back to bt_split/bt_rroot and it's not very clean. 815 */ 816 static recno_t 817 rec_total(h) 818 PAGE *h; 819 { 820 recno_t recs; 821 indx_t nxt, top; 822 823 for (recs = 0, nxt = 0, top = NEXTINDEX(h); nxt < top; ++nxt) 824 recs += GETRINTERNAL(h, nxt)->nrecs; 825 return (recs); 826 } 827