1 //===- llvm/unittest/ADT/StringMapMap.cpp - StringMap unit tests ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "gtest/gtest.h"
11 #include "llvm/ADT/StringMap.h"
12 #include "llvm/Support/DataTypes.h"
18 class StringMapTest : public testing::Test {
20 StringMap<uint32_t> testMap;
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;
28 void assertEmptyMap() {
30 EXPECT_EQ(0u, testMap.size());
31 EXPECT_TRUE(testMap.empty());
34 EXPECT_TRUE(testMap.begin() == testMap.end());
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)) ==
43 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end());
46 void assertSingleItemMap() {
48 EXPECT_EQ(1u, testMap.size());
49 EXPECT_FALSE(testMap.begin() == testMap.end());
50 EXPECT_FALSE(testMap.empty());
53 StringMap<uint32_t>::iterator it = testMap.begin();
54 EXPECT_STREQ(testKey, it->first().data());
55 EXPECT_EQ(testValue, it->second);
57 EXPECT_TRUE(it == testMap.end());
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)) ==
66 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin());
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);
77 TEST_F(StringMapTest, EmptyMapTest) {
81 // Constant map tests.
82 TEST_F(StringMapTest, ConstEmptyMapTest) {
83 const StringMap<uint32_t>& constTestMap = testMap;
86 EXPECT_EQ(0u, constTestMap.size());
87 EXPECT_TRUE(constTestMap.empty());
90 EXPECT_TRUE(constTestMap.begin() == constTestMap.end());
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)) ==
99 EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end());
102 // A map with a single entry.
103 TEST_F(StringMapTest, SingleEntryMapTest) {
104 testMap[testKey] = testValue;
105 assertSingleItemMap();
108 // Test clear() method.
109 TEST_F(StringMapTest, ClearTest) {
110 testMap[testKey] = testValue;
115 // Test erase(iterator) method.
116 TEST_F(StringMapTest, EraseIteratorTest) {
117 testMap[testKey] = testValue;
118 testMap.erase(testMap.begin());
122 // Test erase(value) method.
123 TEST_F(StringMapTest, EraseValueTest) {
124 testMap[testKey] = testValue;
125 testMap.erase(testKey);
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();
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);
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"));
159 // A more complex iteration test.
160 TEST_F(StringMapTest, IterationTest) {
163 // Insert 100 numbers into the map
164 for (int i = 0; i < 100; ++i) {
165 std::stringstream ss;
167 testMap[ss.str()] = i;
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;
180 // Ensure every number was visited.
181 for (int i = 0; i < 100; ++i) {
182 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited";
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 StringRef(testKeyFirst, testKeyLength), 1u);
191 EXPECT_STREQ(testKey, entry->first().data());
192 EXPECT_EQ(1u, entry->second);
196 // Test insert() method.
197 TEST_F(StringMapTest, InsertTest) {
198 SCOPED_TRACE("InsertTest");
200 StringMap<uint32_t>::value_type::Create(
201 StringRef(testKeyFirst, testKeyLength),
202 testMap.getAllocator(), 1u));
203 assertSingleItemMap();
206 // Create a non-default constructable value
207 struct StringMapTestStruct {
208 StringMapTestStruct(int i) : i(i) {}
209 StringMapTestStruct() LLVM_DELETED_FUNCTION;
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);
223 MoveOnly(int i) : i(i) {}
224 MoveOnly(MoveOnly &&RHS) : i(RHS.i) {}
225 MoveOnly &operator=(MoveOnly &&RHS) {
231 MoveOnly(const MoveOnly &);
232 MoveOnly &operator=(const MoveOnly &);
235 TEST_F(StringMapTest, MoveOnlyKey) {
236 StringMap<MoveOnly> t;
237 t.GetOrCreateValue("Test", MoveOnly(42));
238 StringRef Key = "Test";
239 StringMapEntry<MoveOnly>::Create(Key, MoveOnly(42))
243 TEST_F(StringMapTest, MoveConstruct) {
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);
253 TEST_F(StringMapTest, MoveAssignment) {
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);
268 Countable(int Number, int &InstanceCount)
269 : InstanceCount(InstanceCount), Number(Number) {
272 Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) {
276 Countable(const Countable &C)
277 : InstanceCount(C.InstanceCount), Number(C.Number) {
280 Countable &operator=(Countable C) {
284 ~Countable() { --InstanceCount; }
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);
296 StringMap<Countable> B;
298 ASSERT_EQ(InstanceCount, 1);
299 ASSERT_TRUE(A.empty());
301 ASSERT_NE(I, B.end());
302 ASSERT_EQ(I->second.Number, 42);
304 B = StringMap<Countable>();
305 ASSERT_EQ(InstanceCount, 0);
306 ASSERT_TRUE(B.empty());
309 } // end anonymous namespace