xref: /llvm-project/llvm/unittests/ADT/StringMapTest.cpp (revision 38bf13d02ce7dda0a9fc77c94457da0be8cf5c1b)
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>
14 using namespace llvm;
15 
16 namespace {
17 
18 // Test fixture
19 class StringMapTest : public testing::Test {
20 protected:
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 
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);
76 
77 // Empty map tests.
78 TEST_F(StringMapTest, EmptyMapTest) {
79   assertEmptyMap();
80 }
81 
82 // Constant map tests.
83 TEST_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.
104 TEST_F(StringMapTest, SingleEntryMapTest) {
105   testMap[testKey] = testValue;
106   assertSingleItemMap();
107 }
108 
109 // Test clear() method.
110 TEST_F(StringMapTest, ClearTest) {
111   testMap[testKey] = testValue;
112   testMap.clear();
113   assertEmptyMap();
114 }
115 
116 // Test erase(iterator) method.
117 TEST_F(StringMapTest, EraseIteratorTest) {
118   testMap[testKey] = testValue;
119   testMap.erase(testMap.begin());
120   assertEmptyMap();
121 }
122 
123 // Test erase(value) method.
124 TEST_F(StringMapTest, EraseValueTest) {
125   testMap[testKey] = testValue;
126   testMap.erase(testKey);
127   assertEmptyMap();
128 }
129 
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();
136 }
137 
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);
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 TEST_F(StringMapTest, CopyCtorTest) {
161   llvm::StringMap<int> Map;
162 
163   Map["eins"] = 1;
164   Map["zwei"] = 2;
165   Map["drei"] = 3;
166   Map.erase("drei");
167   Map.erase("eins");
168   Map["veir"] = 4;
169   Map["funf"] = 5;
170 
171   EXPECT_EQ(3u, Map.size());
172   EXPECT_EQ(0, Map.lookup("eins"));
173   EXPECT_EQ(2, Map.lookup("zwei"));
174   EXPECT_EQ(0, Map.lookup("drei"));
175   EXPECT_EQ(4, Map.lookup("veir"));
176   EXPECT_EQ(5, Map.lookup("funf"));
177 
178   llvm::StringMap<int> Map2(Map);
179   EXPECT_EQ(3u, Map2.size());
180   EXPECT_EQ(0, Map2.lookup("eins"));
181   EXPECT_EQ(2, Map2.lookup("zwei"));
182   EXPECT_EQ(0, Map2.lookup("drei"));
183   EXPECT_EQ(4, Map2.lookup("veir"));
184   EXPECT_EQ(5, Map2.lookup("funf"));
185 }
186 
187 // A more complex iteration test.
188 TEST_F(StringMapTest, IterationTest) {
189   bool visited[100];
190 
191   // Insert 100 numbers into the map
192   for (int i = 0; i < 100; ++i) {
193     std::stringstream ss;
194     ss << "key_" << i;
195     testMap[ss.str()] = i;
196     visited[i] = false;
197   }
198 
199   // Iterate over all numbers and mark each one found.
200   for (StringMap<uint32_t>::iterator it = testMap.begin();
201       it != testMap.end(); ++it) {
202     std::stringstream ss;
203     ss << "key_" << it->second;
204     ASSERT_STREQ(ss.str().c_str(), it->first().data());
205     visited[it->second] = true;
206   }
207 
208   // Ensure every number was visited.
209   for (int i = 0; i < 100; ++i) {
210     ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited";
211   }
212 }
213 
214 // Test StringMapEntry::Create() method.
215 TEST_F(StringMapTest, StringMapEntryTest) {
216   StringMap<uint32_t>::value_type* entry =
217       StringMap<uint32_t>::value_type::Create(
218           StringRef(testKeyFirst, testKeyLength), 1u);
219   EXPECT_STREQ(testKey, entry->first().data());
220   EXPECT_EQ(1u, entry->second);
221   free(entry);
222 }
223 
224 // Test insert() method.
225 TEST_F(StringMapTest, InsertTest) {
226   SCOPED_TRACE("InsertTest");
227   testMap.insert(
228       StringMap<uint32_t>::value_type::Create(
229           StringRef(testKeyFirst, testKeyLength),
230           testMap.getAllocator(), 1u));
231   assertSingleItemMap();
232 }
233 
234 // Test insert(pair<K, V>) method
235 TEST_F(StringMapTest, InsertPairTest) {
236   bool Inserted;
237   StringMap<uint32_t>::iterator NewIt;
238   std::tie(NewIt, Inserted) =
239       testMap.insert(std::make_pair(testKeyFirst, testValue));
240   EXPECT_EQ(1u, testMap.size());
241   EXPECT_EQ(testValue, testMap[testKeyFirst]);
242   EXPECT_EQ(testKeyFirst, NewIt->first());
243   EXPECT_EQ(testValue, NewIt->second);
244   EXPECT_TRUE(Inserted);
245 
246   StringMap<uint32_t>::iterator ExistingIt;
247   std::tie(ExistingIt, Inserted) =
248       testMap.insert(std::make_pair(testKeyFirst, testValue + 1));
249   EXPECT_EQ(1u, testMap.size());
250   EXPECT_EQ(testValue, testMap[testKeyFirst]);
251   EXPECT_FALSE(Inserted);
252   EXPECT_EQ(NewIt, ExistingIt);
253 }
254 
255 // Test insert(pair<K, V>) method when rehashing occurs
256 TEST_F(StringMapTest, InsertRehashingPairTest) {
257   // Check that the correct iterator is returned when the inserted element is
258   // moved to a different bucket during internal rehashing. This depends on
259   // the particular key, and the implementation of StringMap and HashString.
260   // Changes to those might result in this test not actually checking that.
261   StringMap<uint32_t> t(0);
262   EXPECT_EQ(0u, t.getNumBuckets());
263 
264   StringMap<uint32_t>::iterator It =
265     t.insert(std::make_pair("abcdef", 42)).first;
266   EXPECT_EQ(16u, t.getNumBuckets());
267   EXPECT_EQ("abcdef", It->first());
268   EXPECT_EQ(42u, It->second);
269 }
270 
271 // Create a non-default constructable value
272 struct StringMapTestStruct {
273   StringMapTestStruct(int i) : i(i) {}
274   StringMapTestStruct() = delete;
275   int i;
276 };
277 
278 TEST_F(StringMapTest, NonDefaultConstructable) {
279   StringMap<StringMapTestStruct> t;
280   t.insert(std::make_pair("Test", StringMapTestStruct(123)));
281   StringMap<StringMapTestStruct>::iterator iter = t.find("Test");
282   ASSERT_NE(iter, t.end());
283   ASSERT_EQ(iter->second.i, 123);
284 }
285 
286 struct Immovable {
287   Immovable() {}
288   Immovable(Immovable&&) = delete; // will disable the other special members
289 };
290 
291 struct MoveOnly {
292   int i;
293   MoveOnly(int i) : i(i) {}
294   MoveOnly(const Immovable&) : i(0) {}
295   MoveOnly(MoveOnly &&RHS) : i(RHS.i) {}
296   MoveOnly &operator=(MoveOnly &&RHS) {
297     i = RHS.i;
298     return *this;
299   }
300 
301 private:
302   MoveOnly(const MoveOnly &) = delete;
303   MoveOnly &operator=(const MoveOnly &) = delete;
304 };
305 
306 TEST_F(StringMapTest, MoveOnly) {
307   StringMap<MoveOnly> t;
308   t.insert(std::make_pair("Test", MoveOnly(42)));
309   StringRef Key = "Test";
310   StringMapEntry<MoveOnly>::Create(Key, MoveOnly(42))
311       ->Destroy();
312 }
313 
314 TEST_F(StringMapTest, CtorArg) {
315   StringRef Key = "Test";
316   StringMapEntry<MoveOnly>::Create(Key, Immovable())
317       ->Destroy();
318 }
319 
320 TEST_F(StringMapTest, MoveConstruct) {
321   StringMap<int> A;
322   A["x"] = 42;
323   StringMap<int> B = std::move(A);
324   ASSERT_EQ(A.size(), 0u);
325   ASSERT_EQ(B.size(), 1u);
326   ASSERT_EQ(B["x"], 42);
327   ASSERT_EQ(B.count("y"), 0u);
328 }
329 
330 TEST_F(StringMapTest, MoveAssignment) {
331   StringMap<int> A;
332   A["x"] = 42;
333   StringMap<int> B;
334   B["y"] = 117;
335   A = std::move(B);
336   ASSERT_EQ(A.size(), 1u);
337   ASSERT_EQ(B.size(), 0u);
338   ASSERT_EQ(A["y"], 117);
339   ASSERT_EQ(B.count("x"), 0u);
340 }
341 
342 struct Countable {
343   int &InstanceCount;
344   int Number;
345   Countable(int Number, int &InstanceCount)
346       : InstanceCount(InstanceCount), Number(Number) {
347     ++InstanceCount;
348   }
349   Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) {
350     ++InstanceCount;
351     C.Number = -1;
352   }
353   Countable(const Countable &C)
354       : InstanceCount(C.InstanceCount), Number(C.Number) {
355     ++InstanceCount;
356   }
357   Countable &operator=(Countable C) {
358     Number = C.Number;
359     return *this;
360   }
361   ~Countable() { --InstanceCount; }
362 };
363 
364 TEST_F(StringMapTest, MoveDtor) {
365   int InstanceCount = 0;
366   StringMap<Countable> A;
367   A.insert(std::make_pair("x", Countable(42, InstanceCount)));
368   ASSERT_EQ(InstanceCount, 1);
369   auto I = A.find("x");
370   ASSERT_NE(I, A.end());
371   ASSERT_EQ(I->second.Number, 42);
372 
373   StringMap<Countable> B;
374   B = std::move(A);
375   ASSERT_EQ(InstanceCount, 1);
376   ASSERT_TRUE(A.empty());
377   I = B.find("x");
378   ASSERT_NE(I, B.end());
379   ASSERT_EQ(I->second.Number, 42);
380 
381   B = StringMap<Countable>();
382   ASSERT_EQ(InstanceCount, 0);
383   ASSERT_TRUE(B.empty());
384 }
385 
386 namespace {
387 // Simple class that counts how many moves and copy happens when growing a map
388 struct CountCtorCopyAndMove {
389   static unsigned Ctor;
390   static unsigned Move;
391   static unsigned Copy;
392   int Data = 0;
393   CountCtorCopyAndMove(int Data) : Data(Data) { Ctor++; }
394   CountCtorCopyAndMove() { Ctor++; }
395 
396   CountCtorCopyAndMove(const CountCtorCopyAndMove &) { Copy++; }
397   CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &) {
398     Copy++;
399     return *this;
400   }
401   CountCtorCopyAndMove(CountCtorCopyAndMove &&) { Move++; }
402   CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &&) {
403     Move++;
404     return *this;
405   }
406 };
407 unsigned CountCtorCopyAndMove::Copy = 0;
408 unsigned CountCtorCopyAndMove::Move = 0;
409 unsigned CountCtorCopyAndMove::Ctor = 0;
410 
411 } // anonymous namespace
412 
413 // Make sure creating the map with an initial size of N actually gives us enough
414 // buckets to insert N items without increasing allocation size.
415 TEST(StringMapCustomTest, InitialSizeTest) {
416   // 1 is an "edge value", 32 is an arbitrary power of two, and 67 is an
417   // arbitrary prime, picked without any good reason.
418   for (auto Size : {1, 32, 67}) {
419     StringMap<CountCtorCopyAndMove> Map(Size);
420     auto NumBuckets = Map.getNumBuckets();
421     CountCtorCopyAndMove::Move = 0;
422     CountCtorCopyAndMove::Copy = 0;
423     for (int i = 0; i < Size; ++i)
424       Map.insert(std::pair<std::string, CountCtorCopyAndMove>(
425           std::piecewise_construct, std::forward_as_tuple(Twine(i).str()),
426           std::forward_as_tuple(i)));
427     // After the inital move, the map will move the Elts in the Entry.
428     EXPECT_EQ((unsigned)Size * 2, CountCtorCopyAndMove::Move);
429     // We copy once the pair from the Elts vector
430     EXPECT_EQ(0u, CountCtorCopyAndMove::Copy);
431     // Check that the map didn't grow
432     EXPECT_EQ(Map.getNumBuckets(), NumBuckets);
433   }
434 }
435 
436 TEST(StringMapCustomTest, BracketOperatorCtor) {
437   StringMap<CountCtorCopyAndMove> Map;
438   CountCtorCopyAndMove::Ctor = 0;
439   Map["abcd"];
440   EXPECT_EQ(1u, CountCtorCopyAndMove::Ctor);
441   // Test that operator[] does not create a value when it is already in the map
442   CountCtorCopyAndMove::Ctor = 0;
443   Map["abcd"];
444   EXPECT_EQ(0u, CountCtorCopyAndMove::Ctor);
445 }
446 
447 namespace {
448 struct NonMoveableNonCopyableType {
449   int Data = 0;
450   NonMoveableNonCopyableType() = default;
451   NonMoveableNonCopyableType(int Data) : Data(Data) {}
452   NonMoveableNonCopyableType(const NonMoveableNonCopyableType &) = delete;
453   NonMoveableNonCopyableType(NonMoveableNonCopyableType &&) = delete;
454 };
455 }
456 
457 // Test that we can "emplace" an element in the map without involving map/move
458 TEST(StringMapCustomTest, EmplaceTest) {
459   StringMap<NonMoveableNonCopyableType> Map;
460   Map.emplace_second("abcd", 42);
461   EXPECT_EQ(1u, Map.count("abcd"));
462   EXPECT_EQ(42, Map["abcd"].Data);
463 }
464 
465 } // end anonymous namespace
466