X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=unittests%2FADT%2FStringMapTest.cpp;h=028375d7b4be48a51c7f84a8103aaeaa896c2c2a;hb=86ec9c4081169d44637d08afc4c9d88c4dd7f410;hp=ea91348a5bdf730e92085d5778ad1c78b6de18bc;hpb=1f6efa3996dd1929fbc129203ce5009b620e6969;p=oota-llvm.git

diff --git a/unittests/ADT/StringMapTest.cpp b/unittests/ADT/StringMapTest.cpp
index ea91348a5bd..028375d7b4b 100644
--- a/unittests/ADT/StringMapTest.cpp
+++ b/unittests/ADT/StringMapTest.cpp
@@ -10,6 +10,7 @@
 #include "gtest/gtest.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/DataTypes.h"
+#include <tuple>
 using namespace llvm;
 
 namespace {
@@ -51,7 +52,7 @@ protected:
 
     // Iterator tests
     StringMap<uint32_t>::iterator it = testMap.begin();
-    EXPECT_STREQ(testKey, it->first());
+    EXPECT_STREQ(testKey, it->first().data());
     EXPECT_EQ(testValue, it->second);
     ++it;
     EXPECT_TRUE(it == testMap.end());
@@ -75,7 +76,6 @@ const std::string StringMapTest::testKeyStr(testKey);
 
 // Empty map tests.
 TEST_F(StringMapTest, EmptyMapTest) {
-  SCOPED_TRACE("EmptyMapTest");
   assertEmptyMap();
 }
 
@@ -102,14 +102,12 @@ TEST_F(StringMapTest, ConstEmptyMapTest) {
 
 // A map with a single entry.
 TEST_F(StringMapTest, SingleEntryMapTest) {
-  SCOPED_TRACE("SingleEntryMapTest");
   testMap[testKey] = testValue;
   assertSingleItemMap();
 }
 
 // Test clear() method.
 TEST_F(StringMapTest, ClearTest) {
-  SCOPED_TRACE("ClearTest");
   testMap[testKey] = testValue;
   testMap.clear();
   assertEmptyMap();
@@ -117,7 +115,6 @@ TEST_F(StringMapTest, ClearTest) {
 
 // Test erase(iterator) method.
 TEST_F(StringMapTest, EraseIteratorTest) {
-  SCOPED_TRACE("EraseIteratorTest");
   testMap[testKey] = testValue;
   testMap.erase(testMap.begin());
   assertEmptyMap();
@@ -125,7 +122,6 @@ TEST_F(StringMapTest, EraseIteratorTest) {
 
 // Test erase(value) method.
 TEST_F(StringMapTest, EraseValueTest) {
-  SCOPED_TRACE("EraseValueTest");
   testMap[testKey] = testValue;
   testMap.erase(testKey);
   assertEmptyMap();
@@ -133,13 +129,34 @@ TEST_F(StringMapTest, EraseValueTest) {
 
 // Test inserting two values and erasing one.
 TEST_F(StringMapTest, InsertAndEraseTest) {
-  SCOPED_TRACE("InsertAndEraseTest");
   testMap[testKey] = testValue;
   testMap["otherKey"] = 2;
   testMap.erase("otherKey");
   assertSingleItemMap();
 }
 
+TEST_F(StringMapTest, SmallFullMapTest) {
+  // StringMap has a tricky corner case when the map is small (<8 buckets) and
+  // it fills up through a balanced pattern of inserts and erases. This can
+  // lead to inf-loops in some cases (PR13148) so we test it explicitly here.
+  llvm::StringMap<int> Map(2);
+
+  Map["eins"] = 1;
+  Map["zwei"] = 2;
+  Map["drei"] = 3;
+  Map.erase("drei");
+  Map.erase("eins");
+  Map["veir"] = 4;
+  Map["funf"] = 5;
+
+  EXPECT_EQ(3u, Map.size());
+  EXPECT_EQ(0, Map.lookup("eins"));
+  EXPECT_EQ(2, Map.lookup("zwei"));
+  EXPECT_EQ(0, Map.lookup("drei"));
+  EXPECT_EQ(4, Map.lookup("veir"));
+  EXPECT_EQ(5, Map.lookup("funf"));
+}
+
 // A more complex iteration test.
 TEST_F(StringMapTest, IterationTest) {
   bool visited[100];
@@ -157,7 +174,7 @@ TEST_F(StringMapTest, IterationTest) {
       it != testMap.end(); ++it) {
     std::stringstream ss;
     ss << "key_" << it->second;
-    ASSERT_STREQ(ss.str().c_str(), it->first());
+    ASSERT_STREQ(ss.str().c_str(), it->first().data());
     visited[it->second] = true;
   }
 
@@ -167,29 +184,12 @@ TEST_F(StringMapTest, IterationTest) {
   }
 }
 
-} // end anonymous namespace
-
-namespace llvm {
-
-template <>
-class StringMapEntryInitializer<uint32_t> {
-public:
-  template <typename InitTy>
-  static void Initialize(StringMapEntry<uint32_t> &T, InitTy InitVal) {
-    T.second = InitVal;
-  }
-};
-
-} // end llvm namespace
-
-namespace {
-
 // Test StringMapEntry::Create() method.
 TEST_F(StringMapTest, StringMapEntryTest) {
   StringMap<uint32_t>::value_type* entry =
       StringMap<uint32_t>::value_type::Create(
-          testKeyFirst, testKeyFirst + testKeyLength, 1u);
-  EXPECT_STREQ(testKey, entry->first());
+          StringRef(testKeyFirst, testKeyLength), 1u);
+  EXPECT_STREQ(testKey, entry->first().data());
   EXPECT_EQ(1u, entry->second);
   free(entry);
 }
@@ -199,9 +199,149 @@ TEST_F(StringMapTest, InsertTest) {
   SCOPED_TRACE("InsertTest");
   testMap.insert(
       StringMap<uint32_t>::value_type::Create(
-          testKeyFirst, testKeyFirst + testKeyLength, 
+          StringRef(testKeyFirst, testKeyLength),
           testMap.getAllocator(), 1u));
   assertSingleItemMap();
 }
 
+// Test insert(pair<K, V>) method
+TEST_F(StringMapTest, InsertPairTest) {
+  bool Inserted;
+  StringMap<uint32_t>::iterator NewIt;
+  std::tie(NewIt, Inserted) =
+      testMap.insert(std::make_pair(testKeyFirst, testValue));
+  EXPECT_EQ(1u, testMap.size());
+  EXPECT_EQ(testValue, testMap[testKeyFirst]);
+  EXPECT_EQ(testKeyFirst, NewIt->first());
+  EXPECT_EQ(testValue, NewIt->second);
+  EXPECT_TRUE(Inserted);
+
+  StringMap<uint32_t>::iterator ExistingIt;
+  std::tie(ExistingIt, Inserted) =
+      testMap.insert(std::make_pair(testKeyFirst, testValue + 1));
+  EXPECT_EQ(1u, testMap.size());
+  EXPECT_EQ(testValue, testMap[testKeyFirst]);
+  EXPECT_FALSE(Inserted);
+  EXPECT_EQ(NewIt, ExistingIt);
+}
+
+// Test insert(pair<K, V>) method when rehashing occurs
+TEST_F(StringMapTest, InsertRehashingPairTest) {
+  // Check that the correct iterator is returned when the inserted element is
+  // moved to a different bucket during internal rehashing. This depends on
+  // the particular key, and the implementation of StringMap and HashString.
+  // Changes to those might result in this test not actually checking that.
+  StringMap<uint32_t> t(1);
+  EXPECT_EQ(1u, t.getNumBuckets());
+
+  StringMap<uint32_t>::iterator It =
+    t.insert(std::make_pair("abcdef", 42)).first;
+  EXPECT_EQ(2u, t.getNumBuckets());
+  EXPECT_EQ("abcdef", It->first());
+  EXPECT_EQ(42u, It->second);
+}
+
+// Create a non-default constructable value
+struct StringMapTestStruct {
+  StringMapTestStruct(int i) : i(i) {}
+  StringMapTestStruct() LLVM_DELETED_FUNCTION;
+  int i;
+};
+
+TEST_F(StringMapTest, NonDefaultConstructable) {
+  StringMap<StringMapTestStruct> t;
+  t.GetOrCreateValue("Test", StringMapTestStruct(123));
+  StringMap<StringMapTestStruct>::iterator iter = t.find("Test");
+  ASSERT_NE(iter, t.end());
+  ASSERT_EQ(iter->second.i, 123);
+}
+
+struct MoveOnly {
+  int i;
+  MoveOnly(int i) : i(i) {}
+  MoveOnly(MoveOnly &&RHS) : i(RHS.i) {}
+  MoveOnly &operator=(MoveOnly &&RHS) {
+    i = RHS.i;
+    return *this;
+  }
+
+private:
+  MoveOnly(const MoveOnly &) LLVM_DELETED_FUNCTION;
+  MoveOnly &operator=(const MoveOnly &) LLVM_DELETED_FUNCTION;
+};
+
+TEST_F(StringMapTest, MoveOnlyKey) {
+  StringMap<MoveOnly> t;
+  t.GetOrCreateValue("Test", MoveOnly(42));
+  StringRef Key = "Test";
+  StringMapEntry<MoveOnly>::Create(Key, MoveOnly(42))
+      ->Destroy();
+}
+
+TEST_F(StringMapTest, MoveConstruct) {
+  StringMap<int> A;
+  A.GetOrCreateValue("x", 42);
+  StringMap<int> B = std::move(A);
+  ASSERT_EQ(A.size(), 0u);
+  ASSERT_EQ(B.size(), 1u);
+  ASSERT_EQ(B["x"], 42);
+  ASSERT_EQ(B.count("y"), 0u);
+}
+
+TEST_F(StringMapTest, MoveAssignment) {
+  StringMap<int> A;
+  A["x"] = 42;
+  StringMap<int> B;
+  B["y"] = 117;
+  A = std::move(B);
+  ASSERT_EQ(A.size(), 1u);
+  ASSERT_EQ(B.size(), 0u);
+  ASSERT_EQ(A["y"], 117);
+  ASSERT_EQ(B.count("x"), 0u);
+}
+
+struct Countable {
+  int &InstanceCount;
+  int Number;
+  Countable(int Number, int &InstanceCount)
+      : InstanceCount(InstanceCount), Number(Number) {
+    ++InstanceCount;
+  }
+  Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) {
+    ++InstanceCount;
+    C.Number = -1;
+  }
+  Countable(const Countable &C)
+      : InstanceCount(C.InstanceCount), Number(C.Number) {
+    ++InstanceCount;
+  }
+  Countable &operator=(Countable C) {
+    Number = C.Number;
+    return *this;
+  }
+  ~Countable() { --InstanceCount; }
+};
+
+TEST_F(StringMapTest, MoveDtor) {
+  int InstanceCount = 0;
+  StringMap<Countable> A;
+  A.GetOrCreateValue("x", Countable(42, InstanceCount));
+  ASSERT_EQ(InstanceCount, 1);
+  auto I = A.find("x");
+  ASSERT_NE(I, A.end());
+  ASSERT_EQ(I->second.Number, 42);
+
+  StringMap<Countable> B;
+  B = std::move(A);
+  ASSERT_EQ(InstanceCount, 1);
+  ASSERT_TRUE(A.empty());
+  I = B.find("x");
+  ASSERT_NE(I, B.end());
+  ASSERT_EQ(I->second.Number, 42);
+
+  B = StringMap<Countable>();
+  ASSERT_EQ(InstanceCount, 0);
+  ASSERT_TRUE(B.empty());
+}
+
 } // end anonymous namespace