1/*
2 * Copyright (C) 2012-2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27
28#include "Counters.h"
29#include "DeletedAddressOfOperator.h"
30#include "MoveOnly.h"
31#include "RefLogger.h"
32#include <functional>
33#include <wtf/HashSet.h>
34#include <wtf/RefPtr.h>
35
36namespace TestWebKitAPI {
37
38template<int initialCapacity>
39struct InitialCapacityTestHashTraits : public WTF::UnsignedWithZeroKeyHashTraits<int> {
40 static const int minimumTableSize = initialCapacity;
41};
42
43template<unsigned size>
44void testInitialCapacity()
45{
46 const unsigned initialCapacity = WTF::HashTableCapacityForSize<size>::value;
47 HashSet<int, DefaultHash<int>::Hash, InitialCapacityTestHashTraits<initialCapacity> > testSet;
48
49 // Initial capacity is null.
50 ASSERT_EQ(0u, testSet.capacity());
51
52 // Adding items up to size should never change the capacity.
53 for (size_t i = 0; i < size; ++i) {
54 testSet.add(i);
55 ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
56 }
57
58 // Adding items up to less than half the capacity should not change the capacity.
59 unsigned capacityLimit = initialCapacity / 2 - 1;
60 for (size_t i = size; i < capacityLimit; ++i) {
61 testSet.add(i);
62 ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
63 }
64
65 // Adding one more item increase the capacity.
66 testSet.add(initialCapacity);
67 EXPECT_GT(static_cast<unsigned>(testSet.capacity()), initialCapacity);
68}
69
70template<unsigned size> void generateTestCapacityUpToSize();
71template<> void generateTestCapacityUpToSize<0>()
72{
73}
74template<unsigned size> void generateTestCapacityUpToSize()
75{
76 generateTestCapacityUpToSize<size - 1>();
77 testInitialCapacity<size>();
78}
79
80TEST(WTF_HashSet, InitialCapacity)
81{
82 generateTestCapacityUpToSize<128>();
83}
84
85TEST(WTF_HashSet, MoveOnly)
86{
87 HashSet<MoveOnly> hashSet;
88
89 for (size_t i = 0; i < 100; ++i) {
90 MoveOnly moveOnly(i + 1);
91 hashSet.add(WTFMove(moveOnly));
92 }
93
94 for (size_t i = 0; i < 100; ++i)
95 EXPECT_TRUE(hashSet.contains(MoveOnly(i + 1)));
96
97 for (size_t i = 0; i < 100; ++i)
98 EXPECT_TRUE(hashSet.remove(MoveOnly(i + 1)));
99
100 EXPECT_TRUE(hashSet.isEmpty());
101
102 for (size_t i = 0; i < 100; ++i)
103 hashSet.add(MoveOnly(i + 1));
104
105 for (size_t i = 0; i < 100; ++i)
106 EXPECT_TRUE(hashSet.take(MoveOnly(i + 1)) == MoveOnly(i + 1));
107
108 EXPECT_TRUE(hashSet.isEmpty());
109
110 for (size_t i = 0; i < 100; ++i)
111 hashSet.add(MoveOnly(i + 1));
112
113 HashSet<MoveOnly> secondSet;
114
115 for (size_t i = 0; i < 100; ++i)
116 secondSet.add(hashSet.takeAny());
117
118 EXPECT_TRUE(hashSet.isEmpty());
119
120 for (size_t i = 0; i < 100; ++i)
121 EXPECT_TRUE(secondSet.contains(MoveOnly(i + 1)));
122}
123
124
125TEST(WTF_HashSet, UniquePtrKey)
126{
127 ConstructorDestructorCounter::TestingScope scope;
128
129 HashSet<std::unique_ptr<ConstructorDestructorCounter>> set;
130
131 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
132 set.add(WTFMove(uniquePtr));
133
134 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
135 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
136
137 set.clear();
138
139 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
140 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
141}
142
143TEST(WTF_HashSet, UniquePtrKey_FindUsingRawPointer)
144{
145 HashSet<std::unique_ptr<int>> set;
146
147 auto uniquePtr = std::make_unique<int>(5);
148 int* ptr = uniquePtr.get();
149 set.add(WTFMove(uniquePtr));
150
151 auto it = set.find(ptr);
152 ASSERT_TRUE(it != set.end());
153 EXPECT_EQ(ptr, it->get());
154 EXPECT_EQ(5, *it->get());
155}
156
157TEST(WTF_HashSet, UniquePtrKey_ContainsUsingRawPointer)
158{
159 HashSet<std::unique_ptr<int>> set;
160
161 auto uniquePtr = std::make_unique<int>(5);
162 int* ptr = uniquePtr.get();
163 set.add(WTFMove(uniquePtr));
164
165 EXPECT_EQ(true, set.contains(ptr));
166}
167
168TEST(WTF_HashSet, UniquePtrKey_RemoveUsingRawPointer)
169{
170 ConstructorDestructorCounter::TestingScope scope;
171
172 HashSet<std::unique_ptr<ConstructorDestructorCounter>> set;
173
174 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
175 ConstructorDestructorCounter* ptr = uniquePtr.get();
176 set.add(WTFMove(uniquePtr));
177
178 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
179 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
180
181 bool result = set.remove(ptr);
182 EXPECT_EQ(true, result);
183
184 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
185 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
186}
187
188TEST(WTF_HashSet, UniquePtrKey_TakeUsingRawPointer)
189{
190 ConstructorDestructorCounter::TestingScope scope;
191
192 HashSet<std::unique_ptr<ConstructorDestructorCounter>> set;
193
194 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
195 ConstructorDestructorCounter* ptr = uniquePtr.get();
196 set.add(WTFMove(uniquePtr));
197
198 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
199 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
200
201 auto result = set.take(ptr);
202 EXPECT_EQ(ptr, result.get());
203
204 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
205 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
206
207 result = nullptr;
208
209 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
210 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
211}
212
213TEST(WTF_HashSet, CopyEmpty)
214{
215 {
216 HashSet<unsigned> foo;
217 HashSet<unsigned> bar(foo);
218
219 EXPECT_EQ(0u, bar.capacity());
220 EXPECT_EQ(0u, bar.size());
221 }
222 {
223 HashSet<unsigned> foo({ 1, 5, 64, 42 });
224 EXPECT_EQ(4u, foo.size());
225 foo.remove(1);
226 foo.remove(5);
227 foo.remove(42);
228 foo.remove(64);
229 HashSet<unsigned> bar(foo);
230
231 EXPECT_EQ(0u, bar.capacity());
232 EXPECT_EQ(0u, bar.size());
233 }
234}
235
236TEST(WTF_HashSet, CopyAllocateAtLeastMinimumCapacity)
237{
238 HashSet<unsigned> foo({ 42 });
239 EXPECT_EQ(1u, foo.size());
240 HashSet<unsigned> bar(foo);
241
242 EXPECT_EQ(8u, bar.capacity());
243 EXPECT_EQ(1u, bar.size());
244}
245
246TEST(WTF_HashSet, CopyCapacityIsNotOnBoundary)
247{
248 // Starting at 4 because the minimum size is 8.
249 // With a size of 8, a medium load can be up to 3.3333->3.
250 // Adding 1 to 3 would reach max load.
251 // While correct, that's not really what we care about here.
252 for (unsigned size = 4; size < 100; ++size) {
253 HashSet<unsigned> source;
254 for (unsigned i = 1; i < size + 1; ++i)
255 source.add(i);
256
257 HashSet<unsigned> copy1(source);
258 HashSet<unsigned> copy2(source);
259 HashSet<unsigned> copy3(source);
260
261 EXPECT_EQ(size, copy1.size());
262 EXPECT_EQ(size, copy2.size());
263 EXPECT_EQ(size, copy3.size());
264 for (unsigned i = 1; i < size + 1; ++i) {
265 EXPECT_TRUE(copy1.contains(i));
266 EXPECT_TRUE(copy2.contains(i));
267 EXPECT_TRUE(copy3.contains(i));
268 }
269 EXPECT_FALSE(copy1.contains(size + 2));
270 EXPECT_FALSE(copy2.contains(size + 2));
271 EXPECT_FALSE(copy3.contains(size + 2));
272
273 EXPECT_TRUE(copy2.remove(1));
274 EXPECT_EQ(copy1.capacity(), copy2.capacity());
275 EXPECT_FALSE(copy2.contains(1));
276
277 EXPECT_TRUE(copy3.add(size + 2).isNewEntry);
278 EXPECT_EQ(copy1.capacity(), copy3.capacity());
279 EXPECT_TRUE(copy3.contains(size + 2));
280 }
281}
282
283TEST(WTF_HashSet, RefPtrNotZeroedBeforeDeref)
284{
285 struct DerefObserver {
286 NEVER_INLINE void ref()
287 {
288 ++count;
289 }
290 NEVER_INLINE void deref()
291 {
292 --count;
293 observedBucket = bucketAddress->get();
294 }
295 unsigned count { 1 };
296 const RefPtr<DerefObserver>* bucketAddress { nullptr };
297 const DerefObserver* observedBucket { nullptr };
298 };
299
300 auto observer = std::make_unique<DerefObserver>();
301
302 HashSet<RefPtr<DerefObserver>> set;
303 set.add(adoptRef(observer.get()));
304
305 auto iterator = set.find(observer.get());
306 EXPECT_TRUE(iterator != set.end());
307
308 observer->bucketAddress = iterator.get();
309
310 EXPECT_TRUE(observer->observedBucket == nullptr);
311 EXPECT_TRUE(set.remove(observer.get()));
312
313 // It if fine to either leave the old value intact at deletion or already set it to the deleted
314 // value.
315 // A zero would be a incorrect outcome as it would mean we nulled the bucket before an opaque
316 // call.
317 EXPECT_TRUE(observer->observedBucket == observer.get() || observer->observedBucket == RefPtr<DerefObserver>::hashTableDeletedValue());
318 EXPECT_EQ(observer->count, 0u);
319}
320
321
322TEST(WTF_HashSet, UniquePtrNotZeroedBeforeDestructor)
323{
324 struct DestructorObserver {
325 ~DestructorObserver()
326 {
327 observe();
328 }
329 std::function<void()> observe;
330 };
331
332 const std::unique_ptr<DestructorObserver>* bucketAddress = nullptr;
333 const DestructorObserver* observedBucket = nullptr;
334 std::unique_ptr<DestructorObserver> observer(new DestructorObserver { [&]() {
335 observedBucket = bucketAddress->get();
336 }});
337
338 const DestructorObserver* observerAddress = observer.get();
339
340 HashSet<std::unique_ptr<DestructorObserver>> set;
341 auto addResult = set.add(WTFMove(observer));
342
343 EXPECT_TRUE(addResult.isNewEntry);
344 EXPECT_TRUE(observedBucket == nullptr);
345
346 bucketAddress = addResult.iterator.get();
347
348 EXPECT_TRUE(observedBucket == nullptr);
349 EXPECT_TRUE(set.remove(*addResult.iterator));
350
351 EXPECT_TRUE(observedBucket == observerAddress || observedBucket == reinterpret_cast<const DestructorObserver*>(-1));
352}
353
354TEST(WTF_HashSet, Ref)
355{
356 {
357 RefLogger a("a");
358
359 HashSet<Ref<RefLogger>> set;
360
361 Ref<RefLogger> ref(a);
362 set.add(WTFMove(ref));
363 }
364
365 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
366
367 {
368 RefLogger a("a");
369
370 HashSet<Ref<RefLogger>> set;
371
372 Ref<RefLogger> ref(a);
373 set.add(ref.copyRef());
374 }
375
376 ASSERT_STREQ("ref(a) ref(a) deref(a) deref(a) ", takeLogStr().c_str());
377
378 {
379 RefLogger a("a");
380
381 HashSet<Ref<RefLogger>> set;
382
383 Ref<RefLogger> ref(a);
384 set.add(WTFMove(ref));
385 set.remove(&a);
386 }
387
388 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
389
390 {
391 RefLogger a("a");
392
393 HashSet<Ref<RefLogger>> set;
394
395 Ref<RefLogger> ref(a);
396 set.add(WTFMove(ref));
397
398 auto aOut = set.take(&a);
399 ASSERT_TRUE(static_cast<bool>(aOut));
400 ASSERT_EQ(&a, aOut.value().ptr());
401 }
402
403 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
404
405 {
406 RefLogger a("a");
407
408 HashSet<Ref<RefLogger>> set;
409
410 Ref<RefLogger> ref(a);
411 set.add(WTFMove(ref));
412
413 auto aOut = set.takeAny();
414 ASSERT_TRUE(static_cast<bool>(aOut));
415 ASSERT_EQ(&a, aOut.value().ptr());
416 }
417
418 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
419
420 {
421 HashSet<Ref<RefLogger>> set;
422 auto emptyTake = set.takeAny();
423 ASSERT_FALSE(static_cast<bool>(emptyTake));
424 }
425
426 {
427 RefLogger a("a");
428
429 HashSet<Ref<RefLogger>> set;
430
431 Ref<RefLogger> ref(a);
432 set.add(WTFMove(ref));
433
434 ASSERT_TRUE(set.contains(&a));
435 }
436
437 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
438
439 {
440 HashSet<Ref<RefLogger>> set;
441 for (int i = 0; i < 64; ++i) {
442 // FIXME: All of these RefLogger objects leak. No big deal for a test I guess.
443 Ref<RefLogger> ref = adoptRef(*new RefLogger("a"));
444 auto* pointer = ref.ptr();
445 set.add(WTFMove(ref));
446 ASSERT_TRUE(set.contains(pointer));
447 }
448 }
449 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());
450}
451
452TEST(WTF_HashSet, DeletedAddressOfOperator)
453{
454 HashSet<DeletedAddressOfOperator> set1;
455 set1.add(10);
456
457 set1.remove(10);
458}
459
460TEST(WTF_HashSet, RemoveRandom)
461{
462 HashSet<unsigned> set1 { 1, 2, 3 };
463 set1.remove(set1.random());
464 set1.remove(set1.random());
465 set1.remove(set1.random());
466 ASSERT_TRUE(set1.isEmpty());
467}
468
469TEST(WTF_HashSet, RemoveIf)
470{
471 HashSet<unsigned> set1 { 1, 2, 3, 4, 5 };
472 ASSERT_EQ(set1.size(), 5u);
473 set1.removeIf([] (unsigned item) { return item % 2; });
474 set1.checkConsistency();
475 ASSERT_TRUE(!set1.contains(1));
476 ASSERT_TRUE(set1.contains(2));
477 ASSERT_TRUE(!set1.contains(3));
478 ASSERT_TRUE(set1.contains(4));
479 ASSERT_TRUE(!set1.contains(5));
480 ASSERT_EQ(set1.size(), 2u);
481}
482
483TEST(WTF_HashSet, RemoveIfShrinkToBestSize)
484{
485 HashSet<unsigned> set1;
486 set1.add(1);
487 unsigned originalCapacity = set1.capacity();
488 while (set1.capacity() < originalCapacity * 4)
489 set1.add(set1.size() + 1);
490 set1.removeIf([] (unsigned item) { return item != 1; });
491 set1.checkConsistency();
492 ASSERT_EQ(set1.size(), 1u);
493 ASSERT_EQ(set1.capacity(), originalCapacity);
494
495 set1.clear();
496 set1.checkConsistency();
497 while (set1.capacity() < originalCapacity * 8)
498 set1.add(set1.size() + 1);
499 set1.removeIf([originalCapacity] (unsigned item) { return item >= originalCapacity / 2; });
500 set1.checkConsistency();
501 ASSERT_EQ(set1.size(), originalCapacity / 2 - 1);
502 ASSERT_EQ(set1.capacity(), originalCapacity);
503}
504
505} // namespace TestWebKitAPI
506