1 //===- llvm/unittest/ADT/StringMapMap.cpp - StringMap unit tests ----------===// 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/StringMap.h" 12 #include "llvm/Support/DataTypes.h" 13 #include <tuple> 14 using namespace llvm; 15 16 namespace { 17 18 // Test fixture 19 class StringMapTest : public testing::Test { 20 protected: 21 StringMap<uint32_t> testMap; 22 23 static const char testKey[]; 24 static const uint32_t testValue; 25 static const char* testKeyFirst; 26 static size_t testKeyLength; 27 static const std::string testKeyStr; 28 29 void assertEmptyMap() { 30 // Size tests 31 EXPECT_EQ(0u, testMap.size()); 32 EXPECT_TRUE(testMap.empty()); 33 34 // Iterator tests 35 EXPECT_TRUE(testMap.begin() == testMap.end()); 36 37 // Lookup tests 38 EXPECT_EQ(0u, testMap.count(testKey)); 39 EXPECT_EQ(0u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 40 EXPECT_EQ(0u, testMap.count(testKeyStr)); 41 EXPECT_TRUE(testMap.find(testKey) == testMap.end()); 42 EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 43 testMap.end()); 44 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end()); 45 } 46 47 void assertSingleItemMap() { 48 // Size tests 49 EXPECT_EQ(1u, testMap.size()); 50 EXPECT_FALSE(testMap.begin() == testMap.end()); 51 EXPECT_FALSE(testMap.empty()); 52 53 // Iterator tests 54 StringMap<uint32_t>::iterator it = testMap.begin(); 55 EXPECT_STREQ(testKey, it->first().data()); 56 EXPECT_EQ(testValue, it->second); 57 ++it; 58 EXPECT_TRUE(it == testMap.end()); 59 60 // Lookup tests 61 EXPECT_EQ(1u, testMap.count(testKey)); 62 EXPECT_EQ(1u, testMap.count(StringRef(testKeyFirst, testKeyLength))); 63 EXPECT_EQ(1u, testMap.count(testKeyStr)); 64 EXPECT_TRUE(testMap.find(testKey) == testMap.begin()); 65 EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == 66 testMap.begin()); 67 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin()); 68 } 69 }; 70 71 const char StringMapTest::testKey[] = "key"; 72 const uint32_t StringMapTest::testValue = 1u; 73 const char* StringMapTest::testKeyFirst = testKey; 74 size_t StringMapTest::testKeyLength = sizeof(testKey) - 1; 75 const std::string StringMapTest::testKeyStr(testKey); 76 77 // Empty map tests. 78 TEST_F(StringMapTest, EmptyMapTest) { 79 assertEmptyMap(); 80 } 81 82 // Constant map tests. 83 TEST_F(StringMapTest, ConstEmptyMapTest) { 84 const StringMap<uint32_t>& constTestMap = testMap; 85 86 // Size tests 87 EXPECT_EQ(0u, constTestMap.size()); 88 EXPECT_TRUE(constTestMap.empty()); 89 90 // Iterator tests 91 EXPECT_TRUE(constTestMap.begin() == constTestMap.end()); 92 93 // Lookup tests 94 EXPECT_EQ(0u, constTestMap.count(testKey)); 95 EXPECT_EQ(0u, constTestMap.count(StringRef(testKeyFirst, testKeyLength))); 96 EXPECT_EQ(0u, constTestMap.count(testKeyStr)); 97 EXPECT_TRUE(constTestMap.find(testKey) == constTestMap.end()); 98 EXPECT_TRUE(constTestMap.find(StringRef(testKeyFirst, testKeyLength)) == 99 constTestMap.end()); 100 EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end()); 101 } 102 103 // A map with a single entry. 104 TEST_F(StringMapTest, SingleEntryMapTest) { 105 testMap[testKey] = testValue; 106 assertSingleItemMap(); 107 } 108 109 // Test clear() method. 110 TEST_F(StringMapTest, ClearTest) { 111 testMap[testKey] = testValue; 112 testMap.clear(); 113 assertEmptyMap(); 114 } 115 116 // Test erase(iterator) method. 117 TEST_F(StringMapTest, EraseIteratorTest) { 118 testMap[testKey] = testValue; 119 testMap.erase(testMap.begin()); 120 assertEmptyMap(); 121 } 122 123 // Test erase(value) method. 124 TEST_F(StringMapTest, EraseValueTest) { 125 testMap[testKey] = testValue; 126 testMap.erase(testKey); 127 assertEmptyMap(); 128 } 129 130 // Test inserting two values and erasing one. 131 TEST_F(StringMapTest, InsertAndEraseTest) { 132 testMap[testKey] = testValue; 133 testMap["otherKey"] = 2; 134 testMap.erase("otherKey"); 135 assertSingleItemMap(); 136 } 137 138 TEST_F(StringMapTest, SmallFullMapTest) { 139 // StringMap has a tricky corner case when the map is small (<8 buckets) and 140 // it fills up through a balanced pattern of inserts and erases. This can 141 // lead to inf-loops in some cases (PR13148) so we test it explicitly here. 142 llvm::StringMap<int> Map(2); 143 144 Map["eins"] = 1; 145 Map["zwei"] = 2; 146 Map["drei"] = 3; 147 Map.erase("drei"); 148 Map.erase("eins"); 149 Map["veir"] = 4; 150 Map["funf"] = 5; 151 152 EXPECT_EQ(3u, Map.size()); 153 EXPECT_EQ(0, Map.lookup("eins")); 154 EXPECT_EQ(2, Map.lookup("zwei")); 155 EXPECT_EQ(0, Map.lookup("drei")); 156 EXPECT_EQ(4, Map.lookup("veir")); 157 EXPECT_EQ(5, Map.lookup("funf")); 158 } 159 160 TEST_F(StringMapTest, CopyCtorTest) { 161 llvm::StringMap<int> Map; 162 163 Map["eins"] = 1; 164 Map["zwei"] = 2; 165 Map["drei"] = 3; 166 Map.erase("drei"); 167 Map.erase("eins"); 168 Map["veir"] = 4; 169 Map["funf"] = 5; 170 171 EXPECT_EQ(3u, Map.size()); 172 EXPECT_EQ(0, Map.lookup("eins")); 173 EXPECT_EQ(2, Map.lookup("zwei")); 174 EXPECT_EQ(0, Map.lookup("drei")); 175 EXPECT_EQ(4, Map.lookup("veir")); 176 EXPECT_EQ(5, Map.lookup("funf")); 177 178 llvm::StringMap<int> Map2(Map); 179 EXPECT_EQ(3u, Map2.size()); 180 EXPECT_EQ(0, Map2.lookup("eins")); 181 EXPECT_EQ(2, Map2.lookup("zwei")); 182 EXPECT_EQ(0, Map2.lookup("drei")); 183 EXPECT_EQ(4, Map2.lookup("veir")); 184 EXPECT_EQ(5, Map2.lookup("funf")); 185 } 186 187 // A more complex iteration test. 188 TEST_F(StringMapTest, IterationTest) { 189 bool visited[100]; 190 191 // Insert 100 numbers into the map 192 for (int i = 0; i < 100; ++i) { 193 std::stringstream ss; 194 ss << "key_" << i; 195 testMap[ss.str()] = i; 196 visited[i] = false; 197 } 198 199 // Iterate over all numbers and mark each one found. 200 for (StringMap<uint32_t>::iterator it = testMap.begin(); 201 it != testMap.end(); ++it) { 202 std::stringstream ss; 203 ss << "key_" << it->second; 204 ASSERT_STREQ(ss.str().c_str(), it->first().data()); 205 visited[it->second] = true; 206 } 207 208 // Ensure every number was visited. 209 for (int i = 0; i < 100; ++i) { 210 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 211 } 212 } 213 214 // Test StringMapEntry::Create() method. 215 TEST_F(StringMapTest, StringMapEntryTest) { 216 StringMap<uint32_t>::value_type* entry = 217 StringMap<uint32_t>::value_type::Create( 218 StringRef(testKeyFirst, testKeyLength), 1u); 219 EXPECT_STREQ(testKey, entry->first().data()); 220 EXPECT_EQ(1u, entry->second); 221 free(entry); 222 } 223 224 // Test insert() method. 225 TEST_F(StringMapTest, InsertTest) { 226 SCOPED_TRACE("InsertTest"); 227 testMap.insert( 228 StringMap<uint32_t>::value_type::Create( 229 StringRef(testKeyFirst, testKeyLength), 230 testMap.getAllocator(), 1u)); 231 assertSingleItemMap(); 232 } 233 234 // Test insert(pair<K, V>) method 235 TEST_F(StringMapTest, InsertPairTest) { 236 bool Inserted; 237 StringMap<uint32_t>::iterator NewIt; 238 std::tie(NewIt, Inserted) = 239 testMap.insert(std::make_pair(testKeyFirst, testValue)); 240 EXPECT_EQ(1u, testMap.size()); 241 EXPECT_EQ(testValue, testMap[testKeyFirst]); 242 EXPECT_EQ(testKeyFirst, NewIt->first()); 243 EXPECT_EQ(testValue, NewIt->second); 244 EXPECT_TRUE(Inserted); 245 246 StringMap<uint32_t>::iterator ExistingIt; 247 std::tie(ExistingIt, Inserted) = 248 testMap.insert(std::make_pair(testKeyFirst, testValue + 1)); 249 EXPECT_EQ(1u, testMap.size()); 250 EXPECT_EQ(testValue, testMap[testKeyFirst]); 251 EXPECT_FALSE(Inserted); 252 EXPECT_EQ(NewIt, ExistingIt); 253 } 254 255 // Test insert(pair<K, V>) method when rehashing occurs 256 TEST_F(StringMapTest, InsertRehashingPairTest) { 257 // Check that the correct iterator is returned when the inserted element is 258 // moved to a different bucket during internal rehashing. This depends on 259 // the particular key, and the implementation of StringMap and HashString. 260 // Changes to those might result in this test not actually checking that. 261 StringMap<uint32_t> t(0); 262 EXPECT_EQ(0u, t.getNumBuckets()); 263 264 StringMap<uint32_t>::iterator It = 265 t.insert(std::make_pair("abcdef", 42)).first; 266 EXPECT_EQ(16u, t.getNumBuckets()); 267 EXPECT_EQ("abcdef", It->first()); 268 EXPECT_EQ(42u, It->second); 269 } 270 271 // Create a non-default constructable value 272 struct StringMapTestStruct { 273 StringMapTestStruct(int i) : i(i) {} 274 StringMapTestStruct() = delete; 275 int i; 276 }; 277 278 TEST_F(StringMapTest, NonDefaultConstructable) { 279 StringMap<StringMapTestStruct> t; 280 t.insert(std::make_pair("Test", StringMapTestStruct(123))); 281 StringMap<StringMapTestStruct>::iterator iter = t.find("Test"); 282 ASSERT_NE(iter, t.end()); 283 ASSERT_EQ(iter->second.i, 123); 284 } 285 286 struct Immovable { 287 Immovable() {} 288 Immovable(Immovable&&) = delete; // will disable the other special members 289 }; 290 291 struct MoveOnly { 292 int i; 293 MoveOnly(int i) : i(i) {} 294 MoveOnly(const Immovable&) : i(0) {} 295 MoveOnly(MoveOnly &&RHS) : i(RHS.i) {} 296 MoveOnly &operator=(MoveOnly &&RHS) { 297 i = RHS.i; 298 return *this; 299 } 300 301 private: 302 MoveOnly(const MoveOnly &) = delete; 303 MoveOnly &operator=(const MoveOnly &) = delete; 304 }; 305 306 TEST_F(StringMapTest, MoveOnly) { 307 StringMap<MoveOnly> t; 308 t.insert(std::make_pair("Test", MoveOnly(42))); 309 StringRef Key = "Test"; 310 StringMapEntry<MoveOnly>::Create(Key, MoveOnly(42)) 311 ->Destroy(); 312 } 313 314 TEST_F(StringMapTest, CtorArg) { 315 StringRef Key = "Test"; 316 StringMapEntry<MoveOnly>::Create(Key, Immovable()) 317 ->Destroy(); 318 } 319 320 TEST_F(StringMapTest, MoveConstruct) { 321 StringMap<int> A; 322 A["x"] = 42; 323 StringMap<int> B = std::move(A); 324 ASSERT_EQ(A.size(), 0u); 325 ASSERT_EQ(B.size(), 1u); 326 ASSERT_EQ(B["x"], 42); 327 ASSERT_EQ(B.count("y"), 0u); 328 } 329 330 TEST_F(StringMapTest, MoveAssignment) { 331 StringMap<int> A; 332 A["x"] = 42; 333 StringMap<int> B; 334 B["y"] = 117; 335 A = std::move(B); 336 ASSERT_EQ(A.size(), 1u); 337 ASSERT_EQ(B.size(), 0u); 338 ASSERT_EQ(A["y"], 117); 339 ASSERT_EQ(B.count("x"), 0u); 340 } 341 342 struct Countable { 343 int &InstanceCount; 344 int Number; 345 Countable(int Number, int &InstanceCount) 346 : InstanceCount(InstanceCount), Number(Number) { 347 ++InstanceCount; 348 } 349 Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) { 350 ++InstanceCount; 351 C.Number = -1; 352 } 353 Countable(const Countable &C) 354 : InstanceCount(C.InstanceCount), Number(C.Number) { 355 ++InstanceCount; 356 } 357 Countable &operator=(Countable C) { 358 Number = C.Number; 359 return *this; 360 } 361 ~Countable() { --InstanceCount; } 362 }; 363 364 TEST_F(StringMapTest, MoveDtor) { 365 int InstanceCount = 0; 366 StringMap<Countable> A; 367 A.insert(std::make_pair("x", Countable(42, InstanceCount))); 368 ASSERT_EQ(InstanceCount, 1); 369 auto I = A.find("x"); 370 ASSERT_NE(I, A.end()); 371 ASSERT_EQ(I->second.Number, 42); 372 373 StringMap<Countable> B; 374 B = std::move(A); 375 ASSERT_EQ(InstanceCount, 1); 376 ASSERT_TRUE(A.empty()); 377 I = B.find("x"); 378 ASSERT_NE(I, B.end()); 379 ASSERT_EQ(I->second.Number, 42); 380 381 B = StringMap<Countable>(); 382 ASSERT_EQ(InstanceCount, 0); 383 ASSERT_TRUE(B.empty()); 384 } 385 386 namespace { 387 // Simple class that counts how many moves and copy happens when growing a map 388 struct CountCtorCopyAndMove { 389 static unsigned Ctor; 390 static unsigned Move; 391 static unsigned Copy; 392 int Data = 0; 393 CountCtorCopyAndMove(int Data) : Data(Data) { Ctor++; } 394 CountCtorCopyAndMove() { Ctor++; } 395 396 CountCtorCopyAndMove(const CountCtorCopyAndMove &) { Copy++; } 397 CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &) { 398 Copy++; 399 return *this; 400 } 401 CountCtorCopyAndMove(CountCtorCopyAndMove &&) { Move++; } 402 CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &&) { 403 Move++; 404 return *this; 405 } 406 }; 407 unsigned CountCtorCopyAndMove::Copy = 0; 408 unsigned CountCtorCopyAndMove::Move = 0; 409 unsigned CountCtorCopyAndMove::Ctor = 0; 410 411 } // anonymous namespace 412 413 // Make sure creating the map with an initial size of N actually gives us enough 414 // buckets to insert N items without increasing allocation size. 415 TEST(StringMapCustomTest, InitialSizeTest) { 416 // 1 is an "edge value", 32 is an arbitrary power of two, and 67 is an 417 // arbitrary prime, picked without any good reason. 418 for (auto Size : {1, 32, 67}) { 419 StringMap<CountCtorCopyAndMove> Map(Size); 420 auto NumBuckets = Map.getNumBuckets(); 421 CountCtorCopyAndMove::Move = 0; 422 CountCtorCopyAndMove::Copy = 0; 423 for (int i = 0; i < Size; ++i) 424 Map.insert(std::pair<std::string, CountCtorCopyAndMove>( 425 std::piecewise_construct, std::forward_as_tuple(Twine(i).str()), 426 std::forward_as_tuple(i))); 427 // After the inital move, the map will move the Elts in the Entry. 428 EXPECT_EQ((unsigned)Size * 2, CountCtorCopyAndMove::Move); 429 // We copy once the pair from the Elts vector 430 EXPECT_EQ(0u, CountCtorCopyAndMove::Copy); 431 // Check that the map didn't grow 432 EXPECT_EQ(Map.getNumBuckets(), NumBuckets); 433 } 434 } 435 436 TEST(StringMapCustomTest, BracketOperatorCtor) { 437 StringMap<CountCtorCopyAndMove> Map; 438 CountCtorCopyAndMove::Ctor = 0; 439 Map["abcd"]; 440 EXPECT_EQ(1u, CountCtorCopyAndMove::Ctor); 441 // Test that operator[] does not create a value when it is already in the map 442 CountCtorCopyAndMove::Ctor = 0; 443 Map["abcd"]; 444 EXPECT_EQ(0u, CountCtorCopyAndMove::Ctor); 445 } 446 447 namespace { 448 struct NonMoveableNonCopyableType { 449 int Data = 0; 450 NonMoveableNonCopyableType() = default; 451 NonMoveableNonCopyableType(int Data) : Data(Data) {} 452 NonMoveableNonCopyableType(const NonMoveableNonCopyableType &) = delete; 453 NonMoveableNonCopyableType(NonMoveableNonCopyableType &&) = delete; 454 }; 455 } 456 457 // Test that we can "emplace" an element in the map without involving map/move 458 TEST(StringMapCustomTest, EmplaceTest) { 459 StringMap<NonMoveableNonCopyableType> Map; 460 Map.emplace_second("abcd", 42); 461 EXPECT_EQ(1u, Map.count("abcd")); 462 EXPECT_EQ(42, Map["abcd"].Data); 463 } 464 465 } // end anonymous namespace 466