xref: /minix3/lib/libc/db/hash/hash.c (revision 0a6a1f1d05b60e214de2f05a7310ddd1f0e590e7)
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