1 | //===- llvm/unittest/ADT/DenseMapMap.cpp - DenseMap unit tests --*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #include "llvm/ADT/DenseMap.h" |
10 | #include "llvm/ADT/DenseMapInfo.h" |
11 | #include "llvm/ADT/DenseMapInfoVariant.h" |
12 | #include "llvm/ADT/StringRef.h" |
13 | #include "gmock/gmock.h" |
14 | #include "gtest/gtest.h" |
15 | #include <map> |
16 | #include <set> |
17 | #include <utility> |
18 | #include <variant> |
19 | |
20 | using namespace llvm; |
21 | |
22 | namespace { |
23 | |
24 | uint32_t getTestKey(int i, uint32_t *) { return i; } |
25 | uint32_t getTestValue(int i, uint32_t *) { return 42 + i; } |
26 | |
27 | uint32_t *getTestKey(int i, uint32_t **) { |
28 | static uint32_t dummy_arr1[8192]; |
29 | assert(i < 8192 && "Only support 8192 dummy keys." ); |
30 | return &dummy_arr1[i]; |
31 | } |
32 | uint32_t *getTestValue(int i, uint32_t **) { |
33 | static uint32_t dummy_arr1[8192]; |
34 | assert(i < 8192 && "Only support 8192 dummy keys." ); |
35 | return &dummy_arr1[i]; |
36 | } |
37 | |
38 | /// A test class that tries to check that construction and destruction |
39 | /// occur correctly. |
40 | class CtorTester { |
41 | static std::set<CtorTester *> Constructed; |
42 | int Value; |
43 | |
44 | public: |
45 | explicit CtorTester(int Value = 0) : Value(Value) { |
46 | EXPECT_TRUE(Constructed.insert(this).second); |
47 | } |
48 | CtorTester(uint32_t Value) : Value(Value) { |
49 | EXPECT_TRUE(Constructed.insert(this).second); |
50 | } |
51 | CtorTester(const CtorTester &Arg) : Value(Arg.Value) { |
52 | EXPECT_TRUE(Constructed.insert(this).second); |
53 | } |
54 | CtorTester &operator=(const CtorTester &) = default; |
55 | ~CtorTester() { |
56 | EXPECT_EQ(1u, Constructed.erase(this)); |
57 | } |
58 | operator uint32_t() const { return Value; } |
59 | |
60 | int getValue() const { return Value; } |
61 | bool operator==(const CtorTester &RHS) const { return Value == RHS.Value; } |
62 | }; |
63 | |
64 | std::set<CtorTester *> CtorTester::Constructed; |
65 | |
66 | struct CtorTesterMapInfo { |
67 | static inline CtorTester getEmptyKey() { return CtorTester(-1); } |
68 | static inline CtorTester getTombstoneKey() { return CtorTester(-2); } |
69 | static unsigned getHashValue(const CtorTester &Val) { |
70 | return Val.getValue() * 37u; |
71 | } |
72 | static bool isEqual(const CtorTester &LHS, const CtorTester &RHS) { |
73 | return LHS == RHS; |
74 | } |
75 | }; |
76 | |
77 | CtorTester getTestKey(int i, CtorTester *) { return CtorTester(i); } |
78 | CtorTester getTestValue(int i, CtorTester *) { return CtorTester(42 + i); } |
79 | |
80 | // Test fixture, with helper functions implemented by forwarding to global |
81 | // function overloads selected by component types of the type parameter. This |
82 | // allows all of the map implementations to be tested with shared |
83 | // implementations of helper routines. |
84 | template <typename T> |
85 | class DenseMapTest : public ::testing::Test { |
86 | protected: |
87 | T Map; |
88 | |
89 | static typename T::key_type *const dummy_key_ptr; |
90 | static typename T::mapped_type *const dummy_value_ptr; |
91 | |
92 | typename T::key_type getKey(int i = 0) { |
93 | return getTestKey(i, dummy_key_ptr); |
94 | } |
95 | typename T::mapped_type getValue(int i = 0) { |
96 | return getTestValue(i, dummy_value_ptr); |
97 | } |
98 | }; |
99 | |
100 | template <typename T> |
101 | typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = nullptr; |
102 | template <typename T> |
103 | typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = nullptr; |
104 | |
105 | // Register these types for testing. |
106 | typedef ::testing::Types<DenseMap<uint32_t, uint32_t>, |
107 | DenseMap<uint32_t *, uint32_t *>, |
108 | DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>, |
109 | SmallDenseMap<uint32_t, uint32_t>, |
110 | SmallDenseMap<uint32_t *, uint32_t *>, |
111 | SmallDenseMap<CtorTester, CtorTester, 4, |
112 | CtorTesterMapInfo> |
113 | > DenseMapTestTypes; |
114 | TYPED_TEST_SUITE(DenseMapTest, DenseMapTestTypes, ); |
115 | |
116 | // Empty map tests |
117 | TYPED_TEST(DenseMapTest, EmptyIntMapTest) { |
118 | // Size tests |
119 | EXPECT_EQ(0u, this->Map.size()); |
120 | EXPECT_TRUE(this->Map.empty()); |
121 | |
122 | // Iterator tests |
123 | EXPECT_TRUE(this->Map.begin() == this->Map.end()); |
124 | |
125 | // Lookup tests |
126 | EXPECT_FALSE(this->Map.count(this->getKey())); |
127 | EXPECT_FALSE(this->Map.contains(this->getKey())); |
128 | EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end()); |
129 | EXPECT_EQ(typename TypeParam::mapped_type(), |
130 | this->Map.lookup(this->getKey())); |
131 | } |
132 | |
133 | // Constant map tests |
134 | TYPED_TEST(DenseMapTest, ConstEmptyMapTest) { |
135 | const TypeParam &ConstMap = this->Map; |
136 | EXPECT_EQ(0u, ConstMap.size()); |
137 | EXPECT_TRUE(ConstMap.empty()); |
138 | EXPECT_TRUE(ConstMap.begin() == ConstMap.end()); |
139 | } |
140 | |
141 | // A map with a single entry |
142 | TYPED_TEST(DenseMapTest, SingleEntryMapTest) { |
143 | this->Map[this->getKey()] = this->getValue(); |
144 | |
145 | // Size tests |
146 | EXPECT_EQ(1u, this->Map.size()); |
147 | EXPECT_FALSE(this->Map.begin() == this->Map.end()); |
148 | EXPECT_FALSE(this->Map.empty()); |
149 | |
150 | // Iterator tests |
151 | typename TypeParam::iterator it = this->Map.begin(); |
152 | EXPECT_EQ(this->getKey(), it->first); |
153 | EXPECT_EQ(this->getValue(), it->second); |
154 | ++it; |
155 | EXPECT_TRUE(it == this->Map.end()); |
156 | |
157 | // Lookup tests |
158 | EXPECT_TRUE(this->Map.count(this->getKey())); |
159 | EXPECT_TRUE(this->Map.contains(this->getKey())); |
160 | EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin()); |
161 | EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey())); |
162 | EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); |
163 | } |
164 | |
165 | TYPED_TEST(DenseMapTest, AtTest) { |
166 | this->Map[this->getKey(0)] = this->getValue(0); |
167 | this->Map[this->getKey(1)] = this->getValue(1); |
168 | this->Map[this->getKey(2)] = this->getValue(2); |
169 | EXPECT_EQ(this->getValue(0), this->Map.at(this->getKey(0))); |
170 | EXPECT_EQ(this->getValue(1), this->Map.at(this->getKey(1))); |
171 | EXPECT_EQ(this->getValue(2), this->Map.at(this->getKey(2))); |
172 | } |
173 | |
174 | // Test clear() method |
175 | TYPED_TEST(DenseMapTest, ClearTest) { |
176 | this->Map[this->getKey()] = this->getValue(); |
177 | this->Map.clear(); |
178 | |
179 | EXPECT_EQ(0u, this->Map.size()); |
180 | EXPECT_TRUE(this->Map.empty()); |
181 | EXPECT_TRUE(this->Map.begin() == this->Map.end()); |
182 | } |
183 | |
184 | // Test erase(iterator) method |
185 | TYPED_TEST(DenseMapTest, EraseTest) { |
186 | this->Map[this->getKey()] = this->getValue(); |
187 | this->Map.erase(this->Map.begin()); |
188 | |
189 | EXPECT_EQ(0u, this->Map.size()); |
190 | EXPECT_TRUE(this->Map.empty()); |
191 | EXPECT_TRUE(this->Map.begin() == this->Map.end()); |
192 | } |
193 | |
194 | // Test erase(value) method |
195 | TYPED_TEST(DenseMapTest, EraseTest2) { |
196 | this->Map[this->getKey()] = this->getValue(); |
197 | this->Map.erase(this->getKey()); |
198 | |
199 | EXPECT_EQ(0u, this->Map.size()); |
200 | EXPECT_TRUE(this->Map.empty()); |
201 | EXPECT_TRUE(this->Map.begin() == this->Map.end()); |
202 | } |
203 | |
204 | // Test insert() method |
205 | TYPED_TEST(DenseMapTest, InsertTest) { |
206 | this->Map.insert(std::make_pair(this->getKey(), this->getValue())); |
207 | EXPECT_EQ(1u, this->Map.size()); |
208 | EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); |
209 | } |
210 | |
211 | // Test copy constructor method |
212 | TYPED_TEST(DenseMapTest, CopyConstructorTest) { |
213 | this->Map[this->getKey()] = this->getValue(); |
214 | TypeParam copyMap(this->Map); |
215 | |
216 | EXPECT_EQ(1u, copyMap.size()); |
217 | EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); |
218 | } |
219 | |
220 | // Test copy constructor method where SmallDenseMap isn't small. |
221 | TYPED_TEST(DenseMapTest, CopyConstructorNotSmallTest) { |
222 | for (int Key = 0; Key < 5; ++Key) |
223 | this->Map[this->getKey(Key)] = this->getValue(Key); |
224 | TypeParam copyMap(this->Map); |
225 | |
226 | EXPECT_EQ(5u, copyMap.size()); |
227 | for (int Key = 0; Key < 5; ++Key) |
228 | EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]); |
229 | } |
230 | |
231 | // Test copying from a default-constructed map. |
232 | TYPED_TEST(DenseMapTest, CopyConstructorFromDefaultTest) { |
233 | TypeParam copyMap(this->Map); |
234 | |
235 | EXPECT_TRUE(copyMap.empty()); |
236 | } |
237 | |
238 | // Test copying from an empty map where SmallDenseMap isn't small. |
239 | TYPED_TEST(DenseMapTest, CopyConstructorFromEmptyTest) { |
240 | for (int Key = 0; Key < 5; ++Key) |
241 | this->Map[this->getKey(Key)] = this->getValue(Key); |
242 | this->Map.clear(); |
243 | TypeParam copyMap(this->Map); |
244 | |
245 | EXPECT_TRUE(copyMap.empty()); |
246 | } |
247 | |
248 | // Test assignment operator method |
249 | TYPED_TEST(DenseMapTest, AssignmentTest) { |
250 | this->Map[this->getKey()] = this->getValue(); |
251 | TypeParam copyMap = this->Map; |
252 | |
253 | EXPECT_EQ(1u, copyMap.size()); |
254 | EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); |
255 | |
256 | // test self-assignment. |
257 | copyMap = static_cast<TypeParam &>(copyMap); |
258 | EXPECT_EQ(1u, copyMap.size()); |
259 | EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); |
260 | } |
261 | |
262 | TYPED_TEST(DenseMapTest, AssignmentTestNotSmall) { |
263 | for (int Key = 0; Key < 5; ++Key) |
264 | this->Map[this->getKey(Key)] = this->getValue(Key); |
265 | TypeParam copyMap = this->Map; |
266 | |
267 | EXPECT_EQ(5u, copyMap.size()); |
268 | for (int Key = 0; Key < 5; ++Key) |
269 | EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]); |
270 | |
271 | // test self-assignment. |
272 | copyMap = static_cast<TypeParam &>(copyMap); |
273 | EXPECT_EQ(5u, copyMap.size()); |
274 | for (int Key = 0; Key < 5; ++Key) |
275 | EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]); |
276 | } |
277 | |
278 | // Test swap method |
279 | TYPED_TEST(DenseMapTest, SwapTest) { |
280 | this->Map[this->getKey()] = this->getValue(); |
281 | TypeParam otherMap; |
282 | |
283 | this->Map.swap(otherMap); |
284 | EXPECT_EQ(0u, this->Map.size()); |
285 | EXPECT_TRUE(this->Map.empty()); |
286 | EXPECT_EQ(1u, otherMap.size()); |
287 | EXPECT_EQ(this->getValue(), otherMap[this->getKey()]); |
288 | |
289 | this->Map.swap(otherMap); |
290 | EXPECT_EQ(0u, otherMap.size()); |
291 | EXPECT_TRUE(otherMap.empty()); |
292 | EXPECT_EQ(1u, this->Map.size()); |
293 | EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); |
294 | |
295 | // Make this more interesting by inserting 100 numbers into the map. |
296 | for (int i = 0; i < 100; ++i) |
297 | this->Map[this->getKey(i)] = this->getValue(i); |
298 | |
299 | this->Map.swap(otherMap); |
300 | EXPECT_EQ(0u, this->Map.size()); |
301 | EXPECT_TRUE(this->Map.empty()); |
302 | EXPECT_EQ(100u, otherMap.size()); |
303 | for (int i = 0; i < 100; ++i) |
304 | EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]); |
305 | |
306 | this->Map.swap(otherMap); |
307 | EXPECT_EQ(0u, otherMap.size()); |
308 | EXPECT_TRUE(otherMap.empty()); |
309 | EXPECT_EQ(100u, this->Map.size()); |
310 | for (int i = 0; i < 100; ++i) |
311 | EXPECT_EQ(this->getValue(i), this->Map[this->getKey(i)]); |
312 | } |
313 | |
314 | // A more complex iteration test |
315 | TYPED_TEST(DenseMapTest, IterationTest) { |
316 | bool visited[100]; |
317 | std::map<typename TypeParam::key_type, unsigned> visitedIndex; |
318 | |
319 | // Insert 100 numbers into the map |
320 | for (int i = 0; i < 100; ++i) { |
321 | visited[i] = false; |
322 | visitedIndex[this->getKey(i)] = i; |
323 | |
324 | this->Map[this->getKey(i)] = this->getValue(i); |
325 | } |
326 | |
327 | // Iterate over all numbers and mark each one found. |
328 | for (typename TypeParam::iterator it = this->Map.begin(); |
329 | it != this->Map.end(); ++it) |
330 | visited[visitedIndex[it->first]] = true; |
331 | |
332 | // Ensure every number was visited. |
333 | for (int i = 0; i < 100; ++i) |
334 | ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited" ; |
335 | } |
336 | |
337 | // const_iterator test |
338 | TYPED_TEST(DenseMapTest, ConstIteratorTest) { |
339 | // Check conversion from iterator to const_iterator. |
340 | typename TypeParam::iterator it = this->Map.begin(); |
341 | typename TypeParam::const_iterator cit(it); |
342 | EXPECT_TRUE(it == cit); |
343 | |
344 | // Check copying of const_iterators. |
345 | typename TypeParam::const_iterator cit2(cit); |
346 | EXPECT_TRUE(cit == cit2); |
347 | } |
348 | |
349 | namespace { |
350 | // Simple class that counts how many moves and copy happens when growing a map |
351 | struct CountCopyAndMove { |
352 | static int Move; |
353 | static int Copy; |
354 | CountCopyAndMove() {} |
355 | |
356 | CountCopyAndMove(const CountCopyAndMove &) { Copy++; } |
357 | CountCopyAndMove &operator=(const CountCopyAndMove &) { |
358 | Copy++; |
359 | return *this; |
360 | } |
361 | CountCopyAndMove(CountCopyAndMove &&) { Move++; } |
362 | CountCopyAndMove &operator=(const CountCopyAndMove &&) { |
363 | Move++; |
364 | return *this; |
365 | } |
366 | }; |
367 | int CountCopyAndMove::Copy = 0; |
368 | int CountCopyAndMove::Move = 0; |
369 | |
370 | } // anonymous namespace |
371 | |
372 | // Test initializer list construction. |
373 | TEST(DenseMapCustomTest, InitializerList) { |
374 | DenseMap<int, int> M({{0, 0}, {0, 1}, {1, 2}}); |
375 | EXPECT_EQ(2u, M.size()); |
376 | EXPECT_EQ(1u, M.count(0)); |
377 | EXPECT_EQ(0, M[0]); |
378 | EXPECT_EQ(1u, M.count(1)); |
379 | EXPECT_EQ(2, M[1]); |
380 | } |
381 | |
382 | // Test initializer list construction. |
383 | TEST(DenseMapCustomTest, EqualityComparison) { |
384 | DenseMap<int, int> M1({{0, 0}, {1, 2}}); |
385 | DenseMap<int, int> M2({{0, 0}, {1, 2}}); |
386 | DenseMap<int, int> M3({{0, 0}, {1, 3}}); |
387 | |
388 | EXPECT_EQ(M1, M2); |
389 | EXPECT_NE(M1, M3); |
390 | } |
391 | |
392 | // Test for the default minimum size of a DenseMap |
393 | TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) { |
394 | // IF THIS VALUE CHANGE, please update InitialSizeTest, InitFromIterator, and |
395 | // ReserveTest as well! |
396 | const int ExpectedInitialBucketCount = 64; |
397 | // Formula from DenseMap::getMinBucketToReserveForEntries() |
398 | const int ExpectedMaxInitialEntries = ExpectedInitialBucketCount * 3 / 4 - 1; |
399 | |
400 | DenseMap<int, CountCopyAndMove> Map; |
401 | // Will allocate 64 buckets |
402 | Map.reserve(NumEntries: 1); |
403 | unsigned MemorySize = Map.getMemorySize(); |
404 | CountCopyAndMove::Copy = 0; |
405 | CountCopyAndMove::Move = 0; |
406 | for (int i = 0; i < ExpectedMaxInitialEntries; ++i) |
407 | Map.insert(KV: std::pair<int, CountCopyAndMove>(std::piecewise_construct, |
408 | std::forward_as_tuple(args&: i), |
409 | std::forward_as_tuple())); |
410 | // Check that we didn't grow |
411 | EXPECT_EQ(MemorySize, Map.getMemorySize()); |
412 | // Check that move was called the expected number of times |
413 | EXPECT_EQ(ExpectedMaxInitialEntries, CountCopyAndMove::Move); |
414 | // Check that no copy occurred |
415 | EXPECT_EQ(0, CountCopyAndMove::Copy); |
416 | |
417 | // Adding one extra element should grow the map |
418 | Map.insert(KV: std::pair<int, CountCopyAndMove>( |
419 | std::piecewise_construct, |
420 | std::forward_as_tuple(args: ExpectedMaxInitialEntries), |
421 | std::forward_as_tuple())); |
422 | // Check that we grew |
423 | EXPECT_NE(MemorySize, Map.getMemorySize()); |
424 | // Check that move was called the expected number of times |
425 | // This relies on move-construction elision, and cannot be reliably tested. |
426 | // EXPECT_EQ(ExpectedMaxInitialEntries + 2, CountCopyAndMove::Move); |
427 | // Check that no copy occurred |
428 | EXPECT_EQ(0, CountCopyAndMove::Copy); |
429 | } |
430 | |
431 | // Make sure creating the map with an initial size of N actually gives us enough |
432 | // buckets to insert N items without increasing allocation size. |
433 | TEST(DenseMapCustomTest, InitialSizeTest) { |
434 | // Test a few different sizes, 48 is *not* a random choice: we need a value |
435 | // that is 2/3 of a power of two to stress the grow() condition, and the power |
436 | // of two has to be at least 64 because of minimum size allocation in the |
437 | // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the |
438 | // 64 default init. |
439 | for (auto Size : {1, 2, 48, 66}) { |
440 | DenseMap<int, CountCopyAndMove> Map(Size); |
441 | unsigned MemorySize = Map.getMemorySize(); |
442 | CountCopyAndMove::Copy = 0; |
443 | CountCopyAndMove::Move = 0; |
444 | for (int i = 0; i < Size; ++i) |
445 | Map.insert(KV: std::pair<int, CountCopyAndMove>(std::piecewise_construct, |
446 | std::forward_as_tuple(args&: i), |
447 | std::forward_as_tuple())); |
448 | // Check that we didn't grow |
449 | EXPECT_EQ(MemorySize, Map.getMemorySize()); |
450 | // Check that move was called the expected number of times |
451 | EXPECT_EQ(Size, CountCopyAndMove::Move); |
452 | // Check that no copy occurred |
453 | EXPECT_EQ(0, CountCopyAndMove::Copy); |
454 | } |
455 | } |
456 | |
457 | // Make sure creating the map with a iterator range does not trigger grow() |
458 | TEST(DenseMapCustomTest, InitFromIterator) { |
459 | std::vector<std::pair<int, CountCopyAndMove>> Values; |
460 | // The size is a random value greater than 64 (hardcoded DenseMap min init) |
461 | const int Count = 65; |
462 | Values.reserve(n: Count); |
463 | for (int i = 0; i < Count; i++) |
464 | Values.emplace_back(args&: i, args: CountCopyAndMove()); |
465 | |
466 | CountCopyAndMove::Move = 0; |
467 | CountCopyAndMove::Copy = 0; |
468 | DenseMap<int, CountCopyAndMove> Map(Values.begin(), Values.end()); |
469 | // Check that no move occurred |
470 | EXPECT_EQ(0, CountCopyAndMove::Move); |
471 | // Check that copy was called the expected number of times |
472 | EXPECT_EQ(Count, CountCopyAndMove::Copy); |
473 | } |
474 | |
475 | // Make sure reserve actually gives us enough buckets to insert N items |
476 | // without increasing allocation size. |
477 | TEST(DenseMapCustomTest, ReserveTest) { |
478 | // Test a few different size, 48 is *not* a random choice: we need a value |
479 | // that is 2/3 of a power of two to stress the grow() condition, and the power |
480 | // of two has to be at least 64 because of minimum size allocation in the |
481 | // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the |
482 | // 64 default init. |
483 | for (auto Size : {1, 2, 48, 66}) { |
484 | DenseMap<int, CountCopyAndMove> Map; |
485 | Map.reserve(NumEntries: Size); |
486 | unsigned MemorySize = Map.getMemorySize(); |
487 | CountCopyAndMove::Copy = 0; |
488 | CountCopyAndMove::Move = 0; |
489 | for (int i = 0; i < Size; ++i) |
490 | Map.insert(KV: std::pair<int, CountCopyAndMove>(std::piecewise_construct, |
491 | std::forward_as_tuple(args&: i), |
492 | std::forward_as_tuple())); |
493 | // Check that we didn't grow |
494 | EXPECT_EQ(MemorySize, Map.getMemorySize()); |
495 | // Check that move was called the expected number of times |
496 | EXPECT_EQ(Size, CountCopyAndMove::Move); |
497 | // Check that no copy occurred |
498 | EXPECT_EQ(0, CountCopyAndMove::Copy); |
499 | } |
500 | } |
501 | |
502 | // Make sure DenseMap works with StringRef keys. |
503 | TEST(DenseMapCustomTest, StringRefTest) { |
504 | DenseMap<StringRef, int> M; |
505 | |
506 | M["a" ] = 1; |
507 | M["b" ] = 2; |
508 | M["c" ] = 3; |
509 | |
510 | EXPECT_EQ(3u, M.size()); |
511 | EXPECT_EQ(1, M.lookup("a" )); |
512 | EXPECT_EQ(2, M.lookup("b" )); |
513 | EXPECT_EQ(3, M.lookup("c" )); |
514 | |
515 | EXPECT_EQ(0, M.lookup("q" )); |
516 | |
517 | // Test the empty string, spelled various ways. |
518 | EXPECT_EQ(0, M.lookup("" )); |
519 | EXPECT_EQ(0, M.lookup(StringRef())); |
520 | EXPECT_EQ(0, M.lookup(StringRef("a" , 0))); |
521 | M["" ] = 42; |
522 | EXPECT_EQ(42, M.lookup("" )); |
523 | EXPECT_EQ(42, M.lookup(StringRef())); |
524 | EXPECT_EQ(42, M.lookup(StringRef("a" , 0))); |
525 | } |
526 | |
527 | // Key traits that allows lookup with either an unsigned or char* key; |
528 | // In the latter case, "a" == 0, "b" == 1 and so on. |
529 | struct TestDenseMapInfo { |
530 | static inline unsigned getEmptyKey() { return ~0; } |
531 | static inline unsigned getTombstoneKey() { return ~0U - 1; } |
532 | static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } |
533 | static unsigned getHashValue(const char* Val) { |
534 | return (unsigned)(Val[0] - 'a') * 37U; |
535 | } |
536 | static bool isEqual(const unsigned& LHS, const unsigned& RHS) { |
537 | return LHS == RHS; |
538 | } |
539 | static bool isEqual(const char* LHS, const unsigned& RHS) { |
540 | return (unsigned)(LHS[0] - 'a') == RHS; |
541 | } |
542 | }; |
543 | |
544 | // find_as() tests |
545 | TEST(DenseMapCustomTest, FindAsTest) { |
546 | DenseMap<unsigned, unsigned, TestDenseMapInfo> map; |
547 | map[0] = 1; |
548 | map[1] = 2; |
549 | map[2] = 3; |
550 | |
551 | // Size tests |
552 | EXPECT_EQ(3u, map.size()); |
553 | |
554 | // Normal lookup tests |
555 | EXPECT_EQ(1u, map.count(1)); |
556 | EXPECT_EQ(1u, map.find(0)->second); |
557 | EXPECT_EQ(2u, map.find(1)->second); |
558 | EXPECT_EQ(3u, map.find(2)->second); |
559 | EXPECT_TRUE(map.find(3) == map.end()); |
560 | |
561 | // find_as() tests |
562 | EXPECT_EQ(1u, map.find_as("a" )->second); |
563 | EXPECT_EQ(2u, map.find_as("b" )->second); |
564 | EXPECT_EQ(3u, map.find_as("c" )->second); |
565 | EXPECT_TRUE(map.find_as("d" ) == map.end()); |
566 | } |
567 | |
568 | TEST(DenseMapCustomTest, SmallDenseMapInitializerList) { |
569 | SmallDenseMap<int, int> M = {{0, 0}, {0, 1}, {1, 2}}; |
570 | EXPECT_EQ(2u, M.size()); |
571 | EXPECT_EQ(1u, M.count(0)); |
572 | EXPECT_EQ(0, M[0]); |
573 | EXPECT_EQ(1u, M.count(1)); |
574 | EXPECT_EQ(2, M[1]); |
575 | } |
576 | |
577 | struct ContiguousDenseMapInfo { |
578 | static inline unsigned getEmptyKey() { return ~0; } |
579 | static inline unsigned getTombstoneKey() { return ~0U - 1; } |
580 | static unsigned getHashValue(const unsigned& Val) { return Val; } |
581 | static bool isEqual(const unsigned& LHS, const unsigned& RHS) { |
582 | return LHS == RHS; |
583 | } |
584 | }; |
585 | |
586 | // Test that filling a small dense map with exactly the number of elements in |
587 | // the map grows to have enough space for an empty bucket. |
588 | TEST(DenseMapCustomTest, SmallDenseMapGrowTest) { |
589 | SmallDenseMap<unsigned, unsigned, 32, ContiguousDenseMapInfo> map; |
590 | // Add some number of elements, then delete a few to leave us some tombstones. |
591 | // If we just filled the map with 32 elements we'd grow because of not enough |
592 | // tombstones which masks the issue here. |
593 | for (unsigned i = 0; i < 20; ++i) |
594 | map[i] = i + 1; |
595 | for (unsigned i = 0; i < 10; ++i) |
596 | map.erase(Val: i); |
597 | for (unsigned i = 20; i < 32; ++i) |
598 | map[i] = i + 1; |
599 | |
600 | // Size tests |
601 | EXPECT_EQ(22u, map.size()); |
602 | |
603 | // Try to find an element which doesn't exist. There was a bug in |
604 | // SmallDenseMap which led to a map with num elements == small capacity not |
605 | // having an empty bucket any more. Finding an element not in the map would |
606 | // therefore never terminate. |
607 | EXPECT_TRUE(map.find(32) == map.end()); |
608 | } |
609 | |
610 | TEST(DenseMapCustomTest, LargeSmallDenseMapCompaction) { |
611 | SmallDenseMap<unsigned, unsigned, 128, ContiguousDenseMapInfo> map; |
612 | // Fill to < 3/4 load. |
613 | for (unsigned i = 0; i < 95; ++i) |
614 | map[i] = i; |
615 | // And erase, leaving behind tombstones. |
616 | for (unsigned i = 0; i < 95; ++i) |
617 | map.erase(Val: i); |
618 | // Fill further, so that less than 1/8 are empty, but still below 3/4 load. |
619 | for (unsigned i = 95; i < 128; ++i) |
620 | map[i] = i; |
621 | |
622 | EXPECT_EQ(33u, map.size()); |
623 | // Similar to the previous test, check for a non-existing element, as an |
624 | // indirect check that tombstones have been removed. |
625 | EXPECT_TRUE(map.find(0) == map.end()); |
626 | } |
627 | |
628 | TEST(DenseMapCustomTest, SmallDenseMapWithNumBucketsNonPowerOf2) { |
629 | // Is not power of 2. |
630 | const unsigned NumInitBuckets = 33; |
631 | // Power of 2 less then NumInitBuckets. |
632 | constexpr unsigned InlineBuckets = 4; |
633 | // Constructor should not trigger assert. |
634 | SmallDenseMap<int, int, InlineBuckets> map(NumInitBuckets); |
635 | } |
636 | |
637 | TEST(DenseMapCustomTest, TryEmplaceTest) { |
638 | DenseMap<int, std::unique_ptr<int>> Map; |
639 | std::unique_ptr<int> P(new int(2)); |
640 | auto Try1 = Map.try_emplace(Key: 0, Args: new int(1)); |
641 | EXPECT_TRUE(Try1.second); |
642 | auto Try2 = Map.try_emplace(Key: 0, Args: std::move(P)); |
643 | EXPECT_FALSE(Try2.second); |
644 | EXPECT_EQ(Try1.first, Try2.first); |
645 | EXPECT_NE(nullptr, P); |
646 | } |
647 | |
648 | TEST(DenseMapCustomTest, ConstTest) { |
649 | // Test that const pointers work okay for count and find, even when the |
650 | // underlying map is a non-const pointer. |
651 | DenseMap<int *, int> Map; |
652 | int A; |
653 | int *B = &A; |
654 | const int *C = &A; |
655 | Map.insert(KV: {B, 0}); |
656 | EXPECT_EQ(Map.count(B), 1u); |
657 | EXPECT_EQ(Map.count(C), 1u); |
658 | EXPECT_NE(Map.find(B), Map.end()); |
659 | EXPECT_NE(Map.find(C), Map.end()); |
660 | } |
661 | |
662 | struct IncompleteStruct; |
663 | |
664 | TEST(DenseMapCustomTest, OpaquePointerKey) { |
665 | // Test that we can use a pointer to an incomplete type as a DenseMap key. |
666 | // This is an important build time optimization, since many classes have |
667 | // DenseMap members. |
668 | DenseMap<IncompleteStruct *, int> Map; |
669 | int Keys[3] = {0, 0, 0}; |
670 | IncompleteStruct *K1 = reinterpret_cast<IncompleteStruct *>(&Keys[0]); |
671 | IncompleteStruct *K2 = reinterpret_cast<IncompleteStruct *>(&Keys[1]); |
672 | IncompleteStruct *K3 = reinterpret_cast<IncompleteStruct *>(&Keys[2]); |
673 | Map.insert(KV: {K1, 1}); |
674 | Map.insert(KV: {K2, 2}); |
675 | Map.insert(KV: {K3, 3}); |
676 | EXPECT_EQ(Map.count(K1), 1u); |
677 | EXPECT_EQ(Map[K1], 1); |
678 | EXPECT_EQ(Map[K2], 2); |
679 | EXPECT_EQ(Map[K3], 3); |
680 | Map.clear(); |
681 | EXPECT_EQ(Map.find(K1), Map.end()); |
682 | EXPECT_EQ(Map.find(K2), Map.end()); |
683 | EXPECT_EQ(Map.find(K3), Map.end()); |
684 | } |
685 | } // namespace |
686 | |
687 | namespace { |
688 | struct A { |
689 | A(int value) : value(value) {} |
690 | int value; |
691 | }; |
692 | struct B : public A { |
693 | using A::A; |
694 | }; |
695 | |
696 | struct AlwaysEqType { |
697 | bool operator==(const AlwaysEqType &RHS) const { return true; } |
698 | }; |
699 | } // namespace |
700 | |
701 | namespace llvm { |
702 | template <typename T> |
703 | struct DenseMapInfo<T, std::enable_if_t<std::is_base_of_v<A, T>>> { |
704 | static inline T getEmptyKey() { return {static_cast<int>(~0)}; } |
705 | static inline T getTombstoneKey() { return {static_cast<int>(~0U - 1)}; } |
706 | static unsigned getHashValue(const T &Val) { return Val.value; } |
707 | static bool isEqual(const T &LHS, const T &RHS) { |
708 | return LHS.value == RHS.value; |
709 | } |
710 | }; |
711 | |
712 | template <> struct DenseMapInfo<AlwaysEqType> { |
713 | using T = AlwaysEqType; |
714 | static inline T getEmptyKey() { return {}; } |
715 | static inline T getTombstoneKey() { return {}; } |
716 | static unsigned getHashValue(const T &Val) { return 0; } |
717 | static bool isEqual(const T &LHS, const T &RHS) { |
718 | return false; |
719 | } |
720 | }; |
721 | } // namespace llvm |
722 | |
723 | namespace { |
724 | TEST(DenseMapCustomTest, SFINAEMapInfo) { |
725 | // Test that we can use a pointer to an incomplete type as a DenseMap key. |
726 | // This is an important build time optimization, since many classes have |
727 | // DenseMap members. |
728 | DenseMap<B, int> Map; |
729 | B Keys[3] = {{0}, {1}, {2}}; |
730 | Map.insert(KV: {Keys[0], 1}); |
731 | Map.insert(KV: {Keys[1], 2}); |
732 | Map.insert(KV: {Keys[2], 3}); |
733 | EXPECT_EQ(Map.count(Keys[0]), 1u); |
734 | EXPECT_EQ(Map[Keys[0]], 1); |
735 | EXPECT_EQ(Map[Keys[1]], 2); |
736 | EXPECT_EQ(Map[Keys[2]], 3); |
737 | Map.clear(); |
738 | EXPECT_EQ(Map.find(Keys[0]), Map.end()); |
739 | EXPECT_EQ(Map.find(Keys[1]), Map.end()); |
740 | EXPECT_EQ(Map.find(Keys[2]), Map.end()); |
741 | } |
742 | |
743 | TEST(DenseMapCustomTest, VariantSupport) { |
744 | using variant = std::variant<int, int, AlwaysEqType>; |
745 | DenseMap<variant, int> Map; |
746 | variant Keys[] = { |
747 | variant(std::in_place_index<0>, 1), |
748 | variant(std::in_place_index<1>, 1), |
749 | variant(std::in_place_index<2>), |
750 | }; |
751 | Map.try_emplace(Key: Keys[0], Args: 0); |
752 | Map.try_emplace(Key: Keys[1], Args: 1); |
753 | EXPECT_THAT(Map, testing::SizeIs(2)); |
754 | EXPECT_NE(DenseMapInfo<variant>::getHashValue(Keys[0]), |
755 | DenseMapInfo<variant>::getHashValue(Keys[1])); |
756 | // Check that isEqual dispatches to isEqual of underlying type, and not to |
757 | // operator==. |
758 | EXPECT_FALSE(DenseMapInfo<variant>::isEqual(Keys[2], Keys[2])); |
759 | } |
760 | |
761 | // Test that gTest prints map entries as pairs instead of opaque objects. |
762 | // See third-party/unittest/googletest/internal/custom/gtest-printers.h |
763 | TEST(DenseMapCustomTest, PairPrinting) { |
764 | DenseMap<int, StringRef> Map = {{1, "one" }, {2, "two" }}; |
765 | EXPECT_EQ(R"({ (1, "one"), (2, "two") })" , ::testing::PrintToString(Map)); |
766 | } |
767 | |
768 | } // namespace |
769 | |