Debian Codegraph @

tests/flat_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 flat_hash_map
17 #define THIS_TEST_NAME FlatHashMap
18 #define ORIG_FLAT_HASH_MAP 1
19 #endif
20
21 #ifndef THIS_EXTRA_TPL_PARAMS
22 #define THIS_EXTRA_TPL_PARAMS
23 #endif
24
25 #ifndef THIS_EXTRA_TPL_PARAMS_NULLMUTEX
26 #define THIS_EXTRA_TPL_PARAMS_NULLMUTEX
27 #endif
28
29 #include "parallel_hashmap/phmap.h"
30
31 #if defined(PHMAP_HAVE_STD_ANY)
32 #include <any>
33 #endif
34
35 #ifdef _MSC_VER
36 #pragma warning(push)
37 #pragma warning(disable: 4710 4711)
38 #endif
39
40 #include "hash_generator_testing.h"
41 #include "unordered_map_constructor_test.h"
42 #include "unordered_map_lookup_test.h"
43 #include "unordered_map_members_test.h"
44 #include "unordered_map_modifiers_test.h"
45
46 #ifdef _MSC_VER
47 #pragma warning(pop)
48 #endif
49
50 namespace phmap {
51 namespace priv {
52 namespace {
53 using ::phmap::priv::hash_internal::Enum;
54 using ::phmap::priv::hash_internal::EnumClass;
55 using ::testing::_;
56 using ::testing::Pair;
57 using ::testing::UnorderedElementsAre;
58
59 template <class K, class V>
60 using Map = THIS_HASH_MAP<K, V, StatefulTestingHash, StatefulTestingEqual,
61 Alloc<std::pair<const K, V>> THIS_EXTRA_TPL_PARAMS>;
62
63
64 template <class K, class V, class H = phmap::priv::hash_default_hash<K>,
65 class Eq = phmap::priv::hash_default_eq<K>,
66 class Alloc = phmap::priv::Allocator<
67 phmap::priv::Pair<const K, V>>>
68 using ThisMap = THIS_HASH_MAP<K, V, H, Eq, Alloc THIS_EXTRA_TPL_PARAMS>;
69
70 template <class K, class V, class H = phmap::priv::hash_default_hash<K>,
71 class Eq = phmap::priv::hash_default_eq<K>,
72 class Alloc = phmap::priv::Allocator<
73 phmap::priv::Pair<const K, V>>>
74 using ThisMap_NullMutex = THIS_HASH_MAP<K, V, H, Eq, Alloc THIS_EXTRA_TPL_PARAMS_NULLMUTEX>;
75
76 static_assert(!std::is_standard_layout<NonStandardLayout>(), "");
77
78 using MapTypes =
79 ::testing::Types<Map<int, int>, Map<std::string, int>,
80 Map<Enum, std::string>, Map<EnumClass, int>,
81 Map<int, NonStandardLayout>, Map<NonStandardLayout, int>>;
82
83 INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, ConstructorTest, MapTypes);
84 INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, LookupTest, MapTypes);
85 INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, MembersTest, MapTypes);
86 INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, ModifiersTest, MapTypes);
87
88
89
90 TEST(THIS_TEST_NAME, StandardLayout) {
91 struct Int {
92 explicit Int(size_t val) : value(val) {}
93 Int() : value(0) { ADD_FAILURE(); }
94 Int(const Int& other) : value(other.value) { ADD_FAILURE(); }
95 Int(Int&&) = default;
96 bool operator==(const Int& other) const { return value == other.value; }
97 size_t value;
98 };
99 static_assert(std::is_standard_layout<Int>(), "");
100
101 struct Hash {
102 size_t operator()(const Int& obj) const { return obj.value; }
103 };
104
105 // Verify that neither the key nor the value get default-constructed or
106 // copy-constructed.
107 {
108 ThisMap<Int, Int, Hash> m;
109 m.try_emplace(Int(1), Int(2));
110 m.try_emplace(Int(3), Int(4));
111 m.erase(Int(1));
112 m.rehash(2 * m.bucket_count());
113 }
114 {
115 ThisMap<Int, Int, Hash> m;
116 m.try_emplace(Int(1), Int(2));
117 m.try_emplace(Int(3), Int(4));
118 m.erase(Int(1));
119 m.clear();
120 }
121 }
122
123 // gcc becomes unhappy if this is inside the method, so pull it out here.
124 struct balast {};
125
126 TEST(THIS_TEST_NAME, IteratesMsan) {
127 // Because SwissTable randomizes on pointer addresses, we keep old tables
128 // around to ensure we don't reuse old memory.
129 std::vector<ThisMap<int, balast>> garbage;
130 for (int i = 0; i < 100; ++i) {
131 ThisMap<int, balast> t;
132 for (int j = 0; j < 100; ++j) {
133 t[j];
134 for (const auto& p : t) EXPECT_THAT(p, Pair(_, _));
135 }
136 garbage.push_back(std::move(t));
137 }
138 }
139
140 // Demonstration of the "Lazy Key" pattern. This uses heterogeneous insert to
141 // avoid creating expensive key elements when the item is already present in the
142 // map.
143 struct LazyInt {
144 explicit LazyInt(size_t val, int* tracker_)
145 : value(val), tracker(tracker_) {}
146
147 explicit operator size_t() const {
148 ++*tracker;
149 return value;
150 }
151
152 size_t value;
153 int* tracker;
154 };
155
156 struct Hash {
157 using is_transparent = void;
158 int* tracker;
159 size_t operator()(size_t obj) const {
160 ++*tracker;
161 return obj;
162 }
163 size_t operator()(const LazyInt& obj) const {
164 ++*tracker;
165 return obj.value;
166 }
167 };
168
169 struct Eq {
170 using is_transparent = void;
171 bool operator()(size_t lhs, size_t rhs) const {
172 return lhs == rhs;
173 }
174 bool operator()(size_t lhs, const LazyInt& rhs) const {
175 return lhs == rhs.value;
176 }
177 };
178
179 TEST(THIS_TEST_NAME, PtrKet) {
180 using H = ThisMap<void *, bool>;
181 H hash;
182 int a, b;
183 hash.insert(H::value_type(&a, true));
184 hash.insert(H::value_type(&b, false));
185 }
186
187 TEST(THIS_TEST_NAME, LazyKeyPattern) {
188 // hashes are only guaranteed in opt mode, we use assertions to track internal
189 // state that can cause extra calls to hash.
190 int conversions = 0;
191 int hashes = 0;
192 ThisMap<size_t, size_t, Hash, Eq> m(0, Hash{&hashes});
193 m.reserve(3);
194
195 m[LazyInt(1, &conversions)] = 1;
196 EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 1)));
197 EXPECT_EQ(conversions, 1);
198 #ifdef NDEBUG
199 EXPECT_EQ(hashes, 1);
200 #endif
201
202 m[LazyInt(1, &conversions)] = 2;
203 EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 2)));
204 EXPECT_EQ(conversions, 1);
205 #ifdef NDEBUG
206 EXPECT_EQ(hashes, 2);
207 #endif
208
209 m.try_emplace(LazyInt(2, &conversions), 3);
210 EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 2), Pair(2, 3)));
211 EXPECT_EQ(conversions, 2);
212 #if defined(NDEBUG) && ORIG_FLAT_HASH_MAP
213 // for parallel maps, the reserve(3) above is not sufficient to guarantee that a submap will not resize and therefore rehash
214 EXPECT_EQ(hashes, 3);
215 #endif
216
217 m.try_emplace(LazyInt(2, &conversions), 4);
218 EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 2), Pair(2, 3)));
219 EXPECT_EQ(conversions, 2);
220 #if defined(NDEBUG) && ORIG_FLAT_HASH_MAP
221 // for parallel maps, the reserve(3) above is not sufficient to guarantee that a submap will not resize and therefore rehash
222 EXPECT_EQ(hashes, 4);
223 #endif
224 }
225
226 TEST(THIS_TEST_NAME, BitfieldArgument) {
227 union {
228 int n : 1;
229 };
230 n = 0;
231 ThisMap<int, int> m;
232 m.erase(n);
233 m.count(n);
234 m.prefetch(n);
235 m.find(n);
236 m.contains(n);
237 m.equal_range(n);
238 m.insert_or_assign(n, n);
239 m.insert_or_assign(m.end(), n, n);
240 m.try_emplace(n);
241 m.try_emplace(m.end(), n);
242 m.at(n);
243 m[n];
244 }
245
246 TEST(THIS_TEST_NAME, MergeExtractInsert) {
247 // We can't test mutable keys, or non-copyable keys with ThisMap.
248 // Test that the nodes have the proper API.
249 ThisMap<int, int> m = {{1, 7}, {2, 9}};
250 auto node = m.extract(1);
251 EXPECT_TRUE(node);
252 EXPECT_EQ(node.key(), 1);
253 EXPECT_EQ(node.mapped(), 7);
254 EXPECT_THAT(m, UnorderedElementsAre(Pair(2, 9)));
255
256 node.mapped() = 17;
257 m.insert(std::move(node));
258 EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 17), Pair(2, 9)));
259 }
260
261 #if 0 && !defined(__ANDROID__) && !defined(__APPLE__) && !defined(__EMSCRIPTEN__) && defined(PHMAP_HAVE_STD_ANY)
262 TEST(THIS_TEST_NAME, Any) {
263 ThisMap<int, std::any> m;
264 m.emplace(1, 7);
265 auto it = m.find(1);
266 ASSERT_NE(it, m.end());
267 EXPECT_EQ(7, std::any_cast<int>(it->second));
268
269 m.emplace(std::piecewise_construct, std::make_tuple(2), std::make_tuple(8));
270 it = m.find(2);
271 ASSERT_NE(it, m.end());
272 EXPECT_EQ(8, std::any_cast<int>(it->second));
273
274 m.emplace(std::piecewise_construct, std::make_tuple(3),
275 std::make_tuple(std::any(9)));
276 it = m.find(3);
277 ASSERT_NE(it, m.end());
278 EXPECT_EQ(9, std::any_cast<int>(it->second));
279
280 struct H {
281 size_t operator()(const std::any&) const { return 0; }
282 };
283 struct E {
284 bool operator()(const std::any&, const std::any&) const { return true; }
285 };
286 ThisMap<std::any, int, H, E> m2;
287 m2.emplace(1, 7);
288 auto it2 = m2.find(1);
289 ASSERT_NE(it2, m2.end());
290 EXPECT_EQ(7, it2->second);
291 }
292 #endif // __ANDROID__
293
294 } // namespace
295 } // namespace priv
296 } // namespace phmap