db release 1.85

55 files changed, 2862 insertions, 1741 deletions

diff --git a/include/mpool.h b/include/mpool.h
index 849729759b3..622d2c9a377 100644
--- a/include/mpool.h
+++ b/include/mpool.h
@@ -1,7 +1,7 @@
-/*	$NetBSD: mpool.h,v 1.6 1994/10/26 00:56:07 cgd Exp $	*/
+/*	$NetBSD: mpool.h,v 1.7 1996/05/03 21:13:41 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1991, 1993
+ * 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
@@ -32,98 +32,62 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- *	@(#)mpool.h	8.1 (Berkeley) 6/2/93
+ *	@(#)mpool.h	8.2 (Berkeley) 7/14/94
  */
 
+#include <sys/queue.h>
+
 /*
- * The memory pool scheme is a simple one.  Each in memory page is referenced
- * by a bucket which is threaded in three ways.  All active pages are threaded
- * on a hash chain (hashed by the page number) and an lru chain.  Inactive
- * pages are threaded on a free chain.  Each reference to a memory pool is
- * handed an MPOOL which is the opaque cookie passed to all of the memory
- * routines.
+ * The memory pool scheme is a simple one.  Each in-memory page is referenced
+ * by a bucket which is threaded in up to two of three ways.  All active pages
+ * are threaded on a hash chain (hashed by page number) and an lru chain.
+ * Inactive pages are threaded on a free chain.  Each reference to a memory
+ * pool is handed an opaque MPOOL cookie which stores all of this information.
  */
 #define	HASHSIZE	128
 #define	HASHKEY(pgno)	((pgno - 1) % HASHSIZE)
 
-/* The BKT structures are the elements of the lists. */
-typedef struct BKT {
-	struct BKT	*hnext;		/* next hash bucket */
-	struct BKT	*hprev;		/* previous hash bucket */
-	struct BKT	*cnext;		/* next free/lru bucket */
-	struct BKT	*cprev;		/* previous free/lru bucket */
-	void		*page;		/* page */
-	pgno_t		pgno;		/* page number */
+/* The BKT structures are the elements of the queues. */
+typedef struct _bkt {
+	CIRCLEQ_ENTRY(_bkt) hq;		/* hash queue */
+	CIRCLEQ_ENTRY(_bkt) q;		/* lru queue */
+	void    *page;			/* page */
+	pgno_t   pgno;			/* page number */
 
 #define	MPOOL_DIRTY	0x01		/* page needs to be written */
 #define	MPOOL_PINNED	0x02		/* page is pinned into memory */
-	unsigned long	flags;		/* flags */
+	u_int8_t flags;			/* flags */
 } BKT;
 
-/* The BKTHDR structures are the heads of the lists. */
-typedef struct BKTHDR {
-	struct BKT	*hnext;		/* next hash bucket */
-	struct BKT	*hprev;		/* previous hash bucket */
-	struct BKT	*cnext;		/* next free/lru bucket */
-	struct BKT	*cprev;		/* previous free/lru bucket */
-} BKTHDR;
-
 typedef struct MPOOL {
-	BKTHDR	free;			/* The free list. */
-	BKTHDR	lru;			/* The LRU list. */
-	BKTHDR	hashtable[HASHSIZE];	/* Hashed list by page number. */
-	pgno_t	curcache;		/* Current number of cached pages. */
-	pgno_t	maxcache;		/* Max number of cached pages. */
-	pgno_t	npages;			/* Number of pages in the file. */
-	u_long	pagesize;		/* File page size. */
-	int	fd;			/* File descriptor. */
-					/* Page in conversion routine. */
+	CIRCLEQ_HEAD(_lqh, _bkt) lqh;	/* lru queue head */
+					/* hash queue array */
+	CIRCLEQ_HEAD(_hqh, _bkt) hqh[HASHSIZE];
+	pgno_t	curcache;		/* current number of cached pages */
+	pgno_t	maxcache;		/* max number of cached pages */
+	pgno_t	npages;			/* number of pages in the file */
+	u_long	pagesize;		/* file page size */
+	int	fd;			/* file descriptor */
+					/* page in conversion routine */
 	void    (*pgin) __P((void *, pgno_t, void *));
-					/* Page out conversion routine. */
+					/* page out conversion routine */
 	void    (*pgout) __P((void *, pgno_t, void *));
-	void	*pgcookie;		/* Cookie for page in/out routines. */
+	void	*pgcookie;		/* cookie for page in/out routines */
 #ifdef STATISTICS
-	unsigned long	cachehit;
-	unsigned long	cachemiss;
-	unsigned long	pagealloc;
-	unsigned long	pageflush;
-	unsigned long	pageget;
-	unsigned long	pagenew;
-	unsigned long	pageput;
-	unsigned long	pageread;
-	unsigned long	pagewrite;
+	u_long	cachehit;
+	u_long	cachemiss;
+	u_long	pagealloc;
+	u_long	pageflush;
+	u_long	pageget;
+	u_long	pagenew;
+	u_long	pageput;
+	u_long	pageread;
+	u_long	pagewrite;
 #endif
 } MPOOL;
 
-#ifdef __MPOOLINTERFACE_PRIVATE
-/* Macros to insert/delete into/from hash chain. */
-#define rmhash(bp) { \
-        (bp)->hprev->hnext = (bp)->hnext; \
-        (bp)->hnext->hprev = (bp)->hprev; \
-}
-#define inshash(bp, pg) { \
-	hp = &mp->hashtable[HASHKEY(pg)]; \
-        (bp)->hnext = hp->hnext; \
-        (bp)->hprev = (struct BKT *)hp; \
-        hp->hnext->hprev = (bp); \
-        hp->hnext = (bp); \
-}
-
-/* Macros to insert/delete into/from lru and free chains. */
-#define	rmchain(bp) { \
-        (bp)->cprev->cnext = (bp)->cnext; \
-        (bp)->cnext->cprev = (bp)->cprev; \
-}
-#define inschain(bp, dp) { \
-        (bp)->cnext = (dp)->cnext; \
-        (bp)->cprev = (struct BKT *)(dp); \
-        (dp)->cnext->cprev = (bp); \
-        (dp)->cnext = (bp); \
-}
-#endif
-
 __BEGIN_DECLS
-MPOOL	*mpool_open __P((DBT *, int, pgno_t, pgno_t));
+MPOOL	*mpool_open __P((void *, int, pgno_t, pgno_t));
 void	 mpool_filter __P((MPOOL *, void (*)(void *, pgno_t, void *),
 	    void (*)(void *, pgno_t, void *), void *));
 void	*mpool_new __P((MPOOL *, pgno_t *));
diff --git a/lib/libc/db/README b/lib/libc/db/README
index df1be282063..d06cdf14fc7 100644
--- a/lib/libc/db/README
+++ b/lib/libc/db/README
@@ -1,2 +1,41 @@
-$NetBSD: README,v 1.2 1995/02/27 13:19:30 cgd Exp $
-(was symlink to VERSION.  -- cgd)
+#	$NetBSD: README,v 1.3 1996/05/03 21:17:07 cgd Exp $
+#	@(#)README	8.27 (Berkeley) 9/1/94
+
+This is version 1.85 of the Berkeley DB code.
+
+For information on compiling and installing this software, see the file
+PORT/README.
+
+Newer versions of this software will periodically be made available by
+anonymous ftp from ftp.cs.berkeley.edu.  An archive in compressed format
+is in ucb/4bsd/db.tar.Z, or in gzip format in ucb/4bsd/db.tar.gz.  If
+you'd like to receive announcements of future releases of this software,
+send email to the contact address below.
+
+Email questions may be addressed to Keith Bostic at bostic@cs.berkeley.edu.
+
+============================================
+Distribution contents:
+
+Makefile.inc	Ignore this, it's the 4.4BSD subsystem Makefile.
+PORT		The per OS/architecture directories to use to build
+		libdb.a, if you're not running 4.4BSD.  See the file
+		PORT/README for more information.
+README		This file.
+btree		The B+tree routines.
+changelog	List of changes, per version.
+db		The dbopen(3) interface routine.
+docs		Various USENIX papers, and the formatted manual pages.
+hash		The extended linear hashing routines.
+man		The unformatted manual pages.
+mpool		The memory pool routines.
+recno		The fixed/variable length record routines.
+test		Test package.
+
+============================================
+Debugging:
+
+If you're running a memory checker (e.g. Purify) on DB, make sure that
+you recompile it with "-DPURIFY" in the CFLAGS, first.  By default,
+allocated pages are not initialized by the DB code, and they will show
+up as reads of uninitialized memory in the buffer write routines.
diff --git a/lib/libc/db/VERSION b/lib/libc/db/VERSION
index 440b71bad09..e69de29bb2d 100644
--- a/lib/libc/db/VERSION
+++ b/lib/libc/db/VERSION
@@ -1,113 +0,0 @@
-#	$NetBSD: VERSION,v 1.7 1995/02/27 13:19:33 cgd Exp $
-#	@(#)VERSION	8.17 (Berkeley) 6/20/94
-
-This is version 1.79 of the Berkeley DB code.
-
-For information on compiling and installing this software, see the file
-PORT/README.
-
-If your version of the DB code doesn't have a copy of this version file,
-it's really old, please update it!
-
-Newer versions of this software will periodically be made available by
-anonymous ftp from ftp.cs.berkeley.edu.  An archive in compressed format
-is in ucb/4bsd/db.tar.Z, or in gzip format in ucb/4bsd/db.tar.gz.  If
-you'd like to receive announcements of future releases of this software,
-send email to the contact address below.
-
-Email questions may be addressed to Keith Bostic at bostic@cs.berkeley.edu.
-
-============================================
-Distribution contents:
-
-Makefile.inc	Ignore this, it's the 4.4BSD subsystem Makefile.
-PORT		The per OS/architecture directories to use to build
-		libdb.a, if you're not running 4.4BSD.  See the file
-		PORT/README for more information.
-README		This file.
-VERSION		This file.
-btree		B+tree routines.
-db		Dbopen(3) interface routine.
-doc		USENIX papers, formatted manual pages.
-hash		Extended linear hashing routines.
-man		Unformatted manual pages.
-mpool		Memory pool routines.
-recno		Fixed/variable length record routines.
-test		Test package.
-
-============================================
-1.78 -> 1.79	Mon Jun 20 17:36:47 EDT 1994
-	all:	Minor cleanups of 1.78 for porting reasons; only
-		major change was inlining check of NULL pointer
-		so that __fix_realloc goes away.
-
-1.77 -> 1.78	Thu Jun 16 19:06:43 EDT 1994
-	all:	Move "standard" size typedef's into db.h.
-
-1.76 -> 1.77	Thu Jun 16 16:48:38 EDT 1994
-	hash:	Delete __init_ routine, has special meaning to OSF 2.0.
-
-1.74 -> 1.76
-	all:	Finish up the port to the Alpha.
-
-1.73 -> 1.74
-	recno:	Don't put the record if rec_search fails, in rec_rdelete.
-		Create fixed-length intermediate records past "end" of DB
-		correctly.
-		Realloc bug when reading in fixed records.
-	all:	First cut at port to Alpha (64-bit architecture) using
-		4.4BSD basic integral types typedef's.
-		Cast allocation pointers to shut up old compilers.
-		Rework PORT directory into OS/machine directories.
-
-1.72 -> 1.73
-	btree:	If enough duplicate records were inserted and then deleted
-		that internal pages had references to empty pages of the
-		duplicate keys, the search function ended up on the wrong
-		page.
-
-1.7  -> 1.72	12 Oct 1993
-	hash:	Support NET/2 hash formats.
-
-1.7  -> 1.71	16 Sep 1993
-	btree/recno:
-		Fix bug in internal search routines that caused
-		return of invalid pointers.
-
-1.6  -> 1.7	07 Sep 1993
-	hash:	Fixed big key overflow bugs.
-	test:	Portability hacks, rewrite test script, Makefile.
-	btree/recno:
-		Stop copying non-overflow key/data pairs.
-	PORT:	Break PORT directory up into per architecture/OS
-		subdirectories.
-
-1.5  -> 1.6	06 Jun 1993
-	hash:	In PAIRFITS, the first comparison should look at (P)[2].
-		The hash_realloc function was walking off the end of memory.
-		The overflow page number was wrong when bumping splitpoint.
-
-1.4  -> 1.5	23 May 1993
-	hash:	Set hash default fill factor dynamically.
-	recno:	Fixed bug in sorted page splits.
-		Add page size parameter support.
-		Allow recno to specify the name of the underlying btree;
-			used for vi recovery.
-	btree/recno:
-		Support 64K pages.
-	btree/hash/recno:
-		Provide access to an underlying file descriptor.
-		Change sync routines to take a flag argument, recno
-			uses this to sync out the underlying btree.
-
-1.3  -> 1.4	10 May 1993
-	recno:	Delete the R_CURSORLOG flag from the recno interface.
-		Zero-length record fix for non-mmap reads.
-		Try and make SIZE_T_MAX test in open portable.
-
-1.2  -> 1.3	01 May 1993
-	btree:	Ignore user byte-order setting when reading already
-		existing database.  Fixes to byte-order conversions.
-
-1.1  -> 1.2	15 Apr 1993
-		No bug fixes, only compatibility hacks.
diff --git a/lib/libc/db/btree/Makefile.inc b/lib/libc/db/btree/Makefile.inc
index d187103e2d3..46fbb029e39 100644
--- a/lib/libc/db/btree/Makefile.inc
+++ b/lib/libc/db/btree/Makefile.inc
@@ -1,8 +1,8 @@
-#	$NetBSD: Makefile.inc,v 1.5 1995/02/27 13:19:53 cgd Exp $
-#	@(#)Makefile.inc	8.1 (Berkeley) 6/4/93
+#	$NetBSD: Makefile.inc,v 1.6 1996/05/03 21:50:36 cgd Exp $
+#	@(#)Makefile.inc	8.2 (Berkeley) 7/14/94
 
 .PATH: ${.CURDIR}/db/btree
 
 SRCS+=	bt_close.c bt_conv.c bt_debug.c bt_delete.c bt_get.c bt_open.c \
 	bt_overflow.c bt_page.c bt_put.c bt_search.c bt_seq.c bt_split.c \
-	bt_stack.c bt_utils.c
+	bt_utils.c
diff --git a/lib/libc/db/btree/bt_close.c b/lib/libc/db/btree/bt_close.c
index 2b27327f7ed..b18c278602e 100644
--- a/lib/libc/db/btree/bt_close.c
+++ b/lib/libc/db/btree/bt_close.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: bt_close.c,v 1.6 1995/02/27 13:19:59 cgd Exp $	*/
+/*	$NetBSD: bt_close.c,v 1.7 1996/05/03 21:50:38 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1990, 1993
+ * 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
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_close.c	8.3 (Berkeley) 2/21/94";
+static char sccsid[] = "@(#)bt_close.c	8.7 (Berkeley) 8/17/94";
 #else
-static char rcsid[] = "$NetBSD: bt_close.c,v 1.6 1995/02/27 13:19:59 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_close.c,v 1.7 1996/05/03 21:50:38 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -81,25 +81,30 @@ __bt_close(dbp)
 		t->bt_pinned = NULL;
 	}
 
-	/*
-	 * Delete any already deleted record that we've been saving
-	 * because the cursor pointed to it.
-	 */
-	if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor))
-		return (RET_ERROR);
-
+	/* 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);
 
-	if (t->bt_stack)
-		free(t->bt_stack);
-	if (t->bt_kbuf)
-		free(t->bt_kbuf);
-	if (t->bt_dbuf)
-		free(t->bt_dbuf);
+	/* 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);
@@ -123,8 +128,6 @@ __bt_sync(dbp, flags)
 {
 	BTREE *t;
 	int status;
-	PAGE *h;
-	void *p;
 
 	t = dbp->internal;
 
@@ -140,40 +143,15 @@ __bt_sync(dbp, flags)
 		return (RET_ERROR);
 	}
 
-	if (ISSET(t, B_INMEM | B_RDONLY) || !ISSET(t, B_MODIFIED))
+	if (F_ISSET(t, B_INMEM | B_RDONLY) || !F_ISSET(t, B_MODIFIED))
 		return (RET_SUCCESS);
 
-	if (ISSET(t, B_METADIRTY) && bt_meta(t) == RET_ERROR)
+	if (F_ISSET(t, B_METADIRTY) && bt_meta(t) == RET_ERROR)
 		return (RET_ERROR);
 
-	/*
-	 * Nastiness.  If the cursor has been marked for deletion, but not
-	 * actually deleted, we have to make a copy of the page, delete the
-	 * key/data item, sync the file, and then restore the original page
-	 * contents.
-	 */
-	if (ISSET(t, B_DELCRSR)) {
-		if ((p = (void *)malloc(t->bt_psize)) == NULL)
-			return (RET_ERROR);
-		if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL)
-			return (RET_ERROR);
-		memmove(p, h, t->bt_psize);
-		if ((status =
-		    __bt_dleaf(t, h, t->bt_bcursor.index)) == RET_ERROR)
-			goto ecrsr;
-		mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-	}
-		
 	if ((status = mpool_sync(t->bt_mp)) == RET_SUCCESS)
-		CLR(t, B_MODIFIED);
-
-ecrsr:	if (ISSET(t, B_DELCRSR)) {
-		if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL)
-			return (RET_ERROR);
-		memmove(h, p, t->bt_psize);
-		free(p);
-		mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-	}
+		F_CLR(t, B_MODIFIED);
+
 	return (status);
 }
 
@@ -197,12 +175,12 @@ bt_meta(t)
 		return (RET_ERROR);
 
 	/* Fill in metadata. */
-	m.m_magic = BTREEMAGIC;
-	m.m_version = BTREEVERSION;
-	m.m_psize = t->bt_psize;
-	m.m_free = t->bt_free;
-	m.m_nrecs = t->bt_nrecs;
-	m.m_flags = t->bt_flags & SAVEMETA;
+	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);
diff --git a/lib/libc/db/btree/bt_conv.c b/lib/libc/db/btree/bt_conv.c
index 1d513865455..27ab66c0752 100644
--- a/lib/libc/db/btree/bt_conv.c
+++ b/lib/libc/db/btree/bt_conv.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: bt_conv.c,v 1.5 1995/02/27 13:20:04 cgd Exp $	*/
+/*	$NetBSD: bt_conv.c,v 1.6 1996/05/03 21:50:39 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_conv.c	8.3 (Berkeley) 5/31/94";
+static char sccsid[] = "@(#)bt_conv.c	8.5 (Berkeley) 8/17/94";
 #else
-static char rcsid[] = "$NetBSD: bt_conv.c,v 1.5 1995/02/27 13:20:04 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_conv.c,v 1.6 1996/05/03 21:50:39 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -74,7 +74,7 @@ __bt_pgin(t, pg, pp)
 	u_char flags;
 	char *p;
 
-	if (!ISSET(((BTREE *)t), B_NEEDSWAP))
+	if (!F_ISSET(((BTREE *)t), B_NEEDSWAP))
 		return;
 	if (pg == P_META) {
 		mswap(pp);
@@ -142,7 +142,7 @@ __bt_pgout(t, pg, pp)
 	u_char flags;
 	char *p;
 
-	if (!ISSET(((BTREE *)t), B_NEEDSWAP))
+	if (!F_ISSET(((BTREE *)t), B_NEEDSWAP))
 		return;
 	if (pg == P_META) {
 		mswap(pp);
@@ -212,16 +212,16 @@ mswap(pg)
 	char *p;
 
 	p = (char *)pg;
-	P_32_SWAP(p);		/* m_magic */
+	P_32_SWAP(p);		/* magic */
 	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* m_version */
+	P_32_SWAP(p);		/* version */
 	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* m_psize */
+	P_32_SWAP(p);		/* psize */
 	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* m_free */
+	P_32_SWAP(p);		/* free */
 	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* m_nrecs */
+	P_32_SWAP(p);		/* nrecs */
 	p += sizeof(u_int32_t);
-	P_32_SWAP(p);		/* m_flags */
+	P_32_SWAP(p);		/* flags */
 	p += sizeof(u_int32_t);
 }
diff --git a/lib/libc/db/btree/bt_debug.c b/lib/libc/db/btree/bt_debug.c
index fb967122aaa..7b80328b952 100644
--- a/lib/libc/db/btree/bt_debug.c
+++ b/lib/libc/db/btree/bt_debug.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: bt_debug.c,v 1.5 1995/02/27 13:20:12 cgd Exp $	*/
+/*	$NetBSD: bt_debug.c,v 1.6 1996/05/03 21:50:41 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_debug.c	8.3 (Berkeley) 5/31/94";
+static char sccsid[] = "@(#)bt_debug.c	8.5 (Berkeley) 8/17/94";
 #else
-static char rcsid[] = "$NetBSD: bt_debug.c,v 1.5 1995/02/27 13:20:12 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_debug.c,v 1.6 1996/05/03 21:50:41 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -71,24 +71,22 @@ __bt_dump(dbp)
 
 	t = dbp->internal;
 	(void)fprintf(stderr, "%s: pgsz %d",
-	    ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize);
-	if (ISSET(t, R_RECNO))
+	    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 (ISSET(t, flag)) { \
+	if (F_ISSET(t, flag)) { \
 		(void)fprintf(stderr, "%s%s", sep, name); \
 		sep = ", "; \
 	}
-	if (t->bt_flags) {
+	if (t->flags != 0) {
 		sep = " flags (";
-		X(B_DELCRSR,	"DELCRSR");
 		X(R_FIXLEN,	"FIXLEN");
 		X(B_INMEM,	"INMEM");
 		X(B_NODUPS,	"NODUPS");
 		X(B_RDONLY,	"RDONLY");
 		X(R_RECNO,	"RECNO");
-		X(B_SEQINIT,	"SEQINIT");
 		X(B_METADIRTY,"METADIRTY");
 		(void)fprintf(stderr, ")\n");
 	}
@@ -114,19 +112,19 @@ __bt_dmpage(h)
 	char *sep;
 
 	m = (BTMETA *)h;
-	(void)fprintf(stderr, "magic %lx\n", m->m_magic);
-	(void)fprintf(stderr, "version %lu\n", m->m_version);
-	(void)fprintf(stderr, "psize %lu\n", m->m_psize);
-	(void)fprintf(stderr, "free %lu\n", m->m_free);
-	(void)fprintf(stderr, "nrecs %lu\n", m->m_nrecs);
-	(void)fprintf(stderr, "flags %lu", m->m_flags);
+	(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->m_flags & flag) { \
+	if (m->flags & flag) { \
 		(void)fprintf(stderr, "%s%s", sep, name); \
 		sep = ", "; \
 	}
-	if (m->m_flags) {
+	if (m->flags) {
 		sep = " (";
 		X(B_NODUPS,	"NODUPS");
 		X(R_RECNO,	"RECNO");
@@ -198,7 +196,7 @@ __bt_dpage(h)
 	    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) {
+		switch (h->flags & P_TYPE) {
 		case P_BINTERNAL:
 			bi = GETBINTERNAL(h, cur);
 			(void)fprintf(stderr,
@@ -273,7 +271,7 @@ __bt_stat(dbp)
 	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) {
+		switch (h->flags & P_TYPE) {
 		case P_BINTERNAL:
 		case P_RINTERNAL:
 			++pinternal;
@@ -301,7 +299,7 @@ __bt_stat(dbp)
 			(void)mpool_put(t->bt_mp, h, 0);
 			break;
 		}
-		i = ISSET(t, R_RECNO) ?
+		i = F_ISSET(t, R_RECNO) ?
 		    GETRINTERNAL(h, 0)->pgno :
 		    GETBINTERNAL(h, 0)->pgno;
 		(void)mpool_put(t->bt_mp, h, 0);
@@ -309,7 +307,7 @@ __bt_stat(dbp)
 
 	(void)fprintf(stderr, "%d level%s with %ld keys",
 	    levels, levels == 1 ? "" : "s", nkeys);
-	if (ISSET(t, R_RECNO))
+	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",
diff --git a/lib/libc/db/btree/bt_delete.c b/lib/libc/db/btree/bt_delete.c
index e5ced2bc5c9..32efd2529fb 100644
--- a/lib/libc/db/btree/bt_delete.c
+++ b/lib/libc/db/btree/bt_delete.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: bt_delete.c,v 1.6 1995/02/27 13:20:16 cgd Exp $	*/
+/*	$NetBSD: bt_delete.c,v 1.7 1996/05/03 21:50:44 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_delete.c	8.4 (Berkeley) 5/31/94";
+static char sccsid[] = "@(#)bt_delete.c	8.13 (Berkeley) 7/28/94";
 #else
-static char rcsid[] = "$NetBSD: bt_delete.c,v 1.6 1995/02/27 13:20:16 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_delete.c,v 1.7 1996/05/03 21:50:44 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -53,18 +53,17 @@ static char rcsid[] = "$NetBSD: bt_delete.c,v 1.6 1995/02/27 13:20:16 cgd Exp $"
 #include <db.h>
 #include "btree.h"
 
-static int bt_bdelete __P((BTREE *, const DBT *));
+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.
+ * __bt_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.
+ * Return RET_SPECIAL if the key is not found.
  */
 int
 __bt_delete(dbp, key, flags)
@@ -73,6 +72,8 @@ __bt_delete(dbp, key, flags)
 	u_int flags;
 {
 	BTREE *t;
+	CURSOR *c;
+	PAGE *h;
 	int status;
 
 	t = dbp->internal;
@@ -83,242 +84,433 @@ __bt_delete(dbp, key, flags)
 		t->bt_pinned = NULL;
 	}
 
