1*7c478bd9Sstevel@tonic-gate /*-
2*7c478bd9Sstevel@tonic-gate * See the file LICENSE for redistribution information.
3*7c478bd9Sstevel@tonic-gate *
4*7c478bd9Sstevel@tonic-gate * Copyright (c) 1996, 1997, 1998
5*7c478bd9Sstevel@tonic-gate * Sleepycat Software. All rights reserved.
6*7c478bd9Sstevel@tonic-gate */
7*7c478bd9Sstevel@tonic-gate
8*7c478bd9Sstevel@tonic-gate #include "config.h"
9*7c478bd9Sstevel@tonic-gate
10*7c478bd9Sstevel@tonic-gate #ifndef lint
11*7c478bd9Sstevel@tonic-gate static const char sccsid[] = "@(#)db_shash.c 10.9 (Sleepycat) 4/10/98";
12*7c478bd9Sstevel@tonic-gate #endif /* not lint */
13*7c478bd9Sstevel@tonic-gate
14*7c478bd9Sstevel@tonic-gate #ifndef NO_SYSTEM_INCLUDES
15*7c478bd9Sstevel@tonic-gate #include <sys/types.h>
16*7c478bd9Sstevel@tonic-gate #endif
17*7c478bd9Sstevel@tonic-gate
18*7c478bd9Sstevel@tonic-gate #include "db_int.h"
19*7c478bd9Sstevel@tonic-gate #include "shqueue.h"
20*7c478bd9Sstevel@tonic-gate #include "common_ext.h"
21*7c478bd9Sstevel@tonic-gate
22*7c478bd9Sstevel@tonic-gate /*
23*7c478bd9Sstevel@tonic-gate * Table of good hash values. Up to ~250,000 buckets, we use powers of 2.
24*7c478bd9Sstevel@tonic-gate * After that, we slow the rate of increase by half. For each choice, we
25*7c478bd9Sstevel@tonic-gate * then use a nearby prime number as the hash value.
26*7c478bd9Sstevel@tonic-gate *
27*7c478bd9Sstevel@tonic-gate * If a terabyte is the maximum cache we'll see, and we assume there are
28*7c478bd9Sstevel@tonic-gate * 10 1K buckets on each hash chain, then 107374182 is the maximum number
29*7c478bd9Sstevel@tonic-gate * of buckets we'll ever need.
30*7c478bd9Sstevel@tonic-gate */
31*7c478bd9Sstevel@tonic-gate static const struct {
32*7c478bd9Sstevel@tonic-gate u_int32_t power;
33*7c478bd9Sstevel@tonic-gate u_int32_t prime;
34*7c478bd9Sstevel@tonic-gate } list[] = {
35*7c478bd9Sstevel@tonic-gate { 64, 67}, /* 2^6 */
36*7c478bd9Sstevel@tonic-gate { 128, 131}, /* 2^7 */
37*7c478bd9Sstevel@tonic-gate { 256, 257}, /* 2^8 */
38*7c478bd9Sstevel@tonic-gate { 512, 521}, /* 2^9 */
39*7c478bd9Sstevel@tonic-gate { 1024, 1031}, /* 2^10 */
40*7c478bd9Sstevel@tonic-gate { 2048, 2053}, /* 2^11 */
41*7c478bd9Sstevel@tonic-gate { 4096, 4099}, /* 2^12 */
42*7c478bd9Sstevel@tonic-gate { 8192, 8191}, /* 2^13 */
43*7c478bd9Sstevel@tonic-gate { 16384, 16381}, /* 2^14 */
44*7c478bd9Sstevel@tonic-gate { 32768, 32771}, /* 2^15 */
45*7c478bd9Sstevel@tonic-gate { 65536, 65537}, /* 2^16 */
46*7c478bd9Sstevel@tonic-gate { 131072, 131071}, /* 2^17 */
47*7c478bd9Sstevel@tonic-gate { 262144, 262147}, /* 2^18 */
48*7c478bd9Sstevel@tonic-gate { 393216, 393209}, /* 2^18 + 2^18/2 */
49*7c478bd9Sstevel@tonic-gate { 524288, 524287}, /* 2^19 */
50*7c478bd9Sstevel@tonic-gate { 786432, 786431}, /* 2^19 + 2^19/2 */
51*7c478bd9Sstevel@tonic-gate { 1048576, 1048573}, /* 2^20 */
52*7c478bd9Sstevel@tonic-gate { 1572864, 1572869}, /* 2^20 + 2^20/2 */
53*7c478bd9Sstevel@tonic-gate { 2097152, 2097169}, /* 2^21 */
54*7c478bd9Sstevel@tonic-gate { 3145728, 3145721}, /* 2^21 + 2^21/2 */
55*7c478bd9Sstevel@tonic-gate { 4194304, 4194301}, /* 2^22 */
56*7c478bd9Sstevel@tonic-gate { 6291456, 6291449}, /* 2^22 + 2^22/2 */
57*7c478bd9Sstevel@tonic-gate { 8388608, 8388617}, /* 2^23 */
58*7c478bd9Sstevel@tonic-gate { 12582912, 12582917}, /* 2^23 + 2^23/2 */
59*7c478bd9Sstevel@tonic-gate { 16777216, 16777213}, /* 2^24 */
60*7c478bd9Sstevel@tonic-gate { 25165824, 25165813}, /* 2^24 + 2^24/2 */
61*7c478bd9Sstevel@tonic-gate { 33554432, 33554393}, /* 2^25 */
62*7c478bd9Sstevel@tonic-gate { 50331648, 50331653}, /* 2^25 + 2^25/2 */
63*7c478bd9Sstevel@tonic-gate { 67108864, 67108859}, /* 2^26 */
64*7c478bd9Sstevel@tonic-gate { 100663296, 100663291}, /* 2^26 + 2^26/2 */
65*7c478bd9Sstevel@tonic-gate { 134217728, 134217757}, /* 2^27 */
66*7c478bd9Sstevel@tonic-gate { 201326592, 201326611}, /* 2^27 + 2^27/2 */
67*7c478bd9Sstevel@tonic-gate { 268435456, 268435459}, /* 2^28 */
68*7c478bd9Sstevel@tonic-gate { 402653184, 402653189}, /* 2^28 + 2^28/2 */
69*7c478bd9Sstevel@tonic-gate { 536870912, 536870909}, /* 2^29 */
70*7c478bd9Sstevel@tonic-gate { 805306368, 805306357}, /* 2^29 + 2^29/2 */
71*7c478bd9Sstevel@tonic-gate {1073741824, 1073741827}, /* 2^30 */
72*7c478bd9Sstevel@tonic-gate {0, 0}
73*7c478bd9Sstevel@tonic-gate };
74*7c478bd9Sstevel@tonic-gate
75*7c478bd9Sstevel@tonic-gate /*
76*7c478bd9Sstevel@tonic-gate * __db_tablesize --
77*7c478bd9Sstevel@tonic-gate * Choose a size for the hash table.
78*7c478bd9Sstevel@tonic-gate *
79*7c478bd9Sstevel@tonic-gate * PUBLIC: int __db_tablesize __P((u_int32_t));
80*7c478bd9Sstevel@tonic-gate */
81*7c478bd9Sstevel@tonic-gate int
__db_tablesize(n_buckets)82*7c478bd9Sstevel@tonic-gate __db_tablesize(n_buckets)
83*7c478bd9Sstevel@tonic-gate u_int32_t n_buckets;
84*7c478bd9Sstevel@tonic-gate {
85*7c478bd9Sstevel@tonic-gate int i;
86*7c478bd9Sstevel@tonic-gate
87*7c478bd9Sstevel@tonic-gate /*
88*7c478bd9Sstevel@tonic-gate * We try to be clever about how big we make the hash tables. Use a
89*7c478bd9Sstevel@tonic-gate * prime number close to the "suggested" number of elements that will
90*7c478bd9Sstevel@tonic-gate * be in the hash table. Use 64 as the minimum hash table size.
91*7c478bd9Sstevel@tonic-gate *
92*7c478bd9Sstevel@tonic-gate * Ref: Sedgewick, Algorithms in C, "Hash Functions"
93*7c478bd9Sstevel@tonic-gate */
94*7c478bd9Sstevel@tonic-gate if (n_buckets < 64)
95*7c478bd9Sstevel@tonic-gate n_buckets = 64;
96*7c478bd9Sstevel@tonic-gate
97*7c478bd9Sstevel@tonic-gate for (i = 0;; ++i) {
98*7c478bd9Sstevel@tonic-gate if (list[i].power == 0) {
99*7c478bd9Sstevel@tonic-gate --i;
100*7c478bd9Sstevel@tonic-gate break;
101*7c478bd9Sstevel@tonic-gate }
102*7c478bd9Sstevel@tonic-gate if (list[i].power >= n_buckets)
103*7c478bd9Sstevel@tonic-gate break;
104*7c478bd9Sstevel@tonic-gate }
105*7c478bd9Sstevel@tonic-gate return (list[i].prime);
106*7c478bd9Sstevel@tonic-gate }
107*7c478bd9Sstevel@tonic-gate
108*7c478bd9Sstevel@tonic-gate /*
109*7c478bd9Sstevel@tonic-gate * __db_hashinit --
110*7c478bd9Sstevel@tonic-gate * Initialize a hash table that resides in shared memory.
111*7c478bd9Sstevel@tonic-gate *
112*7c478bd9Sstevel@tonic-gate * PUBLIC: void __db_hashinit __P((void *, u_int32_t));
113*7c478bd9Sstevel@tonic-gate */
114*7c478bd9Sstevel@tonic-gate void
__db_hashinit(begin,nelements)115*7c478bd9Sstevel@tonic-gate __db_hashinit(begin, nelements)
116*7c478bd9Sstevel@tonic-gate void *begin;
117*7c478bd9Sstevel@tonic-gate u_int32_t nelements;
118*7c478bd9Sstevel@tonic-gate {
119*7c478bd9Sstevel@tonic-gate u_int32_t i;
120*7c478bd9Sstevel@tonic-gate SH_TAILQ_HEAD(hash_head) *headp;
121*7c478bd9Sstevel@tonic-gate
122*7c478bd9Sstevel@tonic-gate headp = (struct hash_head *)begin;
123*7c478bd9Sstevel@tonic-gate
124*7c478bd9Sstevel@tonic-gate for (i = 0; i < nelements; i++, headp++)
125*7c478bd9Sstevel@tonic-gate SH_TAILQ_INIT(headp);
126*7c478bd9Sstevel@tonic-gate }
127