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 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 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