hash.cpp revision f5256e16dfc425c1d466f6308d4026d529ce9e0b 
1//===-------------------------- hash.cpp ----------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "__hash_table"
11#include "algorithm"
12
13_LIBCPP_BEGIN_NAMESPACE_STD
14
15namespace {
16
17// handle all next_prime(i) for i in [1, 210), special case 0
18const unsigned small_primes[] =
19{
20    0,
21    2,
22    3,
23    5,
24    7,
25    11,
26    13,
27    17,
28    19,
29    23,
30    29,
31    31,
32    37,
33    41,
34    43,
35    47,
36    53,
37    59,
38    61,
39    67,
40    71,
41    73,
42    79,
43    83,
44    89,
45    97,
46    101,
47    103,
48    107,
49    109,
50    113,
51    127,
52    131,
53    137,
54    139,
55    149,
56    151,
57    157,
58    163,
59    167,
60    173,
61    179,
62    181,
63    191,
64    193,
65    197,
66    199,
67    211
68};
69
70// potential primes = 210*k + indices[i], k >= 1
71//   these numbers are not divisible by 2, 3, 5 or 7
72//   (or any integer 2 <= j <= 10 for that matter).
73const unsigned indices[] =
74{
75    1,
76    11,
77    13,
78    17,
79    19,
80    23,
81    29,
82    31,
83    37,
84    41,
85    43,
86    47,
87    53,
88    59,
89    61,
90    67,
91    71,
92    73,
93    79,
94    83,
95    89,
96    97,
97    101,
98    103,
99    107,
100    109,
101    113,
102    121,
103    127,
104    131,
105    137,
106    139,
107    143,
108    149,
109    151,
110    157,
111    163,
112    167,
113    169,
114    173,
115    179,
116    181,
117    187,
118    191,
119    193,
120    197,
121    199,
122    209
123};
124
125}
126
127// Returns:  If n == 0, returns 0.  Else returns the lowest prime number that
128// is greater than or equal to n.
129//
130// The algorithm creates a list of small primes, plus an open-ended list of
131// potential primes.  All prime numbers are potential prime numbers.  However
132// some potential prime numbers are not prime.  In an ideal world, all potential
133// prime numbers would be prime.  Candiate prime numbers are chosen as the next
134// highest potential prime.  Then this number is tested for prime by dividing it
135// by all potential prime numbers less than the sqrt of the candidate.
136//
137// This implementation defines potential primes as those numbers not divisible
138// by 2, 3, 5, and 7.  Other (common) implementations define potential primes
139// as those not divisible by 2.  A few other implementations define potential
140// primes as those not divisible by 2 or 3.  By raising the number of small
141// primes which the potential prime is not divisible by, the set of potential
142// primes more closely approximates the set of prime numbers.  And thus there
143// are fewer potential primes to search, and fewer potential primes to divide
144// against.
145
146size_t
147__next_prime(size_t n)
148{
149    const size_t L = 210;
150    const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
151    // If n is small enough, search in small_primes
152    if (n <= small_primes[N-1])
153        return *std::lower_bound(small_primes, small_primes + N, n);
154    // Else n > largest small_primes
155    // Start searching list of potential primes: L * k0 + indices[in]
156    const size_t M = sizeof(indices) / sizeof(indices[0]);
157    // Select first potential prime >= n
158    //   Known a-priori n >= L
159    size_t k0 = n / L;
160    size_t in = std::lower_bound(indices, indices + M, n % L) - indices;
161    n = L * k0 + indices[in];
162    while (true)
163    {
164        // Divide n by all primes or potential primes (i) until:
165        //    1.  The division is even, so try next potential prime.
166        //    2.  The i > sqrt(n), in which case n is prime.
167        // It is known a-priori that n is not divisible by 2, 3, 5 or 7,
168        //    so don't test those (j == 5 ->  divide by 11 first).  And the
169        //    potential primes start with 211, so don't test against the last
170        //    small prime.
171        for (size_t j = 5; j < N - 1; ++j)
172        {
173            if (n % small_primes[j] == 0)
174                goto next;
175            if (n / small_primes[j] < small_primes[j])
176                return n;
177        }
178        // n wasn't divisible by small primes, try potential primes
179        {
180            size_t i = 211;
181            while (true)
182            {
183                if (n % i == 0)
184                    break;
185                if (n / i < i)
186                    return n;
187
188                i += 10;
189                if (n % i == 0)
190                    break;
191                if (n / i < i)
192                    return n;
193
194                i += 2;
195                if (n % i == 0)
196                    break;
197                if (n / i < i)
198                    return n;
199
200                i += 4;
201                if (n % i == 0)
202                    break;
203                if (n / i < i)
204                    return n;
205
206                i += 2;
207                if (n % i == 0)
208                    break;
209                if (n / i < i)
210                    return n;
211
212                i += 4;
213                if (n % i == 0)
214                    break;
215                if (n / i < i)
216                    return n;
217
218                i += 6;
219                if (n % i == 0)
220                    break;
221                if (n / i < i)
222                    return n;
223
224                i += 2;
225                if (n % i == 0)
226                    break;
227                if (n / i < i)
228                    return n;
229
230                i += 6;
231                if (n % i == 0)
232                    break;
233                if (n / i < i)
234                    return n;
235
236                i += 4;
237                if (n % i == 0)
238                    break;
239                if (n / i < i)
240                    return n;
241
242                i += 2;
243                if (n % i == 0)
244                    break;
245                if (n / i < i)
246                    return n;
247
248                i += 4;
249                if (n % i == 0)
250                    break;
251                if (n / i < i)
252                    return n;
253
254                i += 6;
255                if (n % i == 0)
256                    break;
257                if (n / i < i)
258                    return n;
259
260                i += 6;
261                if (n % i == 0)
262                    break;
263                if (n / i < i)
264                    return n;
265
266                i += 2;
267                if (n % i == 0)
268                    break;
269                if (n / i < i)
270                    return n;
271
272                i += 6;
273                if (n % i == 0)
274                    break;
275                if (n / i < i)
276                    return n;
277
278                i += 4;
279                if (n % i == 0)
280                    break;
281                if (n / i < i)
282                    return n;
283
284                i += 2;
285                if (n % i == 0)
286                    break;
287                if (n / i < i)
288                    return n;
289
290                i += 6;
291                if (n % i == 0)
292                    break;
293                if (n / i < i)
294                    return n;
295
296                i += 4;
297                if (n % i == 0)
298                    break;
299                if (n / i < i)
300                    return n;
301
302                i += 6;
303                if (n % i == 0)
304                    break;
305                if (n / i < i)
306                    return n;
307
308                i += 8;
309                if (n % i == 0)
310                    break;
311                if (n / i < i)
312                    return n;
313
314                i += 4;
315                if (n % i == 0)
316                    break;
317                if (n / i < i)
318                    return n;
319
320                i += 2;
321                if (n % i == 0)
322                    break;
323                if (n / i < i)
324                    return n;
325
326                i += 4;
327                if (n % i == 0)
328                    break;
329                if (n / i < i)
330                    return n;
331
332                i += 2;
333                if (n % i == 0)
334                    break;
335                if (n / i < i)
336                    return n;
337
338                i += 4;
339                if (n % i == 0)
340                    break;
341                if (n / i < i)
342                    return n;
343
344                i += 8;
345                if (n % i == 0)
346                    break;
347                if (n / i < i)
348                    return n;
349
350                i += 6;
351                if (n % i == 0)
352                    break;
353                if (n / i < i)
354                    return n;
355
356                i += 4;
357                if (n % i == 0)
358                    break;
359                if (n / i < i)
360                    return n;
361
362                i += 6;
363                if (n % i == 0)
364                    break;
365                if (n / i < i)
366                    return n;
367
368                i += 2;
369                if (n % i == 0)
370                    break;
371                if (n / i < i)
372                    return n;
373
374                i += 4;
375                if (n % i == 0)
376                    break;
377                if (n / i < i)
378                    return n;
379
380                i += 6;
381                if (n % i == 0)
382                    break;
383                if (n / i < i)
384                    return n;
385
386                i += 2;
387                if (n % i == 0)
388                    break;
389                if (n / i < i)
390                    return n;
391
392                i += 6;
393                if (n % i == 0)
394                    break;
395                if (n / i < i)
396                    return n;
397
398                i += 6;
399                if (n % i == 0)
400                    break;
401                if (n / i < i)
402                    return n;
403
404                i += 4;
405                if (n % i == 0)
406                    break;
407                if (n / i < i)
408                    return n;
409
410                i += 2;
411                if (n % i == 0)
412                    break;
413                if (n / i < i)
414                    return n;
415
416                i += 4;
417                if (n % i == 0)
418                    break;
419                if (n / i < i)
420                    return n;
421
422                i += 6;
423                if (n % i == 0)
424                    break;
425                if (n / i < i)
426                    return n;
427
428                i += 2;
429                if (n % i == 0)
430                    break;
431                if (n / i < i)
432                    return n;
433
434                i += 6;
435                if (n % i == 0)
436                    break;
437                if (n / i < i)
438                    return n;
439
440                i += 4;
441                if (n % i == 0)
442                    break;
443                if (n / i < i)
444                    return n;
445
446                i += 2;
447                if (n % i == 0)
448                    break;
449                if (n / i < i)
450                    return n;
451
452                i += 4;
453                if (n % i == 0)
454                    break;
455                if (n / i < i)
456                    return n;
457
458                i += 2;
459                if (n % i == 0)
460                    break;
461                if (n / i < i)
462                    return n;
463
464                i += 10;
465                if (n % i == 0)
466                    break;
467                if (n / i < i)
468                    return n;
469
470                // This will loop i to the next "plane" of potential primes
471                i += 2;
472            }
473        }
474next:
475        // n is not prime.  Increment n to next potential prime.
476        if (++in == M)
477        {
478            ++k0;
479            in = 0;
480        }
481        n = L * k0 + indices[in];
482    }
483}
484
485_LIBCPP_END_NAMESPACE_STD
486