Debian Codegraph @

llvm-project/llvm/unittests/ADT/DenseMapTest.cpp

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