1/*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 1996,2008 Oracle.  All rights reserved.
5 *
6 * $Id: db_shash.c,v 12.8 2008/01/08 20:58:08 bostic Exp $
7 */
8
9#include "db_config.h"
10
11#include "db_int.h"
12
13/*
14 * __db_tablesize --
15 *	Choose a size for the hash table.
16 *
17 * PUBLIC: u_int32_t __db_tablesize __P((u_int32_t));
18 */
19u_int32_t
20__db_tablesize(n_buckets)
21	u_int32_t n_buckets;
22{
23	/*
24	 * We try to be clever about how big we make the hash tables.  Use a
25	 * prime number close to the "suggested" number of elements that will
26	 * be in the hash table.  Use 32 as the minimum hash table size.
27	 *
28	 * Ref: Sedgewick, Algorithms in C, "Hash Functions"
29	 *
30	 * Up to ~250,000 buckets, we use powers of 2.  After that, we slow
31	 * the rate of increase by half.  For each choice, we then use a
32	 * nearby prime number as the hash value.
33	 *
34	 * If a terabyte is the maximum cache we'll see, and we assume there
35	 * are 10 1K buckets on each hash chain, then 107374182 is the maximum
36	 * number of buckets we'll ever need.
37	 *
38	 * We don't use the obvious static data structure because some C
39	 * compilers (and I use the term loosely), can't handle them.
40	 */
41#define	HASH_SIZE(power, prime) {					\
42	if ((power) >= n_buckets)					\
43		return (prime);						\
44}
45	HASH_SIZE(32, 37);			/* 2^5 */
46	HASH_SIZE(64, 67);			/* 2^6 */
47	HASH_SIZE(128, 131);			/* 2^7 */
48	HASH_SIZE(256, 257);			/* 2^8 */
49	HASH_SIZE(512, 521);			/* 2^9 */
50	HASH_SIZE(1024, 1031);			/* 2^10 */
51	HASH_SIZE(2048, 2053);			/* 2^11 */
52	HASH_SIZE(4096, 4099);			/* 2^12 */
53	HASH_SIZE(8192, 8191);			/* 2^13 */
54	HASH_SIZE(16384, 16381);		/* 2^14 */
55	HASH_SIZE(32768, 32771);		/* 2^15 */
56	HASH_SIZE(65536, 65537);		/* 2^16 */
57	HASH_SIZE(131072, 131071);		/* 2^17 */
58	HASH_SIZE(262144, 262147);		/* 2^18 */
59	HASH_SIZE(393216, 393209);		/* 2^18 + 2^18/2 */
60	HASH_SIZE(524288, 524287);		/* 2^19 */
61	HASH_SIZE(786432, 786431);		/* 2^19 + 2^19/2 */
62	HASH_SIZE(1048576, 1048573);		/* 2^20 */
63	HASH_SIZE(1572864, 1572869);		/* 2^20 + 2^20/2 */
64	HASH_SIZE(2097152, 2097169);		/* 2^21 */
65	HASH_SIZE(3145728, 3145721);		/* 2^21 + 2^21/2 */
66	HASH_SIZE(4194304, 4194301);		/* 2^22 */
67	HASH_SIZE(6291456, 6291449);		/* 2^22 + 2^22/2 */
68	HASH_SIZE(8388608, 8388617);		/* 2^23 */
69	HASH_SIZE(12582912, 12582917);		/* 2^23 + 2^23/2 */
70	HASH_SIZE(16777216, 16777213);		/* 2^24 */
71	HASH_SIZE(25165824, 25165813);		/* 2^24 + 2^24/2 */
72	HASH_SIZE(33554432, 33554393);		/* 2^25 */
73	HASH_SIZE(50331648, 50331653);		/* 2^25 + 2^25/2 */
74	HASH_SIZE(67108864, 67108859);		/* 2^26 */
75	HASH_SIZE(100663296, 100663291);	/* 2^26 + 2^26/2 */
76	HASH_SIZE(134217728, 134217757);	/* 2^27 */
77	HASH_SIZE(201326592, 201326611);	/* 2^27 + 2^27/2 */
78	HASH_SIZE(268435456, 268435459);	/* 2^28 */
79	HASH_SIZE(402653184, 402653189);	/* 2^28 + 2^28/2 */
80	HASH_SIZE(536870912, 536870909);	/* 2^29 */
81	HASH_SIZE(805306368, 805306357);	/* 2^29 + 2^29/2 */
82	HASH_SIZE(1073741824, 1073741827);	/* 2^30 */
83	return (1073741827);
84}
85
86/*
87 * __db_hashinit --
88 *	Initialize a hash table that resides in shared memory.
89 *
90 * PUBLIC: void __db_hashinit __P((void *, u_int32_t));
91 */
92void
93__db_hashinit(begin, nelements)
94	void *begin;
95	u_int32_t nelements;
96{
97	u_int32_t i;
98	SH_TAILQ_HEAD(hash_head) *headp;
99
100	headp = (struct hash_head *)begin;
101
102	for (i = 0; i < nelements; i++, headp++)
103		SH_TAILQ_INIT(headp);
104}
105