11573Srgrimes/*-
214287Spst * Copyright (c) 1990, 1993, 1994
31573Srgrimes *	The Regents of the University of California.  All rights reserved.
41573Srgrimes *
51573Srgrimes * This code is derived from software contributed to Berkeley by
61573Srgrimes * Margo Seltzer.
71573Srgrimes *
81573Srgrimes * Redistribution and use in source and binary forms, with or without
91573Srgrimes * modification, are permitted provided that the following conditions
101573Srgrimes * are met:
111573Srgrimes * 1. Redistributions of source code must retain the above copyright
121573Srgrimes *    notice, this list of conditions and the following disclaimer.
131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright
141573Srgrimes *    notice, this list of conditions and the following disclaimer in the
151573Srgrimes *    documentation and/or other materials provided with the distribution.
161573Srgrimes * 4. Neither the name of the University nor the names of its contributors
171573Srgrimes *    may be used to endorse or promote products derived from this software
181573Srgrimes *    without specific prior written permission.
191573Srgrimes *
201573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
211573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
221573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
231573Srgrimes * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
241573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
251573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
261573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
271573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
281573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
291573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
301573Srgrimes * SUCH DAMAGE.
311573Srgrimes *
3214287Spst *	@(#)hash.h	8.3 (Berkeley) 5/31/94
3372092Sasmodai * $FreeBSD$
341573Srgrimes */
351573Srgrimes
361573Srgrimes/* Operations */
371573Srgrimestypedef enum {
381573Srgrimes	HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
391573Srgrimes} ACTION;
401573Srgrimes
411573Srgrimes/* Buffer Management structures */
421573Srgrimestypedef struct _bufhead BUFHEAD;
431573Srgrimes
441573Srgrimesstruct _bufhead {
4514287Spst	BUFHEAD		*prev;		/* LRU links */
4614287Spst	BUFHEAD		*next;		/* LRU links */
4714287Spst	BUFHEAD		*ovfl;		/* Overflow page buffer header */
4814287Spst	u_int32_t	 addr;		/* Address of this page */
4914287Spst	char		*page;		/* Actual page data */
5014287Spst	char	 	flags;
511573Srgrimes#define	BUF_MOD		0x0001
521573Srgrimes#define BUF_DISK	0x0002
531573Srgrimes#define	BUF_BUCKET	0x0004
541573Srgrimes#define	BUF_PIN		0x0008
551573Srgrimes};
561573Srgrimes
571573Srgrimes#define IS_BUCKET(X)	((X) & BUF_BUCKET)
581573Srgrimes
591573Srgrimestypedef BUFHEAD **SEGMENT;
601573Srgrimes
611573Srgrimes/* Hash Table Information */
6214287Spsttypedef struct hashhdr {		/* Disk resident portion */
63189330Sdelphij	int32_t		magic;		/* Magic NO for hash tables */
64189330Sdelphij	int32_t		version;	/* Version ID */
6514287Spst	u_int32_t	lorder;		/* Byte Order */
66189330Sdelphij	int32_t		bsize;		/* Bucket/Page Size */
67189330Sdelphij	int32_t		bshift;		/* Bucket shift */
68189330Sdelphij	int32_t		dsize;		/* Directory Size */
69189330Sdelphij	int32_t		ssize;		/* Segment Size */
70189330Sdelphij	int32_t		sshift;		/* Segment shift */
71189330Sdelphij	int32_t		ovfl_point;	/* Where overflow pages are being
7214287Spst					 * allocated */
73189330Sdelphij	int32_t		last_freed;	/* Last overflow page freed */
74190484Sdelphij	u_int32_t	max_bucket;	/* ID of Maximum bucket in use */
75190484Sdelphij	u_int32_t	high_mask;	/* Mask to modulo into entire table */
76190484Sdelphij	u_int32_t	low_mask;	/* Mask to modulo into lower half of
7714287Spst					 * table */
78190484Sdelphij	u_int32_t	ffactor;	/* Fill factor */
79189330Sdelphij	int32_t		nkeys;		/* Number of keys in hash table */
80189330Sdelphij	int32_t		hdrpages;	/* Size of table header */
81189330Sdelphij	int32_t		h_charkey;	/* value of hash(CHARKEY) */
8214287Spst#define NCACHED	32			/* number of bit maps and spare
8314287Spst					 * points */
84189330Sdelphij	int32_t		spares[NCACHED];/* spare pages for overflow */
8514287Spst	u_int16_t	bitmaps[NCACHED];	/* address of overflow page
8614287Spst						 * bitmaps */
871573Srgrimes} HASHHDR;
881573Srgrimes
8914287Spsttypedef struct htab	 {		/* Memory resident data structure */
9014287Spst	HASHHDR 	hdr;		/* Header */
9114287Spst	int		nsegs;		/* Number of allocated segments */
9214287Spst	int		exsegs;		/* Number of extra allocated
9314287Spst					 * segments */
9414287Spst	u_int32_t			/* Hash function */
9592905Sobrien	    (*hash)(const void *, size_t);
9614287Spst	int		flags;		/* Flag values */
9714287Spst	int		fp;		/* File pointer */
9814287Spst	char		*tmp_buf;	/* Temporary Buffer for BIG data */
9914287Spst	char		*tmp_key;	/* Temporary Buffer for BIG keys */
10014287Spst	BUFHEAD 	*cpage;		/* Current page */
10114287Spst	int		cbucket;	/* Current bucket */
10214287Spst	int		cndx;		/* Index of next item on cpage */
10314287Spst	int		error;		/* Error Number -- for DBM
10472092Sasmodai					 * compatibility */
10514287Spst	int		new_file;	/* Indicates if fd is backing store
10614287Spst					 * or no */
10714287Spst	int		save_file;	/* Indicates whether we need to flush
10814287Spst					 * file at
10914287Spst					 * exit */
11014287Spst	u_int32_t	*mapp[NCACHED];	/* Pointers to page maps */
11114287Spst	int		nmaps;		/* Initial number of bitmaps */
11214287Spst	int		nbufs;		/* Number of buffers left to
11314287Spst					 * allocate */
11414287Spst	BUFHEAD 	bufhead;	/* Header of buffer lru list */
11514287Spst	SEGMENT 	*dir;		/* Hash Bucket directory */
1161573Srgrimes} HTAB;
1171573Srgrimes
1181573Srgrimes/*
1191573Srgrimes * Constants
1201573Srgrimes */
121206178Savg#define	MAX_BSIZE		32768		/* 2^15 but should be 65536 */
1221573Srgrimes#define MIN_BUFFERS		6
1231573Srgrimes#define MINHDRSIZE		512
1241573Srgrimes#define DEF_BUFSIZE		65536		/* 64 K */
1251573Srgrimes#define DEF_BUCKET_SIZE		4096
1261573Srgrimes#define DEF_BUCKET_SHIFT	12		/* log2(BUCKET) */
1271573Srgrimes#define DEF_SEGSIZE		256
1281573Srgrimes#define DEF_SEGSIZE_SHIFT	8		/* log2(SEGSIZE)	 */
1291573Srgrimes#define DEF_DIRSIZE		256
1301573Srgrimes#define DEF_FFACTOR		65536
1311573Srgrimes#define MIN_FFACTOR		4
1321573Srgrimes#define SPLTMAX			8
1331573Srgrimes#define CHARKEY			"%$sniglet^&"
1341573Srgrimes#define NUMKEY			1038583
1351573Srgrimes#define BYTE_SHIFT		3
1361573Srgrimes#define INT_TO_BYTE		2
1371573Srgrimes#define INT_BYTE_SHIFT		5
13814287Spst#define ALL_SET			((u_int32_t)0xFFFFFFFF)
1391573Srgrimes#define ALL_CLEAR		0
1401573Srgrimes
14114287Spst#define PTROF(X)	((BUFHEAD *)((ptrdiff_t)(X)&~0x3))
14214287Spst#define ISMOD(X)	((u_int32_t)(ptrdiff_t)(X)&0x1)
14314287Spst#define DOMOD(X)	((X) = (char *)((ptrdiff_t)(X)|0x1))
14414287Spst#define ISDISK(X)	((u_int32_t)(ptrdiff_t)(X)&0x2)
14514287Spst#define DODISK(X)	((X) = (char *)((ptrdiff_t)(X)|0x2))
1461573Srgrimes
1471573Srgrimes#define BITS_PER_MAP	32
1481573Srgrimes
1491573Srgrimes/* Given the address of the beginning of a big map, clear/set the nth bit */
1501573Srgrimes#define CLRBIT(A, N)	((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
1511573Srgrimes#define SETBIT(A, N)	((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
1521573Srgrimes#define ISSET(A, N)	((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
1531573Srgrimes
1541573Srgrimes/* Overflow management */
1551573Srgrimes/*
1561573Srgrimes * Overflow page numbers are allocated per split point.  At each doubling of
1571573Srgrimes * the table, we can allocate extra pages.  So, an overflow page number has
1581573Srgrimes * the top 5 bits indicate which split point and the lower 11 bits indicate
1591573Srgrimes * which page at that split point is indicated (pages within split points are
1601573Srgrimes * numberered starting with 1).
1611573Srgrimes */
1621573Srgrimes
1631573Srgrimes#define SPLITSHIFT	11
1641573Srgrimes#define SPLITMASK	0x7FF
16514287Spst#define SPLITNUM(N)	(((u_int32_t)(N)) >> SPLITSHIFT)
1661573Srgrimes#define OPAGENUM(N)	((N) & SPLITMASK)
16714287Spst#define	OADDR_OF(S,O)	((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))
1681573Srgrimes
1691573Srgrimes#define BUCKET_TO_PAGE(B) \
1701573Srgrimes	(B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0)
1711573Srgrimes#define OADDR_TO_PAGE(B) 	\
1721573Srgrimes	BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
1731573Srgrimes
1741573Srgrimes/*
1751573Srgrimes * page.h contains a detailed description of the page format.
1761573Srgrimes *
1771573Srgrimes * Normally, keys and data are accessed from offset tables in the top of
1781573Srgrimes * each page which point to the beginning of the key and data.  There are
1791573Srgrimes * four flag values which may be stored in these offset tables which indicate
1801573Srgrimes * the following:
1811573Srgrimes *
1821573Srgrimes *
1831573Srgrimes * OVFLPAGE	Rather than a key data pair, this pair contains
1841573Srgrimes *		the address of an overflow page.  The format of
1851573Srgrimes *		the pair is:
1861573Srgrimes *		    OVERFLOW_PAGE_NUMBER OVFLPAGE
1871573Srgrimes *
1881573Srgrimes * PARTIAL_KEY	This must be the first key/data pair on a page
1891573Srgrimes *		and implies that page contains only a partial key.
1901573Srgrimes *		That is, the key is too big to fit on a single page
1911573Srgrimes *		so it starts on this page and continues on the next.
1921573Srgrimes *		The format of the page is:
1931573Srgrimes *		    KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
1948870Srgrimes *
1951573Srgrimes *		    KEY_OFF -- offset of the beginning of the key
1961573Srgrimes *		    PARTIAL_KEY -- 1
1971573Srgrimes *		    OVFL_PAGENO - page number of the next overflow page
1981573Srgrimes *		    OVFLPAGE -- 0
1991573Srgrimes *
2001573Srgrimes * FULL_KEY	This must be the first key/data pair on the page.  It
2011573Srgrimes *		is used in two cases.
2021573Srgrimes *
2031573Srgrimes *		Case 1:
2041573Srgrimes *		    There is a complete key on the page but no data
2051573Srgrimes *		    (because it wouldn't fit).  The next page contains
2061573Srgrimes *		    the data.
2071573Srgrimes *
2081573Srgrimes *		    Page format it:
2091573Srgrimes *		    KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
2101573Srgrimes *
2111573Srgrimes *		    KEY_OFF -- offset of the beginning of the key
2121573Srgrimes *		    FULL_KEY -- 2
2131573Srgrimes *		    OVFL_PAGENO - page number of the next overflow page
2141573Srgrimes *		    OVFLPAGE -- 0
2151573Srgrimes *
2161573Srgrimes *		Case 2:
2171573Srgrimes *		    This page contains no key, but part of a large
2181573Srgrimes *		    data field, which is continued on the next page.
2191573Srgrimes *
2201573Srgrimes *		    Page format it:
2211573Srgrimes *		    DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
2221573Srgrimes *
2231573Srgrimes *		    KEY_OFF -- offset of the beginning of the data on
2241573Srgrimes *				this page
2251573Srgrimes *		    FULL_KEY -- 2
2261573Srgrimes *		    OVFL_PAGENO - page number of the next overflow page
2271573Srgrimes *		    OVFLPAGE -- 0
2281573Srgrimes *
2298870Srgrimes * FULL_KEY_DATA
2301573Srgrimes *		This must be the first key/data pair on the page.
2311573Srgrimes *		There are two cases:
2321573Srgrimes *
2331573Srgrimes *		Case 1:
2341573Srgrimes *		    This page contains a key and the beginning of the
2351573Srgrimes *		    data field, but the data field is continued on the
2361573Srgrimes *		    next page.
2371573Srgrimes *
2381573Srgrimes *		    Page format is:
2391573Srgrimes *		    KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
2401573Srgrimes *
2411573Srgrimes *		    KEY_OFF -- offset of the beginning of the key
2421573Srgrimes *		    FULL_KEY_DATA -- 3
2431573Srgrimes *		    OVFL_PAGENO - page number of the next overflow page
2441573Srgrimes *		    DATA_OFF -- offset of the beginning of the data
2451573Srgrimes *
2461573Srgrimes *		Case 2:
2471573Srgrimes *		    This page contains the last page of a big data pair.
2481573Srgrimes *		    There is no key, only the  tail end of the data
2491573Srgrimes *		    on this page.
2501573Srgrimes *
2511573Srgrimes *		    Page format is:
2521573Srgrimes *		    DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
2531573Srgrimes *
2541573Srgrimes *		    DATA_OFF -- offset of the beginning of the data on
2551573Srgrimes *				this page
2561573Srgrimes *		    FULL_KEY_DATA -- 3
2571573Srgrimes *		    OVFL_PAGENO - page number of the next overflow page
2581573Srgrimes *		    OVFLPAGE -- 0
2591573Srgrimes *
2601573Srgrimes *		    OVFL_PAGENO and OVFLPAGE are optional (they are
2611573Srgrimes *		    not present if there is no next page).
2621573Srgrimes */
2631573Srgrimes
2641573Srgrimes#define OVFLPAGE	0
2651573Srgrimes#define PARTIAL_KEY	1
2661573Srgrimes#define FULL_KEY	2
2671573Srgrimes#define FULL_KEY_DATA	3
2681573Srgrimes#define	REAL_KEY	4
2691573Srgrimes
2701573Srgrimes/* Short hands for accessing structure */
2711573Srgrimes#define BSIZE		hdr.bsize
2721573Srgrimes#define BSHIFT		hdr.bshift
2731573Srgrimes#define DSIZE		hdr.dsize
2741573Srgrimes#define SGSIZE		hdr.ssize
2751573Srgrimes#define SSHIFT		hdr.sshift
2761573Srgrimes#define LORDER		hdr.lorder
2771573Srgrimes#define OVFL_POINT	hdr.ovfl_point
2781573Srgrimes#define	LAST_FREED	hdr.last_freed
2791573Srgrimes#define MAX_BUCKET	hdr.max_bucket
2801573Srgrimes#define FFACTOR		hdr.ffactor
2811573Srgrimes#define HIGH_MASK	hdr.high_mask
2821573Srgrimes#define LOW_MASK	hdr.low_mask
2831573Srgrimes#define NKEYS		hdr.nkeys
2841573Srgrimes#define HDRPAGES	hdr.hdrpages
2851573Srgrimes#define SPARES		hdr.spares
2861573Srgrimes#define BITMAPS		hdr.bitmaps
2871573Srgrimes#define VERSION		hdr.version
2881573Srgrimes#define MAGIC		hdr.magic
2891573Srgrimes#define NEXT_FREE	hdr.next_free
2901573Srgrimes#define H_CHARKEY	hdr.h_charkey
291