Replace Berkeley DB with SQLite 3

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

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

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


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

5 files changed, 624 insertions, 0 deletions

diff --git a/utils/db1-ast/include/circ-queue.h b/utils/db1-ast/include/circ-queue.h
new file mode 100644
index 000000000..33ba9115b
--- /dev/null
+++ b/utils/db1-ast/include/circ-queue.h
@@ -0,0 +1,131 @@
+/*
+ * Copyright (c) 1991, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	@(#)queue.h	8.5 (Berkeley) 8/20/94
+ * $FreeBSD: ports/misc/44bsd-more/files/queue.h,v 1.1 2001/01/06 03:41:36 hoek Exp $
+ */
+
+/*
+ * Circular queue definitions.
+ */
+#define CIRCLEQ_HEAD(name, type)					\
+struct name {								\
+	struct type *cqh_first;		/* first element */		\
+	struct type *cqh_last;		/* last element */		\
+}
+
+#define CIRCLEQ_ENTRY(type)						\
+struct {								\
+	struct type *cqe_next;		/* next element */		\
+	struct type *cqe_prev;		/* previous element */		\
+}
+
+/*
+ * Circular queue functions.
+ */
+#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
+
+#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
+
+#define CIRCLEQ_FOREACH(var, head, field)				\
+	for((var) = (head)->cqh_first;					\
+	    (var) != (void *)(head);					\
+	    (var) = (var)->field.cqe_next)
+
+#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
+	for((var) = (head)->cqh_last;					\
+	    (var) != (void *)(head);					\
+	    (var) = (var)->field.cqe_prev)
+
+#define	CIRCLEQ_INIT(head) do {						\
+	(head)->cqh_first = (void *)(head);				\
+	(head)->cqh_last = (void *)(head);				\
+} while (0)
+
+#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
+	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
+	(elm)->field.cqe_prev = (listelm);				\
+	if ((listelm)->field.cqe_next == (void *)(head))		\
+		(head)->cqh_last = (elm);				\
+	else								\
+		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
+	(listelm)->field.cqe_next = (elm);				\
+} while (0)
+
+#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
+	(elm)->field.cqe_next = (listelm);				\
+	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
+	if ((listelm)->field.cqe_prev == (void *)(head))		\
+		(head)->cqh_first = (elm);				\
+	else								\
+		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
+	(listelm)->field.cqe_prev = (elm);				\
+} while (0)
+
+#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
+	(elm)->field.cqe_next = (head)->cqh_first;			\
+	(elm)->field.cqe_prev = (void *)(head);				\
+	if ((head)->cqh_last == (void *)(head))				\
+		(head)->cqh_last = (elm);				\
+	else								\
+		(head)->cqh_first->field.cqe_prev = (elm);		\
+	(head)->cqh_first = (elm);					\
+} while (0)
+
+#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
+	(elm)->field.cqe_next = (void *)(head);				\
+	(elm)->field.cqe_prev = (head)->cqh_last;			\
+	if ((head)->cqh_first == (void *)(head))			\
+		(head)->cqh_first = (elm);				\
+	else								\
+		(head)->cqh_last->field.cqe_next = (elm);		\
+	(head)->cqh_last = (elm);					\
+} while (0)
+
+#define CIRCLEQ_LAST(head) ((head)->cqh_last)
+
+#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)
+
+#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
+
+#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
+	if ((elm)->field.cqe_next == (void *)(head))			\
+		(head)->cqh_last = (elm)->field.cqe_prev;		\
+	else								\
+		(elm)->field.cqe_next->field.cqe_prev =			\
+		    (elm)->field.cqe_prev;				\
+	if ((elm)->field.cqe_prev == (void *)(head))			\
+		(head)->cqh_first = (elm)->field.cqe_next;		\
+	else								\
+		(elm)->field.cqe_prev->field.cqe_next =			\
+		    (elm)->field.cqe_next;				\
+} while (0)
diff --git a/utils/db1-ast/include/compat.h b/utils/db1-ast/include/compat.h
new file mode 100644
index 000000000..706e58265
--- /dev/null
+++ b/utils/db1-ast/include/compat.h
@@ -0,0 +1,49 @@
+/* Values for building 4.4 BSD db routines in the GNU C library.  */
+
+#ifndef _compat_h_
+#define _compat_h_
+
+#include <fcntl.h>
+
+/*
+ * If you can't provide lock values in the open(2) call.  Note, this
+ * allows races to happen.
+ */
+#ifndef O_EXLOCK			/* 4.4BSD extension. */
+#define	O_EXLOCK	0
+#endif
+
+#ifndef O_SHLOCK			/* 4.4BSD extension. */
+#define	O_SHLOCK	0
+#endif
+
+#include <errno.h>
+
+#ifndef EFTYPE
+#define	EFTYPE		EINVAL		/* POSIX 1003.1 format errno. */
+#endif
+
+#include <unistd.h>
+#include <limits.h>
+
+#ifndef _POSIX_VDISABLE			/* POSIX 1003.1 disabling char. */
+#define	_POSIX_VDISABLE	0		/* Some systems used 0. */
+#endif
+
+#include <termios.h>
+
+#ifndef	TCSASOFT			/* 4.4BSD extension. */
+#define	TCSASOFT	0
+#endif
+
+#include <sys/param.h>
+
+#ifndef	MAX				/* Usually found in <sys/param.h>. */
+#define	MAX(_a,_b)	((_a)<(_b)?(_b):(_a))
+#endif
+#ifndef	MIN				/* Usually found in <sys/param.h>. */
+#define	MIN(_a,_b)	((_a)<(_b)?(_a):(_b))
+#endif
+
+
+#endif /* compat.h */
diff --git a/utils/db1-ast/include/db.h b/utils/db1-ast/include/db.h
new file mode 100644
index 000000000..a58724bdd
--- /dev/null
+++ b/utils/db1-ast/include/db.h
@@ -0,0 +1,250 @@
+/*-
+ * Copyright (c) 1990, 1993, 1994
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	@(#)db.h	8.7 (Berkeley) 6/16/94
+ */
+
+#ifndef _DB_H
+#define	_DB_H 1
+
+#include <sys/types.h>
+#include <sys/cdefs.h>
+
+#include <limits.h>
+
+#ifdef __DBINTERFACE_PRIVATE
+#include <compat.h>
+#endif
+
+#ifdef SOLARIS
+#include "solaris-compat/compat.h"
+#endif
+
+#define	RET_ERROR	-1		/* Return values. */
+#define	RET_SUCCESS	 0
+#define	RET_SPECIAL	 1
+
+#ifndef	__BIT_TYPES_DEFINED__
+#define	__BIT_TYPES_DEFINED__
+#if (!defined(__FreeBSD__) && !defined(__NetBSD__) && !defined(__APPLE__))
+typedef	__signed char		   int8_t;
+typedef	short			  int16_t;
+typedef	int			  int32_t;
+typedef	unsigned char		 u_int8_t;
+typedef	unsigned short		u_int16_t;
+typedef	unsigned int		u_int32_t;
+#ifdef WE_DONT_NEED_QUADS
+typedef	long long		  int64_t;
+typedef	unsigned long long	u_int64_t;
+#endif
+#endif /* __FreeBSD__ */
+#endif
+
+#ifdef SOLARIS
+#define	__P(p) p
+#define __BEGIN_DECLS
+#define __END_DECLS
+#endif
+
+#define	MAX_PAGE_NUMBER	0xffffffff	/* >= # of pages in a file */
+typedef u_int32_t	pgno_t;
+#define	MAX_PAGE_OFFSET	65535		/* >= # of bytes in a page */
+typedef u_int16_t	indx_t;
+#define	MAX_REC_NUMBER	0xffffffff	/* >= # of records in a tree */
+typedef u_int32_t	recno_t;
+
+/* Key/data structure -- a Data-Base Thang. */
+typedef struct {
+	void	*data;			/* data */
+	size_t	 size;			/* data length */
+} DBT;
+
+/* Routine flags. */
+#define	R_CURSOR	1		/* del, put, seq */
+#define	__R_UNUSED	2		/* UNUSED */
+#define	R_FIRST		3		/* seq */
+#define	R_IAFTER	4		/* put (RECNO) */
+#define	R_IBEFORE	5		/* put (RECNO) */
+#define	R_LAST		6		/* seq (BTREE, RECNO) */
+#define	R_NEXT		7		/* seq */
+#define	R_NOOVERWRITE	8		/* put */
+#define	R_PREV		9		/* seq (BTREE, RECNO) */
+#define	R_SETCURSOR	10		/* put (RECNO) */
+#define	R_RECNOSYNC	11		/* sync (RECNO) */
+
+typedef enum { DB_BTREE, DB_HASH, DB_RECNO } DBTYPE;
+
+/*
+ * !!!
+ * The following flags are included in the dbopen(3) call as part of the
+ * open(2) flags.  In order to avoid conflicts with the open flags, start
+ * at the top of the 16 or 32-bit number space and work our way down.  If
+ * the open flags were significantly expanded in the future, it could be
+ * a problem.  Wish I'd left another flags word in the dbopen call.
+ *
+ * !!!
+ * None of this stuff is implemented yet.  The only reason that it's here
+ * is so that the access methods can skip copying the key/data pair when
+ * the DB_LOCK flag isn't set.
+ */
+#if UINT_MAX > 65535
+#define	DB_LOCK		0x20000000	/* Do locking. */
+#define	DB_SHMEM	0x40000000	/* Use shared memory. */
+#define	DB_TXN		0x80000000	/* Do transactions. */
+#else
+#define	DB_LOCK		    0x2000	/* Do locking. */
+#define	DB_SHMEM	    0x4000	/* Use shared memory. */
+#define	DB_TXN		    0x8000	/* Do transactions. */
+#endif
+
+/* Access method description structure. */
+typedef struct __db {
+	DBTYPE type;			/* Underlying db type. */
+	int (*close)	__P((struct __db *));
+	int (*del)	__P((const struct __db *, const DBT *, u_int));
+	int (*get)	__P((const struct __db *, const DBT *, DBT *, u_int));
+	int (*put)	__P((const struct __db *, DBT *, const DBT *, u_int));
+	int (*seq)	__P((const struct __db *, DBT *, DBT *, u_int));
+	int (*sync)	__P((const struct __db *, u_int));
+	void *internal;			/* Access method private. */
+	int (*fd)	__P((const struct __db *));
+} DB;
+
+#define	BTREEMAGIC	0x053162
+#define	BTREEVERSION	3
+
+/* Structure used to pass parameters to the btree routines. */
+typedef struct {
+#define	R_DUP		0x01	/* duplicate keys */
+	u_long	flags;
+	u_int	cachesize;	/* bytes to cache */
+	int	maxkeypage;	/* maximum keys per page */
+	int	minkeypage;	/* minimum keys per page */
+	u_int	psize;		/* page size */
+	int	(*compare)	/* comparison function */
+	    __P((const DBT *, const DBT *));
+	size_t	(*prefix)	/* prefix function */
+	    __P((const DBT *, const DBT *));
+	int	lorder;		/* byte order */
+} BTREEINFO;
+
+#define	HASHMAGIC	0x061561
+#define	HASHVERSION	2
+
+/* Structure used to pass parameters to the hashing routines. */
+typedef struct {
+	u_int	bsize;		/* bucket size */
+	u_int	ffactor;	/* fill factor */
+	u_int	nelem;		/* number of elements */
+	u_int	cachesize;	/* bytes to cache */
+	u_int32_t		/* hash function */
+		(*hash) __P((const void *, size_t));
+	int	lorder;		/* byte order */
+} HASHINFO;
+
+/* Structure used to pass parameters to the record routines. */
+typedef struct {
+#define	R_FIXEDLEN	0x01	/* fixed-length records */
+#define	R_NOKEY		0x02	/* key not required */
+#define	R_SNAPSHOT	0x04	/* snapshot the input */
+	u_long	flags;
+	u_int	cachesize;	/* bytes to cache */
+	u_int	psize;		/* page size */
+	int	lorder;		/* byte order */
+	size_t	reclen;		/* record length (fixed-length records) */
+	u_char	bval;		/* delimiting byte (variable-length records */
+	char	*bfname;	/* btree file name */ 
+} RECNOINFO;
+
+#ifdef __DBINTERFACE_PRIVATE
+/*
+ * Little endian <==> big endian 32-bit swap macros.
+ *	M_32_SWAP	swap a memory location
+ *	P_32_SWAP	swap a referenced memory location
+ *	P_32_COPY	swap from one location to another
+ */
+#define	M_32_SWAP(a) {							\
+	u_int32_t _tmp = a;						\
+	((char *)&a)[0] = ((char *)&_tmp)[3];				\
+	((char *)&a)[1] = ((char *)&_tmp)[2];				\
+	((char *)&a)[2] = ((char *)&_tmp)[1];				\
+	((char *)&a)[3] = ((char *)&_tmp)[0];				\
+}
+#define	P_32_SWAP(a) {							\
+	u_int32_t _tmp = *(u_int32_t *)a;				\
+	((char *)a)[0] = ((char *)&_tmp)[3];				\
+	((char *)a)[1] = ((char *)&_tmp)[2];				\
+	((char *)a)[2] = ((char *)&_tmp)[1];				\
+	((char *)a)[3] = ((char *)&_tmp)[0];				\
+}
+#define	P_32_COPY(a, b) {						\
+	((char *)&(b))[0] = ((char *)&(a))[3];				\
+	((char *)&(b))[1] = ((char *)&(a))[2];				\
+	((char *)&(b))[2] = ((char *)&(a))[1];				\
+	((char *)&(b))[3] = ((char *)&(a))[0];				\
+}
+
+/*
+ * Little endian <==> big endian 16-bit swap macros.
+ *	M_16_SWAP	swap a memory location
+ *	P_16_SWAP	swap a referenced memory location
+ *	P_16_COPY	swap from one location to another
+ */
+#define	M_16_SWAP(a) {							\
+	u_int16_t _tmp = a;						\
+	((char *)&a)[0] = ((char *)&_tmp)[1];				\
+	((char *)&a)[1] = ((char *)&_tmp)[0];				\
+}
+#define	P_16_SWAP(a) {							\
+	u_int16_t _tmp = *(u_int16_t *)a;				\
+	((char *)a)[0] = ((char *)&_tmp)[1];				\
+	((char *)a)[1] = ((char *)&_tmp)[0];				\
+}
+#define	P_16_COPY(a, b) {						\
+	((char *)&(b))[0] = ((char *)&(a))[1];				\
+	((char *)&(b))[1] = ((char *)&(a))[0];				\
+}
+#endif
+
+__BEGIN_DECLS
+DB *__dbopen __P((const char *, int, int, DBTYPE, const void *));
+DB *dbopen __P((const char *, int, int, DBTYPE, const void *));
+
+#ifdef __DBINTERFACE_PRIVATE
+DB	*__bt_open __P((const char *, int, int, const BTREEINFO *, int));
+DB	*__hash_open __P((const char *, int, int, const HASHINFO *, int));
+DB	*__rec_open __P((const char *, int, int, const RECNOINFO *, int));
+void	 __dbpanic __P((DB *dbp));
+#endif
+__END_DECLS
+
+#endif /* db.h */
diff --git a/utils/db1-ast/include/mpool.h b/utils/db1-ast/include/mpool.h
new file mode 100644
index 000000000..0cfc5741c
--- /dev/null
+++ b/utils/db1-ast/include/mpool.h
@@ -0,0 +1,115 @@
+/*-
+ * 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.
+ *
+ *	@(#)mpool.h	8.2 (Berkeley) 7/14/94
+ */
+
+#ifndef _MPOOL_H
+#define _MPOOL_H 1
+
+#include <sys/queue.h>
+#ifndef CIRCLEQ_HEAD
+#include <circ-queue.h>
+#endif
+
+/*
+ * The memory pool scheme is a simple one.  Each in-memory page is referenced
+ * by a bucket which is threaded in up to two of three ways.  All active pages
+ * are threaded on a hash chain (hashed by page number) and an lru chain.
+ * Inactive pages are threaded on a free chain.  Each reference to a memory
+ * pool is handed an opaque MPOOL cookie which stores all of this information.
+ */
+#define	HASHSIZE	128
+#define	HASHKEY(pgno)	((pgno - 1) % HASHSIZE)
+
+/* The BKT structures are the elements of the queues. */
+typedef struct _bkt {
+	CIRCLEQ_ENTRY(_bkt) hq;		/* hash queue */
+	CIRCLEQ_ENTRY(_bkt) q;		/* lru queue */
+	void    *page;			/* page */
+	pgno_t   pgno;			/* page number */
+
+#define	MPOOL_DIRTY	0x01		/* page needs to be written */
+#define	MPOOL_PINNED	0x02		/* page is pinned into memory */
+	u_int8_t flags;			/* flags */
+} BKT;
+
+typedef struct MPOOL {
+	CIRCLEQ_HEAD(_lqh, _bkt) lqh;	/* lru queue head */
+					/* hash queue array */
+	CIRCLEQ_HEAD(_hqh, _bkt) hqh[HASHSIZE];
+	pgno_t	curcache;		/* current number of cached pages */
+	pgno_t	maxcache;		/* max number of cached pages */
+	pgno_t	npages;			/* number of pages in the file */
+	u_long	pagesize;		/* file page size */
+	int	fd;			/* file descriptor */
+					/* page in conversion routine */
+	void    (*pgin) __P((void *, pgno_t, void *));
+					/* page out conversion routine */
+	void    (*pgout) __P((void *, pgno_t, void *));
+	void	*pgcookie;		/* cookie for page in/out routines */
+#ifdef STATISTICS
+	u_long	cachehit;
+	u_long	cachemiss;
+	u_long	pagealloc;
+	u_long	pageflush;
+	u_long	pageget;
+	u_long	pagenew;
+	u_long	pageput;
+	u_long	pageread;
+	u_long	pagewrite;
+#endif
+} MPOOL;
+
+__BEGIN_DECLS
+MPOOL	*__mpool_open __P((void *, int, pgno_t, pgno_t));
+MPOOL	*mpool_open __P((void *, int, pgno_t, pgno_t));
+void	 __mpool_filter __P((MPOOL *, void (*)(void *, pgno_t, void *),
+	    void (*)(void *, pgno_t, void *), void *));
+void	 mpool_filter __P((MPOOL *, void (*)(void *, pgno_t, void *),
+	    void (*)(void *, pgno_t, void *), void *));
+void	*__mpool_new __P((MPOOL *, pgno_t *));
+void	*mpool_new __P((MPOOL *, pgno_t *));
+void	*__mpool_get __P((MPOOL *, pgno_t, u_int));
+void	*mpool_get __P((MPOOL *, pgno_t, u_int));
+int	 __mpool_put __P((MPOOL *, void *, u_int));
+int	 mpool_put __P((MPOOL *, void *, u_int));
+int	 __mpool_sync __P((MPOOL *));
+int	 mpool_sync __P((MPOOL *));
+int	 __mpool_close __P((MPOOL *));
+int	 mpool_close __P((MPOOL *));
+#ifdef STATISTICS
+void	 mpool_stat __P((MPOOL *));
+#endif
+__END_DECLS
+
+#endif /* mpool.h */
diff --git a/utils/db1-ast/include/ndbm.h b/utils/db1-ast/include/ndbm.h
new file mode 100644
index 000000000..d2079b0a5
--- /dev/null
+++ b/utils/db1-ast/include/ndbm.h
@@ -0,0 +1,79 @@
+/*-
+ * 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.
+ *
+ *	@(#)ndbm.h	8.1 (Berkeley) 6/2/93
+ */
+
+#ifndef _NDBM_H
+#define	_NDBM_H 1
+
+#include "db.h"
+
+/* Map dbm interface onto db(3). */
+#define DBM_RDONLY	O_RDONLY
+
+/* Flags to dbm_store(). */
+#define DBM_INSERT      0
+#define DBM_REPLACE     1
+
+/*
+ * The db(3) support for ndbm(3) always appends this suffix to the
+ * file name to avoid overwriting the user's original database.
+ */
+#define	DBM_SUFFIX	".db"
+
+typedef struct {
+	char *dptr;
+	int dsize;
+} datum;
+
+typedef DB DBM;
+#define	dbm_pagfno(a)	DBM_PAGFNO_NOT_AVAILABLE
+
+__BEGIN_DECLS
+void	 dbm_close __P((DBM *));
+int	 dbm_delete __P((DBM *, datum));
+datum	 dbm_fetch __P((DBM *, datum));
+datum	 dbm_firstkey __P((DBM *));
+long	 dbm_forder __P((DBM *, datum));
+datum	 dbm_nextkey __P((DBM *));
+DBM	*dbm_open __P((const char *, int, int));
+int	 dbm_store __P((DBM *, datum, datum, int));
+int	 dbm_dirfno __P((DBM *));
+int	 dbm_error __P((DBM *));
+int	 dbm_clearerr __P((DBM *));
+__END_DECLS
+
+#endif /* ndbm.h */