about summary refs log tree commit diff
path: root/db/recno
diff options
context:
space:
mode:
Diffstat (limited to 'db/recno')
-rw-r--r--db/recno/extern.h54
-rw-r--r--db/recno/rec_close.c182
-rw-r--r--db/recno/rec_delete.c197
-rw-r--r--db/recno/rec_get.c311
-rw-r--r--db/recno/rec_open.c241
-rw-r--r--db/recno/rec_put.c280
-rw-r--r--db/recno/rec_search.c126
-rw-r--r--db/recno/rec_seq.c131
-rw-r--r--db/recno/rec_utils.c122
-rw-r--r--db/recno/recno.h39
10 files changed, 1683 insertions, 0 deletions
diff --git a/db/recno/extern.h b/db/recno/extern.h
new file mode 100644
index 0000000000..feed434453
--- /dev/null
+++ b/db/recno/extern.h
@@ -0,0 +1,54 @@
+/*-
+ * Copyright (c) 1991, 1993
+ *	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.3 (Berkeley) 6/4/94
+ */
+
+#include "../btree/extern.h"
+
+int	 __rec_close __P((DB *));
+int	 __rec_delete __P((const DB *, const DBT *, u_int));
+int	 __rec_dleaf __P((BTREE *, PAGE *, u_int32_t));
+int	 __rec_fd __P((const DB *));
+int	 __rec_fmap __P((BTREE *, recno_t));
+int	 __rec_fout __P((BTREE *));
+int	 __rec_fpipe __P((BTREE *, recno_t));
+int	 __rec_get __P((const DB *, const DBT *, DBT *, u_int));
+int	 __rec_iput __P((BTREE *, recno_t, const DBT *, u_int));
+int	 __rec_put __P((const DB *dbp, DBT *, const DBT *, u_int));
+int	 __rec_ret __P((BTREE *, EPG *, recno_t, DBT *, DBT *));
+EPG	*__rec_search __P((BTREE *, recno_t, enum SRCHOP));
+int	 __rec_seq __P((const DB *, DBT *, DBT *, u_int));
+int	 __rec_sync __P((const DB *, u_int));
+int	 __rec_vmap __P((BTREE *, recno_t));
+int	 __rec_vout __P((BTREE *));
+int	 __rec_vpipe __P((BTREE *, recno_t));
diff --git a/db/recno/rec_close.c b/db/recno/rec_close.c
new file mode 100644
index 0000000000..16fb0b4eca
--- /dev/null
+++ b/db/recno/rec_close.c
@@ -0,0 +1,182 @@
+/*-
+ * 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[] = "@(#)rec_close.c	8.6 (Berkeley) 8/18/94";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+#include <sys/uio.h>
+#include <sys/mman.h>
+
+#include <errno.h>
+#include <limits.h>
+#include <stdio.h>
+#include <unistd.h>
+
+#include <db.h>
+#include "recno.h"
+
+/*
+ * __REC_CLOSE -- Close a recno tree.
+ *
+ * Parameters:
+ *	dbp:	pointer to access method
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+int
+__rec_close(dbp)
+	DB *dbp;
+{
+	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;
+	}
+
+	if (__rec_sync(dbp, 0) == RET_ERROR)
+		return (RET_ERROR);
+
+	/* Committed to closing. */
+	status = RET_SUCCESS;
+	if (F_ISSET(t, R_MEMMAPPED) && munmap(t->bt_smap, t->bt_msize))
+		status = RET_ERROR;
+
+	if (!F_ISSET(t, R_INMEM))
+		if (F_ISSET(t, R_CLOSEFP)) {
+			if (fclose(t->bt_rfp))
+				status = RET_ERROR;
+		} else
+			if (close(t->bt_rfd))
+				status = RET_ERROR;
+
+	if (__bt_close(dbp) == RET_ERROR)
+		status = RET_ERROR;
+
+	return (status);
+}
+
+/*
+ * __REC_SYNC -- sync the recno tree to disk.
+ *
+ * Parameters:
+ *	dbp:	pointer to access method
+ *
+ * Returns:
+ *	RET_SUCCESS, RET_ERROR.
+ */
+int
+__rec_sync(dbp, flags)
+	const DB *dbp;
+	u_int flags;
+{
+	struct iovec iov[2];
+	BTREE *t;
+	DBT data, key;
+	off_t off;
+	recno_t scursor, trec;
+	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 (flags == R_RECNOSYNC)
+		return (__bt_sync(dbp, 0));
+
+	if (F_ISSET(t, R_RDONLY | R_INMEM) || !F_ISSET(t, R_MODIFIED))
+		return (RET_SUCCESS);
+
+	/* Read any remaining records into the tree. */
+	if (!F_ISSET(t, R_EOF) && t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR)
+		return (RET_ERROR);
+
+	/* Rewind the file descriptor. */
+	if (lseek(t->bt_rfd, (off_t)0, SEEK_SET) != 0)
+		return (RET_ERROR);
+
+	/* Save the cursor. */
+	scursor = t->bt_cursor.rcursor;
+
+	key.size = sizeof(recno_t);
+	key.data = &trec;
+
+	if (F_ISSET(t, R_FIXLEN)) {
+		/*
+		 * We assume that fixed length records are all fixed length.
+		 * Any that aren't are either EINVAL'd or corrected by the
+		 * record put code.
+		 */
+		status = (dbp->seq)(dbp, &key, &data, R_FIRST);
+		while (status == RET_SUCCESS) {
+			if (write(t->bt_rfd, data.data, data.size) != data.size)
+				return (RET_ERROR);
+			status = (dbp->seq)(dbp, &key, &data, R_NEXT);
+		}
+	} else {
+		iov[1].iov_base = &t->bt_bval;
+		iov[1].iov_len = 1;
+
+		status = (dbp->seq)(dbp, &key, &data, R_FIRST);
+		while (status == RET_SUCCESS) {
+			iov[0].iov_base = data.data;
+			iov[0].iov_len = data.size;
+			if (writev(t->bt_rfd, iov, 2) != data.size + 1)
+				return (RET_ERROR);
+			status = (dbp->seq)(dbp, &key, &data, R_NEXT);
+		}
+	}
+
+	/* Restore the cursor. */
+	t->bt_cursor.rcursor = scursor;
+
+	if (status == RET_ERROR)
+		return (RET_ERROR);
+	if ((off = lseek(t->bt_rfd, (off_t)0, SEEK_CUR)) == -1)
+		return (RET_ERROR);
+	if (ftruncate(t->bt_rfd, off))
+		return (RET_ERROR);
+	F_CLR(t, R_MODIFIED);
+	return (RET_SUCCESS);
+}
diff --git a/db/recno/rec_delete.c b/db/recno/rec_delete.c
new file mode 100644
index 0000000000..a16593d4e6
--- /dev/null
+++ b/db/recno/rec_delete.c
@@ -0,0 +1,197 @@
+/*-
+ * 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[] = "@(#)rec_delete.c	8.7 (Berkeley) 7/14/94";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+
+#include <errno.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <db.h>
+#include "recno.h"
+
+static int rec_rdelete __P((BTREE *, recno_t));
+
+/*
+ * __REC_DELETE -- Delete the item(s) referenced by a key.
+ *
+ * Parameters:
+ *	dbp:	pointer to access method
+ *	key:	key to delete
+ *	flags:	R_CURSOR if deleting what the cursor references
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
+ */
+int
+__rec_delete(dbp, key, flags)
+	const DB *dbp;
+	const DBT *key;
+	u_int flags;
+{
+	BTREE *t;
+	recno_t nrec;
+	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;
+	}
+
+	switch(flags) {
+	case 0:
+		if ((nrec = *(recno_t *)key->data) == 0)
+			goto einval;
+		if (nrec > t->bt_nrecs)
+			return (RET_SPECIAL);
+		--nrec;
+		status = rec_rdelete(t, nrec);
+		break;
+	case R_CURSOR:
+		if (!F_ISSET(&t->bt_cursor, CURS_INIT))
+			goto einval;
+		if (t->bt_nrecs == 0)
+			return (RET_SPECIAL);
+		status = rec_rdelete(t, t->bt_cursor.rcursor - 1);
+		if (status == RET_SUCCESS)
+			--t->bt_cursor.rcursor;
+		break;
+	default:
+einval:		errno = EINVAL;
+		return (RET_ERROR);
+	}
+
+	if (status == RET_SUCCESS)
+		F_SET(t, B_MODIFIED | R_MODIFIED);
+	return (status);
+}
+
+/*
+ * REC_RDELETE -- Delete the data matching the specified key.
+ *
+ * Parameters:
+ *	tree:	tree
+ *	nrec:	record to delete
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
+ */
+static int
+rec_rdelete(t, nrec)
+	BTREE *t;
+	recno_t nrec;
+{
+	EPG *e;
+	PAGE *h;
+	int status;
+
+	/* Find the record; __rec_search pins the page. */
+	if ((e = __rec_search(t, nrec, SDELETE)) == NULL)
+		return (RET_ERROR);
+
+	/* Delete the record. */
+	h = e->page;
+	status = __rec_dleaf(t, h, e->index);
+	if (status != RET_SUCCESS) {
+		mpool_put(t->bt_mp, h, 0);
+		return (status);
+	}
+	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+	return (RET_SUCCESS);
+}
+
+/*
+ * __REC_DLEAF -- Delete a single record from a recno leaf page.
+ *
+ * Parameters:
+ *	t:	tree
+ *	index:	index on current page to delete
+ *
+ * Returns:
+ *	RET_SUCCESS, RET_ERROR.
+ */
+int
+__rec_dleaf(t, h, index)
+	BTREE *t;
+	PAGE *h;
+	u_int32_t index;
+{
+	RLEAF *rl;
+	indx_t *ip, cnt, offset;
+	u_int32_t nbytes;
+	char *from;
+	void *to;
+
+	/*
+	 * Delete a record from a recno leaf page.  Internal records are never
+	 * deleted from internal pages, regardless of the records that caused
+	 * them to be added being deleted.  Pages made empty by deletion are
+	 * not reclaimed.  They are, however, made available for reuse.
+	 *
+	 * Pack the remaining entries at the end of the page, shift the indices
+	 * down, overwriting the deleted record and its index.  If the record
+	 * uses overflow pages, make them available for reuse.
+	 */
+	to = rl = GETRLEAF(h, index);
+	if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR)
+		return (RET_ERROR);
+	nbytes = NRLEAF(rl);
+
+	/*
+	 * Compress the key/data pairs.  Compress and adjust the [BR]LEAF
+	 * offsets.  Reset the headers.
+	 */
+	from = (char *)h + h->upper;
+	memmove(from + nbytes, from, (char *)to - from);
+	h->upper += nbytes;
+
+	offset = h->linp[index];
+	for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip)
+		if (ip[0] < offset)
+			ip[0] += nbytes;
+	for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip)
+		ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
+	h->lower -= sizeof(indx_t);
+	--t->bt_nrecs;
+	return (RET_SUCCESS);
+}
diff --git a/db/recno/rec_get.c b/db/recno/rec_get.c
new file mode 100644
index 0000000000..47dd773fb9
--- /dev/null
+++ b/db/recno/rec_get.c
@@ -0,0 +1,311 @@
+/*-
+ * 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[] = "@(#)rec_get.c	8.9 (Berkeley) 8/18/94";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+
+#include <errno.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include <db.h>
+#include "recno.h"
+
+/*
+ * __REC_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
+__rec_get(dbp, key, data, flags)
+	const DB *dbp;
+	const DBT *key;
+	DBT *data;
+	u_int flags;
+{
+	BTREE *t;
+	EPG *e;
+	recno_t nrec;
+	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;
+	}
+
+	/* Get currently doesn't take any flags, and keys of 0 are illegal. */
+	if (flags || (nrec = *(recno_t *)key->data) == 0) {
+		errno = EINVAL;
+		return (RET_ERROR);
+	}
+
+	/*
+	 * If we haven't seen this record yet, try to find it in the
+	 * original file.
+	 */
+	if (nrec > t->bt_nrecs) {
+		if (F_ISSET(t, R_EOF | R_INMEM))
+			return (RET_SPECIAL);
+		if ((status = t->bt_irec(t, nrec)) != RET_SUCCESS)
+			return (status);
+	}
+
+	--nrec;
+	if ((e = __rec_search(t, nrec, SEARCH)) == NULL)
+		return (RET_ERROR);
+
+	status = __rec_ret(t, e, 0, NULL, data);
+	if (F_ISSET(t, B_DB_LOCK))
+		mpool_put(t->bt_mp, e->page, 0);
+	else
+		t->bt_pinned = e->page;
+	return (status);
+}
+
+/*
+ * __REC_FPIPE -- Get fixed length records from a pipe.
+ *
+ * Parameters:
+ *	t:	tree
+ *	cnt:	records to read
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+int
+__rec_fpipe(t, top)
+	BTREE *t;
+	recno_t top;
+{
+	DBT data;
+	recno_t nrec;
+	size_t len;
+	int ch;
+	u_char *p;
+
+	if (t->bt_rdata.size < t->bt_reclen) {
+		t->bt_rdata.data = t->bt_rdata.data == NULL ?
+		    malloc(t->bt_reclen) :
+		    realloc(t->bt_rdata.data, t->bt_reclen);
+		if (t->bt_rdata.data == NULL)
+			return (RET_ERROR);
+		t->bt_rdata.size = t->bt_reclen;
+	}
+	data.data = t->bt_rdata.data;
+	data.size = t->bt_reclen;
+
+	for (nrec = t->bt_nrecs; nrec < top;) {
+		len = t->bt_reclen;
+		for (p = t->bt_rdata.data;; *p++ = ch)
+			if ((ch = getc(t->bt_rfp)) == EOF || !--len) {
+				if (ch != EOF)
+					*p = ch;
+				if (len != 0)
+					memset(p, t->bt_bval, len);
+				if (__rec_iput(t,
+				    nrec, &data, 0) != RET_SUCCESS)
+					return (RET_ERROR);
+				++nrec;
+				break;
+			}
+		if (ch == EOF)
+			break;
+	}
+	if (nrec < top) {
+		F_SET(t, R_EOF);
+		return (RET_SPECIAL);
+	}
+	return (RET_SUCCESS);
+}
+
+/*
+ * __REC_VPIPE -- Get variable length records from a pipe.
+ *
+ * Parameters:
+ *	t:	tree
+ *	cnt:	records to read
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+int
+__rec_vpipe(t, top)
+	BTREE *t;
+	recno_t top;
+{
+	DBT data;
+	recno_t nrec;
+	indx_t len;
+	size_t sz;
+	int bval, ch;
+	u_char *p;
+
+	bval = t->bt_bval;
+	for (nrec = t->bt_nrecs; nrec < top; ++nrec) {
+		for (p = t->bt_rdata.data,
+		    sz = t->bt_rdata.size;; *p++ = ch, --sz) {
+			if ((ch = getc(t->bt_rfp)) == EOF || ch == bval) {
+				data.data = t->bt_rdata.data;
+				data.size = p - (u_char *)t->bt_rdata.data;
+				if (ch == EOF && data.size == 0)
+					break;
+				if (__rec_iput(t, nrec, &data, 0)
+				    != RET_SUCCESS)
+					return (RET_ERROR);
+				break;
+			}
+			if (sz == 0) {
+				len = p - (u_char *)t->bt_rdata.data;
+				t->bt_rdata.size += (sz = 256);
+				t->bt_rdata.data = t->bt_rdata.data == NULL ?
+				    malloc(t->bt_rdata.size) :
+				    realloc(t->bt_rdata.data, t->bt_rdata.size);
+				if (t->bt_rdata.data == NULL)
+					return (RET_ERROR);
+				p = (u_char *)t->bt_rdata.data + len;
+			}
+		}
+		if (ch == EOF)
+			break;
+	}
+	if (nrec < top) {
+		F_SET(t, R_EOF);
+		return (RET_SPECIAL);
+	}
+	return (RET_SUCCESS);
+}
+
+/*
+ * __REC_FMAP -- Get fixed length records from a file.
+ *
+ * Parameters:
+ *	t:	tree
+ *	cnt:	records to read
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+int
+__rec_fmap(t, top)
+	BTREE *t;
+	recno_t top;
+{
+	DBT data;
+	recno_t nrec;
+	u_char *sp, *ep, *p;
+	size_t len;
+
+	if (t->bt_rdata.size < t->bt_reclen) {
+		t->bt_rdata.data = t->bt_rdata.data == NULL ?
+		    malloc(t->bt_reclen) :
+		    realloc(t->bt_rdata.data, t->bt_reclen);
+		if (t->bt_rdata.data == NULL)
+			return (RET_ERROR);
+		t->bt_rdata.size = t->bt_reclen;
+	}
+	data.data = t->bt_rdata.data;
+	data.size = t->bt_reclen;
+
+	sp = (u_char *)t->bt_cmap;
+	ep = (u_char *)t->bt_emap;
+	for (nrec = t->bt_nrecs; nrec < top; ++nrec) {
+		if (sp >= ep) {
+			F_SET(t, R_EOF);
+			return (RET_SPECIAL);
+		}
+		len = t->bt_reclen;
+		for (p = t->bt_rdata.data;
+		    sp < ep && len > 0; *p++ = *sp++, --len);
+		if (len != 0)
+			memset(p, t->bt_bval, len);
+		if (__rec_iput(t, nrec, &data, 0) != RET_SUCCESS)
+			return (RET_ERROR);
+	}
+	t->bt_cmap = (caddr_t)sp;
+	return (RET_SUCCESS);
+}
+
+/*
+ * __REC_VMAP -- Get variable length records from a file.
+ *
+ * Parameters:
+ *	t:	tree
+ *	cnt:	records to read
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+int
+__rec_vmap(t, top)
+	BTREE *t;
+	recno_t top;
+{
+	DBT data;
+	u_char *sp, *ep;
+	recno_t nrec;
+	int bval;
+
+	sp = (u_char *)t->bt_cmap;
+	ep = (u_char *)t->bt_emap;
+	bval = t->bt_bval;
+
+	for (nrec = t->bt_nrecs; nrec < top; ++nrec) {
+		if (sp >= ep) {
+			F_SET(t, R_EOF);
+			return (RET_SPECIAL);
+		}
+		for (data.data = sp; sp < ep && *sp != bval; ++sp);
+		data.size = sp - (u_char *)data.data;
+		if (__rec_iput(t, nrec, &data, 0) != RET_SUCCESS)
+			return (RET_ERROR);
+		++sp;
+	}
+	t->bt_cmap = (caddr_t)sp;
+	return (RET_SUCCESS);
+}
diff --git a/db/recno/rec_open.c b/db/recno/rec_open.c
new file mode 100644
index 0000000000..51d8a3c260
--- /dev/null
+++ b/db/recno/rec_open.c
@@ -0,0 +1,241 @@
+/*-
+ * 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[] = "@(#)rec_open.c	8.10 (Berkeley) 9/1/94";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+
+#include <errno.h>
+#include <fcntl.h>
+#include <limits.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <unistd.h>
+
+#include <db.h>
+#include "recno.h"
+
+DB *
+__rec_open(fname, flags, mode, openinfo, dflags)
+	const char *fname;
+	int flags, mode, dflags;
+	const RECNOINFO *openinfo;
+{
+	BTREE *t;
+	BTREEINFO btopeninfo;
+	DB *dbp;
+	PAGE *h;
+	struct stat sb;
+	int rfd, sverrno;
+
+	/* Open the user's file -- if this fails, we're done. */
+	if (fname != NULL && (rfd = open(fname, flags, mode)) < 0)
+		return (NULL);
+
+	/* Create a btree in memory (backed by disk). */
+	dbp = NULL;
+	if (openinfo) {
+		if (openinfo->flags & ~(R_FIXEDLEN | R_NOKEY | R_SNAPSHOT))
+			goto einval;
+		btopeninfo.flags = 0;
+		btopeninfo.cachesize = openinfo->cachesize;
+		btopeninfo.maxkeypage = 0;
+		btopeninfo.minkeypage = 0;
+		btopeninfo.psize = openinfo->psize;
+		btopeninfo.compare = NULL;
+		btopeninfo.prefix = NULL;
+		btopeninfo.lorder = openinfo->lorder;
+		dbp = __bt_open(openinfo->bfname,
+		    O_RDWR, S_IRUSR | S_IWUSR, &btopeninfo, dflags);
+	} else
+		dbp = __bt_open(NULL, O_RDWR, S_IRUSR | S_IWUSR, NULL, dflags);
+	if (dbp == NULL)
+		goto err;
+
+	/*
+	 * Some fields in the tree structure are recno specific.  Fill them
+	 * in and make the btree structure look like a recno structure.  We
+	 * don't change the bt_ovflsize value, it's close enough and slightly
+	 * bigger.
+	 */
+	t = dbp->internal;
+	if (openinfo) {
+		if (openinfo->flags & R_FIXEDLEN) {
+			F_SET(t, R_FIXLEN);
+			t->bt_reclen = openinfo->reclen;
+			if (t->bt_reclen == 0)
+				goto einval;
+		}
+		t->bt_bval = openinfo->bval;
+	} else
+		t->bt_bval = '\n';
+
+	F_SET(t, R_RECNO);
+	if (fname == NULL)
+		F_SET(t, R_EOF | R_INMEM);
+	else
+		t->bt_rfd = rfd;
+
+	if (fname != NULL) {
+		/*
+		 * In 4.4BSD, stat(2) returns true for ISSOCK on pipes.
+		 * Unfortunately, that's not portable, so we use lseek
+		 * and check the errno values.
+		 */
+		errno = 0;
+		if (lseek(rfd, (off_t)0, SEEK_CUR) == -1 && errno == ESPIPE) {
+			switch (flags & O_ACCMODE) {
+			case O_RDONLY:
+				F_SET(t, R_RDONLY);
+				break;
+			default:
+				goto einval;
+			}
+slow:			if ((t->bt_rfp = fdopen(rfd, "r")) == NULL)
+				goto err;
+			F_SET(t, R_CLOSEFP);
+			t->bt_irec =
+			    F_ISSET(t, R_FIXLEN) ? __rec_fpipe : __rec_vpipe;
+		} else {
+			switch (flags & O_ACCMODE) {
+			case O_RDONLY:
+				F_SET(t, R_RDONLY);
+				break;
+			case O_RDWR:
+				break;
+			default:
+				goto einval;
+			}
+
+			if (fstat(rfd, &sb))
+				goto err;
+			/*
+			 * Kluge -- we'd like to test to see if the file is too
+			 * big to mmap.  Since, we don't know what size or type
+			 * off_t's or size_t's are, what the largest unsigned
+			 * integral type is, or what random insanity the local
+			 * C compiler will perpetrate, doing the comparison in
+			 * a portable way is flatly impossible.  Hope that mmap
+			 * fails if the file is too large.
+			 */
+			if (sb.st_size == 0)
+				F_SET(t, R_EOF);
+			else {
+#ifdef MMAP_NOT_AVAILABLE
+				/*
+				 * XXX
+				 * Mmap doesn't work correctly on many current
+				 * systems.  In particular, it can fail subtly,
+				 * with cache coherency problems.  Don't use it
+				 * for now.
+				 */
+				t->bt_msize = sb.st_size;
+				if ((t->bt_smap = mmap(NULL, t->bt_msize,
+				    PROT_READ, MAP_PRIVATE, rfd,
+				    (off_t)0)) == (caddr_t)-1)
+					goto slow;
+				t->bt_cmap = t->bt_smap;
+				t->bt_emap = t->bt_smap + sb.st_size;
+				t->bt_irec = F_ISSET(t, R_FIXLEN) ?
+				    __rec_fmap : __rec_vmap;
+				F_SET(t, R_MEMMAPPED);
+#else
+				goto slow;
+#endif
+			}
+		}
+	}
+
+	/* Use the recno routines. */
+	dbp->close = __rec_close;
+	dbp->del = __rec_delete;
+	dbp->fd = __rec_fd;
+	dbp->get = __rec_get;
+	dbp->put = __rec_put;
+	dbp->seq = __rec_seq;
+	dbp->sync = __rec_sync;
+
+	/* If the root page was created, reset the flags. */
+	if ((h = mpool_get(t->bt_mp, P_ROOT, 0)) == NULL)
+		goto err;
+	if ((h->flags & P_TYPE) == P_BLEAF) {
+		F_CLR(h, P_TYPE);
+		F_SET(h, P_RLEAF);
+		mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+	} else
+		mpool_put(t->bt_mp, h, 0);
+
+	if (openinfo && openinfo->flags & R_SNAPSHOT &&
+	    !F_ISSET(t, R_EOF | R_INMEM) &&
+	    t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR)
+                goto err;
+	return (dbp);
+
+einval:	errno = EINVAL;
+err:	sverrno = errno;
+	if (dbp != NULL)
+		(void)__bt_close(dbp);
+	if (fname != NULL)
+		(void)close(rfd);
+	errno = sverrno;
+	return (NULL);
+}
+
+int
+__rec_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, R_INMEM)) {
+		errno = ENOENT;
+		return (-1);
+	}
+	return (t->bt_rfd);
+}
diff --git a/db/recno/rec_put.c b/db/recno/rec_put.c
new file mode 100644
index 0000000000..1afae0d5a6
--- /dev/null
+++ b/db/recno/rec_put.c
@@ -0,0 +1,280 @@
+/*-
+ * 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[] = "@(#)rec_put.c	8.7 (Berkeley) 8/18/94";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <db.h>
+#include "recno.h"
+
+/*
+ * __REC_PUT -- Add a recno item to the tree.
+ *
+ * Parameters:
+ *	dbp:	pointer to access method
+ *	key:	key
+ *	data:	data
+ *	flag:	R_CURSOR, R_IAFTER, R_IBEFORE, R_NOOVERWRITE
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is
+ *	already in the tree and R_NOOVERWRITE specified.
+ */
+int
+__rec_put(dbp, key, data, flags)
+	const DB *dbp;
+	DBT *key;
+	const DBT *data;
+	u_int flags;
+{
+	BTREE *t;
+	DBT fdata, tdata;
+	recno_t nrec;
+	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 using fixed-length records, and the record is long, return
+	 * EINVAL.  If it's short, pad it out.  Use the record data return
+	 * memory, it's only short-term.
+	 */
+	if (F_ISSET(t, R_FIXLEN) && data->size != t->bt_reclen) {
+		if (data->size > t->bt_reclen)
+			goto einval;
+
+		if (t->bt_rdata.size < t->bt_reclen) {
+			t->bt_rdata.data = t->bt_rdata.data == NULL ?
+			    malloc(t->bt_reclen) :
+			    realloc(t->bt_rdata.data, t->bt_reclen);
+			if (t->bt_rdata.data == NULL)
+				return (RET_ERROR);
+			t->bt_rdata.size = t->bt_reclen;
+		}
+		memmove(t->bt_rdata.data, data->data, data->size);
+		memset((char *)t->bt_rdata.data + data->size,
+		    t->bt_bval, t->bt_reclen - data->size);
+		fdata.data = t->bt_rdata.data;
+		fdata.size = t->bt_reclen;
+	} else {
+		fdata.data = data->data;
+		fdata.size = data->size;
+	}
+
+	switch (flags) {
+	case R_CURSOR:
+		if (!F_ISSET(&t->bt_cursor, CURS_INIT))
+			goto einval;
+		nrec = t->bt_cursor.rcursor;
+		break;
+	case R_SETCURSOR:
+		if ((nrec = *(recno_t *)key->data) == 0)
+			goto einval;
+		break;
+	case R_IAFTER:
+		if ((nrec = *(recno_t *)key->data) == 0) {
+			nrec = 1;
+			flags = R_IBEFORE;
+		}
+		break;
+	case 0:
+	case R_IBEFORE:
+		if ((nrec = *(recno_t *)key->data) == 0)
+			goto einval;
+		break;
+	case R_NOOVERWRITE:
+		if ((nrec = *(recno_t *)key->data) == 0)
+			goto einval;
+		if (nrec <= t->bt_nrecs)
+			return (RET_SPECIAL);
+		break;
+	default:
+einval:		errno = EINVAL;
+		return (RET_ERROR);
+	}
+
+	/*
+	 * Make sure that records up to and including the put record are
+	 * already in the database.  If skipping records, create empty ones.
+	 */
+	if (nrec > t->bt_nrecs) {
+		if (!F_ISSET(t, R_EOF | R_INMEM) &&
+		    t->bt_irec(t, nrec) == RET_ERROR)
+			return (RET_ERROR);
+		if (nrec > t->bt_nrecs + 1) {
+			if (F_ISSET(t, R_FIXLEN)) {
+				if ((tdata.data =
+				    (void *)malloc(t->bt_reclen)) == NULL)
+					return (RET_ERROR);
+				tdata.size = t->bt_reclen;
+				memset(tdata.data, t->bt_bval, tdata.size);
+			} else {
+				tdata.data = NULL;
+				tdata.size = 0;
+			}
+			while (nrec > t->bt_nrecs + 1)
+				if (__rec_iput(t,
+				    t->bt_nrecs, &tdata, 0) != RET_SUCCESS)
+					return (RET_ERROR);
+			if (F_ISSET(t, R_FIXLEN))
+				free(tdata.data);
+		}
+	}
+
+	if ((status = __rec_iput(t, nrec - 1, &fdata, flags)) != RET_SUCCESS)
+		return (status);
+
+	if (flags == R_SETCURSOR)
+		t->bt_cursor.rcursor = nrec;
+	
+	F_SET(t, R_MODIFIED);
+	return (__rec_ret(t, NULL, nrec, key, NULL));
+}
+
+/*
+ * __REC_IPUT -- Add a recno item to the tree.
+ *
+ * Parameters:
+ *	t:	tree
+ *	nrec:	record number
+ *	data:	data
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+int
+__rec_iput(t, nrec, data, flags)
+	BTREE *t;
+	recno_t nrec;
+	const DBT *data;
+	u_int flags;
+{
+	DBT tdata;
+	EPG *e;
+	PAGE *h;
+	indx_t index, nxtindex;
+	pgno_t pg;
+	u_int32_t nbytes;
+	int dflags, status;
+	char *dest, db[NOVFLSIZE];
+
+	/*
+	 * If the data won't fit on a page, store it on indirect pages.
+	 *
+	 * XXX
+	 * If the insert fails later on, these pages aren't recovered.
+	 */
+	if (data->size > t->bt_ovflsize) {
+		if (__ovfl_put(t, data, &pg) == RET_ERROR)
+			return (RET_ERROR);
+		tdata.data = db;
+		tdata.size = NOVFLSIZE;
+		*(pgno_t *)db = pg;
+		*(u_int32_t *)(db + sizeof(pgno_t)) = data->size;
+		dflags = P_BIGDATA;
+		data = &tdata;
+	} else
+		dflags = 0;
+
+	/* __rec_search pins the returned page. */
+	if ((e = __rec_search(t, nrec,
+	    nrec > t->bt_nrecs || flags == R_IAFTER || flags == R_IBEFORE ?
+	    SINSERT : SEARCH)) == NULL)
+		return (RET_ERROR);
+
+	h = e->page;
+	index = e->index;
+
+	/*
+	 * Add the specified key/data pair to the tree.  The R_IAFTER and
+	 * R_IBEFORE flags insert the key after/before the specified key.
+	 *
+	 * Pages are split as required.
+	 */
+	switch (flags) {
+	case R_IAFTER:
+		++index;
+		break;
+	case R_IBEFORE:
+		break;
+	default:
+		if (nrec < t->bt_nrecs &&
+		    __rec_dleaf(t, h, index) == RET_ERROR) {
+			mpool_put(t->bt_mp, h, 0);
+			return (RET_ERROR);
+		}
+		break;
+	}
+
+	/*
+	 * If not enough room, 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 = NRLEAFDBT(data->size);
+	if (h->upper - h->lower < nbytes + sizeof(indx_t)) {
+		status = __bt_split(t, h, NULL, data, dflags, nbytes, index);
+		if (status == RET_SUCCESS)
+			++t->bt_nrecs;
+		return (status);
+	}
+
+	if (index < (nxtindex = NEXTINDEX(h)))
+		memmove(h->linp + index + 1, h->linp + index,
+		    (nxtindex - index) * sizeof(indx_t));
+	h->lower += sizeof(indx_t);
+
+	h->linp[index] = h->upper -= nbytes;
+	dest = (char *)h + h->upper;
+	WR_RLEAF(dest, data, dflags);
+
+	++t->bt_nrecs;
+	F_SET(t, B_MODIFIED);
+	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+
+	return (RET_SUCCESS);
+}
diff --git a/db/recno/rec_search.c b/db/recno/rec_search.c
new file mode 100644
index 0000000000..acc109e992
--- /dev/null
+++ b/db/recno/rec_search.c
@@ -0,0 +1,126 @@
+/*-
+ * Copyright (c) 1990, 1993
+ *	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[] = "@(#)rec_search.c	8.4 (Berkeley) 7/14/94";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+
+#include <errno.h>
+#include <stdio.h>
+
+#include <db.h>
+#include "recno.h"
+
+/*
+ * __REC_SEARCH -- Search a btree for a key.
+ *
+ * Parameters:
+ *	t:	tree to search
+ *	recno:	key to find
+ *	op: 	search operation
+ *
+ * Returns:
+ *	EPG for matching record, if any, or the EPG for the location of the
+ *	key, if it were inserted into the tree.
+ *
+ * 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 *
+__rec_search(t, recno, op)
+	BTREE *t;
+	recno_t recno;
+	enum SRCHOP op;
+{
+	register indx_t index;
+	register PAGE *h;
+	EPGNO *parent;
+	RINTERNAL *r;
+	pgno_t pg;
+	indx_t top;
+	recno_t total;
+	int sverrno;
+
+	BT_CLR(t);
+	for (pg = P_ROOT, total = 0;;) {
+		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
+			goto err;
+		if (h->flags & P_RLEAF) {
+			t->bt_cur.page = h;
+			t->bt_cur.index = recno - total;
+			return (&t->bt_cur);
+		}
+		for (index = 0, top = NEXTINDEX(h);;) {
+			r = GETRINTERNAL(h, index);
+			if (++index == top || total + r->nrecs > recno)
+				break;
+			total += r->nrecs;
+		}
+
+		BT_PUSH(t, pg, index - 1);
+		
+		pg = r->pgno;
+		switch (op) {
+		case SDELETE:
+			--GETRINTERNAL(h, (index - 1))->nrecs;
+			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+			break;
+		case SINSERT:
+			++GETRINTERNAL(h, (index - 1))->nrecs;
+			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+			break;
+		case SEARCH:
+			mpool_put(t->bt_mp, h, 0);
+			break;
+		}
+
+	}
+	/* Try and recover the tree. */
+err:	sverrno = errno;
+	if (op != SEARCH)
+		while  ((parent = BT_POP(t)) != NULL) {
+			if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
+				break;
+			if (op == SINSERT)
+				--GETRINTERNAL(h, parent->index)->nrecs;
+			else
+				++GETRINTERNAL(h, parent->index)->nrecs;
+                        mpool_put(t->bt_mp, h, MPOOL_DIRTY);
+                }
+	errno = sverrno;
+	return (NULL);
+}
diff --git a/db/recno/rec_seq.c b/db/recno/rec_seq.c
new file mode 100644
index 0000000000..f80992c598
--- /dev/null
+++ b/db/recno/rec_seq.c
@@ -0,0 +1,131 @@
+/*-
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)rec_seq.c	8.3 (Berkeley) 7/14/94";
+#endif /* not lint */
+
+#include <sys/types.h>
+
+#include <errno.h>
+#include <limits.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <db.h>
+#include "recno.h"
+
+/*
+ * __REC_SEQ -- Recno 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
+__rec_seq(dbp, key, data, flags)
+	const DB *dbp;
+	DBT *key, *data;
+	u_int flags;
+{
+	BTREE *t;
+	EPG *e;
+	recno_t nrec;
+	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;
+	}
+
+	switch(flags) {
+	case R_CURSOR:
+		if ((nrec = *(recno_t *)key->data) == 0)
+			goto einval;
+		break;
+	case R_NEXT:
+		if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
+			nrec = t->bt_cursor.rcursor + 1;
+			break;
+		}
+		/* FALLTHROUGH */
+	case R_FIRST:
+		nrec = 1;
+		break;
+	case R_PREV:
+		if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
+			if ((nrec = t->bt_cursor.rcursor - 1) == 0)
+				return (RET_SPECIAL);
+			break;
+		}
+		/* FALLTHROUGH */
+	case R_LAST:
+		if (!F_ISSET(t, R_EOF | R_INMEM) &&
+		    t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR)
+			return (RET_ERROR);
+		nrec = t->bt_nrecs;
+		break;
+	default:
+einval:		errno = EINVAL;
+		return (RET_ERROR);
+	}
+	
+	if (t->bt_nrecs == 0 || nrec > t->bt_nrecs) {
+		if (!F_ISSET(t, R_EOF | R_INMEM) &&
+		    (status = t->bt_irec(t, nrec)) != RET_SUCCESS)
+			return (status);
+		if (t->bt_nrecs == 0 || nrec > t->bt_nrecs)
+			return (RET_SPECIAL);
+	}
+
+	if ((e = __rec_search(t, nrec - 1, SEARCH)) == NULL)
+		return (RET_ERROR);
+
+	F_SET(&t->bt_cursor, CURS_INIT);
+	t->bt_cursor.rcursor = nrec;
+
+	status = __rec_ret(t, e, nrec, key, data);
+	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/db/recno/rec_utils.c b/db/recno/rec_utils.c
new file mode 100644
index 0000000000..baea3fad50
--- /dev/null
+++ b/db/recno/rec_utils.c
@@ -0,0 +1,122 @@
+/*-
+ * 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[] = "@(#)rec_utils.c	8.6 (Berkeley) 7/16/94";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/param.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <db.h>
+#include "recno.h"
+
+/*
+ * __rec_ret --
+ *	Build return data.
+ *
+ * Parameters:
+ *	t:	tree
+ *	e:	key/data pair to be returned
+ *   nrec:	record number
+ *    key:	user's key structure
+ *	data:	user's data structure
+ *
+ * Returns:
+ *	RET_SUCCESS, RET_ERROR.
+ */
+int
+__rec_ret(t, e, nrec, key, data)
+	BTREE *t;
+	EPG *e;
+	recno_t nrec;
+	DBT *key, *data;
+{
+	RLEAF *rl;
+	void *p;
+
+	if (key == NULL)
+		goto dataonly;
+
+	/* We have to copy the key, it's not on the page. */
+	if (sizeof(recno_t) > t->bt_rkey.size) {
+		p = (void *)(t->bt_rkey.data == NULL ?
+		    malloc(sizeof(recno_t)) :
+		    realloc(t->bt_rkey.data, sizeof(recno_t)));
+		if (p == NULL)
+			return (RET_ERROR);
+		t->bt_rkey.data = p;
+		t->bt_rkey.size = sizeof(recno_t);
+	}
+	memmove(t->bt_rkey.data, &nrec, sizeof(recno_t));
+	key->size = sizeof(recno_t);
+	key->data = t->bt_rkey.data;
+
+dataonly:
+	if (data == NULL)
+		return (RET_SUCCESS);
+
+	/*
+	 * We must copy big keys/data to make them contigous.  Otherwise,
+	 * leave the page pinned and don't copy unless the user specified
+	 * concurrent access.
+	 */
+	rl = GETRLEAF(e->page, e->index);
+	if (rl->flags & P_BIGDATA) {
+		if (__ovfl_get(t, rl->bytes,
+		    &data->size, &t->bt_rdata.data, &t->bt_rdata.size))
+			return (RET_ERROR);
+		data->data = t->bt_rdata.data;
+	} else if (F_ISSET(t, B_DB_LOCK)) {
+		/* Use +1 in case the first record retrieved is 0 length. */
+		if (rl->dsize + 1 > t->bt_rdata.size) {
+			p = (void *)(t->bt_rdata.data == NULL ?
+			    malloc(rl->dsize + 1) :
+			    realloc(t->bt_rdata.data, rl->dsize + 1));
+			if (p == NULL)
+				return (RET_ERROR);
+			t->bt_rdata.data = p;
+			t->bt_rdata.size = rl->dsize + 1;
+		}
+		memmove(t->bt_rdata.data, rl->bytes, rl->dsize);
+		data->size = rl->dsize;
+		data->data = t->bt_rdata.data;
+	} else {
+		data->size = rl->dsize;
+		data->data = rl->bytes;
+	}
+	return (RET_SUCCESS);
+}
diff --git a/db/recno/recno.h b/db/recno/recno.h
new file mode 100644
index 0000000000..bec772c2fa
--- /dev/null
+++ b/db/recno/recno.h
@@ -0,0 +1,39 @@
+/*-
+ * Copyright (c) 1991, 1993
+ *	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.
+ *
+ *	@(#)recno.h	8.1 (Berkeley) 6/4/93
+ */
+
+enum SRCHOP { SDELETE, SINSERT, SEARCH};	/* Rec_search operation. */
+
+#include "../btree/btree.h"
+#include "extern.h"