contrib/libc++/src/hash.cpp

   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 - k0 * 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