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