1/*
2 * Copyright (C) 2011 Google Inc. All rights reserved.
3 * Copyright (C) 2017 Apple Inc. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24 * THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include "config.h"
28
29#include "Counters.h"
30#include "DeletedAddressOfOperator.h"
31#include "MoveOnly.h"
32#include "RefLogger.h"
33#include "Test.h"
34#include <string>
35#include <wtf/HashMap.h>
36#include <wtf/Ref.h>
37#include <wtf/text/StringHash.h>
38
39namespace TestWebKitAPI {
40
41typedef WTF::HashMap<int, int> IntHashMap;
42
43TEST(WTF_HashMap, HashTableIteratorComparison)
44{
45 IntHashMap map;
46 map.add(1, 2);
47 ASSERT_TRUE(map.begin() != map.end());
48 ASSERT_FALSE(map.begin() == map.end());
49
50 IntHashMap::const_iterator begin = map.begin();
51 ASSERT_TRUE(begin == map.begin());
52 ASSERT_TRUE(map.begin() == begin);
53 ASSERT_TRUE(begin != map.end());
54 ASSERT_TRUE(map.end() != begin);
55 ASSERT_FALSE(begin != map.begin());
56 ASSERT_FALSE(map.begin() != begin);
57 ASSERT_FALSE(begin == map.end());
58 ASSERT_FALSE(map.end() == begin);
59}
60
61struct TestDoubleHashTraits : HashTraits<double> {
62 static const int minimumTableSize = 8;
63};
64
65typedef HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits> DoubleHashMap;
66
67static int bucketForKey(double key)
68{
69 return DefaultHash<double>::Hash::hash(key) & (TestDoubleHashTraits::minimumTableSize - 1);
70}
71
72template<typename T> struct BigTableHashTraits : public HashTraits<T> {
73 static const int minimumTableSize = WTF::HashTableCapacityForSize<4096>::value;
74};
75
76template<typename T> struct ZeroHash : public IntHash<T> {
77 static unsigned hash(const T&) { return 0; }
78};
79
80TEST(WTF_HashMap, DoubleHashCollisions)
81{
82 // The "clobber" key here is one that ends up stealing the bucket that the -0 key
83 // originally wants to be in. This makes the 0 and -0 keys collide and the test then
84 // fails unless the FloatHash::equals() implementation can distinguish them.
85 const double clobberKey = 6;
86 const double zeroKey = 0;
87 const double negativeZeroKey = -zeroKey;
88
89 DoubleHashMap map;
90
91 map.add(clobberKey, 1);
92 map.add(zeroKey, 2);
93 map.add(negativeZeroKey, 3);
94
95 ASSERT_EQ(bucketForKey(clobberKey), bucketForKey(negativeZeroKey));
96 ASSERT_EQ(map.get(clobberKey), 1);
97 ASSERT_EQ(map.get(zeroKey), 2);
98 ASSERT_EQ(map.get(negativeZeroKey), 3);
99}
100
101TEST(WTF_HashMap, MoveOnlyValues)
102{
103 HashMap<unsigned, MoveOnly> moveOnlyValues;
104
105 for (size_t i = 0; i < 100; ++i) {
106 MoveOnly moveOnly(i + 1);
107 moveOnlyValues.set(i + 1, WTFMove(moveOnly));
108 }
109
110 for (size_t i = 0; i < 100; ++i) {
111 auto it = moveOnlyValues.find(i + 1);
112 ASSERT_FALSE(it == moveOnlyValues.end());
113 }
114
115 for (size_t i = 0; i < 50; ++i)
116 ASSERT_EQ(moveOnlyValues.take(i + 1).value(), i + 1);
117
118 for (size_t i = 50; i < 100; ++i)
119 ASSERT_TRUE(moveOnlyValues.remove(i + 1));
120
121 ASSERT_TRUE(moveOnlyValues.isEmpty());
122}
123
124TEST(WTF_HashMap, MoveOnlyKeys)
125{
126 HashMap<MoveOnly, unsigned> moveOnlyKeys;
127
128 for (size_t i = 0; i < 100; ++i) {
129 MoveOnly moveOnly(i + 1);
130 moveOnlyKeys.set(WTFMove(moveOnly), i + 1);
131 }
132
133 for (size_t i = 0; i < 100; ++i) {
134 auto it = moveOnlyKeys.find(MoveOnly(i + 1));
135 ASSERT_FALSE(it == moveOnlyKeys.end());
136 }
137
138 for (size_t i = 0; i < 100; ++i)
139 ASSERT_FALSE(moveOnlyKeys.add(MoveOnly(i + 1), i + 1).isNewEntry);
140
141 for (size_t i = 0; i < 100; ++i)
142 ASSERT_TRUE(moveOnlyKeys.remove(MoveOnly(i + 1)));
143
144 ASSERT_TRUE(moveOnlyKeys.isEmpty());
145}
146
147TEST(WTF_HashMap, InitializerList)
148{
149 HashMap<unsigned, std::string> map = {
150 { 1, "one" },
151 { 2, "two" },
152 { 3, "three" },
153 { 4, "four" },
154 };
155
156 EXPECT_EQ(4u, map.size());
157
158 EXPECT_EQ("one", map.get(1));
159 EXPECT_EQ("two", map.get(2));
160 EXPECT_EQ("three", map.get(3));
161 EXPECT_EQ("four", map.get(4));
162 EXPECT_EQ(std::string(), map.get(5));
163}
164
165TEST(WTF_HashMap, EfficientGetter)
166{
167 HashMap<unsigned, CopyMoveCounter> map;
168 map.set(1, CopyMoveCounter());
169
170 {
171 CopyMoveCounter::TestingScope scope;
172 map.get(1);
173 EXPECT_EQ(0U, CopyMoveCounter::constructionCount);
174 EXPECT_EQ(1U, CopyMoveCounter::copyCount);
175 EXPECT_EQ(0U, CopyMoveCounter::moveCount);
176 }
177
178 {
179 CopyMoveCounter::TestingScope scope;
180 map.get(2);
181 EXPECT_EQ(1U, CopyMoveCounter::constructionCount);
182 EXPECT_EQ(0U, CopyMoveCounter::copyCount);
183 EXPECT_EQ(1U, CopyMoveCounter::moveCount);
184 }
185}
186
187TEST(WTF_HashMap, UniquePtrKey)
188{
189 ConstructorDestructorCounter::TestingScope scope;
190
191 HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
192
193 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
194 map.add(WTFMove(uniquePtr), 2);
195
196 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
197 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
198
199 map.clear();
200
201 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
202 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
203}
204
205TEST(WTF_HashMap, UniquePtrKey_CustomDeleter)
206{
207 ConstructorDestructorCounter::TestingScope constructorDestructorCounterScope;
208 DeleterCounter<ConstructorDestructorCounter>::TestingScope deleterCounterScope;
209
210 HashMap<std::unique_ptr<ConstructorDestructorCounter, DeleterCounter<ConstructorDestructorCounter>>, int> map;
211
212 std::unique_ptr<ConstructorDestructorCounter, DeleterCounter<ConstructorDestructorCounter>> uniquePtr(new ConstructorDestructorCounter(), DeleterCounter<ConstructorDestructorCounter>());
213 map.add(WTFMove(uniquePtr), 2);
214
215 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
216 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
217
218 EXPECT_EQ(0u, DeleterCounter<ConstructorDestructorCounter>::deleterCount());
219
220 map.clear();
221
222 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
223 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
224
225 EXPECT_EQ(1u, DeleterCounter<ConstructorDestructorCounter>::deleterCount());
226}
227
228TEST(WTF_HashMap, UniquePtrKey_FindUsingRawPointer)
229{
230 HashMap<std::unique_ptr<int>, int> map;
231
232 auto uniquePtr = std::make_unique<int>(5);
233 int* ptr = uniquePtr.get();
234 map.add(WTFMove(uniquePtr), 2);
235
236 auto it = map.find(ptr);
237 ASSERT_TRUE(it != map.end());
238 EXPECT_EQ(ptr, it->key.get());
239 EXPECT_EQ(2, it->value);
240}
241
242TEST(WTF_HashMap, UniquePtrKey_ContainsUsingRawPointer)
243{
244 HashMap<std::unique_ptr<int>, int> map;
245
246 auto uniquePtr = std::make_unique<int>(5);
247 int* ptr = uniquePtr.get();
248 map.add(WTFMove(uniquePtr), 2);
249
250 EXPECT_EQ(true, map.contains(ptr));
251}
252
253TEST(WTF_HashMap, UniquePtrKey_GetUsingRawPointer)
254{
255 HashMap<std::unique_ptr<int>, int> map;
256
257 auto uniquePtr = std::make_unique<int>(5);
258 int* ptr = uniquePtr.get();
259 map.add(WTFMove(uniquePtr), 2);
260
261 int value = map.get(ptr);
262 EXPECT_EQ(2, value);
263}
264
265TEST(WTF_HashMap, UniquePtrKey_RemoveUsingRawPointer)
266{
267 ConstructorDestructorCounter::TestingScope scope;
268
269 HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
270
271 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
272 ConstructorDestructorCounter* ptr = uniquePtr.get();
273 map.add(WTFMove(uniquePtr), 2);
274
275 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
276 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
277
278 bool result = map.remove(ptr);
279 EXPECT_EQ(true, result);
280
281 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
282 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
283}
284
285TEST(WTF_HashMap, UniquePtrKey_TakeUsingRawPointer)
286{
287 ConstructorDestructorCounter::TestingScope scope;
288
289 HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
290
291 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
292 ConstructorDestructorCounter* ptr = uniquePtr.get();
293 map.add(WTFMove(uniquePtr), 2);
294
295 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
296 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
297
298 int result = map.take(ptr);
299 EXPECT_EQ(2, result);
300
301 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
302 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
303}
304
305TEST(WTF_HashMap, RefPtrKey_Add)
306{
307 DerivedRefLogger a("a");
308
309 HashMap<RefPtr<RefLogger>, int> map;
310
311 RefPtr<RefLogger> ptr(&a);
312 map.add(ptr, 0);
313
314 ASSERT_STREQ("ref(a) ref(a) ", takeLogStr().c_str());
315}
316
317TEST(WTF_HashMap, RefPtrKey_AddUsingRelease)
318{
319 DerivedRefLogger a("a");
320
321 HashMap<RefPtr<RefLogger>, int> map;
322
323 RefPtr<RefLogger> ptr(&a);
324 map.add(WTFMove(ptr), 0);
325
326 EXPECT_STREQ("ref(a) ", takeLogStr().c_str());
327}
328
329TEST(WTF_HashMap, RefPtrKey_AddUsingMove)
330{
331 DerivedRefLogger a("a");
332
333 HashMap<RefPtr<RefLogger>, int> map;
334
335 RefPtr<RefLogger> ptr(&a);
336 map.add(WTFMove(ptr), 0);
337
338 EXPECT_STREQ("ref(a) ", takeLogStr().c_str());
339}
340
341TEST(WTF_HashMap, RefPtrKey_AddUsingRaw)
342{
343 DerivedRefLogger a("a");
344
345 HashMap<RefPtr<RefLogger>, int> map;
346
347 RefPtr<RefLogger> ptr(&a);
348 map.add(ptr.get(), 0);
349
350 EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str());
351}
352
353TEST(WTF_HashMap, RefPtrKey_AddKeyAlreadyPresent)
354{
355 DerivedRefLogger a("a");
356
357 HashMap<RefPtr<RefLogger>, int> map;
358
359 {
360 RefPtr<RefLogger> ptr(&a);
361 map.add(ptr, 0);
362 }
363
364 EXPECT_STREQ("ref(a) ref(a) deref(a) ", takeLogStr().c_str());
365
366 {
367 RefPtr<RefLogger> ptr2(&a);
368 auto addResult = map.add(ptr2, 0);
369 EXPECT_FALSE(addResult.isNewEntry);
370 }
371
372 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
373}
374
375TEST(WTF_HashMap, RefPtrKey_AddUsingReleaseKeyAlreadyPresent)
376{
377 DerivedRefLogger a("a");
378
379 HashMap<RefPtr<RefLogger>, int> map;
380
381 {
382 RefPtr<RefLogger> ptr(&a);
383 map.add(ptr, 0);
384 }
385
386 EXPECT_STREQ("ref(a) ref(a) deref(a) ", takeLogStr().c_str());
387
388 {
389 RefPtr<RefLogger> ptr2(&a);
390 auto addResult = map.add(WTFMove(ptr2), 0);
391 EXPECT_FALSE(addResult.isNewEntry);
392 }
393
394 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
395}
396
397TEST(WTF_HashMap, RefPtrKey_AddUsingMoveKeyAlreadyPresent)
398{
399 DerivedRefLogger a("a");
400
401 HashMap<RefPtr<RefLogger>, int> map;
402
403 {
404 RefPtr<RefLogger> ptr(&a);
405 map.add(ptr, 0);
406 }
407
408 EXPECT_STREQ("ref(a) ref(a) deref(a) ", takeLogStr().c_str());
409
410 {
411 RefPtr<RefLogger> ptr2(&a);
412 auto addResult = map.add(WTFMove(ptr2), 0);
413 EXPECT_FALSE(addResult.isNewEntry);
414 }
415
416 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
417}
418
419TEST(WTF_HashMap, RefPtrKey_Set)
420{
421 DerivedRefLogger a("a");
422
423 HashMap<RefPtr<RefLogger>, int> map;
424
425 RefPtr<RefLogger> ptr(&a);
426 map.set(ptr, 0);
427
428 ASSERT_STREQ("ref(a) ref(a) ", takeLogStr().c_str());
429}
430
431TEST(WTF_HashMap, RefPtrKey_SetUsingRelease)
432{
433 DerivedRefLogger a("a");
434
435 HashMap<RefPtr<RefLogger>, int> map;
436
437 RefPtr<RefLogger> ptr(&a);
438 map.set(WTFMove(ptr), 0);
439
440 EXPECT_STREQ("ref(a) ", takeLogStr().c_str());
441}
442
443
444TEST(WTF_HashMap, RefPtrKey_SetUsingMove)
445{
446 DerivedRefLogger a("a");
447
448 HashMap<RefPtr<RefLogger>, int> map;
449
450 RefPtr<RefLogger> ptr(&a);
451 map.set(WTFMove(ptr), 0);
452
453 EXPECT_STREQ("ref(a) ", takeLogStr().c_str());
454}
455
456TEST(WTF_HashMap, RefPtrKey_SetUsingRaw)
457{
458 DerivedRefLogger a("a");
459
460 HashMap<RefPtr<RefLogger>, int> map;
461
462 RefPtr<RefLogger> ptr(&a);
463 map.set(ptr.get(), 0);
464
465 EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str());
466}
467
468TEST(WTF_HashMap, RefPtrKey_SetKeyAlreadyPresent)
469{
470 DerivedRefLogger a("a");
471
472 HashMap<RefPtr<RefLogger>, int> map;
473
474 RefPtr<RefLogger> ptr(&a);
475 map.set(ptr, 0);
476
477 EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str());
478
479 {
480 RefPtr<RefLogger> ptr2(&a);
481 auto addResult = map.set(ptr2, 1);
482 EXPECT_FALSE(addResult.isNewEntry);
483 EXPECT_EQ(1, map.get(ptr.get()));
484 }
485
486 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
487}
488
489TEST(WTF_HashMap, RefPtrKey_SetUsingReleaseKeyAlreadyPresent)
490{
491 DerivedRefLogger a("a");
492
493 HashMap<RefPtr<RefLogger>, int> map;
494
495 RefPtr<RefLogger> ptr(&a);
496 map.set(ptr, 0);
497
498 EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str());
499
500 {
501 RefPtr<RefLogger> ptr2(&a);
502 auto addResult = map.set(WTFMove(ptr2), 1);
503 EXPECT_FALSE(addResult.isNewEntry);
504 EXPECT_EQ(1, map.get(ptr.get()));
505 }
506
507 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
508}
509
510TEST(WTF_HashMap, RefPtrKey_SetUsingMoveKeyAlreadyPresent)
511{
512 DerivedRefLogger a("a");
513
514 HashMap<RefPtr<RefLogger>, int> map;
515
516 RefPtr<RefLogger> ptr(&a);
517 map.set(ptr, 0);
518
519 EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str());
520
521 {
522 RefPtr<RefLogger> ptr2(&a);
523 auto addResult = map.set(WTFMove(ptr2), 1);
524 EXPECT_FALSE(addResult.isNewEntry);
525 EXPECT_EQ(1, map.get(ptr.get()));
526 }
527
528 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
529}
530
531TEST(WTF_HashMap, Ensure)
532{
533 HashMap<unsigned, unsigned> map;
534 {
535 auto addResult = map.ensure(1, [] { return 1; });
536 EXPECT_EQ(1u, addResult.iterator->value);
537 EXPECT_EQ(1u, addResult.iterator->key);
538 EXPECT_TRUE(addResult.isNewEntry);
539 auto addResult2 = map.ensure(1, [] { return 2; });
540 EXPECT_EQ(1u, addResult2.iterator->value);
541 EXPECT_EQ(1u, addResult2.iterator->key);
542 EXPECT_FALSE(addResult2.isNewEntry);
543 }
544}
545
546TEST(WTF_HashMap, Ensure_MoveOnlyValues)
547{
548 HashMap<unsigned, MoveOnly> moveOnlyValues;
549 {
550 auto addResult = moveOnlyValues.ensure(1, [] { return MoveOnly(1); });
551 EXPECT_EQ(1u, addResult.iterator->value.value());
552 EXPECT_EQ(1u, addResult.iterator->key);
553 EXPECT_TRUE(addResult.isNewEntry);
554 auto addResult2 = moveOnlyValues.ensure(1, [] { return MoveOnly(2); });
555 EXPECT_EQ(1u, addResult2.iterator->value.value());
556 EXPECT_EQ(1u, addResult2.iterator->key);
557 EXPECT_FALSE(addResult2.isNewEntry);
558 }
559}
560
561TEST(WTF_HashMap, Ensure_UniquePointer)
562{
563 HashMap<unsigned, std::unique_ptr<unsigned>> map;
564 {
565 auto addResult = map.ensure(1, [] { return std::make_unique<unsigned>(1); });
566 EXPECT_EQ(1u, *map.get(1));
567 EXPECT_EQ(1u, *addResult.iterator->value.get());
568 EXPECT_EQ(1u, addResult.iterator->key);
569 EXPECT_TRUE(addResult.isNewEntry);
570 auto addResult2 = map.ensure(1, [] { return std::make_unique<unsigned>(2); });
571 EXPECT_EQ(1u, *map.get(1));
572 EXPECT_EQ(1u, *addResult2.iterator->value.get());
573 EXPECT_EQ(1u, addResult2.iterator->key);
574 EXPECT_FALSE(addResult2.isNewEntry);
575 }
576}
577
578TEST(WTF_HashMap, Ensure_RefPtr)
579{
580 DerivedRefLogger a("a");
581
582 HashMap<unsigned, RefPtr<RefLogger>> map;
583
584 map.ensure(1, [&] { return RefPtr<RefLogger>(&a); });
585 EXPECT_STREQ("ref(a) ", takeLogStr().c_str());
586
587 map.ensure(1, [&] { return RefPtr<RefLogger>(&a); });
588 EXPECT_STREQ("", takeLogStr().c_str());
589}
590
591class ObjectWithRefLogger {
592public:
593 ObjectWithRefLogger(Ref<RefLogger>&& logger)
594 : m_logger(WTFMove(logger))
595 {
596 }
597
598 Ref<RefLogger> m_logger;
599};
600
601
602void testMovingUsingEnsure(Ref<RefLogger>&& logger)
603{
604 HashMap<unsigned, std::unique_ptr<ObjectWithRefLogger>> map;
605
606 map.ensure(1, [&] { return std::make_unique<ObjectWithRefLogger>(WTFMove(logger)); });
607}
608
609void testMovingUsingAdd(Ref<RefLogger>&& logger)
610{
611 HashMap<unsigned, std::unique_ptr<ObjectWithRefLogger>> map;
612
613 auto& slot = map.add(1, nullptr).iterator->value;
614 slot = std::make_unique<ObjectWithRefLogger>(WTFMove(logger));
615}
616
617TEST(WTF_HashMap, Ensure_LambdasCapturingByReference)
618{
619 {
620 DerivedRefLogger a("a");
621 Ref<RefLogger> ref(a);
622 testMovingUsingEnsure(WTFMove(ref));
623
624 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
625 }
626
627 {
628 DerivedRefLogger a("a");
629 Ref<RefLogger> ref(a);
630 testMovingUsingAdd(WTFMove(ref));
631
632 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
633 }
634}
635
636
637TEST(WTF_HashMap, ValueIsDestructedOnRemove)
638{
639 struct DestructorObserver {
640 DestructorObserver() = default;
641
642 DestructorObserver(bool* destructed)
643 : destructed(destructed)
644 {
645 }
646
647 ~DestructorObserver()
648 {
649 if (destructed)
650 *destructed = true;
651 }
652
653 DestructorObserver(DestructorObserver&& other)
654 : destructed(other.destructed)
655 {
656 other.destructed = nullptr;
657 }
658
659 DestructorObserver& operator=(DestructorObserver&& other)
660 {
661 destructed = other.destructed;
662 other.destructed = nullptr;
663 return *this;
664 }
665
666 bool* destructed { nullptr };
667 };
668
669 HashMap<int, DestructorObserver> map;
670
671 bool destructed = false;
672 map.add(5, DestructorObserver { &destructed });
673
674 EXPECT_FALSE(destructed);
675
676 bool removeResult = map.remove(5);
677
678 EXPECT_TRUE(removeResult);
679 EXPECT_TRUE(destructed);
680}
681
682TEST(WTF_HashMap, RefPtrNotZeroedBeforeDeref)
683{
684 struct DerefObserver {
685 NEVER_INLINE void ref()
686 {
687 ++count;
688 }
689 NEVER_INLINE void deref()
690 {
691 --count;
692 observedBucket = bucketAddress->get();
693 }
694 unsigned count { 1 };
695 const RefPtr<DerefObserver>* bucketAddress { nullptr };
696 const DerefObserver* observedBucket { nullptr };
697 };
698
699 auto observer = std::make_unique<DerefObserver>();
700
701 HashMap<RefPtr<DerefObserver>, int> map;
702 map.add(adoptRef(observer.get()), 5);
703
704 auto iterator = map.find(observer.get());
705 EXPECT_TRUE(iterator != map.end());
706
707 observer->bucketAddress = &iterator->key;
708
709 EXPECT_TRUE(observer->observedBucket == nullptr);
710 EXPECT_TRUE(map.remove(observer.get()));
711
712 // It if fine to either leave the old value intact at deletion or already set it to the deleted
713 // value.
714 // A zero would be a incorrect outcome as it would mean we nulled the bucket before an opaque
715 // call.
716 EXPECT_TRUE(observer->observedBucket == observer.get() || observer->observedBucket == RefPtr<DerefObserver>::hashTableDeletedValue());
717 EXPECT_EQ(observer->count, 0u);
718}
719
720TEST(WTF_HashMap, Ref_Key)
721{
722 {
723 RefLogger a("a");
724
725 HashMap<Ref<RefLogger>, int> map;
726
727 Ref<RefLogger> ref(a);
728 map.add(WTFMove(ref), 1);
729 }
730
731 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
732
733 {
734 RefLogger a("a");
735
736 HashMap<Ref<RefLogger>, int> map;
737
738 Ref<RefLogger> ref(a);
739 map.set(WTFMove(ref), 1);
740 }
741
742 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
743
744 {
745 RefLogger a("a");
746
747 HashMap<Ref<RefLogger>, int> map;
748
749 Ref<RefLogger> refA(a);
750 map.add(WTFMove(refA), 1);
751
752 Ref<RefLogger> refA2(a);
753 map.set(WTFMove(refA2), 1);
754 }
755
756 ASSERT_STREQ("ref(a) ref(a) deref(a) deref(a) ", takeLogStr().c_str());
757
758 {
759 RefLogger a("a");
760
761 HashMap<Ref<RefLogger>, int> map;
762
763 Ref<RefLogger> ref(a);
764 map.ensure(WTFMove(ref), []() {
765 return 1;
766 });
767 }
768
769 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
770
771 {
772 RefLogger a("a");
773
774 HashMap<Ref<RefLogger>, int> map;
775
776 Ref<RefLogger> ref(a);
777 map.add(WTFMove(ref), 1);
778
779 auto it = map.find(&a);
780 ASSERT_TRUE(it != map.end());
781
782 ASSERT_EQ(it->key.ptr(), &a);
783 ASSERT_EQ(it->value, 1);
784 }
785
786 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
787
788 {
789 RefLogger a("a");
790
791 HashMap<Ref<RefLogger>, int> map;
792
793 Ref<RefLogger> ref(a);
794 map.add(WTFMove(ref), 1);
795
796 map.remove(&a);
797 }
798
799 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
800
801 {
802 RefLogger a("a");
803
804 HashMap<Ref<RefLogger>, int> map;
805
806 Ref<RefLogger> ref(a);
807 map.add(WTFMove(ref), 1);
808
809 int i = map.take(&a);
810 ASSERT_EQ(i, 1);
811 }
812
813 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
814
815 {
816 HashMap<Ref<RefLogger>, int> map;
817 for (int i = 0; i < 64; ++i) {
818 // FIXME: All of these RefLogger objects leak. No big deal for a test I guess.
819 Ref<RefLogger> ref = adoptRef(*new RefLogger("a"));
820 auto* pointer = ref.ptr();
821 map.add(WTFMove(ref), i + 1);
822 ASSERT_TRUE(map.contains(pointer));
823 }
824 }
825
826 ASSERT_STREQ("deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) ", takeLogStr().c_str());
827}
828
829TEST(WTF_HashMap, Ref_Value)
830{
831 {
832 RefLogger a("a");
833
834 HashMap<int, Ref<RefLogger>> map;
835
836 Ref<RefLogger> ref(a);
837 map.add(1, WTFMove(ref));
838 }
839
840 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
841
842 {
843 RefLogger a("a");
844
845 HashMap<int, Ref<RefLogger>> map;
846
847 Ref<RefLogger> ref(a);
848 map.set(1, WTFMove(ref));
849 }
850
851 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
852
853 {
854 RefLogger a("a");
855 RefLogger b("b");
856
857 HashMap<int, Ref<RefLogger>> map;
858
859 Ref<RefLogger> refA(a);
860 map.add(1, WTFMove(refA));
861
862 Ref<RefLogger> refB(b);
863 map.set(1, WTFMove(refB));
864 }
865
866 ASSERT_STREQ("ref(a) ref(b) deref(a) deref(b) ", takeLogStr().c_str());
867
868 {
869 RefLogger a("a");
870
871 HashMap<int, Ref<RefLogger>> map;
872
873 Ref<RefLogger> ref(a);
874 map.add(1, WTFMove(ref));
875
876 auto aGet = map.get(1);
877 ASSERT_EQ(aGet, &a);
878 }
879
880 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
881
882 {
883 HashMap<int, Ref<RefLogger>> map;
884
885 auto emptyGet = map.get(1);
886 ASSERT_TRUE(emptyGet == nullptr);
887 }
888
889 {
890 RefLogger a("a");
891
892 HashMap<int, Ref<RefLogger>> map;
893
894 Ref<RefLogger> ref(a);
895 map.add(1, WTFMove(ref));
896
897 auto aOut = map.take(1);
898 ASSERT_TRUE(static_cast<bool>(aOut));
899 ASSERT_EQ(&a, aOut.value().ptr());
900 }
901
902 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
903
904 {
905 HashMap<int, Ref<RefLogger>> map;
906
907 auto emptyTake = map.take(1);
908 ASSERT_FALSE(static_cast<bool>(emptyTake));
909 }
910
911 {
912 RefLogger a("a");
913
914 HashMap<int, Ref<RefLogger>> map;
915
916 Ref<RefLogger> ref(a);
917 map.add(1, WTFMove(ref));
918 map.remove(1);
919 }
920
921 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
922
923 {
924 RefLogger a("a");
925
926 HashMap<int, Ref<RefLogger>> map;
927
928 map.ensure(1, [&]() mutable {
929 Ref<RefLogger> ref(a);
930 return ref;
931 });
932 }
933
934 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
935
936 {
937 HashMap<int, Ref<RefLogger>> map;
938 for (int i = 0; i < 64; ++i) {
939 // FIXME: All of these RefLogger objects leak. No big deal for a test I guess.
940 Ref<RefLogger> ref = adoptRef(*new RefLogger("a"));
941 map.add(i + 1, WTFMove(ref));
942 ASSERT_TRUE(map.contains(i + 1));
943 }
944 }
945
946 ASSERT_STREQ("deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) deref(a) ", takeLogStr().c_str());
947}
948
949TEST(WTF_HashMap, DeletedAddressOfOperator)
950{
951 HashMap<int, DeletedAddressOfOperator> map1;
952 for (auto& value : map1.values())
953 (void)value;
954}
955
956TEST(WTF_HashMap, RefMappedToNonZeroEmptyValue)
957{
958 class Value {
959 public:
960 Value() = default;
961 Value(Value&&) = default;
962 Value(const Value&) = default;
963 Value& operator=(Value&&) = default;
964
965 Value(int32_t f)
966 : m_field(f)
967 { }
968
969 int32_t field() { return m_field; }
970
971 private:
972 int32_t m_field { 0xbadbeef };
973 };
974
975 class Key : public RefCounted<Key> {
976 Key() = default;
977 public:
978 static Ref<Key> create() { return adoptRef(*new Key); }
979 };
980
981 static_assert(!WTF::HashTraits<Value>::emptyValueIsZero, "");
982
983 HashMap<Ref<Key>, Value> map;
984 Vector<std::pair<Ref<Key>, int32_t>> vectorMap;
985
986 for (int32_t i = 0; i < 160; ++i) {
987 Ref<Key> key = Key::create();
988 map.add(Ref<Key>(key.get()), Value { i });
989 vectorMap.append({ WTFMove(key), i });
990 }
991
992 for (auto& pair : vectorMap)
993 ASSERT_EQ(pair.second, map.get(pair.first).field());
994
995 for (auto& pair : vectorMap)
996 ASSERT_TRUE(map.remove(pair.first));
997}
998
999TEST(WTF_HashMap, Random_Empty)
1000{
1001 HashMap<unsigned, unsigned> map;
1002
1003 auto result = map.random();
1004 ASSERT_EQ(result, map.end());
1005}
1006
1007TEST(WTF_HashMap, Random_WrapAround)
1008{
1009 HashMap<unsigned, unsigned, ZeroHash<unsigned>, BigTableHashTraits<unsigned>> map;
1010 map.add(1, 1);
1011
1012 auto result = map.random();
1013 ASSERT_EQ(result, map.begin());
1014}
1015
1016TEST(WTF_HashMap, Random_IsEvenlyDistributed)
1017{
1018 HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> map;
1019 map.add(0, 0);
1020 map.add(1, 1);
1021
1022 unsigned zeros = 0;
1023 unsigned ones = 0;
1024
1025 for (unsigned i = 0; i < 1000; ++i) {
1026 auto it = map.random();
1027 if (!it->value)
1028 ++zeros;
1029 else {
1030 ASSERT_EQ(it->value, 1u);
1031 ++ones;
1032 }
1033 }
1034
1035 ASSERT_EQ(zeros + ones, 1000u);
1036 ASSERT_LE(zeros, 600u);
1037 ASSERT_LE(ones, 600u);
1038}
1039
1040TEST(WTF_HashMap, Random_IsEvenlyDistributedAfterRemove)
1041{
1042 for (size_t tableSize = 2; tableSize <= 2 * 6; ++tableSize) { // Our hash tables shrink at a load factor of 1 / 6.
1043 HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> map;
1044 for (size_t i = 0; i < tableSize; ++i)
1045 map.add(i, i);
1046 for (size_t i = 2; i < tableSize; ++i)
1047 map.remove(i);
1048
1049 unsigned zeros = 0;
1050 unsigned ones = 0;
1051
1052 for (unsigned i = 0; i < 1000; ++i) {
1053 auto it = map.random();
1054 if (!it->value)
1055 ++zeros;
1056 else {
1057 ASSERT_EQ(it->value, 1u);
1058 ++ones;
1059 }
1060 }
1061
1062 ASSERT_EQ(zeros + ones, 1000u);
1063 ASSERT_LE(zeros, 600u);
1064 ASSERT_LE(ones, 600u);
1065 }
1066}
1067
1068} // namespace TestWebKitAPI
1069