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