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"
19 class StringMapTest : public testing::Test {
21 StringMap<uint32_t> testMap;
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;
29 void assertEmptyMap() {
31 EXPECT_EQ(0u, testMap.size());
32 EXPECT_TRUE(testMap.empty());
35 EXPECT_TRUE(testMap.begin() == testMap.end());
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)) ==
44 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end());
47 void assertSingleItemMap() {
49 EXPECT_EQ(1u, testMap.size());
50 EXPECT_FALSE(testMap.begin() == testMap.end());
51 EXPECT_FALSE(testMap.empty());
54 StringMap<uint32_t>::iterator it = testMap.begin();
55 EXPECT_STREQ(testKey, it->first().data());
56 EXPECT_EQ(testValue, it->second);
58 EXPECT_TRUE(it == testMap.end());
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)) ==
67 EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin());
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);
78 TEST_F(StringMapTest, EmptyMapTest) {
82 // Constant map tests.
83 TEST_F(StringMapTest, ConstEmptyMapTest) {
84 const StringMap<uint32_t>& constTestMap = testMap;
87 EXPECT_EQ(0u, constTestMap.size());
88 EXPECT_TRUE(constTestMap.empty());
91 EXPECT_TRUE(constTestMap.begin() == constTestMap.end());
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)) ==
100 EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end());
103 // A map with a single entry.
104 TEST_F(StringMapTest, SingleEntryMapTest) {
105 testMap[testKey] = testValue;
106 assertSingleItemMap();
109 // Test clear() method.
110 TEST_F(StringMapTest, ClearTest) {
111 testMap[testKey] = testValue;
116 // Test erase(iterator) method.
117 TEST_F(StringMapTest, EraseIteratorTest) {
118 testMap[testKey] = testValue;
119 testMap.erase(testMap.begin());
123 // Test erase(value) method.
124 TEST_F(StringMapTest, EraseValueTest) {
125 testMap[testKey] = testValue;
126 testMap.erase(testKey);
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();
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);
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"));
160 // A more complex iteration test.
161 TEST_F(StringMapTest, IterationTest) {
164 // Insert 100 numbers into the map
165 for (int i = 0; i < 100; ++i) {
166 std::stringstream ss;
168 testMap[ss.str()] = i;
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;
181 // Ensure every number was visited.
182 for (int i = 0; i < 100; ++i) {
183 ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited";
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);
197 // Test insert() method.
198 TEST_F(StringMapTest, InsertTest) {
199 SCOPED_TRACE("InsertTest");
201 StringMap<uint32_t>::value_type::Create(
202 StringRef(testKeyFirst, testKeyLength),
203 testMap.getAllocator(), 1u));
204 assertSingleItemMap();
207 // Test insert(pair<K, V>) method
208 TEST_F(StringMapTest, InsertPairTest) {
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);
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);
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());
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);
244 // Create a non-default constructable value
245 struct StringMapTestStruct {
246 StringMapTestStruct(int i) : i(i) {}
247 StringMapTestStruct() = delete;
251 TEST_F(StringMapTest, NonDefaultConstructable) {
252 StringMap<StringMapTestStruct> t;
253 t.insert(std::make_pair("Test", StringMapTestStruct(123)));
254 StringMap<StringMapTestStruct>::iterator iter = t.find("Test");
255 ASSERT_NE(iter, t.end());
256 ASSERT_EQ(iter->second.i, 123);
261 Immovable(Immovable&&) = delete; // will disable the other special members
266 MoveOnly(int i) : i(i) {}
267 MoveOnly(const Immovable&) : i(0) {}
268 MoveOnly(MoveOnly &&RHS) : i(RHS.i) {}
269 MoveOnly &operator=(MoveOnly &&RHS) {
275 MoveOnly(const MoveOnly &) = delete;
276 MoveOnly &operator=(const MoveOnly &) = delete;
279 TEST_F(StringMapTest, MoveOnly) {
280 StringMap<MoveOnly> t;
281 t.insert(std::make_pair("Test", MoveOnly(42)));
282 StringRef Key = "Test";
283 StringMapEntry<MoveOnly>::Create(Key, MoveOnly(42))
287 TEST_F(StringMapTest, CtorArg) {
288 StringRef Key = "Test";
289 StringMapEntry<MoveOnly>::Create(Key, Immovable())
293 TEST_F(StringMapTest, MoveConstruct) {
296 StringMap<int> B = std::move(A);
297 ASSERT_EQ(A.size(), 0u);
298 ASSERT_EQ(B.size(), 1u);
299 ASSERT_EQ(B["x"], 42);
300 ASSERT_EQ(B.count("y"), 0u);
303 TEST_F(StringMapTest, MoveAssignment) {
309 ASSERT_EQ(A.size(), 1u);
310 ASSERT_EQ(B.size(), 0u);
311 ASSERT_EQ(A["y"], 117);
312 ASSERT_EQ(B.count("x"), 0u);
318 Countable(int Number, int &InstanceCount)
319 : InstanceCount(InstanceCount), Number(Number) {
322 Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) {
326 Countable(const Countable &C)
327 : InstanceCount(C.InstanceCount), Number(C.Number) {
330 Countable &operator=(Countable C) {
334 ~Countable() { --InstanceCount; }
337 TEST_F(StringMapTest, MoveDtor) {
338 int InstanceCount = 0;
339 StringMap<Countable> A;
340 A.insert(std::make_pair("x", Countable(42, InstanceCount)));
341 ASSERT_EQ(InstanceCount, 1);
342 auto I = A.find("x");
343 ASSERT_NE(I, A.end());
344 ASSERT_EQ(I->second.Number, 42);
346 StringMap<Countable> B;
348 ASSERT_EQ(InstanceCount, 1);
349 ASSERT_TRUE(A.empty());
351 ASSERT_NE(I, B.end());
352 ASSERT_EQ(I->second.Number, 42);
354 B = StringMap<Countable>();
355 ASSERT_EQ(InstanceCount, 0);
356 ASSERT_TRUE(B.empty());
359 } // end anonymous namespace