llvm/unittests/ADT/StringMapTest.cpp

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