about summary refs log tree commit diff
path: root/db2/common/db_shash.c
blob: ab188f564f99a5bf8c749bd8f04149181b385985 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*-
 * See the file LICENSE for redistribution information.
 *
 * Copyright (c) 1996, 1997
 *	Sleepycat Software.  All rights reserved.
 */

#include "config.h"

#ifndef lint
static const char sccsid[] = "@(#)db_shash.c	10.4 (Sleepycat) 1/8/98";
#endif /* not lint */

#ifndef NO_SYSTEM_INCLUDES
#include <sys/types.h>
#endif

#include "db_int.h"
#include "shqueue.h"
#include "common_ext.h"

/* Powers-of-2 and close-by prime number pairs. */
static const struct {
	u_int	power;
	u_int	prime;
} list[] = {
	{  64,	  67},
	{ 128,	 131},
	{ 256,	 257},
	{ 512,	 521},
	{1024,	1031},
	{2048,	2053},
	{4096,	4099},
	{8192,	8191},
	{0,	   0}
};

/*
 * __db_tablesize --
 *	Choose a size for the hash table.
 *
 * PUBLIC: int __db_tablesize __P((u_int));
 */
int
__db_tablesize(n_buckets)
	u_int n_buckets;
{
	int i;

	/*
	 * We try to be clever about how big we make the hash tables.  Pick
	 * a prime number close to the "suggested" number of elements that
	 * will be in the hash table.  We shoot for minimum collisions (i.e.
	 * one element in each bucket).  We use 64 as the minimum table size.
	 *
	 * Ref: Sedgewick, Algorithms in C, "Hash Functions"
	 */
	if (n_buckets < 64)
		n_buckets = 64;

	for (i = 0;; ++i) {
		if (list[i].power == 0) {
			--i;
			break;
		}
		if (list[i].power >= n_buckets)
			break;
	}
	return (list[i].prime);
}

/*
 * __db_hashinit --
 *	Initialize a hash table that resides in shared memory.
 *
 * PUBLIC: void __db_hashinit __P((void *, int));
 */
void
__db_hashinit(begin, nelements)
	void *begin;
	int nelements;
{
	int i;
	SH_TAILQ_HEAD(hash_head) *headp;

	headp = (struct hash_head *)begin;

	for (i = 0; i < nelements; i++, headp++)
		SH_TAILQ_INIT(headp);
}