Update. cvs/libc-ud-970827

1997-08-10 19:17  Philip Blundell  <Philip.Blundell@pobox.com>

	* nss/nss_db/db-XXX.c: Include <db_185.h> not <db.h>.  Somebody
	should update this to use the new db API.
	* nss/nss_db/db-netgrp.c: Likewise.
	* nss/nss_db/db-alias.c: Likewise.
	* db2/Makefile: Makefile for db-2.x in glibc.

1997-08-27 21:20  Ulrich Drepper  <drepper@cygnus.com>

	* csu/Makefile (before-compile): New goal.  Make sure abi-tag.h
	is generated.
	[$(elf)=yes] (asm-CPPFLAGS): Make sure abi-tag.h file can be found.

	* Makeconfig [$(build-omitfp)=yes] (CFLAGS-.o): Add
	-D__USE_STRING_INLINES.
	* string/string.f: Move strnlen optimization after inclusion of
	<bits/string.h>.  Include <bits/string.h> only if __USE_STRING_INLINES
	is defined.
	* sysdeps/generic/memcpy.c: Undef memcpy to allow macro of this name
	in <bits/string.h>.
	* sysdeps/generic/memset.c: Likewise.
	* sysdeps/i386/string.h: i386 optimized string functions.
	* sysdeps/i386/i486string.h: i486+ optimized string functions.

	* Makefile (subdirs): Change db to db2.
	* shlib-versions: Bump libdb verion number to 3.
	* include/db.h: Include from db2 directory.
	* include/db_185.h: New file.
	* sysdeps/i386/Makefile [$(subdirs)=db2] (CPPFLAGS): Add macros
	to provide spinlock information for db2.
	* sysdeps/m68k/m68020/Makefile: New file.  Likewise.
	* sysdeps/sparc/Makefile: New file.  Likewise.
	* sysdeps/unix/sysv/linux/Makefile [$(subdirs)=db2] (CPPFLAGS):
	Add -DHAVE_LLSEEK.
	* db2/config.h: Hand-edited config file for db2 in glibc.
	* db2/compat.h: New file from db-2.3.4.
	* db2/db.h: Likewise.
	* db2/db_185.h: Likewise.
	* db2/db_int.h: Likewise.
	* db2/makedb.c: Likewise.
	* db2/btree/bt_close.c: Likewise.
	* db2/btree/bt_compare.c: Likewise.
	* db2/btree/bt_conv.c: Likewise.
	* db2/btree/bt_cursor.c: Likewise.
	* db2/btree/bt_delete.c: Likewise.
	* db2/btree/bt_open.c: Likewise.
	* db2/btree/bt_page.c: Likewise.
	* db2/btree/bt_put.c: Likewise.
	* db2/btree/bt_rec.c: Likewise.
	* db2/btree/bt_recno.c: Likewise.
	* db2/btree/btree_auto.c: Likewise.
	* db2/btree/bt_rsearch.c: Likewise.
	* db2/btree/bt_search.c: Likewise.
	* db2/btree/bt_split.c: Likewise.
	* db2/btree/bt_stat.c: Likewise.
	* db2/btree/btree.src: Likewise.
	* db2/common/db_appinit.c: Likewise.
	* db2/common/db_err.c: Likewise.
	* db2/common/db_byteorder.c: Likewise.
	* db2/common/db_apprec.c: Likewise.
	* db2/common/db_salloc.c: Likewise.
	* db2/common/db_log2.c: Likewise.
	* db2/common/db_region.c: Likewise.
	* db2/common/db_shash.c: Likewise.
	* db2/db/db.c: Likewise.
	* db2/db/db.src: Likewise.
	* db2/db/db_conv.c: Likewise.
	* db2/db/db_dispatch.c: Likewise.
	* db2/db/db_dup.c: Likewise.
	* db2/db/db_overflow.c: Likewise.
	* db2/db/db_pr.c: Likewise.
	* db2/db/db_rec.c: Likewise.
	* db2/db/db_ret.c: Likewise.
	* db2/db/db_thread.c: Likewise.
	* db2/db/db_auto.c: Likewise.
	* db2/db185/db185.c: Likewise.
	* db2/db185/db185_int.h: Likewise.
	* db2/dbm/dbm.c: Likewise.
	* db2/hash/hash.c: Likewise.
	* db2/hash/hash.src: Likewise.
	* db2/hash/hash_page.c: Likewise.
	* db2/hash/hash_conv.c: Likewise.
	* db2/hash/hash_debug.c: Likewise.
	* db2/hash/hash_stat.c: Likewise.
	* db2/hash/hash_rec.c: Likewise.
	* db2/hash/hash_dup.c: Likewise.
	* db2/hash/hash_func.c: Likewise.
	* db2/hash/hash_auto.c: Likewise.
	* db2/include/mp.h: Likewise.
	* db2/include/btree.h: Likewise.
	* db2/include/db.h.src: Likewise.
	* db2/include/db_int.h.src: Likewise.
	* db2/include/db_shash.h: Likewise.
	* db2/include/db_swap.h: Likewise.
	* db2/include/db_185.h.src: Likewise.
	* db2/include/txn.h: Likewise.
	* db2/include/db_am.h: Likewise.
	* db2/include/shqueue.h: Likewise.
	* db2/include/hash.h: Likewise.
	* db2/include/db_dispatch.h: Likewise.
	* db2/include/lock.h: Likewise.
	* db2/include/db_page.h: Likewise.
	* db2/include/log.h: Likewise.
	* db2/include/db_auto.h: Likewise.
	* db2/include/btree_auto.h: Likewise.
	* db2/include/hash_auto.h: Likewise.
	* db2/include/log_auto.h: Likewise.
	* db2/include/txn_auto.h: Likewise.
	* db2/include/db_ext.h: Likewise.
	* db2/include/btree_ext.h: Likewise.
	* db2/include/clib_ext.h: Likewise.
	* db2/include/common_ext.h: Likewise.
	* db2/include/hash_ext.h: Likewise.
	* db2/include/lock_ext.h: Likewise.
	* db2/include/log_ext.h: Likewise.
	* db2/include/mp_ext.h: Likewise.
	* db2/include/mutex_ext.h: Likewise.
	* db2/include/os_ext.h: Likewise.
	* db2/include/txn_ext.h: Likewise.
	* db2/include/cxx_int.h: Likewise.
	* db2/include/db_cxx.h: Likewise.
	* db2/include/queue.h: Likewise.
	* db2/lock/lock.c: Likewise.
	* db2/lock/lock_conflict.c: Likewise.
	* db2/lock/lock_util.c: Likewise.
	* db2/lock/lock_deadlock.c: Likewise.
	* db2/log/log.c: Likewise.
	* db2/log/log_get.c: Likewise.
	* db2/log/log.src: Likewise.
	* db2/log/log_compare.c: Likewise.
	* db2/log/log_put.c: Likewise.
	* db2/log/log_rec.c: Likewise.
	* db2/log/log_archive.c: Likewise.
	* db2/log/log_register.c: Likewise.
	* db2/log/log_auto.c: Likewise.
	* db2/log/log_findckp.c: Likewise.
	* db2/mp/mp_bh.c: Likewise.
	* db2/mp/mp_fget.c: Likewise.
	* db2/mp/mp_fopen.c: Likewise.
	* db2/mp/mp_fput.c: Likewise.
	* db2/mp/mp_fset.c: Likewise.
	* db2/mp/mp_open.c: Likewise.
	* db2/mp/mp_region.c: Likewise.
	* db2/mp/mp_pr.c: Likewise.
	* db2/mp/mp_sync.c: Likewise.
	* db2/mutex/68020.gcc: Likewise.
	* db2/mutex/mutex.c: Likewise.
	* db2/mutex/README: Likewise.
	* db2/mutex/x86.gcc: Likewise.
	* db2/mutex/sparc.gcc: Likewise.
	* db2/mutex/uts4.cc.s: Likewise.
	* db2/mutex/alpha.dec: Likewise.
	* db2/mutex/alpha.gcc: Likewise.
	* db2/mutex/parisc.gcc: Likewise.
	* db2/mutex/parisc.hp: Likewise.
	* db2/os/db_os_abs.c: Likewise.
	* db2/os/db_os_dir.c: Likewise.
	* db2/os/db_os_fid.c: Likewise.
	* db2/os/db_os_lseek.c: Likewise.
	* db2/os/db_os_mmap.c: Likewise.
	* db2/os/db_os_open.c: Likewise.
	* db2/os/db_os_rw.c: Likewise.
	* db2/os/db_os_sleep.c: Likewise.
	* db2/os/db_os_stat.c: Likewise.
	* db2/os/db_os_unlink.c: Likewise.
	* db2/txn/txn.c: Likewise.
	* db2/txn/txn.src: Likewise.
	* db2/txn/txn_rec.c: Likewise.
	* db2/txn/txn_auto.c: Likewise.
	* db2/clib/getlong.c: Likewise.
	* db2/progs/db_archive/db_archive.c: Likewise.
	* db2/progs/db_checkpoint/db_checkpoint.c: Likewise.
	* db2/progs/db_deadlock/db_deadlock.c: Likewise.
	* db2/progs/db_dump/db_dump.c: Likewise.
	* db2/progs/db_dump185/db_dump185.c: Likewise.
	* db2/progs/db_load/db_load.c: Likewise.
	* db2/progs/db_printlog/db_printlog.c: Likewise.
	* db2/progs/db_recover/db_recover.c: Likewise.
	* db2/progs/db_stat/db_stat.c: Likewise.

	* libio/stdio.h [__cplusplus] (__STDIO_INLINE): Define as inline.

	* po/de.po, po/sv.po: Update from 2.0.5 translations.

	* sysdeps/unix/sysv/linux/netinet/tcp.h: Pretty print.

	* sunrpc/rpc/xdr.h (XDR): Don't define argument of x_destroy callback
	as const.
	* sunrpc/xdr_mem.c (xdrmem_destroy): Don't define argument as const.
	* sunrpx/xdr_rec.c (xdrrec_destroy): Likewise.
	* sunrpx/xdr_stdio.c (xdrstdio_destroy): Likewise.

