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"
13using namespace llvm;
14
15namespace {
16
17// Test fixture
18class StringMapTest : public testing::Test {
19protected:
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
70const char StringMapTest::testKey[] = "key";
71const uint32_t StringMapTest::testValue = 1u;
72const char* StringMapTest::testKeyFirst = testKey;
73size_t StringMapTest::testKeyLength = sizeof(testKey) - 1;
74const std::string StringMapTest::testKeyStr(testKey);
75
76// Empty map tests.
77TEST_F(StringMapTest, EmptyMapTest) {
78  assertEmptyMap();
79}
80
81// Constant map tests.
82TEST_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.
103TEST_F(StringMapTest, SingleEntryMapTest) {
104  testMap[testKey] = testValue;
105  assertSingleItemMap();
106}
107
108// Test clear() method.
109TEST_F(StringMapTest, ClearTest) {
110  testMap[testKey] = testValue;
111  testMap.clear();
112  assertEmptyMap();
113}
114
115// Test erase(iterator) method.
116TEST_F(StringMapTest, EraseIteratorTest) {
117  testMap[testKey] = testValue;
118  testMap.erase(testMap.begin());
119  assertEmptyMap();
120}
121
122// Test erase(value) method.
123TEST_F(StringMapTest, EraseValueTest) {
124  testMap[testKey] = testValue;
125  testMap.erase(testKey);
126  assertEmptyMap();
127}
128
129// Test inserting two values and erasing one.
130TEST_F(StringMapTest, InsertAndEraseTest) {
131  testMap[testKey] = testValue;
132  testMap["otherKey"] = 2;
133  testMap.erase("otherKey");
134  assertSingleItemMap();
135}
136
137TEST_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.
160TEST_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} // end anonymous namespace
187
188namespace llvm {
189
190template <>
191class StringMapEntryInitializer<uint32_t> {
192public:
193  template <typename InitTy>
194  static void Initialize(StringMapEntry<uint32_t> &T, InitTy InitVal) {
195    T.second = InitVal;
196  }
197};
198
199} // end llvm namespace
200
201namespace {
202
203// Test StringMapEntry::Create() method.
204TEST_F(StringMapTest, StringMapEntryTest) {
205  StringMap<uint32_t>::value_type* entry =
206      StringMap<uint32_t>::value_type::Create(
207          testKeyFirst, testKeyFirst + testKeyLength, 1u);
208  EXPECT_STREQ(testKey, entry->first().data());
209  EXPECT_EQ(1u, entry->second);
210  free(entry);
211}
212
213// Test insert() method.
214TEST_F(StringMapTest, InsertTest) {
215  SCOPED_TRACE("InsertTest");
216  testMap.insert(
217      StringMap<uint32_t>::value_type::Create(
218          testKeyFirst, testKeyFirst + testKeyLength,
219          testMap.getAllocator(), 1u));
220  assertSingleItemMap();
221}
222
223} // end anonymous namespace
224