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 = makeUnique<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 = makeUniqueWithoutFastMallocCheck<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 = makeUniqueWithoutFastMallocCheck<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 = makeUnique<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 = makeUnique<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
283struct DerefObserver {
284 WTF_MAKE_STRUCT_FAST_ALLOCATED;
285 NEVER_INLINE void ref()
286 {
287 ++count;
288 }
289 NEVER_INLINE void deref()
290 {
291 --count;
292 observedBucket = bucketAddress->get();
293 }
294 unsigned count { 1 };
295 const RefPtr<DerefObserver>* bucketAddress { nullptr };
296 const DerefObserver* observedBucket { nullptr };
297};
298
299TEST(WTF_HashSet, RefPtrNotZeroedBeforeDeref)
300{
301 auto observer = makeUnique<DerefObserver>();
302
303 HashSet<RefPtr<DerefObserver>> set;
304 set.add(adoptRef(observer.get()));
305
306 auto iterator = set.find(observer.get());
307 EXPECT_TRUE(iterator != set.end());
308
309 observer->bucketAddress = iterator.get();
310
311 EXPECT_TRUE(observer->observedBucket == nullptr);
312 EXPECT_TRUE(set.remove(observer.get()));
313
314 // It if fine to either leave the old value intact at deletion or already set it to the deleted
315 // value.
316 // A zero would be a incorrect outcome as it would mean we nulled the bucket before an opaque
317 // call.
318 EXPECT_TRUE(observer->observedBucket == observer.get() || observer->observedBucket == RefPtr<DerefObserver>::hashTableDeletedValue());
319 EXPECT_EQ(observer->count, 0u);
320}
321
322
323TEST(WTF_HashSet, UniquePtrNotZeroedBeforeDestructor)
324{
325 struct DestructorObserver {
326 ~DestructorObserver()
327 {
328 observe();
329 }
330 std::function<void()> observe;
331 };
332
333 const std::unique_ptr<DestructorObserver>* bucketAddress = nullptr;
334 const DestructorObserver* observedBucket = nullptr;
335 std::unique_ptr<DestructorObserver> observer(new DestructorObserver { [&]() {
336 observedBucket = bucketAddress->get();
337 }});
338
339 const DestructorObserver* observerAddress = observer.get();
340
341 HashSet<std::unique_ptr<DestructorObserver>> set;
342 auto addResult = set.add(WTFMove(observer));
343
344 EXPECT_TRUE(addResult.isNewEntry);
345 EXPECT_TRUE(observedBucket == nullptr);
346
347 bucketAddress = addResult.iterator.get();
348
349 EXPECT_TRUE(observedBucket == nullptr);
350 EXPECT_TRUE(set.remove(*addResult.iterator));
351
352 EXPECT_TRUE(observedBucket == observerAddress || observedBucket == reinterpret_cast<const DestructorObserver*>(-1));
353}
354
355TEST(WTF_HashSet, Ref)
356{
357 {
358 RefLogger a("a");
359
360 HashSet<Ref<RefLogger>> set;
361
362 Ref<RefLogger> ref(a);
363 set.add(WTFMove(ref));
364 }
365
366 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
367
368 {
369 RefLogger a("a");
370
371 HashSet<Ref<RefLogger>> set;
372
373 Ref<RefLogger> ref(a);
374 set.add(ref.copyRef());
375 }
376
377 ASSERT_STREQ("ref(a) ref(a) deref(a) deref(a) ", takeLogStr().c_str());
378
379 {
380 RefLogger a("a");
381
382 HashSet<Ref<RefLogger>> set;
383
384 Ref<RefLogger> ref(a);
385 set.add(WTFMove(ref));
386 set.remove(&a);
387 }
388
389 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
390
391 {
392 RefLogger a("a");
393
394 HashSet<Ref<RefLogger>> set;
395
396 Ref<RefLogger> ref(a);
397 set.add(WTFMove(ref));
398
399 auto aOut = set.take(&a);
400 ASSERT_TRUE(static_cast<bool>(aOut));
401 ASSERT_EQ(&a, aOut.value().ptr());
402 }
403
404 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
405
406 {
407 RefLogger a("a");
408
409 HashSet<Ref<RefLogger>> set;
410
411 Ref<RefLogger> ref(a);
412 set.add(WTFMove(ref));
413
414 auto aOut = set.takeAny();
415 ASSERT_TRUE(static_cast<bool>(aOut));
416 ASSERT_EQ(&a, aOut.value().ptr());
417 }
418
419 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
420
421 {
422 HashSet<Ref<RefLogger>> set;
423 auto emptyTake = set.takeAny();
424 ASSERT_FALSE(static_cast<bool>(emptyTake));
425 }
426
427 {
428 RefLogger a("a");
429
430 HashSet<Ref<RefLogger>> set;
431
432 Ref<RefLogger> ref(a);
433 set.add(WTFMove(ref));
434
435 ASSERT_TRUE(set.contains(&a));
436 }
437
438 ASSERT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
439
440 {
441 HashSet<Ref<RefLogger>> set;
442 for (int i = 0; i < 64; ++i) {
443 // FIXME: All of these RefLogger objects leak. No big deal for a test I guess.
444 Ref<RefLogger> ref = adoptRef(*new RefLogger("a"));
445 auto* pointer = ref.ptr();
446 set.add(WTFMove(ref));
447 ASSERT_TRUE(set.contains(pointer));
448 }
449 }
450 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());
451}
452
453TEST(WTF_HashSet, DeletedAddressOfOperator)
454{
455 HashSet<DeletedAddressOfOperator> set1;
456 set1.add(10);
457
458 set1.remove(10);
459}
460
461TEST(WTF_HashSet, RemoveRandom)
462{
463 HashSet<unsigned> set1 { 1, 2, 3 };
464 set1.remove(set1.random());
465 set1.remove(set1.random());
466 set1.remove(set1.random());
467 ASSERT_TRUE(set1.isEmpty());
468}
469
470TEST(WTF_HashSet, RemoveIf)
471{
472 HashSet<unsigned> set1 { 1, 2, 3, 4, 5 };
473 ASSERT_EQ(set1.size(), 5u);
474 set1.removeIf([] (unsigned item) { return item % 2; });
475 set1.checkConsistency();
476 ASSERT_TRUE(!set1.contains(1));
477 ASSERT_TRUE(set1.contains(2));
478 ASSERT_TRUE(!set1.contains(3));
479 ASSERT_TRUE(set1.contains(4));
480 ASSERT_TRUE(!set1.contains(5));
481 ASSERT_EQ(set1.size(), 2u);
482}
483
484TEST(WTF_HashSet, RemoveIfShrinkToBestSize)
485{
486 HashSet<unsigned> set1;
487 set1.add(1);
488 unsigned originalCapacity = set1.capacity();
489 while (set1.capacity() < originalCapacity * 4)
490 set1.add(set1.size() + 1);
491 set1.removeIf([] (unsigned item) { return item != 1; });
492 set1.checkConsistency();
493 ASSERT_EQ(set1.size(), 1u);
494 ASSERT_EQ(set1.capacity(), originalCapacity);
495
496 set1.clear();
497 set1.checkConsistency();
498 while (set1.capacity() < originalCapacity * 8)
499 set1.add(set1.size() + 1);
500 set1.removeIf([originalCapacity] (unsigned item) { return item >= originalCapacity / 2; });
501 set1.checkConsistency();
502 ASSERT_EQ(set1.size(), originalCapacity / 2 - 1);
503 ASSERT_EQ(set1.capacity(), originalCapacity);
504}
505
506} // namespace TestWebKitAPI
507