Coverage Report

Created: 2020-09-22 08:39

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