#include "gtest/gtest.h"
#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/DataTypes.h"
+#include <tuple>
using namespace llvm;
namespace {
static const char testKey[];
static const uint32_t testValue;
static const char* testKeyFirst;
- static const char* testKeyLast;
+ static size_t testKeyLength;
static const std::string testKeyStr;
void assertEmptyMap() {
// Lookup tests
EXPECT_EQ(0u, testMap.count(testKey));
- EXPECT_EQ(0u, testMap.count(testKeyFirst, testKeyLast));
+ EXPECT_EQ(0u, testMap.count(StringRef(testKeyFirst, testKeyLength)));
EXPECT_EQ(0u, testMap.count(testKeyStr));
EXPECT_TRUE(testMap.find(testKey) == testMap.end());
- EXPECT_TRUE(testMap.find(testKeyFirst, testKeyLast) == testMap.end());
+ EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) ==
+ testMap.end());
EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end());
}
// 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());
// Lookup tests
EXPECT_EQ(1u, testMap.count(testKey));
- EXPECT_EQ(1u, testMap.count(testKeyFirst, testKeyLast));
+ EXPECT_EQ(1u, testMap.count(StringRef(testKeyFirst, testKeyLength)));
EXPECT_EQ(1u, testMap.count(testKeyStr));
EXPECT_TRUE(testMap.find(testKey) == testMap.begin());
- EXPECT_TRUE(testMap.find(testKeyFirst, testKeyLast) == testMap.begin());
+ EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) ==
+ testMap.begin());
EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin());
}
};
const char StringMapTest::testKey[] = "key";
const uint32_t StringMapTest::testValue = 1u;
const char* StringMapTest::testKeyFirst = testKey;
-const char* StringMapTest::testKeyLast = testKey + sizeof(testKey) - 1;
+size_t StringMapTest::testKeyLength = sizeof(testKey) - 1;
const std::string StringMapTest::testKeyStr(testKey);
-// Empty map tests
+// Empty map tests.
TEST_F(StringMapTest, EmptyMapTest) {
- SCOPED_TRACE("EmptyMapTest");
assertEmptyMap();
}
-// Constant map tests
+// Constant map tests.
TEST_F(StringMapTest, ConstEmptyMapTest) {
const StringMap<uint32_t>& constTestMap = testMap;
// Lookup tests
EXPECT_EQ(0u, constTestMap.count(testKey));
- EXPECT_EQ(0u, constTestMap.count(testKeyFirst, testKeyLast));
+ EXPECT_EQ(0u, constTestMap.count(StringRef(testKeyFirst, testKeyLength)));
EXPECT_EQ(0u, constTestMap.count(testKeyStr));
EXPECT_TRUE(constTestMap.find(testKey) == constTestMap.end());
- EXPECT_TRUE(constTestMap.find(testKeyFirst, testKeyLast) ==
- constTestMap.end());
+ EXPECT_TRUE(constTestMap.find(StringRef(testKeyFirst, testKeyLength)) ==
+ constTestMap.end());
EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end());
}
-// A map with a single entry
+// A map with a single entry.
TEST_F(StringMapTest, SingleEntryMapTest) {
- SCOPED_TRACE("SingleEntryMapTest");
testMap[testKey] = testValue;
assertSingleItemMap();
}
-// Test clear() method
+// Test clear() method.
TEST_F(StringMapTest, ClearTest) {
- SCOPED_TRACE("ClearTest");
testMap[testKey] = testValue;
testMap.clear();
assertEmptyMap();
}
-// Test erase(iterator) method
+// Test erase(iterator) method.
TEST_F(StringMapTest, EraseIteratorTest) {
- SCOPED_TRACE("EraseIteratorTest");
testMap[testKey] = testValue;
testMap.erase(testMap.begin());
assertEmptyMap();
}
-// Test erase(value) method
+// Test erase(value) method.
TEST_F(StringMapTest, EraseValueTest) {
- SCOPED_TRACE("EraseValueTest");
testMap[testKey] = testValue;
testMap.erase(testKey);
assertEmptyMap();
}
-// Test inserting two values and erasing one
+// 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 StringMapEntry::Create() method.
-// DISABLED because this fails without a StringMapEntryInitializer, and
-// I can't get it to compile with one.
-TEST_F(StringMapTest, DISABLED_StringMapEntryTest) {
- StringMap<uint32_t>::value_type* entry =
- StringMap<uint32_t>::value_type::Create(
- testKeyFirst, testKeyLast, 1u);
- EXPECT_STREQ(testKey, entry->first());
- EXPECT_EQ(1u, entry->second);
-}
+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);
-// Test insert() method
-// DISABLED because this fails without a StringMapEntryInitializer, and
-// I can't get it to compile with one.
-TEST_F(StringMapTest, DISABLED_InsertTest) {
- SCOPED_TRACE("InsertTest");
- testMap.insert(
- StringMap<uint32_t>::value_type::Create(
- testKeyFirst, testKeyLast, testMap.getAllocator(), 1u));
- assertSingleItemMap();
+ 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
+// A more complex iteration test.
TEST_F(StringMapTest, IterationTest) {
bool visited[100];
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;
}
}
}
+// Test StringMapEntry::Create() method.
+TEST_F(StringMapTest, StringMapEntryTest) {
+ StringMap<uint32_t>::value_type* entry =
+ StringMap<uint32_t>::value_type::Create(
+ StringRef(testKeyFirst, testKeyLength), 1u);
+ EXPECT_STREQ(testKey, entry->first().data());
+ EXPECT_EQ(1u, entry->second);
+ free(entry);
+}
+
+// Test insert() method.
+TEST_F(StringMapTest, InsertTest) {
+ SCOPED_TRACE("InsertTest");
+ testMap.insert(
+ StringMap<uint32_t>::value_type::Create(
+ 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
projects / oota-llvm.git / blobdiff