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/container/node_hash_map.h"
16
17 #include <cstddef>
18 #include <new>
19 #include <string>
20 #include <tuple>
21 #include <type_traits>
22 #include <utility>
23 #include <vector>
24
25 #include "gmock/gmock.h"
26 #include "gtest/gtest.h"
27 #include "absl/base/config.h"
28 #include "absl/container/internal/hash_policy_testing.h"
29 #include "absl/container/internal/tracked.h"
30 #include "absl/container/internal/unordered_map_constructor_test.h"
31 #include "absl/container/internal/unordered_map_lookup_test.h"
32 #include "absl/container/internal/unordered_map_members_test.h"
33 #include "absl/container/internal/unordered_map_modifiers_test.h"
34
35 namespace absl {
36 ABSL_NAMESPACE_BEGIN
37 namespace container_internal {
38 namespace {
39
40 using ::testing::Field;
41 using ::testing::IsEmpty;
42 using ::testing::Pair;
43 using ::testing::UnorderedElementsAre;
44 using ::testing::UnorderedElementsAreArray;
45
46 using MapTypes = ::testing::Types<
47 absl::node_hash_map<int, int, StatefulTestingHash, StatefulTestingEqual,
48 Alloc<std::pair<const int, int>>>,
49 absl::node_hash_map<std::string, std::string, StatefulTestingHash,
50 StatefulTestingEqual,
51 Alloc<std::pair<const std::string, std::string>>>>;
52
53 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ConstructorTest, MapTypes);
54 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, LookupTest, MapTypes);
55 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, MembersTest, MapTypes);
56 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ModifiersTest, MapTypes);
57
58 using M = absl::node_hash_map<std::string, Tracked<int>>;
59
TEST(NodeHashMap,Emplace)60 TEST(NodeHashMap, Emplace) {
61 M m;
62 Tracked<int> t(53);
63 m.emplace("a", t);
64 ASSERT_EQ(0, t.num_moves());
65 ASSERT_EQ(1, t.num_copies());
66
67 m.emplace(std::string("a"), t);
68 ASSERT_EQ(0, t.num_moves());
69 ASSERT_EQ(1, t.num_copies());
70
71 std::string a("a");
72 m.emplace(a, t);
73 ASSERT_EQ(0, t.num_moves());
74 ASSERT_EQ(1, t.num_copies());
75
76 const std::string ca("a");
77 m.emplace(a, t);
78 ASSERT_EQ(0, t.num_moves());
79 ASSERT_EQ(1, t.num_copies());
80
81 m.emplace(std::make_pair("a", t));
82 ASSERT_EQ(0, t.num_moves());
83 ASSERT_EQ(2, t.num_copies());
84
85 m.emplace(std::make_pair(std::string("a"), t));
86 ASSERT_EQ(0, t.num_moves());
87 ASSERT_EQ(3, t.num_copies());
88
89 std::pair<std::string, Tracked<int>> p("a", t);
90 ASSERT_EQ(0, t.num_moves());
91 ASSERT_EQ(4, t.num_copies());
92 m.emplace(p);
93 ASSERT_EQ(0, t.num_moves());
94 ASSERT_EQ(4, t.num_copies());
95
96 const std::pair<std::string, Tracked<int>> cp("a", t);
97 ASSERT_EQ(0, t.num_moves());
98 ASSERT_EQ(5, t.num_copies());
99 m.emplace(cp);
100 ASSERT_EQ(0, t.num_moves());
101 ASSERT_EQ(5, t.num_copies());
102
103 std::pair<const std::string, Tracked<int>> pc("a", t);
104 ASSERT_EQ(0, t.num_moves());
105 ASSERT_EQ(6, t.num_copies());
106 m.emplace(pc);
107 ASSERT_EQ(0, t.num_moves());
108 ASSERT_EQ(6, t.num_copies());
109
110 const std::pair<const std::string, Tracked<int>> cpc("a", t);
111 ASSERT_EQ(0, t.num_moves());
112 ASSERT_EQ(7, t.num_copies());
113 m.emplace(cpc);
114 ASSERT_EQ(0, t.num_moves());
115 ASSERT_EQ(7, t.num_copies());
116
117 m.emplace(std::piecewise_construct, std::forward_as_tuple("a"),
118 std::forward_as_tuple(t));
119 ASSERT_EQ(0, t.num_moves());
120 ASSERT_EQ(7, t.num_copies());
121
122 m.emplace(std::piecewise_construct, std::forward_as_tuple(std::string("a")),
123 std::forward_as_tuple(t));
124 ASSERT_EQ(0, t.num_moves());
125 ASSERT_EQ(7, t.num_copies());
126 }
127
TEST(NodeHashMap,AssignRecursive)128 TEST(NodeHashMap, AssignRecursive) {
129 struct Tree {
130 // Verify that unordered_map<K, IncompleteType> can be instantiated.
131 absl::node_hash_map<int, Tree> children;
132 };
133 Tree root;
134 const Tree& child = root.children.emplace().first->second;
135 // Verify that `lhs = rhs` doesn't read rhs after clearing lhs.
136 root = child;
137 }
138
TEST(FlatHashMap,MoveOnlyKey)139 TEST(FlatHashMap, MoveOnlyKey) {
140 struct Key {
141 Key() = default;
142 Key(Key&&) = default;
143 Key& operator=(Key&&) = default;
144 };
145 struct Eq {
146 bool operator()(const Key&, const Key&) const { return true; }
147 };
148 struct Hash {
149 size_t operator()(const Key&) const { return 0; }
150 };
151 absl::node_hash_map<Key, int, Hash, Eq> m;
152 m[Key()];
153 }
154
155 struct NonMovableKey {
NonMovableKeyabsl::container_internal::__anonee0e9c720111::NonMovableKey156 explicit NonMovableKey(int i) : i(i) {}
157 NonMovableKey(NonMovableKey&&) = delete;
158 int i;
159 };
160 struct NonMovableKeyHash {
161 using is_transparent = void;
operator ()absl::container_internal::__anonee0e9c720111::NonMovableKeyHash162 size_t operator()(const NonMovableKey& k) const { return k.i; }
operator ()absl::container_internal::__anonee0e9c720111::NonMovableKeyHash163 size_t operator()(int k) const { return k; }
164 };
165 struct NonMovableKeyEq {
166 using is_transparent = void;
operator ()absl::container_internal::__anonee0e9c720111::NonMovableKeyEq167 bool operator()(const NonMovableKey& a, const NonMovableKey& b) const {
168 return a.i == b.i;
169 }
operator ()absl::container_internal::__anonee0e9c720111::NonMovableKeyEq170 bool operator()(const NonMovableKey& a, int b) const { return a.i == b; }
171 };
172
TEST(NodeHashMap,MergeExtractInsert)173 TEST(NodeHashMap, MergeExtractInsert) {
174 absl::node_hash_map<NonMovableKey, int, NonMovableKeyHash, NonMovableKeyEq>
175 set1, set2;
176 set1.emplace(std::piecewise_construct, std::make_tuple(7),
177 std::make_tuple(-7));
178 set1.emplace(std::piecewise_construct, std::make_tuple(17),
179 std::make_tuple(-17));
180
181 set2.emplace(std::piecewise_construct, std::make_tuple(7),
182 std::make_tuple(-70));
183 set2.emplace(std::piecewise_construct, std::make_tuple(19),
184 std::make_tuple(-190));
185
186 auto Elem = [](int key, int value) {
187 return Pair(Field(&NonMovableKey::i, key), value);
188 };
189
190 EXPECT_THAT(set1, UnorderedElementsAre(Elem(7, -7), Elem(17, -17)));
191 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(19, -190)));
192
193 // NonMovableKey is neither copyable nor movable. We should still be able to
194 // move nodes around.
195 static_assert(!std::is_move_constructible<NonMovableKey>::value, "");
196 set1.merge(set2);
197
198 EXPECT_THAT(set1,
199 UnorderedElementsAre(Elem(7, -7), Elem(17, -17), Elem(19, -190)));
200 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
201
202 auto node = set1.extract(7);
203 EXPECT_TRUE(node);
204 EXPECT_EQ(node.key().i, 7);
205 EXPECT_EQ(node.mapped(), -7);
206 EXPECT_THAT(set1, UnorderedElementsAre(Elem(17, -17), Elem(19, -190)));
207
208 auto insert_result = set2.insert(std::move(node));
209 EXPECT_FALSE(node);
210 EXPECT_FALSE(insert_result.inserted);
211 EXPECT_TRUE(insert_result.node);
212 EXPECT_EQ(insert_result.node.key().i, 7);
213 EXPECT_EQ(insert_result.node.mapped(), -7);
214 EXPECT_THAT(*insert_result.position, Elem(7, -70));
215 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
216
217 node = set1.extract(17);
218 EXPECT_TRUE(node);
219 EXPECT_EQ(node.key().i, 17);
220 EXPECT_EQ(node.mapped(), -17);
221 EXPECT_THAT(set1, UnorderedElementsAre(Elem(19, -190)));
222
223 node.mapped() = 23;
224
225 insert_result = set2.insert(std::move(node));
226 EXPECT_FALSE(node);
227 EXPECT_TRUE(insert_result.inserted);
228 EXPECT_FALSE(insert_result.node);
229 EXPECT_THAT(*insert_result.position, Elem(17, 23));
230 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(17, 23)));
231 }
232
FirstIsEven(std::pair<const int,int> p)233 bool FirstIsEven(std::pair<const int, int> p) { return p.first % 2 == 0; }
234
TEST(NodeHashMap,EraseIf)235 TEST(NodeHashMap, EraseIf) {
236 // Erase all elements.
237 {
238 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
239 EXPECT_EQ(erase_if(s, [](std::pair<const int, int>) { return true; }), 5);
240 EXPECT_THAT(s, IsEmpty());
241 }
242 // Erase no elements.
243 {
244 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
245 EXPECT_EQ(erase_if(s, [](std::pair<const int, int>) { return false; }), 0);
246 EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3),
247 Pair(4, 4), Pair(5, 5)));
248 }
249 // Erase specific elements.
250 {
251 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
252 EXPECT_EQ(erase_if(s,
253 [](std::pair<const int, int> kvp) {
254 return kvp.first % 2 == 1;
255 }),
256 3);
257 EXPECT_THAT(s, UnorderedElementsAre(Pair(2, 2), Pair(4, 4)));
258 }
259 // Predicate is function reference.
260 {
261 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
262 EXPECT_EQ(erase_if(s, FirstIsEven), 2);
263 EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5)));
264 }
265 // Predicate is function pointer.
266 {
267 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
268 EXPECT_EQ(erase_if(s, &FirstIsEven), 2);
269 EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5)));
270 }
271 }
272
TEST(NodeHashMap,CForEach)273 TEST(NodeHashMap, CForEach) {
274 node_hash_map<int, int> m;
275 std::vector<std::pair<int, int>> expected;
276 for (int i = 0; i < 100; ++i) {
277 {
278 SCOPED_TRACE("mutable object iteration");
279 std::vector<std::pair<int, int>> v;
280 absl::container_internal::c_for_each_fast(
281 m, [&v](std::pair<const int, int>& p) { v.push_back(p); });
282 EXPECT_THAT(v, UnorderedElementsAreArray(expected));
283 }
284 {
285 SCOPED_TRACE("const object iteration");
286 std::vector<std::pair<int, int>> v;
287 const node_hash_map<int, int>& cm = m;
288 absl::container_internal::c_for_each_fast(
289 cm, [&v](const std::pair<const int, int>& p) { v.push_back(p); });
290 EXPECT_THAT(v, UnorderedElementsAreArray(expected));
291 }
292 {
293 SCOPED_TRACE("const object iteration");
294 std::vector<std::pair<int, int>> v;
295 absl::container_internal::c_for_each_fast(
296 node_hash_map<int, int>(m),
297 [&v](std::pair<const int, int>& p) { v.push_back(p); });
298 EXPECT_THAT(v, UnorderedElementsAreArray(expected));
299 }
300 m[i] = i;
301 expected.emplace_back(i, i);
302 }
303 }
304
TEST(NodeHashMap,CForEachMutate)305 TEST(NodeHashMap, CForEachMutate) {
306 node_hash_map<int, int> s;
307 std::vector<std::pair<int, int>> expected;
308 for (int i = 0; i < 100; ++i) {
309 std::vector<std::pair<int, int>> v;
310 absl::container_internal::c_for_each_fast(
311 s, [&v](std::pair<const int, int>& p) {
312 v.push_back(p);
313 p.second++;
314 });
315 EXPECT_THAT(v, UnorderedElementsAreArray(expected));
316 for (auto& p : expected) {
317 p.second++;
318 }
319 EXPECT_THAT(s, UnorderedElementsAreArray(expected));
320 s[i] = i;
321 expected.emplace_back(i, i);
322 }
323 }
324
325 // This test requires std::launder for mutable key access in node handles.
326 #if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
TEST(NodeHashMap,NodeHandleMutableKeyAccess)327 TEST(NodeHashMap, NodeHandleMutableKeyAccess) {
328 node_hash_map<std::string, std::string> map;
329
330 map["key1"] = "mapped";
331
332 auto nh = map.extract(map.begin());
333 nh.key().resize(3);
334 map.insert(std::move(nh));
335
336 EXPECT_THAT(map, testing::ElementsAre(Pair("key", "mapped")));
337 }
338 #endif
339
TEST(NodeHashMap,RecursiveTypeCompiles)340 TEST(NodeHashMap, RecursiveTypeCompiles) {
341 struct RecursiveType {
342 node_hash_map<int, RecursiveType> m;
343 };
344 RecursiveType t;
345 t.m[0] = RecursiveType{};
346 }
347
348 } // namespace
349 } // namespace container_internal
350 ABSL_NAMESPACE_END
351 } // namespace absl
352