GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libc/db/hash/hash.c Lines: 0 418 0.0 %
Date: 2017-11-13 Branches: 0 231 0.0 %

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