Replace Berkeley DB with SQLite 3

There were some bugs in the very ancient version of Berkeley DB that Asterisk
used. Instead of spending the time tracking down the bugs in the Berkeley code
we move to the much better documented SQLite 3.

Conversion of the old astdb happens at runtime by running the included
astdb2sqlite3 utility. The ast_db API with SQLite 3 backend should behave
identically to the old Berkeley backend, but in the future we could offer a
much more robust interface.

We do not include the SQLite 3 library in the source tree, but instead rely
upon the distribution-provided libraries. SQLite is so ubiquitous that this
should not place undue burden on administrators.


git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@326589 65c4cc65-6c06-0410-ace0-fbb531ad65f3

15 files changed, 0 insertions, 4824 deletions

diff --git a/main/db1-ast/btree/bt_close.c b/main/db1-ast/btree/bt_close.c
deleted file mode 100644
index 67a6e5340..000000000
--- a/main/db1-ast/btree/bt_close.c
+++ /dev/null
@@ -1,182 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_close.c	8.7 (Berkeley) 8/17/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/param.h>
-
-#include <errno.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-static int bt_meta __P((BTREE *));
-
-/*
- * BT_CLOSE -- Close a btree.
- *
- * Parameters:
- *	dbp:	pointer to access method
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- */
-int
-__bt_close(dbp)
-	DB *dbp;
-{
-	BTREE *t;
-	int fd;
-
-	t = dbp->internal;
-
-	/* Toss any page pinned across calls. */
-	if (t->bt_pinned != NULL) {
-		mpool_put(t->bt_mp, t->bt_pinned, 0);
-		t->bt_pinned = NULL;
-	}
-
-	/* Sync the tree. */
-	if (__bt_sync(dbp, 0) == RET_ERROR)
-		return (RET_ERROR);
-
-	/* Close the memory pool. */
-	if (mpool_close(t->bt_mp) == RET_ERROR)
-		return (RET_ERROR);
-
-	/* Free random memory. */
-	if (t->bt_cursor.key.data != NULL) {
-		free(t->bt_cursor.key.data);
-		t->bt_cursor.key.size = 0;
-		t->bt_cursor.key.data = NULL;
-	}
-	if (t->bt_rkey.data) {
-		free(t->bt_rkey.data);
-		t->bt_rkey.size = 0;
-		t->bt_rkey.data = NULL;
-	}
-	if (t->bt_rdata.data) {
-		free(t->bt_rdata.data);
-		t->bt_rdata.size = 0;
-		t->bt_rdata.data = NULL;
-	}
-
-	fd = t->bt_fd;
-	free(t);
-	free(dbp);
-	return (close(fd) ? RET_ERROR : RET_SUCCESS);
-}
-
-/*
- * BT_SYNC -- sync the btree to disk.
- *
- * Parameters:
- *	dbp:	pointer to access method
- *
- * Returns:
- *	RET_SUCCESS, RET_ERROR.
- */
-int
-__bt_sync(dbp, flags)
-	const DB *dbp;
-	u_int flags;
-{
-	BTREE *t;
-	int status;
-
-	t = dbp->internal;
-
-	/* Toss any page pinned across calls. */
-	if (t->bt_pinned != NULL) {
-		mpool_put(t->bt_mp, t->bt_pinned, 0);
-		t->bt_pinned = NULL;
-	}
-
-	/* Sync doesn't currently take any flags. */
-	if (flags != 0) {
-		errno = EINVAL;
-		return (RET_ERROR);
-	}
-
-	if (F_ISSET(t, B_INMEM | B_RDONLY) || !F_ISSET(t, B_MODIFIED))
-		return (RET_SUCCESS);
-
-	if (F_ISSET(t, B_METADIRTY) && bt_meta(t) == RET_ERROR)
-		return (RET_ERROR);
-
-	if ((status = mpool_sync(t->bt_mp)) == RET_SUCCESS)
-		F_CLR(t, B_MODIFIED);
-
-	return (status);
-}
-
-/*
- * BT_META -- write the tree meta data to disk.
- *
- * Parameters:
- *	t:	tree
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- */
-static int
-bt_meta(t)
-	BTREE *t;
-{
-	BTMETA m;
-	void *p;
-
-	if ((p = mpool_get(t->bt_mp, P_META, 0)) == NULL)
-		return (RET_ERROR);
-
-	/* Fill in metadata. */
-	m.magic = BTREEMAGIC;
-	m.version = BTREEVERSION;
-	m.psize = t->bt_psize;
-	m.free = t->bt_free;
-	m.nrecs = t->bt_nrecs;
-	m.flags = F_ISSET(t, SAVEMETA);
-
-	memmove(p, &m, sizeof(BTMETA));
-	mpool_put(t->bt_mp, p, MPOOL_DIRTY);
-	return (RET_SUCCESS);
-}
diff --git a/main/db1-ast/btree/bt_conv.c b/main/db1-ast/btree/bt_conv.c
deleted file mode 100644
index d2ebdc57b..000000000
--- a/main/db1-ast/btree/bt_conv.c
+++ /dev/null
@@ -1,221 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_conv.c	8.5 (Berkeley) 8/17/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/param.h>
-
-#include <stdio.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-static void mswap __P((PAGE *));
-
-/*
- * __BT_BPGIN, __BT_BPGOUT --
- *	Convert host-specific number layout to/from the host-independent
- *	format stored on disk.
- *
- * Parameters:
- *	t:	tree
- *	pg:	page number
- *	h:	page to convert
- */
-void
-__bt_pgin(t, pg, pp)
-	void *t;
-	pgno_t pg;
-	void *pp;
-{
-	PAGE *h;
-	indx_t i, top;
-	u_char flags;
-	char *p;
-
-	if (!F_ISSET(((BTREE *)t), B_NEEDSWAP))
-		return;
-	if (pg == P_META) {
-		mswap(pp);
-		return;
-	}
-
-	h = pp;
-	M_32_SWAP(h->pgno);
-	M_32_SWAP(h->prevpg);
-	M_32_SWAP(h->nextpg);
-	M_32_SWAP(h->flags);
-	M_16_SWAP(h->lower);
-	M_16_SWAP(h->upper);
-
-	top = NEXTINDEX(h);
-	if ((h->flags & P_TYPE) == P_BINTERNAL)
-		for (i = 0; i < top; i++) {
-			M_16_SWAP(h->linp[i]);
-			p = (char *)GETBINTERNAL(h, i);
-			P_32_SWAP(p);
-			p += sizeof(u_int32_t);
-			P_32_SWAP(p);
-			p += sizeof(pgno_t);
-			if (*(u_char *)p & P_BIGKEY) {
-				p += sizeof(u_char);
-				P_32_SWAP(p);
-				p += sizeof(pgno_t);
-				P_32_SWAP(p);
-			}
-		}
-	else if ((h->flags & P_TYPE) == P_BLEAF)
-		for (i = 0; i < top; i++) {
-			M_16_SWAP(h->linp[i]);
-			p = (char *)GETBLEAF(h, i);
-			P_32_SWAP(p);
-			p += sizeof(u_int32_t);
-			P_32_SWAP(p);
-			p += sizeof(u_int32_t);
-			flags = *(u_char *)p;
-			if (flags & (P_BIGKEY | P_BIGDATA)) {
-				p += sizeof(u_char);
-				if (flags & P_BIGKEY) {
-					P_32_SWAP(p);
-					p += sizeof(pgno_t);
-					P_32_SWAP(p);
-				}
-				if (flags & P_BIGDATA) {
-					p += sizeof(u_int32_t);
-					P_32_SWAP(p);
-					p += sizeof(pgno_t);
-					P_32_SWAP(p);
-				}
-			}
-		}
-}
-
-void
-__bt_pgout(t, pg, pp)
-	void *t;
-	pgno_t pg;
-	void *pp;
-{
-	PAGE *h;
-	indx_t i, top;
-	u_char flags;
-	char *p;
-
-	if (!F_ISSET(((BTREE *)t), B_NEEDSWAP))
-		return;
-	if (pg == P_META) {
-		mswap(pp);
-		return;
-	}
-
-	h = pp;
-	top = NEXTINDEX(h);
-	if ((h->flags & P_TYPE) == P_BINTERNAL)
-		for (i = 0; i < top; i++) {
-			p = (char *)GETBINTERNAL(h, i);
-			P_32_SWAP(p);
-			p += sizeof(u_int32_t);
-			P_32_SWAP(p);
-			p += sizeof(pgno_t);
-			if (*(u_char *)p & P_BIGKEY) {
-				p += sizeof(u_char);
-				P_32_SWAP(p);
-				p += sizeof(pgno_t);
-				P_32_SWAP(p);
-			}
-			M_16_SWAP(h->linp[i]);
-		}
-	else if ((h->flags & P_TYPE) == P_BLEAF)
-		for (i = 0; i < top; i++) {
-			p = (char *)GETBLEAF(h, i);
-			P_32_SWAP(p);
-			p += sizeof(u_int32_t);
-			P_32_SWAP(p);
-			p += sizeof(u_int32_t);
-			flags = *(u_char *)p;
-			if (flags & (P_BIGKEY | P_BIGDATA)) {
-				p += sizeof(u_char);
-				if (flags & P_BIGKEY) {
-					P_32_SWAP(p);
-					p += sizeof(pgno_t);
-					P_32_SWAP(p);
-				}
-				if (flags & P_BIGDATA) {
-					p += sizeof(u_int32_t);
-					P_32_SWAP(p);
-					p += sizeof(pgno_t);
-					P_32_SWAP(p);
-				}
-			}
-			M_16_SWAP(h->linp[i]);
-		}
-
-	M_32_SWAP(h->pgno);
-	M_32_SWAP(h->prevpg);
-	M_32_SWAP(h->nextpg);
-	M_32_SWAP(h->flags);
-	M_16_SWAP(h->lower);
-	M_16_SWAP(h->upper);
-}
-
-/*
- * MSWAP -- Actually swap the bytes on the meta page.
- *
- * Parameters:
- *	p:	page to convert
- */
-static void
-mswap(pg)
-	PAGE *pg;
-{
-	char *p;
-
-	p = (char *)pg;
-	P_32_SWAP(p);		/* magic */
-	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* version */
-	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* psize */
-	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* free */
-	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* nrecs */
-	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* flags */
-	p += sizeof(u_int32_t);
-}
diff --git a/main/db1-ast/btree/bt_debug.c b/main/db1-ast/btree/bt_debug.c
deleted file mode 100644
index e035851a8..000000000
--- a/main/db1-ast/btree/bt_debug.c
+++ /dev/null
@@ -1,329 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_debug.c	8.5 (Berkeley) 8/17/94";
-#endif /* LIBC_SCCS and not lint */
-
-#ifdef DEBUG
-#include <sys/param.h>
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-/*
- * BT_DUMP -- Dump the tree
- *
- * Parameters:
- *	dbp:	pointer to the DB
- */
-void
-__bt_dump(dbp)
-	DB *dbp;
-{
-	BTREE *t;
-	PAGE *h;
-	pgno_t i;
-	char *sep;
-
-	t = dbp->internal;
-	(void)fprintf(stderr, "%s: pgsz %d",
-	    F_ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize);
-	if (F_ISSET(t, R_RECNO))
-		(void)fprintf(stderr, " keys %lu", t->bt_nrecs);
-#undef X
-#define	X(flag, name) \
-	if (F_ISSET(t, flag)) { \
-		(void)fprintf(stderr, "%s%s", sep, name); \
-		sep = ", "; \
-	}
-	if (t->flags != 0) {
-		sep = " flags (";
-		X(R_FIXLEN,	"FIXLEN");
-		X(B_INMEM,	"INMEM");
-		X(B_NODUPS,	"NODUPS");
-		X(B_RDONLY,	"RDONLY");
-		X(R_RECNO,	"RECNO");
-		X(B_METADIRTY,"METADIRTY");
-		(void)fprintf(stderr, ")\n");
-	}
-#undef X
-
-	for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) {
-		__bt_dpage(h);
-		(void)mpool_put(t->bt_mp, h, 0);
-	}
-}
-
-/*
- * BT_DMPAGE -- Dump the meta page
- *
- * Parameters:
- *	h:	pointer to the PAGE
- */
-void
-__bt_dmpage(h)
-	PAGE *h;
-{
-	BTMETA *m;
-	char *sep;
-
-	m = (BTMETA *)h;
-	(void)fprintf(stderr, "magic %lx\n", m->magic);
-	(void)fprintf(stderr, "version %lu\n", m->version);
-	(void)fprintf(stderr, "psize %lu\n", m->psize);
-	(void)fprintf(stderr, "free %lu\n", m->free);
-	(void)fprintf(stderr, "nrecs %lu\n", m->nrecs);
-	(void)fprintf(stderr, "flags %lu", m->flags);
-#undef X
-#define	X(flag, name) \
-	if (m->flags & flag) { \
-		(void)fprintf(stderr, "%s%s", sep, name); \
-		sep = ", "; \
-	}
-	if (m->flags) {
-		sep = " (";
-		X(B_NODUPS,	"NODUPS");
-		X(R_RECNO,	"RECNO");
-		(void)fprintf(stderr, ")");
-	}
-}
-
-/*
- * BT_DNPAGE -- Dump the page
- *
- * Parameters:
- *	n:	page number to dump.
- */
-void
-__bt_dnpage(dbp, pgno)
-	DB *dbp;
-	pgno_t pgno;
-{
-	BTREE *t;
-	PAGE *h;
-
-	t = dbp->internal;
-	if ((h = mpool_get(t->bt_mp, pgno, 0)) != NULL) {
-		__bt_dpage(h);
-		(void)mpool_put(t->bt_mp, h, 0);
-	}
-}
-
-/*
- * BT_DPAGE -- Dump the page
- *
- * Parameters:
- *	h:	pointer to the PAGE
- */
-void
-__bt_dpage(h)
-	PAGE *h;
-{
-	BINTERNAL *bi;
-	BLEAF *bl;
-	RINTERNAL *ri;
-	RLEAF *rl;
-	indx_t cur, top;
-	char *sep;
-
-	(void)fprintf(stderr, "    page %d: (", h->pgno);
-#undef X
-#define	X(flag, name) \
-	if (h->flags & flag) { \
-		(void)fprintf(stderr, "%s%s", sep, name); \
-		sep = ", "; \
-	}
-	sep = "";
-	X(P_BINTERNAL,	"BINTERNAL")		/* types */
-	X(P_BLEAF,	"BLEAF")
-	X(P_RINTERNAL,	"RINTERNAL")		/* types */
-	X(P_RLEAF,	"RLEAF")
-	X(P_OVERFLOW,	"OVERFLOW")
-	X(P_PRESERVE,	"PRESERVE");
-	(void)fprintf(stderr, ")\n");
-#undef X
-
-	(void)fprintf(stderr, "\tprev %2d next %2d", h->prevpg, h->nextpg);
-	if (h->flags & P_OVERFLOW)
-		return;
-
-	top = NEXTINDEX(h);
-	(void)fprintf(stderr, " lower %3d upper %3d nextind %d\n",
-	    h->lower, h->upper, top);
-	for (cur = 0; cur < top; cur++) {
-		(void)fprintf(stderr, "\t[%03d] %4d ", cur, h->linp[cur]);
-		switch (h->flags & P_TYPE) {
-		case P_BINTERNAL:
-			bi = GETBINTERNAL(h, cur);
-			(void)fprintf(stderr,
-			    "size %03d pgno %03d", bi->ksize, bi->pgno);
-			if (bi->flags & P_BIGKEY)
-				(void)fprintf(stderr, " (indirect)");
-			else if (bi->ksize)
-				(void)fprintf(stderr,
-				    " {%.*s}", (int)bi->ksize, bi->bytes);
-			break;
-		case P_RINTERNAL:
-			ri = GETRINTERNAL(h, cur);
-			(void)fprintf(stderr, "entries %03d pgno %03d",
-				ri->nrecs, ri->pgno);
-			break;
-		case P_BLEAF:
-			bl = GETBLEAF(h, cur);
-			if (bl->flags & P_BIGKEY)
-				(void)fprintf(stderr,
-				    "big key page %lu size %u/",
-				    *(pgno_t *)bl->bytes,
-				    *(u_int32_t *)(bl->bytes + sizeof(pgno_t)));
-			else if (bl->ksize)
-				(void)fprintf(stderr, "%s/", bl->bytes);
-			if (bl->flags & P_BIGDATA)
-				(void)fprintf(stderr,
-				    "big data page %lu size %u",
-				    *(pgno_t *)(bl->bytes + bl->ksize),
-				    *(u_int32_t *)(bl->bytes + bl->ksize +
-				    sizeof(pgno_t)));
-			else if (bl->dsize)
-				(void)fprintf(stderr, "%.*s",
-				    (int)bl->dsize, bl->bytes + bl->ksize);
-			break;
-		case P_RLEAF:
-			rl = GETRLEAF(h, cur);
-			if (rl->flags & P_BIGDATA)
-				(void)fprintf(stderr,
-				    "big data page %lu size %u",
-				    *(pgno_t *)rl->bytes,
-				    *(u_int32_t *)(rl->bytes + sizeof(pgno_t)));
-			else if (rl->dsize)
-				(void)fprintf(stderr,
-				    "%.*s", (int)rl->dsize, rl->bytes);
-			break;
-		}
-		(void)fprintf(stderr, "\n");
-	}
-}
-#endif
-
-#ifdef STATISTICS
-/*
- * BT_STAT -- Gather/print the tree statistics
- *
- * Parameters:
- *	dbp:	pointer to the DB
- */
-void
-__bt_stat(dbp)
-	DB *dbp;
-{
-	extern u_long bt_cache_hit, bt_cache_miss, bt_pfxsaved, bt_rootsplit;
-	extern u_long bt_sortsplit, bt_split;
-	BTREE *t;
-	PAGE *h;
-	pgno_t i, pcont, pinternal, pleaf;
-	u_long ifree, lfree, nkeys;
-	int levels;
-
-	t = dbp->internal;
-	pcont = pinternal = pleaf = 0;
-	nkeys = ifree = lfree = 0;
-	for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) {
-		switch (h->flags & P_TYPE) {
-		case P_BINTERNAL:
-		case P_RINTERNAL:
-			++pinternal;
-			ifree += h->upper - h->lower;
-			break;
-		case P_BLEAF:
-		case P_RLEAF:
-			++pleaf;
-			lfree += h->upper - h->lower;
-			nkeys += NEXTINDEX(h);
-			break;
-		case P_OVERFLOW:
-			++pcont;
-			break;
-		}
-		(void)mpool_put(t->bt_mp, h, 0);
-	}
-
-	/* Count the levels of the tree. */
-	for (i = P_ROOT, levels = 0 ;; ++levels) {
-		h = mpool_get(t->bt_mp, i, 0);
-		if (h->flags & (P_BLEAF|P_RLEAF)) {
-			if (levels == 0)
-				levels = 1;
-			(void)mpool_put(t->bt_mp, h, 0);
-			break;
-		}
-		i = F_ISSET(t, R_RECNO) ?
-		    GETRINTERNAL(h, 0)->pgno :
-		    GETBINTERNAL(h, 0)->pgno;
-		(void)mpool_put(t->bt_mp, h, 0);
-	}
-
-	(void)fprintf(stderr, "%d level%s with %ld keys",
-	    levels, levels == 1 ? "" : "s", nkeys);
-	if (F_ISSET(t, R_RECNO))
-		(void)fprintf(stderr, " (%ld header count)", t->bt_nrecs);
-	(void)fprintf(stderr,
-	    "\n%lu pages (leaf %ld, internal %ld, overflow %ld)\n",
-	    pinternal + pleaf + pcont, pleaf, pinternal, pcont);
-	(void)fprintf(stderr, "%ld cache hits, %ld cache misses\n",
-	    bt_cache_hit, bt_cache_miss);
-	(void)fprintf(stderr, "%ld splits (%ld root splits, %ld sort splits)\n",
-	    bt_split, bt_rootsplit, bt_sortsplit);
-	pleaf *= t->bt_psize - BTDATAOFF;
-	if (pleaf)
-		(void)fprintf(stderr,
-		    "%.0f%% leaf fill (%ld bytes used, %ld bytes free)\n",
-		    ((double)(pleaf - lfree) / pleaf) * 100,
-		    pleaf - lfree, lfree);
-	pinternal *= t->bt_psize - BTDATAOFF;
-	if (pinternal)
-		(void)fprintf(stderr,
-		    "%.0f%% internal fill (%ld bytes used, %ld bytes free\n",
-		    ((double)(pinternal - ifree) / pinternal) * 100,
-		    pinternal - ifree, ifree);
-	if (bt_pfxsaved)
-		(void)fprintf(stderr, "prefix checking removed %lu bytes.\n",
-		    bt_pfxsaved);
-}
-#endif
diff --git a/main/db1-ast/btree/bt_delete.c b/main/db1-ast/btree/bt_delete.c
deleted file mode 100644
index 6e3883db9..000000000
--- a/main/db1-ast/btree/bt_delete.c
+++ /dev/null
@@ -1,657 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_delete.c	8.13 (Berkeley) 7/28/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <errno.h>
-#include <stdio.h>
-#include <string.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-static int __bt_bdelete __P((BTREE *, const DBT *));
-static int __bt_curdel __P((BTREE *, const DBT *, PAGE *, u_int));
-static int __bt_pdelete __P((BTREE *, PAGE *));
-static int __bt_relink __P((BTREE *, PAGE *));
-static int __bt_stkacq __P((BTREE *, PAGE **, CURSOR *));
-
-/*
- * __bt_delete
- *	Delete the item(s) referenced by a key.
- *
- * Return RET_SPECIAL if the key is not found.
- */
-int
-__bt_delete(dbp, key, flags)
-	const DB *dbp;
-	const DBT *key;
-	u_int flags;
-{
-	BTREE *t;
-	CURSOR *c;
-	PAGE *h;
-	int status;
-
-	t = dbp->internal;
-
-	/* Toss any page pinned across calls. */
-	if (t->bt_pinned != NULL) {
-		mpool_put(t->bt_mp, t->bt_pinned, 0);
-		t->bt_pinned = NULL;
-	}
-
-	/* Check for change to a read-only tree. */
-	if (F_ISSET(t, B_RDONLY)) {
-		errno = EPERM;
-		return (RET_ERROR);
-	}
-
-	switch (flags) {
-	case 0:
-		status = __bt_bdelete(t, key);
-		break;
-	case R_CURSOR:
-		/*
-		 * If flags is R_CURSOR, delete the cursor.  Must already
-		 * have started a scan and not have already deleted it.
-		 */
-		c = &t->bt_cursor;
-		if (F_ISSET(c, CURS_INIT)) {
-			if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE))
-				return (RET_SPECIAL);
-			if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
-				return (RET_ERROR);
-
-			/*
-			 * If the page is about to be emptied, we'll need to
-			 * delete it, which means we have to acquire a stack.
-			 */
-			if (NEXTINDEX(h) == 1)
-				if (__bt_stkacq(t, &h, &t->bt_cursor))
-					return (RET_ERROR);
-
-			status = __bt_dleaf(t, NULL, h, c->pg.index);
-
-			if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) {
-				if (__bt_pdelete(t, h))
-					return (RET_ERROR);
-			} else
-				mpool_put(t->bt_mp,
-				    h, status == RET_SUCCESS ? MPOOL_DIRTY : 0);
-			break;
-		}
-		/* FALLTHROUGH */
-	default:
-		errno = EINVAL;
-		return (RET_ERROR);
-	}
-	if (status == RET_SUCCESS)
-		F_SET(t, B_MODIFIED);
-	return (status);
-}
-
-/*
- * __bt_stkacq --
- *	Acquire a stack so we can delete a cursor entry.
- *
- * Parameters:
- *	  t:	tree
- *	 hp:	pointer to current, pinned PAGE pointer
- *	  c:	pointer to the cursor
- *
- * Returns:
- *	0 on success, 1 on failure
- */
-static int
-__bt_stkacq(t, hp, c)
-	BTREE *t;
-	PAGE **hp;
-	CURSOR *c;
-{
-	BINTERNAL *bi;
-	EPG *e;
-	EPGNO *parent;
-	PAGE *h;
-	indx_t idx = 0;
-	pgno_t pgno;
-	recno_t nextpg, prevpg;
-	int exact, level;
-
-	/*
-	 * Find the first occurrence of the key in the tree.  Toss the
-	 * currently locked page so we don't hit an already-locked page.
-	 */
-	h = *hp;
-	mpool_put(t->bt_mp, h, 0);
-	if ((e = __bt_search(t, &c->key, &exact)) == NULL)
-		return (1);
-	h = e->page;
-
-	/* See if we got it in one shot. */
-	if (h->pgno == c->pg.pgno)
-		goto ret;
-
-	/*
-	 * Move right, looking for the page.  At each move we have to move
-	 * up the stack until we don't have to move to the next page.  If
-	 * we have to change pages at an internal level, we have to fix the
-	 * stack back up.
-	 */
-	while (h->pgno != c->pg.pgno) {
-		if ((nextpg = h->nextpg) == P_INVALID)
-			break;
-		mpool_put(t->bt_mp, h, 0);
-
-		/* Move up the stack. */
-		for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
-			/* Get the parent page. */
-			if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
-				return (1);
-
-			/* Move to the next index. */
-			if (parent->index != NEXTINDEX(h) - 1) {
-				idx = parent->index + 1;
-				BT_PUSH(t, h->pgno, idx);
-				break;
-			}
-			mpool_put(t->bt_mp, h, 0);
-		}
-
-		/* Restore the stack. */
-		while (level--) {
-			/* Push the next level down onto the stack. */
-			bi = GETBINTERNAL(h, idx);
-			pgno = bi->pgno;
-			BT_PUSH(t, pgno, 0);
-
-			/* Lose the currently pinned page. */
-			mpool_put(t->bt_mp, h, 0);
-
-			/* Get the next level down. */
-			if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
-				return (1);
-			idx = 0;
-		}
-		mpool_put(t->bt_mp, h, 0);
-		if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL)
-			return (1);
-	}
-
-	if (h->pgno == c->pg.pgno)
-		goto ret;
-
-	/* Reacquire the original stack. */
-	mpool_put(t->bt_mp, h, 0);
-	if ((e = __bt_search(t, &c->key, &exact)) == NULL)
-		return (1);
-	h = e->page;
-
-	/*
-	 * Move left, looking for the page.  At each move we have to move
-	 * up the stack until we don't have to change pages to move to the
-	 * next page.  If we have to change pages at an internal level, we
-	 * have to fix the stack back up.
-	 */
-	while (h->pgno != c->pg.pgno) {
-		if ((prevpg = h->prevpg) == P_INVALID)
-			break;
-		mpool_put(t->bt_mp, h, 0);
-
-		/* Move up the stack. */
-		for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
-			/* Get the parent page. */
-			if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
-				return (1);
-
-			/* Move to the next index. */
-			if (parent->index != 0) {
-				idx = parent->index - 1;
-				BT_PUSH(t, h->pgno, idx);
-				break;
-			}
-			mpool_put(t->bt_mp, h, 0);
-		}
-
-		/* Restore the stack. */
-		while (level--) {
-			/* Push the next level down onto the stack. */
-			bi = GETBINTERNAL(h, idx);
-			pgno = bi->pgno;
-
-			/* Lose the currently pinned page. */
-			mpool_put(t->bt_mp, h, 0);
-
-			/* Get the next level down. */
-			if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
-				return (1);
-
-			idx = NEXTINDEX(h) - 1;
-			BT_PUSH(t, pgno, idx);
-		}
-		mpool_put(t->bt_mp, h, 0);
-		if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL)
-			return (1);
-	}
-
-
-ret:	mpool_put(t->bt_mp, h, 0);
-	return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL);
-}
-
-/*
- * __bt_bdelete --
- *	Delete all key/data pairs matching the specified key.
- *
- * Parameters:
- *	  t:	tree
- *	key:	key to delete
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
- */
-static int
-__bt_bdelete(t, key)
-	BTREE *t;
-	const DBT *key;
-{
-	EPG *e;
-	PAGE *h;
-	int deleted, exact, redo;
-
-	deleted = 0;
-
-	/* Find any matching record; __bt_search pins the page. */
-loop:	if ((e = __bt_search(t, key, &exact)) == NULL)
-		return (deleted ? RET_SUCCESS : RET_ERROR);
-	if (!exact) {
-		mpool_put(t->bt_mp, e->page, 0);
-		return (deleted ? RET_SUCCESS : RET_SPECIAL);
-	}
-
-	/*
-	 * Delete forward, then delete backward, from the found key.  If
-	 * there are duplicates and we reach either side of the page, do
-	 * the key search again, so that we get them all.
-	 */
-	redo = 0;
-	h = e->page;
-	do {
-		if (__bt_dleaf(t, key, h, e->index)) {
-			mpool_put(t->bt_mp, h, 0);
-			return (RET_ERROR);
-		}
-		if (F_ISSET(t, B_NODUPS)) {
-			if (NEXTINDEX(h) == 0) {
-				if (__bt_pdelete(t, h))
-					return (RET_ERROR);
-			} else
-				mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-			return (RET_SUCCESS);
-		}
-		deleted = 1;
-	} while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
-
-	/* Check for right-hand edge of the page. */
-	if (e->index == NEXTINDEX(h))
-		redo = 1;
-
-	/* Delete from the key to the beginning of the page. */
-	while (e->index-- > 0) {
-		if (__bt_cmp(t, key, e) != 0)
-			break;
-		if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) {
-			mpool_put(t->bt_mp, h, 0);
-			return (RET_ERROR);
-		}
-		if (e->index == 0)
-			redo = 1;
-	}
-
-	/* Check for an empty page. */
-	if (NEXTINDEX(h) == 0) {
-		if (__bt_pdelete(t, h))
-			return (RET_ERROR);
-		goto loop;
-	}
-
-	/* Put the page. */
-	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-
-	if (redo)
-		goto loop;
-	return (RET_SUCCESS);
-}
-
-/*
- * __bt_pdelete --
- *	Delete a single page from the tree.
- *
- * Parameters:
- *	t:	tree
- *	h:	leaf page
- *
- * Returns:
- *	RET_SUCCESS, RET_ERROR.
- *
- * Side-effects:
- *	mpool_put's the page
- */
-static int
-__bt_pdelete(t, h)
-	BTREE *t;
-	PAGE *h;
-{
-	BINTERNAL *bi;
-	PAGE *pg;
-	EPGNO *parent;
-	indx_t cnt, idx, *ip, offset;
-	u_int32_t nksize;
-	char *from;
-
-	/*
-	 * Walk the parent page stack -- a LIFO stack of the pages that were
-	 * traversed when we searched for the page where the delete occurred.
-	 * Each stack entry is a page number and a page index offset.  The
-	 * offset is for the page traversed on the search.  We've just deleted
-	 * a page, so we have to delete the key from the parent page.
-	 *
-	 * If the delete from the parent page makes it empty, this process may
-	 * continue all the way up the tree.  We stop if we reach the root page
-	 * (which is never deleted, it's just not worth the effort) or if the
-	 * delete does not empty the page.
-	 */
-	while ((parent = BT_POP(t)) != NULL) {
-		/* Get the parent page. */
-		if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
-			return (RET_ERROR);
-
-		idx = parent->index;
-		bi = GETBINTERNAL(pg, idx);
-
-		/* Free any overflow pages. */
-		if (bi->flags & P_BIGKEY &&
-		    __ovfl_delete(t, bi->bytes) == RET_ERROR) {
-			mpool_put(t->bt_mp, pg, 0);
-			return (RET_ERROR);
-		}
-
-		/*
-		 * Free the parent if it has only the one key and it's not the
-		 * root page. If it's the rootpage, turn it back into an empty
-		 * leaf page.
-		 */
-		if (NEXTINDEX(pg) == 1) {
-			if (pg->pgno == P_ROOT) {
-				pg->lower = BTDATAOFF;
-				pg->upper = t->bt_psize;
-				pg->flags = P_BLEAF;
-			} else {
-				if (__bt_relink(t, pg) || __bt_free(t, pg))
-					return (RET_ERROR);
-				continue;
-			}
-		} else {
-			/* Pack remaining key items at the end of the page. */
-			nksize = NBINTERNAL(bi->ksize);
-			from = (char *)pg + pg->upper;
-			memmove(from + nksize, from, (char *)bi - from);
-			pg->upper += nksize;
-
-			/* Adjust indices' offsets, shift the indices down. */
-			offset = pg->linp[idx];
-			for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip)
-				if (ip[0] < offset)
-					ip[0] += nksize;
-			for (cnt = NEXTINDEX(pg) - idx; --cnt; ++ip)
-				ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1];
-			pg->lower -= sizeof(indx_t);
-		}
-
-		mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
-		break;
-	}
-
-	/* Free the leaf page, as long as it wasn't the root. */
-	if (h->pgno == P_ROOT) {
-		mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-		return (RET_SUCCESS);
-	}
-	return (__bt_relink(t, h) || __bt_free(t, h));
-}
-
-/*
- * __bt_dleaf --
- *	Delete a single record from a leaf page.
- *
- * Parameters:
- *	t:	tree
- *    key:	referenced key
- *	h:	page
- *	index:	index on page to delete
- *
- * Returns:
- *	RET_SUCCESS, RET_ERROR.
- */
-int
-__bt_dleaf(t, key, h, idx)
-	BTREE *t;
-	const DBT *key;
-	PAGE *h;
-	u_int idx;
-{
-	BLEAF *bl;
-	indx_t cnt, *ip, offset;
-	u_int32_t nbytes;
-	void *to;
-	char *from;
-
-	/* If this record is referenced by the cursor, delete the cursor. */
-	if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
-	    !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
-	    t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == idx &&
-	    __bt_curdel(t, key, h, idx))
-		return (RET_ERROR);
-
-	/* If the entry uses overflow pages, make them available for reuse. */
-	to = bl = GETBLEAF(h, idx);
-	if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
-		return (RET_ERROR);
-	if (bl->flags & P_BIGDATA &&
-	    __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
-		return (RET_ERROR);
-
-	/* Pack the remaining key/data items at the end of the page. */
-	nbytes = NBLEAF(bl);
-	from = (char *)h + h->upper;
-	memmove(from + nbytes, from, (char *)to - from);
-	h->upper += nbytes;
-
-	/* Adjust the indices' offsets, shift the indices down. */
-	offset = h->linp[idx];
-	for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip)
-		if (ip[0] < offset)
-			ip[0] += nbytes;
-	for (cnt = NEXTINDEX(h) - idx; --cnt; ++ip)
-		ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
-	h->lower -= sizeof(indx_t);
-
-	/* If the cursor is on this page, adjust it as necessary. */
-	if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
-	    !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
-	    t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > idx)
-		--t->bt_cursor.pg.index;
-
-	return (RET_SUCCESS);
-}
-
-/*
- * __bt_curdel --
- *	Delete the cursor.
- *
- * Parameters:
- *	t:	tree
- *    key:	referenced key (or NULL)
- *	h:	page
- *  index:	index on page to delete
- *
- * Returns:
- *	RET_SUCCESS, RET_ERROR.
- */
-static int
-__bt_curdel(t, key, h, idx)
-	BTREE *t;
-	const DBT *key;
-	PAGE *h;
-	u_int idx;
-{
-	CURSOR *c;
-	EPG e;
-	PAGE *pg;
-	int curcopy, status;
-
-	/*
-	 * If there are duplicates, move forward or backward to one.
-	 * Otherwise, copy the key into the cursor area.
-	 */
-	c = &t->bt_cursor;
-	F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE);
-
-	curcopy = 0;
-	if (!F_ISSET(t, B_NODUPS)) {
-		/*
-		 * We're going to have to do comparisons.  If we weren't
-		 * provided a copy of the key, i.e. the user is deleting
-		 * the current cursor position, get one.
-		 */
-		if (key == NULL) {
-			e.page = h;
-			e.index = idx;
-			if ((status = __bt_ret(t, &e,
-			    &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS)
-				return (status);
-			curcopy = 1;
-			key = &c->key;
-		}
-		/* Check previous key, if not at the beginning of the page. */
-		if (idx > 0) {
-			e.page = h;
-			e.index = idx - 1;
-			if (__bt_cmp(t, key, &e) == 0) {
-				F_SET(c, CURS_BEFORE);
-				goto dup2;
-			}
-		}
-		/* Check next key, if not at the end of the page. */
-		if (idx < NEXTINDEX(h) - 1) {
-			e.page = h;
-			e.index = idx + 1;
-			if (__bt_cmp(t, key, &e) == 0) {
-				F_SET(c, CURS_AFTER);
-				goto dup2;
-			}
-		}
-		/* Check previous key if at the beginning of the page. */
-		if (idx == 0 && h->prevpg != P_INVALID) {
-			if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
-				return (RET_ERROR);
-			e.page = pg;
-			e.index = NEXTINDEX(pg) - 1;
-			if (__bt_cmp(t, key, &e) == 0) {
-				F_SET(c, CURS_BEFORE);
-				goto dup1;
-			}
-			mpool_put(t->bt_mp, pg, 0);
-		}
-		/* Check next key if at the end of the page. */
-		if (idx == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) {
-			if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
-				return (RET_ERROR);
-			e.page = pg;
-			e.index = 0;
-			if (__bt_cmp(t, key, &e) == 0) {
-				F_SET(c, CURS_AFTER);
-dup1:				mpool_put(t->bt_mp, pg, 0);
-dup2:				c->pg.pgno = e.page->pgno;
-				c->pg.index = e.index;
-				return (RET_SUCCESS);
-			}
-			mpool_put(t->bt_mp, pg, 0);
-		}
-	}
-	e.page = h;
-	e.index = idx;
-	if (curcopy || (status =
-	    __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) {
-		F_SET(c, CURS_ACQUIRE);
-		return (RET_SUCCESS);
-	}
-	return (status);
-}
-
-/*
- * __bt_relink --
- *	Link around a deleted page.
- *
- * Parameters:
- *	t:	tree
- *	h:	page to be deleted
- */
-static int
-__bt_relink(t, h)
-	BTREE *t;
-	PAGE *h;
-{
-	PAGE *pg;
-
-	if (h->nextpg != P_INVALID) {
-		if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
-			return (RET_ERROR);
-		pg->prevpg = h->prevpg;
-		mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
-	}
-	if (h->prevpg != P_INVALID) {
-		if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
-			return (RET_ERROR);
-		pg->nextpg = h->nextpg;
-		mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
-	}
-	return (0);
-}
diff --git a/main/db1-ast/btree/bt_get.c b/main/db1-ast/btree/bt_get.c
deleted file mode 100644
index b5e18022c..000000000
--- a/main/db1-ast/btree/bt_get.c
+++ /dev/null
@@ -1,105 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_get.c	8.6 (Berkeley) 7/20/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <errno.h>
-#include <stddef.h>
-#include <stdio.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-/*
- * __BT_GET -- Get a record from the btree.
- *
- * Parameters:
- *	dbp:	pointer to access method
- *	key:	key to find
- *	data:	data to return
- *	flag:	currently unused
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
- */
-int
-__bt_get(dbp, key, data, flags)
-	const DB *dbp;
-	const DBT *key;
-	DBT *data;
-	u_int flags;
-{
-	BTREE *t;
-	EPG *e;
-	int exact, status;
-
-	t = dbp->internal;
-
-	/* Toss any page pinned across calls. */
-	if (t->bt_pinned != NULL) {
-		mpool_put(t->bt_mp, t->bt_pinned, 0);
-		t->bt_pinned = NULL;
-	}
-
-	/* Get currently doesn't take any flags. */
-	if (flags) {
-		errno = EINVAL;
-		return (RET_ERROR);
-	}
-
-	if ((e = __bt_search(t, key, &exact)) == NULL)
-		return (RET_ERROR);
-	if (!exact) {
-		mpool_put(t->bt_mp, e->page, 0);
-		return (RET_SPECIAL);
-	}
-
-	status = __bt_ret(t, e, NULL, NULL, data, &t->bt_rdata, 0);
-
-	/*
-	 * If the user is doing concurrent access, we copied the
-	 * key/data, toss the page.
-	 */
-	if (F_ISSET(t, B_DB_LOCK))
-		mpool_put(t->bt_mp, e->page, 0);
-	else
-		t->bt_pinned = e->page;
-	return (status);
-}
diff --git a/main/db1-ast/btree/bt_open.c b/main/db1-ast/btree/bt_open.c
deleted file mode 100644
index 5d40e4593..000000000
--- a/main/db1-ast/btree/bt_open.c
+++ /dev/null
@@ -1,458 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_open.c	8.10 (Berkeley) 8/17/94";
-#endif /* LIBC_SCCS and not lint */
-
-/*
- * Implementation of btree access method for 4.4BSD.
- *
- * The design here was originally based on that of the btree access method
- * used in the Postgres database system at UC Berkeley.  This implementation
- * is wholly independent of the Postgres code.
- */
-
-#include <sys/param.h>
-#include <sys/stat.h>
-
-#include <errno.h>
-#include <fcntl.h>
-#include <limits.h>
-#include <signal.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-#ifdef DEBUG
-#undef	MINPSIZE
-#define	MINPSIZE	128
-#endif
-
-static int byteorder __P((void));
-static int nroot __P((BTREE *));
-static int tmp __P((void));
-
-/*
- * __BT_OPEN -- Open a btree.
- *
- * Creates and fills a DB struct, and calls the routine that actually
- * opens the btree.
- *
- * Parameters:
- *	fname:	filename (NULL for in-memory trees)
- *	flags:	open flag bits
- *	mode:	open permission bits
- *	b:	BTREEINFO pointer
- *
- * Returns:
- *	NULL on failure, pointer to DB on success.
- *
- */
-DB *
-__bt_open(fname, flags, mode, openinfo, dflags)
-	const char *fname;
-	int flags, mode, dflags;
-	const BTREEINFO *openinfo;
-{
-	struct stat sb;
-	BTMETA m;
-	BTREE *t;
-	BTREEINFO b;
-	DB *dbp;
-	pgno_t ncache;
-	ssize_t nr;
-	int machine_lorder;
-
-	t = NULL;
-
-	/*
-	 * Intention is to make sure all of the user's selections are okay
-	 * here and then use them without checking.  Can't be complete, since
-	 * we don't know the right page size, lorder or flags until the backing
-	 * file is opened.  Also, the file's page size can cause the cachesize
-	 * to change.
-	 */
-	machine_lorder = byteorder();
-	if (openinfo) {
-		b = *openinfo;
-
-		/* Flags: R_DUP. */
-		if (b.flags & ~(R_DUP))
-			goto einval;
-
-		/*
-		 * Page size must be indx_t aligned and >= MINPSIZE.  Default
-		 * page size is set farther on, based on the underlying file
-		 * transfer size.
-		 */
-		if (b.psize &&
-		    (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 ||
-		    b.psize & (sizeof(indx_t) - 1)))
-			goto einval;
-
-		/* Minimum number of keys per page; absolute minimum is 2. */
-		if (b.minkeypage) {
-			if (b.minkeypage < 2)
-				goto einval;
-		} else
-			b.minkeypage = DEFMINKEYPAGE;
-
-		/* If no comparison, use default comparison and prefix. */
-		if (b.compare == NULL) {
-			b.compare = __bt_defcmp;
-			if (b.prefix == NULL)
-				b.prefix = __bt_defpfx;
-		}
-
-		if (b.lorder == 0)
-			b.lorder = machine_lorder;
-	} else {
-		b.compare = __bt_defcmp;
-		b.cachesize = 0;
-		b.flags = 0;
-		b.lorder = machine_lorder;
-		b.minkeypage = DEFMINKEYPAGE;
-		b.prefix = __bt_defpfx;
-		b.psize = 0;
-	}
-
-	/* Check for the ubiquitous PDP-11. */
-	if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN)
-		goto einval;
-
-	/* Allocate and initialize DB and BTREE structures. */
-	if ((t = (BTREE *)malloc(sizeof(BTREE))) == NULL)
-		goto err;
-	memset(t, 0, sizeof(BTREE));
-	t->bt_fd = -1;			/* Don't close unopened fd on error. */
-	t->bt_lorder = b.lorder;
-	t->bt_order = NOT;
-	t->bt_cmp = b.compare;
-	t->bt_pfx = b.prefix;
-	t->bt_rfd = -1;
-
-	if ((t->bt_dbp = dbp = (DB *)malloc(sizeof(DB))) == NULL)
-		goto err;
-	memset(t->bt_dbp, 0, sizeof(DB));
-	if (t->bt_lorder != machine_lorder)
-		F_SET(t, B_NEEDSWAP);
-
-	dbp->type = DB_BTREE;
-	dbp->internal = t;
-	dbp->close = __bt_close;
-	dbp->del = __bt_delete;
-	dbp->fd = __bt_fd;
-	dbp->get = __bt_get;
-	dbp->put = __bt_put;
-	dbp->seq = __bt_seq;
-	dbp->sync = __bt_sync;
-
-	/*
-	 * If no file name was supplied, this is an in-memory btree and we
-	 * open a backing temporary file.  Otherwise, it's a disk-based tree.
-	 */
-	if (fname) {
-		switch (flags & O_ACCMODE) {
-		case O_RDONLY:
-			F_SET(t, B_RDONLY);
-			break;
-		case O_RDWR:
-			break;
-		case O_WRONLY:
-		default:
-			goto einval;
-		}
-
-		if ((t->bt_fd = open(fname, flags, mode)) < 0)
-			goto err;
-
-	} else {
-		if ((flags & O_ACCMODE) != O_RDWR)
-			goto einval;
-		if ((t->bt_fd = tmp()) == -1)
-			goto err;
-		F_SET(t, B_INMEM);
-	}
-
-	if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
-		goto err;
-
-	if (fstat(t->bt_fd, &sb))
-		goto err;
-	if (sb.st_size) {
-		if ((nr = read(t->bt_fd, &m, sizeof(BTMETA))) < 0)
-			goto err;
-		if (nr != sizeof(BTMETA))
-			goto eftype;
-
-		/*
-		 * Read in the meta-data.  This can change the notion of what
-		 * the lorder, page size and flags are, and, when the page size
-		 * changes, the cachesize value can change too.  If the user
-		 * specified the wrong byte order for an existing database, we
-		 * don't bother to return an error, we just clear the NEEDSWAP
-		 * bit.
-		 */
-		if (m.magic == BTREEMAGIC)
-			F_CLR(t, B_NEEDSWAP);
-		else {
-			F_SET(t, B_NEEDSWAP);
-			M_32_SWAP(m.magic);
-			M_32_SWAP(m.version);
-			M_32_SWAP(m.psize);
-			M_32_SWAP(m.free);
-			M_32_SWAP(m.nrecs);
-			M_32_SWAP(m.flags);
-		}
-		if (m.magic != BTREEMAGIC || m.version != BTREEVERSION)
-			goto eftype;
-		if (m.psize < MINPSIZE || m.psize > MAX_PAGE_OFFSET + 1 ||
-		    m.psize & (sizeof(indx_t) - 1))
-			goto eftype;
-		if (m.flags & ~SAVEMETA)
-			goto eftype;
-		b.psize = m.psize;
-		F_SET(t, m.flags);
-		t->bt_free = m.free;
-		t->bt_nrecs = m.nrecs;
-	} else {
-		/*
-		 * Set the page size to the best value for I/O to this file.
-		 * Don't overflow the page offset type.
-		 */
-		if (b.psize == 0) {
-#ifdef _STATBUF_ST_BLKSIZE
-			b.psize = sb.st_blksize;
-#endif
-			if (b.psize < MINPSIZE)
-				b.psize = MINPSIZE;
-			if (b.psize > MAX_PAGE_OFFSET + 1)
-				b.psize = MAX_PAGE_OFFSET + 1;
-		}
-
-		/* Set flag if duplicates permitted. */
-		if (!(b.flags & R_DUP))
-			F_SET(t, B_NODUPS);
-
-		t->bt_free = P_INVALID;
-		t->bt_nrecs = 0;
-		F_SET(t, B_METADIRTY);
-	}
-
-	t->bt_psize = b.psize;
-
-	/* Set the cache size; must be a multiple of the page size. */
-	if (b.cachesize && b.cachesize & (b.psize - 1))
-		b.cachesize += (~b.cachesize & (b.psize - 1)) + 1;
-	if (b.cachesize < b.psize * MINCACHE)
-		b.cachesize = b.psize * MINCACHE;
-
-	/* Calculate number of pages to cache. */
-	ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize;
-
-	/*
-	 * The btree data structure requires that at least two keys can fit on
-	 * a page, but other than that there's no fixed requirement.  The user
-	 * specified a minimum number per page, and we translated that into the
-	 * number of bytes a key/data pair can use before being placed on an
-	 * overflow page.  This calculation includes the page header, the size
-	 * of the index referencing the leaf item and the size of the leaf item
-	 * structure.  Also, don't let the user specify a minkeypage such that
-	 * a key/data pair won't fit even if both key and data are on overflow
-	 * pages.
-	 */
-	t->bt_ovflsize = (t->bt_psize - BTDATAOFF) / b.minkeypage -
-	    (sizeof(indx_t) + NBLEAFDBT(0, 0));
-	if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t))
-		t->bt_ovflsize =
-		    NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t);
-
-	/* Initialize the buffer pool. */
-	if ((t->bt_mp =
-	    mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
-		goto err;
-	if (!F_ISSET(t, B_INMEM))
-		mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);
-
-	/* Create a root page if new tree. */
-	if (nroot(t) == RET_ERROR)
-		goto err;
-
-	/* Global flags. */
-	if (dflags & DB_LOCK)
-		F_SET(t, B_DB_LOCK);
-	if (dflags & DB_SHMEM)
-		F_SET(t, B_DB_SHMEM);
-	if (dflags & DB_TXN)
-		F_SET(t, B_DB_TXN);
-
-	return (dbp);
-
-einval:	errno = EINVAL;
-	goto err;
-
-eftype:	errno = EFTYPE;
-	goto err;
-
-err:	if (t) {
-		if (t->bt_dbp)
-			free(t->bt_dbp);
-		if (t->bt_fd != -1)
-			(void)close(t->bt_fd);
-		free(t);
-	}
-	return (NULL);
-}
-
-/*
- * NROOT -- Create the root of a new tree.
- *
- * Parameters:
- *	t:	tree
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- */
-static int
-nroot(t)
-	BTREE *t;
-{
-	PAGE *meta, *root;
-	pgno_t npg;
-
-	if ((meta = mpool_get(t->bt_mp, 0, 0)) != NULL) {
-		mpool_put(t->bt_mp, meta, 0);
-		return (RET_SUCCESS);
-	}
-	if (errno != EINVAL)		/* It's OK to not exist. */
-		return (RET_ERROR);
-	errno = 0;
-
-	if ((meta = mpool_new(t->bt_mp, &npg)) == NULL)
-		return (RET_ERROR);
-
-	if ((root = mpool_new(t->bt_mp, &npg)) == NULL)
-		return (RET_ERROR);
-
-	if (npg != P_ROOT)
-		return (RET_ERROR);
-	root->pgno = npg;
-	root->prevpg = root->nextpg = P_INVALID;
-	root->lower = BTDATAOFF;
-	root->upper = t->bt_psize;
-	root->flags = P_BLEAF;
-	memset(meta, 0, t->bt_psize);
-	mpool_put(t->bt_mp, meta, MPOOL_DIRTY);
-	mpool_put(t->bt_mp, root, MPOOL_DIRTY);
-	return (RET_SUCCESS);
-}
-
-static int
-tmp()
-{
-	sigset_t set, oset;
-	int fd;
-	const char *envtmp;
-	char *path;
-	static const char fmt[] = "%s/bt.XXXXXX";
-	size_t n;
-
-	envtmp = getenv("TMPDIR");
-	if (!envtmp)
-	  envtmp = "/tmp";
-	n = strlen (envtmp) + sizeof fmt;
-#ifdef	__GNUC__
-	path = __builtin_alloca(n);
-#else
-	path = malloc(n);
-#endif
-	(void)snprintf(path, n, fmt, envtmp ? envtmp : "/tmp");
-
-	(void)sigfillset(&set);
-	(void)sigprocmask(SIG_BLOCK, &set, &oset);
-	if ((fd = mkstemp(path)) != -1)
-		(void)unlink(path);
-	(void)sigprocmask(SIG_SETMASK, &oset, NULL);
-#ifndef	__GNUC__
-	free(path);
-#endif
-	return(fd);
-}
-
-static int
-byteorder()
-{
-	u_int32_t x;
-	u_char *p;
-
-	x = 0x01020304;
-	p = (u_char *)&x;
-	switch (*p) {
-	case 1:
-		return (BIG_ENDIAN);
-	case 4:
-		return (LITTLE_ENDIAN);
-	default:
-		return (0);
-	}
-}
-
-int
-__bt_fd(dbp)
-        const DB *dbp;
-{
-	BTREE *t;
-
-	t = dbp->internal;
-
-	/* Toss any page pinned across calls. */
-	if (t->bt_pinned != NULL) {
-		mpool_put(t->bt_mp, t->bt_pinned, 0);
-		t->bt_pinned = NULL;
-	}
-
-	/* In-memory database can't have a file descriptor. */
-	if (F_ISSET(t, B_INMEM)) {
-		errno = ENOENT;
-		return (-1);
-	}
-	return (t->bt_fd);
-}
diff --git a/main/db1-ast/btree/bt_overflow.c b/main/db1-ast/btree/bt_overflow.c
deleted file mode 100644
index d8f310d91..000000000
--- a/main/db1-ast/btree/bt_overflow.c
+++ /dev/null
@@ -1,228 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_overflow.c	8.5 (Berkeley) 7/16/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/param.h>
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-/*
- * Big key/data code.
- *
- * Big key and data entries are stored on linked lists of pages.  The initial
- * reference is byte string stored with the key or data and is the page number
- * and size.  The actual record is stored in a chain of pages linked by the
- * nextpg field of the PAGE header.
- *
- * The first page of the chain has a special property.  If the record is used
- * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set
- * in the header.
- *
- * XXX
- * A single DBT is written to each chain, so a lot of space on the last page
- * is wasted.  This is a fairly major bug for some data sets.
- */
-
-/*
- * __OVFL_GET -- Get an overflow key/data item.
- *
- * Parameters:
- *	t:	tree
- *	p:	pointer to { pgno_t, u_int32_t }
- *	buf:	storage address
- *	bufsz:	storage size
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- */
-int
-__ovfl_get(t, p, ssz, buf, bufsz)
-	BTREE *t;
-	void *p;
-	size_t *ssz;
-	void **buf;
-	size_t *bufsz;
-{
-	PAGE *h;
-	pgno_t pg;
-	size_t nb, plen;
-	u_int32_t sz;
-
-	memmove(&pg, p, sizeof(pgno_t));
-	memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
-	*ssz = sz;
-
-#ifdef DEBUG
-	if (pg == P_INVALID || sz == 0)
-		abort();
-#endif
-	/* Make the buffer bigger as necessary. */
-	if (*bufsz < sz) {
-		*buf = (char *)(*buf == NULL ? malloc(sz) : realloc(*buf, sz));
-		if (*buf == NULL)
-			return (RET_ERROR);
-		*bufsz = sz;
-	}
-
-	/*
-	 * Step through the linked list of pages, copying the data on each one
-	 * into the buffer.  Never copy more than the data's length.
-	 */
-	plen = t->bt_psize - BTDATAOFF;
-	for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) {
-		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-			return (RET_ERROR);
-
-		nb = MIN(sz, plen);
-		memmove(p, (char *)h + BTDATAOFF, nb);
-		mpool_put(t->bt_mp, h, 0);
-
-		if ((sz -= nb) == 0)
-			break;
-	}
-	return (RET_SUCCESS);
-}
-
-/*
- * __OVFL_PUT -- Store an overflow key/data item.
- *
- * Parameters:
- *	t:	tree
- *	data:	DBT to store
- *	pgno:	storage page number
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- */
-int
-__ovfl_put(t, dbt, pg)
-	BTREE *t;
-	const DBT *dbt;
-	pgno_t *pg;
-{
-	PAGE *h, *last;
-	void *p;
-	pgno_t npg;
-	size_t nb, plen;
-	u_int32_t sz;
-
-	/*
-	 * Allocate pages and copy the key/data record into them.  Store the
-	 * number of the first page in the chain.
-	 */
-	plen = t->bt_psize - BTDATAOFF;
-	for (last = NULL, p = dbt->data, sz = dbt->size;;
-	    p = (char *)p + plen, last = h) {
-		if ((h = __bt_new(t, &npg)) == NULL)
-			return (RET_ERROR);
-
-		h->pgno = npg;
-		h->nextpg = h->prevpg = P_INVALID;
-		h->flags = P_OVERFLOW;
-		h->lower = h->upper = 0;
-
-		nb = MIN(sz, plen);
-		memmove((char *)h + BTDATAOFF, p, nb);
-
-		if (last) {
-			last->nextpg = h->pgno;
-			mpool_put(t->bt_mp, last, MPOOL_DIRTY);
-		} else
-			*pg = h->pgno;
-
-		if ((sz -= nb) == 0) {
-			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-			break;
-		}
-	}
-	return (RET_SUCCESS);
-}
-
-/*
- * __OVFL_DELETE -- Delete an overflow chain.
- *
- * Parameters:
- *	t:	tree
- *	p:	pointer to { pgno_t, u_int32_t }
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- */
-int
-__ovfl_delete(t, p)
-	BTREE *t;
-	void *p;
-{
-	PAGE *h;
-	pgno_t pg;
-	size_t plen;
-	u_int32_t sz;
-
-	memmove(&pg, p, sizeof(pgno_t));
-	memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
-
-#ifdef DEBUG
-	if (pg == P_INVALID || sz == 0)
-		abort();
-#endif
-	if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-		return (RET_ERROR);
-
-	/* Don't delete chains used by internal pages. */
-	if (h->flags & P_PRESERVE) {
-		mpool_put(t->bt_mp, h, 0);
-		return (RET_SUCCESS);
-	}
-
-	/* Step through the chain, calling the free routine for each page. */
-	for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
-		pg = h->nextpg;
-		__bt_free(t, h);
-		if (sz <= plen)
-			break;
-		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-			return (RET_ERROR);
-	}
-	return (RET_SUCCESS);
-}
diff --git a/main/db1-ast/btree/bt_page.c b/main/db1-ast/btree/bt_page.c
deleted file mode 100644
index e77a1d6b5..000000000
--- a/main/db1-ast/btree/bt_page.c
+++ /dev/null
@@ -1,100 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_page.c	8.3 (Berkeley) 7/14/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <stdio.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-/*
- * __bt_free --
- *	Put a page on the freelist.
- *
- * Parameters:
- *	t:	tree
- *	h:	page to free
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- *
- * Side-effect:
- *	mpool_put's the page.
- */
-int
-__bt_free(t, h)
-	BTREE *t;
-	PAGE *h;
-{
-	/* Insert the page at the head of the free list. */
-	h->prevpg = P_INVALID;
-	h->nextpg = t->bt_free;
-	t->bt_free = h->pgno;
-	F_SET(t, B_METADIRTY);
-
-	/* Make sure the page gets written back. */
-	return (mpool_put(t->bt_mp, h, MPOOL_DIRTY));
-}
-
-/*
- * __bt_new --
- *	Get a new page, preferably from the freelist.
- *
- * Parameters:
- *	t:	tree
- *	npg:	storage for page number.
- *
- * Returns:
- *	Pointer to a page, NULL on error.
- */
-PAGE *
-__bt_new(t, npg)
-	BTREE *t;
-	pgno_t *npg;
-{
-	PAGE *h;
-
-	if (t->bt_free != P_INVALID &&
-	    (h = mpool_get(t->bt_mp, t->bt_free, 0)) != NULL) {
-		*npg = t->bt_free;
-		t->bt_free = h->nextpg;
-		F_SET(t, B_METADIRTY);
-		return (h);
-	}
-	return (mpool_new(t->bt_mp, npg));
-}
diff --git a/main/db1-ast/btree/bt_put.c b/main/db1-ast/btree/bt_put.c
deleted file mode 100644
index 604ff06a3..000000000
--- a/main/db1-ast/btree/bt_put.c
+++ /dev/null
@@ -1,321 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_put.c	8.8 (Berkeley) 7/26/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <errno.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-static EPG *bt_fast __P((BTREE *, const DBT *, const DBT *, int *));
-
-/*
- * __BT_PUT -- Add a btree item to the tree.
- *
- * Parameters:
- *	dbp:	pointer to access method
- *	key:	key
- *	data:	data
- *	flag:	R_NOOVERWRITE
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the
- *	tree and R_NOOVERWRITE specified.
- */
-int
-__bt_put(dbp, key, data, flags)
-	const DB *dbp;
-	DBT *key;
-	const DBT *data;
-	u_int flags;
-{
-	BTREE *t;
-	DBT tkey, tdata;
-	EPG *e = 0;
-	PAGE *h;
-	indx_t idx, nxtindex;
-	pgno_t pg;
-	u_int32_t nbytes;
-	int dflags, exact, status;
-	char *dest, db[NOVFLSIZE], kb[NOVFLSIZE];
-
-	t = dbp->internal;
-
-	/* Toss any page pinned across calls. */
-	if (t->bt_pinned != NULL) {
-		mpool_put(t->bt_mp, t->bt_pinned, 0);
-		t->bt_pinned = NULL;
-	}
-
-	/* Check for change to a read-only tree. */
-	if (F_ISSET(t, B_RDONLY)) {
-		errno = EPERM;
-		return (RET_ERROR);
-	}
-
-	switch (flags) {
-	case 0:
-	case R_NOOVERWRITE:
-		break;
-	case R_CURSOR:
-		/*
-		 * If flags is R_CURSOR, put the cursor.  Must already
-		 * have started a scan and not have already deleted it.
-		 */
-		if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
-		    !F_ISSET(&t->bt_cursor,
-		        CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE))
-			break;
-		/* FALLTHROUGH */
-	default:
-		errno = EINVAL;
-		return (RET_ERROR);
-	}
-
-	/*
-	 * If the key/data pair won't fit on a page, store it on overflow
-	 * pages.  Only put the key on the overflow page if the pair are
-	 * still too big after moving the data to an overflow page.
-	 *
-	 * XXX
-	 * If the insert fails later on, the overflow pages aren't recovered.
-	 */
-	dflags = 0;
-	if (key->size + data->size > t->bt_ovflsize) {
-		if (key->size > t->bt_ovflsize) {
-storekey:		if (__ovfl_put(t, key, &pg) == RET_ERROR)
-				return (RET_ERROR);
-			tkey.data = kb;
-			tkey.size = NOVFLSIZE;
-			memmove(kb, &pg, sizeof(pgno_t));
-			memmove(kb + sizeof(pgno_t),
-			    &key->size, sizeof(u_int32_t));
-			dflags |= P_BIGKEY;
-			key = &tkey;
-		}
-		if (key->size + data->size > t->bt_ovflsize) {
-			if (__ovfl_put(t, data, &pg) == RET_ERROR)
-				return (RET_ERROR);
-			tdata.data = db;
-			tdata.size = NOVFLSIZE;
-			memmove(db, &pg, sizeof(pgno_t));
-			memmove(db + sizeof(pgno_t),
-			    &data->size, sizeof(u_int32_t));
-			dflags |= P_BIGDATA;
-			data = &tdata;
-		}
-		if (key->size + data->size > t->bt_ovflsize)
-			goto storekey;
-	}
-
-	/* Replace the cursor. */
-	if (flags == R_CURSOR) {
-		if ((h = mpool_get(t->bt_mp, t->bt_cursor.pg.pgno, 0)) == NULL)
-			return (RET_ERROR);
-		idx = t->bt_cursor.pg.index;
-		goto delete;
-	}
-
-	/*
-	 * Find the key to delete, or, the location at which to insert.
-	 * Bt_fast and __bt_search both pin the returned page.
-	 */
-	if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL)
-		if ((e = __bt_search(t, key, &exact)) == NULL)
-			return (RET_ERROR);
-	h = e->page;
-	idx = e->index;
-
-	/*
-	 * Add the key/data pair to the tree.  If an identical key is already
-	 * in the tree, and R_NOOVERWRITE is set, an error is returned.  If
-	 * R_NOOVERWRITE is not set, the key is either added (if duplicates are
-	 * permitted) or an error is returned.
-	 */
-	switch (flags) {
-	case R_NOOVERWRITE:
-		if (!exact)
-			break;
-		mpool_put(t->bt_mp, h, 0);
-		return (RET_SPECIAL);
-	default:
-		if (!exact || !F_ISSET(t, B_NODUPS))
-			break;
-		/*
-		 * !!!
-		 * Note, the delete may empty the page, so we need to put a
-		 * new entry into the page immediately.
-		 */
-delete:		if (__bt_dleaf(t, key, h, idx) == RET_ERROR) {
-			mpool_put(t->bt_mp, h, 0);
-			return (RET_ERROR);
-		}
-		break;
-	}
-
-	/*
-	 * If not enough room, or the user has put a ceiling on the number of
-	 * keys permitted in the page, split the page.  The split code will
-	 * insert the key and data and unpin the current page.  If inserting
-	 * into the offset array, shift the pointers up.
-	 */
-	nbytes = NBLEAFDBT(key->size, data->size);
-	if ((u_int32_t) (h->upper - h->lower) < nbytes + sizeof(indx_t)) {
-		if ((status = __bt_split(t, h, key,
-		    data, dflags, nbytes, idx)) != RET_SUCCESS)
-			return (status);
-		goto success;
-	}
-
-	if (idx < (nxtindex = NEXTINDEX(h)))
-		memmove(h->linp + idx + 1, h->linp + idx,
-		    (nxtindex - idx) * sizeof(indx_t));
-	h->lower += sizeof(indx_t);
-
-	h->linp[idx] = h->upper -= nbytes;
-	dest = (char *)h + h->upper;
-	WR_BLEAF(dest, key, data, dflags);
-
-	/* If the cursor is on this page, adjust it as necessary. */
-	if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
-	    !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
-	    t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index >= idx)
-		++t->bt_cursor.pg.index;
-
-	if (t->bt_order == NOT) {
-		if (h->nextpg == P_INVALID) {
-			if (idx == NEXTINDEX(h) - 1) {
-				t->bt_order = FORWARD;
-				t->bt_last.index = idx;
-				t->bt_last.pgno = h->pgno;
-			}
-		} else if (h->prevpg == P_INVALID) {
-			if (idx == 0) {
-				t->bt_order = BACK;
-				t->bt_last.index = 0;
-				t->bt_last.pgno = h->pgno;
-			}
-		}
-	}
-
-	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-
-success:
-	if (flags == R_SETCURSOR)
-		__bt_setcur(t, e->page->pgno, e->index);
-
-	F_SET(t, B_MODIFIED);
-	return (RET_SUCCESS);
-}
-
-#ifdef STATISTICS
-u_long bt_cache_hit, bt_cache_miss;
-#endif
-
-/*
- * BT_FAST -- Do a quick check for sorted data.
- *
- * Parameters:
- *	t:	tree
- *	key:	key to insert
- *
- * Returns:
- * 	EPG for new record or NULL if not found.
- */
-static EPG *
-bt_fast(t, key, data, exactp)
-	BTREE *t;
-	const DBT *key, *data;
-	int *exactp;
-{
-	PAGE *h;
-	u_int32_t nbytes;
-	int cmp;
-
-	if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) {
-		t->bt_order = NOT;
-		return (NULL);
-	}
-	t->bt_cur.page = h;
-	t->bt_cur.index = t->bt_last.index;
-
-	/*
-	 * If won't fit in this page or have too many keys in this page,
-	 * have to search to get split stack.
-	 */
-	nbytes = NBLEAFDBT(key->size, data->size);
-	if ((u_int32_t) (h->upper - h->lower) < nbytes + sizeof(indx_t))
-		goto miss;
-
-	if (t->bt_order == FORWARD) {
-		if (t->bt_cur.page->nextpg != P_INVALID)
-			goto miss;
-		if (t->bt_cur.index != NEXTINDEX(h) - 1)
-			goto miss;
-		if ((cmp = __bt_cmp(t, key, &t->bt_cur)) < 0)
-			goto miss;
-		t->bt_last.index = cmp ? ++t->bt_cur.index : t->bt_cur.index;
-	} else {
-		if (t->bt_cur.page->prevpg != P_INVALID)
-			goto miss;
-		if (t->bt_cur.index != 0)
-			goto miss;
-		if ((cmp = __bt_cmp(t, key, &t->bt_cur)) > 0)
-			goto miss;
-		t->bt_last.index = 0;
-	}
-	*exactp = cmp == 0;
-#ifdef STATISTICS
-	++bt_cache_hit;
-#endif
-	return (&t->bt_cur);
-
-miss:
-#ifdef STATISTICS
-	++bt_cache_miss;
-#endif
-	t->bt_order = NOT;
-	mpool_put(t->bt_mp, h, 0);
-	return (NULL);
-}
diff --git a/main/db1-ast/btree/bt_search.c b/main/db1-ast/btree/bt_search.c
deleted file mode 100644
index 623f43949..000000000
--- a/main/db1-ast/btree/bt_search.c
+++ /dev/null
@@ -1,213 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_search.c	8.8 (Berkeley) 7/31/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <stdio.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-static int __bt_snext __P((BTREE *, PAGE *, const DBT *, int *));
-static int __bt_sprev __P((BTREE *, PAGE *, const DBT *, int *));
-
-/*
- * __bt_search --
- *	Search a btree for a key.
- *
- * Parameters:
- *	t:	tree to search
- *	key:	key to find
- *	exactp:	pointer to exact match flag
- *
- * Returns:
- *	The EPG for matching record, if any, or the EPG for the location
- *	of the key, if it were inserted into the tree, is entered into
- *	the bt_cur field of the tree.  A pointer to the field is returned.
- */
-EPG *
-__bt_search(t, key, exactp)
-	BTREE *t;
-	const DBT *key;
-	int *exactp;
-{
-	PAGE *h;
-	indx_t base, index, lim;
-	pgno_t pg;
-	int cmp;
-
-	BT_CLR(t);
-	for (pg = P_ROOT;;) {
-		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-			return (NULL);
-
-		/* Do a binary search on the current page. */
-		t->bt_cur.page = h;
-		for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) {
-			t->bt_cur.index = index = base + (lim >> 1);
-			if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) {
-				if (h->flags & P_BLEAF) {
-					*exactp = 1;
-					return (&t->bt_cur);
-				}
-				goto next;
-			}
-			if (cmp > 0) {
-				base = index + 1;
-				--lim;
-			}
-		}
-
-		/*
-		 * If it's a leaf page, we're almost done.  If no duplicates
-		 * are allowed, or we have an exact match, we're done.  Else,
-		 * it's possible that there were matching keys on this page,
-		 * which later deleted, and we're on a page with no matches
-		 * while there are matches on other pages.  If at the start or
-		 * end of a page, check the adjacent page.
-		 */
-		if (h->flags & P_BLEAF) {
-			if (!F_ISSET(t, B_NODUPS)) {
-				if (base == 0 &&
-				    h->prevpg != P_INVALID &&
-				    __bt_sprev(t, h, key, exactp))
-					return (&t->bt_cur);
-				if (base == NEXTINDEX(h) &&
-				    h->nextpg != P_INVALID &&
-				    __bt_snext(t, h, key, exactp))
-					return (&t->bt_cur);
-			}
-			*exactp = 0;
-			t->bt_cur.index = base;
-			return (&t->bt_cur);
-		}
-
-		/*
-		 * No match found.  Base is the smallest index greater than
-		 * key and may be zero or a last + 1 index.  If it's non-zero,
-		 * decrement by one, and record the internal page which should
-		 * be a parent page for the key.  If a split later occurs, the
-		 * inserted page will be to the right of the saved page.
-		 */
-		index = base ? base - 1 : base;
-
-next:		BT_PUSH(t, h->pgno, index);
-		pg = GETBINTERNAL(h, index)->pgno;
-		mpool_put(t->bt_mp, h, 0);
-	}
-}
-
-/*
- * __bt_snext --
- *	Check for an exact match after the key.
- *
- * Parameters:
- *	t:	tree
- *	h:	current page
- *	key:	key
- *	exactp:	pointer to exact match flag
- *
- * Returns:
- *	If an exact match found.
- */
-static int
-__bt_snext(t, h, key, exactp)
-	BTREE *t;
-	PAGE *h;
-	const DBT *key;
-	int *exactp;
-{
-	EPG e;
-
-	/*
-	 * Get the next page.  The key is either an exact
-	 * match, or not as good as the one we already have.
-	 */
-	if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
-		return (0);
-	e.index = 0;
-	if (__bt_cmp(t, key, &e) == 0) {
-		mpool_put(t->bt_mp, h, 0);
-		t->bt_cur = e;
-		*exactp = 1;
-		return (1);
-	}
-	mpool_put(t->bt_mp, e.page, 0);
-	return (0);
-}
-
-/*
- * __bt_sprev --
- *	Check for an exact match before the key.
- *
- * Parameters:
- *	t:	tree
- *	h:	current page
- *	key:	key
- *	exactp:	pointer to exact match flag
- *
- * Returns:
- *	If an exact match found.
- */
-static int
-__bt_sprev(t, h, key, exactp)
-	BTREE *t;
-	PAGE *h;
-	const DBT *key;
-	int *exactp;
-{
-	EPG e;
-
-	/*
-	 * Get the previous page.  The key is either an exact
-	 * match, or not as good as the one we already have.
-	 */
-	if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
-		return (0);
-	e.index = NEXTINDEX(e.page) - 1;
-	if (__bt_cmp(t, key, &e) == 0) {
-		mpool_put(t->bt_mp, h, 0);
-		t->bt_cur = e;
-		*exactp = 1;
-		return (1);
-	}
-	mpool_put(t->bt_mp, e.page, 0);
-	return (0);
-}
diff --git a/main/db1-ast/btree/bt_seq.c b/main/db1-ast/btree/bt_seq.c
deleted file mode 100644
index 3f1724274..000000000
--- a/main/db1-ast/btree/bt_seq.c
+++ /dev/null
@@ -1,460 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_seq.c	8.7 (Berkeley) 7/20/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <errno.h>
-#include <stddef.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-static int __bt_first __P((BTREE *, const DBT *, EPG *, int *));
-static int __bt_seqadv __P((BTREE *, EPG *, int));
-static int __bt_seqset __P((BTREE *, EPG *, DBT *, int));
-
-/*
- * Sequential scan support.
- *
- * The tree can be scanned sequentially, starting from either end of the
- * tree or from any specific key.  A scan request before any scanning is
- * done is initialized as starting from the least node.
- */
-
-/*
- * __bt_seq --
- *	Btree sequential scan interface.
- *
- * Parameters:
- *	dbp:	pointer to access method
- *	key:	key for positioning and return value
- *	data:	data return value
- *	flags:	R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV.
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
- */
-int
-__bt_seq(dbp, key, data, flags)
-	const DB *dbp;
-	DBT *key, *data;
-	u_int flags;
-{
-	BTREE *t;
-	EPG e;
-	int status;
-
-	t = dbp->internal;
-
-	/* Toss any page pinned across calls. */
-	if (t->bt_pinned != NULL) {
-		mpool_put(t->bt_mp, t->bt_pinned, 0);
-		t->bt_pinned = NULL;
-	}
-
-	/*
-	 * If scan uninitialized as yet, or starting at a specific record, set
-	 * the scan to a specific key.  Both __bt_seqset and __bt_seqadv pin
-	 * the page the cursor references if they're successful.
-	 */
-	switch (flags) {
-	case R_NEXT:
-	case R_PREV:
-		if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
-			status = __bt_seqadv(t, &e, flags);
-			break;
-		}
-		/* FALLTHROUGH */
-	case R_FIRST:
-	case R_LAST:
-	case R_CURSOR:
-		status = __bt_seqset(t, &e, key, flags);
-		break;
-	default:
-		errno = EINVAL;
-		return (RET_ERROR);
-	}
-
-	if (status == RET_SUCCESS) {
-		__bt_setcur(t, e.page->pgno, e.index);
-
-		status =
-		    __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0);
-
-		/*
-		 * If the user is doing concurrent access, we copied the
-		 * key/data, toss the page.
-		 */
-		if (F_ISSET(t, B_DB_LOCK))
-			mpool_put(t->bt_mp, e.page, 0);
-		else
-			t->bt_pinned = e.page;
-	}
-	return (status);
-}
-
-/*
- * __bt_seqset --
- *	Set the sequential scan to a specific key.
- *
- * Parameters:
- *	t:	tree
- *	ep:	storage for returned key
- *	key:	key for initial scan position
- *	flags:	R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
- *
- * Side effects:
- *	Pins the page the cursor references.
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
- */
-static int
-__bt_seqset(t, ep, key, flags)
-	BTREE *t;
-	EPG *ep;
-	DBT *key;
-	int flags;
-{
-	PAGE *h;
-	pgno_t pg;
-	int exact;
-
-	/*
-	 * Find the first, last or specific key in the tree and point the
-	 * cursor at it.  The cursor may not be moved until a new key has
-	 * been found.
-	 */
-	switch (flags) {
-	case R_CURSOR:				/* Keyed scan. */
-		/*
-		 * Find the first instance of the key or the smallest key
-		 * which is greater than or equal to the specified key.
-		 */
-		if (key->data == NULL || key->size == 0) {
-			errno = EINVAL;
-			return (RET_ERROR);
-		}
-		return (__bt_first(t, key, ep, &exact));
-	case R_FIRST:				/* First record. */
-	case R_NEXT:
-		/* Walk down the left-hand side of the tree. */
-		for (pg = P_ROOT;;) {
-			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-				return (RET_ERROR);
-
-			/* Check for an empty tree. */
-			if (NEXTINDEX(h) == 0) {
-				mpool_put(t->bt_mp, h, 0);
-				return (RET_SPECIAL);
-			}
-
-			if (h->flags & (P_BLEAF | P_RLEAF))
-				break;
-			pg = GETBINTERNAL(h, 0)->pgno;
-			mpool_put(t->bt_mp, h, 0);
-		}
-		ep->page = h;
-		ep->index = 0;
-		break;
-	case R_LAST:				/* Last record. */
-	case R_PREV:
-		/* Walk down the right-hand side of the tree. */
-		for (pg = P_ROOT;;) {
-			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-				return (RET_ERROR);
-
-			/* Check for an empty tree. */
-			if (NEXTINDEX(h) == 0) {
-				mpool_put(t->bt_mp, h, 0);
-				return (RET_SPECIAL);
-			}
-
-			if (h->flags & (P_BLEAF | P_RLEAF))
-				break;
-			pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno;
-			mpool_put(t->bt_mp, h, 0);
-		}
-
-		ep->page = h;
-		ep->index = NEXTINDEX(h) - 1;
-		break;
-	}
-	return (RET_SUCCESS);
-}
-
-/*
- * __bt_seqadvance --
- *	Advance the sequential scan.
- *
- * Parameters:
- *	t:	tree
- *	flags:	R_NEXT, R_PREV
- *
- * Side effects:
- *	Pins the page the new key/data record is on.
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
- */
-static int
-__bt_seqadv(t, ep, flags)
-	BTREE *t;
-	EPG *ep;
-	int flags;
-{
-	CURSOR *c;
-	PAGE *h;
-	indx_t index = 0;
-	pgno_t pg;
-	int exact;
-
-	/*
-	 * There are a couple of states that we can be in.  The cursor has
-	 * been initialized by the time we get here, but that's all we know.
-	 */
-	c = &t->bt_cursor;
-
-	/*
-	 * The cursor was deleted where there weren't any duplicate records,
-	 * so the key was saved.  Find out where that key would go in the
-	 * current tree.  It doesn't matter if the returned key is an exact
-	 * match or not -- if it's an exact match, the record was added after
-	 * the delete so we can just return it.  If not, as long as there's
-	 * a record there, return it.
-	 */
-	if (F_ISSET(c, CURS_ACQUIRE))
-		return (__bt_first(t, &c->key, ep, &exact));
-
-	/* Get the page referenced by the cursor. */
-	if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
-		return (RET_ERROR);
-
-	/*
- 	 * Find the next/previous record in the tree and point the cursor at
-	 * it.  The cursor may not be moved until a new key has been found.
-	 */
-	switch (flags) {
-	case R_NEXT:			/* Next record. */
-		/*
-		 * The cursor was deleted in duplicate records, and moved
-		 * forward to a record that has yet to be returned.  Clear
-		 * that flag, and return the record.
-		 */
-		if (F_ISSET(c, CURS_AFTER))
-			goto usecurrent;
-		index = c->pg.index;
-		if (++index == NEXTINDEX(h)) {
-			pg = h->nextpg;
-			mpool_put(t->bt_mp, h, 0);
-			if (pg == P_INVALID)
-				return (RET_SPECIAL);
-			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-				return (RET_ERROR);
-			index = 0;
-		}
-		break;
-	case R_PREV:			/* Previous record. */
-		/*
-		 * The cursor was deleted in duplicate records, and moved
-		 * backward to a record that has yet to be returned.  Clear
-		 * that flag, and return the record.
-		 */
-		if (F_ISSET(c, CURS_BEFORE)) {
-usecurrent:		F_CLR(c, CURS_AFTER | CURS_BEFORE);
-			ep->page = h;
-			ep->index = c->pg.index;
-			return (RET_SUCCESS);
-		}
-		index = c->pg.index;
-		if (index == 0) {
-			pg = h->prevpg;
-			mpool_put(t->bt_mp, h, 0);
-			if (pg == P_INVALID)
-				return (RET_SPECIAL);
-			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-				return (RET_ERROR);
-			index = NEXTINDEX(h) - 1;
-		} else
-			--index;
-		break;
-	}
-
-	ep->page = h;
-	ep->index = index;
-	return (RET_SUCCESS);
-}
-
-/*
- * __bt_first --
- *	Find the first entry.
- *
- * Parameters:
- *	t:	the tree
- *    key:	the key
- *  erval:	return EPG
- * exactp:	pointer to exact match flag
- *
- * Returns:
- *	The first entry in the tree greater than or equal to key,
- *	or RET_SPECIAL if no such key exists.
- */
-static int
-__bt_first(t, key, erval, exactp)
-	BTREE *t;
-	const DBT *key;
-	EPG *erval;
-	int *exactp;
-{
-	PAGE *h;
-	EPG *ep, save;
-	pgno_t pg;
-
-	/*
-	 * Find any matching record; __bt_search pins the page.
-	 *
-	 * If it's an exact match and duplicates are possible, walk backwards
-	 * in the tree until we find the first one.  Otherwise, make sure it's
-	 * a valid key (__bt_search may return an index just past the end of a
-	 * page) and return it.
-	 */
-	if ((ep = __bt_search(t, key, exactp)) == NULL)
-		return (RET_SPECIAL);
-	if (*exactp) {
-		if (F_ISSET(t, B_NODUPS)) {
-			*erval = *ep;
-			return (RET_SUCCESS);
-		}
-
-		/*
-		 * Walk backwards, as long as the entry matches and there are
-		 * keys left in the tree.  Save a copy of each match in case
-		 * we go too far.
-		 */
-		save = *ep;
-		h = ep->page;
-		do {
-			if (save.page->pgno != ep->page->pgno) {
-				mpool_put(t->bt_mp, save.page, 0);
-				save = *ep;
-			} else
-				save.index = ep->index;
-
-			/*
-			 * Don't unpin the page the last (or original) match
-			 * was on, but make sure it's unpinned if an error
-			 * occurs.
-			 */
-			if (ep->index == 0) {
-				if (h->prevpg == P_INVALID)
-					break;
-				if (h->pgno != save.page->pgno)
-					mpool_put(t->bt_mp, h, 0);
-				if ((h = mpool_get(t->bt_mp,
-				    h->prevpg, 0)) == NULL) {
-					if (h->pgno == save.page->pgno)
-						mpool_put(t->bt_mp,
-						    save.page, 0);
-					return (RET_ERROR);
-				}
-				ep->page = h;
-				ep->index = NEXTINDEX(h);
-			}
-			--ep->index;
-		} while (__bt_cmp(t, key, ep) == 0);
-
-		/*
-		 * Reach here with the last page that was looked at pinned,
-		 * which may or may not be the same as the last (or original)
-		 * match page.  If it's not useful, release it.
-		 */
-		if (h->pgno != save.page->pgno)
-			mpool_put(t->bt_mp, h, 0);
-
-		*erval = save;
-		return (RET_SUCCESS);
-	}
-
-	/* If at the end of a page, find the next entry. */
-	if (ep->index == NEXTINDEX(ep->page)) {
-		h = ep->page;
-		pg = h->nextpg;
-		mpool_put(t->bt_mp, h, 0);
-		if (pg == P_INVALID)
-			return (RET_SPECIAL);
-		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-			return (RET_ERROR);
-		ep->index = 0;
-		ep->page = h;
-	}
-	*erval = *ep;
-	return (RET_SUCCESS);
-}
-
-/*
- * __bt_setcur --
- *	Set the cursor to an entry in the tree.
- *
- * Parameters:
- *	t:	the tree
- *   pgno:	page number
- *  index:	page index
- */
-void
-__bt_setcur(t, pgno, index)
-	BTREE *t;
-	pgno_t pgno;
-	u_int index;
-{
-	/* Lose any already deleted key. */
-	if (t->bt_cursor.key.data != NULL) {
-		free(t->bt_cursor.key.data);
-		t->bt_cursor.key.size = 0;
-		t->bt_cursor.key.data = NULL;
-	}
-	F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE);
-
-	/* Update the cursor. */
-	t->bt_cursor.pg.pgno = pgno;
-	t->bt_cursor.pg.index = index;
-	F_SET(&t->bt_cursor, CURS_INIT);
-}
diff --git a/main/db1-ast/btree/bt_split.c b/main/db1-ast/btree/bt_split.c
deleted file mode 100644
index 8fede1e45..000000000
--- a/main/db1-ast/btree/bt_split.c
+++ /dev/null
@@ -1,829 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_split.c	8.9 (Berkeley) 7/26/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <limits.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-static int	 bt_broot __P((BTREE *, PAGE *, PAGE *, PAGE *));
-static PAGE	*bt_page
-		    __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t));
-static int	 bt_preserve __P((BTREE *, pgno_t));
-static PAGE	*bt_psplit
-		    __P((BTREE *, PAGE *, PAGE *, PAGE *, indx_t *, size_t));
-static PAGE	*bt_root
-		    __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t));
-static int	 bt_rroot __P((BTREE *, PAGE *, PAGE *, PAGE *));
-static recno_t	 rec_total __P((PAGE *));
-
-#ifdef STATISTICS
-u_long	bt_rootsplit, bt_split, bt_sortsplit, bt_pfxsaved;
-#endif
-
-/*
- * __BT_SPLIT -- Split the tree.
- *
- * Parameters:
- *	t:	tree
- *	sp:	page to split
- *	key:	key to insert
- *	data:	data to insert
- *	flags:	BIGKEY/BIGDATA flags
- *	ilen:	insert length
- *	skip:	index to leave open
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- */
-int
-__bt_split(t, sp, key, data, flags, ilen, argskip)
-	BTREE *t;
-	PAGE *sp;
-	const DBT *key, *data;
-	int flags;
-	size_t ilen;
-	u_int32_t argskip;
-{
-	BINTERNAL *bi = 0;
-	BLEAF *bl = 0, *tbl;
-	DBT a, b;
-	EPGNO *parent;
-	PAGE *h, *l, *r, *lchild, *rchild;
-	indx_t nxtindex;
-	u_int16_t skip;
-	u_int32_t n, nbytes, nksize = 0;
-	int parentsplit;
-	char *dest;
-
-	/*
-	 * Split the page into two pages, l and r.  The split routines return
-	 * a pointer to the page into which the key should be inserted and with
-	 * skip set to the offset which should be used.  Additionally, l and r
-	 * are pinned.
-	 */
-	skip = argskip;
-	h = sp->pgno == P_ROOT ?
-	    bt_root(t, sp, &l, &r, &skip, ilen) :
-	    bt_page(t, sp, &l, &r, &skip, ilen);
-	if (h == NULL)
-		return (RET_ERROR);
-
-	/*
-	 * Insert the new key/data pair into the leaf page.  (Key inserts
-	 * always cause a leaf page to split first.)
-	 */
-	h->linp[skip] = h->upper -= ilen;
-	dest = (char *)h + h->upper;
-	if (F_ISSET(t, R_RECNO))
-		WR_RLEAF(dest, data, flags)
-	else
-		WR_BLEAF(dest, key, data, flags)
-
-	/* If the root page was split, make it look right. */
-	if (sp->pgno == P_ROOT &&
-	    (F_ISSET(t, R_RECNO) ?
-	    bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
-		goto err2;
-
-	/*
-	 * Now we walk the parent page stack -- a LIFO stack of the pages that
-	 * were traversed when we searched for the page that split.  Each stack
-	 * entry is a page number and a page index offset.  The offset is for
-	 * the page traversed on the search.  We've just split a page, so we
-	 * have to insert a new key into the parent page.
-	 *
-	 * If the insert into the parent page causes it to split, may have to
-	 * continue splitting all the way up the tree.  We stop if the root
-	 * splits or the page inserted into didn't have to split to hold the
-	 * new key.  Some algorithms replace the key for the old page as well
-	 * as the new page.  We don't, as there's no reason to believe that the
-	 * first key on the old page is any better than the key we have, and,
-	 * in the case of a key being placed at index 0 causing the split, the
-	 * key is unavailable.
-	 *
-	 * There are a maximum of 5 pages pinned at any time.  We keep the left
-	 * and right pages pinned while working on the parent.   The 5 are the
-	 * two children, left parent and right parent (when the parent splits)
-	 * and the root page or the overflow key page when calling bt_preserve.
-	 * This code must make sure that all pins are released other than the
-	 * root page or overflow page which is unlocked elsewhere.
-	 */
-	while ((parent = BT_POP(t)) != NULL) {
-		lchild = l;
-		rchild = r;
-
-		/* Get the parent page. */
-		if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
-			goto err2;
-
-	 	/*
-		 * The new key goes ONE AFTER the index, because the split
-		 * was to the right.
-		 */
-		skip = parent->index + 1;
-
-		/*
-		 * Calculate the space needed on the parent page.
-		 *
-		 * Prefix trees: space hack when inserting into BINTERNAL
-		 * pages.  Retain only what's needed to distinguish between
-		 * the new entry and the LAST entry on the page to its left.
-		 * If the keys compare equal, retain the entire key.  Note,
-		 * we don't touch overflow keys, and the entire key must be
-		 * retained for the next-to-left most key on the leftmost
-		 * page of each level, or the search will fail.  Applicable
-		 * ONLY to internal pages that have leaf pages as children.
-		 * Further reduction of the key between pairs of internal
-		 * pages loses too much information.
-		 */
-		switch (rchild->flags & P_TYPE) {
-		case P_BINTERNAL:
-			bi = GETBINTERNAL(rchild, 0);
-			nbytes = NBINTERNAL(bi->ksize);
-			break;
-		case P_BLEAF:
-			bl = GETBLEAF(rchild, 0);
-			nbytes = NBINTERNAL(bl->ksize);
-			if (t->bt_pfx && !(bl->flags & P_BIGKEY) &&
-			    (h->prevpg != P_INVALID || skip > 1)) {
-				tbl = GETBLEAF(lchild, NEXTINDEX(lchild) - 1);
-				a.size = tbl->ksize;
-				a.data = tbl->bytes;
-				b.size = bl->ksize;
-				b.data = bl->bytes;
-				nksize = t->bt_pfx(&a, &b);
-				n = NBINTERNAL(nksize);
-				if (n < nbytes) {
-#ifdef STATISTICS
-					bt_pfxsaved += nbytes - n;
-#endif
-					nbytes = n;
-				} else
-					nksize = 0;
-			} else
-				nksize = 0;
-			break;
-		case P_RINTERNAL:
-		case P_RLEAF:
-			nbytes = NRINTERNAL;
-			break;
-		default:
-			abort();
-		}
-
-		/* Split the parent page if necessary or shift the indices. */
-		if ((u_int32_t) (h->upper - h->lower)
-		    < nbytes + sizeof(indx_t)) {
-			sp = h;
-			h = h->pgno == P_ROOT ?
-			    bt_root(t, h, &l, &r, &skip, nbytes) :
-			    bt_page(t, h, &l, &r, &skip, nbytes);
-			if (h == NULL)
-				goto err1;
-			parentsplit = 1;
-		} else {
-			if (skip < (nxtindex = NEXTINDEX(h)))
-				memmove(h->linp + skip + 1, h->linp + skip,
-				    (nxtindex - skip) * sizeof(indx_t));
-			h->lower += sizeof(indx_t);
-			parentsplit = 0;
-		}
-
-		/* Insert the key into the parent page. */
-		switch (rchild->flags & P_TYPE) {
-		case P_BINTERNAL:
-			h->linp[skip] = h->upper -= nbytes;
-			dest = (char *)h + h->linp[skip];
-			memmove(dest, bi, nbytes);
-			((BINTERNAL *)dest)->pgno = rchild->pgno;
-			break;
-		case P_BLEAF:
-			h->linp[skip] = h->upper -= nbytes;
-			dest = (char *)h + h->linp[skip];
-			WR_BINTERNAL(dest, nksize ? nksize : bl->ksize,
-			    rchild->pgno, bl->flags & P_BIGKEY);
-			memmove(dest, bl->bytes, nksize ? nksize : bl->ksize);
-			if (bl->flags & P_BIGKEY &&
-			    bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
-				goto err1;
-			break;
-		case P_RINTERNAL:
-			/*
-			 * Update the left page count.  If split
-			 * added at index 0, fix the correct page.
-			 */
-			if (skip > 0)
-				dest = (char *)h + h->linp[skip - 1];
-			else
-				dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
-			((RINTERNAL *)dest)->nrecs = rec_total(lchild);
-			((RINTERNAL *)dest)->pgno = lchild->pgno;
-
-			/* Update the right page count. */
-			h->linp[skip] = h->upper -= nbytes;
-			dest = (char *)h + h->linp[skip];
-			((RINTERNAL *)dest)->nrecs = rec_total(rchild);
-			((RINTERNAL *)dest)->pgno = rchild->pgno;
-			break;
-		case P_RLEAF:
-			/*
-			 * Update the left page count.  If split
-			 * added at index 0, fix the correct page.
-			 */
-			if (skip > 0)
-				dest = (char *)h + h->linp[skip - 1];
-			else
-				dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
-			((RINTERNAL *)dest)->nrecs = NEXTINDEX(lchild);
-			((RINTERNAL *)dest)->pgno = lchild->pgno;
-
-			/* Update the right page count. */
-			h->linp[skip] = h->upper -= nbytes;
-			dest = (char *)h + h->linp[skip];
-			((RINTERNAL *)dest)->nrecs = NEXTINDEX(rchild);
-			((RINTERNAL *)dest)->pgno = rchild->pgno;
-			break;
-		default:
-			abort();
-		}
-
-		/* Unpin the held pages. */
-		if (!parentsplit) {
-			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-			break;
-		}
-
-		/* If the root page was split, make it look right. */
-		if (sp->pgno == P_ROOT &&
-		    (F_ISSET(t, R_RECNO) ?
-		    bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
-			goto err1;
-
-		mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
-		mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
-	}
-
-	/* Unpin the held pages. */
-	mpool_put(t->bt_mp, l, MPOOL_DIRTY);
-	mpool_put(t->bt_mp, r, MPOOL_DIRTY);
-
-	/* Clear any pages left on the stack. */
-	return (RET_SUCCESS);
-
-	/*
-	 * If something fails in the above loop we were already walking back
-	 * up the tree and the tree is now inconsistent.  Nothing much we can
-	 * do about it but release any memory we're holding.
-	 */
-err1:	mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
-	mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
-
-err2:	mpool_put(t->bt_mp, l, 0);
-	mpool_put(t->bt_mp, r, 0);
-	__dbpanic(t->bt_dbp);
-	return (RET_ERROR);
-}
-
-/*
- * BT_PAGE -- Split a non-root page of a btree.
- *
- * Parameters:
- *	t:	tree
- *	h:	root page
- *	lp:	pointer to left page pointer
- *	rp:	pointer to right page pointer
- *	skip:	pointer to index to leave open
- *	ilen:	insert length
- *
- * Returns:
- *	Pointer to page in which to insert or NULL on error.
- */
-static PAGE *
-bt_page(t, h, lp, rp, skip, ilen)
-	BTREE *t;
-	PAGE *h, **lp, **rp;
-	indx_t *skip;
-	size_t ilen;
-{
-	PAGE *l, *r, *tp;
-	pgno_t npg;
-
-#ifdef STATISTICS
-	++bt_split;
-#endif
-	/* Put the new right page for the split into place. */
-	if ((r = __bt_new(t, &npg)) == NULL)
-		return (NULL);
-	r->pgno = npg;
-	r->lower = BTDATAOFF;
-	r->upper = t->bt_psize;
-	r->nextpg = h->nextpg;
-	r->prevpg = h->pgno;
-	r->flags = h->flags & P_TYPE;
-
-	/*
-	 * If we're splitting the last page on a level because we're appending
-	 * a key to it (skip is NEXTINDEX()), it's likely that the data is
-	 * sorted.  Adding an empty page on the side of the level is less work
-	 * and can push the fill factor much higher than normal.  If we're
-	 * wrong it's no big deal, we'll just do the split the right way next
-	 * time.  It may look like it's equally easy to do a similar hack for
-	 * reverse sorted data, that is, split the tree left, but it's not.
-	 * Don't even try.
-	 */
-	if (h->nextpg == P_INVALID && *skip == NEXTINDEX(h)) {
-#ifdef STATISTICS
-		++bt_sortsplit;
-#endif
-		h->nextpg = r->pgno;
-		r->lower = BTDATAOFF + sizeof(indx_t);
-		*skip = 0;
-		*lp = h;
-		*rp = r;
-		return (r);
-	}
-
-	/* Put the new left page for the split into place. */
-	if ((l = (PAGE *)malloc(t->bt_psize)) == NULL) {
-		mpool_put(t->bt_mp, r, 0);
-		return (NULL);
-	}
-#ifdef PURIFY
-	memset(l, 0xff, t->bt_psize);
-#endif
-	l->pgno = h->pgno;
-	l->nextpg = r->pgno;
-	l->prevpg = h->prevpg;
-	l->lower = BTDATAOFF;
-	l->upper = t->bt_psize;
-	l->flags = h->flags & P_TYPE;
-
-	/* Fix up the previous pointer of the page after the split page. */
-	if (h->nextpg != P_INVALID) {
-		if ((tp = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) {
-			free(l);
-			/* XXX mpool_free(t->bt_mp, r->pgno); */
-			return (NULL);
-		}
-		tp->prevpg = r->pgno;
-		mpool_put(t->bt_mp, tp, MPOOL_DIRTY);
-	}
-
-	/*
-	 * Split right.  The key/data pairs aren't sorted in the btree page so
-	 * it's simpler to copy the data from the split page onto two new pages
-	 * instead of copying half the data to the right page and compacting
-	 * the left page in place.  Since the left page can't change, we have
-	 * to swap the original and the allocated left page after the split.
-	 */
-	tp = bt_psplit(t, h, l, r, skip, ilen);
-
-	/* Move the new left page onto the old left page. */
-	memmove(h, l, t->bt_psize);
-	if (tp == l)
-		tp = h;
-	free(l);
-
-	*lp = h;
-	*rp = r;
-	return (tp);
-}
-
-/*
- * BT_ROOT -- Split the root page of a btree.
- *
- * Parameters:
- *	t:	tree
- *	h:	root page
- *	lp:	pointer to left page pointer
- *	rp:	pointer to right page pointer
- *	skip:	pointer to index to leave open
- *	ilen:	insert length
- *
- * Returns:
- *	Pointer to page in which to insert or NULL on error.
- */
-static PAGE *
-bt_root(t, h, lp, rp, skip, ilen)
-	BTREE *t;
-	PAGE *h, **lp, **rp;
-	indx_t *skip;
-	size_t ilen;
-{
-	PAGE *l, *r, *tp;
-	pgno_t lnpg, rnpg;
-
-#ifdef STATISTICS
-	++bt_split;
-	++bt_rootsplit;
-#endif
-	/* Put the new left and right pages for the split into place. */
-	if ((l = __bt_new(t, &lnpg)) == NULL ||
-	    (r = __bt_new(t, &rnpg)) == NULL)
-		return (NULL);
-	l->pgno = lnpg;
-	r->pgno = rnpg;
-	l->nextpg = r->pgno;
-	r->prevpg = l->pgno;
-	l->prevpg = r->nextpg = P_INVALID;
-	l->lower = r->lower = BTDATAOFF;
-	l->upper = r->upper = t->bt_psize;
-	l->flags = r->flags = h->flags & P_TYPE;
-
-	/* Split the root page. */
-	tp = bt_psplit(t, h, l, r, skip, ilen);
-
-	*lp = l;
-	*rp = r;
-	return (tp);
-}
-
-/*
- * BT_RROOT -- Fix up the recno root page after it has been split.
- *
- * Parameters:
- *	t:	tree
- *	h:	root page
- *	l:	left page
- *	r:	right page
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- */
-static int
-bt_rroot(t, h, l, r)
-	BTREE *t;
-	PAGE *h, *l, *r;
-{
-	char *dest;
-
-	/* Insert the left and right keys, set the header information. */
-	h->linp[0] = h->upper = t->bt_psize - NRINTERNAL;
-	dest = (char *)h + h->upper;
-	WR_RINTERNAL(dest,
-	    l->flags & P_RLEAF ? NEXTINDEX(l) : rec_total(l), l->pgno);
-
-	h->linp[1] = h->upper -= NRINTERNAL;
-	dest = (char *)h + h->upper;
-	WR_RINTERNAL(dest,
-	    r->flags & P_RLEAF ? NEXTINDEX(r) : rec_total(r), r->pgno);
-
-	h->lower = BTDATAOFF + 2 * sizeof(indx_t);
-
-	/* Unpin the root page, set to recno internal page. */
-	h->flags &= ~P_TYPE;
-	h->flags |= P_RINTERNAL;
-	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-
-	return (RET_SUCCESS);
-}
-
-/*
- * BT_BROOT -- Fix up the btree root page after it has been split.
- *
- * Parameters:
- *	t:	tree
- *	h:	root page
- *	l:	left page
- *	r:	right page
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
- */
-static int
-bt_broot(t, h, l, r)
-	BTREE *t;
-	PAGE *h, *l, *r;
-{
-	BINTERNAL *bi;
-	BLEAF *bl;
-	u_int32_t nbytes;
-	char *dest;
-
-	/*
-	 * If the root page was a leaf page, change it into an internal page.
-	 * We copy the key we split on (but not the key's data, in the case of
-	 * a leaf page) to the new root page.
-	 *
-	 * The btree comparison code guarantees that the left-most key on any
-	 * level of the tree is never used, so it doesn't need to be filled in.
-	 */
-	nbytes = NBINTERNAL(0);
-	h->linp[0] = h->upper = t->bt_psize - nbytes;
-	dest = (char *)h + h->upper;
-	WR_BINTERNAL(dest, 0, l->pgno, 0);
-
-	switch (h->flags & P_TYPE) {
-	case P_BLEAF:
-		bl = GETBLEAF(r, 0);
-		nbytes = NBINTERNAL(bl->ksize);
-		h->linp[1] = h->upper -= nbytes;
-		dest = (char *)h + h->upper;
-		WR_BINTERNAL(dest, bl->ksize, r->pgno, 0);
-		memmove(dest, bl->bytes, bl->ksize);
-
-		/*
-		 * If the key is on an overflow page, mark the overflow chain
-		 * so it isn't deleted when the leaf copy of the key is deleted.
-		 */
-		if (bl->flags & P_BIGKEY &&
-		    bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
-			return (RET_ERROR);
-		break;
-	case P_BINTERNAL:
-		bi = GETBINTERNAL(r, 0);
-		nbytes = NBINTERNAL(bi->ksize);
-		h->linp[1] = h->upper -= nbytes;
-		dest = (char *)h + h->upper;
-		memmove(dest, bi, nbytes);
-		((BINTERNAL *)dest)->pgno = r->pgno;
-		break;
-	default:
-		abort();
-	}
-
-	/* There are two keys on the page. */
-	h->lower = BTDATAOFF + 2 * sizeof(indx_t);
-
-	/* Unpin the root page, set to btree internal page. */
-	h->flags &= ~P_TYPE;
-	h->flags |= P_BINTERNAL;
-	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-
-	return (RET_SUCCESS);
-}
-
-/*
- * BT_PSPLIT -- Do the real work of splitting the page.
- *
- * Parameters:
- *	t:	tree
- *	h:	page to be split
- *	l:	page to put lower half of data
- *	r:	page to put upper half of data
- *	pskip:	pointer to index to leave open
- *	ilen:	insert length
- *
- * Returns:
- *	Pointer to page in which to insert.
- */
-static PAGE *
-bt_psplit(t, h, l, r, pskip, ilen)
-	BTREE *t;
-	PAGE *h, *l, *r;
-	indx_t *pskip;
-	size_t ilen;
-{
-	BINTERNAL *bi;
-	BLEAF *bl;
-	CURSOR *c;
-	RLEAF *rl;
-	PAGE *rval;
-	void *src = 0;
-	indx_t full, half, nxt, off, skip, top, used;
-	u_int32_t nbytes;
-	int bigkeycnt, isbigkey;
-
-	/*
-	 * Split the data to the left and right pages.  Leave the skip index
-	 * open.  Additionally, make some effort not to split on an overflow
-	 * key.  This makes internal page processing faster and can save
-	 * space as overflow keys used by internal pages are never deleted.
-	 */
-	bigkeycnt = 0;
-	skip = *pskip;
-	full = t->bt_psize - BTDATAOFF;
-	half = full / 2;
-	used = 0;
-	for (nxt = off = 0, top = NEXTINDEX(h); nxt < top; ++off) {
-		if (skip == off) {
-			nbytes = ilen;
-			isbigkey = 0;		/* XXX: not really known. */
-		} else
-			switch (h->flags & P_TYPE) {
-			case P_BINTERNAL:
-				src = bi = GETBINTERNAL(h, nxt);
-				nbytes = NBINTERNAL(bi->ksize);
-				isbigkey = bi->flags & P_BIGKEY;
-				break;
-			case P_BLEAF:
-				src = bl = GETBLEAF(h, nxt);
-				nbytes = NBLEAF(bl);
-				isbigkey = bl->flags & P_BIGKEY;
-				break;
-			case P_RINTERNAL:
-				src = GETRINTERNAL(h, nxt);
-				nbytes = NRINTERNAL;
-				isbigkey = 0;
-				break;
-			case P_RLEAF:
-				src = rl = GETRLEAF(h, nxt);
-				nbytes = NRLEAF(rl);
-				isbigkey = 0;
-				break;
-			default:
-				abort();
-			}
-
-		/*
-		 * If the key/data pairs are substantial fractions of the max
-		 * possible size for the page, it's possible to get situations
-		 * where we decide to try and copy too much onto the left page.
-		 * Make sure that doesn't happen.
-		 */
-		if ((skip <= off && used + nbytes + sizeof(indx_t) >= full)
-		    || nxt == top - 1) {
-			--off;
-			break;
-		}
-
-		/* Copy the key/data pair, if not the skipped index. */
-		if (skip != off) {
-			++nxt;
-
-			l->linp[off] = l->upper -= nbytes;
-			memmove((char *)l + l->upper, src, nbytes);
-		}
-
-		used += nbytes + sizeof(indx_t);
-		if (used >= half) {
-			if (!isbigkey || bigkeycnt == 3)
-				break;
-			else
-				++bigkeycnt;
-		}
-	}
-
-	/*
-	 * Off is the last offset that's valid for the left page.
-	 * Nxt is the first offset to be placed on the right page.
-	 */
-	l->lower += (off + 1) * sizeof(indx_t);
-
-	/*
-	 * If splitting the page that the cursor was on, the cursor has to be
-	 * adjusted to point to the same record as before the split.  If the
-	 * cursor is at or past the skipped slot, the cursor is incremented by
-	 * one.  If the cursor is on the right page, it is decremented by the
-	 * number of records split to the left page.
-	 */
-	c = &t->bt_cursor;
-	if (F_ISSET(c, CURS_INIT) && c->pg.pgno == h->pgno) {
-		if (c->pg.index >= skip)
-			++c->pg.index;
-		if (c->pg.index < nxt)			/* Left page. */
-			c->pg.pgno = l->pgno;
-		else {					/* Right page. */
-			c->pg.pgno = r->pgno;
-			c->pg.index -= nxt;
-		}
-	}
-
-	/*
-	 * If the skipped index was on the left page, just return that page.
-	 * Otherwise, adjust the skip index to reflect the new position on
-	 * the right page.
-	 */
-	if (skip <= off) {
-		skip = 0;
-		rval = l;
-	} else {
-		rval = r;
-		*pskip -= nxt;
-	}
-
-	for (off = 0; nxt < top; ++off) {
-		if (skip == nxt) {
-			++off;
-			skip = 0;
-		}
-		switch (h->flags & P_TYPE) {
-		case P_BINTERNAL:
-			src = bi = GETBINTERNAL(h, nxt);
-			nbytes = NBINTERNAL(bi->ksize);
-			break;
-		case P_BLEAF:
-			src = bl = GETBLEAF(h, nxt);
-			nbytes = NBLEAF(bl);
-			break;
-		case P_RINTERNAL:
-			src = GETRINTERNAL(h, nxt);
-			nbytes = NRINTERNAL;
-			break;
-		case P_RLEAF:
-			src = rl = GETRLEAF(h, nxt);
-			nbytes = NRLEAF(rl);
-			break;
-		default:
-			abort();
-		}
-		++nxt;
-		r->linp[off] = r->upper -= nbytes;
-		memmove((char *)r + r->upper, src, nbytes);
-	}
-	r->lower += off * sizeof(indx_t);
-
-	/* If the key is being appended to the page, adjust the index. */
-	if (skip == top)
-		r->lower += sizeof(indx_t);
-
-	return (rval);
-}
-
-/*
- * BT_PRESERVE -- Mark a chain of pages as used by an internal node.
- *
- * Chains of indirect blocks pointed to by leaf nodes get reclaimed when the
- * record that references them gets deleted.  Chains pointed to by internal
- * pages never get deleted.  This routine marks a chain as pointed to by an
- * internal page.
- *
- * Parameters:
- *	t:	tree
- *	pg:	page number of first page in the chain.
- *
- * Returns:
- *	RET_SUCCESS, RET_ERROR.
- */
-static int
-bt_preserve(t, pg)
-	BTREE *t;
-	pgno_t pg;
-{
-	PAGE *h;
-
-	if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-		return (RET_ERROR);
-	h->flags |= P_PRESERVE;
-	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-	return (RET_SUCCESS);
-}
-
-/*
- * REC_TOTAL -- Return the number of recno entries below a page.
- *
- * Parameters:
- *	h:	page
- *
- * Returns:
- *	The number of recno entries below a page.
- *
- * XXX
- * These values could be set by the bt_psplit routine.  The problem is that the
- * entry has to be popped off of the stack etc. or the values have to be passed
- * all the way back to bt_split/bt_rroot and it's not very clean.
- */
-static recno_t
-rec_total(h)
-	PAGE *h;
-{
-	recno_t recs;
-	indx_t nxt, top;
-
-	for (recs = 0, nxt = 0, top = NEXTINDEX(h); nxt < top; ++nxt)
-		recs += GETRINTERNAL(h, nxt)->nrecs;
-	return (recs);
-}
diff --git a/main/db1-ast/btree/bt_utils.c b/main/db1-ast/btree/bt_utils.c
deleted file mode 100644
index 2ecb5e678..000000000
--- a/main/db1-ast/btree/bt_utils.c
+++ /dev/null
@@ -1,260 +0,0 @@
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)bt_utils.c	8.8 (Berkeley) 7/20/94";
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/param.h>
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "../include/db.h"
-#include "btree.h"
-
-/*
- * __bt_ret --
- *	Build return key/data pair.
- *
- * Parameters:
- *	t:	tree
- *	e:	key/data pair to be returned
- *	key:	user's key structure (NULL if not to be filled in)
- *	rkey:	memory area to hold key
- *	data:	user's data structure (NULL if not to be filled in)
- *	rdata:	memory area to hold data
- *       copy:	always copy the key/data item
- *
- * Returns:
- *	RET_SUCCESS, RET_ERROR.
- */
-int
-__bt_ret(t, e, key, rkey, data, rdata, copy)
-	BTREE *t;
-	EPG *e;
-	DBT *key, *rkey, *data, *rdata;
-	int copy;
-{
-	BLEAF *bl;
-	void *p;
-
-	bl = GETBLEAF(e->page, e->index);
-
-	/*
-	 * We must copy big keys/data to make them contiguous.  Otherwise,
-	 * leave the page pinned and don't copy unless the user specified
-	 * concurrent access.
-	 */
-	if (key == NULL)
-		goto dataonly;
-
-	if (bl->flags & P_BIGKEY) {
-		if (__ovfl_get(t, bl->bytes,
-		    &key->size, &rkey->data, &rkey->size))
-			return (RET_ERROR);
-		key->data = rkey->data;
-	} else if (copy || F_ISSET(t, B_DB_LOCK)) {
-		if (bl->ksize > rkey->size) {
-			p = (void *)(rkey->data == NULL ?
-			    malloc(bl->ksize) : realloc(rkey->data, bl->ksize));
-			if (p == NULL)
-				return (RET_ERROR);
-			rkey->data = p;
-			rkey->size = bl->ksize;
-		}
-		memmove(rkey->data, bl->bytes, bl->ksize);
-		key->size = bl->ksize;
-		key->data = rkey->data;
-	} else {
-		key->size = bl->ksize;
-		key->data = bl->bytes;
-	}
-
-dataonly:
-	if (data == NULL)
-		return (RET_SUCCESS);
-
-	if (bl->flags & P_BIGDATA) {
-		if (__ovfl_get(t, bl->bytes + bl->ksize,
-		    &data->size, &rdata->data, &rdata->size))
-			return (RET_ERROR);
-		data->data = rdata->data;
-	} else if (copy || F_ISSET(t, B_DB_LOCK)) {
-		/* Use +1 in case the first record retrieved is 0 length. */
-		if (bl->dsize + 1 > rdata->size) {
-			p = (void *)(rdata->data == NULL ?
-			    malloc(bl->dsize + 1) :
-			    realloc(rdata->data, bl->dsize + 1));
-			if (p == NULL)
-				return (RET_ERROR);
-			rdata->data = p;
-			rdata->size = bl->dsize + 1;
-		}
-		memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
-		data->size = bl->dsize;
-		data->data = rdata->data;
-	} else {
-		data->size = bl->dsize;
-		data->data = bl->bytes + bl->ksize;
-	}
-
-	return (RET_SUCCESS);
-}
-
-/*
- * __BT_CMP -- Compare a key to a given record.
- *
- * Parameters:
- *	t:	tree
- *	k1:	DBT pointer of first arg to comparison
- *	e:	pointer to EPG for comparison
- *
- * Returns:
- *	< 0 if k1 is < record
- *	= 0 if k1 is = record
- *	> 0 if k1 is > record
- */
-int
-__bt_cmp(t, k1, e)
-	BTREE *t;
-	const DBT *k1;
-	EPG *e;
-{
-	BINTERNAL *bi;
-	BLEAF *bl;
-	DBT k2;
-	PAGE *h;
-	void *bigkey;
-
-	/*
-	 * The left-most key on internal pages, at any level of the tree, is
-	 * guaranteed by the following code to be less than any user key.
-	 * This saves us from having to update the leftmost key on an internal
-	 * page when the user inserts a new key in the tree smaller than
-	 * anything we've yet seen.
-	 */
-	h = e->page;
-	if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
-		return (1);
-
-	bigkey = NULL;
-	if (h->flags & P_BLEAF) {
-		bl = GETBLEAF(h, e->index);
-		if (bl->flags & P_BIGKEY)
-			bigkey = bl->bytes;
-		else {
-			k2.data = bl->bytes;
-			k2.size = bl->ksize;
-		}
-	} else {
-		bi = GETBINTERNAL(h, e->index);
-		if (bi->flags & P_BIGKEY)
-			bigkey = bi->bytes;
-		else {
-			k2.data = bi->bytes;
-			k2.size = bi->ksize;
-		}
-	}
-
-	if (bigkey) {
-		if (__ovfl_get(t, bigkey,
-		    &k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
-			return (RET_ERROR);
-		k2.data = t->bt_rdata.data;
-	}
-	return ((*t->bt_cmp)(k1, &k2));
-}
-
-/*
- * __BT_DEFCMP -- Default comparison routine.
- *
- * Parameters:
- *	a:	DBT #1
- *	b: 	DBT #2
- *
- * Returns:
- *	< 0 if a is < b
- *	= 0 if a is = b
- *	> 0 if a is > b
- */
-int
-__bt_defcmp(a, b)
-	const DBT *a, *b;
-{
-	register size_t len;
-	register u_char *p1, *p2;
-
-	/*
-	 * XXX
-	 * If a size_t doesn't fit in an int, this routine can lose.
-	 * What we need is a integral type which is guaranteed to be
-	 * larger than a size_t, and there is no such thing.
-	 */
-	len = MIN(a->size, b->size);
-	for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
-		if (*p1 != *p2)
-			return ((int)*p1 - (int)*p2);
-	return ((int)a->size - (int)b->size);
-}
-
-/*
- * __BT_DEFPFX -- Default prefix routine.
- *
- * Parameters:
- *	a:	DBT #1
- *	b: 	DBT #2
- *
- * Returns:
- *	Number of bytes needed to distinguish b from a.
- */
-size_t
-__bt_defpfx(a, b)
-	const DBT *a, *b;
-{
-	register u_char *p1, *p2;
-	register size_t cnt, len;
-
-	cnt = 1;
-	len = MIN(a->size, b->size);
-	for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
-		if (*p1 != *p2)
-			return (cnt);
-
-	/* a->size must be <= b->size, or they wouldn't be in this order. */
-	return (a->size < b->size ? a->size + 1 : a->size);
-}
diff --git a/main/db1-ast/btree/btree.h b/main/db1-ast/btree/btree.h
deleted file mode 100644
index 1f4a9ec91..000000000
--- a/main/db1-ast/btree/btree.h
+++ /dev/null
@@ -1,391 +0,0 @@
-/*-
- * Copyright (c) 1991, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Mike Olson.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- *	@(#)btree.h	8.11 (Berkeley) 8/17/94
- */
-
-/* Macros to set/clear/test flags. */
-#define	F_SET(p, f)	(p)->flags |= (f)
-#define	F_CLR(p, f)	(p)->flags &= ~(f)
-#define	F_ISSET(p, f)	((p)->flags & (f))
-
-#include <mpool.h>
-
-#define mpool_open __mpool_open
-#define mpool_filter __mpool_filter
-#define mpool_new __mpool_new
-#define mpool_get __mpool_get
-#define mpool_put __mpool_put
-#define mpool_sync __mpool_sync
-#define mpool_close __mpool_close
-
-#define	DEFMINKEYPAGE	(2)		/* Minimum keys per page */
-#define	MINCACHE	(5)		/* Minimum cached pages */
-#define	MINPSIZE	(512)		/* Minimum page size */
-
-/*
- * Page 0 of a btree file contains a copy of the meta-data.  This page is also
- * used as an out-of-band page, i.e. page pointers that point to nowhere point
- * to page 0.  Page 1 is the root of the btree.
- */
-#define	P_INVALID	 0		/* Invalid tree page number. */
-#define	P_META		 0		/* Tree metadata page number. */
-#define	P_ROOT		 1		/* Tree root page number. */
-
-/*
- * There are five page layouts in the btree: btree internal pages (BINTERNAL),
- * btree leaf pages (BLEAF), recno internal pages (RINTERNAL), recno leaf pages
- * (RLEAF) and overflow pages.  All five page types have a page header (PAGE).
- * This implementation requires that values within structures NOT be padded.
- * (ANSI C permits random padding.)  If your compiler pads randomly you'll have
- * to do some work to get this package to run.
- */
-typedef struct _page {
-	pgno_t	pgno;			/* this page's page number */
-	pgno_t	prevpg;			/* left sibling */
-	pgno_t	nextpg;			/* right sibling */
-
-#define	P_BINTERNAL	0x01		/* btree internal page */
-#define	P_BLEAF		0x02		/* leaf page */
-#define	P_OVERFLOW	0x04		/* overflow page */
-#define	P_RINTERNAL	0x08		/* recno internal page */
-#define	P_RLEAF		0x10		/* leaf page */
-#define P_TYPE		0x1f		/* type mask */
-#define	P_PRESERVE	0x20		/* never delete this chain of pages */
-	u_int32_t flags;
-
-	indx_t	lower;			/* lower bound of free space on page */
-	indx_t	upper;			/* upper bound of free space on page */
-	indx_t	linp[1];		/* indx_t-aligned VAR. LENGTH DATA */
-} PAGE;
-
-/* First and next index. */
-#define	BTDATAOFF							\
-	(sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t) +		\
-	    sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t))
-#define	NEXTINDEX(p)	(((p)->lower - BTDATAOFF) / sizeof(indx_t))
-
-/*
- * For pages other than overflow pages, there is an array of offsets into the
- * rest of the page immediately following the page header.  Each offset is to
- * an item which is unique to the type of page.  The h_lower offset is just
- * past the last filled-in index.  The h_upper offset is the first item on the
- * page.  Offsets are from the beginning of the page.
- *
- * If an item is too big to store on a single page, a flag is set and the item
- * is a { page, size } pair such that the page is the first page of an overflow
- * chain with size bytes of item.  Overflow pages are simply bytes without any
- * external structure.
- *
- * The page number and size fields in the items are pgno_t-aligned so they can
- * be manipulated without copying.  (This presumes that 32 bit items can be
- * manipulated on this system.)
- */
-#define	LALIGN(n)	(((n) + sizeof(pgno_t) - 1) & ~(sizeof(pgno_t) - 1))
-#define	NOVFLSIZE	(sizeof(pgno_t) + sizeof(u_int32_t))
-
-/*
- * For the btree internal pages, the item is a key.  BINTERNALs are {key, pgno}
- * pairs, such that the key compares less than or equal to all of the records
- * on that page.  For a tree without duplicate keys, an internal page with two
- * consecutive keys, a and b, will have all records greater than or equal to a
- * and less than b stored on the page associated with a.  Duplicate keys are
- * somewhat special and can cause duplicate internal and leaf page records and
- * some minor modifications of the above rule.
- */
-typedef struct _binternal {
-	u_int32_t ksize;		/* key size */
-	pgno_t	pgno;			/* page number stored on */
-#define	P_BIGDATA	0x01		/* overflow data */
-#define	P_BIGKEY	0x02		/* overflow key */
-	u_char	flags;
-	char	bytes[1];		/* data */
-} BINTERNAL;
-
-/* Get the page's BINTERNAL structure at index indx. */
-#define	GETBINTERNAL(pg, indx)						\
-	((BINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
-
-/* Get the number of bytes in the entry. */
-#define NBINTERNAL(len)							\
-	LALIGN(sizeof(u_int32_t) + sizeof(pgno_t) + sizeof(u_char) + (len))
-
-/* Copy a BINTERNAL entry to the page. */
-#define	WR_BINTERNAL(p, size, pgno, flags) {				\
-	*(u_int32_t *)p = size;						\
-	p += sizeof(u_int32_t);						\
-	*(pgno_t *)p = pgno;						\
-	p += sizeof(pgno_t);						\
-	*(u_char *)p = flags;						\
-	p += sizeof(u_char);						\
-}
-
-/*
- * For the recno internal pages, the item is a page number with the number of
- * keys found on that page and below.
- */
-typedef struct _rinternal {
-	recno_t	nrecs;			/* number of records */
-	pgno_t	pgno;			/* page number stored below */
-} RINTERNAL;
-
-/* Get the page's RINTERNAL structure at index indx. */
-#define	GETRINTERNAL(pg, indx)						\
-	((RINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
-
-/* Get the number of bytes in the entry. */
-#define NRINTERNAL							\
-	LALIGN(sizeof(recno_t) + sizeof(pgno_t))
-
-/* Copy a RINTERNAL entry to the page. */
-#define	WR_RINTERNAL(p, nrecs, pgno) {					\
-	*(recno_t *)p = nrecs;						\
-	p += sizeof(recno_t);						\
-	*(pgno_t *)p = pgno;						\
-}
-
-/* For the btree leaf pages, the item is a key and data pair. */
-typedef struct _bleaf {
-	u_int32_t	ksize;		/* size of key */
-	u_int32_t	dsize;		/* size of data */
-	u_char	flags;			/* P_BIGDATA, P_BIGKEY */
-	char	bytes[1];		/* data */
-} BLEAF;
-
-/* Get the page's BLEAF structure at index indx. */
-#define	GETBLEAF(pg, indx)						\
-	((BLEAF *)((char *)(pg) + (pg)->linp[indx]))
-
-/* Get the number of bytes in the entry. */
-#define NBLEAF(p)	NBLEAFDBT((p)->ksize, (p)->dsize)
-
-/* Get the number of bytes in the user's key/data pair. */
-#define NBLEAFDBT(ksize, dsize)						\
-	LALIGN(sizeof(u_int32_t) + sizeof(u_int32_t) + sizeof(u_char) +	\
-	    (ksize) + (dsize))
-
-/* Copy a BLEAF entry to the page. */
-#define	WR_BLEAF(p, key, data, flags) {					\
-	*(u_int32_t *)p = key->size;					\
-	p += sizeof(u_int32_t);						\
-	*(u_int32_t *)p = data->size;					\
-	p += sizeof(u_int32_t);						\
-	*(u_char *)p = flags;						\
-	p += sizeof(u_char);						\
-	memmove(p, key->data, key->size);				\
-	p += key->size;							\
-	memmove(p, data->data, data->size);				\
-}
-
-/* For the recno leaf pages, the item is a data entry. */
-typedef struct _rleaf {
-	u_int32_t	dsize;		/* size of data */
-	u_char	flags;			/* P_BIGDATA */
-	char	bytes[1];
-} RLEAF;
-
-/* Get the page's RLEAF structure at index indx. */
-#define	GETRLEAF(pg, indx)						\
-	((RLEAF *)((char *)(pg) + (pg)->linp[indx]))
-
-/* Get the number of bytes in the entry. */
-#define NRLEAF(p)	NRLEAFDBT((p)->dsize)
-
-/* Get the number of bytes from the user's data. */
-#define	NRLEAFDBT(dsize)						\
-	LALIGN(sizeof(u_int32_t) + sizeof(u_char) + (dsize))
-
-/* Copy a RLEAF entry to the page. */
-#define	WR_RLEAF(p, data, flags) {					\
-	*(u_int32_t *)p = data->size;					\
-	p += sizeof(u_int32_t);						\
-	*(u_char *)p = flags;						\
-	p += sizeof(u_char);						\
-	memmove(p, data->data, data->size);				\
-}
-
-/*
- * A record in the tree is either a pointer to a page and an index in the page
- * or a page number and an index.  These structures are used as a cursor, stack
- * entry and search returns as well as to pass records to other routines.
- *
- * One comment about searches.  Internal page searches must find the largest
- * record less than key in the tree so that descents work.  Leaf page searches
- * must find the smallest record greater than key so that the returned index
- * is the record's correct position for insertion.
- */
-typedef struct _epgno {
-	pgno_t	pgno;			/* the page number */
-	indx_t	index;			/* the index on the page */
-} EPGNO;
-
-typedef struct _epg {
-	PAGE	*page;			/* the (pinned) page */
-	indx_t	 index;			/* the index on the page */
-} EPG;
-
-/*
- * About cursors.  The cursor (and the page that contained the key/data pair
- * that it referenced) can be deleted, which makes things a bit tricky.  If
- * there are no duplicates of the cursor key in the tree (i.e. B_NODUPS is set
- * or there simply aren't any duplicates of the key) we copy the key that it
- * referenced when it's deleted, and reacquire a new cursor key if the cursor
- * is used again.  If there are duplicates keys, we move to the next/previous
- * key, and set a flag so that we know what happened.  NOTE: if duplicate (to
- * the cursor) keys are added to the tree during this process, it is undefined
- * if they will be returned or not in a cursor scan.
- *
- * The flags determine the possible states of the cursor:
- *
- * CURS_INIT	The cursor references *something*.
- * CURS_ACQUIRE	The cursor was deleted, and a key has been saved so that
- *		we can reacquire the right position in the tree.
- * CURS_AFTER, CURS_BEFORE
- *		The cursor was deleted, and now references a key/data pair
- *		that has not yet been returned, either before or after the
- *		deleted key/data pair.
- * XXX
- * This structure is broken out so that we can eventually offer multiple
- * cursors as part of the DB interface.
- */
-typedef struct _cursor {
-	EPGNO	 pg;			/* B: Saved tree reference. */
-	DBT	 key;			/* B: Saved key, or key.data == NULL. */
-	recno_t	 rcursor;		/* R: recno cursor (1-based) */
-
-#define	CURS_ACQUIRE	0x01		/*  B: Cursor needs to be reacquired. */
-#define	CURS_AFTER	0x02		/*  B: Unreturned cursor after key. */
-#define	CURS_BEFORE	0x04		/*  B: Unreturned cursor before key. */
-#define	CURS_INIT	0x08		/* RB: Cursor initialized. */
-	u_int8_t flags;
-} CURSOR;
-
-/*
- * The metadata of the tree.  The nrecs field is used only by the RECNO code.
- * This is because the btree doesn't really need it and it requires that every
- * put or delete call modify the metadata.
- */
-typedef struct _btmeta {
-	u_int32_t	magic;		/* magic number */
-	u_int32_t	version;	/* version */
-	u_int32_t	psize;		/* page size */
-	u_int32_t	free;		/* page number of first free page */
-	u_int32_t	nrecs;		/* R: number of records */
-
-#define	SAVEMETA	(B_NODUPS | R_RECNO)
-	u_int32_t	flags;		/* bt_flags & SAVEMETA */
-} BTMETA;
-
-/* The in-memory btree/recno data structure. */
-typedef struct _btree {
-	MPOOL	 *bt_mp;		/* memory pool cookie */
-
-	DB	 *bt_dbp;		/* pointer to enclosing DB */
-
-	EPG	  bt_cur;		/* current (pinned) page */
-	PAGE	 *bt_pinned;		/* page pinned across calls */
-
-	CURSOR	  bt_cursor;		/* cursor */
-
-#define	BT_PUSH(t, p, i) {						\
-	t->bt_sp->pgno = p; 						\
-	t->bt_sp->index = i; 						\
-	++t->bt_sp;							\
-}
-#define	BT_POP(t)	(t->bt_sp == t->bt_stack ? NULL : --t->bt_sp)
-#define	BT_CLR(t)	(t->bt_sp = t->bt_stack)
-	EPGNO	  bt_stack[50];		/* stack of parent pages */
-	EPGNO	 *bt_sp;		/* current stack pointer */
-
-	DBT	  bt_rkey;		/* returned key */
-	DBT	  bt_rdata;		/* returned data */
-
-	int	  bt_fd;		/* tree file descriptor */
-
-	pgno_t	  bt_free;		/* next free page */
-	u_int32_t bt_psize;		/* page size */
-	indx_t	  bt_ovflsize;		/* cut-off for key/data overflow */
-	int	  bt_lorder;		/* byte order */
-					/* sorted order */
-	enum { NOT, BACK, FORWARD } bt_order;
-	EPGNO	  bt_last;		/* last insert */
-
-					/* B: key comparison function */
-	int	(*bt_cmp) __P((const DBT *, const DBT *));
-					/* B: prefix comparison function */
-	size_t	(*bt_pfx) __P((const DBT *, const DBT *));
-					/* R: recno input function */
-	int	(*bt_irec) __P((struct _btree *, recno_t));
-
-	FILE	 *bt_rfp;		/* R: record FILE pointer */
-	int	  bt_rfd;		/* R: record file descriptor */
-
-	caddr_t	  bt_cmap;		/* R: current point in mapped space */
-	caddr_t	  bt_smap;		/* R: start of mapped space */
-	caddr_t   bt_emap;		/* R: end of mapped space */
-	size_t	  bt_msize;		/* R: size of mapped region. */
-
-	recno_t	  bt_nrecs;		/* R: number of records */
-	size_t	  bt_reclen;		/* R: fixed record length */
-	u_char	  bt_bval;		/* R: delimiting byte/pad character */
-
-/*
- * NB:
- * B_NODUPS and R_RECNO are stored on disk, and may not be changed.
- */
-#define	B_INMEM		0x00001		/* in-memory tree */
-#define	B_METADIRTY	0x00002		/* need to write metadata */
-#define	B_MODIFIED	0x00004		/* tree modified */
-#define	B_NEEDSWAP	0x00008		/* if byte order requires swapping */
-#define	B_RDONLY	0x00010		/* read-only tree */
-
-#define	B_NODUPS	0x00020		/* no duplicate keys permitted */
-#define	R_RECNO		0x00080		/* record oriented tree */
-
-#define	R_CLOSEFP	0x00040		/* opened a file pointer */
-#define	R_EOF		0x00100		/* end of input file reached. */
-#define	R_FIXLEN	0x00200		/* fixed length records */
-#define	R_MEMMAPPED	0x00400		/* memory mapped file. */
-#define	R_INMEM		0x00800		/* in-memory file */
-#define	R_MODIFIED	0x01000		/* modified file */
-#define	R_RDONLY	0x02000		/* read-only file */
-
-#define	B_DB_LOCK	0x04000		/* DB_LOCK specified. */
-#define	B_DB_SHMEM	0x08000		/* DB_SHMEM specified. */
-#define	B_DB_TXN	0x10000		/* DB_TXN specified. */
-	u_int32_t flags;
-} BTREE;
-
-#include "extern.h"
diff --git a/main/db1-ast/btree/extern.h b/main/db1-ast/btree/extern.h
deleted file mode 100644
index ebd9c5492..000000000
--- a/main/db1-ast/btree/extern.h
+++ /dev/null
@@ -1,70 +0,0 @@
-/*-
- * Copyright (c) 1991, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- *	@(#)extern.h	8.10 (Berkeley) 7/20/94
- */
-
-int	 __bt_close __P((DB *));
-int	 __bt_cmp __P((BTREE *, const DBT *, EPG *));
-int	 __bt_crsrdel __P((BTREE *, EPGNO *));
-int	 __bt_defcmp __P((const DBT *, const DBT *));
-size_t	 __bt_defpfx __P((const DBT *, const DBT *));
-int	 __bt_delete __P((const DB *, const DBT *, u_int));
-int	 __bt_dleaf __P((BTREE *, const DBT *, PAGE *, u_int));
-int	 __bt_fd __P((const DB *));
-int	 __bt_free __P((BTREE *, PAGE *));
-int	 __bt_get __P((const DB *, const DBT *, DBT *, u_int));
-PAGE	*__bt_new __P((BTREE *, pgno_t *));
-void	 __bt_pgin __P((void *, pgno_t, void *));
-void	 __bt_pgout __P((void *, pgno_t, void *));
-int	 __bt_push __P((BTREE *, pgno_t, int));
-int	 __bt_put __P((const DB *dbp, DBT *, const DBT *, u_int));
-int	 __bt_ret __P((BTREE *, EPG *, DBT *, DBT *, DBT *, DBT *, int));
-EPG	*__bt_search __P((BTREE *, const DBT *, int *));
-int	 __bt_seq __P((const DB *, DBT *, DBT *, u_int));
-void	 __bt_setcur __P((BTREE *, pgno_t, u_int));
-int	 __bt_split __P((BTREE *, PAGE *,
-	    const DBT *, const DBT *, int, size_t, u_int32_t));
-int	 __bt_sync __P((const DB *, u_int));
-
-int	 __ovfl_delete __P((BTREE *, void *));
-int	 __ovfl_get __P((BTREE *, void *, size_t *, void **, size_t *));
-int	 __ovfl_put __P((BTREE *, const DBT *, pgno_t *));
-
-#ifdef DEBUG
-void	 __bt_dnpage __P((DB *, pgno_t));
-void	 __bt_dpage __P((PAGE *));
-void	 __bt_dump __P((DB *));
-#endif
-#ifdef STATISTICS
-void	 __bt_stat __P((DB *));
-#endif