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