1 //===-------------------------- hash.cpp ----------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "__hash_table"
13 #include "type_traits"
16 #pragma clang diagnostic ignored "-Wtautological-constant-out-of-range-compare"
19 _LIBCPP_BEGIN_NAMESPACE_STD
23 // handle all next_prime(i) for i in [1, 210), special case 0
24 const unsigned small_primes[] =
76 // potential primes = 210*k + indices[i], k >= 1
77 // these numbers are not divisible by 2, 3, 5 or 7
78 // (or any integer 2 <= j <= 10 for that matter).
79 const unsigned indices[] =
133 // Returns: If n == 0, returns 0. Else returns the lowest prime number that
134 // is greater than or equal to n.
136 // The algorithm creates a list of small primes, plus an open-ended list of
137 // potential primes. All prime numbers are potential prime numbers. However
138 // some potential prime numbers are not prime. In an ideal world, all potential
139 // prime numbers would be prime. Candidate prime numbers are chosen as the next
140 // highest potential prime. Then this number is tested for prime by dividing it
141 // by all potential prime numbers less than the sqrt of the candidate.
143 // This implementation defines potential primes as those numbers not divisible
144 // by 2, 3, 5, and 7. Other (common) implementations define potential primes
145 // as those not divisible by 2. A few other implementations define potential
146 // primes as those not divisible by 2 or 3. By raising the number of small
147 // primes which the potential prime is not divisible by, the set of potential
148 // primes more closely approximates the set of prime numbers. And thus there
149 // are fewer potential primes to search, and fewer potential primes to divide
152 template <size_t _Sz = sizeof(size_t)>
153 inline _LIBCPP_INLINE_VISIBILITY
154 typename enable_if<_Sz == 4, void>::type
155 __check_for_overflow(size_t N)
157 #ifndef _LIBCPP_NO_EXCEPTIONS
159 throw overflow_error("__next_prime overflow");
165 template <size_t _Sz = sizeof(size_t)>
166 inline _LIBCPP_INLINE_VISIBILITY
167 typename enable_if<_Sz == 8, void>::type
168 __check_for_overflow(size_t N)
170 #ifndef _LIBCPP_NO_EXCEPTIONS
171 if (N > 0xFFFFFFFFFFFFFFC5ull)
172 throw overflow_error("__next_prime overflow");
179 __next_prime(size_t n)
181 const size_t L = 210;
182 const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
183 // If n is small enough, search in small_primes
184 if (n <= small_primes[N-1])
185 return *std::lower_bound(small_primes, small_primes + N, n);
186 // Else n > largest small_primes
187 // Check for overflow
188 __check_for_overflow(n);
189 // Start searching list of potential primes: L * k0 + indices[in]
190 const size_t M = sizeof(indices) / sizeof(indices[0]);
191 // Select first potential prime >= n
192 // Known a-priori n >= L
194 size_t in = static_cast<size_t>(std::lower_bound(indices, indices + M, n - k0 * L)
196 n = L * k0 + indices[in];
199 // Divide n by all primes or potential primes (i) until:
200 // 1. The division is even, so try next potential prime.
201 // 2. The i > sqrt(n), in which case n is prime.
202 // It is known a-priori that n is not divisible by 2, 3, 5 or 7,
203 // so don't test those (j == 5 -> divide by 11 first). And the
204 // potential primes start with 211, so don't test against the last
206 for (size_t j = 5; j < N - 1; ++j)
208 const std::size_t p = small_primes[j];
209 const std::size_t q = n / p;
215 // n wasn't divisible by small primes, try potential primes
220 std::size_t q = n / i;
555 // This will loop i to the next "plane" of potential primes
560 // n is not prime. Increment n to next potential prime.
566 n = L * k0 + indices[in];
570 _LIBCPP_END_NAMESPACE_STD