-	if (ISSET(t, B_RDONLY)) {
+	/* Check for change to a read-only tree. */
+	if (F_ISSET(t, B_RDONLY)) {
 		errno = EPERM;
 		return (RET_ERROR);
 	}
 
-	switch(flags) {
+	switch (flags) {
 	case 0:
-		status = bt_bdelete(t, key);
+		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 the record.  For
-		 * the delete cursor bit to have been set requires that the
-		 * scan be initialized, so no reason to check.
+		 * If flags is R_CURSOR, delete the cursor.  Must already
+		 * have started a scan and not have already deleted it.
 		 */
-		if (!ISSET(t, B_SEQINIT))
-                        goto einval;
-		status = ISSET(t, B_DELCRSR) ?
-		    RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor);
-		break;
+		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:
-einval:		errno = EINVAL;
+		errno = EINVAL;
 		return (RET_ERROR);
 	}
 	if (status == RET_SUCCESS)
-		SET(t, B_MODIFIED);
+		F_SET(t, B_MODIFIED);
 	return (status);
 }
 
 /*
- * BT_BDELETE -- Delete all key/data pairs matching the specified key.
+ * __bt_stkacq --
+ *	Acquire a stack so we can delete a cursor entry.
  *
  * Parameters:
- *	tree:	tree
+ *	  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 index;
+	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) {
+				index = parent->index + 1;
+				BT_PUSH(t, h->pgno, index);
+				break;
+			}
+			mpool_put(t->bt_mp, h, 0);
+		}
+
+		/* Restore the stack. */
+		while (level--) {
+			/* Push the next level down onto the stack. */
+			bi = GETBINTERNAL(h, index);
+			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);
+			index = 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) {
+				index = parent->index - 1;
+				BT_PUSH(t, h->pgno, index);
+				break;
+			}
+			mpool_put(t->bt_mp, h, 0);
+		}
+
+		/* Restore the stack. */
+		while (level--) {
+			/* Push the next level down onto the stack. */
+			bi = GETBINTERNAL(h, index);
+			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);
+
+			index = NEXTINDEX(h) - 1;
+			BT_PUSH(t, pgno, index);
+		}
+		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)
+__bt_bdelete(t, key)
 	BTREE *t;
 	const DBT *key;
 {
-	EPG *e, save;
+	EPG *e;
 	PAGE *h;
-	pgno_t cpgno, pg;
-	indx_t cindex;
-	int deleted, dirty1, dirty2, exact;
+	int deleted, exact, redo;
+
+	deleted = 0;
 
 	/* Find any matching record; __bt_search pins the page. */
-	if ((e = __bt_search(t, key, &exact)) == NULL)
-		return (RET_ERROR);
+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 (RET_SPECIAL);
+		return (deleted ? RET_SUCCESS : RET_SPECIAL);
 	}
 
 	/*
-	 * Delete forward, then delete backward, from the found key.  The
-	 * ordering is so that the deletions don't mess up the page refs.
-	 * The first loop deletes the key from the original page, the second
-	 * unpins the original page.  In the first loop, dirty1 is set if
-	 * the original page is modified, and dirty2 is set if any subsequent
-	 * pages are modified.  In the second loop, dirty1 starts off set if
-	 * the original page has been modified, and is set if any subsequent
-	 * pages are modified.
-	 *
-	 * If find the key referenced by the cursor, don't delete it, just
-	 * flag it for future deletion.  The cursor page number is P_INVALID
-	 * unless the sequential scan is initialized, so no reason to check.
-	 * A special case is when the already deleted cursor record was the
-	 * only record found.  If so, then the delete opertion fails as no
-	 * records were deleted.
-	 *
-	 * Cycle in place in the current page until the current record doesn't
-	 * match the key or the page is empty.  If the latter, walk forward,
-	 * skipping empty pages and repeating until a record doesn't match
-	 * the key or the end of the tree is reached.
+	 * 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.
 	 */
-	cpgno = t->bt_bcursor.pgno;
-	cindex = t->bt_bcursor.index;
-	save = *e;
-	dirty1 = 0;
-	for (h = e->page, deleted = 0;;) {
-		dirty2 = 0;
-		do {
-			if (h->pgno == cpgno && e->index == cindex) {
-				if (!ISSET(t, B_DELCRSR)) {
-					SET(t, B_DELCRSR);
-					deleted = 1;
-				}
-				++e->index;
-			} else {
-				if (__bt_dleaf(t, h, e->index)) {
-					if (h->pgno != save.page->pgno)
-						mpool_put(t->bt_mp, h, dirty2);
-					mpool_put(t->bt_mp, save.page, dirty1);
+	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);
-				}
-				if (h->pgno == save.page->pgno)
-					dirty1 = MPOOL_DIRTY;
-				else
-					dirty2 = MPOOL_DIRTY;
-				deleted = 1;
-			}
-		} while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
-
-		/*
-		 * Quit if didn't find a match, no next page, or first key on
-		 * the next page doesn't match.  Don't unpin the original page
-		 * unless an error occurs.
-		 */
-		if (e->index < NEXTINDEX(h))
-			break;
-		for (;;) {
-			if ((pg = h->nextpg) == P_INVALID)
-				goto done1;
-			if (h->pgno != save.page->pgno)
-				mpool_put(t->bt_mp, h, dirty2);
-			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) {
-				mpool_put(t->bt_mp, save.page, dirty1);
-				return (RET_ERROR);
-			}
-			if (NEXTINDEX(h) != 0) {
-				e->page = h;
-				e->index = 0;
-				break;
-			}
+			} 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;
 	}
 
-	/*
-	 * Reach here with the original page and the last page referenced
-	 * pinned (they may be the same).  Release it if not the original.
-	 */
-done1:	if (h->pgno != save.page->pgno)
-		mpool_put(t->bt_mp, h, dirty2);
+	/* 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, index, *ip, offset;
+	u_int32_t nksize;
+	char *from;
 
 	/*
-	 * Walk backwards from the record previous to the record returned by
-	 * __bt_search, skipping empty pages, until a record doesn't match
-	 * the key or reach the beginning of the tree.
+	 * 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.
 	 */
-	*e = save;
-	for (;;) {
-		if (e->index)
-			--e->index;
-		for (h = e->page; e->index; --e->index) {
-			if (__bt_cmp(t, key, e) != 0)
-				goto done2;
-			if (h->pgno == cpgno && e->index == cindex) {
-				if (!ISSET(t, B_DELCRSR)) {
-					SET(t, B_DELCRSR);
-					deleted = 1;
-				}
+	while ((parent = BT_POP(t)) != NULL) {
+		/* Get the parent page. */
+		if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
+			return (RET_ERROR);
+		
+		index = parent->index;
+		bi = GETBINTERNAL(pg, index);
+
+		/* 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_dleaf(t, h, e->index) == RET_ERROR) {
-					mpool_put(t->bt_mp, h, dirty1);
+				if (__bt_relink(t, pg) || __bt_free(t, pg))
 					return (RET_ERROR);
-				}
-				if (h->pgno == save.page->pgno)
-					dirty1 = MPOOL_DIRTY;
-				deleted = 1;
+				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[index];
+			for (cnt = index, ip = &pg->linp[0]; cnt--; ++ip)
+				if (ip[0] < offset)
+					ip[0] += nksize;
+			for (cnt = NEXTINDEX(pg) - index; --cnt; ++ip)
+				ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1];
+			pg->lower -= sizeof(indx_t);
 		}
 
-		if ((pg = h->prevpg) == P_INVALID)
-			goto done2;
-		mpool_put(t->bt_mp, h, dirty1);
-		dirty1 = 0;
-		if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL)
-			return (RET_ERROR);
-		e->index = NEXTINDEX(e->page);
+		mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
+		break;
 	}
 
-	/*
-	 * Reach here with the last page that was looked at pinned.  Release
-	 * it.
-	 */
-done2:	mpool_put(t->bt_mp, h, dirty1);
-	return (deleted ? RET_SUCCESS : RET_SPECIAL);
+	/* 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.
+ * __bt_dleaf --
+ *	Delete a single record from a leaf page.
  *
  * Parameters:
  *	t:	tree
- *	index:	index on current page to delete
+ *    key:	referenced key
+ *	h:	page
+ *	index:	index on page to delete
  *
  * Returns:
  *	RET_SUCCESS, RET_ERROR.
  */
 int
-__bt_dleaf(t, h, index)
+__bt_dleaf(t, key, h, index)
 	BTREE *t;
+	const DBT *key;
 	PAGE *h;
-	indx_t index;
+	u_int index;
 {
-	register BLEAF *bl;
-	register indx_t cnt, *ip, offset;
-	register u_int32_t nbytes;
-	char *from;
+	BLEAF *bl;
+	indx_t cnt, *ip, offset;
+	u_int32_t nbytes;
 	void *to;
+	char *from;
 
-	/*
-	 * Delete a record from a btree 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.
-	 */
+	/* 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 == index &&
+	    __bt_curdel(t, key, h, index))
+		return (RET_ERROR);
+
+	/* If the entry uses overflow pages, make them available for reuse. */
 	to = bl = GETBLEAF(h, index);
 	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);
-	nbytes = NBLEAF(bl);
 
-	/*
-	 * Compress the key/data pairs.  Compress and adjust the [BR]LEAF
-	 * offsets.  Reset the headers.
-	 */
+	/* 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[index];
 	for (cnt = index, ip = &h->linp[0]; cnt--; ++ip)
 		if (ip[0] < offset)
@@ -326,5 +518,146 @@ __bt_dleaf(t, h, index)
 	for (cnt = NEXTINDEX(h) - index; --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 > index)
+		--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, index)
+	BTREE *t;
+	const DBT *key;
+	PAGE *h;
+	u_int index;
+{
+	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 = index;
+			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 (index > 0) { 
+			e.page = h;
+			e.index = index - 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 (index < NEXTINDEX(h) - 1) {
+			e.page = h;
+			e.index = index + 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 (index == 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 (index == 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 = index;
+	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/lib/libc/db/btree/bt_get.c b/lib/libc/db/btree/bt_get.c
index 2adc73feb7a..18e3a37b6c0 100644
--- a/lib/libc/db/btree/bt_get.c
+++ b/lib/libc/db/btree/bt_get.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: bt_get.c,v 1.6 1995/02/27 13:20:22 cgd Exp $	*/
+/*	$NetBSD: bt_get.c,v 1.7 1996/05/03 21:50:45 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1990, 1993
+ * 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
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_get.c	8.2 (Berkeley) 9/7/93";
+static char sccsid[] = "@(#)bt_get.c	8.6 (Berkeley) 7/20/94";
 #else
-static char rcsid[] = "$NetBSD: bt_get.c,v 1.6 1995/02/27 13:20:22 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_get.c,v 1.7 1996/05/03 21:50:45 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -97,148 +97,15 @@ __bt_get(dbp, key, data, flags)
 		return (RET_SPECIAL);
 	}
 
-	/*
-	 * A special case is if we found the record but it's flagged for
-	 * deletion.  In this case, we want to find another record with the
-	 * same key, if it exists.  Rather than look around the tree we call
-	 * __bt_first and have it redo the search, as __bt_first will not
-	 * return keys marked for deletion.  Slow, but should never happen.
-	 */
-	if (ISSET(t, B_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno &&
-	    e->index == t->bt_bcursor.index) {
-		mpool_put(t->bt_mp, e->page, 0);
-		if ((e = __bt_first(t, key, &exact)) == NULL)
-			return (RET_ERROR);
-		if (!exact)
-			return (RET_SPECIAL);
-	}
+	status = __bt_ret(t, e, NULL, NULL, data, &t->bt_rdata, 0);
 
-	status = __bt_ret(t, e, NULL, data);
 	/*
 	 * If the user is doing concurrent access, we copied the
 	 * key/data, toss the page.
 	 */
-	if (ISSET(t, B_DB_LOCK))
+	if (F_ISSET(t, B_DB_LOCK))
 		mpool_put(t->bt_mp, e->page, 0);
 	else
 		t->bt_pinned = e->page;
 	return (status);
 }
-
-/*
- * __BT_FIRST -- Find the first entry.
- *
- * Parameters:
- *	t:	the tree
- *	key:	the key
- *
- * Returns:
- *	The first entry in the tree greater than or equal to key.
- */
-EPG *
-__bt_first(t, key, exactp)
-	BTREE *t;
-	const DBT *key;
-	int *exactp;
-{
-	register PAGE *h;
-	register EPG *e;
-	EPG save;
-	pgno_t cpgno, pg;
-	indx_t cindex;
-	int found;
-
-	/*
-	 * Find any matching record; __bt_search pins the page.  Only exact
-	 * matches are tricky, otherwise just return the location of the key
-	 * if it were to be inserted into the tree.
-	 */
-	if ((e = __bt_search(t, key, exactp)) == NULL)
-		return (NULL);
-	if (!*exactp)
-		return (e);
-
-	if (ISSET(t, B_DELCRSR)) {
-		cpgno = t->bt_bcursor.pgno;
-		cindex = t->bt_bcursor.index;
-	} else {
-		cpgno = P_INVALID;
-		cindex = 0;		/* GCC thinks it's uninitialized. */
-	}
-
-	/*
-	 * Walk backwards, skipping empty pages, 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.  A special case is that we don't return a match
-	 * on records that the cursor references that have already been flagged
-	 * for deletion.
-	 */
-	save = *e;
-	h = e->page;
-	found = 0;
-	do {
-		if (cpgno != h->pgno || cindex != e->index) {
-			if (save.page->pgno != e->page->pgno) {
-				mpool_put(t->bt_mp, save.page, 0);
-				save = *e;
-			} else
-				save.index = e->index;
-			found = 1;
-		}
-		/*
-		 * Make a special effort not to unpin the page the last (or
-		 * original) match was on, but also make sure it's unpinned
-		 * if an error occurs.
-		 */
-		while (e->index == 0) {
-			if (h->prevpg == P_INVALID)
-				goto done1;
-			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 (NULL);
-			}
-			e->page = h;
-			e->index = NEXTINDEX(h);
-		}
-		--e->index;
-	} while (__bt_cmp(t, key, e) == 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.
-	 */
-done1:	if (h->pgno != save.page->pgno)
-		mpool_put(t->bt_mp, h, 0);
-
-	/*
-	 * If still haven't found a record, the only possibility left is the
-	 * next one.  Move forward one slot, skipping empty pages and check.
-	 */
-	if (!found) {
-		h = save.page;
-		if (++save.index == NEXTINDEX(h)) {
-			do {
-				pg = h->nextpg;
-				mpool_put(t->bt_mp, h, 0);
-				if (pg == P_INVALID) {
-					*exactp = 0;
-					return (e);
-				}
-				if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-					return (NULL);
-			} while ((save.index = NEXTINDEX(h)) == 0);
-			save.page = h;
-		}
-		if (__bt_cmp(t, key, &save) != 0) {
-			*exactp = 0;
-			return (e);
-		}
-	}
-	*e = save;
-	*exactp = 1;
-	return (e);
-}
diff --git a/lib/libc/db/btree/bt_open.c b/lib/libc/db/btree/bt_open.c
index 63162702051..8339edea618 100644
--- a/lib/libc/db/btree/bt_open.c
+++ b/lib/libc/db/btree/bt_open.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: bt_open.c,v 1.7 1995/02/27 13:20:27 cgd Exp $	*/
+/*	$NetBSD: bt_open.c,v 1.8 1996/05/03 21:50:46 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_open.c	8.7 (Berkeley) 6/16/94";
+static char sccsid[] = "@(#)bt_open.c	8.10 (Berkeley) 8/17/94";
 #else
-static char rcsid[] = "$NetBSD: bt_open.c,v 1.7 1995/02/27 13:20:27 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_open.c,v 1.8 1996/05/03 21:50:46 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -67,6 +67,11 @@ static char rcsid[] = "$NetBSD: bt_open.c,v 1.7 1995/02/27 13:20:27 cgd Exp $";
 #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));
@@ -163,7 +168,6 @@ __bt_open(fname, flags, mode, openinfo, dflags)
 	if ((t = (BTREE *)malloc(sizeof(BTREE))) == NULL)
 		goto err;
 	memset(t, 0, sizeof(BTREE));
-	t->bt_bcursor.pgno = P_INVALID;
 	t->bt_fd = -1;			/* Don't close unopened fd on error. */
 	t->bt_lorder = b.lorder;
 	t->bt_order = NOT;
@@ -173,9 +177,9 @@ __bt_open(fname, flags, mode, openinfo, dflags)
 
 	if ((t->bt_dbp = dbp = (DB *)malloc(sizeof(DB))) == NULL)
 		goto err;
-	t->bt_flags = 0;
+	memset(t->bt_dbp, 0, sizeof(DB));
 	if (t->bt_lorder != machine_lorder)
-		SET(t, B_NEEDSWAP);
+		F_SET(t, B_NEEDSWAP);
 
 	dbp->type = DB_BTREE;
 	dbp->internal = t;
@@ -192,9 +196,9 @@ __bt_open(fname, flags, mode, openinfo, dflags)
 	 * open a backing temporary file.  Otherwise, it's a disk-based tree.
 	 */
 	if (fname) {
-		switch(flags & O_ACCMODE) {
+		switch (flags & O_ACCMODE) {
 		case O_RDONLY:
-			SET(t, B_RDONLY);
+			F_SET(t, B_RDONLY);
 			break;
 		case O_RDWR:
 			break;
@@ -211,7 +215,7 @@ __bt_open(fname, flags, mode, openinfo, dflags)
 			goto einval;
 		if ((t->bt_fd = tmp()) == -1)
 			goto err;
-		SET(t, B_INMEM);
+		F_SET(t, B_INMEM);
 	}
 
 	if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
@@ -233,28 +237,28 @@ __bt_open(fname, flags, mode, openinfo, dflags)
 		 * don't bother to return an error, we just clear the NEEDSWAP
 		 * bit.
 		 */
-		if (m.m_magic == BTREEMAGIC)
-			CLR(t, B_NEEDSWAP);
+		if (m.magic == BTREEMAGIC)
+			F_CLR(t, B_NEEDSWAP);
 		else {
-			SET(t, B_NEEDSWAP);
-			M_32_SWAP(m.m_magic);
-			M_32_SWAP(m.m_version);
-			M_32_SWAP(m.m_psize);
-			M_32_SWAP(m.m_free);
-			M_32_SWAP(m.m_nrecs);
-			M_32_SWAP(m.m_flags);
+			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.m_magic != BTREEMAGIC || m.m_version != BTREEVERSION)
+		if (m.magic != BTREEMAGIC || m.version != BTREEVERSION)
 			goto eftype;
-		if (m.m_psize < MINPSIZE || m.m_psize > MAX_PAGE_OFFSET + 1 ||
-		    m.m_psize & sizeof(indx_t) - 1)
+		if (m.psize < MINPSIZE || m.psize > MAX_PAGE_OFFSET + 1 ||
+		    m.psize & sizeof(indx_t) - 1)
 			goto eftype;
-		if (m.m_flags & ~SAVEMETA)
+		if (m.flags & ~SAVEMETA)
 			goto eftype;
-		b.psize = m.m_psize;
-		t->bt_flags |= m.m_flags;
-		t->bt_free = m.m_free;
-		t->bt_nrecs = m.m_nrecs;
+		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.
@@ -270,11 +274,11 @@ __bt_open(fname, flags, mode, openinfo, dflags)
 
 		/* Set flag if duplicates permitted. */
 		if (!(b.flags & R_DUP))
-			SET(t, B_NODUPS);
+			F_SET(t, B_NODUPS);
 
 		t->bt_free = P_INVALID;
 		t->bt_nrecs = 0;
-		SET(t, B_METADIRTY);
+		F_SET(t, B_METADIRTY);
 	}
 
 	t->bt_psize = b.psize;
@@ -309,7 +313,7 @@ __bt_open(fname, flags, mode, openinfo, dflags)
 	if ((t->bt_mp =
 	    mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
 		goto err;
-	if (!ISSET(t, B_INMEM))
+	if (!F_ISSET(t, B_INMEM))
 		mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);
 
 	/* Create a root page if new tree. */
@@ -318,11 +322,11 @@ __bt_open(fname, flags, mode, openinfo, dflags)
 
 	/* Global flags. */
 	if (dflags & DB_LOCK)
-		SET(t, B_DB_LOCK);
+		F_SET(t, B_DB_LOCK);
 	if (dflags & DB_SHMEM)
-		SET(t, B_DB_SHMEM);
+		F_SET(t, B_DB_SHMEM);
 	if (dflags & DB_TXN)
-		SET(t, B_DB_TXN);
+		F_SET(t, B_DB_TXN);
 
 	return (dbp);
 
@@ -438,7 +442,7 @@ __bt_fd(dbp)
 	}
 
 	/* In-memory database can't have a file descriptor. */
-	if (ISSET(t, B_INMEM)) {
+	if (F_ISSET(t, B_INMEM)) {
 		errno = ENOENT;
 		return (-1);
 	}
diff --git a/lib/libc/db/btree/bt_overflow.c b/lib/libc/db/btree/bt_overflow.c
index b5c43c60435..fcae9ef013b 100644
--- a/lib/libc/db/btree/bt_overflow.c
+++ b/lib/libc/db/btree/bt_overflow.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: bt_overflow.c,v 1.5 1995/02/27 13:20:33 cgd Exp $	*/
+/*	$NetBSD: bt_overflow.c,v 1.6 1996/05/03 21:50:48 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_overflow.c	8.4 (Berkeley) 6/20/94";
+static char sccsid[] = "@(#)bt_overflow.c	8.5 (Berkeley) 7/16/94";
 #else
-static char rcsid[] = "$NetBSD: bt_overflow.c,v 1.5 1995/02/27 13:20:33 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_overflow.c,v 1.6 1996/05/03 21:50:48 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -87,7 +87,7 @@ __ovfl_get(t, p, ssz, buf, bufsz)
 	BTREE *t;
 	void *p;
 	size_t *ssz;
-	char **buf;
+	void **buf;
 	size_t *bufsz;
 {
 	PAGE *h;
diff --git a/lib/libc/db/btree/bt_page.c b/lib/libc/db/btree/bt_page.c
index d6a44941854..7b977bd0d36 100644
--- a/lib/libc/db/btree/bt_page.c
+++ b/lib/libc/db/btree/bt_page.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: bt_page.c,v 1.5 1995/02/27 13:20:36 cgd Exp $	*/
+/*	$NetBSD: bt_page.c,v 1.6 1996/05/03 21:50:49 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1990, 1993
+ * 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
@@ -35,9 +35,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_page.c	8.2 (Berkeley) 2/21/94";
+static char sccsid[] = "@(#)bt_page.c	8.3 (Berkeley) 7/14/94";
 #else
-static char rcsid[] = "$NetBSD: bt_page.c,v 1.5 1995/02/27 13:20:36 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_page.c,v 1.6 1996/05/03 21:50:49 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -49,7 +49,8 @@ static char rcsid[] = "$NetBSD: bt_page.c,v 1.5 1995/02/27 13:20:36 cgd Exp $";
 #include "btree.h"
 
 /*
- * __BT_FREE -- Put a page on the freelist.
+ * __bt_free --
+ *	Put a page on the freelist.
  *
  * Parameters:
  *	t:	tree
@@ -57,13 +58,16 @@ static char rcsid[] = "$NetBSD: bt_page.c,v 1.5 1995/02/27 13:20:36 cgd Exp $";
  *
  * 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 start of the free list. */
+	/* Insert the page at the head of the free list. */
 	h->prevpg = P_INVALID;
 	h->nextpg = t->bt_free;
 	t->bt_free = h->pgno;
@@ -73,7 +77,8 @@ __bt_free(t, h)
 }
 
 /*
- * __BT_NEW -- Get a new page, preferably from the freelist.
+ * __bt_new --
+ *	Get a new page, preferably from the freelist.
  *
  * Parameters:
  *	t:	tree
@@ -91,9 +96,9 @@ __bt_new(t, npg)
 
 	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;
-			return (h);
+		*npg = t->bt_free;
+		t->bt_free = h->nextpg;
+		return (h);
 	}
 	return (mpool_new(t->bt_mp, npg));
 }
diff --git a/lib/libc/db/btree/bt_put.c b/lib/libc/db/btree/bt_put.c
index 9ddc98d8ec1..5d13b062648 100644
--- a/lib/libc/db/btree/bt_put.c
+++ b/lib/libc/db/btree/bt_put.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: bt_put.c,v 1.7 1995/02/27 13:20:40 cgd Exp $	*/
+/*	$NetBSD: bt_put.c,v 1.8 1996/05/03 21:50:51 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_put.c	8.4 (Berkeley) 5/31/94";
+static char sccsid[] = "@(#)bt_put.c	8.8 (Berkeley) 7/26/94";
 #else
-static char rcsid[] = "$NetBSD: bt_put.c,v 1.7 1995/02/27 13:20:40 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_put.c,v 1.8 1996/05/03 21:50:51 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -94,33 +94,38 @@ __bt_put(dbp, key, data, flags)
 		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 R_CURSOR:
-		if (!ISSET(t, B_SEQINIT))
-			goto einval;
-		if (ISSET(t, B_DELCRSR))
-			goto einval;
-		break;
 	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:
-einval:		errno = EINVAL;
-		return (RET_ERROR);
-	}
-
-	if (ISSET(t, B_RDONLY)) {
-		errno = EPERM;
+		errno = EINVAL;
 		return (RET_ERROR);
 	}
 
 	/*
-	 * If the key/data won't fit on a page, store it on indirect pages.
-	 * Only store the key on the overflow page if it's too big after the
-	 * data is on an overflow page.
+	 * 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, these pages aren't recovered.
+	 * If the insert fails later on, the overflow pages aren't recovered.
 	 */
 	dflags = 0;
 	if (key->size + data->size > t->bt_ovflsize) {
@@ -152,15 +157,15 @@ storekey:		if (__ovfl_put(t, key, &pg) == RET_ERROR)
 
 	/* Replace the cursor. */
 	if (flags == R_CURSOR) {
-		if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL)
+		if ((h = mpool_get(t->bt_mp, t->bt_cursor.pg.pgno, 0)) == NULL)
 			return (RET_ERROR);
-		index = t->bt_bcursor.index;
+		index = t->bt_cursor.pg.index;
 		goto delete;
 	}
 
 	/*
-	 * Find the key to delete, or, the location at which to insert.  Bt_fast
-	 * and __bt_search pin the returned page.
+	 * 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)
@@ -169,34 +174,26 @@ storekey:		if (__ovfl_put(t, key, &pg) == RET_ERROR)
 	index = e->index;
 
 	/*
-	 * Add the specified 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.
-	 *
-	 * Pages are split as required.
+	 * 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;
-		/*
-		 * One special case is if the cursor references the record and
-		 * it's been flagged for deletion.  Then, we delete the record,
-		 * leaving the cursor there -- this means that the inserted
-		 * record will not be seen in a cursor scan.
-		 */
-		if (ISSET(t, B_DELCRSR) && t->bt_bcursor.pgno == h->pgno &&
-		    t->bt_bcursor.index == index) {
-			CLR(t, B_DELCRSR);
-			goto delete;
-		}
 		mpool_put(t->bt_mp, h, 0);
 		return (RET_SPECIAL);
 	default:
-		if (!exact || !ISSET(t, B_NODUPS))
+		if (!exact || !F_ISSET(t, B_NODUPS))
 			break;
-delete:		if (__bt_dleaf(t, h, index) == RET_ERROR) {
+		/*
+		 * !!!
+		 * 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, index) == RET_ERROR) {
 			mpool_put(t->bt_mp, h, 0);
 			return (RET_ERROR);
 		}
@@ -226,6 +223,12 @@ delete:		if (__bt_dleaf(t, h, index) == RET_ERROR) {
 	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 >= index)
+		++t->bt_cursor.pg.index;
+
 	if (t->bt_order == NOT)
 		if (h->nextpg == P_INVALID) {
 			if (index == NEXTINDEX(h) - 1) {
@@ -244,11 +247,10 @@ delete:		if (__bt_dleaf(t, h, index) == RET_ERROR) {
 	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
 
 success:
-	if (flags == R_SETCURSOR) {
-		t->bt_bcursor.pgno = e->page->pgno;
-		t->bt_bcursor.index = e->index;
-	}
-	SET(t, B_MODIFIED);
+	if (flags == R_SETCURSOR)
+		__bt_setcur(t, e->page->pgno, e->index);
+
+	F_SET(t, B_MODIFIED);
 	return (RET_SUCCESS);
 }
 
@@ -284,8 +286,8 @@ bt_fast(t, key, data, exactp)
 	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.
+	 * 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 (h->upper - h->lower < nbytes + sizeof(indx_t))
diff --git a/lib/libc/db/btree/bt_search.c b/lib/libc/db/btree/bt_search.c
index c98fe7346ea..d0832b9d383 100644
--- a/lib/libc/db/btree/bt_search.c
+++ b/lib/libc/db/btree/bt_search.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: bt_search.c,v 1.7 1995/02/27 13:20:44 cgd Exp $	*/
+/*	$NetBSD: bt_search.c,v 1.8 1996/05/03 21:50:52 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1990, 1993
+ * 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
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_search.c	8.6 (Berkeley) 3/15/94";
+static char sccsid[] = "@(#)bt_search.c	8.8 (Berkeley) 7/31/94";
 #else
-static char rcsid[] = "$NetBSD: bt_search.c,v 1.7 1995/02/27 13:20:44 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_search.c,v 1.8 1996/05/03 21:50:52 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -51,11 +51,12 @@ static char rcsid[] = "$NetBSD: bt_search.c,v 1.7 1995/02/27 13:20:44 cgd Exp $"
 #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 *));
+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.
+ * __bt_search --
+ *	Search a btree for a key.
  *
  * Parameters:
  *	t:	tree to search
@@ -101,24 +102,26 @@ __bt_search(t, key, exactp)
 		}
 
 		/*
-		 * If it's a leaf page, and duplicates aren't allowed, we're
-		 * done.  If duplicates are allowed, it's possible that there
-		 * were duplicate keys on duplicate pages, and they were later
-		 * deleted, so we could be on a page with no matches while
-		 * there are matches on other pages.  If we're at the start or
-		 * end of a page, check on both sides.
+		 * 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) {
-			t->bt_cur.index = base;
-			*exactp = 0;
-			if (!ISSET(t, B_NODUPS)) {
+			if (!F_ISSET(t, B_NODUPS)) {
 				if (base == 0 &&
-				    bt_sprev(t, h, key, exactp))
+				    h->prevpg != P_INVALID &&
+				    __bt_sprev(t, h, key, exactp))
 					return (&t->bt_cur);
 				if (base == NEXTINDEX(h) &&
-				    bt_snext(t, h, key, exactp))
+				    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);
 		}
 
@@ -131,111 +134,86 @@ __bt_search(t, key, exactp)
 		 */
 		index = base ? base - 1 : base;
 
-next:		if (__bt_push(t, h->pgno, index) == RET_ERROR)
-			return (NULL);
+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.
+ * __bt_snext --
+ *	Check for an exact match after the key.
  *
  * Parameters:
- *	t:	tree to search
- *	h:	current page.
- *	key:	key to find
+ *	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)
+__bt_snext(t, h, key, exactp)
 	BTREE *t;
 	PAGE *h;
 	const DBT *key;
 	int *exactp;
 {
 	EPG e;
-	PAGE *tp;
-	pgno_t pg;
 
-	/* Skip until reach the end of the tree or a key. */
-	for (pg = h->nextpg; pg != P_INVALID;) {
-		if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) {
-			mpool_put(t->bt_mp, h, 0);
-			return (NULL);
-		}
-		if (NEXTINDEX(tp) != 0)
-			break;
-		pg = tp->prevpg;
-		mpool_put(t->bt_mp, tp, 0);
-	}
 	/*
-	 * The key is either an exact match, or not as good as
-	 * the one we already have.
+	 * Get the next page.  The key is either an exact
+	 * match, or not as good as the one we already have.
 	 */
-	if (pg != P_INVALID) {
-		e.page = tp;
-		e.index = NEXTINDEX(tp) - 1;
-		if (__bt_cmp(t, key, &e) == 0) {
-			mpool_put(t->bt_mp, h, 0);
-			t->bt_cur = e;
-			*exactp = 1;
-			return (1);
-		}
+	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.
+ * __bt_sprev --
+ *	Check for an exact match before the key.
  *
  * Parameters:
- *	t:	tree to search
- *	h:	current page.
- *	key:	key to find
+ *	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)
+__bt_sprev(t, h, key, exactp)
 	BTREE *t;
 	PAGE *h;
 	const DBT *key;
 	int *exactp;
 {
 	EPG e;
-	PAGE *tp;
-	pgno_t pg;
 
-	/* Skip until reach the beginning of the tree or a key. */
-	for (pg = h->prevpg; pg != P_INVALID;) {
-		if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) {
-			mpool_put(t->bt_mp, h, 0);
-			return (NULL);
-		}
-		if (NEXTINDEX(tp) != 0)
-			break;
-		pg = tp->prevpg;
-		mpool_put(t->bt_mp, tp, 0);
-	}
 	/*
-	 * The key is either an exact match, or not as good as
-	 * the one we already have.
+	 * Get the previous page.  The key is either an exact
+	 * match, or not as good as the one we already have.
 	 */
-	if (pg != P_INVALID) {
-		e.page = tp;
-		e.index = NEXTINDEX(tp) - 1;
-		if (__bt_cmp(t, key, &e) == 0) {
-			mpool_put(t->bt_mp, h, 0);
-			t->bt_cur = e;
-			*exactp = 1;
-			return (1);
-		}
+	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/lib/libc/db/btree/bt_seq.c b/lib/libc/db/btree/bt_seq.c
index f029cc3e174..7717593a589 100644
--- a/lib/libc/db/btree/bt_seq.c
+++ b/lib/libc/db/btree/bt_seq.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $	*/
+/*	$NetBSD: bt_seq.c,v 1.7 1996/05/03 21:50:54 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1990, 1993
+ * 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
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_seq.c	8.2 (Berkeley) 9/7/93";
+static char sccsid[] = "@(#)bt_seq.c	8.7 (Berkeley) 7/20/94";
 #else
-static char rcsid[] = "$NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_seq.c,v 1.7 1996/05/03 21:50:54 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -54,24 +54,21 @@ static char rcsid[] = "$NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $";
 #include <db.h>
 #include "btree.h"
 
-static int	 bt_seqadv __P((BTREE *, EPG *, int));
-static int	 bt_seqset __P((BTREE *, EPG *, DBT *, int));
+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.
- *
- * Each tree has an EPGNO which has the current position of the cursor.  The
- * cursor has to survive deletions/insertions in the tree without losing its
- * position.  This is done by noting deletions without doing them, and then
- * doing them when the cursor moves (or the tree is closed).
+ * 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.
+ * __bt_seq --
+ *	Btree sequential scan interface.
  *
  * Parameters:
  *	dbp:	pointer to access method
@@ -102,21 +99,21 @@ __bt_seq(dbp, key, data, flags)
 
 	/*
 	 * If scan unitialized 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.
+	 * the scan to a specific key.  Both __bt_seqset and __bt_seqadv pin
+	 * the page the cursor references if they're successful.
 	 */
-	switch(flags) {
+	switch (flags) {
 	case R_NEXT:
 	case R_PREV:
-		if (ISSET(t, B_SEQINIT)) {
-			status = bt_seqadv(t, &e, flags);
+		if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
+			status = __bt_seqadv(t, &e, flags);
 			break;
 		}
 		/* FALLTHROUGH */
-	case R_CURSOR:
 	case R_FIRST:
 	case R_LAST:
-		status = bt_seqset(t, &e, key, flags);
+	case R_CURSOR:
+		status = __bt_seqset(t, &e, key, flags);
 		break;
 	default:
 		errno = EINVAL;
@@ -124,27 +121,26 @@ __bt_seq(dbp, key, data, flags)
 	}
 
 	if (status == RET_SUCCESS) {
-		status = __bt_ret(t, &e, key, data);
+		__bt_setcur(t, e.page->pgno, e.index);
 
-		/* Update the actual cursor. */
-		t->bt_bcursor.pgno = e.page->pgno;
-		t->bt_bcursor.index = 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 (ISSET(t, B_DB_LOCK))
+		if (F_ISSET(t, B_DB_LOCK))
 			mpool_put(t->bt_mp, e.page, 0);
 		else
 			t->bt_pinned = e.page;
-		SET(t, B_SEQINIT);
 	}
 	return (status);
 }
 
 /*
- * BT_SEQSET -- Set the sequential scan to a specific key.
+ * __bt_seqset --
+ *	Set the sequential scan to a specific key.
  *
  * Parameters:
  *	t:	tree
@@ -159,87 +155,50 @@ __bt_seq(dbp, key, data, flags)
  *	RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
  */
 static int
-bt_seqset(t, ep, key, flags)
+__bt_seqset(t, ep, key, flags)
 	BTREE *t;
 	EPG *ep;
 	DBT *key;
 	int flags;
 {
-	EPG *e;
 	PAGE *h;
 	pgno_t pg;
 	int exact;
 
 	/*
-	 * Delete any already deleted record that we've been saving because
-	 * the cursor pointed to it.  Since going to a specific key, should
-	 * delete any logically deleted records so they aren't found.
-	 */
-	if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor))
-		return (RET_ERROR);
-
-	/*
-	 * 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.
+	 * 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) {
+	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 run out
-		 * of keys, return RET_SPECIAL.
+		 * 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);
 		}
-		e = __bt_first(t, key, &exact);	/* Returns pinned page. */
-		if (e == NULL)
-			return (RET_ERROR);
-		/*
-		 * If at the end of a page, skip any empty pages and find the
-		 * next entry.
-		 */
-		if (e->index == NEXTINDEX(e->page)) {
-			h = e->page;
-			do {
-				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);
-			} while (NEXTINDEX(h) == 0);
-			e->index = 0;
-			e->page = h;
-		}
-		*ep = *e;
-		break;
+		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);
 		}
-
-		/* Skip any empty pages. */
-		while (NEXTINDEX(h) == 0 && h->nextpg != P_INVALID) {
-			pg = h->nextpg;
-			mpool_put(t->bt_mp, h, 0);
-			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-				return (RET_ERROR);
-		}
-
-		if (NEXTINDEX(h) == 0) {
-			mpool_put(t->bt_mp, h, 0);
-			return (RET_SPECIAL);
-		}
-
 		ep->page = h;
 		ep->index = 0;
 		break;
@@ -249,25 +208,19 @@ bt_seqset(t, ep, key, flags)
 		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);
 		}
 