1997-08-27 18:47  Ulrich Drepper  <drepper@cygnus.com>

	* sysdeps/unix/sysv/linux/if_index.c: Include <errno.h>.
	Reported by Benjamin Kosnik <bkoz@cygnus.com>.

1997-08-27 02:27  Roland McGrath  <roland@baalperazim.frob.com>

	* abi-tags: New file.
	* csu/Makefile (distribute): Remove abi-tag.h.
	($(objpfx)abi-tag.h): New target.
	* Makefile (distribute): Add abi-tags.
	* sysdeps/unix/sysv/linux/abi-tag.h: File removed.
	* sysdeps/mach/hurd/abi-tag.h: File removed.
	* sysdeps/stub/abi-tag.h: File removed.

1997-08-25  Andreas Schwab  <schwab@issan.informatik.uni-dortmund.de>

	* sysdeps/unix/make-syscalls.sh: Change output so that it
	generates compilation rules only for the currently selected object
	suffixes.

1997-08-25  Andreas Schwab  <schwab@issan.informatik.uni-dortmund.de>

	* sysdeps/m68k/dl-machine.h (RTLD_START): Switch back to previous
	section to avoid confusing the compiler.
	* sysdeps/alpha/dl-machine.h (RTLD_START): Likewise.
	* sysdeps/i386/dl-machine.h (RTLD_START): Likewise.
	* sysdeps/mips/dl-machine.h (RTLD_START): Likewise.
	* sysdeps/mips/mips64/dl-machine.h (RTLD_START): Likewise.
	* sysdeps/sparc/sparc32/dl-machine.h (RTLD_START): Likewise.

	* sysdeps/m68k/dl-machine.h (elf_machine_load_address): Use a GOT
	relocation instead of a constant to avoid text relocation.
	(ELF_MACHINE_BEFORE_RTLD_RELOC): Removed.
	(RTLD_START): Declare global labels as functions and add size
	directive.

