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