summaryrefslogtreecommitdiff
path: root/absl/hash/hash_test.cc
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2019-01-30 10:59:43 -0800
committerGravatar Ashley Hedberg <ahedberg@google.com>2019-01-30 14:24:09 -0500
commita4cb1c8ba61531a63f9d309eea01ac1d43d8371d (patch)
tree4cd407a27c50ef86e2644af93f117cf5eb2b7bd3 /absl/hash/hash_test.cc
parent540e2537b92cd4abfae6ceddfe24304345461f32 (diff)
Export of internal Abseil changes.
-- 6fdf24a197b964f9bacbebd0ceca305aef1654fc by Shaindel Schwartz <shaindel@google.com>: Internal change PiperOrigin-RevId: 231627312 -- 65f7faf52bff01384171efb85fee159378dedf70 by CJ Johnson <johnsoncj@google.com>: Relocates the definitions of the InputIterator-accepting parts of the InlinedVector API into the top-level. The removed functions had no other callers so there was no reason to keep the layer of indirection in the form of the function call. PiperOrigin-RevId: 231527459 -- 30e105b749b5ecc50fdaf26c7da589617efce425 by CJ Johnson <johnsoncj@google.com>: Relocates closing brace for absl namespace in InlinedVector to the correct end location PiperOrigin-RevId: 231477871 -- 063c1e8b9d1f032662c46d574e20ecc357b87d0c by Eric Fiselier <ericwf@google.com>: Cleanup std::hash probing metafunctions. Previously there were two different ways to probe for std::hash. One in hash.h and another in type_traits.h, and they were both implemented differently, and neither correctly worked around bad STL implementations. This patch unifies the implementations into a single IsHashable trait. It also: * Correctly checks for old libc++ versions where this won't work. * Avoids undefined behavior which resulted from calling std::is_constructible incomplete types. * Unifies the feature test macro used in the headers and the tests. Additionally it also slightly changes the behavior of when absl::variant is hashable. Previously we disable hashing when std::hash<T>()(key) was formed but when std::hash<T> couldn't be destructed. This seems wrong. If a user provides a evil specialization of std::hash, then it's OK for variant's hash to blow up. PiperOrigin-RevId: 231468345 -- 05d75dd4b07c893de9b104731644d0d207b01253 by Abseil Team <absl-team@google.com>: Import of CCTZ from GitHub. PiperOrigin-RevId: 231397518 -- a0ee9032f9e04039f3410ed17fcf45ae1a3868f5 by CJ Johnson <johnsoncj@google.com>: Remove unused EnableIfAtLeastInputIterator from InlinedVector PiperOrigin-RevId: 231348903 -- 4dcd4e9a6780a81d7a6974c7bf22a037e6482b49 by Abseil Team <absl-team@google.com>: Remove unnecessary register keyword from absl/base/internal/endian.h. PiperOrigin-RevId: 231316570 -- c8584836caa3a10f90a8604a85d4b831310b72ee by Abseil Team <absl-team@google.com>: Fix hashtablez_sampler compilation on older Android NDK builds PiperOrigin-RevId: 231283542 GitOrigin-RevId: 6fdf24a197b964f9bacbebd0ceca305aef1654fc Change-Id: I185b12fb8347e3ad0ffcb2cbb83a53450e5eb938
Diffstat (limited to 'absl/hash/hash_test.cc')
-rw-r--r--absl/hash/hash_test.cc331
1 files changed, 327 insertions, 4 deletions
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc
index 224832b1..a5af93ad 100644
--- a/absl/hash/hash_test.cc
+++ b/absl/hash/hash_test.cc
@@ -15,6 +15,7 @@
#include "absl/hash/hash.h"
#include <array>
+#include <bitset>
#include <cstring>
#include <deque>
#include <forward_list>
@@ -84,6 +85,327 @@ using IntTypes = testing::Types<unsigned char, char, int, int32_t, int64_t, uint
uint64_t, size_t>;
INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueIntTest, IntTypes);
+enum LegacyEnum { kValue1, kValue2, kValue3 };
+
+enum class EnumClass { kValue4, kValue5, kValue6 };
+
+TEST(HashValueTest, EnumAndBool) {
+ EXPECT_TRUE((is_hashable<LegacyEnum>::value));
+ EXPECT_TRUE((is_hashable<EnumClass>::value));
+ EXPECT_TRUE((is_hashable<bool>::value));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ LegacyEnum::kValue1, LegacyEnum::kValue2, LegacyEnum::kValue3)));
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ EnumClass::kValue4, EnumClass::kValue5, EnumClass::kValue6)));
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(true, false)));
+}
+
+TEST(HashValueTest, FloatingPoint) {
+ EXPECT_TRUE((is_hashable<float>::value));
+ EXPECT_TRUE((is_hashable<double>::value));
+ EXPECT_TRUE((is_hashable<long double>::value));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(42.f, 0.f, -0.f, std::numeric_limits<float>::infinity(),
+ -std::numeric_limits<float>::infinity())));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(42., 0., -0., std::numeric_limits<double>::infinity(),
+ -std::numeric_limits<double>::infinity())));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ // Add some values with small exponent to test that NORMAL values also
+ // append their category.
+ .5L, 1.L, 2.L, 4.L, 42.L, 0.L, -0.L,
+ 17 * static_cast<long double>(std::numeric_limits<double>::max()),
+ std::numeric_limits<long double>::infinity(),
+ -std::numeric_limits<long double>::infinity())));
+}
+
+TEST(HashValueTest, Pointer) {
+ EXPECT_TRUE((is_hashable<int*>::value));
+
+ int i;
+ int* ptr = &i;
+ int* n = nullptr;
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(&i, ptr, nullptr, ptr + 1, n)));
+}
+
+// TODO(EricWF): MSVC 15 has a bug that causes it to incorrectly evaluate the
+// SFINAE in internal/hash.h, causing this test to fail.
+#if !defined(_MSC_VER)
+TEST(HashValueTest, PairAndTuple) {
+ EXPECT_TRUE((is_hashable<std::pair<int, int>>::value));
+ EXPECT_TRUE((is_hashable<std::pair<const int&, const int&>>::value));
+ EXPECT_TRUE((is_hashable<std::tuple<int&, int&>>::value));
+ EXPECT_TRUE((is_hashable<std::tuple<int&&, int&&>>::value));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ std::make_pair(0, 42), std::make_pair(0, 42), std::make_pair(42, 0),
+ std::make_pair(0, 0), std::make_pair(42, 42), std::make_pair(1, 42))));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(std::make_tuple(0, 0, 0), std::make_tuple(0, 0, 42),
+ std::make_tuple(0, 23, 0), std::make_tuple(17, 0, 0),
+ std::make_tuple(42, 0, 0), std::make_tuple(3, 9, 9),
+ std::make_tuple(0, 0, -42))));
+
+ // Test that tuples of lvalue references work (so we need a few lvalues):
+ int a = 0, b = 1, c = 17, d = 23;
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ std::tie(a, a), std::tie(a, b), std::tie(b, c), std::tie(c, d))));
+
+ // Test that tuples of rvalue references work:
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ std::forward_as_tuple(0, 0, 0), std::forward_as_tuple(0, 0, 42),
+ std::forward_as_tuple(0, 23, 0), std::forward_as_tuple(17, 0, 0),
+ std::forward_as_tuple(42, 0, 0), std::forward_as_tuple(3, 9, 9),
+ std::forward_as_tuple(0, 0, -42))));
+}
+#endif // !defined(_MSC_VER)
+
+TEST(HashValueTest, CombineContiguousWorks) {
+ std::vector<std::tuple<int>> v1 = {std::make_tuple(1), std::make_tuple(3)};
+ std::vector<std::tuple<int>> v2 = {std::make_tuple(1), std::make_tuple(2)};
+
+ auto vh1 = SpyHash(v1);
+ auto vh2 = SpyHash(v2);
+ EXPECT_NE(vh1, vh2);
+}
+
+struct DummyDeleter {
+ template <typename T>
+ void operator() (T* ptr) {}
+};
+
+struct SmartPointerEq {
+ template <typename T, typename U>
+ bool operator()(const T& t, const U& u) const {
+ return GetPtr(t) == GetPtr(u);
+ }
+
+ template <typename T>
+ static auto GetPtr(const T& t) -> decltype(&*t) {
+ return t ? &*t : nullptr;
+ }
+
+ static std::nullptr_t GetPtr(std::nullptr_t) { return nullptr; }
+};
+
+TEST(HashValueTest, SmartPointers) {
+ EXPECT_TRUE((is_hashable<std::unique_ptr<int>>::value));
+ EXPECT_TRUE((is_hashable<std::unique_ptr<int, DummyDeleter>>::value));
+ EXPECT_TRUE((is_hashable<std::shared_ptr<int>>::value));
+
+ int i, j;
+ std::unique_ptr<int, DummyDeleter> unique1(&i);
+ std::unique_ptr<int, DummyDeleter> unique2(&i);
+ std::unique_ptr<int, DummyDeleter> unique_other(&j);
+ std::unique_ptr<int, DummyDeleter> unique_null;
+
+ std::shared_ptr<int> shared1(&i, DummyDeleter());
+ std::shared_ptr<int> shared2(&i, DummyDeleter());
+ std::shared_ptr<int> shared_other(&j, DummyDeleter());
+ std::shared_ptr<int> shared_null;
+
+ // Sanity check of the Eq function.
+ ASSERT_TRUE(SmartPointerEq{}(unique1, shared1));
+ ASSERT_FALSE(SmartPointerEq{}(unique1, shared_other));
+ ASSERT_TRUE(SmartPointerEq{}(unique_null, nullptr));
+ ASSERT_FALSE(SmartPointerEq{}(shared2, nullptr));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::forward_as_tuple(&i, nullptr, //
+ unique1, unique2, unique_null, //
+ absl::make_unique<int>(), //
+ shared1, shared2, shared_null, //
+ std::make_shared<int>()),
+ SmartPointerEq{}));
+}
+
+TEST(HashValueTest, FunctionPointer) {
+ using Func = int (*)();
+ EXPECT_TRUE(is_hashable<Func>::value);
+
+ Func p1 = [] { return 2; }, p2 = [] { return 1; };
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(p1, p2, nullptr)));
+}
+
+struct WrapInTuple {
+ template <typename T>
+ std::tuple<int, T, size_t> operator()(const T& t) const {
+ return std::make_tuple(7, t, 0xdeadbeef);
+ }
+};
+
+TEST(HashValueTest, Strings) {
+ EXPECT_TRUE((is_hashable<std::string>::value));
+ EXPECT_TRUE((is_hashable<std::string>::value));
+
+ const std::string small = "foo";
+ const std::string dup = "foofoo";
+ const std::string large = "large";
+ const std::string huge = std::string(5000, 'a');
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ std::string(), absl::string_view(),
+ std::string(""), absl::string_view(""),
+ std::string(small), absl::string_view(small),
+ std::string(dup), absl::string_view(dup),
+ std::string(large), absl::string_view(large),
+ std::string(huge), absl::string_view(huge))));
+
+ // Also check that nested types maintain the same hash.
+ const WrapInTuple t{};
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ //
+ t(std::string()), t(absl::string_view()),
+ t(std::string("")), t(absl::string_view("")),
+ t(std::string(small)), t(absl::string_view(small)),
+ t(std::string(dup)), t(absl::string_view(dup)),
+ t(std::string(large)), t(absl::string_view(large)),
+ t(std::string(huge)), t(absl::string_view(huge)))));
+
+ // Make sure that hashing a `const char*` does not use its std::string-value.
+ EXPECT_NE(SpyHash(static_cast<const char*>("ABC")),
+ SpyHash(absl::string_view("ABC")));
+}
+
+// TODO(EricWF): MSVC 15 has a bug that causes it to incorrectly evaluate the
+// SFINAE in internal/hash.h, causing this test to fail.
+#if !defined(_MSC_VER)
+TEST(HashValueTest, StdArray) {
+ EXPECT_TRUE((is_hashable<std::array<int, 3>>::value));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(std::array<int, 3>{}, std::array<int, 3>{{0, 23, 42}})));
+}
+#endif // !defined(_MSC_VER)
+
+TEST(HashValueTest, StdBitset) {
+ EXPECT_TRUE((is_hashable<std::bitset<257>>::value));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ {std::bitset<2>("00"), std::bitset<2>("01"), std::bitset<2>("10"),
+ std::bitset<2>("11")}));
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ {std::bitset<5>("10101"), std::bitset<5>("10001"), std::bitset<5>()}));
+
+ constexpr int kNumBits = 256;
+ std::array<std::string, 6> bit_strings;
+ bit_strings.fill(std::string(kNumBits, '1'));
+ bit_strings[1][0] = '0';
+ bit_strings[2][1] = '0';
+ bit_strings[3][kNumBits / 3] = '0';
+ bit_strings[4][kNumBits - 2] = '0';
+ bit_strings[5][kNumBits - 1] = '0';
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ {std::bitset<kNumBits>(bit_strings[0].c_str()),
+ std::bitset<kNumBits>(bit_strings[1].c_str()),
+ std::bitset<kNumBits>(bit_strings[2].c_str()),
+ std::bitset<kNumBits>(bit_strings[3].c_str()),
+ std::bitset<kNumBits>(bit_strings[4].c_str()),
+ std::bitset<kNumBits>(bit_strings[5].c_str())}));
+} // namespace
+
+template <typename T>
+class HashValueSequenceTest : public testing::Test {
+};
+TYPED_TEST_SUITE_P(HashValueSequenceTest);
+
+TYPED_TEST_P(HashValueSequenceTest, BasicUsage) {
+ EXPECT_TRUE((is_hashable<TypeParam>::value));
+
+ using ValueType = typename TypeParam::value_type;
+ auto a = static_cast<ValueType>(0);
+ auto b = static_cast<ValueType>(23);
+ auto c = static_cast<ValueType>(42);
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(TypeParam(), TypeParam{}, TypeParam{a, b, c},
+ TypeParam{a, b}, TypeParam{b, c})));
+}
+
+REGISTER_TYPED_TEST_CASE_P(HashValueSequenceTest, BasicUsage);
+using IntSequenceTypes =
+ testing::Types<std::deque<int>, std::forward_list<int>, std::list<int>,
+ std::vector<int>, std::vector<bool>, std::set<int>,
+ std::multiset<int>>;
+INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueSequenceTest, IntSequenceTypes);
+
+// Private type that only supports AbslHashValue to make sure our chosen hash
+// implentation is recursive within absl::Hash.
+// It uses std::abs() on the value to provide different bitwise representations
+// of the same logical value.
+struct Private {
+ int i;
+ template <typename H>
+ friend H AbslHashValue(H h, Private p) {
+ return H::combine(std::move(h), std::abs(p.i));
+ }
+
+ friend bool operator==(Private a, Private b) {
+ return std::abs(a.i) == std::abs(b.i);
+ }
+
+ friend std::ostream& operator<<(std::ostream& o, Private p) {
+ return o << p.i;
+ }
+};
+
+TEST(HashValueTest, PrivateSanity) {
+ // Sanity check that Private is working as the tests below expect it to work.
+ EXPECT_TRUE(is_hashable<Private>::value);
+ EXPECT_NE(SpyHash(Private{0}), SpyHash(Private{1}));
+ EXPECT_EQ(SpyHash(Private{1}), SpyHash(Private{1}));
+}
+
+TEST(HashValueTest, Optional) {
+ EXPECT_TRUE(is_hashable<absl::optional<Private>>::value);
+
+ using O = absl::optional<Private>;
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(O{}, O{{1}}, O{{-1}}, O{{10}})));
+}
+
+TEST(HashValueTest, Variant) {
+ using V = absl::variant<Private, std::string>;
+ EXPECT_TRUE(is_hashable<V>::value);
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ V(Private{1}), V(Private{-1}), V(Private{2}), V("ABC"), V("BCD"))));
+
+#if ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
+ struct S {};
+ EXPECT_FALSE(is_hashable<absl::variant<S>>::value);
+#endif
+}
+
+// TODO(EricWF): MSVC 15 has a bug that causes it to incorrectly evaluate the
+// SFINAE in internal/hash.h, causing this test to fail.
+#if !defined(_MSC_VER)
+TEST(HashValueTest, Maps) {
+ EXPECT_TRUE((is_hashable<std::map<int, std::string>>::value));
+
+ using M = std::map<int, std::string>;
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ M{}, M{{0, "foo"}}, M{{1, "foo"}}, M{{0, "bar"}}, M{{1, "bar"}},
+ M{{0, "foo"}, {42, "bar"}}, M{{1, "foo"}, {42, "bar"}},
+ M{{1, "foo"}, {43, "bar"}}, M{{1, "foo"}, {43, "baz"}})));
+
+ using MM = std::multimap<int, std::string>;
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ MM{}, MM{{0, "foo"}}, MM{{1, "foo"}}, MM{{0, "bar"}}, MM{{1, "bar"}},
+ MM{{0, "foo"}, {0, "bar"}}, MM{{0, "bar"}, {0, "foo"}},
+ MM{{0, "foo"}, {42, "bar"}}, MM{{1, "foo"}, {42, "bar"}},
+ MM{{1, "foo"}, {1, "foo"}, {43, "bar"}}, MM{{1, "foo"}, {43, "baz"}})));
+}
+#endif // !defined(_MSC_VER)
+
template <typename T, typename = void>
struct IsHashCallble : std::false_type {};
@@ -108,7 +430,8 @@ TEST(IsHashableTest, ValidHash) {
EXPECT_TRUE(IsHashCallble<int>::value);
EXPECT_TRUE(IsAggregateInitializable<absl::Hash<int>>::value);
}
-#if ABSL_HASH_INTERNAL_CAN_POISON_ && !defined(__APPLE__)
+
+#if ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
TEST(IsHashableTest, PoisonHash) {
struct X {};
EXPECT_FALSE((is_hashable<X>::value));
@@ -120,7 +443,7 @@ TEST(IsHashableTest, PoisonHash) {
EXPECT_FALSE(IsHashCallble<X>::value);
EXPECT_FALSE(IsAggregateInitializable<absl::Hash<X>>::value);
}
-#endif // ABSL_HASH_INTERNAL_CAN_POISON_
+#endif // ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
// Hashable types
//
@@ -245,13 +568,13 @@ void TestCustomHashType(InvokeTagConstant<InvokeTag::kNone>, T...) {
}
void TestCustomHashType(InvokeTagConstant<InvokeTag::kNone>) {
-#if ABSL_HASH_INTERNAL_CAN_POISON_
+#if ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
// is_hashable is false if we don't support any of the hooks.
using type = CustomHashType<>;
EXPECT_FALSE(is_hashable<type>());
EXPECT_FALSE(is_hashable<const type>());
EXPECT_FALSE(is_hashable<const type&>());
-#endif // ABSL_HASH_INTERNAL_CAN_POISON_
+#endif // ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
}
template <InvokeTag Tag, typename... T>