1/*-
2 * Copyright (c) 1990, 1993, 1994
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Margo Seltzer.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 4. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 *	@(#)hash.h	8.3 (Berkeley) 5/31/94
33 * $FreeBSD$
34 */
35
36/* Operations */
37typedef enum {
38	HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
39} ACTION;
40
41/* Buffer Management structures */
42typedef struct _bufhead BUFHEAD;
43
44struct _bufhead {
45	BUFHEAD		*prev;		/* LRU links */
46	BUFHEAD		*next;		/* LRU links */
47	BUFHEAD		*ovfl;		/* Overflow page buffer header */
48	u_int32_t	 addr;		/* Address of this page */
49	char		*page;		/* Actual page data */
50	char	 	flags;
51#define	BUF_MOD		0x0001
52#define BUF_DISK	0x0002
53#define	BUF_BUCKET	0x0004
54#define	BUF_PIN		0x0008
55};
56
57#define IS_BUCKET(X)	((X) & BUF_BUCKET)
58
59typedef BUFHEAD **SEGMENT;
60
61/* Hash Table Information */
62typedef struct hashhdr {		/* Disk resident portion */
63	int32_t		magic;		/* Magic NO for hash tables */
64	int32_t		version;	/* Version ID */
65	u_int32_t	lorder;		/* Byte Order */
66	int32_t		bsize;		/* Bucket/Page Size */
67	int32_t		bshift;		/* Bucket shift */
68	int32_t		dsize;		/* Directory Size */
69	int32_t		ssize;		/* Segment Size */
70	int32_t		sshift;		/* Segment shift */
71	int32_t		ovfl_point;	/* Where overflow pages are being
72					 * allocated */
73	int32_t		last_freed;	/* Last overflow page freed */
74	u_int32_t	max_bucket;	/* ID of Maximum bucket in use */
75	u_int32_t	high_mask;	/* Mask to modulo into entire table */
76	u_int32_t	low_mask;	/* Mask to modulo into lower half of
77					 * table */
78	u_int32_t	ffactor;	/* Fill factor */
79	int32_t		nkeys;		/* Number of keys in hash table */
80	int32_t		hdrpages;	/* Size of table header */
81	int32_t		h_charkey;	/* value of hash(CHARKEY) */
82#define NCACHED	32			/* number of bit maps and spare
83					 * points */
84	int32_t		spares[NCACHED];/* spare pages for overflow */
85	u_int16_t	bitmaps[NCACHED];	/* address of overflow page
86						 * bitmaps */
87} HASHHDR;
88
89typedef struct htab	 {		/* Memory resident data structure */
90	HASHHDR 	hdr;		/* Header */
91	int		nsegs;		/* Number of allocated segments */
92	int		exsegs;		/* Number of extra allocated
93					 * segments */
94	u_int32_t			/* Hash function */
95	    (*hash)(const void *, size_t);
96	int		flags;		/* Flag values */
97	int		fp;		/* File pointer */
98	char		*tmp_buf;	/* Temporary Buffer for BIG data */
99	char		*tmp_key;	/* Temporary Buffer for BIG keys */
100	BUFHEAD 	*cpage;		/* Current page */
101	int		cbucket;	/* Current bucket */
102	int		cndx;		/* Index of next item on cpage */
103	int		error;		/* Error Number -- for DBM
104					 * compatibility */
105	int		new_file;	/* Indicates if fd is backing store
106					 * or no */
107	int		save_file;	/* Indicates whether we need to flush
108					 * file at
109					 * exit */
110	u_int32_t	*mapp[NCACHED];	/* Pointers to page maps */
111	int		nmaps;		/* Initial number of bitmaps */
112	int		nbufs;		/* Number of buffers left to
113					 * allocate */
114	BUFHEAD 	bufhead;	/* Header of buffer lru list */
115	SEGMENT 	*dir;		/* Hash Bucket directory */
116} HTAB;
117
118/*
119 * Constants
120 */
121#define	MAX_BSIZE		32768		/* 2^15 but should be 65536 */
122#define MIN_BUFFERS		6
123#define MINHDRSIZE		512
124#define DEF_BUFSIZE		65536		/* 64 K */
125#define DEF_BUCKET_SIZE		4096
126#define DEF_BUCKET_SHIFT	12		/* log2(BUCKET) */
127#define DEF_SEGSIZE		256
128#define DEF_SEGSIZE_SHIFT	8		/* log2(SEGSIZE)	 */
129#define DEF_DIRSIZE		256
130#define DEF_FFACTOR		65536
131#define MIN_FFACTOR		4
132#define SPLTMAX			8
133#define CHARKEY			"%$sniglet^&"
134#define NUMKEY			1038583
135#define BYTE_SHIFT		3
136#define INT_TO_BYTE		2
137#define INT_BYTE_SHIFT		5
138#define ALL_SET			((u_int32_t)0xFFFFFFFF)
139#define ALL_CLEAR		0
140
141#define PTROF(X)	((BUFHEAD *)((ptrdiff_t)(X)&~0x3))
142#define ISMOD(X)	((u_int32_t)(ptrdiff_t)(X)&0x1)
143#define DOMOD(X)	((X) = (char *)((ptrdiff_t)(X)|0x1))
144#define ISDISK(X)	((u_int32_t)(ptrdiff_t)(X)&0x2)
145#define DODISK(X)	((X) = (char *)((ptrdiff_t)(X)|0x2))
146
147#define BITS_PER_MAP	32
148
149/* Given the address of the beginning of a big map, clear/set the nth bit */
150#define CLRBIT(A, N)	((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
151#define SETBIT(A, N)	((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
152#define ISSET(A, N)	((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
153
154/* Overflow management */
155/*
156 * Overflow page numbers are allocated per split point.  At each doubling of
157 * the table, we can allocate extra pages.  So, an overflow page number has
158 * the top 5 bits indicate which split point and the lower 11 bits indicate
159 * which page at that split point is indicated (pages within split points are
160 * numberered starting with 1).
161 */
162
163#define SPLITSHIFT	11
164#define SPLITMASK	0x7FF
165#define SPLITNUM(N)	(((u_int32_t)(N)) >> SPLITSHIFT)
166#define OPAGENUM(N)	((N) & SPLITMASK)
167#define	OADDR_OF(S,O)	((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))
168
169#define BUCKET_TO_PAGE(B) \
170	(B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0)
171#define OADDR_TO_PAGE(B) 	\
172	BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
173
174/*
175 * page.h contains a detailed description of the page format.
176 *
177 * Normally, keys and data are accessed from offset tables in the top of
178 * each page which point to the beginning of the key and data.  There are
179 * four flag values which may be stored in these offset tables which indicate
180 * the following:
181 *
182 *
183 * OVFLPAGE	Rather than a key data pair, this pair contains
184 *		the address of an overflow page.  The format of
185 *		the pair is:
186 *		    OVERFLOW_PAGE_NUMBER OVFLPAGE
187 *
188 * PARTIAL_KEY	This must be the first key/data pair on a page
189 *		and implies that page contains only a partial key.
190 *		That is, the key is too big to fit on a single page
191 *		so it starts on this page and continues on the next.
192 *		The format of the page is:
193 *		    KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
194 *
195 *		    KEY_OFF -- offset of the beginning of the key
196 *		    PARTIAL_KEY -- 1
197 *		    OVFL_PAGENO - page number of the next overflow page
198 *		    OVFLPAGE -- 0
199 *
200 * FULL_KEY	This must be the first key/data pair on the page.  It
201 *		is used in two cases.
202 *
203 *		Case 1:
204 *		    There is a complete key on the page but no data
205 *		    (because it wouldn't fit).  The next page contains
206 *		    the data.
207 *
208 *		    Page format it:
209 *		    KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
210 *
211 *		    KEY_OFF -- offset of the beginning of the key
212 *		    FULL_KEY -- 2
213 *		    OVFL_PAGENO - page number of the next overflow page
214 *		    OVFLPAGE -- 0
215 *
216 *		Case 2:
217 *		    This page contains no key, but part of a large
218 *		    data field, which is continued on the next page.
219 *
220 *		    Page format it:
221 *		    DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
222 *
223 *		    KEY_OFF -- offset of the beginning of the data on
224 *				this page
225 *		    FULL_KEY -- 2
226 *		    OVFL_PAGENO - page number of the next overflow page
227 *		    OVFLPAGE -- 0
228 *
229 * FULL_KEY_DATA
230 *		This must be the first key/data pair on the page.
231 *		There are two cases:
232 *
233 *		Case 1:
234 *		    This page contains a key and the beginning of the
235 *		    data field, but the data field is continued on the
236 *		    next page.
237 *
238 *		    Page format is:
239 *		    KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
240 *
241 *		    KEY_OFF -- offset of the beginning of the key
242 *		    FULL_KEY_DATA -- 3
243 *		    OVFL_PAGENO - page number of the next overflow page
244 *		    DATA_OFF -- offset of the beginning of the data
245 *
246 *		Case 2:
247 *		    This page contains the last page of a big data pair.
248 *		    There is no key, only the  tail end of the data
249 *		    on this page.
250 *
251 *		    Page format is:
252 *		    DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
253 *
254 *		    DATA_OFF -- offset of the beginning of the data on
255 *				this page
256 *		    FULL_KEY_DATA -- 3
257 *		    OVFL_PAGENO - page number of the next overflow page
258 *		    OVFLPAGE -- 0
259 *
260 *		    OVFL_PAGENO and OVFLPAGE are optional (they are
261 *		    not present if there is no next page).
262 */
263
264#define OVFLPAGE	0
265#define PARTIAL_KEY	1
266#define FULL_KEY	2
267#define FULL_KEY_DATA	3
268#define	REAL_KEY	4
269
270/* Short hands for accessing structure */
271#define BSIZE		hdr.bsize
272#define BSHIFT		hdr.bshift
273#define DSIZE		hdr.dsize
274#define SGSIZE		hdr.ssize
275#define SSHIFT		hdr.sshift
276#define LORDER		hdr.lorder
277#define OVFL_POINT	hdr.ovfl_point
278#define	LAST_FREED	hdr.last_freed
279#define MAX_BUCKET	hdr.max_bucket
280#define FFACTOR		hdr.ffactor
281#define HIGH_MASK	hdr.high_mask
282#define LOW_MASK	hdr.low_mask
283#define NKEYS		hdr.nkeys
284#define HDRPAGES	hdr.hdrpages
285#define SPARES		hdr.spares
286#define BITMAPS		hdr.bitmaps
287#define VERSION		hdr.version
288#define MAGIC		hdr.magic
289#define NEXT_FREE	hdr.next_free
290#define H_CHARKEY	hdr.h_charkey
291