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 #else 164 (void)N; 165 #endif 166 } 167 168 template <size_t _Sz = sizeof(size_t)> 169 inline _LIBCPP_INLINE_VISIBILITY 170 typename enable_if<_Sz == 8, void>::type 171 __check_for_overflow(size_t N) 172 { 173 #ifndef _LIBCPP_NO_EXCEPTIONS 174 if (N > 0xFFFFFFFFFFFFFFC5ull) 175 throw overflow_error("__next_prime overflow"); 176 #else 177 (void)N; 178 #endif 179 } 180 181 size_t 182 __next_prime(size_t n) 183 { 184 const size_t L = 210; 185 const size_t N = sizeof(small_primes) / sizeof(small_primes[0]); 186 // If n is small enough, search in small_primes 187 if (n <= small_primes[N-1]) 188 return *std::lower_bound(small_primes, small_primes + N, n); 189 // Else n > largest small_primes 190 // Check for overflow 191 __check_for_overflow(n); 192 // Start searching list of potential primes: L * k0 + indices[in] 193 const size_t M = sizeof(indices) / sizeof(indices[0]); 194 // Select first potential prime >= n 195 // Known a-priori n >= L 196 size_t k0 = n / L; 197 size_t in = static_cast<size_t>(std::lower_bound(indices, indices + M, n - k0 * L) 198 - indices); 199 n = L * k0 + indices[in]; 200 while (true) 201 { 202 // Divide n by all primes or potential primes (i) until: 203 // 1. The division is even, so try next potential prime. 204 // 2. The i > sqrt(n), in which case n is prime. 205 // It is known a-priori that n is not divisible by 2, 3, 5 or 7, 206 // so don't test those (j == 5 -> divide by 11 first). And the 207 // potential primes start with 211, so don't test against the last 208 // small prime. 209 for (size_t j = 5; j < N - 1; ++j) 210 { 211 const std::size_t p = small_primes[j]; 212 const std::size_t q = n / p; 213 if (q < p) 214 return n; 215 if (n == q * p) 216 goto next; 217 } 218 // n wasn't divisible by small primes, try potential primes 219 { 220 size_t i = 211; 221 while (true) 222 { 223 std::size_t q = n / i; 224 if (q < i) 225 return n; 226 if (n == q * i) 227 break; 228 229 i += 10; 230 q = n / i; 231 if (q < i) 232 return n; 233 if (n == q * i) 234 break; 235 236 i += 2; 237 q = n / i; 238 if (q < i) 239 return n; 240 if (n == q * i) 241 break; 242 243 i += 4; 244 q = n / i; 245 if (q < i) 246 return n; 247 if (n == q * i) 248 break; 249 250 i += 2; 251 q = n / i; 252 if (q < i) 253 return n; 254 if (n == q * i) 255 break; 256 257 i += 4; 258 q = n / i; 259 if (q < i) 260 return n; 261 if (n == q * i) 262 break; 263 264 i += 6; 265 q = n / i; 266 if (q < i) 267 return n; 268 if (n == q * i) 269 break; 270 271 i += 2; 272 q = n / i; 273 if (q < i) 274 return n; 275 if (n == q * i) 276 break; 277 278 i += 6; 279 q = n / i; 280 if (q < i) 281 return n; 282 if (n == q * i) 283 break; 284 285 i += 4; 286 q = n / i; 287 if (q < i) 288 return n; 289 if (n == q * i) 290 break; 291 292 i += 2; 293 q = n / i; 294 if (q < i) 295 return n; 296 if (n == q * i) 297 break; 298 299 i += 4; 300 q = n / i; 301 if (q < i) 302 return n; 303 if (n == q * i) 304 break; 305 306 i += 6; 307 q = n / i; 308 if (q < i) 309 return n; 310 if (n == q * i) 311 break; 312 313 i += 6; 314 q = n / i; 315 if (q < i) 316 return n; 317 if (n == q * i) 318 break; 319 320 i += 2; 321 q = n / i; 322 if (q < i) 323 return n; 324 if (n == q * i) 325 break; 326 327 i += 6; 328 q = n / i; 329 if (q < i) 330 return n; 331 if (n == q * i) 332 break; 333 334 i += 4; 335 q = n / i; 336 if (q < i) 337 return n; 338 if (n == q * i) 339 break; 340 341 i += 2; 342 q = n / i; 343 if (q < i) 344 return n; 345 if (n == q * i) 346 break; 347 348 i += 6; 349 q = n / i; 350 if (q < i) 351 return n; 352 if (n == q * i) 353 break; 354 355 i += 4; 356 q = n / i; 357 if (q < i) 358 return n; 359 if (n == q * i) 360 break; 361 362 i += 6; 363 q = n / i; 364 if (q < i) 365 return n; 366 if (n == q * i) 367 break; 368 369 i += 8; 370 q = n / i; 371 if (q < i) 372 return n; 373 if (n == q * i) 374 break; 375 376 i += 4; 377 q = n / i; 378 if (q < i) 379 return n; 380 if (n == q * i) 381 break; 382 383 i += 2; 384 q = n / i; 385 if (q < i) 386 return n; 387 if (n == q * i) 388 break; 389 390 i += 4; 391 q = n / i; 392 if (q < i) 393 return n; 394 if (n == q * i) 395 break; 396 397 i += 2; 398 q = n / i; 399 if (q < i) 400 return n; 401 if (n == q * i) 402 break; 403 404 i += 4; 405 q = n / i; 406 if (q < i) 407 return n; 408 if (n == q * i) 409 break; 410 411 i += 8; 412 q = n / i; 413 if (q < i) 414 return n; 415 if (n == q * i) 416 break; 417 418 i += 6; 419 q = n / i; 420 if (q < i) 421 return n; 422 if (n == q * i) 423 break; 424 425 i += 4; 426 q = n / i; 427 if (q < i) 428 return n; 429 if (n == q * i) 430 break; 431 432 i += 6; 433 q = n / i; 434 if (q < i) 435 return n; 436 if (n == q * i) 437 break; 438 439 i += 2; 440 q = n / i; 441 if (q < i) 442 return n; 443 if (n == q * i) 444 break; 445 446 i += 4; 447 q = n / i; 448 if (q < i) 449 return n; 450 if (n == q * i) 451 break; 452 453 i += 6; 454 q = n / i; 455 if (q < i) 456 return n; 457 if (n == q * i) 458 break; 459 460 i += 2; 461 q = n / i; 462 if (q < i) 463 return n; 464 if (n == q * i) 465 break; 466 467 i += 6; 468 q = n / i; 469 if (q < i) 470 return n; 471 if (n == q * i) 472 break; 473 474 i += 6; 475 q = n / i; 476 if (q < i) 477 return n; 478 if (n == q * i) 479 break; 480 481 i += 4; 482 q = n / i; 483 if (q < i) 484 return n; 485 if (n == q * i) 486 break; 487 488 i += 2; 489 q = n / i; 490 if (q < i) 491 return n; 492 if (n == q * i) 493 break; 494 495 i += 4; 496 q = n / i; 497 if (q < i) 498 return n; 499 if (n == q * i) 500 break; 501 502 i += 6; 503 q = n / i; 504 if (q < i) 505 return n; 506 if (n == q * i) 507 break; 508 509 i += 2; 510 q = n / i; 511 if (q < i) 512 return n; 513 if (n == q * i) 514 break; 515 516 i += 6; 517 q = n / i; 518 if (q < i) 519 return n; 520 if (n == q * i) 521 break; 522 523 i += 4; 524 q = n / i; 525 if (q < i) 526 return n; 527 if (n == q * i) 528 break; 529 530 i += 2; 531 q = n / i; 532 if (q < i) 533 return n; 534 if (n == q * i) 535 break; 536 537 i += 4; 538 q = n / i; 539 if (q < i) 540 return n; 541 if (n == q * i) 542 break; 543 544 i += 2; 545 q = n / i; 546 if (q < i) 547 return n; 548 if (n == q * i) 549 break; 550 551 i += 10; 552 q = n / i; 553 if (q < i) 554 return n; 555 if (n == q * i) 556 break; 557 558 // This will loop i to the next "plane" of potential primes 559 i += 2; 560 } 561 } 562 next: 563 // n is not prime. Increment n to next potential prime. 564 if (++in == M) 565 { 566 ++k0; 567 in = 0; 568 } 569 n = L * k0 + indices[in]; 570 } 571 } 572 573 _LIBCPP_END_NAMESPACE_STD 574