Commit | Line | Data |
---|---|---|
cb07bd68 KB |
1 | /*- |
2 | * Copyright (c) 1990 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * This code is derived from software contributed to Berkeley by | |
6 | * Margo Seltzer. | |
7 | * | |
8 | * %sccs.include.redist.c% | |
9 | */ | |
10 | ||
11 | #if defined(LIBC_SCCS) && !defined(lint) | |
e5278b07 | 12 | static char sccsid[] = "@(#)hash.c 5.24 (Berkeley) %G%"; |
cb07bd68 KB |
13 | #endif /* LIBC_SCCS and not lint */ |
14 | ||
15 | #include <sys/param.h> | |
cb07bd68 | 16 | #include <sys/stat.h> |
e5278b07 | 17 | |
fb91cf55 | 18 | #include <fcntl.h> |
cb07bd68 | 19 | #include <errno.h> |
6f0d4752 | 20 | #ifdef DEBUG |
cb07bd68 | 21 | #include <assert.h> |
6f0d4752 | 22 | #endif |
cb07bd68 | 23 | #include <db.h> |
4c56dde1 | 24 | #include <stdio.h> |
fb91cf55 KB |
25 | #include <stdlib.h> |
26 | #include <unistd.h> | |
cb07bd68 | 27 | #include <string.h> |
fb91cf55 | 28 | #include "hash.h" |
6f0d4752 KB |
29 | #include "page.h" |
30 | #include "extern.h" | |
31 | ||
32 | static int alloc_segs __P((int)); | |
33 | static int flush_meta __P((void)); | |
34 | static int hash_access __P((ACTION, DBT *, DBT *)); | |
35 | static int hash_close __P((DB *)); | |
36 | static int hash_delete __P((const DB *, const DBT *, u_int)); | |
eb9054a0 | 37 | static int hash_get __P((const DB *, const DBT *, DBT *, u_int)); |
6f0d4752 KB |
38 | static int hash_put __P((const DB *, const DBT *, const DBT *, u_int)); |
39 | static void *hash_realloc __P((SEGMENT **, int, int)); | |
40 | static int hash_seq __P((const DB *, DBT *, DBT *, u_int)); | |
41 | static int hash_sync __P((const DB *)); | |
42 | static int hdestroy __P((void)); | |
43 | static HTAB *init_hash __P((HASHINFO *)); | |
44 | static int init_htab __P((int)); | |
45 | #if BYTE_ORDER == LITTLE_ENDIAN | |
46 | static void swap_header __P((void)); | |
47 | static void swap_header_copy __P((HASHHDR *, HASHHDR *)); | |
48 | #endif | |
cb07bd68 | 49 | |
cb07bd68 | 50 | /* Fast arithmetic, relying on powers of 2, */ |
6f0d4752 | 51 | #define MOD(x, y) ((x) & ((y) - 1)) |
cb07bd68 | 52 | |
6f0d4752 | 53 | #define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; } |
cb07bd68 KB |
54 | |
55 | /* Return values */ | |
6f0d4752 KB |
56 | #define SUCCESS (0) |
57 | #define ERROR (-1) | |
58 | #define ABNORMAL (1) | |
cb07bd68 KB |
59 | |
60 | /* Local data */ | |
cb07bd68 KB |
61 | HTAB *hashp = NULL; |
62 | ||
63 | #ifdef HASH_STATISTICS | |
64 | long hash_accesses, hash_collisions, hash_expansions, hash_overflows; | |
65 | #endif | |
66 | ||
6f0d4752 | 67 | /************************** INTERFACE ROUTINES ***************************/ |
cb07bd68 KB |
68 | /* OPEN/CLOSE */ |
69 | ||
6f0d4752 | 70 | extern DB * |
e5610f74 | 71 | __hash_open(file, flags, mode, info) |
6f0d4752 KB |
72 | const char *file; |
73 | int flags, mode; | |
74 | const HASHINFO *info; /* Special directives for create */ | |
cb07bd68 | 75 | { |
6f0d4752 KB |
76 | struct stat statbuf; |
77 | DB *dbp; | |
78 | int bpages, hdrsize, new_table, nsegs, save_errno; | |
cb07bd68 | 79 | |
6f0d4752 KB |
80 | if (!(hashp = calloc(1, sizeof(HTAB)))) |
81 | return (NULL); | |
82 | hashp->fp = -1; | |
83 | /* | |
84 | * Select flags relevant to us. Even if user wants write only, we need | |
85 | * to be able to read the actual file, so we need to open it read/write. | |
86 | * But, the field in the hashp structure needs to be accurate so that | |
87 | * we can check accesses. | |
88 | */ | |
791aaeff KB |
89 | hashp->flags = flags = flags & (O_CREAT | O_EXCL | O_EXLOCK | |
90 | O_RDONLY | O_RDWR | O_SHLOCK | O_TRUNC | O_WRONLY); | |
6f0d4752 KB |
91 | if (flags & O_WRONLY) |
92 | flags = (flags & ~O_WRONLY) | O_RDWR; | |
93 | ||
94 | new_table = 0; | |
95 | if (!file || (flags & O_TRUNC) || | |
96 | (stat(file, &statbuf) && (errno == ENOENT))) { | |
97 | if (errno == ENOENT) | |
98 | errno = 0; /* Just in case someone looks at errno */ | |
99 | new_table = 1; | |
cb07bd68 | 100 | } |
6f0d4752 KB |
101 | if (file) { |
102 | if ((hashp->fp = open(file, flags, mode)) == -1) | |
103 | RETURN_ERROR(errno, error0); | |
104 | (void)fcntl(hashp->fp, F_SETFD, 1); | |
105 | } | |
106 | if (new_table) { | |
107 | if (!(hashp = init_hash((HASHINFO *)info))) | |
108 | RETURN_ERROR(errno, error1); | |
109 | } else { | |
110 | /* Table already exists */ | |
111 | if (info && info->hash) | |
112 | hashp->hash = info->hash; | |
113 | else | |
114 | hashp->hash = default_hash; | |
cb07bd68 | 115 | |
6f0d4752 | 116 | hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR)); |
cb07bd68 | 117 | #if BYTE_ORDER == LITTLE_ENDIAN |
6f0d4752 | 118 | swap_header(); |
cb07bd68 | 119 | #endif |
6f0d4752 KB |
120 | if (hdrsize == -1) |
121 | RETURN_ERROR(errno, error1); | |
122 | if (hdrsize != sizeof(HASHHDR)) | |
123 | RETURN_ERROR(EFTYPE, error1); | |
124 | /* Verify file type, versions and hash function */ | |
125 | if (hashp->MAGIC != HASHMAGIC) | |
126 | RETURN_ERROR(EFTYPE, error1); | |
c8526f36 | 127 | if (hashp->VERSION != HASHVERSION) |
6f0d4752 KB |
128 | RETURN_ERROR(EFTYPE, error1); |
129 | if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY) | |
130 | RETURN_ERROR(EFTYPE, error1); | |
eb9054a0 KB |
131 | /* |
132 | * Figure out how many segments we need. Max_Bucket is the | |
133 | * maximum bucket number, so the number of buckets is | |
134 | * max_bucket + 1. | |
135 | */ | |
136 | nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / | |
6f0d4752 KB |
137 | hashp->SGSIZE; |
138 | hashp->nsegs = 0; | |
139 | if (alloc_segs(nsegs)) | |
140 | /* | |
141 | * If alloc_segs fails, table will have been destroyed | |
142 | * and errno will have been set. | |
143 | */ | |
144 | return (NULL); | |
145 | /* Read in bitmaps */ | |
c8526f36 | 146 | bpages = (hashp->SPARES[hashp->OVFL_POINT] + |
6f0d4752 KB |
147 | (hashp->BSIZE << BYTE_SHIFT) - 1) >> |
148 | (hashp->BSHIFT + BYTE_SHIFT); | |
149 | ||
150 | hashp->nmaps = bpages; | |
eb9054a0 | 151 | (void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_long *)); |
cb07bd68 KB |
152 | } |
153 | ||
6f0d4752 KB |
154 | /* Initialize Buffer Manager */ |
155 | if (info && info->cachesize) | |
156 | __buf_init(info->cachesize); | |
157 | else | |
158 | __buf_init(DEF_BUFSIZE); | |
159 | ||
160 | hashp->new_file = new_table; | |
161 | hashp->save_file = file && (hashp->flags & (O_WRONLY | O_RDWR)); | |
162 | hashp->cbucket = -1; | |
163 | if (!(dbp = malloc(sizeof(DB)))) { | |
164 | save_errno = errno; | |
165 | hdestroy(); | |
166 | errno = save_errno; | |
167 | return (NULL); | |
cb07bd68 | 168 | } |
6f0d4752 KB |
169 | dbp->internal = (char *)hashp; |
170 | dbp->close = hash_close; | |
171 | dbp->del = hash_delete; | |
172 | dbp->get = hash_get; | |
173 | dbp->put = hash_put; | |
174 | dbp->seq = hash_seq; | |
175 | dbp->sync = hash_sync; | |
176 | dbp->type = DB_HASH; | |
cb07bd68 KB |
177 | |
178 | #ifdef DEBUG | |
6f0d4752 | 179 | (void)fprintf(stderr, |
c8526f36 | 180 | "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n", |
6f0d4752 KB |
181 | "init_htab:", |
182 | "TABLE POINTER ", hashp, | |
183 | "BUCKET SIZE ", hashp->BSIZE, | |
184 | "BUCKET SHIFT ", hashp->BSHIFT, | |
185 | "DIRECTORY SIZE ", hashp->DSIZE, | |
186 | "SEGMENT SIZE ", hashp->SGSIZE, | |
187 | "SEGMENT SHIFT ", hashp->SSHIFT, | |
188 | "FILL FACTOR ", hashp->FFACTOR, | |
189 | "MAX BUCKET ", hashp->MAX_BUCKET, | |
c8526f36 KB |
190 | "OVFL POINT ", hashp->OVFL_POINT, |
191 | "LAST FREED ", hashp->LAST_FREED, | |
6f0d4752 KB |
192 | "HIGH MASK ", hashp->HIGH_MASK, |
193 | "LOW MASK ", hashp->LOW_MASK, | |
194 | "NSEGS ", hashp->nsegs, | |
195 | "NKEYS ", hashp->NKEYS); | |
cb07bd68 KB |
196 | #endif |
197 | #ifdef HASH_STATISTICS | |
198 | hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; | |
199 | #endif | |
6f0d4752 | 200 | return (dbp); |
cb07bd68 KB |
201 | |
202 | error1: | |
992dde47 KB |
203 | if (hashp != NULL) |
204 | (void)close(hashp->fp); | |
cb07bd68 KB |
205 | |
206 | error0: | |
6f0d4752 KB |
207 | free(hashp); |
208 | errno = save_errno; | |
209 | return (NULL); | |
cb07bd68 KB |
210 | } |
211 | ||
212 | static int | |
6f0d4752 KB |
213 | hash_close(dbp) |
214 | DB *dbp; | |
cb07bd68 | 215 | { |
6f0d4752 | 216 | int retval; |
f1f9da3d | 217 | |
6f0d4752 KB |
218 | if (!dbp) |
219 | return (ERROR); | |
cb07bd68 | 220 | hashp = (HTAB *)dbp->internal; |
f1f9da3d | 221 | retval = hdestroy(); |
6f0d4752 KB |
222 | free(dbp); |
223 | return (retval); | |
cb07bd68 KB |
224 | } |
225 | ||
cb07bd68 | 226 | /************************** LOCAL CREATION ROUTINES **********************/ |
6f0d4752 KB |
227 | static HTAB * |
228 | init_hash(info) | |
229 | HASHINFO *info; | |
cb07bd68 | 230 | { |
6f0d4752 | 231 | int nelem; |
cb07bd68 KB |
232 | |
233 | nelem = 1; | |
c8526f36 | 234 | hashp->NKEYS = 0; |
6f0d4752 KB |
235 | hashp->LORDER = BYTE_ORDER; |
236 | hashp->BSIZE = DEF_BUCKET_SIZE; | |
237 | hashp->BSHIFT = DEF_BUCKET_SHIFT; | |
238 | hashp->SGSIZE = DEF_SEGSIZE; | |
239 | hashp->SSHIFT = DEF_SEGSIZE_SHIFT; | |
240 | hashp->DSIZE = DEF_DIRSIZE; | |
241 | hashp->FFACTOR = DEF_FFACTOR; | |
242 | hashp->hash = default_hash; | |
243 | bzero(hashp->SPARES, sizeof(hashp->SPARES)); | |
c8526f36 | 244 | bzero (hashp->BITMAPS, sizeof (hashp->BITMAPS)); |
6f0d4752 KB |
245 | |
246 | if (info) { | |
247 | if (info->bsize) { | |
248 | /* Round pagesize up to power of 2 */ | |
249 | hashp->BSHIFT = __log2(info->bsize); | |
250 | hashp->BSIZE = 1 << hashp->BSHIFT; | |
251 | if (hashp->BSIZE > MAX_BSIZE) { | |
252 | errno = EINVAL; | |
253 | return (NULL); | |
254 | } | |
cb07bd68 | 255 | } |
6f0d4752 KB |
256 | if (info->ffactor) |
257 | hashp->FFACTOR = info->ffactor; | |
258 | if (info->hash) | |
259 | hashp->hash = info->hash; | |
260 | if (info->nelem) | |
261 | nelem = info->nelem; | |
262 | if (info->lorder) { | |
263 | if (info->lorder != BIG_ENDIAN && | |
264 | info->lorder != LITTLE_ENDIAN) { | |
265 | errno = EINVAL; | |
266 | return (NULL); | |
267 | } | |
268 | hashp->LORDER = info->lorder; | |
cb07bd68 | 269 | } |
cb07bd68 | 270 | } |
cb07bd68 | 271 | /* init_htab should destroy the table and set errno if it fails */ |
6f0d4752 KB |
272 | if (init_htab(nelem)) |
273 | return (NULL); | |
274 | else | |
275 | return (hashp); | |
cb07bd68 | 276 | } |
cb07bd68 | 277 | /* |
6f0d4752 KB |
278 | * This calls alloc_segs which may run out of memory. Alloc_segs will destroy |
279 | * the table and set errno, so we just pass the error information along. | |
280 | * | |
281 | * Returns 0 on No Error | |
282 | */ | |
cb07bd68 | 283 | static int |
6f0d4752 KB |
284 | init_htab(nelem) |
285 | int nelem; | |
cb07bd68 | 286 | { |
6f0d4752 KB |
287 | register int nbuckets, nsegs; |
288 | int l2; | |
289 | ||
290 | /* | |
291 | * Divide number of elements by the fill factor and determine a | |
292 | * desired number of buckets. Allocate space for the next greater | |
293 | * power of two number of buckets. | |
294 | */ | |
cb07bd68 KB |
295 | nelem = (nelem - 1) / hashp->FFACTOR + 1; |
296 | ||
6f9c5818 | 297 | l2 = __log2(MAX(nelem, 2)); |
cb07bd68 | 298 | nbuckets = 1 << l2; |
cb07bd68 KB |
299 | |
300 | hashp->SPARES[l2] = l2 + 1; | |
6f0d4752 | 301 | hashp->SPARES[l2 + 1] = l2 + 1; |
c8526f36 KB |
302 | hashp->OVFL_POINT = l2; |
303 | hashp->LAST_FREED = 2; | |
304 | ||
6f0d4752 | 305 | /* First bitmap page is at: splitpoint l2 page offset 1 */ |
eb9054a0 KB |
306 | if (__init_bitmap(OADDR_OF(l2, 1), l2 + 1, 0)) |
307 | return (-1); | |
cb07bd68 KB |
308 | |
309 | hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; | |
310 | hashp->HIGH_MASK = (nbuckets << 1) - 1; | |
6f0d4752 KB |
311 | hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> |
312 | hashp->BSHIFT) + 1; | |
cb07bd68 KB |
313 | |
314 | nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; | |
315 | nsegs = 1 << __log2(nsegs); | |
316 | ||
6f0d4752 KB |
317 | if (nsegs > hashp->DSIZE) |
318 | hashp->DSIZE = nsegs; | |
319 | return (alloc_segs(nsegs)); | |
cb07bd68 KB |
320 | } |
321 | ||
322 | /********************** DESTROY/CLOSE ROUTINES ************************/ | |
323 | ||
324 | /* | |
6f0d4752 KB |
325 | * Flushes any changes to the file if necessary and destroys the hashp |
326 | * structure, freeing all allocated space. | |
327 | */ | |
cb07bd68 KB |
328 | static int |
329 | hdestroy() | |
330 | { | |
6f0d4752 | 331 | int i, save_errno; |
cb07bd68 KB |
332 | |
333 | save_errno = 0; | |
334 | ||
335 | if (hashp != NULL) { | |
336 | #ifdef HASH_STATISTICS | |
6f0d4752 KB |
337 | (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", |
338 | hash_accesses, hash_collisions); | |
339 | (void)fprintf(stderr, "hdestroy: expansions %ld\n", | |
340 | hash_expansions); | |
341 | (void)fprintf(stderr, "hdestroy: overflows %ld\n", | |
342 | hash_overflows); | |
343 | (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", | |
344 | hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); | |
345 | ||
346 | for (i = 0; i < NCACHED; i++) | |
347 | (void)fprintf(stderr, | |
348 | "spares[%d] = %d\n", i, hashp->SPARES[i]); | |
cb07bd68 | 349 | #endif |
6f0d4752 KB |
350 | /* |
351 | * Call on buffer manager to free buffers, and if required, | |
352 | * write them to disk. | |
353 | */ | |
354 | if (__buf_free(1, hashp->save_file)) | |
355 | save_errno = errno; | |
356 | if (hashp->dir) { | |
357 | free(*hashp->dir); /* Free initial segments */ | |
358 | /* Free extra segments */ | |
359 | while (hashp->exsegs--) | |
360 | free(hashp->dir[--hashp->nsegs]); | |
361 | free(hashp->dir); | |
cb07bd68 | 362 | } |
6f0d4752 KB |
363 | if (flush_meta() && !save_errno) |
364 | save_errno = errno; | |
de31e977 | 365 | /* Free Bigmaps */ |
6f0d4752 KB |
366 | for (i = 0; i < hashp->nmaps; i++) |
367 | if (hashp->mapp[i]) | |
368 | free(hashp->mapp[i]); | |
ea7a61eb | 369 | |
6f0d4752 KB |
370 | if (hashp->fp != -1) |
371 | (void)close(hashp->fp); | |
372 | free(hashp); | |
cb07bd68 KB |
373 | hashp = NULL; |
374 | } | |
6f0d4752 KB |
375 | if (save_errno) { |
376 | errno = save_errno; | |
377 | return (ERROR); | |
cb07bd68 | 378 | } |
6f0d4752 | 379 | return (SUCCESS); |
cb07bd68 | 380 | } |
6f0d4752 KB |
381 | /* |
382 | * Write modified pages to disk | |
383 | * | |
384 | * Returns: | |
385 | * 0 == OK | |
386 | * -1 ERROR | |
387 | */ | |
cb07bd68 KB |
388 | static int |
389 | hash_sync(dbp) | |
6f0d4752 | 390 | const DB *dbp; |
cb07bd68 | 391 | { |
6f0d4752 KB |
392 | if (!dbp) |
393 | return (ERROR); | |
cb07bd68 KB |
394 | hashp = (HTAB *)dbp->internal; |
395 | ||
6f0d4752 KB |
396 | if (!hashp->save_file) |
397 | return (0); | |
398 | if (__buf_free(0, 1) || flush_meta()) | |
399 | return (ERROR); | |
cb07bd68 | 400 | hashp->new_file = 0; |
6f0d4752 | 401 | return (0); |
cb07bd68 KB |
402 | } |
403 | ||
404 | /* | |
6f0d4752 KB |
405 | * Returns: |
406 | * 0 == OK | |
407 | * -1 indicates that errno should be set | |
408 | */ | |
cb07bd68 KB |
409 | static int |
410 | flush_meta() | |
411 | { | |
129017de MT |
412 | HASHHDR *whdrp; |
413 | #if BYTE_ORDER == LITTLE_ENDIAN | |
414 | HASHHDR whdr; | |
415 | #endif | |
6f0d4752 KB |
416 | int fp, i, wsize; |
417 | ||
418 | if (!hashp->save_file) | |
419 | return (0); | |
cb07bd68 | 420 | hashp->MAGIC = HASHMAGIC; |
c8526f36 | 421 | hashp->VERSION = HASHVERSION; |
6f0d4752 | 422 | hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); |
cb07bd68 KB |
423 | |
424 | fp = hashp->fp; | |
425 | whdrp = &hashp->hdr; | |
426 | #if BYTE_ORDER == LITTLE_ENDIAN | |
427 | whdrp = &whdr; | |
6f0d4752 | 428 | swap_header_copy(&hashp->hdr, whdrp); |
cb07bd68 | 429 | #endif |
6f0d4752 KB |
430 | if ((lseek(fp, 0, SEEK_SET) == -1) || |
431 | ((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1)) | |
432 | return (-1); | |
433 | else | |
434 | if (wsize != sizeof(HASHHDR)) { | |
435 | errno = EFTYPE; | |
436 | hashp->errno = errno; | |
437 | return (-1); | |
cb07bd68 | 438 | } |
6f0d4752 KB |
439 | for (i = 0; i < NCACHED; i++) |
440 | if (hashp->mapp[i]) | |
e5610f74 | 441 | if (__put_page((char *)hashp->mapp[i], |
6f0d4752 KB |
442 | hashp->BITMAPS[i], 0, 1)) |
443 | return (-1); | |
444 | return (0); | |
cb07bd68 | 445 | } |
6f0d4752 | 446 | |
cb07bd68 KB |
447 | /*******************************SEARCH ROUTINES *****************************/ |
448 | /* | |
6f0d4752 KB |
449 | * All the access routines return |
450 | * | |
451 | * Returns: | |
452 | * 0 on SUCCESS | |
453 | * 1 to indicate an external ERROR (i.e. key not found, etc) | |
454 | * -1 to indicate an internal ERROR (i.e. out of memory, etc) | |
455 | */ | |
cb07bd68 | 456 | static int |
6f0d4752 KB |
457 | hash_get(dbp, key, data, flag) |
458 | const DB *dbp; | |
eb9054a0 KB |
459 | const DBT *key; |
460 | DBT *data; | |
6f0d4752 | 461 | u_int flag; |
cb07bd68 | 462 | { |
6f0d4752 KB |
463 | if (flag) { |
464 | hashp->errno = errno = EINVAL; | |
465 | return (ERROR); | |
466 | } | |
467 | hashp = (HTAB *)dbp->internal; | |
468 | if (hashp->flags & O_WRONLY) { | |
469 | hashp->errno = errno = EPERM; | |
470 | return (ERROR); | |
471 | } | |
eb9054a0 | 472 | return (hash_access(HASH_GET, (DBT *)key, data)); |
cb07bd68 KB |
473 | } |
474 | ||
475 | static int | |
6f0d4752 KB |
476 | hash_put(dbp, key, data, flag) |
477 | const DB *dbp; | |
478 | const DBT *key, *data; | |
479 | u_int flag; | |
cb07bd68 | 480 | { |
6f0d4752 KB |
481 | if (flag && flag != R_NOOVERWRITE) { |
482 | hashp->errno = errno = EINVAL; | |
483 | return (ERROR); | |
484 | } | |
485 | hashp = (HTAB *)dbp->internal; | |
486 | if ((hashp->flags & O_ACCMODE) == O_RDONLY) { | |
487 | hashp->errno = errno = EPERM; | |
488 | return (ERROR); | |
489 | } | |
eb9054a0 | 490 | return (hash_access(flag == R_NOOVERWRITE ? |
6f0d4752 | 491 | HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data)); |
cb07bd68 KB |
492 | } |
493 | ||
494 | static int | |
6f0d4752 KB |
495 | hash_delete(dbp, key, flag) |
496 | const DB *dbp; | |
497 | const DBT *key; | |
498 | u_int flag; /* Ignored */ | |
cb07bd68 | 499 | { |
6f0d4752 KB |
500 | if (flag && flag != R_CURSOR) { |
501 | hashp->errno = errno = EINVAL; | |
502 | return (ERROR); | |
503 | } | |
504 | hashp = (HTAB *)dbp->internal; | |
505 | if ((hashp->flags & O_ACCMODE) == O_RDONLY) { | |
506 | hashp->errno = errno = EPERM; | |
507 | return (ERROR); | |
508 | } | |
509 | return (hash_access(HASH_DELETE, (DBT *)key, NULL)); | |
cb07bd68 KB |
510 | } |
511 | ||
512 | /* | |
6f0d4752 KB |
513 | * Assume that hashp has been set in wrapper routine. |
514 | */ | |
cb07bd68 KB |
515 | static int |
516 | hash_access(action, key, val) | |
6f0d4752 KB |
517 | ACTION action; |
518 | DBT *key, *val; | |
cb07bd68 | 519 | { |
6f0d4752 KB |
520 | register BUFHEAD *rbufp; |
521 | BUFHEAD *bufp, *save_bufp; | |
522 | register u_short *bp; | |
523 | register int n, ndx, off, size; | |
524 | register char *kp; | |
525 | u_short pageno; | |
cb07bd68 KB |
526 | |
527 | #ifdef HASH_STATISTICS | |
528 | hash_accesses++; | |
529 | #endif | |
530 | ||
6f0d4752 | 531 | off = hashp->BSIZE; |
cb07bd68 | 532 | size = key->size; |
c6ad6315 | 533 | kp = (char *)key->data; |
6f0d4752 KB |
534 | rbufp = __get_buf(__call_hash(kp, size), NULL, 0); |
535 | if (!rbufp) | |
536 | return (ERROR); | |
f1f9da3d | 537 | save_bufp = rbufp; |
cb07bd68 | 538 | |
f1f9da3d KB |
539 | /* Pin the bucket chain */ |
540 | rbufp->flags |= BUF_PIN; | |
6f0d4752 KB |
541 | for (bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) |
542 | if (bp[1] >= REAL_KEY) { | |
543 | /* Real key/data pair */ | |
544 | if (size == off - *bp && | |
545 | bcmp(kp, rbufp->page + *bp, size) == 0) | |
546 | goto found; | |
547 | off = bp[1]; | |
cb07bd68 | 548 | #ifdef HASH_STATISTICS |
6f0d4752 | 549 | hash_collisions++; |
cb07bd68 | 550 | #endif |
6f0d4752 KB |
551 | bp += 2; |
552 | ndx += 2; | |
553 | } else if (bp[1] == OVFLPAGE) { | |
554 | rbufp = __get_buf(*bp, rbufp, 0); | |
555 | if (!rbufp) { | |
556 | save_bufp->flags &= ~BUF_PIN; | |
557 | return (ERROR); | |
558 | } | |
559 | /* FOR LOOP INIT */ | |
560 | bp = (u_short *)rbufp->page; | |
561 | n = *bp++; | |
562 | ndx = 1; | |
563 | off = hashp->BSIZE; | |
564 | } else if (bp[1] < REAL_KEY) { | |
565 | if ((ndx = __find_bigpair(rbufp, ndx, kp, size)) > 0) | |
566 | goto found; | |
567 | if (ndx == -2) { | |
568 | bufp = rbufp; | |
569 | if (!(pageno = __find_last_page(&bufp))) { | |
570 | ndx = 0; | |
571 | rbufp = bufp; | |
572 | break; /* FOR */ | |
573 | } | |
574 | rbufp = __get_buf(pageno, bufp, 0); | |
575 | if (!rbufp) { | |
576 | save_bufp->flags &= ~BUF_PIN; | |
577 | return (ERROR); | |
578 | } | |
579 | /* FOR LOOP INIT */ | |
580 | bp = (u_short *)rbufp->page; | |
581 | n = *bp++; | |
582 | ndx = 1; | |
583 | off = hashp->BSIZE; | |
584 | } else { | |
585 | save_bufp->flags &= ~BUF_PIN; | |
586 | return (ERROR); | |
587 | } | |
cb07bd68 | 588 | } |
cb07bd68 KB |
589 | |
590 | /* Not found */ | |
6f0d4752 KB |
591 | switch (action) { |
592 | case HASH_PUT: | |
593 | case HASH_PUTNEW: | |
cb07bd68 | 594 | if (__addel(rbufp, key, val)) { |
6f0d4752 KB |
595 | save_bufp->flags &= ~BUF_PIN; |
596 | return (ERROR); | |
cb07bd68 | 597 | } else { |
6f0d4752 KB |
598 | save_bufp->flags &= ~BUF_PIN; |
599 | return (SUCCESS); | |
cb07bd68 | 600 | } |
6f0d4752 KB |
601 | case HASH_GET: |
602 | case HASH_DELETE: | |
603 | default: | |
f1f9da3d | 604 | save_bufp->flags &= ~BUF_PIN; |
6f0d4752 | 605 | return (ABNORMAL); |
cb07bd68 KB |
606 | } |
607 | ||
608 | found: | |
609 | switch (action) { | |
6f0d4752 | 610 | case HASH_PUTNEW: |
f1f9da3d | 611 | save_bufp->flags &= ~BUF_PIN; |
6f0d4752 KB |
612 | return (ABNORMAL); |
613 | case HASH_GET: | |
cb07bd68 | 614 | bp = (u_short *)rbufp->page; |
e5610f74 | 615 | if (bp[ndx + 1] < REAL_KEY) { |
eb9054a0 KB |
616 | if (__big_return(rbufp, ndx, val, 0)) |
617 | return (ERROR); | |
e5610f74 | 618 | } else { |
6f0d4752 KB |
619 | val->data = (u_char *)rbufp->page + (int)bp[ndx + 1]; |
620 | val->size = bp[ndx] - bp[ndx + 1]; | |
cb07bd68 KB |
621 | } |
622 | break; | |
6f0d4752 KB |
623 | case HASH_PUT: |
624 | if ((__delpair(rbufp, ndx)) || (__addel(rbufp, key, val))) { | |
625 | save_bufp->flags &= ~BUF_PIN; | |
626 | return (ERROR); | |
f1f9da3d | 627 | } |
cb07bd68 | 628 | break; |
6f0d4752 KB |
629 | case HASH_DELETE: |
630 | if (__delpair(rbufp, ndx)) | |
631 | return (ERROR); | |
cb07bd68 KB |
632 | break; |
633 | } | |
f1f9da3d | 634 | save_bufp->flags &= ~BUF_PIN; |
cb07bd68 KB |
635 | return (SUCCESS); |
636 | } | |
637 | ||
638 | static int | |
639 | hash_seq(dbp, key, data, flag) | |
6f0d4752 KB |
640 | const DB *dbp; |
641 | DBT *key, *data; | |
642 | u_int flag; | |
cb07bd68 | 643 | { |
6f0d4752 KB |
644 | register u_int bucket; |
645 | register BUFHEAD *bufp; | |
646 | u_short *bp, ndx; | |
cb07bd68 | 647 | |
6f0d4752 KB |
648 | if (flag && flag != R_FIRST && flag != R_NEXT) { |
649 | hashp->errno = errno = EINVAL; | |
650 | return (ERROR); | |
651 | } | |
cb07bd68 | 652 | hashp = (HTAB *)dbp->internal; |
6f0d4752 KB |
653 | if (hashp->flags & O_WRONLY) { |
654 | hashp->errno = errno = EPERM; | |
655 | return (ERROR); | |
cb07bd68 KB |
656 | } |
657 | #ifdef HASH_STATISTICS | |
658 | hash_accesses++; | |
659 | #endif | |
6f0d4752 KB |
660 | if ((hashp->cbucket < 0) || (flag == R_FIRST)) { |
661 | hashp->cbucket = 0; | |
662 | hashp->cndx = 1; | |
663 | hashp->cpage = NULL; | |
cb07bd68 | 664 | } |
6f0d4752 | 665 | |
e5278b07 KB |
666 | for (bp = NULL; !bp || !bp[0]; ++hashp->cbucket) { |
667 | if (!(bufp = hashp->cpage)) { | |
668 | for (bucket = hashp->cbucket; | |
669 | bucket <= hashp->MAX_BUCKET; | |
670 | bucket++, hashp->cndx = 1) { | |
671 | bufp = __get_buf(bucket, NULL, 0); | |
672 | if (!bufp) | |
673 | return (ERROR); | |
674 | hashp->cpage = bufp; | |
675 | bp = (u_short *)bufp->page; | |
676 | if (bp[0]) | |
677 | break; | |
678 | } | |
679 | hashp->cbucket = bucket; | |
680 | if (hashp->cbucket > hashp->MAX_BUCKET) { | |
681 | hashp->cbucket = -1; | |
682 | return (ABNORMAL); | |
683 | } | |
684 | } else | |
685 | bp = (u_short *)hashp->cpage->page; | |
cb07bd68 | 686 | |
cb07bd68 | 687 | #ifdef DEBUG |
e5278b07 KB |
688 | assert(bp); |
689 | assert(bufp); | |
cb07bd68 | 690 | #endif |
e5278b07 KB |
691 | while (bp[hashp->cndx + 1] == OVFLPAGE) { |
692 | bufp = hashp->cpage = | |
693 | __get_buf(bp[hashp->cndx], bufp, 0); | |
694 | if (!bufp) | |
695 | return (ERROR); | |
696 | bp = (u_short *)(bufp->page); | |
697 | hashp->cndx = 1; | |
698 | } | |
699 | if (!bp[0]) | |
700 | hashp->cpage = NULL; | |
cb07bd68 KB |
701 | } |
702 | ndx = hashp->cndx; | |
6f0d4752 | 703 | if (bp[ndx + 1] < REAL_KEY) { |
eb9054a0 | 704 | if (__big_keydata(bufp, key, data, 1)) |
6f0d4752 | 705 | return (ERROR); |
cb07bd68 | 706 | } else { |
6f0d4752 KB |
707 | key->data = (u_char *)hashp->cpage->page + bp[ndx]; |
708 | key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; | |
709 | data->data = (u_char *)hashp->cpage->page + bp[ndx + 1]; | |
710 | data->size = bp[ndx] - bp[ndx + 1]; | |
711 | ndx += 2; | |
712 | if (ndx > bp[0]) { | |
713 | hashp->cpage = NULL; | |
714 | hashp->cbucket++; | |
715 | hashp->cndx = 1; | |
716 | } else | |
717 | hashp->cndx = ndx; | |
cb07bd68 KB |
718 | } |
719 | return (SUCCESS); | |
720 | } | |
721 | ||
722 | /********************************* UTILITIES ************************/ | |
6f0d4752 | 723 | |
cb07bd68 | 724 | /* |
6f0d4752 KB |
725 | * Returns: |
726 | * 0 ==> OK | |
727 | * -1 ==> Error | |
728 | */ | |
cb07bd68 KB |
729 | extern int |
730 | __expand_table() | |
731 | { | |
6f0d4752 KB |
732 | u_int old_bucket, new_bucket; |
733 | int dirsize, new_segnum, spare_ndx; | |
734 | ||
cb07bd68 KB |
735 | #ifdef HASH_STATISTICS |
736 | hash_expansions++; | |
737 | #endif | |
cb07bd68 KB |
738 | new_bucket = ++hashp->MAX_BUCKET; |
739 | old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); | |
740 | ||
741 | new_segnum = new_bucket >> hashp->SSHIFT; | |
742 | ||
743 | /* Check if we need a new segment */ | |
6f0d4752 KB |
744 | if (new_segnum >= hashp->nsegs) { |
745 | /* Check if we need to expand directory */ | |
746 | if (new_segnum >= hashp->DSIZE) { | |
747 | /* Reallocate directory */ | |
748 | dirsize = hashp->DSIZE * sizeof(SEGMENT *); | |
749 | if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) | |
750 | return (-1); | |
751 | hashp->DSIZE = dirsize << 1; | |
cb07bd68 | 752 | } |
6f0d4752 KB |
753 | if (!(hashp->dir[new_segnum] = |
754 | calloc(hashp->SGSIZE, sizeof(SEGMENT)))) | |
755 | return (-1); | |
756 | hashp->exsegs++; | |
757 | hashp->nsegs++; | |
cb07bd68 | 758 | } |
cb07bd68 | 759 | /* |
6f0d4752 KB |
760 | * If the split point is increasing (MAX_BUCKET's log base 2 |
761 | * * increases), we need to copy the current contents of the spare | |
762 | * split bucket to the next bucket. | |
763 | */ | |
6f9c5818 KB |
764 | spare_ndx = __log2(hashp->MAX_BUCKET + 1); |
765 | if (spare_ndx > hashp->OVFL_POINT) { | |
c8526f36 KB |
766 | hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; |
767 | hashp->OVFL_POINT = spare_ndx; | |
768 | } | |
769 | ||
6f0d4752 KB |
770 | if (new_bucket > hashp->HIGH_MASK) { |
771 | /* Starting a new doubling */ | |
772 | hashp->LOW_MASK = hashp->HIGH_MASK; | |
773 | hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; | |
cb07bd68 | 774 | } |
6f0d4752 KB |
775 | /* Relocate records to the new bucket */ |
776 | return (__split_page(old_bucket, new_bucket)); | |
cb07bd68 | 777 | } |
6f0d4752 | 778 | |
cb07bd68 | 779 | /* |
6f0d4752 KB |
780 | * If realloc guarantees that the pointer is not destroyed if the realloc |
781 | * fails, then this routine can go away. | |
782 | */ | |
783 | static void * | |
784 | hash_realloc(p_ptr, oldsize, newsize) | |
785 | SEGMENT **p_ptr; | |
786 | int oldsize, newsize; | |
cb07bd68 | 787 | { |
6f0d4752 | 788 | register void *p; |
cb07bd68 | 789 | |
6f0d4752 KB |
790 | if (p = malloc(newsize)) { |
791 | bcopy(*p_ptr, p, oldsize); | |
792 | bzero(*p_ptr + oldsize, newsize - oldsize); | |
cb07bd68 KB |
793 | free(*p_ptr); |
794 | *p_ptr = p; | |
795 | } | |
796 | return (p); | |
797 | } | |
798 | ||
de31e977 | 799 | extern u_int |
6f0d4752 KB |
800 | __call_hash(k, len) |
801 | char *k; | |
802 | int len; | |
cb07bd68 | 803 | { |
6f0d4752 | 804 | int n, bucket; |
cb07bd68 | 805 | |
6f0d4752 | 806 | n = hashp->hash(k, len); |
cb07bd68 | 807 | bucket = n & hashp->HIGH_MASK; |
6f0d4752 KB |
808 | if (bucket > hashp->MAX_BUCKET) |
809 | bucket = bucket & hashp->LOW_MASK; | |
810 | return (bucket); | |
cb07bd68 KB |
811 | } |
812 | ||
813 | /* | |
6f0d4752 KB |
814 | * Allocate segment table. On error, destroy the table and set errno. |
815 | * | |
816 | * Returns 0 on success | |
817 | */ | |
cb07bd68 | 818 | static int |
6f0d4752 KB |
819 | alloc_segs(nsegs) |
820 | int nsegs; | |
cb07bd68 | 821 | { |
6f0d4752 KB |
822 | register int i; |
823 | register SEGMENT store; | |
cb07bd68 | 824 | |
6f0d4752 | 825 | int save_errno; |
cb07bd68 | 826 | |
6f0d4752 KB |
827 | if (!(hashp->dir = calloc(hashp->DSIZE, sizeof(SEGMENT *)))) { |
828 | save_errno = errno; | |
829 | (void)hdestroy(); | |
830 | errno = save_errno; | |
831 | return (-1); | |
832 | } | |
833 | /* Allocate segments */ | |
834 | store = calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT)); | |
835 | if (!store) { | |
836 | save_errno = errno; | |
837 | (void)hdestroy(); | |
838 | errno = save_errno; | |
839 | return (-1); | |
840 | } | |
841 | for (i = 0; i < nsegs; i++, hashp->nsegs++) | |
842 | hashp->dir[i] = &store[i << hashp->SSHIFT]; | |
843 | return (0); | |
cb07bd68 KB |
844 | } |
845 | ||
6f0d4752 | 846 | #if BYTE_ORDER == LITTLE_ENDIAN |
cb07bd68 | 847 | /* |
6f0d4752 KB |
848 | * Hashp->hdr needs to be byteswapped. |
849 | */ | |
cb07bd68 | 850 | static void |
6f0d4752 KB |
851 | swap_header_copy(srcp, destp) |
852 | HASHHDR *srcp, *destp; | |
cb07bd68 | 853 | { |
6f0d4752 KB |
854 | int i; |
855 | ||
856 | BLSWAP_COPY(srcp->magic, destp->magic); | |
857 | BLSWAP_COPY(srcp->version, destp->version); | |
858 | BLSWAP_COPY(srcp->lorder, destp->lorder); | |
859 | BLSWAP_COPY(srcp->bsize, destp->bsize); | |
860 | BLSWAP_COPY(srcp->bshift, destp->bshift); | |
861 | BLSWAP_COPY(srcp->dsize, destp->dsize); | |
862 | BLSWAP_COPY(srcp->ssize, destp->ssize); | |
863 | BLSWAP_COPY(srcp->sshift, destp->sshift); | |
c8526f36 KB |
864 | BLSWAP_COPY(srcp->ovfl_point, destp->ovfl_point); |
865 | BLSWAP_COPY(srcp->last_freed, destp->last_freed); | |
6f0d4752 KB |
866 | BLSWAP_COPY(srcp->max_bucket, destp->max_bucket); |
867 | BLSWAP_COPY(srcp->high_mask, destp->high_mask); | |
868 | BLSWAP_COPY(srcp->low_mask, destp->low_mask); | |
869 | BLSWAP_COPY(srcp->ffactor, destp->ffactor); | |
870 | BLSWAP_COPY(srcp->nkeys, destp->nkeys); | |
871 | BLSWAP_COPY(srcp->hdrpages, destp->hdrpages); | |
872 | BLSWAP_COPY(srcp->h_charkey, destp->h_charkey); | |
873 | for (i = 0; i < NCACHED; i++) { | |
874 | BLSWAP_COPY(srcp->spares[i], destp->spares[i]); | |
875 | BSSWAP_COPY(srcp->bitmaps[i], destp->bitmaps[i]); | |
876 | } | |
cb07bd68 KB |
877 | } |
878 | ||
879 | static void | |
6f0d4752 | 880 | swap_header() |
cb07bd68 | 881 | { |
6f0d4752 KB |
882 | HASHHDR *hdrp; |
883 | int i; | |
884 | ||
885 | hdrp = &hashp->hdr; | |
886 | ||
887 | BLSWAP(hdrp->magic); | |
888 | BLSWAP(hdrp->version); | |
889 | BLSWAP(hdrp->lorder); | |
890 | BLSWAP(hdrp->bsize); | |
891 | BLSWAP(hdrp->bshift); | |
892 | BLSWAP(hdrp->dsize); | |
893 | BLSWAP(hdrp->ssize); | |
894 | BLSWAP(hdrp->sshift); | |
c8526f36 KB |
895 | BLSWAP(hdrp->ovfl_point); |
896 | BLSWAP(hdrp->last_freed); | |
6f0d4752 KB |
897 | BLSWAP(hdrp->max_bucket); |
898 | BLSWAP(hdrp->high_mask); | |
899 | BLSWAP(hdrp->low_mask); | |
900 | BLSWAP(hdrp->ffactor); | |
901 | BLSWAP(hdrp->nkeys); | |
902 | BLSWAP(hdrp->hdrpages); | |
903 | BLSWAP(hdrp->h_charkey); | |
904 | for (i = 0; i < NCACHED; i++) { | |
905 | BLSWAP(hdrp->spares[i]); | |
906 | BSSWAP(hdrp->bitmaps[i]); | |
907 | } | |
cb07bd68 | 908 | } |
6f0d4752 | 909 | #endif |