Rename "modules" to "plugins", and fix up makefile variables etc

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

16 files changed, 4470 insertions, 0 deletions

diff --git a/src/plugins/kdb/db2/libdb2/hash/Makefile.in b/src/plugins/kdb/db2/libdb2/hash/Makefile.in
new file mode 100644
index 0000000..1e60e9a
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/hash/Makefile.in
@@ -0,0 +1,13 @@
+thisconfigdir=./..
+myfulldir=plugins/kdb/db2/libdb2/hash
+mydir=hash
+BUILDTOP=$(REL)..$(S)..$(S)..$(S)..$(S)..
+STLIBOBJS=	hash.o hash_bigkey.o hash_debug.o hash_func.o hash_log2.o \
+		hash_page.o hsearch.o dbm.o
+
+LOCALINCLUDES=	-I. -I$(srcdir)/../include -I../include -I$(srcdir)/../mpool \
+		-I$(srcdir)/../db
+
+all-unix:: all-libobjs
+clean-unix:: clean-libobjs
+# @libobj_frag@
diff --git a/src/plugins/kdb/db2/libdb2/hash/Makefile.inc b/src/plugins/kdb/db2/libdb2/hash/Makefile.inc
new file mode 100644
index 0000000..87746f7
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/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/plugins/kdb/db2/libdb2/hash/dbm.c b/src/plugins/kdb/db2/libdb2/hash/dbm.c
new file mode 100644
index 0000000..58c9df7
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/hash/dbm.c
@@ -0,0 +1,356 @@
+/*-
+ * 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 "db-dbm.h"
+#include "hash.h"
+
+/* If the two size fields of datum and DBMT are not equal, then
+ * casting between structures will result in stack garbage being
+ * transfered. Has been observed for DEC Alpha OSF, but will handle
+ *  the general case.
+ */
+
+#define NEED_COPY
+
+/*
+ *
+ * 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
+kdb2_dbminit(file)
+	char *file;
+{
+	if (__cur_db != NULL)
+		(void)kdb2_dbm_close(__cur_db);
+	if ((__cur_db = kdb2_dbm_open(file, O_RDWR|O_BINARY, 0)) != NULL)
+		return (0);
+	if ((__cur_db = kdb2_dbm_open(file, O_RDONLY|O_BINARY, 0)) != NULL)
+		return (0);
+	return (-1);
+}
+
+datum
+kdb2_fetch(key)
+	datum key;
+{
+	datum item;
+
+	if (__cur_db == NULL) {
+		no_open_db();
+		item.dptr = 0;
+		return (item);
+	}
+	return (kdb2_dbm_fetch(__cur_db, key));
+}
+
+datum
+kdb2_firstkey()
+{
+	datum item;
+
+	if (__cur_db == NULL) {
+		no_open_db();
+		item.dptr = 0;
+		return (item);
+	}
+	return (kdb2_dbm_firstkey(__cur_db));
+}
+
+datum
+kdb2_nextkey(key)
+	datum key;
+{
+	datum item;
+
+	if (__cur_db == NULL) {
+		no_open_db();
+		item.dptr = 0;
+		return (item);
+	}
+	return (kdb2_dbm_nextkey(__cur_db));
+}
+
+int
+kdb2_delete(key)
+	datum key;
+{
+	if (__cur_db == NULL) {
+		no_open_db();
+		return (-1);
+	}
+	return (kdb2_dbm_delete(__cur_db, key));
+}
+
+int
+kdb2_store(key, dat)
+	datum key, dat;
+{
+	if (__cur_db == NULL) {
+		no_open_db();
+		return (-1);
+	}
+	return (kdb2_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 *
+kdb2_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)strncpy(path, file, sizeof(path) - 1);
+	path[sizeof(path) - 1] = '\0';
+	(void)strncat(path, DBM_SUFFIX, sizeof(path) - 1 - strlen(path));
+	return ((DBM *)__hash_open(path, flags, mode, &info, 0));
+}
+
+/*
+ * Returns:
+ *	Nothing.
+ */
+void
+kdb2_dbm_close(db)
+	DBM *db;
+{
+	(void)(db->close)(db);
+}
+
+/*
+ * Returns:
+ *	DATUM on success
+ *	NULL on failure
+ */
+datum
+kdb2_dbm_fetch(db, key)
+	DBM *db;
+	datum key;
+{
+	datum retval;
+	int status;
+
+#ifdef NEED_COPY
+	DBT k, r;
+
+	k.data = key.dptr;
+	k.size = key.dsize;
+	status = (db->get)(db, &k, &r, 0);
+	retval.dptr = r.data;
+	retval.dsize = r.size;
+#else
+	status = (db->get)(db, (DBT *)&key, (DBT *)&retval, 0);
+#endif
+	if (status) {
+		retval.dptr = NULL;
+		retval.dsize = 0;
+	}
+	return (retval);
+}
+
+/*
+ * Returns:
+ *	DATUM on success
+ *	NULL on failure
+ */
+datum
+kdb2_dbm_firstkey(db)
+	DBM *db;
+{
+	int status;
+	datum retkey;
+
+#ifdef NEED_COPY
+	DBT k, r;
+
+	status = (db->seq)(db, &k, &r, R_FIRST);
+	retkey.dptr = k.data;
+	retkey.dsize = k.size;
+#else
+	datum retdata;
+
+	status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_FIRST);
+#endif
+	if (status)
+		retkey.dptr = NULL;
+	return (retkey);
+}
+
+/*
+ * Returns:
+ *	DATUM on success
+ *	NULL on failure
+ */
+datum
+kdb2_dbm_nextkey(db)
+	DBM *db;
+{
+	int status;
+	datum retkey;
+
+#ifdef NEED_COPY
+	DBT k, r;
+
+	status = (db->seq)(db, &k, &r, R_NEXT);
+	retkey.dptr = k.data;
+	retkey.dsize = k.size;
+#else
+	datum retdata;
+
+	status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_NEXT);
+#endif
+	if (status)
+		retkey.dptr = NULL;
+	return (retkey);
+}
+
+/*
+ * Returns:
+ *	 0 on success
+ *	<0 failure
+ */
+int
+kdb2_dbm_delete(db, key)
+	DBM *db;
+	datum key;
+{
+	int status;
+
+#ifdef NEED_COPY
+	DBT k;
+
+	k.data = key.dptr;
+	k.size = key.dsize;
+	status = (db->del)(db, &k, 0);
+#else
+	status = (db->del)(db, (DBT *)&key, 0);
+#endif
+	if (status)
+		return (-1);
+	else
+		return (0);
+}
+
+/*
+ * Returns:
+ *	 0 on success
+ *	<0 failure
+ *	 1 if DBM_INSERT and entry exists
+ */
+int
+kdb2_dbm_store(db, key, content, flags)
+	DBM *db;
+	datum key, content;
+	int flags;
+{
+#ifdef NEED_COPY
+	DBT k, c;
+
+	k.data = key.dptr;
+	k.size = key.dsize;
+	c.data = content.dptr;
+	c.size = content.dsize;
+	return ((db->put)(db, &k, &c,
+	    (flags == DBM_INSERT) ? R_NOOVERWRITE : 0));
+#else
+	return ((db->put)(db, (DBT *)&key, (DBT *)&content,
+	    (flags == DBM_INSERT) ? R_NOOVERWRITE : 0));
+#endif
+}
+
+int
+kdb2_dbm_error(db)
+	DBM *db;
+{
+	HTAB *hp;
+
+	hp = (HTAB *)db->internal;
+	return (hp->local_errno);
+}
+
+int
+kdb2_dbm_clearerr(db)
+	DBM *db;
+{
+	HTAB *hp;
+
+	hp = (HTAB *)db->internal;
+	hp->local_errno = 0;
+	return (0);
+}
+
+int
+kdb2_dbm_dirfno(db)
+	DBM *db;
+{
+	return(((HTAB *)db->internal)->fp);
+}
diff --git a/src/plugins/kdb/db2/libdb2/hash/extern.h b/src/plugins/kdb/db2/libdb2/hash/extern.h
new file mode 100644
index 0000000..872b6b0
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/hash/extern.h
@@ -0,0 +1,109 @@
+/*-
+ * 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
+ */
+
+#define __add_bigpage		__kdb2_add_bigpage
+#define __add_ovflpage		__kdb2_add_ovflpage
+#define __addel			__kdb2_addel
+#define __alloc_tmp		__kdb2_alloc_tmp
+#define __big_delete		__kdb2_big_delete
+#define __big_insert		__kdb2_big_insert
+#define __big_keydata		__kdb2_big_keydata
+#define __big_return		__kdb2_big_return
+#define __call_hash		__kdb2_call_hash
+#define __cursor_creat		__kdb2_cursor_creat
+#define __delete_page		__kdb2_delete_page
+#define __delpair		__kdb2_delpair
+#define __expand_table		__kdb2_expand_table
+#define __find_bigpair		__kdb2_find_bigpair
+#define __free_ovflpage		__kdb2_free_ovflpage
+#define __get_bigkey		__kdb2_get_bigkey
+#define __get_buf		__kdb2_get_buf
+#define __get_item		__kdb2_get_item
+#define __get_item_done		__kdb2_get_item_done
+#define __get_item_first	__kdb2_get_item_first
+#define __get_item_next		__kdb2_get_item_next
+#define __get_item_reset	__kdb2_get_item_reset
+#define __get_page		__kdb2_get_page
+#define __ibitmap		__kdb2_ibitmap
+#define __log2			__kdb2_log2
+#define __new_page		__kdb2_new_page
+#define __pgin_routine		__kdb2_pgin_routine
+#define __pgout_routine		__kdb2_pgout_routine
+#define __put_buf		__kdb2_put_buf
+#define __put_page		__kdb2_put_page
+#define __reclaim_tmp		__kdb2_reclaim_tmp
+#define __split_page		__kdb2_split_page
+
+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/plugins/kdb/db2/libdb2/hash/hash.c b/src/plugins/kdb/db2/libdb2/hash/hash.c
new file mode 100644
index 0000000..0e25493
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/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, const 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 *, const 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 *
+__kdb2_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 = 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|O_BINARY, 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, 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;
+	const 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;
+
+	/*
+	 * 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.
+ */
+static 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);
+}
+
+static 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->local_errno = errno = EINVAL;
+		return (ERROR);
+	}
+	return (hash_access(hashp, HASH_GET, 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->local_errno = errno = EINVAL;
+		return (ERROR);
+	}
+	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
+		hashp->local_errno = errno = EPERM;
+		return (ERROR);
+	}
+	return (hash_access(hashp, flag == R_NOOVERWRITE ?
+		HASH_PUTNEW : HASH_PUT, 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->local_errno = errno = EINVAL;
+		return (ERROR);
+	}
+	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
+		hashp->local_errno = errno = EPERM;
+		return (ERROR);
+	}
+
+	return (hash_access(hashp, HASH_DELETE, key, NULL));
+}
+
+/*
+ * Assume that hashp has been set in wrapper routine.
+ */
+static int32_t
+hash_access(hashp, action, key, val)
+	HTAB *hashp;
+	ACTION action;
+	const DBT *key;
+	DBT *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;
+}
+
+static 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->local_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);
+}
+
+static 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/plugins/kdb/db2/libdb2/hash/hash.c.patch b/src/plugins/kdb/db2/libdb2/hash/hash.c.patch
new file mode 100644
index 0000000..b72cc0d
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/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/plugins/kdb/db2/libdb2/hash/hash.h b/src/plugins/kdb/db2/libdb2/hash/hash.h
new file mode 100644
index 0000000..b202fc9
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/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 */
+	const 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	local_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_SHIFT	12		/* log2(BUCKET) */
+#define DEF_BUCKET_SIZE		(1<<DEF_BUCKET_SHIFT)
+#define DEF_SEGSIZE_SHIFT	8		/* log2(SEGSIZE)	 */
+#define DEF_SEGSIZE		(1<<DEF_SEGSIZE_SHIFT)
+#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/plugins/kdb/db2/libdb2/hash/hash_bigkey.c b/src/plugins/kdb/db2/libdb2/hash/hash_bigkey.c
new file mode 100644
index 0000000..06210a5
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/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 = (u_int8_t *)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 = (u_int8_t *)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 = (u_int8_t *)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/plugins/kdb/db2/libdb2/hash/hash_debug.c b/src/plugins/kdb/db2/libdb2/hash/hash_debug.c
new file mode 100644
index 0000000..69229fc
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/hash/hash_debug.c
@@ -0,0 +1,105 @@
+/*-
+ * 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"
+
+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/plugins/kdb/db2/libdb2/hash/hash_func.c b/src/plugins/kdb/db2/libdb2/hash/hash_func.c
new file mode 100644
index 0000000..1dee694
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/hash/hash_func.c
@@ -0,0 +1,201 @@
+/*-
+ * 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"
+
+#if 0
+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));
+#endif
+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
+
+#if 0
+static 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))
+
+static 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.
+ */
+static 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);
+}
+#endif
+
+
+/* Chris Torek's hash function. */
+static u_int32_t
+hash4(key, len)
+	const void *key;
+	size_t len;
+{
+	u_int32_t h, loop;
+	const u_int8_t *k;
+
+#define HASH4a   h = (h << 5) - h + *k++;
+#define HASH4b   h = (h << 5) + h + *k++;
+#define HASH4 HASH4b
+
+	h = 0;
+	k = (const 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/plugins/kdb/db2/libdb2/hash/hash_log2.c b/src/plugins/kdb/db2/libdb2/hash/hash_log2.c
new file mode 100644
index 0000000..8c710e5
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/hash/hash_log2.c
@@ -0,0 +1,55 @@
+/*-
+ * 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"
+#include "hash.h"
+#include "page.h"
+#include "extern.h"
+
+u_int32_t
+__kdb2_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/plugins/kdb/db2/libdb2/hash/hash_page.c b/src/plugins/kdb/db2/libdb2/hash/hash_page.c
new file mode 100644
index 0000000..e25115d
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/hash/hash_page.c
@@ -0,0 +1,1387 @@
+/*-
+ * 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 status;
+
+	status = __get_item(hashp, cursorp, key, val, item_info);
+	cursorp->ndx++;
+	cursorp->pgndx++;
+	return (status);
+}
+
+/*
+ * 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.
+ */
+static 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.
+ */
+static 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 (!ovfl_num)
+		return (NULL);
+
+	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 (!ovfl_num)
+		return (NULL);
+
+	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));
+}
+
+static 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);
+}
+
+static 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));
+	}
+}
+
+static 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);
+}
+
+/*
+ * returns 0 on error
+ */
+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 */
+
+static 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/plugins/kdb/db2/libdb2/hash/hsearch.c b/src/plugins/kdb/db2/libdb2/hash/hsearch.c
new file mode 100644
index 0000000..02ff7ef
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/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 | O_BINARY, 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/plugins/kdb/db2/libdb2/hash/page.h b/src/plugins/kdb/db2/libdb2/hash/page.h
new file mode 100644
index 0000000..8ef8a2e
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/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/plugins/kdb/db2/libdb2/hash/page.h.patch b/src/plugins/kdb/db2/libdb2/hash/page.h.patch
new file mode 100644
index 0000000..4a0311f
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/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/plugins/kdb/db2/libdb2/hash/search.h b/src/plugins/kdb/db2/libdb2/hash/search.h
new file mode 100644
index 0000000..6d6a0a8
--- /dev/null
+++ b/src/plugins/kdb/db2/libdb2/hash/search.h
@@ -0,0 +1,55 @@
+/*-
+ * 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;
+
+#define hcreate		kdb2_hcreate
+#define hdestroy	kdb2_hdestroy
+#define hsearch		kdb2_hsearch
+
+int	 hcreate __P((unsigned int));
+void	 hdestroy __P((void));
+ENTRY	*hsearch __P((ENTRY, ACTION));