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