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 MallocAllocator Allocator; 228 StringMap<uint32_t>::value_type *entry = 229 StringMap<uint32_t>::value_type::Create( 230 StringRef(testKeyFirst, testKeyLength), Allocator, 1u); 231 EXPECT_STREQ(testKey, entry->first().data()); 232 EXPECT_EQ(1u, entry->second); 233 entry->Destroy(Allocator); 234 } 235 236 // Test insert() method. 237 TEST_F(StringMapTest, InsertTest) { 238 SCOPED_TRACE("InsertTest"); 239 testMap.insert( 240 StringMap<uint32_t>::value_type::Create( 241 StringRef(testKeyFirst, testKeyLength), 242 testMap.getAllocator(), 1u)); 243 assertSingleItemMap(); 244 } 245 246 // Test insert(pair<K, V>) method 247 TEST_F(StringMapTest, InsertPairTest) { 248 bool Inserted; 249 StringMap<uint32_t>::iterator NewIt; 250 std::tie(NewIt, Inserted) = 251 testMap.insert(std::make_pair(testKeyFirst, testValue)); 252 EXPECT_EQ(1u, testMap.size()); 253 EXPECT_EQ(testValue, testMap[testKeyFirst]); 254 EXPECT_EQ(testKeyFirst, NewIt->first()); 255 EXPECT_EQ(testValue, NewIt->second); 256 EXPECT_TRUE(Inserted); 257 258 StringMap<uint32_t>::iterator ExistingIt; 259 std::tie(ExistingIt, Inserted) = 260 testMap.insert(std::make_pair(testKeyFirst, testValue + 1)); 261 EXPECT_EQ(1u, testMap.size()); 262 EXPECT_EQ(testValue, testMap[testKeyFirst]); 263 EXPECT_FALSE(Inserted); 264 EXPECT_EQ(NewIt, ExistingIt); 265 } 266 267 // Test insert(pair<K, V>) method when rehashing occurs 268 TEST_F(StringMapTest, InsertRehashingPairTest) { 269 // Check that the correct iterator is returned when the inserted element is 270 // moved to a different bucket during internal rehashing. This depends on 271 // the particular key, and the implementation of StringMap and HashString. 272 // Changes to those might result in this test not actually checking that. 273 StringMap<uint32_t> t(0); 274 EXPECT_EQ(0u, t.getNumBuckets()); 275 276 StringMap<uint32_t>::iterator It = 277 t.insert(std::make_pair("abcdef", 42)).first; 278 EXPECT_EQ(16u, t.getNumBuckets()); 279 EXPECT_EQ("abcdef", It->first()); 280 EXPECT_EQ(42u, It->second); 281 } 282 283 TEST_F(StringMapTest, InsertOrAssignTest) { 284 struct A : CountCopyAndMove { 285 A(int v) : v(v) {} 286 int v; 287 }; 288 StringMap<A> t(0); 289 290 auto try1 = t.insert_or_assign("A", A(1)); 291 EXPECT_TRUE(try1.second); 292 EXPECT_EQ(1, try1.first->second.v); 293 EXPECT_EQ(1, try1.first->second.move); 294 295 auto try2 = t.insert_or_assign("A", A(2)); 296 EXPECT_FALSE(try2.second); 297 EXPECT_EQ(2, try2.first->second.v); 298 EXPECT_EQ(2, try1.first->second.move); 299 300 EXPECT_EQ(try1.first, try2.first); 301 EXPECT_EQ(0, try1.first->second.copy); 302 } 303 304 TEST_F(StringMapTest, IterMapKeys) { 305 StringMap<int> Map; 306 Map["A"] = 1; 307 Map["B"] = 2; 308 Map["C"] = 3; 309 Map["D"] = 3; 310 311 auto Keys = to_vector<4>(Map.keys()); 312 llvm::sort(Keys); 313 314 SmallVector<StringRef, 4> Expected = {"A", "B", "C", "D"}; 315 EXPECT_EQ(Expected, Keys); 316 } 317 318 // Create a non-default constructable value 319 struct StringMapTestStruct { 320 StringMapTestStruct(int i) : i(i) {} 321 StringMapTestStruct() = delete; 322 int i; 323 }; 324 325 TEST_F(StringMapTest, NonDefaultConstructable) { 326 StringMap<StringMapTestStruct> t; 327 t.insert(std::make_pair("Test", StringMapTestStruct(123))); 328 StringMap<StringMapTestStruct>::iterator iter = t.find("Test"); 329 ASSERT_NE(iter, t.end()); 330 ASSERT_EQ(iter->second.i, 123); 331 } 332 333 struct Immovable { 334 Immovable() {} 335 Immovable(Immovable&&) = delete; // will disable the other special members 336 }; 337 338 struct MoveOnly { 339 int i; 340 MoveOnly(int i) : i(i) {} 341 MoveOnly(const Immovable&) : i(0) {} 342 MoveOnly(MoveOnly &&RHS) : i(RHS.i) {} 343 MoveOnly &operator=(MoveOnly &&RHS) { 344 i = RHS.i; 345 return *this; 346 } 347 348 private: 349 MoveOnly(const MoveOnly &) = delete; 350 MoveOnly &operator=(const MoveOnly &) = delete; 351 }; 352 353 TEST_F(StringMapTest, MoveOnly) { 354 StringMap<MoveOnly> t; 355 t.insert(std::make_pair("Test", MoveOnly(42))); 356 StringRef Key = "Test"; 357 StringMapEntry<MoveOnly>::Create(Key, t.getAllocator(), MoveOnly(42)) 358 ->Destroy(t.getAllocator()); 359 } 360 361 TEST_F(StringMapTest, CtorArg) { 362 StringRef Key = "Test"; 363 MallocAllocator Allocator; 364 StringMapEntry<MoveOnly>::Create(Key, Allocator, Immovable()) 365 ->Destroy(Allocator); 366 } 367 368 TEST_F(StringMapTest, MoveConstruct) { 369 StringMap<int> A; 370 A["x"] = 42; 371 StringMap<int> B = std::move(A); 372 ASSERT_EQ(A.size(), 0u); 373 ASSERT_EQ(B.size(), 1u); 374 ASSERT_EQ(B["x"], 42); 375 ASSERT_EQ(B.count("y"), 0u); 376 } 377 378 TEST_F(StringMapTest, MoveAssignment) { 379 StringMap<int> A; 380 A["x"] = 42; 381 StringMap<int> B; 382 B["y"] = 117; 383 A = std::move(B); 384 ASSERT_EQ(A.size(), 1u); 385 ASSERT_EQ(B.size(), 0u); 386 ASSERT_EQ(A["y"], 117); 387 ASSERT_EQ(B.count("x"), 0u); 388 } 389 390 struct Countable { 391 int &InstanceCount; 392 int Number; 393 Countable(int Number, int &InstanceCount) 394 : InstanceCount(InstanceCount), Number(Number) { 395 ++InstanceCount; 396 } 397 Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) { 398 ++InstanceCount; 399 C.Number = -1; 400 } 401 Countable(const Countable &C) 402 : InstanceCount(C.InstanceCount), Number(C.Number) { 403 ++InstanceCount; 404 } 405 Countable &operator=(Countable C) { 406 Number = C.Number; 407 return *this; 408 } 409 ~Countable() { --InstanceCount; } 410 }; 411 412 TEST_F(StringMapTest, MoveDtor) { 413 int InstanceCount = 0; 414 StringMap<Countable> A; 415 A.insert(std::make_pair("x", Countable(42, InstanceCount))); 416 ASSERT_EQ(InstanceCount, 1); 417 auto I = A.find("x"); 418 ASSERT_NE(I, A.end()); 419 ASSERT_EQ(I->second.Number, 42); 420 421 StringMap<Countable> B; 422 B = std::move(A); 423 ASSERT_EQ(InstanceCount, 1); 424 ASSERT_TRUE(A.empty()); 425 I = B.find("x"); 426 ASSERT_NE(I, B.end()); 427 ASSERT_EQ(I->second.Number, 42); 428 429 B = StringMap<Countable>(); 430 ASSERT_EQ(InstanceCount, 0); 431 ASSERT_TRUE(B.empty()); 432 } 433 434 namespace { 435 // Simple class that counts how many moves and copy happens when growing a map 436 struct CountCtorCopyAndMove { 437 static unsigned Ctor; 438 static unsigned Move; 439 static unsigned Copy; 440 int Data = 0; 441 CountCtorCopyAndMove(int Data) : Data(Data) { Ctor++; } 442 CountCtorCopyAndMove() { Ctor++; } 443 444 CountCtorCopyAndMove(const CountCtorCopyAndMove &) { Copy++; } 445 CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &) { 446 Copy++; 447 return *this; 448 } 449 CountCtorCopyAndMove(CountCtorCopyAndMove &&) { Move++; } 450 CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &&) { 451 Move++; 452 return *this; 453 } 454 }; 455 unsigned CountCtorCopyAndMove::Copy = 0; 456 unsigned CountCtorCopyAndMove::Move = 0; 457 unsigned CountCtorCopyAndMove::Ctor = 0; 458 459 } // anonymous namespace 460 461 // Make sure creating the map with an initial size of N actually gives us enough 462 // buckets to insert N items without increasing allocation size. 463 TEST(StringMapCustomTest, InitialSizeTest) { 464 // 1 is an "edge value", 32 is an arbitrary power of two, and 67 is an 465 // arbitrary prime, picked without any good reason. 466 for (auto Size : {1, 32, 67}) { 467 StringMap<CountCtorCopyAndMove> Map(Size); 468 auto NumBuckets = Map.getNumBuckets(); 469 CountCtorCopyAndMove::Move = 0; 470 CountCtorCopyAndMove::Copy = 0; 471 for (int i = 0; i < Size; ++i) 472 Map.insert(std::pair<std::string, CountCtorCopyAndMove>( 473 std::piecewise_construct, std::forward_as_tuple(Twine(i).str()), 474 std::forward_as_tuple(i))); 475 // After the initial move, the map will move the Elts in the Entry. 476 EXPECT_EQ((unsigned)Size * 2, CountCtorCopyAndMove::Move); 477 // We copy once the pair from the Elts vector 478 EXPECT_EQ(0u, CountCtorCopyAndMove::Copy); 479 // Check that the map didn't grow 480 EXPECT_EQ(Map.getNumBuckets(), NumBuckets); 481 } 482 } 483 484 TEST(StringMapCustomTest, BracketOperatorCtor) { 485 StringMap<CountCtorCopyAndMove> Map; 486 CountCtorCopyAndMove::Ctor = 0; 487 Map["abcd"]; 488 EXPECT_EQ(1u, CountCtorCopyAndMove::Ctor); 489 // Test that operator[] does not create a value when it is already in the map 490 CountCtorCopyAndMove::Ctor = 0; 491 Map["abcd"]; 492 EXPECT_EQ(0u, CountCtorCopyAndMove::Ctor); 493 } 494 495 namespace { 496 struct NonMoveableNonCopyableType { 497 int Data = 0; 498 NonMoveableNonCopyableType() = default; 499 NonMoveableNonCopyableType(int Data) : Data(Data) {} 500 NonMoveableNonCopyableType(const NonMoveableNonCopyableType &) = delete; 501 NonMoveableNonCopyableType(NonMoveableNonCopyableType &&) = delete; 502 }; 503 } 504 505 // Test that we can "emplace" an element in the map without involving map/move 506 TEST(StringMapCustomTest, EmplaceTest) { 507 StringMap<NonMoveableNonCopyableType> Map; 508 Map.try_emplace("abcd", 42); 509 EXPECT_EQ(1u, Map.count("abcd")); 510 EXPECT_EQ(42, Map["abcd"].Data); 511 } 512 513 // Test that StringMapEntryBase can handle size_t wide sizes. 514 TEST(StringMapCustomTest, StringMapEntryBaseSize) { 515 size_t LargeValue; 516 517 // Test that the entry can represent max-unsigned. 518 if (sizeof(size_t) <= sizeof(unsigned)) 519 LargeValue = std::numeric_limits<unsigned>::max(); 520 else 521 LargeValue = std::numeric_limits<unsigned>::max() + 1ULL; 522 StringMapEntryBase LargeBase(LargeValue); 523 EXPECT_EQ(LargeValue, LargeBase.getKeyLength()); 524 525 // Test that the entry can hold at least max size_t. 526 LargeValue = std::numeric_limits<size_t>::max(); 527 StringMapEntryBase LargerBase(LargeValue); 528 LargeValue = std::numeric_limits<size_t>::max(); 529 EXPECT_EQ(LargeValue, LargerBase.getKeyLength()); 530 } 531 532 // Test that StringMapEntry can handle size_t wide sizes. 533 TEST(StringMapCustomTest, StringMapEntrySize) { 534 size_t LargeValue; 535 536 // Test that the entry can represent max-unsigned. 537 if (sizeof(size_t) <= sizeof(unsigned)) 538 LargeValue = std::numeric_limits<unsigned>::max(); 539 else 540 LargeValue = std::numeric_limits<unsigned>::max() + 1ULL; 541 StringMapEntry<int> LargeEntry(LargeValue); 542 StringRef Key = LargeEntry.getKey(); 543 EXPECT_EQ(LargeValue, Key.size()); 544 545 // Test that the entry can hold at least max size_t. 546 LargeValue = std::numeric_limits<size_t>::max(); 547 StringMapEntry<int> LargerEntry(LargeValue); 548 Key = LargerEntry.getKey(); 549 EXPECT_EQ(LargeValue, Key.size()); 550 } 551 552 } // end anonymous namespace 553