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