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