unittests/ADT/StringMapTest.cpp

   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 "gtest/gtest.h"
  11 #include "llvm/ADT/StringMap.h"
  12 #include "llvm/Support/DataTypes.h"
  13 #include <tuple>
  14 using namespace llvm;
  15
  16 namespace {
  17
  18 // Test fixture
  19 class StringMapTest : public testing::Test {
  20 protected:
  21   StringMap<uint32_t> testMap;
  22
  23   static const char testKey[];
  24   static const uint32_t testValue;
  25   static const char* testKeyFirst;
  26   static size_t testKeyLength;
  27   static const std::string testKeyStr;
  28
  29   void assertEmptyMap() {
  30     // Size tests
  31     EXPECT_EQ(0u, testMap.size());
  32     EXPECT_TRUE(testMap.empty());
  33
  34     // Iterator tests
  35     EXPECT_TRUE(testMap.begin() == testMap.end());
  36
  37     // Lookup tests
  38     EXPECT_EQ(0u, testMap.count(testKey));
  39     EXPECT_EQ(0u, testMap.count(StringRef(testKeyFirst, testKeyLength)));
  40     EXPECT_EQ(0u, testMap.count(testKeyStr));
  41     EXPECT_TRUE(testMap.find(testKey) == testMap.end());
  42     EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) ==
  43                 testMap.end());
  44     EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end());
  45   }
  46
  47   void assertSingleItemMap() {
  48     // Size tests
  49     EXPECT_EQ(1u, testMap.size());
  50     EXPECT_FALSE(testMap.begin() == testMap.end());
  51     EXPECT_FALSE(testMap.empty());
  52
  53     // Iterator tests
  54     StringMap<uint32_t>::iterator it = testMap.begin();
  55     EXPECT_STREQ(testKey, it->first().data());
  56     EXPECT_EQ(testValue, it->second);
  57     ++it;
  58     EXPECT_TRUE(it == testMap.end());
  59
  60     // Lookup tests
  61     EXPECT_EQ(1u, testMap.count(testKey));
  62     EXPECT_EQ(1u, testMap.count(StringRef(testKeyFirst, testKeyLength)));
  63     EXPECT_EQ(1u, testMap.count(testKeyStr));
  64     EXPECT_TRUE(testMap.find(testKey) == testMap.begin());
  65     EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) ==
  66                 testMap.begin());
  67     EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin());
  68   }
  69 };
  70
  71 const char StringMapTest::testKey[] = "key";
  72 const uint32_t StringMapTest::testValue = 1u;
  73 const char* StringMapTest::testKeyFirst = testKey;
  74 size_t StringMapTest::testKeyLength = sizeof(testKey) - 1;
  75 const std::string StringMapTest::testKeyStr(testKey);
  76
  77 // Empty map tests.
  78 TEST_F(StringMapTest, EmptyMapTest) {
  79   assertEmptyMap();
  80 }
  81
  82 // Constant map tests.
  83 TEST_F(StringMapTest, ConstEmptyMapTest) {
  84   const StringMap<uint32_t>& constTestMap = testMap;
  85
  86   // Size tests
  87   EXPECT_EQ(0u, constTestMap.size());
  88   EXPECT_TRUE(constTestMap.empty());
  89
  90   // Iterator tests
  91   EXPECT_TRUE(constTestMap.begin() == constTestMap.end());
  92
  93   // Lookup tests
  94   EXPECT_EQ(0u, constTestMap.count(testKey));
  95   EXPECT_EQ(0u, constTestMap.count(StringRef(testKeyFirst, testKeyLength)));
  96   EXPECT_EQ(0u, constTestMap.count(testKeyStr));
  97   EXPECT_TRUE(constTestMap.find(testKey) == constTestMap.end());
  98   EXPECT_TRUE(constTestMap.find(StringRef(testKeyFirst, testKeyLength)) ==
  99               constTestMap.end());
 100   EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end());
 101 }
 102
 103 // A map with a single entry.
 104 TEST_F(StringMapTest, SingleEntryMapTest) {
 105   testMap[testKey] = testValue;
 106   assertSingleItemMap();
 107 }
 108
 109 // Test clear() method.
 110 TEST_F(StringMapTest, ClearTest) {
 111   testMap[testKey] = testValue;
 112   testMap.clear();
 113   assertEmptyMap();
 114 }
 115
 116 // Test erase(iterator) method.
 117 TEST_F(StringMapTest, EraseIteratorTest) {
 118   testMap[testKey] = testValue;
 119   testMap.erase(testMap.begin());
 120   assertEmptyMap();
 121 }
 122
 123 // Test erase(value) method.
 124 TEST_F(StringMapTest, EraseValueTest) {
 125   testMap[testKey] = testValue;
 126   testMap.erase(testKey);
 127   assertEmptyMap();
 128 }
 129
 130 // Test inserting two values and erasing one.
 131 TEST_F(StringMapTest, InsertAndEraseTest) {
 132   testMap[testKey] = testValue;
 133   testMap["otherKey"] = 2;
 134   testMap.erase("otherKey");
 135   assertSingleItemMap();
 136 }
 137
 138 TEST_F(StringMapTest, SmallFullMapTest) {
 139   // StringMap has a tricky corner case when the map is small (<8 buckets) and
 140   // it fills up through a balanced pattern of inserts and erases. This can
 141   // lead to inf-loops in some cases (PR13148) so we test it explicitly here.
 142   llvm::StringMap<int> Map(2);
 143
 144   Map["eins"] = 1;
 145   Map["zwei"] = 2;
 146   Map["drei"] = 3;
 147   Map.erase("drei");
 148   Map.erase("eins");
 149   Map["veir"] = 4;
 150   Map["funf"] = 5;
 151
 152   EXPECT_EQ(3u, Map.size());
 153   EXPECT_EQ(0, Map.lookup("eins"));
 154   EXPECT_EQ(2, Map.lookup("zwei"));
 155   EXPECT_EQ(0, Map.lookup("drei"));
 156   EXPECT_EQ(4, Map.lookup("veir"));
 157   EXPECT_EQ(5, Map.lookup("funf"));
 158 }
 159
 160 // A more complex iteration test.
 161 TEST_F(StringMapTest, IterationTest) {
 162   bool visited[100];
 163
 164   // Insert 100 numbers into the map
 165   for (int i = 0; i < 100; ++i) {
 166     std::stringstream ss;
 167     ss << "key_" << i;
 168     testMap[ss.str()] = i;
 169     visited[i] = false;
 170   }
 171
 172   // Iterate over all numbers and mark each one found.
 173   for (StringMap<uint32_t>::iterator it = testMap.begin();
 174       it != testMap.end(); ++it) {
 175     std::stringstream ss;
 176     ss << "key_" << it->second;
 177     ASSERT_STREQ(ss.str().c_str(), it->first().data());
 178     visited[it->second] = true;
 179   }
 180
 181   // Ensure every number was visited.
 182   for (int i = 0; i < 100; ++i) {
 183     ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited";
 184   }
 185 }
 186
 187 // Test StringMapEntry::Create() method.
 188 TEST_F(StringMapTest, StringMapEntryTest) {
 189   StringMap<uint32_t>::value_type* entry =
 190       StringMap<uint32_t>::value_type::Create(
 191           StringRef(testKeyFirst, testKeyLength), 1u);
 192   EXPECT_STREQ(testKey, entry->first().data());
 193   EXPECT_EQ(1u, entry->second);
 194   free(entry);
 195 }
 196
 197 // Test insert() method.
 198 TEST_F(StringMapTest, InsertTest) {
 199   SCOPED_TRACE("InsertTest");
 200   testMap.insert(
 201       StringMap<uint32_t>::value_type::Create(
 202           StringRef(testKeyFirst, testKeyLength),
 203           testMap.getAllocator(), 1u));
 204   assertSingleItemMap();
 205 }
 206
 207 // Test insert(pair<K, V>) method
 208 TEST_F(StringMapTest, InsertPairTest) {
 209   bool Inserted;
 210   StringMap<uint32_t>::iterator NewIt;
 211   std::tie(NewIt, Inserted) =
 212       testMap.insert(std::make_pair(testKeyFirst, testValue));
 213   EXPECT_EQ(1u, testMap.size());
 214   EXPECT_EQ(testValue, testMap[testKeyFirst]);
 215   EXPECT_EQ(testKeyFirst, NewIt->first());
 216   EXPECT_EQ(testValue, NewIt->second);
 217   EXPECT_TRUE(Inserted);
 218
 219   StringMap<uint32_t>::iterator ExistingIt;
 220   std::tie(ExistingIt, Inserted) =
 221       testMap.insert(std::make_pair(testKeyFirst, testValue + 1));
 222   EXPECT_EQ(1u, testMap.size());
 223   EXPECT_EQ(testValue, testMap[testKeyFirst]);
 224   EXPECT_FALSE(Inserted);
 225   EXPECT_EQ(NewIt, ExistingIt);
 226 }
 227
 228 // Test insert(pair<K, V>) method when rehashing occurs
 229 TEST_F(StringMapTest, InsertRehashingPairTest) {
 230   // Check that the correct iterator is returned when the inserted element is
 231   // moved to a different bucket during internal rehashing. This depends on
 232   // the particular key, and the implementation of StringMap and HashString.
 233   // Changes to those might result in this test not actually checking that.
 234   StringMap<uint32_t> t(1);
 235   EXPECT_EQ(1u, t.getNumBuckets());
 236
 237   StringMap<uint32_t>::iterator It =
 238     t.insert(std::make_pair("abcdef", 42)).first;
 239   EXPECT_EQ(2u, t.getNumBuckets());
 240   EXPECT_EQ("abcdef", It->first());
 241   EXPECT_EQ(42u, It->second);
 242 }
 243
 244 // Create a non-default constructable value
 245 struct StringMapTestStruct {
 246   StringMapTestStruct(int i) : i(i) {}
 247   StringMapTestStruct() LLVM_DELETED_FUNCTION;
 248   int i;
 249 };
 250
 251 TEST_F(StringMapTest, NonDefaultConstructable) {
 252   StringMap<StringMapTestStruct> t;
 253   t.GetOrCreateValue("Test", StringMapTestStruct(123));
 254   StringMap<StringMapTestStruct>::iterator iter = t.find("Test");
 255   ASSERT_NE(iter, t.end());
 256   ASSERT_EQ(iter->second.i, 123);
 257 }
 258
 259 struct MoveOnly {
 260   int i;
 261   MoveOnly(int i) : i(i) {}
 262   MoveOnly(MoveOnly &&RHS) : i(RHS.i) {}
 263   MoveOnly &operator=(MoveOnly &&RHS) {
 264     i = RHS.i;
 265     return *this;
 266   }
 267
 268 private:
 269   MoveOnly(const MoveOnly &) LLVM_DELETED_FUNCTION;
 270   MoveOnly &operator=(const MoveOnly &) LLVM_DELETED_FUNCTION;
 271 };
 272
 273 TEST_F(StringMapTest, MoveOnlyKey) {
 274   StringMap<MoveOnly> t;
 275   t.GetOrCreateValue("Test", MoveOnly(42));
 276   StringRef Key = "Test";
 277   StringMapEntry<MoveOnly>::Create(Key, MoveOnly(42))
 278       ->Destroy();
 279 }
 280
 281 TEST_F(StringMapTest, MoveConstruct) {
 282   StringMap<int> A;
 283   A.GetOrCreateValue("x", 42);
 284   StringMap<int> B = std::move(A);
 285   ASSERT_EQ(A.size(), 0u);
 286   ASSERT_EQ(B.size(), 1u);
 287   ASSERT_EQ(B["x"], 42);
 288   ASSERT_EQ(B.count("y"), 0u);
 289 }
 290
 291 TEST_F(StringMapTest, MoveAssignment) {
 292   StringMap<int> A;
 293   A["x"] = 42;
 294   StringMap<int> B;
 295   B["y"] = 117;
 296   A = std::move(B);
 297   ASSERT_EQ(A.size(), 1u);
 298   ASSERT_EQ(B.size(), 0u);
 299   ASSERT_EQ(A["y"], 117);
 300   ASSERT_EQ(B.count("x"), 0u);
 301 }
 302
 303 struct Countable {
 304   int &InstanceCount;
 305   int Number;
 306   Countable(int Number, int &InstanceCount)
 307       : InstanceCount(InstanceCount), Number(Number) {
 308     ++InstanceCount;
 309   }
 310   Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) {
 311     ++InstanceCount;
 312     C.Number = -1;
 313   }
 314   Countable(const Countable &C)
 315       : InstanceCount(C.InstanceCount), Number(C.Number) {
 316     ++InstanceCount;
 317   }
 318   Countable &operator=(Countable C) {
 319     Number = C.Number;
 320     return *this;
 321   }
 322   ~Countable() { --InstanceCount; }
 323 };
 324
 325 TEST_F(StringMapTest, MoveDtor) {
 326   int InstanceCount = 0;
 327   StringMap<Countable> A;
 328   A.GetOrCreateValue("x", Countable(42, InstanceCount));
 329   ASSERT_EQ(InstanceCount, 1);
 330   auto I = A.find("x");
 331   ASSERT_NE(I, A.end());
 332   ASSERT_EQ(I->second.Number, 42);
 333
 334   StringMap<Countable> B;
 335   B = std::move(A);
 336   ASSERT_EQ(InstanceCount, 1);
 337   ASSERT_TRUE(A.empty());
 338   I = B.find("x");
 339   ASSERT_NE(I, B.end());
 340   ASSERT_EQ(I->second.Number, 42);
 341
 342   B = StringMap<Countable>();
 343   ASSERT_EQ(InstanceCount, 0);
 344   ASSERT_TRUE(B.empty());
 345 }
 346
 347 } // end anonymous namespace