-		/* Skip any empty pages. */
-		while (NEXTINDEX(h) == 0 && h->prevpg != P_INVALID) {
-			pg = h->prevpg;
-			mpool_put(t->bt_mp, h, 0);
-			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
-				return (RET_ERROR);
-		}
-
-		if (NEXTINDEX(h) == 0) {
-			mpool_put(t->bt_mp, h, 0);
-			return (RET_SPECIAL);
-		}
-
 		ep->page = h;
 		ep->index = NEXTINDEX(h) - 1;
 		break;
@@ -276,7 +229,8 @@ bt_seqset(t, ep, key, flags)
 }
 
 /*
- * BT_SEQADVANCE -- Advance the sequential scan.
+ * __bt_seqadvance --
+ *	Advance the sequential scan.
  *
  * Parameters:
  *	t:	tree
@@ -289,98 +243,224 @@ bt_seqset(t, ep, key, flags)
  *	RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
  */
 static int
-bt_seqadv(t, e, flags)
+__bt_seqadv(t, ep, flags)
 	BTREE *t;
-	EPG *e;
+	EPG *ep;
 	int flags;
 {
-	EPGNO *c, delc;
+	CURSOR *c;
 	PAGE *h;
 	indx_t index;
 	pgno_t pg;
+	int exact;
 
-	/* Save the current cursor if going to delete it. */
-	c = &t->bt_bcursor;
-	if (ISSET(t, B_DELCRSR))
-		delc = *c;
+	/*
+	 * 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;
 
-	if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL)
+	/*
+	 * 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.
+ 	 * 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.
 	 */
-	index = c->index;
-	switch(flags) {
+	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)) {
-			do {
-				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);
-			} while (NEXTINDEX(h) == 0);
+			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. */
-		if (index-- == 0) {
-			do {
-				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);
-			} while (NEXTINDEX(h) == 0);
-			index = NEXTINDEX(h) - 1;
+		/*
+		 * 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;
 	}
 
-	e->page = h;
-	e->index = index;
+	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;
 
 	/*
-	 * Delete any already deleted record that we've been saving because the
-	 * cursor pointed to it.  This could cause the new index to be shifted
-	 * down by one if the record we're deleting is on the same page and has
-	 * a larger index.
+	 * 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 (ISSET(t, B_DELCRSR)) {
-		CLR(t, B_DELCRSR);			/* Don't try twice. */
-		if (c->pgno == delc.pgno && c->index > delc.index)
-			--c->index;
-		if (__bt_crsrdel(t, &delc))
+	if ((ep = __bt_search(t, key, exactp)) == NULL)
+		return (NULL);
+	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_CRSRDEL -- Delete the record referenced by the cursor.
+ * __bt_setcur --
+ *	Set the cursor to an entry in the tree.
  *
  * Parameters:
- *	t:	tree
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
+ *	t:	the tree
+ *   pgno:	page number
+ *  index:	page index
  */
-int
-__bt_crsrdel(t, c)
+void
+__bt_setcur(t, pgno, index)
 	BTREE *t;
-	EPGNO *c;
+	pgno_t pgno;
+	u_int index;
 {
-	PAGE *h;
-	int status;
+	/* 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);
 
-	CLR(t, B_DELCRSR);			/* Don't try twice. */
-	if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL)
-		return (RET_ERROR);
-	status = __bt_dleaf(t, h, c->index);
-	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
-	return (status);
+	/* 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/lib/libc/db/btree/bt_split.c b/lib/libc/db/btree/bt_split.c
index 22334c1e430..110e3f9dd1d 100644
--- a/lib/libc/db/btree/bt_split.c
+++ b/lib/libc/db/btree/bt_split.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: bt_split.c,v 1.5 1995/02/27 13:20:55 cgd Exp $	*/
+/*	$NetBSD: bt_split.c,v 1.6 1996/05/03 21:50:56 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_split.c	8.6 (Berkeley) 6/16/94";
+static char sccsid[] = "@(#)bt_split.c	8.9 (Berkeley) 7/26/94";
 #else
-static char rcsid[] = "$NetBSD: bt_split.c,v 1.5 1995/02/27 13:20:55 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_split.c,v 1.6 1996/05/03 21:50:56 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -123,14 +123,14 @@ __bt_split(t, sp, key, data, flags, ilen, argskip)
 	 */
 	h->linp[skip] = h->upper -= ilen;
 	dest = (char *)h + h->upper;
-	if (ISSET(t, R_RECNO))
+	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 &&
-	    (ISSET(t, R_RECNO) ?
+	    (F_ISSET(t, R_RECNO) ?
 	    bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
 		goto err2;
 
@@ -238,7 +238,7 @@ __bt_split(t, sp, key, data, flags, ilen, argskip)
 		}
 
 		/* Insert the key into the parent page. */
-		switch(rchild->flags & P_TYPE) {
+		switch (rchild->flags & P_TYPE) {
 		case P_BINTERNAL:
 			h->linp[skip] = h->upper -= nbytes;
 			dest = (char *)h + h->linp[skip];
@@ -303,7 +303,7 @@ __bt_split(t, sp, key, data, flags, ilen, argskip)
 
 		/* If the root page was split, make it look right. */
 		if (sp->pgno == P_ROOT &&
-		    (ISSET(t, R_RECNO) ?
+		    (F_ISSET(t, R_RECNO) ?
 		    bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
 			goto err1;
 
@@ -396,6 +396,9 @@ bt_page(t, h, lp, rp, skip, ilen)
 		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;
@@ -411,7 +414,7 @@ bt_page(t, h, lp, rp, skip, ilen)
 			return (NULL);
 		}
 		tp->prevpg = r->pgno;
-		mpool_put(t->bt_mp, tp, 0);
+		mpool_put(t->bt_mp, tp, MPOOL_DIRTY);
 	}
 
 	/*
@@ -558,7 +561,7 @@ bt_broot(t, h, l, r)
 	dest = (char *)h + h->upper;
 	WR_BINTERNAL(dest, 0, l->pgno, 0);
 
-	switch(h->flags & P_TYPE) {
+	switch (h->flags & P_TYPE) {
 	case P_BLEAF:
 		bl = GETBLEAF(r, 0);
 		nbytes = NBINTERNAL(bl->ksize);
@@ -621,8 +624,8 @@ bt_psplit(t, h, l, r, pskip, ilen)
 {
 	BINTERNAL *bi;
 	BLEAF *bl;
+	CURSOR *c;
 	RLEAF *rl;
-	EPGNO *c;
 	PAGE *rval;
 	void *src;
 	indx_t full, half, nxt, off, skip, top, used;
@@ -710,19 +713,16 @@ bt_psplit(t, h, l, r, pskip, ilen)
 	 * 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.
-	 *
-	 * Don't bother checking for the B_SEQINIT flag, the page number will
-	 * be P_INVALID.
 	 */
-	c = &t->bt_bcursor;
-	if (c->pgno == h->pgno) {
-		if (c->index >= skip)
-			++c->index;
-		if (c->index < nxt)			/* Left page. */
-			c->pgno = l->pgno;
+	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->pgno = r->pgno;
-			c->index -= nxt;
+			c->pg.pgno = r->pgno;
+			c->pg.index -= nxt;
 		}
 	}
 
diff --git a/lib/libc/db/btree/bt_stack.c b/lib/libc/db/btree/bt_stack.c
index 7199ae9b090..e69de29bb2d 100644
--- a/lib/libc/db/btree/bt_stack.c
+++ b/lib/libc/db/btree/bt_stack.c
@@ -1,102 +0,0 @@
-/*	$NetBSD: bt_stack.c,v 1.5 1995/02/27 13:21:01 cgd Exp $	*/
-
-/*-
- * 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)
-#if 0
-static char sccsid[] = "@(#)bt_stack.c	8.4 (Berkeley) 6/20/94";
-#else
-static char rcsid[] = "$NetBSD: bt_stack.c,v 1.5 1995/02/27 13:21:01 cgd Exp $";
-#endif
-#endif /* LIBC_SCCS and not lint */
-
-#include <sys/types.h>
-
-#include <errno.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-#include <db.h>
-#include "btree.h"
-
-/*
- * When a page splits, a new record has to be inserted into its parent page.
- * This page may have to split as well, all the way up to the root.  Since
- * parent pointers in each page would be expensive, we maintain a stack of
- * parent pages as we descend the tree.
- *
- * XXX
- * This is a concurrency problem -- if user a builds a stack, then user b
- * splits the tree, then user a tries to split the tree, there's a new level
- * in the tree that user a doesn't know about.
- */
-
-/*
- * __BT_PUSH -- Push parent page info onto the stack (LIFO).
- *
- * Parameters:
- *	t:	tree
- *	pgno:	page
- *	index:	page index
- *
- * Returns:
- * 	RET_ERROR, RET_SUCCESS
- */
-int
-__bt_push(t, pgno, index)
-	BTREE *t;
-	pgno_t pgno;
-	indx_t index;
-{
-	size_t sz;
-
-	if (t->bt_sp == t->bt_maxstack) {
-		t->bt_maxstack += 50;
-		sz = t->bt_maxstack * sizeof(EPGNO);
-		t->bt_stack = (EPGNO *)(t->bt_stack == NULL ?
-		    malloc(sz) : realloc(t->bt_stack, sz));
-		if (t->bt_stack == NULL) {
-			t->bt_maxstack -= 50;
-			return (RET_ERROR);
-		}
-	}
-
-	t->bt_stack[t->bt_sp].pgno = pgno;
-	t->bt_stack[t->bt_sp].index = index;
-	++t->bt_sp;
-	return (RET_SUCCESS);
-}
diff --git a/lib/libc/db/btree/bt_utils.c b/lib/libc/db/btree/bt_utils.c
index f9acf0ab8a1..2637f719a18 100644
--- a/lib/libc/db/btree/bt_utils.c
+++ b/lib/libc/db/btree/bt_utils.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: bt_utils.c,v 1.6 1995/02/27 13:21:04 cgd Exp $	*/
+/*	$NetBSD: bt_utils.c,v 1.7 1996/05/03 21:50:58 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)bt_utils.c	8.5 (Berkeley) 6/20/94";
+static char sccsid[] = "@(#)bt_utils.c	8.8 (Berkeley) 7/20/94";
 #else
-static char rcsid[] = "$NetBSD: bt_utils.c,v 1.6 1995/02/27 13:21:04 cgd Exp $";
+static char rcsid[] = "$NetBSD: bt_utils.c,v 1.7 1996/05/03 21:50:58 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -54,81 +54,91 @@ static char rcsid[] = "$NetBSD: bt_utils.c,v 1.6 1995/02/27 13:21:04 cgd Exp $";
 #include "btree.h"
 
 /*
- * __BT_RET -- Build return key/data pair as a result of search or scan.
+ * __bt_ret --
+ *	Build return key/data pair.
  *
  * Parameters:
  *	t:	tree
- *	d:	LEAF to be returned to the user.
+ *	e:	key/data pair to be returned
  *	key:	user's key structure (NULL if not to be filled in)
- *	data:	user's data structure
+ *	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, data)
+__bt_ret(t, e, key, rkey, data, rdata, copy)
 	BTREE *t;
 	EPG *e;
-	DBT *key, *data;
+	DBT *key, *rkey, *data, *rdata;
+	int copy;
 {
-	register BLEAF *bl;
-	register void *p;
+	BLEAF *bl;
+	void *p;
 
 	bl = GETBLEAF(e->page, e->index);
 
 	/*
-	 * We always copy big keys/data to make them contigous.  Otherwise,
-	 * we leave the page pinned and don't copy unless the user specified
+	 * 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.
 	 */
-	if (bl->flags & P_BIGDATA) {
-		if (__ovfl_get(t, bl->bytes + bl->ksize,
-		    &data->size, &t->bt_dbuf, &t->bt_dbufsz))
+	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);
-		data->data = t->bt_dbuf;
-	} else if (ISSET(t, B_DB_LOCK)) {
-		/* Use +1 in case the first record retrieved is 0 length. */
-		if (bl->dsize + 1 > t->bt_dbufsz) {
-			p = (void *)(t->bt_dbuf == NULL ?
-			    malloc(bl->dsize + 1) :
-			    realloc(t->bt_dbuf, bl->dsize + 1));
+		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);
-			t->bt_dbuf = p;
-			t->bt_dbufsz = bl->dsize + 1;
+			rkey->data = p;
+			rkey->size = bl->ksize;
 		}
-		memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize);
-		data->size = bl->dsize;
-		data->data = t->bt_dbuf;
+		memmove(rkey->data, bl->bytes, bl->ksize);
+		key->size = bl->ksize;
+		key->data = rkey->data;
 	} else {
-		data->size = bl->dsize;
-		data->data = bl->bytes + bl->ksize;
+		key->size = bl->ksize;
+		key->data = bl->bytes;
 	}
 
-	if (key == NULL)
+dataonly:
+	if (data == NULL)
 		return (RET_SUCCESS);
 
-	if (bl->flags & P_BIGKEY) {
-		if (__ovfl_get(t, bl->bytes,
-		    &key->size, &t->bt_kbuf, &t->bt_kbufsz))
+	if (bl->flags & P_BIGDATA) {
+		if (__ovfl_get(t, bl->bytes + bl->ksize,
+		    &data->size, &rdata->data, &rdata->size))
 			return (RET_ERROR);
-		key->data = t->bt_kbuf;
-	} else if (ISSET(t, B_DB_LOCK)) {
-		if (bl->ksize > t->bt_kbufsz) {
-			p = (void *)(t->bt_kbuf == NULL ?
-			    malloc(bl->ksize) : realloc(t->bt_kbuf, bl->ksize));
+		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);
-			t->bt_kbuf = p;
-			t->bt_kbufsz = bl->ksize;
+			rdata->data = p;
+			rdata->size = bl->dsize + 1;
 		}
-		memmove(t->bt_kbuf, bl->bytes, bl->ksize);
-		key->size = bl->ksize;
-		key->data = t->bt_kbuf;
+		memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
+		data->size = bl->dsize;
+		data->data = rdata->data;
 	} else {
-		key->size = bl->ksize;
-		key->data = bl->bytes;
+		data->size = bl->dsize;
+		data->data = bl->bytes + bl->ksize;
 	}
+
 	return (RET_SUCCESS);
 }
 
@@ -189,9 +199,9 @@ __bt_cmp(t, k1, e)
 
 	if (bigkey) {
 		if (__ovfl_get(t, bigkey,
-		    &k2.size, &t->bt_dbuf, &t->bt_dbufsz))
+		    &k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
 			return (RET_ERROR);
-		k2.data = t->bt_dbuf;
+		k2.data = t->bt_rdata.data;
 	}
 	return ((*t->bt_cmp)(k1, &k2));
 }
diff --git a/lib/libc/db/btree/btree.h b/lib/libc/db/btree/btree.h
index 747ed93638e..d2bb945a1c3 100644
--- a/lib/libc/db/btree/btree.h
+++ b/lib/libc/db/btree/btree.h
@@ -1,4 +1,4 @@
-/*	$NetBSD: btree.h,v 1.8 1995/02/27 13:21:08 cgd Exp $	*/
+/*	$NetBSD: btree.h,v 1.9 1996/05/03 21:51:00 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1991, 1993, 1994
@@ -35,9 +35,14 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- *	@(#)btree.h	8.6 (Berkeley) 5/31/94
+ *	@(#)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	DEFMINKEYPAGE	(2)		/* Minimum keys per page */
@@ -81,8 +86,9 @@ typedef struct _page {
 } 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	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))
 
 /*
@@ -101,8 +107,7 @@ typedef struct _page {
  * 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	LALIGN(n)	(((n) + sizeof(pgno_t) - 1) & ~(sizeof(pgno_t) - 1))
 #define	NOVFLSIZE	(sizeof(pgno_t) + sizeof(u_int32_t))
 
 /*
@@ -124,11 +129,11 @@ typedef struct _binternal {
 } BINTERNAL;
 
 /* Get the page's BINTERNAL structure at index indx. */
