1*0a6a1f1dSLionel Sambuc /* $NetBSD: hash.c,v 1.35 2015/06/22 21:16:02 christos Exp $ */
22639ae9bSBen Gras
32639ae9bSBen Gras /*-
42639ae9bSBen Gras * Copyright (c) 1990, 1993, 1994
52639ae9bSBen Gras * The Regents of the University of California. All rights reserved.
62639ae9bSBen Gras *
72639ae9bSBen Gras * This code is derived from software contributed to Berkeley by
82639ae9bSBen Gras * Margo Seltzer.
92639ae9bSBen Gras *
102639ae9bSBen Gras * Redistribution and use in source and binary forms, with or without
112639ae9bSBen Gras * modification, are permitted provided that the following conditions
122639ae9bSBen Gras * are met:
132639ae9bSBen Gras * 1. Redistributions of source code must retain the above copyright
142639ae9bSBen Gras * notice, this list of conditions and the following disclaimer.
152639ae9bSBen Gras * 2. Redistributions in binary form must reproduce the above copyright
162639ae9bSBen Gras * notice, this list of conditions and the following disclaimer in the
172639ae9bSBen Gras * documentation and/or other materials provided with the distribution.
182639ae9bSBen Gras * 3. Neither the name of the University nor the names of its contributors
192639ae9bSBen Gras * may be used to endorse or promote products derived from this software
202639ae9bSBen Gras * without specific prior written permission.
212639ae9bSBen Gras *
222639ae9bSBen Gras * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
232639ae9bSBen Gras * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
242639ae9bSBen Gras * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
252639ae9bSBen Gras * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
262639ae9bSBen Gras * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
272639ae9bSBen Gras * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
282639ae9bSBen Gras * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
292639ae9bSBen Gras * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
302639ae9bSBen Gras * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
312639ae9bSBen Gras * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
322639ae9bSBen Gras * SUCH DAMAGE.
332639ae9bSBen Gras */
342639ae9bSBen Gras
352639ae9bSBen Gras #if HAVE_NBTOOL_CONFIG_H
362639ae9bSBen Gras #include "nbtool_config.h"
372639ae9bSBen Gras #endif
382639ae9bSBen Gras
392639ae9bSBen Gras #include <sys/cdefs.h>
40*0a6a1f1dSLionel Sambuc __RCSID("$NetBSD: hash.c,v 1.35 2015/06/22 21:16:02 christos Exp $");
412639ae9bSBen Gras
422639ae9bSBen Gras #include "namespace.h"
432639ae9bSBen Gras #include <sys/param.h>
442639ae9bSBen Gras #include <sys/stat.h>
452639ae9bSBen Gras
462639ae9bSBen Gras #include <errno.h>
472639ae9bSBen Gras #include <fcntl.h>
482639ae9bSBen Gras #include <stdio.h>
492639ae9bSBen Gras #include <stdlib.h>
502639ae9bSBen Gras #include <string.h>
512639ae9bSBen Gras #include <unistd.h>
522639ae9bSBen Gras #include <assert.h>
532639ae9bSBen Gras
542639ae9bSBen Gras #include <db.h>
552639ae9bSBen Gras #include "hash.h"
562639ae9bSBen Gras #include "page.h"
572639ae9bSBen Gras #include "extern.h"
582639ae9bSBen Gras
592639ae9bSBen Gras static int alloc_segs(HTAB *, int);
602639ae9bSBen Gras static int flush_meta(HTAB *);
612639ae9bSBen Gras static int hash_access(HTAB *, ACTION, DBT *, DBT *);
622639ae9bSBen Gras static int hash_close(DB *);
632fe8fb19SBen Gras static int hash_delete(const DB *, const DBT *, uint32_t);
642639ae9bSBen Gras static int hash_fd(const DB *);
652fe8fb19SBen Gras static int hash_get(const DB *, const DBT *, DBT *, uint32_t);
662fe8fb19SBen Gras static int hash_put(const DB *, DBT *, const DBT *, uint32_t);
672639ae9bSBen Gras static void *hash_realloc(SEGMENT **, size_t, size_t);
682fe8fb19SBen Gras static int hash_seq(const DB *, DBT *, DBT *, uint32_t);
692fe8fb19SBen Gras static int hash_sync(const DB *, uint32_t);
702639ae9bSBen Gras static int hdestroy(HTAB *);
712639ae9bSBen Gras static HTAB *init_hash(HTAB *, const char *, const HASHINFO *);
722639ae9bSBen Gras static int init_htab(HTAB *, size_t);
732639ae9bSBen Gras #if BYTE_ORDER == LITTLE_ENDIAN
742639ae9bSBen Gras static void swap_header(HTAB *);
752639ae9bSBen Gras static void swap_header_copy(HASHHDR *, HASHHDR *);
762639ae9bSBen Gras #endif
772639ae9bSBen Gras
782639ae9bSBen Gras /* Fast arithmetic, relying on powers of 2, */
792639ae9bSBen Gras #define MOD(x, y) ((x) & ((y) - 1))
802639ae9bSBen Gras
812639ae9bSBen Gras #define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; }
822639ae9bSBen Gras
832639ae9bSBen Gras /* Return values */
842639ae9bSBen Gras #define SUCCESS (0)
852639ae9bSBen Gras #define ERROR (-1)
862639ae9bSBen Gras #define ABNORMAL (1)
872639ae9bSBen Gras
882639ae9bSBen Gras #ifdef HASH_STATISTICS
892639ae9bSBen Gras int hash_accesses, hash_collisions, hash_expansions, hash_overflows;
902639ae9bSBen Gras #endif
912639ae9bSBen Gras
922639ae9bSBen Gras /************************** INTERFACE ROUTINES ***************************/
932639ae9bSBen Gras /* OPEN/CLOSE */
942639ae9bSBen Gras
952639ae9bSBen Gras /* ARGSUSED */
962639ae9bSBen Gras DB *
__hash_open(const char * file,int flags,mode_t mode,const HASHINFO * info,int dflags)972639ae9bSBen Gras __hash_open(const char *file, int flags, mode_t mode, const HASHINFO *info,
982639ae9bSBen Gras int dflags)
992639ae9bSBen Gras {
1002639ae9bSBen Gras HTAB *hashp;
1012639ae9bSBen Gras struct stat statbuf;
1022639ae9bSBen Gras DB *dbp;
1032639ae9bSBen Gras int bpages, new_table, nsegs, save_errno;
1042639ae9bSBen Gras ssize_t hdrsize;
1052639ae9bSBen Gras
1062639ae9bSBen Gras if ((flags & O_ACCMODE) == O_WRONLY) {
1072639ae9bSBen Gras errno = EINVAL;
1082639ae9bSBen Gras return (NULL);
1092639ae9bSBen Gras }
1102639ae9bSBen Gras
1112639ae9bSBen Gras if (!(hashp = calloc(1, sizeof(HTAB))))
1122639ae9bSBen Gras return (NULL);
1132639ae9bSBen Gras hashp->fp = -1;
1142639ae9bSBen Gras
1152639ae9bSBen Gras /*
1162639ae9bSBen Gras * Even if user wants write only, we need to be able to read
1172639ae9bSBen Gras * the actual file, so we need to open it read/write. But, the
1182639ae9bSBen Gras * field in the hashp structure needs to be accurate so that
1192639ae9bSBen Gras * we can check accesses.
1202639ae9bSBen Gras */
1212639ae9bSBen Gras hashp->flags = flags;
1222639ae9bSBen Gras
1232639ae9bSBen Gras new_table = 0;
1242639ae9bSBen Gras if (!file || (flags & O_TRUNC) ||
1252639ae9bSBen Gras (stat(file, &statbuf) && (errno == ENOENT))) {
1262639ae9bSBen Gras if (errno == ENOENT)
1272639ae9bSBen Gras errno = 0; /* Just in case someone looks at errno */
1282639ae9bSBen Gras new_table = 1;
1292639ae9bSBen Gras }
1302639ae9bSBen Gras if (file) {
13184d9c625SLionel Sambuc if ((hashp->fp = __dbopen(file, flags, mode, &statbuf)) == -1)
1322639ae9bSBen Gras RETURN_ERROR(errno, error0);
1332639ae9bSBen Gras new_table |= statbuf.st_size == 0;
1342639ae9bSBen Gras }
1352639ae9bSBen Gras if (new_table) {
1362639ae9bSBen Gras if (!(hashp = init_hash(hashp, file, info)))
1372639ae9bSBen Gras RETURN_ERROR(errno, error1);
1382639ae9bSBen Gras } else {
1392639ae9bSBen Gras /* Table already exists */
1402639ae9bSBen Gras if (info && info->hash)
1412639ae9bSBen Gras hashp->hash = info->hash;
1422639ae9bSBen Gras else
1432639ae9bSBen Gras hashp->hash = __default_hash;
1442639ae9bSBen Gras
1452639ae9bSBen Gras hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR));
1462639ae9bSBen Gras #if BYTE_ORDER == LITTLE_ENDIAN
1472639ae9bSBen Gras swap_header(hashp);
1482639ae9bSBen Gras #endif
1492639ae9bSBen Gras if (hdrsize == -1)
1502639ae9bSBen Gras RETURN_ERROR(errno, error1);
1512639ae9bSBen Gras if (hdrsize != sizeof(HASHHDR))
1522639ae9bSBen Gras RETURN_ERROR(EFTYPE, error1);
1532639ae9bSBen Gras /* Verify file type, versions and hash function */
1542639ae9bSBen Gras if (hashp->MAGIC != HASHMAGIC)
1552639ae9bSBen Gras RETURN_ERROR(EFTYPE, error1);
1562639ae9bSBen Gras #define OLDHASHVERSION 1
1572639ae9bSBen Gras if (hashp->VERSION != HASHVERSION &&
1582639ae9bSBen Gras hashp->VERSION != OLDHASHVERSION)
1592639ae9bSBen Gras RETURN_ERROR(EFTYPE, error1);
1602639ae9bSBen Gras if (hashp->hash(CHARKEY, sizeof(CHARKEY)) !=
1612639ae9bSBen Gras (uint32_t)hashp->H_CHARKEY)
1622639ae9bSBen Gras RETURN_ERROR(EFTYPE, error1);
1632639ae9bSBen Gras /*
1642639ae9bSBen Gras * Figure out how many segments we need. Max_Bucket is the
1652639ae9bSBen Gras * maximum bucket number, so the number of buckets is
1662639ae9bSBen Gras * max_bucket + 1.
1672639ae9bSBen Gras */
1682639ae9bSBen Gras nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) /
1692639ae9bSBen Gras hashp->SGSIZE;
1702639ae9bSBen Gras hashp->nsegs = 0;
1712639ae9bSBen Gras if (alloc_segs(hashp, nsegs))
1722639ae9bSBen Gras /*
1732639ae9bSBen Gras * If alloc_segs fails, table will have been destroyed
1742639ae9bSBen Gras * and errno will have been set.
1752639ae9bSBen Gras */
1762639ae9bSBen Gras return (NULL);
1772639ae9bSBen Gras /* Read in bitmaps */
1782639ae9bSBen Gras bpages = (hashp->SPARES[hashp->OVFL_POINT] +
1792639ae9bSBen Gras (unsigned int)(hashp->BSIZE << BYTE_SHIFT) - 1) >>
1802639ae9bSBen Gras (hashp->BSHIFT + BYTE_SHIFT);
1812639ae9bSBen Gras
1822639ae9bSBen Gras hashp->nmaps = bpages;
1832639ae9bSBen Gras (void)memset(&hashp->mapp[0], 0, bpages * sizeof(uint32_t *));
1842639ae9bSBen Gras }
1852639ae9bSBen Gras
1862639ae9bSBen Gras /* Initialize Buffer Manager */
1872639ae9bSBen Gras if (info && info->cachesize)
1882639ae9bSBen Gras __buf_init(hashp, info->cachesize);
1892639ae9bSBen Gras else
1902639ae9bSBen Gras __buf_init(hashp, DEF_BUFSIZE);
1912639ae9bSBen Gras
1922639ae9bSBen Gras hashp->new_file = new_table;
1932639ae9bSBen Gras hashp->save_file = file && (hashp->flags & O_RDWR);
1942639ae9bSBen Gras hashp->cbucket = -1;
19584d9c625SLionel Sambuc if (!(dbp = malloc(sizeof(*dbp)))) {
1962639ae9bSBen Gras save_errno = errno;
1972639ae9bSBen Gras hdestroy(hashp);
1982639ae9bSBen Gras errno = save_errno;
1992639ae9bSBen Gras return (NULL);
2002639ae9bSBen Gras }
2012639ae9bSBen Gras dbp->internal = hashp;
2022639ae9bSBen Gras dbp->close = hash_close;
2032639ae9bSBen Gras dbp->del = hash_delete;
2042639ae9bSBen Gras dbp->fd = hash_fd;
2052639ae9bSBen Gras dbp->get = hash_get;
2062639ae9bSBen Gras dbp->put = hash_put;
2072639ae9bSBen Gras dbp->seq = hash_seq;
2082639ae9bSBen Gras dbp->sync = hash_sync;
2092639ae9bSBen Gras dbp->type = DB_HASH;
2102639ae9bSBen Gras
211f14fb602SLionel Sambuc #ifdef DEBUG1
2122639ae9bSBen Gras (void)fprintf(stderr,
2132639ae9bSBen Gras "%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",
2142639ae9bSBen Gras "init_htab:",
2152639ae9bSBen Gras "TABLE POINTER ", hashp,
2162639ae9bSBen Gras "BUCKET SIZE ", hashp->BSIZE,
2172639ae9bSBen Gras "BUCKET SHIFT ", hashp->BSHIFT,
2182639ae9bSBen Gras "DIRECTORY SIZE ", hashp->DSIZE,
2192639ae9bSBen Gras "SEGMENT SIZE ", hashp->SGSIZE,
2202639ae9bSBen Gras "SEGMENT SHIFT ", hashp->SSHIFT,
2212639ae9bSBen Gras "FILL FACTOR ", hashp->FFACTOR,
2222639ae9bSBen Gras "MAX BUCKET ", hashp->MAX_BUCKET,
2232639ae9bSBen Gras "OVFL POINT ", hashp->OVFL_POINT,
2242639ae9bSBen Gras "LAST FREED ", hashp->LAST_FREED,
2252639ae9bSBen Gras "HIGH MASK ", hashp->HIGH_MASK,
2262639ae9bSBen Gras "LOW MASK ", hashp->LOW_MASK,
2272639ae9bSBen Gras "NSEGS ", hashp->nsegs,
2282639ae9bSBen Gras "NKEYS ", hashp->NKEYS);
2292639ae9bSBen Gras #endif
2302639ae9bSBen Gras #ifdef HASH_STATISTICS
2312639ae9bSBen Gras hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
2322639ae9bSBen Gras #endif
2332639ae9bSBen Gras return (dbp);
2342639ae9bSBen Gras
2352639ae9bSBen Gras error1:
2362639ae9bSBen Gras if (hashp != NULL)
2372639ae9bSBen Gras (void)close(hashp->fp);
2382639ae9bSBen Gras
2392639ae9bSBen Gras error0:
2402639ae9bSBen Gras free(hashp);
2412639ae9bSBen Gras errno = save_errno;
2422639ae9bSBen Gras return (NULL);
2432639ae9bSBen Gras }
2442639ae9bSBen Gras
2452639ae9bSBen Gras static int
hash_close(DB * dbp)2462639ae9bSBen Gras hash_close(DB *dbp)
2472639ae9bSBen Gras {
2482639ae9bSBen Gras HTAB *hashp;
2492639ae9bSBen Gras int retval;
2502639ae9bSBen Gras
2512639ae9bSBen Gras if (!dbp)
2522639ae9bSBen Gras return (ERROR);
2532639ae9bSBen Gras
2542639ae9bSBen Gras hashp = dbp->internal;
2552639ae9bSBen Gras retval = hdestroy(hashp);
2562639ae9bSBen Gras free(dbp);
2572639ae9bSBen Gras return (retval);
2582639ae9bSBen Gras }
2592639ae9bSBen Gras
2602639ae9bSBen Gras static int
hash_fd(const DB * dbp)2612639ae9bSBen Gras hash_fd(const DB *dbp)
2622639ae9bSBen Gras {
2632639ae9bSBen Gras HTAB *hashp;
2642639ae9bSBen Gras
2652639ae9bSBen Gras if (!dbp)
2662639ae9bSBen Gras return (ERROR);
2672639ae9bSBen Gras
2682639ae9bSBen Gras hashp = dbp->internal;
2692639ae9bSBen Gras if (hashp->fp == -1) {
2702639ae9bSBen Gras errno = ENOENT;
2712639ae9bSBen Gras return (-1);
2722639ae9bSBen Gras }
2732639ae9bSBen Gras return (hashp->fp);
2742639ae9bSBen Gras }
2752639ae9bSBen Gras
2762639ae9bSBen Gras /************************** LOCAL CREATION ROUTINES **********************/
2772639ae9bSBen Gras static HTAB *
init_hash(HTAB * hashp,const char * file,const HASHINFO * info)2782639ae9bSBen Gras init_hash(HTAB *hashp, const char *file, const HASHINFO *info)
2792639ae9bSBen Gras {
2802639ae9bSBen Gras struct stat statbuf;
2812639ae9bSBen Gras int nelem;
2822639ae9bSBen Gras
2832639ae9bSBen Gras nelem = 1;
2842639ae9bSBen Gras hashp->NKEYS = 0;
2852639ae9bSBen Gras hashp->LORDER = BYTE_ORDER;
2862639ae9bSBen Gras hashp->BSIZE = DEF_BUCKET_SIZE;
2872639ae9bSBen Gras hashp->BSHIFT = DEF_BUCKET_SHIFT;
2882639ae9bSBen Gras hashp->SGSIZE = DEF_SEGSIZE;
2892639ae9bSBen Gras hashp->SSHIFT = DEF_SEGSIZE_SHIFT;
2902639ae9bSBen Gras hashp->DSIZE = DEF_DIRSIZE;
2912639ae9bSBen Gras hashp->FFACTOR = DEF_FFACTOR;
2922639ae9bSBen Gras hashp->hash = __default_hash;
2932639ae9bSBen Gras memset(hashp->SPARES, 0, sizeof(hashp->SPARES));
2942639ae9bSBen Gras memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));
2952639ae9bSBen Gras
2962639ae9bSBen Gras /* Fix bucket size to be optimal for file system */
2972639ae9bSBen Gras if (file != NULL) {
2982639ae9bSBen Gras if (stat(file, &statbuf))
2992639ae9bSBen Gras return (NULL);
3002fe8fb19SBen Gras hashp->BSIZE = MIN(statbuf.st_blksize, MAX_BSIZE);
3012639ae9bSBen Gras hashp->BSHIFT = __log2((uint32_t)hashp->BSIZE);
3022639ae9bSBen Gras }
3032639ae9bSBen Gras
3042639ae9bSBen Gras if (info) {
3052639ae9bSBen Gras if (info->bsize) {
3062639ae9bSBen Gras /* Round pagesize up to power of 2 */
3072639ae9bSBen Gras hashp->BSHIFT = __log2(info->bsize);
3082639ae9bSBen Gras hashp->BSIZE = 1 << hashp->BSHIFT;
3092639ae9bSBen Gras if (hashp->BSIZE > MAX_BSIZE) {
3102639ae9bSBen Gras errno = EINVAL;
3112639ae9bSBen Gras return (NULL);
3122639ae9bSBen Gras }
3132639ae9bSBen Gras }
3142639ae9bSBen Gras if (info->ffactor)
3152639ae9bSBen Gras hashp->FFACTOR = info->ffactor;
3162639ae9bSBen Gras if (info->hash)
3172639ae9bSBen Gras hashp->hash = info->hash;
3182639ae9bSBen Gras if (info->nelem)
3192639ae9bSBen Gras nelem = info->nelem;
3202639ae9bSBen Gras if (info->lorder) {
3212639ae9bSBen Gras if (info->lorder != BIG_ENDIAN &&
3222639ae9bSBen Gras info->lorder != LITTLE_ENDIAN) {
3232639ae9bSBen Gras errno = EINVAL;
3242639ae9bSBen Gras return (NULL);
3252639ae9bSBen Gras }
3262639ae9bSBen Gras hashp->LORDER = info->lorder;
3272639ae9bSBen Gras }
3282639ae9bSBen Gras }
3292639ae9bSBen Gras /* init_htab should destroy the table and set errno if it fails */
3302639ae9bSBen Gras if (init_htab(hashp, (size_t)nelem))
3312639ae9bSBen Gras return (NULL);
3322639ae9bSBen Gras else
3332639ae9bSBen Gras return (hashp);
3342639ae9bSBen Gras }
3352639ae9bSBen Gras /*
3362639ae9bSBen Gras * This calls alloc_segs which may run out of memory. Alloc_segs will destroy
3372639ae9bSBen Gras * the table and set errno, so we just pass the error information along.
3382639ae9bSBen Gras *
3392639ae9bSBen Gras * Returns 0 on No Error
3402639ae9bSBen Gras */
3412639ae9bSBen Gras static int
init_htab(HTAB * hashp,size_t nelem)3422639ae9bSBen Gras init_htab(HTAB *hashp, size_t nelem)
3432639ae9bSBen Gras {
3442639ae9bSBen Gras int nbuckets;
3452639ae9bSBen Gras uint32_t nsegs;
3462639ae9bSBen Gras int l2;
3472639ae9bSBen Gras
3482639ae9bSBen Gras /*
3492639ae9bSBen Gras * Divide number of elements by the fill factor and determine a
3502639ae9bSBen Gras * desired number of buckets. Allocate space for the next greater
3512639ae9bSBen Gras * power of two number of buckets.
3522639ae9bSBen Gras */
3532639ae9bSBen Gras nelem = (nelem - 1) / hashp->FFACTOR + 1;
3542639ae9bSBen Gras
3552639ae9bSBen Gras _DBFIT(nelem, uint32_t);
3562639ae9bSBen Gras l2 = __log2(MAX((uint32_t)nelem, 2));
3572639ae9bSBen Gras nbuckets = 1 << l2;
3582639ae9bSBen Gras
3592639ae9bSBen Gras hashp->SPARES[l2] = l2 + 1;
3602639ae9bSBen Gras hashp->SPARES[l2 + 1] = l2 + 1;
3612639ae9bSBen Gras hashp->OVFL_POINT = l2;
3622639ae9bSBen Gras hashp->LAST_FREED = 2;
3632639ae9bSBen Gras
3642639ae9bSBen Gras /* First bitmap page is at: splitpoint l2 page offset 1 */
3652639ae9bSBen Gras if (__ibitmap(hashp, (int)OADDR_OF(l2, 1), l2 + 1, 0))
3662639ae9bSBen Gras return (-1);
3672639ae9bSBen Gras
3682639ae9bSBen Gras hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
3692639ae9bSBen Gras hashp->HIGH_MASK = (nbuckets << 1) - 1;
3702639ae9bSBen Gras /* LINTED constant in conditional context */
3712639ae9bSBen Gras hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>
3722639ae9bSBen Gras hashp->BSHIFT) + 1;
3732639ae9bSBen Gras
3742639ae9bSBen Gras nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
3752639ae9bSBen Gras nsegs = 1 << __log2(nsegs);
3762639ae9bSBen Gras
3772639ae9bSBen Gras if (nsegs > (uint32_t)hashp->DSIZE)
3782639ae9bSBen Gras hashp->DSIZE = nsegs;
3792639ae9bSBen Gras return (alloc_segs(hashp, (int)nsegs));
3802639ae9bSBen Gras }
3812639ae9bSBen Gras
3822639ae9bSBen Gras /********************** DESTROY/CLOSE ROUTINES ************************/
3832639ae9bSBen Gras
3842639ae9bSBen Gras /*
3852639ae9bSBen Gras * Flushes any changes to the file if necessary and destroys the hashp
3862639ae9bSBen Gras * structure, freeing all allocated space.
3872639ae9bSBen Gras */
3882639ae9bSBen Gras static int
hdestroy(HTAB * hashp)3892639ae9bSBen Gras hdestroy(HTAB *hashp)
3902639ae9bSBen Gras {
3912639ae9bSBen Gras int i, save_errno;
3922639ae9bSBen Gras
3932639ae9bSBen Gras save_errno = 0;
3942639ae9bSBen Gras
3952639ae9bSBen Gras #ifdef HASH_STATISTICS
3962639ae9bSBen Gras (void)fprintf(stderr, "hdestroy: accesses %d collisions %d\n",
3972639ae9bSBen Gras hash_accesses, hash_collisions);
3982639ae9bSBen Gras (void)fprintf(stderr, "hdestroy: expansions %d\n",
3992639ae9bSBen Gras hash_expansions);
4002639ae9bSBen Gras (void)fprintf(stderr, "hdestroy: overflows %d\n",
4012639ae9bSBen Gras hash_overflows);
4022639ae9bSBen Gras (void)fprintf(stderr, "keys %d maxp %d segmentcount %d\n",
4032639ae9bSBen Gras hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
4042639ae9bSBen Gras
4052639ae9bSBen Gras for (i = 0; i < NCACHED; i++)
4062639ae9bSBen Gras (void)fprintf(stderr,
4072639ae9bSBen Gras "spares[%d] = %d\n", i, hashp->SPARES[i]);
4082639ae9bSBen Gras #endif
4092639ae9bSBen Gras /*
4102639ae9bSBen Gras * Call on buffer manager to free buffers, and if required,
4112639ae9bSBen Gras * write them to disk.
4122639ae9bSBen Gras */
4132639ae9bSBen Gras if (__buf_free(hashp, 1, hashp->save_file))
4142639ae9bSBen Gras save_errno = errno;
4152639ae9bSBen Gras if (hashp->dir) {
4162639ae9bSBen Gras free(*hashp->dir); /* Free initial segments */
4172639ae9bSBen Gras /* Free extra segments */
4182639ae9bSBen Gras while (hashp->exsegs--)
4192639ae9bSBen Gras free(hashp->dir[--hashp->nsegs]);
4202639ae9bSBen Gras free(hashp->dir);
4212639ae9bSBen Gras }
4222639ae9bSBen Gras if (flush_meta(hashp) && !save_errno)
4232639ae9bSBen Gras save_errno = errno;
4242639ae9bSBen Gras /* Free Bigmaps */
4252639ae9bSBen Gras for (i = 0; i < hashp->nmaps; i++)
4262639ae9bSBen Gras if (hashp->mapp[i])
4272639ae9bSBen Gras free(hashp->mapp[i]);
4282639ae9bSBen Gras
4292639ae9bSBen Gras if (hashp->fp != -1)
4302639ae9bSBen Gras (void)close(hashp->fp);
4312639ae9bSBen Gras
4322639ae9bSBen Gras free(hashp);
4332639ae9bSBen Gras
4342639ae9bSBen Gras if (save_errno) {
4352639ae9bSBen Gras errno = save_errno;
4362639ae9bSBen Gras return (ERROR);
4372639ae9bSBen Gras }
4382639ae9bSBen Gras return (SUCCESS);
4392639ae9bSBen Gras }
4402639ae9bSBen Gras /*
4412639ae9bSBen Gras * Write modified pages to disk
4422639ae9bSBen Gras *
4432639ae9bSBen Gras * Returns:
4442639ae9bSBen Gras * 0 == OK
4452639ae9bSBen Gras * -1 ERROR
4462639ae9bSBen Gras */
4472639ae9bSBen Gras static int
hash_sync(const DB * dbp,uint32_t flags)4482fe8fb19SBen Gras hash_sync(const DB *dbp, uint32_t flags)
4492639ae9bSBen Gras {
4502639ae9bSBen Gras HTAB *hashp;
4512639ae9bSBen Gras
4522639ae9bSBen Gras if (flags != 0) {
4532639ae9bSBen Gras errno = EINVAL;
4542639ae9bSBen Gras return (ERROR);
4552639ae9bSBen Gras }
4562639ae9bSBen Gras
4572639ae9bSBen Gras if (!dbp)
4582639ae9bSBen Gras return (ERROR);
4592639ae9bSBen Gras
4602639ae9bSBen Gras hashp = dbp->internal;
4612639ae9bSBen Gras if (!hashp->save_file)
4622639ae9bSBen Gras return (0);
4632639ae9bSBen Gras if (__buf_free(hashp, 0, 1) || flush_meta(hashp))
4642639ae9bSBen Gras return (ERROR);
4652639ae9bSBen Gras hashp->new_file = 0;
4662639ae9bSBen Gras return (0);
4672639ae9bSBen Gras }
4682639ae9bSBen Gras
4692639ae9bSBen Gras /*
4702639ae9bSBen Gras * Returns:
4712639ae9bSBen Gras * 0 == OK
4722639ae9bSBen Gras * -1 indicates that errno should be set
4732639ae9bSBen Gras */
4742639ae9bSBen Gras static int
flush_meta(HTAB * hashp)4752639ae9bSBen Gras flush_meta(HTAB *hashp)
4762639ae9bSBen Gras {
4772639ae9bSBen Gras HASHHDR *whdrp;
4782639ae9bSBen Gras #if BYTE_ORDER == LITTLE_ENDIAN
4792639ae9bSBen Gras HASHHDR whdr;
4802639ae9bSBen Gras #endif
4812639ae9bSBen Gras int fp, i;
4822639ae9bSBen Gras ssize_t wsize;
4832639ae9bSBen Gras
4842639ae9bSBen Gras if (!hashp->save_file)
4852639ae9bSBen Gras return (0);
4862639ae9bSBen Gras hashp->MAGIC = HASHMAGIC;
4872639ae9bSBen Gras hashp->VERSION = HASHVERSION;
4882639ae9bSBen Gras hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));
4892639ae9bSBen Gras
4902639ae9bSBen Gras fp = hashp->fp;
4912639ae9bSBen Gras whdrp = &hashp->hdr;
4922639ae9bSBen Gras #if BYTE_ORDER == LITTLE_ENDIAN
4932639ae9bSBen Gras whdrp = &whdr;
4942639ae9bSBen Gras swap_header_copy(&hashp->hdr, whdrp);
4952639ae9bSBen Gras #endif
4962639ae9bSBen Gras if ((wsize = pwrite(fp, whdrp, sizeof(HASHHDR), (off_t)0)) == -1)
4972639ae9bSBen Gras return (-1);
4982639ae9bSBen Gras else
4992639ae9bSBen Gras if (wsize != sizeof(HASHHDR)) {
5002639ae9bSBen Gras errno = EFTYPE;
5012639ae9bSBen Gras hashp->err = errno;
5022639ae9bSBen Gras return (-1);
5032639ae9bSBen Gras }
5042639ae9bSBen Gras for (i = 0; i < NCACHED; i++)
5052639ae9bSBen Gras if (hashp->mapp[i])
5062639ae9bSBen Gras if (__put_page(hashp, (char *)(void *)hashp->mapp[i],
5072639ae9bSBen Gras (u_int)hashp->BITMAPS[i], 0, 1))
5082639ae9bSBen Gras return (-1);
5092639ae9bSBen Gras return (0);
5102639ae9bSBen Gras }
5112639ae9bSBen Gras
5122639ae9bSBen Gras /*******************************SEARCH ROUTINES *****************************/
5132639ae9bSBen Gras /*
5142639ae9bSBen Gras * All the access routines return
5152639ae9bSBen Gras *
5162639ae9bSBen Gras * Returns:
5172639ae9bSBen Gras * 0 on SUCCESS
5182639ae9bSBen Gras * 1 to indicate an external ERROR (i.e. key not found, etc)
5192639ae9bSBen Gras * -1 to indicate an internal ERROR (i.e. out of memory, etc)
5202639ae9bSBen Gras */
5212639ae9bSBen Gras static int
hash_get(const DB * dbp,const DBT * key,DBT * data,uint32_t flag)5222fe8fb19SBen Gras hash_get(const DB *dbp, const DBT *key, DBT *data, uint32_t flag)
5232639ae9bSBen Gras {
5242639ae9bSBen Gras HTAB *hashp;
5252639ae9bSBen Gras
5262639ae9bSBen Gras hashp = dbp->internal;
5272639ae9bSBen Gras if (flag) {
5282639ae9bSBen Gras hashp->err = errno = EINVAL;
5292639ae9bSBen Gras return (ERROR);
5302639ae9bSBen Gras }
5312639ae9bSBen Gras return (hash_access(hashp, HASH_GET, __UNCONST(key), data));
5322639ae9bSBen Gras }
5332639ae9bSBen Gras
5342639ae9bSBen Gras static int
hash_put(const DB * dbp,DBT * key,const DBT * data,uint32_t flag)5352fe8fb19SBen Gras hash_put(const DB *dbp, DBT *key, const DBT *data, uint32_t flag)
5362639ae9bSBen Gras {
5372639ae9bSBen Gras HTAB *hashp;
5382639ae9bSBen Gras
5392639ae9bSBen Gras hashp = dbp->internal;
5402639ae9bSBen Gras if (flag && flag != R_NOOVERWRITE) {
5412639ae9bSBen Gras hashp->err = errno = EINVAL;
5422639ae9bSBen Gras return (ERROR);
5432639ae9bSBen Gras }
5442639ae9bSBen Gras if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
5452639ae9bSBen Gras hashp->err = errno = EPERM;
5462639ae9bSBen Gras return (ERROR);
5472639ae9bSBen Gras }
5482639ae9bSBen Gras /* LINTED const castaway */
5492639ae9bSBen Gras return (hash_access(hashp, flag == R_NOOVERWRITE ?
5502639ae9bSBen Gras HASH_PUTNEW : HASH_PUT, __UNCONST(key), __UNCONST(data)));
5512639ae9bSBen Gras }
5522639ae9bSBen Gras
5532639ae9bSBen Gras static int
hash_delete(const DB * dbp,const DBT * key,uint32_t flag)5542fe8fb19SBen Gras hash_delete(const DB *dbp, const DBT *key, uint32_t flag)
5552639ae9bSBen Gras {
5562639ae9bSBen Gras HTAB *hashp;
5572639ae9bSBen Gras
5582639ae9bSBen Gras hashp = dbp->internal;
5592639ae9bSBen Gras if (flag && flag != R_CURSOR) {
5602639ae9bSBen Gras hashp->err = errno = EINVAL;
5612639ae9bSBen Gras return (ERROR);
5622639ae9bSBen Gras }
5632639ae9bSBen Gras if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
5642639ae9bSBen Gras hashp->err = errno = EPERM;
5652639ae9bSBen Gras return (ERROR);
5662639ae9bSBen Gras }
5672639ae9bSBen Gras return hash_access(hashp, HASH_DELETE, __UNCONST(key), NULL);
5682639ae9bSBen Gras }
5692639ae9bSBen Gras
5702639ae9bSBen Gras /*
5712639ae9bSBen Gras * Assume that hashp has been set in wrapper routine.
5722639ae9bSBen Gras */
5732639ae9bSBen Gras static int
hash_access(HTAB * hashp,ACTION action,DBT * key,DBT * val)5742639ae9bSBen Gras hash_access(HTAB *hashp, ACTION action, DBT *key, DBT *val)
5752639ae9bSBen Gras {
5762639ae9bSBen Gras BUFHEAD *rbufp;
5772639ae9bSBen Gras BUFHEAD *bufp, *save_bufp;
5782639ae9bSBen Gras uint16_t *bp;
5792639ae9bSBen Gras int n, ndx, off;
5802639ae9bSBen Gras size_t size;
5812639ae9bSBen Gras char *kp;
5822639ae9bSBen Gras uint16_t pageno;
5832639ae9bSBen Gras
5842639ae9bSBen Gras #ifdef HASH_STATISTICS
5852639ae9bSBen Gras hash_accesses++;
5862639ae9bSBen Gras #endif
5872639ae9bSBen Gras
5882639ae9bSBen Gras off = hashp->BSIZE;
5892639ae9bSBen Gras size = key->size;
5902639ae9bSBen Gras kp = (char *)key->data;
5912639ae9bSBen Gras rbufp = __get_buf(hashp, __call_hash(hashp, kp, (int)size), NULL, 0);
5922639ae9bSBen Gras if (!rbufp)
5932639ae9bSBen Gras return (ERROR);
5942639ae9bSBen Gras save_bufp = rbufp;
5952639ae9bSBen Gras
5962639ae9bSBen Gras /* Pin the bucket chain */
5972639ae9bSBen Gras rbufp->flags |= BUF_PIN;
5982639ae9bSBen Gras for (bp = (uint16_t *)(void *)rbufp->page, n = *bp++, ndx = 1; ndx < n;)
5992639ae9bSBen Gras if (bp[1] >= REAL_KEY) {
6002639ae9bSBen Gras /* Real key/data pair */
6012639ae9bSBen Gras if (size == (size_t)(off - *bp) &&
6022639ae9bSBen Gras memcmp(kp, rbufp->page + *bp, size) == 0)
6032639ae9bSBen Gras goto found;
6042639ae9bSBen Gras off = bp[1];
6052639ae9bSBen Gras #ifdef HASH_STATISTICS
6062639ae9bSBen Gras hash_collisions++;
6072639ae9bSBen Gras #endif
6082639ae9bSBen Gras bp += 2;
6092639ae9bSBen Gras ndx += 2;
6102639ae9bSBen Gras } else if (bp[1] == OVFLPAGE) {
6112639ae9bSBen Gras rbufp = __get_buf(hashp, (uint32_t)*bp, rbufp, 0);
6122639ae9bSBen Gras if (!rbufp) {
6132639ae9bSBen Gras save_bufp->flags &= ~BUF_PIN;
6142639ae9bSBen Gras return (ERROR);
6152639ae9bSBen Gras }
6162639ae9bSBen Gras /* FOR LOOP INIT */
6172639ae9bSBen Gras bp = (uint16_t *)(void *)rbufp->page;
6182639ae9bSBen Gras n = *bp++;
6192639ae9bSBen Gras ndx = 1;
6202639ae9bSBen Gras off = hashp->BSIZE;
6212639ae9bSBen Gras } else if (bp[1] < REAL_KEY) {
6222639ae9bSBen Gras if ((ndx =
6232639ae9bSBen Gras __find_bigpair(hashp, rbufp, ndx, kp, (int)size)) > 0)
6242639ae9bSBen Gras goto found;
6252639ae9bSBen Gras if (ndx == -2) {
6262639ae9bSBen Gras bufp = rbufp;
6272639ae9bSBen Gras if (!(pageno =
6282639ae9bSBen Gras __find_last_page(hashp, &bufp))) {
6292639ae9bSBen Gras ndx = 0;
6302639ae9bSBen Gras rbufp = bufp;
6312639ae9bSBen Gras break; /* FOR */
6322639ae9bSBen Gras }
6332639ae9bSBen Gras rbufp = __get_buf(hashp, (uint32_t)pageno,
6342639ae9bSBen Gras bufp, 0);
6352639ae9bSBen Gras if (!rbufp) {
6362639ae9bSBen Gras save_bufp->flags &= ~BUF_PIN;
6372639ae9bSBen Gras return (ERROR);
6382639ae9bSBen Gras }
6392639ae9bSBen Gras /* FOR LOOP INIT */
6402639ae9bSBen Gras bp = (uint16_t *)(void *)rbufp->page;
6412639ae9bSBen Gras n = *bp++;
6422639ae9bSBen Gras ndx = 1;
6432639ae9bSBen Gras off = hashp->BSIZE;
6442639ae9bSBen Gras } else {
6452639ae9bSBen Gras save_bufp->flags &= ~BUF_PIN;
6462639ae9bSBen Gras return (ERROR);
6472639ae9bSBen Gras }
6482639ae9bSBen Gras }
6492639ae9bSBen Gras
6502639ae9bSBen Gras /* Not found */
6512639ae9bSBen Gras switch (action) {
6522639ae9bSBen Gras case HASH_PUT:
6532639ae9bSBen Gras case HASH_PUTNEW:
6542639ae9bSBen Gras if (__addel(hashp, rbufp, key, val)) {
6552639ae9bSBen Gras save_bufp->flags &= ~BUF_PIN;
6562639ae9bSBen Gras return (ERROR);
6572639ae9bSBen Gras } else {
6582639ae9bSBen Gras save_bufp->flags &= ~BUF_PIN;
6592639ae9bSBen Gras return (SUCCESS);
6602639ae9bSBen Gras }
6612639ae9bSBen Gras case HASH_GET:
6622639ae9bSBen Gras case HASH_DELETE:
6632639ae9bSBen Gras default:
6642639ae9bSBen Gras save_bufp->flags &= ~BUF_PIN;
6652639ae9bSBen Gras return (ABNORMAL);
6662639ae9bSBen Gras }
6672639ae9bSBen Gras
6682639ae9bSBen Gras found:
6692639ae9bSBen Gras switch (action) {
6702639ae9bSBen Gras case HASH_PUTNEW:
6712639ae9bSBen Gras save_bufp->flags &= ~BUF_PIN;
6722639ae9bSBen Gras return (ABNORMAL);
6732639ae9bSBen Gras case HASH_GET:
6742639ae9bSBen Gras bp = (uint16_t *)(void *)rbufp->page;
6752639ae9bSBen Gras if (bp[ndx + 1] < REAL_KEY) {
6762639ae9bSBen Gras if (__big_return(hashp, rbufp, ndx, val, 0))
6772639ae9bSBen Gras return (ERROR);
6782639ae9bSBen Gras } else {
6792639ae9bSBen Gras val->data = (uint8_t *)rbufp->page + (int)bp[ndx + 1];
6802639ae9bSBen Gras val->size = bp[ndx] - bp[ndx + 1];
6812639ae9bSBen Gras }
6822639ae9bSBen Gras break;
6832639ae9bSBen Gras case HASH_PUT:
6842639ae9bSBen Gras if ((__delpair(hashp, rbufp, ndx)) ||
6852639ae9bSBen Gras (__addel(hashp, rbufp, key, val))) {
6862639ae9bSBen Gras save_bufp->flags &= ~BUF_PIN;
6872639ae9bSBen Gras return (ERROR);
6882639ae9bSBen Gras }
6892639ae9bSBen Gras break;
6902639ae9bSBen Gras case HASH_DELETE:
6912639ae9bSBen Gras if (__delpair(hashp, rbufp, ndx))
6922639ae9bSBen Gras return (ERROR);
693*0a6a1f1dSLionel Sambuc /*
694*0a6a1f1dSLionel Sambuc * Our index lags 2 behind on the same page when we are
695*0a6a1f1dSLionel Sambuc * deleting the element pointed to by the index; otherwise
696*0a6a1f1dSLionel Sambuc * deleting randomly from an iterated hash produces undefined
697*0a6a1f1dSLionel Sambuc * results.
698*0a6a1f1dSLionel Sambuc */
699*0a6a1f1dSLionel Sambuc if (ndx != hashp->cndx - 2 || rbufp != hashp->cpage)
700*0a6a1f1dSLionel Sambuc break;
701*0a6a1f1dSLionel Sambuc
702*0a6a1f1dSLionel Sambuc if (hashp->cndx > 1) {
703*0a6a1f1dSLionel Sambuc /* Move back one element */
704*0a6a1f1dSLionel Sambuc hashp->cndx -= 2;
705*0a6a1f1dSLionel Sambuc } else {
706*0a6a1f1dSLionel Sambuc /*
707*0a6a1f1dSLionel Sambuc * Move back one page, and indicate to go to the last
708*0a6a1f1dSLionel Sambuc * element of the previous page by setting cndx to -1
709*0a6a1f1dSLionel Sambuc */
710*0a6a1f1dSLionel Sambuc hashp->cbucket--;
711*0a6a1f1dSLionel Sambuc hashp->cpage = NULL;
712*0a6a1f1dSLionel Sambuc hashp->cndx = -1;
713*0a6a1f1dSLionel Sambuc }
7142639ae9bSBen Gras break;
7152639ae9bSBen Gras default:
7162639ae9bSBen Gras abort();
7172639ae9bSBen Gras }
7182639ae9bSBen Gras save_bufp->flags &= ~BUF_PIN;
7192639ae9bSBen Gras return (SUCCESS);
7202639ae9bSBen Gras }
7212639ae9bSBen Gras
7222639ae9bSBen Gras static int
hash_seq(const DB * dbp,DBT * key,DBT * data,uint32_t flag)7232fe8fb19SBen Gras hash_seq(const DB *dbp, DBT *key, DBT *data, uint32_t flag)
7242639ae9bSBen Gras {
7252639ae9bSBen Gras uint32_t bucket;
7262639ae9bSBen Gras BUFHEAD *bufp = NULL; /* XXX: gcc */
7272639ae9bSBen Gras HTAB *hashp;
7282639ae9bSBen Gras uint16_t *bp, ndx;
7292639ae9bSBen Gras
7302639ae9bSBen Gras hashp = dbp->internal;
7312639ae9bSBen Gras if (flag && flag != R_FIRST && flag != R_NEXT) {
7322639ae9bSBen Gras hashp->err = errno = EINVAL;
7332639ae9bSBen Gras return (ERROR);
7342639ae9bSBen Gras }
7352639ae9bSBen Gras #ifdef HASH_STATISTICS
7362639ae9bSBen Gras hash_accesses++;
7372639ae9bSBen Gras #endif
7382639ae9bSBen Gras if ((hashp->cbucket < 0) || (flag == R_FIRST)) {
7392639ae9bSBen Gras hashp->cbucket = 0;
7402639ae9bSBen Gras hashp->cndx = 1;
7412639ae9bSBen Gras hashp->cpage = NULL;
7422639ae9bSBen Gras }
7432639ae9bSBen Gras
744*0a6a1f1dSLionel Sambuc next_bucket:
7452639ae9bSBen Gras for (bp = NULL; !bp || !bp[0]; ) {
7462639ae9bSBen Gras if (!(bufp = hashp->cpage)) {
7472639ae9bSBen Gras for (bucket = hashp->cbucket;
7482639ae9bSBen Gras bucket <= (uint32_t)hashp->MAX_BUCKET;
749*0a6a1f1dSLionel Sambuc bucket++) {
7502639ae9bSBen Gras bufp = __get_buf(hashp, bucket, NULL, 0);
7512639ae9bSBen Gras if (!bufp)
7522639ae9bSBen Gras return (ERROR);
7532639ae9bSBen Gras hashp->cpage = bufp;
7542639ae9bSBen Gras bp = (uint16_t *)(void *)bufp->page;
7552639ae9bSBen Gras if (bp[0])
7562639ae9bSBen Gras break;
7572639ae9bSBen Gras }
7582639ae9bSBen Gras hashp->cbucket = bucket;
7592639ae9bSBen Gras if (hashp->cbucket > hashp->MAX_BUCKET) {
7602639ae9bSBen Gras hashp->cbucket = -1;
7612639ae9bSBen Gras return (ABNORMAL);
7622639ae9bSBen Gras }
763*0a6a1f1dSLionel Sambuc if (hashp->cndx == -1) {
764*0a6a1f1dSLionel Sambuc /* move to the last element of the page */
765*0a6a1f1dSLionel Sambuc hashp->cndx = 1;
766*0a6a1f1dSLionel Sambuc while (bp[hashp->cndx - 1] != 0)
767*0a6a1f1dSLionel Sambuc hashp->cndx += 2;
768*0a6a1f1dSLionel Sambuc } else {
769*0a6a1f1dSLionel Sambuc /* start on the first element */
770*0a6a1f1dSLionel Sambuc hashp->cndx = 1;
771*0a6a1f1dSLionel Sambuc }
772*0a6a1f1dSLionel Sambuc } else {
7732639ae9bSBen Gras bp = (uint16_t *)(void *)hashp->cpage->page;
774*0a6a1f1dSLionel Sambuc if (flag == R_NEXT || flag == 0) {
775*0a6a1f1dSLionel Sambuc if (hashp->cndx > bp[0]) {
776*0a6a1f1dSLionel Sambuc hashp->cpage = NULL;
777*0a6a1f1dSLionel Sambuc hashp->cbucket++;
778*0a6a1f1dSLionel Sambuc hashp->cndx = 1;
779*0a6a1f1dSLionel Sambuc goto next_bucket;
780*0a6a1f1dSLionel Sambuc }
781*0a6a1f1dSLionel Sambuc }
782*0a6a1f1dSLionel Sambuc }
783*0a6a1f1dSLionel Sambuc
7842639ae9bSBen Gras
7852639ae9bSBen Gras _DIAGASSERT(bp != NULL);
7862639ae9bSBen Gras _DIAGASSERT(bufp != NULL);
7872639ae9bSBen Gras while (bp[hashp->cndx + 1] == OVFLPAGE) {
7882639ae9bSBen Gras bufp = hashp->cpage =
7892639ae9bSBen Gras __get_buf(hashp, (uint32_t)bp[hashp->cndx], bufp,
7902639ae9bSBen Gras 0);
7912639ae9bSBen Gras if (!bufp)
7922639ae9bSBen Gras return (ERROR);
7932639ae9bSBen Gras bp = (uint16_t *)(void *)(bufp->page);
7942639ae9bSBen Gras hashp->cndx = 1;
7952639ae9bSBen Gras }
7962639ae9bSBen Gras if (!bp[0]) {
7972639ae9bSBen Gras hashp->cpage = NULL;
7982639ae9bSBen Gras ++hashp->cbucket;
7992639ae9bSBen Gras }
8002639ae9bSBen Gras }
8012639ae9bSBen Gras ndx = hashp->cndx;
8022639ae9bSBen Gras if (bp[ndx + 1] < REAL_KEY) {
8032639ae9bSBen Gras if (__big_keydata(hashp, bufp, key, data, 1))
8042639ae9bSBen Gras return (ERROR);
8052639ae9bSBen Gras } else {
8062639ae9bSBen Gras if (hashp->cpage == NULL)
8072639ae9bSBen Gras return (ERROR);
8082639ae9bSBen Gras key->data = (uint8_t *)hashp->cpage->page + bp[ndx];
8092639ae9bSBen Gras key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
8102639ae9bSBen Gras data->data = (uint8_t *)hashp->cpage->page + bp[ndx + 1];
8112639ae9bSBen Gras data->size = bp[ndx] - bp[ndx + 1];
8122639ae9bSBen Gras }
813*0a6a1f1dSLionel Sambuc hashp->cndx += 2;
8142639ae9bSBen Gras return (SUCCESS);
8152639ae9bSBen Gras }
8162639ae9bSBen Gras
8172639ae9bSBen Gras /********************************* UTILITIES ************************/
8182639ae9bSBen Gras
8192639ae9bSBen Gras /*
8202639ae9bSBen Gras * Returns:
8212639ae9bSBen Gras * 0 ==> OK
8222639ae9bSBen Gras * -1 ==> Error
8232639ae9bSBen Gras */
8242639ae9bSBen Gras int
__expand_table(HTAB * hashp)8252639ae9bSBen Gras __expand_table(HTAB *hashp)
8262639ae9bSBen Gras {
8272639ae9bSBen Gras uint32_t old_bucket, new_bucket;
8282639ae9bSBen Gras int new_segnum, spare_ndx;
8292639ae9bSBen Gras size_t dirsize;
8302639ae9bSBen Gras
8312639ae9bSBen Gras #ifdef HASH_STATISTICS
8322639ae9bSBen Gras hash_expansions++;
8332639ae9bSBen Gras #endif
8342639ae9bSBen Gras new_bucket = ++hashp->MAX_BUCKET;
8352639ae9bSBen Gras old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
8362639ae9bSBen Gras
8372639ae9bSBen Gras new_segnum = new_bucket >> hashp->SSHIFT;
8382639ae9bSBen Gras
8392639ae9bSBen Gras /* Check if we need a new segment */
8402639ae9bSBen Gras if (new_segnum >= hashp->nsegs) {
8412639ae9bSBen Gras /* Check if we need to expand directory */
8422639ae9bSBen Gras if (new_segnum >= hashp->DSIZE) {
8432639ae9bSBen Gras /* Reallocate directory */
8442639ae9bSBen Gras dirsize = hashp->DSIZE * sizeof(SEGMENT *);
8452639ae9bSBen Gras if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1))
8462639ae9bSBen Gras return (-1);
847f14fb602SLionel Sambuc dirsize <<= 1;
848f14fb602SLionel Sambuc _DBFIT(dirsize, uint32_t);
849f14fb602SLionel Sambuc hashp->DSIZE = (uint32_t)dirsize;
8502639ae9bSBen Gras }
8512639ae9bSBen Gras if ((hashp->dir[new_segnum] =
8522639ae9bSBen Gras calloc((size_t)hashp->SGSIZE, sizeof(SEGMENT))) == NULL)
8532639ae9bSBen Gras return (-1);
8542639ae9bSBen Gras hashp->exsegs++;
8552639ae9bSBen Gras hashp->nsegs++;
8562639ae9bSBen Gras }
8572639ae9bSBen Gras /*
8582639ae9bSBen Gras * If the split point is increasing (MAX_BUCKET's log base 2
8592639ae9bSBen Gras * * increases), we need to copy the current contents of the spare
8602639ae9bSBen Gras * split bucket to the next bucket.
8612639ae9bSBen Gras */
8622639ae9bSBen Gras spare_ndx = __log2((uint32_t)(hashp->MAX_BUCKET + 1));
8632639ae9bSBen Gras if (spare_ndx > hashp->OVFL_POINT) {
8642639ae9bSBen Gras hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];
8652639ae9bSBen Gras hashp->OVFL_POINT = spare_ndx;
8662639ae9bSBen Gras }
8672639ae9bSBen Gras
8682639ae9bSBen Gras if (new_bucket > (uint32_t)hashp->HIGH_MASK) {
8692639ae9bSBen Gras /* Starting a new doubling */
8702639ae9bSBen Gras hashp->LOW_MASK = hashp->HIGH_MASK;
8712639ae9bSBen Gras hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
8722639ae9bSBen Gras }
8732639ae9bSBen Gras /* Relocate records to the new bucket */
8742639ae9bSBen Gras return (__split_page(hashp, old_bucket, new_bucket));
8752639ae9bSBen Gras }
8762639ae9bSBen Gras
8772639ae9bSBen Gras /*
8782639ae9bSBen Gras * If realloc guarantees that the pointer is not destroyed if the realloc
8792639ae9bSBen Gras * fails, then this routine can go away.
8802639ae9bSBen Gras */
8812639ae9bSBen Gras static void *
hash_realloc(SEGMENT ** p_ptr,size_t oldsize,size_t newsize)8822639ae9bSBen Gras hash_realloc(SEGMENT **p_ptr, size_t oldsize, size_t newsize)
8832639ae9bSBen Gras {
8842639ae9bSBen Gras void *p;
8852639ae9bSBen Gras
8862639ae9bSBen Gras if ((p = malloc(newsize)) != NULL) {
8872639ae9bSBen Gras memmove(p, *p_ptr, oldsize);
8882639ae9bSBen Gras memset((char *)p + oldsize, 0, newsize - oldsize);
8892639ae9bSBen Gras free(*p_ptr);
8902639ae9bSBen Gras *p_ptr = p;
8912639ae9bSBen Gras }
8922639ae9bSBen Gras return (p);
8932639ae9bSBen Gras }
8942639ae9bSBen Gras
8952639ae9bSBen Gras uint32_t
__call_hash(HTAB * hashp,char * k,int len)8962639ae9bSBen Gras __call_hash(HTAB *hashp, char *k, int len)
8972639ae9bSBen Gras {
8982639ae9bSBen Gras int n, bucket;
8992639ae9bSBen Gras
9002639ae9bSBen Gras n = hashp->hash(k, (size_t)len);
9012639ae9bSBen Gras bucket = n & hashp->HIGH_MASK;
9022639ae9bSBen Gras if (bucket > hashp->MAX_BUCKET)
9032639ae9bSBen Gras bucket = bucket & hashp->LOW_MASK;
9042639ae9bSBen Gras return (bucket);
9052639ae9bSBen Gras }
9062639ae9bSBen Gras
9072639ae9bSBen Gras /*
9082639ae9bSBen Gras * Allocate segment table. On error, destroy the table and set errno.
9092639ae9bSBen Gras *
9102639ae9bSBen Gras * Returns 0 on success
9112639ae9bSBen Gras */
9122639ae9bSBen Gras static int
alloc_segs(HTAB * hashp,int nsegs)9132639ae9bSBen Gras alloc_segs(HTAB *hashp, int nsegs)
9142639ae9bSBen Gras {
9152639ae9bSBen Gras int i;
9162639ae9bSBen Gras SEGMENT store;
9172639ae9bSBen Gras
9182639ae9bSBen Gras int save_errno;
9192639ae9bSBen Gras
9202639ae9bSBen Gras hashp->dir = calloc((size_t)hashp->DSIZE, sizeof(SEGMENT *));
9212639ae9bSBen Gras if (hashp->dir == NULL) {
9222639ae9bSBen Gras save_errno = errno;
9232639ae9bSBen Gras (void)hdestroy(hashp);
9242639ae9bSBen Gras errno = save_errno;
9252639ae9bSBen Gras return (-1);
9262639ae9bSBen Gras }
9272639ae9bSBen Gras hashp->nsegs = nsegs;
9282639ae9bSBen Gras if (nsegs == 0)
9292639ae9bSBen Gras return 0;
9302639ae9bSBen Gras /* Allocate segments */
9312639ae9bSBen Gras store = calloc((size_t)(nsegs << hashp->SSHIFT), sizeof(SEGMENT));
9322639ae9bSBen Gras if (store == NULL) {
9332639ae9bSBen Gras save_errno = errno;
9342639ae9bSBen Gras (void)hdestroy(hashp);
9352639ae9bSBen Gras errno = save_errno;
9362639ae9bSBen Gras return (-1);
9372639ae9bSBen Gras }
9382639ae9bSBen Gras for (i = 0; i < nsegs; i++)
9392639ae9bSBen Gras hashp->dir[i] = &store[i << hashp->SSHIFT];
9402639ae9bSBen Gras return (0);
9412639ae9bSBen Gras }
9422639ae9bSBen Gras
9432639ae9bSBen Gras #if BYTE_ORDER == LITTLE_ENDIAN
9442639ae9bSBen Gras /*
9452639ae9bSBen Gras * Hashp->hdr needs to be byteswapped.
9462639ae9bSBen Gras */
9472639ae9bSBen Gras static void
swap_header_copy(HASHHDR * srcp,HASHHDR * destp)9482639ae9bSBen Gras swap_header_copy(HASHHDR *srcp, HASHHDR *destp)
9492639ae9bSBen Gras {
9502639ae9bSBen Gras size_t i;
9512639ae9bSBen Gras
9522639ae9bSBen Gras P_32_COPY(srcp->magic, destp->magic);
9532639ae9bSBen Gras P_32_COPY(srcp->version, destp->version);
9542639ae9bSBen Gras P_32_COPY(srcp->lorder, destp->lorder);
9552639ae9bSBen Gras P_32_COPY(srcp->bsize, destp->bsize);
9562639ae9bSBen Gras P_32_COPY(srcp->bshift, destp->bshift);
9572639ae9bSBen Gras P_32_COPY(srcp->dsize, destp->dsize);
9582639ae9bSBen Gras P_32_COPY(srcp->ssize, destp->ssize);
9592639ae9bSBen Gras P_32_COPY(srcp->sshift, destp->sshift);
9602639ae9bSBen Gras P_32_COPY(srcp->ovfl_point, destp->ovfl_point);
9612639ae9bSBen Gras P_32_COPY(srcp->last_freed, destp->last_freed);
9622639ae9bSBen Gras P_32_COPY(srcp->max_bucket, destp->max_bucket);
9632639ae9bSBen Gras P_32_COPY(srcp->high_mask, destp->high_mask);
9642639ae9bSBen Gras P_32_COPY(srcp->low_mask, destp->low_mask);
9652639ae9bSBen Gras P_32_COPY(srcp->ffactor, destp->ffactor);
9662639ae9bSBen Gras P_32_COPY(srcp->nkeys, destp->nkeys);
9672639ae9bSBen Gras P_32_COPY(srcp->hdrpages, destp->hdrpages);
9682639ae9bSBen Gras P_32_COPY(srcp->h_charkey, destp->h_charkey);
9692639ae9bSBen Gras for (i = 0; i < NCACHED; i++) {
9702639ae9bSBen Gras P_32_COPY(srcp->spares[i], destp->spares[i]);
9712639ae9bSBen Gras P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]);
9722639ae9bSBen Gras }
9732639ae9bSBen Gras }
9742639ae9bSBen Gras
9752639ae9bSBen Gras static void
swap_header(HTAB * hashp)9762639ae9bSBen Gras swap_header(HTAB *hashp)
9772639ae9bSBen Gras {
9782639ae9bSBen Gras HASHHDR *hdrp;
9792639ae9bSBen Gras size_t i;
9802639ae9bSBen Gras
9812639ae9bSBen Gras hdrp = &hashp->hdr;
9822639ae9bSBen Gras
9832639ae9bSBen Gras M_32_SWAP(hdrp->magic);
9842639ae9bSBen Gras M_32_SWAP(hdrp->version);
9852639ae9bSBen Gras M_32_SWAP(hdrp->lorder);
9862639ae9bSBen Gras M_32_SWAP(hdrp->bsize);
9872639ae9bSBen Gras M_32_SWAP(hdrp->bshift);
9882639ae9bSBen Gras M_32_SWAP(hdrp->dsize);
9892639ae9bSBen Gras M_32_SWAP(hdrp->ssize);
9902639ae9bSBen Gras M_32_SWAP(hdrp->sshift);
9912639ae9bSBen Gras M_32_SWAP(hdrp->ovfl_point);
9922639ae9bSBen Gras M_32_SWAP(hdrp->last_freed);
9932639ae9bSBen Gras M_32_SWAP(hdrp->max_bucket);
9942639ae9bSBen Gras M_32_SWAP(hdrp->high_mask);
9952639ae9bSBen Gras M_32_SWAP(hdrp->low_mask);
9962639ae9bSBen Gras M_32_SWAP(hdrp->ffactor);
9972639ae9bSBen Gras M_32_SWAP(hdrp->nkeys);
9982639ae9bSBen Gras M_32_SWAP(hdrp->hdrpages);
9992639ae9bSBen Gras M_32_SWAP(hdrp->h_charkey);
10002639ae9bSBen Gras for (i = 0; i < NCACHED; i++) {
10012639ae9bSBen Gras M_32_SWAP(hdrp->spares[i]);
10022639ae9bSBen Gras M_16_SWAP(hdrp->bitmaps[i]);
10032639ae9bSBen Gras }
10042639ae9bSBen Gras }
10052639ae9bSBen Gras #endif
1006