1//===- llvm/unittest/ADT/DenseMapMap.cpp - DenseMap unit tests --*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#include "gtest/gtest.h" 11#include "llvm/ADT/DenseMap.h" 12#include <map> 13#include <set> 14 15using namespace llvm; 16 17namespace { 18 19uint32_t getTestKey(int i, uint32_t *) { return i; } 20uint32_t getTestValue(int i, uint32_t *) { return 42 + i; } 21 22uint32_t *getTestKey(int i, uint32_t **) { 23 static uint32_t dummy_arr1[8192]; 24 assert(i < 8192 && "Only support 8192 dummy keys."); 25 return &dummy_arr1[i]; 26} 27uint32_t *getTestValue(int i, uint32_t **) { 28 static uint32_t dummy_arr1[8192]; 29 assert(i < 8192 && "Only support 8192 dummy keys."); 30 return &dummy_arr1[i]; 31} 32 33/// \brief A test class that tries to check that construction and destruction 34/// occur correctly. 35class CtorTester { 36 static std::set<CtorTester *> Constructed; 37 int Value; 38 39public: 40 explicit CtorTester(int Value = 0) : Value(Value) { 41 EXPECT_TRUE(Constructed.insert(this).second); 42 } 43 CtorTester(uint32_t Value) : Value(Value) { 44 EXPECT_TRUE(Constructed.insert(this).second); 45 } 46 CtorTester(const CtorTester &Arg) : Value(Arg.Value) { 47 EXPECT_TRUE(Constructed.insert(this).second); 48 } 49 CtorTester &operator=(const CtorTester &) = default; 50 ~CtorTester() { 51 EXPECT_EQ(1u, Constructed.erase(this)); 52 } 53 operator uint32_t() const { return Value; } 54 55 int getValue() const { return Value; } 56 bool operator==(const CtorTester &RHS) const { return Value == RHS.Value; } 57}; 58 59std::set<CtorTester *> CtorTester::Constructed; 60 61struct CtorTesterMapInfo { 62 static inline CtorTester getEmptyKey() { return CtorTester(-1); } 63 static inline CtorTester getTombstoneKey() { return CtorTester(-2); } 64 static unsigned getHashValue(const CtorTester &Val) { 65 return Val.getValue() * 37u; 66 } 67 static bool isEqual(const CtorTester &LHS, const CtorTester &RHS) { 68 return LHS == RHS; 69 } 70}; 71 72CtorTester getTestKey(int i, CtorTester *) { return CtorTester(i); } 73CtorTester getTestValue(int i, CtorTester *) { return CtorTester(42 + i); } 74 75// Test fixture, with helper functions implemented by forwarding to global 76// function overloads selected by component types of the type parameter. This 77// allows all of the map implementations to be tested with shared 78// implementations of helper routines. 79template <typename T> 80class DenseMapTest : public ::testing::Test { 81protected: 82 T Map; 83 84 static typename T::key_type *const dummy_key_ptr; 85 static typename T::mapped_type *const dummy_value_ptr; 86 87 typename T::key_type getKey(int i = 0) { 88 return getTestKey(i, dummy_key_ptr); 89 } 90 typename T::mapped_type getValue(int i = 0) { 91 return getTestValue(i, dummy_value_ptr); 92 } 93}; 94 95template <typename T> 96typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = nullptr; 97template <typename T> 98typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = nullptr; 99 100// Register these types for testing. 101typedef ::testing::Types<DenseMap<uint32_t, uint32_t>, 102 DenseMap<uint32_t *, uint32_t *>, 103 DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>, 104 SmallDenseMap<uint32_t, uint32_t>, 105 SmallDenseMap<uint32_t *, uint32_t *>, 106 SmallDenseMap<CtorTester, CtorTester, 4, 107 CtorTesterMapInfo> 108 > DenseMapTestTypes; 109TYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes); 110 111// Empty map tests 112TYPED_TEST(DenseMapTest, EmptyIntMapTest) { 113 // Size tests 114 EXPECT_EQ(0u, this->Map.size()); 115 EXPECT_TRUE(this->Map.empty()); 116 117 // Iterator tests 118 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 119 120 // Lookup tests 121 EXPECT_FALSE(this->Map.count(this->getKey())); 122 EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end()); 123#if !defined(_MSC_VER) || defined(__clang__) 124 EXPECT_EQ(typename TypeParam::mapped_type(), 125 this->Map.lookup(this->getKey())); 126#else 127 // MSVC, at least old versions, cannot parse the typename to disambiguate 128 // TypeParam::mapped_type as a type. However, because MSVC doesn't implement 129 // two-phase name lookup, it also doesn't require the typename. Deal with 130 // this mutual incompatibility through specialized code. 131 EXPECT_EQ(TypeParam::mapped_type(), 132 this->Map.lookup(this->getKey())); 133#endif 134} 135 136// Constant map tests 137TYPED_TEST(DenseMapTest, ConstEmptyMapTest) { 138 const TypeParam &ConstMap = this->Map; 139 EXPECT_EQ(0u, ConstMap.size()); 140 EXPECT_TRUE(ConstMap.empty()); 141 EXPECT_TRUE(ConstMap.begin() == ConstMap.end()); 142} 143 144// A map with a single entry 145TYPED_TEST(DenseMapTest, SingleEntryMapTest) { 146 this->Map[this->getKey()] = this->getValue(); 147 148 // Size tests 149 EXPECT_EQ(1u, this->Map.size()); 150 EXPECT_FALSE(this->Map.begin() == this->Map.end()); 151 EXPECT_FALSE(this->Map.empty()); 152 153 // Iterator tests 154 typename TypeParam::iterator it = this->Map.begin(); 155 EXPECT_EQ(this->getKey(), it->first); 156 EXPECT_EQ(this->getValue(), it->second); 157 ++it; 158 EXPECT_TRUE(it == this->Map.end()); 159 160 // Lookup tests 161 EXPECT_TRUE(this->Map.count(this->getKey())); 162 EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin()); 163 EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey())); 164 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 165} 166 167// Test clear() method 168TYPED_TEST(DenseMapTest, ClearTest) { 169 this->Map[this->getKey()] = this->getValue(); 170 this->Map.clear(); 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(iterator) method 178TYPED_TEST(DenseMapTest, EraseTest) { 179 this->Map[this->getKey()] = this->getValue(); 180 this->Map.erase(this->Map.begin()); 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 erase(value) method 188TYPED_TEST(DenseMapTest, EraseTest2) { 189 this->Map[this->getKey()] = this->getValue(); 190 this->Map.erase(this->getKey()); 191 192 EXPECT_EQ(0u, this->Map.size()); 193 EXPECT_TRUE(this->Map.empty()); 194 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 195} 196 197// Test insert() method 198TYPED_TEST(DenseMapTest, InsertTest) { 199 this->Map.insert(std::make_pair(this->getKey(), this->getValue())); 200 EXPECT_EQ(1u, this->Map.size()); 201 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 202} 203 204// Test copy constructor method 205TYPED_TEST(DenseMapTest, CopyConstructorTest) { 206 this->Map[this->getKey()] = this->getValue(); 207 TypeParam copyMap(this->Map); 208 209 EXPECT_EQ(1u, copyMap.size()); 210 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 211} 212 213// Test copy constructor method where SmallDenseMap isn't small. 214TYPED_TEST(DenseMapTest, CopyConstructorNotSmallTest) { 215 for (int Key = 0; Key < 5; ++Key) 216 this->Map[this->getKey(Key)] = this->getValue(Key); 217 TypeParam copyMap(this->Map); 218 219 EXPECT_EQ(5u, copyMap.size()); 220 for (int Key = 0; Key < 5; ++Key) 221 EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]); 222} 223 224// Test copying from a default-constructed map. 225TYPED_TEST(DenseMapTest, CopyConstructorFromDefaultTest) { 226 TypeParam copyMap(this->Map); 227 228 EXPECT_TRUE(copyMap.empty()); 229} 230 231// Test copying from an empty map where SmallDenseMap isn't small. 232TYPED_TEST(DenseMapTest, CopyConstructorFromEmptyTest) { 233 for (int Key = 0; Key < 5; ++Key) 234 this->Map[this->getKey(Key)] = this->getValue(Key); 235 this->Map.clear(); 236 TypeParam copyMap(this->Map); 237 238 EXPECT_TRUE(copyMap.empty()); 239} 240 241// Test assignment operator method 242TYPED_TEST(DenseMapTest, AssignmentTest) { 243 this->Map[this->getKey()] = this->getValue(); 244 TypeParam copyMap = this->Map; 245 246 EXPECT_EQ(1u, copyMap.size()); 247 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 248 249 // test self-assignment. 250 copyMap = copyMap; 251 EXPECT_EQ(1u, copyMap.size()); 252 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 253} 254 255TYPED_TEST(DenseMapTest, AssignmentTestNotSmall) { 256 for (int Key = 0; Key < 5; ++Key) 257 this->Map[this->getKey(Key)] = this->getValue(Key); 258 TypeParam copyMap = this->Map; 259 260 EXPECT_EQ(5u, copyMap.size()); 261 for (int Key = 0; Key < 5; ++Key) 262 EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]); 263 264 // test self-assignment. 265 copyMap = copyMap; 266 EXPECT_EQ(5u, copyMap.size()); 267 for (int Key = 0; Key < 5; ++Key) 268 EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]); 269} 270 271// Test swap method 272TYPED_TEST(DenseMapTest, SwapTest) { 273 this->Map[this->getKey()] = this->getValue(); 274 TypeParam otherMap; 275 276 this->Map.swap(otherMap); 277 EXPECT_EQ(0u, this->Map.size()); 278 EXPECT_TRUE(this->Map.empty()); 279 EXPECT_EQ(1u, otherMap.size()); 280 EXPECT_EQ(this->getValue(), otherMap[this->getKey()]); 281 282 this->Map.swap(otherMap); 283 EXPECT_EQ(0u, otherMap.size()); 284 EXPECT_TRUE(otherMap.empty()); 285 EXPECT_EQ(1u, this->Map.size()); 286 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 287 288 // Make this more interesting by inserting 100 numbers into the map. 289 for (int i = 0; i < 100; ++i) 290 this->Map[this->getKey(i)] = this->getValue(i); 291 292 this->Map.swap(otherMap); 293 EXPECT_EQ(0u, this->Map.size()); 294 EXPECT_TRUE(this->Map.empty()); 295 EXPECT_EQ(100u, otherMap.size()); 296 for (int i = 0; i < 100; ++i) 297 EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]); 298 299 this->Map.swap(otherMap); 300 EXPECT_EQ(0u, otherMap.size()); 301 EXPECT_TRUE(otherMap.empty()); 302 EXPECT_EQ(100u, this->Map.size()); 303 for (int i = 0; i < 100; ++i) 304 EXPECT_EQ(this->getValue(i), this->Map[this->getKey(i)]); 305} 306 307// A more complex iteration test 308TYPED_TEST(DenseMapTest, IterationTest) { 309 bool visited[100]; 310 std::map<typename TypeParam::key_type, unsigned> visitedIndex; 311 312 // Insert 100 numbers into the map 313 for (int i = 0; i < 100; ++i) { 314 visited[i] = false; 315 visitedIndex[this->getKey(i)] = i; 316 317 this->Map[this->getKey(i)] = this->getValue(i); 318 } 319 320 // Iterate over all numbers and mark each one found. 321 for (typename TypeParam::iterator it = this->Map.begin(); 322 it != this->Map.end(); ++it) 323 visited[visitedIndex[it->first]] = true; 324 325 // Ensure every number was visited. 326 for (int i = 0; i < 100; ++i) 327 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 328} 329 330// const_iterator test 331TYPED_TEST(DenseMapTest, ConstIteratorTest) { 332 // Check conversion from iterator to const_iterator. 333 typename TypeParam::iterator it = this->Map.begin(); 334 typename TypeParam::const_iterator cit(it); 335 EXPECT_TRUE(it == cit); 336 337 // Check copying of const_iterators. 338 typename TypeParam::const_iterator cit2(cit); 339 EXPECT_TRUE(cit == cit2); 340} 341 342// Make sure DenseMap works with StringRef keys. 343TEST(DenseMapCustomTest, StringRefTest) { 344 DenseMap<StringRef, int> M; 345 346 M["a"] = 1; 347 M["b"] = 2; 348 M["c"] = 3; 349 350 EXPECT_EQ(3u, M.size()); 351 EXPECT_EQ(1, M.lookup("a")); 352 EXPECT_EQ(2, M.lookup("b")); 353 EXPECT_EQ(3, M.lookup("c")); 354 355 EXPECT_EQ(0, M.lookup("q")); 356 357 // Test the empty string, spelled various ways. 358 EXPECT_EQ(0, M.lookup("")); 359 EXPECT_EQ(0, M.lookup(StringRef())); 360 EXPECT_EQ(0, M.lookup(StringRef("a", 0))); 361 M[""] = 42; 362 EXPECT_EQ(42, M.lookup("")); 363 EXPECT_EQ(42, M.lookup(StringRef())); 364 EXPECT_EQ(42, M.lookup(StringRef("a", 0))); 365} 366 367// Key traits that allows lookup with either an unsigned or char* key; 368// In the latter case, "a" == 0, "b" == 1 and so on. 369struct TestDenseMapInfo { 370 static inline unsigned getEmptyKey() { return ~0; } 371 static inline unsigned getTombstoneKey() { return ~0U - 1; } 372 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 373 static unsigned getHashValue(const char* Val) { 374 return (unsigned)(Val[0] - 'a') * 37U; 375 } 376 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 377 return LHS == RHS; 378 } 379 static bool isEqual(const char* LHS, const unsigned& RHS) { 380 return (unsigned)(LHS[0] - 'a') == RHS; 381 } 382}; 383 384// find_as() tests 385TEST(DenseMapCustomTest, FindAsTest) { 386 DenseMap<unsigned, unsigned, TestDenseMapInfo> map; 387 map[0] = 1; 388 map[1] = 2; 389 map[2] = 3; 390 391 // Size tests 392 EXPECT_EQ(3u, map.size()); 393 394 // Normal lookup tests 395 EXPECT_EQ(1u, map.count(1)); 396 EXPECT_EQ(1u, map.find(0)->second); 397 EXPECT_EQ(2u, map.find(1)->second); 398 EXPECT_EQ(3u, map.find(2)->second); 399 EXPECT_TRUE(map.find(3) == map.end()); 400 401 // find_as() tests 402 EXPECT_EQ(1u, map.find_as("a")->second); 403 EXPECT_EQ(2u, map.find_as("b")->second); 404 EXPECT_EQ(3u, map.find_as("c")->second); 405 EXPECT_TRUE(map.find_as("d") == map.end()); 406} 407 408struct ContiguousDenseMapInfo { 409 static inline unsigned getEmptyKey() { return ~0; } 410 static inline unsigned getTombstoneKey() { return ~0U - 1; } 411 static unsigned getHashValue(const unsigned& Val) { return Val; } 412 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 413 return LHS == RHS; 414 } 415}; 416 417// Test that filling a small dense map with exactly the number of elements in 418// the map grows to have enough space for an empty bucket. 419TEST(DenseMapCustomTest, SmallDenseMapGrowTest) { 420 SmallDenseMap<unsigned, unsigned, 32, ContiguousDenseMapInfo> map; 421 // Add some number of elements, then delete a few to leave us some tombstones. 422 // If we just filled the map with 32 elements we'd grow because of not enough 423 // tombstones which masks the issue here. 424 for (unsigned i = 0; i < 20; ++i) 425 map[i] = i + 1; 426 for (unsigned i = 0; i < 10; ++i) 427 map.erase(i); 428 for (unsigned i = 20; i < 32; ++i) 429 map[i] = i + 1; 430 431 // Size tests 432 EXPECT_EQ(22u, map.size()); 433 434 // Try to find an element which doesn't exist. There was a bug in 435 // SmallDenseMap which led to a map with num elements == small capacity not 436 // having an empty bucket any more. Finding an element not in the map would 437 // therefore never terminate. 438 EXPECT_TRUE(map.find(32) == map.end()); 439} 440 441} 442