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::__anon4f39678b0111::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::__anon4f39678b0111::NonMovableKeyHash149   size_t operator()(const NonMovableKey& k) const { return k.i; }
operator ()absl::container_internal::__anon4f39678b0111::NonMovableKeyHash150   size_t operator()(int k) const { return k; }
151 };
152 struct NonMovableKeyEq {
153   using is_transparent = void;
operator ()absl::container_internal::__anon4f39678b0111::NonMovableKeyEq154   bool operator()(const NonMovableKey& a, const NonMovableKey& b) const {
155     return a.i == b.i;
156   }
operator ()absl::container_internal::__anon4f39678b0111::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 }  // namespace
258 }  // namespace container_internal
259 ABSL_NAMESPACE_END
260 }  // namespace absl
261