17c478bd9Sstevel@tonic-gate /*-
27c478bd9Sstevel@tonic-gate * Copyright (c) 1990, 1993, 1994
37c478bd9Sstevel@tonic-gate * The Regents of the University of California. All rights reserved.
47c478bd9Sstevel@tonic-gate *
57c478bd9Sstevel@tonic-gate * This code is derived from software contributed to Berkeley by
67c478bd9Sstevel@tonic-gate * Mike Olson.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without
97c478bd9Sstevel@tonic-gate * modification, are permitted provided that the following conditions
107c478bd9Sstevel@tonic-gate * are met:
117c478bd9Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright
127c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer.
137c478bd9Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright
147c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the
157c478bd9Sstevel@tonic-gate * documentation and/or other materials provided with the distribution.
167c478bd9Sstevel@tonic-gate * 3. All advertising materials mentioning features or use of this software
177c478bd9Sstevel@tonic-gate * must display the following acknowledgement:
187c478bd9Sstevel@tonic-gate * This product includes software developed by the University of
197c478bd9Sstevel@tonic-gate * California, Berkeley and its contributors.
207c478bd9Sstevel@tonic-gate * 4. Neither the name of the University nor the names of its contributors
217c478bd9Sstevel@tonic-gate * may be used to endorse or promote products derived from this software
227c478bd9Sstevel@tonic-gate * without specific prior written permission.
237c478bd9Sstevel@tonic-gate *
247c478bd9Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
257c478bd9Sstevel@tonic-gate * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
267c478bd9Sstevel@tonic-gate * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
277c478bd9Sstevel@tonic-gate * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
287c478bd9Sstevel@tonic-gate * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
297c478bd9Sstevel@tonic-gate * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
307c478bd9Sstevel@tonic-gate * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
317c478bd9Sstevel@tonic-gate * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
327c478bd9Sstevel@tonic-gate * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
337c478bd9Sstevel@tonic-gate * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
347c478bd9Sstevel@tonic-gate * SUCH DAMAGE.
357c478bd9Sstevel@tonic-gate */
367c478bd9Sstevel@tonic-gate
377c478bd9Sstevel@tonic-gate #if defined(LIBC_SCCS) && !defined(lint)
387c478bd9Sstevel@tonic-gate static char sccsid[] = "@(#)bt_split.c 8.10 (Berkeley) 1/9/95";
397c478bd9Sstevel@tonic-gate #endif /* LIBC_SCCS and not lint */
407c478bd9Sstevel@tonic-gate
417c478bd9Sstevel@tonic-gate #include <sys/types.h>
427c478bd9Sstevel@tonic-gate
437c478bd9Sstevel@tonic-gate #include <limits.h>
447c478bd9Sstevel@tonic-gate #include <stdio.h>
457c478bd9Sstevel@tonic-gate #include <stdlib.h>
467c478bd9Sstevel@tonic-gate #include <string.h>
477c478bd9Sstevel@tonic-gate
487c478bd9Sstevel@tonic-gate #include "db-int.h"
497c478bd9Sstevel@tonic-gate #include "btree.h"
507c478bd9Sstevel@tonic-gate
517c478bd9Sstevel@tonic-gate static int bt_broot __P((BTREE *, PAGE *, PAGE *, PAGE *));
527c478bd9Sstevel@tonic-gate static PAGE *bt_page
537c478bd9Sstevel@tonic-gate __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t));
547c478bd9Sstevel@tonic-gate static int bt_preserve __P((BTREE *, db_pgno_t));
557c478bd9Sstevel@tonic-gate static PAGE *bt_psplit
567c478bd9Sstevel@tonic-gate __P((BTREE *, PAGE *, PAGE *, PAGE *, indx_t *, size_t));
577c478bd9Sstevel@tonic-gate static PAGE *bt_root
587c478bd9Sstevel@tonic-gate __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t));
597c478bd9Sstevel@tonic-gate static int bt_rroot __P((BTREE *, PAGE *, PAGE *, PAGE *));
607c478bd9Sstevel@tonic-gate static recno_t rec_total __P((PAGE *));
617c478bd9Sstevel@tonic-gate
627c478bd9Sstevel@tonic-gate #ifdef STATISTICS
637c478bd9Sstevel@tonic-gate u_long bt_rootsplit, bt_split, bt_sortsplit, bt_pfxsaved;
647c478bd9Sstevel@tonic-gate #endif
657c478bd9Sstevel@tonic-gate
667c478bd9Sstevel@tonic-gate /*
677c478bd9Sstevel@tonic-gate * __BT_SPLIT -- Split the tree.
687c478bd9Sstevel@tonic-gate *
697c478bd9Sstevel@tonic-gate * Parameters:
707c478bd9Sstevel@tonic-gate * t: tree
717c478bd9Sstevel@tonic-gate * sp: page to split
727c478bd9Sstevel@tonic-gate * key: key to insert
737c478bd9Sstevel@tonic-gate * data: data to insert
747c478bd9Sstevel@tonic-gate * flags: BIGKEY/BIGDATA flags
757c478bd9Sstevel@tonic-gate * ilen: insert length
767c478bd9Sstevel@tonic-gate * skip: index to leave open
777c478bd9Sstevel@tonic-gate *
787c478bd9Sstevel@tonic-gate * Returns:
797c478bd9Sstevel@tonic-gate * RET_ERROR, RET_SUCCESS
807c478bd9Sstevel@tonic-gate */
817c478bd9Sstevel@tonic-gate int
__bt_split(t,sp,key,data,flags,ilen,argskip)827c478bd9Sstevel@tonic-gate __bt_split(t, sp, key, data, flags, ilen, argskip)
837c478bd9Sstevel@tonic-gate BTREE *t;
847c478bd9Sstevel@tonic-gate PAGE *sp;
857c478bd9Sstevel@tonic-gate const DBT *key, *data;
867c478bd9Sstevel@tonic-gate int flags;
877c478bd9Sstevel@tonic-gate size_t ilen;
887c478bd9Sstevel@tonic-gate u_int32_t argskip;
897c478bd9Sstevel@tonic-gate {
907c478bd9Sstevel@tonic-gate BINTERNAL *bi;
917c478bd9Sstevel@tonic-gate BLEAF *bl, *tbl;
927c478bd9Sstevel@tonic-gate DBT a, b;
937c478bd9Sstevel@tonic-gate EPGNO *parent;
947c478bd9Sstevel@tonic-gate PAGE *h, *l, *r, *lchild, *rchild;
957c478bd9Sstevel@tonic-gate indx_t nxtindex;
967c478bd9Sstevel@tonic-gate u_int16_t skip;
977c478bd9Sstevel@tonic-gate u_int32_t n, nbytes, nksize;
987c478bd9Sstevel@tonic-gate int parentsplit;
997c478bd9Sstevel@tonic-gate char *dest;
1007c478bd9Sstevel@tonic-gate
1017c478bd9Sstevel@tonic-gate /*
1027c478bd9Sstevel@tonic-gate * Split the page into two pages, l and r. The split routines return
1037c478bd9Sstevel@tonic-gate * a pointer to the page into which the key should be inserted and with
1047c478bd9Sstevel@tonic-gate * skip set to the offset which should be used. Additionally, l and r
1057c478bd9Sstevel@tonic-gate * are pinned.
1067c478bd9Sstevel@tonic-gate */
1077c478bd9Sstevel@tonic-gate skip = argskip;
1087c478bd9Sstevel@tonic-gate h = sp->pgno == P_ROOT ?
1097c478bd9Sstevel@tonic-gate bt_root(t, sp, &l, &r, &skip, ilen) :
1107c478bd9Sstevel@tonic-gate bt_page(t, sp, &l, &r, &skip, ilen);
1117c478bd9Sstevel@tonic-gate if (h == NULL)
1127c478bd9Sstevel@tonic-gate return (RET_ERROR);
1137c478bd9Sstevel@tonic-gate
1147c478bd9Sstevel@tonic-gate /*
1157c478bd9Sstevel@tonic-gate * Insert the new key/data pair into the leaf page. (Key inserts
1167c478bd9Sstevel@tonic-gate * always cause a leaf page to split first.)
1177c478bd9Sstevel@tonic-gate */
1187c478bd9Sstevel@tonic-gate h->linp[skip] = h->upper -= ilen;
1197c478bd9Sstevel@tonic-gate dest = (char *)h + h->upper;
1207c478bd9Sstevel@tonic-gate if (F_ISSET(t, R_RECNO))
1217c478bd9Sstevel@tonic-gate WR_RLEAF(dest, data, flags)
1227c478bd9Sstevel@tonic-gate else
1237c478bd9Sstevel@tonic-gate WR_BLEAF(dest, key, data, flags)
1247c478bd9Sstevel@tonic-gate
1257c478bd9Sstevel@tonic-gate /* If the root page was split, make it look right. */
1267c478bd9Sstevel@tonic-gate if (sp->pgno == P_ROOT &&
1277c478bd9Sstevel@tonic-gate (F_ISSET(t, R_RECNO) ?
1287c478bd9Sstevel@tonic-gate bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
1297c478bd9Sstevel@tonic-gate goto err2;
1307c478bd9Sstevel@tonic-gate
1317c478bd9Sstevel@tonic-gate /*
1327c478bd9Sstevel@tonic-gate * Now we walk the parent page stack -- a LIFO stack of the pages that
1337c478bd9Sstevel@tonic-gate * were traversed when we searched for the page that split. Each stack
1347c478bd9Sstevel@tonic-gate * entry is a page number and a page index offset. The offset is for
1357c478bd9Sstevel@tonic-gate * the page traversed on the search. We've just split a page, so we
1367c478bd9Sstevel@tonic-gate * have to insert a new key into the parent page.
1377c478bd9Sstevel@tonic-gate *
1387c478bd9Sstevel@tonic-gate * If the insert into the parent page causes it to split, may have to
1397c478bd9Sstevel@tonic-gate * continue splitting all the way up the tree. We stop if the root
1407c478bd9Sstevel@tonic-gate * splits or the page inserted into didn't have to split to hold the
1417c478bd9Sstevel@tonic-gate * new key. Some algorithms replace the key for the old page as well
1427c478bd9Sstevel@tonic-gate * as the new page. We don't, as there's no reason to believe that the
1437c478bd9Sstevel@tonic-gate * first key on the old page is any better than the key we have, and,
1447c478bd9Sstevel@tonic-gate * in the case of a key being placed at index 0 causing the split, the
1457c478bd9Sstevel@tonic-gate * key is unavailable.
1467c478bd9Sstevel@tonic-gate *
1477c478bd9Sstevel@tonic-gate * There are a maximum of 5 pages pinned at any time. We keep the left
1487c478bd9Sstevel@tonic-gate * and right pages pinned while working on the parent. The 5 are the
1497c478bd9Sstevel@tonic-gate * two children, left parent and right parent (when the parent splits)
1507c478bd9Sstevel@tonic-gate * and the root page or the overflow key page when calling bt_preserve.
1517c478bd9Sstevel@tonic-gate * This code must make sure that all pins are released other than the
1527c478bd9Sstevel@tonic-gate * root page or overflow page which is unlocked elsewhere.
1537c478bd9Sstevel@tonic-gate */
1547c478bd9Sstevel@tonic-gate while ((parent = BT_POP(t)) != NULL) {
1557c478bd9Sstevel@tonic-gate lchild = l;
1567c478bd9Sstevel@tonic-gate rchild = r;
1577c478bd9Sstevel@tonic-gate
1587c478bd9Sstevel@tonic-gate /* Get the parent page. */
1597c478bd9Sstevel@tonic-gate if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
1607c478bd9Sstevel@tonic-gate goto err2;
1617c478bd9Sstevel@tonic-gate
1627c478bd9Sstevel@tonic-gate /*
1637c478bd9Sstevel@tonic-gate * The new key goes ONE AFTER the index, because the split
1647c478bd9Sstevel@tonic-gate * was to the right.
1657c478bd9Sstevel@tonic-gate */
1667c478bd9Sstevel@tonic-gate skip = parent->index + 1;
1677c478bd9Sstevel@tonic-gate
1687c478bd9Sstevel@tonic-gate /*
1697c478bd9Sstevel@tonic-gate * Calculate the space needed on the parent page.
1707c478bd9Sstevel@tonic-gate *
1717c478bd9Sstevel@tonic-gate * Prefix trees: space hack when inserting into BINTERNAL
1727c478bd9Sstevel@tonic-gate * pages. Retain only what's needed to distinguish between
1737c478bd9Sstevel@tonic-gate * the new entry and the LAST entry on the page to its left.
1747c478bd9Sstevel@tonic-gate * If the keys compare equal, retain the entire key. Note,
1757c478bd9Sstevel@tonic-gate * we don't touch overflow keys, and the entire key must be
1767c478bd9Sstevel@tonic-gate * retained for the next-to-left most key on the leftmost
1777c478bd9Sstevel@tonic-gate * page of each level, or the search will fail. Applicable
1787c478bd9Sstevel@tonic-gate * ONLY to internal pages that have leaf pages as children.
1797c478bd9Sstevel@tonic-gate * Further reduction of the key between pairs of internal
1807c478bd9Sstevel@tonic-gate * pages loses too much information.
1817c478bd9Sstevel@tonic-gate */
1827c478bd9Sstevel@tonic-gate switch (rchild->flags & P_TYPE) {
1837c478bd9Sstevel@tonic-gate case P_BINTERNAL:
1847c478bd9Sstevel@tonic-gate bi = GETBINTERNAL(rchild, 0);
1857c478bd9Sstevel@tonic-gate nbytes = NBINTERNAL(bi->ksize);
1867c478bd9Sstevel@tonic-gate break;
1877c478bd9Sstevel@tonic-gate case P_BLEAF:
1887c478bd9Sstevel@tonic-gate bl = GETBLEAF(rchild, 0);
1897c478bd9Sstevel@tonic-gate nbytes = NBINTERNAL(bl->ksize);
1907c478bd9Sstevel@tonic-gate if (t->bt_pfx && !(bl->flags & P_BIGKEY) &&
1917c478bd9Sstevel@tonic-gate (h->prevpg != P_INVALID || skip > 1)) {
1927c478bd9Sstevel@tonic-gate tbl = GETBLEAF(lchild, NEXTINDEX(lchild) - 1);
1937c478bd9Sstevel@tonic-gate a.size = tbl->ksize;
1947c478bd9Sstevel@tonic-gate a.data = tbl->bytes;
1957c478bd9Sstevel@tonic-gate b.size = bl->ksize;
1967c478bd9Sstevel@tonic-gate b.data = bl->bytes;
1977c478bd9Sstevel@tonic-gate nksize = t->bt_pfx(&a, &b);
1987c478bd9Sstevel@tonic-gate n = NBINTERNAL(nksize);
1997c478bd9Sstevel@tonic-gate if (n < nbytes) {
2007c478bd9Sstevel@tonic-gate #ifdef STATISTICS
2017c478bd9Sstevel@tonic-gate bt_pfxsaved += nbytes - n;
2027c478bd9Sstevel@tonic-gate #endif
2037c478bd9Sstevel@tonic-gate nbytes = n;
2047c478bd9Sstevel@tonic-gate } else
2057c478bd9Sstevel@tonic-gate nksize = 0;
2067c478bd9Sstevel@tonic-gate } else
2077c478bd9Sstevel@tonic-gate nksize = 0;
2087c478bd9Sstevel@tonic-gate break;
2097c478bd9Sstevel@tonic-gate case P_RINTERNAL:
2107c478bd9Sstevel@tonic-gate case P_RLEAF:
2117c478bd9Sstevel@tonic-gate nbytes = NRINTERNAL;
2127c478bd9Sstevel@tonic-gate break;
2137c478bd9Sstevel@tonic-gate default:
2147c478bd9Sstevel@tonic-gate abort();
2157c478bd9Sstevel@tonic-gate }
2167c478bd9Sstevel@tonic-gate
2177c478bd9Sstevel@tonic-gate /* Split the parent page if necessary or shift the indices. */
2187c478bd9Sstevel@tonic-gate if (h->upper - h->lower < nbytes + sizeof(indx_t)) {
2197c478bd9Sstevel@tonic-gate sp = h;
2207c478bd9Sstevel@tonic-gate h = h->pgno == P_ROOT ?
2217c478bd9Sstevel@tonic-gate bt_root(t, h, &l, &r, &skip, nbytes) :
2227c478bd9Sstevel@tonic-gate bt_page(t, h, &l, &r, &skip, nbytes);
2237c478bd9Sstevel@tonic-gate if (h == NULL)
2247c478bd9Sstevel@tonic-gate goto err1;
2257c478bd9Sstevel@tonic-gate parentsplit = 1;
2267c478bd9Sstevel@tonic-gate } else {
2277c478bd9Sstevel@tonic-gate if (skip < (nxtindex = NEXTINDEX(h)))
2287c478bd9Sstevel@tonic-gate memmove(h->linp + skip + 1, h->linp + skip,
2297c478bd9Sstevel@tonic-gate (nxtindex - skip) * sizeof(indx_t));
2307c478bd9Sstevel@tonic-gate h->lower += sizeof(indx_t);
2317c478bd9Sstevel@tonic-gate parentsplit = 0;
2327c478bd9Sstevel@tonic-gate }
2337c478bd9Sstevel@tonic-gate
2347c478bd9Sstevel@tonic-gate /* Insert the key into the parent page. */
2357c478bd9Sstevel@tonic-gate switch (rchild->flags & P_TYPE) {
2367c478bd9Sstevel@tonic-gate case P_BINTERNAL:
2377c478bd9Sstevel@tonic-gate h->linp[skip] = h->upper -= nbytes;
2387c478bd9Sstevel@tonic-gate dest = (char *)h + h->linp[skip];
2397c478bd9Sstevel@tonic-gate memmove(dest, bi, nbytes);
2407c478bd9Sstevel@tonic-gate ((BINTERNAL *)dest)->pgno = rchild->pgno;
2417c478bd9Sstevel@tonic-gate break;
2427c478bd9Sstevel@tonic-gate case P_BLEAF:
2437c478bd9Sstevel@tonic-gate h->linp[skip] = h->upper -= nbytes;
2447c478bd9Sstevel@tonic-gate dest = (char *)h + h->linp[skip];
2457c478bd9Sstevel@tonic-gate WR_BINTERNAL(dest, nksize ? nksize : bl->ksize,
2467c478bd9Sstevel@tonic-gate rchild->pgno, bl->flags & P_BIGKEY);
2477c478bd9Sstevel@tonic-gate memmove(dest, bl->bytes, nksize ? nksize : bl->ksize);
2487c478bd9Sstevel@tonic-gate if (bl->flags & P_BIGKEY &&
2497c478bd9Sstevel@tonic-gate bt_preserve(t, *(db_pgno_t *)bl->bytes) == RET_ERROR)
2507c478bd9Sstevel@tonic-gate goto err1;
2517c478bd9Sstevel@tonic-gate break;
2527c478bd9Sstevel@tonic-gate case P_RINTERNAL:
2537c478bd9Sstevel@tonic-gate /*
2547c478bd9Sstevel@tonic-gate * Update the left page count. If split
2557c478bd9Sstevel@tonic-gate * added at index 0, fix the correct page.
2567c478bd9Sstevel@tonic-gate */
2577c478bd9Sstevel@tonic-gate if (skip > 0)
2587c478bd9Sstevel@tonic-gate dest = (char *)h + h->linp[skip - 1];
2597c478bd9Sstevel@tonic-gate else
2607c478bd9Sstevel@tonic-gate dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
2617c478bd9Sstevel@tonic-gate ((RINTERNAL *)dest)->nrecs = rec_total(lchild);
2627c478bd9Sstevel@tonic-gate ((RINTERNAL *)dest)->pgno = lchild->pgno;
2637c478bd9Sstevel@tonic-gate
2647c478bd9Sstevel@tonic-gate /* Update the right page count. */
2657c478bd9Sstevel@tonic-gate h->linp[skip] = h->upper -= nbytes;
2667c478bd9Sstevel@tonic-gate dest = (char *)h + h->linp[skip];
2677c478bd9Sstevel@tonic-gate ((RINTERNAL *)dest)->nrecs = rec_total(rchild);
2687c478bd9Sstevel@tonic-gate ((RINTERNAL *)dest)->pgno = rchild->pgno;
2697c478bd9Sstevel@tonic-gate break;
2707c478bd9Sstevel@tonic-gate case P_RLEAF:
2717c478bd9Sstevel@tonic-gate /*
2727c478bd9Sstevel@tonic-gate * Update the left page count. If split
2737c478bd9Sstevel@tonic-gate * added at index 0, fix the correct page.
2747c478bd9Sstevel@tonic-gate */
2757c478bd9Sstevel@tonic-gate if (skip > 0)
2767c478bd9Sstevel@tonic-gate dest = (char *)h + h->linp[skip - 1];
2777c478bd9Sstevel@tonic-gate else
2787c478bd9Sstevel@tonic-gate dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
2797c478bd9Sstevel@tonic-gate ((RINTERNAL *)dest)->nrecs = NEXTINDEX(lchild);
2807c478bd9Sstevel@tonic-gate ((RINTERNAL *)dest)->pgno = lchild->pgno;
2817c478bd9Sstevel@tonic-gate
2827c478bd9Sstevel@tonic-gate /* Update the right page count. */
2837c478bd9Sstevel@tonic-gate h->linp[skip] = h->upper -= nbytes;
2847c478bd9Sstevel@tonic-gate dest = (char *)h + h->linp[skip];
2857c478bd9Sstevel@tonic-gate ((RINTERNAL *)dest)->nrecs = NEXTINDEX(rchild);
2867c478bd9Sstevel@tonic-gate ((RINTERNAL *)dest)->pgno = rchild->pgno;
2877c478bd9Sstevel@tonic-gate break;
2887c478bd9Sstevel@tonic-gate default:
2897c478bd9Sstevel@tonic-gate abort();
2907c478bd9Sstevel@tonic-gate }
2917c478bd9Sstevel@tonic-gate
2927c478bd9Sstevel@tonic-gate /* Unpin the held pages. */
2937c478bd9Sstevel@tonic-gate if (!parentsplit) {
2947c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, MPOOL_DIRTY);
2957c478bd9Sstevel@tonic-gate break;
2967c478bd9Sstevel@tonic-gate }
2977c478bd9Sstevel@tonic-gate
2987c478bd9Sstevel@tonic-gate /* If the root page was split, make it look right. */
2997c478bd9Sstevel@tonic-gate if (sp->pgno == P_ROOT &&
3007c478bd9Sstevel@tonic-gate (F_ISSET(t, R_RECNO) ?
3017c478bd9Sstevel@tonic-gate bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
3027c478bd9Sstevel@tonic-gate goto err1;
3037c478bd9Sstevel@tonic-gate
3047c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
3057c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
3067c478bd9Sstevel@tonic-gate }
3077c478bd9Sstevel@tonic-gate
3087c478bd9Sstevel@tonic-gate /* Unpin the held pages. */
3097c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, l, MPOOL_DIRTY);
3107c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, r, MPOOL_DIRTY);
3117c478bd9Sstevel@tonic-gate
3127c478bd9Sstevel@tonic-gate /* Clear any pages left on the stack. */
3137c478bd9Sstevel@tonic-gate return (RET_SUCCESS);
3147c478bd9Sstevel@tonic-gate
3157c478bd9Sstevel@tonic-gate /*
3167c478bd9Sstevel@tonic-gate * If something fails in the above loop we were already walking back
3177c478bd9Sstevel@tonic-gate * up the tree and the tree is now inconsistent. Nothing much we can
3187c478bd9Sstevel@tonic-gate * do about it but release any memory we're holding.
3197c478bd9Sstevel@tonic-gate */
3207c478bd9Sstevel@tonic-gate err1: mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
3217c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
3227c478bd9Sstevel@tonic-gate
3237c478bd9Sstevel@tonic-gate err2: mpool_put(t->bt_mp, l, 0);
3247c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, r, 0);
3257c478bd9Sstevel@tonic-gate __dbpanic(t->bt_dbp);
3267c478bd9Sstevel@tonic-gate return (RET_ERROR);
3277c478bd9Sstevel@tonic-gate }
3287c478bd9Sstevel@tonic-gate
3297c478bd9Sstevel@tonic-gate /*
3307c478bd9Sstevel@tonic-gate * BT_PAGE -- Split a non-root page of a btree.
3317c478bd9Sstevel@tonic-gate *
3327c478bd9Sstevel@tonic-gate * Parameters:
3337c478bd9Sstevel@tonic-gate * t: tree
3347c478bd9Sstevel@tonic-gate * h: root page
3357c478bd9Sstevel@tonic-gate * lp: pointer to left page pointer
3367c478bd9Sstevel@tonic-gate * rp: pointer to right page pointer
3377c478bd9Sstevel@tonic-gate * skip: pointer to index to leave open
3387c478bd9Sstevel@tonic-gate * ilen: insert length
3397c478bd9Sstevel@tonic-gate *
3407c478bd9Sstevel@tonic-gate * Returns:
3417c478bd9Sstevel@tonic-gate * Pointer to page in which to insert or NULL on error.
3427c478bd9Sstevel@tonic-gate */
3437c478bd9Sstevel@tonic-gate static PAGE *
bt_page(t,h,lp,rp,skip,ilen)3447c478bd9Sstevel@tonic-gate bt_page(t, h, lp, rp, skip, ilen)
3457c478bd9Sstevel@tonic-gate BTREE *t;
3467c478bd9Sstevel@tonic-gate PAGE *h, **lp, **rp;
3477c478bd9Sstevel@tonic-gate indx_t *skip;
3487c478bd9Sstevel@tonic-gate size_t ilen;
3497c478bd9Sstevel@tonic-gate {
3507c478bd9Sstevel@tonic-gate PAGE *l, *r, *tp;
3517c478bd9Sstevel@tonic-gate db_pgno_t npg;
3527c478bd9Sstevel@tonic-gate
3537c478bd9Sstevel@tonic-gate #ifdef STATISTICS
3547c478bd9Sstevel@tonic-gate ++bt_split;
3557c478bd9Sstevel@tonic-gate #endif
3567c478bd9Sstevel@tonic-gate /* Put the new right page for the split into place. */
3577c478bd9Sstevel@tonic-gate if ((r = __bt_new(t, &npg)) == NULL)
3587c478bd9Sstevel@tonic-gate return (NULL);
3597c478bd9Sstevel@tonic-gate r->pgno = npg;
3607c478bd9Sstevel@tonic-gate r->lower = BTDATAOFF;
3617c478bd9Sstevel@tonic-gate r->upper = t->bt_psize;
3627c478bd9Sstevel@tonic-gate r->nextpg = h->nextpg;
3637c478bd9Sstevel@tonic-gate r->prevpg = h->pgno;
3647c478bd9Sstevel@tonic-gate r->flags = h->flags & P_TYPE;
3657c478bd9Sstevel@tonic-gate
3667c478bd9Sstevel@tonic-gate /*
3677c478bd9Sstevel@tonic-gate * If we're splitting the last page on a level because we're appending
3687c478bd9Sstevel@tonic-gate * a key to it (skip is NEXTINDEX()), it's likely that the data is
3697c478bd9Sstevel@tonic-gate * sorted. Adding an empty page on the side of the level is less work
3707c478bd9Sstevel@tonic-gate * and can push the fill factor much higher than normal. If we're
3717c478bd9Sstevel@tonic-gate * wrong it's no big deal, we'll just do the split the right way next
3727c478bd9Sstevel@tonic-gate * time. It may look like it's equally easy to do a similar hack for
3737c478bd9Sstevel@tonic-gate * reverse sorted data, that is, split the tree left, but it's not.
3747c478bd9Sstevel@tonic-gate * Don't even try.
3757c478bd9Sstevel@tonic-gate */
3767c478bd9Sstevel@tonic-gate if (h->nextpg == P_INVALID && *skip == NEXTINDEX(h)) {
3777c478bd9Sstevel@tonic-gate #ifdef STATISTICS
3787c478bd9Sstevel@tonic-gate ++bt_sortsplit;
3797c478bd9Sstevel@tonic-gate #endif
3807c478bd9Sstevel@tonic-gate h->nextpg = r->pgno;
3817c478bd9Sstevel@tonic-gate r->lower = BTDATAOFF + sizeof(indx_t);
3827c478bd9Sstevel@tonic-gate *skip = 0;
3837c478bd9Sstevel@tonic-gate *lp = h;
3847c478bd9Sstevel@tonic-gate *rp = r;
3857c478bd9Sstevel@tonic-gate return (r);
3867c478bd9Sstevel@tonic-gate }
3877c478bd9Sstevel@tonic-gate
3887c478bd9Sstevel@tonic-gate /* Put the new left page for the split into place. */
3897c478bd9Sstevel@tonic-gate if ((l = (PAGE *)malloc(t->bt_psize)) == NULL) {
3907c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, r, 0);
3917c478bd9Sstevel@tonic-gate return (NULL);
3927c478bd9Sstevel@tonic-gate }
3937c478bd9Sstevel@tonic-gate #ifdef PURIFY
3947c478bd9Sstevel@tonic-gate memset(l, 0xff, t->bt_psize);
3957c478bd9Sstevel@tonic-gate #endif
3967c478bd9Sstevel@tonic-gate l->pgno = h->pgno;
3977c478bd9Sstevel@tonic-gate l->nextpg = r->pgno;
3987c478bd9Sstevel@tonic-gate l->prevpg = h->prevpg;
3997c478bd9Sstevel@tonic-gate l->lower = BTDATAOFF;
4007c478bd9Sstevel@tonic-gate l->upper = t->bt_psize;
4017c478bd9Sstevel@tonic-gate l->flags = h->flags & P_TYPE;
4027c478bd9Sstevel@tonic-gate
4037c478bd9Sstevel@tonic-gate /* Fix up the previous pointer of the page after the split page. */
4047c478bd9Sstevel@tonic-gate if (h->nextpg != P_INVALID) {
4057c478bd9Sstevel@tonic-gate if ((tp = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) {
4067c478bd9Sstevel@tonic-gate free(l);
4077c478bd9Sstevel@tonic-gate /* XXX mpool_free(t->bt_mp, r->pgno); */
4087c478bd9Sstevel@tonic-gate return (NULL);
4097c478bd9Sstevel@tonic-gate }
4107c478bd9Sstevel@tonic-gate tp->prevpg = r->pgno;
4117c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, tp, MPOOL_DIRTY);
4127c478bd9Sstevel@tonic-gate }
4137c478bd9Sstevel@tonic-gate
4147c478bd9Sstevel@tonic-gate /*
4157c478bd9Sstevel@tonic-gate * Split right. The key/data pairs aren't sorted in the btree page so
4167c478bd9Sstevel@tonic-gate * it's simpler to copy the data from the split page onto two new pages
4177c478bd9Sstevel@tonic-gate * instead of copying half the data to the right page and compacting
4187c478bd9Sstevel@tonic-gate * the left page in place. Since the left page can't change, we have
4197c478bd9Sstevel@tonic-gate * to swap the original and the allocated left page after the split.
4207c478bd9Sstevel@tonic-gate */
4217c478bd9Sstevel@tonic-gate tp = bt_psplit(t, h, l, r, skip, ilen);
4227c478bd9Sstevel@tonic-gate
4237c478bd9Sstevel@tonic-gate /* Move the new left page onto the old left page. */
4247c478bd9Sstevel@tonic-gate memmove(h, l, t->bt_psize);
4257c478bd9Sstevel@tonic-gate if (tp == l)
4267c478bd9Sstevel@tonic-gate tp = h;
4277c478bd9Sstevel@tonic-gate free(l);
4287c478bd9Sstevel@tonic-gate
4297c478bd9Sstevel@tonic-gate *lp = h;
4307c478bd9Sstevel@tonic-gate *rp = r;
4317c478bd9Sstevel@tonic-gate return (tp);
4327c478bd9Sstevel@tonic-gate }
4337c478bd9Sstevel@tonic-gate
4347c478bd9Sstevel@tonic-gate /*
4357c478bd9Sstevel@tonic-gate * BT_ROOT -- Split the root page of a btree.
4367c478bd9Sstevel@tonic-gate *
4377c478bd9Sstevel@tonic-gate * Parameters:
4387c478bd9Sstevel@tonic-gate * t: tree
4397c478bd9Sstevel@tonic-gate * h: root page
4407c478bd9Sstevel@tonic-gate * lp: pointer to left page pointer
4417c478bd9Sstevel@tonic-gate * rp: pointer to right page pointer
4427c478bd9Sstevel@tonic-gate * skip: pointer to index to leave open
4437c478bd9Sstevel@tonic-gate * ilen: insert length
4447c478bd9Sstevel@tonic-gate *
4457c478bd9Sstevel@tonic-gate * Returns:
4467c478bd9Sstevel@tonic-gate * Pointer to page in which to insert or NULL on error.
4477c478bd9Sstevel@tonic-gate */
4487c478bd9Sstevel@tonic-gate static PAGE *
bt_root(t,h,lp,rp,skip,ilen)4497c478bd9Sstevel@tonic-gate bt_root(t, h, lp, rp, skip, ilen)
4507c478bd9Sstevel@tonic-gate BTREE *t;
4517c478bd9Sstevel@tonic-gate PAGE *h, **lp, **rp;
4527c478bd9Sstevel@tonic-gate indx_t *skip;
4537c478bd9Sstevel@tonic-gate size_t ilen;
4547c478bd9Sstevel@tonic-gate {
4557c478bd9Sstevel@tonic-gate PAGE *l, *r, *tp;
4567c478bd9Sstevel@tonic-gate db_pgno_t lnpg, rnpg;
4577c478bd9Sstevel@tonic-gate
4587c478bd9Sstevel@tonic-gate #ifdef STATISTICS
4597c478bd9Sstevel@tonic-gate ++bt_split;
4607c478bd9Sstevel@tonic-gate ++bt_rootsplit;
4617c478bd9Sstevel@tonic-gate #endif
4627c478bd9Sstevel@tonic-gate /* Put the new left and right pages for the split into place. */
4637c478bd9Sstevel@tonic-gate if ((l = __bt_new(t, &lnpg)) == NULL ||
4647c478bd9Sstevel@tonic-gate (r = __bt_new(t, &rnpg)) == NULL)
4657c478bd9Sstevel@tonic-gate return (NULL);
4667c478bd9Sstevel@tonic-gate l->pgno = lnpg;
4677c478bd9Sstevel@tonic-gate r->pgno = rnpg;
4687c478bd9Sstevel@tonic-gate l->nextpg = r->pgno;
4697c478bd9Sstevel@tonic-gate r->prevpg = l->pgno;
4707c478bd9Sstevel@tonic-gate l->prevpg = r->nextpg = P_INVALID;
4717c478bd9Sstevel@tonic-gate l->lower = r->lower = BTDATAOFF;
4727c478bd9Sstevel@tonic-gate l->upper = r->upper = t->bt_psize;
4737c478bd9Sstevel@tonic-gate l->flags = r->flags = h->flags & P_TYPE;
4747c478bd9Sstevel@tonic-gate
4757c478bd9Sstevel@tonic-gate /* Split the root page. */
4767c478bd9Sstevel@tonic-gate tp = bt_psplit(t, h, l, r, skip, ilen);
4777c478bd9Sstevel@tonic-gate
4787c478bd9Sstevel@tonic-gate *lp = l;
4797c478bd9Sstevel@tonic-gate *rp = r;
4807c478bd9Sstevel@tonic-gate return (tp);
4817c478bd9Sstevel@tonic-gate }
4827c478bd9Sstevel@tonic-gate
4837c478bd9Sstevel@tonic-gate /*
4847c478bd9Sstevel@tonic-gate * BT_RROOT -- Fix up the recno root page after it has been split.
4857c478bd9Sstevel@tonic-gate *
4867c478bd9Sstevel@tonic-gate * Parameters:
4877c478bd9Sstevel@tonic-gate * t: tree
4887c478bd9Sstevel@tonic-gate * h: root page
4897c478bd9Sstevel@tonic-gate * l: left page
4907c478bd9Sstevel@tonic-gate * r: right page
4917c478bd9Sstevel@tonic-gate *
4927c478bd9Sstevel@tonic-gate * Returns:
4937c478bd9Sstevel@tonic-gate * RET_ERROR, RET_SUCCESS
4947c478bd9Sstevel@tonic-gate */
4957c478bd9Sstevel@tonic-gate static int
bt_rroot(t,h,l,r)4967c478bd9Sstevel@tonic-gate bt_rroot(t, h, l, r)
4977c478bd9Sstevel@tonic-gate BTREE *t;
4987c478bd9Sstevel@tonic-gate PAGE *h, *l, *r;
4997c478bd9Sstevel@tonic-gate {
5007c478bd9Sstevel@tonic-gate char *dest;
5017c478bd9Sstevel@tonic-gate
5027c478bd9Sstevel@tonic-gate /* Insert the left and right keys, set the header information. */
5037c478bd9Sstevel@tonic-gate h->linp[0] = h->upper = t->bt_psize - NRINTERNAL;
5047c478bd9Sstevel@tonic-gate dest = (char *)h + h->upper;
5057c478bd9Sstevel@tonic-gate WR_RINTERNAL(dest,
5067c478bd9Sstevel@tonic-gate l->flags & P_RLEAF ? NEXTINDEX(l) : rec_total(l), l->pgno);
5077c478bd9Sstevel@tonic-gate
5087c478bd9Sstevel@tonic-gate h->linp[1] = h->upper -= NRINTERNAL;
5097c478bd9Sstevel@tonic-gate dest = (char *)h + h->upper;
5107c478bd9Sstevel@tonic-gate WR_RINTERNAL(dest,
5117c478bd9Sstevel@tonic-gate r->flags & P_RLEAF ? NEXTINDEX(r) : rec_total(r), r->pgno);
5127c478bd9Sstevel@tonic-gate
5137c478bd9Sstevel@tonic-gate h->lower = BTDATAOFF + 2 * sizeof(indx_t);
5147c478bd9Sstevel@tonic-gate
5157c478bd9Sstevel@tonic-gate /* Unpin the root page, set to recno internal page. */
5167c478bd9Sstevel@tonic-gate h->flags &= ~P_TYPE;
5177c478bd9Sstevel@tonic-gate h->flags |= P_RINTERNAL;
5187c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, MPOOL_DIRTY);
5197c478bd9Sstevel@tonic-gate
5207c478bd9Sstevel@tonic-gate return (RET_SUCCESS);
5217c478bd9Sstevel@tonic-gate }
5227c478bd9Sstevel@tonic-gate
5237c478bd9Sstevel@tonic-gate /*
5247c478bd9Sstevel@tonic-gate * BT_BROOT -- Fix up the btree root page after it has been split.
5257c478bd9Sstevel@tonic-gate *
5267c478bd9Sstevel@tonic-gate * Parameters:
5277c478bd9Sstevel@tonic-gate * t: tree
5287c478bd9Sstevel@tonic-gate * h: root page
5297c478bd9Sstevel@tonic-gate * l: left page
5307c478bd9Sstevel@tonic-gate * r: right page
5317c478bd9Sstevel@tonic-gate *
5327c478bd9Sstevel@tonic-gate * Returns:
5337c478bd9Sstevel@tonic-gate * RET_ERROR, RET_SUCCESS
5347c478bd9Sstevel@tonic-gate */
5357c478bd9Sstevel@tonic-gate static int
bt_broot(t,h,l,r)5367c478bd9Sstevel@tonic-gate bt_broot(t, h, l, r)
5377c478bd9Sstevel@tonic-gate BTREE *t;
5387c478bd9Sstevel@tonic-gate PAGE *h, *l, *r;
5397c478bd9Sstevel@tonic-gate {
5407c478bd9Sstevel@tonic-gate BINTERNAL *bi;
5417c478bd9Sstevel@tonic-gate BLEAF *bl;
5427c478bd9Sstevel@tonic-gate u_int32_t nbytes;
5437c478bd9Sstevel@tonic-gate char *dest;
5447c478bd9Sstevel@tonic-gate
5457c478bd9Sstevel@tonic-gate /*
5467c478bd9Sstevel@tonic-gate * If the root page was a leaf page, change it into an internal page.
5477c478bd9Sstevel@tonic-gate * We copy the key we split on (but not the key's data, in the case of
5487c478bd9Sstevel@tonic-gate * a leaf page) to the new root page.
5497c478bd9Sstevel@tonic-gate *
5507c478bd9Sstevel@tonic-gate * The btree comparison code guarantees that the left-most key on any
5517c478bd9Sstevel@tonic-gate * level of the tree is never used, so it doesn't need to be filled in.
5527c478bd9Sstevel@tonic-gate */
5537c478bd9Sstevel@tonic-gate nbytes = NBINTERNAL(0);
5547c478bd9Sstevel@tonic-gate h->linp[0] = h->upper = t->bt_psize - nbytes;
5557c478bd9Sstevel@tonic-gate dest = (char *)h + h->upper;
5567c478bd9Sstevel@tonic-gate WR_BINTERNAL(dest, 0, l->pgno, 0);
5577c478bd9Sstevel@tonic-gate
5587c478bd9Sstevel@tonic-gate switch (h->flags & P_TYPE) {
5597c478bd9Sstevel@tonic-gate case P_BLEAF:
5607c478bd9Sstevel@tonic-gate bl = GETBLEAF(r, 0);
5617c478bd9Sstevel@tonic-gate nbytes = NBINTERNAL(bl->ksize);
5627c478bd9Sstevel@tonic-gate h->linp[1] = h->upper -= nbytes;
5637c478bd9Sstevel@tonic-gate dest = (char *)h + h->upper;
5647c478bd9Sstevel@tonic-gate WR_BINTERNAL(dest, bl->ksize, r->pgno, 0);
5657c478bd9Sstevel@tonic-gate memmove(dest, bl->bytes, bl->ksize);
5667c478bd9Sstevel@tonic-gate
5677c478bd9Sstevel@tonic-gate /*
5687c478bd9Sstevel@tonic-gate * If the key is on an overflow page, mark the overflow chain
5697c478bd9Sstevel@tonic-gate * so it isn't deleted when the leaf copy of the key is deleted.
5707c478bd9Sstevel@tonic-gate */
5717c478bd9Sstevel@tonic-gate if (bl->flags & P_BIGKEY &&
5727c478bd9Sstevel@tonic-gate bt_preserve(t, *(db_pgno_t *)bl->bytes) == RET_ERROR)
5737c478bd9Sstevel@tonic-gate return (RET_ERROR);
5747c478bd9Sstevel@tonic-gate break;
5757c478bd9Sstevel@tonic-gate case P_BINTERNAL:
5767c478bd9Sstevel@tonic-gate bi = GETBINTERNAL(r, 0);
5777c478bd9Sstevel@tonic-gate nbytes = NBINTERNAL(bi->ksize);
5787c478bd9Sstevel@tonic-gate h->linp[1] = h->upper -= nbytes;
5797c478bd9Sstevel@tonic-gate dest = (char *)h + h->upper;
5807c478bd9Sstevel@tonic-gate memmove(dest, bi, nbytes);
5817c478bd9Sstevel@tonic-gate ((BINTERNAL *)dest)->pgno = r->pgno;
5827c478bd9Sstevel@tonic-gate break;
5837c478bd9Sstevel@tonic-gate default:
5847c478bd9Sstevel@tonic-gate abort();
5857c478bd9Sstevel@tonic-gate }
5867c478bd9Sstevel@tonic-gate
5877c478bd9Sstevel@tonic-gate /* There are two keys on the page. */
5887c478bd9Sstevel@tonic-gate h->lower = BTDATAOFF + 2 * sizeof(indx_t);
5897c478bd9Sstevel@tonic-gate
5907c478bd9Sstevel@tonic-gate /* Unpin the root page, set to btree internal page. */
5917c478bd9Sstevel@tonic-gate h->flags &= ~P_TYPE;
5927c478bd9Sstevel@tonic-gate h->flags |= P_BINTERNAL;
5937c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, MPOOL_DIRTY);
5947c478bd9Sstevel@tonic-gate
5957c478bd9Sstevel@tonic-gate return (RET_SUCCESS);
5967c478bd9Sstevel@tonic-gate }
5977c478bd9Sstevel@tonic-gate
5987c478bd9Sstevel@tonic-gate /*
5997c478bd9Sstevel@tonic-gate * BT_PSPLIT -- Do the real work of splitting the page.
6007c478bd9Sstevel@tonic-gate *
6017c478bd9Sstevel@tonic-gate * Parameters:
6027c478bd9Sstevel@tonic-gate * t: tree
6037c478bd9Sstevel@tonic-gate * h: page to be split
6047c478bd9Sstevel@tonic-gate * l: page to put lower half of data
6057c478bd9Sstevel@tonic-gate * r: page to put upper half of data
6067c478bd9Sstevel@tonic-gate * pskip: pointer to index to leave open
6077c478bd9Sstevel@tonic-gate * ilen: insert length
6087c478bd9Sstevel@tonic-gate *
6097c478bd9Sstevel@tonic-gate * Returns:
6107c478bd9Sstevel@tonic-gate * Pointer to page in which to insert.
6117c478bd9Sstevel@tonic-gate */
6127c478bd9Sstevel@tonic-gate static PAGE *
bt_psplit(t,h,l,r,pskip,ilen)6137c478bd9Sstevel@tonic-gate bt_psplit(t, h, l, r, pskip, ilen)
6147c478bd9Sstevel@tonic-gate BTREE *t;
6157c478bd9Sstevel@tonic-gate PAGE *h, *l, *r;
6167c478bd9Sstevel@tonic-gate indx_t *pskip;
6177c478bd9Sstevel@tonic-gate size_t ilen;
6187c478bd9Sstevel@tonic-gate {
6197c478bd9Sstevel@tonic-gate BINTERNAL *bi;
6207c478bd9Sstevel@tonic-gate BLEAF *bl;
6217c478bd9Sstevel@tonic-gate CURSOR *c;
6227c478bd9Sstevel@tonic-gate RLEAF *rl;
6237c478bd9Sstevel@tonic-gate PAGE *rval;
6247c478bd9Sstevel@tonic-gate void *src;
6257c478bd9Sstevel@tonic-gate indx_t full, half, nxt, off, skip, top, used;
6267c478bd9Sstevel@tonic-gate u_int32_t nbytes;
6277c478bd9Sstevel@tonic-gate int bigkeycnt, isbigkey;
6287c478bd9Sstevel@tonic-gate
6297c478bd9Sstevel@tonic-gate /*
6307c478bd9Sstevel@tonic-gate * Split the data to the left and right pages. Leave the skip index
6317c478bd9Sstevel@tonic-gate * open. Additionally, make some effort not to split on an overflow
6327c478bd9Sstevel@tonic-gate * key. This makes internal page processing faster and can save
6337c478bd9Sstevel@tonic-gate * space as overflow keys used by internal pages are never deleted.
6347c478bd9Sstevel@tonic-gate */
6357c478bd9Sstevel@tonic-gate bigkeycnt = 0;
6367c478bd9Sstevel@tonic-gate skip = *pskip;
6377c478bd9Sstevel@tonic-gate full = t->bt_psize - BTDATAOFF;
6387c478bd9Sstevel@tonic-gate half = full / 2;
6397c478bd9Sstevel@tonic-gate used = 0;
6407c478bd9Sstevel@tonic-gate for (nxt = off = 0, top = NEXTINDEX(h); nxt < top; ++off) {
6417c478bd9Sstevel@tonic-gate if (skip == off) {
6427c478bd9Sstevel@tonic-gate nbytes = ilen;
6437c478bd9Sstevel@tonic-gate isbigkey = 0; /* XXX: not really known. */
6447c478bd9Sstevel@tonic-gate } else
6457c478bd9Sstevel@tonic-gate switch (h->flags & P_TYPE) {
6467c478bd9Sstevel@tonic-gate case P_BINTERNAL:
6477c478bd9Sstevel@tonic-gate src = bi = GETBINTERNAL(h, nxt);
6487c478bd9Sstevel@tonic-gate nbytes = NBINTERNAL(bi->ksize);
6497c478bd9Sstevel@tonic-gate isbigkey = bi->flags & P_BIGKEY;
6507c478bd9Sstevel@tonic-gate break;
6517c478bd9Sstevel@tonic-gate case P_BLEAF:
6527c478bd9Sstevel@tonic-gate src = bl = GETBLEAF(h, nxt);
6537c478bd9Sstevel@tonic-gate nbytes = NBLEAF(bl);
6547c478bd9Sstevel@tonic-gate isbigkey = bl->flags & P_BIGKEY;
6557c478bd9Sstevel@tonic-gate break;
6567c478bd9Sstevel@tonic-gate case P_RINTERNAL:
6577c478bd9Sstevel@tonic-gate src = GETRINTERNAL(h, nxt);
6587c478bd9Sstevel@tonic-gate nbytes = NRINTERNAL;
6597c478bd9Sstevel@tonic-gate isbigkey = 0;
6607c478bd9Sstevel@tonic-gate break;
6617c478bd9Sstevel@tonic-gate case P_RLEAF:
6627c478bd9Sstevel@tonic-gate src = rl = GETRLEAF(h, nxt);
6637c478bd9Sstevel@tonic-gate nbytes = NRLEAF(rl);
6647c478bd9Sstevel@tonic-gate isbigkey = 0;
6657c478bd9Sstevel@tonic-gate break;
6667c478bd9Sstevel@tonic-gate default:
6677c478bd9Sstevel@tonic-gate abort();
6687c478bd9Sstevel@tonic-gate }
6697c478bd9Sstevel@tonic-gate
6707c478bd9Sstevel@tonic-gate /*
6717c478bd9Sstevel@tonic-gate * If the key/data pairs are substantial fractions of the max
6727c478bd9Sstevel@tonic-gate * possible size for the page, it's possible to get situations
6737c478bd9Sstevel@tonic-gate * where we decide to try and copy too much onto the left page.
6747c478bd9Sstevel@tonic-gate * Make sure that doesn't happen.
6757c478bd9Sstevel@tonic-gate */
6767c478bd9Sstevel@tonic-gate if ((skip <= off && used + nbytes + sizeof(indx_t) >= full)
6777c478bd9Sstevel@tonic-gate || nxt == top - 1) {
6787c478bd9Sstevel@tonic-gate --off;
6797c478bd9Sstevel@tonic-gate break;
6807c478bd9Sstevel@tonic-gate }
6817c478bd9Sstevel@tonic-gate
6827c478bd9Sstevel@tonic-gate /* Copy the key/data pair, if not the skipped index. */
6837c478bd9Sstevel@tonic-gate if (skip != off) {
6847c478bd9Sstevel@tonic-gate ++nxt;
6857c478bd9Sstevel@tonic-gate
6867c478bd9Sstevel@tonic-gate l->linp[off] = l->upper -= nbytes;
6877c478bd9Sstevel@tonic-gate memmove((char *)l + l->upper, src, nbytes);
6887c478bd9Sstevel@tonic-gate }
6897c478bd9Sstevel@tonic-gate
6907c478bd9Sstevel@tonic-gate used += nbytes + sizeof(indx_t);
6917c478bd9Sstevel@tonic-gate if (used >= half) {
6927c478bd9Sstevel@tonic-gate if (!isbigkey || bigkeycnt == 3)
6937c478bd9Sstevel@tonic-gate break;
6947c478bd9Sstevel@tonic-gate else
6957c478bd9Sstevel@tonic-gate ++bigkeycnt;
6967c478bd9Sstevel@tonic-gate }
6977c478bd9Sstevel@tonic-gate }
6987c478bd9Sstevel@tonic-gate
6997c478bd9Sstevel@tonic-gate /*
7007c478bd9Sstevel@tonic-gate * Off is the last offset that's valid for the left page.
7017c478bd9Sstevel@tonic-gate * Nxt is the first offset to be placed on the right page.
7027c478bd9Sstevel@tonic-gate */
7037c478bd9Sstevel@tonic-gate l->lower += (off + 1) * sizeof(indx_t);
7047c478bd9Sstevel@tonic-gate
7057c478bd9Sstevel@tonic-gate /*
7067c478bd9Sstevel@tonic-gate * If splitting the page that the cursor was on, the cursor has to be
7077c478bd9Sstevel@tonic-gate * adjusted to point to the same record as before the split. If the
7087c478bd9Sstevel@tonic-gate * cursor is at or past the skipped slot, the cursor is incremented by
7097c478bd9Sstevel@tonic-gate * one. If the cursor is on the right page, it is decremented by the
7107c478bd9Sstevel@tonic-gate * number of records split to the left page.
7117c478bd9Sstevel@tonic-gate */
7127c478bd9Sstevel@tonic-gate c = &t->bt_cursor;
7137c478bd9Sstevel@tonic-gate if (F_ISSET(c, CURS_INIT) && c->pg.pgno == h->pgno) {
7147c478bd9Sstevel@tonic-gate if (c->pg.index >= skip)
7157c478bd9Sstevel@tonic-gate ++c->pg.index;
7167c478bd9Sstevel@tonic-gate if (c->pg.index < nxt) /* Left page. */
7177c478bd9Sstevel@tonic-gate c->pg.pgno = l->pgno;
7187c478bd9Sstevel@tonic-gate else { /* Right page. */
7197c478bd9Sstevel@tonic-gate c->pg.pgno = r->pgno;
7207c478bd9Sstevel@tonic-gate c->pg.index -= nxt;
7217c478bd9Sstevel@tonic-gate }
7227c478bd9Sstevel@tonic-gate }
7237c478bd9Sstevel@tonic-gate
7247c478bd9Sstevel@tonic-gate /*
7257c478bd9Sstevel@tonic-gate * If the skipped index was on the left page, just return that page.
7267c478bd9Sstevel@tonic-gate * Otherwise, adjust the skip index to reflect the new position on
7277c478bd9Sstevel@tonic-gate * the right page.
7287c478bd9Sstevel@tonic-gate */
7297c478bd9Sstevel@tonic-gate if (skip <= off) {
730*3605ad6fSsemery /*
731*3605ad6fSsemery * If we get here then 'skip' is in the left page. We do
732*3605ad6fSsemery * not want to mix this with the right page, so we assign
733*3605ad6fSsemery * an unrealistic value (-1).
734*3605ad6fSsemery */
735*3605ad6fSsemery skip = (indx_t)-1;
7367c478bd9Sstevel@tonic-gate rval = l;
7377c478bd9Sstevel@tonic-gate } else {
7387c478bd9Sstevel@tonic-gate rval = r;
7397c478bd9Sstevel@tonic-gate *pskip -= nxt;
7407c478bd9Sstevel@tonic-gate }
7417c478bd9Sstevel@tonic-gate
7427c478bd9Sstevel@tonic-gate for (off = 0; nxt < top; ++off) {
7437c478bd9Sstevel@tonic-gate if (skip == nxt) {
7447c478bd9Sstevel@tonic-gate ++off;
745*3605ad6fSsemery /*
746*3605ad6fSsemery * Assign 'skip' an unrealistic value (-1) to ensure
747*3605ad6fSsemery * it is not matched again.
748*3605ad6fSsemery */
749*3605ad6fSsemery skip = (indx_t)-1;
7507c478bd9Sstevel@tonic-gate }
7517c478bd9Sstevel@tonic-gate switch (h->flags & P_TYPE) {
7527c478bd9Sstevel@tonic-gate case P_BINTERNAL:
7537c478bd9Sstevel@tonic-gate src = bi = GETBINTERNAL(h, nxt);
7547c478bd9Sstevel@tonic-gate nbytes = NBINTERNAL(bi->ksize);
7557c478bd9Sstevel@tonic-gate break;
7567c478bd9Sstevel@tonic-gate case P_BLEAF:
7577c478bd9Sstevel@tonic-gate src = bl = GETBLEAF(h, nxt);
7587c478bd9Sstevel@tonic-gate nbytes = NBLEAF(bl);
7597c478bd9Sstevel@tonic-gate break;
7607c478bd9Sstevel@tonic-gate case P_RINTERNAL:
7617c478bd9Sstevel@tonic-gate src = GETRINTERNAL(h, nxt);
7627c478bd9Sstevel@tonic-gate nbytes = NRINTERNAL;
7637c478bd9Sstevel@tonic-gate break;
7647c478bd9Sstevel@tonic-gate case P_RLEAF:
7657c478bd9Sstevel@tonic-gate src = rl = GETRLEAF(h, nxt);
7667c478bd9Sstevel@tonic-gate nbytes = NRLEAF(rl);
7677c478bd9Sstevel@tonic-gate break;
7687c478bd9Sstevel@tonic-gate default:
7697c478bd9Sstevel@tonic-gate abort();
7707c478bd9Sstevel@tonic-gate }
7717c478bd9Sstevel@tonic-gate ++nxt;
7727c478bd9Sstevel@tonic-gate r->linp[off] = r->upper -= nbytes;
7737c478bd9Sstevel@tonic-gate memmove((char *)r + r->upper, src, nbytes);
7747c478bd9Sstevel@tonic-gate }
7757c478bd9Sstevel@tonic-gate r->lower += off * sizeof(indx_t);
7767c478bd9Sstevel@tonic-gate
7777c478bd9Sstevel@tonic-gate /* If the key is being appended to the page, adjust the index. */
7787c478bd9Sstevel@tonic-gate if (skip == top)
7797c478bd9Sstevel@tonic-gate r->lower += sizeof(indx_t);
7807c478bd9Sstevel@tonic-gate
7817c478bd9Sstevel@tonic-gate return (rval);
7827c478bd9Sstevel@tonic-gate }
7837c478bd9Sstevel@tonic-gate
7847c478bd9Sstevel@tonic-gate /*
7857c478bd9Sstevel@tonic-gate * BT_PRESERVE -- Mark a chain of pages as used by an internal node.
7867c478bd9Sstevel@tonic-gate *
7877c478bd9Sstevel@tonic-gate * Chains of indirect blocks pointed to by leaf nodes get reclaimed when the
7887c478bd9Sstevel@tonic-gate * record that references them gets deleted. Chains pointed to by internal
7897c478bd9Sstevel@tonic-gate * pages never get deleted. This routine marks a chain as pointed to by an
7907c478bd9Sstevel@tonic-gate * internal page.
7917c478bd9Sstevel@tonic-gate *
7927c478bd9Sstevel@tonic-gate * Parameters:
7937c478bd9Sstevel@tonic-gate * t: tree
7947c478bd9Sstevel@tonic-gate * pg: page number of first page in the chain.
7957c478bd9Sstevel@tonic-gate *
7967c478bd9Sstevel@tonic-gate * Returns:
7977c478bd9Sstevel@tonic-gate * RET_SUCCESS, RET_ERROR.
7987c478bd9Sstevel@tonic-gate */
7997c478bd9Sstevel@tonic-gate static int
bt_preserve(t,pg)8007c478bd9Sstevel@tonic-gate bt_preserve(t, pg)
8017c478bd9Sstevel@tonic-gate BTREE *t;
8027c478bd9Sstevel@tonic-gate db_pgno_t pg;
8037c478bd9Sstevel@tonic-gate {
8047c478bd9Sstevel@tonic-gate PAGE *h;
8057c478bd9Sstevel@tonic-gate
8067c478bd9Sstevel@tonic-gate if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
8077c478bd9Sstevel@tonic-gate return (RET_ERROR);
8087c478bd9Sstevel@tonic-gate h->flags |= P_PRESERVE;
8097c478bd9Sstevel@tonic-gate mpool_put(t->bt_mp, h, MPOOL_DIRTY);
8107c478bd9Sstevel@tonic-gate return (RET_SUCCESS);
8117c478bd9Sstevel@tonic-gate }
8127c478bd9Sstevel@tonic-gate
8137c478bd9Sstevel@tonic-gate /*
8147c478bd9Sstevel@tonic-gate * REC_TOTAL -- Return the number of recno entries below a page.
8157c478bd9Sstevel@tonic-gate *
8167c478bd9Sstevel@tonic-gate * Parameters:
8177c478bd9Sstevel@tonic-gate * h: page
8187c478bd9Sstevel@tonic-gate *
8197c478bd9Sstevel@tonic-gate * Returns:
8207c478bd9Sstevel@tonic-gate * The number of recno entries below a page.
8217c478bd9Sstevel@tonic-gate *
8227c478bd9Sstevel@tonic-gate * XXX
8237c478bd9Sstevel@tonic-gate * These values could be set by the bt_psplit routine. The problem is that the
8247c478bd9Sstevel@tonic-gate * entry has to be popped off of the stack etc. or the values have to be passed
8257c478bd9Sstevel@tonic-gate * all the way back to bt_split/bt_rroot and it's not very clean.
8267c478bd9Sstevel@tonic-gate */
8277c478bd9Sstevel@tonic-gate static recno_t
rec_total(h)8287c478bd9Sstevel@tonic-gate rec_total(h)
8297c478bd9Sstevel@tonic-gate PAGE *h;
8307c478bd9Sstevel@tonic-gate {
8317c478bd9Sstevel@tonic-gate recno_t recs;
8327c478bd9Sstevel@tonic-gate indx_t nxt, top;
8337c478bd9Sstevel@tonic-gate
8347c478bd9Sstevel@tonic-gate for (recs = 0, nxt = 0, top = NEXTINDEX(h); nxt < top; ++nxt)
8357c478bd9Sstevel@tonic-gate recs += GETRINTERNAL(h, nxt)->nrecs;
8367c478bd9Sstevel@tonic-gate return (recs);
8377c478bd9Sstevel@tonic-gate }
838