hash.cpp revision d2a9251977be7d3cb9421b263d8a604dff709dad 
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 - k0 * 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            const std::size_t p = small_primes[j];
174            const std::size_t q = n / p;
175            if (q < p)
176                return n;
177            if (n == q * p)
178                goto next;
179        }
180        // n wasn't divisible by small primes, try potential primes
181        {
182            size_t i = 211;
183            while (true)
184            {
185                std::size_t q = n / i;
186                if (q < i)
187                    return n;
188                if (n == q * i)
189                    break;
190
191                i += 10;
192                q = n / i;
193                if (q < i)
194                    return n;
195                if (n == q * i)
196                    break;
197
198                i += 2;
199                q = n / i;
200                if (q < i)
201                    return n;
202                if (n == q * i)
203                    break;
204
205                i += 4;
206                q = n / i;
207                if (q < i)
208                    return n;
209                if (n == q * i)
210                    break;
211
212                i += 2;
213                q = n / i;
214                if (q < i)
215                    return n;
216                if (n == q * i)
217                    break;
218
219                i += 4;
220                q = n / i;
221                if (q < i)
222                    return n;
223                if (n == q * i)
224                    break;
225
226                i += 6;
227                q = n / i;
228                if (q < i)
229                    return n;
230                if (n == q * i)
231                    break;
232
233                i += 2;
234                q = n / i;
235                if (q < i)
236                    return n;
237                if (n == q * i)
238                    break;
239
240                i += 6;
241                q = n / i;
242                if (q < i)
243                    return n;
244                if (n == q * i)
245                    break;
246
247                i += 4;
248                q = n / i;
249                if (q < i)
250                    return n;
251                if (n == q * i)
252                    break;
253
254                i += 2;
255                q = n / i;
256                if (q < i)
257                    return n;
258                if (n == q * i)
259                    break;
260
261                i += 4;
262                q = n / i;
263                if (q < i)
264                    return n;
265                if (n == q * i)
266                    break;
267
268                i += 6;
269                q = n / i;
270                if (q < i)
271                    return n;
272                if (n == q * i)
273                    break;
274
275                i += 6;
276                q = n / i;
277                if (q < i)
278                    return n;
279                if (n == q * i)
280                    break;
281
282                i += 2;
283                q = n / i;
284                if (q < i)
285                    return n;
286                if (n == q * i)
287                    break;
288
289                i += 6;
290                q = n / i;
291                if (q < i)
292                    return n;
293                if (n == q * i)
294                    break;
295
296                i += 4;
297                q = n / i;
298                if (q < i)
299                    return n;
300                if (n == q * i)
301                    break;
302
303                i += 2;
304                q = n / i;
305                if (q < i)
306                    return n;
307                if (n == q * i)
308                    break;
309
310                i += 6;
311                q = n / i;
312                if (q < i)
313                    return n;
314                if (n == q * i)
315                    break;
316
317                i += 4;
318                q = n / i;
319                if (q < i)
320                    return n;
321                if (n == q * i)
322                    break;
323
324                i += 6;
325                q = n / i;
326                if (q < i)
327                    return n;
328                if (n == q * i)
329                    break;
330
331                i += 8;
332                q = n / i;
333                if (q < i)
334                    return n;
335                if (n == q * i)
336                    break;
337
338                i += 4;
339                q = n / i;
340                if (q < i)
341                    return n;
342                if (n == q * i)
343                    break;
344
345                i += 2;
346                q = n / i;
347                if (q < i)
348                    return n;
349                if (n == q * i)
350                    break;
351
352                i += 4;
353                q = n / i;
354                if (q < i)
355                    return n;
356                if (n == q * i)
357                    break;
358
359                i += 2;
360                q = n / i;
361                if (q < i)
362                    return n;
363                if (n == q * i)
364                    break;
365
366                i += 4;
367                q = n / i;
368                if (q < i)
369                    return n;
370                if (n == q * i)
371                    break;
372
373                i += 8;
374                q = n / i;
375                if (q < i)
376                    return n;
377                if (n == q * i)
378                    break;
379
380                i += 6;
381                q = n / i;
382                if (q < i)
383                    return n;
384                if (n == q * i)
385                    break;
386
387                i += 4;
388                q = n / i;
389                if (q < i)
390                    return n;
391                if (n == q * i)
392                    break;
393
394                i += 6;
395                q = n / i;
396                if (q < i)
397                    return n;
398                if (n == q * i)
399                    break;
400
401                i += 2;
402                q = n / i;
403                if (q < i)
404                    return n;
405                if (n == q * i)
406                    break;
407
408                i += 4;
409                q = n / i;
410                if (q < i)
411                    return n;
412                if (n == q * i)
413                    break;
414
415                i += 6;
416                q = n / i;
417                if (q < i)
418                    return n;
419                if (n == q * i)
420                    break;
421
422                i += 2;
423                q = n / i;
424                if (q < i)
425                    return n;
426                if (n == q * i)
427                    break;
428
429                i += 6;
430                q = n / i;
431                if (q < i)
432                    return n;
433                if (n == q * i)
434                    break;
435
436                i += 6;
437                q = n / i;
438                if (q < i)
439                    return n;
440                if (n == q * i)
441                    break;
442
443                i += 4;
444                q = n / i;
445                if (q < i)
446                    return n;
447                if (n == q * i)
448                    break;
449
450                i += 2;
451                q = n / i;
452                if (q < i)
453                    return n;
454                if (n == q * i)
455                    break;
456
457                i += 4;
458                q = n / i;
459                if (q < i)
460                    return n;
461                if (n == q * i)
462                    break;
463
464                i += 6;
465                q = n / i;
466                if (q < i)
467                    return n;
468                if (n == q * i)
469                    break;
470
471                i += 2;
472                q = n / i;
473                if (q < i)
474                    return n;
475                if (n == q * i)
476                    break;
477
478                i += 6;
479                q = n / i;
480                if (q < i)
481                    return n;
482                if (n == q * i)
483                    break;
484
485                i += 4;
486                q = n / i;
487                if (q < i)
488                    return n;
489                if (n == q * i)
490                    break;
491
492                i += 2;
493                q = n / i;
494                if (q < i)
495                    return n;
496                if (n == q * i)
497                    break;
498
499                i += 4;
500                q = n / i;
501                if (q < i)
502                    return n;
503                if (n == q * i)
504                    break;
505
506                i += 2;
507                q = n / i;
508                if (q < i)
509                    return n;
510                if (n == q * i)
511                    break;
512
513                i += 10;
514                q = n / i;
515                if (q < i)
516                    return n;
517                if (n == q * i)
518                    break;
519
520                // This will loop i to the next "plane" of potential primes
521                i += 2;
522            }
523        }
524next:
525        // n is not prime.  Increment n to next potential prime.
526        if (++in == M)
527        {
528            ++k0;
529            in = 0;
530        }
531        n = L * k0 + indices[in];
532    }
533}
534
535_LIBCPP_END_NAMESPACE_STD
536