1/*
2 * Copyright (C) 2011 Google Inc. All rights reserved.
3 * Copyright (C) 2016-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 "MoveOnly.h"
31#include "RefLogger.h"
32#include <string>
33#include <wtf/HashCountedSet.h>
34#include <wtf/text/StringHash.h>
35
36namespace TestWebKitAPI {
37
38typedef WTF::HashCountedSet<int> IntHashCountedSet;
39
40TEST(WTF_HashCountedSet, HashTableIteratorComparison)
41{
42 IntHashCountedSet hashCountedSet;
43 hashCountedSet.add(1);
44 ASSERT_TRUE(hashCountedSet.begin() != hashCountedSet.end());
45 ASSERT_FALSE(hashCountedSet.begin() == hashCountedSet.end());
46
47 IntHashCountedSet::const_iterator begin = hashCountedSet.begin();
48 ASSERT_TRUE(begin == hashCountedSet.begin());
49 ASSERT_TRUE(hashCountedSet.begin() == begin);
50 ASSERT_TRUE(begin != hashCountedSet.end());
51 ASSERT_TRUE(hashCountedSet.end() != begin);
52 ASSERT_FALSE(begin != hashCountedSet.begin());
53 ASSERT_FALSE(hashCountedSet.begin() != begin);
54 ASSERT_FALSE(begin == hashCountedSet.end());
55 ASSERT_FALSE(hashCountedSet.end() == begin);
56}
57
58struct TestDoubleHashTraits : HashTraits<double> {
59 static const int minimumTableSize = 8;
60};
61
62typedef HashCountedSet<double, DefaultHash<double>::Hash, TestDoubleHashTraits> DoubleHashCountedSet;
63
64static int bucketForKey(double key)
65{
66 return DefaultHash<double>::Hash::hash(key) & (TestDoubleHashTraits::minimumTableSize - 1);
67}
68
69TEST(WTF_HashCountedSet, DoubleHashCollisions)
70{
71 // The "clobber" key here is one that ends up stealing the bucket that the -0 key
72 // originally wants to be in. This makes the 0 and -0 keys collide and the test then
73 // fails unless the FloatHash::equals() implementation can distinguish them.
74 const double clobberKey = 6;
75 const double zeroKey = 0;
76 const double negativeZeroKey = -zeroKey;
77
78 DoubleHashCountedSet hashCountedSet;
79
80 hashCountedSet.add(clobberKey);
81
82 ASSERT_EQ(hashCountedSet.count(clobberKey), 1u);
83 ASSERT_EQ(hashCountedSet.count(zeroKey), 0u);
84 ASSERT_EQ(hashCountedSet.count(negativeZeroKey), 0u);
85
86 hashCountedSet.add(zeroKey);
87 hashCountedSet.add(negativeZeroKey);
88
89 ASSERT_EQ(bucketForKey(clobberKey), bucketForKey(negativeZeroKey));
90 ASSERT_EQ(hashCountedSet.count(clobberKey), 1u);
91 ASSERT_EQ(hashCountedSet.count(zeroKey), 1u);
92 ASSERT_EQ(hashCountedSet.count(negativeZeroKey), 1u);
93
94 hashCountedSet.add(clobberKey);
95 hashCountedSet.add(zeroKey);
96 hashCountedSet.add(negativeZeroKey);
97
98 ASSERT_EQ(hashCountedSet.count(clobberKey), 2u);
99 ASSERT_EQ(hashCountedSet.count(zeroKey), 2u);
100 ASSERT_EQ(hashCountedSet.count(negativeZeroKey), 2u);
101
102 hashCountedSet.add(clobberKey, 12);
103 hashCountedSet.add(zeroKey, 15);
104 hashCountedSet.add(negativeZeroKey, 17);
105
106 ASSERT_EQ(hashCountedSet.count(clobberKey), 14u);
107 ASSERT_EQ(hashCountedSet.count(zeroKey), 17u);
108 ASSERT_EQ(hashCountedSet.count(negativeZeroKey), 19u);
109}
110
111TEST(WTF_HashCountedSet, DoubleHashCollisionsInitialCount)
112{
113 // The "clobber" key here is one that ends up stealing the bucket that the -0 key
114 // originally wants to be in. This makes the 0 and -0 keys collide and the test then
115 // fails unless the FloatHash::equals() implementation can distinguish them.
116 const double clobberKey = 6;
117 const double zeroKey = 0;
118 const double negativeZeroKey = -zeroKey;
119
120 DoubleHashCountedSet hashCountedSet;
121
122 hashCountedSet.add(clobberKey, 5);
123
124 ASSERT_EQ(hashCountedSet.count(clobberKey), 5u);
125 ASSERT_EQ(hashCountedSet.count(zeroKey), 0u);
126 ASSERT_EQ(hashCountedSet.count(negativeZeroKey), 0u);
127
128 hashCountedSet.add(zeroKey, 22);
129 hashCountedSet.add(negativeZeroKey, 0);
130
131 ASSERT_EQ(bucketForKey(clobberKey), bucketForKey(negativeZeroKey));
132 ASSERT_EQ(hashCountedSet.count(clobberKey), 5u);
133 ASSERT_EQ(hashCountedSet.count(zeroKey), 22u);
134 ASSERT_EQ(hashCountedSet.count(negativeZeroKey), 0u);
135
136 hashCountedSet.add(clobberKey);
137 hashCountedSet.add(zeroKey);
138 hashCountedSet.add(negativeZeroKey);
139
140 ASSERT_EQ(hashCountedSet.count(clobberKey), 6u);
141 ASSERT_EQ(hashCountedSet.count(zeroKey), 23u);
142 ASSERT_EQ(hashCountedSet.count(negativeZeroKey), 1u);
143}
144
145
146TEST(WTF_HashCountedSet, MoveOnlyKeys)
147{
148 HashCountedSet<MoveOnly> moveOnlyKeys;
149
150 for (size_t i = 0; i < 100; ++i) {
151 MoveOnly moveOnly(i + 1);
152 moveOnlyKeys.add(WTFMove(moveOnly));
153 }
154
155 for (size_t i = 0; i < 100; ++i) {
156 auto it = moveOnlyKeys.find(MoveOnly(i + 1));
157 ASSERT_FALSE(it == moveOnlyKeys.end());
158 ASSERT_EQ(it->value, 1u);
159 }
160
161 for (size_t i = 0; i < 100; ++i)
162 ASSERT_FALSE(moveOnlyKeys.add(MoveOnly(i + 1)).isNewEntry);
163
164 for (size_t i = 0; i < 100; ++i)
165 ASSERT_FALSE(moveOnlyKeys.remove(MoveOnly(i + 1)));
166
167 for (size_t i = 0; i < 100; ++i)
168 ASSERT_TRUE(moveOnlyKeys.remove(MoveOnly(i + 1)));
169
170 ASSERT_TRUE(moveOnlyKeys.isEmpty());
171}
172
173TEST(WTF_HashCountedSet, MoveOnlyKeysInitialCount)
174{
175 HashCountedSet<MoveOnly> moveOnlyKeys;
176
177 for (size_t i = 0; i < 100; ++i) {
178 MoveOnly moveOnly(i + 1);
179 moveOnlyKeys.add(WTFMove(moveOnly), i + 1);
180 }
181
182 for (size_t i = 0; i < 100; ++i) {
183 auto it = moveOnlyKeys.find(MoveOnly(i + 1));
184 ASSERT_FALSE(it == moveOnlyKeys.end());
185 ASSERT_EQ(it->value, i + 1);
186 }
187
188 for (size_t i = 0; i < 100; ++i)
189 ASSERT_FALSE(moveOnlyKeys.add(MoveOnly(i + 1)).isNewEntry);
190
191 for (size_t i = 0; i < 100; ++i)
192 ASSERT_EQ(moveOnlyKeys.count(MoveOnly(i + 1)), i + 2);
193
194 for (size_t i = 0; i < 100; ++i)
195 ASSERT_FALSE(moveOnlyKeys.remove(MoveOnly(i + 1)));
196
197 for (size_t i = 0; i < 100; ++i)
198 ASSERT_EQ(moveOnlyKeys.count(MoveOnly(i + 1)), i + 1);
199}
200
201TEST(WTF_HashCountedSet, InitializerList)
202{
203 HashCountedSet<String> hashCountedSet = {
204 "one",
205 "two",
206 "three",
207 "four",
208 "four",
209 "four",
210 "four",
211 };
212
213 EXPECT_EQ(4u, hashCountedSet.size());
214
215 EXPECT_EQ(hashCountedSet.count("one"), 1u);
216 EXPECT_EQ(hashCountedSet.count("two"), 1u);
217 EXPECT_EQ(hashCountedSet.count("three"), 1u);
218 EXPECT_EQ(hashCountedSet.count("four"), 4u);
219}
220
221TEST(WTF_HashCountedSet, InitializerListInitialCount)
222{
223 HashCountedSet<String> hashCountedSet = {
224 { String("one"), 1u },
225 { String("two"), 2u },
226 { String("three"), 3u },
227 { String("four"), 4u },
228 };
229
230 EXPECT_EQ(4u, hashCountedSet.size());
231
232 EXPECT_EQ(hashCountedSet.count("one"), 1u);
233 EXPECT_EQ(hashCountedSet.count("two"), 2u);
234 EXPECT_EQ(hashCountedSet.count("three"), 3u);
235 EXPECT_EQ(hashCountedSet.count("four"), 4u);
236}
237
238TEST(WTF_HashCountedSet, UniquePtrKey)
239{
240 ConstructorDestructorCounter::TestingScope scope;
241
242 HashCountedSet<std::unique_ptr<ConstructorDestructorCounter>> hashCountedSet;
243
244 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
245 hashCountedSet.add(WTFMove(uniquePtr));
246
247 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
248 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
249
250 hashCountedSet.clear();
251
252 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
253 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
254}
255
256TEST(WTF_HashCountedSet, UniquePtrKeyInitialCount)
257{
258 ConstructorDestructorCounter::TestingScope scope;
259
260 HashCountedSet<std::unique_ptr<ConstructorDestructorCounter>> hashCountedSet;
261
262 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
263 hashCountedSet.add(WTFMove(uniquePtr), 12);
264
265 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
266 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
267
268 hashCountedSet.clear();
269
270 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
271 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
272}
273
274TEST(WTF_HashCountedSet, UniquePtrKey_CustomDeleter)
275{
276 ConstructorDestructorCounter::TestingScope constructorDestructorCounterScope;
277 DeleterCounter<ConstructorDestructorCounter>::TestingScope deleterCounterScope;
278
279 HashCountedSet<std::unique_ptr<ConstructorDestructorCounter, DeleterCounter<ConstructorDestructorCounter>>> hashCountedSet;
280
281 std::unique_ptr<ConstructorDestructorCounter, DeleterCounter<ConstructorDestructorCounter>> uniquePtr(new ConstructorDestructorCounter(), DeleterCounter<ConstructorDestructorCounter>());
282 hashCountedSet.add(WTFMove(uniquePtr));
283
284 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
285 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
286
287 EXPECT_EQ(0u, DeleterCounter<ConstructorDestructorCounter>::deleterCount());
288
289 hashCountedSet.clear();
290
291 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
292 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
293
294 EXPECT_EQ(1u, DeleterCounter<ConstructorDestructorCounter>::deleterCount());
295}
296
297TEST(WTF_HashCountedSet, UniquePtrKey_FindUsingRawPointer)
298{
299 HashCountedSet<std::unique_ptr<int>> hashCountedSet;
300
301 auto uniquePtr = std::make_unique<int>(5);
302 int* ptr = uniquePtr.get();
303 hashCountedSet.add(WTFMove(uniquePtr));
304
305 auto it = hashCountedSet.find(ptr);
306 ASSERT_TRUE(it != hashCountedSet.end());
307 EXPECT_EQ(ptr, it->key.get());
308 EXPECT_EQ(1u, it->value);
309}
310
311TEST(WTF_HashCountedSet, UniquePtrKey_ContainsUsingRawPointer)
312{
313 HashCountedSet<std::unique_ptr<int>> hashCountedSet;
314
315 auto uniquePtr = std::make_unique<int>(5);
316 int* ptr = uniquePtr.get();
317 hashCountedSet.add(WTFMove(uniquePtr));
318
319 EXPECT_EQ(true, hashCountedSet.contains(ptr));
320}
321
322TEST(WTF_HashCountedSet, UniquePtrKey_GetUsingRawPointer)
323{
324 HashCountedSet<std::unique_ptr<int>> hashCountedSet;
325
326 auto uniquePtr = std::make_unique<int>(5);
327 int* ptr = uniquePtr.get();
328 hashCountedSet.add(WTFMove(uniquePtr));
329
330 int value = hashCountedSet.count(ptr);
331 EXPECT_EQ(1, value);
332}
333
334TEST(WTF_HashCountedSet, UniquePtrKey_RemoveUsingRawPointer)
335{
336 ConstructorDestructorCounter::TestingScope scope;
337
338 HashCountedSet<std::unique_ptr<ConstructorDestructorCounter>> hashCountedSet;
339
340 auto uniquePtr = std::make_unique<ConstructorDestructorCounter>();
341 ConstructorDestructorCounter* ptr = uniquePtr.get();
342 hashCountedSet.add(WTFMove(uniquePtr));
343
344 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
345 EXPECT_EQ(0u, ConstructorDestructorCounter::destructionCount);
346
347 bool result = hashCountedSet.remove(ptr);
348 EXPECT_EQ(true, result);
349
350 EXPECT_EQ(1u, ConstructorDestructorCounter::constructionCount);
351 EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
352}
353
354TEST(WTF_HashCountedSet, RefPtrKey_Add)
355{
356 DerivedRefLogger a("a");
357
358 HashCountedSet<RefPtr<RefLogger>> hashCountedSet;
359
360 RefPtr<RefLogger> ptr(&a);
361 hashCountedSet.add(ptr);
362
363 ASSERT_STREQ("ref(a) ref(a) ", takeLogStr().c_str());
364 EXPECT_EQ(1U, hashCountedSet.count(ptr));
365 EXPECT_EQ(1U, hashCountedSet.count(ptr.get()));
366}
367
368TEST(WTF_HashCountedSet, RefPtrKey_AddUsingRelease)
369{
370 DerivedRefLogger a("a");
371
372 HashCountedSet<RefPtr<RefLogger>> hashCountedSet;
373
374 RefPtr<RefLogger> ptr(&a);
375 hashCountedSet.add(WTFMove(ptr));
376
377 EXPECT_STREQ("ref(a) ", takeLogStr().c_str());
378}
379
380TEST(WTF_HashCountedSet, RefPtrKey_AddUsingMove)
381{
382 DerivedRefLogger a("a");
383
384 HashCountedSet<RefPtr<RefLogger>> hashCountedSet;
385
386 RefPtr<RefLogger> ptr(&a);
387 hashCountedSet.add(WTFMove(ptr));
388
389 EXPECT_STREQ("ref(a) ", takeLogStr().c_str());
390}
391
392TEST(WTF_HashCountedSet, RefPtrKey_AddUsingRaw)
393{
394 DerivedRefLogger a("a");
395
396 HashCountedSet<RefPtr<RefLogger>> hashCountedSet;
397
398 RefPtr<RefLogger> ptr(&a);
399 hashCountedSet.add(ptr.get());
400
401 EXPECT_STREQ("ref(a) ref(a) ", takeLogStr().c_str());
402 EXPECT_EQ(1U, hashCountedSet.count(ptr));
403 EXPECT_EQ(1U, hashCountedSet.count(ptr.get()));
404}
405
406TEST(WTF_HashCountedSet, RefPtrKey_AddKeyAlreadyPresent)
407{
408 DerivedRefLogger a("a");
409
410 HashCountedSet<RefPtr<RefLogger>> hashCountedSet;
411
412 {
413 RefPtr<RefLogger> ptr(&a);
414 hashCountedSet.add(ptr);
415 }
416
417 EXPECT_STREQ("ref(a) ref(a) deref(a) ", takeLogStr().c_str());
418
419 {
420 RefPtr<RefLogger> ptr2(&a);
421 auto addResult = hashCountedSet.add(ptr2);
422 EXPECT_FALSE(addResult.isNewEntry);
423 }
424
425 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
426}
427
428TEST(WTF_HashCountedSet, RefPtrKey_AddUsingReleaseKeyAlreadyPresent)
429{
430 DerivedRefLogger a("a");
431
432 HashCountedSet<RefPtr<RefLogger>> hashCountedSet;
433
434 {
435 RefPtr<RefLogger> ptr(&a);
436 hashCountedSet.add(ptr);
437 }
438
439 EXPECT_STREQ("ref(a) ref(a) deref(a) ", takeLogStr().c_str());
440
441 {
442 RefPtr<RefLogger> ptr2(&a);
443 auto addResult = hashCountedSet.add(WTFMove(ptr2));
444 EXPECT_FALSE(addResult.isNewEntry);
445 }
446
447 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
448}
449
450TEST(WTF_HashCountedSet, RefPtrKey_AddUsingMoveKeyAlreadyPresent)
451{
452 DerivedRefLogger a("a");
453
454 HashCountedSet<RefPtr<RefLogger>> hashCountedSet;
455
456 {
457 RefPtr<RefLogger> ptr(&a);
458 hashCountedSet.add(ptr);
459 }
460
461 EXPECT_STREQ("ref(a) ref(a) deref(a) ", takeLogStr().c_str());
462
463 {
464 RefPtr<RefLogger> ptr2(&a);
465 auto addResult = hashCountedSet.add(WTFMove(ptr2));
466 EXPECT_FALSE(addResult.isNewEntry);
467 }
468
469 EXPECT_STREQ("ref(a) deref(a) ", takeLogStr().c_str());
470}
471
472TEST(WTF_HashCountedSet, Values)
473{
474 HashCountedSet<int> set { 1, 1, 2, 3, 3 };
475
476 auto vector = copyToVector(set.values());
477 EXPECT_EQ(3U, vector.size());
478
479 std::sort(vector.begin(), vector.end());
480 EXPECT_EQ(1, vector[0]);
481 EXPECT_EQ(2, vector[1]);
482 EXPECT_EQ(3, vector[2]);
483}
484
485} // namespace TestWebKitAPI
486