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