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
40namespace TestWebKitAPI {
41
42typedef WTF::HashMap<int, int> IntHashMap;
43
44TEST(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
62struct TestDoubleHashTraits : HashTraits<double> {
63 static const int minimumTableSize = 8;
64};
65
66typedef HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits> DoubleHashMap;
67
68static int bucketForKey(double key)
69{
70 return DefaultHash<double>::Hash::hash(key) & (TestDoubleHashTraits::minimumTableSize - 1);
71}
72
73template<typename T> struct BigTableHashTraits : public HashTraits<T> {
74 static const int minimumTableSize = WTF::HashTableCapacityForSize<4096>::value;
75};
76
77template<typename T> struct ZeroHash : public IntHash<T> {
78 static unsigned hash(const T&) { return 0; }
79};
80
81TEST(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
102TEST(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
125TEST(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
148TEST(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
166TEST(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
188TEST(WTF_HashMap, UniquePtrKey)
189{
190 ConstructorDestructorCounter::TestingScope scope;
191
192 HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
193
194 auto uniquePtr = makeUnique<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
206TEST(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
229TEST(WTF_HashMap, UniquePtrKey_FindUsingRawPointer)
230{
231 HashMap<std::unique_ptr<int>, int> map;
232
233 auto uniquePtr = makeUniqueWithoutFastMallocCheck<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
243TEST(WTF_HashMap, UniquePtrKey_ContainsUsingRawPointer)
244{
245 HashMap<std::unique_ptr<int>, int> map;
246
247 auto uniquePtr = makeUniqueWithoutFastMallocCheck<int>(5);
248 int* ptr = uniquePtr.get();
249 map.add(WTFMove(uniquePtr), 2);
250
251 EXPECT_EQ(true, map.contains(ptr));
252}
253
254TEST(WTF_HashMap, UniquePtrKey_GetUsingRawPointer)
255{
256 HashMap<std::unique_ptr<int>, int> map;
257
258 auto uniquePtr = makeUniqueWithoutFastMallocCheck<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
266TEST(WTF_HashMap, UniquePtrKey_RemoveUsingRawPointer)
267{
268 ConstructorDestructorCounter::TestingScope scope;
269
270 HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
271
272 auto uniquePtr = makeUnique<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
286TEST(WTF_HashMap, UniquePtrKey_TakeUsingRawPointer)
287{
288 ConstructorDestructorCounter::TestingScope scope;
289
290 HashMap<std::unique_ptr<ConstructorDestructorCounter>, int> map;
291
292 auto uniquePtr = makeUnique<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
306TEST(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
318TEST(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
330TEST(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
342TEST(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
354TEST(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
376TEST(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
398TEST(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
420TEST(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
432TEST(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
445TEST(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
457TEST(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
469TEST(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
490TEST(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
511TEST(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
532TEST(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
547TEST(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
562TEST(WTF_HashMap, Ensure_UniquePointer)
563{
564 HashMap<unsigned, std::unique_ptr<unsigned>> map;
565 {
566 auto addResult = map.ensure(1, [] { return makeUniqueWithoutFastMallocCheck<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 makeUniqueWithoutFastMallocCheck<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
579TEST(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
592class ObjectWithRefLogger {
593 WTF_MAKE_FAST_ALLOCATED;
594public:
595 ObjectWithRefLogger(Ref<RefLogger>&& logger)
596 : m_logger(WTFMove(logger))
597 {
598 }
599
600 Ref<RefLogger> m_logger;
601};
602
603
604void testMovingUsingEnsure(Ref<RefLogger>&& logger)
605{
606 HashMap<unsigned, std::unique_ptr<ObjectWithRefLogger>> map;
607
608 map.ensure(1, [&] { return makeUnique<ObjectWithRefLogger>(WTFMove(logger)); });
609}
610
611void testMovingUsingAdd(Ref<RefLogger>&& logger)
612{
613 HashMap<unsigned, std::unique_ptr<ObjectWithRefLogger>> map;
614
615 auto& slot = map.add(1, nullptr).iterator->value;
616 slot = makeUnique<ObjectWithRefLogger>(WTFMove(logger));
617}
618
619TEST(WTF_HashMap, Ensure_LambdasCapturingByReference)
620{
621 {
622 DerivedRefLogger a("a");
623 Ref<RefLogger> ref(a);
624 testMovingUsingEnsure(WTFMove(ref));
625
626 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
627 }
628
629 {
630 DerivedRefLogger a("a");
631 Ref<RefLogger> ref(a);
632 testMovingUsingAdd(WTFMove(ref));
633
634 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
635 }
636}
637
638
639TEST(WTF_HashMap, ValueIsDestructedOnRemove)
640{
641 struct DestructorObserver {
642 DestructorObserver() = default;
643
644 DestructorObserver(bool* destructed)
645 : destructed(destructed)
646 {
647 }
648
649 ~DestructorObserver()
650 {
651 if (destructed)
652 *destructed = true;
653 }
654
655 DestructorObserver(DestructorObserver&& other)
656 : destructed(other.destructed)
657 {
658 other.destructed = nullptr;
659 }
660
661 DestructorObserver& operator=(DestructorObserver&& other)
662 {
663 destructed = other.destructed;
664 other.destructed = nullptr;
665 return *this;
666 }
667
668 bool* destructed { nullptr };
669 };
670
671 HashMap<int, DestructorObserver> map;
672
673 bool destructed = false;
674 map.add(5, DestructorObserver { &destructed });
675
676 EXPECT_FALSE(destructed);
677
678 bool removeResult = map.remove(5);
679
680 EXPECT_TRUE(removeResult);
681 EXPECT_TRUE(destructed);
682}
683
684struct DerefObserver {
685 WTF_MAKE_STRUCT_FAST_ALLOCATED;
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
700TEST(WTF_HashMap, RefPtrNotZeroedBeforeDeref)
701{
702 auto observer = makeUnique<DerefObserver>();
703
704 HashMap<RefPtr<DerefObserver>, int> map;
705 map.add(adoptRef(observer.get()), 5);
706
707 auto iterator = map.find(observer.get());
708 EXPECT_TRUE(iterator != map.end());
709
710 observer->bucketAddress = &iterator->key;
711
712 EXPECT_TRUE(observer->observedBucket == nullptr);
713 EXPECT_TRUE(map.remove(observer.get()));
714
715 // It if fine to either leave the old value intact at deletion or already set it to the deleted
716 // value.
717 // A zero would be a incorrect outcome as it would mean we nulled the bucket before an opaque
718 // call.
719 EXPECT_TRUE(observer->observedBucket == observer.get() || observer->observedBucket == RefPtr<DerefObserver>::hashTableDeletedValue());
720 EXPECT_EQ(observer->count, 0u);
721}
722
723TEST(WTF_HashMap, Ref_Key)
724{
725 {
726 RefLogger a("a");
727
728 HashMap<Ref<RefLogger>, int> map;
729
730 Ref<RefLogger> ref(a);
731 map.add(WTFMove(ref), 1);
732 }
733
734 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
735
736 {
737 RefLogger a("a");
738
739 HashMap<Ref<RefLogger>, int> map;
740
741 Ref<RefLogger> ref(a);
742 map.set(WTFMove(ref), 1);
743 }
744
745 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
746
747 {
748 RefLogger a("a");
749
750 HashMap<Ref<RefLogger>, int> map;
751
752 Ref<RefLogger> refA(a);
753 map.add(WTFMove(refA), 1);
754
755 Ref<RefLogger> refA2(a);
756 map.set(WTFMove(refA2), 1);
757 }
758
759 ASSERT_STREQ("ref(a) ref(a) deref(a) deref(a) ", takeLogStr().c_str());
760
761 {
762 RefLogger a("a");
763
764 HashMap<Ref<RefLogger>, int> map;
765
766 Ref<RefLogger> ref(a);
767 map.ensure(WTFMove(ref), []() {
768 return 1;
769 });
770 }
771
772 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
773
774 {
775 RefLogger a("a");
776
777 HashMap<Ref<RefLogger>, int> map;
778
779 Ref<RefLogger> ref(a);
780 map.add(WTFMove(ref), 1);
781
782 auto it = map.find(&a);
783 ASSERT_TRUE(it != map.end());
784
785 ASSERT_EQ(it->key.ptr(), &a);
786 ASSERT_EQ(it->value, 1);
787 }
788
789 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
790
791 {
792 RefLogger a("a");
793
794 HashMap<Ref<RefLogger>, int> map;
795
796 Ref<RefLogger> ref(a);
797 map.add(WTFMove(ref), 1);
798
799 map.remove(&a);
800 }
801
802 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
803
804 {
805 RefLogger a("a");
806
807 HashMap<Ref<RefLogger>, int> map;
808
809 Ref<RefLogger> ref(a);
810 map.add(WTFMove(ref), 1);
811
812 int i = map.take(&a);
813 ASSERT_EQ(i, 1);
814 }
815
816 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
817
818 {
819 HashMap<Ref<RefLogger>, int> map;
820 for (int i = 0; i < 64; ++i) {
821 // FIXME: All of these RefLogger objects leak. No big deal for a test I guess.
822 Ref<RefLogger> ref = adoptRef(*new RefLogger("a"));
823 auto* pointer = ref.ptr();
824 map.add(WTFMove(ref), i + 1);
825 ASSERT_TRUE(map.contains(pointer));
826 }
827 }
828
829 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());
830}
831
832TEST(WTF_HashMap, Ref_Value)
833{
834 {
835 RefLogger a("a");
836
837 HashMap<int, Ref<RefLogger>> map;
838
839 Ref<RefLogger> ref(a);
840 map.add(1, WTFMove(ref));
841 }
842
843 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
844
845 {
846 RefLogger a("a");
847
848 HashMap<int, Ref<RefLogger>> map;
849
850 Ref<RefLogger> ref(a);
851 map.set(1, WTFMove(ref));
852 }
853
854 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
855
856 {
857 RefLogger a("a");
858 RefLogger b("b");
859
860 HashMap<int, Ref<RefLogger>> map;
861
862 Ref<RefLogger> refA(a);
863 map.add(1, WTFMove(refA));
864
865 Ref<RefLogger> refB(b);
866 map.set(1, WTFMove(refB));
867 }
868
869 ASSERT_STREQ("ref(a) ref(b) deref(a) deref(b) ", takeLogStr().c_str());
870
871 {
872 RefLogger a("a");
873
874 HashMap<int, Ref<RefLogger>> map;
875
876 Ref<RefLogger> ref(a);
877 map.add(1, WTFMove(ref));
878
879 auto aGet = map.get(1);
880 ASSERT_EQ(aGet, &a);
881 }
882
883 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
884
885 {
886 HashMap<int, Ref<RefLogger>> map;
887
888 auto emptyGet = map.get(1);
889 ASSERT_TRUE(emptyGet == nullptr);
890 }
891
892 {
893 RefLogger a("a");
894
895 HashMap<int, Ref<RefLogger>> map;
896
897 Ref<RefLogger> ref(a);
898 map.add(1, WTFMove(ref));
899
900 auto aOut = map.take(1);
901 ASSERT_TRUE(static_cast<bool>(aOut));
902 ASSERT_EQ(&a, aOut.value().ptr());
903 }
904
905 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
906
907 {
908 HashMap<int, Ref<RefLogger>> map;
909
910 auto emptyTake = map.take(1);
911 ASSERT_FALSE(static_cast<bool>(emptyTake));
912 }
913
914 {
915 RefLogger a("a");
916
917 HashMap<int, Ref<RefLogger>> map;
918
919 Ref<RefLogger> ref(a);
920 map.add(1, WTFMove(ref));
921 map.remove(1);
922 }
923
924 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
925
926 {
927 RefLogger a("a");
928
929 HashMap<int, Ref<RefLogger>> map;
930
931 map.ensure(1, [&]() mutable {
932 Ref<RefLogger> ref(a);
933 return ref;
934 });
935 }
936
937 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
938
939 {
940 HashMap<int, Ref<RefLogger>> map;
941 for (int i = 0; i < 64; ++i) {
942 // FIXME: All of these RefLogger objects leak. No big deal for a test I guess.
943 Ref<RefLogger> ref = adoptRef(*new RefLogger("a"));
944 map.add(i + 1, WTFMove(ref));
945 ASSERT_TRUE(map.contains(i + 1));
946 }
947 }
948
949 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());
950}
951
952TEST(WTF_HashMap, DeletedAddressOfOperator)
953{
954 HashMap<int, DeletedAddressOfOperator> map1;
955 for (auto& value : map1.values())
956 (void)value;
957}
958
959TEST(WTF_HashMap, RefMappedToNonZeroEmptyValue)
960{
961 class Value {
962 public:
963 Value() = default;
964 Value(Value&&) = default;
965 Value(const Value&) = default;
966 Value& operator=(Value&&) = default;
967
968 Value(int32_t f)
969 : m_field(f)
970 { }
971
972 int32_t field() { return m_field; }
973
974 private:
975 int32_t m_field { 0xbadbeef };
976 };
977
978 class Key : public RefCounted<Key> {
979 Key() = default;
980 public:
981 static Ref<Key> create() { return adoptRef(*new Key); }
982 };
983
984 static_assert(!WTF::HashTraits<Value>::emptyValueIsZero, "");
985
986 HashMap<Ref<Key>, Value> map;
987 Vector<std::pair<Ref<Key>, int32_t>> vectorMap;
988
989 for (int32_t i = 0; i < 160; ++i) {
990 Ref<Key> key = Key::create();
991 map.add(Ref<Key>(key.get()), Value { i });
992 vectorMap.append({ WTFMove(key), i });
993 }
994
995 for (auto& pair : vectorMap)
996 ASSERT_EQ(pair.second, map.get(pair.first).field());
997
998 for (auto& pair : vectorMap)
999 ASSERT_TRUE(map.remove(pair.first));
1000}
1001
1002TEST(WTF_HashMap, Random_Empty)
1003{
1004 HashMap<unsigned, unsigned> map;
1005
1006 auto result = map.random();
1007 ASSERT_EQ(result, map.end());
1008}
1009
1010TEST(WTF_HashMap, Random_WrapAround)
1011{
1012 HashMap<unsigned, unsigned, ZeroHash<unsigned>, BigTableHashTraits<unsigned>> map;
1013 map.add(1, 1);
1014
1015 auto result = map.random();
1016 ASSERT_EQ(result, map.begin());
1017}
1018
1019TEST(WTF_HashMap, Random_IsEvenlyDistributed)
1020{
1021 HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> map;
1022 map.add(0, 0);
1023 map.add(1, 1);
1024
1025 unsigned zeros = 0;
1026 unsigned ones = 0;
1027
1028 for (unsigned i = 0; i < 1000; ++i) {
1029 auto it = map.random();
1030 if (!it->value)
1031 ++zeros;
1032 else {
1033 ASSERT_EQ(it->value, 1u);
1034 ++ones;
1035 }
1036 }
1037
1038 ASSERT_EQ(zeros + ones, 1000u);
1039 ASSERT_LE(zeros, 600u);
1040 ASSERT_LE(ones, 600u);
1041}
1042
1043TEST(WTF_HashMap, ReserveInitialCapacity)
1044{
1045 HashMap<String, String> map;
1046 EXPECT_EQ(0u, map.size());
1047 map.reserveInitialCapacity(9999);
1048 EXPECT_EQ(0u, map.size());
1049 for (int i = 0; i < 9999; ++i)
1050 map.add(makeString("foo", i), makeString("bar", i));
1051 EXPECT_EQ(9999u, map.size());
1052 EXPECT_TRUE(map.contains("foo3"_str));
1053 EXPECT_STREQ("bar3", map.get("foo3"_str).utf8().data());
1054 for (int i = 0; i < 9999; ++i)
1055 map.add(makeString("excess", i), makeString("baz", i));
1056 EXPECT_EQ(9999u + 9999u, map.size());
1057 for (int i = 0; i < 9999; ++i)
1058 EXPECT_TRUE(map.remove(makeString("foo", i)));
1059 EXPECT_EQ(9999u, map.size());
1060 EXPECT_STREQ("baz3", map.get("excess3"_str).utf8().data());
1061 for (int i = 0; i < 9999; ++i)
1062 EXPECT_TRUE(map.remove(makeString("excess", i)));
1063 EXPECT_EQ(0u, map.size());
1064
1065 HashMap<String, String> map2;
1066 map2.reserveInitialCapacity(9999);
1067 EXPECT_FALSE(map2.remove("foo1"_s));
1068 for (int i = 0; i < 2000; ++i)
1069 map2.add(makeString("foo", i), makeString("bar", i));
1070 EXPECT_EQ(2000u, map2.size());
1071 for (int i = 0; i < 2000; ++i)
1072 EXPECT_TRUE(map2.remove(makeString("foo", i)));
1073 EXPECT_EQ(0u, map2.size());
1074}
1075
1076TEST(WTF_HashMap, Random_IsEvenlyDistributedAfterRemove)
1077{
1078 for (size_t tableSize = 2; tableSize <= 2 * 6; ++tableSize) { // Our hash tables shrink at a load factor of 1 / 6.
1079 HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> map;
1080 for (size_t i = 0; i < tableSize; ++i)
1081 map.add(i, i);
1082 for (size_t i = 2; i < tableSize; ++i)
1083 map.remove(i);
1084
1085 unsigned zeros = 0;
1086 unsigned ones = 0;
1087
1088 for (unsigned i = 0; i < 1000; ++i) {
1089 auto it = map.random();
1090 if (!it->value)
1091 ++zeros;
1092 else {
1093 ASSERT_EQ(it->value, 1u);
1094 ++ones;
1095 }
1096 }
1097
1098 ASSERT_EQ(zeros + ones, 1000u);
1099 ASSERT_LE(zeros, 600u);
1100 ASSERT_LE(ones, 600u);
1101 }
1102}
1103
1104} // namespace TestWebKitAPI
1105