this commit includes all the changes on the OV_9510_INTEGRATION and

OV_MERGE branches.  This includes, but is not limited to, the new openvision
admin system, and major changes to gssapi to add functionality, and bring
the implementation in line with rfc1964.  before committing, the
code was built and tested for netbsd and solaris.

git-svn-id: svn://anonsvn.mit.edu/krb5/trunk@8774 dc483132-0cff-0310-8789-dd5450dbe970

15 files changed, 4347 insertions, 0 deletions

diff --git a/src/util/db2/hash/Makefile.inc b/src/util/db2/hash/Makefile.inc
new file mode 100644
index 000000000..87746f721
--- /dev/null
+++ b/src/util/db2/hash/Makefile.inc
@@ -0,0 +1,6 @@
+#       @(#)Makefile.inc	8.2 (Berkeley) 11/7/95
+
+.PATH: ${.CURDIR}/db/hash
+
+SRCS+=	hash.c hash_bigkey.c hash_buf.c hash_func.c hash_log2.c \
+	hash_page.c hsearch.c dbm.c
diff --git a/src/util/db2/hash/dbm.c b/src/util/db2/hash/dbm.c
new file mode 100644
index 000000000..a5a31f45b
--- /dev/null
+++ b/src/util/db2/hash/dbm.c
@@ -0,0 +1,297 @@
+/*-
+ * Copyright (c) 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Margo Seltzer.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)dbm.c	8.6 (Berkeley) 11/7/95";
+#endif /* LIBC_SCCS and not lint */
+
+#include "db-int.h"
+
+#include <sys/param.h>
+
+#include <fcntl.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "db-ndbm.h"
+#include "hash.h"
+
+/*
+ *
+ * This package provides dbm and ndbm compatible interfaces to DB.
+ * First are the DBM routines, which call the NDBM routines, and
+ * the NDBM routines, which call the DB routines.
+ */
+static DBM *__cur_db;
+
+static void no_open_db __P((void));
+
+int
+dbminit(file)
+	char *file;
+{
+	if (__cur_db != NULL)
+		(void)dbm_close(__cur_db);
+	if ((__cur_db = dbm_open(file, O_RDWR, 0)) != NULL)
+		return (0);
+	if ((__cur_db = dbm_open(file, O_RDONLY, 0)) != NULL)
+		return (0);
+	return (-1);
+}
+
+datum
+fetch(key)
+	datum key;
+{
+	datum item;
+
+	if (__cur_db == NULL) {
+		no_open_db();
+		item.dptr = 0;
+		return (item);
+	}
+	return (dbm_fetch(__cur_db, key));
+}
+
+datum
+firstkey()
+{
+	datum item;
+
+	if (__cur_db == NULL) {
+		no_open_db();
+		item.dptr = 0;
+		return (item);
+	}
+	return (dbm_firstkey(__cur_db));
+}
+
+datum
+nextkey(key)
+	datum key;
+{
+	datum item;
+
+	if (__cur_db == NULL) {
+		no_open_db();
+		item.dptr = 0;
+		return (item);
+	}
+	return (dbm_nextkey(__cur_db));
+}
+
+int
+delete(key)
+	datum key;
+{
+	if (__cur_db == NULL) {
+		no_open_db();
+		return (-1);
+	}
+	return (dbm_delete(__cur_db, key));
+}
+
+int
+store(key, dat)
+	datum key, dat;
+{
+	if (__cur_db == NULL) {
+		no_open_db();
+		return (-1);
+	}
+	return (dbm_store(__cur_db, key, dat, DBM_REPLACE));
+}
+
+static void
+no_open_db()
+{
+	(void)fprintf(stderr, "dbm: no open database.\n");
+}
+
+/*
+ * Returns:
+ * 	*DBM on success
+ *	 NULL on failure
+ */
+DBM *
+dbm_open(file, flags, mode)
+	const char *file;
+	int flags, mode;
+{
+	HASHINFO info;
+	char path[MAXPATHLEN];
+
+	info.bsize = 4096;
+	info.ffactor = 40;
+	info.nelem = 1;
+	info.cachesize = 0;
+	info.hash = NULL;
+	info.lorder = 0;
+	(void)strcpy(path, file);
+	(void)strcat(path, DBM_SUFFIX);
+	return ((DBM *)__hash_open(path, flags, mode, &info, 0));
+}
+
+/*
+ * Returns:
+ *	Nothing.
+ */
+void
+dbm_close(db)
+	DBM *db;
+{
+	(void)(db->close)(db);
+}
+
+/*
+ * Returns:
+ *	DATUM on success
+ *	NULL on failure
+ */
+datum
+dbm_fetch(db, key)
+	DBM *db;
+	datum key;
+{
+	datum retval;
+	int status;
+
+	status = (db->get)(db, (DBT *)&key, (DBT *)&retval, 0);
+	if (status) {
+		retval.dptr = NULL;
+		retval.dsize = 0;
+	}
+	return (retval);
+}
+
+/*
+ * Returns:
+ *	DATUM on success
+ *	NULL on failure
+ */
+datum
+dbm_firstkey(db)
+	DBM *db;
+{
+	int status;
+	datum retdata, retkey;
+
+	status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_FIRST);
+	if (status)
+		retkey.dptr = NULL;
+	return (retkey);
+}
+
+/*
+ * Returns:
+ *	DATUM on success
+ *	NULL on failure
+ */
+datum
+dbm_nextkey(db)
+	DBM *db;
+{
+	int status;
+	datum retdata, retkey;
+
+	status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_NEXT);
+	if (status)
+		retkey.dptr = NULL;
+	return (retkey);
+}
+
+/*
+ * Returns:
+ *	 0 on success
+ *	<0 failure
+ */
+int
+dbm_delete(db, key)
+	DBM *db;
+	datum key;
+{
+	int status;
+
+	status = (db->del)(db, (DBT *)&key, 0);
+	if (status)
+		return (-1);
+	else
+		return (0);
+}
+
+/*
+ * Returns:
+ *	 0 on success
+ *	<0 failure
+ *	 1 if DBM_INSERT and entry exists
+ */
+int
+dbm_store(db, key, content, flags)
+	DBM *db;
+	datum key, content;
+	int flags;
+{
+	return ((db->put)(db, (DBT *)&key, (DBT *)&content,
+	    (flags == DBM_INSERT) ? R_NOOVERWRITE : 0));
+}
+
+int
+dbm_error(db)
+	DBM *db;
+{
+	HTAB *hp;
+
+	hp = (HTAB *)db->internal;
+	return (hp->errno);
+}
+
+int
+dbm_clearerr(db)
+	DBM *db;
+{
+	HTAB *hp;
+
+	hp = (HTAB *)db->internal;
+	hp->errno = 0;
+	return (0);
+}
+
+int
+dbm_dirfno(db)
+	DBM *db;
+{
+	return(((HTAB *)db->internal)->fp);
+}
diff --git a/src/util/db2/hash/extern.h b/src/util/db2/hash/extern.h
new file mode 100644
index 000000000..dd8a34e8e
--- /dev/null
+++ b/src/util/db2/hash/extern.h
@@ -0,0 +1,76 @@
+/*-
+ * Copyright (c) 1991, 1993, 1994
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	@(#)extern.h	8.8 (Berkeley) 11/7/95
+ */
+
+PAGE16	 *__add_bigpage __P((HTAB *, PAGE16 *, indx_t, const u_int8_t));
+PAGE16	 *__add_ovflpage __P((HTAB *, PAGE16 *));
+int32_t	  __addel __P((HTAB *, ITEM_INFO *,
+		const DBT *, const DBT *, u_int32_t, const u_int8_t));
+u_int32_t __alloc_tmp __P((HTAB*));
+int32_t	  __big_delete __P((HTAB *, PAGE16 *, indx_t));
+int32_t	  __big_insert __P((HTAB *, PAGE16 *, const DBT *, const DBT *));
+int32_t	  __big_keydata __P((HTAB *, PAGE16 *, DBT *, DBT *, int32_t));
+int32_t	  __big_return __P((HTAB *, ITEM_INFO *, DBT *, int32_t));
+u_int32_t __call_hash __P((HTAB *, int8_t *, int32_t));
+CURSOR	 *__cursor_creat __P((const DB *));
+int32_t	  __delete_page __P((HTAB *, PAGE16 *, int32_t));
+int32_t	  __delpair __P((HTAB *, CURSOR *, ITEM_INFO *));
+int32_t	  __expand_table __P((HTAB *));
+int32_t	  __find_bigpair __P((HTAB *, CURSOR *, int8_t *, int32_t));
+void	  __free_ovflpage __P((HTAB *, PAGE16 *));
+int32_t	  __get_bigkey __P((HTAB *, PAGE16 *, indx_t, DBT *));
+PAGE16	 *__get_buf __P((HTAB *, u_int32_t, int32_t));
+u_int32_t __get_item __P((HTAB *, CURSOR *, DBT *, DBT *, ITEM_INFO *));
+u_int32_t __get_item_done __P((HTAB *, CURSOR *));
+u_int32_t __get_item_first __P((HTAB *, CURSOR *, DBT *, DBT *, ITEM_INFO *));
+u_int32_t __get_item_next __P((HTAB *, CURSOR *, DBT *, DBT *, ITEM_INFO *));
+u_int32_t __get_item_reset __P((HTAB *, CURSOR *));
+PAGE16	 *__get_page __P((HTAB *, u_int32_t, int32_t));
+int32_t	  __ibitmap __P((HTAB *, int32_t, int32_t, int32_t));
+u_int32_t __log2 __P((u_int32_t));
+int32_t	  __new_page __P((HTAB *, u_int32_t, int32_t));
+void	  __pgin_routine __P((void *, db_pgno_t, void *));
+void	  __pgout_routine __P((void *, db_pgno_t, void *));
+u_int32_t __put_buf __P((HTAB *, PAGE16 *, u_int32_t));
+int32_t	  __put_page __P((HTAB *, PAGE16 *, int32_t, int32_t));
+void	  __reclaim_tmp __P((HTAB *));
+int32_t	  __split_page __P((HTAB *, u_int32_t, u_int32_t));
+
+/* Default hash routine. */
+extern u_int32_t (*__default_hash) __P((const void *, size_t));
+
+#ifdef HASH_STATISTICS
+extern long hash_accesses, hash_bigpages, hash_collisions, hash_expansions;
+extern long hash_overflow;
+#endif
diff --git a/src/util/db2/hash/hash.c b/src/util/db2/hash/hash.c
new file mode 100644
index 000000000..017138606
--- /dev/null
+++ b/src/util/db2/hash/hash.c
@@ -0,0 +1,1068 @@
+/*-
+ * 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
+ * Margo Seltzer.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)hash.c	8.12 (Berkeley) 11/7/95";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/param.h>
+#include <sys/stat.h>
+
+#include <errno.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#ifdef DEBUG
+#include <assert.h>
+#endif
+
+#include "db-int.h"
+#include "hash.h"
+#include "page.h"
+#include "extern.h"
+
+static int32_t flush_meta __P((HTAB *));
+static int32_t hash_access __P((HTAB *, ACTION, DBT *, DBT *));
+static int32_t hash_close __P((DB *));
+static int32_t hash_delete __P((const DB *, const DBT *, u_int32_t));
+static int32_t hash_fd __P((const DB *));
+static int32_t hash_get __P((const DB *, const DBT *, DBT *, u_int32_t));
+static int32_t hash_put __P((const DB *, DBT *, const DBT *, u_int32_t));
+static int32_t hash_seq __P((const DB *, DBT *, DBT *, u_int32_t));
+static int32_t hash_sync __P((const DB *, u_int32_t));
+static int32_t hdestroy __P((HTAB *));
+static int32_t cursor_get __P((const DB *, CURSOR *, DBT *, DBT *, \
+	u_int32_t));
+static int32_t cursor_delete __P((const DB *, CURSOR *, u_int32_t));
+static HTAB *init_hash __P((HTAB *, const char *, HASHINFO *));
+static int32_t init_htab __P((HTAB *, int32_t));
+#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
+static void swap_header __P((HTAB *));
+static void swap_header_copy __P((HASHHDR *, HASHHDR *));
+#endif
+static u_int32_t hget_header __P((HTAB *, u_int32_t));
+static void hput_header __P((HTAB *));
+
+#define RETURN_ERROR(ERR, LOC)	{ save_errno = ERR; goto LOC; }
+
+/* Return values */
+#define	SUCCESS	 (0)
+#define	ERROR	(-1)
+#define	ABNORMAL (1)
+
+#ifdef HASH_STATISTICS
+u_int32_t hash_accesses, hash_collisions, hash_expansions, hash_overflows,
+	hash_bigpages;
+#endif
+
+/************************** INTERFACE ROUTINES ***************************/
+/* OPEN/CLOSE */
+
+extern DB *
+__hash_open(file, flags, mode, info, dflags)
+	const char *file;
+	int32_t flags, mode, dflags;
+	const HASHINFO *info;	/* Special directives for create */
+{
+	struct stat statbuf;
+	DB *dbp;
+	DBT mpool_key;
+	HTAB *hashp;
+	int32_t bpages, csize, new_table, save_errno, specified_file;
+
+	if ((flags & O_ACCMODE) == O_WRONLY) {
+		errno = EINVAL;
+		return (NULL);
+	}
+	if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB))))
+		return (NULL);
+	hashp->fp = -1;
+
+	/* set this now, before file goes away... */
+	specified_file = (file != NULL);
+	if (!file) {
+		file = tmpnam(NULL);
+		/* store the file name so that we can unlink it later */
+		hashp->fname = (char *)file;
+#ifdef DEBUG
+		fprintf(stderr, "Using file name %s.\n", file);
+#endif
+	}
+	/*
+	 * Even if user wants write only, we need to be able to read
+	 * the actual file, so we need to open it read/write. But, the
+	 * field in the hashp structure needs to be accurate so that
+	 * we can check accesses.
+	 */
+	hashp->flags = flags;
+	hashp->save_file = specified_file && (hashp->flags & O_RDWR);
+
+	new_table = 0;
+	if (!file || (flags & O_TRUNC) ||
+	    (stat(file, &statbuf) && (errno == ENOENT))) {
+		if (errno == ENOENT)
+			errno = 0;	/* In case someone looks at errno. */
+		new_table = 1;
+	}
+	if (file) {
+		if ((hashp->fp = open(file, flags, mode)) == -1)
+			RETURN_ERROR(errno, error0);
+		(void)fcntl(hashp->fp, F_SETFD, 1);
+	}
+
+	/* Process arguments to set up hash table header. */
+	if (new_table) {
+		if (!(hashp = init_hash(hashp, file, (HASHINFO *)info)))
+			RETURN_ERROR(errno, error1);
+	} else {
+		/* Table already exists */
+		if (info && info->hash)
+			hashp->hash = info->hash;
+		else
+			hashp->hash = __default_hash;
+
+		/* copy metadata from page into header */
+		if (hget_header(hashp,
+		    (info && info->bsize ? info->bsize : DEF_BUCKET_SIZE)) !=
+		    sizeof(HASHHDR))
+			RETURN_ERROR(EFTYPE, error1);
+
+		/* Verify file type, versions and hash function */
+		if (hashp->hdr.magic != HASHMAGIC)
+			RETURN_ERROR(EFTYPE, error1);
+#define	OLDHASHVERSION	1
+		if (hashp->hdr.version != HASHVERSION &&
+		    hashp->hdr.version != OLDHASHVERSION)
+			RETURN_ERROR(EFTYPE, error1);
+		if (hashp->hash(CHARKEY, sizeof(CHARKEY))
+		    != hashp->hdr.h_charkey)
+			RETURN_ERROR(EFTYPE, error1);
+		/*
+		 * Figure out how many segments we need.  Max_Bucket is the
+		 * maximum bucket number, so the number of buckets is
+		 * max_bucket + 1.
+		 */
+
+		/* Read in bitmaps */
+		bpages = (hashp->hdr.spares[hashp->hdr.ovfl_point] +
+		    (hashp->hdr.bsize << BYTE_SHIFT) - 1) >>
+		    (hashp->hdr.bshift + BYTE_SHIFT);
+
+		hashp->nmaps = bpages;
+		(void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_int32_t *));
+	}
+
+	/* start up mpool */
+	mpool_key.data = (u_int8_t *)file;
+	mpool_key.size = strlen(file);
+
+	if (info && info->cachesize)
+		csize = info->cachesize / hashp->hdr.bsize;
+	else
+		csize = DEF_CACHESIZE / hashp->hdr.bsize;
+	hashp->mp = mpool_open(&mpool_key, hashp->fp, hashp->hdr.bsize, csize);
+
+	if (!hashp->mp)
+		RETURN_ERROR(errno, error1);
+	mpool_filter(hashp->mp, __pgin_routine, __pgout_routine, hashp);
+
+	/*
+	 * For a new table, set up the bitmaps.
+	 */
+	if (new_table &&
+	   init_htab(hashp, info && info->nelem ? info->nelem : 1))
+		goto error2;
+
+	/* initialize the cursor queue */
+	TAILQ_INIT(&hashp->curs_queue);
+	hashp->seq_cursor = NULL;
+
+
+	/* get a chunk of memory for our split buffer */
+	hashp->split_buf = (PAGE16 *)malloc(hashp->hdr.bsize);
+	if (!hashp->split_buf)
+		goto error2;
+
+	hashp->new_file = new_table;
+
+	if (!(dbp = (DB *)malloc(sizeof(DB))))
+		goto error2;
+
+	dbp->internal = hashp;
+	dbp->close = hash_close;
+	dbp->del = hash_delete;
+	dbp->fd = hash_fd;
+	dbp->get = hash_get;
+	dbp->put = hash_put;
+	dbp->seq = hash_seq;
+	dbp->sync = hash_sync;
+	dbp->type = DB_HASH;
+
+#ifdef DEBUG
+	(void)fprintf(stderr,
+	    "%s\n%s%lx\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
+	    "init_htab:",
+	    "TABLE POINTER   ", (void *)hashp,
+	    "BUCKET SIZE     ", hashp->hdr.bsize,
+	    "BUCKET SHIFT    ", hashp->hdr.bshift,
+	    "FILL FACTOR     ", hashp->hdr.ffactor,
+	    "MAX BUCKET      ", hashp->hdr.max_bucket,
+	    "OVFL POINT      ", hashp->hdr.ovfl_point,
+	    "LAST FREED      ", hashp->hdr.last_freed,
+	    "HIGH MASK       ", hashp->hdr.high_mask,
+	    "LOW  MASK       ", hashp->hdr.low_mask,
+	    "NKEYS           ", hashp->hdr.nkeys);
+#endif
+#ifdef HASH_STATISTICS
+	hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
+	hash_bigpages = 0;
+#endif
+	return (dbp);
+
+error2:
+	save_errno = errno;
+	hdestroy(hashp);
+	errno = save_errno;
+	return (NULL);
+
+error1:
+	if (hashp != NULL)
+		(void)close(hashp->fp);
+
+error0:
+	free(hashp);
+	errno = save_errno;
+	return (NULL);
+}
+
+static int32_t
+hash_close(dbp)
+	DB *dbp;
+{
+	HTAB *hashp;
+	int32_t retval;
+
+	if (!dbp)
+		return (ERROR);
+
+	hashp = (HTAB *)dbp->internal;
+	retval = hdestroy(hashp);
+	free(dbp);
+	return (retval);
+}
+
+static int32_t
+hash_fd(dbp)
+	const DB *dbp;
+{
+	HTAB *hashp;
+
+	if (!dbp)
+		return (ERROR);
+
+	hashp = (HTAB *)dbp->internal;
+	if (hashp->fp == -1) {
+		errno = ENOENT;
+		return (-1);
+	}
+	return (hashp->fp);
+}
+
+/************************** LOCAL CREATION ROUTINES **********************/
+static HTAB *
+init_hash(hashp, file, info)
+	HTAB *hashp;
+	const char *file;
+	HASHINFO *info;
+{
+	struct stat statbuf;
+	int32_t nelem;
+
+	nelem = 1;
+	hashp->hdr.nkeys = 0;
+	hashp->hdr.lorder = DB_BYTE_ORDER;
+	hashp->hdr.bsize = DEF_BUCKET_SIZE;
+	hashp->hdr.bshift = DEF_BUCKET_SHIFT;
+	hashp->hdr.ffactor = DEF_FFACTOR;
+	hashp->hash = __default_hash;
+	memset(hashp->hdr.spares, 0, sizeof(hashp->hdr.spares));
+	memset(hashp->hdr.bitmaps, 0, sizeof(hashp->hdr.bitmaps));
+
+	/* Fix bucket size to be optimal for file system */
+	if (file != NULL) {
+		if (stat(file, &statbuf))
+			return (NULL);
+		hashp->hdr.bsize = statbuf.st_blksize;
+		hashp->hdr.bshift = __log2(hashp->hdr.bsize);
+	}
+	if (info) {
+		if (info->bsize) {
+			/* Round pagesize up to power of 2 */
+			hashp->hdr.bshift = __log2(info->bsize);
+			hashp->hdr.bsize = 1 << hashp->hdr.bshift;
+			if (hashp->hdr.bsize > MAX_BSIZE) {
+				errno = EINVAL;
+				return (NULL);
+			}
+		}
+		if (info->ffactor)
+			hashp->hdr.ffactor = info->ffactor;
+		if (info->hash)
+			hashp->hash = info->hash;
+		if (info->lorder) {
+			if ((info->lorder != DB_BIG_ENDIAN) &&
+			    (info->lorder != DB_LITTLE_ENDIAN)) {
+				errno = EINVAL;
+				return (NULL);
+			}
+			hashp->hdr.lorder = info->lorder;
+		}
+	}
+	return (hashp);
+}
+
+/*
+ * Returns 0 on No Error
+ */
+static int32_t
+init_htab(hashp, nelem)
+	HTAB *hashp;
+	int32_t nelem;
+{
+	int32_t l2, nbuckets;
+	db_pgno_t i;
+
+	/*
+	 * Divide number of elements by the fill factor and determine a
+	 * desired number of buckets.  Allocate space for the next greater
+	 * power of two number of buckets.
+	 */
+	nelem = (nelem - 1) / hashp->hdr.ffactor + 1;
+
+	l2 = __log2(MAX(nelem, 2));
+	nbuckets = 1 << l2;
+
+	hashp->hdr.spares[l2] = l2 + 1;
+	hashp->hdr.spares[l2 + 1] = l2 + 1;
+	hashp->hdr.ovfl_point = l2;
+	hashp->hdr.last_freed = 2;
+
+	hashp->hdr.max_bucket = hashp->hdr.low_mask = nbuckets - 1;
+	hashp->hdr.high_mask = (nbuckets << 1) - 1;
+
+	/*
+	 * The number of header pages is the size of the header divided by
+	 * the amount of freespace on header pages (the page size - the
+	 * size of 1 integer where the length of the header info on that
+	 * page is stored) plus another page if it didn't divide evenly.
+	 */
+	hashp->hdr.hdrpages =
+	    (sizeof(HASHHDR) / (hashp->hdr.bsize - HEADER_OVERHEAD)) +
+	    (((sizeof(HASHHDR) % (hashp->hdr.bsize - HEADER_OVERHEAD)) == 0)
+	    ? 0 : 1);
+
+	/* Create pages for these buckets */
+	/*
+	for (i = 0; i <= hashp->hdr.max_bucket; i++) {
+		if (__new_page(hashp, (u_int32_t)i, A_BUCKET) != 0)
+			return (-1);
+	}
+	*/
+
+	/* First bitmap page is at: splitpoint l2 page offset 1 */
+	if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))
+		return (-1);
+
+	return (0);
+}
+
+/*
+ * Functions to get/put hash header.  We access the file directly.
+ */
+u_int32_t
+hget_header(hashp, page_size)
+	HTAB *hashp;
+	u_int32_t page_size;
+{
+	u_int32_t num_copied, i;
+	u_int8_t *hdr_dest;
+
+	num_copied = 0;
+	i = 0;
+
+	hdr_dest = (u_int8_t *)&hashp->hdr;
+
+	/* 
+	 * XXX
+	 * This should not be printing to stderr on a "normal" error case.
+	 */
+	lseek(hashp->fp, 0, SEEK_SET);
+	num_copied = read(hashp->fp, hdr_dest, sizeof(HASHHDR));
+	if (num_copied != sizeof(HASHHDR)) {
+		fprintf(stderr, "hash: could not retrieve header");
+		return (0);
+	}
+#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
+	swap_header(hashp);
+#endif
+	return (num_copied);
+}
+
+void
+hput_header(hashp)
+	HTAB *hashp;
+{
+	HASHHDR *whdrp;
+#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
+	HASHHDR whdr;
+#endif
+	u_int32_t num_copied, i;
+
+	num_copied = i = 0;
+
+	whdrp = &hashp->hdr;
+#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
+	whdrp = &whdr;
+	swap_header_copy(&hashp->hdr, whdrp);
+#endif
+
+	lseek(hashp->fp, 0, SEEK_SET);
+	num_copied = write(hashp->fp, whdrp, sizeof(HASHHDR));
+	if (num_copied != sizeof(HASHHDR))
+		(void)fprintf(stderr, "hash: could not write hash header");
+	return;
+}
+
+/********************** DESTROY/CLOSE ROUTINES ************************/
+
+/*
+ * Flushes any changes to the file if necessary and destroys the hashp
+ * structure, freeing all allocated space.
+ */
+static int32_t
+hdestroy(hashp)
+	HTAB *hashp;
+{
+	int32_t save_errno;
+
+	save_errno = 0;
+
+#ifdef HASH_STATISTICS
+	{ int i;
+	(void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
+	    hash_accesses, hash_collisions);
+	(void)fprintf(stderr,
+	    "hdestroy: expansions %ld\n", hash_expansions);
+	(void)fprintf(stderr,
+	    "hdestroy: overflows %ld\n", hash_overflows);
+	(void)fprintf(stderr,
+	    "hdestroy: big key/data pages %ld\n", hash_bigpages);
+	(void)fprintf(stderr,
+	    "keys %ld maxp %d\n", hashp->hdr.nkeys, hashp->hdr.max_bucket);
+
+	for (i = 0; i < NCACHED; i++)
+		(void)fprintf(stderr,
+		    "spares[%d] = %d\n", i, hashp->hdr.spares[i]);
+	}
+#endif
+
+	if (flush_meta(hashp) && !save_errno)
+		save_errno = errno;
+
+	/* Free the split page */
+	if (hashp->split_buf)
+		free(hashp->split_buf);
+
+	/* Free the big key and big data returns */
+	if (hashp->bigkey_buf)
+		free(hashp->bigkey_buf);
+	if (hashp->bigdata_buf)
+		free(hashp->bigdata_buf);
+ 
+	/* XXX This should really iterate over the cursor queue, but
+	   it's not clear how to do that, and the only cursor a hash
+	   table ever creates is the one used by hash_seq().  Passing
+	   NULL as the first arg is also a kludge, but I know that
+	   it's never used, so I do it.  The intent is to plug the
+	   memory leak.  Correctness can come later. */
+ 
+	if (hashp->seq_cursor)
+		hashp->seq_cursor->delete(NULL, hashp->seq_cursor, 0);
+
+	/* shut down mpool */
+	mpool_sync(hashp->mp);
+	mpool_close(hashp->mp);
+
+	if (hashp->fp != -1)
+		(void)close(hashp->fp);
+
+	/* 
+	 * *** This may cause problems if hashp->fname is set in any case
+	 * other than the case that we are generating a temporary file name.
+	 * Note that the new version of mpool should support temporary
+	 * files within mpool itself.
+	 */
+	if (hashp->fname && !hashp->save_file) {
+#ifdef DEBUG
+		fprintf(stderr, "Unlinking file %s.\n", hashp->fname);
+#endif
+		/* we need to chmod the file to allow it to be deleted... */
+		chmod(hashp->fname, 0700);
+		unlink(hashp->fname);
+		/* destroy the temporary name */
+		tmpnam(NULL);
+	}
+	free(hashp);
+
+	if (save_errno) {
+		errno = save_errno;
+		return (ERROR);
+	}
+	return (SUCCESS);
+}
+
+/*
+ * Write modified pages to disk
+ *
+ * Returns:
+ *	 0 == OK
+ *	-1 ERROR
+ */
+static int32_t
+hash_sync(dbp, flags)
+	const DB *dbp;
+	u_int32_t flags;
+{
+	HTAB *hashp;
+
+	hashp = (HTAB *)dbp->internal;
+
+	/*
+	 * XXX
+	 * Check success/failure conditions.
+	 */
+	return (flush_meta(hashp) || mpool_sync(hashp->mp));
+}
+
+/*
+ * Returns:
+ *	 0 == OK
+ *	-1 indicates that errno should be set
+ */
+static int32_t
+flush_meta(hashp)
+	HTAB *hashp;
+{
+	int32_t i;
+
+	if (!hashp->save_file)
+		return (0);
+	hashp->hdr.magic = HASHMAGIC;
+	hashp->hdr.version = HASHVERSION;
+	hashp->hdr.h_charkey = hashp->hash(CHARKEY, sizeof(CHARKEY));
+
+	/* write out metadata */
+	hput_header(hashp);
+
+	for (i = 0; i < NCACHED; i++)
+		if (hashp->mapp[i]) {
+			if (__put_page(hashp,
+			    (PAGE16 *)hashp->mapp[i], A_BITMAP, 1))
+				return (-1);
+			hashp->mapp[i] = NULL;
+		}
+	return (0);
+}
+
+/*******************************SEARCH ROUTINES *****************************/
+/*
+ * All the access routines return
+ *
+ * Returns:
+ *	 0 on SUCCESS
+ *	 1 to indicate an external ERROR (i.e. key not found, etc)
+ *	-1 to indicate an internal ERROR (i.e. out of memory, etc)
+ */
+
+/* *** make sure this is true! */
+
+static int32_t
+hash_get(dbp, key, data, flag)
+	const DB *dbp;
+	const DBT *key;
+	DBT *data;
+	u_int32_t flag;
+{
+	HTAB *hashp;
+
+	hashp = (HTAB *)dbp->internal;
+	if (flag) {
+		hashp->errno = errno = EINVAL;
+		return (ERROR);
+	}
+	return (hash_access(hashp, HASH_GET, (DBT *)key, data));
+}
+
+static int32_t
+hash_put(dbp, key, data, flag)
+	const DB *dbp;
+	DBT *key;
+	const DBT *data;
+	u_int32_t flag;
+{
+	HTAB *hashp;
+
+	hashp = (HTAB *)dbp->internal;
+	if (flag && flag != R_NOOVERWRITE) {
+		hashp->errno = errno = EINVAL;
+		return (ERROR);
+	}
+	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
+		hashp->errno = errno = EPERM;
+		return (ERROR);
+	}
+	return (hash_access(hashp, flag == R_NOOVERWRITE ?
+		HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data));
+}
+
+static int32_t
+hash_delete(dbp, key, flag)
+	const DB *dbp;
+	const DBT *key;
+	u_int32_t flag;		/* Ignored */
+{
+	HTAB *hashp;
+
+	hashp = (HTAB *)dbp->internal;
+	if (flag) {
+		hashp->errno = errno = EINVAL;
+		return (ERROR);
+	}
+	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
+		hashp->errno = errno = EPERM;
+		return (ERROR);
+	}
+
+	return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL));
+}
+
+/*
+ * Assume that hashp has been set in wrapper routine.
+ */
+static int32_t
+hash_access(hashp, action, key, val)
+	HTAB *hashp;
+	ACTION action;
+	DBT *key, *val;
+{
+	DBT page_key, page_val;
+	CURSOR cursor;
+	ITEM_INFO item_info;
+	u_int32_t bucket;
+	u_int32_t num_items;
+
+#ifdef HASH_STATISTICS
+	hash_accesses++;
+#endif
+
+	num_items = 0;
+
+	/* 
+	 * Set up item_info so that we're looking for space to add an item
+	 * as we cycle through the pages looking for the key.
+	 */
+	if (action == HASH_PUT || action == HASH_PUTNEW) {
+		if (ISBIG(key->size + val->size, hashp))
+			item_info.seek_size = PAIR_OVERHEAD;
+		else
+			item_info.seek_size = key->size + val->size;
+	} else
+		item_info.seek_size = 0;
+	item_info.seek_found_page = 0;
+
+	bucket = __call_hash(hashp, (int8_t *)key->data, key->size);
+
+	cursor.pagep = NULL;
+	__get_item_reset(hashp, &cursor);
+
+	cursor.bucket = bucket;
+	while (1) {
+		__get_item_next(hashp, &cursor, &page_key, &page_val, &item_info);
+		if (item_info.status == ITEM_ERROR)
+			return (ABNORMAL);
+		if (item_info.status == ITEM_NO_MORE)
+			break;
+		num_items++;
+		if (item_info.key_off == BIGPAIR) {
+			/*
+			 * !!!
+			 * 0 is a valid index.
+			 */
+			if (__find_bigpair(hashp, &cursor, (int8_t *)key->data,
+			    key->size) > 0)
+				goto found;
+		} else if (key->size == page_key.size &&
+		    !memcmp(key->data, page_key.data, key->size))
+			goto found;
+	}
+#ifdef HASH_STATISTICS
+	hash_collisions++;
+#endif
+	__get_item_done(hashp, &cursor);
+
+	/*
+	 * At this point, item_info will list either the last page in
+	 * the chain, or the last page in the chain plus a pgno for where
+	 * to find the first page in the chain with space for the
+	 * item we wish to add.
+	 */
+
+	/* Not found */
+	switch (action) {
+	case HASH_PUT:
+	case HASH_PUTNEW:
+		if (__addel(hashp, &item_info, key, val, num_items, 0))
+			return (ERROR);
+		break;
+	case HASH_GET:
+	case HASH_DELETE:
+	default:
+		return (ABNORMAL);
+	}
+
+	if (item_info.caused_expand)
+		__expand_table(hashp);
+	return (SUCCESS);
+
+found:	__get_item_done(hashp, &cursor);
+
+	switch (action) {
+	case HASH_PUTNEW:
+		/* mpool_put(hashp->mp, pagep, 0); */
+		return (ABNORMAL);
+	case HASH_GET:
+		if (item_info.key_off == BIGPAIR) {
+			if (__big_return(hashp, &item_info, val, 0))
+				return (ERROR);
+		} else {
+			val->data = page_val.data;
+			val->size = page_val.size;
+		}
+		/* *** data may not be available! */
+		break;
+	case HASH_PUT:
+		if (__delpair(hashp, &cursor, &item_info) ||
+		    __addel(hashp, &item_info, key, val, UNKNOWN, 0))
+			return (ERROR);
+		__get_item_done(hashp, &cursor);
+		if (item_info.caused_expand)
+			__expand_table(hashp);
+		break;
+	case HASH_DELETE:
+		if (__delpair(hashp, &cursor, &item_info))
+			return (ERROR);
+		break;
+	default:
+		abort();
+	}
+	return (SUCCESS);
+}
+
+/* ****************** CURSORS ********************************** */
+CURSOR *
+__cursor_creat(dbp)
+	const DB *dbp;
+{
+	CURSOR *new_curs;
+	HTAB *hashp;
+
+	new_curs = (CURSOR *)malloc(sizeof(struct cursor_t));
+	if (!new_curs)
+		return NULL;
+	new_curs->internal =
+	    (struct item_info *)malloc(sizeof(struct item_info));
+	if (!new_curs->internal) {
+		free(new_curs);
+		return NULL;
+	}
+	new_curs->get = cursor_get;
+	new_curs->delete = cursor_delete;
+
+	new_curs->bucket = 0;
+	new_curs->pgno = INVALID_PGNO;
+	new_curs->ndx = 0;
+	new_curs->pgndx = 0;
+	new_curs->pagep = NULL;
+
+	/* place onto queue of cursors */
+	hashp = (HTAB *)dbp->internal;
+	TAILQ_INSERT_TAIL(&hashp->curs_queue, new_curs, queue);
+
+	return new_curs;
+}
+
+int32_t
+cursor_get(dbp, cursorp, key, val, flags)
+	const DB *dbp;
+	CURSOR *cursorp;
+	DBT *key, *val;
+	u_int32_t flags;
+{
+	HTAB *hashp;
+	ITEM_INFO item_info;
+
+	hashp = (HTAB *)dbp->internal;
+
+	if (flags && flags != R_FIRST && flags != R_NEXT) {
+		hashp->errno = errno = EINVAL;
+		return (ERROR);
+	}
+#ifdef HASH_STATISTICS
+	hash_accesses++;
+#endif
+
+	item_info.seek_size = 0;
+
+	if (flags == R_FIRST)
+		__get_item_first(hashp, cursorp, key, val, &item_info);
+	else
+		__get_item_next(hashp, cursorp, key, val, &item_info);
+
+	/*
+	 * This needs to be changed around.  As is, get_item_next advances
+	 * the pointers on the page but this function actually advances
+	 * bucket pointers.  This works, since the only other place we 
+	 * use get_item_next is in hash_access which only deals with one
+	 * bucket at a time.  However, there is the problem that certain other
+	 * functions (such as find_bigpair and delpair) depend on the
+	 * pgndx member of the cursor.  Right now, they are using pngdx - 1
+	 * since indices refer to the __next__ item that is to be fetched
+	 * from the page.  This is ugly, as you may have noticed, whoever
+	 * you are.  The best solution would be to depend on item_infos to
+	 * deal with _current_ information, and have the cursors only
+	 * deal with _next_ information.  In that scheme, get_item_next
+	 * would also advance buckets.  Version 3...
+	 */
+
+
+	/*
+	 * Must always enter this loop to do error handling and
+	 * check for big key/data pair.
+	 */
+	while (1) {
+		if (item_info.status == ITEM_OK) {
+			if (item_info.key_off == BIGPAIR &&
+			    __big_keydata(hashp, cursorp->pagep, key, val,
+			    item_info.pgndx))
+				return (ABNORMAL);
+
+			break;
+		} else if (item_info.status != ITEM_NO_MORE)
+			return (ABNORMAL);
+
+		__put_page(hashp, cursorp->pagep, A_RAW, 0);
+		cursorp->ndx = cursorp->pgndx = 0;
+		cursorp->bucket++;
+		cursorp->pgno = INVALID_PGNO;
+		cursorp->pagep = NULL;
+		if (cursorp->bucket > hashp->hdr.max_bucket)
+			return (ABNORMAL);
+		__get_item_next(hashp, cursorp, key, val, &item_info);
+	}
+
+	__get_item_done(hashp, cursorp);
+	return (0);
+}
+
+int32_t
+cursor_delete(dbp, cursor, flags)
+	const DB *dbp;
+	CURSOR *cursor;
+	u_int32_t flags;
+{
+	/* XXX this is empirically determined, so it might not be completely
+	   correct, but it seems to work.  At the very least it fixes
+	   a memory leak */
+ 
+	free(cursor->internal);
+	free(cursor);
+
+	return (0);
+}
+
+static int32_t
+hash_seq(dbp, key, val, flag)
+	const DB *dbp;
+	DBT *key, *val;
+	u_int32_t flag;
+{
+	HTAB *hashp;
+
+	/*
+	 * Seq just uses the default cursor to go sequecing through the
+	 * database.  Note that the default cursor is the first in the list. 
+	 */
+
+	hashp = (HTAB *)dbp->internal;
+	if (!hashp->seq_cursor)
+		hashp->seq_cursor = __cursor_creat(dbp);
+
+	return (hashp->seq_cursor->get(dbp, hashp->seq_cursor, key, val, flag));
+}
+
+/********************************* UTILITIES ************************/
+
+/*
+ * Returns:
+ *	 0 ==> OK
+ *	-1 ==> Error
+ */
+int32_t
+__expand_table(hashp)
+	HTAB *hashp;
+{
+	u_int32_t old_bucket, new_bucket;
+	int32_t spare_ndx;
+
+#ifdef HASH_STATISTICS
+	hash_expansions++;
+#endif
+	new_bucket = ++hashp->hdr.max_bucket;
+	old_bucket = (hashp->hdr.max_bucket & hashp->hdr.low_mask);
+
+	/* Get a page for this new bucket */
+	if (__new_page(hashp, new_bucket, A_BUCKET) != 0)
+		return (-1);
+
+	/*
+	 * If the split point is increasing (hdr.max_bucket's log base 2
+	 * increases), we need to copy the current contents of the spare
+	 * split bucket to the next bucket.
+	 */
+	spare_ndx = __log2(hashp->hdr.max_bucket + 1);
+	if (spare_ndx > hashp->hdr.ovfl_point) {
+		hashp->hdr.spares[spare_ndx] = hashp->hdr.spares[hashp->hdr.ovfl_point];
+		hashp->hdr.ovfl_point = spare_ndx;
+	}
+	if (new_bucket > hashp->hdr.high_mask) {
+		/* Starting a new doubling */
+		hashp->hdr.low_mask = hashp->hdr.high_mask;
+		hashp->hdr.high_mask = new_bucket | hashp->hdr.low_mask;
+	}
+	if (BUCKET_TO_PAGE(new_bucket) > MAX_PAGES(hashp)) {
+		fprintf(stderr, "hash: Cannot allocate new bucket.  Pages exhausted.\n");
+		return (-1);
+	}
+	/* Relocate records to the new bucket */
+	return (__split_page(hashp, old_bucket, new_bucket));
+}
+
+u_int32_t
+__call_hash(hashp, k, len)
+	HTAB *hashp;
+	int8_t *k;
+	int32_t len;
+{
+	int32_t n, bucket;
+
+	n = hashp->hash(k, len);
+	bucket = n & hashp->hdr.high_mask;
+	if (bucket > hashp->hdr.max_bucket)
+		bucket = bucket & hashp->hdr.low_mask;
+	return (bucket);
+}
+
+#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
+/*
+ * Hashp->hdr needs to be byteswapped.
+ */
+static void
+swap_header_copy(srcp, destp)
+	HASHHDR *srcp, *destp;
+{
+	int32_t i;
+
+	P_32_COPY(srcp->magic, destp->magic);
+	P_32_COPY(srcp->version, destp->version);
+	P_32_COPY(srcp->lorder, destp->lorder);
+	P_32_COPY(srcp->bsize, destp->bsize);
+	P_32_COPY(srcp->bshift, destp->bshift);
+	P_32_COPY(srcp->ovfl_point, destp->ovfl_point);
+	P_32_COPY(srcp->last_freed, destp->last_freed);
+	P_32_COPY(srcp->max_bucket, destp->max_bucket);
+	P_32_COPY(srcp->high_mask, destp->high_mask);
+	P_32_COPY(srcp->low_mask, destp->low_mask);
+	P_32_COPY(srcp->ffactor, destp->ffactor);
+	P_32_COPY(srcp->nkeys, destp->nkeys);
+	P_32_COPY(srcp->hdrpages, destp->hdrpages);
+	P_32_COPY(srcp->h_charkey, destp->h_charkey);
+	for (i = 0; i < NCACHED; i++) {
+		P_32_COPY(srcp->spares[i], destp->spares[i]);
+		P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]);
+	}
+}
+
+static void
+swap_header(hashp)
+	HTAB *hashp;
+{
+	HASHHDR *hdrp;
+	int32_t i;
+
+	hdrp = &hashp->hdr;
+
+	M_32_SWAP(hdrp->magic);
+	M_32_SWAP(hdrp->version);
+	M_32_SWAP(hdrp->lorder);
+	M_32_SWAP(hdrp->bsize);
+	M_32_SWAP(hdrp->bshift);
+	M_32_SWAP(hdrp->ovfl_point);
+	M_32_SWAP(hdrp->last_freed);
+	M_32_SWAP(hdrp->max_bucket);
+	M_32_SWAP(hdrp->high_mask);
+	M_32_SWAP(hdrp->low_mask);
+	M_32_SWAP(hdrp->ffactor);
+	M_32_SWAP(hdrp->nkeys);
+	M_32_SWAP(hdrp->hdrpages);
+	M_32_SWAP(hdrp->h_charkey);
+	for (i = 0; i < NCACHED; i++) {
+		M_32_SWAP(hdrp->spares[i]);
+		M_16_SWAP(hdrp->bitmaps[i]);
+	}
+}
+#endif /* DB_BYTE_ORDER == DB_LITTLE_ENDIAN */
diff --git a/src/util/db2/hash/hash.c.patch b/src/util/db2/hash/hash.c.patch
new file mode 100644
index 000000000..b72cc0d26
--- /dev/null
+++ b/src/util/db2/hash/hash.c.patch
@@ -0,0 +1,109 @@
+*** /tmp/,RCSt1a21714	Wed Apr  3 11:49:15 1996
+--- hash.c	Wed Apr  3 08:43:04 1996
+***************
+*** 399,405
+  	/* Create pages for these buckets */
+  	/*
+  	for (i = 0; i <= hashp->hdr.max_bucket; i++) {
+! 		if (__new_page(hashp, i, A_BUCKET) != 0)
+  			return (-1);
+  	}
+  	*/
+
+--- 399,405 -----
+  	/* Create pages for these buckets */
+  	/*
+  	for (i = 0; i <= hashp->hdr.max_bucket; i++) {
+! 		if (__new_page(hashp, (u_int32_t)i, A_BUCKET) != 0)
+  			return (-1);
+  	}
+  	*/
+***************
+*** 560,567
+  	 * XXX
+  	 * Check success/failure conditions.
+  	 */
+! 	mpool_sync(hashp->mp);
+! 	return (0);
+  }
+  
+  /*
+
+--- 560,566 -----
+  	 * XXX
+  	 * Check success/failure conditions.
+  	 */
+! 	return (flush_meta(hashp) || mpool_sync(hashp->mp));
+  }
+  
+  /*
+***************
+*** 585,591
+  	hput_header(hashp);
+  
+  	for (i = 0; i < NCACHED; i++)
+! 		if (hashp->mapp[i])
+  			if (__put_page(hashp,
+  			    (PAGE16 *)hashp->mapp[i], A_BITMAP, 1))
+  				return (-1);
+
+--- 584,590 -----
+  	hput_header(hashp);
+  
+  	for (i = 0; i < NCACHED; i++)
+! 		if (hashp->mapp[i]) {
+  			if (__put_page(hashp,
+  			    (PAGE16 *)hashp->mapp[i], A_BITMAP, 1))
+  				return (-1);
+***************
+*** 589,594
+  			if (__put_page(hashp,
+  			    (PAGE16 *)hashp->mapp[i], A_BITMAP, 1))
+  				return (-1);
+  	return (0);
+  }
+  
+
+--- 588,595 -----
+  			if (__put_page(hashp,
+  			    (PAGE16 *)hashp->mapp[i], A_BITMAP, 1))
+  				return (-1);
++ 			hashp->mapp[i] = NULL;
++ 		}
+  	return (0);
+  }
+  
+***************
+*** 726,732
+  #ifdef HASH_STATISTICS
+  	hash_collisions++;
+  #endif
+- 
+  	__get_item_done(hashp, &cursor);
+  
+  	/*
+
+--- 727,732 -----
+  #ifdef HASH_STATISTICS
+  	hash_collisions++;
+  #endif
+  	__get_item_done(hashp, &cursor);
+  
+  	/*
+***************
+*** 773,778
+  		if (__delpair(hashp, &cursor, &item_info) ||
+  		    __addel(hashp, &item_info, key, val, UNKNOWN, 0))
+  			return (ERROR);
+  		if (item_info.caused_expand)
+  			__expand_table(hashp);
+  		break;
+
+--- 773,779 -----
+  		if (__delpair(hashp, &cursor, &item_info) ||
+  		    __addel(hashp, &item_info, key, val, UNKNOWN, 0))
+  			return (ERROR);
++ 		__get_item_done(hashp, &cursor);
+  		if (item_info.caused_expand)
+  			__expand_table(hashp);
+  		break;
diff --git a/src/util/db2/hash/hash.h b/src/util/db2/hash/hash.h
new file mode 100644
index 000000000..973d543a8
--- /dev/null
+++ b/src/util/db2/hash/hash.h
@@ -0,0 +1,196 @@
+/*-
+ * 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
+ * Margo Seltzer.
+ *
+ * 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.
+ *
+ *	@(#)hash.h	8.4 (Berkeley) 11/2/95
+ */
+
+#include "mpool.h"
+#include "db-queue.h"
+
+/* Operations */
+typedef enum {
+	HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
+} ACTION;
+
+/* cursor structure */
+typedef struct cursor_t {
+	TAILQ_ENTRY(cursor_t) queue;
+	int (*get)	__P((const DB *, struct cursor_t *, DBT *, DBT *, \
+			     u_int32_t));
+	int (*delete) __P((const DB *, struct cursor_t *, u_int32_t));
+	db_pgno_t	bucket;
+	db_pgno_t	pgno;
+	indx_t	ndx;
+	indx_t	pgndx;
+	u_int16_t *pagep;
+	void *internal;
+} CURSOR;
+
+
+#define IS_BUCKET(X)	((X) & BUF_BUCKET)
+#define IS_VALID(X)     (!((X) & BUF_INVALID))
+
+/* Hash Table Information */
+typedef struct hashhdr {	/* Disk resident portion */
+	int32_t	magic;		/* Magic NO for hash tables */
+	int32_t	version;	/* Version ID */
+	int32_t	lorder;		/* Byte Order */
+	int32_t	bsize;		/* Bucket/Page Size */
+	int32_t	bshift;		/* Bucket shift */
+	int32_t	ovfl_point;	/* Where overflow pages are being allocated */
+	int32_t	last_freed;	/* Last overflow page freed */
+	int32_t	max_bucket;	/* ID of Maximum bucket in use */
+	int32_t	high_mask;	/* Mask to modulo into entire table */
+	int32_t	low_mask;	/* Mask to modulo into lower half of table */
+	int32_t	ffactor;	/* Fill factor */
+	int32_t	nkeys;		/* Number of keys in hash table */
+	int32_t	hdrpages;	/* Size of table header */
+	int32_t	h_charkey;	/* value of hash(CHARKEY) */
+#define NCACHED	32		/* number of bit maps and spare points */
+	int32_t	spares[NCACHED];/* spare pages for overflow */
+	u_int16_t	bitmaps[NCACHED];	/* address of overflow page bitmaps */
+} HASHHDR;
+
+typedef struct htab {		/* Memory resident data structure */
+	TAILQ_HEAD(_cursor_queue, cursor_t) curs_queue;
+	HASHHDR hdr;		/* Header */
+	u_int32_t (*hash) __P((const void *, size_t)); /* Hash Function */
+	int32_t	flags;		/* Flag values */
+	int32_t	fp;		/* File pointer */
+	char *fname;        	/* File path */
+	u_int8_t *bigdata_buf;	/* Temporary Buffer for BIG data */
+	u_int8_t *bigkey_buf;	/* Temporary Buffer for BIG keys */
+	u_int16_t  *split_buf;	/* Temporary buffer for splits */
+	CURSOR	*seq_cursor;	/* Cursor used for hash_seq */
+	int32_t	errno;		/* Error Number -- for DBM compatability */
+	int32_t	new_file;	/* Indicates if fd is backing store or no */
+	int32_t	save_file;	/* Indicates whether we need to flush file at
+				 * exit */
+	u_int32_t *mapp[NCACHED];/* Pointers to page maps */
+	int32_t	nmaps;		/* Initial number of bitmaps */
+	MPOOL	*mp;		/* mpool for buffer management */
+} HTAB;
+
+/*
+ * Constants
+ */
+#define	MAX_BSIZE		65536		/* 2^16 */
+#define MIN_BUFFERS		6
+#define MINHDRSIZE		512
+#define DEF_CACHESIZE	65536
+#define DEF_BUCKET_SIZE		4096
+#define DEF_BUCKET_SHIFT	12		/* log2(BUCKET) */
+#define DEF_SEGSIZE		256
+#define DEF_SEGSIZE_SHIFT	8		/* log2(SEGSIZE)	 */
+#define DEF_DIRSIZE		256
+#define DEF_FFACTOR		65536
+#define MIN_FFACTOR		4
+#define SPLTMAX			8
+#define CHARKEY			"%$sniglet^&"
+#define NUMKEY			1038583
+#define BYTE_SHIFT		3
+#define INT32_T_TO_BYTE		2
+#define INT32_T_BYTE_SHIFT		5
+#define ALL_SET			((u_int32_t)0xFFFFFFFF)
+#define ALL_CLEAR		0
+
+#define PTROF(X)	((BUFHEAD *)((ptr_t)(X)&~0x3))
+#define ISMOD(X)	((ptr_t)(X)&0x1)
+#define DOMOD(X)	((X) = (int8_t *)((ptr_t)(X)|0x1))
+#define ISDISK(X)	((ptr_t)(X)&0x2)
+#define DODISK(X)	((X) = (int8_t *)((ptr_t)(X)|0x2))
+
+#define BITS_PER_MAP	32
+
+/* Given the address of the beginning of a big map, clear/set the nth bit */
+#define CLRBIT(A, N)	((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
+#define SETBIT(A, N)	((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
+#define ISSET(A, N)	((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
+
+/* Overflow management */
+/*
+ * Overflow page numbers are allocated per split point.  At each doubling of
+ * the table, we can allocate extra pages.  So, an overflow page number has
+ * the top 5 bits indicate which split point and the lower 11 bits indicate
+ * which page at that split point is indicated (pages within split points are
+ * numberered starting with 1).
+ */
+
+#define SPLITSHIFT	11
+#define SPLITMASK	0x7FF
+#define SPLITNUM(N)	(((u_int32_t)(N)) >> SPLITSHIFT)
+#define OPAGENUM(N)	((N) & SPLITMASK)
+#define	OADDR_OF(S,O)	((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))
+
+#define BUCKET_TO_PAGE(B) \
+	((B) + hashp->hdr.hdrpages + ((B) \
+	    ? hashp->hdr.spares[__log2((B)+1)-1] : 0))
+#define OADDR_TO_PAGE(B) 	\
+	(BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B)))
+
+#define POW2(N)  (1 << (N))
+
+#define MAX_PAGES(H) (DB_OFF_T_MAX / (H)->hdr.bsize)
+
+/* Shorthands for accessing structure */
+#define METADATA_PGNO 0
+#define SPLIT_PGNO 0xFFFF
+
+typedef struct item_info {
+	db_pgno_t 		pgno;
+	db_pgno_t		bucket;
+	indx_t		ndx;
+	indx_t		pgndx;
+	u_int8_t	status;
+	int32_t		seek_size;
+	db_pgno_t		seek_found_page;
+	indx_t		key_off;
+	indx_t		data_off;
+	u_int8_t	caused_expand;
+} ITEM_INFO;
+
+
+#define	ITEM_ERROR	0
+#define	ITEM_OK		1
+#define	ITEM_NO_MORE	2
+
+#define	ITEM_GET_FIRST	0
+#define	ITEM_GET_NEXT	1
+#define	ITEM_GET_RESET	2
+#define	ITEM_GET_DONE	3
+#define	ITEM_GET_N	4
+
+#define	UNKNOWN		0xffffffff		/* for num_items */
+#define	NO_EXPAND	0xfffffffe 
diff --git a/src/util/db2/hash/hash_bigkey.c b/src/util/db2/hash/hash_bigkey.c
new file mode 100644
index 000000000..689dc3db6
--- /dev/null
+++ b/src/util/db2/hash/hash_bigkey.c
@@ -0,0 +1,483 @@
+/*-
+ * 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
+ * Margo Seltzer.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)hash_bigkey.c	8.5 (Berkeley) 11/2/95";
+#endif /* LIBC_SCCS and not lint */
+
+/*
+ * PACKAGE: hash
+ * DESCRIPTION:
+ *	Big key/data handling for the hashing package.
+ *
+ * ROUTINES:
+ * External
+ *	__big_keydata
+ *	__big_split
+ *	__big_insert
+ *	__big_return
+ *	__big_delete
+ *	__find_last_page
+ * Internal
+ *	collect_key
+ *	collect_data
+ */
+#include <sys/types.h>
+
+#include <stdlib.h>
+#include <string.h>
+
+#ifdef DEBUG
+#include <assert.h>
+#endif
+
+#include "db-int.h"
+#include "hash.h"
+#include "page.h"
+#include "extern.h"
+
+static int32_t collect_key __P((HTAB *, PAGE16 *, int32_t, db_pgno_t *));
+static int32_t collect_data __P((HTAB *, PAGE16 *, int32_t));
+
+/*
+ * Big_insert
+ *
+ * You need to do an insert and the key/data pair is greater than 
+ * MINFILL * the bucket size
+ *
+ * Returns:
+ *	 0 ==> OK
+ *	-1 ==> ERROR
+ */
+int32_t
+__big_insert(hashp, pagep, key, val)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	const DBT *key, *val;
+{
+	size_t  key_size, val_size;
+	indx_t  key_move_bytes, val_move_bytes;
+	int8_t *key_data, *val_data, base_page;
+
+	key_data = (int8_t *)key->data;
+	key_size = key->size;
+	val_data = (int8_t *)val->data;
+	val_size = val->size;
+
+	NUM_ENT(pagep) = NUM_ENT(pagep) + 1;
+
+	for (base_page = 1; key_size + val_size;) {
+		/* Add a page! */
+		pagep =
+		    __add_bigpage(hashp, pagep, NUM_ENT(pagep) - 1, base_page);
+		if (!pagep)
+			return (-1);
+
+		/* There's just going to be one entry on this page. */
+		NUM_ENT(pagep) = 1;
+
+		/* Move the key's data. */
+		key_move_bytes = MIN(FREESPACE(pagep), key_size);
+		/* Mark the page as to how much key & data is on this page. */
+		BIGKEYLEN(pagep) = key_move_bytes;
+		val_move_bytes =
+		    MIN(FREESPACE(pagep) - key_move_bytes, val_size);
+		BIGDATALEN(pagep) = val_move_bytes;
+
+		/* Note big pages build beginning --> end, not vice versa. */
+		if (key_move_bytes)
+			memmove(BIGKEY(pagep), key_data, key_move_bytes);
+		if (val_move_bytes)
+			memmove(BIGDATA(pagep), val_data, val_move_bytes);
+
+		key_size -= key_move_bytes;
+		key_data += key_move_bytes;
+		val_size -= val_move_bytes;
+		val_data += val_move_bytes;
+
+		base_page = 0;
+	}
+	__put_page(hashp, pagep, A_RAW, 1);
+	return (0);
+}
+
+/*
+ * Called when we need to delete a big pair.
+ *
+ * Returns:
+ *	 0 => OK
+ *	-1 => ERROR
+ */
+int32_t
+#ifdef __STDC__
+__big_delete(HTAB *hashp, PAGE16 *pagep, indx_t ndx)
+#else
+__big_delete(hashp, pagep, ndx)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	u_int32_t ndx;		/* Index of big pair on base page. */
+#endif
+{
+	PAGE16 *last_pagep;
+
+	/* Get first page with big key/data. */
+	pagep = __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW);
+	if (!pagep)
+		return (-1);
+
+	/*
+	 * Traverse through the pages, freeing the previous one (except
+	 * the first) at each new page.
+	 */
+	while (NEXT_PGNO(pagep) != INVALID_PGNO) {
+		last_pagep = pagep;
+		pagep = __get_page(hashp, NEXT_PGNO(pagep), A_RAW);
+		if (!pagep)
+			return (-1);
+		__delete_page(hashp, last_pagep, A_OVFL);
+	}
+
+	/* Free the last page in the chain. */
+	__delete_page(hashp, pagep, A_OVFL);
+	return (0);
+}
+
+/*
+ * Given a key, indicates whether the big key at cursorp matches the
+ * given key.
+ *
+ * Returns:
+ *	 1 = Found!
+ *	 0 = Key not found
+ *	-1 error
+ */
+int32_t
+__find_bigpair(hashp, cursorp, key, size)
+	HTAB *hashp;
+	CURSOR *cursorp;
+	int8_t *key;
+	int32_t size;
+{
+	PAGE16 *pagep, *hold_pagep;
+	db_pgno_t  next_pgno;
+	int32_t ksize;
+	u_int16_t bytes;
+	int8_t *kkey;
+
+	ksize = size;
+	kkey = key;
+	bytes = 0;
+
+	hold_pagep = NULL;
+	/* Chances are, hashp->cpage is the base page. */
+	if (cursorp->pagep)
+		pagep = hold_pagep = cursorp->pagep;
+	else {
+		pagep = __get_page(hashp, cursorp->pgno, A_RAW);
+		if (!pagep)
+			return (-1);
+	}
+
+	/*
+	 * Now, get the first page with the big stuff on it.
+	 *
+	 * XXX
+	 * KLUDGE: we know that cursor is looking at the _next_ item, so
+	 * we have to look at pgndx - 1.
+	 */
+	next_pgno = OADDR_TO_PAGE(DATA_OFF(pagep, (cursorp->pgndx - 1)));
+	if (!hold_pagep)
+		__put_page(hashp, pagep, A_RAW, 0);
+	pagep = __get_page(hashp, next_pgno, A_RAW);
+	if (!pagep)
+		return (-1);
+
+	/* While there are both keys to compare. */
+	while ((ksize > 0) && (BIGKEYLEN(pagep))) {
+		if (ksize < KEY_OFF(pagep, 0) ||
+		    memcmp(BIGKEY(pagep), kkey, BIGKEYLEN(pagep))) {
+			__put_page(hashp, pagep, A_RAW, 0);
+			return (0);
+		}
+		kkey += BIGKEYLEN(pagep);
+		ksize -= BIGKEYLEN(pagep);
+		if (NEXT_PGNO(pagep) != INVALID_PGNO) {
+			next_pgno = NEXT_PGNO(pagep);
+			__put_page(hashp, pagep, A_RAW, 0);
+			pagep = __get_page(hashp, next_pgno, A_RAW);
+			if (!pagep)
+				return (-1);
+		}
+	}
+	__put_page(hashp, pagep, A_RAW, 0);
+#ifdef DEBUG
+	assert(ksize >= 0);
+#endif
+	if (ksize != 0) {
+#ifdef HASH_STATISTICS
+		++hash_collisions;
+#endif
+		return (0);
+	} else
+		return (1);
+}
+
+/*
+ * Fill in the key and data for this big pair.
+ */
+int32_t
+__big_keydata(hashp, pagep, key, val, ndx)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	DBT *key, *val;
+	int32_t ndx;
+{
+	ITEM_INFO ii;
+	PAGE16 *key_pagep;
+	db_pgno_t last_page;
+
+	key_pagep =
+	    __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW);
+	if (!key_pagep)
+		return (-1);
+	key->size = collect_key(hashp, key_pagep, 0, &last_page);
+	key->data = hashp->bigkey_buf;
+	__put_page(hashp, key_pagep, A_RAW, 0);
+
+	if (key->size == -1)
+		return (-1);
+
+	/* Create an item_info to direct __big_return to the beginning pgno. */
+	ii.pgno = last_page;
+	return (__big_return(hashp, &ii, val, 1));
+}
+
+/*
+ * Return the big key on page, ndx.
+ */
+int32_t
+#ifdef __STDC__
+__get_bigkey(HTAB *hashp, PAGE16 *pagep, indx_t ndx, DBT *key)
+#else
+__get_bigkey(hashp, pagep, ndx, key)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	u_int32_t ndx;
+	DBT *key;
+#endif
+{
+	PAGE16 *key_pagep;
+
+	key_pagep =
+	    __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW);
+	if (!pagep)
+		return (-1);
+	key->size = collect_key(hashp, key_pagep, 0, NULL);
+	key->data = hashp->bigkey_buf;
+
+	__put_page(hashp, key_pagep, A_RAW, 0);
+
+	return (0);
+}
+
+/*
+ * Return the big key and data indicated in item_info.
+ */
+int32_t
+__big_return(hashp, item_info, val, on_bigkey_page)
+	HTAB *hashp;
+	ITEM_INFO *item_info;
+	DBT *val;
+	int32_t on_bigkey_page;
+{
+	PAGE16 *pagep;
+	db_pgno_t next_pgno;
+
+	if (!on_bigkey_page) {
+		/* Get first page with big pair on it. */
+		pagep = __get_page(hashp,
+		    OADDR_TO_PAGE(item_info->data_off), A_RAW);
+		if (!pagep)
+			return (-1);
+	} else {
+		pagep = __get_page(hashp, item_info->pgno, A_RAW);
+		if (!pagep)
+			return (-1);
+	}
+
+	/* Traverse through the bigkey pages until a page with data is found. */
+	while (!BIGDATALEN(pagep)) {
+		next_pgno = NEXT_PGNO(pagep);
+		__put_page(hashp, pagep, A_RAW, 0);
+		pagep = __get_page(hashp, next_pgno, A_RAW);
+		if (!pagep)
+			return (-1);
+	}
+
+	val->size = collect_data(hashp, pagep, 0);
+	if (val->size < 1)
+		return (-1);
+	val->data = (void *)hashp->bigdata_buf;
+
+	__put_page(hashp, pagep, A_RAW, 0);
+	return (0);
+}
+
+/*
+ * Given a page with a big key on it, traverse through the pages counting data
+ * length, and collect all of the data on the way up.  Store the key in
+ * hashp->bigkey_buf.  last_page indicates to the calling function what the
+ * last page with key on it is; this will help if you later want to retrieve
+ * the data portion.
+ *
+ * Does the work for __get_bigkey.
+ *
+ * Return total length of data; -1 if error.
+ */
+static int32_t
+collect_key(hashp, pagep, len, last_page)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	int32_t len;
+	db_pgno_t *last_page;
+{
+	PAGE16 *next_pagep;
+	int32_t totlen, retval;
+	db_pgno_t next_pgno;
+#ifdef DEBUG
+	db_pgno_t save_addr;
+#endif
+
+	/* If this is the last page with key. */
+	if (BIGDATALEN(pagep)) {
+		totlen = len + BIGKEYLEN(pagep);
+		if (hashp->bigkey_buf)
+			free(hashp->bigkey_buf);
+		hashp->bigkey_buf = (char *)malloc(totlen);
+		if (!hashp->bigkey_buf)
+			return (-1);
+		memcpy(hashp->bigkey_buf + len,
+		    BIGKEY(pagep), BIGKEYLEN(pagep));
+		if (last_page)
+			*last_page = ADDR(pagep);
+		return (totlen);
+	}
+
+	/* Key filled up all of last key page, so we've gone 1 too far. */
+	if (BIGKEYLEN(pagep) == 0) {
+		if (hashp->bigkey_buf)
+			free(hashp->bigkey_buf);
+		hashp->bigkey_buf = (char *)malloc(len);
+		return (hashp->bigkey_buf ? len : -1);
+	}
+	totlen = len + BIGKEYLEN(pagep);
+
+	/* Set pagep to the next page in the chain. */
+	if (last_page)
+		*last_page = ADDR(pagep);
+	next_pgno = NEXT_PGNO(pagep);
+	next_pagep = __get_page(hashp, next_pgno, A_RAW);
+	if (!next_pagep)
+		return (-1);
+#ifdef DEBUG
+	save_addr = ADDR(pagep);
+#endif
+	retval = collect_key(hashp, next_pagep, totlen, last_page);
+
+#ifdef DEBUG
+	assert(save_addr == ADDR(pagep));
+#endif
+	memcpy(hashp->bigkey_buf + len, BIGKEY(pagep), BIGKEYLEN(pagep));
+	__put_page(hashp, next_pagep, A_RAW, 0);
+
+	return (retval);
+}
+
+/*
+ * Given a page with big data on it, recur through the pages counting data
+ * length, and collect all of the data on the way up.  Store the data in
+ * hashp->bigdata_buf.
+ *
+ * Does the work for __big_return.
+ *
+ * Return total length of data; -1 if error.
+ */
+static int32_t
+collect_data(hashp, pagep, len)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	int32_t len;
+{
+	PAGE16 *next_pagep;
+	int32_t totlen, retval;
+	db_pgno_t next_pgno;
+#ifdef DEBUG
+	db_pgno_t save_addr;
+#endif
+
+	/* If there is no next page. */
+	if (NEXT_PGNO(pagep) == INVALID_PGNO) {
+		if (hashp->bigdata_buf)
+			free(hashp->bigdata_buf);
+		totlen = len + BIGDATALEN(pagep);
+		hashp->bigdata_buf = (char *)malloc(totlen);
+		if (!hashp->bigdata_buf)
+			return (-1);
+		memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep),
+		    BIGDATA(pagep), BIGDATALEN(pagep));
+		return (totlen);
+	}
+	totlen = len + BIGDATALEN(pagep);
+
+	/* Set pagep to the next page in the chain. */
+	next_pgno = NEXT_PGNO(pagep);
+	next_pagep = __get_page(hashp, next_pgno, A_RAW);
+	if (!next_pagep)
+		return (-1);
+
+#ifdef DEBUG
+	save_addr = ADDR(pagep);
+#endif
+	retval = collect_data(hashp, next_pagep, totlen);
+#ifdef DEBUG
+	assert(save_addr == ADDR(pagep));
+#endif
+	memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep),
+	    BIGDATA(pagep), BIGDATALEN(pagep));
+	__put_page(hashp, next_pagep, A_RAW, 0);
+
+	return (retval);
+}
diff --git a/src/util/db2/hash/hash_debug.c b/src/util/db2/hash/hash_debug.c
new file mode 100644
index 000000000..ed99c6932
--- /dev/null
+++ b/src/util/db2/hash/hash_debug.c
@@ -0,0 +1,106 @@
+/*-
+ * Copyright (c) 1995
+ *	The President and Fellows of Harvard University
+ *
+ * This code is derived from software contributed to Harvard by
+ * Jeremy Rassen.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)hash_debug.c	8.4 (Berkeley) 11/7/95";
+#endif /* LIBC_SCCS and not lint */
+
+#ifdef DEBUG
+/*
+ * PACKAGE:  hashing
+ *
+ * DESCRIPTION:
+ *	Debug routines.
+ *
+ * ROUTINES:
+ *
+ * External
+ *	__dump_bucket
+ */
+#include <stdio.h>
+
+#include "db-int.h"
+#include "hash.h"
+#include "page.h"
+#include "extern.h"
+#include "compat.h"
+
+void
+__dump_bucket(hashp, bucket)
+	HTAB *hashp;
+	u_int32_t bucket;
+{
+	CURSOR cursor;
+	DBT key, val;
+	ITEM_INFO item_info;
+	int var;
+	char *cp;
+
+	cursor.pagep = NULL;
+	item_info.seek_size = 0;
+	item_info.seek_found_page = 0;
+
+	__get_item_reset(hashp, &cursor);
+
+	cursor.bucket = bucket;
+	for (;;) {
+		__get_item_next(hashp, &cursor, &key, &val, &item_info);
+		if (item_info.status == ITEM_ERROR) {
+			(void)printf("get_item_next returned error\n");
+			break;
+		} else if (item_info.status == ITEM_NO_MORE)
+			break;
+
+		if (item_info.key_off == BIGPAIR) {
+			if (__big_keydata(hashp, cursor.pagep, &key, &val,
+			    item_info.pgndx)) {
+				(void)printf("__big_keydata returned error\n");
+				break;
+			}
+		}
+
+		if (key.size == sizeof(int)) {
+			memcpy(&var, key.data, sizeof(int));
+			(void)printf("%d\n", var);
+		} else {
+			for (cp = (char *)key.data; key.size--; cp++)
+				(void)printf("%c", *cp);
+			(void)printf("\n");
+		}
+	}
+	__get_item_done(hashp, &cursor);
+}
+#endif /* DEBUG */
diff --git a/src/util/db2/hash/hash_func.c b/src/util/db2/hash/hash_func.c
new file mode 100644
index 000000000..efa2a2843
--- /dev/null
+++ b/src/util/db2/hash/hash_func.c
@@ -0,0 +1,196 @@
+/*-
+ * Copyright (c) 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Margo Seltzer.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)hash_func.c	8.4 (Berkeley) 11/7/95";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+
+#include "db-int.h"
+#include "hash.h"
+#include "page.h"
+#include "extern.h"
+
+static u_int32_t hash1 __P((const void *, size_t));
+static u_int32_t hash2 __P((const void *, size_t));
+static u_int32_t hash3 __P((const void *, size_t));
+static u_int32_t hash4 __P((const void *, size_t));
+
+/* Default hash function. */
+u_int32_t (*__default_hash) __P((const void *, size_t)) = hash4;
+
+/*
+ * Assume that we've already split the bucket to which this key hashes,
+ * calculate that bucket, and check that in fact we did already split it.
+ *
+ * EJB's original hsearch hash.
+ */
+#define PRIME1		37
+#define PRIME2		1048583
+
+u_int32_t
+hash1(key, len)
+	const void *key;
+	size_t len;
+{
+	u_int32_t h;
+	u_int8_t *k;
+
+	h = 0;
+	k = (u_int8_t *)key;
+	/* Convert string to integer */
+	while (len--)
+		h = h * PRIME1 ^ (*k++ - ' ');
+	h %= PRIME2;
+	return (h);
+}
+
+/*
+ * Phong Vo's linear congruential hash
+ */
+#define dcharhash(h, c)	((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
+
+u_int32_t
+hash2(key, len)
+	const void *key;
+	size_t len;
+{
+	u_int32_t h;
+	u_int8_t *e, c, *k;
+
+	k = (u_int8_t *)key;
+	e = k + len;
+	for (h = 0; k != e;) {
+		c = *k++;
+		if (!c && k > e)
+			break;
+		dcharhash(h, c);
+	}
+	return (h);
+}
+
+/*
+ * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
+ * units.  On the first time through the loop we get the "leftover bytes"
+ * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
+ * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
+ * this routine is heavily used enough, it's worth the ugly coding.
+ *
+ * Ozan Yigit's original sdbm hash.
+ */
+u_int32_t
+hash3(key, len)
+	const void *key;
+	size_t len;
+{
+	u_int32_t n, loop;
+	u_int8_t *k;
+
+#define HASHC   n = *k++ + 65599 * n
+
+	n = 0;
+	k = (u_int8_t *)key;
+	if (len > 0) {
+		loop = (len + 8 - 1) >> 3;
+
+		switch (len & (8 - 1)) {
+		case 0:
+			do {	/* All fall throughs */
+				HASHC;
+		case 7:
+				HASHC;
+		case 6:
+				HASHC;
+		case 5:
+				HASHC;
+		case 4:
+				HASHC;
+		case 3:
+				HASHC;
+		case 2:
+				HASHC;
+		case 1:
+				HASHC;
+			} while (--loop);
+		}
+
+	}
+	return (n);
+}
+
+/* Chris Torek's hash function. */
+u_int32_t
+hash4(key, len)
+	const void *key;
+	size_t len;
+{
+	u_int32_t h, loop;
+	u_int8_t *k;
+
+#define HASH4a   h = (h << 5) - h + *k++;
+#define HASH4b   h = (h << 5) + h + *k++;
+#define HASH4 HASH4b
+
+	h = 0;
+	k = (u_int8_t *)key;
+	if (len > 0) {
+		loop = (len + 8 - 1) >> 3;
+
+		switch (len & (8 - 1)) {
+		case 0:
+			do {	/* All fall throughs */
+				HASH4;
+		case 7:
+				HASH4;
+		case 6:
+				HASH4;
+		case 5:
+				HASH4;
+		case 4:
+				HASH4;
+		case 3:
+				HASH4;
+		case 2:
+				HASH4;
+		case 1:
+				HASH4;
+			} while (--loop);
+		}
+
+	}
+	return (h);
+}
diff --git a/src/util/db2/hash/hash_log2.c b/src/util/db2/hash/hash_log2.c
new file mode 100644
index 000000000..8604945e8
--- /dev/null
+++ b/src/util/db2/hash/hash_log2.c
@@ -0,0 +1,52 @@
+/*-
+ * 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
+ * Margo Seltzer.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)hash_log2.c	8.4 (Berkeley) 11/7/95";
+#endif /* LIBC_SCCS and not lint */
+
+#include "db-int.h"
+
+u_int32_t
+__log2(num)
+	u_int32_t num;
+{
+	u_int32_t i, limit;
+
+	limit = 1;
+	for (i = 0; limit < num; limit = limit << 1, i++);
+	return (i);
+}
diff --git a/src/util/db2/hash/hash_page.c b/src/util/db2/hash/hash_page.c
new file mode 100644
index 000000000..8622075d1
--- /dev/null
+++ b/src/util/db2/hash/hash_page.c
@@ -0,0 +1,1380 @@
+/*-
+ * 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
+ * Margo Seltzer.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)hash_page.c	8.11 (Berkeley) 11/7/95";
+#endif /* LIBC_SCCS and not lint */
+
+/*
+ * PACKAGE:  hashing
+ *
+ * DESCRIPTION:
+ *      Page manipulation for hashing package.
+ *
+ * ROUTINES:
+ *
+ * External
+ *      __get_page
+ *      __add_ovflpage
+ * Internal
+ *      overflow_page
+ *      open_temp
+ */
+
+#include <sys/types.h>
+
+#ifdef DEBUG
+#include <assert.h>
+#endif
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "db-int.h"
+#include "hash.h"
+#include "page.h"
+#include "extern.h"
+
+static int32_t	 add_bigptr __P((HTAB *, ITEM_INFO *, indx_t));
+static u_int32_t *fetch_bitmap __P((HTAB *, int32_t));
+static u_int32_t first_free __P((u_int32_t));
+static indx_t	 next_realkey __P((PAGE16 *, indx_t));
+static u_int16_t overflow_page __P((HTAB *));
+static void	 page_init __P((HTAB *, PAGE16 *, db_pgno_t, u_int8_t));
+static indx_t	 prev_realkey __P((PAGE16 *, indx_t));
+static void	 putpair __P((PAGE8 *, const DBT *, const DBT *));
+static void	 swap_page_header_in __P((PAGE16 *));
+static void	 swap_page_header_out __P((PAGE16 *));
+
+#ifdef DEBUG_SLOW
+static void	 account_page(HTAB *, db_pgno_t, int);
+#endif
+
+u_int32_t
+__get_item(hashp, cursorp, key, val, item_info)
+	HTAB *hashp;
+	CURSOR *cursorp;
+	DBT *key, *val;
+	ITEM_INFO *item_info;
+{
+	db_pgno_t next_pgno;
+	int32_t i;
+
+	/* Check if we need to get a page. */
+	if (!cursorp->pagep) {
+		if (cursorp->pgno == INVALID_PGNO) {
+			cursorp->pagep =
+			    __get_page(hashp, cursorp->bucket, A_BUCKET);
+			cursorp->pgno = ADDR(cursorp->pagep);
+			cursorp->ndx = 0;
+			cursorp->pgndx = 0;
+		} else 
+			cursorp->pagep =
+			    __get_page(hashp, cursorp->pgno, A_RAW);
+		if (!cursorp->pagep) {
+			item_info->status = ITEM_ERROR;
+			return (-1);
+		}
+	}
+	if (item_info->seek_size &&
+	    FREESPACE(cursorp->pagep) > item_info->seek_size)
+		item_info->seek_found_page = cursorp->pgno;
+
+	if (cursorp->pgndx == NUM_ENT(cursorp->pagep)) {
+		/* Fetch next page. */
+		if (NEXT_PGNO(cursorp->pagep) == INVALID_PGNO) {
+			item_info->status = ITEM_NO_MORE;
+			return (-1);
+		}
+		next_pgno = NEXT_PGNO(cursorp->pagep);
+		cursorp->pgndx = 0;
+		__put_page(hashp, cursorp->pagep, A_RAW, 0);
+		cursorp->pagep = __get_page(hashp, next_pgno, A_RAW);
+		if (!cursorp->pagep) {
+			item_info->status = ITEM_ERROR;
+			return (-1);
+		}
+		cursorp->pgno = next_pgno;
+	}
+	if (KEY_OFF(cursorp->pagep, cursorp->pgndx) != BIGPAIR) {
+		if ((i = prev_realkey(cursorp->pagep, cursorp->pgndx)) ==
+		    cursorp->pgndx)
+			key->size = hashp->hdr.bsize -
+			    KEY_OFF(cursorp->pagep, cursorp->pgndx);
+		else
+			key->size = DATA_OFF(cursorp->pagep, i) -
+			    KEY_OFF(cursorp->pagep, cursorp->pgndx);
+	}
+
+	/* 
+	 * All of this information will be set incorrectly for big keys, but
+	 * it will be ignored anyway.
+	 */
+	val->size = KEY_OFF(cursorp->pagep, cursorp->pgndx) -
+	    DATA_OFF(cursorp->pagep, cursorp->pgndx);
+	key->data = KEY(cursorp->pagep, cursorp->pgndx);
+	val->data = DATA(cursorp->pagep, cursorp->pgndx);
+	item_info->pgno = cursorp->pgno;
+	item_info->bucket = cursorp->bucket;
+	item_info->ndx = cursorp->ndx;
+	item_info->pgndx = cursorp->pgndx;
+	item_info->key_off = KEY_OFF(cursorp->pagep, cursorp->pgndx);
+	item_info->data_off = DATA_OFF(cursorp->pagep, cursorp->pgndx);
+	item_info->status = ITEM_OK;
+
+	return (0);
+}
+
+u_int32_t
+__get_item_reset(hashp, cursorp)
+	HTAB *hashp;
+	CURSOR *cursorp;
+{
+	if (cursorp->pagep)
+		__put_page(hashp, cursorp->pagep, A_RAW, 0);
+	cursorp->pagep = NULL;
+	cursorp->bucket = -1;
+	cursorp->ndx = 0;
+	cursorp->pgndx = 0;
+	cursorp->pgno = INVALID_PGNO;
+	return (0);
+}
+
+u_int32_t
+__get_item_done(hashp, cursorp)
+	HTAB *hashp;
+	CURSOR *cursorp;
+{
+	if (cursorp->pagep)
+		__put_page(hashp, cursorp->pagep, A_RAW, 0);
+	cursorp->pagep = NULL;
+
+	/* 
+	 * We don't throw out the page number since we might want to
+	 * continue getting on this page.
+	 */
+	return (0);
+}
+
+u_int32_t
+__get_item_first(hashp, cursorp, key, val, item_info)
+	HTAB *hashp;
+	CURSOR *cursorp;
+	DBT *key, *val;
+	ITEM_INFO *item_info;
+{
+	__get_item_reset(hashp, cursorp);
+	cursorp->bucket = 0;
+	return (__get_item_next(hashp, cursorp, key, val, item_info));
+}
+
+/*
+ * Returns a pointer to key/data pair on a page.  In the case of bigkeys,
+ * just returns the page number and index of the bigkey pointer pair.
+ */
+u_int32_t
+__get_item_next(hashp, cursorp, key, val, item_info)
+	HTAB *hashp;
+	CURSOR *cursorp;
+	DBT *key, *val;
+	ITEM_INFO *item_info;
+{
+	int stat;
+
+	stat = __get_item(hashp, cursorp, key, val, item_info);
+	cursorp->ndx++;
+	cursorp->pgndx++;
+	return (stat);
+}
+
+/*
+ * Put a non-big pair on a page.
+ */
+static void
+putpair(p, key, val)
+	PAGE8 *p;
+	const DBT *key, *val;
+{
+	u_int16_t *pagep, n, off;
+
+	pagep = (PAGE16 *)p;
+
+	/* Items on the page are 0-indexed. */
+	n = NUM_ENT(pagep);
+	off = OFFSET(pagep) - key->size + 1;
+	memmove(p + off, key->data, key->size);
+	KEY_OFF(pagep, n) = off;
+
+	off -= val->size;
+	memmove(p + off, val->data, val->size);
+	DATA_OFF(pagep, n) = off;
+
+	/* Adjust page info. */
+	NUM_ENT(pagep) = n + 1;
+	OFFSET(pagep) = off - 1;
+}
+
+/*
+ * Returns the index of the next non-bigkey pair after n on the page.
+ * Returns -1 if there are no more non-big things on the page.
+ */
+indx_t
+#ifdef __STDC__
+next_realkey(PAGE16 * pagep, indx_t n)
+#else
+next_realkey(pagep, n)
+	PAGE16 *pagep;
+	u_int32_t n;
+#endif
+{
+	indx_t i;
+
+	for (i = n + 1; i < NUM_ENT(pagep); i++)
+		if (KEY_OFF(pagep, i) != BIGPAIR)
+			return (i);
+	return (-1);
+}
+
+/*
+ * Returns the index of the previous non-bigkey pair after n on the page.
+ * Returns n if there are no previous non-big things on the page.
+ */
+static indx_t
+#ifdef __STDC__
+prev_realkey(PAGE16 * pagep, indx_t n)
+#else
+prev_realkey(pagep, n)
+	PAGE16 *pagep;
+	u_int32_t n;
+#endif
+{
+	int32_t i;
+
+	/* Need a signed value to do the compare properly. */
+	for (i = n - 1; i > -1; i--)
+		if (KEY_OFF(pagep, i) != BIGPAIR)
+			return (i);
+	return (n);
+}
+
+/*
+ * Returns:
+ *       0 OK
+ *      -1 error
+ */
+extern int32_t
+__delpair(hashp, cursorp, item_info)
+	HTAB *hashp;
+	CURSOR *cursorp;
+	ITEM_INFO *item_info;
+{
+	PAGE16 *pagep;
+	indx_t ndx;
+	short check_ndx;
+	int16_t delta, len, next_key;
+	int32_t n;
+	u_int8_t *src, *dest;
+
+	ndx = cursorp->pgndx;
+	if (!cursorp->pagep) {
+		pagep = __get_page(hashp, cursorp->pgno, A_RAW);
+		if (!pagep)
+			return (-1);
+		/*
+		 * KLUGE: pgndx has gone one too far, because cursor points
+		 * to the _next_ item.  Use pgndx - 1.
+		 */
+		--ndx;
+	} else
+		pagep = cursorp->pagep;
+#ifdef DEBUG
+	assert(ADDR(pagep) == cursorp->pgno);
+#endif
+
+	if (KEY_OFF(pagep, ndx) == BIGPAIR) {
+		delta = 0;
+		__big_delete(hashp, pagep, ndx);
+	} else {
+		/*
+		 * Compute "delta", the amount we have to shift all of the
+		 * offsets.  To find the delta, we need to make sure that
+		 * we aren't looking at the DATA_OFF of a big/keydata pair.
+		 */
+		for (check_ndx = (short)(ndx - 1);
+		    check_ndx >= 0 && KEY_OFF(pagep, check_ndx) == BIGPAIR;
+		    check_ndx--);
+		if (check_ndx < 0)
+			delta = hashp->hdr.bsize - DATA_OFF(pagep, ndx);
+		else
+			delta =
+			    DATA_OFF(pagep, check_ndx) - DATA_OFF(pagep, ndx);
+
+		/*
+		 * The hard case: we want to remove something other than
+		 * the last item on the page.  We need to shift data and
+		 * offsets down.
+		 */
+		if (ndx != NUM_ENT(pagep) - 1) {
+			/*
+			 * Move the data: src is the address of the last data
+			 * item on the page.
+			 */
+			src = (u_int8_t *)pagep + OFFSET(pagep) + 1;
+			/* 
+			 * Length is the distance between where to start
+			 * deleting and end of the data on the page.
+			 */
+			len = DATA_OFF(pagep, ndx) - (OFFSET(pagep) + 1);
+			/*
+			 * Dest is the location of the to-be-deleted item
+			 * occupied - length.
+			 */
+			if (check_ndx < 0)
+				dest =
+				    (u_int8_t *)pagep + hashp->hdr.bsize - len;
+			else
+				dest = (u_int8_t *)pagep +
+				    DATA_OFF(pagep, (check_ndx)) - len;
+			memmove(dest, src, len);
+		}
+	}
+
+	/* Adjust the offsets. */
+	for (n = ndx; n < NUM_ENT(pagep) - 1; n++)
+		if (KEY_OFF(pagep, (n + 1)) != BIGPAIR) {
+			next_key = next_realkey(pagep, n);
+#ifdef DEBUG
+			assert(next_key != -1);
+#endif
+			KEY_OFF(pagep, n) = KEY_OFF(pagep, (n + 1)) + delta;
+			DATA_OFF(pagep, n) = DATA_OFF(pagep, (n + 1)) + delta;
+		} else {
+			KEY_OFF(pagep, n) = KEY_OFF(pagep, (n + 1));
+			DATA_OFF(pagep, n) = DATA_OFF(pagep, (n + 1));
+		}
+
+	/* Adjust page metadata. */
+	OFFSET(pagep) = OFFSET(pagep) + delta;
+	NUM_ENT(pagep) = NUM_ENT(pagep) - 1;
+
+	--hashp->hdr.nkeys;
+
+	/* Is this page now an empty overflow page?  If so, free it. */
+	if (TYPE(pagep) == HASH_OVFLPAGE && NUM_ENT(pagep) == 0) {
+		PAGE16 *empty_page;
+		db_pgno_t to_find, next_pgno, link_page;
+
+		/*
+		 * We need to go back to the first page in the chain and 
+		 * look for this page so that we can update the previous
+		 * page's NEXT_PGNO field.
+		 */
+		to_find = ADDR(pagep);
+		empty_page = pagep;
+		link_page = NEXT_PGNO(empty_page);
+		pagep = __get_page(hashp, item_info->bucket, A_BUCKET);
+		if (!pagep)
+			return (-1);
+		while (NEXT_PGNO(pagep) != to_find) {
+			next_pgno = NEXT_PGNO(pagep);
+#ifdef DEBUG
+			assert(next_pgno != INVALID_PGNO);
+#endif
+			__put_page(hashp, pagep, A_RAW, 0);
+			pagep = __get_page(hashp, next_pgno, A_RAW);
+			if (!pagep)
+				return (-1);
+		}
+
+		/*
+		 * At this point, pagep should point to the page before the
+		 * page to be deleted.
+		 */
+		NEXT_PGNO(pagep) = link_page;
+		if (item_info->pgno == to_find) {
+			item_info->pgno = ADDR(pagep);
+			item_info->pgndx = NUM_ENT(pagep);
+			item_info->seek_found_page = ADDR(pagep);
+		}
+		__delete_page(hashp, empty_page, A_OVFL);
+	}
+	__put_page(hashp, pagep, A_RAW, 1);
+
+	return (0);
+}
+
+extern int32_t
+__split_page(hashp, obucket, nbucket)
+	HTAB *hashp;
+	u_int32_t obucket, nbucket;
+{
+	DBT key, val;
+	ITEM_INFO old_ii, new_ii;
+	PAGE16 *old_pagep, *temp_pagep;
+	db_pgno_t next_pgno;
+	int32_t off;
+	u_int16_t n;
+	int8_t base_page;
+
+	off = hashp->hdr.bsize;
+	old_pagep = __get_page(hashp, obucket, A_BUCKET);
+
+	base_page = 1;
+
+	temp_pagep = hashp->split_buf;
+	memcpy(temp_pagep, old_pagep, hashp->hdr.bsize);
+
+	page_init(hashp, old_pagep, ADDR(old_pagep), HASH_PAGE);
+	__put_page(hashp, old_pagep, A_RAW, 1);
+
+	old_ii.pgno = BUCKET_TO_PAGE(obucket);
+	new_ii.pgno = BUCKET_TO_PAGE(nbucket);
+	old_ii.bucket = obucket;
+	new_ii.bucket = nbucket;
+	old_ii.seek_found_page = new_ii.seek_found_page = 0;
+
+	while (temp_pagep != 0) {
+		off = hashp->hdr.bsize;
+		for (n = 0; n < NUM_ENT(temp_pagep); n++) {
+			if (KEY_OFF(temp_pagep, n) == BIGPAIR) {
+				__get_bigkey(hashp, temp_pagep, n, &key);
+				if (__call_hash(hashp,
+				    key.data, key.size) == obucket)
+					add_bigptr(hashp, &old_ii,
+					    DATA_OFF(temp_pagep, n));
+				else
+					add_bigptr(hashp, &new_ii,
+					    DATA_OFF(temp_pagep, n));
+			} else {
+				key.size = off - KEY_OFF(temp_pagep, n);
+				key.data = KEY(temp_pagep, n);
+				off = KEY_OFF(temp_pagep, n);
+				val.size = off - DATA_OFF(temp_pagep, n);
+				val.data = DATA(temp_pagep, n);
+				if (__call_hash(hashp,
+				    key.data, key.size) == obucket)
+					__addel(hashp, &old_ii, &key, &val,
+					    NO_EXPAND, 1);
+				else
+					__addel(hashp, &new_ii, &key, &val,
+					    NO_EXPAND, 1);
+				off = DATA_OFF(temp_pagep, n);
+			}
+		}
+		next_pgno = NEXT_PGNO(temp_pagep);
+
+		/* Clear temp_page; if it's an overflow page, free it. */
+		if (!base_page)
+			__delete_page(hashp, temp_pagep, A_OVFL);
+		else
+			base_page = 0;
+		if (next_pgno != INVALID_PGNO)
+			temp_pagep = __get_page(hashp, next_pgno, A_RAW);
+		else
+			break;
+	}
+	return (0);
+}
+
+/*
+ * Add the given pair to the page.  
+ *
+ *
+ * Returns:
+ *       0 ==> OK
+ *	-1 ==> failure
+ */
+extern  int32_t
+#ifdef __STDC__
+__addel(HTAB *hashp, ITEM_INFO *item_info, const DBT *key, const DBT *val,
+    u_int32_t num_items, const u_int8_t expanding)
+#else
+__addel(hashp, item_info, key, val, num_items, expanding)
+	HTAB *hashp;
+	ITEM_INFO *item_info;
+	const DBT *key, *val;
+	u_int32_t num_items;
+	const u_int32_t expanding;
+#endif
+{
+	PAGE16 *pagep;
+	int32_t do_expand;
+	db_pgno_t next_pgno;
+
+	do_expand = 0;
+
+	pagep = __get_page(hashp,
+	    item_info->seek_found_page != 0 ?
+	    item_info->seek_found_page : item_info->pgno, A_RAW);
+	if (!pagep)
+		return (-1);
+
+	/* Advance to first page in chain with room for item. */
+	while (NUM_ENT(pagep) && NEXT_PGNO(pagep) != INVALID_PGNO) {
+		/* 
+		 * This may not be the end of the chain, but the pair may fit
+		 * anyway.
+		 */
+		if (ISBIG(PAIRSIZE(key, val), hashp) && BIGPAIRFITS(pagep))
+			break;
+		if (PAIRFITS(pagep, key, val))
+			break;
+		next_pgno = NEXT_PGNO(pagep);
+		__put_page(hashp, pagep, A_RAW, 0);
+		pagep = (PAGE16 *)__get_page(hashp, next_pgno, A_RAW);
+		if (!pagep)
+			return (-1);
+	}
+
+	if ((ISBIG(PAIRSIZE(key, val), hashp) &&
+	     !BIGPAIRFITS(pagep)) ||
+	    (!ISBIG(PAIRSIZE(key, val), hashp) &&
+	     !PAIRFITS(pagep, key, val))) {
+		do_expand = 1;
+		pagep = __add_ovflpage(hashp, pagep);
+		if (!pagep)
+			return (-1);
+
+		if ((ISBIG(PAIRSIZE(key, val), hashp) &&
+		     !BIGPAIRFITS(pagep)) ||
+		    (!ISBIG(PAIRSIZE(key, val), hashp) &&
+		     !PAIRFITS(pagep, key, val))) {
+			__put_page(hashp, pagep, A_RAW, 0);
+			return (-1);
+		}
+	}
+ 
+	/* At this point, we know the page fits, so we just add it */
+ 
+	if (ISBIG(PAIRSIZE(key, val), hashp)) {
+		if (__big_insert(hashp, pagep, key, val))
+			return (-1);
+	} else {
+		putpair((PAGE8 *)pagep, key, val);
+	}
+
+	/*
+	 * For splits, we are going to update item_info's page number
+	 * field, so that we can easily return to the same page the
+	 * next time we come in here.  For other operations, this shouldn't
+	 * matter, since adds are the last thing that happens before we
+	 * return to the user program.
+	 */
+	item_info->pgno = ADDR(pagep);
+
+	if (!expanding)
+		hashp->hdr.nkeys++;
+
+	/* Kludge: if this is a big page, then it's already been put. */
+	if (!ISBIG(PAIRSIZE(key, val), hashp))
+		__put_page(hashp, pagep, A_RAW, 1);
+
+	if (expanding)
+		item_info->caused_expand = 0;
+	else
+		switch (num_items) {
+		case NO_EXPAND:
+			item_info->caused_expand = 0;
+			break;
+		case UNKNOWN:
+			item_info->caused_expand |=
+			    (hashp->hdr.nkeys / hashp->hdr.max_bucket) >
+			    hashp->hdr.ffactor ||
+			    item_info->pgndx > hashp->hdr.ffactor;
+			break;
+		default:
+			item_info->caused_expand =
+			    num_items > hashp->hdr.ffactor ? 1 : do_expand;
+			break;
+		}
+	return (0);
+}
+
+/* 
+ * Special __addel used in big splitting; this one just puts the pointer
+ * to an already-allocated big page in the appropriate bucket.
+ */
+int32_t
+#ifdef __STDC__
+add_bigptr(HTAB * hashp, ITEM_INFO * item_info, indx_t big_pgno)
+#else
+add_bigptr(hashp, item_info, big_pgno)
+	HTAB *hashp;
+	ITEM_INFO *item_info;
+	u_int32_t big_pgno;
+#endif
+{
+	PAGE16 *pagep;
+	db_pgno_t next_pgno;
+
+	pagep = __get_page(hashp, item_info->bucket, A_BUCKET);
+	if (!pagep)
+		return (-1);
+
+	/*
+	 * Note: in __addel(), we used item_info->pgno for the beginning of
+	 * our search for space.  Now, we use item_info->bucket, since we
+	 * know that the space required by a big pair on the base page is
+	 * quite small, and we may very well find that space early in the
+	 * chain.
+	 */
+
+	/* Find first page in chain that has space for a big pair. */
+	while (NUM_ENT(pagep) && (NEXT_PGNO(pagep) != INVALID_PGNO)) {
+		if (BIGPAIRFITS(pagep))
+			break;
+		next_pgno = NEXT_PGNO(pagep);
+		__put_page(hashp, pagep, A_RAW, 0);
+		pagep = __get_page(hashp, next_pgno, A_RAW);
+		if (!pagep)
+			return (-1);
+	}
+	if (!BIGPAIRFITS(pagep)) {
+		pagep = __add_ovflpage(hashp, pagep);
+		if (!pagep)
+			return (-1);
+#ifdef DEBUG
+		assert(BIGPAIRFITS(pagep));
+#endif
+	}
+	KEY_OFF(pagep, NUM_ENT(pagep)) = BIGPAIR;
+	DATA_OFF(pagep, NUM_ENT(pagep)) = big_pgno;
+	NUM_ENT(pagep) = NUM_ENT(pagep) + 1;
+
+	__put_page(hashp, pagep, A_RAW, 1);
+
+	return (0);
+}
+
+/*
+ *
+ * Returns:
+ *      pointer on success
+ *      NULL on error
+ */
+extern PAGE16 *
+__add_ovflpage(hashp, pagep)
+	HTAB *hashp;
+	PAGE16 *pagep;
+{
+	PAGE16 *new_pagep;
+	u_int16_t ovfl_num;
+
+	/* Check if we are dynamically determining the fill factor. */
+	if (hashp->hdr.ffactor == DEF_FFACTOR) {
+		hashp->hdr.ffactor = NUM_ENT(pagep) >> 1;
+		if (hashp->hdr.ffactor < MIN_FFACTOR)
+			hashp->hdr.ffactor = MIN_FFACTOR;
+	}
+	ovfl_num = overflow_page(hashp);
+
+	if (__new_page(hashp, (u_int32_t)ovfl_num, A_OVFL) != 0)
+		return (NULL);
+
+	if (!ovfl_num || !(new_pagep = __get_page(hashp, ovfl_num, A_OVFL)))
+		return (NULL);
+
+	NEXT_PGNO(pagep) = (db_pgno_t)OADDR_TO_PAGE(ovfl_num);
+	TYPE(new_pagep) = HASH_OVFLPAGE;
+
+	__put_page(hashp, pagep, A_RAW, 1);
+
+#ifdef HASH_STATISTICS
+	hash_overflows++;
+#endif
+	return (new_pagep);
+}
+
+/*
+ *
+ * Returns:
+ *      pointer on success
+ *      NULL on error
+ */
+extern PAGE16 *
+#ifdef __STDC__
+__add_bigpage(HTAB * hashp, PAGE16 * pagep, indx_t ndx, const u_int8_t
+    is_basepage)
+#else
+__add_bigpage(hashp, pagep, ndx, is_basepage)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	u_int32_t ndx;
+	const u_int32_t is_basepage;
+#endif
+{
+	PAGE16 *new_pagep;
+	u_int16_t ovfl_num;
+
+	ovfl_num = overflow_page(hashp);
+
+	if (__new_page(hashp, (u_int32_t)ovfl_num, A_OVFL) != 0)
+		return (NULL);
+
+	if (!ovfl_num || !(new_pagep = __get_page(hashp, ovfl_num, A_OVFL)))
+		return (NULL);
+
+	if (is_basepage) {
+		KEY_OFF(pagep, ndx) = BIGPAIR;
+		DATA_OFF(pagep, ndx) = (indx_t)ovfl_num;
+	} else
+		NEXT_PGNO(pagep) = ADDR(new_pagep);
+
+	__put_page(hashp, pagep, A_RAW, 1);
+
+	TYPE(new_pagep) = HASH_BIGPAGE;
+
+#ifdef HASH_STATISTICS
+	hash_bigpages++;
+#endif
+	return (new_pagep);
+}
+
+static void
+#ifdef __STDC__
+page_init(HTAB * hashp, PAGE16 * pagep, db_pgno_t pgno, u_int8_t type)
+#else
+page_init(hashp, pagep, pgno, type)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	db_pgno_t pgno;
+	u_int32_t type;
+#endif
+{
+	NUM_ENT(pagep) = 0;
+	PREV_PGNO(pagep) = NEXT_PGNO(pagep) = INVALID_PGNO;
+	TYPE(pagep) = type;
+	OFFSET(pagep) = hashp->hdr.bsize - 1;
+	/*
+	 * Note: since in the current version ADDR(pagep) == PREV_PGNO(pagep),
+	 * make sure that ADDR(pagep) is set after resetting PREV_PGNO(pagep).
+	 * We reset PREV_PGNO(pagep) just in case the macros are changed.
+	 */
+	ADDR(pagep) = pgno;
+
+	return;
+}
+
+int32_t
+__new_page(hashp, addr, addr_type)
+	HTAB *hashp;
+	u_int32_t addr;
+	int32_t addr_type;
+{
+	db_pgno_t paddr;
+	PAGE16 *pagep;
+
+	switch (addr_type) {		/* Convert page number. */
+	case A_BUCKET:
+		paddr = BUCKET_TO_PAGE(addr);
+		break;
+	case A_OVFL:
+	case A_BITMAP:
+		paddr = OADDR_TO_PAGE(addr);
+		break;
+	default:
+		paddr = addr;
+		break;
+	}
+	pagep = mpool_new(hashp->mp, &paddr, MPOOL_PAGE_REQUEST);
+	if (!pagep)
+		return (-1);
+#if DEBUG_SLOW
+	account_page(hashp, paddr, 1);
+#endif
+
+	if (addr_type != A_BITMAP)
+		page_init(hashp, pagep, paddr, HASH_PAGE);
+
+	__put_page(hashp, pagep, addr_type, 1);
+
+	return (0);
+}
+
+int32_t
+__delete_page(hashp, pagep, page_type)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	int32_t page_type;
+{
+	if (page_type == A_OVFL)
+		__free_ovflpage(hashp, pagep);
+	return (mpool_delete(hashp->mp, pagep));
+}
+
+u_int8_t
+is_bitmap_pgno(hashp, pgno)
+	HTAB *hashp;
+	db_pgno_t pgno;
+{
+	int32_t i;
+
+	for (i = 0; i < hashp->nmaps; i++)
+		if (OADDR_TO_PAGE(hashp->hdr.bitmaps[i]) == pgno)
+			return (1);
+	return (0);
+}
+
+void
+__pgin_routine(pg_cookie, pgno, page)
+	void *pg_cookie;
+	db_pgno_t pgno;
+	void *page;
+{
+	HTAB *hashp;
+	PAGE16 *pagep;
+	int32_t max, i;
+
+	pagep = (PAGE16 *)page;
+	hashp = (HTAB *)pg_cookie;
+
+	/* 
+	 * There are the following cases for swapping: 
+	 * 0) New page that may be unitialized.
+	 * 1) Bucket page or overflow page.  Either swap
+	 *	the header or initialize the page.
+	 * 2) Bitmap page.  Swap the whole page!
+	 * 3) Header pages.  Not handled here; these are written directly
+	 *    to the file.
+	 */
+
+	if (NUM_ENT(pagep) == 0 && NEXT_PGNO(pagep) == 0 &&
+	    !is_bitmap_pgno(hashp, pgno)) {
+		/* XXX check for !0 LSN */
+		page_init(hashp, pagep, pgno, HASH_PAGE);
+		return;
+	}
+
+	if (hashp->hdr.lorder == DB_BYTE_ORDER)
+		return;
+	if (is_bitmap_pgno(hashp, pgno)) {
+		max = hashp->hdr.bsize >> 2;	/* divide by 4 bytes */
+		for (i = 0; i < max; i++)
+			M_32_SWAP(((int32_t *)pagep)[i]);
+	} else
+		swap_page_header_in(pagep);
+}
+
+void
+__pgout_routine(pg_cookie, pgno, page)
+	void *pg_cookie;
+	db_pgno_t pgno;
+	void *page;
+{
+	HTAB *hashp;
+	PAGE16 *pagep;
+	int32_t i, max;
+
+	pagep = (PAGE16 *)page;
+	hashp = (HTAB *)pg_cookie;
+
+	/* 
+	 * There are the following cases for swapping: 
+	 * 1) Bucket page or overflow page.  Just swap the header.
+	 * 2) Bitmap page.  Swap the whole page!
+	 * 3) Header pages.  Not handled here; these are written directly
+	 *    to the file.
+	 */
+
+	if (hashp->hdr.lorder == DB_BYTE_ORDER)
+		return;
+	if (is_bitmap_pgno(hashp, pgno)) {
+		max = hashp->hdr.bsize >> 2;	/* divide by 4 bytes */
+		for (i = 0; i < max; i++)
+			M_32_SWAP(((int32_t *)pagep)[i]);
+	} else
+		swap_page_header_out(pagep);
+}
+
+/*
+ *
+ * Returns:
+ *       0 ==> OK
+ *      -1 ==>failure
+ */
+extern int32_t
+__put_page(hashp, pagep, addr_type, is_dirty)
+	HTAB *hashp;
+	PAGE16 *pagep;
+	int32_t addr_type, is_dirty;
+{
+#if DEBUG_SLOW
+	account_page(hashp,
+	    ((BKT *)((char *)pagep - sizeof(BKT)))->pgno, -1);
+#endif
+
+	return (mpool_put(hashp->mp, pagep, (is_dirty ? MPOOL_DIRTY : 0)));
+}
+
+/*
+ * Returns:
+ *       0 indicates SUCCESS
+ *      -1 indicates FAILURE
+ */
+extern PAGE16 *
+__get_page(hashp, addr, addr_type)
+	HTAB *hashp;
+	u_int32_t addr;
+	int32_t addr_type;
+{
+	PAGE16 *pagep;
+	db_pgno_t paddr;
+
+	switch (addr_type) {			/* Convert page number. */
+	case A_BUCKET:
+		paddr = BUCKET_TO_PAGE(addr);
+		break;
+	case A_OVFL:
+	case A_BITMAP:
+		paddr = OADDR_TO_PAGE(addr);
+		break;
+	default:
+		paddr = addr;
+		break;
+	}
+	pagep = (PAGE16 *)mpool_get(hashp->mp, paddr, 0);
+
+#if DEBUG_SLOW
+	account_page(hashp, paddr, 1);
+#endif
+#ifdef DEBUG
+	assert(ADDR(pagep) == paddr || ADDR(pagep) == 0 ||
+	    addr_type == A_BITMAP || addr_type == A_HEADER);
+#endif
+
+	return (pagep);
+}
+
+void
+swap_page_header_in(pagep)
+	PAGE16 *pagep;
+{
+	u_int32_t i;
+
+	/* can leave type and filler alone, since they're 1-byte quantities */
+
+	M_32_SWAP(PREV_PGNO(pagep));
+	M_32_SWAP(NEXT_PGNO(pagep));
+	M_16_SWAP(NUM_ENT(pagep));
+	M_16_SWAP(OFFSET(pagep));
+
+	for (i = 0; i < NUM_ENT(pagep); i++) {
+		M_16_SWAP(KEY_OFF(pagep, i));
+		M_16_SWAP(DATA_OFF(pagep, i));
+	}
+}
+
+void
+swap_page_header_out(pagep)
+	PAGE16 *pagep;
+{
+	u_int32_t i;
+
+	for (i = 0; i < NUM_ENT(pagep); i++) {
+		M_16_SWAP(KEY_OFF(pagep, i));
+		M_16_SWAP(DATA_OFF(pagep, i))
+	}
+
+	/* can leave type and filler alone, since they're 1-byte quantities */
+
+	M_32_SWAP(PREV_PGNO(pagep));
+	M_32_SWAP(NEXT_PGNO(pagep));
+	M_16_SWAP(NUM_ENT(pagep));
+	M_16_SWAP(OFFSET(pagep));
+}
+
+#define BYTE_MASK	((1 << INT32_T_BYTE_SHIFT) -1)
+/*
+ * Initialize a new bitmap page.  Bitmap pages are left in memory
+ * once they are read in.
+ */
+extern int32_t
+__ibitmap(hashp, pnum, nbits, ndx)
+	HTAB *hashp;
+	int32_t pnum, nbits, ndx;
+{
+	u_int32_t *ip;
+	int32_t clearbytes, clearints;
+
+	/* make a new bitmap page */
+	if (__new_page(hashp, pnum, A_BITMAP) != 0)
+		return (1);
+	if (!(ip = (u_int32_t *)__get_page(hashp, pnum, A_BITMAP)))
+		return (1);
+	hashp->nmaps++;
+	clearints = ((nbits - 1) >> INT32_T_BYTE_SHIFT) + 1;
+	clearbytes = clearints << INT32_T_TO_BYTE;
+	(void)memset((int8_t *)ip, 0, clearbytes);
+	(void)memset((int8_t *)ip + clearbytes,
+	    0xFF, hashp->hdr.bsize - clearbytes);
+	ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK);
+	SETBIT(ip, 0);
+	hashp->hdr.bitmaps[ndx] = (u_int16_t)pnum;
+	hashp->mapp[ndx] = ip;
+	return (0);
+}
+
+static u_int32_t
+first_free(map)
+	u_int32_t map;
+{
+	u_int32_t i, mask;
+
+	for (mask = 0x1, i = 0; i < BITS_PER_MAP; i++) {
+		if (!(mask & map))
+			return (i);
+		mask = mask << 1;
+	}
+	return (i);
+}
+
+static u_int16_t
+overflow_page(hashp)
+	HTAB *hashp;
+{
+	u_int32_t *freep;
+	int32_t bit, first_page, free_bit, free_page, i, in_use_bits, j;
+	int32_t max_free, offset, splitnum;
+	u_int16_t addr;
+#ifdef DEBUG2
+	int32_t tmp1, tmp2;
+#endif
+
+	splitnum = hashp->hdr.ovfl_point;
+	max_free = hashp->hdr.spares[splitnum];
+
+	free_page = (max_free - 1) >> (hashp->hdr.bshift + BYTE_SHIFT);
+	free_bit = (max_free - 1) & ((hashp->hdr.bsize << BYTE_SHIFT) - 1);
+
+	/*
+	 * Look through all the free maps to find the first free block.
+ 	 * The compiler under -Wall will complain that freep may be used
+	 * before being set, however, this loop will ALWAYS get executed
+	 * at least once, so freep is guaranteed to be set.
+	 */
+	first_page = hashp->hdr.last_freed >> (hashp->hdr.bshift + BYTE_SHIFT);
+	for (i = first_page; i <= free_page; i++) {
+		if (!(freep = fetch_bitmap(hashp, i)))
+			return (0);
+		if (i == free_page)
+			in_use_bits = free_bit;
+		else
+			in_use_bits = (hashp->hdr.bsize << BYTE_SHIFT) - 1;
+
+		if (i == first_page) {
+			bit = hashp->hdr.last_freed &
+			    ((hashp->hdr.bsize << BYTE_SHIFT) - 1);
+			j = bit / BITS_PER_MAP;
+			bit = bit & ~(BITS_PER_MAP - 1);
+		} else {
+			bit = 0;
+			j = 0;
+		}
+		for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
+			if (freep[j] != ALL_SET)
+				goto found;
+	}
+
+	/* No Free Page Found */
+	hashp->hdr.last_freed = hashp->hdr.spares[splitnum];
+	hashp->hdr.spares[splitnum]++;
+	offset = hashp->hdr.spares[splitnum] -
+	    (splitnum ? hashp->hdr.spares[splitnum - 1] : 0);
+
+#define	OVMSG	"HASH: Out of overflow pages.  Increase page size\n"
+
+	if (offset > SPLITMASK) {
+		if (++splitnum >= NCACHED) {
+			(void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
+			return (0);
+		}
+		hashp->hdr.ovfl_point = splitnum;
+		hashp->hdr.spares[splitnum] = hashp->hdr.spares[splitnum - 1];
+		hashp->hdr.spares[splitnum - 1]--;
+		offset = 1;
+	}
+	/* Check if we need to allocate a new bitmap page. */
+	if (free_bit == (hashp->hdr.bsize << BYTE_SHIFT) - 1) {
+		free_page++;
+		if (free_page >= NCACHED) {
+			(void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
+			return (0);
+		}
+		/*
+		 * This is tricky.  The 1 indicates that you want the new page
+		 * allocated with 1 clear bit.  Actually, you are going to
+		 * allocate 2 pages from this map.  The first is going to be
+		 * the map page, the second is the overflow page we were
+		 * looking for.  The __ibitmap routine automatically, sets
+		 * the first bit of itself to indicate that the bitmap itself
+		 * is in use.  We would explicitly set the second bit, but
+		 * don't have to if we tell __ibitmap not to leave it clear
+		 * in the first place.
+		 */
+		if (__ibitmap(hashp,
+		    (int32_t)OADDR_OF(splitnum, offset), 1, free_page))
+			return (0);
+		hashp->hdr.spares[splitnum]++;
+#ifdef DEBUG2
+		free_bit = 2;
+#endif
+		offset++;
+		if (offset > SPLITMASK) {
+			if (++splitnum >= NCACHED) {
+				(void)write(STDERR_FILENO,
+				    OVMSG, sizeof(OVMSG) - 1);
+				return (0);
+			}
+			hashp->hdr.ovfl_point = splitnum;
+			hashp->hdr.spares[splitnum] =
+			    hashp->hdr.spares[splitnum - 1];
+			hashp->hdr.spares[splitnum - 1]--;
+			offset = 0;
+		}
+	} else {
+		/*
+		 * Free_bit addresses the last used bit.  Bump it to address
+		 * the first available bit.
+		 */
+		free_bit++;
+		SETBIT(freep, free_bit);
+	}
+
+	/* Calculate address of the new overflow page */
+	addr = OADDR_OF(splitnum, offset);
+#ifdef DEBUG2
+	(void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
+	    addr, free_bit, free_page);
+#endif
+
+	if (OADDR_TO_PAGE(addr) > MAX_PAGES(hashp)) {
+		(void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
+		return (0);
+	}
+	return (addr);
+
+found:
+	bit = bit + first_free(freep[j]);
+	SETBIT(freep, bit);
+#ifdef DEBUG2
+	tmp1 = bit;
+	tmp2 = i;
+#endif
+	/*
+	 * Bits are addressed starting with 0, but overflow pages are addressed
+	 * beginning at 1. Bit is a bit address number, so we need to increment
+	 * it to convert it to a page number.
+	 */
+	bit = 1 + bit + (i * (hashp->hdr.bsize << BYTE_SHIFT));
+	if (bit >= hashp->hdr.last_freed)
+		hashp->hdr.last_freed = bit - 1;
+
+	/* Calculate the split number for this page */
+	for (i = 0; i < splitnum && (bit > hashp->hdr.spares[i]); i++);
+	offset = (i ? bit - hashp->hdr.spares[i - 1] : bit);
+	if (offset >= SPLITMASK)
+		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",
+	    addr, tmp1, tmp2);
+#endif
+
+	if (OADDR_TO_PAGE(addr) > MAX_PAGES(hashp)) {
+		(void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
+		return (0);
+	}
+	/* Allocate and return the overflow page */
+	return (addr);
+}
+
+#ifdef DEBUG
+int
+bucket_to_page(hashp, n)
+	HTAB *hashp;
+	int n;
+{
+	int ret_val;
+
+	ret_val = n + hashp->hdr.hdrpages;
+	if (n != 0)
+		ret_val += hashp->hdr.spares[__log2(n + 1) - 1];
+	return (ret_val);
+}
+
+int32_t
+oaddr_to_page(hashp, n)
+	HTAB *hashp;
+	int n;
+{
+	int ret_val, temp;
+
+	temp = (1 << SPLITNUM(n)) - 1;
+	ret_val = bucket_to_page(hashp, temp);
+	ret_val += (n & SPLITMASK);
+
+	return (ret_val);
+}
+#endif /* DEBUG */
+
+indx_t
+page_to_oaddr(hashp, pgno)
+	HTAB *hashp;
+	db_pgno_t pgno;
+{
+	int32_t sp, ret_val;
+
+	/*
+	 * To convert page number to overflow address:
+	 *
+	 * 1.  Find a starting split point -- use 0 since there are only
+	 *     32 split points.
+	 * 2.  Find the split point s.t. 2^sp + hdr.spares[sp] < pgno and
+	 *     2^(sp+1) = hdr.spares[sp+1] > pgno.  The overflow address will
+	 *     be located at sp.
+	 * 3.  return...
+	 */
+	pgno -= hashp->hdr.hdrpages;
+	for (sp = 0; sp < NCACHED; sp++)
+		if (POW2(sp) + hashp->hdr.spares[sp] < pgno &&
+		    (POW2(sp + 1) + hashp->hdr.spares[sp + 1]) > pgno)
+			break;
+
+	ret_val = OADDR_OF(sp + 1,
+	    pgno - ((POW2(sp + 1) - 1) + hashp->hdr.spares[sp]));
+#ifdef DEBUG
+	assert(OADDR_TO_PAGE(ret_val) == (pgno + hashp->hdr.hdrpages));
+#endif
+	return (ret_val);
+}
+
+/*
+ * Mark this overflow page as free.
+ */
+extern void
+__free_ovflpage(hashp, pagep)
+	HTAB *hashp;
+	PAGE16 *pagep;
+{
+	u_int32_t *freep;
+	int32_t bit_address, free_page, free_bit;
+	u_int16_t addr, ndx;
+
+	addr = page_to_oaddr(hashp, ADDR(pagep));
+
+#ifdef DEBUG2
+	(void)fprintf(stderr, "Freeing %d\n", addr);
+#endif
+	ndx = ((u_int16_t)addr) >> SPLITSHIFT;
+	bit_address =
+	    (ndx ? hashp->hdr.spares[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
+	if (bit_address < hashp->hdr.last_freed)
+		hashp->hdr.last_freed = bit_address;
+	free_page = (bit_address >> (hashp->hdr.bshift + BYTE_SHIFT));
+	free_bit = bit_address & ((hashp->hdr.bsize << BYTE_SHIFT) - 1);
+
+	freep = fetch_bitmap(hashp, free_page);
+#ifdef DEBUG
+	/*
+	 * This had better never happen.  It means we tried to read a bitmap
+	 * that has already had overflow pages allocated off it, and we
+	 * failed to read it from the file.
+	 */
+	if (!freep)
+		assert(0);
+#endif
+	CLRBIT(freep, free_bit);
+#ifdef DEBUG2
+	(void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
+	    obufp->addr, free_bit, free_page);
+#endif
+}
+
+static u_int32_t *
+fetch_bitmap(hashp, ndx)
+	HTAB *hashp;
+	int32_t ndx;
+{
+	if (ndx >= hashp->nmaps)
+		return (NULL);
+	if (!hashp->mapp[ndx])
+	    hashp->mapp[ndx] = (u_int32_t *)__get_page(hashp,
+	        hashp->hdr.bitmaps[ndx], A_BITMAP);
+
+	return (hashp->mapp[ndx]);
+}
+
+#ifdef DEBUG_SLOW
+static void
+account_page(hashp, pgno, inout)
+	HTAB *hashp;
+	db_pgno_t pgno;
+	int inout;
+{
+	static struct {
+		db_pgno_t pgno;
+		int times;
+	} list[100];
+	static int last;
+	int i, j;
+
+	if (inout == -1)			/* XXX: Kluge */
+		inout = 0;
+
+	/* Find page in list. */
+	for (i = 0; i < last; i++)
+		if (list[i].pgno == pgno)
+			break;
+	/* Not found. */
+	if (i == last) {
+		list[last].times = inout;
+		list[last].pgno = pgno;
+		last++;
+	}
+	list[i].times = inout;
+	if (list[i].times == 0) {
+		for (j = i; j < last; j++)
+			list[j] = list[j + 1];
+		last--;
+	}
+	for (i = 0; i < last; i++, list[i].times++)
+		if (list[i].times > 20 && !is_bitmap_pgno(hashp, list[i].pgno))
+			(void)fprintf(stderr,
+			    "Warning: pg %d has been out for %d times\n",
+			    list[i].pgno, list[i].times);
+}
+#endif /* DEBUG_SLOW */
diff --git a/src/util/db2/hash/hsearch.c b/src/util/db2/hash/hsearch.c
new file mode 100644
index 000000000..f257cd6ea
--- /dev/null
+++ b/src/util/db2/hash/hsearch.c
@@ -0,0 +1,107 @@
+/*-
+ * Copyright (c) 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Margo Seltzer.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)hsearch.c	8.5 (Berkeley) 9/21/94";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+
+#include <fcntl.h>
+#include <string.h>
+
+#include "db-int.h"
+#include "search.h"
+
+static DB *dbp = NULL;
+static ENTRY retval;
+
+extern int
+hcreate(nel)
+	u_int nel;
+{
+	HASHINFO info;
+
+	info.nelem = nel;
+	info.bsize = 256;
+	info.ffactor = 8;
+	info.cachesize = 0;
+	info.hash = NULL;
+	info.lorder = 0;
+	dbp = (DB *)__hash_open(NULL, O_CREAT | O_RDWR, 0600, &info, 0);
+	return (dbp != NULL);
+}
+
+extern ENTRY *
+hsearch(item, action)
+	ENTRY item;
+	ACTION action;
+{
+	DBT key, val;
+	int status;
+
+	if (!dbp)
+		return (NULL);
+	key.data = (u_char *)item.key;
+	key.size = strlen(item.key) + 1;
+
+	if (action == ENTER) {
+		val.data = (u_char *)item.data;
+		val.size = strlen(item.data) + 1;
+		status = (dbp->put)(dbp, &key, &val, R_NOOVERWRITE);
+		if (status)
+			return (NULL);
+	} else {
+		/* FIND */
+		status = (dbp->get)(dbp, &key, &val, 0);
+		if (status)
+			return (NULL);
+		else
+			item.data = (char *)val.data;
+	}
+	retval.key = item.key;
+	retval.data = item.data;
+	return (&retval);
+}
+
+extern void
+hdestroy()
+{
+	if (dbp) {
+		(void)(dbp->close)(dbp);
+		dbp = NULL;
+	}
+}
diff --git a/src/util/db2/hash/page.h b/src/util/db2/hash/page.h
new file mode 100644
index 000000000..8ef8a2e29
--- /dev/null
+++ b/src/util/db2/hash/page.h
@@ -0,0 +1,178 @@
+/*-
+ * 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
+ * Margo Seltzer.
+ *
+ * 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.
+ *
+ *	@(#)page.h	8.4 (Berkeley) 11/7/95
+ */
+
+#define HI_MASK 0xFFFF0000
+#define LO_MASK (~HI_MASK)
+
+#define HI(N) ((u_int16_t)(((N) & HI_MASK) >> 16))
+#define LO(N) ((u_int16_t)((N) & LO_MASK))
+
+/* Constants for big key page overhead information. */
+#define NUMSHORTS	0
+#define KEYLEN		1
+#define DATALEN 	2
+#define NEXTPAGE 	3
+
+/*
+ * Hash pages store meta-data beginning at the top of the page (offset 0)
+ * and key/data values beginning at the bottom of the page (offset pagesize).
+ * Fields are always accessed via macros so that we can change the page
+ * format without too much pain.  The only changes that will require massive
+ * code changes are if we no longer store key/data offsets next to each
+ * other (since we use that fact to compute key lengths).  In the accessor
+ * macros below, P means a pointer to the page, I means an index of the
+ * particular entry being accessed.
+ * 
+ * Hash base page format
+ * BYTE ITEM			NBYTES 	TYPE		ACCESSOR MACRO
+ * ---- ------------------	------	--------	--------------
+ * 0	previous page number 	4	db_pgno_t		PREV_PGNO(P)
+ * 4	next page number	4	db_pgno_t		NEXT_PGNO(P)
+ * 8	# pairs on page		2	indx_t		NUM_ENT(P)
+ * 10	page type		1	u_int8_t	TYPE(P)
+ * 11	padding			1	u_int8_t	none
+ * 12	highest free byte	2	indx_t		OFFSET(P)
+ * 14	key offset 0		2	indx_t		KEY_OFF(P, I)
+ * 16	data offset 0		2	indx_t		DATA_OFF(P, I)
+ * 18	key  offset 1		2	indx_t		KEY_OFF(P, I)
+ * 20	data offset 1		2	indx_t		DATA_OFF(P, I)
+ * ...etc...
+ */
+
+/* Indices (in bytes) of the beginning of each of these entries */
+#define I_PREV_PGNO	 0
+#define I_NEXT_PGNO	 4
+#define I_ENTRIES	 8
+#define I_TYPE		10
+#define I_HF_OFFSET	12
+
+/* Overhead is everything prior to the first key/data pair. */
+#define PAGE_OVERHEAD	(I_HF_OFFSET + sizeof(indx_t))
+
+/* To allocate a pair, we need room for one key offset and one data offset. */
+#define PAIR_OVERHEAD	((sizeof(indx_t) << 1))
+
+/* Use this macro to extract a value of type T from page P at offset O. */
+#define REFERENCE(P, T, O)  (((T *)((u_int8_t *)(P) + O))[0])
+
+/*
+ * Use these macros to access fields on a page; P is a PAGE16 *.
+ */
+#define NUM_ENT(P)	(REFERENCE((P), indx_t, I_ENTRIES))
+#define PREV_PGNO(P)	(REFERENCE((P), db_pgno_t, I_PREV_PGNO))
+#define NEXT_PGNO(P)	(REFERENCE((P), db_pgno_t, I_NEXT_PGNO))
+#define TYPE(P)		(REFERENCE((P), u_int8_t, I_TYPE))
+#define OFFSET(P)	(REFERENCE((P), indx_t, I_HF_OFFSET))
+/*
+ * We need to store a page's own address on each page (unlike the Btree
+ * access method which needs the previous page).  We use the PREV_PGNO
+ * field to store our own page number.
+ */
+#define ADDR(P)		(PREV_PGNO((P)))
+
+/* Extract key/data offsets and data for a given index. */
+#define DATA_OFF(P, N) \
+	REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD + sizeof(indx_t))
+#define KEY_OFF(P, N) \
+	REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD)
+
+#define KEY(P, N)	(((PAGE8 *)(P)) + KEY_OFF((P), (N)))
+#define DATA(P, N)	(((PAGE8 *)(P)) + DATA_OFF((P), (N)))
+
+/*
+ * Macros used to compute various sizes on a page.
+ */
+#define	PAIRSIZE(K, D)	(PAIR_OVERHEAD + (K)->size + (D)->size)
+#define BIGOVERHEAD	(4 * sizeof(u_int16_t))
+#define KEYSIZE(K)	(4 * sizeof(u_int16_t) + (K)->size);
+#define OVFLSIZE	(2 * sizeof(u_int16_t))
+#define BIGPAGEOVERHEAD (4 * sizeof(u_int16_t))
+#define BIGPAGEOFFSET   4
+#define BIGPAGESIZE(P)	((P)->BSIZE - BIGPAGEOVERHEAD)
+
+#define PAGE_META(N)	(((N) + 3) * sizeof(u_int16_t))
+#define MINFILL 0.75
+#define ISBIG(N, P)	(((N) > ((P)->hdr.bsize * MINFILL)) ? 1 : 0)
+
+#define ITEMSIZE(I)    (sizeof(u_int16_t) + (I)->size)
+
+/*
+ * Big key/data pages use a different page format.  They have a single
+ * key/data "pair" containing the length of the key and data instead
+ * of offsets.
+ */
+#define BIGKEYLEN(P)	(KEY_OFF((P), 0))
+#define BIGDATALEN(P)	(DATA_OFF((P), 0))
+#define BIGKEY(P)	(((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD)
+#define BIGDATA(P) \
+	(((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD + KEY_OFF((P), 0))
+
+
+#define OVFLPAGE	0
+#define BIGPAIR		0
+#define INVALID_PGNO	0xFFFFFFFF
+
+typedef unsigned short PAGE16;
+typedef unsigned char  PAGE8;
+
+#define A_BUCKET	0
+#define A_OVFL		1
+#define A_BITMAP	2
+#define A_RAW		4
+#define A_HEADER	5
+
+#define PAIRFITS(P,K,D)	((PAIRSIZE((K),(D))) <= FREESPACE((P)))
+#define BIGPAIRFITS(P)	((FREESPACE((P)) >= PAIR_OVERHEAD))
+/*
+ * Since these are all unsigned, we need to guarantee that we never go
+ * negative.  Offset values are 0-based and overheads are one based (i.e.
+ * one byte of overhead is 1, not 0), so we need to convert OFFSETs to
+ * 1-based counting before subtraction.
+ */
+#define FREESPACE(P) \
+	((OFFSET((P)) + 1 - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD)))
+
+/* 
+ * Overhead on header pages is just one word -- the length of the
+ * header info stored on that page.
+ */
+#define HEADER_OVERHEAD 4
+
+#define HASH_PAGE	2
+#define HASH_BIGPAGE	3
+#define HASH_OVFLPAGE	4
diff --git a/src/util/db2/hash/page.h.patch b/src/util/db2/hash/page.h.patch
new file mode 100644
index 000000000..4a0311fea
--- /dev/null
+++ b/src/util/db2/hash/page.h.patch
@@ -0,0 +1,42 @@
+*** /tmp/,RCSt1a21720	Wed Apr  3 11:49:55 1996
+--- page.h	Wed Apr  3 08:42:25 1996
+***************
+*** 158,163
+  
+  #define PAIRFITS(P,K,D)	((PAIRSIZE((K),(D))) <= FREESPACE((P)))
+  #define BIGPAIRFITS(P)	((FREESPACE((P)) >= PAIR_OVERHEAD))
+  #define FREESPACE(P) \
+  	((OFFSET((P)) - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD)))
+  
+
+--- 158,169 -----
+  
+  #define PAIRFITS(P,K,D)	((PAIRSIZE((K),(D))) <= FREESPACE((P)))
+  #define BIGPAIRFITS(P)	((FREESPACE((P)) >= PAIR_OVERHEAD))
++ /*
++  * Since these are all unsigned, we need to guarantee that we never go
++  * negative.  Offset values are 0-based and overheads are one based (i.e.
++  * one byte of overhead is 1, not 0), so we need to convert OFFSETs to
++  * 1-based counting before subtraction.
++  */
+  #define FREESPACE(P) \
+  	((OFFSET((P)) + 1 - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD)))
+  
+***************
+*** 159,165
+  #define PAIRFITS(P,K,D)	((PAIRSIZE((K),(D))) <= FREESPACE((P)))
+  #define BIGPAIRFITS(P)	((FREESPACE((P)) >= PAIR_OVERHEAD))
+  #define FREESPACE(P) \
+! 	((OFFSET((P)) - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD)))
+  
+  /* 
+   * Overhead on header pages is just one word -- the length of the
+
+--- 165,171 -----
+   * 1-based counting before subtraction.
+   */
+  #define FREESPACE(P) \
+! 	((OFFSET((P)) + 1 - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD)))
+  
+  /* 
+   * Overhead on header pages is just one word -- the length of the
diff --git a/src/util/db2/hash/search.h b/src/util/db2/hash/search.h
new file mode 100644
index 000000000..4d3b9143e
--- /dev/null
+++ b/src/util/db2/hash/search.h
@@ -0,0 +1,51 @@
+/*-
+ * Copyright (c) 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Margo Seltzer.
+ *
+ * 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.
+ *
+ *	@(#)search.h	8.1 (Berkeley) 6/4/93
+ */
+
+/* Backward compatibility to hsearch interface. */
+typedef struct entry {
+	char *key;
+	char *data;
+} ENTRY;
+
+typedef enum {
+	FIND, ENTER
+} ACTION;
+
+int	 hcreate __P((unsigned int));
+void	 hdestroy __P((void));
+ENTRY	*hsearch __P((ENTRY, ACTION));