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