llvm/unittests/ADT/DenseMapTest.cpp

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