diff options
| author | Howard Hinnant <hhinnant@apple.com> | 2010-09-13 01:43:27 +0000 |
|---|---|---|
| committer | Howard Hinnant <hhinnant@apple.com> | 2010-09-13 01:43:27 +0000 |
| commit | 8fb62e398a9dff0d4f61b22928acf65d8a8e59eb (patch) | |
| tree | 42f4e80c1628c021b972a1aa4a74462c72b9162d /libcxx/src/hash.cpp | |
| parent | ac32b4ddc0ee0b5bf621209c1d8d341edff3e978 (diff) | |
| download | bcm5719-llvm-8fb62e398a9dff0d4f61b22928acf65d8a8e59eb.tar.gz bcm5719-llvm-8fb62e398a9dff0d4f61b22928acf65d8a8e59eb.zip | |
Experimenting with a new forward fomulation (kudos Daniel Kruegler), updated insert iterators to work better with pproxies, and doubled the speed of __next_prime.
llvm-svn: 113731
Diffstat (limited to 'libcxx/src/hash.cpp')
| -rw-r--r-- | libcxx/src/hash.cpp | 346 |
1 files changed, 198 insertions, 148 deletions
diff --git a/libcxx/src/hash.cpp b/libcxx/src/hash.cpp index 1189894f78b..dd4e8e3e1ac 100644 --- a/libcxx/src/hash.cpp +++ b/libcxx/src/hash.cpp @@ -157,7 +157,7 @@ __next_prime(size_t n) // Select first potential prime >= n // Known a-priori n >= L size_t k0 = n / L; - size_t in = std::lower_bound(indices, indices + M, n % L) - indices; + size_t in = std::lower_bound(indices, indices + M, n - k0 * L) - indices; n = L * k0 + indices[in]; while (true) { @@ -170,302 +170,352 @@ __next_prime(size_t n) // small prime. for (size_t j = 5; j < N - 1; ++j) { - if (n % small_primes[j] == 0) - goto next; - if (n / small_primes[j] < small_primes[j]) + const std::size_t p = small_primes[j]; + const std::size_t q = n / p; + if (q < p) return n; + if (n == q * p) + goto next; } // n wasn't divisible by small primes, try potential primes { size_t i = 211; while (true) { - if (n % i == 0) - break; - if (n / i < i) + std::size_t q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 10; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 8; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 8; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 6; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 4; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 2; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; i += 10; - if (n % i == 0) - break; - if (n / i < i) + q = n / i; + if (q < i) return n; + if (n == q * i) + break; // This will loop i to the next "plane" of potential primes i += 2; |
