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"
13#include <tuple>
14using namespace llvm;
15
16namespace {
17
18// Test fixture
19class StringMapTest : public testing::Test {
20protected:
21  StringMap<uint32_t> testMap;
22
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;
28
29  void assertEmptyMap() {
30    // Size tests
31    EXPECT_EQ(0u, testMap.size());
32    EXPECT_TRUE(testMap.empty());
33
34    // Iterator tests
35    EXPECT_TRUE(testMap.begin() == testMap.end());
36
37    // Lookup tests
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)) ==
43                testMap.end());
44    EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end());
45  }
46
47  void assertSingleItemMap() {
48    // Size tests
49    EXPECT_EQ(1u, testMap.size());
50    EXPECT_FALSE(testMap.begin() == testMap.end());
51    EXPECT_FALSE(testMap.empty());
52
53    // Iterator tests
54    StringMap<uint32_t>::iterator it = testMap.begin();
55    EXPECT_STREQ(testKey, it->first().data());
56    EXPECT_EQ(testValue, it->second);
57    ++it;
58    EXPECT_TRUE(it == testMap.end());
59
60    // Lookup tests
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)) ==
66                testMap.begin());
67    EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin());
68  }
69};
70
71const char StringMapTest::testKey[] = "key";
72const uint32_t StringMapTest::testValue = 1u;
73const char* StringMapTest::testKeyFirst = testKey;
74size_t StringMapTest::testKeyLength = sizeof(testKey) - 1;
75const std::string StringMapTest::testKeyStr(testKey);
76
77// Empty map tests.
78TEST_F(StringMapTest, EmptyMapTest) {
79  assertEmptyMap();
80}
81
82// Constant map tests.
83TEST_F(StringMapTest, ConstEmptyMapTest) {
84  const StringMap<uint32_t>& constTestMap = testMap;
85
86  // Size tests
87  EXPECT_EQ(0u, constTestMap.size());
88  EXPECT_TRUE(constTestMap.empty());
89
90  // Iterator tests
91  EXPECT_TRUE(constTestMap.begin() == constTestMap.end());
92
93  // Lookup tests
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)) ==
99              constTestMap.end());
100  EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end());
101}
102
103// A map with a single entry.
104TEST_F(StringMapTest, SingleEntryMapTest) {
105  testMap[testKey] = testValue;
106  assertSingleItemMap();
107}
108
109// Test clear() method.
110TEST_F(StringMapTest, ClearTest) {
111  testMap[testKey] = testValue;
112  testMap.clear();
113  assertEmptyMap();
114}
115
116// Test erase(iterator) method.
117TEST_F(StringMapTest, EraseIteratorTest) {
118  testMap[testKey] = testValue;
119  testMap.erase(testMap.begin());
120  assertEmptyMap();
121}
122
123// Test erase(value) method.
124TEST_F(StringMapTest, EraseValueTest) {
125  testMap[testKey] = testValue;
126  testMap.erase(testKey);
127  assertEmptyMap();
128}
129
130// Test inserting two values and erasing one.
131TEST_F(StringMapTest, InsertAndEraseTest) {
132  testMap[testKey] = testValue;
133  testMap["otherKey"] = 2;
134  testMap.erase("otherKey");
135  assertSingleItemMap();
136}
137
138TEST_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);
143
144  Map["eins"] = 1;
145  Map["zwei"] = 2;
146  Map["drei"] = 3;
147  Map.erase("drei");
148  Map.erase("eins");
149  Map["veir"] = 4;
150  Map["funf"] = 5;
151
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"));
158}
159
160// A more complex iteration test.
161TEST_F(StringMapTest, IterationTest) {
162  bool visited[100];
163
164  // Insert 100 numbers into the map
165  for (int i = 0; i < 100; ++i) {
166    std::stringstream ss;
167    ss << "key_" << i;
168    testMap[ss.str()] = i;
169    visited[i] = false;
170  }
171
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;
179  }
180
181  // Ensure every number was visited.
182  for (int i = 0; i < 100; ++i) {
183    ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited";
184  }
185}
186
187// Test StringMapEntry::Create() method.
188TEST_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);
194  free(entry);
195}
196
197// Test insert() method.
198TEST_F(StringMapTest, InsertTest) {
199  SCOPED_TRACE("InsertTest");
200  testMap.insert(
201      StringMap<uint32_t>::value_type::Create(
202          StringRef(testKeyFirst, testKeyLength),
203          testMap.getAllocator(), 1u));
204  assertSingleItemMap();
205}
206
207// Test insert(pair<K, V>) method
208TEST_F(StringMapTest, InsertPairTest) {
209  bool Inserted;
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);
218
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);
226}
227
228// Test insert(pair<K, V>) method when rehashing occurs
229TEST_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());
236
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);
242}
243
244// Create a non-default constructable value
245struct StringMapTestStruct {
246  StringMapTestStruct(int i) : i(i) {}
247  StringMapTestStruct() LLVM_DELETED_FUNCTION;
248  int i;
249};
250
251TEST_F(StringMapTest, NonDefaultConstructable) {
252  StringMap<StringMapTestStruct> t;
253  t.GetOrCreateValue("Test", StringMapTestStruct(123));
254  StringMap<StringMapTestStruct>::iterator iter = t.find("Test");
255  ASSERT_NE(iter, t.end());
256  ASSERT_EQ(iter->second.i, 123);
257}
258
259struct MoveOnly {
260  int i;
261  MoveOnly(int i) : i(i) {}
262  MoveOnly(MoveOnly &&RHS) : i(RHS.i) {}
263  MoveOnly &operator=(MoveOnly &&RHS) {
264    i = RHS.i;
265    return *this;
266  }
267
268private:
269  MoveOnly(const MoveOnly &) LLVM_DELETED_FUNCTION;
270  MoveOnly &operator=(const MoveOnly &) LLVM_DELETED_FUNCTION;
271};
272
273TEST_F(StringMapTest, MoveOnlyKey) {
274  StringMap<MoveOnly> t;
275  t.GetOrCreateValue("Test", MoveOnly(42));
276  StringRef Key = "Test";
277  StringMapEntry<MoveOnly>::Create(Key, MoveOnly(42))
278      ->Destroy();
279}
280
281TEST_F(StringMapTest, MoveConstruct) {
282  StringMap<int> A;
283  A.GetOrCreateValue("x", 42);
284  StringMap<int> B = std::move(A);
285  ASSERT_EQ(A.size(), 0u);
286  ASSERT_EQ(B.size(), 1u);
287  ASSERT_EQ(B["x"], 42);
288  ASSERT_EQ(B.count("y"), 0u);
289}
290
291TEST_F(StringMapTest, MoveAssignment) {
292  StringMap<int> A;
293  A["x"] = 42;
294  StringMap<int> B;
295  B["y"] = 117;
296  A = std::move(B);
297  ASSERT_EQ(A.size(), 1u);
298  ASSERT_EQ(B.size(), 0u);
299  ASSERT_EQ(A["y"], 117);
300  ASSERT_EQ(B.count("x"), 0u);
301}
302
303struct Countable {
304  int &InstanceCount;
305  int Number;
306  Countable(int Number, int &InstanceCount)
307      : InstanceCount(InstanceCount), Number(Number) {
308    ++InstanceCount;
309  }
310  Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) {
311    ++InstanceCount;
312    C.Number = -1;
313  }
314  Countable(const Countable &C)
315      : InstanceCount(C.InstanceCount), Number(C.Number) {
316    ++InstanceCount;
317  }
318  Countable &operator=(Countable C) {
319    Number = C.Number;
320    return *this;
321  }
322  ~Countable() { --InstanceCount; }
323};
324
325TEST_F(StringMapTest, MoveDtor) {
326  int InstanceCount = 0;
327  StringMap<Countable> A;
328  A.GetOrCreateValue("x", Countable(42, InstanceCount));
329  ASSERT_EQ(InstanceCount, 1);
330  auto I = A.find("x");
331  ASSERT_NE(I, A.end());
332  ASSERT_EQ(I->second.Number, 42);
333
334  StringMap<Countable> B;
335  B = std::move(A);
336  ASSERT_EQ(InstanceCount, 1);
337  ASSERT_TRUE(A.empty());
338  I = B.find("x");
339  ASSERT_NE(I, B.end());
340  ASSERT_EQ(I->second.Number, 42);
341
342  B = StringMap<Countable>();
343  ASSERT_EQ(InstanceCount, 0);
344  ASSERT_TRUE(B.empty());
345}
346
347} // end anonymous namespace
348