Mercurial > trustbridge > nss-cmake-static
comparison nss/lib/dbm/include/hash.h @ 3:150b72113545
Add DBM and legacydb support
author | Andre Heinecke <andre.heinecke@intevation.de> |
---|---|
date | Tue, 05 Aug 2014 18:32:02 +0200 (2014-08-05) |
parents | |
children | b513267f632f |
comparison
equal
deleted
inserted
replaced
2:a945361df361 | 3:150b72113545 |
---|---|
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 * 3. ***REMOVED*** - see | |
17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change | |
18 * 4. Neither the name of the University nor the names of its contributors | |
19 * may be used to endorse or promote products derived from this software | |
20 * without specific prior written permission. | |
21 * | |
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
32 * SUCH DAMAGE. | |
33 * | |
34 * @(#)hash.h 8.3 (Berkeley) 5/31/94 | |
35 */ | |
36 | |
37 /* Operations */ | |
38 | |
39 #include <stdio.h> | |
40 #include "mcom_db.h" | |
41 typedef enum { | |
42 HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT | |
43 } ACTION; | |
44 | |
45 /* Buffer Management structures */ | |
46 typedef struct _bufhead BUFHEAD; | |
47 | |
48 struct _bufhead { | |
49 BUFHEAD *prev; /* LRU links */ | |
50 BUFHEAD *next; /* LRU links */ | |
51 BUFHEAD *ovfl; /* Overflow page buffer header */ | |
52 uint32 addr; /* Address of this page */ | |
53 char *page; /* Actual page data */ | |
54 char is_disk; | |
55 char flags; | |
56 #define BUF_MOD 0x0001 | |
57 #define BUF_DISK 0x0002 | |
58 #define BUF_BUCKET 0x0004 | |
59 #define BUF_PIN 0x0008 | |
60 }; | |
61 | |
62 #define IS_BUCKET(X) ((X) & BUF_BUCKET) | |
63 | |
64 typedef BUFHEAD **SEGMENT; | |
65 | |
66 typedef int DBFILE_PTR; | |
67 #define NO_FILE -1 | |
68 #ifdef macintosh | |
69 #define DBFILE_OPEN(path, flag,mode) open((path), flag) | |
70 #define EXISTS(path) | |
71 #else | |
72 #define DBFILE_OPEN(path, flag,mode) open((path), (flag), (mode)) | |
73 #endif | |
74 /* Hash Table Information */ | |
75 typedef struct hashhdr { /* Disk resident portion */ | |
76 int32 magic; /* Magic NO for hash tables */ | |
77 int32 version; /* Version ID */ | |
78 uint32 lorder; /* Byte Order */ | |
79 int32 bsize; /* Bucket/Page Size */ | |
80 int32 bshift; /* Bucket shift */ | |
81 int32 dsize; /* Directory Size */ | |
82 int32 ssize; /* Segment Size */ | |
83 int32 sshift; /* Segment shift */ | |
84 int32 ovfl_point; /* Where overflow pages are being | |
85 * allocated */ | |
86 int32 last_freed; /* Last overflow page freed */ | |
87 int32 max_bucket; /* ID of Maximum bucket in use */ | |
88 int32 high_mask; /* Mask to modulo into entire table */ | |
89 int32 low_mask; /* Mask to modulo into lower half of | |
90 * table */ | |
91 int32 ffactor; /* Fill factor */ | |
92 int32 nkeys; /* Number of keys in hash table */ | |
93 int32 hdrpages; /* Size of table header */ | |
94 uint32 h_charkey; /* value of hash(CHARKEY) */ | |
95 #define NCACHED 32 /* number of bit maps and spare | |
96 * points */ | |
97 int32 spares[NCACHED];/* spare pages for overflow */ | |
98 uint16 bitmaps[NCACHED]; /* address of overflow page | |
99 * bitmaps */ | |
100 } HASHHDR; | |
101 | |
102 typedef struct htab { /* Memory resident data structure */ | |
103 HASHHDR hdr; /* Header */ | |
104 int nsegs; /* Number of allocated segments */ | |
105 int exsegs; /* Number of extra allocated | |
106 * segments */ | |
107 uint32 /* Hash function */ | |
108 (*hash)(const void *, size_t); | |
109 int flags; /* Flag values */ | |
110 DBFILE_PTR fp; /* File pointer */ | |
111 char *filename; | |
112 char *tmp_buf; /* Temporary Buffer for BIG data */ | |
113 char *tmp_key; /* Temporary Buffer for BIG keys */ | |
114 BUFHEAD *cpage; /* Current page */ | |
115 int cbucket; /* Current bucket */ | |
116 int cndx; /* Index of next item on cpage */ | |
117 int dbmerrno; /* Error Number -- for DBM | |
118 * compatability */ | |
119 int new_file; /* Indicates if fd is backing store | |
120 * or no */ | |
121 int save_file; /* Indicates whether we need to flush | |
122 * file at | |
123 * exit */ | |
124 uint32 *mapp[NCACHED]; /* Pointers to page maps */ | |
125 int nmaps; /* Initial number of bitmaps */ | |
126 int nbufs; /* Number of buffers left to | |
127 * allocate */ | |
128 BUFHEAD bufhead; /* Header of buffer lru list */ | |
129 SEGMENT *dir; /* Hash Bucket directory */ | |
130 off_t file_size; /* in bytes */ | |
131 char is_temp; /* unlink file on close */ | |
132 char updateEOF; /* force EOF update on flush */ | |
133 } HTAB; | |
134 | |
135 /* | |
136 * Constants | |
137 */ | |
138 #define DATABASE_CORRUPTED_ERROR -999 /* big ugly abort, delete database */ | |
139 #define OLD_MAX_BSIZE 65536 /* 2^16 */ | |
140 #define MAX_BSIZE 32l*1024l /* 2^15 */ | |
141 #define MIN_BUFFERS 6 | |
142 #define MINHDRSIZE 512 | |
143 #define DEF_BUFSIZE 65536l /* 64 K */ | |
144 #define DEF_BUCKET_SIZE 4096 | |
145 #define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ | |
146 #define DEF_SEGSIZE 256 | |
147 #define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ | |
148 #define DEF_DIRSIZE 256 | |
149 #define DEF_FFACTOR 65536l | |
150 #define MIN_FFACTOR 4 | |
151 #define SPLTMAX 8 | |
152 #define CHARKEY "%$sniglet^&" | |
153 #define NUMKEY 1038583l | |
154 #define BYTE_SHIFT 3 | |
155 #define INT_TO_BYTE 2 | |
156 #define INT_BYTE_SHIFT 5 | |
157 #define ALL_SET ((uint32)0xFFFFFFFF) | |
158 #define ALL_CLEAR 0 | |
159 | |
160 #define PTROF(X) ((ptrdiff_t)(X) == BUF_DISK ? 0 : (X)) | |
161 #define ISDISK(X) ((X) ? ((ptrdiff_t)(X) == BUF_DISK ? BUF_DISK \ | |
162 : (X)->is_disk) : 0) | |
163 | |
164 #define BITS_PER_MAP 32 | |
165 | |
166 /* Given the address of the beginning of a big map, clear/set the nth bit */ | |
167 #define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) | |
168 #define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) | |
169 #define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) | |
170 | |
171 /* Overflow management */ | |
172 /* | |
173 * Overflow page numbers are allocated per split point. At each doubling of | |
174 * the table, we can allocate extra pages. So, an overflow page number has | |
175 * the top 5 bits indicate which split point and the lower 11 bits indicate | |
176 * which page at that split point is indicated (pages within split points are | |
177 * numberered starting with 1). | |
178 */ | |
179 | |
180 #define SPLITSHIFT 11 | |
181 #define SPLITMASK 0x7FF | |
182 #define SPLITNUM(N) (((uint32)(N)) >> SPLITSHIFT) | |
183 #define OPAGENUM(N) ((N) & SPLITMASK) | |
184 #define OADDR_OF(S,O) ((uint32)((uint32)(S) << SPLITSHIFT) + (O)) | |
185 | |
186 #define BUCKET_TO_PAGE(B) \ | |
187 (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((uint32)((B)+1))-1] : 0) | |
188 #define OADDR_TO_PAGE(B) \ | |
189 BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B)); | |
190 | |
191 /* | |
192 * page.h contains a detailed description of the page format. | |
193 * | |
194 * Normally, keys and data are accessed from offset tables in the top of | |
195 * each page which point to the beginning of the key and data. There are | |
196 * four flag values which may be stored in these offset tables which indicate | |
197 * the following: | |
198 * | |
199 * | |
200 * OVFLPAGE Rather than a key data pair, this pair contains | |
201 * the address of an overflow page. The format of | |
202 * the pair is: | |
203 * OVERFLOW_PAGE_NUMBER OVFLPAGE | |
204 * | |
205 * PARTIAL_KEY This must be the first key/data pair on a page | |
206 * and implies that page contains only a partial key. | |
207 * That is, the key is too big to fit on a single page | |
208 * so it starts on this page and continues on the next. | |
209 * The format of the page is: | |
210 * KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE | |
211 * | |
212 * KEY_OFF -- offset of the beginning of the key | |
213 * PARTIAL_KEY -- 1 | |
214 * OVFL_PAGENO - page number of the next overflow page | |
215 * OVFLPAGE -- 0 | |
216 * | |
217 * FULL_KEY This must be the first key/data pair on the page. It | |
218 * is used in two cases. | |
219 * | |
220 * Case 1: | |
221 * There is a complete key on the page but no data | |
222 * (because it wouldn't fit). The next page contains | |
223 * the data. | |
224 * | |
225 * Page format it: | |
226 * KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE | |
227 * | |
228 * KEY_OFF -- offset of the beginning of the key | |
229 * FULL_KEY -- 2 | |
230 * OVFL_PAGENO - page number of the next overflow page | |
231 * OVFLPAGE -- 0 | |
232 * | |
233 * Case 2: | |
234 * This page contains no key, but part of a large | |
235 * data field, which is continued on the next page. | |
236 * | |
237 * Page format it: | |
238 * DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE | |
239 * | |
240 * KEY_OFF -- offset of the beginning of the data on | |
241 * this page | |
242 * FULL_KEY -- 2 | |
243 * OVFL_PAGENO - page number of the next overflow page | |
244 * OVFLPAGE -- 0 | |
245 * | |
246 * FULL_KEY_DATA | |
247 * This must be the first key/data pair on the page. | |
248 * There are two cases: | |
249 * | |
250 * Case 1: | |
251 * This page contains a key and the beginning of the | |
252 * data field, but the data field is continued on the | |
253 * next page. | |
254 * | |
255 * Page format is: | |
256 * KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF | |
257 * | |
258 * KEY_OFF -- offset of the beginning of the key | |
259 * FULL_KEY_DATA -- 3 | |
260 * OVFL_PAGENO - page number of the next overflow page | |
261 * DATA_OFF -- offset of the beginning of the data | |
262 * | |
263 * Case 2: | |
264 * This page contains the last page of a big data pair. | |
265 * There is no key, only the tail end of the data | |
266 * on this page. | |
267 * | |
268 * Page format is: | |
269 * DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE> | |
270 * | |
271 * DATA_OFF -- offset of the beginning of the data on | |
272 * this page | |
273 * FULL_KEY_DATA -- 3 | |
274 * OVFL_PAGENO - page number of the next overflow page | |
275 * OVFLPAGE -- 0 | |
276 * | |
277 * OVFL_PAGENO and OVFLPAGE are optional (they are | |
278 * not present if there is no next page). | |
279 */ | |
280 | |
281 #define OVFLPAGE 0 | |
282 #define PARTIAL_KEY 1 | |
283 #define FULL_KEY 2 | |
284 #define FULL_KEY_DATA 3 | |
285 #define REAL_KEY 4 | |
286 | |
287 /* Short hands for accessing structure */ | |
288 #undef BSIZE | |
289 #define BSIZE hdr.bsize | |
290 #undef BSHIFT | |
291 #define BSHIFT hdr.bshift | |
292 #define DSIZE hdr.dsize | |
293 #define SGSIZE hdr.ssize | |
294 #define SSHIFT hdr.sshift | |
295 #define LORDER hdr.lorder | |
296 #define OVFL_POINT hdr.ovfl_point | |
297 #define LAST_FREED hdr.last_freed | |
298 #define MAX_BUCKET hdr.max_bucket | |
299 #define FFACTOR hdr.ffactor | |
300 #define HIGH_MASK hdr.high_mask | |
301 #define LOW_MASK hdr.low_mask | |
302 #define NKEYS hdr.nkeys | |
303 #define HDRPAGES hdr.hdrpages | |
304 #define SPARES hdr.spares | |
305 #define BITMAPS hdr.bitmaps | |
306 #define VERSION hdr.version | |
307 #define MAGIC hdr.magic | |
308 #define NEXT_FREE hdr.next_free | |
309 #define H_CHARKEY hdr.h_charkey | |
310 | |
311 extern uint32 (*__default_hash) (const void *, size_t); | |
312 void __buf_init(HTAB *hashp, int32 nbytes); | |
313 int __big_delete(HTAB *hashp, BUFHEAD *bufp); | |
314 BUFHEAD * __get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage); | |
315 uint32 __call_hash(HTAB *hashp, char *k, size_t len); | |
316 #include "page.h" | |
317 extern int __big_split(HTAB *hashp, BUFHEAD *op,BUFHEAD *np, | |
318 BUFHEAD *big_keyp,uint32 addr,uint32 obucket, SPLIT_RETURN *ret); | |
319 void __free_ovflpage(HTAB *hashp, BUFHEAD *obufp); | |
320 BUFHEAD * __add_ovflpage(HTAB *hashp, BUFHEAD *bufp); | |
321 int __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val); | |
322 int __expand_table(HTAB *hashp); | |
323 uint32 __log2(uint32 num); | |
324 void __reclaim_buf(HTAB *hashp, BUFHEAD *bp); | |
325 int __get_page(HTAB *hashp, char * p, uint32 bucket, int is_bucket, int is_disk, int is_bitmap); | |
326 int __put_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_bitmap); | |
327 int __ibitmap(HTAB *hashp, int pnum, int nbits, int ndx); | |
328 int __buf_free(HTAB *hashp, int do_free, int to_disk); | |
329 int __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size); | |
330 uint16 __find_last_page(HTAB *hashp, BUFHEAD **bpp); | |
331 int __addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT * val); | |
332 int __big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current); | |
333 int __delpair(HTAB *hashp, BUFHEAD *bufp, int ndx); | |
334 int __big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set); | |
335 int __split_page(HTAB *hashp, uint32 obucket, uint32 nbucket); |