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