-#define	GETBINTERNAL(pg, indx) \
+#define	GETBINTERNAL(pg, indx)						\
 	((BINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
 
 /* Get the number of bytes in the entry. */
-#define NBINTERNAL(len) \
+#define NBINTERNAL(len)							\
 	LALIGN(sizeof(u_int32_t) + sizeof(pgno_t) + sizeof(u_char) + (len))
 
 /* Copy a BINTERNAL entry to the page. */
@@ -151,18 +156,18 @@ typedef struct _rinternal {
 } RINTERNAL;
 
 /* Get the page's RINTERNAL structure at index indx. */
-#define	GETRINTERNAL(pg, indx) \
+#define	GETRINTERNAL(pg, indx)						\
 	((RINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
 
 /* Get the number of bytes in the entry. */
-#define NRINTERNAL \
+#define NRINTERNAL							\
 	LALIGN(sizeof(recno_t) + sizeof(pgno_t))
 
 /* Copy a RINTERAL entry to the page. */
-#define	WR_RINTERNAL(p, nrecs, pgno) { \
-	*(recno_t *)p = nrecs; \
-	p += sizeof(recno_t); \
-	*(pgno_t *)p = pgno; \
+#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. */
@@ -174,15 +179,15 @@ typedef struct _bleaf {
 } BLEAF;
 
 /* Get the page's BLEAF structure at index indx. */
-#define	GETBLEAF(pg, 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) + \
+#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. */
@@ -206,14 +211,14 @@ typedef struct _rleaf {
 } RLEAF;
 
 /* Get the page's RLEAF structure at index indx. */
-#define	GETRLEAF(pg, 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) \
+#define	NRLEAFDBT(dsize)						\
 	LALIGN(sizeof(u_int32_t) + sizeof(u_char) + (dsize))
 
 /* Copy a RLEAF entry to the page. */
@@ -234,12 +239,6 @@ typedef struct _rleaf {
  * 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.
- *
- * One comment about cursors.  The cursor key is never removed from the tree,
- * even if deleted.  This is because it is quite difficult to decide where the
- * cursor should be when other keys have been inserted/deleted in the tree;
- * duplicate keys make it impossible.  This scheme does require extra work
- * though, to make sure that we don't perform an operation on a deleted key.
  */
 typedef struct _epgno {
 	pgno_t	pgno;			/* the page number */
@@ -252,53 +251,90 @@ typedef struct _epg {
 } EPG;
 
 /*
- * The metadata of the tree.  The m_nrecs field is used only by the RECNO code.
+ * 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	m_magic;	/* magic number */
-	u_int32_t	m_version;	/* version */
-	u_int32_t	m_psize;	/* page size */
-	u_int32_t	m_free;		/* page number of first free page */
-	u_int32_t	m_nrecs;	/* R: number of records */
+	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	m_flags;	/* bt_flags & SAVEMETA */
-	u_int32_t	m_unused;	/* unused */
+	u_int32_t	flags;		/* bt_flags & SAVEMETA */
 } BTMETA;
 
 /* The in-memory btree/recno data structure. */
 typedef struct _btree {
-	MPOOL	*bt_mp;			/* memory pool cookie */
+	MPOOL	 *bt_mp;		/* memory pool cookie */
 
-	DB	*bt_dbp;		/* pointer to enclosing DB */
+	DB	 *bt_dbp;		/* pointer to enclosing DB */
 
-	EPG	bt_cur;			/* current (pinned) page */
-	PAGE	*bt_pinned;		/* page pinned across calls */
+	EPG	  bt_cur;		/* current (pinned) page */
+	PAGE	 *bt_pinned;		/* page pinned across calls */
 
-	EPGNO	bt_bcursor;		/* B: btree cursor */
-	recno_t	bt_rcursor;		/* R: recno cursor (1-based) */
+	CURSOR	  bt_cursor;		/* cursor */
 
-#define	BT_POP(t)	(t->bt_sp ? t->bt_stack + --t->bt_sp : NULL)
-#define	BT_CLR(t)	(t->bt_sp = 0)
-	EPGNO	*bt_stack;		/* stack of parent pages */
-	u_int	bt_sp;			/* current stack pointer */
-	u_int	bt_maxstack;		/* largest stack */
+#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 */
 
-	char	*bt_kbuf;		/* key buffer */
-	size_t	bt_kbufsz;		/* key buffer size */
-	char	*bt_dbuf;		/* data buffer */
-	size_t	bt_dbufsz;		/* data buffer size */
+	DBT	  bt_rkey;		/* returned key */
+	DBT	  bt_rdata;		/* returned data */
 
-	int	bt_fd;			/* tree file descriptor */
+	int	  bt_fd;		/* tree file descriptor */
 
-	pgno_t	bt_free;		/* next free page */
+	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 */
+	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 */
+	EPGNO	  bt_last;		/* last insert */
 
 					/* B: key comparison function */
 	int	(*bt_cmp) __P((const DBT *, const DBT *));
@@ -307,49 +343,43 @@ typedef struct _btree {
 					/* 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 */
+	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. */
+	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 */
+	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_DELCRSR	0x00001		/* cursor has been deleted */
-#define	B_INMEM		0x00002		/* in-memory tree */
-#define	B_METADIRTY	0x00004		/* need to write metadata */
-#define	B_MODIFIED	0x00008		/* tree modified */
-#define	B_NEEDSWAP	0x00010		/* if byte order requires swapping */
+#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	B_RDONLY	0x00040		/* read-only tree */
 #define	R_RECNO		0x00080		/* record oriented tree */
-#define	B_SEQINIT	0x00100		/* sequential scan initialized */
-
-#define	R_CLOSEFP	0x00200		/* opened a file pointer */
-#define	R_EOF		0x00400		/* end of input file reached. */
-#define	R_FIXLEN	0x00800		/* fixed length records */
-#define	R_MEMMAPPED	0x01000		/* memory mapped file. */
-#define	R_INMEM		0x02000		/* in-memory file */
-#define	R_MODIFIED	0x04000		/* modified file */
-#define	R_RDONLY	0x08000		/* read-only file */
 
-#define	B_DB_LOCK	0x10000		/* DB_LOCK specified. */
-#define	B_DB_SHMEM	0x20000		/* DB_SHMEM specified. */
-#define	B_DB_TXN	0x40000		/* DB_TXN specified. */
-
-	u_int32_t	bt_flags;	/* btree state */
+#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;
 
-#define	SET(t, f)	((t)->bt_flags |= (f))
-#define	CLR(t, f)	((t)->bt_flags &= ~(f))
-#define	ISSET(t, f)	((t)->bt_flags & (f))
-
 #include "extern.h"
diff --git a/lib/libc/db/btree/extern.h b/lib/libc/db/btree/extern.h
index 6d09c2eb204..6a4fddf61c4 100644
--- a/lib/libc/db/btree/extern.h
+++ b/lib/libc/db/btree/extern.h
@@ -1,7 +1,7 @@
-/*	$NetBSD: extern.h,v 1.5 1995/02/27 13:21:12 cgd Exp $	*/
+/*	$NetBSD: extern.h,v 1.6 1996/05/03 21:51:01 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1991, 1993
+ * 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
@@ -32,7 +32,7 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- *	@(#)extern.h	8.4 (Berkeley) 6/4/94
+ *	@(#)extern.h	8.10 (Berkeley) 7/20/94
  */
 
 int	 __bt_close __P((DB *));
@@ -41,9 +41,8 @@ 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 *, PAGE *, int));
+int	 __bt_dleaf __P((BTREE *, const DBT *, PAGE *, u_int));
 int	 __bt_fd __P((const DB *));
-EPG	*__bt_first __P((BTREE *, const DBT *, int *));
 int	 __bt_free __P((BTREE *, PAGE *));
 int	 __bt_get __P((const DB *, const DBT *, DBT *, u_int));
 PAGE	*__bt_new __P((BTREE *, pgno_t *));
@@ -51,15 +50,16 @@ 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 *));
+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 *, char **, size_t *));
+int	 __ovfl_get __P((BTREE *, void *, size_t *, void **, size_t *));
 int	 __ovfl_put __P((BTREE *, const DBT *, pgno_t *));
 
 #ifdef DEBUG
diff --git a/lib/libc/db/changelog b/lib/libc/db/changelog
new file mode 100644
index 00000000000..f820e56b588
--- /dev/null
+++ b/lib/libc/db/changelog
@@ -0,0 +1,105 @@
+#	$NetBSD: changelog,v 1.2 1996/05/03 21:20:56 cgd Exp $
+
+1.84 -> 1.85
+	recno:	#ifdef out use of mmap, it's not portable enough.
+
+1.83 -> 1.84	Thu Aug 18 15:46:07 EDT 1994
+	recno:	Rework fixed-length records so that closing and reopening
+		the file now works.  Pad short records on input.  Never do
+		signed comparison in recno input reading functions.
+
+1.82 -> 1.83	Tue Jul 26 15:33:44 EDT 1994
+	btree:	Rework cursor deletion code yet again; bugs with
+		deleting empty pages that only contained the cursor
+		record.
+
+1.81 -> 1.82	Sat Jul 16 11:01:50 EDT 1994
+	btree:	Fix bugs introduced by new cursor/deletion code.
+		Replace return kbuf/dbuf with real DBT's.
+
+1.80 -> 1.81
+	btree:	Fix bugs introduced by new cursor/deletion code.
+	all:	Add #defines for Purify.
+
+1.79 -> 1.80	Wed Jul 13 22:41:54 EDT 1994
+	btree	Change deletion to coalesce empty pages.  This is a major
+		change, cursors and duplicate pages all had to be reworked.
+		Return to a fixed stack.
+	recno:	Affected by cursor changes.  New cursor structures should
+		permit multiple cursors in the future.
+
+1.78 -> 1.79	Mon Jun 20 17:36:47 EDT 1994
+	all:	Minor cleanups of 1.78 for porting reasons; only
+		major change was inlining check of NULL pointer
+		so that __fix_realloc goes away.
+
+1.77 -> 1.78	Thu Jun 16 19:06:43 EDT 1994
+	all:	Move "standard" size typedef's into db.h.
+
+1.76 -> 1.77	Thu Jun 16 16:48:38 EDT 1994
+	hash:	Delete __init_ routine, has special meaning to OSF 2.0.
+
+1.74 -> 1.76
+	all:	Finish up the port to the Alpha.
+
+1.73 -> 1.74
+	recno:	Don't put the record if rec_search fails, in rec_rdelete.
+		Create fixed-length intermediate records past "end" of DB
+		correctly.
+		Realloc bug when reading in fixed records.
+	all:	First cut at port to Alpha (64-bit architecture) using
+		4.4BSD basic integral types typedef's.
+		Cast allocation pointers to shut up old compilers.
+		Rework PORT directory into OS/machine directories.
+
+1.72 -> 1.73
+	btree:	If enough duplicate records were inserted and then deleted
+		that internal pages had references to empty pages of the
+		duplicate keys, the search function ended up on the wrong
+		page.
+
+1.7  -> 1.72	12 Oct 1993
+	hash:	Support NET/2 hash formats.
+
+1.7  -> 1.71	16 Sep 1993
+	btree/recno:
+		Fix bug in internal search routines that caused
+		return of invalid pointers.
+
+1.6  -> 1.7	07 Sep 1993
+	hash:	Fixed big key overflow bugs.
+	test:	Portability hacks, rewrite test script, Makefile.
+	btree/recno:
+		Stop copying non-overflow key/data pairs.
+	PORT:	Break PORT directory up into per architecture/OS
+		subdirectories.
+
+1.5  -> 1.6	06 Jun 1993
+	hash:	In PAIRFITS, the first comparison should look at (P)[2].
+		The hash_realloc function was walking off the end of memory.
+		The overflow page number was wrong when bumping splitpoint.
+
+1.4  -> 1.5	23 May 1993
+	hash:	Set hash default fill factor dynamically.
+	recno:	Fixed bug in sorted page splits.
+		Add page size parameter support.
+		Allow recno to specify the name of the underlying btree;
+			used for vi recovery.
+	btree/recno:
+		Support 64K pages.
+	btree/hash/recno:
+		Provide access to an underlying file descriptor.
+		Change sync routines to take a flag argument, recno
+			uses this to sync out the underlying btree.
+
+1.3  -> 1.4	10 May 1993
+	recno:	Delete the R_CURSORLOG flag from the recno interface.
+		Zero-length record fix for non-mmap reads.
+		Try and make SIZE_T_MAX test in open portable.
+
+1.2  -> 1.3	01 May 1993
+	btree:	Ignore user byte-order setting when reading already
+		existing database.  Fixes to byte-order conversions.
+
+1.1  -> 1.2	15 Apr 1993
+		No bug fixes, only compatibility hacks.
diff --git a/lib/libc/db/db2netbsd b/lib/libc/db/db2netbsd
new file mode 100644
index 00000000000..e29c97593bc
--- /dev/null
+++ b/lib/libc/db/db2netbsd
@@ -0,0 +1,31 @@
+#!/bin/sh
+#	$NetBSD: db2netbsd,v 1.1 1996/05/03 22:43:02 cgd Exp $
+
+# This version transforms a Berkeley DB distribution into something
+# which can be 'cvs import'ed into the NetBSD source repository.
+# It is to be run in the untarred Berkeley DB distribution directory
+# (e.g. the "db.1.85" directory created by tar xvf), and sets up
+# the destination tree in place.
+
+version=`basename $PWD | sed -e 's/db\.//'`
+releasetag=`basename $PWD | sed -e 's/\./-/g'`
+
+CLEANFILES="PORT docs test/btree.tests test/hash.tests"
+
+# clean up pieces that we never import
+/bin/rm -rf $CLEANFILES
+find . -type l -o -name tags | xargs /bin/rm -f
+
+# The include files are already in place
+
+# Put the regression tests in the right place
+mkdir -p regress/lib/libc
+mv test regress/lib/libc/db
+
+# Put the libc pieces in the right place.
+mkdir -p lib/libc/db
+mv Makefile.inc README btree changelog db hash man mpool recno lib/libc/db
+
+echo "import with:"
+echo "cvs import -m \"Import of Berkeley DB version $version\" \
+src CSRG $releasetag"
diff --git a/lib/libc/db/hash/Makefile.inc b/lib/libc/db/hash/Makefile.inc
index 00f339ac2ed..79fddf587d9 100644
--- a/lib/libc/db/hash/Makefile.inc
+++ b/lib/libc/db/hash/Makefile.inc
@@ -1,4 +1,4 @@
-#	$NetBSD: Makefile.inc,v 1.5 1995/02/27 13:21:44 cgd Exp $
+#	$NetBSD: Makefile.inc,v 1.6 1996/05/03 21:43:43 cgd Exp $
 #       @(#)Makefile.inc	8.1 (Berkeley) 6/4/93
 
 .PATH: ${.CURDIR}/db/hash
diff --git a/lib/libc/db/hash/README b/lib/libc/db/hash/README
index fd1fc653a92..444bcb90414 100644
--- a/lib/libc/db/hash/README
+++ b/lib/libc/db/hash/README
@@ -1,4 +1,4 @@
-#	$NetBSD: README,v 1.3 1995/02/27 13:21:52 cgd Exp $
+#	$NetBSD: README,v 1.4 1996/05/03 21:43:44 cgd Exp $
 #	@(#)README	8.1 (Berkeley) 6/4/93
 
 This package implements a superset of the hsearch and dbm/ndbm libraries.
diff --git a/lib/libc/db/hash/extern.h b/lib/libc/db/hash/extern.h
index af98921ef19..6b87ce4496d 100644
--- a/lib/libc/db/hash/extern.h
+++ b/lib/libc/db/hash/extern.h
@@ -1,4 +1,4 @@
-/*	$NetBSD: extern.h,v 1.4 1995/02/27 13:21:55 cgd Exp $	*/
+/*	$NetBSD: extern.h,v 1.5 1996/05/03 21:43:45 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1991, 1993, 1994
diff --git a/lib/libc/db/hash/hash.c b/lib/libc/db/hash/hash.c
index 2fc3281cb9f..7ee731e500b 100644
--- a/lib/libc/db/hash/hash.c
+++ b/lib/libc/db/hash/hash.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: hash.c,v 1.8 1995/02/27 13:21:59 cgd Exp $	*/
+/*	$NetBSD: hash.c,v 1.9 1996/05/03 21:43:47 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -40,7 +40,7 @@
 #if 0
 static char sccsid[] = "@(#)hash.c	8.9 (Berkeley) 6/16/94";
 #else
-static char rcsid[] = "$NetBSD: hash.c,v 1.8 1995/02/27 13:21:59 cgd Exp $";
+static char rcsid[] = "$NetBSD: hash.c,v 1.9 1996/05/03 21:43:47 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
diff --git a/lib/libc/db/hash/hash.h b/lib/libc/db/hash/hash.h
index 1ad93b74d9f..8ed5c6f6130 100644
--- a/lib/libc/db/hash/hash.h
+++ b/lib/libc/db/hash/hash.h
@@ -1,4 +1,4 @@
-/*	$NetBSD: hash.h,v 1.5 1995/02/27 13:22:08 cgd Exp $	*/
+/*	$NetBSD: hash.h,v 1.6 1996/05/03 21:43:48 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
diff --git a/lib/libc/db/hash/hash_bigkey.c b/lib/libc/db/hash/hash_bigkey.c
index 993839d9f79..0db652b8645 100644
--- a/lib/libc/db/hash/hash_bigkey.c
+++ b/lib/libc/db/hash/hash_bigkey.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: hash_bigkey.c,v 1.5 1995/02/27 13:22:16 cgd Exp $	*/
+/*	$NetBSD: hash_bigkey.c,v 1.6 1996/05/03 21:43:49 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -40,7 +40,7 @@
 #if 0
 static char sccsid[] = "@(#)hash_bigkey.c	8.3 (Berkeley) 5/31/94";
 #else
-static char rcsid[] = "$NetBSD: hash_bigkey.c,v 1.5 1995/02/27 13:22:16 cgd Exp $";
+static char rcsid[] = "$NetBSD: hash_bigkey.c,v 1.6 1996/05/03 21:43:49 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
diff --git a/lib/libc/db/hash/hash_buf.c b/lib/libc/db/hash/hash_buf.c
index 7747331688a..81aca2a1dc3 100644
--- a/lib/libc/db/hash/hash_buf.c
+++ b/lib/libc/db/hash/hash_buf.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: hash_buf.c,v 1.5 1995/02/27 13:22:23 cgd Exp $	*/
+/*	$NetBSD: hash_buf.c,v 1.6 1996/05/03 21:43:51 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)hash_buf.c	8.4 (Berkeley) 6/4/94";
+static char sccsid[] = "@(#)hash_buf.c	8.5 (Berkeley) 7/15/94";
 #else
-static char rcsid[] = "$NetBSD: hash_buf.c,v 1.5 1995/02/27 13:22:23 cgd Exp $";
+static char rcsid[] = "$NetBSD: hash_buf.c,v 1.6 1996/05/03 21:43:51 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -185,10 +185,16 @@ newbuf(hashp, addr, prev_bp)
 		/* Allocate a new one */
 		if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL)
 			return (NULL);
+#ifdef PURIFY
+		memset(bp, 0xff, sizeof(BUFHEAD));
+#endif
 		if ((bp->page = (char *)malloc(hashp->BSIZE)) == NULL) {
 			free(bp);
 			return (NULL);
 		}
+#ifdef PURIFY
+		memset(bp->page, 0xff, hashp->BSIZE);
+#endif
 		if (hashp->nbufs)
 			hashp->nbufs--;
 	} else {
diff --git a/lib/libc/db/hash/hash_func.c b/lib/libc/db/hash/hash_func.c
index a978b99d2fa..09cf72e77f6 100644
--- a/lib/libc/db/hash/hash_func.c
+++ b/lib/libc/db/hash/hash_func.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: hash_func.c,v 1.5 1995/02/27 13:22:27 cgd Exp $	*/
+/*	$NetBSD: hash_func.c,v 1.6 1996/05/03 21:43:52 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993
@@ -40,7 +40,7 @@
 #if 0
 static char sccsid[] = "@(#)hash_func.c	8.2 (Berkeley) 2/21/94";
 #else
-static char rcsid[] = "$NetBSD: hash_func.c,v 1.5 1995/02/27 13:22:27 cgd Exp $";
+static char rcsid[] = "$NetBSD: hash_func.c,v 1.6 1996/05/03 21:43:52 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
diff --git a/lib/libc/db/hash/hash_log2.c b/lib/libc/db/hash/hash_log2.c
index 9332cbac887..6ac2ab1ec2d 100644
--- a/lib/libc/db/hash/hash_log2.c
+++ b/lib/libc/db/hash/hash_log2.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: hash_log2.c,v 1.5 1995/02/27 13:22:30 cgd Exp $	*/
+/*	$NetBSD: hash_log2.c,v 1.6 1996/05/03 21:43:54 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -40,7 +40,7 @@
 #if 0
 static char sccsid[] = "@(#)hash_log2.c	8.2 (Berkeley) 5/31/94";
 #else
-static char rcsid[] = "$NetBSD: hash_log2.c,v 1.5 1995/02/27 13:22:30 cgd Exp $";
+static char rcsid[] = "$NetBSD: hash_log2.c,v 1.6 1996/05/03 21:43:54 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
diff --git a/lib/libc/db/hash/hash_page.c b/lib/libc/db/hash/hash_page.c
index 49ee8904a14..c81d46ba60f 100644
--- a/lib/libc/db/hash/hash_page.c
+++ b/lib/libc/db/hash/hash_page.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: hash_page.c,v 1.7 1995/02/27 13:22:34 cgd Exp $	*/
+/*	$NetBSD: hash_page.c,v 1.8 1996/05/03 21:43:55 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)hash_page.c	8.6 (Berkeley) 6/16/94";
+static char sccsid[] = "@(#)hash_page.c	8.7 (Berkeley) 8/16/94";
 #else
-static char rcsid[] = "$NetBSD: hash_page.c,v 1.7 1995/02/27 13:22:34 cgd Exp $";
+static char rcsid[] = "$NetBSD: hash_page.c,v 1.8 1996/05/03 21:43:55 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -689,7 +689,7 @@ overflow_page(hashp)
 	for ( i = first_page; i <= free_page; i++ ) {
 		if (!(freep = (u_int32_t *)hashp->mapp[i]) &&
 		    !(freep = fetch_bitmap(hashp, i)))
-			return (NULL);
+			return (0);
 		if (i == free_page)
 			in_use_bits = free_bit;
 		else
@@ -719,7 +719,7 @@ overflow_page(hashp)
 	if (offset > SPLITMASK) {
 		if (++splitnum >= NCACHED) {
 			(void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
-			return (NULL);
+			return (0);
 		}
 		hashp->OVFL_POINT = splitnum;
 		hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
@@ -732,7 +732,7 @@ overflow_page(hashp)
 		free_page++;
 		if (free_page >= NCACHED) {
 			(void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
-			return (NULL);
+			return (0);
 		}
 		/*
 		 * This is tricky.  The 1 indicates that you want the new page
@@ -745,9 +745,9 @@ overflow_page(hashp)
 		 * don't have to if we tell init_bitmap not to leave it clear
 		 * in the first place.
 		 */
-		if (__ibitmap(hashp, (int)OADDR_OF(splitnum, offset),
-		    1, free_page))
-			return (NULL);
+		if (__ibitmap(hashp,
+		    (int)OADDR_OF(splitnum, offset), 1, free_page))
+			return (0);
 		hashp->SPARES[splitnum]++;
 #ifdef DEBUG2
 		free_bit = 2;
@@ -757,7 +757,7 @@ overflow_page(hashp)
 			if (++splitnum >= NCACHED) {
 				(void)write(STDERR_FILENO, OVMSG,
 				    sizeof(OVMSG) - 1);
-				return (NULL);
+				return (0);
 			}
 			hashp->OVFL_POINT = splitnum;
 			hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
@@ -801,7 +801,7 @@ found:
 	for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);
 	offset = (i ? bit - hashp->SPARES[i - 1] : bit);
 	if (offset >= SPLITMASK)
