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