/Users/buildslave/jenkins/workspace/coverage/llvm-project/libcxx/src/hash.cpp

Source (jump to first uncovered line)
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include <__hash_table>
#include <algorithm>
#include <stdexcept>
#include <type_traits>

_LIBCPP_CLANG_DIAGNOSTIC_IGNORED("-Wtautological-constant-out-of-range-compare")

_LIBCPP_BEGIN_NAMESPACE_STD

namespace {

// handle all next_prime(i) for i in [1, 210), special case 0
const unsigned small_primes[] =
{
    0,
    2,
    3,
    5,
    7,
    11,
    13,
    17,
    19,
    23,
    29,
    31,
    37,
    41,
    43,
    47,
    53,
    59,
    61,
    67,
    71,
    73,
    79,
    83,
    89,
    97,
    101,
    103,
    107,
    109,
    113,
    127,
    131,
    137,
    139,
    149,
    151,
    157,
    163,
    167,
    173,
    179,
    181,
    191,
    193,
    197,
    199,
    211
};

// potential primes = 210*k + indices[i], k >= 1
//   these numbers are not divisible by 2, 3, 5 or 7
//   (or any integer 2 <= j <= 10 for that matter).
const unsigned indices[] =
{
    1,
    11,
    13,
    17,
    19,
    23,
    29,
    31,
    37,
    41,
    43,
    47,
    53,
    59,
    61,
    67,
    71,
    73,
    79,
    83,
    89,
    97,
    101,
    103,
    107,
    109,
    113,
    121,
    127,
    131,
    137,
    139,
    143,
    149,
    151,
    157,
    163,
    167,
    169,
    173,
    179,
    181,
    187,
    191,
    193,
    197,
    199,
    209
};

}

// Returns:  If n == 0, returns 0.  Else returns the lowest prime number that
// is greater than or equal to n.
//
// The algorithm creates a list of small primes, plus an open-ended list of
// potential primes.  All prime numbers are potential prime numbers.  However
// some potential prime numbers are not prime.  In an ideal world, all potential
// prime numbers would be prime.  Candidate prime numbers are chosen as the next
// highest potential prime.  Then this number is tested for prime by dividing it
// by all potential prime numbers less than the sqrt of the candidate.
//
// This implementation defines potential primes as those numbers not divisible
// by 2, 3, 5, and 7.  Other (common) implementations define potential primes
// as those not divisible by 2.  A few other implementations define potential
// primes as those not divisible by 2 or 3.  By raising the number of small
// primes which the potential prime is not divisible by, the set of potential
// primes more closely approximates the set of prime numbers.  And thus there
// are fewer potential primes to search, and fewer potential primes to divide
// against.

template <size_t _Sz = sizeof(size_t)>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if<_Sz == 4, void>::type
__check_for_overflow(size_t N)
{
    if (N > 0xFFFFFFFB)
        __throw_overflow_error("__next_prime overflow");
}

template <size_t _Sz = sizeof(size_t)>
inline _LIBCPP_INLINE_VISIBILITY
typename enable_if<_Sz == 8, void>::type
__check_for_overflow(size_t N)
{
    if (N > 0xFFFFFFFFFFFFFFC5ull)
        __throw_overflow_error("__next_prime overflow");
}

size_t
__next_prime(size_t n)
{
    const size_t L = 210;
    const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
    // If n is small enough, search in small_primes
    if (n <= small_primes[N-1])
        return *std::lower_bound(small_primes, small_primes + N, n);
    // Else n > largest small_primes
    // Check for overflow
    __check_for_overflow(n);
    // Start searching list of potential primes: L * k0 + indices[in]
    const size_t M = sizeof(indices) / sizeof(indices[0]);
    // Select first potential prime >= n
    //   Known a-priori n >= L
    size_t k0 = n / L;
    size_t in = static_cast<size_t>(std::lower_bound(indices, indices + M, n - k0 * L)
                                    - indices);
    n = L * k0 + indices[in];
    while (true)
    {
        // Divide n by all primes or potential primes (i) until:
        //    1.  The division is even, so try next potential prime.
        //    2.  The i > sqrt(n), in which case n is prime.
        // It is known a-priori that n is not divisible by 2, 3, 5 or 7,
        //    so don't test those (j == 5 ->  divide by 11 first).  And the
        //    potential primes start with 211, so don't test against the last
        //    small prime.
        for (size_t j = 5; j < N - 1; ++j)
        {
            const std::size_t p = small_primes[j];
            const std::size_t q = n / p;
            if (q < p)
                return n;
            if (n == q * p)
                goto next;
        }
        // n wasn't divisible by small primes, try potential primes
        {
            size_t i = 211;
            while (true)
            {
                std::size_t q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 10;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 8;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 8;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 6;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 4;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 2;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                i += 10;
                q = n / i;
                if (q < i)
                    return n;
                if (n == q * i)
                    break;

                // This will loop i to the next "plane" of potential primes
                i += 2;
            }
        }
next:
        // n is not prime.  Increment n to next potential prime.
        if (++in == M)
        {
            ++k0;
            in = 0;
        }
        n = L * k0 + indices[in];
    }
}

_LIBCPP_END_NAMESPACE_STD

Coverage Report

Created: 2022-07-16 07:03

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