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-exception 6// 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 destruction 59/// 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 global 99// function overloads selected by component types of the type parameter. This 100// allows all of the map implementations to be tested with shared 101// 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 tests 131TYPED_TEST(DenseMapTest, EmptyIntMapTest) { 132 // Size tests 133 EXPECT_EQ(0u, this->Map.size()); 134 EXPECT_TRUE(this->Map.empty()); 135 136 // Lookup tests 137 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 tests 144TYPED_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 entry 151TYPED_TEST(DenseMapTest, SingleEntryMapTest) { 152 this->Map[this->getKey()] = this->getValue(); 153 154 // Size tests 155 EXPECT_EQ(1u, this->Map.size()); 156 EXPECT_FALSE(this->Map.empty()); 157 158 // Lookup tests 159 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() method 166TYPED_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) method 175TYPED_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) method 184TYPED_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() method 193TYPED_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 method 201TYPED_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 method 238TYPED_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 method 268TYPED_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 test 303TYPED_TEST(DenseMapTest, IterationTest) { 304 int visited[100]; 305 std::map<typename TypeParam::key_type, unsigned> visitedIndex; 306 307 // Insert 100 numbers into the map 308 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 map 327struct 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 namespace 347 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 DenseMap 371TEST(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 buckets 377 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 grow 387 EXPECT_EQ(MemorySize, Map.getMemorySize()); 388 // Check that move was called the expected number of times 389 EXPECT_EQ(ExpectedMaxInitialEntries, CountCopyAndMove::Move); 390 // Check that no copy occurred 391 EXPECT_EQ(0, CountCopyAndMove::Copy); 392 393 // Adding one extra element should grow the map 394 detail::DenseMapPair<int, CountCopyAndMove> KV; 395 KV.first = ExpectedMaxInitialEntries; 396 Map.insert(move(KV)); 397 // Check that we grew 398 EXPECT_NE(MemorySize, Map.getMemorySize()); 399 // Check that move was called the expected number of times 400 // This relies on move-construction elision, and cannot be reliably tested. 401 // EXPECT_EQ(ExpectedMaxInitialEntries + 2, CountCopyAndMove::Move); 402 // Check that no copy occurred 403 EXPECT_EQ(0, CountCopyAndMove::Copy); 404} 405 406// Make sure creating the map with an initial size of N actually gives us enough 407// 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 value 410 // that is 2/3 of a power of two to stress the grow() condition, and the power 411 // of two has to be at least 512 because of minimum size allocation in the 412 // 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 grow 424 EXPECT_EQ(MemorySize, Map.getMemorySize()); 425 // Check that move was called the expected number of times 426 EXPECT_EQ(Size, CountCopyAndMove::Move); 427 // Check that no copy occurred 428 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 occurred 443 EXPECT_EQ(0, CountCopyAndMove::Move); 444 // Check that copy was called the expected number of times 445 EXPECT_EQ(Count, CountCopyAndMove::Copy); 446} 447 448// Make sure reserve actually gives us enough buckets to insert N items 449// without increasing allocation size. 450TEST(DenseMapCustomTest, ReserveTest) { 451 // Test a few different size, 341 is *not* a random choice: we need a value 452 // that is 2/3 of a power of two to stress the grow() condition, and the power 453 // of two has to be at least 512 because of minimum size allocation in the 454 // 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 grow 467 EXPECT_EQ(MemorySize, Map.getMemorySize()); 468 // Check that move was called the expected number of times 469 EXPECT_EQ(Size, CountCopyAndMove::Move); 470 // Check that no copy occurred 471 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() tests 493TEST(DenseMapCustomTest, FindAsTest) { 494 DenseMap<unsigned, unsigned, TestDenseMapInfo> map; 495 map[0] = 1; 496 map[1] = 2; 497 map[2] = 3; 498 499 // Size tests 500 EXPECT_EQ(3u, map.size()); 501 502 // Normal lookup tests 503 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() tests 510 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 have 532 // 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} // namespace 551