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