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