dchip.prime source code

1 /*
2  * Copyright (c) 2007-2013 Scott Lembcke and Howling Moon Software
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to deal
6  * in the Software without restriction, including without limitation the rights
7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  * copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20  * SOFTWARE.
21  */
22 module dchip.prime;
23 
24 import dchip.chipmunk;
25 
26 // Used for resizing hash tables.
27 // Values approximately double.
28 // http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
29 immutable primes = [
30     5,
31     13,
32     23,
33     47,
34     97,
35     193,
36     389,
37     769,
38     1543,
39     3079,
40     6151,
41     12289,
42     24593,
43     49157,
44     98317,
45     196613,
46     393241,
47     786433,
48     1572869,
49     3145739,
50     6291469,
51     12582917,
52     25165843,
53     50331653,
54     100663319,
55     201326611,
56     402653189,
57     805306457,
58     1610612741,
59     0,
60 ];
61 
62 int next_prime(int n)
63 {
64     int i = 0;
65 
66     while (n > primes[i])
67     {
68         i++;
69         cpAssertHard(primes[i], "Tried to resize a hash table to a size greater than 1610612741 O_o");         // realistically this should never happen
70     }
71 
72     return primes[i];
73 }