Introduce absl::TransparentHash for transparent hashing of multiple types. absl::TransparentHash<Ts...> is a hash functor that can hash any of the types Ts... It is marked as transparent (is_transparent = void). This allows containers like absl::flat_hash_map to use a single hash functor for lookups with different but comparable types (e.g., std::string and absl::string_view). Added a test case in absl/hash/hash_test.cc using Name and NameView to demonstrate and test absl::TransparentHash with a custom transparent equality functor. ``` name cpu/op cpu/op vs base BM_TransparentFind 2.620n ± 1% 2.413n ± 1% -7.90% (p=0.002 n=6) name time/op time/op vs base BM_TransparentFind 2.625n ± 1% 2.418n ± 1% -7.87% (p=0.002 n=6) name INSTRUCTIONS/op INSTRUCTIONS/op vs base BM_TransparentFind 45.07 ± 0% 42.07 ± 0% -6.67% (p=0.002 n=6) name CYCLES/op CYCLES/op vs base BM_TransparentFind 9.229 ± 0% 8.492 ± 0% -7.98% (p=0.002 n=6) ``` PiperOrigin-RevId: 975251791 Change-Id: I7400e103167d707366f0be82dce627ab478959dd
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index ed97743..c4b82e3 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h
@@ -588,9 +588,9 @@ static size_t space_used(const T*) { return 0; } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { - return &TypeErasedApplyToSlotFn<Hash, T, kIsDefault, kSeedShift>; + return &TypeErasedApplyToSlotFn<Hash, T, kIsAbsl, kSeedShift>; } }; } // namespace container_internal
diff --git a/absl/container/flat_hash_set_test.cc b/absl/container/flat_hash_set_test.cc index c5878aa..6c99e8d 100644 --- a/absl/container/flat_hash_set_test.cc +++ b/absl/container/flat_hash_set_test.cc
@@ -389,14 +389,14 @@ 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, + EXPECT_EQ(HashtableDebugAccess<flat_hash_set<int>>::kIsAbslHash, true); + EXPECT_EQ(HashtableDebugAccess<flat_hash_set<std::string>>::kIsAbslHash, true); struct Hash { size_t operator()(size_t i) const { return i; } }; - EXPECT_EQ((HashtableDebugAccess<flat_hash_set<size_t, Hash>>::kIsDefaultHash), + EXPECT_EQ((HashtableDebugAccess<flat_hash_set<size_t, Hash>>::kIsAbslHash), false); }
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index fceb4eb..b03eb95 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -486,13 +486,13 @@ // Variadic arguments hash function that ignore the rest of the arguments. // Useful for usage with policy traits. -template <class Hash, bool kIsDefault, size_t kSeedShift> +template <class Hash, bool kIsAbsl, size_t kSeedShift> struct HashElement { HashElement(const Hash& h, size_t s) : hash(h), seed(s >> kSeedShift) {} template <class K, class... Args> size_t operator()(const K& key, Args&&...) const { - if constexpr (kIsDefault) { + if constexpr (kIsAbsl) { // 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. @@ -506,12 +506,12 @@ }; // No arguments function hash function for a specific key. -template <class Hash, class Key, bool kIsDefault, size_t kSeedShift> +template <class Hash, class Key, bool kIsAbsl, size_t kSeedShift> struct HashKey { HashKey(const Hash& h, const Key& k) : hash(h), key(k) {} size_t operator()(size_t seed) const { - return HashElement<Hash, kIsDefault, kSeedShift>{hash, seed}(key); + return HashElement<Hash, kIsAbsl, kSeedShift>{hash, seed}(key); } const Hash& hash; const Key& key; @@ -534,31 +534,31 @@ // 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, bool kIsDefault, size_t kSeedShift> +template <class Fn, class T, bool kIsAbsl, size_t kSeedShift> size_t TypeErasedApplyToSlotFn(const void* fn, void* slot, size_t seed) { const auto* f = static_cast<const Fn*>(fn); - return HashElement<Fn, kIsDefault, kSeedShift>{ + return HashElement<Fn, kIsAbsl, kSeedShift>{ *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, bool kIsDefault, size_t kSeedShift> +template <class Fn, class T, bool kIsAbsl, size_t kSeedShift> 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<T**>(slot_ptr); - return HashElement<Fn, kIsDefault, kSeedShift>{*f, seed}(*slot); + return HashElement<Fn, kIsAbsl, kSeedShift>{*f, seed}(*slot); } // Type erased function to apply `Fn` to data inside of the `slot_ptr->first`. // The data is expected to have type `T`. -template <class Fn, class T, bool kIsDefault, size_t kSeedShift> +template <class Fn, class T, bool kIsAbsl, size_t kSeedShift> size_t TypeErasedDerefAndApplyToSlotFirstFn(const void* fn, void* slot_ptr, size_t seed) { const auto* f = static_cast<const Fn*>(fn); const T* slot = *static_cast<T**>(slot_ptr); - return HashElement<Fn, kIsDefault, kSeedShift>{*f, seed}(slot->first); + return HashElement<Fn, kIsAbsl, kSeedShift>{*f, seed}(slot->first); } } // namespace container_internal
diff --git a/absl/container/internal/container_memory_test.cc b/absl/container/internal/container_memory_test.cc index 9ed387a..70fc0ea 100644 --- a/absl/container/internal/container_memory_test.cc +++ b/absl/container/internal/container_memory_test.cc
@@ -316,9 +316,9 @@ size_t x = 7; size_t seed = 100; auto fn = [](size_t v) { return v * 2; }; - EXPECT_EQ((TypeErasedApplyToSlotFn<decltype(fn), size_t, /*kIsDefault=*/false, + EXPECT_EQ((TypeErasedApplyToSlotFn<decltype(fn), size_t, /*kIsAbsl=*/false, /*kSeedShift=*/0>(&fn, &x, seed)), - (HashElement<decltype(fn), /*kIsDefault=*/false, /*kSeedShift=*/0>( + (HashElement<decltype(fn), /*kIsAbsl=*/false, /*kSeedShift=*/0>( fn, seed)(x))); } @@ -329,9 +329,9 @@ size_t* x_ptr = &x; EXPECT_EQ( (TypeErasedDerefAndApplyToSlotFn<decltype(fn), size_t, - /*kIsDefault=*/false, + /*kIsAbsl=*/false, /*kSeedShift=*/0>(&fn, &x_ptr, seed)), - (HashElement<decltype(fn), /*kIsDefault=*/false, /*kSeedShift=*/0>( + (HashElement<decltype(fn), /*kIsAbsl=*/false, /*kSeedShift=*/0>( fn, seed)(x))); } @@ -344,7 +344,7 @@ return v * 2 + seed * 3; } } hash; - EXPECT_EQ((HashElement<HashWithSeed, /*kIsDefault=*/true, + EXPECT_EQ((HashElement<HashWithSeed, /*kIsAbsl=*/true, /*kSeedShift=*/0>(hash, seed)(x)), hash.hash_with_seed(x, seed)); } @@ -354,7 +354,7 @@ size_t seed = 100; auto fn = [](size_t v) { return v * 2; }; EXPECT_EQ( - (HashElement<decltype(fn), /*kIsDefault=*/false, /*kSeedShift=*/0>( + (HashElement<decltype(fn), /*kIsAbsl=*/false, /*kSeedShift=*/0>( fn, seed)(x)), fn(x) ^ seed); } @@ -364,7 +364,7 @@ size_t seed = 100; auto fn = [](size_t v) { return v * 2; }; EXPECT_EQ( - (HashElement<decltype(fn), /*kIsDefault=*/false, /*kSeedShift=*/1>( + (HashElement<decltype(fn), /*kIsAbsl=*/false, /*kSeedShift=*/1>( fn, seed)(x)), fn(x) ^ (seed >> 1)); }
diff --git a/absl/container/internal/hash_policy_traits.h b/absl/container/internal/hash_policy_traits.h index beed150..e905995 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, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> 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,10 +155,10 @@ // 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, kIsDefault, kSeedShift>() == + return Policy::template get_hash_slot_fn<Hash, kIsAbsl, kSeedShift>() == nullptr - ? &hash_slot_fn_non_type_erased<Hash, kIsDefault, kSeedShift> - : Policy::template get_hash_slot_fn<Hash, kIsDefault, + ? &hash_slot_fn_non_type_erased<Hash, kIsAbsl, kSeedShift> + : Policy::template get_hash_slot_fn<Hash, kIsAbsl, kSeedShift>(); #if defined(__GNUC__) && !defined(__clang__) #pragma GCC diagnostic pop @@ -169,11 +169,11 @@ static constexpr bool soo_enabled() { return soo_enabled_impl(Rank1{}); } private: - template <class Hash, bool kIsDefault, size_t kSeedShift> + 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) { return Policy::apply( - HashElement<Hash, kIsDefault, kSeedShift>{ + HashElement<Hash, kIsAbsl, kSeedShift>{ *static_cast<const Hash*>(hash_fn), seed}, Policy::element(static_cast<slot_type*>(slot))); }
diff --git a/absl/container/internal/hash_policy_traits_test.cc b/absl/container/internal/hash_policy_traits_test.cc index 8d498e0..62ed9d5 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, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -99,7 +99,7 @@ return fn(v); } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> 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, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { - return &TypeErasedApplyToSlotFn<Hash, int, kIsDefault, kSeedShift>; + return &TypeErasedApplyToSlotFn<Hash, int, kIsAbsl, kSeedShift>; } }; @@ -121,10 +121,10 @@ Hash hasher; Slot value = 7; auto* fn = hash_policy_traits<PolicyNoHashFn>::get_hash_slot_fn< - Hash, /*kIsDefault=*/false, /*kSeedShift=*/6>(); + Hash, /*kIsAbsl=*/false, /*kSeedShift=*/6>(); EXPECT_NE(fn, nullptr); EXPECT_EQ(fn(&hasher, &value, 100), - (HashElement<Hash, /*kIsDefault=*/false, /*kSeedShift=*/6>( + (HashElement<Hash, /*kIsAbsl=*/false, /*kSeedShift=*/6>( hasher, 100)(value))); EXPECT_EQ(apply_called_count, 1); } @@ -136,12 +136,12 @@ Hash hasher; Slot value = 7; auto* fn = hash_policy_traits<PolicyCustomHashFn>::get_hash_slot_fn< - Hash, /*kIsDefault=*/false, /*kSeedShift=*/6>(); + Hash, /*kIsAbsl=*/false, /*kSeedShift=*/6>(); EXPECT_EQ(fn, - (PolicyCustomHashFn::get_hash_slot_fn<Hash, /*kIsDefault=*/false, + (PolicyCustomHashFn::get_hash_slot_fn<Hash, /*kIsAbsl=*/false, /*kSeedShift=*/6>())); EXPECT_EQ(fn(&hasher, &value, 100), - (HashElement<Hash, /*kIsDefault=*/false, /*kSeedShift=*/6>( + (HashElement<Hash, /*kIsAbsl=*/false, /*kSeedShift=*/6>( hasher, 100)(value))); EXPECT_EQ(apply_called_count, 0); }
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index d02af7e..2e63c10 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -322,6 +322,11 @@ std::declval<Ts>()...))>, Policy, Hash, Eq, Ts...> : std::true_type {}; +template <typename T, template <typename...> class Template> +struct is_instance_of : std::false_type {}; +template <template <typename...> class Template, typename... Args> +struct is_instance_of<Template<Args...>, Template> : std::true_type {}; + ABSL_DLL extern char kDefaultIterSlot; // Returns a pointer to a control byte that can be used by default-constructed @@ -2301,9 +2306,13 @@ using slot_type = typename PolicyTraits::slot_type; - constexpr static bool kIsDefaultHash = + constexpr static bool kIsAbslHash = std::is_same_v<hasher, absl::Hash<key_type>> || - std::is_same_v<hasher, absl::container_internal::StringHash>; + std::is_same_v<hasher, absl::container_internal::StringHash> || + // TODO(b/384509507): resolve `no header providing + // "absl::hash_internal::TransparentHash" is directly included`. + // Maybe we should make "internal/hash.h" be a separate library. + is_instance_of<hasher, absl::hash_internal::TransparentHash>::value; // For non-default hashers it is required to have low bits entropy because // (a) in such cases, the seed is xor'ed with the hash value rather than being // used as a seed for the hash function, (b) the seed has low bits that are @@ -2312,7 +2321,7 @@ // performance optimization for default hashers. For non-default hashers, we // shift it back. constexpr static size_t kSeedShift = - kIsDefaultHash ? 0 : HashtableInlineData::kCapacityBitStoredInDataCount; + kIsAbslHash ? 0 : HashtableInlineData::kCapacityBitStoredInDataCount; constexpr static bool SooEnabled() { return PolicyTraits::soo_enabled() && @@ -3538,12 +3547,12 @@ } template <class K> ABSL_ATTRIBUTE_ALWAYS_INLINE size_t hash_of(const K& key) const { - return HashElement<hasher, kIsDefaultHash, kSeedShift>{ + return HashElement<hasher, kIsAbslHash, kSeedShift>{ hash_ref(), common().seed().seed()}(key); } ABSL_ATTRIBUTE_ALWAYS_INLINE size_t hash_of(slot_type* slot) const { return PolicyTraits::apply( - HashElement<hasher, kIsDefaultHash, kSeedShift>{hash_ref(), + HashElement<hasher, kIsAbslHash, kSeedShift>{hash_ref(), common().seed().seed()}, PolicyTraits::element(slot)); } @@ -3685,7 +3694,7 @@ : 0, kUseMemcpy>( common(), GetPolicyFunctions(), - HashKey<hasher, K, kIsDefaultHash, kSeedShift>{hash_ref(), key}, + HashKey<hasher, K, kIsAbslHash, kSeedShift>{hash_ref(), key}, force_sampling)); return {slot, true}; } @@ -3705,7 +3714,7 @@ return { to_slot(PrepareInsertSmallNonSoo( common(), GetPolicyFunctions(), - HashKey<hasher, K, kIsDefaultHash, kSeedShift>{hash_ref(), key})), + HashKey<hasher, K, kIsAbslHash, kSeedShift>{hash_ref(), key})), true}; } @@ -3738,7 +3747,7 @@ ? PrepareInsertLargeGenerationsEnabled( common(), GetPolicyFunctions(), hash, mask_empty, FindInfo{target_group_offset, seq.index()}, - HashKey<hasher, K, kIsDefaultHash, kSeedShift>{ + HashKey<hasher, K, kIsAbslHash, kSeedShift>{ hash_ref(), key}) : PrepareInsertLarge( common(), GetPolicyFunctions(), hash, mask_empty, @@ -4041,7 +4050,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, kIsDefaultHash, + PolicyTraits::template get_hash_slot_fn<hasher, kIsAbslHash, kSeedShift>(), PolicyTraits::transfer_uses_memcpy() ? TransferNRelocatable<sizeof(slot_type)> @@ -4147,7 +4156,7 @@ using Traits = typename Set::PolicyTraits; using Slot = typename Traits::slot_type; - constexpr static bool kIsDefaultHash = Set::kIsDefaultHash; + constexpr static bool kIsAbslHash = Set::kIsAbslHash; static size_t GetNumProbes(const Set& set, const typename Set::key_type& key) {
diff --git a/absl/container/internal/raw_hash_set_benchmark.cc b/absl/container/internal/raw_hash_set_benchmark.cc index 58baabe..9ef43ea 100644 --- a/absl/container/internal/raw_hash_set_benchmark.cc +++ b/absl/container/internal/raw_hash_set_benchmark.cc
@@ -75,7 +75,7 @@ return std::forward<F>(f)(x, x); } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -142,7 +142,7 @@ PairArgs(std::forward<Args>(args)...)); } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -172,13 +172,14 @@ struct MyInt { int64_t value; + + template <typename H> + friend H AbslHashValue(H h, const MyInt& x) { + return H::combine(std::move(h), x.value); + } }; -struct TransparentIntHash { - using is_transparent = void; - size_t operator()(int64_t x) const { return absl::Hash<int64_t>{}(x); } - size_t operator()(MyInt x) const { return absl::Hash<int64_t>{}(x.value); } -}; +using TransparentIntHash = absl::TransparentHash<int64_t, MyInt>; struct TransparentIntEq { using is_transparent = void;
diff --git a/absl/container/internal/raw_hash_set_probe_benchmark.cc b/absl/container/internal/raw_hash_set_probe_benchmark.cc index fee9531..890e40e 100644 --- a/absl/container/internal/raw_hash_set_probe_benchmark.cc +++ b/absl/container/internal/raw_hash_set_probe_benchmark.cc
@@ -81,7 +81,7 @@ return std::forward<F>(f)(arg, arg); } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> 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 06a73bf..cc252b4 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1022,7 +1022,7 @@ std::forward<F>(f), std::forward<Args>(args)...); } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -1176,7 +1176,7 @@ PairArgs(std::forward<Args>(args)...)); } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -2808,6 +2808,11 @@ return *this; } + template <typename H> + friend H AbslHashValue(H h, const DecomposeType& d) { + return H::combine(std::move(h), d.i); + } + int i; }; @@ -2850,7 +2855,7 @@ return std::forward<F>(f)(x, x); } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { return nullptr; } @@ -3000,6 +3005,8 @@ TestDecompose<TransparentHashIntOverload, DecomposeEq>(true); TestDecompose<TransparentHashIntOverload, TransparentEqIntOverload>(true); TestDecompose<DecomposeHash, TransparentEqIntOverload>(true); + TestDecompose<absl::TransparentHash<DecomposeType, int>, + TransparentEqIntOverload>(true); } struct Modulo1000Hash {
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h index 75fc0cc..60013e3 100644 --- a/absl/container/node_hash_map.h +++ b/absl/container/node_hash_map.h
@@ -681,11 +681,11 @@ static Value& value(value_type* elem) { return elem->second; } static const Value& value(const value_type* elem) { return elem->second; } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { return memory_internal::IsLayoutCompatible<Key, Value>::value ? &TypeErasedDerefAndApplyToSlotFirstFn<Hash, value_type, - kIsDefault, kSeedShift> + kIsAbsl, kSeedShift> : nullptr; } };
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h index 9da52e7..95a270b 100644 --- a/absl/container/node_hash_set.h +++ b/absl/container/node_hash_set.h
@@ -582,9 +582,9 @@ static size_t element_space_used(const T*) { return sizeof(T); } - template <class Hash, bool kIsDefault, size_t kSeedShift> + template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { - return &TypeErasedDerefAndApplyToSlotFn<Hash, T, kIsDefault, kSeedShift>; + return &TypeErasedDerefAndApplyToSlotFn<Hash, T, kIsAbsl, kSeedShift>; } }; } // namespace container_internal
diff --git a/absl/hash/hash.h b/absl/hash/hash.h index 7a76771..bfccf27 100644 --- a/absl/hash/hash.h +++ b/absl/hash/hash.h
@@ -22,6 +22,8 @@ // * The `absl::Hash` functor, which is used to invoke the hasher within the // Abseil hashing framework. `absl::Hash<T>` supports most basic types and // a number of Abseil types out of the box. +// * The `absl::TransparentHash` functor, which provides transparent hashing +// for heterogeneous lookup across multiple types in associative containers. // * `AbslHashValue`, an extension point that allows you to extend types to // support Abseil hashing without requiring you to define a hashing // algorithm. @@ -255,6 +257,89 @@ template <typename T> using Hash = absl::hash_internal::Hash<T>; +// TransparentHash +// +// `absl::TransparentHash<Ts...>` is a transparent hash functor that provides +// heterogeneous hashing across multiple types `Ts...` for associative +// containers such as `absl::flat_hash_set` and `absl::flat_hash_map`. +// +// It exposes `operator()(const T&)` overloads for each type `T` in `Ts...`, +// delegating each call to `absl::Hash<T>{}(value)`. It also defines the nested +// type alias `using is_transparent = void;`, signaling to containers that +// heterogeneous lookup is supported. +// +// If any type in `Ts...` is not hashable within the `absl::Hash` framework, +// `absl::TransparentHash` is poisoned (its call operators are disabled) in the +// same manner as `absl::Hash`. +// +// Duplicates types are allowed in `Ts...`. +// +// Requirements: +// +// For heterogeneous lookup to be correct, equivalent values across different +// types must produce identical hash values. That is, if `a == b`, then +// `TransparentHash{}(a) == TransparentHash{}(b)` must hold. This is typically +// satisfied when the `AbslHashValue()` implementations for each type combine +// identical fields in the same order. +// +// Usage: +// +// `absl::TransparentHash` can be used in two ways: +// +// 1. As an explicit `Hash` template argument to a container: +// +// absl::flat_hash_set<Name, absl::TransparentHash<Name, NameView>, +// NameEq> set; +// +// 2. As the nested `absl_container_hash` type alias within a user-defined key +// type: +// +// struct Name { +// ... +// using absl_container_hash = absl::TransparentHash<Name, NameView>; +// }; +// +// When `absl_container_hash` is defined in the key type, Abseil hash +// containers will automatically use it and enable heterogeneous lookup by +// default (using `std::equal_to<void>` for equality if `absl_container_eq` +// is not provided). +// +// Example: +// +// struct NameView { +// absl::string_view first; +// absl::string_view last; +// +// template <typename H> +// friend H AbslHashValue(H h, const NameView& nv) { +// return H::combine(std::move(h), nv.first, nv.last); +// } +// friend bool operator==(const NameView& a, const NameView& b); +// }; +// +// struct Name { +// std::string first; +// std::string last; +// +// template <typename H> +// friend H AbslHashValue(H h, const Name& n) { +// return H::combine(std::move(h), n.first, n.last); +// } +// friend bool operator==(const Name& a, const Name& b); +// friend bool operator==(const Name& a, const NameView& b); +// +// using absl_container_hash = absl::TransparentHash<Name, NameView>; +// }; +// +// absl::flat_hash_set<Name> names; +// names.insert(Name{"John", "Doe"}); +// +// // Look up using `NameView` without constructing a temporary `Name` or +// // allocating memory: +// assert(names.contains(NameView{"John", "Doe"})); +template <typename... Ts> +using TransparentHash = absl::hash_internal::TransparentHash<Ts...>; + // HashOf // // absl::HashOf() is a helper that generates a hash from the values of its
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index d80ccb4..75e9756 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc
@@ -34,6 +34,7 @@ #include <tuple> #include <type_traits> #include <unordered_map> +#include <unordered_set> #include <utility> #include <variant> #include <vector> @@ -1352,4 +1353,110 @@ } } +struct NameView { + absl::string_view name; + absl::string_view lang; + + friend bool operator==(const NameView& lhs, const NameView& rhs) { + return lhs.name == rhs.name && lhs.lang == rhs.lang; + } + + template <typename H> + friend H AbslHashValue(H h, const NameView& name) { + return H::combine(std::move(h), name.name, name.lang); + } +}; + +struct Name { + std::string name; + std::string lang; + + friend bool operator==(const Name& lhs, const Name& rhs) { + return lhs.name == rhs.name && lhs.lang == rhs.lang; + } + friend bool operator==(const NameView& lhs, const Name& rhs) { + return lhs.name == rhs.name && lhs.lang == rhs.lang; + } + friend bool operator==(const Name& lhs, const NameView& rhs) { + return lhs.name == rhs.name && lhs.lang == rhs.lang; + } + + template <typename H> + friend H AbslHashValue(H h, const Name& name) { + return H::combine(std::move(h), name.name, name.lang); + } + + using absl_container_hash = absl::TransparentHash<NameView, Name>; +}; + +template <typename NameHash> +class TransparentHashTest : public testing::Test {}; + +using NameHashTypes = + testing::Types<absl::TransparentHash<Name, NameView>, + absl::TransparentHash<Name, Name, NameView>, + absl::TransparentHash<Name, NameView, Name>, + absl::TransparentHash<Name, NameView, Name, NameView>, + absl::TransparentHash<Name, NameView, Name, NameView, Name, + NameView, Name>>; +TYPED_TEST_SUITE(TransparentHashTest, NameHashTypes); + +TYPED_TEST(TransparentHashTest, BasicUsage) { + using NameHash = TypeParam; + static_assert(std::is_same_v<typename NameHash::is_transparent, void>); + + EXPECT_FALSE((std::is_convertible_v<NameHash, absl::Hash<Name>>)); + EXPECT_FALSE((std::is_convertible_v<NameHash, absl::Hash<NameView>>)); + + EXPECT_EQ(NameHash{}(Name{"foo", "en"}), NameHash{}(NameView{"foo", "en"})); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( + std::make_tuple(Name{"foo", "en"}, NameView{"foo", "en"}, + Name{"bar", "en"}, NameView{"bar", "en"}, + Name{"foo", "de"}, NameView{"foo", "de"}, + Name{"bar", "de"}, NameView{"bar", "de"}))); + + absl::flat_hash_set<Name, NameHash, std::equal_to<>> set; + set.insert(Name{"foo", "en"}); + EXPECT_TRUE(set.contains(NameView{"foo", "en"})); + EXPECT_TRUE(set.contains(Name{"foo", "en"})); + + std::unordered_set<Name, NameHash, std::equal_to<>> std_set; + std_set.insert(Name{"foo", "en"}); + EXPECT_TRUE(std_set.find(Name{"foo", "en"}) != std_set.end()); +} + +TEST(HashTest, TransparentHashDefaultLookUp) { + absl::flat_hash_set<Name> set; + set.insert(Name{"foo", "en"}); + EXPECT_TRUE(set.contains(NameView{"foo", "en"})); + EXPECT_TRUE(set.contains(Name{"foo", "en"})); +} + +struct Unhashable {}; + +template <typename Hasher> +class TransparentPoisonedHashTest : public testing::Test {}; + +using TransparentPoisonedHashTypes = + testing::Types<absl::TransparentHash<Unhashable>, + absl::TransparentHash<Unhashable, Unhashable>, + absl::TransparentHash<int, Unhashable>, + absl::TransparentHash<int, Unhashable, int>, + absl::TransparentHash<int, Unhashable, int, Unhashable>>; +TYPED_TEST_SUITE(TransparentPoisonedHashTest, TransparentPoisonedHashTypes); + +TYPED_TEST(TransparentPoisonedHashTest, PoisonHash) { + using Hasher = TypeParam; + EXPECT_FALSE(std::is_default_constructible_v<Hasher>); + EXPECT_FALSE(std::is_copy_constructible_v<Hasher>); + EXPECT_FALSE(std::is_move_constructible_v<Hasher>); + EXPECT_FALSE(std::is_copy_assignable_v<Hasher>); + EXPECT_FALSE(std::is_move_assignable_v<Hasher>); +#if !defined(__GNUC__) || defined(__clang__) + // TODO(b/144368551): As of GCC 8.4 this does not compile. + EXPECT_FALSE(IsAggregateInitializable<Hasher>::value); +#endif +} + } // namespace
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index a7dc74c..fdee6f7 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h
@@ -1569,6 +1569,7 @@ PoisonedHash() = delete; PoisonedHash(const PoisonedHash&) = delete; PoisonedHash& operator=(const PoisonedHash&) = delete; + void operator()() const = delete; }; template <typename T> @@ -1578,7 +1579,7 @@ } private: - friend struct HashWithSeed; + friend HashWithSeed; size_t hash_with_seed(const T& value, size_t seed) const { return MixingHashState::hash_with_seed(value, seed); @@ -1589,6 +1590,57 @@ struct Hash : std::conditional_t<is_hashable<T>::value, HashImpl<T>, PoisonedHash> {}; +template <typename T, typename... Ts> +inline constexpr bool pack_contains_v = (std::is_same_v<T, Ts> || ...); + +template <size_t> +struct EmptyDuplicatedHash { + void operator()() const = delete; +}; + +template <typename... Ts> +class TransparentHashImpl; + +template <typename T> +class TransparentHashImpl<T> : private Hash<T> { + public: + using Hash<T>::operator(); +}; + +template <typename T, typename... Ts> +using TransparentHashImplSingle = + std::conditional_t<pack_contains_v<T, Ts...>, + EmptyDuplicatedHash<sizeof...(Ts)>, Hash<T>>; + +template <typename T, typename... Ts> +class TransparentHashImpl<T, Ts...> + : private TransparentHashImpl<Ts...>, + private TransparentHashImplSingle<T, Ts...> { + public: + using TransparentHashImpl<Ts...>::operator(); + using TransparentHashImplSingle<T, Ts...>::operator(); +}; + +template <typename... Ts> +using TransparentHashBase = + std::conditional_t<(... && is_hashable<Ts>::value), + TransparentHashImpl<Ts...>, PoisonedHash>; + +template <typename... Ts> +class TransparentHash : private TransparentHashBase<Ts...> { + public: + using is_transparent = void; + using TransparentHashBase<Ts...>::operator(); + + private: + friend HashWithSeed; + + template <typename T> + size_t hash_with_seed(const T& value, size_t seed) const { + return MixingHashState::hash_with_seed(value, seed); + } +}; + template <typename H> template <typename T, typename... Ts> H HashStateBase<H>::combine(H state, const T& value, const Ts&... values) {