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