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