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