lib/libc/db/btree/bt_split.c

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