1112 lines · 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-exception6//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/STLForwardCompat.h"14#include "llvm/ADT/SmallSet.h"15#include "llvm/ADT/StringRef.h"16#include "gmock/gmock.h"17#include "gtest/gtest.h"18#include <map>19#include <optional>20#include <set>21#include <utility>22#include <variant>23 24using namespace llvm;25 26namespace {27uint32_t getTestKey(int i, uint32_t *) { return i; }28uint32_t getTestValue(int i, uint32_t *) { return 42 + i; }29 30uint32_t *getTestKey(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}35uint32_t *getTestValue(int i, uint32_t **) {36 static uint32_t dummy_arr1[8192];37 assert(i < 8192 && "Only support 8192 dummy keys.");38 return &dummy_arr1[i];39}40 41enum class EnumClass { Val };42 43EnumClass getTestKey(int i, EnumClass *) {44 // We can't possibly support 100 values for the swap test, so just return an45 // invalid EnumClass for testing.46 return static_cast<EnumClass>(i);47}48 49/// A test class that tries to check that construction and destruction50/// occur correctly.51class CtorTester {52 static std::set<CtorTester *> Constructed;53 int Value;54 55public:56 explicit CtorTester(int Value = 0) : Value(Value) {57 EXPECT_TRUE(Constructed.insert(this).second);58 }59 CtorTester(uint32_t Value) : Value(Value) {60 EXPECT_TRUE(Constructed.insert(this).second);61 }62 CtorTester(const CtorTester &Arg) : Value(Arg.Value) {63 EXPECT_TRUE(Constructed.insert(this).second);64 }65 CtorTester &operator=(const CtorTester &) = default;66 ~CtorTester() {67 EXPECT_EQ(1u, Constructed.erase(this));68 }69 operator uint32_t() const { return Value; }70 71 int getValue() const { return Value; }72 bool operator==(const CtorTester &RHS) const { return Value == RHS.Value; }73 74 // Return the number of live CtorTester objects, excluding the empty and75 // tombstone keys.76 static size_t getNumConstructed() {77 return std::count_if(Constructed.begin(), Constructed.end(),78 [](const CtorTester *Obj) {79 int V = Obj->getValue();80 return V != -1 && V != -2;81 });82 }83};84 85std::set<CtorTester *> CtorTester::Constructed;86 87struct CtorTesterMapInfo {88 static inline CtorTester getEmptyKey() { return CtorTester(-1); }89 static inline CtorTester getTombstoneKey() { return CtorTester(-2); }90 static unsigned getHashValue(const CtorTester &Val) {91 return Val.getValue() * 37u;92 }93 static bool isEqual(const CtorTester &LHS, const CtorTester &RHS) {94 return LHS == RHS;95 }96};97 98CtorTester getTestKey(int i, CtorTester *) { return CtorTester(i); }99CtorTester getTestValue(int i, CtorTester *) { return CtorTester(42 + i); }100 101std::optional<uint32_t> getTestKey(int i, std::optional<uint32_t> *) {102 return i;103}104 105// Test fixture, with helper functions implemented by forwarding to global106// function overloads selected by component types of the type parameter. This107// allows all of the map implementations to be tested with shared108// implementations of helper routines.109template <typename T>110class DenseMapTest : public ::testing::Test {111protected:112 T Map;113 114 static typename T::key_type *const dummy_key_ptr;115 static typename T::mapped_type *const dummy_value_ptr;116 117 typename T::key_type getKey(int i = 0) {118 return getTestKey(i, dummy_key_ptr);119 }120 typename T::mapped_type getValue(int i = 0) {121 return getTestValue(i, dummy_value_ptr);122 }123};124 125template <typename T>126typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = nullptr;127template <typename T>128typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = nullptr;129 130// Register these types for testing.131// clang-format off132using DenseMapTestTypes = ::testing::Types<133 DenseMap<uint32_t, uint32_t>,134 DenseMap<uint32_t *, uint32_t *>,135 DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>,136 DenseMap<EnumClass, uint32_t>,137 DenseMap<std::optional<uint32_t>, uint32_t>,138 SmallDenseMap<uint32_t, uint32_t>,139 SmallDenseMap<uint32_t *, uint32_t *>,140 SmallDenseMap<CtorTester, CtorTester, 4, CtorTesterMapInfo>,141 SmallDenseMap<EnumClass, uint32_t>,142 SmallDenseMap<std::optional<uint32_t>, uint32_t>>;143// clang-format on144 145TYPED_TEST_SUITE(DenseMapTest, DenseMapTestTypes, );146 147// Empty map tests148TYPED_TEST(DenseMapTest, EmptyIntMapTest) {149 // Size tests150 EXPECT_EQ(0u, this->Map.size());151 EXPECT_TRUE(this->Map.empty());152 153 // Iterator tests154 EXPECT_TRUE(this->Map.begin() == this->Map.end());155 156 // Lookup tests157 EXPECT_FALSE(this->Map.count(this->getKey()));158 EXPECT_FALSE(this->Map.contains(this->getKey()));159 EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end());160 EXPECT_EQ(typename TypeParam::mapped_type(),161 this->Map.lookup(this->getKey()));162}163 164// Constant map tests165TYPED_TEST(DenseMapTest, ConstEmptyMapTest) {166 const TypeParam &ConstMap = this->Map;167 EXPECT_EQ(0u, ConstMap.size());168 EXPECT_TRUE(ConstMap.empty());169 EXPECT_TRUE(ConstMap.begin() == ConstMap.end());170}171 172// A map with a single entry173TYPED_TEST(DenseMapTest, SingleEntryMapTest) {174 this->Map[this->getKey()] = this->getValue();175 176 // Size tests177 EXPECT_EQ(1u, this->Map.size());178 EXPECT_FALSE(this->Map.begin() == this->Map.end());179 EXPECT_FALSE(this->Map.empty());180 181 // Iterator tests182 typename TypeParam::iterator it = this->Map.begin();183 EXPECT_EQ(this->getKey(), it->first);184 EXPECT_EQ(this->getValue(), it->second);185 ++it;186 EXPECT_TRUE(it == this->Map.end());187 188 // Lookup tests189 EXPECT_TRUE(this->Map.count(this->getKey()));190 EXPECT_TRUE(this->Map.contains(this->getKey()));191 EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin());192 EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey()));193 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);194}195 196TYPED_TEST(DenseMapTest, AtTest) {197 this->Map[this->getKey(0)] = this->getValue(0);198 this->Map[this->getKey(1)] = this->getValue(1);199 this->Map[this->getKey(2)] = this->getValue(2);200 EXPECT_EQ(this->getValue(0), this->Map.at(this->getKey(0)));201 EXPECT_EQ(this->getValue(1), this->Map.at(this->getKey(1)));202 EXPECT_EQ(this->getValue(2), this->Map.at(this->getKey(2)));203 204 this->Map.at(this->getKey(0)) = this->getValue(1);205 EXPECT_EQ(this->getValue(1), this->Map.at(this->getKey(0)));206 207 const auto &ConstMap = this->Map;208 EXPECT_EQ(this->getValue(1), ConstMap.at(this->getKey(0)));209 EXPECT_EQ(this->getValue(1), ConstMap.at(this->getKey(1)));210 EXPECT_EQ(this->getValue(2), ConstMap.at(this->getKey(2)));211}212 213// Test clear() method214TYPED_TEST(DenseMapTest, ClearTest) {215 this->Map[this->getKey()] = this->getValue();216 this->Map.clear();217 218 EXPECT_EQ(0u, this->Map.size());219 EXPECT_TRUE(this->Map.empty());220 EXPECT_TRUE(this->Map.begin() == this->Map.end());221}222 223// Test erase(iterator) method224TYPED_TEST(DenseMapTest, EraseTest) {225 this->Map[this->getKey()] = this->getValue();226 this->Map.erase(this->Map.begin());227 228 EXPECT_EQ(0u, this->Map.size());229 EXPECT_TRUE(this->Map.empty());230 EXPECT_TRUE(this->Map.begin() == this->Map.end());231}232 233// Test erase(value) method234TYPED_TEST(DenseMapTest, EraseTest2) {235 this->Map[this->getKey()] = this->getValue();236 this->Map.erase(this->getKey());237 238 EXPECT_EQ(0u, this->Map.size());239 EXPECT_TRUE(this->Map.empty());240 EXPECT_TRUE(this->Map.begin() == this->Map.end());241}242 243// Test insert() method244TYPED_TEST(DenseMapTest, InsertTest) {245 this->Map.insert(std::make_pair(this->getKey(), this->getValue()));246 EXPECT_EQ(1u, this->Map.size());247 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);248}249 250// Test copy constructor method251TYPED_TEST(DenseMapTest, CopyConstructorTest) {252 this->Map[this->getKey()] = this->getValue();253 TypeParam copyMap(this->Map);254 255 EXPECT_EQ(1u, copyMap.size());256 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]);257}258 259// Test copy constructor method where SmallDenseMap isn't small.260TYPED_TEST(DenseMapTest, CopyConstructorNotSmallTest) {261 for (int Key = 0; Key < 5; ++Key)262 this->Map[this->getKey(Key)] = this->getValue(Key);263 TypeParam copyMap(this->Map);264 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 range constructors.271TYPED_TEST(DenseMapTest, RangeConstructorTest) {272 using KeyAndValue =273 std::pair<typename TypeParam::key_type, typename TypeParam::mapped_type>;274 KeyAndValue PlainArray[] = {{this->getKey(0), this->getValue(0)},275 {this->getKey(1), this->getValue(1)}};276 277 TypeParam MapFromRange(llvm::from_range, PlainArray);278 EXPECT_EQ(2u, MapFromRange.size());279 EXPECT_EQ(this->getValue(0), MapFromRange[this->getKey(0)]);280 EXPECT_EQ(this->getValue(1), MapFromRange[this->getKey(1)]);281 282 TypeParam MapFromInitList({{this->getKey(0), this->getValue(1)},283 {this->getKey(1), this->getValue(2)}});284 EXPECT_EQ(2u, MapFromInitList.size());285 EXPECT_EQ(this->getValue(1), MapFromInitList[this->getKey(0)]);286 EXPECT_EQ(this->getValue(2), MapFromInitList[this->getKey(1)]);287}288 289// Test copying from a default-constructed map.290TYPED_TEST(DenseMapTest, CopyConstructorFromDefaultTest) {291 TypeParam copyMap(this->Map);292 293 EXPECT_TRUE(copyMap.empty());294}295 296// Test copying from an empty map where SmallDenseMap isn't small.297TYPED_TEST(DenseMapTest, CopyConstructorFromEmptyTest) {298 for (int Key = 0; Key < 5; ++Key)299 this->Map[this->getKey(Key)] = this->getValue(Key);300 this->Map.clear();301 TypeParam copyMap(this->Map);302 303 EXPECT_TRUE(copyMap.empty());304}305 306// Test assignment operator method307TYPED_TEST(DenseMapTest, AssignmentTest) {308 this->Map[this->getKey()] = this->getValue();309 TypeParam copyMap = this->Map;310 311 EXPECT_EQ(1u, copyMap.size());312 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]);313 314 // test self-assignment.315 copyMap = static_cast<TypeParam &>(copyMap);316 EXPECT_EQ(1u, copyMap.size());317 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]);318}319 320TYPED_TEST(DenseMapTest, AssignmentTestNotSmall) {321 for (int Key = 0; Key < 5; ++Key)322 this->Map[this->getKey(Key)] = this->getValue(Key);323 TypeParam copyMap = this->Map;324 325 EXPECT_EQ(5u, copyMap.size());326 for (int Key = 0; Key < 5; ++Key)327 EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]);328 329 // test self-assignment.330 copyMap = static_cast<TypeParam &>(copyMap);331 EXPECT_EQ(5u, copyMap.size());332 for (int Key = 0; Key < 5; ++Key)333 EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]);334}335 336// Test swap method337TYPED_TEST(DenseMapTest, SwapTest) {338 this->Map[this->getKey()] = this->getValue();339 TypeParam otherMap;340 341 this->Map.swap(otherMap);342 EXPECT_EQ(0u, this->Map.size());343 EXPECT_TRUE(this->Map.empty());344 EXPECT_EQ(1u, otherMap.size());345 EXPECT_EQ(this->getValue(), otherMap[this->getKey()]);346 347 this->Map.swap(otherMap);348 EXPECT_EQ(0u, otherMap.size());349 EXPECT_TRUE(otherMap.empty());350 EXPECT_EQ(1u, this->Map.size());351 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);352 353 // Make this more interesting by inserting 100 numbers into the map.354 for (int i = 0; i < 100; ++i)355 this->Map[this->getKey(i)] = this->getValue(i);356 357 this->Map.swap(otherMap);358 EXPECT_EQ(0u, this->Map.size());359 EXPECT_TRUE(this->Map.empty());360 EXPECT_EQ(100u, otherMap.size());361 for (int i = 0; i < 100; ++i)362 EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]);363 364 this->Map.swap(otherMap);365 EXPECT_EQ(0u, otherMap.size());366 EXPECT_TRUE(otherMap.empty());367 EXPECT_EQ(100u, this->Map.size());368 for (int i = 0; i < 100; ++i)369 EXPECT_EQ(this->getValue(i), this->Map[this->getKey(i)]);370}371 372// A more complex iteration test373TYPED_TEST(DenseMapTest, IterationTest) {374 bool visited[100];375 std::map<typename TypeParam::key_type, unsigned> visitedIndex;376 377 // Insert 100 numbers into the map378 for (int i = 0; i < 100; ++i) {379 visited[i] = false;380 visitedIndex[this->getKey(i)] = i;381 382 this->Map[this->getKey(i)] = this->getValue(i);383 }384 385 // Iterate over all numbers and mark each one found.386 for (typename TypeParam::iterator it = this->Map.begin();387 it != this->Map.end(); ++it)388 visited[visitedIndex[it->first]] = true;389 390 // Ensure every number was visited.391 for (int i = 0; i < 100; ++i)392 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited";393}394 395// const_iterator test396TYPED_TEST(DenseMapTest, ConstIteratorTest) {397 // Check conversion from iterator to const_iterator.398 typename TypeParam::iterator it = this->Map.begin();399 typename TypeParam::const_iterator cit(it);400 EXPECT_TRUE(it == cit);401 402 // Check copying of const_iterators.403 typename TypeParam::const_iterator cit2(cit);404 EXPECT_TRUE(cit == cit2);405}406 407// TYPED_TEST below cycles through different types. We define UniversalSmallSet408// here so that we'll use SmallSet or SmallPtrSet depending on whether the409// element type is a pointer.410template <typename T, unsigned N>411using UniversalSmallSet =412 std::conditional_t<std::is_pointer_v<T>, SmallPtrSet<T, N>, SmallSet<T, N>>;413 414TYPED_TEST(DenseMapTest, KeysValuesIterator) {415 UniversalSmallSet<typename TypeParam::key_type, 10> Keys;416 UniversalSmallSet<typename TypeParam::mapped_type, 10> Values;417 for (int I = 0; I < 10; ++I) {418 auto K = this->getKey(I);419 auto V = this->getValue(I);420 Keys.insert(K);421 Values.insert(V);422 this->Map[K] = V;423 }424 425 UniversalSmallSet<typename TypeParam::key_type, 10> ActualKeys;426 UniversalSmallSet<typename TypeParam::mapped_type, 10> ActualValues;427 for (auto K : this->Map.keys())428 ActualKeys.insert(K);429 for (auto V : this->Map.values())430 ActualValues.insert(V);431 432 EXPECT_EQ(Keys, ActualKeys);433 EXPECT_EQ(Values, ActualValues);434}435 436TYPED_TEST(DenseMapTest, ConstKeysValuesIterator) {437 UniversalSmallSet<typename TypeParam::key_type, 10> Keys;438 UniversalSmallSet<typename TypeParam::mapped_type, 10> Values;439 for (int I = 0; I < 10; ++I) {440 auto K = this->getKey(I);441 auto V = this->getValue(I);442 Keys.insert(K);443 Values.insert(V);444 this->Map[K] = V;445 }446 447 const TypeParam &ConstMap = this->Map;448 UniversalSmallSet<typename TypeParam::key_type, 10> ActualKeys;449 UniversalSmallSet<typename TypeParam::mapped_type, 10> ActualValues;450 for (auto K : ConstMap.keys())451 ActualKeys.insert(K);452 for (auto V : ConstMap.values())453 ActualValues.insert(V);454 455 EXPECT_EQ(Keys, ActualKeys);456 EXPECT_EQ(Values, ActualValues);457}458 459// Test initializer list construction.460TEST(DenseMapCustomTest, InitializerList) {461 DenseMap<int, int> M({{0, 0}, {0, 1}, {1, 2}});462 EXPECT_EQ(2u, M.size());463 EXPECT_EQ(1u, M.count(0));464 EXPECT_EQ(0, M[0]);465 EXPECT_EQ(1u, M.count(1));466 EXPECT_EQ(2, M[1]);467}468 469// Test initializer list construction.470TEST(DenseMapCustomTest, EqualityComparison) {471 DenseMap<int, int> M1({{0, 0}, {1, 2}});472 DenseMap<int, int> M2({{0, 0}, {1, 2}});473 DenseMap<int, int> M3({{0, 0}, {1, 3}});474 475 EXPECT_EQ(M1, M2);476 EXPECT_NE(M1, M3);477}478 479TEST(DenseMapCustomTest, InsertRange) {480 DenseMap<int, int> M;481 482 std::pair<int, int> InputVals[3] = {{0, 0}, {0, 1}, {1, 2}};483 M.insert_range(InputVals);484 485 EXPECT_EQ(M.size(), 2u);486 EXPECT_THAT(M, testing::UnorderedElementsAre(testing::Pair(0, 0),487 testing::Pair(1, 2)));488}489 490TEST(SmallDenseMapCustomTest, InsertRange) {491 SmallDenseMap<int, int> M;492 493 std::pair<int, int> InputVals[3] = {{0, 0}, {0, 1}, {1, 2}};494 M.insert_range(InputVals);495 496 EXPECT_EQ(M.size(), 2u);497 EXPECT_THAT(M, testing::UnorderedElementsAre(testing::Pair(0, 0),498 testing::Pair(1, 2)));499}500 501// Test for the default minimum size of a DenseMap502TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) {503 // IF THIS VALUE CHANGE, please update InitialSizeTest, InitFromIterator, and504 // ReserveTest as well!505 const int ExpectedInitialBucketCount = 64;506 // Formula from DenseMap::getMinBucketToReserveForEntries()507 const int ExpectedMaxInitialEntries = ExpectedInitialBucketCount * 3 / 4 - 1;508 509 DenseMap<int, CountCopyAndMove> Map;510 // Will allocate 64 buckets511 Map.reserve(1);512 unsigned MemorySize = Map.getMemorySize();513 CountCopyAndMove::ResetCounts();514 515 for (int i = 0; i < ExpectedMaxInitialEntries; ++i)516 Map.insert(std::pair<int, CountCopyAndMove>(std::piecewise_construct,517 std::forward_as_tuple(i),518 std::forward_as_tuple()));519 // Check that we didn't grow520 EXPECT_EQ(MemorySize, Map.getMemorySize());521 // Check that move was called the expected number of times522 EXPECT_EQ(ExpectedMaxInitialEntries, CountCopyAndMove::TotalMoves());523 // Check that no copy occurred524 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());525 526 // Adding one extra element should grow the map527 Map.insert(std::pair<int, CountCopyAndMove>(528 std::piecewise_construct,529 std::forward_as_tuple(ExpectedMaxInitialEntries),530 std::forward_as_tuple()));531 // Check that we grew532 EXPECT_NE(MemorySize, Map.getMemorySize());533 // Check that move was called the expected number of times534 // This relies on move-construction elision, and cannot be reliably tested.535 // EXPECT_EQ(ExpectedMaxInitialEntries + 2, CountCopyAndMove::Move);536 // Check that no copy occurred537 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());538}539 540// Make sure creating the map with an initial size of N actually gives us enough541// buckets to insert N items without increasing allocation size.542TEST(DenseMapCustomTest, InitialSizeTest) {543 // Test a few different sizes, 48 is *not* a random choice: we need a value544 // that is 2/3 of a power of two to stress the grow() condition, and the power545 // of two has to be at least 64 because of minimum size allocation in the546 // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the547 // 64 default init.548 for (auto Size : {1, 2, 48, 66}) {549 DenseMap<int, CountCopyAndMove> Map(Size);550 unsigned MemorySize = Map.getMemorySize();551 CountCopyAndMove::ResetCounts();552 553 for (int i = 0; i < Size; ++i)554 Map.insert(std::pair<int, CountCopyAndMove>(std::piecewise_construct,555 std::forward_as_tuple(i),556 std::forward_as_tuple()));557 // Check that we didn't grow558 EXPECT_EQ(MemorySize, Map.getMemorySize());559 // Check that move was called the expected number of times560 EXPECT_EQ(Size, CountCopyAndMove::TotalMoves());561 // Check that no copy occurred562 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());563 }564}565 566// Make sure creating the map with a iterator range does not trigger grow()567TEST(DenseMapCustomTest, InitFromIterator) {568 std::vector<std::pair<int, CountCopyAndMove>> Values;569 // The size is a random value greater than 64 (hardcoded DenseMap min init)570 const int Count = 65;571 Values.reserve(Count);572 for (int i = 0; i < Count; i++)573 Values.emplace_back(i, CountCopyAndMove(i));574 575 CountCopyAndMove::ResetCounts();576 DenseMap<int, CountCopyAndMove> Map(Values.begin(), Values.end());577 // Check that no move occurred578 EXPECT_EQ(0, CountCopyAndMove::TotalMoves());579 // Check that copy was called the expected number of times580 EXPECT_EQ(Count, CountCopyAndMove::TotalCopies());581}582 583// Make sure reserve actually gives us enough buckets to insert N items584// without increasing allocation size.585TEST(DenseMapCustomTest, ReserveTest) {586 // Test a few different size, 48 is *not* a random choice: we need a value587 // that is 2/3 of a power of two to stress the grow() condition, and the power588 // of two has to be at least 64 because of minimum size allocation in the589 // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the590 // 64 default init.591 for (auto Size : {1, 2, 48, 66}) {592 DenseMap<int, CountCopyAndMove> Map;593 Map.reserve(Size);594 unsigned MemorySize = Map.getMemorySize();595 CountCopyAndMove::ResetCounts();596 for (int i = 0; i < Size; ++i)597 Map.insert(std::pair<int, CountCopyAndMove>(std::piecewise_construct,598 std::forward_as_tuple(i),599 std::forward_as_tuple()));600 // Check that we didn't grow601 EXPECT_EQ(MemorySize, Map.getMemorySize());602 // Check that move was called the expected number of times603 EXPECT_EQ(Size, CountCopyAndMove::TotalMoves());604 // Check that no copy occurred605 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());606 }607}608 609TEST(DenseMapCustomTest, InsertOrAssignTest) {610 DenseMap<int, CountCopyAndMove> Map;611 612 CountCopyAndMove val1(1);613 CountCopyAndMove::ResetCounts();614 auto try0 = Map.insert_or_assign(0, val1);615 EXPECT_TRUE(try0.second);616 EXPECT_EQ(0, CountCopyAndMove::TotalMoves());617 EXPECT_EQ(1, CountCopyAndMove::CopyConstructions);618 EXPECT_EQ(0, CountCopyAndMove::CopyAssignments);619 620 CountCopyAndMove::ResetCounts();621 auto try1 = Map.insert_or_assign(0, val1);622 EXPECT_FALSE(try1.second);623 EXPECT_EQ(0, CountCopyAndMove::TotalMoves());624 EXPECT_EQ(0, CountCopyAndMove::CopyConstructions);625 EXPECT_EQ(1, CountCopyAndMove::CopyAssignments);626 627 int key2 = 2;628 CountCopyAndMove val2(2);629 CountCopyAndMove::ResetCounts();630 auto try2 = Map.insert_or_assign(key2, std::move(val2));631 EXPECT_TRUE(try2.second);632 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());633 EXPECT_EQ(1, CountCopyAndMove::MoveConstructions);634 EXPECT_EQ(0, CountCopyAndMove::MoveAssignments);635 636 CountCopyAndMove val3(3);637 CountCopyAndMove::ResetCounts();638 auto try3 = Map.insert_or_assign(key2, std::move(val3));639 EXPECT_FALSE(try3.second);640 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());641 EXPECT_EQ(0, CountCopyAndMove::MoveConstructions);642 EXPECT_EQ(1, CountCopyAndMove::MoveAssignments);643}644 645TEST(DenseMapCustomTest, EmplaceOrAssign) {646 DenseMap<int, CountCopyAndMove> Map;647 648 CountCopyAndMove::ResetCounts();649 auto Try0 = Map.emplace_or_assign(3, 3);650 EXPECT_TRUE(Try0.second);651 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());652 EXPECT_EQ(0, CountCopyAndMove::TotalMoves());653 EXPECT_EQ(1, CountCopyAndMove::ValueConstructions);654 655 CountCopyAndMove::ResetCounts();656 auto Try1 = Map.emplace_or_assign(3, 4);657 EXPECT_FALSE(Try1.second);658 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());659 EXPECT_EQ(1, CountCopyAndMove::ValueConstructions);660 EXPECT_EQ(0, CountCopyAndMove::MoveConstructions);661 EXPECT_EQ(1, CountCopyAndMove::MoveAssignments);662 663 int Key = 5;664 CountCopyAndMove::ResetCounts();665 auto Try2 = Map.emplace_or_assign(Key, 3);666 EXPECT_TRUE(Try2.second);667 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());668 EXPECT_EQ(0, CountCopyAndMove::TotalMoves());669 EXPECT_EQ(1, CountCopyAndMove::ValueConstructions);670 671 CountCopyAndMove::ResetCounts();672 auto Try3 = Map.emplace_or_assign(Key, 4);673 EXPECT_FALSE(Try3.second);674 EXPECT_EQ(0, CountCopyAndMove::TotalCopies());675 EXPECT_EQ(1, CountCopyAndMove::ValueConstructions);676 EXPECT_EQ(0, CountCopyAndMove::MoveConstructions);677 EXPECT_EQ(1, CountCopyAndMove::MoveAssignments);678}679 680// Make sure DenseMap works with StringRef keys.681TEST(DenseMapCustomTest, StringRefTest) {682 DenseMap<StringRef, int> M;683 684 M["a"] = 1;685 M["b"] = 2;686 M["c"] = 3;687 688 EXPECT_EQ(3u, M.size());689 EXPECT_EQ(1, M.lookup("a"));690 EXPECT_EQ(2, M.lookup("b"));691 EXPECT_EQ(3, M.lookup("c"));692 693 EXPECT_EQ(0, M.lookup("q"));694 695 // Test the empty string, spelled various ways.696 EXPECT_EQ(0, M.lookup(""));697 EXPECT_EQ(0, M.lookup(StringRef()));698 EXPECT_EQ(0, M.lookup(StringRef("a", 0)));699 M[""] = 42;700 EXPECT_EQ(42, M.lookup(""));701 EXPECT_EQ(42, M.lookup(StringRef()));702 EXPECT_EQ(42, M.lookup(StringRef("a", 0)));703}704 705struct NonDefaultConstructible {706 unsigned V;707 NonDefaultConstructible(unsigned V) : V(V) {};708 bool operator==(const NonDefaultConstructible &Other) const {709 return V == Other.V;710 }711};712 713TEST(DenseMapCustomTest, LookupOr) {714 DenseMap<int, NonDefaultConstructible> M;715 716 M.insert_or_assign(0, 3u);717 M.insert_or_assign(1, 2u);718 M.insert_or_assign(1, 0u);719 720 EXPECT_EQ(M.lookup_or(0, 4u), 3u);721 EXPECT_EQ(M.lookup_or(1, 4u), 0u);722 EXPECT_EQ(M.lookup_or(2, 4u), 4u);723}724 725TEST(DenseMapCustomTest, LookupOrConstness) {726 DenseMap<int, unsigned *> M;727 unsigned Default = 3u;728 unsigned *Ret = M.lookup_or(0, &Default);729 EXPECT_EQ(Ret, &Default);730}731 732// Key traits that allows lookup with either an unsigned or char* key;733// In the latter case, "a" == 0, "b" == 1 and so on.734struct TestDenseMapInfo {735 static inline unsigned getEmptyKey() { return ~0; }736 static inline unsigned getTombstoneKey() { return ~0U - 1; }737 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }738 static unsigned getHashValue(const char* Val) {739 return (unsigned)(Val[0] - 'a') * 37U;740 }741 static bool isEqual(const unsigned& LHS, const unsigned& RHS) {742 return LHS == RHS;743 }744 static bool isEqual(const char* LHS, const unsigned& RHS) {745 return (unsigned)(LHS[0] - 'a') == RHS;746 }747};748 749// find_as() tests750TEST(DenseMapCustomTest, FindAsTest) {751 DenseMap<unsigned, unsigned, TestDenseMapInfo> map;752 map[0] = 1;753 map[1] = 2;754 map[2] = 3;755 756 // Size tests757 EXPECT_EQ(3u, map.size());758 759 // Normal lookup tests760 EXPECT_EQ(1u, map.count(1));761 EXPECT_EQ(1u, map.find(0)->second);762 EXPECT_EQ(2u, map.find(1)->second);763 EXPECT_EQ(3u, map.find(2)->second);764 EXPECT_TRUE(map.find(3) == map.end());765 766 // find_as() tests767 EXPECT_EQ(1u, map.find_as("a")->second);768 EXPECT_EQ(2u, map.find_as("b")->second);769 EXPECT_EQ(3u, map.find_as("c")->second);770 EXPECT_TRUE(map.find_as("d") == map.end());771}772 773TEST(DenseMapCustomTest, SmallDenseMapFromRange) {774 std::pair<int, StringRef> PlainArray[] = {{0, "0"}, {1, "1"}, {2, "2"}};775 SmallDenseMap<int, StringRef> M(llvm::from_range, PlainArray);776 EXPECT_EQ(3u, M.size());777 using testing::Pair;778 EXPECT_THAT(M, testing::UnorderedElementsAre(Pair(0, "0"), Pair(1, "1"),779 Pair(2, "2")));780}781 782TEST(DenseMapCustomTest, SmallDenseMapInitializerList) {783 SmallDenseMap<int, int> M = {{0, 0}, {0, 1}, {1, 2}};784 EXPECT_EQ(2u, M.size());785 EXPECT_EQ(1u, M.count(0));786 EXPECT_EQ(0, M[0]);787 EXPECT_EQ(1u, M.count(1));788 EXPECT_EQ(2, M[1]);789}790 791struct ContiguousDenseMapInfo {792 static inline unsigned getEmptyKey() { return ~0; }793 static inline unsigned getTombstoneKey() { return ~0U - 1; }794 static unsigned getHashValue(const unsigned& Val) { return Val; }795 static bool isEqual(const unsigned& LHS, const unsigned& RHS) {796 return LHS == RHS;797 }798};799 800// Test that filling a small dense map with exactly the number of elements in801// the map grows to have enough space for an empty bucket.802TEST(DenseMapCustomTest, SmallDenseMapGrowTest) {803 SmallDenseMap<unsigned, unsigned, 32, ContiguousDenseMapInfo> map;804 // Add some number of elements, then delete a few to leave us some tombstones.805 // If we just filled the map with 32 elements we'd grow because of not enough806 // tombstones which masks the issue here.807 for (unsigned i = 0; i < 20; ++i)808 map[i] = i + 1;809 for (unsigned i = 0; i < 10; ++i)810 map.erase(i);811 for (unsigned i = 20; i < 32; ++i)812 map[i] = i + 1;813 814 // Size tests815 EXPECT_EQ(22u, map.size());816 817 // Try to find an element which doesn't exist. There was a bug in818 // SmallDenseMap which led to a map with num elements == small capacity not819 // having an empty bucket any more. Finding an element not in the map would820 // therefore never terminate.821 EXPECT_TRUE(map.find(32) == map.end());822}823 824TEST(DenseMapCustomTest, LargeSmallDenseMapCompaction) {825 SmallDenseMap<unsigned, unsigned, 128, ContiguousDenseMapInfo> map;826 // Fill to < 3/4 load.827 for (unsigned i = 0; i < 95; ++i)828 map[i] = i;829 // And erase, leaving behind tombstones.830 for (unsigned i = 0; i < 95; ++i)831 map.erase(i);832 // Fill further, so that less than 1/8 are empty, but still below 3/4 load.833 for (unsigned i = 95; i < 128; ++i)834 map[i] = i;835 836 EXPECT_EQ(33u, map.size());837 // Similar to the previous test, check for a non-existing element, as an838 // indirect check that tombstones have been removed.839 EXPECT_TRUE(map.find(0) == map.end());840}841 842TEST(DenseMapCustomTest, SmallDenseMapWithNumBucketsNonPowerOf2) {843 // Is not power of 2.844 const unsigned NumInitBuckets = 33;845 // Power of 2 less then NumInitBuckets.846 constexpr unsigned InlineBuckets = 4;847 // Constructor should not trigger assert.848 SmallDenseMap<int, int, InlineBuckets> map(NumInitBuckets);849}850 851TEST(DenseMapCustomTest, TryEmplaceTest) {852 DenseMap<int, std::unique_ptr<int>> Map;853 std::unique_ptr<int> P(new int(2));854 auto Try1 = Map.try_emplace(0, new int(1));855 EXPECT_TRUE(Try1.second);856 auto Try2 = Map.try_emplace(0, std::move(P));857 EXPECT_FALSE(Try2.second);858 EXPECT_EQ(Try1.first, Try2.first);859 EXPECT_NE(nullptr, P);860}861 862TEST(DenseMapCustomTest, ConstTest) {863 // Test that const pointers work okay for count and find, even when the864 // underlying map is a non-const pointer.865 DenseMap<int *, int> Map;866 int A;867 int *B = &A;868 const int *C = &A;869 Map.insert({B, 0});870 EXPECT_EQ(Map.count(B), 1u);871 EXPECT_EQ(Map.count(C), 1u);872 EXPECT_NE(Map.find(B), Map.end());873 EXPECT_NE(Map.find(C), Map.end());874}875 876struct IncompleteStruct;877 878TEST(DenseMapCustomTest, OpaquePointerKey) {879 // Test that we can use a pointer to an incomplete type as a DenseMap key.880 // This is an important build time optimization, since many classes have881 // DenseMap members.882 DenseMap<IncompleteStruct *, int> Map;883 int Keys[3] = {0, 0, 0};884 IncompleteStruct *K1 = reinterpret_cast<IncompleteStruct *>(&Keys[0]);885 IncompleteStruct *K2 = reinterpret_cast<IncompleteStruct *>(&Keys[1]);886 IncompleteStruct *K3 = reinterpret_cast<IncompleteStruct *>(&Keys[2]);887 Map.insert({K1, 1});888 Map.insert({K2, 2});889 Map.insert({K3, 3});890 EXPECT_EQ(Map.count(K1), 1u);891 EXPECT_EQ(Map[K1], 1);892 EXPECT_EQ(Map[K2], 2);893 EXPECT_EQ(Map[K3], 3);894 Map.clear();895 EXPECT_EQ(Map.find(K1), Map.end());896 EXPECT_EQ(Map.find(K2), Map.end());897 EXPECT_EQ(Map.find(K3), Map.end());898}899} // namespace900 901namespace {902struct A {903 A(int value) : value(value) {}904 int value;905};906struct B : public A {907 using A::A;908};909 910struct AlwaysEqType {911 bool operator==(const AlwaysEqType &RHS) const { return true; }912};913} // namespace914 915namespace llvm {916template <typename T>917struct DenseMapInfo<T, std::enable_if_t<std::is_base_of_v<A, T>>> {918 static inline T getEmptyKey() { return {static_cast<int>(~0)}; }919 static inline T getTombstoneKey() { return {static_cast<int>(~0U - 1)}; }920 static unsigned getHashValue(const T &Val) { return Val.value; }921 static bool isEqual(const T &LHS, const T &RHS) {922 return LHS.value == RHS.value;923 }924};925 926template <> struct DenseMapInfo<AlwaysEqType> {927 using T = AlwaysEqType;928 static inline T getEmptyKey() { return {}; }929 static inline T getTombstoneKey() { return {}; }930 static unsigned getHashValue(const T &Val) { return 0; }931 static bool isEqual(const T &LHS, const T &RHS) {932 return false;933 }934};935} // namespace llvm936 937namespace {938TEST(DenseMapCustomTest, SFINAEMapInfo) {939 // Test that we can use a pointer to an incomplete type as a DenseMap key.940 // This is an important build time optimization, since many classes have941 // DenseMap members.942 DenseMap<B, int> Map;943 B Keys[3] = {{0}, {1}, {2}};944 Map.insert({Keys[0], 1});945 Map.insert({Keys[1], 2});946 Map.insert({Keys[2], 3});947 EXPECT_EQ(Map.count(Keys[0]), 1u);948 EXPECT_EQ(Map[Keys[0]], 1);949 EXPECT_EQ(Map[Keys[1]], 2);950 EXPECT_EQ(Map[Keys[2]], 3);951 Map.clear();952 EXPECT_EQ(Map.find(Keys[0]), Map.end());953 EXPECT_EQ(Map.find(Keys[1]), Map.end());954 EXPECT_EQ(Map.find(Keys[2]), Map.end());955}956 957TEST(DenseMapCustomTest, VariantSupport) {958 using variant = std::variant<int, int, AlwaysEqType>;959 DenseMap<variant, int> Map;960 variant Keys[] = {961 variant(std::in_place_index<0>, 1),962 variant(std::in_place_index<1>, 1),963 variant(std::in_place_index<2>),964 };965 Map.try_emplace(Keys[0], 0);966 Map.try_emplace(Keys[1], 1);967 EXPECT_THAT(Map, testing::SizeIs(2));968 EXPECT_NE(DenseMapInfo<variant>::getHashValue(Keys[0]),969 DenseMapInfo<variant>::getHashValue(Keys[1]));970 // Check that isEqual dispatches to isEqual of underlying type, and not to971 // operator==.972 EXPECT_FALSE(DenseMapInfo<variant>::isEqual(Keys[2], Keys[2]));973}974 975// Test that gTest prints map entries as pairs instead of opaque objects.976// See third-party/unittest/googletest/internal/custom/gtest-printers.h977TEST(DenseMapCustomTest, PairPrinting) {978 DenseMap<int, StringRef> Map = {{1, "one"}, {2, "two"}};979 EXPECT_EQ(R"({ (1, "one"), (2, "two") })", ::testing::PrintToString(Map));980}981 982TEST(DenseMapCustomTest, InitSize) {983 constexpr unsigned ElemSize = sizeof(std::pair<int *, int>);984 985 {986 DenseMap<int *, int> Map;987 EXPECT_EQ(ElemSize * 0U, Map.getMemorySize());988 }989 {990 DenseMap<int *, int> Map(0);991 EXPECT_EQ(ElemSize * 0U, Map.getMemorySize());992 }993 {994 DenseMap<int *, int> Map(1);995 EXPECT_EQ(ElemSize * 4U, Map.getMemorySize());996 }997 {998 DenseMap<int *, int> Map(2);999 EXPECT_EQ(ElemSize * 4U, Map.getMemorySize());1000 }1001 {1002 DenseMap<int *, int> Map(3);1003 EXPECT_EQ(ElemSize * 8U, Map.getMemorySize());1004 }1005 {1006 int A, B;1007 DenseMap<int *, int> Map = {{&A, 1}, {&B, 2}};1008 EXPECT_EQ(ElemSize * 4U, Map.getMemorySize());1009 }1010 {1011 int A, B, C;1012 DenseMap<int *, int> Map = {{&A, 1}, {&B, 2}, {&C, 3}};1013 EXPECT_EQ(ElemSize * 8U, Map.getMemorySize());1014 }1015}1016 1017TEST(SmallDenseMapCustomTest, InitSize) {1018 constexpr unsigned ElemSize = sizeof(std::pair<int *, int>);1019 {1020 SmallDenseMap<int *, int> Map;1021 EXPECT_EQ(ElemSize * 4U, Map.getMemorySize());1022 }1023 {1024 SmallDenseMap<int *, int> Map(0);1025 EXPECT_EQ(ElemSize * 4U, Map.getMemorySize());1026 }1027 {1028 SmallDenseMap<int *, int> Map(1);1029 EXPECT_EQ(ElemSize * 4U, Map.getMemorySize());1030 }1031 {1032 SmallDenseMap<int *, int> Map(2);1033 EXPECT_EQ(ElemSize * 4U, Map.getMemorySize());1034 }1035 {1036 SmallDenseMap<int *, int> Map(3);1037 EXPECT_EQ(ElemSize * 8U, Map.getMemorySize());1038 }1039 {1040 int A, B;1041 SmallDenseMap<int *, int> Map = {{&A, 1}, {&B, 2}};1042 EXPECT_EQ(ElemSize * 4U, Map.getMemorySize());1043 }1044 {1045 int A, B, C;1046 SmallDenseMap<int *, int> Map = {{&A, 1}, {&B, 2}, {&C, 3}};1047 EXPECT_EQ(ElemSize * 8U, Map.getMemorySize());1048 }1049}1050 1051TEST(DenseMapCustomTest, KeyDtor) {1052 // This test relies on CtorTester being non-trivially destructible.1053 static_assert(!std::is_trivially_destructible_v<CtorTester>,1054 "CtorTester must not be trivially destructible");1055 1056 // Test that keys are destructed on scope exit.1057 EXPECT_EQ(0u, CtorTester::getNumConstructed());1058 {1059 DenseMap<CtorTester, int, CtorTesterMapInfo> Map;1060 Map.try_emplace(CtorTester(0), 1);1061 Map.try_emplace(CtorTester(1), 2);1062 EXPECT_EQ(2u, CtorTester::getNumConstructed());1063 }1064 EXPECT_EQ(0u, CtorTester::getNumConstructed());1065 1066 // Test that keys are destructed on erase and shrink_and_clear.1067 EXPECT_EQ(0u, CtorTester::getNumConstructed());1068 {1069 DenseMap<CtorTester, int, CtorTesterMapInfo> Map;1070 Map.try_emplace(CtorTester(0), 1);1071 Map.try_emplace(CtorTester(1), 2);1072 EXPECT_EQ(2u, CtorTester::getNumConstructed());1073 Map.erase(CtorTester(1));1074 EXPECT_EQ(1u, CtorTester::getNumConstructed());1075 Map.shrink_and_clear();1076 EXPECT_EQ(0u, CtorTester::getNumConstructed());1077 }1078 EXPECT_EQ(0u, CtorTester::getNumConstructed());1079}1080 1081TEST(DenseMapCustomTest, ValueDtor) {1082 // This test relies on CtorTester being non-trivially destructible.1083 static_assert(!std::is_trivially_destructible_v<CtorTester>,1084 "CtorTester must not be trivially destructible");1085 1086 // Test that values are destructed on scope exit.1087 EXPECT_EQ(0u, CtorTester::getNumConstructed());1088 {1089 DenseMap<int, CtorTester> Map;1090 Map.try_emplace(0, CtorTester(1));1091 Map.try_emplace(1, CtorTester(2));1092 EXPECT_EQ(2u, CtorTester::getNumConstructed());1093 }1094 EXPECT_EQ(0u, CtorTester::getNumConstructed());1095 1096 // Test that values are destructed on erase and shrink_and_clear.1097 EXPECT_EQ(0u, CtorTester::getNumConstructed());1098 {1099 DenseMap<int, CtorTester> Map;1100 Map.try_emplace(0, CtorTester(1));1101 Map.try_emplace(1, CtorTester(2));1102 EXPECT_EQ(2u, CtorTester::getNumConstructed());1103 Map.erase(1);1104 EXPECT_EQ(1u, CtorTester::getNumConstructed());1105 Map.shrink_and_clear();1106 EXPECT_EQ(0u, CtorTester::getNumConstructed());1107 }1108 EXPECT_EQ(0u, CtorTester::getNumConstructed());1109}1110 1111} // namespace1112