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() { 50 EXPECT_EQ(1u, Constructed.erase(this)); 51 } 52 operator uint32_t() const { return Value; } 53 54 int getValue() const { return Value; } 55 bool operator==(const CtorTester &RHS) const { return Value == RHS.Value; } 56 }; 57 58 std::set<CtorTester *> CtorTester::Constructed; 59 60 struct CtorTesterMapInfo { 61 static inline CtorTester getEmptyKey() { return CtorTester(-1); } 62 static inline CtorTester getTombstoneKey() { return CtorTester(-2); } 63 static unsigned getHashValue(const CtorTester &Val) { 64 return Val.getValue() * 37u; 65 } 66 static bool isEqual(const CtorTester &LHS, const CtorTester &RHS) { 67 return LHS == RHS; 68 } 69 }; 70 71 CtorTester getTestKey(int i, CtorTester *) { return CtorTester(i); } 72 CtorTester getTestValue(int i, CtorTester *) { return CtorTester(42 + i); } 73 74 // Test fixture, with helper functions implemented by forwarding to global 75 // function overloads selected by component types of the type parameter. This 76 // allows all of the map implementations to be tested with shared 77 // implementations of helper routines. 78 template <typename T> 79 class DenseMapTest : public ::testing::Test { 80 protected: 81 T Map; 82 83 static typename T::key_type *const dummy_key_ptr; 84 static typename T::mapped_type *const dummy_value_ptr; 85 86 typename T::key_type getKey(int i = 0) { 87 return getTestKey(i, dummy_key_ptr); 88 } 89 typename T::mapped_type getValue(int i = 0) { 90 return getTestValue(i, dummy_value_ptr); 91 } 92 }; 93 94 template <typename T> 95 typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = 0; 96 template <typename T> 97 typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = 0; 98 99 // Register these types for testing. 100 typedef ::testing::Types<DenseMap<uint32_t, uint32_t>, 101 DenseMap<uint32_t *, uint32_t *>, 102 DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>, 103 SmallDenseMap<uint32_t, uint32_t>, 104 SmallDenseMap<uint32_t *, uint32_t *>, 105 SmallDenseMap<CtorTester, CtorTester, 4, 106 CtorTesterMapInfo> 107 > DenseMapTestTypes; 108 TYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes); 109 110 // Empty map tests 111 TYPED_TEST(DenseMapTest, EmptyIntMapTest) { 112 // Size tests 113 EXPECT_EQ(0u, this->Map.size()); 114 EXPECT_TRUE(this->Map.empty()); 115 116 // Iterator tests 117 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 118 119 // Lookup tests 120 EXPECT_FALSE(this->Map.count(this->getKey())); 121 EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end()); 122 #ifndef _MSC_VER 123 EXPECT_EQ(typename TypeParam::mapped_type(), 124 this->Map.lookup(this->getKey())); 125 #else 126 // MSVC, at least old versions, cannot parse the typename to disambiguate 127 // TypeParam::mapped_type as a type. However, because MSVC doesn't implement 128 // two-phase name lookup, it also doesn't require the typename. Deal with 129 // this mutual incompatibility through specialized code. 130 EXPECT_EQ(TypeParam::mapped_type(), 131 this->Map.lookup(this->getKey())); 132 #endif 133 } 134 135 // Constant map tests 136 TYPED_TEST(DenseMapTest, ConstEmptyMapTest) { 137 const TypeParam &ConstMap = this->Map; 138 EXPECT_EQ(0u, ConstMap.size()); 139 EXPECT_TRUE(ConstMap.empty()); 140 EXPECT_TRUE(ConstMap.begin() == ConstMap.end()); 141 } 142 143 // A map with a single entry 144 TYPED_TEST(DenseMapTest, SingleEntryMapTest) { 145 this->Map[this->getKey()] = this->getValue(); 146 147 // Size tests 148 EXPECT_EQ(1u, this->Map.size()); 149 EXPECT_FALSE(this->Map.begin() == this->Map.end()); 150 EXPECT_FALSE(this->Map.empty()); 151 152 // Iterator tests 153 typename TypeParam::iterator it = this->Map.begin(); 154 EXPECT_EQ(this->getKey(), it->first); 155 EXPECT_EQ(this->getValue(), it->second); 156 ++it; 157 EXPECT_TRUE(it == this->Map.end()); 158 159 // Lookup tests 160 EXPECT_TRUE(this->Map.count(this->getKey())); 161 EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin()); 162 EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey())); 163 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 164 } 165 166 // Test clear() method 167 TYPED_TEST(DenseMapTest, ClearTest) { 168 this->Map[this->getKey()] = this->getValue(); 169 this->Map.clear(); 170 171 EXPECT_EQ(0u, this->Map.size()); 172 EXPECT_TRUE(this->Map.empty()); 173 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 174 } 175 176 // Test erase(iterator) method 177 TYPED_TEST(DenseMapTest, EraseTest) { 178 this->Map[this->getKey()] = this->getValue(); 179 this->Map.erase(this->Map.begin()); 180 181 EXPECT_EQ(0u, this->Map.size()); 182 EXPECT_TRUE(this->Map.empty()); 183 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 184 } 185 186 // Test erase(value) method 187 TYPED_TEST(DenseMapTest, EraseTest2) { 188 this->Map[this->getKey()] = this->getValue(); 189 this->Map.erase(this->getKey()); 190 191 EXPECT_EQ(0u, this->Map.size()); 192 EXPECT_TRUE(this->Map.empty()); 193 EXPECT_TRUE(this->Map.begin() == this->Map.end()); 194 } 195 196 // Test insert() method 197 TYPED_TEST(DenseMapTest, InsertTest) { 198 this->Map.insert(std::make_pair(this->getKey(), this->getValue())); 199 EXPECT_EQ(1u, this->Map.size()); 200 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 201 } 202 203 // Test copy constructor method 204 TYPED_TEST(DenseMapTest, CopyConstructorTest) { 205 this->Map[this->getKey()] = this->getValue(); 206 TypeParam copyMap(this->Map); 207 208 EXPECT_EQ(1u, copyMap.size()); 209 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 210 } 211 212 // Test assignment operator method 213 TYPED_TEST(DenseMapTest, AssignmentTest) { 214 this->Map[this->getKey()] = this->getValue(); 215 TypeParam copyMap = this->Map; 216 217 EXPECT_EQ(1u, copyMap.size()); 218 EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 219 } 220 221 // Test swap method 222 TYPED_TEST(DenseMapTest, SwapTest) { 223 this->Map[this->getKey()] = this->getValue(); 224 TypeParam otherMap; 225 226 this->Map.swap(otherMap); 227 EXPECT_EQ(0u, this->Map.size()); 228 EXPECT_TRUE(this->Map.empty()); 229 EXPECT_EQ(1u, otherMap.size()); 230 EXPECT_EQ(this->getValue(), otherMap[this->getKey()]); 231 232 this->Map.swap(otherMap); 233 EXPECT_EQ(0u, otherMap.size()); 234 EXPECT_TRUE(otherMap.empty()); 235 EXPECT_EQ(1u, this->Map.size()); 236 EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 237 238 // Make this more interesting by inserting 100 numbers into the map. 239 for (int i = 0; i < 100; ++i) 240 this->Map[this->getKey(i)] = this->getValue(i); 241 242 this->Map.swap(otherMap); 243 EXPECT_EQ(0u, this->Map.size()); 244 EXPECT_TRUE(this->Map.empty()); 245 EXPECT_EQ(100u, otherMap.size()); 246 for (int i = 0; i < 100; ++i) 247 EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]); 248 249 this->Map.swap(otherMap); 250 EXPECT_EQ(0u, otherMap.size()); 251 EXPECT_TRUE(otherMap.empty()); 252 EXPECT_EQ(100u, this->Map.size()); 253 for (int i = 0; i < 100; ++i) 254 EXPECT_EQ(this->getValue(i), this->Map[this->getKey(i)]); 255 } 256 257 // A more complex iteration test 258 TYPED_TEST(DenseMapTest, IterationTest) { 259 bool visited[100]; 260 std::map<typename TypeParam::key_type, unsigned> visitedIndex; 261 262 // Insert 100 numbers into the map 263 for (int i = 0; i < 100; ++i) { 264 visited[i] = false; 265 visitedIndex[this->getKey(i)] = i; 266 267 this->Map[this->getKey(i)] = this->getValue(i); 268 } 269 270 // Iterate over all numbers and mark each one found. 271 for (typename TypeParam::iterator it = this->Map.begin(); 272 it != this->Map.end(); ++it) 273 visited[visitedIndex[it->first]] = true; 274 275 // Ensure every number was visited. 276 for (int i = 0; i < 100; ++i) 277 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 278 } 279 280 // const_iterator test 281 TYPED_TEST(DenseMapTest, ConstIteratorTest) { 282 // Check conversion from iterator to const_iterator. 283 typename TypeParam::iterator it = this->Map.begin(); 284 typename TypeParam::const_iterator cit(it); 285 EXPECT_TRUE(it == cit); 286 287 // Check copying of const_iterators. 288 typename TypeParam::const_iterator cit2(cit); 289 EXPECT_TRUE(cit == cit2); 290 } 291 292 // Key traits that allows lookup with either an unsigned or char* key; 293 // In the latter case, "a" == 0, "b" == 1 and so on. 294 struct TestDenseMapInfo { 295 static inline unsigned getEmptyKey() { return ~0; } 296 static inline unsigned getTombstoneKey() { return ~0U - 1; } 297 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 298 static unsigned getHashValue(const char* Val) { 299 return (unsigned)(Val[0] - 'a') * 37U; 300 } 301 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 302 return LHS == RHS; 303 } 304 static bool isEqual(const char* LHS, const unsigned& RHS) { 305 return (unsigned)(LHS[0] - 'a') == RHS; 306 } 307 }; 308 309 // find_as() tests 310 TEST(DenseMapCustomTest, FindAsTest) { 311 DenseMap<unsigned, unsigned, TestDenseMapInfo> map; 312 map[0] = 1; 313 map[1] = 2; 314 map[2] = 3; 315 316 // Size tests 317 EXPECT_EQ(3u, map.size()); 318 319 // Normal lookup tests 320 EXPECT_EQ(1, map.count(1)); 321 EXPECT_EQ(1u, map.find(0)->second); 322 EXPECT_EQ(2u, map.find(1)->second); 323 EXPECT_EQ(3u, map.find(2)->second); 324 EXPECT_TRUE(map.find(3) == map.end()); 325 326 // find_as() tests 327 EXPECT_EQ(1u, map.find_as("a")->second); 328 EXPECT_EQ(2u, map.find_as("b")->second); 329 EXPECT_EQ(3u, map.find_as("c")->second); 330 EXPECT_TRUE(map.find_as("d") == map.end()); 331 } 332 333 struct ContiguousDenseMapInfo { 334 static inline unsigned getEmptyKey() { return ~0; } 335 static inline unsigned getTombstoneKey() { return ~0U - 1; } 336 static unsigned getHashValue(const unsigned& Val) { return Val; } 337 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 338 return LHS == RHS; 339 } 340 }; 341 342 // Test that filling a small dense map with exactly the number of elements in 343 // the map grows to have enough space for an empty bucket. 344 TEST(DenseMapCustomTest, SmallDenseMapGrowTest) { 345 SmallDenseMap<unsigned, unsigned, 32, ContiguousDenseMapInfo> map; 346 // Add some number of elements, then delete a few to leave us some tombstones. 347 // If we just filled the map with 32 elements we'd grow because of not enough 348 // tombstones which masks the issue here. 349 for (unsigned i = 0; i < 20; ++i) 350 map[i] = i + 1; 351 for (unsigned i = 0; i < 10; ++i) 352 map.erase(i); 353 for (unsigned i = 20; i < 32; ++i) 354 map[i] = i + 1; 355 356 // Size tests 357 EXPECT_EQ(22u, map.size()); 358 359 // Try to find an element which doesn't exist. There was a bug in 360 // SmallDenseMap which led to a map with num elements == small capacity not 361 // having an empty bucket any more. Finding an element not in the map would 362 // therefore never terminate. 363 EXPECT_TRUE(map.find(32) == map.end()); 364 } 365 366 } 367
