1227825Stheraven//===-------------------------- hash.cpp ----------------------------------===// 2227825Stheraven// 3227825Stheraven// The LLVM Compiler Infrastructure 4227825Stheraven// 5227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 6227825Stheraven// Source Licenses. See LICENSE.TXT for details. 7227825Stheraven// 8227825Stheraven//===----------------------------------------------------------------------===// 9227825Stheraven 10227825Stheraven#include "__hash_table" 11227825Stheraven#include "algorithm" 12227825Stheraven#include "stdexcept" 13246487Stheraven#include "type_traits" 14227825Stheraven 15246487Stheraven#ifdef __clang__ 16246487Stheraven#pragma clang diagnostic ignored "-Wtautological-constant-out-of-range-compare" 17246487Stheraven#endif 18246487Stheraven 19227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 20227825Stheraven 21227825Stheravennamespace { 22227825Stheraven 23227825Stheraven// handle all next_prime(i) for i in [1, 210), special case 0 24227825Stheravenconst unsigned small_primes[] = 25227825Stheraven{ 26227825Stheraven 0, 27227825Stheraven 2, 28227825Stheraven 3, 29227825Stheraven 5, 30227825Stheraven 7, 31227825Stheraven 11, 32227825Stheraven 13, 33227825Stheraven 17, 34227825Stheraven 19, 35227825Stheraven 23, 36227825Stheraven 29, 37227825Stheraven 31, 38227825Stheraven 37, 39227825Stheraven 41, 40227825Stheraven 43, 41227825Stheraven 47, 42227825Stheraven 53, 43227825Stheraven 59, 44227825Stheraven 61, 45227825Stheraven 67, 46227825Stheraven 71, 47227825Stheraven 73, 48227825Stheraven 79, 49227825Stheraven 83, 50227825Stheraven 89, 51227825Stheraven 97, 52227825Stheraven 101, 53227825Stheraven 103, 54227825Stheraven 107, 55227825Stheraven 109, 56227825Stheraven 113, 57227825Stheraven 127, 58227825Stheraven 131, 59227825Stheraven 137, 60227825Stheraven 139, 61227825Stheraven 149, 62227825Stheraven 151, 63227825Stheraven 157, 64227825Stheraven 163, 65227825Stheraven 167, 66227825Stheraven 173, 67227825Stheraven 179, 68227825Stheraven 181, 69227825Stheraven 191, 70227825Stheraven 193, 71227825Stheraven 197, 72227825Stheraven 199, 73227825Stheraven 211 74227825Stheraven}; 75227825Stheraven 76227825Stheraven// potential primes = 210*k + indices[i], k >= 1 77227825Stheraven// these numbers are not divisible by 2, 3, 5 or 7 78227825Stheraven// (or any integer 2 <= j <= 10 for that matter). 79227825Stheravenconst unsigned indices[] = 80227825Stheraven{ 81227825Stheraven 1, 82227825Stheraven 11, 83227825Stheraven 13, 84227825Stheraven 17, 85227825Stheraven 19, 86227825Stheraven 23, 87227825Stheraven 29, 88227825Stheraven 31, 89227825Stheraven 37, 90227825Stheraven 41, 91227825Stheraven 43, 92227825Stheraven 47, 93227825Stheraven 53, 94227825Stheraven 59, 95227825Stheraven 61, 96227825Stheraven 67, 97227825Stheraven 71, 98227825Stheraven 73, 99227825Stheraven 79, 100227825Stheraven 83, 101227825Stheraven 89, 102227825Stheraven 97, 103227825Stheraven 101, 104227825Stheraven 103, 105227825Stheraven 107, 106227825Stheraven 109, 107227825Stheraven 113, 108227825Stheraven 121, 109227825Stheraven 127, 110227825Stheraven 131, 111227825Stheraven 137, 112227825Stheraven 139, 113227825Stheraven 143, 114227825Stheraven 149, 115227825Stheraven 151, 116227825Stheraven 157, 117227825Stheraven 163, 118227825Stheraven 167, 119227825Stheraven 169, 120227825Stheraven 173, 121227825Stheraven 179, 122227825Stheraven 181, 123227825Stheraven 187, 124227825Stheraven 191, 125227825Stheraven 193, 126227825Stheraven 197, 127227825Stheraven 199, 128227825Stheraven 209 129227825Stheraven}; 130227825Stheraven 131227825Stheraven} 132227825Stheraven 133227825Stheraven// Returns: If n == 0, returns 0. Else returns the lowest prime number that 134227825Stheraven// is greater than or equal to n. 135227825Stheraven// 136227825Stheraven// The algorithm creates a list of small primes, plus an open-ended list of 137227825Stheraven// potential primes. All prime numbers are potential prime numbers. However 138227825Stheraven// some potential prime numbers are not prime. In an ideal world, all potential 139278724Sdim// prime numbers would be prime. Candidate prime numbers are chosen as the next 140227825Stheraven// highest potential prime. Then this number is tested for prime by dividing it 141227825Stheraven// by all potential prime numbers less than the sqrt of the candidate. 142227825Stheraven// 143227825Stheraven// This implementation defines potential primes as those numbers not divisible 144227825Stheraven// by 2, 3, 5, and 7. Other (common) implementations define potential primes 145227825Stheraven// as those not divisible by 2. A few other implementations define potential 146227825Stheraven// primes as those not divisible by 2 or 3. By raising the number of small 147227825Stheraven// primes which the potential prime is not divisible by, the set of potential 148227825Stheraven// primes more closely approximates the set of prime numbers. And thus there 149227825Stheraven// are fewer potential primes to search, and fewer potential primes to divide 150227825Stheraven// against. 151227825Stheraven 152246487Stheraventemplate <size_t _Sz = sizeof(size_t)> 153227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 154246487Stheraventypename enable_if<_Sz == 4, void>::type 155246487Stheraven__check_for_overflow(size_t N) 156227825Stheraven{ 157246487Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 158227825Stheraven if (N > 0xFFFFFFFB) 159227825Stheraven throw overflow_error("__next_prime overflow"); 160249998Sdim#else 161249998Sdim (void)N; 162227825Stheraven#endif 163227825Stheraven} 164227825Stheraven 165246487Stheraventemplate <size_t _Sz = sizeof(size_t)> 166227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 167246487Stheraventypename enable_if<_Sz == 8, void>::type 168246487Stheraven__check_for_overflow(size_t N) 169227825Stheraven{ 170246487Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 171227825Stheraven if (N > 0xFFFFFFFFFFFFFFC5ull) 172227825Stheraven throw overflow_error("__next_prime overflow"); 173249998Sdim#else 174249998Sdim (void)N; 175227825Stheraven#endif 176227825Stheraven} 177227825Stheraven 178227825Stheravensize_t 179227825Stheraven__next_prime(size_t n) 180227825Stheraven{ 181227825Stheraven const size_t L = 210; 182227825Stheraven const size_t N = sizeof(small_primes) / sizeof(small_primes[0]); 183227825Stheraven // If n is small enough, search in small_primes 184227825Stheraven if (n <= small_primes[N-1]) 185227825Stheraven return *std::lower_bound(small_primes, small_primes + N, n); 186227825Stheraven // Else n > largest small_primes 187227825Stheraven // Check for overflow 188246487Stheraven __check_for_overflow(n); 189227825Stheraven // Start searching list of potential primes: L * k0 + indices[in] 190227825Stheraven const size_t M = sizeof(indices) / sizeof(indices[0]); 191227825Stheraven // Select first potential prime >= n 192227825Stheraven // Known a-priori n >= L 193227825Stheraven size_t k0 = n / L; 194232950Stheraven size_t in = static_cast<size_t>(std::lower_bound(indices, indices + M, n - k0 * L) 195232950Stheraven - indices); 196227825Stheraven n = L * k0 + indices[in]; 197227825Stheraven while (true) 198227825Stheraven { 199227825Stheraven // Divide n by all primes or potential primes (i) until: 200227825Stheraven // 1. The division is even, so try next potential prime. 201227825Stheraven // 2. The i > sqrt(n), in which case n is prime. 202227825Stheraven // It is known a-priori that n is not divisible by 2, 3, 5 or 7, 203227825Stheraven // so don't test those (j == 5 -> divide by 11 first). And the 204227825Stheraven // potential primes start with 211, so don't test against the last 205227825Stheraven // small prime. 206227825Stheraven for (size_t j = 5; j < N - 1; ++j) 207227825Stheraven { 208227825Stheraven const std::size_t p = small_primes[j]; 209227825Stheraven const std::size_t q = n / p; 210227825Stheraven if (q < p) 211227825Stheraven return n; 212227825Stheraven if (n == q * p) 213227825Stheraven goto next; 214227825Stheraven } 215227825Stheraven // n wasn't divisible by small primes, try potential primes 216227825Stheraven { 217227825Stheraven size_t i = 211; 218227825Stheraven while (true) 219227825Stheraven { 220227825Stheraven std::size_t q = n / i; 221227825Stheraven if (q < i) 222227825Stheraven return n; 223227825Stheraven if (n == q * i) 224227825Stheraven break; 225227825Stheraven 226227825Stheraven i += 10; 227227825Stheraven q = n / i; 228227825Stheraven if (q < i) 229227825Stheraven return n; 230227825Stheraven if (n == q * i) 231227825Stheraven break; 232227825Stheraven 233227825Stheraven i += 2; 234227825Stheraven q = n / i; 235227825Stheraven if (q < i) 236227825Stheraven return n; 237227825Stheraven if (n == q * i) 238227825Stheraven break; 239227825Stheraven 240227825Stheraven i += 4; 241227825Stheraven q = n / i; 242227825Stheraven if (q < i) 243227825Stheraven return n; 244227825Stheraven if (n == q * i) 245227825Stheraven break; 246227825Stheraven 247227825Stheraven i += 2; 248227825Stheraven q = n / i; 249227825Stheraven if (q < i) 250227825Stheraven return n; 251227825Stheraven if (n == q * i) 252227825Stheraven break; 253227825Stheraven 254227825Stheraven i += 4; 255227825Stheraven q = n / i; 256227825Stheraven if (q < i) 257227825Stheraven return n; 258227825Stheraven if (n == q * i) 259227825Stheraven break; 260227825Stheraven 261227825Stheraven i += 6; 262227825Stheraven q = n / i; 263227825Stheraven if (q < i) 264227825Stheraven return n; 265227825Stheraven if (n == q * i) 266227825Stheraven break; 267227825Stheraven 268227825Stheraven i += 2; 269227825Stheraven q = n / i; 270227825Stheraven if (q < i) 271227825Stheraven return n; 272227825Stheraven if (n == q * i) 273227825Stheraven break; 274227825Stheraven 275227825Stheraven i += 6; 276227825Stheraven q = n / i; 277227825Stheraven if (q < i) 278227825Stheraven return n; 279227825Stheraven if (n == q * i) 280227825Stheraven break; 281227825Stheraven 282227825Stheraven i += 4; 283227825Stheraven q = n / i; 284227825Stheraven if (q < i) 285227825Stheraven return n; 286227825Stheraven if (n == q * i) 287227825Stheraven break; 288227825Stheraven 289227825Stheraven i += 2; 290227825Stheraven q = n / i; 291227825Stheraven if (q < i) 292227825Stheraven return n; 293227825Stheraven if (n == q * i) 294227825Stheraven break; 295227825Stheraven 296227825Stheraven i += 4; 297227825Stheraven q = n / i; 298227825Stheraven if (q < i) 299227825Stheraven return n; 300227825Stheraven if (n == q * i) 301227825Stheraven break; 302227825Stheraven 303227825Stheraven i += 6; 304227825Stheraven q = n / i; 305227825Stheraven if (q < i) 306227825Stheraven return n; 307227825Stheraven if (n == q * i) 308227825Stheraven break; 309227825Stheraven 310227825Stheraven i += 6; 311227825Stheraven q = n / i; 312227825Stheraven if (q < i) 313227825Stheraven return n; 314227825Stheraven if (n == q * i) 315227825Stheraven break; 316227825Stheraven 317227825Stheraven i += 2; 318227825Stheraven q = n / i; 319227825Stheraven if (q < i) 320227825Stheraven return n; 321227825Stheraven if (n == q * i) 322227825Stheraven break; 323227825Stheraven 324227825Stheraven i += 6; 325227825Stheraven q = n / i; 326227825Stheraven if (q < i) 327227825Stheraven return n; 328227825Stheraven if (n == q * i) 329227825Stheraven break; 330227825Stheraven 331227825Stheraven i += 4; 332227825Stheraven q = n / i; 333227825Stheraven if (q < i) 334227825Stheraven return n; 335227825Stheraven if (n == q * i) 336227825Stheraven break; 337227825Stheraven 338227825Stheraven i += 2; 339227825Stheraven q = n / i; 340227825Stheraven if (q < i) 341227825Stheraven return n; 342227825Stheraven if (n == q * i) 343227825Stheraven break; 344227825Stheraven 345227825Stheraven i += 6; 346227825Stheraven q = n / i; 347227825Stheraven if (q < i) 348227825Stheraven return n; 349227825Stheraven if (n == q * i) 350227825Stheraven break; 351227825Stheraven 352227825Stheraven i += 4; 353227825Stheraven q = n / i; 354227825Stheraven if (q < i) 355227825Stheraven return n; 356227825Stheraven if (n == q * i) 357227825Stheraven break; 358227825Stheraven 359227825Stheraven i += 6; 360227825Stheraven q = n / i; 361227825Stheraven if (q < i) 362227825Stheraven return n; 363227825Stheraven if (n == q * i) 364227825Stheraven break; 365227825Stheraven 366227825Stheraven i += 8; 367227825Stheraven q = n / i; 368227825Stheraven if (q < i) 369227825Stheraven return n; 370227825Stheraven if (n == q * i) 371227825Stheraven break; 372227825Stheraven 373227825Stheraven i += 4; 374227825Stheraven q = n / i; 375227825Stheraven if (q < i) 376227825Stheraven return n; 377227825Stheraven if (n == q * i) 378227825Stheraven break; 379227825Stheraven 380227825Stheraven i += 2; 381227825Stheraven q = n / i; 382227825Stheraven if (q < i) 383227825Stheraven return n; 384227825Stheraven if (n == q * i) 385227825Stheraven break; 386227825Stheraven 387227825Stheraven i += 4; 388227825Stheraven q = n / i; 389227825Stheraven if (q < i) 390227825Stheraven return n; 391227825Stheraven if (n == q * i) 392227825Stheraven break; 393227825Stheraven 394227825Stheraven i += 2; 395227825Stheraven q = n / i; 396227825Stheraven if (q < i) 397227825Stheraven return n; 398227825Stheraven if (n == q * i) 399227825Stheraven break; 400227825Stheraven 401227825Stheraven i += 4; 402227825Stheraven q = n / i; 403227825Stheraven if (q < i) 404227825Stheraven return n; 405227825Stheraven if (n == q * i) 406227825Stheraven break; 407227825Stheraven 408227825Stheraven i += 8; 409227825Stheraven q = n / i; 410227825Stheraven if (q < i) 411227825Stheraven return n; 412227825Stheraven if (n == q * i) 413227825Stheraven break; 414227825Stheraven 415227825Stheraven i += 6; 416227825Stheraven q = n / i; 417227825Stheraven if (q < i) 418227825Stheraven return n; 419227825Stheraven if (n == q * i) 420227825Stheraven break; 421227825Stheraven 422227825Stheraven i += 4; 423227825Stheraven q = n / i; 424227825Stheraven if (q < i) 425227825Stheraven return n; 426227825Stheraven if (n == q * i) 427227825Stheraven break; 428227825Stheraven 429227825Stheraven i += 6; 430227825Stheraven q = n / i; 431227825Stheraven if (q < i) 432227825Stheraven return n; 433227825Stheraven if (n == q * i) 434227825Stheraven break; 435227825Stheraven 436227825Stheraven i += 2; 437227825Stheraven q = n / i; 438227825Stheraven if (q < i) 439227825Stheraven return n; 440227825Stheraven if (n == q * i) 441227825Stheraven break; 442227825Stheraven 443227825Stheraven i += 4; 444227825Stheraven q = n / i; 445227825Stheraven if (q < i) 446227825Stheraven return n; 447227825Stheraven if (n == q * i) 448227825Stheraven break; 449227825Stheraven 450227825Stheraven i += 6; 451227825Stheraven q = n / i; 452227825Stheraven if (q < i) 453227825Stheraven return n; 454227825Stheraven if (n == q * i) 455227825Stheraven break; 456227825Stheraven 457227825Stheraven i += 2; 458227825Stheraven q = n / i; 459227825Stheraven if (q < i) 460227825Stheraven return n; 461227825Stheraven if (n == q * i) 462227825Stheraven break; 463227825Stheraven 464227825Stheraven i += 6; 465227825Stheraven q = n / i; 466227825Stheraven if (q < i) 467227825Stheraven return n; 468227825Stheraven if (n == q * i) 469227825Stheraven break; 470227825Stheraven 471227825Stheraven i += 6; 472227825Stheraven q = n / i; 473227825Stheraven if (q < i) 474227825Stheraven return n; 475227825Stheraven if (n == q * i) 476227825Stheraven break; 477227825Stheraven 478227825Stheraven i += 4; 479227825Stheraven q = n / i; 480227825Stheraven if (q < i) 481227825Stheraven return n; 482227825Stheraven if (n == q * i) 483227825Stheraven break; 484227825Stheraven 485227825Stheraven i += 2; 486227825Stheraven q = n / i; 487227825Stheraven if (q < i) 488227825Stheraven return n; 489227825Stheraven if (n == q * i) 490227825Stheraven break; 491227825Stheraven 492227825Stheraven i += 4; 493227825Stheraven q = n / i; 494227825Stheraven if (q < i) 495227825Stheraven return n; 496227825Stheraven if (n == q * i) 497227825Stheraven break; 498227825Stheraven 499227825Stheraven i += 6; 500227825Stheraven q = n / i; 501227825Stheraven if (q < i) 502227825Stheraven return n; 503227825Stheraven if (n == q * i) 504227825Stheraven break; 505227825Stheraven 506227825Stheraven i += 2; 507227825Stheraven q = n / i; 508227825Stheraven if (q < i) 509227825Stheraven return n; 510227825Stheraven if (n == q * i) 511227825Stheraven break; 512227825Stheraven 513227825Stheraven i += 6; 514227825Stheraven q = n / i; 515227825Stheraven if (q < i) 516227825Stheraven return n; 517227825Stheraven if (n == q * i) 518227825Stheraven break; 519227825Stheraven 520227825Stheraven i += 4; 521227825Stheraven q = n / i; 522227825Stheraven if (q < i) 523227825Stheraven return n; 524227825Stheraven if (n == q * i) 525227825Stheraven break; 526227825Stheraven 527227825Stheraven i += 2; 528227825Stheraven q = n / i; 529227825Stheraven if (q < i) 530227825Stheraven return n; 531227825Stheraven if (n == q * i) 532227825Stheraven break; 533227825Stheraven 534227825Stheraven i += 4; 535227825Stheraven q = n / i; 536227825Stheraven if (q < i) 537227825Stheraven return n; 538227825Stheraven if (n == q * i) 539227825Stheraven break; 540227825Stheraven 541227825Stheraven i += 2; 542227825Stheraven q = n / i; 543227825Stheraven if (q < i) 544227825Stheraven return n; 545227825Stheraven if (n == q * i) 546227825Stheraven break; 547227825Stheraven 548227825Stheraven i += 10; 549227825Stheraven q = n / i; 550227825Stheraven if (q < i) 551227825Stheraven return n; 552227825Stheraven if (n == q * i) 553227825Stheraven break; 554227825Stheraven 555227825Stheraven // This will loop i to the next "plane" of potential primes 556227825Stheraven i += 2; 557227825Stheraven } 558227825Stheraven } 559227825Stheravennext: 560227825Stheraven // n is not prime. Increment n to next potential prime. 561227825Stheraven if (++in == M) 562227825Stheraven { 563227825Stheraven ++k0; 564227825Stheraven in = 0; 565227825Stheraven } 566227825Stheraven n = L * k0 + indices[in]; 567227825Stheraven } 568227825Stheraven} 569227825Stheraven 570227825Stheraven_LIBCPP_END_NAMESPACE_STD 571