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