flat_hash_map_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 
16 
22 #include "absl/types/any.h"
23 
24 namespace absl {
25 namespace container_internal {
26 namespace {
29 using ::testing::_;
30 using ::testing::Pair;
31 using ::testing::UnorderedElementsAre;
32 
33 template <class K, class V>
34 using Map = flat_hash_map<K, V, StatefulTestingHash, StatefulTestingEqual,
35  Alloc<std::pair<const K, V>>>;
36 
37 static_assert(!std::is_standard_layout<NonStandardLayout>(), "");
38 
39 using MapTypes =
40  ::testing::Types<Map<int, int>, Map<std::string, int>,
41  Map<Enum, std::string>, Map<EnumClass, int>,
42  Map<int, NonStandardLayout>, Map<NonStandardLayout, int>>;
43 
44 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashMap, ConstructorTest, MapTypes);
45 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashMap, LookupTest, MapTypes);
46 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashMap, MembersTest, MapTypes);
47 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashMap, ModifiersTest, MapTypes);
48 
49 TEST(FlatHashMap, StandardLayout) {
50  struct Int {
51  explicit Int(size_t value) : value(value) {}
52  Int() : value(0) { ADD_FAILURE(); }
53  Int(const Int& other) : value(other.value) { ADD_FAILURE(); }
54  Int(Int&&) = default;
55  bool operator==(const Int& other) const { return value == other.value; }
56  size_t value;
57  };
58  static_assert(std::is_standard_layout<Int>(), "");
59 
60  struct Hash {
61  size_t operator()(const Int& obj) const { return obj.value; }
62  };
63 
64  // Verify that neither the key nor the value get default-constructed or
65  // copy-constructed.
66  {
67  flat_hash_map<Int, Int, Hash> m;
68  m.try_emplace(Int(1), Int(2));
69  m.try_emplace(Int(3), Int(4));
70  m.erase(Int(1));
71  m.rehash(2 * m.bucket_count());
72  }
73  {
74  flat_hash_map<Int, Int, Hash> m;
75  m.try_emplace(Int(1), Int(2));
76  m.try_emplace(Int(3), Int(4));
77  m.erase(Int(1));
78  m.clear();
79  }
80 }
81 
82 // gcc becomes unhappy if this is inside the method, so pull it out here.
83 struct balast {};
84 
85 TEST(FlatHashMap, IteratesMsan) {
86  // Because SwissTable randomizes on pointer addresses, we keep old tables
87  // around to ensure we don't reuse old memory.
88  std::vector<absl::flat_hash_map<int, balast>> garbage;
89  for (int i = 0; i < 100; ++i) {
91  for (int j = 0; j < 100; ++j) {
92  t[j];
93  for (const auto& p : t) EXPECT_THAT(p, Pair(_, _));
94  }
95  garbage.push_back(std::move(t));
96  }
97 }
98 
99 // Demonstration of the "Lazy Key" pattern. This uses heterogeneous insert to
100 // avoid creating expensive key elements when the item is already present in the
101 // map.
102 struct LazyInt {
103  explicit LazyInt(size_t value, int* tracker)
104  : value(value), tracker(tracker) {}
105 
106  explicit operator size_t() const {
107  ++*tracker;
108  return value;
109  }
110 
111  size_t value;
112  int* tracker;
113 };
114 
115 struct Hash {
116  using is_transparent = void;
117  int* tracker;
118  size_t operator()(size_t obj) const {
119  ++*tracker;
120  return obj;
121  }
122  size_t operator()(const LazyInt& obj) const {
123  ++*tracker;
124  return obj.value;
125  }
126 };
127 
128 struct Eq {
129  using is_transparent = void;
130  bool operator()(size_t lhs, size_t rhs) const {
131  return lhs == rhs;
132  }
133  bool operator()(size_t lhs, const LazyInt& rhs) const {
134  return lhs == rhs.value;
135  }
136 };
137 
138 TEST(FlatHashMap, LazyKeyPattern) {
139  // hashes are only guaranteed in opt mode, we use assertions to track internal
140  // state that can cause extra calls to hash.
141  int conversions = 0;
142  int hashes = 0;
143  flat_hash_map<size_t, size_t, Hash, Eq> m(0, Hash{&hashes});
144  m.reserve(3);
145 
146  m[LazyInt(1, &conversions)] = 1;
147  EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 1)));
148  EXPECT_EQ(conversions, 1);
149 #ifdef NDEBUG
150  EXPECT_EQ(hashes, 1);
151 #endif
152 
153  m[LazyInt(1, &conversions)] = 2;
154  EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 2)));
155  EXPECT_EQ(conversions, 1);
156 #ifdef NDEBUG
157  EXPECT_EQ(hashes, 2);
158 #endif
159 
160  m.try_emplace(LazyInt(2, &conversions), 3);
161  EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 2), Pair(2, 3)));
162  EXPECT_EQ(conversions, 2);
163 #ifdef NDEBUG
164  EXPECT_EQ(hashes, 3);
165 #endif
166 
167  m.try_emplace(LazyInt(2, &conversions), 4);
168  EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 2), Pair(2, 3)));
169  EXPECT_EQ(conversions, 2);
170 #ifdef NDEBUG
171  EXPECT_EQ(hashes, 4);
172 #endif
173 }
174 
175 TEST(FlatHashMap, BitfieldArgument) {
176  union {
177  int n : 1;
178  };
179  n = 0;
180  flat_hash_map<int, int> m;
181  m.erase(n);
182  m.count(n);
183  m.prefetch(n);
184  m.find(n);
185  m.contains(n);
186  m.equal_range(n);
187  m.insert_or_assign(n, n);
188  m.insert_or_assign(m.end(), n, n);
189  m.try_emplace(n);
190  m.try_emplace(m.end(), n);
191  m.at(n);
192  m[n];
193 }
194 
195 TEST(FlatHashMap, MergeExtractInsert) {
196  // We can't test mutable keys, or non-copyable keys with flat_hash_map.
197  // Test that the nodes have the proper API.
198  absl::flat_hash_map<int, int> m = {{1, 7}, {2, 9}};
199  auto node = m.extract(1);
200  EXPECT_TRUE(node);
201  EXPECT_EQ(node.key(), 1);
202  EXPECT_EQ(node.mapped(), 7);
203  EXPECT_THAT(m, UnorderedElementsAre(Pair(2, 9)));
204 
205  node.mapped() = 17;
206  m.insert(std::move(node));
207  EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 17), Pair(2, 9)));
208 }
209 
210 #if (defined(ABSL_HAVE_STD_ANY) || !defined(_LIBCPP_VERSION)) && \
211  !defined(__EMSCRIPTEN__)
212 TEST(FlatHashMap, Any) {
214  m.emplace(1, 7);
215  auto it = m.find(1);
216  ASSERT_NE(it, m.end());
217  EXPECT_EQ(7, absl::any_cast<int>(it->second));
218 
219  m.emplace(std::piecewise_construct, std::make_tuple(2), std::make_tuple(8));
220  it = m.find(2);
221  ASSERT_NE(it, m.end());
222  EXPECT_EQ(8, absl::any_cast<int>(it->second));
223 
224  m.emplace(std::piecewise_construct, std::make_tuple(3),
225  std::make_tuple(absl::any(9)));
226  it = m.find(3);
227  ASSERT_NE(it, m.end());
228  EXPECT_EQ(9, absl::any_cast<int>(it->second));
229 
230  struct H {
231  size_t operator()(const absl::any&) const { return 0; }
232  };
233  struct E {
234  bool operator()(const absl::any&, const absl::any&) const { return true; }
235  };
237  m2.emplace(1, 7);
238  auto it2 = m2.find(1);
239  ASSERT_NE(it2, m2.end());
240  EXPECT_EQ(7, it2->second);
241 }
242 #endif // (defined(ABSL_HAVE_STD_ANY) || !defined(_LIBCPP_VERSION)) &&
243  // !defined(__EMSCRIPTEN__)
244 
245 } // namespace
246 } // namespace container_internal
247 } // namespace absl
int * tracker
EnumClass
Definition: hash_test.cc:90
TEST(NotificationTest, SanityTest)
Definition: algorithm.h:29
bool operator==(const absl::InlinedVector< T, N, A > &a, const absl::InlinedVector< T, N, A > &b)
Definition: any.h:214
size_t value
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:18