etc/services - sync with NetBSD-8
[minix.git] / external / bsd / libc++ / dist / libcxx / src / hash.cpp
blobdc90f789c6b81e200cbd2307a8440a3a5b566bb8
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 //===----------------------------------------------------------------------===//
10 #include "__hash_table"
11 #include "algorithm"
12 #include "stdexcept"
13 #include "type_traits"
15 #ifdef __clang__
16 #pragma clang diagnostic ignored "-Wtautological-constant-out-of-range-compare"
17 #endif
19 _LIBCPP_BEGIN_NAMESPACE_STD
21 namespace {
23 // handle all next_prime(i) for i in [1, 210), special case 0
24 const unsigned small_primes[] =
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
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[] =
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,
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,
133 // Returns: If n == 0, returns 0. Else returns the lowest prime number that
134 // is greater than or equal to n.
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.
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.
152 template <size_t _Sz = sizeof(size_t)>
153 inline _LIBCPP_INLINE_VISIBILITY
154 typename enable_if<_Sz == 4, void>::type
155 __check_for_overflow(size_t N)
157 #ifndef _LIBCPP_NO_EXCEPTIONS
158 if (N > 0xFFFFFFFB)
159 throw overflow_error("__next_prime overflow");
160 #else
161 (void)N;
162 #endif
165 template <size_t _Sz = sizeof(size_t)>
166 inline _LIBCPP_INLINE_VISIBILITY
167 typename enable_if<_Sz == 8, void>::type
168 __check_for_overflow(size_t N)
170 #ifndef _LIBCPP_NO_EXCEPTIONS
171 if (N > 0xFFFFFFFFFFFFFFC5ull)
172 throw overflow_error("__next_prime overflow");
173 #else
174 (void)N;
175 #endif
178 size_t
179 __next_prime(size_t n)
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)
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)
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;
215 // n wasn't divisible by small primes, try potential primes
217 size_t i = 211;
218 while (true)
220 std::size_t q = n / i;
221 if (q < i)
222 return n;
223 if (n == q * i)
224 break;
226 i += 10;
227 q = n / i;
228 if (q < i)
229 return n;
230 if (n == q * i)
231 break;
233 i += 2;
234 q = n / i;
235 if (q < i)
236 return n;
237 if (n == q * i)
238 break;
240 i += 4;
241 q = n / i;
242 if (q < i)
243 return n;
244 if (n == q * i)
245 break;
247 i += 2;
248 q = n / i;
249 if (q < i)
250 return n;
251 if (n == q * i)
252 break;
254 i += 4;
255 q = n / i;
256 if (q < i)
257 return n;
258 if (n == q * i)
259 break;
261 i += 6;
262 q = n / i;
263 if (q < i)
264 return n;
265 if (n == q * i)
266 break;
268 i += 2;
269 q = n / i;
270 if (q < i)
271 return n;
272 if (n == q * i)
273 break;
275 i += 6;
276 q = n / i;
277 if (q < i)
278 return n;
279 if (n == q * i)
280 break;
282 i += 4;
283 q = n / i;
284 if (q < i)
285 return n;
286 if (n == q * i)
287 break;
289 i += 2;
290 q = n / i;
291 if (q < i)
292 return n;
293 if (n == q * i)
294 break;
296 i += 4;
297 q = n / i;
298 if (q < i)
299 return n;
300 if (n == q * i)
301 break;
303 i += 6;
304 q = n / i;
305 if (q < i)
306 return n;
307 if (n == q * i)
308 break;
310 i += 6;
311 q = n / i;
312 if (q < i)
313 return n;
314 if (n == q * i)
315 break;
317 i += 2;
318 q = n / i;
319 if (q < i)
320 return n;
321 if (n == q * i)
322 break;
324 i += 6;
325 q = n / i;
326 if (q < i)
327 return n;
328 if (n == q * i)
329 break;
331 i += 4;
332 q = n / i;
333 if (q < i)
334 return n;
335 if (n == q * i)
336 break;
338 i += 2;
339 q = n / i;
340 if (q < i)
341 return n;
342 if (n == q * i)
343 break;
345 i += 6;
346 q = n / i;
347 if (q < i)
348 return n;
349 if (n == q * i)
350 break;
352 i += 4;
353 q = n / i;
354 if (q < i)
355 return n;
356 if (n == q * i)
357 break;
359 i += 6;
360 q = n / i;
361 if (q < i)
362 return n;
363 if (n == q * i)
364 break;
366 i += 8;
367 q = n / i;
368 if (q < i)
369 return n;
370 if (n == q * i)
371 break;
373 i += 4;
374 q = n / i;
375 if (q < i)
376 return n;
377 if (n == q * i)
378 break;
380 i += 2;
381 q = n / i;
382 if (q < i)
383 return n;
384 if (n == q * i)
385 break;
387 i += 4;
388 q = n / i;
389 if (q < i)
390 return n;
391 if (n == q * i)
392 break;
394 i += 2;
395 q = n / i;
396 if (q < i)
397 return n;
398 if (n == q * i)
399 break;
401 i += 4;
402 q = n / i;
403 if (q < i)
404 return n;
405 if (n == q * i)
406 break;
408 i += 8;
409 q = n / i;
410 if (q < i)
411 return n;
412 if (n == q * i)
413 break;
415 i += 6;
416 q = n / i;
417 if (q < i)
418 return n;
419 if (n == q * i)
420 break;
422 i += 4;
423 q = n / i;
424 if (q < i)
425 return n;
426 if (n == q * i)
427 break;
429 i += 6;
430 q = n / i;
431 if (q < i)
432 return n;
433 if (n == q * i)
434 break;
436 i += 2;
437 q = n / i;
438 if (q < i)
439 return n;
440 if (n == q * i)
441 break;
443 i += 4;
444 q = n / i;
445 if (q < i)
446 return n;
447 if (n == q * i)
448 break;
450 i += 6;
451 q = n / i;
452 if (q < i)
453 return n;
454 if (n == q * i)
455 break;
457 i += 2;
458 q = n / i;
459 if (q < i)
460 return n;
461 if (n == q * i)
462 break;
464 i += 6;
465 q = n / i;
466 if (q < i)
467 return n;
468 if (n == q * i)
469 break;
471 i += 6;
472 q = n / i;
473 if (q < i)
474 return n;
475 if (n == q * i)
476 break;
478 i += 4;
479 q = n / i;
480 if (q < i)
481 return n;
482 if (n == q * i)
483 break;
485 i += 2;
486 q = n / i;
487 if (q < i)
488 return n;
489 if (n == q * i)
490 break;
492 i += 4;
493 q = n / i;
494 if (q < i)
495 return n;
496 if (n == q * i)
497 break;
499 i += 6;
500 q = n / i;
501 if (q < i)
502 return n;
503 if (n == q * i)
504 break;
506 i += 2;
507 q = n / i;
508 if (q < i)
509 return n;
510 if (n == q * i)
511 break;
513 i += 6;
514 q = n / i;
515 if (q < i)
516 return n;
517 if (n == q * i)
518 break;
520 i += 4;
521 q = n / i;
522 if (q < i)
523 return n;
524 if (n == q * i)
525 break;
527 i += 2;
528 q = n / i;
529 if (q < i)
530 return n;
531 if (n == q * i)
532 break;
534 i += 4;
535 q = n / i;
536 if (q < i)
537 return n;
538 if (n == q * i)
539 break;
541 i += 2;
542 q = n / i;
543 if (q < i)
544 return n;
545 if (n == q * i)
546 break;
548 i += 10;
549 q = n / i;
550 if (q < i)
551 return n;
552 if (n == q * i)
553 break;
555 // This will loop i to the next "plane" of potential primes
556 i += 2;
559 next:
560 // n is not prime. Increment n to next potential prime.
561 if (++in == M)
563 ++k0;
564 in = 0;
566 n = L * k0 + indices[in];
570 _LIBCPP_END_NAMESPACE_STD