diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index e10a6ac..9f88825 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -159,8 +159,6 @@ "hash/internal/hash.h" "hash/internal/hash.cc" "hash/internal/spy_hash_state.h" - "hash/internal/low_level_hash.h" - "hash/internal/low_level_hash.cc" "hash/internal/weakly_mixed_integer.h" "log/absl_check.h" "log/absl_log.h"
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 9a79523..6658772 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -410,6 +410,7 @@ linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ "//absl/base:config", + "//absl/hash", "//absl/memory", "//absl/meta:type_traits", "//absl/utility", @@ -749,6 +750,7 @@ ":hashtable_debug_hooks", ":hashtablez_sampler", ":raw_hash_set_resize_impl", + "//absl/base", "//absl/base:config", "//absl/base:core_headers", "//absl/base:dynamic_annotations",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index b1c3ffa..6adba18 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -469,6 +469,7 @@ ${ABSL_DEFAULT_COPTS} DEPS absl::config + absl::hash absl::memory absl::type_traits absl::utility @@ -786,6 +787,7 @@ COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::base absl::bits absl::common_policy_traits absl::compressed_tuple
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h index 5fa5023..a1f4f24 100644 --- a/absl/container/flat_hash_map.h +++ b/absl/container/flat_hash_map.h
@@ -660,10 +660,10 @@ std::forward<Args>(args)...); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return memory_internal::IsLayoutCompatible<K, V>::value - ? &TypeErasedApplyToSlotFn<Hash, K> + ? &TypeErasedApplyToSlotFn<Hash, K, kIsDefault> : nullptr; }
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index bc1ceb1..2d25552 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h
@@ -558,9 +558,9 @@ static size_t space_used(const T*) { return 0; } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { - return &TypeErasedApplyToSlotFn<Hash, T>; + return &TypeErasedApplyToSlotFn<Hash, T, kIsDefault>; } }; } // namespace container_internal
diff --git a/absl/container/flat_hash_set_test.cc b/absl/container/flat_hash_set_test.cc index bb90efa..ca069b4 100644 --- a/absl/container/flat_hash_set_test.cc +++ b/absl/container/flat_hash_set_test.cc
@@ -383,6 +383,20 @@ EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3)); } +TEST(FlatHashSet, IsDefaultHash) { + using absl::container_internal::hashtable_debug_internal:: + HashtableDebugAccess; + EXPECT_EQ(HashtableDebugAccess<flat_hash_set<int>>::kIsDefaultHash, true); + EXPECT_EQ(HashtableDebugAccess<flat_hash_set<std::string>>::kIsDefaultHash, + true); + + struct Hash { + size_t operator()(size_t i) const { return i; } + }; + EXPECT_EQ((HashtableDebugAccess<flat_hash_set<size_t, Hash>>::kIsDefaultHash), + false); +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index ed7b90b..8c97469 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -26,6 +26,7 @@ #include <utility> #include "absl/base/config.h" +#include "absl/hash/hash.h" #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" #include "absl/utility/utility.h" @@ -483,19 +484,33 @@ // Variadic arguments hash function that ignore the rest of the arguments. // Useful for usage with policy traits. -template <class Hash> +template <class Hash, bool kIsDefault> struct HashElement { + HashElement(const Hash& h, size_t s) : hash(h), seed(s) {} + template <class K, class... Args> size_t operator()(const K& key, Args&&...) const { - return h(key); + if constexpr (kIsDefault) { + // TODO(b/384509507): resolve `no header providing + // "absl::hash_internal::SupportsHashWithSeed" is directly included`. + // Maybe we should make "internal/hash.h" be a separate library. + return absl::hash_internal::HashWithSeed().hash(hash, key, seed); + } + // NOLINTNEXTLINE(clang-diagnostic-sign-conversion) + return hash(key) ^ seed; } - const Hash& h; + const Hash& hash; + size_t seed; }; // No arguments function hash function for a specific key. -template <class Hash, class Key> +template <class Hash, class Key, bool kIsDefault> struct HashKey { - size_t operator()() const { return HashElement<Hash>{hash}(key); } + HashKey(const Hash& h, const Key& k) : hash(h), key(k) {} + + size_t operator()(size_t seed) const { + return HashElement<Hash, kIsDefault>{hash, seed}(key); + } const Hash& hash; const Key& key; }; @@ -513,23 +528,24 @@ }; // Type erased function for computing hash of the slot. -using HashSlotFn = size_t (*)(const void* hash_fn, void* slot); +using HashSlotFn = size_t (*)(const void* hash_fn, void* slot, size_t seed); // Type erased function to apply `Fn` to data inside of the `slot`. // The data is expected to have type `T`. -template <class Fn, class T> -size_t TypeErasedApplyToSlotFn(const void* fn, void* slot) { +template <class Fn, class T, bool kIsDefault> +size_t TypeErasedApplyToSlotFn(const void* fn, void* slot, size_t seed) { const auto* f = static_cast<const Fn*>(fn); - return HashElement<Fn>{*f}(*static_cast<const T*>(slot)); + return HashElement<Fn, kIsDefault>{*f, seed}(*static_cast<const T*>(slot)); } // Type erased function to apply `Fn` to data inside of the `*slot_ptr`. // The data is expected to have type `T`. -template <class Fn, class T> -size_t TypeErasedDerefAndApplyToSlotFn(const void* fn, void* slot_ptr) { +template <class Fn, class T, bool kIsDefault> +size_t TypeErasedDerefAndApplyToSlotFn(const void* fn, void* slot_ptr, + size_t seed) { const auto* f = static_cast<const Fn*>(fn); const T* slot = *static_cast<const T**>(slot_ptr); - return HashElement<Fn>{*f}(*slot); + return HashElement<Fn, kIsDefault>{*f, seed}(*slot); } } // namespace container_internal
diff --git a/absl/container/internal/container_memory_test.cc b/absl/container/internal/container_memory_test.cc index 7e4357d..97b09f7 100644 --- a/absl/container/internal/container_memory_test.cc +++ b/absl/container/internal/container_memory_test.cc
@@ -300,16 +300,46 @@ TEST(ApplyTest, TypeErasedApplyToSlotFn) { size_t x = 7; + size_t seed = 100; auto fn = [](size_t v) { return v * 2; }; - EXPECT_EQ((TypeErasedApplyToSlotFn<decltype(fn), size_t>(&fn, &x)), 14); + EXPECT_EQ( + (TypeErasedApplyToSlotFn<decltype(fn), size_t, /*kIsDefault=*/false>( + &fn, &x, seed)), + (HashElement<decltype(fn), /*kIsDefault=*/false>(fn, seed)(x))); } TEST(ApplyTest, TypeErasedDerefAndApplyToSlotFn) { size_t x = 7; + size_t seed = 100; auto fn = [](size_t v) { return v * 2; }; size_t* x_ptr = &x; + EXPECT_EQ((TypeErasedDerefAndApplyToSlotFn<decltype(fn), size_t, + /*kIsDefault=*/false>(&fn, &x_ptr, + seed)), + (HashElement<decltype(fn), /*kIsDefault=*/false>(fn, seed)(x))); +} + +TEST(HashElement, DefaultHash) { + size_t x = 7; + size_t seed = 100; + struct HashWithSeed { + size_t operator()(size_t v) const { return v * 2; } + size_t hash_with_seed(size_t v, size_t seed) const { + return v * 2 + seed * 3; + } + } hash; + EXPECT_EQ((HashElement<HashWithSeed, /*kIsDefault=*/true>(hash, seed)(x)), + hash.hash_with_seed(x, seed)); +} + +TEST(HashElement, NonDefaultHash) { + size_t x = 7; + size_t seed = 100; + auto fn = [](size_t v) { return v * 2; }; EXPECT_EQ( - (TypeErasedDerefAndApplyToSlotFn<decltype(fn), size_t>(&fn, &x_ptr)), 14); + (HashElement<decltype(fn), /*kIsDefault=*/false>( + fn, seed)(x)), + fn(x) ^ seed); } } // namespace
diff --git a/absl/container/internal/hash_function_defaults.h b/absl/container/internal/hash_function_defaults.h index c2a757b..eefecab 100644 --- a/absl/container/internal/hash_function_defaults.h +++ b/absl/container/internal/hash_function_defaults.h
@@ -79,6 +79,18 @@ size_t operator()(const absl::Cord& v) const { return absl::Hash<absl::Cord>{}(v); } + + private: + friend struct absl::hash_internal::HashWithSeed; + + size_t hash_with_seed(absl::string_view v, size_t seed) const { + return absl::hash_internal::HashWithSeed().hash( + absl::Hash<absl::string_view>{}, v, seed); + } + size_t hash_with_seed(const absl::Cord& v, size_t seed) const { + return absl::hash_internal::HashWithSeed().hash(absl::Hash<absl::Cord>{}, v, + seed); + } }; struct StringEq {
diff --git a/absl/container/internal/hash_policy_traits.h b/absl/container/internal/hash_policy_traits.h index 1d7c910..82eed2a 100644 --- a/absl/container/internal/hash_policy_traits.h +++ b/absl/container/internal/hash_policy_traits.h
@@ -146,7 +146,7 @@ return P::value(elem); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { // get_hash_slot_fn may return nullptr to signal that non type erased function // should be used. GCC warns against comparing function address with nullptr. @@ -155,9 +155,9 @@ // silent error: the address of * will never be NULL [-Werror=address] #pragma GCC diagnostic ignored "-Waddress" #endif - return Policy::template get_hash_slot_fn<Hash>() == nullptr - ? &hash_slot_fn_non_type_erased<Hash> - : Policy::template get_hash_slot_fn<Hash>(); + return Policy::template get_hash_slot_fn<Hash, kIsDefault>() == nullptr + ? &hash_slot_fn_non_type_erased<Hash, kIsDefault> + : Policy::template get_hash_slot_fn<Hash, kIsDefault>(); #if defined(__GNUC__) && !defined(__clang__) #pragma GCC diagnostic pop #endif @@ -167,10 +167,12 @@ static constexpr bool soo_enabled() { return soo_enabled_impl(Rank1{}); } private: - template <class Hash> - static size_t hash_slot_fn_non_type_erased(const void* hash_fn, void* slot) { - return Policy::apply(HashElement<Hash>{*static_cast<const Hash*>(hash_fn)}, - Policy::element(static_cast<slot_type*>(slot))); + template <class Hash, bool kIsDefault> + static size_t hash_slot_fn_non_type_erased(const void* hash_fn, void* slot, + size_t seed) { + return Policy::apply( + HashElement<Hash, kIsDefault>{*static_cast<const Hash*>(hash_fn), seed}, + Policy::element(static_cast<slot_type*>(slot))); } // Use go/ranked-overloads for dispatching. Rank1 is preferred.
diff --git a/absl/container/internal/hash_policy_traits_test.cc b/absl/container/internal/hash_policy_traits_test.cc index 2d2c7c2..03de132 100644 --- a/absl/container/internal/hash_policy_traits_test.cc +++ b/absl/container/internal/hash_policy_traits_test.cc
@@ -45,7 +45,7 @@ static std::function<int(int)> apply_impl; static std::function<Slot&(Slot*)> value; - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -99,7 +99,7 @@ return fn(v); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -108,9 +108,9 @@ size_t* PolicyNoHashFn::apply_called_count; struct PolicyCustomHashFn : PolicyNoHashFn { - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { - return &TypeErasedApplyToSlotFn<Hash, int>; + return &TypeErasedApplyToSlotFn<Hash, int, kIsDefault>; } }; @@ -120,9 +120,11 @@ Hash hasher; Slot value = 7; - auto* fn = hash_policy_traits<PolicyNoHashFn>::get_hash_slot_fn<Hash>(); + auto* fn = hash_policy_traits<PolicyNoHashFn>::get_hash_slot_fn< + Hash, /*kIsDefault=*/false>(); EXPECT_NE(fn, nullptr); - EXPECT_EQ(fn(&hasher, &value), hasher(value)); + EXPECT_EQ(fn(&hasher, &value, 100), + (HashElement<Hash, /*kIsDefault=*/false>(hasher, 100)(value))); EXPECT_EQ(apply_called_count, 1); } @@ -132,9 +134,12 @@ Hash hasher; Slot value = 7; - auto* fn = hash_policy_traits<PolicyCustomHashFn>::get_hash_slot_fn<Hash>(); - EXPECT_EQ(fn, PolicyCustomHashFn::get_hash_slot_fn<Hash>()); - EXPECT_EQ(fn(&hasher, &value), hasher(value)); + auto* fn = hash_policy_traits<PolicyCustomHashFn>::get_hash_slot_fn< + Hash, /*kIsDefault=*/false>(); + EXPECT_EQ( + fn, (PolicyCustomHashFn::get_hash_slot_fn<Hash, /*kIsDefault=*/false>())); + EXPECT_EQ(fn(&hasher, &value, 100), + (HashElement<Hash, /*kIsDefault=*/false>(hasher, 100)(value))); EXPECT_EQ(apply_called_count, 0); }
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index daa9ff6..640c5a5 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -88,13 +88,13 @@ return value ^ static_cast<size_t>(reinterpret_cast<uintptr_t>(&counter)); } -bool ShouldRehashForBugDetection(PerTableSeed seed, size_t capacity) { +bool ShouldRehashForBugDetection(size_t capacity) { // Note: we can't use the abseil-random library because abseil-random // depends on swisstable. We want to return true with probability // `min(1, RehashProbabilityConstant() / capacity())`. In order to do this, // we probe based on a random hash and see if the offset is less than // RehashProbabilityConstant(). - return probe(seed, capacity, absl::HashOf(RandomSeed())).offset() < + return probe(capacity, absl::HashOf(RandomSeed())).offset() < RehashProbabilityConstant(); } @@ -140,23 +140,22 @@ } bool CommonFieldsGenerationInfoEnabled:: - should_rehash_for_bug_detection_on_insert(PerTableSeed seed, - size_t capacity) const { + should_rehash_for_bug_detection_on_insert(size_t capacity) const { if (reserved_growth_ == kReservedGrowthJustRanOut) return true; if (reserved_growth_ > 0) return false; - return ShouldRehashForBugDetection(seed, capacity); + return ShouldRehashForBugDetection(capacity); } bool CommonFieldsGenerationInfoEnabled::should_rehash_for_bug_detection_on_move( - PerTableSeed seed, size_t capacity) const { - return ShouldRehashForBugDetection(seed, capacity); + size_t capacity) const { + return ShouldRehashForBugDetection(capacity); } namespace { FindInfo find_first_non_full_from_h1(const ctrl_t* ctrl, size_t h1, size_t capacity) { - auto seq = probe(h1, capacity); + auto seq = probe_h1(capacity, h1); if (IsEmptyOrDeleted(ctrl[seq.offset()])) { return {seq.offset(), /*probe_length=*/0}; } @@ -248,7 +247,7 @@ } FindInfo find_first_non_full(const CommonFields& common, size_t hash) { - return find_first_non_full_from_h1(common.control(), H1(hash, common.seed()), + return find_first_non_full_from_h1(common.control(), H1(hash), common.capacity()); } @@ -344,7 +343,7 @@ continue; } if (!IsDeleted(ctrl[i])) continue; - const size_t hash = (*hasher)(hash_fn, slot_ptr); + const size_t hash = (*hasher)(hash_fn, slot_ptr, common.seed().seed()); const FindInfo target = find_first_non_full(common, hash); const size_t new_i = target.offset; total_probe_length += target.probe_length; @@ -576,9 +575,10 @@ void* new_slots = common.slot_array(); const void* hash_fn = policy.hash_fn(common); const size_t slot_size = policy.slot_size; + const size_t seed = common.seed().seed(); const auto insert_slot = [&](void* slot) { - size_t hash = policy.hash_slot(hash_fn, slot); + size_t hash = policy.hash_slot(hash_fn, slot, seed); FindInfo target; if (common.is_small()) { target = FindInfo{0, 0}; @@ -687,8 +687,9 @@ common.set_capacity(new_capacity); const auto [new_ctrl, new_slots] = AllocBackingArray(common, policy, new_capacity, has_infoz, alloc); - common.set_control</*kGenerateSeed=*/true>(new_ctrl); + common.set_control(new_ctrl); common.set_slots(new_slots); + common.generate_new_seed(has_infoz); size_t total_probe_length = 0; ResetCtrl(common, slot_size); @@ -738,23 +739,26 @@ // It is rare to resize an SOO table with one element to a large size. // Requires: `c` contains SOO data. void InsertOldSooSlotAndInitializeControlBytes( - CommonFields& c, const PolicyFunctions& __restrict policy, size_t hash, - ctrl_t* new_ctrl, void* new_slots) { + CommonFields& c, const PolicyFunctions& __restrict policy, ctrl_t* new_ctrl, + void* new_slots, bool has_infoz) { ABSL_SWISSTABLE_ASSERT(c.size() == policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(policy.soo_enabled); size_t new_capacity = c.capacity(); - c.generate_new_seed(); - size_t offset = probe(c.seed(), new_capacity, hash).offset(); + c.generate_new_seed(has_infoz); + + const size_t soo_slot_hash = + policy.hash_slot(policy.hash_fn(c), c.soo_data(), c.seed().seed()); + size_t offset = probe(new_capacity, soo_slot_hash).offset(); offset = offset == new_capacity ? 0 : offset; SanitizerPoisonMemoryRegion(new_slots, policy.slot_size * new_capacity); void* target_slot = SlotAddress(new_slots, offset, policy.slot_size); SanitizerUnpoisonMemoryRegion(target_slot, policy.slot_size); policy.transfer_n(&c, target_slot, c.soo_data(), 1); - c.set_control</*kGenerateSeed=*/false>(new_ctrl); + c.set_control(new_ctrl); c.set_slots(new_slots); ResetCtrl(c, policy.slot_size); - SetCtrl(c, offset, H2(hash), policy.slot_size); + SetCtrl(c, offset, H2(soo_slot_hash), policy.slot_size); } enum class ResizeFullSooTableSamplingMode { @@ -783,6 +787,7 @@ void* alloc = policy.get_char_alloc(common); HashtablezInfoHandle infoz; + bool has_infoz = false; if (sampling_mode == ResizeFullSooTableSamplingMode::kForceSampleNoResizeIfUnsampled) { if (ABSL_PREDICT_FALSE(policy.is_hashtablez_eligible)) { @@ -790,13 +795,10 @@ policy.soo_capacity()); } - if (!infoz.IsSampled()) { - return; - } + if (!infoz.IsSampled()) return; + has_infoz = true; } - const bool has_infoz = infoz.IsSampled(); - common.set_capacity(new_capacity); // We do not set control and slots in CommonFields yet to avoid overriding @@ -804,11 +806,8 @@ const auto [new_ctrl, new_slots] = AllocBackingArray(common, policy, new_capacity, has_infoz, alloc); - const size_t soo_slot_hash = - policy.hash_slot(policy.hash_fn(common), common.soo_data()); - - InsertOldSooSlotAndInitializeControlBytes(common, policy, soo_slot_hash, - new_ctrl, new_slots); + InsertOldSooSlotAndInitializeControlBytes(common, policy, new_ctrl, new_slots, + has_infoz); ResetGrowthLeft(common); if (has_infoz) { common.set_has_infoz(); @@ -998,12 +997,13 @@ const void* hash_fn = policy.hash_fn(c); auto hash_slot = policy.hash_slot; auto transfer_n = policy.transfer_n; + const size_t seed = c.seed().seed(); for (size_t old_index = start; old_index < old_capacity; ++old_index) { if (old_ctrl[old_index] != ctrl_t::kSentinel) { continue; } void* src_slot = SlotAddress(old_slots, old_index, slot_size); - const size_t hash = hash_slot(hash_fn, src_slot); + const size_t hash = hash_slot(hash_fn, src_slot, seed); const FindInfo target = find_first_non_full(c, hash); total_probe_length += target.probe_length; const size_t new_i = target.offset; @@ -1276,7 +1276,7 @@ std::pair<ctrl_t*, void*> Grow1To3AndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, - absl::FunctionRef<size_t()> get_hash) { + absl::FunctionRef<size_t(size_t)> get_hash) { // TODO(b/413062340): Refactor to reuse more code with // GrowSooTableToNextCapacityAndPrepareInsert. ABSL_SWISSTABLE_ASSERT(common.capacity() == 1); @@ -1296,13 +1296,18 @@ const auto [new_ctrl, new_slots] = AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc); - common.set_control</*kGenerateSeed=*/true>(new_ctrl); + common.set_control(new_ctrl); common.set_slots(new_slots); SanitizerPoisonMemoryRegion(new_slots, kNewCapacity * slot_size); - const size_t new_hash = get_hash(); + if (ABSL_PREDICT_TRUE(!has_infoz)) { + // When we're sampled, we already have a seed. + common.generate_new_seed(/*has_infoz=*/false); + } + const size_t new_hash = get_hash(common.seed().seed()); h2_t new_h2 = H2(new_hash); - size_t orig_hash = policy.hash_slot(policy.hash_fn(common), old_slots); + size_t orig_hash = + policy.hash_slot(policy.hash_fn(common), old_slots, common.seed().seed()); size_t offset = Resize1To3NewOffset(new_hash, common.seed()); InitializeThreeElementsControlBytes(H2(orig_hash), new_h2, offset, new_ctrl); @@ -1348,7 +1353,7 @@ const auto [new_ctrl, new_slots] = AllocBackingArray(common, policy, new_capacity, has_infoz, alloc); - common.set_control</*kGenerateSeed=*/false>(new_ctrl); + common.set_control(new_ctrl); common.set_slots(new_slots); SanitizerPoisonMemoryRegion(new_slots, new_capacity * slot_size); @@ -1397,7 +1402,7 @@ std::pair<ctrl_t*, void*> PrepareInsertSmallNonSoo( CommonFields& common, const PolicyFunctions& __restrict policy, - absl::FunctionRef<size_t()> get_hash) { + absl::FunctionRef<size_t(size_t)> get_hash) { ABSL_SWISSTABLE_ASSERT(common.is_small()); ABSL_SWISSTABLE_ASSERT(!policy.soo_enabled); if (common.capacity() == 1) { @@ -1426,15 +1431,16 @@ const auto [new_ctrl, new_slots] = AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc); - // In small tables seed is not needed. - common.set_control</*kGenerateSeed=*/false>(new_ctrl); + common.set_control(new_ctrl); common.set_slots(new_slots); static_assert(NextCapacity(0) == 1); PrepareInsertCommon(common); if (ABSL_PREDICT_FALSE(has_infoz)) { - ReportSingleGroupTableGrowthToInfoz(common, infoz, get_hash()); + common.generate_new_seed(/*has_infoz=*/true); + ReportSingleGroupTableGrowthToInfoz(common, infoz, + get_hash(common.seed().seed())); } return {SooControl(), new_slots}; } @@ -1535,11 +1541,12 @@ ABSL_ATTRIBUTE_NOINLINE size_t GrowEmptySooTableToNextCapacityForceSamplingAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, - size_t new_hash) { + absl::FunctionRef<size_t(size_t)> get_hash) { ResizeEmptyNonAllocatedTableImpl(common, policy, NextCapacity(SooCapacity()), /*force_infoz=*/true); PrepareInsertCommon(common); common.growth_info().OverwriteEmptyAsFull(); + const size_t new_hash = get_hash(common.seed().seed()); SetCtrlInSingleGroupTable(common, SooSlotIndex(), H2(new_hash), policy.slot_size); common.infoz().RecordInsert(new_hash, /*distance_from_desired=*/0); @@ -1630,12 +1637,12 @@ template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy> size_t GrowSooTableToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, - size_t new_hash, ctrl_t soo_slot_ctrl) { + absl::FunctionRef<size_t(size_t)> get_hash, bool force_sampling) { AssertSoo(common, policy); - if (ABSL_PREDICT_FALSE(soo_slot_ctrl == ctrl_t::kEmpty)) { + if (ABSL_PREDICT_FALSE(force_sampling)) { // The table is empty, it is only used for forced sampling of SOO tables. return GrowEmptySooTableToNextCapacityForceSamplingAndPrepareInsert( - common, policy, new_hash); + common, policy, get_hash); } ABSL_SWISSTABLE_ASSERT(common.size() == policy.soo_capacity()); static constexpr size_t kNewCapacity = NextCapacity(SooCapacity()); @@ -1654,11 +1661,14 @@ PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2); - common.generate_new_seed(); + common.generate_new_seed(/*has_infoz=*/false); + const h2_t soo_slot_h2 = H2(policy.hash_slot( + policy.hash_fn(common), common.soo_data(), common.seed().seed())); + const size_t new_hash = get_hash(common.seed().seed()); const size_t offset = Resize1To3NewOffset(new_hash, common.seed()); - InitializeThreeElementsControlBytes(static_cast<h2_t>(soo_slot_ctrl), - H2(new_hash), offset, new_ctrl); + InitializeThreeElementsControlBytes(soo_slot_h2, H2(new_hash), offset, + new_ctrl); SanitizerPoisonMemoryRegion(new_slots, slot_size * kNewCapacity); void* target_slot = SlotAddress(new_slots, SooSlotIndex(), slot_size); @@ -1680,8 +1690,7 @@ static_assert(SooSlotMemcpySize == 0); policy.transfer_n(&common, target_slot, common.soo_data(), 1); } - // Seed was already generated above. - common.set_control</*kGenerateSeed=*/false>(new_ctrl); + common.set_control(new_ctrl); common.set_slots(new_slots); // Full SOO table couldn't be sampled. If SOO table is sampled, it would @@ -1793,47 +1802,22 @@ ABSL_SWISSTABLE_ASSERT(other.capacity() > soo_capacity); const size_t cap = common.capacity(); ABSL_SWISSTABLE_ASSERT(cap > soo_capacity); - // Note about single group tables: - // 1. It is correct to have any order of elements. - // 2. Order has to be non deterministic. - // 3. We are assigning elements with arbitrary `shift` starting from - // `capacity + shift` position. - // 4. `shift` must be coprime with `capacity + 1` in order to be able to use - // modular arithmetic to traverse all positions, instead of cycling - // through a subset of positions. Odd numbers are coprime with any - // `capacity + 1` (2^N). size_t offset = cap; - const size_t shift = is_single_group(cap) ? (common.seed().seed() | 1) : 0; const void* hash_fn = policy.hash_fn(common); auto hasher = policy.hash_slot; + const size_t seed = common.seed().seed(); IterateOverFullSlotsImpl( - other, slot_size, [&](const ctrl_t* that_ctrl, void* that_slot) { - if (shift == 0) { - // Big tables case. Position must be searched via probing. - // The table is guaranteed to be empty, so we can do faster than - // a full `insert`. - const size_t hash = (*hasher)(hash_fn, that_slot); - FindInfo target = find_first_non_full(common, hash); - infoz.RecordInsert(hash, target.probe_length); - offset = target.offset; - } else { - // Small tables case. Next position is computed via shift. - offset = (offset + shift) & cap; - } - const h2_t h2 = static_cast<h2_t>(*that_ctrl); - // We rely on the hash not changing for small tables. - ABSL_SWISSTABLE_ASSERT( - H2((*hasher)(hash_fn, that_slot)) == h2 && - "hash function value changed unexpectedly during the copy"); - SetCtrl(common, offset, h2, slot_size); + other, slot_size, [&](const ctrl_t*, void* that_slot) { + // The table is guaranteed to be empty, so we can do faster than + // a full `insert`. + const size_t hash = (*hasher)(hash_fn, that_slot, seed); + FindInfo target = find_first_non_full(common, hash); + infoz.RecordInsert(hash, target.probe_length); + offset = target.offset; + SetCtrl(common, offset, H2(hash), slot_size); copy_fn(SlotAddress(common.slot_array(), offset, slot_size), that_slot); common.maybe_increment_generation_on_insert(); }); - if (shift != 0) { - // On small table copy we do not record individual inserts. - // RecordInsert requires hash, but it is unknown for small tables. - infoz.RecordStorageChanged(size, cap); - } common.increment_size(size); common.growth_info().OverwriteManyEmptyAsFull(size); } @@ -1859,18 +1843,11 @@ ReserveAllocatedTable(common, policy, new_size); } -size_t PrepareInsertLarge(CommonFields& common, - const PolicyFunctions& __restrict policy, size_t hash, - FindInfo target) { +namespace { +size_t PrepareInsertLargeImpl(CommonFields& common, + const PolicyFunctions& __restrict policy, + size_t hash, FindInfo target) { ABSL_SWISSTABLE_ASSERT(!common.is_small()); - if (common.should_rehash_for_bug_detection_on_insert()) { - // Move to a different heap allocation in order to detect bugs. - const size_t cap = common.capacity(); - ResizeAllocatedTableWithSeedChange( - common, policy, common.growth_left() > 0 ? cap : NextCapacity(cap)); - target = find_first_non_full(common, hash); - } - const GrowthInfo growth_info = common.growth_info(); // When there are no deleted slots in the table // and growth_left is positive, we can insert at the first @@ -1884,6 +1861,31 @@ common.infoz().RecordInsert(hash, target.probe_length); return target.offset; } +} // namespace + +size_t PrepareInsertLarge(CommonFields& common, + const PolicyFunctions& __restrict policy, size_t hash, + FindInfo target) { + // NOLINTNEXTLINE(misc-static-assert) + ABSL_SWISSTABLE_ASSERT(!SwisstableGenerationsEnabled()); + return PrepareInsertLargeImpl(common, policy, hash, target); +} + +size_t PrepareInsertLargeGenerationsEnabled( + CommonFields& common, const PolicyFunctions& policy, size_t hash, + FindInfo target, absl::FunctionRef<size_t(size_t)> recompute_hash) { + // NOLINTNEXTLINE(misc-static-assert) + ABSL_SWISSTABLE_ASSERT(SwisstableGenerationsEnabled()); + if (common.should_rehash_for_bug_detection_on_insert()) { + // Move to a different heap allocation in order to detect bugs. + const size_t cap = common.capacity(); + ResizeAllocatedTableWithSeedChange( + common, policy, common.growth_left() > 0 ? cap : NextCapacity(cap)); + hash = recompute_hash(common.seed().seed()); + target = find_first_non_full(common, hash); + } + return PrepareInsertLargeImpl(common, policy, hash, target); +} namespace { // Returns true if the following is true @@ -1919,32 +1921,33 @@ // We need to instantiate ALL possible template combinations because we define // the function in the cc file. template size_t GrowSooTableToNextCapacityAndPrepareInsert<0, false>( - CommonFields&, const PolicyFunctions&, size_t, ctrl_t); + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); template size_t GrowSooTableToNextCapacityAndPrepareInsert< - OptimalMemcpySizeForSooSlotTransfer(1), true>(CommonFields&, - const PolicyFunctions&, - size_t, ctrl_t); + OptimalMemcpySizeForSooSlotTransfer(1), true>( + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(2, 3)); template size_t GrowSooTableToNextCapacityAndPrepareInsert< - OptimalMemcpySizeForSooSlotTransfer(3), true>(CommonFields&, - const PolicyFunctions&, - size_t, ctrl_t); + OptimalMemcpySizeForSooSlotTransfer(3), true>( + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(4, 8)); template size_t GrowSooTableToNextCapacityAndPrepareInsert< - OptimalMemcpySizeForSooSlotTransfer(8), true>(CommonFields&, - const PolicyFunctions&, - size_t, ctrl_t); + OptimalMemcpySizeForSooSlotTransfer(8), true>( + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); #if UINTPTR_MAX == UINT32_MAX static_assert(MaxSooSlotSize() == 8); #else static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(9, 16)); template size_t GrowSooTableToNextCapacityAndPrepareInsert< - OptimalMemcpySizeForSooSlotTransfer(16), true>(CommonFields&, - const PolicyFunctions&, - size_t, ctrl_t); + OptimalMemcpySizeForSooSlotTransfer(16), true>( + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); static_assert(MaxSooSlotSize() == 16); #endif
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 7106bc8..08c5d57 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -194,6 +194,7 @@ #include <utility> #include "absl/base/attributes.h" +#include "absl/base/casts.h" #include "absl/base/config.h" #include "absl/base/internal/endian.h" #include "absl/base/internal/iterator_traits.h" @@ -446,18 +447,29 @@ // The number of bits in the seed. // It is big enough to ensure non-determinism of iteration order. // We store the seed inside a uint64_t together with size and other metadata. - // Using 16 bits allows us to save one `and` instruction in H1 (we use movzwl - // instead of movq+and). + // Using 16 bits allows us to save one `and` instruction in H1 (we use + // sign-extended move instead of mov+and). static constexpr size_t kBitCount = 16; + static constexpr size_t kSignBit = uint64_t{1} << (kBitCount - 1); - // Returns the seed for the table. Only the lowest kBitCount are non zero. - size_t seed() const { return seed_; } + // Returns the seed for the table. + size_t seed() const { + // We use a sign-extended load to ensure high bits are non-zero. + int16_t seed_signed = absl::bit_cast<int16_t>(seed_); + auto seed_sign_extended = + static_cast<std::make_signed_t<size_t>>(seed_signed); + return absl::bit_cast<size_t>(seed_sign_extended); + } private: friend class HashtableSize; - explicit PerTableSeed(size_t seed) : seed_(seed) {} + explicit PerTableSeed(uint16_t seed) : seed_(seed) { + ABSL_SWISSTABLE_ASSERT((seed & kSignBit) != 0 || seed == 0); + } - const size_t seed_; + // The most significant bit of the seed is always 1 when there is a non-zero + // seed. This way, when sign-extended the seed has non-zero high bits. + const uint16_t seed_; }; // Returns next per-table seed. @@ -496,8 +508,14 @@ return PerTableSeed(static_cast<size_t>(data_) & kSeedMask); } - void generate_new_seed() { - data_ = (data_ & ~kSeedMask) ^ uint64_t{NextSeed()}; + void generate_new_seed() { set_seed(NextSeed()); } + + // We need to use a constant seed when the table is sampled so that sampled + // hashes use the same seed and can e.g. identify stuck bits accurately. + void set_sampled_seed() { set_seed(PerTableSeed::kSignBit); } + + bool is_sampled_seed() const { + return (data_ & kSeedMask) == PerTableSeed::kSignBit; } // Returns true if the table has infoz. @@ -511,6 +529,9 @@ void set_no_seed_for_testing() { data_ &= ~kSeedMask; } private: + void set_seed(uint16_t seed) { + data_ = (data_ & ~kSeedMask) | (seed | PerTableSeed::kSignBit); + } static constexpr size_t kSizeShift = 64 - kSizeBitCount; static constexpr uint64_t kSizeOneNoMetadata = uint64_t{1} << kSizeShift; static constexpr uint64_t kMetadataMask = kSizeOneNoMetadata - 1; @@ -521,11 +542,8 @@ uint64_t data_; }; -// Mixes the hash with a per-table seed. Note that we only use the low bits of -// H1 because we bitwise-and with capacity later. -inline size_t H1(size_t hash, PerTableSeed seed) { - return hash ^ seed.seed(); -} +// H1 is just the low bits of the hash. +inline size_t H1(size_t hash) { return hash; } // Extracts the H2 portion of a hash: the 7 most significant bits. // @@ -566,11 +584,9 @@ // references. We rehash on the first insertion after reserved_growth_ reaches // 0 after a call to reserve. We also do a rehash with low probability // whenever reserved_growth_ is zero. - bool should_rehash_for_bug_detection_on_insert(PerTableSeed seed, - size_t capacity) const; + bool should_rehash_for_bug_detection_on_insert(size_t capacity) const; // Similar to above, except that we don't depend on reserved_growth_. - bool should_rehash_for_bug_detection_on_move(PerTableSeed seed, - size_t capacity) const; + bool should_rehash_for_bug_detection_on_move(size_t capacity) const; void maybe_increment_generation_on_insert() { if (reserved_growth_ == kReservedGrowthJustRanOut) reserved_growth_ = 0; @@ -623,12 +639,8 @@ CommonFieldsGenerationInfoDisabled& operator=( CommonFieldsGenerationInfoDisabled&&) = default; - bool should_rehash_for_bug_detection_on_insert(PerTableSeed, size_t) const { - return false; - } - bool should_rehash_for_bug_detection_on_move(PerTableSeed, size_t) const { - return false; - } + bool should_rehash_for_bug_detection_on_insert(size_t) const { return false; } + bool should_rehash_for_bug_detection_on_move(size_t) const { return false; } void maybe_increment_generation_on_insert() {} void increment_generation() {} void reset_reserved_growth(size_t, size_t) {} @@ -955,19 +967,7 @@ ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap_or_soo_.control().get()); } - // When we set the control bytes, we also often want to generate a new seed. - // So we bundle these two operations together to make sure we don't forget to - // generate a new seed. - // The table will be invalidated if - // `kGenerateSeed && !empty() && !is_single_group(capacity())` because H1 is - // being changed. In such cases, we will need to rehash the table. - template <bool kGenerateSeed> - void set_control(ctrl_t* c) { - heap_or_soo_.control().set(c); - if constexpr (kGenerateSeed) { - generate_new_seed(); - } - } + void set_control(ctrl_t* c) { heap_or_soo_.control().set(c); } // Note: we can't use slots() because Qt defines "slots" as a macro. void* slot_array() const { return heap_or_soo_.slot_array().get(); } @@ -1002,13 +1002,20 @@ } bool empty() const { return size_.empty(); } - // The seed used for the H1 part of the hash function. + // The seed used for the hash function. PerTableSeed seed() const { return size_.seed(); } - // Generates a new seed for the H1 part of the hash function. - // The table will be invalidated if - // `kGenerateSeed && !empty() && !is_single_group(capacity())` because H1 is - // being changed. In such cases, we will need to rehash the table. - void generate_new_seed() { size_.generate_new_seed(); } + // Generates a new seed the hash function. + // The table will be invalidated if `!empty()` because hash is being changed. + // In such cases, we will need to rehash the table. + void generate_new_seed(bool has_infoz) { + // Note: we can't use has_infoz() here because we set has_infoz later than + // we generate the seed. + if (ABSL_PREDICT_FALSE(has_infoz)) { + size_.set_sampled_seed(); + return; + } + size_.generate_new_seed(); + } void set_no_seed_for_testing() { size_.set_no_seed_for_testing(); } // The total number of available slots. @@ -1036,7 +1043,10 @@ } bool has_infoz() const { return size_.has_infoz(); } - void set_has_infoz() { size_.set_has_infoz(); } + void set_has_infoz() { + ABSL_SWISSTABLE_ASSERT(size_.is_sampled_seed()); + size_.set_has_infoz(); + } HashtablezInfoHandle* infoz_ptr() const { // growth_info is stored before control bytes. @@ -1063,11 +1073,11 @@ // will end up rehashing anyways. if (growth_left() == 0) return false; return CommonFieldsGenerationInfo:: - should_rehash_for_bug_detection_on_insert(seed(), capacity()); + should_rehash_for_bug_detection_on_insert(capacity()); } bool should_rehash_for_bug_detection_on_move() const { return CommonFieldsGenerationInfo::should_rehash_for_bug_detection_on_move( - seed(), capacity()); + capacity()); } void reset_reserved_growth(size_t reservation) { CommonFieldsGenerationInfo::reset_reserved_growth(reservation, size()); @@ -1402,15 +1412,14 @@ } // Begins a probing operation on `common.control`, using `hash`. -inline probe_seq<Group::kWidth> probe(size_t h1, size_t capacity) { +inline probe_seq<Group::kWidth> probe_h1(size_t capacity, size_t h1) { return probe_seq<Group::kWidth>(h1, capacity); } -inline probe_seq<Group::kWidth> probe(PerTableSeed seed, size_t capacity, - size_t hash) { - return probe(H1(hash, seed), capacity); +inline probe_seq<Group::kWidth> probe(size_t capacity, size_t hash) { + return probe_h1(capacity, H1(hash)); } inline probe_seq<Group::kWidth> probe(const CommonFields& common, size_t hash) { - return probe(common.seed(), common.capacity(), hash); + return probe(common.capacity(), hash); } // Probes an array of control bits using a probe sequence derived from `hash`, @@ -1611,7 +1620,7 @@ void* (*hash_fn)(CommonFields& common); // Returns the hash of the pointed-to slot. - size_t (*hash_slot)(const void* hash_fn, void* slot); + HashSlotFn hash_slot; // Transfers the contents of `count` slots from src_slot to dst_slot. // We use ability to transfer several slots in single group table growth. @@ -1766,17 +1775,12 @@ // Resizes SOO table to the NextCapacity(SooCapacity()) and prepares insert for // the given new_hash. Returns the offset of the new element. -// `soo_slot_ctrl` is the control byte of the SOO slot. -// If soo_slot_ctrl is kEmpty -// 1. The table must be empty. -// 2. Table will be forced to be sampled. // All possible template combinations are defined in cc file to improve // compilation time. template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy> -size_t GrowSooTableToNextCapacityAndPrepareInsert(CommonFields& common, - const PolicyFunctions& policy, - size_t new_hash, - ctrl_t soo_slot_ctrl); +size_t GrowSooTableToNextCapacityAndPrepareInsert( + CommonFields& common, const PolicyFunctions& policy, + absl::FunctionRef<size_t(size_t)> get_hash, bool force_sampling); // PrepareInsert for small tables (is_small()==true). // Returns the new control and the new slot. @@ -1784,7 +1788,7 @@ // (is_small()==false). std::pair<ctrl_t*, void*> PrepareInsertSmallNonSoo( CommonFields& common, const PolicyFunctions& policy, - absl::FunctionRef<size_t()> get_hash); + absl::FunctionRef<size_t(size_t)> get_hash); // Resizes table with allocated slots and change the table seed. // Tables with SOO enabled must have capacity > policy.soo_capacity. @@ -1837,6 +1841,12 @@ size_t PrepareInsertLarge(CommonFields& common, const PolicyFunctions& policy, size_t hash, FindInfo target); +// Same as above, but with generations enabled, we may end up changing the seed, +// which means we need to be able to recompute the hash. +size_t PrepareInsertLargeGenerationsEnabled( + CommonFields& common, const PolicyFunctions& policy, size_t hash, + FindInfo target, absl::FunctionRef<size_t(size_t)> recompute_hash); + // A SwissTable. // // Policy: a policy defines how to perform different operations on @@ -1890,6 +1900,10 @@ using slot_type = typename PolicyTraits::slot_type; + constexpr static bool kIsDefaultHash = + std::is_same_v<hasher, absl::Hash<key_type>> || + std::is_same_v<hasher, absl::container_internal::StringHash>; + // TODO(b/289225379): we could add extra SOO space inside raw_hash_set // after CommonFields to allow inlining larger slot_types (e.g. std::string), // but it's a bit complicated if we want to support incomplete mapped_type in @@ -3091,11 +3105,13 @@ } template <class K> ABSL_ATTRIBUTE_ALWAYS_INLINE size_t hash_of(const K& key) const { - return HashElement<hasher>{hash_ref()}(key); + return HashElement<hasher, kIsDefaultHash>{hash_ref(), + common().seed().seed()}(key); } ABSL_ATTRIBUTE_ALWAYS_INLINE size_t hash_of(slot_type* slot) const { - return PolicyTraits::apply(HashElement<hasher>{hash_ref()}, - PolicyTraits::element(slot)); + return PolicyTraits::apply( + HashElement<hasher, kIsDefaultHash>{hash_ref(), common().seed().seed()}, + PolicyTraits::element(slot)); } // Casting directly from e.g. char* to slot_type* can cause compilation errors @@ -3211,25 +3227,26 @@ template <class K> std::pair<iterator, bool> find_or_prepare_insert_soo(const K& key) { ABSL_SWISSTABLE_ASSERT(is_soo()); - ctrl_t soo_slot_ctrl; + bool force_sampling; if (empty()) { if (!should_sample_soo()) { common().set_full_soo(); return {single_iterator(), true}; } - soo_slot_ctrl = ctrl_t::kEmpty; + force_sampling = true; } else if (equal_to(key, single_slot())) { return {single_iterator(), false}; } else { - soo_slot_ctrl = static_cast<ctrl_t>(H2(hash_of(single_slot()))); + force_sampling = false; } ABSL_SWISSTABLE_ASSERT(capacity() == 1); - const size_t hash = hash_of(key); constexpr bool kUseMemcpy = PolicyTraits::transfer_uses_memcpy() && SooEnabled(); size_t index = GrowSooTableToNextCapacityAndPrepareInsert< kUseMemcpy ? OptimalMemcpySizeForSooSlotTransfer(sizeof(slot_type)) : 0, - kUseMemcpy>(common(), GetPolicyFunctions(), hash, soo_slot_ctrl); + kUseMemcpy>(common(), GetPolicyFunctions(), + HashKey<hasher, K, kIsDefaultHash>{hash_ref(), key}, + force_sampling); return {iterator_at(index), true}; } @@ -3244,9 +3261,9 @@ return {single_iterator(), false}; } } - return {iterator_at_ptr( - PrepareInsertSmallNonSoo(common(), GetPolicyFunctions(), - HashKey<hasher, K>{hash_ref(), key})), + return {iterator_at_ptr(PrepareInsertSmallNonSoo( + common(), GetPolicyFunctions(), + HashKey<hasher, K, kIsDefaultHash>{hash_ref(), key})), true}; } @@ -3270,10 +3287,15 @@ auto mask_empty = g.MaskEmpty(); if (ABSL_PREDICT_TRUE(mask_empty)) { size_t target = seq.offset(mask_empty.LowestBitSet()); - return { - iterator_at(PrepareInsertLarge(common(), GetPolicyFunctions(), hash, - FindInfo{target, seq.index()})), - true}; + size_t index = + SwisstableGenerationsEnabled() + ? PrepareInsertLargeGenerationsEnabled( + common(), GetPolicyFunctions(), hash, + FindInfo{target, seq.index()}, + HashKey<hasher, K, kIsDefaultHash>{hash_ref(), key}) + : PrepareInsertLarge(common(), GetPolicyFunctions(), hash, + FindInfo{target, seq.index()}); + return {iterator_at(index), true}; } seq.next(); ABSL_SWISSTABLE_ASSERT(seq.index() <= capacity() && "full table!"); @@ -3526,8 +3548,6 @@ ctrl_t* new_ctrl = common.control(); slot_type* new_slots = set->slot_array(); - const PerTableSeed seed = common.seed(); - for (size_t group_index = 0; group_index < old_capacity; group_index += Group::kWidth) { GroupFullEmptyOrDeleted old_g(old_ctrl + group_index); @@ -3543,7 +3563,7 @@ // TODO(b/382423690): try to avoid entire hash calculation since we need // only one new bit of h1. size_t hash = set->hash_of(old_slot); - size_t h1 = H1(hash, seed); + size_t h1 = H1(hash); h2_t h2 = H2(hash); size_t new_index = TryFindNewIndexWithoutProbing( h1, old_index, old_capacity, new_ctrl, new_capacity); @@ -3586,7 +3606,7 @@ // for standard layout and alignof(Hash) <= alignof(CommonFields). std::is_empty_v<hasher> ? &GetRefForEmptyClass : &raw_hash_set::get_hash_ref_fn, - PolicyTraits::template get_hash_slot_fn<hasher>(), + PolicyTraits::template get_hash_slot_fn<hasher, kIsDefaultHash>(), PolicyTraits::transfer_uses_memcpy() ? TransferNRelocatable<sizeof(slot_type)> : &raw_hash_set::transfer_n_slots_fn, @@ -3689,6 +3709,8 @@ using Traits = typename Set::PolicyTraits; using Slot = typename Traits::slot_type; + constexpr static bool kIsDefaultHash = Set::kIsDefaultHash; + static size_t GetNumProbes(const Set& set, const typename Set::key_type& key) { if (set.is_soo()) return 0; @@ -3733,16 +3755,21 @@ // Extern template instantiations reduce binary size and linker input size. // Function definition is in raw_hash_set.cc. extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<0, false>( - CommonFields&, const PolicyFunctions&, size_t, ctrl_t); + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<1, true>( - CommonFields&, const PolicyFunctions&, size_t, ctrl_t); + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<4, true>( - CommonFields&, const PolicyFunctions&, size_t, ctrl_t); + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<8, true>( - CommonFields&, const PolicyFunctions&, size_t, ctrl_t); + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); #if UINTPTR_MAX == UINT64_MAX extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<16, true>( - CommonFields&, const PolicyFunctions&, size_t, ctrl_t); + CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + bool); #endif } // namespace container_internal
diff --git a/absl/container/internal/raw_hash_set_allocator_test.cc b/absl/container/internal/raw_hash_set_allocator_test.cc index 7e7a506..2e6f8f5 100644 --- a/absl/container/internal/raw_hash_set_allocator_test.cc +++ b/absl/container/internal/raw_hash_set_allocator_test.cc
@@ -180,7 +180,7 @@ static slot_type& element(slot_type* slot) { return *slot; } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; }
diff --git a/absl/container/internal/raw_hash_set_benchmark.cc b/absl/container/internal/raw_hash_set_benchmark.cc index ac94877..07a5b90 100644 --- a/absl/container/internal/raw_hash_set_benchmark.cc +++ b/absl/container/internal/raw_hash_set_benchmark.cc
@@ -64,7 +64,7 @@ return std::forward<F>(f)(x, x); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -127,7 +127,7 @@ PairArgs(std::forward<Args>(args)...)); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; }
diff --git a/absl/container/internal/raw_hash_set_probe_benchmark.cc b/absl/container/internal/raw_hash_set_probe_benchmark.cc index e56648f..458038e 100644 --- a/absl/container/internal/raw_hash_set_probe_benchmark.cc +++ b/absl/container/internal/raw_hash_set_probe_benchmark.cc
@@ -71,7 +71,7 @@ return std::forward<F>(f)(arg, arg); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr auto get_hash_slot_fn() { return nullptr; }
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index f835b94..e1dafff 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -386,7 +386,7 @@ std::forward<F>(f), std::forward<Args>(args)...); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -534,7 +534,7 @@ PairArgs(std::forward<Args>(args)...)); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -1131,7 +1131,7 @@ return std::forward<F>(f)(x, x); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -2814,12 +2814,12 @@ // Expect that we sampled at the requested sampling rate of ~1%. EXPECT_NEAR((end_size - start_size) / static_cast<double>(tables.size()), 0.01, 0.005); - EXPECT_EQ(observed_checksums.size(), 5); + ASSERT_EQ(observed_checksums.size(), 5); for (const auto& [_, count] : observed_checksums) { EXPECT_NEAR((100 * count) / static_cast<double>(tables.size()), 0.2, 0.05); } - EXPECT_EQ(reservations.size(), 10); + ASSERT_EQ(reservations.size(), 10); for (const auto& [reservation, count] : reservations) { EXPECT_GE(reservation, 0); EXPECT_LT(reservation, 100); @@ -4057,7 +4057,7 @@ CommonFields& common = RawHashSetTestOnlyAccess::GetCommon(t); // Set 0 seed so that H1 is always 0. common.set_no_seed_for_testing(); - ASSERT_EQ(H1(t.hash_function()(75), common.seed()), 0); + ASSERT_EQ(H1(t.hash_function()(75)), 0); uint8_t inserted_till = 210; for (uint8_t i = 0; i < inserted_till; ++i) { t.insert(i); @@ -4081,6 +4081,16 @@ EXPECT_EQ(t.capacity(), kTargetCapacity); } +// Test that after calling generate_new_seed(), the high bits of the returned +// seed are non-zero. +TEST(PerTableSeed, HighBitsAreNonZero) { + HashtableSize hs(no_seed_empty_tag_t{}); + for (int i = 0; i < 100; ++i) { + hs.generate_new_seed(); + ASSERT_GT(hs.seed().seed() >> 16, 0); + } +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h index 5f6be95..46faa89 100644 --- a/absl/container/node_hash_map.h +++ b/absl/container/node_hash_map.h
@@ -663,10 +663,10 @@ static Value& value(value_type* elem) { return elem->second; } static const Value& value(const value_type* elem) { return elem->second; } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { return memory_internal::IsLayoutCompatible<Key, Value>::value - ? &TypeErasedDerefAndApplyToSlotFn<Hash, Key> + ? &TypeErasedDerefAndApplyToSlotFn<Hash, Key, kIsDefault> : nullptr; } };
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h index 127c640..9eef870 100644 --- a/absl/container/node_hash_set.h +++ b/absl/container/node_hash_set.h
@@ -557,9 +557,9 @@ static size_t element_space_used(const T*) { return sizeof(T); } - template <class Hash> + template <class Hash, bool kIsDefault> static constexpr HashSlotFn get_hash_slot_fn() { - return &TypeErasedDerefAndApplyToSlotFn<Hash, T>; + return &TypeErasedDerefAndApplyToSlotFn<Hash, T, kIsDefault>; } }; } // namespace container_internal
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel index 8176cd9..0488227 100644 --- a/absl/hash/BUILD.bazel +++ b/absl/hash/BUILD.bazel
@@ -43,11 +43,11 @@ linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":city", - ":low_level_hash", ":weakly_mixed_integer", "//absl/base:config", "//absl/base:core_headers", "//absl/base:endian", + "//absl/base:prefetch", "//absl/container:fixed_array", "//absl/functional:function_ref", "//absl/meta:type_traits", @@ -188,22 +188,6 @@ ) cc_library( - name = "low_level_hash", - srcs = ["internal/low_level_hash.cc"], - hdrs = ["internal/low_level_hash.h"], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - visibility = ["//visibility:private"], - deps = [ - "//absl/base:config", - "//absl/base:core_headers", - "//absl/base:endian", - "//absl/base:prefetch", - "//absl/numeric:int128", - ], -) - -cc_library( name = "weakly_mixed_integer", hdrs = ["internal/weakly_mixed_integer.h"], copts = ABSL_DEFAULT_COPTS, @@ -225,7 +209,7 @@ linkopts = ABSL_DEFAULT_LINKOPTS, visibility = ["//visibility:private"], deps = [ - ":low_level_hash", + ":hash", "//absl/strings", "@googletest//:gtest", "@googletest//:gtest_main",
diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt index 6996d93..b439e4c 100644 --- a/absl/hash/CMakeLists.txt +++ b/absl/hash/CMakeLists.txt
@@ -38,7 +38,6 @@ absl::optional absl::variant absl::utility - absl::low_level_hash absl::weakly_mixed_integer PUBLIC ) @@ -156,24 +155,6 @@ # Internal-only target, do not depend on directly. absl_cc_library( NAME - low_level_hash - HDRS - "internal/low_level_hash.h" - SRCS - "internal/low_level_hash.cc" - COPTS - ${ABSL_DEFAULT_COPTS} - DEPS - absl::config - absl::core_headers - absl::endian - absl::int128 - absl::prefetch -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME weakly_mixed_integer HDRS "internal/weakly_mixed_integer.h" @@ -191,7 +172,7 @@ COPTS ${ABSL_TEST_COPTS} DEPS - absl::low_level_hash + absl::hash absl::strings GTest::gmock_main )
diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc index 1b47e61..87d2061 100644 --- a/absl/hash/internal/hash.cc +++ b/absl/hash/internal/hash.cc
@@ -14,27 +14,102 @@ #include "absl/hash/internal/hash.h" +#include <cassert> #include <cstddef> #include <cstdint> #include <type_traits> #include "absl/base/attributes.h" #include "absl/base/config.h" +#include "absl/base/internal/unaligned_access.h" +#include "absl/base/optimization.h" +#include "absl/base/prefetch.h" #include "absl/hash/internal/city.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace hash_internal { -uint64_t MixingHashState::CombineLargeContiguousImpl32( - const unsigned char* first, size_t len, uint64_t state) { +namespace { + +uint64_t Mix32Bytes(const uint8_t* ptr, uint64_t current_state) { + uint64_t a = absl::base_internal::UnalignedLoad64(ptr); + uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); + uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); + uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); + + uint64_t cs0 = Mix(a ^ kStaticRandomData[1], b ^ current_state); + uint64_t cs1 = Mix(c ^ kStaticRandomData[2], d ^ current_state); + return cs0 ^ cs1; +} + +[[maybe_unused]] uint64_t LowLevelHashLenGt32(const void* data, size_t len, + uint64_t seed) { + assert(len > 32); + const uint8_t* ptr = static_cast<const uint8_t*>(data); + uint64_t current_state = seed ^ kStaticRandomData[0] ^ len; + const uint8_t* last_32_ptr = ptr + len - 32; + + if (len > 64) { + // If we have more than 64 bytes, we're going to handle chunks of 64 + // bytes at a time. We're going to build up four separate hash states + // which we will then hash together. This avoids short dependency chains. + uint64_t duplicated_state0 = current_state; + uint64_t duplicated_state1 = current_state; + uint64_t duplicated_state2 = current_state; + + do { + // Always prefetch the next cacheline. + PrefetchToLocalCache(ptr + ABSL_CACHELINE_SIZE); + + uint64_t a = absl::base_internal::UnalignedLoad64(ptr); + uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); + uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); + uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); + uint64_t e = absl::base_internal::UnalignedLoad64(ptr + 32); + uint64_t f = absl::base_internal::UnalignedLoad64(ptr + 40); + uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48); + uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56); + + current_state = Mix(a ^ kStaticRandomData[1], b ^ current_state); + duplicated_state0 = Mix(c ^ kStaticRandomData[2], d ^ duplicated_state0); + + duplicated_state1 = Mix(e ^ kStaticRandomData[3], f ^ duplicated_state1); + duplicated_state2 = Mix(g ^ kStaticRandomData[4], h ^ duplicated_state2); + + ptr += 64; + len -= 64; + } while (len > 64); + + current_state = (current_state ^ duplicated_state0) ^ + (duplicated_state1 + duplicated_state2); + } + + // We now have a data `ptr` with at most 64 bytes and the current state + // of the hashing state machine stored in current_state. + if (len > 32) { + current_state = Mix32Bytes(ptr, current_state); + } + + // We now have a data `ptr` with at most 32 bytes and the current state + // of the hashing state machine stored in current_state. But we can + // safely read from `ptr + len - 32`. + return Mix32Bytes(last_32_ptr, current_state); +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t HashBlockOn32Bit( + const unsigned char* data, size_t len, uint64_t state) { + // TODO(b/417141985): expose and use CityHash32WithSeed. + return Mix( + PrecombineLengthMix(state, len) ^ + hash_internal::CityHash32(reinterpret_cast<const char*>(data), len), + kMul); +} + +ABSL_ATTRIBUTE_NOINLINE uint64_t +SplitAndCombineOn32Bit(const unsigned char* first, size_t len, uint64_t state) { while (len >= PiecewiseChunkSize()) { - // TODO(b/417141985): avoid code duplication with CombineContiguousImpl. - state = - Mix(PrecombineLengthMix(state, PiecewiseChunkSize()) ^ - hash_internal::CityHash32(reinterpret_cast<const char*>(first), - PiecewiseChunkSize()), - kMul); + state = HashBlockOn32Bit(first, PiecewiseChunkSize(), state); len -= PiecewiseChunkSize(); first += PiecewiseChunkSize(); } @@ -48,10 +123,20 @@ std::integral_constant<int, 4>{}); } -uint64_t MixingHashState::CombineLargeContiguousImpl64( - const unsigned char* first, size_t len, uint64_t state) { +ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t HashBlockOn64Bit( + const unsigned char* data, size_t len, uint64_t state) { +#ifdef ABSL_HAVE_INTRINSIC_INT128 + return LowLevelHashLenGt32(data, len, state); +#else + return hash_internal::CityHash64WithSeed(reinterpret_cast<const char*>(data), + len, state); +#endif +} + +ABSL_ATTRIBUTE_NOINLINE uint64_t +SplitAndCombineOn64Bit(const unsigned char* first, size_t len, uint64_t state) { while (len >= PiecewiseChunkSize()) { - state = Hash64(first, PiecewiseChunkSize(), state); + state = HashBlockOn64Bit(first, PiecewiseChunkSize(), state); len -= PiecewiseChunkSize(); first += PiecewiseChunkSize(); } @@ -65,6 +150,30 @@ std::integral_constant<int, 8>{}); } +} // namespace + +uint64_t CombineLargeContiguousImplOn32BitLengthGt8(const unsigned char* first, + size_t len, + uint64_t state) { + assert(len > 8); + assert(sizeof(size_t) == 4); // NOLINT(misc-static-assert) + if (ABSL_PREDICT_TRUE(len <= PiecewiseChunkSize())) { + return HashBlockOn32Bit(first, len, state); + } + return SplitAndCombineOn32Bit(first, len, state); +} + +uint64_t CombineLargeContiguousImplOn64BitLengthGt32(const unsigned char* first, + size_t len, + uint64_t state) { + assert(len > 32); + assert(sizeof(size_t) == 8); // NOLINT(misc-static-assert) + if (ABSL_PREDICT_TRUE(len <= PiecewiseChunkSize())) { + return HashBlockOn64Bit(first, len, state); + } + return SplitAndCombineOn64Bit(first, len, state); +} + ABSL_CONST_INIT const void* const MixingHashState::kSeed = &kSeed; } // namespace hash_internal
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index 5802064..3e27d3f 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h
@@ -79,7 +79,6 @@ #include "absl/base/port.h" #include "absl/container/fixed_array.h" #include "absl/hash/internal/city.h" -#include "absl/hash/internal/low_level_hash.h" #include "absl/hash/internal/weakly_mixed_integer.h" #include "absl/meta/type_traits.h" #include "absl/numeric/bits.h" @@ -354,6 +353,15 @@ } }; +// For use in `raw_hash_set` to pass a seed to the hash function. +struct HashWithSeed { + template <typename Hasher, typename T> + size_t hash(const Hasher& hasher, const T& value, size_t seed) const { + // NOLINTNEXTLINE(clang-diagnostic-sign-conversion) + return hasher.hash_with_seed(value, seed); + } +}; + // Convenience function that combines `hash_state` with the byte representation // of `value`. template <typename H, typename T, @@ -940,6 +948,186 @@ return state + (uint64_t{len} << 24); } + inline constexpr uint64_t kMul = uint64_t{0xdcb22ca68cb134ed}; + +// Random data taken from the hexadecimal digits of Pi's fractional component. +// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number +ABSL_CACHELINE_ALIGNED inline constexpr uint64_t kStaticRandomData[] = { + 0x243f'6a88'85a3'08d3, 0x1319'8a2e'0370'7344, 0xa409'3822'299f'31d0, + 0x082e'fa98'ec4e'6c89, 0x4528'21e6'38d0'1377, +}; + +ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t Mix(uint64_t lhs, uint64_t rhs) { + // For 32 bit platforms we are trying to use all 64 lower bits. + if constexpr (sizeof(size_t) < 8) { + uint64_t m = lhs * rhs; + return m ^ (m >> 32); + } + // absl::uint128 is not an alias or a thin wrapper around the intrinsic. + // We use the intrinsic when available to improve performance. + // TODO(b/399425325): Try to remove MulType since compiler seem to generate + // the same code with just absl::uint128. + // See https://gcc.godbolt.org/z/s3hGarraG for details. +#ifdef ABSL_HAVE_INTRINSIC_INT128 + using MulType = __uint128_t; +#else // ABSL_HAVE_INTRINSIC_INT128 + using MulType = absl::uint128; +#endif // ABSL_HAVE_INTRINSIC_INT128 + // Though the 128-bit product on AArch64 needs two instructions, it is + // still a good balance between speed and hash quality. + MulType m = lhs; + m *= rhs; + return Uint128High64(m) ^ Uint128Low64(m); +} + +// Reads 8 bytes from p. +inline uint64_t Read8(const unsigned char* p) { +// Suppress erroneous array bounds errors on GCC. +#if defined(__GNUC__) && !defined(__clang__) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Warray-bounds" +#endif + return absl::base_internal::UnalignedLoad64(p); +#if defined(__GNUC__) && !defined(__clang__) +#pragma GCC diagnostic pop +#endif +} + +// Reads 9 to 16 bytes from p. +// The first 8 bytes are in .first, and the rest of the bytes are in .second +// along with duplicated bytes from .first if len<16. +inline std::pair<uint64_t, uint64_t> Read9To16(const unsigned char* p, + size_t len) { + return {Read8(p), Read8(p + len - 8)}; +} + +// Reads 4 to 8 bytes from p. +// Bytes are permuted and some input bytes may be duplicated in output. +inline uint64_t Read4To8(const unsigned char* p, size_t len) { + // If `len < 8`, we duplicate bytes. We always put low memory at the end. + // E.g., on little endian platforms: + // `ABCD` will be read as `ABCDABCD`. + // `ABCDE` will be read as `BCDEABCD`. + // `ABCDEF` will be read as `CDEFABCD`. + // `ABCDEFG` will be read as `DEFGABCD`. + // `ABCDEFGH` will be read as `EFGHABCD`. + // We also do not care about endianness. On big-endian platforms, bytes will + // be permuted differently. We always shift low memory by 32, because that + // can be pipelined earlier. Reading high memory requires computing + // `p + len - 4`. + uint64_t most_significant = + static_cast<uint64_t>(absl::base_internal::UnalignedLoad32(p)) << 32; + uint64_t least_significant = + absl::base_internal::UnalignedLoad32(p + len - 4); + return most_significant | least_significant; +} + +// Reads 1 to 3 bytes from p. Some input bytes may be duplicated in output. +inline uint32_t Read1To3(const unsigned char* p, size_t len) { + // The trick used by this implementation is to avoid branches. + // We always read three bytes by duplicating. + // E.g., + // `A` is read as `AAA`. + // `AB` is read as `ABB`. + // `ABC` is read as `ABC`. + // We always shift `p[0]` so that it can be pipelined better. + // Other bytes require extra computation to find indices. + uint32_t mem0 = (static_cast<uint32_t>(p[0]) << 16) | p[len - 1]; + uint32_t mem1 = static_cast<uint32_t>(p[len / 2]) << 8; + return mem0 | mem1; +} + +// Slow dispatch path for calls to CombineContiguousImpl with a size argument +// larger than inlined size. Has the same effect as calling +// CombineContiguousImpl() repeatedly with the chunk stride size. +uint64_t CombineLargeContiguousImplOn32BitLengthGt8(const unsigned char* first, + size_t len, uint64_t state); +uint64_t CombineLargeContiguousImplOn64BitLengthGt32(const unsigned char* first, + size_t len, + uint64_t state); + +ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t CombineSmallContiguousImpl( + uint64_t state, const unsigned char* first, size_t len) { + ABSL_ASSUME(len <= 8); + uint64_t v; + if (len >= 4) { + v = Read4To8(first, len); + } else if (len > 0) { + v = Read1To3(first, len); + } else { + // Empty string must modify the state. + v = 0x57; + } + return Mix(state ^ v, kMul); +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t CombineContiguousImpl9to16( + uint64_t state, const unsigned char* first, size_t len) { + ABSL_ASSUME(len >= 9); + ABSL_ASSUME(len <= 16); + // Note: any time one half of the mix function becomes zero it will fail to + // incorporate any bits from the other half. However, there is exactly 1 in + // 2^64 values for each side that achieve this, and only when the size is + // exactly 16 -- for smaller sizes there is an overlapping byte that makes + // this impossible unless the seed is *also* incredibly unlucky. + auto p = Read9To16(first, len); + return Mix(state ^ p.first, kMul ^ p.second); +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t CombineContiguousImpl17to32( + uint64_t state, const unsigned char* first, size_t len) { + ABSL_ASSUME(len >= 17); + ABSL_ASSUME(len <= 32); + // Do two mixes of overlapping 16-byte ranges in parallel to minimize + // latency. + const uint64_t m0 = + Mix(Read8(first) ^ kStaticRandomData[1], Read8(first + 8) ^ state); + + const unsigned char* tail_16b_ptr = first + (len - 16); + const uint64_t m1 = Mix(Read8(tail_16b_ptr) ^ kStaticRandomData[3], + Read8(tail_16b_ptr + 8) ^ state); + return m0 ^ m1; +} + +// Implementation of the base case for combine_contiguous where we actually +// mix the bytes into the state. +// Dispatch to different implementations of combine_contiguous depending +// on the value of `sizeof(size_t)`. +inline uint64_t CombineContiguousImpl( + uint64_t state, const unsigned char* first, size_t len, + std::integral_constant<int, 4> /* sizeof_size_t */) { + // For large values we use CityHash, for small ones we use custom low latency + // hash. + if (len <= 8) { + return CombineSmallContiguousImpl(PrecombineLengthMix(state, len), first, + len); + } + return CombineLargeContiguousImplOn32BitLengthGt8(first, len, state); +} + +inline uint64_t CombineContiguousImpl( + uint64_t state, const unsigned char* first, size_t len, + std::integral_constant<int, 8> /* sizeof_size_t */) { + // For large values we use LowLevelHash or CityHash depending on the platform, + // for small ones we use custom low latency hash. + if (len <= 8) { + return CombineSmallContiguousImpl(PrecombineLengthMix(state, len), first, + len); + } + if (len <= 16) { + return CombineContiguousImpl9to16(PrecombineLengthMix(state, len), first, + len); + } + if (len <= 32) { + return CombineContiguousImpl17to32(PrecombineLengthMix(state, len), first, + len); + } + // We must not mix length into the state here because calling + // CombineContiguousImpl twice with PiecewiseChunkSize() must be equivalent + // to calling CombineLargeContiguousImpl once with 2 * PiecewiseChunkSize(). + return CombineLargeContiguousImplOn64BitLengthGt32(first, len, state); +} + #if defined(ABSL_INTERNAL_LEGACY_HASH_NAMESPACE) && \ ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ #define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 1 @@ -1044,22 +1232,11 @@ : std::integral_constant<bool, HashSelect::template Apply<T>::value> {}; class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> { - // absl::uint128 is not an alias or a thin wrapper around the intrinsic. - // We use the intrinsic when available to improve performance. -#ifdef ABSL_HAVE_INTRINSIC_INT128 - using uint128 = __uint128_t; -#else // ABSL_HAVE_INTRINSIC_INT128 - using uint128 = absl::uint128; -#endif // ABSL_HAVE_INTRINSIC_INT128 - template <typename T> using IntegralFastPath = conjunction<std::is_integral<T>, is_uniquely_represented<T>, FitsIn64Bits<T>>; - static constexpr uint64_t kMul = - uint64_t{0xdcb22ca68cb134ed}; - public: // Move only MixingHashState(MixingHashState&&) = default; @@ -1076,20 +1253,25 @@ } using MixingHashState::HashStateBase::combine_contiguous; + template <typename T> + static size_t hash(const T& value) { + return hash_with_seed(value, Seed()); + } + // For performance reasons in non-opt mode, we specialize this for // integral types. // Otherwise we would be instantiating and calling dozens of functions for // something that is just one multiplication and a couple xor's. // The result should be the same as running the whole algorithm, but faster. template <typename T, absl::enable_if_t<IntegralFastPath<T>::value, int> = 0> - static size_t hash(T value) { + static size_t hash_with_seed(T value, size_t seed) { return static_cast<size_t>( - Mix(Seed() ^ static_cast<std::make_unsigned_t<T>>(value), kMul)); + Mix(seed ^ static_cast<std::make_unsigned_t<T>>(value), kMul)); } template <typename T, absl::enable_if_t<!IntegralFastPath<T>::value, int> = 0> - static size_t hash(const T& value) { - return static_cast<size_t>(combine(MixingHashState{}, value).state_); + static size_t hash_with_seed(const T& value, size_t seed) { + return static_cast<size_t>(combine(MixingHashState{seed}, value).state_); } private: @@ -1153,151 +1335,6 @@ return MixingHashState::combine(std::move(state), unordered_state); } - // Implementation of the base case for combine_contiguous where we actually - // mix the bytes into the state. - // Dispatch to different implementations of the combine_contiguous depending - // on the value of `sizeof(size_t)`. - static uint64_t CombineContiguousImpl(uint64_t state, - const unsigned char* first, size_t len, - std::integral_constant<int, 4> - /* sizeof_size_t */); - static uint64_t CombineContiguousImpl(uint64_t state, - const unsigned char* first, size_t len, - std::integral_constant<int, 8> - /* sizeof_size_t */); - - ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t CombineSmallContiguousImpl( - uint64_t state, const unsigned char* first, size_t len) { - ABSL_ASSUME(len <= 8); - uint64_t v; - if (len >= 4) { - v = Read4To8(first, len); - } else if (len > 0) { - v = Read1To3(first, len); - } else { - // Empty string must modify the state. - v = 0x57; - } - return Mix(state ^ v, kMul); - } - - ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t CombineContiguousImpl9to16( - uint64_t state, const unsigned char* first, size_t len) { - ABSL_ASSUME(len >= 9); - ABSL_ASSUME(len <= 16); - // Note: any time one half of the mix function becomes zero it will fail to - // incorporate any bits from the other half. However, there is exactly 1 in - // 2^64 values for each side that achieve this, and only when the size is - // exactly 16 -- for smaller sizes there is an overlapping byte that makes - // this impossible unless the seed is *also* incredibly unlucky. - auto p = Read9To16(first, len); - return Mix(state ^ p.first, kMul ^ p.second); - } - - ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t CombineContiguousImpl17to32( - uint64_t state, const unsigned char* first, size_t len) { - ABSL_ASSUME(len >= 17); - ABSL_ASSUME(len <= 32); - // Do two mixes of overlapping 16-byte ranges in parallel to minimize - // latency. - const uint64_t m0 = - Mix(Read8(first) ^ kStaticRandomData[1], Read8(first + 8) ^ state); - - const unsigned char* tail_16b_ptr = first + (len - 16); - const uint64_t m1 = Mix(Read8(tail_16b_ptr) ^ kStaticRandomData[3], - Read8(tail_16b_ptr + 8) ^ state); - return m0 ^ m1; - } - - // Slow dispatch path for calls to CombineContiguousImpl with a size argument - // larger than PiecewiseChunkSize(). Has the same effect as calling - // CombineContiguousImpl() repeatedly with the chunk stride size. - static uint64_t CombineLargeContiguousImpl32(const unsigned char* first, - size_t len, uint64_t state); - static uint64_t CombineLargeContiguousImpl64(const unsigned char* first, - size_t len, uint64_t state); - - // Reads 9 to 16 bytes from p. - // The first 8 bytes are in .first, and the rest of the bytes are in .second - // along with duplicated bytes from .first if len<16. - static std::pair<uint64_t, uint64_t> Read9To16(const unsigned char* p, - size_t len) { - return {Read8(p), Read8(p + len - 8)}; - } - - // Reads 8 bytes from p. - static uint64_t Read8(const unsigned char* p) { - // Suppress erroneous array bounds errors on GCC. -#if defined(__GNUC__) && !defined(__clang__) -#pragma GCC diagnostic push -#pragma GCC diagnostic ignored "-Warray-bounds" -#endif - return absl::base_internal::UnalignedLoad64(p); -#if defined(__GNUC__) && !defined(__clang__) -#pragma GCC diagnostic pop -#endif - } - - // Reads 4 to 8 bytes from p. - // Bytes are permuted and some input bytes may be duplicated in output. - static uint64_t Read4To8(const unsigned char* p, size_t len) { - // If `len < 8`, we duplicate bytes. We always put low memory at the end. - // E.g., on little endian platforms: - // `ABCD` will be read as `ABCDABCD`. - // `ABCDE` will be read as `BCDEABCD`. - // `ABCDEF` will be read as `CDEFABCD`. - // `ABCDEFG` will be read as `DEFGABCD`. - // `ABCDEFGH` will be read as `EFGHABCD`. - // We also do not care about endianness. On big-endian platforms, bytes will - // be permuted differently. We always shift low memory by 32, because that - // can be pipelined earlier. Reading high memory requires computing - // `p + len - 4`. - uint64_t most_significant = - static_cast<uint64_t>(absl::base_internal::UnalignedLoad32(p)) << 32; - uint64_t least_significant = - absl::base_internal::UnalignedLoad32(p + len - 4); - return most_significant | least_significant; - } - - // Reads 1 to 3 bytes from p. Some input bytes may be duplicated in output. - static uint32_t Read1To3(const unsigned char* p, size_t len) { - // The trick used by this implementation is to avoid branches. - // We always read three bytes by duplicating. - // E.g., - // `A` is read as `AAA`. - // `AB` is read as `ABB`. - // `ABC` is read as `ABC`. - // We always shift `p[0]` so that it can be pipelined better. - // Other bytes require extra computation to find indices. - uint32_t mem0 = (static_cast<uint32_t>(p[0]) << 16) | p[len - 1]; - uint32_t mem1 = static_cast<uint32_t>(p[len / 2]) << 8; - return mem0 | mem1; - } - - ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Mix(uint64_t lhs, uint64_t rhs) { - // For 32 bit platforms we are trying to use all 64 lower bits. - if constexpr (sizeof(size_t) < 8) { - uint64_t m = lhs * rhs; - return m ^ (m >> 32); - } - // Though the 128-bit product on AArch64 needs two instructions, it is - // still a good balance between speed and hash quality. - uint128 m = lhs; - m *= rhs; - return Uint128High64(m) ^ Uint128Low64(m); - } - - ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Hash64(const unsigned char* data, - size_t len, - uint64_t state) { -#ifdef ABSL_HAVE_INTRINSIC_INT128 - return LowLevelHashLenGt32(data, len, state); -#else - return hash_internal::CityHash64WithSeed( - reinterpret_cast<const char*>(data), len, state); -#endif - } - // A non-deterministic seed. // // The current purpose of this seed is to generate non-deterministic results @@ -1327,52 +1364,6 @@ uint64_t state_; }; -inline uint64_t MixingHashState::CombineContiguousImpl( - uint64_t state, const unsigned char* first, size_t len, - std::integral_constant<int, 4> /* sizeof_size_t */) { - // For large values we use CityHash, for small ones we use custom low latency - // hash. - if (len <= 8) { - return CombineSmallContiguousImpl(PrecombineLengthMix(state, len), first, - len); - } - if (ABSL_PREDICT_TRUE(len <= PiecewiseChunkSize())) { - // TODO(b/417141985): expose and use CityHash32WithSeed. - return Mix(PrecombineLengthMix(state, len) ^ - hash_internal::CityHash32( - reinterpret_cast<const char*>(first), len), - kMul); - } - return CombineLargeContiguousImpl32(first, len, state); -} - -inline uint64_t MixingHashState::CombineContiguousImpl( - uint64_t state, const unsigned char* first, size_t len, - std::integral_constant<int, 8> /* sizeof_size_t */) { - // For large values we use LowLevelHash or CityHash depending on the platform, - // for small ones we use custom low latency hash. - if (len <= 8) { - return CombineSmallContiguousImpl(PrecombineLengthMix(state, len), first, - len); - } - if (len <= 16) { - return CombineContiguousImpl9to16(PrecombineLengthMix(state, len), first, - len); - } - if (len <= 32) { - return CombineContiguousImpl17to32(PrecombineLengthMix(state, len), first, - len); - } - if (ABSL_PREDICT_TRUE(len <= PiecewiseChunkSize())) { - // Length is mixed into the state inside of Hash64. - return Hash64(first, len, state); - } - // We must not mix length to the state here because calling - // CombineContiguousImpl twice with PiecewiseChunkSize() must be equivalent - // to calling CombineLargeContiguousImpl once with 2 * PiecewiseChunkSize(). - return CombineLargeContiguousImpl64(first, len, state); -} - struct AggregateBarrier {}; // Add a private base class to make sure this type is not an aggregate. @@ -1389,6 +1380,13 @@ size_t operator()(const T& value) const { return MixingHashState::hash(value); } + + private: + friend struct HashWithSeed; + + size_t hash_with_seed(const T& value, size_t seed) const { + return MixingHashState::hash_with_seed(value, seed); + } }; template <typename T>
diff --git a/absl/hash/internal/low_level_hash.cc b/absl/hash/internal/low_level_hash.cc deleted file mode 100644 index 575cf74..0000000 --- a/absl/hash/internal/low_level_hash.cc +++ /dev/null
@@ -1,106 +0,0 @@ -// Copyright 2020 The Abseil Authors -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include "absl/hash/internal/low_level_hash.h" - -#include <cassert> -#include <cstddef> -#include <cstdint> - -#include "absl/base/config.h" -#include "absl/base/internal/unaligned_access.h" -#include "absl/base/optimization.h" -#include "absl/base/prefetch.h" -#include "absl/numeric/int128.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace hash_internal { -namespace { - -uint64_t Mix(uint64_t v0, uint64_t v1) { - absl::uint128 p = v0; - p *= v1; - return absl::Uint128Low64(p) ^ absl::Uint128High64(p); -} - -uint64_t Mix32Bytes(const uint8_t* ptr, uint64_t current_state) { - uint64_t a = absl::base_internal::UnalignedLoad64(ptr); - uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); - uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); - uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); - - uint64_t cs0 = Mix(a ^ kStaticRandomData[1], b ^ current_state); - uint64_t cs1 = Mix(c ^ kStaticRandomData[2], d ^ current_state); - return cs0 ^ cs1; -} - -} // namespace - -uint64_t LowLevelHashLenGt32(const void* data, size_t len, uint64_t seed) { - assert(len > 32); - const uint8_t* ptr = static_cast<const uint8_t*>(data); - uint64_t current_state = seed ^ kStaticRandomData[0] ^ len; - const uint8_t* last_32_ptr = ptr + len - 32; - - if (len > 64) { - // If we have more than 64 bytes, we're going to handle chunks of 64 - // bytes at a time. We're going to build up four separate hash states - // which we will then hash together. This avoids short dependency chains. - uint64_t duplicated_state0 = current_state; - uint64_t duplicated_state1 = current_state; - uint64_t duplicated_state2 = current_state; - - do { - // Always prefetch the next cacheline. - PrefetchToLocalCache(ptr + ABSL_CACHELINE_SIZE); - - uint64_t a = absl::base_internal::UnalignedLoad64(ptr); - uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); - uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); - uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); - uint64_t e = absl::base_internal::UnalignedLoad64(ptr + 32); - uint64_t f = absl::base_internal::UnalignedLoad64(ptr + 40); - uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48); - uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56); - - current_state = Mix(a ^ kStaticRandomData[1], b ^ current_state); - duplicated_state0 = Mix(c ^ kStaticRandomData[2], d ^ duplicated_state0); - - duplicated_state1 = Mix(e ^ kStaticRandomData[3], f ^ duplicated_state1); - duplicated_state2 = Mix(g ^ kStaticRandomData[4], h ^ duplicated_state2); - - ptr += 64; - len -= 64; - } while (len > 64); - - current_state = (current_state ^ duplicated_state0) ^ - (duplicated_state1 + duplicated_state2); - } - - // We now have a data `ptr` with at most 64 bytes and the current state - // of the hashing state machine stored in current_state. - if (len > 32) { - current_state = Mix32Bytes(ptr, current_state); - } - - // We now have a data `ptr` with at most 32 bytes and the current state - // of the hashing state machine stored in current_state. But we can - // safely read from `ptr + len - 32`. - return Mix32Bytes(last_32_ptr, current_state); -} - -} // namespace hash_internal -ABSL_NAMESPACE_END -} // namespace absl
diff --git a/absl/hash/internal/low_level_hash.h b/absl/hash/internal/low_level_hash.h deleted file mode 100644 index bb2821c..0000000 --- a/absl/hash/internal/low_level_hash.h +++ /dev/null
@@ -1,57 +0,0 @@ -// Copyright 2020 The Abseil Authors -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// This file provides the Google-internal implementation of LowLevelHash. -// -// LowLevelHash is a fast hash function for hash tables, the fastest we've -// currently (late 2020) found that passes the SMHasher tests. The algorithm -// relies on intrinsic 128-bit multiplication for speed. This is not meant to be -// secure - just fast. -// -// It is closely based on a version of wyhash, but does not maintain or -// guarantee future compatibility with it. - -#ifndef ABSL_HASH_INTERNAL_LOW_LEVEL_HASH_H_ -#define ABSL_HASH_INTERNAL_LOW_LEVEL_HASH_H_ - -#include <stdint.h> -#include <stdlib.h> - -#include "absl/base/config.h" -#include "absl/base/optimization.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace hash_internal { - -// Random data taken from the hexadecimal digits of Pi's fractional component. -// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number -ABSL_CACHELINE_ALIGNED static constexpr uint64_t kStaticRandomData[] = { - 0x243f'6a88'85a3'08d3, 0x1319'8a2e'0370'7344, 0xa409'3822'299f'31d0, - 0x082e'fa98'ec4e'6c89, 0x4528'21e6'38d0'1377, -}; - -// Hash function for a byte array. A 64-bit seed and a set of five 64-bit -// integers are hashed into the result. The length must be greater than 32. -// -// To allow all hashable types (including string_view and Span) to depend on -// this algorithm, we keep the API low-level, with as few dependencies as -// possible. -uint64_t LowLevelHashLenGt32(const void* data, size_t len, uint64_t seed); - -} // namespace hash_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_HASH_INTERNAL_LOW_LEVEL_HASH_H_
diff --git a/absl/hash/internal/low_level_hash_test.cc b/absl/hash/internal/low_level_hash_test.cc index fcfa6eb..9b7868c 100644 --- a/absl/hash/internal/low_level_hash_test.cc +++ b/absl/hash/internal/low_level_hash_test.cc
@@ -12,25 +12,26 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include "absl/hash/internal/low_level_hash.h" - #include <cstddef> #include <cstdint> +#include <string> #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/hash/hash.h" #include "absl/strings/escaping.h" +#include "absl/strings/string_view.h" #define UPDATE_GOLDEN 0 namespace { TEST(LowLevelHashTest, VerifyGolden) { - constexpr size_t kNumGoldenOutputs = 94; + constexpr size_t kNumGoldenOutputs = 95; static struct { absl::string_view base64_data; uint64_t seed; - } cases[] = { + } cases[kNumGoldenOutputs] = { {"VprUGNH+5NnNRaORxgH/ySrZFQFDL+4VAodhfBNinmn8cg==", uint64_t{0x531858a40bfa7ea1}}, {"gc1xZaY+q0nPcUvOOnWnT3bqfmT/geth/f7Dm2e/DemMfk4=", @@ -357,9 +358,12 @@ uint64_t{0xc9ae5c8759b4877a}}, }; -#if defined(ABSL_IS_BIG_ENDIAN) +#if defined(ABSL_IS_BIG_ENDIAN) || !defined(ABSL_HAVE_INTRINSIC_INT128) || \ + UINTPTR_MAX != UINT64_MAX constexpr uint64_t kGolden[kNumGoldenOutputs] = {}; - GTEST_SKIP() << "We only maintain golden data for little endian systems."; + GTEST_SKIP() + << "We only maintain golden data for little endian 64 bit systems with " + "128 bit intristics."; #else constexpr uint64_t kGolden[kNumGoldenOutputs] = { 0x669da02f8d009e0f, 0xceb19bf2255445cd, 0x0e746992d6d43a7c, @@ -393,18 +397,22 @@ 0xb8116dd26cf6feec, 0x7a77a6e4ed0cf081, 0xb71eec2d5a184316, 0x6fa932f77b4da817, 0x795f79b33909b2c4, 0x1b8755ef6b5eb34e, 0x2255b72d7d6b2d79, 0xf2bdafafa90bd50a, 0x442a578f02cb1fc8, - 0xc25aefe55ecf83db, + 0xc25aefe55ecf83db, 0x3114c056f9c5a676, }; #endif + auto hash_fn = [](absl::string_view s, uint64_t state) { + return absl::hash_internal::CombineLargeContiguousImplOn64BitLengthGt32( + reinterpret_cast<const unsigned char*>(s.data()), s.size(), state); + }; + #if UPDATE_GOLDEN (void)kGolden; // Silence warning. for (size_t i = 0; i < kNumGoldenOutputs; ++i) { std::string str; ASSERT_TRUE(absl::Base64Unescape(cases[i].base64_data, &str)); ASSERT_GT(str.size(), 32); - uint64_t h = absl::hash_internal::LowLevelHashLenGt32( - str.data(), str.size(), cases[i].seed); + uint64_t h = hash_fn(str, cases[i].seed); printf("0x%016" PRIx64 ", ", h); if (i % 3 == 2) { printf("\n"); @@ -419,9 +427,7 @@ std::string str; ASSERT_TRUE(absl::Base64Unescape(cases[i].base64_data, &str)); ASSERT_GT(str.size(), 32); - EXPECT_EQ(absl::hash_internal::LowLevelHashLenGt32(str.data(), str.size(), - cases[i].seed), - kGolden[i]); + EXPECT_EQ(hash_fn(str, cases[i].seed), kGolden[i]); } #endif }
diff --git a/absl/log/check_test_impl.inc b/absl/log/check_test_impl.inc index 7a0000e..37226a3 100644 --- a/absl/log/check_test_impl.inc +++ b/absl/log/check_test_impl.inc
@@ -22,6 +22,8 @@ #error ABSL_TEST_CHECK must be defined for these tests to work. #endif +#include <cstdint> +#include <limits> #include <ostream> #include <string> @@ -40,6 +42,7 @@ using ::testing::AllOf; using ::testing::AnyOf; +using ::testing::ContainsRegex; using ::testing::HasSubstr; using ::testing::Not; @@ -638,9 +641,8 @@ EXPECT_DEATH( ABSL_TEST_CHECK_EQ(p, nullptr), AnyOf( - HasSubstr("Check failed: p == nullptr (0000000000001234 vs. (null))"), - HasSubstr("Check failed: p == nullptr (0x1234 vs. (null))") - )); + HasSubstr("Check failed: p == nullptr (0000000000001234 vs. (null))"), + HasSubstr("Check failed: p == nullptr (0x1234 vs. (null))"))); } // An uncopyable object with operator<<. @@ -670,6 +672,273 @@ HasSubstr("Check failed: v1 == v2 (Uncopyable{1} vs. Uncopyable{2})")); } +enum class ScopedEnum { kValue1 = 1, kValue2 = 2 }; + +TEST(CHECKTest, TestScopedEnumComparisonChecks) { + ABSL_TEST_CHECK_EQ(ScopedEnum::kValue1, ScopedEnum::kValue1); + ABSL_TEST_CHECK_NE(ScopedEnum::kValue1, ScopedEnum::kValue2); + ABSL_TEST_CHECK_LT(ScopedEnum::kValue1, ScopedEnum::kValue2); + ABSL_TEST_CHECK_LE(ScopedEnum::kValue1, ScopedEnum::kValue2); + ABSL_TEST_CHECK_GT(ScopedEnum::kValue2, ScopedEnum::kValue1); + ABSL_TEST_CHECK_GE(ScopedEnum::kValue2, ScopedEnum::kValue2); + ABSL_TEST_DCHECK_EQ(ScopedEnum::kValue1, ScopedEnum::kValue1); + ABSL_TEST_DCHECK_NE(ScopedEnum::kValue1, ScopedEnum::kValue2); + ABSL_TEST_DCHECK_LT(ScopedEnum::kValue1, ScopedEnum::kValue2); + ABSL_TEST_DCHECK_LE(ScopedEnum::kValue1, ScopedEnum::kValue2); + ABSL_TEST_DCHECK_GT(ScopedEnum::kValue2, ScopedEnum::kValue1); + ABSL_TEST_DCHECK_GE(ScopedEnum::kValue2, ScopedEnum::kValue2); + + // Check that overloads work correctly with references as well. + const ScopedEnum x = ScopedEnum::kValue1; + const ScopedEnum& x_ref = x; + ABSL_TEST_CHECK_EQ(x, x_ref); + ABSL_TEST_CHECK_EQ(x_ref, x_ref); +} + +#if GTEST_HAS_DEATH_TEST +TEST(CHECKDeathTest, TestScopedEnumCheckFailureMessagePrintsIntegerValues) { + const auto e1 = ScopedEnum::kValue1; + const auto e2 = ScopedEnum::kValue2; + EXPECT_DEATH(ABSL_TEST_CHECK_EQ(e1, e2), + ContainsRegex(R"re(Check failed:.*\(1 vs. 2\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_NE(e1, e1), + ContainsRegex(R"re(Check failed:.*\(1 vs. 1\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_GT(e1, e1), + ContainsRegex(R"re(Check failed:.*\(1 vs. 1\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_GE(e1, e2), + ContainsRegex(R"re(Check failed:.*\(1 vs. 2\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_LT(e2, e2), + ContainsRegex(R"re(Check failed:.*\(2 vs. 2\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_LE(e2, e1), + ContainsRegex(R"re(Check failed:.*\(2 vs. 1\))re")); + + const auto& e1_ref = e1; + EXPECT_DEATH(ABSL_TEST_CHECK_NE(e1_ref, e1), + ContainsRegex(R"re(Check failed:.*\(1 vs. 1\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_NE(e1_ref, e1_ref), + ContainsRegex(R"re(Check failed:.*\(1 vs. 1\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_EQ(e2, e1_ref), + ContainsRegex(R"re(Check failed:.*\(2 vs. 1\))re")); + +#ifndef NDEBUG + EXPECT_DEATH(ABSL_TEST_DCHECK_EQ(e2, e1), + ContainsRegex(R"re(Check failed:.*\(2 vs. 1\))re")); +#else + // DHECK_EQ is not evaluated in non-debug mode. + ABSL_TEST_DCHECK_EQ(e2, e1); +#endif // NDEBUG +} +#endif // GTEST_HAS_DEATH_TEST + +enum class ScopedInt8Enum : int8_t { + kValue1 = 1, + kValue2 = 66 // Printable ascii value 'B'. +}; + +TEST(CHECKDeathTest, TestScopedInt8EnumCheckFailureMessagePrintsCharValues) { + const auto e1 = ScopedInt8Enum::kValue1; + const auto e2 = ScopedInt8Enum::kValue2; + EXPECT_DEATH( + ABSL_TEST_CHECK_EQ(e1, e2), + ContainsRegex(R"re(Check failed:.*\(signed char value 1 vs. 'B'\))re")); + EXPECT_DEATH( + ABSL_TEST_CHECK_NE(e1, e1), + ContainsRegex( + R"re(Check failed:.*\(signed char value 1 vs. signed char value 1\))re")); + EXPECT_DEATH( + ABSL_TEST_CHECK_GT(e1, e1), + ContainsRegex( + R"re(Check failed:.*\(signed char value 1 vs. signed char value 1\))re")); + EXPECT_DEATH( + ABSL_TEST_CHECK_GE(e1, e2), + ContainsRegex(R"re(Check failed:.*\(signed char value 1 vs. 'B'\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_LT(e2, e2), + ContainsRegex(R"re(Check failed:.*\('B' vs. 'B'\))re")); + EXPECT_DEATH( + ABSL_TEST_CHECK_LE(e2, e1), + ContainsRegex(R"re(Check failed:.*\('B' vs. signed char value 1\))re")); +} + +enum class ScopedUnsignedEnum : uint16_t { + kValue1 = std::numeric_limits<uint16_t>::min(), + kValue2 = std::numeric_limits<uint16_t>::max() +}; + +TEST(CHECKDeathTest, + TestScopedUnsignedEnumCheckFailureMessagePrintsCorrectValues) { + const auto e1 = ScopedUnsignedEnum::kValue1; + const auto e2 = ScopedUnsignedEnum::kValue2; + EXPECT_DEATH(ABSL_TEST_CHECK_EQ(e1, e2), + ContainsRegex(R"re(Check failed:.*\(0 vs. 65535\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_NE(e1, e1), + ContainsRegex(R"re(Check failed:.*\(0 vs. 0\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_GT(e1, e1), + ContainsRegex(R"re(Check failed:.*\(0 vs. 0\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_GE(e1, e2), + ContainsRegex(R"re(Check failed:.*\(0 vs. 65535\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_LT(e1, e1), + ContainsRegex(R"re(Check failed:.*\(0 vs. 0\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_LE(e2, e1), + ContainsRegex(R"re(Check failed:.*\(65535 vs. 0\))re")); +} + +enum class ScopedInt64Enum : int64_t { + kMin = std::numeric_limits<int64_t>::min(), + kMax = std::numeric_limits<int64_t>::max(), +}; + +// Tests that int64-backed enums are printed correctly even for very large and +// very small values. +TEST(CHECKDeathTest, TestScopedInt64EnumCheckFailureMessage) { + const auto min = ScopedInt64Enum::kMin; + const auto max = ScopedInt64Enum::kMax; + EXPECT_DEATH( + ABSL_TEST_CHECK_EQ(max, min), + ContainsRegex( + "Check failed:.*9223372036854775807 vs. -9223372036854775808")); + EXPECT_DEATH( + ABSL_TEST_CHECK_NE(max, max), + ContainsRegex( + "Check failed:.*9223372036854775807 vs. 9223372036854775807")); + EXPECT_DEATH( + ABSL_TEST_CHECK_GT(min, min), + ContainsRegex( + "Check failed:.*-9223372036854775808 vs. -9223372036854775808")); + EXPECT_DEATH( + ABSL_TEST_CHECK_GE(min, max), + ContainsRegex( + R"(Check failed:.*-9223372036854775808 vs. 9223372036854775807)")); + EXPECT_DEATH( + ABSL_TEST_CHECK_LT(max, max), + ContainsRegex( + R"(Check failed:.*9223372036854775807 vs. 9223372036854775807)")); + EXPECT_DEATH( + ABSL_TEST_CHECK_LE(max, min), + ContainsRegex( + R"(Check failed:.*9223372036854775807 vs. -9223372036854775808)")); +} + +enum class ScopedBoolEnum : bool { + kFalse, + kTrue, +}; + +TEST(CHECKDeathTest, TestScopedBoolEnumCheckFailureMessagePrintsCorrectValues) { + const auto t = ScopedBoolEnum::kTrue; + const auto f = ScopedBoolEnum::kFalse; + EXPECT_DEATH(ABSL_TEST_CHECK_EQ(t, f), + ContainsRegex(R"re(Check failed:.*\(1 vs. 0\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_NE(f, f), + ContainsRegex(R"re(Check failed:.*\(0 vs. 0\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_GT(f, f), + ContainsRegex(R"re(Check failed:.*\(0 vs. 0\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_GE(f, t), + ContainsRegex(R"re(Check failed:.*\(0 vs. 1\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_LT(t, t), + ContainsRegex(R"re(Check failed:.*\(1 vs. 1\))re")); + EXPECT_DEATH(ABSL_TEST_CHECK_LE(t, f), + ContainsRegex(R"re(Check failed:.*\(1 vs. 0\))re")); +} + +enum class ScopedEnumWithAbslStringify { + kValue1 = 1, + kValue2 = 2, + kValue3 = 3 +}; + +template <typename Sink> +void AbslStringify(Sink& sink, ScopedEnumWithAbslStringify v) { + switch (v) { + case ScopedEnumWithAbslStringify::kValue1: + sink.Append("AbslStringify: kValue1"); + break; + case ScopedEnumWithAbslStringify::kValue2: + sink.Append("AbslStringify: kValue2"); + break; + case ScopedEnumWithAbslStringify::kValue3: + sink.Append("AbslStringify: kValue3"); + break; + } +} + +#if GTEST_HAS_DEATH_TEST +TEST(CHECKDeathTest, TestScopedEnumUsesAbslStringify) { + EXPECT_DEATH(ABSL_TEST_CHECK_EQ(ScopedEnumWithAbslStringify::kValue1, + ScopedEnumWithAbslStringify::kValue2), + ContainsRegex("Check failed:.*AbslStringify: kValue1 vs. " + "AbslStringify: kValue2")); +} +#endif // GTEST_HAS_DEATH_TEST + +enum class ScopedEnumWithOutputOperator { + kValue1 = 1, + kValue2 = 2, +}; + +std::ostream& operator<<(std::ostream& os, ScopedEnumWithOutputOperator v) { + switch (v) { + case ScopedEnumWithOutputOperator::kValue1: + os << "OutputOperator: kValue1"; + break; + case ScopedEnumWithOutputOperator::kValue2: + os << "OutputOperator: kValue2"; + break; + } + return os; +} + +#if GTEST_HAS_DEATH_TEST +TEST(CHECKDeathTest, TestOutputOperatorIsUsedForScopedEnum) { + EXPECT_DEATH(ABSL_TEST_CHECK_EQ(ScopedEnumWithOutputOperator::kValue1, + ScopedEnumWithOutputOperator::kValue2), + ContainsRegex("Check failed:.*OutputOperator: kValue1 vs. " + "OutputOperator: kValue2")); +} +#endif // GTEST_HAS_DEATH_TEST + +enum class ScopedEnumWithAbslStringifyAndOutputOperator { + kValue1 = 1, + kValue2 = 2, +}; + +template <typename Sink> +void AbslStringify(Sink& sink, ScopedEnumWithAbslStringifyAndOutputOperator v) { + switch (v) { + case ScopedEnumWithAbslStringifyAndOutputOperator::kValue1: + sink.Append("AbslStringify: kValue1"); + break; + case ScopedEnumWithAbslStringifyAndOutputOperator::kValue2: + sink.Append("AbslStringify: kValue2"); + break; + } +} + +std::ostream& operator<<(std::ostream& os, + ScopedEnumWithAbslStringifyAndOutputOperator v) { + switch (v) { + case ScopedEnumWithAbslStringifyAndOutputOperator::kValue1: + os << "OutputOperator: kValue1"; + break; + case ScopedEnumWithAbslStringifyAndOutputOperator::kValue2: + os << "OutputOperator: kValue2"; + break; + } + return os; +} + +#if GTEST_HAS_DEATH_TEST + +// Test that, if operator<< and AbslStringify are both defined for a scoped +// enum, streaming takes precedence over AbslStringify. +TEST(CHECKDeathTest, TestScopedEnumPrefersOutputOperatorOverAbslStringify) { + EXPECT_DEATH( + ABSL_TEST_CHECK_EQ(ScopedEnumWithAbslStringifyAndOutputOperator::kValue1, + ScopedEnumWithAbslStringifyAndOutputOperator::kValue2), + ContainsRegex("Check failed:.*OutputOperator: kValue1 vs. " + "OutputOperator: kValue2")); +} +#endif // GTEST_HAS_DEATH_TEST + } // namespace absl_log_internal // NOLINTEND(misc-definitions-in-headers)
diff --git a/absl/log/internal/check_op.h b/absl/log/internal/check_op.h index 17afded..d7b55f6 100644 --- a/absl/log/internal/check_op.h +++ b/absl/log/internal/check_op.h
@@ -298,12 +298,11 @@ // This overload triggers when the call is ambiguous. // It means that T is either one from this list or printed as one from this -// list. Eg an enum that decays to `int` for printing. +// list. Eg an unscoped enum that decays to `int` for printing. // We ask the overload set to give us the type we want to convert it to. template <typename T> -decltype(detect_specialization::operator<<(std::declval<std::ostream&>(), - std::declval<const T&>())) -Detect(char); +decltype(detect_specialization::operator<<( + std::declval<std::ostream&>(), std::declval<const T&>())) Detect(char); // A sink for AbslStringify which redirects everything to a std::ostream. class StringifySink { @@ -344,6 +343,35 @@ std::enable_if_t<HasAbslStringify<T>::value, StringifyToStreamWrapper<T>> Detect(...); // Ellipsis has lowest preference when int passed. + +// is_streamable is true for types that have an output stream operator<<. +template <class T, class = void> +struct is_streamable : std::false_type {}; + +template <class T> +struct is_streamable<T, std::void_t<decltype(std::declval<std::ostream&>() + << std::declval<T>())>> + : std::true_type {}; + +// This overload triggers when T is a scoped enum that has not defined an output +// stream operator (operator<<) or AbslStringify. It causes the enum value to be +// converted to a type that can be streamed. For consistency with other enums, a +// scoped enum backed by a bool or char is converted to its underlying type, and +// one backed by another integer is converted to (u)int64_t. +template <typename T> +std::enable_if_t< + std::conjunction_v< + std::is_enum<T>, std::negation<std::is_convertible<T, int>>, + std::negation<is_streamable<T>>, std::negation<HasAbslStringify<T>>>, + std::conditional_t< + std::is_same_v<std::underlying_type_t<T>, bool> || + std::is_same_v<std::underlying_type_t<T>, char> || + std::is_same_v<std::underlying_type_t<T>, signed char> || + std::is_same_v<std::underlying_type_t<T>, unsigned char>, + std::underlying_type_t<T>, + std::conditional_t<std::is_signed_v<std::underlying_type_t<T>>, int64_t, + uint64_t>>> +Detect(...); } // namespace detect_specialization template <typename T>
diff --git a/absl/numeric/bits_test.cc b/absl/numeric/bits_test.cc index 2977976..e2c6409 100644 --- a/absl/numeric/bits_test.cc +++ b/absl/numeric/bits_test.cc
@@ -151,6 +151,9 @@ EXPECT_EQ(rotl(uint32_t{0x12345678UL}, -4), uint32_t{0x81234567UL}); EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, -4), uint64_t{0x112345678ABCDEF0ULL}); + + EXPECT_EQ(rotl(uint32_t{1234}, std::numeric_limits<int>::min()), + uint32_t{1234}); } TEST(Rotate, Right) { @@ -190,6 +193,9 @@ EXPECT_EQ(rotr(uint32_t{0x12345678UL}, -4), uint32_t{0x23456781UL}); EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, -4), uint64_t{0x2345678ABCDEF011ULL}); + + EXPECT_EQ(rotl(uint32_t{1234}, std::numeric_limits<int>::min()), + uint32_t{1234}); } TEST(Rotate, Symmetry) {
diff --git a/absl/numeric/internal/bits.h b/absl/numeric/internal/bits.h index e1d18b8..e681544 100644 --- a/absl/numeric/internal/bits.h +++ b/absl/numeric/internal/bits.h
@@ -77,8 +77,28 @@ static_assert(IsPowerOf2(std::numeric_limits<T>::digits), "T must have a power-of-2 size"); - return static_cast<T>(x >> (s & (std::numeric_limits<T>::digits - 1))) | - static_cast<T>(x << ((-s) & (std::numeric_limits<T>::digits - 1))); + // Rotate by s mod the number of digits to avoid unnecessary rotations. + // + // A negative s represents a left rotation instead of a right rotation. + // We compute it as an equivalent complementary right rotation by leveraging + // its two's complement representation. + // + // For example, suppose we rotate a 3-bit number by -2. + // In that case: + // * s = 0b11111111111111111111111111111110 + // * n = 8 + // * r = (0b11111111111111111111111111111110 & 0b111) = 0b110 + // + // Instead of rotating by 2 to the left, we rotate by 6 to the right, which + // is equivalent. + const int n = std::numeric_limits<T>::digits; + const int r = s & (n - 1); + + if (r == 0) { + return x; + } else { + return (x >> r) | (x << (n - r)); + } } template <class T> @@ -88,8 +108,16 @@ static_assert(IsPowerOf2(std::numeric_limits<T>::digits), "T must have a power-of-2 size"); - return static_cast<T>(x << (s & (std::numeric_limits<T>::digits - 1))) | - static_cast<T>(x >> ((-s) & (std::numeric_limits<T>::digits - 1))); + // Rotate by s mod the number of digits to avoid unnecessary rotations. + // See comment in RotateRight for a detailed explanation of the logic below. + const int n = std::numeric_limits<T>::digits; + const int r = s & (n - 1); + + if (r == 0) { + return x; + } else { + return (x << r) | (x >> (n - r)); + } } ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
diff --git a/absl/strings/str_split.h b/absl/strings/str_split.h index 7e8e31c..761568a 100644 --- a/absl/strings/str_split.h +++ b/absl/strings/str_split.h
@@ -277,7 +277,7 @@ class MaxSplitsImpl { public: MaxSplitsImpl(Delimiter delimiter, int limit) - : delimiter_(delimiter), limit_(limit), count_(0) {} + : delimiter_(std::move(delimiter)), limit_(limit), count_(0) {} absl::string_view Find(absl::string_view text, size_t pos) { if (count_++ == limit_) { return absl::string_view(text.data() + text.size(),