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