-		return (NULL);	/* Out of overflow pages */
+		return (0);	/* Out of overflow pages */
 	addr = OADDR_OF(i, offset);
 #ifdef DEBUG2
 	(void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
diff --git a/lib/libc/db/hash/hsearch.c b/lib/libc/db/hash/hsearch.c
index ef825ab7182..409182c0c64 100644
--- a/lib/libc/db/hash/hsearch.c
+++ b/lib/libc/db/hash/hsearch.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: hsearch.c,v 1.8 1995/02/27 13:22:38 cgd Exp $	*/
+/*	$NetBSD: hsearch.c,v 1.10 1996/05/03 22:16:32 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)hsearch.c	8.3 (Berkeley) 2/21/94";
+static char sccsid[] = "@(#)hsearch.c	8.4 (Berkeley) 7/21/94";
 #else
-static char rcsid[] = "$NetBSD: hsearch.c,v 1.8 1995/02/27 13:22:38 cgd Exp $";
+static char rcsid[] = "$NetBSD: hsearch.c,v 1.10 1996/05/03 22:16:32 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -64,7 +64,7 @@ hcreate(nel)
 	info.nelem = nel;
 	info.bsize = 256;
 	info.ffactor = 8;
-	info.cachesize = NULL;
+	info.cachesize = 0;
 	info.hash = NULL;
 	info.lorder = 0;
 	dbp = (DB *)__hash_open(NULL, O_CREAT | O_RDWR, 0600, &info, 0);
diff --git a/lib/libc/db/hash/ndbm.c b/lib/libc/db/hash/ndbm.c
index 875b0494e59..dd519a4a8ce 100644
--- a/lib/libc/db/hash/ndbm.c
+++ b/lib/libc/db/hash/ndbm.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: ndbm.c,v 1.7 1995/02/27 13:22:44 cgd Exp $	*/
+/*	$NetBSD: ndbm.c,v 1.9 1996/05/04 00:38:58 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)ndbm.c	8.3 (Berkeley) 5/30/94";
+static char sccsid[] = "@(#)ndbm.c	8.4 (Berkeley) 7/21/94";
 #else
-static char rcsid[] = "$NetBSD: ndbm.c,v 1.7 1995/02/27 13:22:44 cgd Exp $";
+static char rcsid[] = "$NetBSD: ndbm.c,v 1.9 1996/05/04 00:38:58 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -73,7 +73,7 @@ dbm_open(file, flags, mode)
 	info.bsize = 4096;
 	info.ffactor = 40;
 	info.nelem = 1;
-	info.cachesize = NULL;
+	info.cachesize = 0;
 	info.hash = NULL;
 	info.lorder = 0;
 	(void)strcpy(path, file);
@@ -98,15 +98,20 @@ dbm_fetch(db, key)
 	DBM *db;
 	datum key;
 {
-	datum retval;
+	datum retdata;
 	int status;
+	DBT dbtkey, dbtretdata;
 
-	status = (db->get)(db, (DBT *)&key, (DBT *)&retval, 0);
+	dbtkey.data = key.dptr;
+	dbtkey.size = key.dsize;
+	status = (db->get)(db, &dbtkey, &dbtretdata, 0);
 	if (status) {
-		retval.dptr = NULL;
-		retval.dsize = 0;
+		dbtretdata.data = NULL;
+		dbtretdata.size = 0;
 	}
-	return (retval);
+	retdata.dptr = dbtretdata.data;
+	retdata.dsize = dbtretdata.size;
+	return (retdata);
 }
 
 /*
@@ -119,11 +124,14 @@ dbm_firstkey(db)
 	DBM *db;
 {
 	int status;
-	datum retdata, retkey;
+	datum retkey;
+	DBT dbtretkey, dbtretdata;
 
-	status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_FIRST);
+	status = (db->seq)(db, &dbtretkey, &dbtretdata, R_FIRST);
 	if (status)
-		retkey.dptr = NULL;
+		dbtretkey.data = NULL;
+	retkey.dptr = dbtretkey.data;
+	retkey.dsize = dbtretkey.size;
 	return (retkey);
 }
 
@@ -137,13 +145,17 @@ dbm_nextkey(db)
 	DBM *db;
 {
 	int status;
-	datum retdata, retkey;
+	datum retkey;
+	DBT dbtretkey, dbtretdata;
 
-	status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_NEXT);
+	status = (db->seq)(db, &dbtretkey, &dbtretdata, R_NEXT);
 	if (status)
-		retkey.dptr = NULL;
+		dbtretkey.data = NULL;
+	retkey.dptr = dbtretkey.data;
+	retkey.dsize = dbtretkey.size;
 	return (retkey);
 }
+
 /*
  * Returns:
  *	 0 on success
@@ -155,8 +167,11 @@ dbm_delete(db, key)
 	datum key;
 {
 	int status;
+	DBT dbtkey;
 
-	status = (db->del)(db, (DBT *)&key, 0);
+	dbtkey.data = key.dptr;
+	dbtkey.size = key.dsize;
+	status = (db->del)(db, &dbtkey, 0);
 	if (status)
 		return (-1);
 	else
@@ -170,12 +185,18 @@ dbm_delete(db, key)
  *	 1 if DBM_INSERT and entry exists
  */
 extern int
-dbm_store(db, key, content, flags)
+dbm_store(db, key, data, flags)
 	DBM *db;
-	datum key, content;
+	datum key, data;
 	int flags;
 {
-	return ((db->put)(db, (DBT *)&key, (DBT *)&content,
+	DBT dbtkey, dbtdata;
+
+	dbtkey.data = key.dptr;
+	dbtkey.size = key.dsize;
+	dbtdata.data = data.dptr;
+	dbtdata.size = data.dsize;
+	return ((db->put)(db, &dbtkey, &dbtdata,
 	    (flags == DBM_INSERT) ? R_NOOVERWRITE : 0));
 }
 
diff --git a/lib/libc/db/hash/page.h b/lib/libc/db/hash/page.h
index ed62d595dc1..0ea00b7aea6 100644
--- a/lib/libc/db/hash/page.h
+++ b/lib/libc/db/hash/page.h
@@ -1,4 +1,4 @@
-/*	$NetBSD: page.h,v 1.5 1995/02/27 13:22:52 cgd Exp $	*/
+/*	$NetBSD: page.h,v 1.6 1996/05/03 21:43:59 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
diff --git a/lib/libc/db/hash/search.h b/lib/libc/db/hash/search.h
index d11ac14eefb..b9f73132d8d 100644
--- a/lib/libc/db/hash/search.h
+++ b/lib/libc/db/hash/search.h
@@ -1,4 +1,4 @@
-/*	$NetBSD: search.h,v 1.5 1995/02/27 13:22:58 cgd Exp $	*/
+/*	$NetBSD: search.h,v 1.6 1996/05/03 21:44:01 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993
diff --git a/lib/libc/db/man/btree.3 b/lib/libc/db/man/btree.3
index f0cd4eba8d6..7c74828975a 100644
--- a/lib/libc/db/man/btree.3
+++ b/lib/libc/db/man/btree.3
@@ -1,4 +1,4 @@
-.\"	$NetBSD: btree.3,v 1.5 1995/02/27 13:23:18 cgd Exp $
+.\"	$NetBSD: btree.3,v 1.6 1996/05/03 21:26:48 cgd Exp $
 .\"
 .\" Copyright (c) 1990, 1993
 .\"	The Regents of the University of California.  All rights reserved.
@@ -31,9 +31,9 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.\"	@(#)btree.3	8.3 (Berkeley) 2/21/94
+.\"	@(#)btree.3	8.4 (Berkeley) 8/18/94
 .\"
-.TH BTREE 3 "February 21, 1994"
+.TH BTREE 3 "August 18, 1994"
 .\".UC 7
 .SH NAME
 btree \- btree database access method
@@ -209,6 +209,13 @@ O lg base N where base is the average fill factor.
 Often, inserting ordered data into btrees results in a low fill factor.
 This implementation has been modified to make ordered insertion the best
 case, resulting in a much better than normal page fill factor.
+.SH ERRORS
+The
+.I btree
+access method routines may fail and set
+.I errno
+for any of the errors specified for the library routine
+.IR dbopen (3).
 .SH "SEE ALSO"
 .IR dbopen (3),
 .IR hash (3),
diff --git a/lib/libc/db/man/hash.3 b/lib/libc/db/man/hash.3
index 6d296a8f6d1..fcdb1f3af12 100644
--- a/lib/libc/db/man/hash.3
+++ b/lib/libc/db/man/hash.3
@@ -1,4 +1,4 @@
-.\"	$NetBSD: hash.3,v 1.5 1995/02/27 13:23:31 cgd Exp $
+.\"	$NetBSD: hash.3,v 1.6 1996/05/03 21:26:50 cgd Exp $
 .\"
 .\" Copyright (c) 1990, 1993
 .\"	The Regents of the University of California.  All rights reserved.
@@ -31,9 +31,9 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.\"	@(#)hash.3	8.5 (Berkeley) 2/21/94
+.\"	@(#)hash.3	8.6 (Berkeley) 8/18/94
 .\"
-.TH HASH 3 "February 21, 1994"
+.TH HASH 3 "August 18, 1994"
 .UC 7
 .SH NAME
 hash \- hash database access method
@@ -139,6 +139,13 @@ and
 .IR ndbm (3)
 are provided, however these interfaces are not compatible with
 previous file formats.
+.SH ERRORS
+The
+.I hash
+access method routines may fail and set
+.I errno
+for any of the errors specified for the library routine
+.IR dbopen (3).
 .SH "SEE ALSO"
 .IR btree (3),
 .IR dbopen (3),
diff --git a/lib/libc/db/man/recno.3 b/lib/libc/db/man/recno.3
index 63a366b645f..1fd42078053 100644
--- a/lib/libc/db/man/recno.3
+++ b/lib/libc/db/man/recno.3
@@ -1,4 +1,4 @@
-.\"	$NetBSD: recno.3,v 1.5 1995/06/13 00:53:40 jtc Exp $
+.\"	$NetBSD: recno.3,v 1.6 1996/05/03 21:26:51 cgd Exp $
 .\"
 .\" Copyright (c) 1990, 1993
 .\"	The Regents of the University of California.  All rights reserved.
@@ -31,9 +31,9 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.\"	@(#)recno.3	8.3 (Berkeley) 2/21/94
+.\"	@(#)recno.3	8.5 (Berkeley) 8/18/94
 .\"
-.TH RECNO 3 "February 21, 1994"
+.TH RECNO 3 "August 18, 1994"
 .UC 7
 .SH NAME
 recno \- record number database access method
@@ -99,6 +99,9 @@ The structure element
 specifies the length of the record, and the structure element
 .I bval
 is used as the pad character.
+Any records, inserted into the database, that are less than
+.I reclen
+bytes long are automatically padded.
 .TP
 R_NOKEY
 In the interface specified by
@@ -178,6 +181,11 @@ The
 .I size
 field of the key should be the size of that type.
 .PP
+Because there can be no meta-data associated with the underlying
+recno access method files, any changes made to the default values
+(e.g. fixed record length or byte separator value) must be explicitly
+specified each time the file is opened.
+.PP
 In the interface specified by
 .IR dbopen ,
 using the
@@ -185,6 +193,18 @@ using the
 interface to create a new record will cause the creation of multiple,
 empty records if the record number is more than one greater than the
 largest record currently in the database.
+.SH ERRORS
+The
+.I recno
+access method routines may fail and set
+.I errno
+for any of the errors specified for the library routine
+.IR dbopen (3)
+or the following:
+.TP
+[EINVAL]
+An attempt was made to add a record to a fixed-length database that
+was too large to fit.
 .SH "SEE ALSO"
 .IR btree (3),
 .IR dbopen (3),
diff --git a/lib/libc/db/mpool/mpool.c b/lib/libc/db/mpool/mpool.c
index 6417c29d453..be04f45e56c 100644
--- a/lib/libc/db/mpool/mpool.c
+++ b/lib/libc/db/mpool/mpool.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: mpool.c,v 1.5 1995/02/27 13:24:05 cgd Exp $	*/
+/*	$NetBSD: mpool.c,v 1.6 1996/05/03 21:29:48 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1990, 1993
+ * 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
@@ -35,13 +35,14 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)mpool.c	8.2 (Berkeley) 2/21/94";
+static char sccsid[] = "@(#)mpool.c	8.5 (Berkeley) 7/26/94";
 #else
-static char rcsid[] = "$NetBSD: mpool.c,v 1.5 1995/02/27 13:24:05 cgd Exp $";
+static char rcsid[] = "$NetBSD: mpool.c,v 1.6 1996/05/03 21:29:48 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
 #include <sys/param.h>
+#include <sys/queue.h>
 #include <sys/stat.h>
 
 #include <errno.h>
@@ -51,31 +52,21 @@ static char rcsid[] = "$NetBSD: mpool.c,v 1.5 1995/02/27 13:24:05 cgd Exp $";
 #include <unistd.h>
 
 #include <db.h>
+
 #define	__MPOOLINTERFACE_PRIVATE
-#include "mpool.h"
+#include <mpool.h>
 
 static BKT *mpool_bkt __P((MPOOL *));
 static BKT *mpool_look __P((MPOOL *, pgno_t));
 static int  mpool_write __P((MPOOL *, BKT *));
-#ifdef DEBUG
-static void __mpoolerr __P((const char *fmt, ...));
-#endif
 
 /*
- * MPOOL_OPEN -- initialize a memory pool.
- *
- * Parameters:
- *	key:		Shared buffer key.
- *	fd:		File descriptor.
- *	pagesize:	File page size.
- *	maxcache:	Max number of cached pages.
- *
- * Returns:
- *	MPOOL pointer, NULL on error.
+ * mpool_open --
+ *	Initialize a memory pool.
  */
 MPOOL *
 mpool_open(key, fd, pagesize, maxcache)
-	DBT *key;
+	void *key;
 	int fd;
 	pgno_t pagesize, maxcache;
 {
@@ -83,49 +74,35 @@ mpool_open(key, fd, pagesize, maxcache)
 	MPOOL *mp;
 	int entry;
 
+	/*
+	 * Get information about the file.
+	 *
+	 * XXX
+	 * We don't currently handle pipes, although we should.
+	 */
 	if (fstat(fd, &sb))
 		return (NULL);
-	/* XXX
-	 * We should only set st_size to 0 for pipes -- 4.4BSD has the fix so
-	 * that stat(2) returns true for ISSOCK on pipes.  Until then, this is
-	 * fairly close.
-	 */
 	if (!S_ISREG(sb.st_mode)) {
 		errno = ESPIPE;
 		return (NULL);
 	}
 
-	if ((mp = (MPOOL *)malloc(sizeof(MPOOL))) == NULL)
+	/* Allocate and initialize the MPOOL cookie. */
+	if ((mp = (MPOOL *)calloc(1, sizeof(MPOOL))) == NULL)
 		return (NULL);
-	mp->free.cnext = mp->free.cprev = (BKT *)&mp->free;
-	mp->lru.cnext = mp->lru.cprev = (BKT *)&mp->lru;
+	CIRCLEQ_INIT(&mp->lqh);
 	for (entry = 0; entry < HASHSIZE; ++entry)
-		mp->hashtable[entry].hnext = mp->hashtable[entry].hprev = 
-		    mp->hashtable[entry].cnext = mp->hashtable[entry].cprev =
-		    (BKT *)&mp->hashtable[entry];
-	mp->curcache = 0;
+		CIRCLEQ_INIT(&mp->hqh[entry]);
 	mp->maxcache = maxcache;
-	mp->pagesize = pagesize;
 	mp->npages = sb.st_size / pagesize;
+	mp->pagesize = pagesize;
 	mp->fd = fd;
-	mp->pgcookie = NULL;
-	mp->pgin = mp->pgout = NULL;
-
-#ifdef STATISTICS
-	mp->cachehit = mp->cachemiss = mp->pagealloc = mp->pageflush = 
-	    mp->pageget = mp->pagenew = mp->pageput = mp->pageread = 
-	    mp->pagewrite = 0;
-#endif
 	return (mp);
 }
 
 /*
- * MPOOL_FILTER -- initialize input/output filters.
- *
- * Parameters:
- *	pgin:		Page in conversion routine.
- *	pgout:		Page out conversion routine.
- *	pgcookie:	Cookie for page in/out routines.
+ * mpool_filter --
+ *	Initialize input/output filters.
  */
 void
 mpool_filter(mp, pgin, pgout, pgcookie)
@@ -140,124 +117,128 @@ mpool_filter(mp, pgin, pgout, pgcookie)
 }
 	
 /*
- * MPOOL_NEW -- get a new page
- *
- * Parameters:
- *	mp:		mpool cookie
- *	pgnoadddr:	place to store new page number
- * Returns:
- *	RET_ERROR, RET_SUCCESS
+ * mpool_new --
+ *	Get a new page of memory.
  */
 void *
 mpool_new(mp, pgnoaddr)
 	MPOOL *mp;
 	pgno_t *pgnoaddr;
 {
-	BKT *b;
-	BKTHDR *hp;
+	struct _hqh *head;
+	BKT *bp;
 
+	if (mp->npages == MAX_PAGE_NUMBER) {
+		(void)fprintf(stderr, "mpool_new: page allocation overflow.\n");
+		abort();
+	}
 #ifdef STATISTICS
 	++mp->pagenew;
 #endif
 	/*
-	 * Get a BKT from the cache.  Assign a new page number, attach it to
-	 * the hash and lru chains and return.
+	 * Get a BKT from the cache.  Assign a new page number, attach
+	 * it to the head of the hash chain, the tail of the lru chain,
+	 * and return.
 	 */
-	if ((b = mpool_bkt(mp)) == NULL)
+	if ((bp = mpool_bkt(mp)) == NULL)
 		return (NULL);
-	*pgnoaddr = b->pgno = mp->npages++;
-	b->flags = MPOOL_PINNED;
-	inshash(b, b->pgno);
-	inschain(b, &mp->lru);
-	return (b->page);
+	*pgnoaddr = bp->pgno = mp->npages++;
+	bp->flags = MPOOL_PINNED;
+
+	head = &mp->hqh[HASHKEY(bp->pgno)];
+	CIRCLEQ_INSERT_HEAD(head, bp, hq);
+	CIRCLEQ_INSERT_TAIL(&mp->lqh, bp, q);
+	return (bp->page);
 }
 
 /*
- * MPOOL_GET -- get a page from the pool
- *
- * Parameters:
- *	mp:	mpool cookie
- *	pgno:	page number
- *	flags:	not used
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
+ * mpool_get
+ *	Get a page.
  */
 void *
 mpool_get(mp, pgno, flags)
 	MPOOL *mp;
 	pgno_t pgno;
-	u_int flags;		/* XXX not used? */
+	u_int flags;				/* XXX not used? */
 {
-	BKT *b;
-	BKTHDR *hp;
+	struct _hqh *head;
+	BKT *bp;
 	off_t off;
 	int nr;
 
-	/*
-	 * If asking for a specific page that is already in the cache, find
-	 * it and return it.
-	 */
-	if (b = mpool_look(mp, pgno)) {
+	/* Check for attempt to retrieve a non-existent page. */
+	if (pgno >= mp->npages) {
+		errno = EINVAL;
+		return (NULL);
+	}
+
 #ifdef STATISTICS
-		++mp->pageget;
+	++mp->pageget;
 #endif
+
+	/* Check for a page that is cached. */
+	if ((bp = mpool_look(mp, pgno)) != NULL) {
 #ifdef DEBUG
-		if (b->flags & MPOOL_PINNED)
-			__mpoolerr("mpool_get: page %d already pinned",
-			    b->pgno);
+		if (bp->flags & MPOOL_PINNED) {
+			(void)fprintf(stderr,
+			    "mpool_get: page %d already pinned\n", bp->pgno);
+			abort();
+		}
 #endif
-		rmchain(b);
-		inschain(b, &mp->lru);
-		b->flags |= MPOOL_PINNED;
-		return (b->page);
-	}
-
-	/* Not allowed to retrieve a non-existent page. */
-	if (pgno >= mp->npages) {
-		errno = EINVAL;
-		return (NULL);
+		/*
+		 * Move the page to the head of the hash chain and the tail
+		 * of the lru chain.
+		 */
+		head = &mp->hqh[HASHKEY(bp->pgno)];
+		CIRCLEQ_REMOVE(head, bp, hq);
+		CIRCLEQ_INSERT_HEAD(head, bp, hq);
+		CIRCLEQ_REMOVE(&mp->lqh, bp, q);
+		CIRCLEQ_INSERT_TAIL(&mp->lqh, bp, q);
+
+		/* Return a pinned page. */
+		bp->flags |= MPOOL_PINNED;
+		return (bp->page);
 	}
 
 	/* Get a page from the cache. */
-	if ((b = mpool_bkt(mp)) == NULL)
+	if ((bp = mpool_bkt(mp)) == NULL)
 		return (NULL);
-	b->pgno = pgno;
-	b->flags = MPOOL_PINNED;
 
+	/* Read in the contents. */
 #ifdef STATISTICS
 	++mp->pageread;
 #endif
-	/* Read in the contents. */
 	off = mp->pagesize * pgno;
 	if (lseek(mp->fd, off, SEEK_SET) != off)
 		return (NULL);
-	if ((nr = read(mp->fd, b->page, mp->pagesize)) != mp->pagesize) {
+	if ((nr = read(mp->fd, bp->page, mp->pagesize)) != mp->pagesize) {
 		if (nr >= 0)
 			errno = EFTYPE;
 		return (NULL);
 	}
-	if (mp->pgin)
-		(mp->pgin)(mp->pgcookie, b->pgno, b->page);
 
-	inshash(b, b->pgno);
-	inschain(b, &mp->lru);
-#ifdef STATISTICS
-	++mp->pageget;
-#endif
-	return (b->page);
+	/* Set the page number, pin the page. */
+	bp->pgno = pgno;
+	bp->flags = MPOOL_PINNED;
+
+	/*
+	 * Add the page to the head of the hash chain and the tail
+	 * of the lru chain.
+	 */
+	head = &mp->hqh[HASHKEY(bp->pgno)];
+	CIRCLEQ_INSERT_HEAD(head, bp, hq);
+	CIRCLEQ_INSERT_TAIL(&mp->lqh, bp, q);
+
+	/* Run through the user's filter. */
+	if (mp->pgin != NULL)
+		(mp->pgin)(mp->pgcookie, bp->pgno, bp->page);
+
+	return (bp->page);
 }
 
 /*
- * MPOOL_PUT -- return a page to the pool
- *
- * Parameters:
- *	mp:	mpool cookie
- *	page:	page pointer
- *	pgno:	page number
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
+ * mpool_put
+ *	Return a page.
  */
 int
 mpool_put(mp, page, flags)
@@ -265,193 +246,172 @@ mpool_put(mp, page, flags)
 	void *page;
 	u_int flags;
 {
-	BKT *baddr;
-#ifdef DEBUG
-	BKT *b;
-#endif
+	BKT *bp;
 
 #ifdef STATISTICS
 	++mp->pageput;
 #endif
-	baddr = (BKT *)((char *)page - sizeof(BKT));
+	bp = (BKT *)((char *)page - sizeof(BKT));
 #ifdef DEBUG
-	if (!(baddr->flags & MPOOL_PINNED))
-		__mpoolerr("mpool_put: page %d not pinned", b->pgno);
-	for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) {
-		if (b == (BKT *)&mp->lru)
-			__mpoolerr("mpool_put: %0x: bad address", baddr);
-		if (b == baddr)
-			break;
+	if (!(bp->flags & MPOOL_PINNED)) {
+		(void)fprintf(stderr,
+		    "mpool_put: page %d not pinned\n", bp->pgno);
+		abort();
 	}
 #endif
-	baddr->flags &= ~MPOOL_PINNED;
-	baddr->flags |= flags & MPOOL_DIRTY;
+	bp->flags &= ~MPOOL_PINNED;
+	bp->flags |= flags & MPOOL_DIRTY;
 	return (RET_SUCCESS);
 }
 
 /*
- * MPOOL_CLOSE -- close the buffer pool
- *
- * Parameters:
- *	mp:	mpool cookie
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
+ * mpool_close
+ *	Close the buffer pool.
  */
 int
 mpool_close(mp)
 	MPOOL *mp;
 {
-	BKT *b, *next;
+	BKT *bp;
 
 	/* Free up any space allocated to the lru pages. */
-	for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = next) {
-		next = b->cprev;
-		free(b);
+	while ((bp = mp->lqh.cqh_first) != (void *)&mp->lqh) {
+		CIRCLEQ_REMOVE(&mp->lqh, mp->lqh.cqh_first, q);
+		free(bp);
 	}
+
+	/* Free the MPOOL cookie. */
 	free(mp);
 	return (RET_SUCCESS);
 }
 
 /*
- * MPOOL_SYNC -- sync the file to disk.
- *
- * Parameters:
- *	mp:	mpool cookie
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
+ * mpool_sync
+ *	Sync the pool to disk.
  */
 int
 mpool_sync(mp)
 	MPOOL *mp;
 {
-	BKT *b;
+	BKT *bp;
 
-	for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev)
-		if (b->flags & MPOOL_DIRTY && mpool_write(mp, b) == RET_ERROR)
+	/* Walk the lru chain, flushing any dirty pages to disk. */
+	for (bp = mp->lqh.cqh_first;
+	    bp != (void *)&mp->lqh; bp = bp->q.cqe_next)
+		if (bp->flags & MPOOL_DIRTY &&
+		    mpool_write(mp, bp) == RET_ERROR)
 			return (RET_ERROR);
+
+	/* Sync the file descriptor. */
 	return (fsync(mp->fd) ? RET_ERROR : RET_SUCCESS);
 }
 
 /*
- * MPOOL_BKT -- get/create a BKT from the cache
- *
- * Parameters:
- *	mp:	mpool cookie
- *
- * Returns:
- *	NULL on failure and a pointer to the BKT on success	
+ * mpool_bkt
+ *	Get a page from the cache (or create one).
  */
 static BKT *
 mpool_bkt(mp)
 	MPOOL *mp;
 {
-	BKT *b;
+	struct _hqh *head;
+	BKT *bp;
 
+	/* If under the max cached, always create a new page. */
 	if (mp->curcache < mp->maxcache)
 		goto new;
 
 	/*
-	 * If the cache is maxxed out, search the lru list for a buffer we
-	 * can flush.  If we find one, write it if necessary and take it off
-	 * any lists.  If we don't find anything we grow the cache anyway.
+	 * If the cache is max'd out, walk the lru list for a buffer we
+	 * can flush.  If we find one, write it (if necessary) and take it
+	 * off any lists.  If we don't find anything we grow the cache anyway.
 	 * The cache never shrinks.
 	 */
-	for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev)
-		if (!(b->flags & MPOOL_PINNED)) {
-			if (b->flags & MPOOL_DIRTY &&
-			    mpool_write(mp, b) == RET_ERROR)
+	for (bp = mp->lqh.cqh_first;
+	    bp != (void *)&mp->lqh; bp = bp->q.cqe_next)
+		if (!(bp->flags & MPOOL_PINNED)) {
+			/* Flush if dirty. */
+			if (bp->flags & MPOOL_DIRTY &&
+			    mpool_write(mp, bp) == RET_ERROR)
 				return (NULL);
-			rmhash(b);
-			rmchain(b);
 #ifdef STATISTICS
 			++mp->pageflush;
 #endif
+			/* Remove from the hash and lru queues. */
+			head = &mp->hqh[HASHKEY(bp->pgno)];
+			CIRCLEQ_REMOVE(head, bp, hq);
+			CIRCLEQ_REMOVE(&mp->lqh, bp, q);
 #ifdef DEBUG
-			{
-				void *spage;
-				spage = b->page;
-				memset(b, 0xff, sizeof(BKT) + mp->pagesize);
-				b->page = spage;
+			{ void *spage;
+				spage = bp->page;
+				memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
+				bp->page = spage;
 			}
 #endif
-			return (b);
+			return (bp);
 		}
 
-new:	if ((b = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL)
+new:	if ((bp = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL)
 		return (NULL);
 #ifdef STATISTICS
 	++mp->pagealloc;
 #endif
-#ifdef DEBUG
-	memset(b, 0xff, sizeof(BKT) + mp->pagesize);
+#if defined(DEBUG) || defined(PURIFY)
+	memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
 #endif
-	b->page = (char *)b + sizeof(BKT);
+	bp->page = (char *)bp + sizeof(BKT);
 	++mp->curcache;
-	return (b);
+	return (bp);
 }
 
 /*
- * MPOOL_WRITE -- sync a page to disk
- *
- * Parameters:
- *	mp:	mpool cookie
- *
- * Returns:
- *	RET_ERROR, RET_SUCCESS
+ * mpool_write
+ *	Write a page to disk.
  */
 static int
-mpool_write(mp, b)
+mpool_write(mp, bp)
 	MPOOL *mp;
-	BKT *b;
+	BKT *bp;
 {
 	off_t off;
 
-	if (mp->pgout)
-		(mp->pgout)(mp->pgcookie, b->pgno, b->page);
-
 #ifdef STATISTICS
 	++mp->pagewrite;
 #endif
-	off = mp->pagesize * b->pgno;
+
+	/* Run through the user's filter. */
+	if (mp->pgout)
+		(mp->pgout)(mp->pgcookie, bp->pgno, bp->page);
+
+	off = mp->pagesize * bp->pgno;
 	if (lseek(mp->fd, off, SEEK_SET) != off)
 		return (RET_ERROR);
-	if (write(mp->fd, b->page, mp->pagesize) != mp->pagesize)
+	if (write(mp->fd, bp->page, mp->pagesize) != mp->pagesize)
 		return (RET_ERROR);
-	b->flags &= ~MPOOL_DIRTY;
+
+	bp->flags &= ~MPOOL_DIRTY;
 	return (RET_SUCCESS);
 }
 
 /*
- * MPOOL_LOOK -- lookup a page
- *
- * Parameters:
- *	mp:	mpool cookie
- *	pgno:	page number
- *
- * Returns:
- *	NULL on failure and a pointer to the BKT on success
+ * mpool_look
+ *	Lookup a page in the cache.
  */
 static BKT *
 mpool_look(mp, pgno)
 	MPOOL *mp;
 	pgno_t pgno;
 {
-	register BKT *b;
-	register BKTHDR *tb;
+	struct _hqh *head;
+	BKT *bp;
 
-	/* XXX
-	 * If find the buffer, put it first on the hash chain so can
-	 * find it again quickly.
-	 */
-	tb = &mp->hashtable[HASHKEY(pgno)];
-	for (b = tb->hnext; b != (BKT *)tb; b = b->hnext)
-		if (b->pgno == pgno) {
+	head = &mp->hqh[HASHKEY(pgno)];
+	for (bp = head->cqh_first; bp != (void *)head; bp = bp->hq.cqe_next)
+		if (bp->pgno == pgno) {
 #ifdef STATISTICS
 			++mp->cachehit;
 #endif
-			return (b);
+			return (bp);
 		}
 #ifdef STATISTICS
 	++mp->cachemiss;
@@ -461,16 +421,14 @@ mpool_look(mp, pgno)
 
 #ifdef STATISTICS
 /*
- * MPOOL_STAT -- cache statistics
- *
- * Parameters:
- *	mp:	mpool cookie
+ * mpool_stat
+ *	Print out cache statistics.
  */
 void
 mpool_stat(mp)
 	MPOOL *mp;
 {
-	BKT *b;
+	BKT *bp;
 	int cnt;
 	char *sep;
 
@@ -492,11 +450,12 @@ mpool_stat(mp)
 
 	sep = "";
 	cnt = 0;
-	for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) {
-		(void)fprintf(stderr, "%s%d", sep, b->pgno);
-		if (b->flags & MPOOL_DIRTY)
+	for (bp = mp->lqh.cqh_first;
+	    bp != (void *)&mp->lqh; bp = bp->q.cqe_next) {
+		(void)fprintf(stderr, "%s%d", sep, bp->pgno);
+		if (bp->flags & MPOOL_DIRTY)
 			(void)fprintf(stderr, "d");
-		if (b->flags & MPOOL_PINNED)
+		if (bp->flags & MPOOL_PINNED)
 			(void)fprintf(stderr, "P");
 		if (++cnt == 10) {
 			sep = "\n";
@@ -508,33 +467,3 @@ mpool_stat(mp)
 	(void)fprintf(stderr, "\n");
 }
 #endif
-
-#ifdef DEBUG
-#if __STDC__
-#include <stdarg.h>
-#else
-#include <varargs.h>
-#endif
-
-static void
-#if __STDC__
-__mpoolerr(const char *fmt, ...)
-#else
-__mpoolerr(fmt, va_alist)
-	char *fmt;
-	va_dcl
-#endif
-{
-	va_list ap;
-#if __STDC__
-	va_start(ap, fmt);
-#else
-	va_start(ap);
-#endif
-	(void)vfprintf(stderr, fmt, ap);
-	va_end(ap);
-	(void)fprintf(stderr, "\n");
-	abort();
-	/* NOTREACHED */
-}
-#endif
diff --git a/lib/libc/db/mpool/mpool.libtp b/lib/libc/db/mpool/mpool.libtp
new file mode 100644
index 00000000000..3ab0c8f835c
--- /dev/null
+++ b/lib/libc/db/mpool/mpool.libtp
@@ -0,0 +1,746 @@
+/******************************************************************************
+
+VERSION $Id: mpool.libtp,v 1.1 1996/05/07 09:02:01 deraadt Exp $
+PACKAGE: 	User Level Shared Memory Manager
+
+DESCRIPTION: 	
+	This package provides a buffer pool interface implemented as
+	a collection of file pages mapped into shared memory.
+
+	Based on Mark's buffer manager
+
+ROUTINES: 
+    External
+	buf_alloc
+	buf_flags
+	buf_get
+	buf_init
+	buf_last
+	buf_open
+	buf_pin
+	buf_sync
+	buf_unpin
+    Internal
+	bf_assign_buf
+	bf_fid_to_fd
+	bf_newbuf
+	bf_put_page
+	
+
+******************************************************************************/
+#include	<sys/types.h>
+#include	<assert.h>
+#include	<sys/file.h>
+#include	<sys/stat.h>
+#include	<stdio.h>
+#include	<errno.h>
+#include	"list.h"
+#include	"user.h"
+#include	"txn_sys.h"
+#include	"buf.h"
+#include	"semkeys.h"
+#include	"error.h"
+
+/*
+    we need to translate between some type of file id that the user 
+    process passes and a file descriptor.  For now, it's a nop.
+*/
+#define GET_MASTER      get_sem ( buf_spinlock )
+#define RELEASE_MASTER  release_sem ( buf_spinlock )
+
+#define	LRUID	*buf_lru
+#define	LRUP	(bufhdr_table+*buf_lru)
+#define	MRU	bufhdr_table[*buf_lru].lru.prev
+
+/* Global indicator that you have started reusing buffers */
+int	do_statistics = 0;
+/*
+    Process Statics (pointers into shared memory)
+*/
+static	BUF_T	*buf_table = 0;
+static	BUFHDR_T	*bufhdr_table;
+static	int	*buf_hash_table;
+static	int	*buf_lru;		/* LRU is the free list */
+static	int	buf_spinlock;
+static	FINFO_T	*buf_fids;
+static	int	*buf_sp;		/* Pointer to string free space */
+static	char	*buf_strings;
+
+/* Process Local FID->FD table */
+static	int	fds[NUM_FILE_ENTRIES];
+
+/* Static routines */
+static	BUFHDR_T	*bf_assign_buf();
+static	int		bf_fid_to_fd();
+static	BUFHDR_T	*bf_newbuf();
+static	int		bf_put_page();
+
+/*
+    Return  0 on success
+	    1 on failure
+*/
+extern int
+buf_init ( )
+{
+    ADDR_T	buf_region;
+    BUFHDR_T	*bhp;
+    int		i;
+    int		ref_count;
+    int		*spinlockp;
+
+    /*
+	Initialize Process local structures
+    */
+    for ( i = 0; i < NUM_FILE_ENTRIES; i++ ) {
+	fds[i] = -1;
+    }
+
+    buf_region = attach_region ( BUF_REGION_NAME, BUF_REGION_NUM,
+				 BUF_REGION_SIZE, &ref_count );
+    if ( !buf_region ) {
+	return (1);
+    }
+    error_log3 ( "Buf Region: ADDR: %d ID: %d SIZE: %d\n", buf_region,
+		    BUF_REGION_NUM, BUF_REGION_SIZE );
+
+    buf_table = (BUF_T *)buf_region;
+    bufhdr_table = (BUFHDR_T *)(buf_table + NUM_BUFS);
+    buf_hash_table = (int *)(bufhdr_table + NUM_BUFS);
+    buf_lru = buf_hash_table + NUMTABLE_ENTRIES;
+    spinlockp = buf_lru + 1;
+    buf_fids = (FINFO_T *)(spinlockp+1);
+    buf_sp = (int *)(buf_fids + NUM_FILE_ENTRIES);
+    buf_strings = (char *)(buf_sp + 1);
+
+    /* Create locking spinlock (gets creating holding the lock) */
+    buf_spinlock = create_sem ( BUF_SPIN_NAME, BUF_SPIN_NUM, ref_count <= 1 );
+    if ( buf_spinlock < 0 )  {
+	return(1);
+    }
+    if ( ref_count <= 1 ) {
+	*spinlockp = buf_spinlock;
+
+	/* Now initialize the buffer manager */
+
+	/* 1. Free list */
+	*buf_lru = 0;
+
+	/* 2. Buffer headers */
+	for ( i = 0, bhp = bufhdr_table; i < NUM_BUFS; bhp++, i++ ) {
+		bhp->lru.next = i+1;
+		bhp->lru.prev = i-1;
+		bhp->flags = 0;				/* All Flags off */
+		bhp->refcount = 0;
+		bhp->wait_proc = -1;			/* No sleepers */
+		LISTPE_INIT ( hash, bhp, i );		/* Hash chains */
+	}
+	bufhdr_table[0].lru.prev = NUM_BUFS-1;
+	bufhdr_table[NUM_BUFS-1].lru.next = 0;
+
+	/* 3. Hash Table */
+	for ( i = 0; i < NUMTABLE_ENTRIES; i++ ) {
+		buf_hash_table[i] = NUM_BUFS;
+	}
+
+	/* 4. File ID Table */
+	for ( i = 0; i < NUM_FILE_ENTRIES; i++ ) {
+		buf_fids[i].offset = -1;
+		buf_fids[i].npages = -1;
+		buf_fids[i].refcount = 0;
+	}
+
+	/* 5. Free String Pointer */
+	*buf_sp = (FILE_NAME_LEN*NUM_FILE_ENTRIES);
+	if (RELEASE_MASTER) {
+		return(1);
+	}
+	error_log0 ( "Initialized buffer region\n" );
+    } 
+    return (0);
+}
+
+extern	void
+buf_exit()
+{
+    int	ref;
+    int	i;
+
+    /* Flush Buffer Pool on Exit */
+    for ( i = 0; i < NUM_FILE_ENTRIES; i++ ) {
+	if ( fds[i] != -1 ) {
+		close ( fds[i] );
+	}
+    }
+    if ( buf_table ) {
+	detach_region ( buf_table, BUF_REGION_NUM, BUF_REGION_SIZE, &ref );
+    }
+    return;
+}
+
+/*
+	We need an empty buffer.  Find the LRU unpinned NON-Dirty page.
+*/
+static BUFHDR_T	*
+bf_newbuf()
+{
+    int		fd;
+    int		lruid;
+    int		nbytes;
+    int		ndx;
+    BUFHDR_T	*bhp;
+
+    lruid = LRUID;
+    for ( bhp = LRUP; 
+	  bhp->flags & (BUF_PINNED|BUF_IO_IN_PROGRESS); 
+	  bhp = LISTP_NEXTP (bufhdr_table, lru, bhp ) ) {
+
+	if ( bhp->lru.next == lruid ) {
+		/* OUT OF BUFFERS */
+		error_log1 ( "All buffers are pinned.  %s\n",
+				"Unable to grant buffer request" );
+		return(NULL);
+	}
+    }
+    /* BHP can be used */
+    if ( bhp->flags & BUF_DIRTY ) {
+	do_statistics = 1;
+	/* 
+	    MIS  Check for log flushed appropriately
+	*/
+	fd = bf_fid_to_fd(bhp->id.file_id);
+	if ( fd == -1 ) {
+	    error_log1 ("Invalid fid %d\n", bhp->id.file_id);
+	    return(NULL);
+	}
+	if ( bf_put_page(fd, bhp) < 0 ) {
+	    return(NULL);
+	}
+    }
+    /* Update Hash Pointers */
+    ndx = BUF_HASH ( bhp->id.file_id, bhp->id.obj_id );
+    LISTP_REMOVE(bufhdr_table, hash, bhp);
+    if ( buf_hash_table[ndx] == (bhp-bufhdr_table) ) {
+	if ( bhp->hash.next != (bhp-bufhdr_table) ) {
+		buf_hash_table[ndx] = bhp->hash.next;
+	} else {
+		buf_hash_table[ndx] = NUM_BUFS;
+	}
+    }
+    INIT_BUF(bhp); 
+
+    return(bhp);
+}
+/*
+    buf_alloc
+
+    Add a page to a file and return a buffer for it.
+
+*/
+ADDR_T
+buf_alloc ( fid, new_pageno )
+int	fid;
+int	*new_pageno;
+{
+	BUFHDR_T	*bhp;
+	int	fd;
+	int	len;
+	int	ndx;
+	OBJ_T	fobj;
+
+	if (GET_MASTER) {
+		return(NULL);
+	}
+	if ( buf_fids[fid].npages == -1 ) {
+	    /* initialize npages field */
+	    fd = bf_fid_to_fd ( fid );
+	}
+	assert (fid < NUM_FILE_ENTRIES);
+
+	*new_pageno = buf_fids[fid].npages;
+	if ( *new_pageno == -1 ) {
+	    RELEASE_MASTER;
+	    return ( NULL );
+	}
+	buf_fids[fid].npages++;
+	ndx = BUF_HASH ( fid, *new_pageno );
+	fobj.file_id = fid;
+	fobj.obj_id  = *new_pageno;
+	bhp = bf_assign_buf ( ndx, &fobj, BF_PIN|BF_DIRTY|BF_EMPTY, &len );
+	if ( RELEASE_MASTER ) {
+		/* Memory leak */
+		return(NULL);
+	}
+	if ( bhp ) {
+	    return ((ADDR_T)(buf_table+(bhp-bufhdr_table)));
+	} else {
+	    return ( NULL );
+	}
+}
+
+
+/*
+	Buffer Flags
+	BF_DIRTY		Mark page as dirty
+	BF_EMPTY		Don't initialize page, just get buffer
+	BF_PIN			Retrieve with pin 
+
+MIS
+Might want to add a flag that sets an LSN for this buffer is the
+DIRTY flag is set
+
+Eventually, you may want a flag that indicates the I/O and lock
+request should be shipped off together, but not for now.
+*/
+extern ADDR_T
+buf_get ( file_id, page_id, flags, len )
+int	file_id;
+int	page_id;
+u_long	flags;
+int	*len;		/* Number of bytes read into buffer */
+{
+	BUFHDR_T	*bhp;
+	int		bufid;
+	int		fd;
+	int		ndx;
+	int		next_bufid;
+	int		stat;
+	OBJ_T		fobj;	
+
+	ndx = BUF_HASH ( file_id, page_id );
+	fobj.file_id = (long) file_id;
+	fobj.obj_id = (long) page_id;
+	if ( GET_MASTER ) {
+		return(NULL);
+	}
+	/*
+		This could be a for loop, but we lose speed
+		by making all the cases general purpose so we
+		optimize for the no-collision case. 
+	*/
+	bufid = buf_hash_table[ndx]; 
+	if ( bufid < NUM_BUFS ) {
+	    for ( bhp = bufhdr_table+bufid; 
+		  !OBJ_EQ (bhp->id, fobj) || !(bhp->flags & BUF_VALID);
+		  bhp = LISTP_NEXTP ( bufhdr_table, hash, bhp ) ) {
+
+		if ( bhp->hash.next == bufid ) {
+		    goto not_found;
+		}
+	    }
+/* found */
+	    if ( flags & BF_PIN ) {
+		    bhp->flags |= BUF_PINNED;
+		    bhp->refcount++;
+#ifdef PIN_DEBUG
+	fprintf(stderr, "buf_get: %X PINNED (%d)\n", 
+			buf_table + (bhp-bufhdr_table), bhp->refcount);
+#endif
+	    }
+	    if ( flags & BF_DIRTY ) {
+		    bhp->flags |= BUF_DIRTY;
+	    }
+
+	    while ( bhp->flags & BUF_IO_IN_PROGRESS ) {
+		/* MIS -- eventually err check here */
+#ifdef DEBUG
+		printf("About to sleep on %d (me: %d\n)\n", bhp->wait_proc,
+			my_txnp - txn_table);
+#endif
+#ifdef WAIT_STATS
+		buf_waits++;
+#endif
+		stat = proc_sleep_on ( &(bhp->wait_proc), buf_spinlock );
+		if ( stat ) {
+			/* Memory leak */
+			return(NULL);
+		}
+		if (!( bhp->flags & BUF_IO_IN_PROGRESS) &&
+		    (!OBJ_EQ (bhp->id, fobj) || !(bhp->flags & BUF_VALID))) {
+			if (RELEASE_MASTER)
+				return(NULL);
+			return(buf_get ( file_id, page_id, flags, len ));
+		}
+	    }
+	    MAKE_MRU( bhp );
+	    *len = BUFSIZE;
+	} else {
+not_found:
+	    /* If you get here, the page isn't in the hash table */
+	    bhp = bf_assign_buf ( ndx, &fobj, flags, len );
+	}
+	/* Common code between found and not found */
+
+	if ( bhp && bhp->flags & BUF_NEWPAGE ) {
+	    *len = 0;
+	}
+	if (RELEASE_MASTER){
+		/* Memory leak */
+		return(NULL);
+	}
+	if ( bhp ) {
+	    return ((ADDR_T)(buf_table+(bhp-bufhdr_table)));
+	} else {
+	    return ( NULL );
+	}
+}
+
+/*
+	MIS - do I want to add file links to buffer pool?
+*/
+extern int
+buf_sync ( fid, close )
+int	fid;
+int	close;		/* should we dec refcount and possibly
+			   invalidate all the buffers */
+{
+    int	i;
+    int	fd;
+    int	invalidate;
+    BUFHDR_T	*bhp;
+
+    if ( (fd = bf_fid_to_fd ( fid )) < 0 ) {
+	return(1);
+    }
+    if (GET_MASTER) {
+	return(1);
+    }
+    invalidate = (buf_fids[fid].refcount == 1 && close);
+    if ( invalidate )
+	for ( bhp = bufhdr_table, i = 0; i < NUM_BUFS; bhp++, i++ ) {
+	    if (bhp->id.file_id == fid) {
+		if ((bhp->flags & BF_DIRTY) && (bf_put_page( fd, bhp ) < 0)) {
+			return(1);
+		}
+		bhp->id.file_id = -1;
+	    }
+	}
+    if (invalidate || close)
+	buf_fids[fid].refcount--;
+
+    if (RELEASE_MASTER) {
+	return(1);
+    }
+    return(0);
+
+
+}
+
+extern int
+buf_flags ( addr, set_flags, unset_flags )
+ADDR_T	addr;
+u_long	set_flags;
+u_long	unset_flags;
+{
+    int		bufid;
+    BUFHDR_T	*bhp;
+
+#ifdef PIN_DEBUG
+	fprintf(stderr, "buf_flags: %X setting %s%s%s%s%s releasing %s%s%s%s%s\n",
+	    addr, 
+	    set_flags&BUF_DIRTY ? "DIRTY " : "", 
+	    set_flags&BUF_VALID ? "VALID " : "", 
+	    set_flags&BUF_PINNED ? "PINNED " : "", 
+	    set_flags&BUF_IO_ERROR ? "IO_ERROR " : "", 
+	    set_flags&BUF_IO_IN_PROGRESS ? "IO_IN_PROG " : "", 
+	    set_flags&BUF_NEWPAGE ? "NEWPAGE " : "", 
+	    unset_flags&BUF_DIRTY ? "DIRTY " : "", 
+	    unset_flags&BUF_VALID ? "VALID " : "", 
+	    unset_flags&BUF_PINNED ? "PINNED " : "", 
+	    unset_flags&BUF_IO_ERROR ? "IO_ERROR " : "", 
+	    unset_flags&BUF_IO_IN_PROGRESS ? "IO_IN_PROG " : "", 
+	    unset_flags&BUF_NEWPAGE ? "NEWPAGE " : "" );
+#endif
+    if (!ADDR_OK(addr)) {
+	error_log1 ( "buf_pin: Invalid Buffer Address %x\n", addr );
+	return(1);
+    }
+    bufid = ((BUF_T *)addr) - buf_table;
+    assert ( bufid < NUM_BUFS);
+    bhp = &bufhdr_table[bufid];
+    if (GET_MASTER) {
+	return(1);
+    }
+    bhp->flags |= set_flags;
+    if ( set_flags & BUF_PINNED ) {
+	bhp->refcount++;
+    }
+    if ( set_flags & BUF_DIRTY ) {
+	unset_flags |= BUF_NEWPAGE;
+    }
+
+    if ( unset_flags & BUF_PINNED ) {
+	bhp->refcount--;
+	if ( bhp->refcount ) {
+		/* Turn off pin bit so it doesn't get unset */
+		unset_flags &= ~BUF_PINNED;
+	}
+    }
+    bhp->flags &= ~unset_flags;
+    MAKE_MRU(bhp);
+    if (RELEASE_MASTER) {
+	return(1);
+    }
+    return(0);
+}
+
+/*
+	Take a string name and produce an fid.
+
+	returns -1 on error
+
+	MIS -- this is a potential problem -- you keep actual names
+		here -- what if people run from different directories?
+*/
+extern	int
+buf_name_lookup ( fname )
+char	*fname;
+{
+    int	i;
+    int	fid;
+    int	ndx;
+
+    fid = -1;
+    if (GET_MASTER) {
+	    return(-1);
+    }
+    for ( i = 0; i < NUM_FILE_ENTRIES; i++ ) {
+	if ( buf_fids[i].offset == -1 ) {
+		fid = i;
+	} else {
+		if (!strcmp (fname, buf_strings+buf_fids[i].offset)) {
+			if (RELEASE_MASTER) {
+				return(-1);
+			}
+			buf_fids[i].refcount++;
+			return(i);
+		}
+	}
+    }
+    if ( fid == -1 ) {
+	error_log0 ( "No more file ID's\n" );
+    } else {
+	ndx = *buf_sp - strlen(fname) - 1;
+	if ( ndx < 0 ) {
+	    error_log0 ( "Out of string space\n" );
+	    fid = -1;
+	} else {
+	    *buf_sp = ndx;
+	    strcpy ( buf_strings+ndx, fname );
+	    buf_fids[fid].offset = ndx;
+	}
+	buf_fids[fid].refcount = 1;
+    }
+    if (RELEASE_MASTER) {
+	return(-1);
+    }
+    return(fid);
+}
+
+static	int
+bf_fid_to_fd ( fid ) 
+int	fid;
+{
+	struct stat sbuf;
+
+	assert ( (fid < NUM_FILE_ENTRIES) && (buf_fids[fid].offset != -1) );
+	if ( fds[fid] != -1 ) {
+	    return(fds[fid]);
+
+	}
+	fds[fid] = open ( buf_strings+buf_fids[fid].offset, O_RDWR|O_CREAT, 
+			  0666 );
+	if ( fds[fid] < 0 ) {
+	    error_log3 ( "Error Opening File %s FID: %d FD: %d.  Errno = %d\n", 
+			    buf_strings+buf_fids[fid].offset, fid, fds[fid], 
+			    errno );
+	    return(-1);
+	}
+	error_log3 ( "Opening File %s FID: %d FD: %d\n", 
+			buf_strings+buf_fids[fid].offset, fid, fds[fid] );
+	if ( buf_fids[fid].npages == -1 ) {
+		/* Initialize the npages field */
+		if ( fstat ( fds[fid], &sbuf ) ) {
+		    error_log3 ( "Error Fstating %s FID: %d.  Errno = %d\n", 
+				buf_strings+buf_fids[fid].offset, fid, errno );
+		} else {
+		    buf_fids[fid].npages = ( sbuf.st_size / BUFSIZE );
+		}
+	}
+
+	return ( fds[fid] );
+}
+
+static int
+bf_put_page ( fd, bhp ) 
+int	fd;
+BUFHDR_T	*bhp;
+{
+	int	nbytes;
+
+	assert ( (bhp-bufhdr_table) < NUM_BUFS );
+	if ( lseek ( fd, bhp->id.obj_id << BUFSHIFT, L_SET ) < 0 ) {
+	    return(-1);
+	}
+	bhp->flags |= BUF_IO_IN_PROGRESS;
+	if (RELEASE_MASTER) {
+	    return(-1);
+	}
+	nbytes = write(fd, buf_table[bhp-bufhdr_table], BUFSIZE);
+	if (GET_MASTER) {
+	    return(-2);
+	}
+	if ( nbytes < 0 ) {
+		error_log1 ("Write failed with error code %d\n", errno);
+		return(-1);
+	} else if ( nbytes != BUFSIZE ) {
+		error_log1 ("Short write: %d bytes of %d\n", nbytes, BUFSIZE );
+	}
+	bhp->flags &= ~(BUF_DIRTY|BUF_IO_IN_PROGRESS);
+	return (0);
+}
+
+static BUFHDR_T	*
+bf_assign_buf ( ndx, obj, flags, len )
+int	ndx;
+OBJ_T	*obj;
+u_long	flags;
+int	*len;		/* Number of bytes read */
+{
+    BUFHDR_T	*bhp;
+    int		fd;
+
+    assert ( obj->file_id < NUM_FILE_ENTRIES );
+    bhp = bf_newbuf();
+    if ( !bhp ) {
+	return(NULL);
+    }
+    OBJ_ASSIGN ( (*obj), bhp->id );
+    if ( buf_hash_table[ndx] >= NUM_BUFS ) {
+	buf_hash_table[ndx] = bhp-bufhdr_table;
+    } else {
+	LISTPE_INSERT ( bufhdr_table, hash, bhp, buf_hash_table[ndx] );
+    }
+
+    bhp->flags |= BUF_VALID;
+    if ( flags & BF_PIN ) {
+	bhp->flags |= BUF_PINNED;
+	bhp->refcount++;
+#ifdef PIN_DEBUG
+	fprintf(stderr, "bf_assign_buf: %X PINNED (%d)\n", 
+		buf_table + (bhp-bufhdr_table), bhp->refcount);
+#endif
+    }
+    fd = bf_fid_to_fd(obj->file_id);
+    if ( fd == -1 ) {
+	error_log1 ("Invalid fid %d\n", obj->file_id);
+	bhp->flags |= ~BUF_IO_ERROR;
+	return(NULL);
+    }
+    if ( obj->obj_id >= buf_fids[obj->file_id].npages) {
+	buf_fids[obj->file_id].npages = obj->obj_id+1;
+	*len = 0;
+    } else if ( flags & BF_EMPTY ) {
+	*len = 0;
+    } else {
+	bhp->flags |= BUF_IO_IN_PROGRESS;
+	if (RELEASE_MASTER) {
+		return(NULL);
+	}
+	if ( lseek ( fd, obj->obj_id << BUFSHIFT, L_SET ) < -1 ) {
+	    error_log2 ("Unable to perform seek on file: %d  to page %d",
+			obj->file_id, obj->obj_id );
+	    bhp->flags &= ~BUF_IO_IN_PROGRESS;
+	    bhp->flags |= ~BUF_IO_ERROR;
+	    return(NULL);
+	}
+	*len = read(fd, buf_table[bhp-bufhdr_table], BUFSIZE);
+	if ( *len < 0 ) {
+	    error_log2 ("Unable to perform read on file: %d  to page %d",
+			obj->file_id, obj->obj_id );
+	    bhp->flags &= ~BUF_IO_IN_PROGRESS;
+	    bhp->flags |= ~BUF_IO_ERROR;
+	    return(NULL);
+	} 
+	if (GET_MASTER) {
+		return(NULL);
+	}
+	bhp->flags &= ~BUF_IO_IN_PROGRESS;
+	if ( bhp->wait_proc != -1 ) {
+	    /* wake up waiter and anyone waiting on it */
+#ifdef DEBUG
+	    printf("Waking transaction %d due to completed I/O\n", 
+		bhp->wait_proc);
+#endif
+	    proc_wake_id ( bhp->wait_proc );
+	    bhp->wait_proc = -1;
+	}
+	MAKE_MRU(bhp);
+    }
+
+    if ( flags & BF_DIRTY ) {
+	bhp->flags |= BUF_DIRTY;
+    } else if ( *len < BUFSIZE ) {
+	bhp->flags |= BUF_NEWPAGE;
+    }
+    return ( bhp );
+}
+
+int
+buf_last ( fid )
+int	fid;
+{
+	int	val;
+
+	if (GET_MASTER) {
+		return(-1);
+	}
+	assert ( fid < NUM_FILE_ENTRIES );
+	if ( buf_fids[fid].npages == -1 ) {
+	    /* initialize npages field */
+	    (void) bf_fid_to_fd ( fid );
+	}
+	val = buf_fids[fid].npages;	
+	if ( val ) {
+		val--;			/* Convert to page number */
+	}
+	if (RELEASE_MASTER) {
+		return(-1);
+	}
+	return(val);
+}
+
+#ifdef DEBUG
+extern void
+buf_dump ( id, all )
+int	id;
+int	all;
+{
+	int i;
+	BUFHDR_T	*bhp;
+
+	printf ( "LRU + %d\n", *buf_lru );
+	if ( all ) {
+	    printf("ID\tFID\tPID\tLNEXT\tLPREV\tHNEXT\tHPREV\tSLEEP\tFLAG\tREFS\n");
+	    for ( bhp = bufhdr_table, i = 0; i < NUM_BUFS; bhp++, i++ ) {
+		    printf ( "%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%x\t%d\n", i,
+			bhp->id.file_id, bhp->id.obj_id,
+			bhp->lru.next, bhp->lru.prev,
+			bhp->hash.next, bhp->hash.prev,
+			bhp->wait_proc, bhp->flags, bhp->refcount );
+	    }
+	} else {
+		if ( id >= NUM_BUFS ) {
+			printf ( "Buffer ID (%d) too high\n", id );
+			return;
+		}
+		bhp = bufhdr_table+id;
+		printf ( "%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%x\t%d\n", i,
+		    bhp->id.file_id, bhp->id.obj_id,
+		    bhp->lru.next, bhp->lru.prev,
+		    bhp->hash.next, bhp->hash.prev,
+		    bhp->wait_proc, bhp->flags, bhp->refcount );
+	}
+	return;
+}
+#endif
+
diff --git a/lib/libc/db/recno/Makefile.inc b/lib/libc/db/recno/Makefile.inc
index c0fd31125a1..e7f78f4ce76 100644
--- a/lib/libc/db/recno/Makefile.inc
+++ b/lib/libc/db/recno/Makefile.inc
@@ -1,4 +1,4 @@
-#	$NetBSD: Makefile.inc,v 1.4 1995/02/27 13:24:22 cgd Exp $
+#	$NetBSD: Makefile.inc,v 1.5 1996/05/03 21:38:43 cgd Exp $
 #       @(#)Makefile.inc	8.1 (Berkeley) 6/4/93
 
 .PATH: ${.CURDIR}/db/recno
diff --git a/lib/libc/db/recno/extern.h b/lib/libc/db/recno/extern.h
index 5ec5d2f220c..39d8d6379ab 100644
--- a/lib/libc/db/recno/extern.h
+++ b/lib/libc/db/recno/extern.h
@@ -1,4 +1,4 @@
-/*	$NetBSD: extern.h,v 1.4 1995/02/27 13:24:30 cgd Exp $	*/
+/*	$NetBSD: extern.h,v 1.5 1996/05/03 21:38:44 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1991, 1993
diff --git a/lib/libc/db/recno/rec_close.c b/lib/libc/db/recno/rec_close.c
index 7c4dc283525..b8894afd732 100644
--- a/lib/libc/db/recno/rec_close.c
+++ b/lib/libc/db/recno/rec_close.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: rec_close.c,v 1.6 1995/02/27 13:24:37 cgd Exp $	*/
+/*	$NetBSD: rec_close.c,v 1.7 1996/05/03 21:38:45 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1990, 1993
+ * 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
@@ -35,9 +35,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)rec_close.c	8.3 (Berkeley) 2/21/94";
+static char sccsid[] = "@(#)rec_close.c	8.6 (Berkeley) 8/18/94";
 #else
-static char rcsid[] = "$NetBSD: rec_close.c,v 1.6 1995/02/27 13:24:37 cgd Exp $";
+static char rcsid[] = "$NetBSD: rec_close.c,v 1.7 1996/05/03 21:38:45 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -82,11 +82,11 @@ __rec_close(dbp)
 
 	/* Committed to closing. */
 	status = RET_SUCCESS;
-	if (ISSET(t, R_MEMMAPPED) && munmap(t->bt_smap, t->bt_msize))
+	if (F_ISSET(t, R_MEMMAPPED) && munmap(t->bt_smap, t->bt_msize))
 		status = RET_ERROR;
 
-	if (!ISSET(t, R_INMEM))
-		if (ISSET(t, R_CLOSEFP)) {
+	if (!F_ISSET(t, R_INMEM))
+		if (F_ISSET(t, R_CLOSEFP)) {
 			if (fclose(t->bt_rfp))
 				status = RET_ERROR;
 		} else
@@ -131,39 +131,58 @@ __rec_sync(dbp, flags)
 	if (flags == R_RECNOSYNC)
 		return (__bt_sync(dbp, 0));
 
-	if (ISSET(t, R_RDONLY | R_INMEM) || !ISSET(t, R_MODIFIED))
+	if (F_ISSET(t, R_RDONLY | R_INMEM) || !F_ISSET(t, R_MODIFIED))
 		return (RET_SUCCESS);
 
 	/* Read any remaining records into the tree. */
-	if (!ISSET(t, R_EOF) && t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR)
+	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);
 
-	iov[1].iov_base = "\n";
-	iov[1].iov_len = 1;
-	scursor = t->bt_rcursor;
+	/* Save the cursor. */
+	scursor = t->bt_cursor.rcursor;
 
 	key.size = sizeof(recno_t);
 	key.data = &trec;
 
-	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);
-        }
-	t->bt_rcursor = scursor;
+	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);
-	CLR(t, R_MODIFIED);
+	F_CLR(t, R_MODIFIED);
 	return (RET_SUCCESS);
 }
diff --git a/lib/libc/db/recno/rec_delete.c b/lib/libc/db/recno/rec_delete.c
index 6f438a35cd9..3c6d48e698f 100644
--- a/lib/libc/db/recno/rec_delete.c
+++ b/lib/libc/db/recno/rec_delete.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: rec_delete.c,v 1.7 1995/02/27 13:24:48 cgd Exp $	*/
+/*	$NetBSD: rec_delete.c,v 1.8 1996/05/03 21:38:46 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)rec_delete.c	8.6 (Berkeley) 6/4/94";
+static char sccsid[] = "@(#)rec_delete.c	8.7 (Berkeley) 7/14/94";
 #else
-static char rcsid[] = "$NetBSD: rec_delete.c,v 1.7 1995/02/27 13:24:48 cgd Exp $";
+static char rcsid[] = "$NetBSD: rec_delete.c,v 1.8 1996/05/03 21:38:46 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -94,13 +94,13 @@ __rec_delete(dbp, key, flags)
 		status = rec_rdelete(t, nrec);
 		break;
 	case R_CURSOR:
-		if (!ISSET(t, B_SEQINIT))
+		if (!F_ISSET(&t->bt_cursor, CURS_INIT))
 			goto einval;
 		if (t->bt_nrecs == 0)
 			return (RET_SPECIAL);
-		status = rec_rdelete(t, t->bt_rcursor - 1);
+		status = rec_rdelete(t, t->bt_cursor.rcursor - 1);
 		if (status == RET_SUCCESS)
-			--t->bt_rcursor;
+			--t->bt_cursor.rcursor;
 		break;
 	default:
 einval:		errno = EINVAL;
@@ -108,7 +108,7 @@ einval:		errno = EINVAL;
 	}
 
 	if (status == RET_SUCCESS)
-		SET(t, B_MODIFIED | R_MODIFIED);
+		F_SET(t, B_MODIFIED | R_MODIFIED);
 	return (status);
 }
 
diff --git a/lib/libc/db/recno/rec_get.c b/lib/libc/db/recno/rec_get.c
index bc25104e552..a08e16f8089 100644
--- a/lib/libc/db/recno/rec_get.c
+++ b/lib/libc/db/recno/rec_get.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: rec_get.c,v 1.7 1995/02/27 13:24:57 cgd Exp $	*/
+/*	$NetBSD: rec_get.c,v 1.8 1996/05/03 21:38:48 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -35,9 +35,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)rec_get.c	8.5 (Berkeley) 6/20/94";
+static char sccsid[] = "@(#)rec_get.c	8.9 (Berkeley) 8/18/94";
 #else
-static char rcsid[] = "$NetBSD: rec_get.c,v 1.7 1995/02/27 13:24:57 cgd Exp $";
+static char rcsid[] = "$NetBSD: rec_get.c,v 1.8 1996/05/03 21:38:48 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -96,7 +96,7 @@ __rec_get(dbp, key, data, flags)
 	 * original file.
 	 */
 	if (nrec > t->bt_nrecs) {
-		if (ISSET(t, R_EOF | R_INMEM))
+		if (F_ISSET(t, R_EOF | R_INMEM))
 			return (RET_SPECIAL);
 		if ((status = t->bt_irec(t, nrec)) != RET_SUCCESS)
 			return (status);
@@ -107,7 +107,7 @@ __rec_get(dbp, key, data, flags)
 		return (RET_ERROR);
 
 	status = __rec_ret(t, e, 0, NULL, data);
-	if (ISSET(t, B_DB_LOCK))
+	if (F_ISSET(t, B_DB_LOCK))
 		mpool_put(t->bt_mp, e->page, 0);
 	else
 		t->bt_pinned = e->page;
@@ -133,32 +133,38 @@ __rec_fpipe(t, top)
 	recno_t nrec;
 	size_t len;
 	int ch;
-	char *p;
+	u_char *p;
 
-	if (t->bt_dbufsz < t->bt_reclen) {
-		t->bt_dbuf = (char *)(t->bt_dbuf == NULL ?
-		    malloc(t->bt_reclen) : realloc(t->bt_dbuf, t->bt_reclen));
-		if (t->bt_dbuf == NULL)
+	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_dbufsz = t->bt_reclen;
+		t->bt_rdata.size = t->bt_reclen;
 	}
-	data.data = t->bt_dbuf;
+	data.data = t->bt_rdata.data;
 	data.size = t->bt_reclen;
 
-	for (nrec = t->bt_nrecs; nrec < top; ++nrec) {
+	for (nrec = t->bt_nrecs; nrec < top;) {
 		len = t->bt_reclen;
-		for (p = t->bt_dbuf;; *p++ = ch)
-			if ((ch = getc(t->bt_rfp)) == EOF || !len--) {
-				if (__rec_iput(t, nrec, &data, 0)
-				    != RET_SUCCESS)
+		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) {
-		SET(t, R_EOF);
+		F_SET(t, R_EOF);
 		return (RET_SPECIAL);
 	}
 	return (RET_SUCCESS);
@@ -184,14 +190,15 @@ __rec_vpipe(t, top)
 	indx_t len;
 	size_t sz;
 	int bval, ch;
-	char *p;
+	u_char *p;
 
 	bval = t->bt_bval;
 	for (nrec = t->bt_nrecs; nrec < top; ++nrec) {
-		for (p = t->bt_dbuf, sz = t->bt_dbufsz;; *p++ = ch, --sz) {
+		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_dbuf;
-				data.size = p - t->bt_dbuf;
+				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)
@@ -200,21 +207,21 @@ __rec_vpipe(t, top)
 				break;
 			}
 			if (sz == 0) {
-				len = p - t->bt_dbuf;
-				t->bt_dbufsz += (sz = 256);
-				t->bt_dbuf = (char *)(t->bt_dbuf == NULL ?
-				    malloc(t->bt_dbufsz) :
-				    realloc(t->bt_dbuf, t->bt_dbufsz));
-				if (t->bt_dbuf == NULL)
+				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 = t->bt_dbuf + len;
+				p = (u_char *)t->bt_rdata.data + len;
 			}
 		}
 		if (ch == EOF)
 			break;
 	}
 	if (nrec < top) {
-		SET(t, R_EOF);
+		F_SET(t, R_EOF);
 		return (RET_SPECIAL);
 	}
 	return (RET_SUCCESS);
@@ -237,34 +244,36 @@ __rec_fmap(t, top)
 {
 	DBT data;
 	recno_t nrec;
-	caddr_t sp, ep;
+	u_char *sp, *ep, *p;
 	size_t len;
-	char *p;
 
-	if (t->bt_dbufsz < t->bt_reclen) {
-		t->bt_dbuf = (char *)(t->bt_dbuf == NULL ?
-		    malloc(t->bt_reclen) : realloc(t->bt_dbuf, t->bt_reclen));
-		if (t->bt_dbuf == NULL)
+	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_dbufsz = t->bt_reclen;
+		t->bt_rdata.size = t->bt_reclen;
 	}
-	data.data = t->bt_dbuf;
+	data.data = t->bt_rdata.data;
 	data.size = t->bt_reclen;
 
-	sp = t->bt_cmap;
-	ep = t->bt_emap;
+	sp = (u_char *)t->bt_cmap;
+	ep = (u_char *)t->bt_emap;
 	for (nrec = t->bt_nrecs; nrec < top; ++nrec) {
 		if (sp >= ep) {
-			SET(t, R_EOF);
+			F_SET(t, R_EOF);
 			return (RET_SPECIAL);
 		}
 		len = t->bt_reclen;
-		for (p = t->bt_dbuf; sp < ep && len--; *p++ = *sp++);
-		memset(p, t->bt_bval, len);
+		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 = sp;
+	t->bt_cmap = (caddr_t)sp;
 	return (RET_SUCCESS);
 }
 
@@ -284,25 +293,25 @@ __rec_vmap(t, top)
 	recno_t top;
 {
 	DBT data;
-	caddr_t sp, ep;
+	u_char *sp, *ep;
 	recno_t nrec;
 	int bval;
 
-	sp = t->bt_cmap;
-	ep = t->bt_emap;
+	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) {
-			SET(t, R_EOF);
+			F_SET(t, R_EOF);
 			return (RET_SPECIAL);
 		}
 		for (data.data = sp; sp < ep && *sp != bval; ++sp);
-		data.size = sp - (caddr_t)data.data;
+		data.size = sp - (u_char *)data.data;
 		if (__rec_iput(t, nrec, &data, 0) != RET_SUCCESS)
 			return (RET_ERROR);
 		++sp;
 	}
-	t->bt_cmap = sp;
+	t->bt_cmap = (caddr_t)sp;
 	return (RET_SUCCESS);
 }
diff --git a/lib/libc/db/recno/rec_open.c b/lib/libc/db/recno/rec_open.c
index e67a7b6f000..d2c9369b730 100644
--- a/lib/libc/db/recno/rec_open.c
+++ b/lib/libc/db/recno/rec_open.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: rec_open.c,v 1.6 1995/02/27 13:25:05 cgd Exp $	*/
+/*	$NetBSD: rec_open.c,v 1.7 1996/05/03 21:38:49 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1990, 1993
+ * 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
@@ -38,9 +38,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)rec_open.c	8.6 (Berkeley) 2/22/94";
+static char sccsid[] = "@(#)rec_open.c	8.10 (Berkeley) 9/1/94";
 #else
-static char rcsid[] = "$NetBSD: rec_open.c,v 1.6 1995/02/27 13:25:05 cgd Exp $";
+static char rcsid[] = "$NetBSD: rec_open.c,v 1.7 1996/05/03 21:38:49 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -104,7 +104,7 @@ __rec_open(fname, flags, mode, openinfo, dflags)
 	t = dbp->internal;
 	if (openinfo) {
 		if (openinfo->flags & R_FIXEDLEN) {
-			SET(t, R_FIXLEN);
+			F_SET(t, R_FIXLEN);
 			t->bt_reclen = openinfo->reclen;
 			if (t->bt_reclen == 0)
 				goto einval;
@@ -113,12 +113,11 @@ __rec_open(fname, flags, mode, openinfo, dflags)
 	} else
 		t->bt_bval = '\n';
 
-	SET(t, R_RECNO);
+	F_SET(t, R_RECNO);
 	if (fname == NULL)
-		SET(t, R_EOF | R_INMEM);
+		F_SET(t, R_EOF | R_INMEM);
 	else
 		t->bt_rfd = rfd;
-	t->bt_rcursor = 0;
 
 	if (fname != NULL) {
 		/*
@@ -130,20 +129,20 @@ __rec_open(fname, flags, mode, openinfo, dflags)
 		if (lseek(rfd, (off_t)0, SEEK_CUR) == -1 && errno == ESPIPE) {
 			switch (flags & O_ACCMODE) {
 			case O_RDONLY:
-				SET(t, R_RDONLY);
+				F_SET(t, R_RDONLY);
 				break;
 			default:
 				goto einval;
 			}
 slow:			if ((t->bt_rfp = fdopen(rfd, "r")) == NULL)
 				goto err;
-			SET(t, R_CLOSEFP);
+			F_SET(t, R_CLOSEFP);
 			t->bt_irec =
-			    ISSET(t, R_FIXLEN) ? __rec_fpipe : __rec_vpipe;
+			    F_ISSET(t, R_FIXLEN) ? __rec_fpipe : __rec_vpipe;
 		} else {
 			switch (flags & O_ACCMODE) {
 			case O_RDONLY:
-				SET(t, R_RDONLY);
+				F_SET(t, R_RDONLY);
 				break;
 			case O_RDWR:
 				break;
@@ -163,8 +162,16 @@ slow:			if ((t->bt_rfp = fdopen(rfd, "r")) == NULL)
 			 * fails if the file is too large.
 			 */
 			if (sb.st_size == 0)
-				SET(t, R_EOF);
+				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,
@@ -172,9 +179,12 @@ slow:			if ((t->bt_rfp = fdopen(rfd, "r")) == NULL)
 					goto slow;
 				t->bt_cmap = t->bt_smap;
 				t->bt_emap = t->bt_smap + sb.st_size;
-				t->bt_irec = ISSET(t, R_FIXLEN) ?
+				t->bt_irec = F_ISSET(t, R_FIXLEN) ?
 				    __rec_fmap : __rec_vmap;
-				SET(t, R_MEMMAPPED);
+				F_SET(t, R_MEMMAPPED);
+#else
+				goto slow;
+#endif
 			}
 		}
 	}
@@ -192,13 +202,14 @@ slow:			if ((t->bt_rfp = fdopen(rfd, "r")) == NULL)
 	if ((h = mpool_get(t->bt_mp, P_ROOT, 0)) == NULL)
 		goto err;
 	if ((h->flags & P_TYPE) == P_BLEAF) {
-		h->flags = h->flags & ~P_TYPE | P_RLEAF;
+		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 &&
-	    !ISSET(t, R_EOF | R_INMEM) &&
+	    !F_ISSET(t, R_EOF | R_INMEM) &&
 	    t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR)
                 goto err;
 	return (dbp);
@@ -228,7 +239,7 @@ __rec_fd(dbp)
 	}
 
 	/* In-memory database can't have a file descriptor. */
-	if (ISSET(t, R_INMEM)) {
+	if (F_ISSET(t, R_INMEM)) {
 		errno = ENOENT;
 		return (-1);
 	}
diff --git a/lib/libc/db/recno/rec_put.c b/lib/libc/db/recno/rec_put.c
index 77d7079fb73..107d645a649 100644
--- a/lib/libc/db/recno/rec_put.c
+++ b/lib/libc/db/recno/rec_put.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: rec_put.c,v 1.7 1995/02/27 13:25:13 cgd Exp $	*/
+/*	$NetBSD: rec_put.c,v 1.8 1996/05/03 21:38:50 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -35,9 +35,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)rec_put.c	8.4 (Berkeley) 5/31/94";
+static char sccsid[] = "@(#)rec_put.c	8.7 (Berkeley) 8/18/94";
 #else
-static char rcsid[] = "$NetBSD: rec_put.c,v 1.7 1995/02/27 13:25:13 cgd Exp $";
+static char rcsid[] = "$NetBSD: rec_put.c,v 1.8 1996/05/03 21:38:50 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -72,7 +72,7 @@ __rec_put(dbp, key, data, flags)
 	u_int flags;
 {
 	BTREE *t;
-	DBT tdata;
+	DBT fdata, tdata;
 	recno_t nrec;
 	int status;
 
@@ -84,11 +84,38 @@ __rec_put(dbp, key, data, flags)
 		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 (!ISSET(t, B_SEQINIT))
+		if (!F_ISSET(&t->bt_cursor, CURS_INIT))
 			goto einval;
-		nrec = t->bt_rcursor;
+		nrec = t->bt_cursor.rcursor;
 		break;
 	case R_SETCURSOR:
 		if ((nrec = *(recno_t *)key->data) == 0)
@@ -121,11 +148,11 @@ einval:		errno = EINVAL;
 	 * already in the database.  If skipping records, create empty ones.
 	 */
 	if (nrec > t->bt_nrecs) {
-		if (!ISSET(t, R_EOF | R_INMEM) &&
+		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 (ISSET(t, R_FIXLEN)) {
+			if (F_ISSET(t, R_FIXLEN)) {
 				if ((tdata.data =
 				    (void *)malloc(t->bt_reclen)) == NULL)
 					return (RET_ERROR);
@@ -139,18 +166,18 @@ einval:		errno = EINVAL;
 				if (__rec_iput(t,
 				    t->bt_nrecs, &tdata, 0) != RET_SUCCESS)
 					return (RET_ERROR);
-			if (ISSET(t, R_FIXLEN))
+			if (F_ISSET(t, R_FIXLEN))
 				free(tdata.data);
 		}
 	}
 
-	if ((status = __rec_iput(t, nrec - 1, data, flags)) != RET_SUCCESS)
+	if ((status = __rec_iput(t, nrec - 1, &fdata, flags)) != RET_SUCCESS)
 		return (status);
 
 	if (flags == R_SETCURSOR)
-		t->bt_rcursor = nrec;
+		t->bt_cursor.rcursor = nrec;
 	
-	SET(t, R_MODIFIED);
+	F_SET(t, R_MODIFIED);
 	return (__rec_ret(t, NULL, nrec, key, NULL));
 }
 
@@ -252,7 +279,7 @@ __rec_iput(t, nrec, data, flags)
 	WR_RLEAF(dest, data, dflags);
 
 	++t->bt_nrecs;
-	SET(t, B_MODIFIED);
+	F_SET(t, B_MODIFIED);
 	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
 
 	return (RET_SUCCESS);
diff --git a/lib/libc/db/recno/rec_search.c b/lib/libc/db/recno/rec_search.c
index 208328d9ddd..beb714b5146 100644
--- a/lib/libc/db/recno/rec_search.c
+++ b/lib/libc/db/recno/rec_search.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: rec_search.c,v 1.6 1995/02/27 13:25:17 cgd Exp $	*/
+/*	$NetBSD: rec_search.c,v 1.7 1996/05/03 21:38:52 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993
@@ -35,9 +35,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)rec_search.c	8.3 (Berkeley) 2/21/94";
+static char sccsid[] = "@(#)rec_search.c	8.4 (Berkeley) 7/14/94";
 #else
-static char rcsid[] = "$NetBSD: rec_search.c,v 1.6 1995/02/27 13:25:17 cgd Exp $";
+static char rcsid[] = "$NetBSD: rec_search.c,v 1.7 1996/05/03 21:38:52 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -97,8 +97,7 @@ __rec_search(t, recno, op)
 			total += r->nrecs;
 		}
 
-		if (__bt_push(t, pg, index - 1) == RET_ERROR)
-			return (NULL);
+		BT_PUSH(t, pg, index - 1);
 		
 		pg = r->pgno;
 		switch (op) {
diff --git a/lib/libc/db/recno/rec_seq.c b/lib/libc/db/recno/rec_seq.c
index b91f3a27bf6..3b5c534dda6 100644
--- a/lib/libc/db/recno/rec_seq.c
+++ b/lib/libc/db/recno/rec_seq.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: rec_seq.c,v 1.6 1995/02/27 13:25:24 cgd Exp $	*/
+/*	$NetBSD: rec_seq.c,v 1.7 1996/05/03 21:38:53 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1991, 1993
+ * 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
@@ -35,9 +35,9 @@
 
 #ifndef lint
 #if 0
-static char sccsid[] = "@(#)rec_seq.c	8.2 (Berkeley) 9/7/93";
+static char sccsid[] = "@(#)rec_seq.c	8.3 (Berkeley) 7/14/94";
 #else
-static char rcsid[] = "$NetBSD: rec_seq.c,v 1.6 1995/02/27 13:25:24 cgd Exp $";
+static char rcsid[] = "$NetBSD: rec_seq.c,v 1.7 1996/05/03 21:38:53 cgd Exp $";
 #endif
 #endif /* not lint */
 
@@ -88,8 +88,8 @@ __rec_seq(dbp, key, data, flags)
 			goto einval;
 		break;
 	case R_NEXT:
-		if (ISSET(t, B_SEQINIT)) {
-			nrec = t->bt_rcursor + 1;
+		if (F_ISSET(&t->bt_cursor, CURS_INIT)) {
+			nrec = t->bt_cursor.rcursor + 1;
 			break;
 		}
 		/* FALLTHROUGH */
@@ -97,14 +97,14 @@ __rec_seq(dbp, key, data, flags)
 		nrec = 1;
 		break;
 	case R_PREV:
-		if (ISSET(t, B_SEQINIT)) {
-			if ((nrec = t->bt_rcursor - 1) == 0)
+		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 (!ISSET(t, R_EOF | R_INMEM) &&
+		if (!F_ISSET(t, R_EOF | R_INMEM) &&
 		    t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR)
 			return (RET_ERROR);
 		nrec = t->bt_nrecs;
@@ -115,7 +115,7 @@ einval:		errno = EINVAL;
 	}
 	
 	if (t->bt_nrecs == 0 || nrec > t->bt_nrecs) {
-		if (!ISSET(t, R_EOF | R_INMEM) &&
+		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)
@@ -125,11 +125,11 @@ einval:		errno = EINVAL;
 	if ((e = __rec_search(t, nrec - 1, SEARCH)) == NULL)
 		return (RET_ERROR);
 
-	SET(t, B_SEQINIT);
-	t->bt_rcursor = nrec;
+	F_SET(&t->bt_cursor, CURS_INIT);
+	t->bt_cursor.rcursor = nrec;
 
 	status = __rec_ret(t, e, nrec, key, data);
-	if (ISSET(t, B_DB_LOCK))
+	if (F_ISSET(t, B_DB_LOCK))
 		mpool_put(t->bt_mp, e->page, 0);
 	else
 		t->bt_pinned = e->page;
diff --git a/lib/libc/db/recno/rec_utils.c b/lib/libc/db/recno/rec_utils.c
index 7aab4ac3a91..e411dae7db4 100644
--- a/lib/libc/db/recno/rec_utils.c
+++ b/lib/libc/db/recno/rec_utils.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: rec_utils.c,v 1.6 1995/02/27 13:25:29 cgd Exp $	*/
+/*	$NetBSD: rec_utils.c,v 1.7 1996/05/03 21:38:54 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1990, 1993, 1994
@@ -35,9 +35,9 @@
 
 #if defined(LIBC_SCCS) && !defined(lint)
 #if 0
-static char sccsid[] = "@(#)rec_utils.c	8.4 (Berkeley) 6/20/94";
+static char sccsid[] = "@(#)rec_utils.c	8.6 (Berkeley) 7/16/94";
 #else
-static char rcsid[] = "$NetBSD: rec_utils.c,v 1.6 1995/02/27 13:25:29 cgd Exp $";
+static char rcsid[] = "$NetBSD: rec_utils.c,v 1.7 1996/05/03 21:38:54 cgd Exp $";
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -51,11 +51,14 @@ static char rcsid[] = "$NetBSD: rec_utils.c,v 1.6 1995/02/27 13:25:29 cgd Exp $"
 #include "recno.h"
 
 /*
- * __REC_RET -- Build return data as a result of search or scan.
+ * __rec_ret --
+ *	Build return data.
  *
  * Parameters:
  *	t:	tree
- *	d:	LEAF to be returned to the user.
+ *	e:	key/data pair to be returned
+ *   nrec:	record number
+ *    key:	user's key structure
  *	data:	user's data structure
  *
  * Returns:
@@ -68,58 +71,58 @@ __rec_ret(t, e, nrec, key, data)
 	recno_t nrec;
 	DBT *key, *data;
 {
-	register RLEAF *rl;
-	register void *p;
+	RLEAF *rl;
+	void *p;
 
-	if (data == NULL)
-		goto retkey;
+	if (key == NULL)
+		goto dataonly;
 
-	rl = GETRLEAF(e->page, e->index);
+	/* 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 always copy big data to make it contigous.  Otherwise, we
+	 * 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_dbuf, &t->bt_dbufsz))
+		    &data->size, &t->bt_rdata.data, &t->bt_rdata.size))
 			return (RET_ERROR);
-		data->data = t->bt_dbuf;
-	} else if (ISSET(t, B_DB_LOCK)) {
+		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_dbufsz) {
-			p = (void *)(t->bt_dbuf == NULL ?
+		if (rl->dsize + 1 > t->bt_rdata.size) {
+			p = (void *)(t->bt_rdata.data == NULL ?
 			    malloc(rl->dsize + 1) :
-			    realloc(t->bt_dbuf, rl->dsize + 1));
+			    realloc(t->bt_rdata.data, rl->dsize + 1));
 			if (p == NULL)
 				return (RET_ERROR);
-			t->bt_dbuf = p;
-			t->bt_dbufsz = rl->dsize + 1;
+			t->bt_rdata.data = p;
+			t->bt_rdata.size = rl->dsize + 1;
 		}
-		memmove(t->bt_dbuf, rl->bytes, rl->dsize);
+		memmove(t->bt_rdata.data, rl->bytes, rl->dsize);
 		data->size = rl->dsize;
-		data->data = t->bt_dbuf;
+		data->data = t->bt_rdata.data;
 	} else {
 		data->size = rl->dsize;
 		data->data = rl->bytes;
 	}
-
-retkey:	if (key == NULL)
-		return (RET_SUCCESS);
-
-	/* We have to copy the key, it's not on the page. */
-	if (sizeof(recno_t) > t->bt_kbufsz) {
-		p = (void *)(t->bt_kbuf == NULL ?
-		    malloc(sizeof(recno_t)) :
-		    realloc(t->bt_kbuf, sizeof(recno_t)));
-		if (p == NULL)
-			return (RET_ERROR);
-		t->bt_kbuf = p;
-		t->bt_kbufsz = sizeof(recno_t);
-	}
-	memmove(t->bt_kbuf, &nrec, sizeof(recno_t));
-	key->size = sizeof(recno_t);
-	key->data = t->bt_kbuf;
 	return (RET_SUCCESS);
 }
diff --git a/lib/libc/db/recno/recno.h b/lib/libc/db/recno/recno.h
index 5c1c716ace3..747c7bd9ee7 100644
--- a/lib/libc/db/recno/recno.h
+++ b/lib/libc/db/recno/recno.h
@@ -1,4 +1,4 @@
-/*	$NetBSD: recno.h,v 1.4 1995/02/27 13:25:35 cgd Exp $	*/
+/*	$NetBSD: recno.h,v 1.5 1996/05/03 21:38:55 cgd Exp $	*/
 
 /*-
  * Copyright (c) 1991, 1993
diff --git a/regress/lib/libc/db/README b/regress/lib/libc/db/README
index 3b290b09d81..fddf5c3d5a0 100644
--- a/regress/lib/libc/db/README
+++ b/regress/lib/libc/db/README
@@ -1,5 +1,5 @@
-#	$NetBSD: README,v 1.4 1995/04/20 22:39:18 cgd Exp $
-#	@(#)README	8.4 (Berkeley) 6/20/94
+#	$NetBSD: README,v 1.5 1996/05/03 21:54:19 cgd Exp $
+#	@(#)README	8.8 (Berkeley) 7/31/94
 
 To run the tests, enter "make regress".
 
@@ -9,8 +9,11 @@ the test runs, and even larger files (the database files) are created in
 variable TMPDIR to a directory where the files can be built.
 
 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
-The script file consists of lines with a initial character which is
-the "command" for that line.  Legal characters are as follows:
+The script file consists of lines with an initial character which is
+the command for that line, or an initial character indicating a key
+or data entry for a previous command.
+
+Legal command characters are as follows:
 
 c: compare a record
 	+ must be followed by [kK][dD]; the data value in the database
@@ -19,17 +22,24 @@ c: compare a record
 e: echo a string
 	+ writes out the rest of the line into the output file; if the
 	  last character is not a carriage-return, a newline is appended.
+f: set the flags for the next command
+	+ no value zero's the flags
 g: do a get command
 	+ must be followed by [kK]
 	+ writes out the retrieved data DBT.
+o [r]: dump [reverse]
+	+ dump the database out, if 'r' is set, in reverse order.
 p: do a put command
 	+ must be followed by [kK][dD]
 r: do a del command
-	+ must be followed by [kK]
+	+ must be followed by [kK] unless R_CURSOR flag set.
+S: sync the database
 s: do a seq command
+	+ must be followed by [kK] if R_CURSOR flag set.
 	+ writes out the retrieved data DBT.
-f: set the flags for the next command
-	+ no value zero's the flags
+
+Legal key/data characters are as follows:
+
 D [file]: data file
 	+ set the current data value to the contents of the file
 d [data]:
@@ -38,17 +48,21 @@ K [file]: key file
 	+ set the current key value to the contents of the file
 k [data]:
 	+ set the current key value to the contents of the line.
-o [r]: dump [reverse]
-	+ dump the database out, if 'r' is set, in reverse order.
+
+Blank lines, lines with leading white space, and lines with leading
+hash marks (#) are ignored.
 
 Options to dbtest are as follows:
 
+	-d: Set the DB_LOCK flag.
 	-f: Use the file argument as the database file.
 	-i: Use the rest of the argument to set elements in the info
 	    structure.  If the type is btree, then "-i cachesize=10240"
 	    will set BTREEINFO.cachesize to 10240.
 	-o: The rest of the argument is the output file instead of
 	    using stdout.
+	-s: Don't delete the database file before opening it, i.e.
+	    use the database file from a previous run.
 
-Dbtest requires two arguments, the type of access "hash", "recno" or
-"btree", and the script name.
+Dbtest requires two arguments, the type of access "hash", "recno"
+or "btree", and the script name or "-" to indicate stdin.
diff --git a/regress/lib/libc/db/dbtest.c b/regress/lib/libc/db/dbtest.c
index 1fcf09af97f..65587a6fcb2 100644
--- a/regress/lib/libc/db/dbtest.c
+++ b/regress/lib/libc/db/dbtest.c
@@ -1,7 +1,7 @@
-/*	$NetBSD: dbtest.c,v 1.7 1995/04/20 22:39:22 cgd Exp $	*/
+/*	$NetBSD: dbtest.c,v 1.8 1996/05/03 21:57:48 cgd Exp $	*/
 
 /*-
- * Copyright (c) 1992, 1993
+ * Copyright (c) 1992, 1993, 1994
  *	The Regents of the University of California.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -35,15 +35,15 @@
 
 #ifndef lint
 static char copyright[] =
-"@(#) Copyright (c) 1992, 1993\n\
+"@(#) Copyright (c) 1992, 1993, 1994\n\
 	The Regents of the University of California.  All rights reserved.\n";
 #endif /* not lint */
 
 #ifndef lint
 #if 0
-static char sccsid[] = "@(#)dbtest.c	8.8 (Berkeley) 2/21/94";
+static char sccsid[] = "@(#)dbtest.c	8.17 (Berkeley) 9/1/94";
 #else
-static char rcsid[] = "$NetBSD: dbtest.c,v 1.7 1995/04/20 22:39:22 cgd Exp $";
+static char rcsid[] = "$NetBSD: dbtest.c,v 1.8 1996/05/03 21:57:48 cgd Exp $";
 #endif
 #endif /* not lint */
 
@@ -71,6 +71,8 @@ void	 get __P((DB *, DBT *));
 void	 getdata __P((DB *, DBT *, DBT *));
 void	 put __P((DB *, DBT *, DBT *));
 void	 rem __P((DB *, DBT *));
+char	*sflags __P((int));
+void	 synk __P((DB *));
 void	*rfile __P((char *, size_t *));
 void	 seq __P((DB *, DBT *));
 u_int	 setflags __P((char *));
@@ -78,13 +80,14 @@ void	*setinfo __P((DBTYPE, char *));
 void	 usage __P((void));
 void	*xmalloc __P((char *, size_t));
 
-DBTYPE type;
-void *infop;
-u_long lineno;
-u_int flags;
-int ofd = STDOUT_FILENO;
+DBTYPE type;				/* Database type. */
+void *infop;				/* Iflags. */
+u_long lineno;				/* Current line in test script. */
+u_int flags;				/* Current DB flags. */
+int ofd = STDOUT_FILENO;		/* Standard output fd. */
 
 DB *XXdbp;				/* Global for gdb. */
+int XXlineno;				/* Fast breakpoint for gdb. */
 
 int
 main(argc, argv)
@@ -97,14 +100,15 @@ main(argc, argv)
 	DB *dbp;
 	DBT data, key, keydata;
 	size_t len;
-	int ch, oflags;
-	char *fname, *infoarg, *p, buf[8 * 1024];
+	int ch, oflags, sflag;
+	char *fname, *infoarg, *p, *t, buf[8 * 1024];
 
 	infoarg = NULL;
 	fname = NULL;
 	oflags = O_CREAT | O_RDWR;
-	while ((ch = getopt(argc, argv, "f:i:lo:")) != EOF)
-		switch(ch) {
+	sflag = 0;
+	while ((ch = getopt(argc, argv, "f:i:lo:s")) != EOF)
+		switch (ch) {
 		case 'f':
 			fname = optarg;
 			break;
@@ -119,6 +123,9 @@ main(argc, argv)
 			    O_WRONLY|O_CREAT|O_TRUNC, 0666)) < 0)
 				err("%s: %s", optarg, strerror(errno));
 			break;
+		case 's':
+			sflag = 1;
+			break;
 		case '?':
 		default:
 			usage();
@@ -133,8 +140,8 @@ main(argc, argv)
 	type = dbtype(*argv++);
 
 	/* Open the descriptor file. */
-	if (freopen(*argv, "r", stdin) == NULL)
-		err("%s: %s", *argv, strerror(errno));
+        if (strcmp(*argv, "-") && freopen(*argv, "r", stdin) == NULL)
+	    err("%s: %s", *argv, strerror(errno));
 
 	/* Set up the db structure as necessary. */
 	if (infoarg == NULL)
@@ -145,7 +152,10 @@ main(argc, argv)
 			if (*p != '\0')
 				infop = setinfo(type, p);
 
-	/* Open the DB. */
+	/*
+	 * Open the DB.  Delete any preexisting copy, you almost never
+	 * want it around, and it often screws up tests.
+	 */
 	if (fname == NULL) {
 		p = getenv("TMPDIR");
 		if (p == NULL)
@@ -153,7 +163,9 @@ main(argc, argv)
 		(void)sprintf(buf, "%s/__dbtest", p);
 		fname = buf;
 		(void)unlink(buf);
-	}
+	} else  if (!sflag)
+		(void)unlink(fname);
+
 	if ((dbp = dbopen(fname,
 	    oflags, S_IRUSR | S_IWUSR, type, infop)) == NULL)
 		err("dbopen: %s", strerror(errno));
@@ -162,8 +174,16 @@ main(argc, argv)
 	state = COMMAND;
 	for (lineno = 1;
 	    (p = fgets(buf, sizeof(buf), stdin)) != NULL; ++lineno) {
-		len = strlen(buf);
-		switch(*p) {
+		/* Delete the newline, displaying the key/data is easier. */
+		if (ofd == STDOUT_FILENO && (t = strchr(p, '\n')) != NULL)
+			*t = '\0';
+		if ((len = strlen(buf)) == 0 || isspace(*p) || *p == '#')
+			continue;
+
+		/* Convenient gdb break point. */
+		if (XXlineno == lineno)
+			XXlineno = 1;
+		switch (*p) {
 		case 'c':			/* compare */
 			if (state != COMMAND)
 				err("line %lu: not expecting command", lineno);
@@ -176,7 +196,8 @@ main(argc, argv)
 			/* Don't display the newline, if CR at EOL. */
 			if (p[len - 2] == '\r')
 				--len;
-			if (write(ofd, p + 1, len - 1) != len - 1)
+			if (write(ofd, p + 1, len - 1) != len - 1 ||
+			    write(ofd, "\n", 1) != 1)
 				err("write: %s", strerror(errno));
 			break;
 		case 'g':			/* get */
@@ -194,8 +215,19 @@ main(argc, argv)
 		case 'r':			/* remove */
 			if (state != COMMAND)
 				err("line %lu: not expecting command", lineno);
-			state = KEY;
-			command = REMOVE;
+                        if (flags == R_CURSOR) {
+				rem(dbp, &key);
+				state = COMMAND;
+                        } else {
+				state = KEY;
+				command = REMOVE;
+			}
+			break;
+		case 'S':			/* sync */
+			if (state != COMMAND)
+				err("line %lu: not expecting command", lineno);
+			synk(dbp);
+			state = COMMAND;
 			break;
 		case 's':			/* seq */
 			if (state != COMMAND)
@@ -219,7 +251,7 @@ main(argc, argv)
 				err("line %lu: not expecting data", lineno);
 			data.data = xmalloc(p + 1, len - 1);
 			data.size = len - 1;
-ldata:			switch(command) {
+ldata:			switch (command) {
 			case COMPARE:
 				compare(&keydata, &data);
 				break;
@@ -255,7 +287,7 @@ ldata:			switch(command) {
 				key.data = xmalloc(p + 1, len - 1);
 				key.size = len - 1;
 			}
-lkey:			switch(command) {
+lkey:			switch (command) {
 			case COMPARE:
 				getdata(dbp, &key, &keydata);
 				state = DATA;
@@ -271,13 +303,13 @@ lkey:			switch(command) {
 				break;
 			case REMOVE:
 				rem(dbp, &key);
-				if (type != DB_RECNO)
+				if ((type != DB_RECNO) && (flags != R_CURSOR))
 					free(key.data);
 				state = COMMAND;
 				break;
 			case SEQ:
 				seq(dbp, &key);
-				if (type != DB_RECNO)
+				if ((type != DB_RECNO) && (flags != R_CURSOR))
 					free(key.data);
 				state = COMMAND;
 				break;
@@ -291,11 +323,15 @@ lkey:			switch(command) {
 			break;
 		default:
 			err("line %lu: %s: unknown command character",
-			    p, lineno);
+			    lineno, p);
 		}
 	}
 #ifdef STATISTICS
-	if (type == DB_BTREE)
+	/*
+	 * -l must be used (DB_LOCK must be set) for this to be
+	 * used, otherwise a page will be locked and it will fail.
+	 */
+	if (type == DB_BTREE && oflags & DB_LOCK)
 		__bt_stat(dbp);
 #endif
 	if (dbp->close(dbp))
@@ -305,7 +341,6 @@ lkey:			switch(command) {
 }
 
 #define	NOOVERWRITE	"put failed, would overwrite key\n"
-#define	NOSUCHKEY	"get failed, no such key\n"
 
 void
 compare(db1, db2)
@@ -334,17 +369,23 @@ get(dbp, kp)
 {
 	DBT data;
 
-	switch(dbp->get(dbp, kp, &data, flags)) {
+	switch (dbp->get(dbp, kp, &data, flags)) {
 	case 0:
 		(void)write(ofd, data.data, data.size);
+		if (ofd == STDOUT_FILENO)
+			(void)write(ofd, "\n", 1);
 		break;
 	case -1:
 		err("line %lu: get: %s", lineno, strerror(errno));
 		/* NOTREACHED */
 	case 1:
-		(void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1);
-		(void)fprintf(stderr, "%d: %.*s: %s\n", 
-		    lineno, kp->size, kp->data, NOSUCHKEY);
+#define	NOSUCHKEY	"get failed, no such key\n"
+		if (ofd != STDOUT_FILENO)
+			(void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1);
+		else
+			(void)fprintf(stderr, "%d: %.*s: %s",
+			    lineno, MIN(kp->size, 20), kp->data, NOSUCHKEY);
+#undef	NOSUCHKEY
 		break;
 	}
 }
@@ -354,14 +395,14 @@ getdata(dbp, kp, dp)
 	DB *dbp;
 	DBT *kp, *dp;
 {
-	switch(dbp->get(dbp, kp, dp, flags)) {
+	switch (dbp->get(dbp, kp, dp, flags)) {
 	case 0:
 		return;
 	case -1:
 		err("line %lu: getdata: %s", lineno, strerror(errno));
 		/* NOTREACHED */
 	case 1:
-		err("line %lu: get failed, no such key", lineno);
+		err("line %lu: getdata failed, no such key", lineno);
 		/* NOTREACHED */
 	}
 }
@@ -371,7 +412,7 @@ put(dbp, kp, dp)
 	DB *dbp;
 	DBT *kp, *dp;
 {
-	switch(dbp->put(dbp, kp, dp, flags)) {
+	switch (dbp->put(dbp, kp, dp, flags)) {
 	case 0:
 		break;
 	case -1:
@@ -388,34 +429,67 @@ rem(dbp, kp)
 	DB *dbp;
 	DBT *kp;
 {
-	switch(dbp->del(dbp, kp, flags)) {
+	switch (dbp->del(dbp, kp, flags)) {
 	case 0:
 		break;
 	case -1:
-		err("line %lu: get: %s", lineno, strerror(errno));
+		err("line %lu: rem: %s", lineno, strerror(errno));
 		/* NOTREACHED */
 	case 1:
-		(void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1);
+#define	NOSUCHKEY	"rem failed, no such key\n"
+		if (ofd != STDOUT_FILENO)
+			(void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1);
+		else if (flags != R_CURSOR)
+			(void)fprintf(stderr, "%d: %.*s: %s", 
+			    lineno, MIN(kp->size, 20), kp->data, NOSUCHKEY);
+		else
+			(void)fprintf(stderr,
+			    "%d: rem of cursor failed\n", lineno);
+#undef	NOSUCHKEY
 		break;
 	}
 }
 
 void
+synk(dbp)
+	DB *dbp;
+{
+	switch (dbp->sync(dbp, flags)) {
+	case 0:
+		break;
+	case -1:
+		err("line %lu: synk: %s", lineno, strerror(errno));
+		/* NOTREACHED */
+	}
+}
+
+void
 seq(dbp, kp)
 	DB *dbp;
 	DBT *kp;
 {
 	DBT data;
 
-	switch(dbp->seq(dbp, kp, &data, flags)) {
+	switch (dbp->seq(dbp, kp, &data, flags)) {
 	case 0:
 		(void)write(ofd, data.data, data.size);
+		if (ofd == STDOUT_FILENO)
+			(void)write(ofd, "\n", 1);
 		break;
 	case -1:
 		err("line %lu: seq: %s", lineno, strerror(errno));
 		/* NOTREACHED */
 	case 1:
-		(void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1);
+#define	NOSUCHKEY	"seq failed, no such key\n"
+		if (ofd != STDOUT_FILENO)
+			(void)write(ofd, NOSUCHKEY, sizeof(NOSUCHKEY) - 1);
+		else if (flags == R_CURSOR)
+			(void)fprintf(stderr, "%d: %.*s: %s", 
+			    lineno, MIN(kp->size, 20), kp->data, NOSUCHKEY);
+		else
+			(void)fprintf(stderr,
+			    "%d: seq (%s) failed\n", lineno, sflags(flags));
+#undef	NOSUCHKEY
 		break;
 	}
 }
@@ -436,9 +510,11 @@ dump(dbp, rev)
 		nflags = R_NEXT;
 	}
 	for (;; flags = nflags)
-		switch(dbp->seq(dbp, &key, &data, flags)) {
+		switch (dbp->seq(dbp, &key, &data, flags)) {
 		case 0:
 			(void)write(ofd, data.data, data.size);
+			if (ofd == STDOUT_FILENO)
+				(void)write(ofd, "\n", 1);
 			break;
 		case 1:
 			goto done;
@@ -457,31 +533,42 @@ setflags(s)
 	char *p, *index();
 
 	for (; isspace(*s); ++s);
-	if (*s == '\n')
+	if (*s == '\n' || *s == '\0')
 		return (0);
 	if ((p = index(s, '\n')) != NULL)
 		*p = '\0';
-	if (!strcmp(s, "R_CURSOR"))
-		return (R_CURSOR);
-	if (!strcmp(s, "R_FIRST"))
-		return (R_FIRST);
-	if (!strcmp(s, "R_IAFTER"))
-		return (R_IAFTER);
-	if (!strcmp(s, "R_IBEFORE"))
-		return (R_IBEFORE);
-	if (!strcmp(s, "R_LAST"))
-		return (R_LAST);
-	if (!strcmp(s, "R_NEXT"))
-		return (R_NEXT);
-	if (!strcmp(s, "R_NOOVERWRITE"))
-		return (R_NOOVERWRITE);
-	if (!strcmp(s, "R_PREV"))
-		return (R_PREV);
-	if (!strcmp(s, "R_SETCURSOR"))
-		return (R_SETCURSOR);
+	if (!strcmp(s, "R_CURSOR"))		return (R_CURSOR);
+	if (!strcmp(s, "R_FIRST"))		return (R_FIRST);
+	if (!strcmp(s, "R_IAFTER")) 		return (R_IAFTER);
+	if (!strcmp(s, "R_IBEFORE")) 		return (R_IBEFORE);
+	if (!strcmp(s, "R_LAST")) 		return (R_LAST);
+	if (!strcmp(s, "R_NEXT")) 		return (R_NEXT);
+	if (!strcmp(s, "R_NOOVERWRITE"))	return (R_NOOVERWRITE);
+	if (!strcmp(s, "R_PREV"))		return (R_PREV);
+	if (!strcmp(s, "R_SETCURSOR"))		return (R_SETCURSOR);
+
 	err("line %lu: %s: unknown flag", lineno, s);
 	/* NOTREACHED */
 }
+
+char *
+sflags(flags)
+	int flags;
+{
+	switch (flags) {
+	case R_CURSOR:		return ("R_CURSOR");
+	case R_FIRST:		return ("R_FIRST");
+	case R_IAFTER:		return ("R_IAFTER");
+	case R_IBEFORE:		return ("R_IBEFORE");
+	case R_LAST:		return ("R_LAST");
+	case R_NEXT:		return ("R_NEXT");
+	case R_NOOVERWRITE:	return ("R_NOOVERWRITE");
+	case R_PREV:		return ("R_PREV");
+	case R_SETCURSOR:	return ("R_SETCURSOR");
+	}
+
+	return ("UNKNOWN!");
+}
 	
 DBTYPE
 dbtype(s)
@@ -513,7 +600,7 @@ setinfo(type, s)
 	if (!isdigit(*eq))
 		err("%s: structure set statement must be a number", s);
 		
-	switch(type) {
+	switch (type) {
 	case DB_BTREE:
 		if (!strcmp("flags", s)) {
 			ib.flags = atoi(eq);
diff --git a/regress/lib/libc/db/run.test b/regress/lib/libc/db/run.test
index 4073310a311..acbd3f49e17 100644
--- a/regress/lib/libc/db/run.test
+++ b/regress/lib/libc/db/run.test
@@ -1,19 +1,27 @@
 #!/bin/sh -
-#	$NetBSD: run.test,v 1.7 1995/04/20 22:39:27 cgd Exp $
 #
-#	@(#)run.test	8.8 (Berkeley) 6/16/94
+#	$NetBSD: run.test,v 1.8 1996/05/03 21:57:51 cgd Exp $
+#	@(#)run.test	8.10 (Berkeley) 7/26/94
 #
 
 # db regression tests
 main()
 {
 
-DICT=/usr/share/dict/web2
-PROG=./dbtest
-TMP1=t1
-TMP2=t2
-TMP3=t3
+	PROG=./dbtest
+	TMP1=t1
+	TMP2=t2
+	TMP3=t3
 
+	if [ -f /usr/share/dict/words ]; then
+		DICT=/usr/share/dict/words
+	elif [ -f /usr/dict/words ]; then
+		DICT=/usr/dict/words
+	else
+		echo 'run.test: no dictionary'
+		exit 1
+	fi
+	
 	if [ $# -eq 0 ]; then
 		for t in 1 2 3 4 5 6 7 8 9 10 11 12 13 20; do
 			test$t
@@ -345,7 +353,7 @@ test7()
 		for (i = 1; i <= 120; ++i)
 			printf("%05d: input key %d: %s\n", i, i, $0);
 		printf("%05d: input key %d: %s\n", 120, 120, $0);
-		printf("get failed, no such key\n");
+		printf("seq failed, no such key\n");
 		printf("%05d: input key %d: %s\n", 1, 1, $0);
 		printf("%05d: input key %d: %s\n", 2, 2, $0);
 		exit;
@@ -364,10 +372,10 @@ test7()
 			for (i = 1; i <= 120; ++i)
 				printf("s\n");
 			printf("fR_CURSOR\ns\nk120\n");
-			printf("r\nk120\n");
+			printf("r\n");
 			printf("fR_NEXT\ns\n");
 			printf("fR_CURSOR\ns\nk1\n");
-			printf("r\nk1\n");
+			printf("r\n");
 			printf("fR_FIRST\ns\n");
 		}' > $TMP2
 		$PROG -o $TMP3 recno $TMP2
@@ -397,8 +405,6 @@ test8()
 				printf("e\t%d of 10             \n", i);
 			printf("r\nkkey1\nr\nkkey2\n");
 		}
-		printf("e\n");
-		printf("eend of test8 run\n");
 	}' > $TMP1
 	$PROG btree $TMP1
 #	$PROG hash $TMP1
@@ -459,7 +465,7 @@ test10()
 			printf("p\nk%d\nd%s\n", ++i, $0);
 		}
 		END {
-			printf("fR_CURSOR\nr\nk1\n");
+			printf("fR_CURSOR\nr\n");
 			printf("eR_CURSOR SHOULD HAVE FAILED\n");
 		}' > $TMP2
 		$PROG -o $TMP3 $type $TMP2 > /dev/null 2>&1
@@ -573,7 +579,8 @@ test13()
 				echo g
 				echo k$i
 			done > $TMP2
-			$PROG -ilorder=$order -f byte.file -o $TMP3 $type $TMP2
+			$PROG -s \
+			    -ilorder=$order -f byte.file -o $TMP3 $type $TMP2
 			if (cmp -s $TMP1 $TMP3) ; then :
 			else
 				echo "test13: $type/$order get failed"