1997-08-25 17:01  Ulrich Drepper  <drepper@cygnus.com>

	* sysdeps/i386/bits/select.h: Correct assembler versions to work even
	for descriptors >= 32.

	* stdlib/alloca.h: Don't define alloca to __alloca since if gcc
	is used __alloca is not defined to __builtin_alloca and so might
	not be available.
	Reported by Uwe Ohse <uwe@ohse.de>.

	* sysdeps/unix/sysv/linux/sys/sysmacros.h: Define macros in a special
	way if gcc is not used and so dev_t is an array.
	Reported by Uwe Ohse <uwe@ohse.de>.

1997-08-23  Andreas Schwab  <schwab@issan.informatik.uni-dortmund.de>

	* manual/libc.texinfo: Reorder chapters to match logical order.

1997-08-25 12:22  Ulrich Drepper  <drepper@cygnus.com>

	* sunrpc/rpc/xdr.h: Change name of parameters in prototypes of
	xdr_reference, xdrmem_create, and xdrstdio_create because of clash
	with g++ internal symbols.
	Patch by Sudish Joseph <sj@eng.mindspring.net>.

	* elf/dl-deps.c: Implement handling of DT_FILTER.

1 files changed, 535 insertions, 0 deletions

diff --git a/db2/include/db_page.h b/db2/include/db_page.h
new file mode 100644
index 0000000000..9e78682c57
--- /dev/null
+++ b/db2/include/db_page.h
@@ -0,0 +1,535 @@
+/*-
+ * See the file LICENSE for redistribution information.
+ *
+ * Copyright (c) 1996, 1997
+ *	Sleepycat Software.  All rights reserved.
+ *
+ *	@(#)db_page.h	10.10 (Sleepycat) 8/18/97
+ */
+
+#ifndef _DB_PAGE_H_
+#define	_DB_PAGE_H_
+
+/*
+ * DB page formats.
+ *
+ * This implementation requires that values within the following structures
+ * NOT be padded -- note, ANSI C permits random padding within structures.
+ * If your compiler pads randomly you can just forget ever making DB run on
+ * your system.  In addition, no data type can require larger alignment than
+ * its own size, e.g., a 4-byte data element may not require 8-byte alignment.
+ *
+ * Note that key/data lengths are often stored in db_indx_t's -- this is
+ * not accidental, nor does it limit the key/data size.  If the key/data
+ * item fits on a page, it's guaranteed to be small enough to fit into a
+ * db_indx_t, and storing it in one saves space.
+ */
+
+#define	PGNO_METADATA	0	/* Metadata page number. */
+#define	PGNO_INVALID	0	/* Metadata page number, therefore illegal. */
+#define	PGNO_ROOT	1	/* Root is page #1. */
+
+/************************************************************************
+ BTREE METADATA PAGE LAYOUT
+ ************************************************************************/
+
+/*
+ * Btree metadata page layout:
+ *
+ *	+-----------------------------------+
+ *	|    lsn    |   pgno    |   magic   |
+ *	+-----------------------------------+
+ *	|   version |  pagesize |   free    |
+ *	+-----------------------------------+
+ *	|    flags  |  unused ...	    |
+ *	+-----------------------------------+
+ */
+typedef struct _btmeta {
+	DB_LSN	  lsn;		/* 00-07: LSN. */
+	db_pgno_t pgno;		/* 08-11: Current page number. */
+	u_int32_t magic;	/* 12-15: Magic number. */
+	u_int32_t version;	/* 16-19: Version. */
+	u_int32_t pagesize;	/* 20-23: Pagesize. */
+	u_int32_t maxkey;	/* 24-27: Btree: Maxkey. */
+	u_int32_t minkey;	/* 28-31: Btree: Minkey. */
+	u_int32_t free;		/* 32-35: Free list page number. */
+#define	BTM_DUP		0x001	/* 	  Duplicates. */
+#define	BTM_RECNO	0x002	/*	  Recno tree. */
+#define	BTM_RECNUM	0x004	/*	  Btree: maintain record count. */
+#define	BTM_FIXEDLEN	0x008	/*	  Recno: fixed length records. */
+#define	BTM_RENUMBER	0x010	/*	  Recno: renumber on insert/delete. */
+#define	BTM_MASK	0x01f
+	u_int32_t flags;	/* 36-39: Flags. */
+	u_int32_t re_len;	/* 40-43: Recno: fixed-length record length. */
+	u_int32_t re_pad;	/* 44-47: Recno: fixed-length record pad. */
+				/* 48-67: Unique file ID. */
+	u_int8_t  uid[DB_FILE_ID_LEN];
+
+	u_int32_t spare[13];	/* 68-123: Save some room for growth. */
+
+	DB_BTREE_LSTAT stat;	/* 124-163: Statistics. */
+} BTMETA;
+
+/************************************************************************
+ HASH METADATA PAGE LAYOUT
+ ************************************************************************/
+
+/*
+ * Hash metadata page layout:
+ *
+ *	+-----------------------------------+
+ *	|    lsn    |   magic   |  version  |
+ *	+-----------------------------------+
+ *	|  pagesize | ovfl_point| last_freed|
+ *	+-----------------------------------+
+ *	| max_bucket| high_mask | low_mask  |
+ *	+-----------------------------------+
+ * 	| ffactor   |   nelem   | charkey   |
+ *	+-----------------------------------+
+ *	| spares[32]|   flags   | unused    |
+ *	+-----------------------------------+
+ */
+/* Hash Table Information */
+typedef struct hashhdr {	/* Disk resident portion */
+	DB_LSN	lsn;		/* 00-07: LSN of the header page */
+	db_pgno_t pgno;		/* 08-11: Page number (btree compatibility). */
+	u_int32_t magic;	/* 12-15: Magic NO for hash tables */
+	u_int32_t version;	/* 16-19: Version ID */
+	u_int32_t pagesize;	/* 20-23: Bucket/Page Size */
+	u_int32_t ovfl_point;	/* 24-27: Overflow page allocation location */
+	u_int32_t last_freed;	/* 28-31: Last freed overflow page pgno */
+	u_int32_t max_bucket;	/* 32-35: ID of Maximum bucket in use */
+	u_int32_t high_mask;	/* 36-39: Modulo mask into table */
+	u_int32_t low_mask;	/* 40-43: Modulo mask into table lower half */
+	u_int32_t ffactor;	/* 44-47: Fill factor */
+	u_int32_t nelem;	/* 48-51: Number of keys in hash table */
+	u_int32_t h_charkey;	/* 52-55: Value of hash(CHARKEY) */
+#define	DB_HASH_DUP	0x01
+	u_int32_t flags;	/* 56-59: Allow duplicates. */
+#define NCACHED	32		/* number of spare points */
+				/* 60-187: Spare pages for overflow */
+	u_int32_t spares[NCACHED];
+				/* 188-207: Unique file ID. */
+	u_int8_t  uid[DB_FILE_ID_LEN];
+
+	/*
+	 * Minimum page size is 256.
+	 */
+} HASHHDR;
+
+/************************************************************************
+ MAIN PAGE LAYOUT
+ ************************************************************************/
+
+/*
+ *	+-----------------------------------+
+ *	|    lsn    |   pgno    | prev pgno |
+ *	+-----------------------------------+
+ *	| next pgno |  entries  | hf offset |
+ *	+-----------------------------------+
+ *	|   level   |   type    |   index   |
+ *	+-----------------------------------+
+ *	|   index   | free -->              |
+ *	+-----------+-----------------------+
+ *	|   	 F R E E A R E A            |
+ *	+-----------------------------------+
+ *	|              <-- free |   item    |
+ *	+-----------------------------------+
+ *	|   item    |   item    |   item    |
+ *	+-----------------------------------+
+ *
+ * sizeof(PAGE) == 26 bytes, and the following indices are guaranteed to be
+ * two-byte aligned.
+ *
+ * For hash and btree leaf pages, index items are paired, e.g., inp[0] is the
+ * key for inp[1]'s data.  All other types of pages only contain single items.
+ */
+typedef struct _db_page {
+	DB_LSN	  lsn;		/* 00-07: Log sequence number. */
+	db_pgno_t pgno;		/* 08-11: Current page number. */
+	db_pgno_t prev_pgno;	/* 12-15: Previous page number. */
+	db_pgno_t next_pgno;	/* 16-19: Next page number. */
+	db_indx_t entries;	/* 20-21: Number of item pairs on the page. */
+	db_indx_t hf_offset;	/* 22-23: High free byte page offset. */
+
+	/*
+	 * The btree levels are numbered from the leaf to the root, starting
+	 * with 1, so the leaf is level 1, its parent is level 2, and so on.
+	 * We maintain this level on all btree pages, but the only place that
+	 * we actually need it is on the root page.  It would not be difficult
+	 * to hide the byte on the root page once it becomes an internal page,
+	 * so we could get this byte back if we needed it for something else.
+	 */
+#define	LEAFLEVEL	  1
+#define	MAXBTREELEVEL	255
+	u_int8_t  level;	/*    24: Btree tree level. */
+
+#define	P_INVALID	0	/*	  Invalid page type. */
+#define	P_DUPLICATE	1	/*        Duplicate. */
+#define	P_HASH		2	/*        Hash. */
+#define	P_IBTREE	3	/*        Btree internal. */
+#define	P_IRECNO	4	/*        Recno internal. */
+#define	P_LBTREE	5	/*        Btree leaf. */
+#define	P_LRECNO	6	/*        Recno leaf. */
+#define	P_OVERFLOW	7	/*        Overflow. */
+	u_int8_t  type;		/*    25: Page type. */
+	db_indx_t inp[1];	/* Variable length index of items. */
+} PAGE;
+
+/* Element macros. */
+#define	LSN(p)		(((PAGE *)p)->lsn)
+#define	PGNO(p)		(((PAGE *)p)->pgno)
+#define	PREV_PGNO(p)	(((PAGE *)p)->prev_pgno)
+#define	NEXT_PGNO(p)	(((PAGE *)p)->next_pgno)
+#define	NUM_ENT(p)	(((PAGE *)p)->entries)
+#define	HOFFSET(p)	(((PAGE *)p)->hf_offset)
+#define	LEVEL(p)	(((PAGE *)p)->level)
+#define	TYPE(p)		(((PAGE *)p)->type)
+
+/*
+ * !!!
+ * The next_pgno and prev_pgno fields are not maintained for btree and recno
+ * internal pages.  It's a minor performance improvement, and more, it's
+ * hard to do when deleting internal pages, and it decreases the chance of
+ * deadlock during deletes and splits.
+ *
+ * !!!
+ * The btree/recno access method needs db_recno_t bytes of space on the root
+ * page to specify how many records are stored in the tree.  (The alternative
+ * is to store the number of records in the meta-data page, which will create
+ * a second hot spot in trees being actively modified, or recalculate it from
+ * the BINTERNAL fields on each access.)  Overload the prev_pgno field.
+ */
+#define	RE_NREC(p)							\
+	(TYPE(p) == P_LBTREE ? NUM_ENT(p) / 2 :				\
+	    TYPE(p) == P_LRECNO ? NUM_ENT(p) : PREV_PGNO(p))
+#define	RE_NREC_ADJ(p, adj)						\
+	PREV_PGNO(p) += adj;
+#define	RE_NREC_SET(p, num)						\
+	PREV_PGNO(p) = num;
+
+/*
+ * Initialize a page.
+ *
+ * !!!
+ * Don't modify the page's LSN, code depends on it being unchanged after a
+ * P_INIT call.
+ */
+#define	P_INIT(pg, pg_size, n, pg_prev, pg_next, btl, pg_type) do {	\
+	PGNO(pg) = n;							\
+	PREV_PGNO(pg) = pg_prev;					\
+	NEXT_PGNO(pg) = pg_next;					\
+	NUM_ENT(pg) = 0;						\
+	HOFFSET(pg) = pg_size;						\
+	LEVEL(pg) = btl;						\
+	TYPE(pg) = pg_type;						\
+} while (0)
+
+/* Page header length (offset to first index). */
+#define P_OVERHEAD		(SSZA(PAGE, inp))
+
+/* First free byte. */
+#define	LOFFSET(pg)		(P_OVERHEAD + NUM_ENT(pg) * sizeof(db_indx_t))
+
+/* Free space on the page. */
+#define	P_FREESPACE(pg)		(HOFFSET(pg) - LOFFSET(pg))
+
+/* Get a pointer to the bytes at a specific index. */
+#define	P_ENTRY(pg, indx)	((u_int8_t *)pg + ((PAGE *)pg)->inp[indx])
+
+/************************************************************************
+ OVERFLOW PAGE LAYOUT
+ ************************************************************************/
+
+/*
+ * Overflow items are referenced by HOFFPAGE and BOVERFLOW structures, which
+ * store a page number (the first page of the overflow item) and a length
+ * (the total length of the overflow item).  The overflow item consists of
+ * some number of overflow pages, linked by the next_pgno field of the page.
+ * A next_pgno field of PGNO_INVALID flags the end of the overflow item.
+ *
+ * Overflow page overloads:
+ *	The amount of overflow data stored on each page is stored in the
+ *	hf_offset field.
+ *
+ *	The implementation reference counts overflow items as it's possible
+ *	for them to be promoted onto btree internal pages.  The reference
+ *	count is stored in the entries field.
+ */
+#define	OV_LEN(p)	(((PAGE *)p)->hf_offset)
+#define	OV_REF(p)	(((PAGE *)p)->entries)
+
+/* Maximum number of bytes that you can put on an overflow page. */
+#define	P_MAXSPACE(psize)	((psize) - P_OVERHEAD)
+
+/************************************************************************
+ HASH PAGE LAYOUT
+ ************************************************************************/
+
+/* Each index references a group of bytes on the page. */
+#define	H_KEYDATA	1	/* Key/data item. */
+#define	H_DUPLICATE	2	/* Duplicate key/data item. */
+#define	H_OFFPAGE	3	/* Overflow key/data item. */
+#define	H_OFFDUP	4	/* Overflow page of duplicates. */
+
+/*
+ * The first and second types are H_KEYDATA and H_DUPLICATE, represented
+ * by the HKEYDATA structure:
+ *
+ *	+-----------------------------------+
+ *	|    type   | key/data ...          |
+ *	+-----------------------------------+
+ *
+ * For duplicates, the data field encodes duplicate elements in the data
+ * field:
+ *
+ *	+---------------------------------------------------------------+
+ *	|    type   | len1 | element1 | len1 | len2 | element2 | len2   |
+ *	+---------------------------------------------------------------+
+ *
+ * Thus, by keeping track of the offset in the element, we can do both
+ * backward and forward traversal.
+ */
+typedef struct _hkeydata {
+	u_int8_t  type;		/*    00: Page type. */
+	u_int8_t  data[1];	/* Variable length key/data item. */
+} HKEYDATA;
+
+/* Get a HKEYDATA item for a specific index. */
+#define	GET_HKEYDATA(pg, indx)						\
+	((HKEYDATA *)P_ENTRY(pg, indx))
+
+/*
+ * The length of any HKEYDATA item. Note that indx is an element index,
+ * not a PAIR index.
+ */
+#define	LEN_HITEM(pg, pgsize, indx)					\
+	(((indx) == 0 ? pgsize : pg->inp[indx - 1]) - pg->inp[indx])
+
+#define	LEN_HKEYDATA(pg, psize, indx)					\
+	(((indx) == 0 ? psize : pg->inp[indx - 1]) -			\
+	pg->inp[indx] - HKEYDATA_SIZE(0))
+
+/*
+ * Page space required to add a new HKEYDATA item to the page, with and
+ * without the index value.
+ */
+#define	HKEYDATA_SIZE(len)						\
+	((len) + SSZA(HKEYDATA, data))
+#define	HKEYDATA_PSIZE(len)						\
+	(HKEYDATA_SIZE(len) + sizeof(db_indx_t))
+
+/* Put a HKEYDATA item at the location referenced by a page entry. */
+#define	PUT_HKEYDATA(pe, kd, len, type) {				\
+	((HKEYDATA *)pe)->type = type;					\
+	memcpy((u_int8_t *)pe + sizeof(u_int8_t), kd, len);		\
+}
+
+/*
+ * Macros the describe the page layout in terms of key-data pairs.
+ * The use of "pindex" indicates that the argument is the index
+ * expressed in pairs instead of individual elements.
+ */
+#define H_NUMPAIRS(pg)			(NUM_ENT(pg) / 2)
+#define	H_KEYINDEX(pindx)		(2 * (pindx))
+#define	H_DATAINDEX(pindx)		((2 * (pindx)) + 1)
+#define	H_PAIRKEY(pg, pindx)		GET_HKEYDATA(pg, H_KEYINDEX(pindx))
+#define	H_PAIRDATA(pg, pindx)		GET_HKEYDATA(pg, H_DATAINDEX(pindx))
+#define H_PAIRSIZE(pg, psize, pindx)					\
+	(LEN_HITEM(pg, psize, H_KEYINDEX(pindx)) +			\
+	LEN_HITEM(pg, psize, H_DATAINDEX(pindx)))
+#define LEN_HDATA(p, psize, pindx) LEN_HKEYDATA(p, psize, H_DATAINDEX(pindx))
+#define LEN_HKEY(p, psize, pindx) LEN_HKEYDATA(p, psize, H_KEYINDEX(pindx))
+
+/*
+ * The third type is the H_OFFPAGE, represented by the HOFFPAGE structure:
+ *
+ *	+-----------------------------------+
+ *	|   type    |  pgno_t   | total len |
+ *	+-----------------------------------+
+ */
+typedef struct _hoffpage {
+	u_int8_t  type;		/*    00: Page type and delete flag. */
+	u_int8_t  unused[3];	/* 01-03: Padding, unused. */
+	db_pgno_t pgno;		/* 04-07: Offpage page number. */
+	u_int32_t tlen;		/* 08-11: Total length of item. */
+} HOFFPAGE;
+
+/* Get a HOFFPAGE item for a specific index. */
+#define	GET_HOFFPAGE(pg, indx)						\
+	((HOFFPAGE *)P_ENTRY(pg, indx))
+
+/*
+ * Page space required to add a new HOFFPAGE item to the page, with and
+ * without the index value.
+ */
+#define	HOFFPAGE_SIZE		(sizeof(HOFFPAGE))
+#define	HOFFPAGE_PSIZE		(HOFFPAGE_SIZE + sizeof(db_indx_t))
+
+/*
+ * The fourth type is H_OFFDUP represented by the HOFFDUP structure:
+ *
+ *	+-----------------------+
+ *	|   type    |  pgno_t   |
+ *	+-----------------------+
+ */
+typedef struct _hoffdup {
+	u_int8_t  type;		/*    00: Page type and delete flag. */
+	u_int8_t  unused[3];	/* 01-03: Padding, unused. */
+	db_pgno_t pgno;		/* 04-07: Offpage page number. */
+} HOFFDUP;
+
+/* Get a HOFFDUP item for a specific index. */
+#define	GET_HOFFDUP(pg, indx)						\
+	((HOFFDUP *)P_ENTRY(pg, indx))
+
+/*
+ * Page space required to add a new HOFFDUP item to the page, with and
+ * without the index value.
+ */
+#define	HOFFDUP_SIZE		(sizeof(HOFFDUP))
+#define	HOFFDUP_PSIZE		(HOFFDUP_SIZE + sizeof(db_indx_t))
+
+/************************************************************************
+ BTREE PAGE LAYOUT
+ ************************************************************************/
+
+/* Each index references a group of bytes on the page. */
+#define	B_KEYDATA	1	/* Key/data item. */
+#define	B_DUPLICATE	2	/* Duplicate key/data item. */
+#define	B_OVERFLOW	3	/* Overflow key/data item. */
+
+/*
+ * The first type is B_KEYDATA, represented by the BKEYDATA structure:
+ *
+ *	+-----------------------------------+
+ *	|   length  |    type   | key/data  |
+ *	+-----------------------------------+
+ */
+typedef struct _bkeydata {
+	db_indx_t len;		/* 00-01: Key/data item length. */
+	u_int	  deleted :1;	/*    02: Page type and delete flag. */
+	u_int	  type	  :7;
+	u_int8_t  data[1];	/* Variable length key/data item. */
+} BKEYDATA;
+
+/* Get a BKEYDATA item for a specific index. */
+#define	GET_BKEYDATA(pg, indx)						\
+	((BKEYDATA *)P_ENTRY(pg, indx))
+
+/*
+ * Page space required to add a new BKEYDATA item to the page, with and
+ * without the index value.
+ */
+#define	BKEYDATA_SIZE(len)						\
+	ALIGN((len) + SSZA(BKEYDATA, data), 4)
+#define	BKEYDATA_PSIZE(len)						\
+	(BKEYDATA_SIZE(len) + sizeof(db_indx_t))
+
+/*
+ * The second and third types are B_DUPLICATE and B_OVERFLOW, represented
+ * by the BOVERFLOW structure:
+ *
+ *	+-----------------------------------+
+ *	| total len |    type   |   unused  |
+ *	+-----------------------------------+
+ *	| nxt: page |  nxt: off | nxt: len  |
+ *	+-----------------------------------+
+ */
+typedef struct _boverflow {
+	db_indx_t unused1;	/* 00-01: Padding, unused. */
+	u_int     deleted :1;	/*    02: Page type and delete flag. */
+	u_int     type	  :7;
+	u_int8_t  unused2;	/*    03: Padding, unused. */
+	db_pgno_t pgno;		/* 04-07: Next page number. */
+	u_int32_t tlen;		/* 08-11: Total length of item. */
+} BOVERFLOW;
+
+/* Get a BOVERFLOW item for a specific index. */
+#define	GET_BOVERFLOW(pg, indx)						\
+	((BOVERFLOW *)P_ENTRY(pg, indx))
+
+/*
+ * Page space required to add a new BOVERFLOW item to the page, with and
+ * without the index value.
+ */
+#define	BOVERFLOW_SIZE							\
+	ALIGN(sizeof(BOVERFLOW), 4)
+#define	BOVERFLOW_PSIZE							\
+	(BOVERFLOW_SIZE + sizeof(db_indx_t))
+
+/*
+ * Btree leaf and hash page layouts group indices in sets of two, one
+ * for the key and one for the data.  Everything else does it in sets
+ * of one to save space.  I use the following macros so that it's real
+ * obvious what's going on...
+ */
+#define	O_INDX	1
+#define	P_INDX	2
+
+/************************************************************************
+ BTREE INTERNAL PAGE LAYOUT
+ ************************************************************************/
+
+/*
+ * Btree internal entry.
+ *
+ *	+-----------------------------------+
+ *	| leaf pgno |   type    | data ...  |
+ *	+-----------------------------------+
+ */
+typedef struct _binternal {
+	db_indx_t len;		/* 00-01: Key/data item length. */
+	u_int      deleted :1;	/*    02: Page type and delete flag. */
+	u_int      type	  :7;
+	u_int8_t   unused;	/*    03: Padding, unused. */
+	db_pgno_t  pgno;	/* 04-07: Page number of referenced page. */
+	db_recno_t nrecs;	/* 08-11: Subtree record count. */
+	u_int8_t   data[1];	/* Variable length key item. */
+} BINTERNAL;
+
+/* Get a BINTERNAL item for a specific index. */
+#define	GET_BINTERNAL(pg, indx)						\
+	((BINTERNAL *)P_ENTRY(pg, indx))
+
+/*
+ * Page space required to add a new BINTERNAL item to the page, with and
+ * without the index value.
+ */
+#define	BINTERNAL_SIZE(len)						\
+	ALIGN((len) + SSZA(BINTERNAL, data), 4)
+#define	BINTERNAL_PSIZE(len)						\
+	(BINTERNAL_SIZE(len) + sizeof(db_indx_t))
+
+/************************************************************************
+ RECNO INTERNAL PAGE LAYOUT
+ ************************************************************************/
+
+/*
+ * The recno internal entry.
+ *
+ *	+-----------------------+
+ *	| leaf pgno | # of recs |
+ *	+-----------------------+
+ *
+ * XXX
+ * Why not fold this into the db_indx_t structure, it's fixed length.
+ */
+typedef struct _rinternal {
+	db_pgno_t  pgno;	/* 00-03: Page number of referenced page. */
+	db_recno_t nrecs;	/* 04-07: Subtree record count. */
+} RINTERNAL;
+
+/* Get a RINTERNAL item for a specific index. */
+#define	GET_RINTERNAL(pg, indx)						\
+	((RINTERNAL *)P_ENTRY(pg, indx))
+
+/*
+ * Page space required to add a new RINTERNAL item to the page, with and
+ * without the index value.
+ */
+#define	RINTERNAL_SIZE							\
+	ALIGN(sizeof(RINTERNAL), 4)
+#define	RINTERNAL_PSIZE							\
+	(RINTERNAL_SIZE + sizeof(db_indx_t))
+#endif /* _DB_PAGE_H_ */