1 #pragma ident	"%Z%%M%	%I%	%E% SMI"
2 
3 
4 /*-
5  * Copyright (c) 1990, 1993, 1994
6  *	The Regents of the University of California.  All rights reserved.
7  *
8  * This code is derived from software contributed to Berkeley by
9  * Margo Seltzer.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions and the following disclaimer.
16  * 2. Redistributions in binary form must reproduce the above copyright
17  *    notice, this list of conditions and the following disclaimer in the
18  *    documentation and/or other materials provided with the distribution.
19  * 3. All advertising materials mentioning features or use of this software
20  *    must display the following acknowledgement:
21  *	This product includes software developed by the University of
22  *	California, Berkeley and its contributors.
23  * 4. Neither the name of the University nor the names of its contributors
24  *    may be used to endorse or promote products derived from this software
25  *    without specific prior written permission.
26  *
27  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37  * SUCH DAMAGE.
38  */
39 
40 #if defined(LIBC_SCCS) && !defined(lint)
41 static char sccsid[] = "@(#)hash.c	8.12 (Berkeley) 11/7/95";
42 #endif /* LIBC_SCCS and not lint */
43 
44 #undef _TS_ERRNO_
45 #include <sys/param.h>
46 #include <sys/stat.h>
47 
48 #include <errno.h>
49 #include <fcntl.h>
50 #include <stdio.h>
51 #include <stdlib.h>
52 #include <string.h>
53 #include <unistd.h>
54 #include <libintl.h>
55 #ifdef DEBUG
56 #include <assert.h>
57 #endif
58 
59 #include "db-int.h"
60 #include "hash.h"
61 #include "page.h"
62 #include "extern.h"
63 
64 static int32_t flush_meta __P((HTAB *));
65 static int32_t hash_access __P((HTAB *, ACTION, const DBT *, DBT *));
66 static int32_t hash_close __P((DB *));
67 static int32_t hash_delete __P((const DB *, const DBT *, u_int32_t));
68 static int32_t hash_fd __P((const DB *));
69 static int32_t hash_get __P((const DB *, const DBT *, DBT *, u_int32_t));
70 static int32_t hash_put __P((const DB *, DBT *, const DBT *, u_int32_t));
71 static int32_t hash_seq __P((const DB *, DBT *, DBT *, u_int32_t));
72 static int32_t hash_sync __P((const DB *, u_int32_t));
73 static int32_t hdestroy __P((HTAB *));
74 static int32_t cursor_get __P((const DB *, CURSOR *, DBT *, DBT *, \
75 	u_int32_t));
76 static int32_t cursor_delete __P((const DB *, CURSOR *, u_int32_t));
77 static HTAB *init_hash __P((HTAB *, const char *, const HASHINFO *));
78 static int32_t init_htab __P((HTAB *, int32_t));
79 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
80 static void swap_header __P((HTAB *));
81 static void swap_header_copy __P((HASHHDR *, HASHHDR *));
82 #endif
83 static u_int32_t hget_header __P((HTAB *, u_int32_t));
84 static void hput_header __P((HTAB *));
85 
86 #define RETURN_ERROR(ERR, LOC)	{ save_errno = ERR; goto LOC; }
87 
88 /* Return values */
89 #define	SUCCESS	 (0)
90 #define	ERROR	(-1)
91 #define	ABNORMAL (1)
92 
93 #ifdef HASH_STATISTICS
94 u_int32_t hash_accesses, hash_collisions, hash_expansions, hash_overflows,
95 	hash_bigpages;
96 #endif
97 
98 /************************** INTERFACE ROUTINES ***************************/
99 /* OPEN/CLOSE */
100 
101 extern DB *
102 __kdb2_hash_open(file, flags, mode, info, dflags)
103 	const char *file;
104 	int32_t flags, mode, dflags;
105 	const HASHINFO *info;	/* Special directives for create */
106 {
107 	struct stat statbuf;
108 	DB *dbp;
109 	DBT mpool_key;
110 	HTAB *hashp;
111 	int32_t bpages, csize, new_table, save_errno, specified_file;
112 
113 	if ((flags & O_ACCMODE) == O_WRONLY) {
114 		errno = EINVAL;
115 		return (NULL);
116 	}
117 	if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) {
118 		errno = ENOMEM;
119 		return (NULL);
120 	}
121 	hashp->fp = -1;
122 
123 	/* set this now, before file goes away... */
124 	specified_file = (file != NULL);
125 	if (!file) {
126 		/*
127 		 * If we are root and thus have access to /var/run, then use
128 		 * it, else tempnam(3) will use /var/tmp.
129 		 */
130 		if (!(file = tempnam("/var/run", NULL))) {
131 			/*
132 			 * No memory here is not the only failure
133 			 * possibility, but probably the most likely.
134 			 */
135 			errno = ENOMEM;
136 			free(hashp);
137 			return(NULL);
138 		}
139 
140 		/* store the file name so that we can unlink it later */
141 		hashp->fname = file;
142 #ifdef DEBUG
143 			fprintf(stderr, dgettext(TEXT_DOMAIN,
144 			"Using file name %s.\n"), file);
145 #endif
146 	}
147 	/*
148 	 * Even if user wants write only, we need to be able to read
149 	 * the actual file, so we need to open it read/write. But, the
150 	 * field in the hashp structure needs to be accurate so that
151 	 * we can check accesses.
152 	 */
153 	hashp->flags = flags;
154 	hashp->save_file = specified_file && (hashp->flags & O_RDWR);
155 
156 	new_table = 0;
157 	if (!file || (flags & O_TRUNC) ||
158 	    (stat(file, &statbuf) && (errno == ENOENT))) {
159 		if (errno == ENOENT)
160 			errno = 0;	/* In case someone looks at errno. */
161 		new_table = 1;
162 	}
163 	if (file) {
164 		if ((hashp->fp = open(file, flags|O_BINARY, mode)) == -1)
165 			RETURN_ERROR(errno, error0);
166 		(void)fcntl(hashp->fp, F_SETFD, 1);
167 	}
168 
169 	/* Process arguments to set up hash table header. */
170 	if (new_table) {
171 		if (!(hashp = init_hash(hashp, file, info)))
172 			RETURN_ERROR(errno, error1);
173 	} else {
174 		/* Table already exists */
175 		if (info && info->hash)
176 			hashp->hash = info->hash;
177 		else
178 			hashp->hash = __default_hash;
179 
180 		/* copy metadata from page into header */
181 		if (hget_header(hashp,
182 		    (info && info->bsize ? info->bsize : DEF_BUCKET_SIZE)) !=
183 		    sizeof(HASHHDR))
184 			RETURN_ERROR(EFTYPE, error1);
185 
186 		/* Verify file type, versions and hash function */
187 		if (hashp->hdr.magic != HASHMAGIC)
188 			RETURN_ERROR(EFTYPE, error1);
189 #define	OLDHASHVERSION	1
190 		if (hashp->hdr.version != HASHVERSION &&
191 		    hashp->hdr.version != OLDHASHVERSION)
192 			RETURN_ERROR(EFTYPE, error1);
193 		if (hashp->hash(CHARKEY, sizeof(CHARKEY))
194 		    != hashp->hdr.h_charkey)
195 			RETURN_ERROR(EFTYPE, error1);
196 		/*
197 		 * Figure out how many segments we need.  Max_Bucket is the
198 		 * maximum bucket number, so the number of buckets is
199 		 * max_bucket + 1.
200 		 */
201 
202 		/* Read in bitmaps */
203 		bpages = (hashp->hdr.spares[hashp->hdr.ovfl_point] +
204 		    (hashp->hdr.bsize << BYTE_SHIFT) - 1) >>
205 		    (hashp->hdr.bshift + BYTE_SHIFT);
206 
207 		hashp->nmaps = bpages;
208 		(void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_int32_t *));
209 	}
210 
211 	/* start up mpool */
212 	mpool_key.data = (u_int8_t *)file;
213 	mpool_key.size = strlen(file);
214 
215 	if (info && info->cachesize)
216 		csize = info->cachesize / hashp->hdr.bsize;
217 	else
218 		csize = DEF_CACHESIZE / hashp->hdr.bsize;
219 	hashp->mp = mpool_open(&mpool_key, hashp->fp, hashp->hdr.bsize, csize);
220 
221 	if (!hashp->mp)
222 		RETURN_ERROR(errno, error1);
223 	mpool_filter(hashp->mp, __pgin_routine, __pgout_routine, hashp);
224 
225 	/*
226 	 * For a new table, set up the bitmaps.
227 	 */
228 	if (new_table &&
229 	   init_htab(hashp, info && info->nelem ? info->nelem : 1))
230 		goto error2;
231 
232 	/* initialize the cursor queue */
233 	TAILQ_INIT(&hashp->curs_queue);
234 	hashp->seq_cursor = NULL;
235 
236 
237 	/* get a chunk of memory for our split buffer */
238 	hashp->split_buf = (PAGE16 *)malloc(hashp->hdr.bsize);
239 	if (!hashp->split_buf)
240 		goto error2;
241 
242 	hashp->new_file = new_table;
243 
244 	if (!(dbp = (DB *)malloc(sizeof(DB))))
245 		goto error2;
246 
247 	dbp->internal = hashp;
248 	dbp->close = hash_close;
249 	dbp->del = hash_delete;
250 	dbp->fd = hash_fd;
251 	dbp->get = hash_get;
252 	dbp->put = hash_put;
253 	dbp->seq = hash_seq;
254 	dbp->sync = hash_sync;
255 	dbp->type = DB_HASH;
256 
257 #ifdef DEBUG
258 	(void)fprintf(stderr,
259 	    "%s\n%s%lx\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",
260 	    "init_htab:",
261 	    "TABLE POINTER   ", (void *)hashp,
262 	    "BUCKET SIZE     ", hashp->hdr.bsize,
263 	    "BUCKET SHIFT    ", hashp->hdr.bshift,
264 	    "FILL FACTOR     ", hashp->hdr.ffactor,
265 	    "MAX BUCKET      ", hashp->hdr.max_bucket,
266 	    "OVFL POINT      ", hashp->hdr.ovfl_point,
267 	    "LAST FREED      ", hashp->hdr.last_freed,
268 	    "HIGH MASK       ", hashp->hdr.high_mask,
269 	    "LOW  MASK       ", hashp->hdr.low_mask,
270 	    "NKEYS           ", hashp->hdr.nkeys);
271 #endif
272 #ifdef HASH_STATISTICS
273 	hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
274 	hash_bigpages = 0;
275 #endif
276 	return (dbp);
277 
278 error2:
279 	hdestroy(hashp);
280 	errno = save_errno;
281 	return (NULL);
282 
283 error1:
284 	if (hashp != NULL)
285 		(void)close(hashp->fp);
286 
287 error0:
288 	if (!specified_file)
289 		free((void*)(hashp->fname)); /* SUNW14resync */
290 	free(hashp);
291 	errno = save_errno;
292 	return (NULL);
293 }
294 
295 static int32_t
296 hash_close(dbp)
297 	DB *dbp;
298 {
299 	HTAB *hashp;
300 	int32_t retval;
301 
302 	if (!dbp)
303 		return (ERROR);
304 
305 	hashp = (HTAB *)dbp->internal;
306 	retval = hdestroy(hashp);
307 	free(dbp);
308 	return (retval);
309 }
310 
311 static int32_t
312 hash_fd(dbp)
313 	const DB *dbp;
314 {
315 	HTAB *hashp;
316 
317 	if (!dbp)
318 		return (ERROR);
319 
320 	hashp = (HTAB *)dbp->internal;
321 	if (hashp->fp == -1) {
322 		errno = ENOENT;
323 		return (-1);
324 	}
325 	return (hashp->fp);
326 }
327 
328 /************************** LOCAL CREATION ROUTINES **********************/
329 static HTAB *
330 init_hash(hashp, file, info)
331 	HTAB *hashp;
332 	const char *file;
333 	const HASHINFO *info;
334 {
335 	struct stat statbuf;
336 	int32_t nelem;
337 
338 	nelem = 1;
339 	hashp->hdr.nkeys = 0;
340 	hashp->hdr.lorder = DB_BYTE_ORDER;
341 	hashp->hdr.bsize = DEF_BUCKET_SIZE;
342 	hashp->hdr.bshift = DEF_BUCKET_SHIFT;
343 	hashp->hdr.ffactor = DEF_FFACTOR;
344 	hashp->hash = __default_hash;
345 	memset(hashp->hdr.spares, 0, sizeof(hashp->hdr.spares));
346 	memset(hashp->hdr.bitmaps, 0, sizeof(hashp->hdr.bitmaps));
347 
348 	/* Fix bucket size to be optimal for file system */
349 	if (file != NULL) {
350 		if (stat(file, &statbuf))
351 			return (NULL);
352 		hashp->hdr.bsize = statbuf.st_blksize;
353 		hashp->hdr.bshift = __log2(hashp->hdr.bsize);
354 	}
355 	if (info) {
356 		if (info->bsize) {
357 			/* Round pagesize up to power of 2 */
358 			hashp->hdr.bshift = __log2(info->bsize);
359 			hashp->hdr.bsize = 1 << hashp->hdr.bshift;
360 			if (hashp->hdr.bsize > MAX_BSIZE) {
361 				errno = EINVAL;
362 				return (NULL);
363 			}
364 		}
365 		if (info->ffactor)
366 			hashp->hdr.ffactor = info->ffactor;
367 		if (info->hash)
368 			hashp->hash = info->hash;
369 		if (info->lorder) {
370 			if ((info->lorder != DB_BIG_ENDIAN) &&
371 			    (info->lorder != DB_LITTLE_ENDIAN)) {
372 				errno = EINVAL;
373 				return (NULL);
374 			}
375 			hashp->hdr.lorder = info->lorder;
376 		}
377 	}
378 	return (hashp);
379 }
380 
381 /*
382  * Returns 0 on No Error
383  */
384 static int32_t
385 init_htab(hashp, nelem)
386 	HTAB *hashp;
387 	int32_t nelem;
388 {
389 	int32_t l2, nbuckets;
390 
391 	/*
392 	 * Divide number of elements by the fill factor and determine a
393 	 * desired number of buckets.  Allocate space for the next greater
394 	 * power of two number of buckets.
395 	 */
396 	nelem = (nelem - 1) / hashp->hdr.ffactor + 1;
397 
398 	l2 = __log2(MAX(nelem, 2));
399 	nbuckets = 1 << l2;
400 
401 	hashp->hdr.spares[l2] = l2 + 1;
402 	hashp->hdr.spares[l2 + 1] = l2 + 1;
403 	hashp->hdr.ovfl_point = l2;
404 	hashp->hdr.last_freed = 2;
405 
406 	hashp->hdr.max_bucket = hashp->hdr.low_mask = nbuckets - 1;
407 	hashp->hdr.high_mask = (nbuckets << 1) - 1;
408 
409 	/*
410 	 * The number of header pages is the size of the header divided by
411 	 * the amount of freespace on header pages (the page size - the
412 	 * size of 1 integer where the length of the header info on that
413 	 * page is stored) plus another page if it didn't divide evenly.
414 	 */
415 	hashp->hdr.hdrpages =
416 	    (sizeof(HASHHDR) / (hashp->hdr.bsize - HEADER_OVERHEAD)) +
417 	    (((sizeof(HASHHDR) % (hashp->hdr.bsize - HEADER_OVERHEAD)) == 0)
418 	    ? 0 : 1);
419 
420 	/* Create pages for these buckets */
421 	/*
422 	for (i = 0; i <= hashp->hdr.max_bucket; i++) {
423 		if (__new_page(hashp, (u_int32_t)i, A_BUCKET) != 0)
424 			return (-1);
425 	}
426 	*/
427 
428 	/* First bitmap page is at: splitpoint l2 page offset 1 */
429 	if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))
430 		return (-1);
431 
432 	return (0);
433 }
434 
435 /*
436  * Functions to get/put hash header.  We access the file directly.
437  */
438 static u_int32_t
439 hget_header(hashp, page_size)
440 	HTAB *hashp;
441 	u_int32_t page_size;
442 {
443 	u_int32_t num_copied, i;
444 	u_int8_t *hdr_dest;
445 
446 	num_copied = 0;
447 	i = 0;
448 
449 	hdr_dest = (u_int8_t *)&hashp->hdr;
450 
451 	/*
452 	 * XXX
453 	 * This should not be printing to stderr on a "normal" error case.
454 	 */
455 	lseek(hashp->fp, 0, SEEK_SET);
456 	num_copied = read(hashp->fp, hdr_dest, sizeof(HASHHDR));
457 	if (num_copied != sizeof(HASHHDR)) {
458 		fprintf(stderr, dgettext(TEXT_DOMAIN,
459 			"hash: could not retrieve header"));
460 		return (0);
461 	}
462 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
463 	swap_header(hashp);
464 #endif
465 	return (num_copied);
466 }
467 
468 static void
469 hput_header(hashp)
470 	HTAB *hashp;
471 {
472 	HASHHDR *whdrp;
473 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
474 	HASHHDR whdr;
475 #endif
476 	u_int32_t num_copied, i;
477 
478 	num_copied = i = 0;
479 
480 	whdrp = &hashp->hdr;
481 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
482 	whdrp = &whdr;
483 	swap_header_copy(&hashp->hdr, whdrp);
484 #endif
485 
486 	lseek(hashp->fp, 0, SEEK_SET);
487 	num_copied = write(hashp->fp, whdrp, sizeof(HASHHDR));
488 	if (num_copied != sizeof(HASHHDR))
489 		(void)fprintf(stderr, dgettext(TEXT_DOMAIN,
490 			"hash: could not write hash header"));
491 	return;
492 }
493 
494 /********************** DESTROY/CLOSE ROUTINES ************************/
495 
496 /*
497  * Flushes any changes to the file if necessary and destroys the hashp
498  * structure, freeing all allocated space.
499  */
500 static int32_t
501 hdestroy(hashp)
502 	HTAB *hashp;
503 {
504 	int32_t save_errno;
505 
506 	save_errno = 0;
507 
508 #ifdef HASH_STATISTICS
509 	{ int i;
510 	(void)fprintf(stderr, dgettext(TEXT_DOMAIN,
511 			"hdestroy: accesses %ld collisions %ld\n"),
512 	    hash_accesses, hash_collisions);
513 	(void)fprintf(stderr,
514 	   dgettext(TEXT_DOMAIN,
515 			 "hdestroy: expansions %ld\n"), hash_expansions);
516 	(void)fprintf(stderr,
517 	    dgettext(TEXT_DOMAIN,
518 			"hdestroy: overflows %ld\n"), hash_overflows);
519 	(void)fprintf(stderr,
520 	    dgettext(TEXT_DOMAIN,
521 			"hdestroy: big key/data pages %ld\n"), hash_bigpages);
522 	(void)fprintf(stderr,
523 	    "keys %ld maxp %d\n", hashp->hdr.nkeys, hashp->hdr.max_bucket);
524 
525 	for (i = 0; i < NCACHED; i++)
526 		(void)fprintf(stderr,
527 		    "spares[%d] = %d\n", i, hashp->hdr.spares[i]);
528 	}
529 #endif
530 
531 	if (flush_meta(hashp) && !save_errno)
532 		save_errno = errno;
533 
534 	/* Free the split page */
535 	if (hashp->split_buf)
536 		free(hashp->split_buf);
537 
538 	/* Free the big key and big data returns */
539 	if (hashp->bigkey_buf)
540 		free(hashp->bigkey_buf);
541 	if (hashp->bigdata_buf)
542 		free(hashp->bigdata_buf);
543 
544 	/* XXX This should really iterate over the cursor queue, but
545 	   it's not clear how to do that, and the only cursor a hash
546 	   table ever creates is the one used by hash_seq().  Passing
547 	   NULL as the first arg is also a kludge, but I know that
548 	   it's never used, so I do it.  The intent is to plug the
549 	   memory leak.  Correctness can come later. */
550 
551 	if (hashp->seq_cursor)
552 		hashp->seq_cursor->delete(NULL, hashp->seq_cursor, 0);
553 
554 	/* shut down mpool */
555 	mpool_sync(hashp->mp);
556 	mpool_close(hashp->mp);
557 
558 	if (hashp->fp != -1)
559 		(void)close(hashp->fp);
560 
561 	/*
562 	 * *** This may cause problems if hashp->fname is set in any case
563 	 * other than the case that we are generating a temporary file name.
564 	 * Note that the new version of mpool should support temporary
565 	 * files within mpool itself.
566 	 */
567 	if (hashp->fname && !hashp->save_file) {
568 #ifdef DEBUG
569 		fprintf(stderr, dgettext(TEXT_DOMAIN,
570 			"Unlinking file %s.\n"), hashp->fname);
571 #endif
572 		/* we need to chmod the file to allow it to be deleted... */
573 		chmod(hashp->fname, 0700);
574 		unlink(hashp->fname);
575 		/* destroy the temporary name */
576 		free((void *)(hashp->fname)); /* SUNW14resync */
577 	}
578 	free(hashp);
579 
580 	if (save_errno) {
581 		errno = save_errno;
582 		return (ERROR);
583 	}
584 	return (SUCCESS);
585 }
586 
587 /*
588  * Write modified pages to disk
589  *
590  * Returns:
591  *	 0 == OK
592  *	-1 ERROR
593  */
594 static int32_t
595 hash_sync(dbp, flags)
596 	const DB *dbp;
597 	u_int32_t flags;
598 {
599 	HTAB *hashp;
600 
601 	hashp = (HTAB *)dbp->internal;
602 
603 	/*
604 	 * XXX
605 	 * Check success/failure conditions.
606 	 */
607 	return (flush_meta(hashp) || mpool_sync(hashp->mp));
608 }
609 
610 /*
611  * Returns:
612  *	 0 == OK
613  *	-1 indicates that errno should be set
614  */
615 static int32_t
616 flush_meta(hashp)
617 	HTAB *hashp;
618 {
619 	int32_t i;
620 
621 	if (!hashp->save_file)
622 		return (0);
623 	hashp->hdr.magic = HASHMAGIC;
624 	hashp->hdr.version = HASHVERSION;
625 	hashp->hdr.h_charkey = hashp->hash(CHARKEY, sizeof(CHARKEY));
626 
627 	/* write out metadata */
628 	hput_header(hashp);
629 
630 	for (i = 0; i < NCACHED; i++)
631 		if (hashp->mapp[i]) {
632 			if (__put_page(hashp,
633 			    (PAGE16 *)hashp->mapp[i], A_BITMAP, 1))
634 				return (-1);
635 			hashp->mapp[i] = NULL;
636 		}
637 	return (0);
638 }
639 
640 /*******************************SEARCH ROUTINES *****************************/
641 /*
642  * All the access routines return
643  *
644  * Returns:
645  *	 0 on SUCCESS
646  *	 1 to indicate an external ERROR (i.e. key not found, etc)
647  *	-1 to indicate an internal ERROR (i.e. out of memory, etc)
648  */
649 
650 /* *** make sure this is true! */
651 
652 static int32_t
653 hash_get(dbp, key, data, flag)
654 	const DB *dbp;
655 	const DBT *key;
656 	DBT *data;
657 	u_int32_t flag;
658 {
659 	HTAB *hashp;
660 
661 	hashp = (HTAB *)dbp->internal;
662 	if (flag) {
663 		hashp->local_errno = errno = EINVAL;
664 		return (ERROR);
665 	}
666 	return (hash_access(hashp, HASH_GET, key, data));
667 }
668 
669 static int32_t
670 hash_put(dbp, key, data, flag)
671 	const DB *dbp;
672 	DBT *key;
673 	const DBT *data;
674 	u_int32_t flag;
675 {
676 	HTAB *hashp;
677 
678 	hashp = (HTAB *)dbp->internal;
679 	if (flag && flag != R_NOOVERWRITE) {
680 		hashp->local_errno = errno = EINVAL;
681 		return (ERROR);
682 	}
683 	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
684 		hashp->local_errno = errno = EPERM;
685 		return (ERROR);
686 	}
687 	return (hash_access(hashp, flag == R_NOOVERWRITE ?
688 		HASH_PUTNEW : HASH_PUT, key, (DBT *)data));
689 }
690 
691 static int32_t
692 hash_delete(dbp, key, flag)
693 	const DB *dbp;
694 	const DBT *key;
695 	u_int32_t flag;		/* Ignored */
696 {
697 	HTAB *hashp;
698 
699 	hashp = (HTAB *)dbp->internal;
700 	if (flag) {
701 		hashp->local_errno = errno = EINVAL;
702 		return (ERROR);
703 	}
704 	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
705 		hashp->local_errno = errno = EPERM;
706 		return (ERROR);
707 	}
708 
709 	return (hash_access(hashp, HASH_DELETE, key, NULL));
710 }
711 
712 /*
713  * Assume that hashp has been set in wrapper routine.
714  */
715 static int32_t
716 hash_access(hashp, action, key, val)
717 	HTAB *hashp;
718 	ACTION action;
719 	const DBT *key;
720 	DBT *val;
721 {
722 	DBT page_key, page_val;
723 	CURSOR cursor;
724 	ITEM_INFO item_info;
725 	u_int32_t bucket;
726 	u_int32_t num_items;
727 
728 #ifdef HASH_STATISTICS
729 	hash_accesses++;
730 #endif
731 
732 	num_items = 0;
733 
734 	/*
735 	 * Set up item_info so that we're looking for space to add an item
736 	 * as we cycle through the pages looking for the key.
737 	 */
738 	if (action == HASH_PUT || action == HASH_PUTNEW) {
739 		if (ISBIG(key->size + val->size, hashp))
740 			item_info.seek_size = PAIR_OVERHEAD;
741 		else
742 			item_info.seek_size = key->size + val->size;
743 	} else
744 		item_info.seek_size = 0;
745 	item_info.seek_found_page = 0;
746 
747 	bucket = __call_hash(hashp, (int8_t *)key->data, key->size);
748 
749 	cursor.pagep = NULL;
750 	__get_item_reset(hashp, &cursor);
751 
752 	cursor.bucket = bucket;
753 	while (1) {
754 		__get_item_next(hashp, &cursor, &page_key, &page_val, &item_info);
755 		if (item_info.status == ITEM_ERROR)
756 			return (ABNORMAL);
757 		if (item_info.status == ITEM_NO_MORE)
758 			break;
759 		num_items++;
760 		if (item_info.key_off == BIGPAIR) {
761 			/*
762 			 * !!!
763 			 * 0 is a valid index.
764 			 */
765 			if (__find_bigpair(hashp, &cursor, (int8_t *)key->data,
766 			    key->size) > 0)
767 				goto found;
768 		} else if (key->size == page_key.size &&
769 		    !memcmp(key->data, page_key.data, key->size))
770 			goto found;
771 	}
772 #ifdef HASH_STATISTICS
773 	hash_collisions++;
774 #endif
775 	__get_item_done(hashp, &cursor);
776 
777 	/*
778 	 * At this point, item_info will list either the last page in
779 	 * the chain, or the last page in the chain plus a pgno for where
780 	 * to find the first page in the chain with space for the
781 	 * item we wish to add.
782 	 */
783 
784 	/* Not found */
785 	switch (action) {
786 	case HASH_PUT:
787 	case HASH_PUTNEW:
788 		if (__addel(hashp, &item_info, key, val, num_items, 0))
789 			return (ERROR);
790 		break;
791 	case HASH_GET:
792 	case HASH_DELETE:
793 	default:
794 		return (ABNORMAL);
795 	}
796 
797 	if (item_info.caused_expand)
798 		__expand_table(hashp);
799 	return (SUCCESS);
800 
801 found:	__get_item_done(hashp, &cursor);
802 
803 	switch (action) {
804 	case HASH_PUTNEW:
805 		/* mpool_put(hashp->mp, pagep, 0); */
806 		return (ABNORMAL);
807 	case HASH_GET:
808 		if (item_info.key_off == BIGPAIR) {
809 			if (__big_return(hashp, &item_info, val, 0))
810 				return (ERROR);
811 		} else {
812 			val->data = page_val.data;
813 			val->size = page_val.size;
814 		}
815 		/* *** data may not be available! */
816 		break;
817 	case HASH_PUT:
818 		if (__delpair(hashp, &cursor, &item_info) ||
819 		    __addel(hashp, &item_info, key, val, UNKNOWN, 0))
820 			return (ERROR);
821 		__get_item_done(hashp, &cursor);
822 		if (item_info.caused_expand)
823 			__expand_table(hashp);
824 		break;
825 	case HASH_DELETE:
826 		if (__delpair(hashp, &cursor, &item_info))
827 			return (ERROR);
828 		break;
829 	default:
830 		abort();
831 	}
832 	return (SUCCESS);
833 }
834 
835 /* ****************** CURSORS ********************************** */
836 CURSOR *
837 __cursor_creat(dbp)
838 	const DB *dbp;
839 {
840 	CURSOR *new_curs;
841 	HTAB *hashp;
842 
843 	new_curs = (CURSOR *)malloc(sizeof(struct cursor_t));
844 	if (!new_curs)
845 		return NULL;
846 	new_curs->internal =
847 	    (struct item_info *)malloc(sizeof(struct item_info));
848 	if (!new_curs->internal) {
849 		free(new_curs);
850 		return NULL;
851 	}
852 	new_curs->get = cursor_get;
853 	new_curs->delete = cursor_delete;
854 
855 	new_curs->bucket = 0;
856 	new_curs->pgno = INVALID_PGNO;
857 	new_curs->ndx = 0;
858 	new_curs->pgndx = 0;
859 	new_curs->pagep = NULL;
860 
861 	/* place onto queue of cursors */
862 	hashp = (HTAB *)dbp->internal;
863 	TAILQ_INSERT_TAIL(&hashp->curs_queue, new_curs, queue);
864 
865 	return new_curs;
866 }
867 
868 static int32_t
869 cursor_get(dbp, cursorp, key, val, flags)
870 	const DB *dbp;
871 	CURSOR *cursorp;
872 	DBT *key, *val;
873 	u_int32_t flags;
874 {
875 	HTAB *hashp;
876 	ITEM_INFO item_info;
877 
878 	hashp = (HTAB *)dbp->internal;
879 
880 	if (flags && flags != R_FIRST && flags != R_NEXT) {
881 		hashp->local_errno = errno = EINVAL;
882 		return (ERROR);
883 	}
884 #ifdef HASH_STATISTICS
885 	hash_accesses++;
886 #endif
887 
888 	item_info.seek_size = 0;
889 
890 	if (flags == R_FIRST)
891 		__get_item_first(hashp, cursorp, key, val, &item_info);
892 	else
893 		__get_item_next(hashp, cursorp, key, val, &item_info);
894 
895 	/*
896 	 * This needs to be changed around.  As is, get_item_next advances
897 	 * the pointers on the page but this function actually advances
898 	 * bucket pointers.  This works, since the only other place we
899 	 * use get_item_next is in hash_access which only deals with one
900 	 * bucket at a time.  However, there is the problem that certain other
901 	 * functions (such as find_bigpair and delpair) depend on the
902 	 * pgndx member of the cursor.  Right now, they are using pngdx - 1
903 	 * since indices refer to the __next__ item that is to be fetched
904 	 * from the page.  This is ugly, as you may have noticed, whoever
905 	 * you are.  The best solution would be to depend on item_infos to
906 	 * deal with _current_ information, and have the cursors only
907 	 * deal with _next_ information.  In that scheme, get_item_next
908 	 * would also advance buckets.  Version 3...
909 	 */
910 
911 
912 	/*
913 	 * Must always enter this loop to do error handling and
914 	 * check for big key/data pair.
915 	 */
916 	while (1) {
917 		if (item_info.status == ITEM_OK) {
918 			if (item_info.key_off == BIGPAIR &&
919 			    __big_keydata(hashp, cursorp->pagep, key, val,
920 			    item_info.pgndx))
921 				return (ABNORMAL);
922 
923 			break;
924 		} else if (item_info.status != ITEM_NO_MORE)
925 			return (ABNORMAL);
926 
927 		__put_page(hashp, cursorp->pagep, A_RAW, 0);
928 		cursorp->ndx = cursorp->pgndx = 0;
929 		cursorp->bucket++;
930 		cursorp->pgno = INVALID_PGNO;
931 		cursorp->pagep = NULL;
932 		if (cursorp->bucket > hashp->hdr.max_bucket)
933 			return (ABNORMAL);
934 		__get_item_next(hashp, cursorp, key, val, &item_info);
935 	}
936 
937 	__get_item_done(hashp, cursorp);
938 	return (0);
939 }
940 
941 static int32_t
942 cursor_delete(dbp, cursor, flags)
943 	const DB *dbp;
944 	CURSOR *cursor;
945 	u_int32_t flags;
946 {
947 	/* XXX this is empirically determined, so it might not be completely
948 	   correct, but it seems to work.  At the very least it fixes
949 	   a memory leak */
950 
951 	free(cursor->internal);
952 	free(cursor);
953 
954 	return (0);
955 }
956 
957 static int32_t
958 hash_seq(dbp, key, val, flag)
959 	const DB *dbp;
960 	DBT *key, *val;
961 	u_int32_t flag;
962 {
963 	HTAB *hashp;
964 
965 	/*
966 	 * Seq just uses the default cursor to go sequecing through the
967 	 * database.  Note that the default cursor is the first in the list.
968 	 */
969 
970 	hashp = (HTAB *)dbp->internal;
971 	if (!hashp->seq_cursor)
972 		hashp->seq_cursor = __cursor_creat(dbp);
973 
974 	return (hashp->seq_cursor->get(dbp, hashp->seq_cursor, key, val, flag));
975 }
976 
977 /********************************* UTILITIES ************************/
978 
979 /*
980  * Returns:
981  *	 0 ==> OK
982  *	-1 ==> Error
983  */
984 int32_t
985 __expand_table(hashp)
986 	HTAB *hashp;
987 {
988 	u_int32_t old_bucket, new_bucket;
989 	int32_t spare_ndx;
990 
991 #ifdef HASH_STATISTICS
992 	hash_expansions++;
993 #endif
994 	new_bucket = ++hashp->hdr.max_bucket;
995 	old_bucket = (hashp->hdr.max_bucket & hashp->hdr.low_mask);
996 
997 	/* Get a page for this new bucket */
998 	if (__new_page(hashp, new_bucket, A_BUCKET) != 0)
999 		return (-1);
1000 
1001 	/*
1002 	 * If the split point is increasing (hdr.max_bucket's log base 2
1003 	 * increases), we need to copy the current contents of the spare
1004 	 * split bucket to the next bucket.
1005 	 */
1006 	spare_ndx = __log2(hashp->hdr.max_bucket + 1);
1007 	if (spare_ndx > hashp->hdr.ovfl_point) {
1008 		hashp->hdr.spares[spare_ndx] = hashp->hdr.spares[hashp->hdr.ovfl_point];
1009 		hashp->hdr.ovfl_point = spare_ndx;
1010 	}
1011 	if (new_bucket > hashp->hdr.high_mask) {
1012 		/* Starting a new doubling */
1013 		hashp->hdr.low_mask = hashp->hdr.high_mask;
1014 		hashp->hdr.high_mask = new_bucket | hashp->hdr.low_mask;
1015 	}
1016 	if (BUCKET_TO_PAGE(new_bucket) > MAX_PAGES(hashp)) {
1017 		fprintf(stderr,dgettext(TEXT_DOMAIN,
1018 			 "hash: Cannot allocate new bucket.  Pages exhausted.\n"));
1019 		return (-1);
1020 	}
1021 	/* Relocate records to the new bucket */
1022 	return (__split_page(hashp, old_bucket, new_bucket));
1023 }
1024 
1025 u_int32_t
1026 __call_hash(hashp, k, len)
1027 	HTAB *hashp;
1028 	int8_t *k;
1029 	int32_t len;
1030 {
1031 	int32_t n, bucket;
1032 
1033 	n = hashp->hash(k, len);
1034 	bucket = n & hashp->hdr.high_mask;
1035 	if (bucket > hashp->hdr.max_bucket)
1036 		bucket = bucket & hashp->hdr.low_mask;
1037 	return (bucket);
1038 }
1039 
1040 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
1041 /*
1042  * Hashp->hdr needs to be byteswapped.
1043  */
1044 static void
1045 swap_header_copy(srcp, destp)
1046 	HASHHDR *srcp, *destp;
1047 {
1048 	int32_t i;
1049 
1050 	P_32_COPY(srcp->magic, destp->magic);
1051 	P_32_COPY(srcp->version, destp->version);
1052 	P_32_COPY(srcp->lorder, destp->lorder);
1053 	P_32_COPY(srcp->bsize, destp->bsize);
1054 	P_32_COPY(srcp->bshift, destp->bshift);
1055 	P_32_COPY(srcp->ovfl_point, destp->ovfl_point);
1056 	P_32_COPY(srcp->last_freed, destp->last_freed);
1057 	P_32_COPY(srcp->max_bucket, destp->max_bucket);
1058 	P_32_COPY(srcp->high_mask, destp->high_mask);
1059 	P_32_COPY(srcp->low_mask, destp->low_mask);
1060 	P_32_COPY(srcp->ffactor, destp->ffactor);
1061 	P_32_COPY(srcp->nkeys, destp->nkeys);
1062 	P_32_COPY(srcp->hdrpages, destp->hdrpages);
1063 	P_32_COPY(srcp->h_charkey, destp->h_charkey);
1064 	for (i = 0; i < NCACHED; i++) {
1065 		P_32_COPY(srcp->spares[i], destp->spares[i]);
1066 		P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]);
1067 	}
1068 }
1069 
1070 static void
1071 swap_header(hashp)
1072 	HTAB *hashp;
1073 {
1074 	HASHHDR *hdrp;
1075 	int32_t i;
1076 
1077 	hdrp = &hashp->hdr;
1078 
1079 	M_32_SWAP(hdrp->magic);
1080 	M_32_SWAP(hdrp->version);
1081 	M_32_SWAP(hdrp->lorder);
1082 	M_32_SWAP(hdrp->bsize);
1083 	M_32_SWAP(hdrp->bshift);
1084 	M_32_SWAP(hdrp->ovfl_point);
1085 	M_32_SWAP(hdrp->last_freed);
1086 	M_32_SWAP(hdrp->max_bucket);
1087 	M_32_SWAP(hdrp->high_mask);
1088 	M_32_SWAP(hdrp->low_mask);
1089 	M_32_SWAP(hdrp->ffactor);
1090 	M_32_SWAP(hdrp->nkeys);
1091 	M_32_SWAP(hdrp->hdrpages);
1092 	M_32_SWAP(hdrp->h_charkey);
1093 	for (i = 0; i < NCACHED; i++) {
1094 		M_32_SWAP(hdrp->spares[i]);
1095 		M_16_SWAP(hdrp->bitmaps[i]);
1096 	}
1097 }
1098 #endif /* DB_BYTE_ORDER == DB_LITTLE_ENDIAN */
1099