551 lines · cpp
1//===- sanitizer_dense_map_test.cpp -----------------------------*- 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 "sanitizer_common/sanitizer_dense_map.h"10 11#include <initializer_list>12#include <map>13#include <set>14 15#include "gtest/gtest.h"16 17using namespace __sanitizer;18 19namespace {20 21// Helps to keep some tests.22template <typename KeyT, typename ValueT,23 typename KeyInfoT = DenseMapInfo<KeyT>>24class TestDenseMap : public DenseMap<KeyT, ValueT, KeyInfoT> {25 using BaseT = DenseMap<KeyT, ValueT, KeyInfoT>;26 27 public:28 using BaseT::BaseT;29 30 TestDenseMap(std::initializer_list<typename BaseT::value_type> Vals)31 : BaseT(Vals.size()) {32 for (const auto &V : Vals) this->BaseT::insert(V);33 }34 35 template <typename I>36 TestDenseMap(I B, I E) : BaseT(std::distance(B, E)) {37 for (; B != E; ++B) this->BaseT::insert(*B);38 }39};40 41template <typename... T>42using DenseMap = TestDenseMap<T...>;43 44uint32_t getTestKey(int i, uint32_t *) { return i; }45uint32_t getTestValue(int i, uint32_t *) { return 42 + i; }46 47uint32_t *getTestKey(int i, uint32_t **) {48 static uint32_t dummy_arr1[8192];49 assert(i < 8192 && "Only support 8192 dummy keys.");50 return &dummy_arr1[i];51}52uint32_t *getTestValue(int i, uint32_t **) {53 static uint32_t dummy_arr1[8192];54 assert(i < 8192 && "Only support 8192 dummy keys.");55 return &dummy_arr1[i];56}57 58/// A test class that tries to check that construction and destruction59/// occur correctly.60class CtorTester {61 static std::set<CtorTester *> Constructed;62 int Value;63 64 public:65 explicit CtorTester(int Value = 0) : Value(Value) {66 EXPECT_TRUE(Constructed.insert(this).second);67 }68 CtorTester(uint32_t Value) : Value(Value) {69 EXPECT_TRUE(Constructed.insert(this).second);70 }71 CtorTester(const CtorTester &Arg) : Value(Arg.Value) {72 EXPECT_TRUE(Constructed.insert(this).second);73 }74 CtorTester &operator=(const CtorTester &) = default;75 ~CtorTester() { EXPECT_EQ(1u, Constructed.erase(this)); }76 operator uint32_t() const { return Value; }77 78 int getValue() const { return Value; }79 bool operator==(const CtorTester &RHS) const { return Value == RHS.Value; }80};81 82std::set<CtorTester *> CtorTester::Constructed;83 84struct CtorTesterMapInfo {85 static inline CtorTester getEmptyKey() { return CtorTester(-1); }86 static inline CtorTester getTombstoneKey() { return CtorTester(-2); }87 static unsigned getHashValue(const CtorTester &Val) {88 return Val.getValue() * 37u;89 }90 static bool isEqual(const CtorTester &LHS, const CtorTester &RHS) {91 return LHS == RHS;92 }93};94 95CtorTester getTestKey(int i, CtorTester *) { return CtorTester(i); }96CtorTester getTestValue(int i, CtorTester *) { return CtorTester(42 + i); }97 98// Test fixture, with helper functions implemented by forwarding to global99// function overloads selected by component types of the type parameter. This100// allows all of the map implementations to be tested with shared101// implementations of helper routines.102template <typename T>103class DenseMapTest : public ::testing::Test {104 protected:105 T Map;106 107 static typename T::key_type *const dummy_key_ptr;108 static typename T::mapped_type *const dummy_value_ptr;109 110 typename T::key_type getKey(int i = 0) {111 return getTestKey(i, dummy_key_ptr);112 }113 typename T::mapped_type getValue(int i = 0) {114 return getTestValue(i, dummy_value_ptr);115 }116};117 118template <typename T>119typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = nullptr;120template <typename T>121typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = nullptr;122 123// Register these types for testing.124typedef ::testing::Types<DenseMap<uint32_t, uint32_t>,125 DenseMap<uint32_t *, uint32_t *>,126 DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>>127 DenseMapTestTypes;128TYPED_TEST_SUITE(DenseMapTest, DenseMapTestTypes, );129 130// Empty map tests131TYPED_TEST(DenseMapTest, EmptyIntMapTest) {132 // Size tests133 EXPECT_EQ(0u, this->Map.size());134 EXPECT_TRUE(this->Map.empty());135 136 // Lookup tests137 EXPECT_FALSE(this->Map.count(this->getKey()));138 EXPECT_EQ(nullptr, this->Map.find(this->getKey()));139 EXPECT_EQ(typename TypeParam::mapped_type(),140 this->Map.lookup(this->getKey()));141}142 143// Constant map tests144TYPED_TEST(DenseMapTest, ConstEmptyMapTest) {145 const TypeParam &ConstMap = this->Map;146 EXPECT_EQ(0u, ConstMap.size());147 EXPECT_TRUE(ConstMap.empty());148}149 150// A map with a single entry151TYPED_TEST(DenseMapTest, SingleEntryMapTest) {152 this->Map[this->getKey()] = this->getValue();153 154 // Size tests155 EXPECT_EQ(1u, this->Map.size());156 EXPECT_FALSE(this->Map.empty());157 158 // Lookup tests159 EXPECT_TRUE(this->Map.count(this->getKey()));160 EXPECT_NE(nullptr, this->Map.find(this->getKey()));161 EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey()));162 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);163}164 165// Test clear() method166TYPED_TEST(DenseMapTest, ClearTest) {167 this->Map[this->getKey()] = this->getValue();168 this->Map.clear();169 170 EXPECT_EQ(0u, this->Map.size());171 EXPECT_TRUE(this->Map.empty());172}173 174// Test erase(iterator) method175TYPED_TEST(DenseMapTest, EraseTest) {176 this->Map[this->getKey()] = this->getValue();177 this->Map.erase(this->Map.find(this->getKey()));178 179 EXPECT_EQ(0u, this->Map.size());180 EXPECT_TRUE(this->Map.empty());181}182 183// Test erase(value) method184TYPED_TEST(DenseMapTest, EraseTest2) {185 this->Map[this->getKey()] = this->getValue();186 this->Map.erase(this->getKey());187 188 EXPECT_EQ(0u, this->Map.size());189 EXPECT_TRUE(this->Map.empty());190}191 192// Test insert() method193TYPED_TEST(DenseMapTest, InsertTest) {194 this->Map.insert(195 typename TypeParam::value_type(this->getKey(), this->getValue()));196 EXPECT_EQ(1u, this->Map.size());197 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);198}199 200// Test copy constructor method201TYPED_TEST(DenseMapTest, CopyConstructorTest) {202 this->Map[this->getKey()] = this->getValue();203 TypeParam copyMap(this->Map);204 205 EXPECT_EQ(1u, copyMap.size());206 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]);207}208 209// Test copy constructor method where SmallDenseMap isn't small.210TYPED_TEST(DenseMapTest, CopyConstructorNotSmallTest) {211 for (int Key = 0; Key < 5; ++Key)212 this->Map[this->getKey(Key)] = this->getValue(Key);213 TypeParam copyMap(this->Map);214 215 EXPECT_EQ(5u, copyMap.size());216 for (int Key = 0; Key < 5; ++Key)217 EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]);218}219 220// Test copying from a default-constructed map.221TYPED_TEST(DenseMapTest, CopyConstructorFromDefaultTest) {222 TypeParam copyMap(this->Map);223 224 EXPECT_TRUE(copyMap.empty());225}226 227// Test copying from an empty map where SmallDenseMap isn't small.228TYPED_TEST(DenseMapTest, CopyConstructorFromEmptyTest) {229 for (int Key = 0; Key < 5; ++Key)230 this->Map[this->getKey(Key)] = this->getValue(Key);231 this->Map.clear();232 TypeParam copyMap(this->Map);233 234 EXPECT_TRUE(copyMap.empty());235}236 237// Test assignment operator method238TYPED_TEST(DenseMapTest, AssignmentTest) {239 this->Map[this->getKey()] = this->getValue();240 TypeParam copyMap = this->Map;241 242 EXPECT_EQ(1u, copyMap.size());243 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]);244 245 // test self-assignment.246 copyMap = static_cast<TypeParam &>(copyMap);247 EXPECT_EQ(1u, copyMap.size());248 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]);249}250 251TYPED_TEST(DenseMapTest, AssignmentTestNotSmall) {252 for (int Key = 0; Key < 5; ++Key)253 this->Map[this->getKey(Key)] = this->getValue(Key);254 TypeParam copyMap = this->Map;255 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 // test self-assignment.261 copyMap = static_cast<TypeParam &>(copyMap);262 EXPECT_EQ(5u, copyMap.size());263 for (int Key = 0; Key < 5; ++Key)264 EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]);265}266 267// Test swap method268TYPED_TEST(DenseMapTest, SwapTest) {269 this->Map[this->getKey()] = this->getValue();270 TypeParam otherMap;271 272 this->Map.swap(otherMap);273 EXPECT_EQ(0u, this->Map.size());274 EXPECT_TRUE(this->Map.empty());275 EXPECT_EQ(1u, otherMap.size());276 EXPECT_EQ(this->getValue(), otherMap[this->getKey()]);277 278 this->Map.swap(otherMap);279 EXPECT_EQ(0u, otherMap.size());280 EXPECT_TRUE(otherMap.empty());281 EXPECT_EQ(1u, this->Map.size());282 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);283 284 // Make this more interesting by inserting 100 numbers into the map.285 for (int i = 0; i < 100; ++i) this->Map[this->getKey(i)] = this->getValue(i);286 287 this->Map.swap(otherMap);288 EXPECT_EQ(0u, this->Map.size());289 EXPECT_TRUE(this->Map.empty());290 EXPECT_EQ(100u, otherMap.size());291 for (int i = 0; i < 100; ++i)292 EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]);293 294 this->Map.swap(otherMap);295 EXPECT_EQ(0u, otherMap.size());296 EXPECT_TRUE(otherMap.empty());297 EXPECT_EQ(100u, this->Map.size());298 for (int i = 0; i < 100; ++i)299 EXPECT_EQ(this->getValue(i), this->Map[this->getKey(i)]);300}301 302// A more complex iteration test303TYPED_TEST(DenseMapTest, IterationTest) {304 int visited[100];305 std::map<typename TypeParam::key_type, unsigned> visitedIndex;306 307 // Insert 100 numbers into the map308 for (int i = 0; i < 100; ++i) {309 visited[i] = 0;310 visitedIndex[this->getKey(i)] = i;311 312 this->Map[this->getKey(i)] = this->getValue(i);313 }314 315 // Iterate over all numbers and mark each one found.316 this->Map.forEach([&](const typename TypeParam::value_type &kv) {317 ++visited[visitedIndex[kv.first]];318 return true;319 });320 321 // Ensure every number was visited.322 for (int i = 0; i < 100; ++i) ASSERT_EQ(1, visited[i]);323}324 325namespace {326// Simple class that counts how many moves and copy happens when growing a map327struct CountCopyAndMove {328 static int Move;329 static int Copy;330 CountCopyAndMove() {}331 332 CountCopyAndMove(const CountCopyAndMove &) { Copy++; }333 CountCopyAndMove &operator=(const CountCopyAndMove &) {334 Copy++;335 return *this;336 }337 CountCopyAndMove(CountCopyAndMove &&) { Move++; }338 CountCopyAndMove &operator=(const CountCopyAndMove &&) {339 Move++;340 return *this;341 }342};343int CountCopyAndMove::Copy = 0;344int CountCopyAndMove::Move = 0;345 346} // anonymous namespace347 348// Test initializer list construction.349TEST(DenseMapCustomTest, InitializerList) {350 DenseMap<int, int> M({{0, 0}, {0, 1}, {1, 2}});351 EXPECT_EQ(2u, M.size());352 EXPECT_EQ(1u, M.count(0));353 EXPECT_EQ(0, M[0]);354 EXPECT_EQ(1u, M.count(1));355 EXPECT_EQ(2, M[1]);356}357 358// Test initializer list construction.359TEST(DenseMapCustomTest, EqualityComparison) {360 DenseMap<int, int> M1({{0, 0}, {1, 2}});361 DenseMap<int, int> M2({{0, 0}, {1, 2}});362 DenseMap<int, int> M3({{0, 0}, {1, 3}});363 364 EXPECT_EQ(M1, M2);365 EXPECT_NE(M1, M3);366}367 368const int ExpectedInitialBucketCount = GetPageSizeCached() / /* sizeof(KV) */ 8;369 370// Test for the default minimum size of a DenseMap371TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) {372 // Formula from DenseMap::getMinBucketToReserveForEntries()373 const int ExpectedMaxInitialEntries = ExpectedInitialBucketCount * 3 / 4 - 1;374 375 DenseMap<int, CountCopyAndMove> Map;376 // Will allocate 64 buckets377 Map.reserve(1);378 unsigned MemorySize = Map.getMemorySize();379 CountCopyAndMove::Copy = 0;380 CountCopyAndMove::Move = 0;381 for (int i = 0; i < ExpectedMaxInitialEntries; ++i) {382 detail::DenseMapPair<int, CountCopyAndMove> KV;383 KV.first = i;384 Map.insert(move(KV));385 }386 // Check that we didn't grow387 EXPECT_EQ(MemorySize, Map.getMemorySize());388 // Check that move was called the expected number of times389 EXPECT_EQ(ExpectedMaxInitialEntries, CountCopyAndMove::Move);390 // Check that no copy occurred391 EXPECT_EQ(0, CountCopyAndMove::Copy);392 393 // Adding one extra element should grow the map394 detail::DenseMapPair<int, CountCopyAndMove> KV;395 KV.first = ExpectedMaxInitialEntries;396 Map.insert(move(KV));397 // Check that we grew398 EXPECT_NE(MemorySize, Map.getMemorySize());399 // Check that move was called the expected number of times400 // This relies on move-construction elision, and cannot be reliably tested.401 // EXPECT_EQ(ExpectedMaxInitialEntries + 2, CountCopyAndMove::Move);402 // Check that no copy occurred403 EXPECT_EQ(0, CountCopyAndMove::Copy);404}405 406// Make sure creating the map with an initial size of N actually gives us enough407// buckets to insert N items without increasing allocation size.408TEST(DenseMapCustomTest, InitialSizeTest) {409 // Test a few different size, 341 is *not* a random choice: we need a value410 // that is 2/3 of a power of two to stress the grow() condition, and the power411 // of two has to be at least 512 because of minimum size allocation in the412 // DenseMap (see DefaultMinReservedSizeTest).413 for (auto Size : {1, 2, 48, 66, 341, ExpectedInitialBucketCount + 1}) {414 DenseMap<int, CountCopyAndMove> Map(Size);415 unsigned MemorySize = Map.getMemorySize();416 CountCopyAndMove::Copy = 0;417 CountCopyAndMove::Move = 0;418 for (int i = 0; i < Size; ++i) {419 detail::DenseMapPair<int, CountCopyAndMove> KV;420 KV.first = i;421 Map.insert(move(KV));422 }423 // Check that we didn't grow424 EXPECT_EQ(MemorySize, Map.getMemorySize());425 // Check that move was called the expected number of times426 EXPECT_EQ(Size, CountCopyAndMove::Move);427 // Check that no copy occurred428 EXPECT_EQ(0, CountCopyAndMove::Copy);429 }430}431 432// Make sure creating the map with a iterator range does not trigger grow()433TEST(DenseMapCustomTest, InitFromIterator) {434 std::vector<detail::DenseMapPair<int, CountCopyAndMove>> Values;435 // The size is a random value greater than 64 (hardcoded DenseMap min init)436 const int Count = 65;437 for (int i = 0; i < Count; i++) Values.emplace_back(i, CountCopyAndMove());438 439 CountCopyAndMove::Move = 0;440 CountCopyAndMove::Copy = 0;441 DenseMap<int, CountCopyAndMove> Map(Values.begin(), Values.end());442 // Check that no move occurred443 EXPECT_EQ(0, CountCopyAndMove::Move);444 // Check that copy was called the expected number of times445 EXPECT_EQ(Count, CountCopyAndMove::Copy);446}447 448// Make sure reserve actually gives us enough buckets to insert N items449// without increasing allocation size.450TEST(DenseMapCustomTest, ReserveTest) {451 // Test a few different size, 341 is *not* a random choice: we need a value452 // that is 2/3 of a power of two to stress the grow() condition, and the power453 // of two has to be at least 512 because of minimum size allocation in the454 // DenseMap (see DefaultMinReservedSizeTest).455 for (auto Size : {1, 2, 48, 66, 341, ExpectedInitialBucketCount + 1}) {456 DenseMap<int, CountCopyAndMove> Map;457 Map.reserve(Size);458 unsigned MemorySize = Map.getMemorySize();459 CountCopyAndMove::Copy = 0;460 CountCopyAndMove::Move = 0;461 for (int i = 0; i < Size; ++i) {462 detail::DenseMapPair<int, CountCopyAndMove> KV;463 KV.first = i;464 Map.insert(move(KV));465 }466 // Check that we didn't grow467 EXPECT_EQ(MemorySize, Map.getMemorySize());468 // Check that move was called the expected number of times469 EXPECT_EQ(Size, CountCopyAndMove::Move);470 // Check that no copy occurred471 EXPECT_EQ(0, CountCopyAndMove::Copy);472 }473}474 475// Key traits that allows lookup with either an unsigned or char* key;476// In the latter case, "a" == 0, "b" == 1 and so on.477struct TestDenseMapInfo {478 static inline unsigned getEmptyKey() { return ~0; }479 static inline unsigned getTombstoneKey() { return ~0U - 1; }480 static unsigned getHashValue(const unsigned &Val) { return Val * 37U; }481 static unsigned getHashValue(const char *Val) {482 return (unsigned)(Val[0] - 'a') * 37U;483 }484 static bool isEqual(const unsigned &LHS, const unsigned &RHS) {485 return LHS == RHS;486 }487 static bool isEqual(const char *LHS, const unsigned &RHS) {488 return (unsigned)(LHS[0] - 'a') == RHS;489 }490};491 492// find_as() tests493TEST(DenseMapCustomTest, FindAsTest) {494 DenseMap<unsigned, unsigned, TestDenseMapInfo> map;495 map[0] = 1;496 map[1] = 2;497 map[2] = 3;498 499 // Size tests500 EXPECT_EQ(3u, map.size());501 502 // Normal lookup tests503 EXPECT_EQ(1u, map.count(1));504 EXPECT_EQ(1u, map.find(0)->second);505 EXPECT_EQ(2u, map.find(1)->second);506 EXPECT_EQ(3u, map.find(2)->second);507 EXPECT_EQ(nullptr, map.find(3));508 509 // find_as() tests510 EXPECT_EQ(1u, map.find_as("a")->second);511 EXPECT_EQ(2u, map.find_as("b")->second);512 EXPECT_EQ(3u, map.find_as("c")->second);513 EXPECT_EQ(nullptr, map.find_as("d"));514}515 516TEST(DenseMapCustomTest, TryEmplaceTest) {517 DenseMap<int, std::unique_ptr<int>> Map;518 std::unique_ptr<int> P(new int(2));519 auto Try1 = Map.try_emplace(0, new int(1));520 EXPECT_TRUE(Try1.second);521 auto Try2 = Map.try_emplace(0, std::move(P));522 EXPECT_FALSE(Try2.second);523 EXPECT_EQ(Try1.first, Try2.first);524 EXPECT_NE(nullptr, P);525}526 527struct IncompleteStruct;528 529TEST(DenseMapCustomTest, OpaquePointerKey) {530 // Test that we can use a pointer to an incomplete type as a DenseMap key.531 // This is an important build time optimization, since many classes have532 // DenseMap members.533 DenseMap<IncompleteStruct *, int> Map;534 int Keys[3] = {0, 0, 0};535 IncompleteStruct *K1 = reinterpret_cast<IncompleteStruct *>(&Keys[0]);536 IncompleteStruct *K2 = reinterpret_cast<IncompleteStruct *>(&Keys[1]);537 IncompleteStruct *K3 = reinterpret_cast<IncompleteStruct *>(&Keys[2]);538 Map.insert({K1, 1});539 Map.insert({K2, 2});540 Map.insert({K3, 3});541 EXPECT_EQ(Map.count(K1), 1u);542 EXPECT_EQ(Map[K1], 1);543 EXPECT_EQ(Map[K2], 2);544 EXPECT_EQ(Map[K3], 3);545 Map.clear();546 EXPECT_EQ(nullptr, Map.find(K1));547 EXPECT_EQ(nullptr, Map.find(K2));548 EXPECT_EQ(nullptr, Map.find(K3));549}550} // namespace551