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 "absl/container/internal/tracked.h"
18 #include "absl/container/internal/unordered_map_constructor_test.h"
19 #include "absl/container/internal/unordered_map_lookup_test.h"
20 #include "absl/container/internal/unordered_map_members_test.h"
21 #include "absl/container/internal/unordered_map_modifiers_test.h"
22
23 namespace absl {
24 ABSL_NAMESPACE_BEGIN
25 namespace container_internal {
26 namespace {
27
28 using ::testing::Field;
29 using ::testing::IsEmpty;
30 using ::testing::Pair;
31 using ::testing::UnorderedElementsAre;
32
33 using MapTypes = ::testing::Types<
34 absl::node_hash_map<int, int, StatefulTestingHash, StatefulTestingEqual,
35 Alloc<std::pair<const int, int>>>,
36 absl::node_hash_map<std::string, std::string, StatefulTestingHash,
37 StatefulTestingEqual,
38 Alloc<std::pair<const std::string, std::string>>>>;
39
40 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ConstructorTest, MapTypes);
41 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, LookupTest, MapTypes);
42 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, MembersTest, MapTypes);
43 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ModifiersTest, MapTypes);
44
45 using M = absl::node_hash_map<std::string, Tracked<int>>;
46
TEST(NodeHashMap,Emplace)47 TEST(NodeHashMap, Emplace) {
48 M m;
49 Tracked<int> t(53);
50 m.emplace("a", t);
51 ASSERT_EQ(0, t.num_moves());
52 ASSERT_EQ(1, t.num_copies());
53
54 m.emplace(std::string("a"), t);
55 ASSERT_EQ(0, t.num_moves());
56 ASSERT_EQ(1, t.num_copies());
57
58 std::string a("a");
59 m.emplace(a, t);
60 ASSERT_EQ(0, t.num_moves());
61 ASSERT_EQ(1, t.num_copies());
62
63 const std::string ca("a");
64 m.emplace(a, t);
65 ASSERT_EQ(0, t.num_moves());
66 ASSERT_EQ(1, t.num_copies());
67
68 m.emplace(std::make_pair("a", t));
69 ASSERT_EQ(0, t.num_moves());
70 ASSERT_EQ(2, t.num_copies());
71
72 m.emplace(std::make_pair(std::string("a"), t));
73 ASSERT_EQ(0, t.num_moves());
74 ASSERT_EQ(3, t.num_copies());
75
76 std::pair<std::string, Tracked<int>> p("a", t);
77 ASSERT_EQ(0, t.num_moves());
78 ASSERT_EQ(4, t.num_copies());
79 m.emplace(p);
80 ASSERT_EQ(0, t.num_moves());
81 ASSERT_EQ(4, t.num_copies());
82
83 const std::pair<std::string, Tracked<int>> cp("a", t);
84 ASSERT_EQ(0, t.num_moves());
85 ASSERT_EQ(5, t.num_copies());
86 m.emplace(cp);
87 ASSERT_EQ(0, t.num_moves());
88 ASSERT_EQ(5, t.num_copies());
89
90 std::pair<const std::string, Tracked<int>> pc("a", t);
91 ASSERT_EQ(0, t.num_moves());
92 ASSERT_EQ(6, t.num_copies());
93 m.emplace(pc);
94 ASSERT_EQ(0, t.num_moves());
95 ASSERT_EQ(6, t.num_copies());
96
97 const std::pair<const std::string, Tracked<int>> cpc("a", t);
98 ASSERT_EQ(0, t.num_moves());
99 ASSERT_EQ(7, t.num_copies());
100 m.emplace(cpc);
101 ASSERT_EQ(0, t.num_moves());
102 ASSERT_EQ(7, t.num_copies());
103
104 m.emplace(std::piecewise_construct, std::forward_as_tuple("a"),
105 std::forward_as_tuple(t));
106 ASSERT_EQ(0, t.num_moves());
107 ASSERT_EQ(7, t.num_copies());
108
109 m.emplace(std::piecewise_construct, std::forward_as_tuple(std::string("a")),
110 std::forward_as_tuple(t));
111 ASSERT_EQ(0, t.num_moves());
112 ASSERT_EQ(7, t.num_copies());
113 }
114
TEST(NodeHashMap,AssignRecursive)115 TEST(NodeHashMap, AssignRecursive) {
116 struct Tree {
117 // Verify that unordered_map<K, IncompleteType> can be instantiated.
118 absl::node_hash_map<int, Tree> children;
119 };
120 Tree root;
121 const Tree& child = root.children.emplace().first->second;
122 // Verify that `lhs = rhs` doesn't read rhs after clearing lhs.
123 root = child;
124 }
125
TEST(FlatHashMap,MoveOnlyKey)126 TEST(FlatHashMap, MoveOnlyKey) {
127 struct Key {
128 Key() = default;
129 Key(Key&&) = default;
130 Key& operator=(Key&&) = default;
131 };
132 struct Eq {
133 bool operator()(const Key&, const Key&) const { return true; }
134 };
135 struct Hash {
136 size_t operator()(const Key&) const { return 0; }
137 };
138 absl::node_hash_map<Key, int, Hash, Eq> m;
139 m[Key()];
140 }
141
142 struct NonMovableKey {
NonMovableKeyabsl::container_internal::__anon12914f0f0111::NonMovableKey143 explicit NonMovableKey(int i) : i(i) {}
144 NonMovableKey(NonMovableKey&&) = delete;
145 int i;
146 };
147 struct NonMovableKeyHash {
148 using is_transparent = void;
operator ()absl::container_internal::__anon12914f0f0111::NonMovableKeyHash149 size_t operator()(const NonMovableKey& k) const { return k.i; }
operator ()absl::container_internal::__anon12914f0f0111::NonMovableKeyHash150 size_t operator()(int k) const { return k; }
151 };
152 struct NonMovableKeyEq {
153 using is_transparent = void;
operator ()absl::container_internal::__anon12914f0f0111::NonMovableKeyEq154 bool operator()(const NonMovableKey& a, const NonMovableKey& b) const {
155 return a.i == b.i;
156 }
operator ()absl::container_internal::__anon12914f0f0111::NonMovableKeyEq157 bool operator()(const NonMovableKey& a, int b) const { return a.i == b; }
158 };
159
TEST(NodeHashMap,MergeExtractInsert)160 TEST(NodeHashMap, MergeExtractInsert) {
161 absl::node_hash_map<NonMovableKey, int, NonMovableKeyHash, NonMovableKeyEq>
162 set1, set2;
163 set1.emplace(std::piecewise_construct, std::make_tuple(7),
164 std::make_tuple(-7));
165 set1.emplace(std::piecewise_construct, std::make_tuple(17),
166 std::make_tuple(-17));
167
168 set2.emplace(std::piecewise_construct, std::make_tuple(7),
169 std::make_tuple(-70));
170 set2.emplace(std::piecewise_construct, std::make_tuple(19),
171 std::make_tuple(-190));
172
173 auto Elem = [](int key, int value) {
174 return Pair(Field(&NonMovableKey::i, key), value);
175 };
176
177 EXPECT_THAT(set1, UnorderedElementsAre(Elem(7, -7), Elem(17, -17)));
178 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(19, -190)));
179
180 // NonMovableKey is neither copyable nor movable. We should still be able to
181 // move nodes around.
182 static_assert(!std::is_move_constructible<NonMovableKey>::value, "");
183 set1.merge(set2);
184
185 EXPECT_THAT(set1,
186 UnorderedElementsAre(Elem(7, -7), Elem(17, -17), Elem(19, -190)));
187 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
188
189 auto node = set1.extract(7);
190 EXPECT_TRUE(node);
191 EXPECT_EQ(node.key().i, 7);
192 EXPECT_EQ(node.mapped(), -7);
193 EXPECT_THAT(set1, UnorderedElementsAre(Elem(17, -17), Elem(19, -190)));
194
195 auto insert_result = set2.insert(std::move(node));
196 EXPECT_FALSE(node);
197 EXPECT_FALSE(insert_result.inserted);
198 EXPECT_TRUE(insert_result.node);
199 EXPECT_EQ(insert_result.node.key().i, 7);
200 EXPECT_EQ(insert_result.node.mapped(), -7);
201 EXPECT_THAT(*insert_result.position, Elem(7, -70));
202 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
203
204 node = set1.extract(17);
205 EXPECT_TRUE(node);
206 EXPECT_EQ(node.key().i, 17);
207 EXPECT_EQ(node.mapped(), -17);
208 EXPECT_THAT(set1, UnorderedElementsAre(Elem(19, -190)));
209
210 node.mapped() = 23;
211
212 insert_result = set2.insert(std::move(node));
213 EXPECT_FALSE(node);
214 EXPECT_TRUE(insert_result.inserted);
215 EXPECT_FALSE(insert_result.node);
216 EXPECT_THAT(*insert_result.position, Elem(17, 23));
217 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(17, 23)));
218 }
219
FirstIsEven(std::pair<const int,int> p)220 bool FirstIsEven(std::pair<const int, int> p) { return p.first % 2 == 0; }
221
TEST(NodeHashMap,EraseIf)222 TEST(NodeHashMap, EraseIf) {
223 // Erase all elements.
224 {
225 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
226 erase_if(s, [](std::pair<const int, int>) { return true; });
227 EXPECT_THAT(s, IsEmpty());
228 }
229 // Erase no elements.
230 {
231 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
232 erase_if(s, [](std::pair<const int, int>) { return false; });
233 EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3),
234 Pair(4, 4), Pair(5, 5)));
235 }
236 // Erase specific elements.
237 {
238 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
239 erase_if(s,
240 [](std::pair<const int, int> kvp) { return kvp.first % 2 == 1; });
241 EXPECT_THAT(s, UnorderedElementsAre(Pair(2, 2), Pair(4, 4)));
242 }
243 // Predicate is function reference.
244 {
245 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
246 erase_if(s, FirstIsEven);
247 EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5)));
248 }
249 // Predicate is function pointer.
250 {
251 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
252 erase_if(s, &FirstIsEven);
253 EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5)));
254 }
255 }
256
257 // This test requires std::launder for mutable key access in node handles.
258 #if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
TEST(NodeHashMap,NodeHandleMutableKeyAccess)259 TEST(NodeHashMap, NodeHandleMutableKeyAccess) {
260 node_hash_map<std::string, std::string> map;
261
262 map["key1"] = "mapped";
263
264 auto nh = map.extract(map.begin());
265 nh.key().resize(3);
266 map.insert(std::move(nh));
267
268 EXPECT_THAT(map, testing::ElementsAre(Pair("key", "mapped")));
269 }
270 #endif
271
272 } // namespace
273 } // namespace container_internal
274 ABSL_NAMESPACE_END
275 } // namespace absl
276