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 15 using namespace llvm; 16 17 namespace { 18 19 uint32_t getTestKey(int i, uint32_t *) { return i; } 20 uint32_t getTestValue(int i, uint32_t *) { return 42 + i; } 21 22 uint32_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 } 27 uint32_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. 35 class CtorTester { 36 static std::set<CtorTester *> Constructed; 37 int Value; 38 39 public: 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 59 std::set<CtorTester *> CtorTester::Constructed; 60 61 struct 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 72 CtorTester getTestKey(int i, CtorTester *) { return CtorTester(i); } 73 CtorTester 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. 79 template <typename T> 80 class DenseMapTest : public ::testing::Test { 81 protected: 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 95 template <typename T> 96 typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = nullptr; 97 template <typename T> 98 typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = nullptr; 99 100 // Register these types for testing. 101 typedef ::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; 109 TYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes); 110 111 // Empty map tests 112 TYPED_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 137 TYPED_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 145 TYPED_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 168 TYPED_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 178 TYPED_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 188 TYPED_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 198 TYPED_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 205 TYPED_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. 214 TYPED_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. 225 TYPED_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. 232 TYPED_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 242 TYPED_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 255 // Test swap method 256 TYPED_TEST(DenseMapTest, SwapTest) { 257 this->Map[this->getKey()] = this->getValue(); 258 TypeParam otherMap; 259 260 this->Map.swap(otherMap); 261 EXPECT_EQ(0u, this->Map.size()); 262 EXPECT_TRUE(this->Map.empty()); 263 EXPECT_EQ(1u, otherMap.size()); 264 EXPECT_EQ(this->getValue(), otherMap[this->getKey()]); 265 266 this->Map.swap(otherMap); 267 EXPECT_EQ(0u, otherMap.size()); 268 EXPECT_TRUE(otherMap.empty()); 269 EXPECT_EQ(1u, this->Map.size()); 270 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 271 272 // Make this more interesting by inserting 100 numbers into the map. 273 for (int i = 0; i < 100; ++i) 274 this->Map[this->getKey(i)] = this->getValue(i); 275 276 this->Map.swap(otherMap); 277 EXPECT_EQ(0u, this->Map.size()); 278 EXPECT_TRUE(this->Map.empty()); 279 EXPECT_EQ(100u, otherMap.size()); 280 for (int i = 0; i < 100; ++i) 281 EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]); 282 283 this->Map.swap(otherMap); 284 EXPECT_EQ(0u, otherMap.size()); 285 EXPECT_TRUE(otherMap.empty()); 286 EXPECT_EQ(100u, this->Map.size()); 287 for (int i = 0; i < 100; ++i) 288 EXPECT_EQ(this->getValue(i), this->Map[this->getKey(i)]); 289 } 290 291 // A more complex iteration test 292 TYPED_TEST(DenseMapTest, IterationTest) { 293 bool visited[100]; 294 std::map<typename TypeParam::key_type, unsigned> visitedIndex; 295 296 // Insert 100 numbers into the map 297 for (int i = 0; i < 100; ++i) { 298 visited[i] = false; 299 visitedIndex[this->getKey(i)] = i; 300 301 this->Map[this->getKey(i)] = this->getValue(i); 302 } 303 304 // Iterate over all numbers and mark each one found. 305 for (typename TypeParam::iterator it = this->Map.begin(); 306 it != this->Map.end(); ++it) 307 visited[visitedIndex[it->first]] = true; 308 309 // Ensure every number was visited. 310 for (int i = 0; i < 100; ++i) 311 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 312 } 313 314 // const_iterator test 315 TYPED_TEST(DenseMapTest, ConstIteratorTest) { 316 // Check conversion from iterator to const_iterator. 317 typename TypeParam::iterator it = this->Map.begin(); 318 typename TypeParam::const_iterator cit(it); 319 EXPECT_TRUE(it == cit); 320 321 // Check copying of const_iterators. 322 typename TypeParam::const_iterator cit2(cit); 323 EXPECT_TRUE(cit == cit2); 324 } 325 326 // Key traits that allows lookup with either an unsigned or char* key; 327 // In the latter case, "a" == 0, "b" == 1 and so on. 328 struct TestDenseMapInfo { 329 static inline unsigned getEmptyKey() { return ~0; } 330 static inline unsigned getTombstoneKey() { return ~0U - 1; } 331 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 332 static unsigned getHashValue(const char* Val) { 333 return (unsigned)(Val[0] - 'a') * 37U; 334 } 335 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 336 return LHS == RHS; 337 } 338 static bool isEqual(const char* LHS, const unsigned& RHS) { 339 return (unsigned)(LHS[0] - 'a') == RHS; 340 } 341 }; 342 343 // find_as() tests 344 TEST(DenseMapCustomTest, FindAsTest) { 345 DenseMap<unsigned, unsigned, TestDenseMapInfo> map; 346 map[0] = 1; 347 map[1] = 2; 348 map[2] = 3; 349 350 // Size tests 351 EXPECT_EQ(3u, map.size()); 352 353 // Normal lookup tests 354 EXPECT_EQ(1u, map.count(1)); 355 EXPECT_EQ(1u, map.find(0)->second); 356 EXPECT_EQ(2u, map.find(1)->second); 357 EXPECT_EQ(3u, map.find(2)->second); 358 EXPECT_TRUE(map.find(3) == map.end()); 359 360 // find_as() tests 361 EXPECT_EQ(1u, map.find_as("a")->second); 362 EXPECT_EQ(2u, map.find_as("b")->second); 363 EXPECT_EQ(3u, map.find_as("c")->second); 364 EXPECT_TRUE(map.find_as("d") == map.end()); 365 } 366 367 struct ContiguousDenseMapInfo { 368 static inline unsigned getEmptyKey() { return ~0; } 369 static inline unsigned getTombstoneKey() { return ~0U - 1; } 370 static unsigned getHashValue(const unsigned& Val) { return Val; } 371 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 372 return LHS == RHS; 373 } 374 }; 375 376 // Test that filling a small dense map with exactly the number of elements in 377 // the map grows to have enough space for an empty bucket. 378 TEST(DenseMapCustomTest, SmallDenseMapGrowTest) { 379 SmallDenseMap<unsigned, unsigned, 32, ContiguousDenseMapInfo> map; 380 // Add some number of elements, then delete a few to leave us some tombstones. 381 // If we just filled the map with 32 elements we'd grow because of not enough 382 // tombstones which masks the issue here. 383 for (unsigned i = 0; i < 20; ++i) 384 map[i] = i + 1; 385 for (unsigned i = 0; i < 10; ++i) 386 map.erase(i); 387 for (unsigned i = 20; i < 32; ++i) 388 map[i] = i + 1; 389 390 // Size tests 391 EXPECT_EQ(22u, map.size()); 392 393 // Try to find an element which doesn't exist. There was a bug in 394 // SmallDenseMap which led to a map with num elements == small capacity not 395 // having an empty bucket any more. Finding an element not in the map would 396 // therefore never terminate. 397 EXPECT_TRUE(map.find(32) == map.end()); 398 } 399 400 } 401