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