Coverage Report

Created: 2022-07-16 07:03

/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