Add SlotEqFn and get_eq_slot_fn to compare keys with table slots. Add SlotEqFn to container_memory.h to compare search keys with keys stored at offset 0 of a slot (or pointed-to node for node tables). Add get_eq_slot_fn to table policies and hash_policy_traits to expose slot equality functors. This will be used in follow-up changes to share table insertion code. PiperOrigin-RevId: 1020456548
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h index 3a9ada7..5e18999 100644 --- a/absl/container/flat_hash_map.h +++ b/absl/container/flat_hash_map.h
@@ -711,6 +711,10 @@ return GetTypeErasedApplyToSlotFn<Hash, K, kIsDefault, kSeedShift>(); } + static constexpr auto get_eq_slot_fn() { + return SlotEqFn<K, /*kDerefSlot=*/false>{}; + } + static std::pair<const K, V>& element(slot_type* slot) { return slot->value; } };
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index 436c525..b4245ec 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h
@@ -593,6 +593,10 @@ static constexpr HashSlotFn get_hash_slot_fn() { return GetTypeErasedApplyToSlotFn<Hash, T, kIsAbsl, kSeedShift>(); } + + static constexpr auto get_eq_slot_fn() { + return SlotEqFn<T, /*kDerefSlot=*/false>{}; + } }; } // namespace container_internal
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index 84f86d8..e09b880 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -19,6 +19,7 @@ #include <cstddef> #include <cstdint> #include <cstring> +#include <functional> #include <memory> #include <new> #include <tuple> @@ -639,6 +640,25 @@ type_traits_internal::AddConstRefIfExpensiveToCopy<KeyEqual> eq; }; +// Type-erased slot equality functor with the key at offset 0 of `slot` (or +// `*slot` if `kDerefSlot` is true). +template <class SlotKey, bool kDerefSlot> +struct SlotEqFn { + using SlotKeyType = const SlotKey; + + template <class Eq, class SearchKey> + bool operator()(const Eq& eq, const void* slot, const SearchKey& key) const { + if constexpr (kDerefSlot) { + const void* node; + // Copy the pointer to avoid strict aliasing issues. + std::memcpy(&node, slot, sizeof(node)); + slot = node; + } + return EqualElement<SearchKey, Eq>{key, + eq}(*static_cast<const SlotKey*>(slot)); + } +}; + // Type erased function for computing hash of the slot. using HashSlotFn = size_t (*)(const void* hash_fn, void* slot, size_t seed);
diff --git a/absl/container/internal/container_memory_test.cc b/absl/container/internal/container_memory_test.cc index c7978df..619a749 100644 --- a/absl/container/internal/container_memory_test.cc +++ b/absl/container/internal/container_memory_test.cc
@@ -17,6 +17,7 @@ #include <cstddef> #include <cstdint> #include <cstring> +#include <functional> #include <map> #include <memory> #include <string> @@ -400,6 +401,41 @@ (HashElement<decltype(hash), /*kIsAbsl=*/false, 0>(hash, seed)(a))); } +TEST(EqSlotFnTest, SlotEqFnWorks) { + auto test_eq = [](auto eq) { + std::string key = "a"; + SlotEqFn<std::string, /*kDerefSlot=*/false> eq_slot; + static_assert(std::is_empty_v<decltype(eq_slot)>); + static_assert( + std::is_same_v<typename decltype(eq_slot)::SlotKeyType, + const std::string>); + std::string slot_match = "a"; + std::string slot_mismatch = "b"; + EXPECT_TRUE(eq_slot(eq, &slot_match, key)); + EXPECT_FALSE(eq_slot(eq, &slot_mismatch, key)); + + SlotEqFn<std::string, /*kDerefSlot=*/true> eq_deref; + static_assert(std::is_empty_v<decltype(eq_deref)>); + static_assert( + std::is_same_v<typename decltype(eq_deref)::SlotKeyType, + const std::string>); + std::string* slot_match_ptr = &slot_match; + std::string* slot_mismatch_ptr = &slot_mismatch; + EXPECT_TRUE(eq_deref(eq, &slot_match_ptr, key)); + EXPECT_FALSE(eq_deref(eq, &slot_mismatch_ptr, key)); + }; + + test_eq(std::equal_to<std::string>{}); + + struct StatefulEq { + int dummy = 0; + bool operator()(const std::string& lhs, const std::string& rhs) const { + return lhs == rhs; + } + }; + test_eq(StatefulEq{1}); +} + TEST(HashElement, DefaultHash) { size_t x = 7; size_t seed = 100;
diff --git a/absl/container/internal/hash_policy_traits.h b/absl/container/internal/hash_policy_traits.h index 0d3939d..9ce5d0f 100644 --- a/absl/container/internal/hash_policy_traits.h +++ b/absl/container/internal/hash_policy_traits.h
@@ -166,7 +166,40 @@ #endif } + // Returns a slot-equality functor for comparing keys with a slot. + // TODO(b/575748507): Require `get_eq_slot_fn` for all policies and remove + // `PolicyEqSlotFn` and `EqKeyNonTypeErased`. + static constexpr auto get_eq_slot_fn() { + auto fn = PolicyEqSlotFn(0); + if constexpr (std::is_null_pointer_v<decltype(fn)>) { + return EqKeyNonTypeErased{}; + } else { + return fn; + } + } + private: + // Returns `Policy::get_eq_slot_fn`, or nullptr if `Policy` doesn't define it. + template <class P = Policy> + static constexpr auto PolicyEqSlotFn(int) -> decltype(P::get_eq_slot_fn()) { + return P::get_eq_slot_fn(); + } + static constexpr std::nullptr_t PolicyEqSlotFn(char) { return nullptr; } + + // Fallback slot equality functor using `Policy::apply` for custom layouts. + struct EqKeyNonTypeErased { + using SlotKeyType = const key_type; + + template <class Eq, class SearchKey> + bool operator()(const Eq& eq, const void* slot, + const SearchKey& key) const { + return Policy::apply( + EqualElement<SearchKey, Eq>{key, eq}, + hash_policy_traits::element( + static_cast<slot_type*>(const_cast<void*>(slot)))); + } + }; + template <class Hash, bool kIsAbsl, size_t kSeedShift> static size_t hash_slot_fn_non_type_erased(const void* hash_fn, void* slot, size_t seed) {
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h index 0d9aec2..92f3d2e 100644 --- a/absl/container/node_hash_map.h +++ b/absl/container/node_hash_map.h
@@ -687,6 +687,10 @@ static_assert(memory_internal::OffsetOf<value_type>::kFirst == 0); return GetTypeErasedDerefAndApplyToSlotFn<Hash, Key, kIsAbsl, kSeedShift>(); } + + static constexpr auto get_eq_slot_fn() { + return SlotEqFn<Key, /*kDerefSlot=*/true>{}; + } }; } // namespace container_internal
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h index 5acd059..862d9ab 100644 --- a/absl/container/node_hash_set.h +++ b/absl/container/node_hash_set.h
@@ -587,6 +587,10 @@ static constexpr HashSlotFn get_hash_slot_fn() { return GetTypeErasedDerefAndApplyToSlotFn<Hash, T, kIsAbsl, kSeedShift>(); } + + static constexpr auto get_eq_slot_fn() { + return SlotEqFn<T, /*kDerefSlot=*/true>{}; + } }; } // namespace container_internal