1 | //===- llvm/unittest/ADT/StringMapMap.cpp - StringMap unit tests ----------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #include "llvm/ADT/StringMap.h" |
10 | #include "llvm/ADT/STLExtras.h" |
11 | #include "llvm/ADT/Twine.h" |
12 | #include "llvm/Support/DataTypes.h" |
13 | #include "gtest/gtest.h" |
14 | #include <limits> |
15 | #include <tuple> |
16 | using namespace llvm; |
17 | |
18 | namespace { |
19 | |
20 | static_assert(sizeof(StringMap<uint32_t>) < |
21 | sizeof(StringMap<uint32_t, MallocAllocator &>), |
22 | "Ensure empty base optimization happens with default allocator" ); |
23 | |
24 | // Test fixture |
25 | class StringMapTest : public testing::Test { |
26 | protected: |
27 | StringMap<uint32_t> testMap; |
28 | |
29 | static const char testKey[]; |
30 | static const uint32_t testValue; |
31 | static const char *testKeyFirst; |
32 | static size_t testKeyLength; |
33 | static const std::string testKeyStr; |
34 | |
35 | void assertEmptyMap() { |
36 | // Size tests |
37 | EXPECT_EQ(0u, testMap.size()); |
38 | EXPECT_TRUE(testMap.empty()); |
39 | |
40 | // Iterator tests |
41 | EXPECT_TRUE(testMap.begin() == testMap.end()); |
42 | |
43 | // Lookup tests |
44 | EXPECT_FALSE(testMap.contains(testKey)); |
45 | EXPECT_EQ(0u, testMap.count(testKey)); |
46 | EXPECT_EQ(0u, testMap.count(StringRef(testKeyFirst, testKeyLength))); |
47 | EXPECT_EQ(0u, testMap.count(testKeyStr)); |
48 | EXPECT_TRUE(testMap.find(testKey) == testMap.end()); |
49 | EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == |
50 | testMap.end()); |
51 | EXPECT_TRUE(testMap.find(testKeyStr) == testMap.end()); |
52 | } |
53 | |
54 | void assertSingleItemMap() { |
55 | // Size tests |
56 | EXPECT_EQ(1u, testMap.size()); |
57 | EXPECT_FALSE(testMap.begin() == testMap.end()); |
58 | EXPECT_FALSE(testMap.empty()); |
59 | |
60 | // Iterator tests |
61 | StringMap<uint32_t>::iterator it = testMap.begin(); |
62 | EXPECT_STREQ(testKey, it->first().data()); |
63 | EXPECT_EQ(testValue, it->second); |
64 | ++it; |
65 | EXPECT_TRUE(it == testMap.end()); |
66 | |
67 | // Lookup tests |
68 | EXPECT_TRUE(testMap.contains(testKey)); |
69 | EXPECT_EQ(1u, testMap.count(testKey)); |
70 | EXPECT_EQ(1u, testMap.count(StringRef(testKeyFirst, testKeyLength))); |
71 | EXPECT_EQ(1u, testMap.count(testKeyStr)); |
72 | EXPECT_TRUE(testMap.find(testKey) == testMap.begin()); |
73 | EXPECT_TRUE(testMap.find(StringRef(testKeyFirst, testKeyLength)) == |
74 | testMap.begin()); |
75 | EXPECT_TRUE(testMap.find(testKeyStr) == testMap.begin()); |
76 | } |
77 | }; |
78 | |
79 | const char StringMapTest::testKey[] = "key" ; |
80 | const uint32_t StringMapTest::testValue = 1u; |
81 | const char *StringMapTest::testKeyFirst = testKey; |
82 | size_t StringMapTest::testKeyLength = sizeof(testKey) - 1; |
83 | const std::string StringMapTest::testKeyStr(testKey); |
84 | |
85 | struct CountCopyAndMove { |
86 | CountCopyAndMove() = default; |
87 | CountCopyAndMove(const CountCopyAndMove &) { copy = 1; } |
88 | CountCopyAndMove(CountCopyAndMove &&) { move = 1; } |
89 | void operator=(const CountCopyAndMove &) { ++copy; } |
90 | void operator=(CountCopyAndMove &&) { ++move; } |
91 | int copy = 0; |
92 | int move = 0; |
93 | }; |
94 | |
95 | // Empty map tests. |
96 | TEST_F(StringMapTest, EmptyMapTest) { assertEmptyMap(); } |
97 | |
98 | // Constant map tests. |
99 | TEST_F(StringMapTest, ConstEmptyMapTest) { |
100 | const StringMap<uint32_t> &constTestMap = testMap; |
101 | |
102 | // Size tests |
103 | EXPECT_EQ(0u, constTestMap.size()); |
104 | EXPECT_TRUE(constTestMap.empty()); |
105 | |
106 | // Iterator tests |
107 | EXPECT_TRUE(constTestMap.begin() == constTestMap.end()); |
108 | |
109 | // Lookup tests |
110 | EXPECT_EQ(0u, constTestMap.count(testKey)); |
111 | EXPECT_EQ(0u, constTestMap.count(StringRef(testKeyFirst, testKeyLength))); |
112 | EXPECT_EQ(0u, constTestMap.count(testKeyStr)); |
113 | EXPECT_TRUE(constTestMap.find(testKey) == constTestMap.end()); |
114 | EXPECT_TRUE(constTestMap.find(StringRef(testKeyFirst, testKeyLength)) == |
115 | constTestMap.end()); |
116 | EXPECT_TRUE(constTestMap.find(testKeyStr) == constTestMap.end()); |
117 | } |
118 | |
119 | // initializer_list ctor test; also implicitly tests initializer_list and |
120 | // iterator overloads of insert(). |
121 | TEST_F(StringMapTest, InitializerListCtor) { |
122 | testMap = StringMap<uint32_t>({{"key" , 1}}); |
123 | assertSingleItemMap(); |
124 | } |
125 | |
126 | // A map with a single entry. |
127 | TEST_F(StringMapTest, SingleEntryMapTest) { |
128 | testMap[testKey] = testValue; |
129 | assertSingleItemMap(); |
130 | } |
131 | |
132 | // Test clear() method. |
133 | TEST_F(StringMapTest, ClearTest) { |
134 | testMap[testKey] = testValue; |
135 | testMap.clear(); |
136 | assertEmptyMap(); |
137 | } |
138 | |
139 | // Test erase(iterator) method. |
140 | TEST_F(StringMapTest, EraseIteratorTest) { |
141 | testMap[testKey] = testValue; |
142 | testMap.erase(I: testMap.begin()); |
143 | assertEmptyMap(); |
144 | } |
145 | |
146 | // Test erase(value) method. |
147 | TEST_F(StringMapTest, EraseValueTest) { |
148 | testMap[testKey] = testValue; |
149 | testMap.erase(Key: testKey); |
150 | assertEmptyMap(); |
151 | } |
152 | |
153 | // Test inserting two values and erasing one. |
154 | TEST_F(StringMapTest, InsertAndEraseTest) { |
155 | testMap[testKey] = testValue; |
156 | testMap["otherKey" ] = 2; |
157 | testMap.erase(Key: "otherKey" ); |
158 | assertSingleItemMap(); |
159 | } |
160 | |
161 | TEST_F(StringMapTest, SmallFullMapTest) { |
162 | // StringMap has a tricky corner case when the map is small (<8 buckets) and |
163 | // it fills up through a balanced pattern of inserts and erases. This can |
164 | // lead to inf-loops in some cases (PR13148) so we test it explicitly here. |
165 | llvm::StringMap<int> Map(2); |
166 | |
167 | Map["eins" ] = 1; |
168 | Map["zwei" ] = 2; |
169 | Map["drei" ] = 3; |
170 | Map.erase(Key: "drei" ); |
171 | Map.erase(Key: "eins" ); |
172 | Map["veir" ] = 4; |
173 | Map["funf" ] = 5; |
174 | |
175 | EXPECT_EQ(3u, Map.size()); |
176 | EXPECT_EQ(0, Map.lookup("eins" )); |
177 | EXPECT_EQ(2, Map.lookup("zwei" )); |
178 | EXPECT_EQ(0, Map.lookup("drei" )); |
179 | EXPECT_EQ(4, Map.lookup("veir" )); |
180 | EXPECT_EQ(5, Map.lookup("funf" )); |
181 | } |
182 | |
183 | TEST_F(StringMapTest, CopyCtorTest) { |
184 | llvm::StringMap<int> Map; |
185 | |
186 | Map["eins" ] = 1; |
187 | Map["zwei" ] = 2; |
188 | Map["drei" ] = 3; |
189 | Map.erase(Key: "drei" ); |
190 | Map.erase(Key: "eins" ); |
191 | Map["veir" ] = 4; |
192 | Map["funf" ] = 5; |
193 | |
194 | EXPECT_EQ(3u, Map.size()); |
195 | EXPECT_EQ(0, Map.lookup("eins" )); |
196 | EXPECT_EQ(2, Map.lookup("zwei" )); |
197 | EXPECT_EQ(0, Map.lookup("drei" )); |
198 | EXPECT_EQ(4, Map.lookup("veir" )); |
199 | EXPECT_EQ(5, Map.lookup("funf" )); |
200 | |
201 | llvm::StringMap<int> Map2(Map); |
202 | EXPECT_EQ(3u, Map2.size()); |
203 | EXPECT_EQ(0, Map2.lookup("eins" )); |
204 | EXPECT_EQ(2, Map2.lookup("zwei" )); |
205 | EXPECT_EQ(0, Map2.lookup("drei" )); |
206 | EXPECT_EQ(4, Map2.lookup("veir" )); |
207 | EXPECT_EQ(5, Map2.lookup("funf" )); |
208 | } |
209 | |
210 | TEST_F(StringMapTest, AtTest) { |
211 | llvm::StringMap<int> Map; |
212 | |
213 | // keys both found and not found on non-empty map |
214 | Map["a" ] = 1; |
215 | Map["b" ] = 2; |
216 | Map["c" ] = 3; |
217 | EXPECT_EQ(1, Map.at("a" )); |
218 | EXPECT_EQ(2, Map.at("b" )); |
219 | EXPECT_EQ(3, Map.at("c" )); |
220 | } |
221 | |
222 | // A more complex iteration test. |
223 | TEST_F(StringMapTest, IterationTest) { |
224 | bool visited[100]; |
225 | |
226 | // Insert 100 numbers into the map |
227 | for (int i = 0; i < 100; ++i) { |
228 | std::stringstream ss; |
229 | ss << "key_" << i; |
230 | testMap[ss.str()] = i; |
231 | visited[i] = false; |
232 | } |
233 | |
234 | // Iterate over all numbers and mark each one found. |
235 | for (StringMap<uint32_t>::iterator it = testMap.begin(); it != testMap.end(); |
236 | ++it) { |
237 | std::stringstream ss; |
238 | ss << "key_" << it->second; |
239 | ASSERT_STREQ(ss.str().c_str(), it->first().data()); |
240 | visited[it->second] = true; |
241 | } |
242 | |
243 | // Ensure every number was visited. |
244 | for (int i = 0; i < 100; ++i) { |
245 | ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited" ; |
246 | } |
247 | } |
248 | |
249 | // Test StringMapEntry::Create() method. |
250 | TEST_F(StringMapTest, StringMapEntryTest) { |
251 | MallocAllocator Allocator; |
252 | StringMap<uint32_t>::value_type *entry = |
253 | StringMap<uint32_t>::value_type::create( |
254 | key: StringRef(testKeyFirst, testKeyLength), allocator&: Allocator, initVals: 1u); |
255 | EXPECT_STREQ(testKey, entry->first().data()); |
256 | EXPECT_EQ(1u, entry->second); |
257 | entry->Destroy(allocator&: Allocator); |
258 | } |
259 | |
260 | // Test insert() method. |
261 | TEST_F(StringMapTest, InsertTest) { |
262 | SCOPED_TRACE("InsertTest" ); |
263 | testMap.insert(KeyValue: StringMap<uint32_t>::value_type::create( |
264 | key: StringRef(testKeyFirst, testKeyLength), allocator&: testMap.getAllocator(), initVals: 1u)); |
265 | assertSingleItemMap(); |
266 | } |
267 | |
268 | // Test insert(pair<K, V>) method |
269 | TEST_F(StringMapTest, InsertPairTest) { |
270 | bool Inserted; |
271 | StringMap<uint32_t>::iterator NewIt; |
272 | std::tie(args&: NewIt, args&: Inserted) = |
273 | testMap.insert(KV: std::make_pair(x&: testKeyFirst, y: testValue)); |
274 | EXPECT_EQ(1u, testMap.size()); |
275 | EXPECT_EQ(testValue, testMap[testKeyFirst]); |
276 | EXPECT_EQ(testKeyFirst, NewIt->first()); |
277 | EXPECT_EQ(testValue, NewIt->second); |
278 | EXPECT_TRUE(Inserted); |
279 | |
280 | StringMap<uint32_t>::iterator ExistingIt; |
281 | std::tie(args&: ExistingIt, args&: Inserted) = |
282 | testMap.insert(KV: std::make_pair(x&: testKeyFirst, y: testValue + 1)); |
283 | EXPECT_EQ(1u, testMap.size()); |
284 | EXPECT_EQ(testValue, testMap[testKeyFirst]); |
285 | EXPECT_FALSE(Inserted); |
286 | EXPECT_EQ(NewIt, ExistingIt); |
287 | } |
288 | |
289 | // Test insert(pair<K, V>) method when rehashing occurs |
290 | TEST_F(StringMapTest, InsertRehashingPairTest) { |
291 | // Check that the correct iterator is returned when the inserted element is |
292 | // moved to a different bucket during internal rehashing. This depends on |
293 | // the particular key, and the implementation of StringMap and HashString. |
294 | // Changes to those might result in this test not actually checking that. |
295 | StringMap<uint32_t> t(0); |
296 | EXPECT_EQ(0u, t.getNumBuckets()); |
297 | |
298 | StringMap<uint32_t>::iterator It = |
299 | t.insert(KV: std::make_pair(x: "abcdef" , y: 42)).first; |
300 | EXPECT_EQ(16u, t.getNumBuckets()); |
301 | EXPECT_EQ("abcdef" , It->first()); |
302 | EXPECT_EQ(42u, It->second); |
303 | } |
304 | |
305 | TEST_F(StringMapTest, InsertOrAssignTest) { |
306 | struct A : CountCopyAndMove { |
307 | A(int v) : v(v) {} |
308 | int v; |
309 | }; |
310 | StringMap<A> t(0); |
311 | |
312 | auto try1 = t.insert_or_assign(Key: "A" , Val: A(1)); |
313 | EXPECT_TRUE(try1.second); |
314 | EXPECT_EQ(1, try1.first->second.v); |
315 | EXPECT_EQ(1, try1.first->second.move); |
316 | |
317 | auto try2 = t.insert_or_assign(Key: "A" , Val: A(2)); |
318 | EXPECT_FALSE(try2.second); |
319 | EXPECT_EQ(2, try2.first->second.v); |
320 | EXPECT_EQ(2, try1.first->second.move); |
321 | |
322 | EXPECT_EQ(try1.first, try2.first); |
323 | EXPECT_EQ(0, try1.first->second.copy); |
324 | } |
325 | |
326 | TEST_F(StringMapTest, IterMapKeysVector) { |
327 | StringMap<int> Map; |
328 | Map["A" ] = 1; |
329 | Map["B" ] = 2; |
330 | Map["C" ] = 3; |
331 | Map["D" ] = 3; |
332 | |
333 | std::vector<StringRef> Keys{Map.keys().begin(), Map.keys().end()}; |
334 | llvm::sort(C&: Keys); |
335 | |
336 | std::vector<StringRef> Expected{{"A" , "B" , "C" , "D" }}; |
337 | EXPECT_EQ(Expected, Keys); |
338 | } |
339 | |
340 | TEST_F(StringMapTest, IterMapKeysSmallVector) { |
341 | StringMap<int> Map; |
342 | Map["A" ] = 1; |
343 | Map["B" ] = 2; |
344 | Map["C" ] = 3; |
345 | Map["D" ] = 3; |
346 | |
347 | auto Keys = to_vector<4>(Range: Map.keys()); |
348 | llvm::sort(C&: Keys); |
349 | |
350 | SmallVector<StringRef, 4> Expected = {"A" , "B" , "C" , "D" }; |
351 | EXPECT_EQ(Expected, Keys); |
352 | } |
353 | |
354 | // Create a non-default constructable value |
355 | struct StringMapTestStruct { |
356 | StringMapTestStruct(int i) : i(i) {} |
357 | StringMapTestStruct() = delete; |
358 | int i; |
359 | }; |
360 | |
361 | TEST_F(StringMapTest, NonDefaultConstructable) { |
362 | StringMap<StringMapTestStruct> t; |
363 | t.insert(KV: std::make_pair(x: "Test" , y: StringMapTestStruct(123))); |
364 | StringMap<StringMapTestStruct>::iterator iter = t.find(Key: "Test" ); |
365 | ASSERT_NE(iter, t.end()); |
366 | ASSERT_EQ(iter->second.i, 123); |
367 | } |
368 | |
369 | struct Immovable { |
370 | Immovable() {} |
371 | Immovable(Immovable &&) = delete; // will disable the other special members |
372 | }; |
373 | |
374 | struct MoveOnly { |
375 | int i; |
376 | MoveOnly(int i) : i(i) {} |
377 | MoveOnly(const Immovable &) : i(0) {} |
378 | MoveOnly(MoveOnly &&RHS) : i(RHS.i) {} |
379 | MoveOnly &operator=(MoveOnly &&RHS) { |
380 | i = RHS.i; |
381 | return *this; |
382 | } |
383 | |
384 | private: |
385 | MoveOnly(const MoveOnly &) = delete; |
386 | MoveOnly &operator=(const MoveOnly &) = delete; |
387 | }; |
388 | |
389 | TEST_F(StringMapTest, MoveOnly) { |
390 | StringMap<MoveOnly> t; |
391 | t.insert(KV: std::make_pair(x: "Test" , y: MoveOnly(42))); |
392 | StringRef Key = "Test" ; |
393 | StringMapEntry<MoveOnly>::create(key: Key, allocator&: t.getAllocator(), initVals: MoveOnly(42)) |
394 | ->Destroy(allocator&: t.getAllocator()); |
395 | } |
396 | |
397 | TEST_F(StringMapTest, CtorArg) { |
398 | StringRef Key = "Test" ; |
399 | MallocAllocator Allocator; |
400 | StringMapEntry<MoveOnly>::create(key: Key, allocator&: Allocator, initVals: Immovable()) |
401 | ->Destroy(allocator&: Allocator); |
402 | } |
403 | |
404 | TEST_F(StringMapTest, MoveConstruct) { |
405 | StringMap<int> A; |
406 | A["x" ] = 42; |
407 | StringMap<int> B = std::move(A); |
408 | ASSERT_EQ(A.size(), 0u); |
409 | ASSERT_EQ(B.size(), 1u); |
410 | ASSERT_EQ(B["x" ], 42); |
411 | ASSERT_EQ(B.count("y" ), 0u); |
412 | } |
413 | |
414 | TEST_F(StringMapTest, MoveAssignment) { |
415 | StringMap<int> A; |
416 | A["x" ] = 42; |
417 | StringMap<int> B; |
418 | B["y" ] = 117; |
419 | A = std::move(B); |
420 | ASSERT_EQ(A.size(), 1u); |
421 | ASSERT_EQ(B.size(), 0u); |
422 | ASSERT_EQ(A["y" ], 117); |
423 | ASSERT_EQ(B.count("x" ), 0u); |
424 | } |
425 | |
426 | TEST_F(StringMapTest, EqualEmpty) { |
427 | StringMap<int> A; |
428 | StringMap<int> B; |
429 | ASSERT_TRUE(A == B); |
430 | ASSERT_FALSE(A != B); |
431 | ASSERT_TRUE(A == A); // self check |
432 | } |
433 | |
434 | TEST_F(StringMapTest, EqualWithValues) { |
435 | StringMap<int> A; |
436 | A["A" ] = 1; |
437 | A["B" ] = 2; |
438 | A["C" ] = 3; |
439 | A["D" ] = 3; |
440 | |
441 | StringMap<int> B; |
442 | B["A" ] = 1; |
443 | B["B" ] = 2; |
444 | B["C" ] = 3; |
445 | B["D" ] = 3; |
446 | |
447 | ASSERT_TRUE(A == B); |
448 | ASSERT_TRUE(B == A); |
449 | ASSERT_FALSE(A != B); |
450 | ASSERT_FALSE(B != A); |
451 | ASSERT_TRUE(A == A); // self check |
452 | } |
453 | |
454 | TEST_F(StringMapTest, NotEqualMissingKeys) { |
455 | StringMap<int> A; |
456 | A["A" ] = 1; |
457 | A["B" ] = 2; |
458 | |
459 | StringMap<int> B; |
460 | B["A" ] = 1; |
461 | B["B" ] = 2; |
462 | B["C" ] = 3; |
463 | B["D" ] = 3; |
464 | |
465 | ASSERT_FALSE(A == B); |
466 | ASSERT_FALSE(B == A); |
467 | ASSERT_TRUE(A != B); |
468 | ASSERT_TRUE(B != A); |
469 | } |
470 | |
471 | TEST_F(StringMapTest, NotEqualWithDifferentValues) { |
472 | StringMap<int> A; |
473 | A["A" ] = 1; |
474 | A["B" ] = 2; |
475 | A["C" ] = 100; |
476 | A["D" ] = 3; |
477 | |
478 | StringMap<int> B; |
479 | B["A" ] = 1; |
480 | B["B" ] = 2; |
481 | B["C" ] = 3; |
482 | B["D" ] = 3; |
483 | |
484 | ASSERT_FALSE(A == B); |
485 | ASSERT_FALSE(B == A); |
486 | ASSERT_TRUE(A != B); |
487 | ASSERT_TRUE(B != A); |
488 | } |
489 | |
490 | TEST_F(StringMapTest, PrecomputedHash) { |
491 | StringMap<int> A; |
492 | StringRef Key = "foo" ; |
493 | int Value = 42; |
494 | uint64_t Hash = StringMap<int>::hash(Key); |
495 | A.insert(KV: {"foo" , Value}, FullHashValue: Hash); |
496 | auto I = A.find(Key, FullHashValue: Hash); |
497 | ASSERT_NE(I, A.end()); |
498 | ASSERT_EQ(I->second, Value); |
499 | } |
500 | |
501 | struct Countable { |
502 | int &InstanceCount; |
503 | int Number; |
504 | Countable(int Number, int &InstanceCount) |
505 | : InstanceCount(InstanceCount), Number(Number) { |
506 | ++InstanceCount; |
507 | } |
508 | Countable(Countable &&C) : InstanceCount(C.InstanceCount), Number(C.Number) { |
509 | ++InstanceCount; |
510 | C.Number = -1; |
511 | } |
512 | Countable(const Countable &C) |
513 | : InstanceCount(C.InstanceCount), Number(C.Number) { |
514 | ++InstanceCount; |
515 | } |
516 | Countable &operator=(Countable C) { |
517 | Number = C.Number; |
518 | return *this; |
519 | } |
520 | ~Countable() { --InstanceCount; } |
521 | }; |
522 | |
523 | TEST_F(StringMapTest, MoveDtor) { |
524 | int InstanceCount = 0; |
525 | StringMap<Countable> A; |
526 | A.insert(KV: std::make_pair(x: "x" , y: Countable(42, InstanceCount))); |
527 | ASSERT_EQ(InstanceCount, 1); |
528 | auto I = A.find(Key: "x" ); |
529 | ASSERT_NE(I, A.end()); |
530 | ASSERT_EQ(I->second.Number, 42); |
531 | |
532 | StringMap<Countable> B; |
533 | B = std::move(A); |
534 | ASSERT_EQ(InstanceCount, 1); |
535 | ASSERT_TRUE(A.empty()); |
536 | I = B.find(Key: "x" ); |
537 | ASSERT_NE(I, B.end()); |
538 | ASSERT_EQ(I->second.Number, 42); |
539 | |
540 | B = StringMap<Countable>(); |
541 | ASSERT_EQ(InstanceCount, 0); |
542 | ASSERT_TRUE(B.empty()); |
543 | } |
544 | |
545 | TEST_F(StringMapTest, StructuredBindings) { |
546 | StringMap<int> A; |
547 | A["a" ] = 42; |
548 | |
549 | for (auto &[Key, Value] : A) { |
550 | EXPECT_EQ("a" , Key); |
551 | EXPECT_EQ(42, Value); |
552 | } |
553 | } |
554 | |
555 | namespace { |
556 | // Simple class that counts how many moves and copy happens when growing a map |
557 | struct CountCtorCopyAndMove { |
558 | static unsigned Ctor; |
559 | static unsigned Move; |
560 | static unsigned Copy; |
561 | int Data = 0; |
562 | CountCtorCopyAndMove(int Data) : Data(Data) { Ctor++; } |
563 | CountCtorCopyAndMove() { Ctor++; } |
564 | |
565 | CountCtorCopyAndMove(const CountCtorCopyAndMove &) { Copy++; } |
566 | CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &) { |
567 | Copy++; |
568 | return *this; |
569 | } |
570 | CountCtorCopyAndMove(CountCtorCopyAndMove &&) { Move++; } |
571 | CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &&) { |
572 | Move++; |
573 | return *this; |
574 | } |
575 | }; |
576 | unsigned CountCtorCopyAndMove::Copy = 0; |
577 | unsigned CountCtorCopyAndMove::Move = 0; |
578 | unsigned CountCtorCopyAndMove::Ctor = 0; |
579 | |
580 | } // anonymous namespace |
581 | |
582 | // Make sure creating the map with an initial size of N actually gives us enough |
583 | // buckets to insert N items without increasing allocation size. |
584 | TEST(StringMapCustomTest, InitialSizeTest) { |
585 | // 1 is an "edge value", 32 is an arbitrary power of two, and 67 is an |
586 | // arbitrary prime, picked without any good reason. |
587 | for (auto Size : {1, 32, 67}) { |
588 | StringMap<CountCtorCopyAndMove> Map(Size); |
589 | auto NumBuckets = Map.getNumBuckets(); |
590 | CountCtorCopyAndMove::Move = 0; |
591 | CountCtorCopyAndMove::Copy = 0; |
592 | for (int i = 0; i < Size; ++i) |
593 | Map.insert(KV: std::pair<std::string, CountCtorCopyAndMove>( |
594 | std::piecewise_construct, std::forward_as_tuple(args: Twine(i).str()), |
595 | std::forward_as_tuple(args&: i))); |
596 | // After the initial move, the map will move the Elts in the Entry. |
597 | EXPECT_EQ((unsigned)Size * 2, CountCtorCopyAndMove::Move); |
598 | // We copy once the pair from the Elts vector |
599 | EXPECT_EQ(0u, CountCtorCopyAndMove::Copy); |
600 | // Check that the map didn't grow |
601 | EXPECT_EQ(Map.getNumBuckets(), NumBuckets); |
602 | } |
603 | } |
604 | |
605 | TEST(StringMapCustomTest, BracketOperatorCtor) { |
606 | StringMap<CountCtorCopyAndMove> Map; |
607 | CountCtorCopyAndMove::Ctor = 0; |
608 | Map["abcd" ]; |
609 | EXPECT_EQ(1u, CountCtorCopyAndMove::Ctor); |
610 | // Test that operator[] does not create a value when it is already in the map |
611 | CountCtorCopyAndMove::Ctor = 0; |
612 | Map["abcd" ]; |
613 | EXPECT_EQ(0u, CountCtorCopyAndMove::Ctor); |
614 | } |
615 | |
616 | namespace { |
617 | struct NonMoveableNonCopyableType { |
618 | int Data = 0; |
619 | NonMoveableNonCopyableType() = default; |
620 | NonMoveableNonCopyableType(int Data) : Data(Data) {} |
621 | NonMoveableNonCopyableType(const NonMoveableNonCopyableType &) = delete; |
622 | NonMoveableNonCopyableType(NonMoveableNonCopyableType &&) = delete; |
623 | }; |
624 | } // namespace |
625 | |
626 | // Test that we can "emplace" an element in the map without involving map/move |
627 | TEST(StringMapCustomTest, EmplaceTest) { |
628 | StringMap<NonMoveableNonCopyableType> Map; |
629 | Map.try_emplace(Key: "abcd" , Args: 42); |
630 | EXPECT_EQ(1u, Map.count("abcd" )); |
631 | EXPECT_EQ(42, Map["abcd" ].Data); |
632 | } |
633 | |
634 | // Test that StringMapEntryBase can handle size_t wide sizes. |
635 | TEST(StringMapCustomTest, StringMapEntryBaseSize) { |
636 | size_t LargeValue; |
637 | |
638 | // Test that the entry can represent max-unsigned. |
639 | if (sizeof(size_t) <= sizeof(unsigned)) |
640 | LargeValue = std::numeric_limits<unsigned>::max(); |
641 | else |
642 | LargeValue = std::numeric_limits<unsigned>::max() + 1ULL; |
643 | StringMapEntryBase LargeBase(LargeValue); |
644 | EXPECT_EQ(LargeValue, LargeBase.getKeyLength()); |
645 | |
646 | // Test that the entry can hold at least max size_t. |
647 | LargeValue = std::numeric_limits<size_t>::max(); |
648 | StringMapEntryBase LargerBase(LargeValue); |
649 | LargeValue = std::numeric_limits<size_t>::max(); |
650 | EXPECT_EQ(LargeValue, LargerBase.getKeyLength()); |
651 | } |
652 | |
653 | // Test that StringMapEntry can handle size_t wide sizes. |
654 | TEST(StringMapCustomTest, StringMapEntrySize) { |
655 | size_t LargeValue; |
656 | |
657 | // Test that the entry can represent max-unsigned. |
658 | if (sizeof(size_t) <= sizeof(unsigned)) |
659 | LargeValue = std::numeric_limits<unsigned>::max(); |
660 | else |
661 | LargeValue = std::numeric_limits<unsigned>::max() + 1ULL; |
662 | StringMapEntry<int> LargeEntry(LargeValue); |
663 | StringRef Key = LargeEntry.getKey(); |
664 | EXPECT_EQ(LargeValue, Key.size()); |
665 | |
666 | // Test that the entry can hold at least max size_t. |
667 | LargeValue = std::numeric_limits<size_t>::max(); |
668 | StringMapEntry<int> LargerEntry(LargeValue); |
669 | Key = LargerEntry.getKey(); |
670 | EXPECT_EQ(LargeValue, Key.size()); |
671 | } |
672 | |
673 | } // end anonymous namespace |
674 | |