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