hash_test.cc
Go to the documentation of this file.
1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include "absl/hash/hash.h"
16 
17 #include <array>
18 #include <bitset>
19 #include <cstring>
20 #include <deque>
21 #include <forward_list>
22 #include <functional>
23 #include <iterator>
24 #include <limits>
25 #include <list>
26 #include <map>
27 #include <memory>
28 #include <numeric>
29 #include <random>
30 #include <set>
31 #include <string>
32 #include <tuple>
33 #include <type_traits>
34 #include <unordered_map>
35 #include <utility>
36 #include <vector>
37 
38 #include "gmock/gmock.h"
39 #include "gtest/gtest.h"
41 #include "absl/hash/hash_testing.h"
43 #include "absl/meta/type_traits.h"
44 #include "absl/numeric/int128.h"
45 
46 namespace {
47 
48 using absl::Hash;
50 
51 template <typename T>
52 class HashValueIntTest : public testing::Test {
53 };
54 TYPED_TEST_SUITE_P(HashValueIntTest);
55 
56 template <typename T>
57 SpyHashState SpyHash(const T& value) {
58  return SpyHashState::combine(SpyHashState(), value);
59 }
60 
61 // Helper trait to verify if T is hashable. We use absl::Hash's poison status to
62 // detect it.
63 template <typename T>
64 using is_hashable = std::is_default_constructible<absl::Hash<T>>;
65 
66 TYPED_TEST_P(HashValueIntTest, BasicUsage) {
67  EXPECT_TRUE((is_hashable<TypeParam>::value));
68 
69  TypeParam n = 42;
70  EXPECT_EQ(SpyHash(n), SpyHash(TypeParam{42}));
71  EXPECT_NE(SpyHash(n), SpyHash(TypeParam{0}));
72  EXPECT_NE(SpyHash(std::numeric_limits<TypeParam>::max()),
73  SpyHash(std::numeric_limits<TypeParam>::min()));
74 }
75 
76 TYPED_TEST_P(HashValueIntTest, FastPath) {
77  // Test the fast-path to make sure the values are the same.
78  TypeParam n = 42;
79  EXPECT_EQ(absl::Hash<TypeParam>{}(n),
80  absl::Hash<std::tuple<TypeParam>>{}(std::tuple<TypeParam>(n)));
81 }
82 
83 REGISTER_TYPED_TEST_CASE_P(HashValueIntTest, BasicUsage, FastPath);
84 using IntTypes = testing::Types<unsigned char, char, int, int32_t, int64_t, uint32_t,
85  uint64_t, size_t>;
86 INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueIntTest, IntTypes);
87 
88 enum LegacyEnum { kValue1, kValue2, kValue3 };
89 
90 enum class EnumClass { kValue4, kValue5, kValue6 };
91 
92 TEST(HashValueTest, EnumAndBool) {
93  EXPECT_TRUE((is_hashable<LegacyEnum>::value));
94  EXPECT_TRUE((is_hashable<EnumClass>::value));
95  EXPECT_TRUE((is_hashable<bool>::value));
96 
97  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
98  LegacyEnum::kValue1, LegacyEnum::kValue2, LegacyEnum::kValue3)));
99  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
100  EnumClass::kValue4, EnumClass::kValue5, EnumClass::kValue6)));
102  std::make_tuple(true, false)));
103 }
104 
105 TEST(HashValueTest, FloatingPoint) {
106  EXPECT_TRUE((is_hashable<float>::value));
107  EXPECT_TRUE((is_hashable<double>::value));
108  EXPECT_TRUE((is_hashable<long double>::value));
109 
111  std::make_tuple(42.f, 0.f, -0.f, std::numeric_limits<float>::infinity(),
112  -std::numeric_limits<float>::infinity())));
113 
115  std::make_tuple(42., 0., -0., std::numeric_limits<double>::infinity(),
116  -std::numeric_limits<double>::infinity())));
117 
118  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
119  // Add some values with small exponent to test that NORMAL values also
120  // append their category.
121  .5L, 1.L, 2.L, 4.L, 42.L, 0.L, -0.L,
122  17 * static_cast<long double>(std::numeric_limits<double>::max()),
123  std::numeric_limits<long double>::infinity(),
124  -std::numeric_limits<long double>::infinity())));
125 }
126 
127 TEST(HashValueTest, Pointer) {
128  EXPECT_TRUE((is_hashable<int*>::value));
129 
130  int i;
131  int* ptr = &i;
132  int* n = nullptr;
133 
135  std::make_tuple(&i, ptr, nullptr, ptr + 1, n)));
136 }
137 
138 TEST(HashValueTest, PointerAlignment) {
139  // We want to make sure that pointer alignment will not cause bits to be
140  // stuck.
141 
142  constexpr size_t kTotalSize = 1 << 20;
143  std::unique_ptr<char[]> data(new char[kTotalSize]);
144  constexpr size_t kLog2NumValues = 5;
145  constexpr size_t kNumValues = 1 << kLog2NumValues;
146 
147  for (size_t align = 1; align < kTotalSize / kNumValues;
148  align < 8 ? align += 1 : align < 1024 ? align += 8 : align += 32) {
149  SCOPED_TRACE(align);
150  ASSERT_LE(align * kNumValues, kTotalSize);
151 
152  size_t bits_or = 0;
153  size_t bits_and = ~size_t{};
154 
155  for (size_t i = 0; i < kNumValues; ++i) {
156  size_t hash = absl::Hash<void*>()(data.get() + i * align);
157  bits_or |= hash;
158  bits_and &= hash;
159  }
160 
161  // Limit the scope to the bits we would be using for Swisstable.
162  constexpr size_t kMask = (1 << (kLog2NumValues + 7)) - 1;
163  size_t stuck_bits = (~bits_or | bits_and) & kMask;
164  EXPECT_EQ(stuck_bits, 0) << "0x" << std::hex << stuck_bits;
165  }
166 }
167 
168 TEST(HashValueTest, PairAndTuple) {
169  EXPECT_TRUE((is_hashable<std::pair<int, int>>::value));
170  EXPECT_TRUE((is_hashable<std::pair<const int&, const int&>>::value));
171  EXPECT_TRUE((is_hashable<std::tuple<int&, int&>>::value));
172  EXPECT_TRUE((is_hashable<std::tuple<int&&, int&&>>::value));
173 
174  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
175  std::make_pair(0, 42), std::make_pair(0, 42), std::make_pair(42, 0),
176  std::make_pair(0, 0), std::make_pair(42, 42), std::make_pair(1, 42))));
177 
179  std::make_tuple(std::make_tuple(0, 0, 0), std::make_tuple(0, 0, 42),
180  std::make_tuple(0, 23, 0), std::make_tuple(17, 0, 0),
181  std::make_tuple(42, 0, 0), std::make_tuple(3, 9, 9),
182  std::make_tuple(0, 0, -42))));
183 
184  // Test that tuples of lvalue references work (so we need a few lvalues):
185  int a = 0, b = 1, c = 17, d = 23;
186  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
187  std::tie(a, a), std::tie(a, b), std::tie(b, c), std::tie(c, d))));
188 
189  // Test that tuples of rvalue references work:
190  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
191  std::forward_as_tuple(0, 0, 0), std::forward_as_tuple(0, 0, 42),
192  std::forward_as_tuple(0, 23, 0), std::forward_as_tuple(17, 0, 0),
193  std::forward_as_tuple(42, 0, 0), std::forward_as_tuple(3, 9, 9),
194  std::forward_as_tuple(0, 0, -42))));
195 }
196 
197 TEST(HashValueTest, CombineContiguousWorks) {
198  std::vector<std::tuple<int>> v1 = {std::make_tuple(1), std::make_tuple(3)};
199  std::vector<std::tuple<int>> v2 = {std::make_tuple(1), std::make_tuple(2)};
200 
201  auto vh1 = SpyHash(v1);
202  auto vh2 = SpyHash(v2);
203  EXPECT_NE(vh1, vh2);
204 }
205 
206 struct DummyDeleter {
207  template <typename T>
208  void operator() (T* ptr) {}
209 };
210 
211 struct SmartPointerEq {
212  template <typename T, typename U>
213  bool operator()(const T& t, const U& u) const {
214  return GetPtr(t) == GetPtr(u);
215  }
216 
217  template <typename T>
218  static auto GetPtr(const T& t) -> decltype(&*t) {
219  return t ? &*t : nullptr;
220  }
221 
222  static std::nullptr_t GetPtr(std::nullptr_t) { return nullptr; }
223 };
224 
225 TEST(HashValueTest, SmartPointers) {
226  EXPECT_TRUE((is_hashable<std::unique_ptr<int>>::value));
227  EXPECT_TRUE((is_hashable<std::unique_ptr<int, DummyDeleter>>::value));
228  EXPECT_TRUE((is_hashable<std::shared_ptr<int>>::value));
229 
230  int i, j;
231  std::unique_ptr<int, DummyDeleter> unique1(&i);
232  std::unique_ptr<int, DummyDeleter> unique2(&i);
233  std::unique_ptr<int, DummyDeleter> unique_other(&j);
234  std::unique_ptr<int, DummyDeleter> unique_null;
235 
236  std::shared_ptr<int> shared1(&i, DummyDeleter());
237  std::shared_ptr<int> shared2(&i, DummyDeleter());
238  std::shared_ptr<int> shared_other(&j, DummyDeleter());
239  std::shared_ptr<int> shared_null;
240 
241  // Sanity check of the Eq function.
242  ASSERT_TRUE(SmartPointerEq{}(unique1, shared1));
243  ASSERT_FALSE(SmartPointerEq{}(unique1, shared_other));
244  ASSERT_TRUE(SmartPointerEq{}(unique_null, nullptr));
245  ASSERT_FALSE(SmartPointerEq{}(shared2, nullptr));
246 
248  std::forward_as_tuple(&i, nullptr, //
249  unique1, unique2, unique_null, //
250  absl::make_unique<int>(), //
251  shared1, shared2, shared_null, //
252  std::make_shared<int>()),
253  SmartPointerEq{}));
254 }
255 
256 TEST(HashValueTest, FunctionPointer) {
257  using Func = int (*)();
258  EXPECT_TRUE(is_hashable<Func>::value);
259 
260  Func p1 = [] { return 2; }, p2 = [] { return 1; };
262  std::make_tuple(p1, p2, nullptr)));
263 }
264 
265 struct WrapInTuple {
266  template <typename T>
267  std::tuple<int, T, size_t> operator()(const T& t) const {
268  return std::make_tuple(7, t, 0xdeadbeef);
269  }
270 };
271 
272 TEST(HashValueTest, Strings) {
273  EXPECT_TRUE((is_hashable<std::string>::value));
274 
275  const std::string small = "foo";
276  const std::string dup = "foofoo";
277  const std::string large = "large";
278  const std::string huge = std::string(5000, 'a');
279 
280  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
281  std::string(), absl::string_view(),
282  std::string(""), absl::string_view(""),
283  std::string(small), absl::string_view(small),
284  std::string(dup), absl::string_view(dup),
285  std::string(large), absl::string_view(large),
286  std::string(huge), absl::string_view(huge))));
287 
288  // Also check that nested types maintain the same hash.
289  const WrapInTuple t{};
290  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
291  //
292  t(std::string()), t(absl::string_view()),
293  t(std::string("")), t(absl::string_view("")),
294  t(std::string(small)), t(absl::string_view(small)),
295  t(std::string(dup)), t(absl::string_view(dup)),
296  t(std::string(large)), t(absl::string_view(large)),
297  t(std::string(huge)), t(absl::string_view(huge)))));
298 
299  // Make sure that hashing a `const char*` does not use its std::string-value.
300  EXPECT_NE(SpyHash(static_cast<const char*>("ABC")),
301  SpyHash(absl::string_view("ABC")));
302 }
303 
304 TEST(HashValueTest, StdArray) {
305  EXPECT_TRUE((is_hashable<std::array<int, 3>>::value));
306 
308  std::make_tuple(std::array<int, 3>{}, std::array<int, 3>{{0, 23, 42}})));
309 }
310 
311 TEST(HashValueTest, StdBitset) {
312  EXPECT_TRUE((is_hashable<std::bitset<257>>::value));
313 
315  {std::bitset<2>("00"), std::bitset<2>("01"), std::bitset<2>("10"),
316  std::bitset<2>("11")}));
318  {std::bitset<5>("10101"), std::bitset<5>("10001"), std::bitset<5>()}));
319 
320  constexpr int kNumBits = 256;
321  std::array<std::string, 6> bit_strings;
322  bit_strings.fill(std::string(kNumBits, '1'));
323  bit_strings[1][0] = '0';
324  bit_strings[2][1] = '0';
325  bit_strings[3][kNumBits / 3] = '0';
326  bit_strings[4][kNumBits - 2] = '0';
327  bit_strings[5][kNumBits - 1] = '0';
329  {std::bitset<kNumBits>(bit_strings[0].c_str()),
330  std::bitset<kNumBits>(bit_strings[1].c_str()),
331  std::bitset<kNumBits>(bit_strings[2].c_str()),
332  std::bitset<kNumBits>(bit_strings[3].c_str()),
333  std::bitset<kNumBits>(bit_strings[4].c_str()),
334  std::bitset<kNumBits>(bit_strings[5].c_str())}));
335 } // namespace
336 
337 template <typename T>
338 class HashValueSequenceTest : public testing::Test {
339 };
340 TYPED_TEST_SUITE_P(HashValueSequenceTest);
341 
342 TYPED_TEST_P(HashValueSequenceTest, BasicUsage) {
343  EXPECT_TRUE((is_hashable<TypeParam>::value));
344 
345  using ValueType = typename TypeParam::value_type;
346  auto a = static_cast<ValueType>(0);
347  auto b = static_cast<ValueType>(23);
348  auto c = static_cast<ValueType>(42);
349 
351  std::make_tuple(TypeParam(), TypeParam{}, TypeParam{a, b, c},
352  TypeParam{a, b}, TypeParam{b, c})));
353 }
354 
355 REGISTER_TYPED_TEST_CASE_P(HashValueSequenceTest, BasicUsage);
356 using IntSequenceTypes =
357  testing::Types<std::deque<int>, std::forward_list<int>, std::list<int>,
358  std::vector<int>, std::vector<bool>, std::set<int>,
359  std::multiset<int>>;
360 INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueSequenceTest, IntSequenceTypes);
361 
362 // Private type that only supports AbslHashValue to make sure our chosen hash
363 // implentation is recursive within absl::Hash.
364 // It uses std::abs() on the value to provide different bitwise representations
365 // of the same logical value.
366 struct Private {
367  int i;
368  template <typename H>
369  friend H AbslHashValue(H h, Private p) {
370  return H::combine(std::move(h), std::abs(p.i));
371  }
372 
373  friend bool operator==(Private a, Private b) {
374  return std::abs(a.i) == std::abs(b.i);
375  }
376 
377  friend std::ostream& operator<<(std::ostream& o, Private p) {
378  return o << p.i;
379  }
380 };
381 
382 TEST(HashValueTest, PrivateSanity) {
383  // Sanity check that Private is working as the tests below expect it to work.
384  EXPECT_TRUE(is_hashable<Private>::value);
385  EXPECT_NE(SpyHash(Private{0}), SpyHash(Private{1}));
386  EXPECT_EQ(SpyHash(Private{1}), SpyHash(Private{1}));
387 }
388 
389 TEST(HashValueTest, Optional) {
390  EXPECT_TRUE(is_hashable<absl::optional<Private>>::value);
391 
392  using O = absl::optional<Private>;
394  std::make_tuple(O{}, O{{1}}, O{{-1}}, O{{10}})));
395 }
396 
397 TEST(HashValueTest, Variant) {
399  EXPECT_TRUE(is_hashable<V>::value);
400 
401  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
402  V(Private{1}), V(Private{-1}), V(Private{2}), V("ABC"), V("BCD"))));
403 
404 #if ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
405  struct S {};
406  EXPECT_FALSE(is_hashable<absl::variant<S>>::value);
407 #endif
408 }
409 
410 TEST(HashValueTest, Maps) {
411  EXPECT_TRUE((is_hashable<std::map<int, std::string>>::value));
412 
413  using M = std::map<int, std::string>;
414  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
415  M{}, M{{0, "foo"}}, M{{1, "foo"}}, M{{0, "bar"}}, M{{1, "bar"}},
416  M{{0, "foo"}, {42, "bar"}}, M{{1, "foo"}, {42, "bar"}},
417  M{{1, "foo"}, {43, "bar"}}, M{{1, "foo"}, {43, "baz"}})));
418 
419  using MM = std::multimap<int, std::string>;
420  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
421  MM{}, MM{{0, "foo"}}, MM{{1, "foo"}}, MM{{0, "bar"}}, MM{{1, "bar"}},
422  MM{{0, "foo"}, {0, "bar"}}, MM{{0, "bar"}, {0, "foo"}},
423  MM{{0, "foo"}, {42, "bar"}}, MM{{1, "foo"}, {42, "bar"}},
424  MM{{1, "foo"}, {1, "foo"}, {43, "bar"}}, MM{{1, "foo"}, {43, "baz"}})));
425 }
426 
427 template <typename T, typename = void>
428 struct IsHashCallable : std::false_type {};
429 
430 template <typename T>
431 struct IsHashCallable<T, absl::void_t<decltype(std::declval<absl::Hash<T>>()(
432  std::declval<const T&>()))>> : std::true_type {};
433 
434 template <typename T, typename = void>
435 struct IsAggregateInitializable : std::false_type {};
436 
437 template <typename T>
438 struct IsAggregateInitializable<T, absl::void_t<decltype(T{})>>
439  : std::true_type {};
440 
441 TEST(IsHashableTest, ValidHash) {
442  EXPECT_TRUE((is_hashable<int>::value));
443  EXPECT_TRUE(std::is_default_constructible<absl::Hash<int>>::value);
444  EXPECT_TRUE(std::is_copy_constructible<absl::Hash<int>>::value);
445  EXPECT_TRUE(std::is_move_constructible<absl::Hash<int>>::value);
446  EXPECT_TRUE(absl::is_copy_assignable<absl::Hash<int>>::value);
447  EXPECT_TRUE(absl::is_move_assignable<absl::Hash<int>>::value);
448  EXPECT_TRUE(IsHashCallable<int>::value);
449  EXPECT_TRUE(IsAggregateInitializable<absl::Hash<int>>::value);
450 }
451 
452 #if ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
453 TEST(IsHashableTest, PoisonHash) {
454  struct X {};
455  EXPECT_FALSE((is_hashable<X>::value));
456  EXPECT_FALSE(std::is_default_constructible<absl::Hash<X>>::value);
457  EXPECT_FALSE(std::is_copy_constructible<absl::Hash<X>>::value);
458  EXPECT_FALSE(std::is_move_constructible<absl::Hash<X>>::value);
459  EXPECT_FALSE(absl::is_copy_assignable<absl::Hash<X>>::value);
460  EXPECT_FALSE(absl::is_move_assignable<absl::Hash<X>>::value);
461  EXPECT_FALSE(IsHashCallable<X>::value);
462  EXPECT_FALSE(IsAggregateInitializable<absl::Hash<X>>::value);
463 }
464 #endif // ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
465 
466 // Hashable types
467 //
468 // These types exist simply to exercise various AbslHashValue behaviors, so
469 // they are named by what their AbslHashValue overload does.
470 struct NoOp {
471  template <typename HashCode>
472  friend HashCode AbslHashValue(HashCode h, NoOp n) {
473  return h;
474  }
475 };
476 
477 struct EmptyCombine {
478  template <typename HashCode>
479  friend HashCode AbslHashValue(HashCode h, EmptyCombine e) {
480  return HashCode::combine(std::move(h));
481  }
482 };
483 
484 template <typename Int>
485 struct CombineIterative {
486  template <typename HashCode>
487  friend HashCode AbslHashValue(HashCode h, CombineIterative c) {
488  for (int i = 0; i < 5; ++i) {
489  h = HashCode::combine(std::move(h), Int(i));
490  }
491  return h;
492  }
493 };
494 
495 template <typename Int>
496 struct CombineVariadic {
497  template <typename HashCode>
498  friend HashCode AbslHashValue(HashCode h, CombineVariadic c) {
499  return HashCode::combine(std::move(h), Int(0), Int(1), Int(2), Int(3),
500  Int(4));
501  }
502 };
503 enum class InvokeTag {
504  kUniquelyRepresented,
505  kHashValue,
506 #if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_
507  kLegacyHash,
508 #endif // ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_
509  kStdHash,
510  kNone
511 };
512 
513 template <InvokeTag T>
514 using InvokeTagConstant = std::integral_constant<InvokeTag, T>;
515 
516 template <InvokeTag... Tags>
517 struct MinTag;
518 
519 template <InvokeTag a, InvokeTag b, InvokeTag... Tags>
520 struct MinTag<a, b, Tags...> : MinTag<(a < b ? a : b), Tags...> {};
521 
522 template <InvokeTag a>
523 struct MinTag<a> : InvokeTagConstant<a> {};
524 
525 template <InvokeTag... Tags>
526 struct CustomHashType {
527  explicit CustomHashType(size_t val) : value(val) {}
528  size_t value;
529 };
530 
531 template <InvokeTag allowed, InvokeTag... tags>
532 struct EnableIfContained
533  : std::enable_if<absl::disjunction<
534  std::integral_constant<bool, allowed == tags>...>::value> {};
535 
536 template <
537  typename H, InvokeTag... Tags,
538  typename = typename EnableIfContained<InvokeTag::kHashValue, Tags...>::type>
539 H AbslHashValue(H state, CustomHashType<Tags...> t) {
540  static_assert(MinTag<Tags...>::value == InvokeTag::kHashValue, "");
541  return H::combine(std::move(state),
542  t.value + static_cast<int>(InvokeTag::kHashValue));
543 }
544 
545 } // namespace
546 
547 namespace absl {
548 namespace hash_internal {
549 template <InvokeTag... Tags>
550 struct is_uniquely_represented<
551  CustomHashType<Tags...>,
552  typename EnableIfContained<InvokeTag::kUniquelyRepresented, Tags...>::type>
553  : std::true_type {};
554 } // namespace hash_internal
555 } // namespace absl
556 
557 #if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_
558 namespace ABSL_INTERNAL_LEGACY_HASH_NAMESPACE {
559 template <InvokeTag... Tags>
560 struct hash<CustomHashType<Tags...>> {
561  template <InvokeTag... TagsIn, typename = typename EnableIfContained<
562  InvokeTag::kLegacyHash, TagsIn...>::type>
563  size_t operator()(CustomHashType<TagsIn...> t) const {
564  static_assert(MinTag<Tags...>::value == InvokeTag::kLegacyHash, "");
565  return t.value + static_cast<int>(InvokeTag::kLegacyHash);
566  }
567 };
568 } // namespace ABSL_INTERNAL_LEGACY_HASH_NAMESPACE
569 #endif // ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_
570 
571 namespace std {
572 template <InvokeTag... Tags> // NOLINT
573 struct hash<CustomHashType<Tags...>> {
574  template <InvokeTag... TagsIn, typename = typename EnableIfContained<
575  InvokeTag::kStdHash, TagsIn...>::type>
576  size_t operator()(CustomHashType<TagsIn...> t) const {
577  static_assert(MinTag<Tags...>::value == InvokeTag::kStdHash, "");
578  return t.value + static_cast<int>(InvokeTag::kStdHash);
579  }
580 };
581 } // namespace std
582 
583 namespace {
584 
585 template <typename... T>
586 void TestCustomHashType(InvokeTagConstant<InvokeTag::kNone>, T...) {
587  using type = CustomHashType<T::value...>;
588  SCOPED_TRACE(testing::PrintToString(std::vector<InvokeTag>{T::value...}));
589  EXPECT_TRUE(is_hashable<type>());
590  EXPECT_TRUE(is_hashable<const type>());
591  EXPECT_TRUE(is_hashable<const type&>());
592 
593  const size_t offset = static_cast<int>(std::min({T::value...}));
594  EXPECT_EQ(SpyHash(type(7)), SpyHash(size_t{7 + offset}));
595 }
596 
597 void TestCustomHashType(InvokeTagConstant<InvokeTag::kNone>) {
598 #if ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
599  // is_hashable is false if we don't support any of the hooks.
600  using type = CustomHashType<>;
601  EXPECT_FALSE(is_hashable<type>());
602  EXPECT_FALSE(is_hashable<const type>());
603  EXPECT_FALSE(is_hashable<const type&>());
604 #endif // ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
605 }
606 
607 template <InvokeTag Tag, typename... T>
608 void TestCustomHashType(InvokeTagConstant<Tag> tag, T... t) {
609  constexpr auto next = static_cast<InvokeTag>(static_cast<int>(Tag) + 1);
610  TestCustomHashType(InvokeTagConstant<next>(), tag, t...);
611  TestCustomHashType(InvokeTagConstant<next>(), t...);
612 }
613 
614 TEST(HashTest, CustomHashType) {
615  TestCustomHashType(InvokeTagConstant<InvokeTag{}>());
616 }
617 
618 TEST(HashTest, NoOpsAreEquivalent) {
619  EXPECT_EQ(Hash<NoOp>()({}), Hash<NoOp>()({}));
620  EXPECT_EQ(Hash<NoOp>()({}), Hash<EmptyCombine>()({}));
621 }
622 
623 template <typename T>
624 class HashIntTest : public testing::Test {
625 };
626 TYPED_TEST_SUITE_P(HashIntTest);
627 
628 TYPED_TEST_P(HashIntTest, BasicUsage) {
629  EXPECT_NE(Hash<NoOp>()({}), Hash<TypeParam>()(0));
630  EXPECT_NE(Hash<NoOp>()({}),
631  Hash<TypeParam>()(std::numeric_limits<TypeParam>::max()));
632  if (std::numeric_limits<TypeParam>::min() != 0) {
633  EXPECT_NE(Hash<NoOp>()({}),
634  Hash<TypeParam>()(std::numeric_limits<TypeParam>::min()));
635  }
636 
637  EXPECT_EQ(Hash<CombineIterative<TypeParam>>()({}),
638  Hash<CombineVariadic<TypeParam>>()({}));
639 }
640 
641 REGISTER_TYPED_TEST_CASE_P(HashIntTest, BasicUsage);
642 using IntTypes = testing::Types<unsigned char, char, int, int32_t, int64_t, uint32_t,
643  uint64_t, size_t>;
644 INSTANTIATE_TYPED_TEST_CASE_P(My, HashIntTest, IntTypes);
645 
646 struct StructWithPadding {
647  char c;
648  int i;
649 
650  template <typename H>
651  friend H AbslHashValue(H hash_state, const StructWithPadding& s) {
652  return H::combine(std::move(hash_state), s.c, s.i);
653  }
654 };
655 
656 static_assert(sizeof(StructWithPadding) > sizeof(char) + sizeof(int),
657  "StructWithPadding doesn't have padding");
658 static_assert(std::is_standard_layout<StructWithPadding>::value, "");
659 
660 // This check has to be disabled because libstdc++ doesn't support it.
661 // static_assert(std::is_trivially_constructible<StructWithPadding>::value, "");
662 
663 template <typename T>
664 struct ArraySlice {
665  T* begin;
666  T* end;
667 
668  template <typename H>
669  friend H AbslHashValue(H hash_state, const ArraySlice& slice) {
670  for (auto t = slice.begin; t != slice.end; ++t) {
671  hash_state = H::combine(std::move(hash_state), *t);
672  }
673  return hash_state;
674  }
675 };
676 
677 TEST(HashTest, HashNonUniquelyRepresentedType) {
678  // Create equal StructWithPadding objects that are known to have non-equal
679  // padding bytes.
680  static const size_t kNumStructs = 10;
681  unsigned char buffer1[kNumStructs * sizeof(StructWithPadding)];
682  std::memset(buffer1, 0, sizeof(buffer1));
683  auto* s1 = reinterpret_cast<StructWithPadding*>(buffer1);
684 
685  unsigned char buffer2[kNumStructs * sizeof(StructWithPadding)];
686  std::memset(buffer2, 255, sizeof(buffer2));
687  auto* s2 = reinterpret_cast<StructWithPadding*>(buffer2);
688  for (int i = 0; i < kNumStructs; ++i) {
689  SCOPED_TRACE(i);
690  s1[i].c = s2[i].c = '0' + i;
691  s1[i].i = s2[i].i = i;
692  ASSERT_FALSE(memcmp(buffer1 + i * sizeof(StructWithPadding),
693  buffer2 + i * sizeof(StructWithPadding),
694  sizeof(StructWithPadding)) == 0)
695  << "Bug in test code: objects do not have unequal"
696  << " object representations";
697  }
698 
699  EXPECT_EQ(Hash<StructWithPadding>()(s1[0]), Hash<StructWithPadding>()(s2[0]));
700  EXPECT_EQ(Hash<ArraySlice<StructWithPadding>>()({s1, s1 + kNumStructs}),
701  Hash<ArraySlice<StructWithPadding>>()({s2, s2 + kNumStructs}));
702 }
703 
704 TEST(HashTest, StandardHashContainerUsage) {
705  std::unordered_map<int, std::string, Hash<int>> map = {{0, "foo"},
706  {42, "bar"}};
707 
708  EXPECT_NE(map.find(0), map.end());
709  EXPECT_EQ(map.find(1), map.end());
710  EXPECT_NE(map.find(0u), map.end());
711 }
712 
713 struct ConvertibleFromNoOp {
714  ConvertibleFromNoOp(NoOp) {} // NOLINT(runtime/explicit)
715 
716  template <typename H>
717  friend H AbslHashValue(H hash_state, ConvertibleFromNoOp) {
718  return H::combine(std::move(hash_state), 1);
719  }
720 };
721 
722 TEST(HashTest, HeterogeneousCall) {
723  EXPECT_NE(Hash<ConvertibleFromNoOp>()(NoOp()),
724  Hash<NoOp>()(NoOp()));
725 }
726 
727 TEST(IsUniquelyRepresentedTest, SanityTest) {
729 
734 }
735 
736 struct IntAndString {
737  int i;
738  std::string s;
739 
740  template <typename H>
741  friend H AbslHashValue(H hash_state, IntAndString int_and_string) {
742  return H::combine(std::move(hash_state), int_and_string.s,
743  int_and_string.i);
744  }
745 };
746 
747 TEST(HashTest, SmallValueOn64ByteBoundary) {
748  Hash<IntAndString>()(IntAndString{0, std::string(63, '0')});
749 }
750 
751 struct TypeErased {
752  size_t n;
753 
754  template <typename H>
755  friend H AbslHashValue(H hash_state, const TypeErased& v) {
756  v.HashValue(absl::HashState::Create(&hash_state));
757  return hash_state;
758  }
759 
760  void HashValue(absl::HashState state) const {
762  }
763 };
764 
765 TEST(HashTest, TypeErased) {
766  EXPECT_TRUE((is_hashable<TypeErased>::value));
767  EXPECT_TRUE((is_hashable<std::pair<TypeErased, int>>::value));
768 
769  EXPECT_EQ(SpyHash(TypeErased{7}), SpyHash(size_t{7}));
770  EXPECT_NE(SpyHash(TypeErased{7}), SpyHash(size_t{13}));
771 
772  EXPECT_EQ(SpyHash(std::make_pair(TypeErased{7}, 17)),
773  SpyHash(std::make_pair(size_t{7}, 17)));
774 }
775 
776 struct ValueWithBoolConversion {
777  operator bool() const { return false; }
778  int i;
779 };
780 
781 } // namespace
782 namespace std {
783 template <>
784 struct hash<ValueWithBoolConversion> {
785  size_t operator()(ValueWithBoolConversion v) { return v.i; }
786 };
787 } // namespace std
788 
789 namespace {
790 
791 TEST(HashTest, DoesNotUseImplicitConversionsToBool) {
792  EXPECT_NE(absl::Hash<ValueWithBoolConversion>()(ValueWithBoolConversion{0}),
793  absl::Hash<ValueWithBoolConversion>()(ValueWithBoolConversion{1}));
794 }
795 
796 } // namespace
int v
Definition: variant_test.cc:81
char * begin
static HashState Create(T *state)
Definition: hash.h:266
size_t operator()(ValueWithBoolConversion v)
Definition: hash_test.cc:785
static HashState combine(HashStatestate, const T &value, const Ts &...values)
EnumClass
Definition: hash_test.cc:90
std::ostream & operator<<(std::ostream &os, absl::LogSeverity s)
Definition: log_severity.cc:21
LegacyEnum
Definition: hash_test.cc:88
TYPED_TEST_SUITE_P(ConstructorTest)
SpyHashStateImpl< void > SpyHashState
#define X(c)
char * end
CONSTEXPR_F fields align(second_tag, fields f) noexcept
bool operator==(const absl::InlinedVector< T, N, A > &a, const absl::InlinedVector< T, N, A > &b)
char * ptr
H AbslHashValue(H h, const absl::InlinedVector< TheT, TheN, TheA > &a)
size_t value
static char data[kDataSize]
Definition: city_test.cc:31
hash_default_hash< typename T::first_type > hash
ABSL_MUST_USE_RESULT testing::AssertionResult VerifyTypeImplementsAbslHashCorrectly(const Container &values)
Definition: hash_testing.h:344
UnboundConversion o
Definition: parser_test.cc:86
typename type_traits_internal::VoidTImpl< Ts... >::type void_t
Definition: type_traits.h:171
InvokeTag
Definition: hash_test.cc:503
TYPED_TEST_P(ConstructorTest, NoArgs)
TEST(Symbolize, Unimplemented)
uint64_t b
Definition: layout_test.cc:50
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219
static bool Optional(bool)
Definition: demangle.cc:319
absl::hash_internal::Hash< T > Hash
Definition: hash.h:213
REGISTER_TYPED_TEST_CASE_P(ConstructorTest, NoArgs, BucketCount, BucketCountHash, BucketCountHashEqual, BucketCountHashEqualAlloc, BucketCountAlloc, BucketCountHashAlloc, Alloc, InputIteratorBucketHashEqualAlloc, InputIteratorBucketAlloc, InputIteratorBucketHashAlloc, CopyConstructor, CopyConstructorAlloc, MoveConstructor, MoveConstructorAlloc, InitializerListBucketHashEqualAlloc, InitializerListBucketAlloc, InitializerListBucketHashAlloc, Assignment, MoveAssignment, AssignmentFromInitializerList, AssignmentOverwritesExisting, MoveAssignmentOverwritesExisting, AssignmentFromInitializerListOverwritesExisting, AssignmentOnSelf)


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:19:56