Coverage Report

Created: 2020-02-15 09:57

/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
246k
{
172
246k
    const size_t L = 210;
173
246k
    const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
174
246k
    // If n is small enough, search in small_primes
175
246k
    if (n <= small_primes[N-1])
176
246k
        return *std::lower_bound(small_primes, small_primes + N, n);
177
0
    // Else n > largest small_primes
178
0
    // Check for overflow
179
0
    __check_for_overflow(n);
180
0
    // Start searching list of potential primes: L * k0 + indices[in]
181
0
    const size_t M = sizeof(indices) / sizeof(indices[0]);
182
0
    // Select first potential prime >= n
183
0
    //   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
0
        // Divide n by all primes or potential primes (i) until:
191
0
        //    1.  The division is even, so try next potential prime.
192
0
        //    2.  The i > sqrt(n), in which case n is prime.
193
0
        // It is known a-priori that n is not divisible by 2, 3, 5 or 7,
194
0
        //    so don't test those (j == 5 ->  divide by 11 first).  And the
195
0
        //    potential primes start with 211, so don't test against the last
196
0
        //    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
0
        // 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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
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
0
546
0
                // This will loop i to the next "plane" of potential primes
547
0
                i += 2;
548
0
            }
549
0
        }
550
0
next:
551
0
        // 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