1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
/*-
* See the file LICENSE for redistribution information.
*
* Copyright (c) 2008 WiredTiger Software.
* All rights reserved.
*
* $Id$
*/
#include "wt_internal.h"
/*
* __wt_prime
* Return a prime number relatively close to a value.
*/
u_int32_t
__wt_prime(u_int32_t n)
{
/*
* Ref: the hash functions section of "Algorithms in C", by Sedgewick.
*
* The table is the same as the one in Berkeley DB -- check at each
* power-of-two up to 2^18, then mid-points between each power-of-two
* to a maximum of 2^30.
*/
static const struct {
u_int32_t value;
u_int32_t prime;
} t[] = {
{ 32, 37 }, /* 2^5 */
{ 64, 67 }, /* 2^6 */
{ 128, 131 }, /* 2^7 */
{ 256, 257 }, /* 2^8 */
{ 512, 521 }, /* 2^9 */
{ 1024, 1031 }, /* 2^10 */
{ 2048, 2053 }, /* 2^11 */
{ 4096, 4099 }, /* 2^12 */
{ 8192, 8191 }, /* 2^13 */
{ 16384, 16381 }, /* 2^14 */
{ 32768, 32771 }, /* 2^15 */
{ 65536, 65537 }, /* 2^16 */
{ 131072, 131071 }, /* 2^17 */
{ 262144, 262147 }, /* 2^18 */
{ 393216, 393209 }, /* 2^18 + 2^18/2 */
{ 524288, 524287 }, /* 2^19 */
{ 786432, 786431 }, /* 2^19 + 2^19/2 */
{ 1048576, 1048573 }, /* 2^20 */
{ 1572864, 1572869 }, /* 2^20 + 2^20/2 */
{ 2097152, 2097169 }, /* 2^21 */
{ 3145728, 3145721 }, /* 2^21 + 2^21/2 */
{ 4194304, 4194301 }, /* 2^22 */
{ 6291456, 6291449 }, /* 2^22 + 2^22/2 */
{ 8388608, 8388617 }, /* 2^23 */
{ 12582912, 12582917 }, /* 2^23 + 2^23/2 */
{ 16777216, 16777213 }, /* 2^24 */
{ 25165824, 25165813 }, /* 2^24 + 2^24/2 */
{ 33554432, 33554393 }, /* 2^25 */
{ 50331648, 50331653 }, /* 2^25 + 2^25/2 */
{ 67108864, 67108859 }, /* 2^26 */
{ 100663296, 100663291 }, /* 2^26 + 2^26/2 */
{ 134217728, 134217757 }, /* 2^27 */
{ 201326592, 201326611 }, /* 2^27 + 2^27/2 */
{ 268435456, 268435459 }, /* 2^28 */
{ 402653184, 402653189 }, /* 2^28 + 2^28/2 */
{ 536870912, 536870909 }, /* 2^29 */
{ 805306368, 805306357 }, /* 2^29 + 2^29/2 */
{ 1073741824, 1073741827 }, /* 2^30 */
};
u_int i;
for (i = 0; i < WT_ELEMENTS(t); ++i)
if (t[i].value > n)
return (t[i].prime);
return (t[WT_ELEMENTS(t) - 1].prime);
}
|
