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