Deduplicate type-erased SwissTable slot hashing for types with identical hash implementations. Uniquely represented types of the same size and raw pointers all hash their raw bytes in the exact same way, but SwissTable previously instantiated a separate type-erased slot hashing function for each distinct key type. Introduce a canonical hasher base class in absl::hash_internal so that types with identical byte-level hashing share a single type-erased slot hash function across containers. PiperOrigin-RevId: 1011160515
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 4bb6fec..7d74f26 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -460,6 +460,7 @@ "//absl/base:config", "//absl/base:no_destructor", "//absl/functional:overload", + "//absl/hash", "//absl/meta:type_traits", "//absl/strings:string_view", "@googletest//:gtest",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 903b308..c249378 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -508,6 +508,7 @@ DEPS absl::config absl::container_memory + absl::hash absl::no_destructor absl::overload absl::string_view
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h index fa91949..40d44e2 100644 --- a/absl/container/flat_hash_map.h +++ b/absl/container/flat_hash_map.h
@@ -707,7 +707,7 @@ template <class Hash, bool kIsDefault, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { return memory_internal::IsLayoutCompatible<K, V>::value - ? &TypeErasedApplyToSlotFn<Hash, K, kIsDefault, kSeedShift> + ? GetTypeErasedApplyToSlotFn<Hash, K, kIsDefault, kSeedShift>() : nullptr; }
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index b0527b3..436c525 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h
@@ -591,7 +591,7 @@ template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { - return &TypeErasedApplyToSlotFn<Hash, T, kIsAbsl, kSeedShift>; + return GetTypeErasedApplyToSlotFn<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 df448a1..eeff02e 100644 --- a/absl/container/flat_hash_set_test.cc +++ b/absl/container/flat_hash_set_test.cc
@@ -408,6 +408,26 @@ }; EXPECT_EQ((HashtableDebugAccess<flat_hash_set<size_t, Hash>>::kIsAbslHash), false); + + struct DerivedHash : absl::Hash<int> { + size_t operator()(int i) const { return absl::Hash<int>::operator()(-i); } + }; + EXPECT_EQ( + (HashtableDebugAccess<flat_hash_set<int, DerivedHash>>::kIsAbslHash), + false); +} + +TEST(FlatHashSet, DerivedFromAbslHashCallsDerivedOperator) { + struct DerivedHash : absl::Hash<int> { + size_t operator()(int i) const { return absl::Hash<int>::operator()(-i); } + }; + flat_hash_set<int, DerivedHash> s; + for (int i = 0; i < 100; ++i) { + s.insert(i); + } + for (int i = 0; i < 100; ++i) { + EXPECT_TRUE(s.contains(i)); + } } #if defined(__cpp_lib_containers_ranges) && \
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index 8e0653a..7638bfa 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -633,6 +633,29 @@ *f, seed}(*static_cast<const T*>(slot)); } +// Type erased function to apply `CanonicalHasher` to data inside of the `slot`. +template <class CanonicalHasher> +size_t TypeErasedApplyAbslHashToSlotFn(const void*, void* slot, size_t seed) { + using T = typename CanonicalHasher::KeyType; + return absl::hash_internal::HashWithSeed().hash( + CanonicalHasher(), *static_cast<const T*>(slot), seed); +} + +template <class Fn, class T, bool kIsAbsl, size_t kSeedShift> +constexpr HashSlotFn GetTypeErasedApplyToSlotFn() { + using NonConstT = std::remove_const_t<T>; + // Use the canonical `absl::Hash<NonConstT>` implementation when `Fn` is + // `absl::Hash<NonConstT>` or a transparent hasher (such as `StringHash`, + // `BasicStringHash`, `HashEq<T*>::Hash`, or `TransparentHash`) that inherits + // from `absl::Hash<NonConstT>` and hashes `NonConstT` identically. + if constexpr (kIsAbsl && std::is_base_of_v<absl::Hash<NonConstT>, Fn>) { + return &TypeErasedApplyAbslHashToSlotFn< + decltype(absl::hash_internal::CanonicalHasher( + absl::Hash<NonConstT>()))>; + } + return &TypeErasedApplyToSlotFn<Fn, NonConstT, kIsAbsl, kSeedShift>; +} + // 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 kIsAbsl, size_t kSeedShift> @@ -650,6 +673,31 @@ return HashElement<Fn, kIsAbsl, kSeedShift>{*f, seed}(*slot); } +// Type erased function to apply `CanonicalHasher` to data inside of the +// `*slot_ptr`. +template <class CanonicalHasher> +size_t TypeErasedDerefAndApplyAbslHashToSlotFn(const void*, void* slot_ptr, + size_t seed) { + using T = typename CanonicalHasher::KeyType; + const T* slot; + // See comment in `TypeErasedDerefAndApplyToSlotFn`. + std::memcpy(&slot, slot_ptr, sizeof(slot)); + return absl::hash_internal::HashWithSeed().hash(CanonicalHasher(), *slot, + seed); +} + +template <class Fn, class T, bool kIsAbsl, size_t kSeedShift> +constexpr HashSlotFn GetTypeErasedDerefAndApplyToSlotFn() { + using NonConstT = std::remove_const_t<T>; + // See comment in `GetTypeErasedApplyToSlotFn`. + if constexpr (kIsAbsl && std::is_base_of_v<absl::Hash<NonConstT>, Fn>) { + return &TypeErasedDerefAndApplyAbslHashToSlotFn< + decltype(absl::hash_internal::CanonicalHasher( + absl::Hash<NonConstT>()))>; + } + return &TypeErasedDerefAndApplyToSlotFn<Fn, NonConstT, kIsAbsl, kSeedShift>; +} + } // namespace container_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/container/internal/container_memory_test.cc b/absl/container/internal/container_memory_test.cc index f6fdd5c..438e713 100644 --- a/absl/container/internal/container_memory_test.cc +++ b/absl/container/internal/container_memory_test.cc
@@ -31,6 +31,7 @@ #include "absl/base/no_destructor.h" #include "absl/container/internal/test_instance_tracker.h" #include "absl/functional/overload.h" +#include "absl/hash/hash.h" #include "absl/meta/type_traits.h" #include "absl/strings/string_view.h" @@ -329,6 +330,77 @@ fn, seed)(x))); } +TEST(ApplyTest, GetTypeErasedApplyToSlotFnCanonicalizesTypes) { + enum class MyEnum : uint32_t { kOne = 1, kTwo = 2 }; + int32_t a = 1; + uint32_t b = 2; + MyEnum c = MyEnum::kTwo; + int* a_ptr = &a; + uint32_t* b_ptr = &b; + size_t seed = 100; + HashSlotFn fn_int32 = + GetTypeErasedApplyToSlotFn<absl::Hash<int32_t>, int32_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_uint32 = + GetTypeErasedApplyToSlotFn<absl::Hash<uint32_t>, uint32_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_enum = + GetTypeErasedApplyToSlotFn<absl::Hash<MyEnum>, MyEnum, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_uintptr = + GetTypeErasedApplyToSlotFn<absl::Hash<uintptr_t>, uintptr_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_int_ptr = + GetTypeErasedApplyToSlotFn<absl::Hash<int*>, int*, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_uint32_ptr = + GetTypeErasedApplyToSlotFn<absl::Hash<uint32_t*>, uint32_t*, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_transparent_int32 = GetTypeErasedApplyToSlotFn< + absl::TransparentHash<int32_t, int64_t>, int32_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_transparent_converted = + GetTypeErasedApplyToSlotFn<absl::TransparentHash<int64_t>, int32_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + struct DerivedHash : absl::Hash<int32_t> { + size_t operator()(int32_t v) const { return static_cast<size_t>(v + 42); } + } derived_hash; + HashSlotFn fn_derived = + GetTypeErasedApplyToSlotFn<DerivedHash, int32_t, + /*kIsAbsl=*/false, /*kSeedShift=*/0>(); + EXPECT_EQ(fn_int32, fn_uint32); + EXPECT_EQ(fn_int32, fn_enum); + EXPECT_EQ(fn_int32, fn_transparent_int32); + EXPECT_NE(fn_int32, fn_transparent_converted); + EXPECT_NE(fn_int32, fn_derived); + EXPECT_EQ(fn_uintptr, fn_int_ptr); + EXPECT_EQ(fn_int_ptr, fn_uint32_ptr); + EXPECT_EQ( + fn_derived(&derived_hash, &a, seed), + (HashElement<DerivedHash, /*kIsAbsl=*/false, /*kSeedShift=*/0>( + derived_hash, seed)(a))); + EXPECT_EQ( + fn_int32(nullptr, &a, seed), + (HashElement<absl::Hash<int32_t>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<int32_t>{}, seed)(a))); + EXPECT_EQ( + fn_uint32(nullptr, &b, seed), + (HashElement<absl::Hash<uint32_t>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<uint32_t>{}, seed)(b))); + EXPECT_EQ( + fn_enum(nullptr, &c, seed), + (HashElement<absl::Hash<MyEnum>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<MyEnum>{}, seed)(c))); + EXPECT_EQ( + fn_int_ptr(nullptr, &a_ptr, seed), + (HashElement<absl::Hash<int*>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<int*>{}, seed)(a_ptr))); + EXPECT_EQ( + fn_uint32_ptr(nullptr, &b_ptr, seed), + (HashElement<absl::Hash<uint32_t*>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<uint32_t*>{}, seed)(b_ptr))); +} + TEST(ApplyTest, TypeErasedDerefAndApplyToSlotFn) { size_t x = 7; size_t seed = 100; @@ -342,6 +414,80 @@ fn, seed)(x))); } +TEST(ApplyTest, GetTypeErasedDerefAndApplyToSlotFnCanonicalizesTypes) { + enum class MyEnum : uint32_t { kOne = 1, kTwo = 2 }; + int32_t a = 1; + uint32_t b = 2; + MyEnum c = MyEnum::kTwo; + int32_t* a_ptr = &a; + uint32_t* b_ptr = &b; + MyEnum* c_ptr = &c; + int32_t** a_ptr_ptr = &a_ptr; + uint32_t** b_ptr_ptr = &b_ptr; + size_t seed = 100; + HashSlotFn fn_int32 = + GetTypeErasedDerefAndApplyToSlotFn<absl::Hash<int32_t>, int32_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_uint32 = + GetTypeErasedDerefAndApplyToSlotFn<absl::Hash<uint32_t>, uint32_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_enum = + GetTypeErasedDerefAndApplyToSlotFn<absl::Hash<MyEnum>, MyEnum, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_uintptr = + GetTypeErasedDerefAndApplyToSlotFn<absl::Hash<uintptr_t>, uintptr_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_int_ptr = + GetTypeErasedDerefAndApplyToSlotFn<absl::Hash<int32_t*>, int32_t*, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_uint32_ptr = + GetTypeErasedDerefAndApplyToSlotFn<absl::Hash<uint32_t*>, uint32_t*, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_transparent_int32 = GetTypeErasedDerefAndApplyToSlotFn< + absl::TransparentHash<int32_t, int64_t>, int32_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + HashSlotFn fn_transparent_converted = GetTypeErasedDerefAndApplyToSlotFn< + absl::TransparentHash<int64_t>, int32_t, + /*kIsAbsl=*/true, /*kSeedShift=*/0>(); + struct DerivedHash : absl::Hash<int32_t> { + size_t operator()(int32_t v) const { return static_cast<size_t>(v + 42); } + } derived_hash; + HashSlotFn fn_derived = + GetTypeErasedDerefAndApplyToSlotFn<DerivedHash, int32_t, + /*kIsAbsl=*/false, /*kSeedShift=*/0>(); + EXPECT_EQ(fn_int32, fn_uint32); + EXPECT_EQ(fn_int32, fn_enum); + EXPECT_EQ(fn_int32, fn_transparent_int32); + EXPECT_NE(fn_int32, fn_transparent_converted); + EXPECT_NE(fn_int32, fn_derived); + EXPECT_EQ(fn_uintptr, fn_int_ptr); + EXPECT_EQ(fn_int_ptr, fn_uint32_ptr); + EXPECT_EQ( + fn_derived(&derived_hash, &a_ptr, seed), + (HashElement<DerivedHash, /*kIsAbsl=*/false, /*kSeedShift=*/0>( + derived_hash, seed)(a))); + EXPECT_EQ( + fn_int32(nullptr, &a_ptr, seed), + (HashElement<absl::Hash<int32_t>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<int32_t>{}, seed)(a))); + EXPECT_EQ( + fn_uint32(nullptr, &b_ptr, seed), + (HashElement<absl::Hash<uint32_t>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<uint32_t>{}, seed)(b))); + EXPECT_EQ( + fn_enum(nullptr, &c_ptr, seed), + (HashElement<absl::Hash<MyEnum>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<MyEnum>{}, seed)(c))); + EXPECT_EQ( + fn_int_ptr(nullptr, &a_ptr_ptr, seed), + (HashElement<absl::Hash<int32_t*>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<int32_t*>{}, seed)(a_ptr))); + EXPECT_EQ( + fn_uint32_ptr(nullptr, &b_ptr_ptr, seed), + (HashElement<absl::Hash<uint32_t*>, /*kIsAbsl=*/true, /*kSeedShift=*/0>( + absl::Hash<uint32_t*>{}, seed)(b_ptr))); +} + TEST(HashElement, DefaultHash) { size_t x = 7; size_t seed = 100;
diff --git a/absl/container/internal/hash_function_defaults.h b/absl/container/internal/hash_function_defaults.h index 6db9e57..3b568a6 100644 --- a/absl/container/internal/hash_function_defaults.h +++ b/absl/container/internal/hash_function_defaults.h
@@ -45,12 +45,12 @@ #ifndef ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_ #define ABSL_CONTAINER_INTERNAL_HASH_FUNCTION_DEFAULTS_H_ -#include <cstddef> #include <functional> #include <memory> #include <string> #include <string_view> #include <type_traits> +#include <utility> #include "absl/base/config.h" #include "absl/container/internal/common.h" @@ -70,27 +70,18 @@ using Eq = std::equal_to<T>; }; -struct StringHash { +struct StringHash : private absl::Hash<absl::string_view>, + private absl::Hash<std::string>, + private absl::Hash<absl::Cord> { using is_transparent = void; - - size_t operator()(absl::string_view v) const { - return absl::Hash<absl::string_view>{}(v); - } - size_t operator()(const absl::Cord& v) const { - return absl::Hash<absl::Cord>{}(v); - } + using absl::Hash<absl::string_view>::operator(); + using absl::Hash<absl::Cord>::operator(); 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); - } + using absl::Hash<absl::string_view>::hash_with_seed; + using absl::Hash<absl::Cord>::hash_with_seed; }; struct StringEq { @@ -123,20 +114,15 @@ struct HashEq<absl::Cord> : StringHashEq {}; template <typename TChar> -struct BasicStringHash { +struct BasicStringHash : private absl::Hash<std::basic_string_view<TChar>>, + private absl::Hash<std::basic_string<TChar>> { using is_transparent = void; - - size_t operator()(std::basic_string_view<TChar> v) const { - return absl::Hash<std::basic_string_view<TChar>>{}(v); - } + using absl::Hash<std::basic_string_view<TChar>>::operator(); private: friend struct absl::hash_internal::HashWithSeed; - size_t hash_with_seed(std::basic_string_view<TChar> v, size_t seed) const { - return absl::hash_internal::HashWithSeed().hash( - absl::Hash<std::basic_string_view<TChar>>{}, v, seed); - } + using absl::Hash<std::basic_string_view<TChar>>::hash_with_seed; }; template <typename TChar> @@ -177,40 +163,48 @@ // Supports heterogeneous lookup for pointers and smart pointers. template <class T> struct HashEq<T*> { - struct Hash { - using is_transparent = void; - template <class U> - size_t operator()(const U& ptr) const { - return absl::Hash<const T*>{}(HashEq::ToPtr(ptr)); + private: + struct Ptr { + Ptr(const T* p) : ptr(p) {} // NOLINT + template <class U, + std::enable_if_t<std::is_convertible_v<const U&, const T*> && + !std::is_convertible_v<const U&, T*>, + int> = 0> + Ptr(const U& p) : ptr(p) {} // NOLINT + template <class U, class D, + std::enable_if_t<std::is_convertible_v<U*, const T*>, int> = 0> + Ptr(const std::unique_ptr<U, D>& p) : ptr(p.get()) {} // NOLINT + template <class U, + std::enable_if_t<std::is_convertible_v<U*, const T*>, int> = 0> + Ptr(const std::shared_ptr<U>& p) : ptr(p.get()) {} // NOLINT + + template <typename H> + friend H AbslHashValue(H h, Ptr p) { + return H::combine(std::move(h), p.ptr); } + const T* ptr; + }; + + public: + struct Hash : private absl::Hash<T*>, private absl::Hash<Ptr> { + using is_transparent = void; + using absl::Hash<T*>::operator(); + using absl::Hash<Ptr>::operator(); + private: friend struct absl::hash_internal::HashWithSeed; - template <class U> - size_t hash_with_seed(const U& ptr, size_t seed) const { - return absl::hash_internal::HashWithSeed().hash(absl::Hash<const T*>{}, - HashEq::ToPtr(ptr), seed); - } + using absl::Hash<T*>::hash_with_seed; + using absl::Hash<Ptr>::hash_with_seed; }; struct Eq { using is_transparent = void; template <class A, class B> bool operator()(const A& a, const B& b) const { - return HashEq::ToPtr(a) == HashEq::ToPtr(b); + return Ptr(a).ptr == Ptr(b).ptr; } }; - - private: - static const T* ToPtr(const T* ptr) { return ptr; } - template <class U, class D> - static const T* ToPtr(const std::unique_ptr<U, D>& ptr) { - return ptr.get(); - } - template <class U> - static const T* ToPtr(const std::shared_ptr<U>& ptr) { - return ptr.get(); - } }; template <class T, class D>
diff --git a/absl/container/internal/hash_function_defaults_test.cc b/absl/container/internal/hash_function_defaults_test.cc index 64a5a04..1d0c383 100644 --- a/absl/container/internal/hash_function_defaults_test.cc +++ b/absl/container/internal/hash_function_defaults_test.cc
@@ -23,6 +23,7 @@ #include <string_view> #include <type_traits> #include <utility> +#include <variant> #include <vector> #include "gtest/gtest.h" @@ -282,6 +283,16 @@ void operator()(const T* ptr) const {} }; +struct ConvertibleToPtr { + int* ptr; + operator int*() const { return ptr; } // NOLINT +}; + +struct ConvertibleToConstPtr { + const int* ptr; + operator const int*() const { return ptr; } // NOLINT +}; + using PointerTypes = ::testing::Types<const int*, int*, std::unique_ptr<const int>, std::unique_ptr<const int, NoDeleter>, @@ -317,11 +328,15 @@ EXPECT_TRUE(eq(ptr, uptr)); EXPECT_TRUE(eq(ptr, csptr)); EXPECT_TRUE(eq(ptr, cuptr)); + EXPECT_TRUE(eq(ptr, ConvertibleToPtr{ptr})); + EXPECT_TRUE(eq(ptr, ConvertibleToConstPtr{ptr})); EXPECT_FALSE(eq(&dummy, cptr)); EXPECT_FALSE(eq(&dummy, sptr)); EXPECT_FALSE(eq(&dummy, uptr)); EXPECT_FALSE(eq(&dummy, csptr)); EXPECT_FALSE(eq(&dummy, cuptr)); + EXPECT_FALSE(eq(&dummy, ConvertibleToPtr{ptr})); + EXPECT_FALSE(eq(&dummy, ConvertibleToConstPtr{ptr})); } TEST(Hash, DerivedAndBase) { @@ -352,6 +367,16 @@ EXPECT_FALSE(eq(p1, p2)); } +TEST(Hash, PointerToTemplateWithIncompleteType) { + struct Incomplete; + using VariantPtr = const std::variant<Incomplete>*; + hash_default_hash<VariantPtr> hasher; + hash_default_eq<VariantPtr> eq; + VariantPtr p = nullptr; + EXPECT_EQ(hasher(p), hasher(nullptr)); + EXPECT_TRUE(eq(p, nullptr)); +} + TYPED_TEST(HashPointer, Works) { int dummy; auto hash = this->hasher; @@ -367,11 +392,15 @@ EXPECT_EQ(hash(ptr), hash(uptr)); EXPECT_EQ(hash(ptr), hash(csptr)); EXPECT_EQ(hash(ptr), hash(cuptr)); + EXPECT_EQ(hash(ptr), hash(ConvertibleToPtr{ptr})); + EXPECT_EQ(hash(ptr), hash(ConvertibleToConstPtr{ptr})); EXPECT_NE(hash(&dummy), hash(cptr)); EXPECT_NE(hash(&dummy), hash(sptr)); EXPECT_NE(hash(&dummy), hash(uptr)); EXPECT_NE(hash(&dummy), hash(csptr)); EXPECT_NE(hash(&dummy), hash(cuptr)); + EXPECT_NE(hash(&dummy), hash(ConvertibleToPtr{ptr})); + EXPECT_NE(hash(&dummy), hash(ConvertibleToConstPtr{ptr})); } TEST(EqCord, Works) {
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h index 28acb74..61f2b52 100644 --- a/absl/container/node_hash_map.h +++ b/absl/container/node_hash_map.h
@@ -685,8 +685,8 @@ template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { return memory_internal::IsLayoutCompatible<Key, Value>::value - ? &TypeErasedDerefAndApplyToSlotFn<Hash, Key, kIsAbsl, - kSeedShift> + ? GetTypeErasedDerefAndApplyToSlotFn<Hash, Key, kIsAbsl, + kSeedShift>() : nullptr; } };
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h index 7265029..5acd059 100644 --- a/absl/container/node_hash_set.h +++ b/absl/container/node_hash_set.h
@@ -585,7 +585,7 @@ template <class Hash, bool kIsAbsl, size_t kSeedShift> static constexpr HashSlotFn get_hash_slot_fn() { - return &TypeErasedDerefAndApplyToSlotFn<Hash, T, kIsAbsl, kSeedShift>; + return GetTypeErasedDerefAndApplyToSlotFn<Hash, T, kIsAbsl, kSeedShift>(); } }; } // namespace container_internal
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index e42e1a0..cb1e0bc 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc
@@ -1121,6 +1121,39 @@ EXPECT_FALSE(is_uniquely_represented<int*>::value); } +TEST(CanonicalHasherTest, UniquelyRepresentedAndPointerTypesShareBaseClass) { + using absl::hash_internal::CanonicalHasher; + enum class Enum32 : uint32_t { kA = 1 }; + enum class SignedEnum32 : int32_t { kA = -1 }; + + using CanonicalInt32 = decltype(CanonicalHasher(absl::Hash<int32_t>())); + using CanonicalUint32 = decltype(CanonicalHasher(absl::Hash<uint32_t>())); + using CanonicalEnum32 = decltype(CanonicalHasher(absl::Hash<Enum32>())); + using CanonicalSignedEnum32 = + decltype(CanonicalHasher(absl::Hash<SignedEnum32>())); + using CanonicalUintptr = decltype(CanonicalHasher(absl::Hash<uintptr_t>())); + using CanonicalIntPtr = decltype(CanonicalHasher(absl::Hash<int*>())); + using CanonicalDoublePtr = decltype(CanonicalHasher(absl::Hash<double*>())); + using CanonicalConstIntPtr = + decltype(CanonicalHasher(absl::Hash<const int*>())); + using CanonicalString = decltype(CanonicalHasher(absl::Hash<std::string>())); + + EXPECT_TRUE((std::is_same_v<CanonicalInt32, CanonicalUint32>)); + EXPECT_TRUE((std::is_same_v<CanonicalInt32, CanonicalEnum32>)); + EXPECT_TRUE((std::is_same_v<CanonicalInt32, CanonicalSignedEnum32>)); + EXPECT_TRUE((std::is_same_v<CanonicalUintptr, CanonicalIntPtr>)); + EXPECT_TRUE((std::is_same_v<CanonicalIntPtr, CanonicalDoublePtr>)); + EXPECT_TRUE((std::is_same_v<CanonicalIntPtr, CanonicalConstIntPtr>)); + EXPECT_FALSE((std::is_same_v<CanonicalInt32, CanonicalString>)); + + EXPECT_TRUE((std::is_base_of_v<CanonicalInt32, absl::Hash<int32_t>>)); + EXPECT_TRUE((std::is_base_of_v<CanonicalInt32, absl::Hash<uint32_t>>)); + EXPECT_TRUE((std::is_base_of_v<CanonicalInt32, absl::Hash<Enum32>>)); + EXPECT_TRUE((std::is_base_of_v<CanonicalIntPtr, absl::Hash<int*>>)); + EXPECT_TRUE((std::is_base_of_v<CanonicalIntPtr, absl::Hash<double*>>)); + EXPECT_TRUE((std::is_base_of_v<CanonicalString, absl::Hash<std::string>>)); +} + struct IntAndString { int i; std::string s;
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index b30260d..e6eac27 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h
@@ -1427,7 +1427,8 @@ static auto Apply() { if constexpr (std::is_same_v<T, WeaklyMixedInteger>) { return WeaklyMixedIntegerProbe(); - } else if constexpr (is_uniquely_represented<T>::value) { + } else if constexpr (is_uniquely_represented<T>::value || + std::is_pointer_v<T>) { return UniquelyRepresentedProbe(); } else if constexpr (std::is_same_v<State, typename AbslHashValueResultOrVoid< @@ -1601,8 +1602,42 @@ size_t hash_with_seed() const = delete; }; +// Canonical byte-array representation for types of size `N` whose hash depends +// only on their raw bytes. +template <size_t N> +struct SameSizeUniquelyRepresented { + unsigned char bytes[N]; +}; + +template <size_t N> +struct is_uniquely_represented<SameSizeUniquelyRepresented<N>> + : std::true_type {}; + +// Maps `T` to a canonical type when multiple types share the exact same hash +// implementation. `is_uniquely_represented<T>` types and raw pointers `T*` +// (which are hashed as `uintptr_t`) both hash their raw bytes, so they map to +// `SameSizeUniquelyRepresented<sizeof(T)>`. +// A partial specialization is used instead of `std::conditional_t` to avoid +// evaluating `sizeof(T)` when `Hash<T>` is instantiated with an incomplete +// type (such as a recursive struct containing a hash table of itself). +template <typename T, + bool = is_uniquely_represented<T>::value || std::is_pointer_v<T>> +struct CanonicalHashTypeImpl { + using type = T; +}; + template <typename T> -struct HashImpl { +struct CanonicalHashTypeImpl<T, true> { + using type = SameSizeUniquelyRepresented<sizeof(T)>; +}; + +template <typename T> +using CanonicalHashType = typename CanonicalHashTypeImpl<T>::type; + +template <typename T> +struct CanonicalHashImpl { + using KeyType = T; + size_t operator()(const T& value) const { return MixingHashState::hash(value); } @@ -1615,6 +1650,34 @@ } }; +// Base class for `absl::Hash<T>` when `T` is hashable. Inherits from the +// canonical `CanonicalHashImpl<CanonicalHashType<T>>` so `CanonicalHasher()` +// can slice `absl::Hash<T>` to its unique `CanonicalHashImpl` base class, while +// defining `operator()` and `hash_with_seed` for `const T&` directly so +// arguments are implicitly converted to `T` before hashing. +template <typename T> +struct HashImpl : CanonicalHashImpl<CanonicalHashType<T>> { + size_t operator()(const T& value) const { + return MixingHashState::hash(value); + } + + protected: + friend HashWithSeed; + + size_t hash_with_seed(const T& value, size_t seed) const { + return MixingHashState::hash_with_seed(value, seed); + } +}; + +// Returns a canonical hasher by slicing `hasher` to its `CanonicalHashImpl` +// base class. This is useful for type erasure of types with the exact same +// hash function. +template <typename T> +constexpr CanonicalHashImpl<T> CanonicalHasher( + const CanonicalHashImpl<T>& hasher) { + return hasher; +} + template <typename T> struct Hash : std::conditional_t<is_hashable<T>::value, HashImpl<T>, PoisonedHash> {};