diff options
author | Abseil Team <absl-team@google.com> | 2020-11-17 11:25:13 -0800 |
---|---|---|
committer | Derek Mauro <dmauro@google.com> | 2020-11-17 14:40:39 -0500 |
commit | 4ae6730677ea3c2984f8bb0e4919bd0d9dd04f73 (patch) | |
tree | ae9d6d041faaff022f90fb0132ec53850c75512b /absl/hash | |
parent | 1b465af3bf865f588251470ea0dec60851a24041 (diff) |
Export of internal Abseil changes
--
77e2a9c277721f23a8df983c1efc6ed97c167964 by Derek Mauro <dmauro@google.com>:
Simplify an internal piece of CityHash to remove the conflicting
definition of uint128
PiperOrigin-RevId: 342906008
--
593dbb6d5fd32cc5d31e3ba1eda02e8ddeaeaaf6 by Gennadiy Rozental <rogeeff@google.com>:
Skip retired flags in GetAllFlags output.
This is a bug fix. We should not have released this interface producing retired flags. There should be no observable difference for the users who should not care about retired flags.
PiperOrigin-RevId: 342889378
--
bb77e07abff4dbd0a9c97eb85ee85cb39b84d04a by Abseil Team <absl-team@google.com>:
Extract `find_first_not_full` outside of the raw_hash_set.
This function is used in the following scenarios:
0. [relatively hot] insert, when actual new element is added.
1. [relatively cold] resize (explicit or on capacity grow)
2. [relatively cold] copy constructor
3. [cold] rehash on insert/erase (aka cache) use cases
Resize typically mitigated by `reserve` in performance critical cases. Rehashing happen relatively rare, when hash table become polluted with deleted slots.
We keep `find_first_not_full` in header, so that compiler still can inline it, when necessary (most notably in insert use case).
This reduce binary size since only one copy of this function will be present in the binary for all tables where the function is not inlined (at least in one case).
PiperOrigin-RevId: 342736300
GitOrigin-RevId: 77e2a9c277721f23a8df983c1efc6ed97c167964
Change-Id: I3fe9d054c66049bb598ea35c45fc800b1cdaa9b6
Diffstat (limited to 'absl/hash')
-rw-r--r-- | absl/hash/internal/city.cc | 9 | ||||
-rw-r--r-- | absl/hash/internal/city.h | 18 |
2 files changed, 5 insertions, 22 deletions
diff --git a/absl/hash/internal/city.cc b/absl/hash/internal/city.cc index 58d4bcb1..5460134e 100644 --- a/absl/hash/internal/city.cc +++ b/absl/hash/internal/city.cc @@ -200,10 +200,6 @@ static uint64_t Rotate(uint64_t val, int shift) { static uint64_t ShiftMix(uint64_t val) { return val ^ (val >> 47); } -static uint64_t HashLen16(uint64_t u, uint64_t v) { - return Hash128to64(uint128(u, v)); -} - static uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) { // Murmur-inspired hashing. uint64_t a = (u ^ v) * mul; @@ -214,6 +210,11 @@ static uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) { return b; } +static uint64_t HashLen16(uint64_t u, uint64_t v) { + const uint64_t kMul = 0x9ddfea08eb382d69ULL; + return HashLen16(u, v, kMul); +} + static uint64_t HashLen0to16(const char *s, size_t len) { if (len >= 8) { uint64_t mul = k2 + len * 2; diff --git a/absl/hash/internal/city.h b/absl/hash/internal/city.h index 9c1e7a57..393da0b9 100644 --- a/absl/hash/internal/city.h +++ b/absl/hash/internal/city.h @@ -56,11 +56,6 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace hash_internal { -typedef std::pair<uint64_t, uint64_t> uint128; - -inline uint64_t Uint128Low64(const uint128 &x) { return x.first; } -inline uint64_t Uint128High64(const uint128 &x) { return x.second; } - // Hash function for a byte array. uint64_t CityHash64(const char *s, size_t len); @@ -76,19 +71,6 @@ uint64_t CityHash64WithSeeds(const char *s, size_t len, uint64_t seed0, // Hash function for a byte array. Most useful in 32-bit binaries. uint32_t CityHash32(const char *s, size_t len); -// Hash 128 input bits down to 64 bits of output. -// This is intended to be a reasonably good hash function. -inline uint64_t Hash128to64(const uint128 &x) { - // Murmur-inspired hashing. - const uint64_t kMul = 0x9ddfea08eb382d69ULL; - uint64_t a = (Uint128Low64(x) ^ Uint128High64(x)) * kMul; - a ^= (a >> 47); - uint64_t b = (Uint128High64(x) ^ a) * kMul; - b ^= (b >> 47); - b *= kMul; - return b; -} - } // namespace hash_internal ABSL_NAMESPACE_END } // namespace absl |