lib/libcr/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. 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 }