1 //===-------------------------- hash.cpp ----------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "__hash_table"
11 #include "algorithm"
12 #include "stdexcept"
13 #include "type_traits"
14
15 #ifdef __clang__
16 #pragma clang diagnostic ignored "-Wtautological-constant-out-of-range-compare"
17 #endif
18
19 _LIBCPP_BEGIN_NAMESPACE_STD
20
21 namespace {
22
23 // handle all next_prime(i) for i in [1, 210), special case 0
24 const unsigned small_primes[] =
25 {
26 0,
27 2,
28 3,
29 5,
30 7,
31 11,
32 13,
33 17,
34 19,
35 23,
36 29,
37 31,
38 37,
39 41,
40 43,
41 47,
42 53,
43 59,
44 61,
45 67,
46 71,
47 73,
48 79,
49 83,
50 89,
51 97,
52 101,
53 103,
54 107,
55 109,
56 113,
57 127,
58 131,
59 137,
60 139,
61 149,
62 151,
63 157,
64 163,
65 167,
66 173,
67 179,
68 181,
69 191,
70 193,
71 197,
72 199,
73 211
74 };
75
76 // potential primes = 210*k + indices[i], k >= 1
77 // these numbers are not divisible by 2, 3, 5 or 7
78 // (or any integer 2 <= j <= 10 for that matter).
79 const unsigned indices[] =
80 {
81 1,
82 11,
83 13,
84 17,
85 19,
86 23,
87 29,
88 31,
89 37,
90 41,
91 43,
92 47,
93 53,
94 59,
95 61,
96 67,
97 71,
98 73,
99 79,
100 83,
101 89,
102 97,
103 101,
104 103,
105 107,
106 109,
107 113,
108 121,
109 127,
110 131,
111 137,
112 139,
113 143,
114 149,
115 151,
116 157,
117 163,
118 167,
119 169,
120 173,
121 179,
122 181,
123 187,
124 191,
125 193,
126 197,
127 199,
128 209
129 };
130
131 }
132
133 // Returns: If n == 0, returns 0. Else returns the lowest prime number that
134 // is greater than or equal to n.
135 //
136 // The algorithm creates a list of small primes, plus an open-ended list of
137 // potential primes. All prime numbers are potential prime numbers. However
138 // some potential prime numbers are not prime. In an ideal world, all potential
139 // prime numbers would be prime. Candidate prime numbers are chosen as the next
140 // highest potential prime. Then this number is tested for prime by dividing it
141 // by all potential prime numbers less than the sqrt of the candidate.
142 //
143 // This implementation defines potential primes as those numbers not divisible
144 // by 2, 3, 5, and 7. Other (common) implementations define potential primes
145 // as those not divisible by 2. A few other implementations define potential
146 // primes as those not divisible by 2 or 3. By raising the number of small
147 // primes which the potential prime is not divisible by, the set of potential
148 // primes more closely approximates the set of prime numbers. And thus there
149 // are fewer potential primes to search, and fewer potential primes to divide
150 // against.
151
152 template <size_t _Sz = sizeof(size_t)>
153 inline _LIBCPP_INLINE_VISIBILITY
154 typename enable_if<_Sz == 4, void>::type
__check_for_overflow(size_t N)155 __check_for_overflow(size_t N)
156 {
157 #ifndef _LIBCPP_NO_EXCEPTIONS
158 if (N > 0xFFFFFFFB)
159 throw overflow_error("__next_prime overflow");
160 #else
161 (void)N;
162 #endif
163 }
164
165 template <size_t _Sz = sizeof(size_t)>
166 inline _LIBCPP_INLINE_VISIBILITY
167 typename enable_if<_Sz == 8, void>::type
__check_for_overflow(size_t N)168 __check_for_overflow(size_t N)
169 {
170 #ifndef _LIBCPP_NO_EXCEPTIONS
171 if (N > 0xFFFFFFFFFFFFFFC5ull)
172 throw overflow_error("__next_prime overflow");
173 #else
174 (void)N;
175 #endif
176 }
177
178 size_t
__next_prime(size_t n)179 __next_prime(size_t n)
180 {
181 const size_t L = 210;
182 const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
183 // If n is small enough, search in small_primes
184 if (n <= small_primes[N-1])
185 return *std::lower_bound(small_primes, small_primes + N, n);
186 // Else n > largest small_primes
187 // Check for overflow
188 __check_for_overflow(n);
189 // Start searching list of potential primes: L * k0 + indices[in]
190 const size_t M = sizeof(indices) / sizeof(indices[0]);
191 // Select first potential prime >= n
192 // Known a-priori n >= L
193 size_t k0 = n / L;
194 size_t in = static_cast<size_t>(std::lower_bound(indices, indices + M, n - k0 * L)
195 - indices);
196 n = L * k0 + indices[in];
197 while (true)
198 {
199 // Divide n by all primes or potential primes (i) until:
200 // 1. The division is even, so try next potential prime.
201 // 2. The i > sqrt(n), in which case n is prime.
202 // It is known a-priori that n is not divisible by 2, 3, 5 or 7,
203 // so don't test those (j == 5 -> divide by 11 first). And the
204 // potential primes start with 211, so don't test against the last
205 // small prime.
206 for (size_t j = 5; j < N - 1; ++j)
207 {
208 const std::size_t p = small_primes[j];
209 const std::size_t q = n / p;
210 if (q < p)
211 return n;
212 if (n == q * p)
213 goto next;
214 }
215 // n wasn't divisible by small primes, try potential primes
216 {
217 size_t i = 211;
218 while (true)
219 {
220 std::size_t q = n / i;
221 if (q < i)
222 return n;
223 if (n == q * i)
224 break;
225
226 i += 10;
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 += 4;
241 q = n / i;
242 if (q < i)
243 return n;
244 if (n == q * i)
245 break;
246
247 i += 2;
248 q = n / i;
249 if (q < i)
250 return n;
251 if (n == q * i)
252 break;
253
254 i += 4;
255 q = n / i;
256 if (q < i)
257 return n;
258 if (n == q * i)
259 break;
260
261 i += 6;
262 q = n / i;
263 if (q < i)
264 return n;
265 if (n == q * i)
266 break;
267
268 i += 2;
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 += 4;
283 q = n / i;
284 if (q < i)
285 return n;
286 if (n == q * i)
287 break;
288
289 i += 2;
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 += 6;
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 += 2;
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 += 4;
332 q = n / i;
333 if (q < i)
334 return n;
335 if (n == q * i)
336 break;
337
338 i += 2;
339 q = n / i;
340 if (q < i)
341 return n;
342 if (n == q * i)
343 break;
344
345 i += 6;
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 += 6;
360 q = n / i;
361 if (q < i)
362 return n;
363 if (n == q * i)
364 break;
365
366 i += 8;
367 q = n / i;
368 if (q < i)
369 return n;
370 if (n == q * i)
371 break;
372
373 i += 4;
374 q = n / i;
375 if (q < i)
376 return n;
377 if (n == q * i)
378 break;
379
380 i += 2;
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 += 2;
395 q = n / i;
396 if (q < i)
397 return n;
398 if (n == q * i)
399 break;
400
401 i += 4;
402 q = n / i;
403 if (q < i)
404 return n;
405 if (n == q * i)
406 break;
407
408 i += 8;
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 += 4;
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 += 2;
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 += 6;
451 q = n / i;
452 if (q < i)
453 return n;
454 if (n == q * i)
455 break;
456
457 i += 2;
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 += 6;
472 q = n / i;
473 if (q < i)
474 return n;
475 if (n == q * i)
476 break;
477
478 i += 4;
479 q = n / i;
480 if (q < i)
481 return n;
482 if (n == q * i)
483 break;
484
485 i += 2;
486 q = n / i;
487 if (q < i)
488 return n;
489 if (n == q * i)
490 break;
491
492 i += 4;
493 q = n / i;
494 if (q < i)
495 return n;
496 if (n == q * i)
497 break;
498
499 i += 6;
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 += 6;
514 q = n / i;
515 if (q < i)
516 return n;
517 if (n == q * i)
518 break;
519
520 i += 4;
521 q = n / i;
522 if (q < i)
523 return n;
524 if (n == q * i)
525 break;
526
527 i += 2;
528 q = n / i;
529 if (q < i)
530 return n;
531 if (n == q * i)
532 break;
533
534 i += 4;
535 q = n / i;
536 if (q < i)
537 return n;
538 if (n == q * i)
539 break;
540
541 i += 2;
542 q = n / i;
543 if (q < i)
544 return n;
545 if (n == q * i)
546 break;
547
548 i += 10;
549 q = n / i;
550 if (q < i)
551 return n;
552 if (n == q * i)
553 break;
554
555 // This will loop i to the next "plane" of potential primes
556 i += 2;
557 }
558 }
559 next:
560 // n is not prime. Increment n to next potential prime.
561 if (++in == M)
562 {
563 ++k0;
564 in = 0;
565 }
566 n = L * k0 + indices[in];
567 }
568 }
569
570 _LIBCPP_END_NAMESPACE_STD
571