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