Debian Codegraph @

tests/node_hash_map_test.cc

raw
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 #ifndef THIS_HASH_MAP
16 #define THIS_HASH_MAP node_hash_map
17 #define THIS_TEST_NAME NodeHashMap
18 #endif
19
20 #include "parallel_hashmap/phmap.h"
21
22 #include "tracked.h"
23 #include "unordered_map_constructor_test.h"
24 #include "unordered_map_lookup_test.h"
25 #include "unordered_map_members_test.h"
26 #include "unordered_map_modifiers_test.h"
27
28 namespace phmap {
29 namespace priv {
30 namespace {
31
32 using ::testing::Field;
33 using ::testing::Pair;
34 using ::testing::UnorderedElementsAre;
35
36 using MapTypes = ::testing::Types<
37 phmap::THIS_HASH_MAP<int, int, StatefulTestingHash, StatefulTestingEqual,
38 Alloc<std::pair<const int, int>>>,
39 phmap::THIS_HASH_MAP<std::string, std::string, StatefulTestingHash,
40 StatefulTestingEqual,
41 Alloc<std::pair<const std::string, std::string>>>>;
42
43 INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, ConstructorTest, MapTypes);
44 INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, LookupTest, MapTypes);
45 INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, MembersTest, MapTypes);
46 INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, ModifiersTest, MapTypes);
47
48 using M = phmap::THIS_HASH_MAP<std::string, Tracked<int>>;
49
50 TEST(THIS_TEST_NAME, Emplace) {
51 M m;
52 Tracked<int> t(53);
53 m.emplace("a", t);
54 ASSERT_EQ(0, t.num_moves());
55 ASSERT_EQ(1, t.num_copies());
56
57 m.emplace(std::string("a"), t);
58 ASSERT_EQ(0, t.num_moves());
59 ASSERT_EQ(1, t.num_copies());
60
61 std::string a("a");
62 m.emplace(a, t);
63 ASSERT_EQ(0, t.num_moves());
64 ASSERT_EQ(1, t.num_copies());
65
66 const std::string ca("a");
67 m.emplace(a, t);
68 ASSERT_EQ(0, t.num_moves());
69 ASSERT_EQ(1, t.num_copies());
70
71 m.emplace(std::make_pair("a", t));
72 ASSERT_EQ(0, t.num_moves());
73 ASSERT_EQ(2, t.num_copies());
74
75 m.emplace(std::make_pair(std::string("a"), t));
76 ASSERT_EQ(0, t.num_moves());
77 ASSERT_EQ(3, t.num_copies());
78
79 std::pair<std::string, Tracked<int>> p("a", t);
80 ASSERT_EQ(0, t.num_moves());
81 ASSERT_EQ(4, t.num_copies());
82 m.emplace(p);
83 ASSERT_EQ(0, t.num_moves());
84 ASSERT_EQ(4, t.num_copies());
85
86 const std::pair<std::string, Tracked<int>> cp("a", t);
87 ASSERT_EQ(0, t.num_moves());
88 ASSERT_EQ(5, t.num_copies());
89 m.emplace(cp);
90 ASSERT_EQ(0, t.num_moves());
91 ASSERT_EQ(5, t.num_copies());
92
93 std::pair<const std::string, Tracked<int>> pc("a", t);
94 ASSERT_EQ(0, t.num_moves());
95 ASSERT_EQ(6, t.num_copies());
96 m.emplace(pc);
97 ASSERT_EQ(0, t.num_moves());
98 ASSERT_EQ(6, t.num_copies());
99
100 const std::pair<const std::string, Tracked<int>> cpc("a", t);
101 ASSERT_EQ(0, t.num_moves());
102 ASSERT_EQ(7, t.num_copies());
103 m.emplace(cpc);
104 ASSERT_EQ(0, t.num_moves());
105 ASSERT_EQ(7, t.num_copies());
106
107 m.emplace(std::piecewise_construct, std::forward_as_tuple("a"),
108 std::forward_as_tuple(t));
109 ASSERT_EQ(0, t.num_moves());
110 ASSERT_EQ(7, t.num_copies());
111
112 m.emplace(std::piecewise_construct, std::forward_as_tuple(std::string("a")),
113 std::forward_as_tuple(t));
114 ASSERT_EQ(0, t.num_moves());
115 ASSERT_EQ(7, t.num_copies());
116 }
117
118 TEST(THIS_TEST_NAME, AssignRecursive) {
119 struct Tree {
120 // Verify that unordered_map<K, IncompleteType> can be instantiated.
121 phmap::THIS_HASH_MAP<int, Tree> children;
122 };
123 Tree root;
124 const Tree& child = root.children.emplace().first->second;
125 // Verify that `lhs = rhs` doesn't read rhs after clearing lhs.
126 root = child;
127 }
128
129 TEST(FlatHashMap, MoveOnlyKey) {
130 struct Key {
131 Key() = default;
132 Key(Key&&) = default;
133 Key& operator=(Key&&) = default;
134 };
135 struct Eq {
136 bool operator()(const Key&, const Key&) const { return true; }
137 };
138 struct Hash {
139 size_t operator()(const Key&) const { return 0; }
140 };
141 phmap::THIS_HASH_MAP<Key, int, Hash, Eq> m;
142 m[Key()];
143 }
144
145 struct NonMovableKey {
146 explicit NonMovableKey(int i_) : i(i_) {}
147 NonMovableKey(NonMovableKey&&) = delete;
148 int i;
149 };
150 struct NonMovableKeyHash {
151 using is_transparent = void;
152 size_t operator()(const NonMovableKey& k) const { return k.i; }
153 size_t operator()(int k) const { return k; }
154 };
155 struct NonMovableKeyEq {
156 using is_transparent = void;
157 bool operator()(const NonMovableKey& a, const NonMovableKey& b) const {
158 return a.i == b.i;
159 }
160 bool operator()(const NonMovableKey& a, int b) const { return a.i == b; }
161 };
162
163 TEST(THIS_TEST_NAME, MergeExtractInsert) {
164 phmap::THIS_HASH_MAP<NonMovableKey, int, NonMovableKeyHash, NonMovableKeyEq>
165 set1, set2;
166 set1.emplace(std::piecewise_construct, std::make_tuple(7),
167 std::make_tuple(-7));
168 set1.emplace(std::piecewise_construct, std::make_tuple(17),
169 std::make_tuple(-17));
170
171 set2.emplace(std::piecewise_construct, std::make_tuple(7),
172 std::make_tuple(-70));
173 set2.emplace(std::piecewise_construct, std::make_tuple(19),
174 std::make_tuple(-190));
175
176 auto Elem = [](int key, int value) {
177 return Pair(Field(&NonMovableKey::i, key), value);
178 };
179
180 EXPECT_THAT(set1, UnorderedElementsAre(Elem(7, -7), Elem(17, -17)));
181 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(19, -190)));
182
183 // NonMovableKey is neither copyable nor movable. We should still be able to
184 // move nodes around.
185 static_assert(!std::is_move_constructible<NonMovableKey>::value, "");
186 set1.merge(set2);
187
188 EXPECT_THAT(set1,
189 UnorderedElementsAre(Elem(7, -7), Elem(17, -17), Elem(19, -190)));
190 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
191
192 auto node = set1.extract(7);
193 EXPECT_TRUE(node);
194 EXPECT_EQ(node.key().i, 7);
195 EXPECT_EQ(node.mapped(), -7);
196 EXPECT_THAT(set1, UnorderedElementsAre(Elem(17, -17), Elem(19, -190)));
197
198 auto insert_result = set2.insert(std::move(node));
199 EXPECT_FALSE(node);
200 EXPECT_FALSE(insert_result.inserted);
201 EXPECT_TRUE(insert_result.node);
202 EXPECT_EQ(insert_result.node.key().i, 7);
203 EXPECT_EQ(insert_result.node.mapped(), -7);
204 EXPECT_THAT(*insert_result.position, Elem(7, -70));
205 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
206
207 node = set1.extract(17);
208 EXPECT_TRUE(node);
209 EXPECT_EQ(node.key().i, 17);
210 EXPECT_EQ(node.mapped(), -17);
211 EXPECT_THAT(set1, UnorderedElementsAre(Elem(19, -190)));
212
213 node.mapped() = 23;
214
215 insert_result = set2.insert(std::move(node));
216 EXPECT_FALSE(node);
217 EXPECT_TRUE(insert_result.inserted);
218 EXPECT_FALSE(insert_result.node);
219 EXPECT_THAT(*insert_result.position, Elem(17, 23));
220 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(17, 23)));
221 }
222
223 } // namespace
224 } // namespace priv
225 } // namespace phmap