OLD | NEW |
| (Empty) |
1 /* | |
2 * Copyright (C) 2012 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 "wtf/HashSet.h" | |
27 | |
28 #include "testing/gtest/include/gtest/gtest.h" | |
29 #include "wtf/PtrUtil.h" | |
30 #include "wtf/RefCounted.h" | |
31 #include <memory> | |
32 | |
33 namespace WTF { | |
34 | |
35 namespace { | |
36 | |
37 template <unsigned size> | |
38 void testReserveCapacity(); | |
39 template <> | |
40 void testReserveCapacity<0>() {} | |
41 template <unsigned size> | |
42 void testReserveCapacity() { | |
43 HashSet<int> testSet; | |
44 | |
45 // Initial capacity is zero. | |
46 EXPECT_EQ(0UL, testSet.capacity()); | |
47 | |
48 testSet.reserveCapacityForSize(size); | |
49 const unsigned initialCapacity = testSet.capacity(); | |
50 const unsigned minimumTableSize = HashTraits<int>::minimumTableSize; | |
51 | |
52 // reserveCapacityForSize should respect minimumTableSize. | |
53 EXPECT_GE(initialCapacity, minimumTableSize); | |
54 | |
55 // Adding items up to size should never change the capacity. | |
56 for (size_t i = 0; i < size; ++i) { | |
57 testSet.insert(i + 1); // Avoid adding '0'. | |
58 EXPECT_EQ(initialCapacity, testSet.capacity()); | |
59 } | |
60 | |
61 // Adding items up to less than half the capacity should not change the | |
62 // capacity. | |
63 unsigned capacityLimit = initialCapacity / 2 - 1; | |
64 for (size_t i = size; i < capacityLimit; ++i) { | |
65 testSet.insert(i + 1); | |
66 EXPECT_EQ(initialCapacity, testSet.capacity()); | |
67 } | |
68 | |
69 // Adding one more item increases the capacity. | |
70 testSet.insert(capacityLimit + 1); | |
71 EXPECT_GT(testSet.capacity(), initialCapacity); | |
72 | |
73 testReserveCapacity<size - 1>(); | |
74 } | |
75 | |
76 TEST(HashSetTest, ReserveCapacity) { | |
77 testReserveCapacity<128>(); | |
78 } | |
79 | |
80 struct Dummy { | |
81 Dummy(bool& deleted) : deleted(deleted) {} | |
82 | |
83 ~Dummy() { deleted = true; } | |
84 | |
85 bool& deleted; | |
86 }; | |
87 | |
88 TEST(HashSetTest, HashSetOwnPtr) { | |
89 bool deleted1 = false, deleted2 = false; | |
90 | |
91 typedef HashSet<std::unique_ptr<Dummy>> OwnPtrSet; | |
92 OwnPtrSet set; | |
93 | |
94 Dummy* ptr1 = new Dummy(deleted1); | |
95 { | |
96 // AddResult in a separate scope to avoid assertion hit, | |
97 // since we modify the container further. | |
98 HashSet<std::unique_ptr<Dummy>>::AddResult res1 = | |
99 set.insert(WTF::wrapUnique(ptr1)); | |
100 EXPECT_EQ(ptr1, res1.storedValue->get()); | |
101 } | |
102 | |
103 EXPECT_FALSE(deleted1); | |
104 EXPECT_EQ(1UL, set.size()); | |
105 OwnPtrSet::iterator it1 = set.find(ptr1); | |
106 EXPECT_NE(set.end(), it1); | |
107 EXPECT_EQ(ptr1, (*it1).get()); | |
108 | |
109 Dummy* ptr2 = new Dummy(deleted2); | |
110 { | |
111 HashSet<std::unique_ptr<Dummy>>::AddResult res2 = | |
112 set.insert(WTF::wrapUnique(ptr2)); | |
113 EXPECT_EQ(res2.storedValue->get(), ptr2); | |
114 } | |
115 | |
116 EXPECT_FALSE(deleted2); | |
117 EXPECT_EQ(2UL, set.size()); | |
118 OwnPtrSet::iterator it2 = set.find(ptr2); | |
119 EXPECT_NE(set.end(), it2); | |
120 EXPECT_EQ(ptr2, (*it2).get()); | |
121 | |
122 set.erase(ptr1); | |
123 EXPECT_TRUE(deleted1); | |
124 | |
125 set.clear(); | |
126 EXPECT_TRUE(deleted2); | |
127 EXPECT_TRUE(set.isEmpty()); | |
128 | |
129 deleted1 = false; | |
130 deleted2 = false; | |
131 { | |
132 OwnPtrSet set; | |
133 set.insert(WTF::makeUnique<Dummy>(deleted1)); | |
134 set.insert(WTF::makeUnique<Dummy>(deleted2)); | |
135 } | |
136 EXPECT_TRUE(deleted1); | |
137 EXPECT_TRUE(deleted2); | |
138 | |
139 deleted1 = false; | |
140 deleted2 = false; | |
141 std::unique_ptr<Dummy> ownPtr1; | |
142 std::unique_ptr<Dummy> ownPtr2; | |
143 ptr1 = new Dummy(deleted1); | |
144 ptr2 = new Dummy(deleted2); | |
145 { | |
146 OwnPtrSet set; | |
147 set.insert(WTF::wrapUnique(ptr1)); | |
148 set.insert(WTF::wrapUnique(ptr2)); | |
149 ownPtr1 = set.take(ptr1); | |
150 EXPECT_EQ(1UL, set.size()); | |
151 ownPtr2 = set.takeAny(); | |
152 EXPECT_TRUE(set.isEmpty()); | |
153 } | |
154 EXPECT_FALSE(deleted1); | |
155 EXPECT_FALSE(deleted2); | |
156 | |
157 EXPECT_EQ(ptr1, ownPtr1.get()); | |
158 EXPECT_EQ(ptr2, ownPtr2.get()); | |
159 } | |
160 | |
161 class DummyRefCounted : public RefCounted<DummyRefCounted> { | |
162 public: | |
163 DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { | |
164 m_isDeleted = false; | |
165 } | |
166 ~DummyRefCounted() { m_isDeleted = true; } | |
167 | |
168 void ref() { | |
169 WTF::RefCounted<DummyRefCounted>::ref(); | |
170 ++s_refInvokesCount; | |
171 } | |
172 | |
173 static int s_refInvokesCount; | |
174 | |
175 private: | |
176 bool& m_isDeleted; | |
177 }; | |
178 | |
179 int DummyRefCounted::s_refInvokesCount = 0; | |
180 | |
181 TEST(HashSetTest, HashSetRefPtr) { | |
182 bool isDeleted = false; | |
183 RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted)); | |
184 EXPECT_EQ(0, DummyRefCounted::s_refInvokesCount); | |
185 HashSet<RefPtr<DummyRefCounted>> set; | |
186 set.insert(ptr); | |
187 // Referenced only once (to store a copy in the container). | |
188 EXPECT_EQ(1, DummyRefCounted::s_refInvokesCount); | |
189 | |
190 DummyRefCounted* rawPtr = ptr.get(); | |
191 | |
192 EXPECT_TRUE(set.contains(rawPtr)); | |
193 EXPECT_NE(set.end(), set.find(rawPtr)); | |
194 EXPECT_TRUE(set.contains(ptr)); | |
195 EXPECT_NE(set.end(), set.find(ptr)); | |
196 | |
197 ptr.clear(); | |
198 EXPECT_FALSE(isDeleted); | |
199 | |
200 set.erase(rawPtr); | |
201 EXPECT_TRUE(isDeleted); | |
202 EXPECT_TRUE(set.isEmpty()); | |
203 EXPECT_EQ(1, DummyRefCounted::s_refInvokesCount); | |
204 } | |
205 | |
206 class CountCopy final { | |
207 public: | |
208 static int* const kDeletedValue; | |
209 | |
210 explicit CountCopy(int* counter = nullptr) : m_counter(counter) {} | |
211 CountCopy(const CountCopy& other) : m_counter(other.m_counter) { | |
212 if (m_counter && m_counter != kDeletedValue) | |
213 ++*m_counter; | |
214 } | |
215 CountCopy& operator=(const CountCopy& other) { | |
216 m_counter = other.m_counter; | |
217 if (m_counter && m_counter != kDeletedValue) | |
218 ++*m_counter; | |
219 return *this; | |
220 } | |
221 const int* counter() const { return m_counter; } | |
222 | |
223 private: | |
224 int* m_counter; | |
225 }; | |
226 | |
227 int* const CountCopy::kDeletedValue = | |
228 reinterpret_cast<int*>(static_cast<uintptr_t>(-1)); | |
229 | |
230 struct CountCopyHashTraits : public GenericHashTraits<CountCopy> { | |
231 static const bool emptyValueIsZero = false; | |
232 static const bool hasIsEmptyValueFunction = true; | |
233 static bool isEmptyValue(const CountCopy& value) { return !value.counter(); } | |
234 static void constructDeletedValue(CountCopy& slot, bool) { | |
235 slot = CountCopy(CountCopy::kDeletedValue); | |
236 } | |
237 static bool isDeletedValue(const CountCopy& value) { | |
238 return value.counter() == CountCopy::kDeletedValue; | |
239 } | |
240 }; | |
241 | |
242 struct CountCopyHash : public PtrHash<const int*> { | |
243 static unsigned hash(const CountCopy& value) { | |
244 return PtrHash<const int>::hash(value.counter()); | |
245 } | |
246 static bool equal(const CountCopy& left, const CountCopy& right) { | |
247 return PtrHash<const int>::equal(left.counter(), right.counter()); | |
248 } | |
249 static const bool safeToCompareToEmptyOrDeleted = true; | |
250 }; | |
251 | |
252 } // anonymous namespace | |
253 | |
254 template <> | |
255 struct HashTraits<CountCopy> : public CountCopyHashTraits {}; | |
256 | |
257 template <> | |
258 struct DefaultHash<CountCopy> { | |
259 using Hash = CountCopyHash; | |
260 }; | |
261 | |
262 namespace { | |
263 | |
264 TEST(HashSetTest, MoveShouldNotMakeCopy) { | |
265 HashSet<CountCopy> set; | |
266 int counter = 0; | |
267 set.insert(CountCopy(&counter)); | |
268 | |
269 HashSet<CountCopy> other(set); | |
270 counter = 0; | |
271 set = std::move(other); | |
272 EXPECT_EQ(0, counter); | |
273 | |
274 counter = 0; | |
275 HashSet<CountCopy> yetAnother(std::move(set)); | |
276 EXPECT_EQ(0, counter); | |
277 } | |
278 | |
279 class MoveOnly { | |
280 public: | |
281 // kEmpty and kDeleted have special meanings when MoveOnly is used as the key | |
282 // of a hash table. | |
283 enum { kEmpty = 0, kDeleted = -1, kMovedOut = -2 }; | |
284 | |
285 explicit MoveOnly(int value = kEmpty, int id = 0) | |
286 : m_value(value), m_id(id) {} | |
287 MoveOnly(MoveOnly&& other) : m_value(other.m_value), m_id(other.m_id) { | |
288 other.m_value = kMovedOut; | |
289 other.m_id = 0; | |
290 } | |
291 MoveOnly& operator=(MoveOnly&& other) { | |
292 m_value = other.m_value; | |
293 m_id = other.m_id; | |
294 other.m_value = kMovedOut; | |
295 other.m_id = 0; | |
296 return *this; | |
297 } | |
298 | |
299 int value() const { return m_value; } | |
300 // id() is used for distinguishing MoveOnlys with the same value(). | |
301 int id() const { return m_id; } | |
302 | |
303 private: | |
304 MoveOnly(const MoveOnly&) = delete; | |
305 MoveOnly& operator=(const MoveOnly&) = delete; | |
306 | |
307 int m_value; | |
308 int m_id; | |
309 }; | |
310 | |
311 struct MoveOnlyHashTraits : public GenericHashTraits<MoveOnly> { | |
312 // This is actually true, but we pretend that it's false to disable the | |
313 // optimization. | |
314 static const bool emptyValueIsZero = false; | |
315 | |
316 static const bool hasIsEmptyValueFunction = true; | |
317 static bool isEmptyValue(const MoveOnly& value) { | |
318 return value.value() == MoveOnly::kEmpty; | |
319 } | |
320 static void constructDeletedValue(MoveOnly& slot, bool) { | |
321 slot = MoveOnly(MoveOnly::kDeleted); | |
322 } | |
323 static bool isDeletedValue(const MoveOnly& value) { | |
324 return value.value() == MoveOnly::kDeleted; | |
325 } | |
326 }; | |
327 | |
328 struct MoveOnlyHash { | |
329 static unsigned hash(const MoveOnly& value) { | |
330 return DefaultHash<int>::Hash::hash(value.value()); | |
331 } | |
332 static bool equal(const MoveOnly& left, const MoveOnly& right) { | |
333 return DefaultHash<int>::Hash::equal(left.value(), right.value()); | |
334 } | |
335 static const bool safeToCompareToEmptyOrDeleted = true; | |
336 }; | |
337 | |
338 } // anonymous namespace | |
339 | |
340 template <> | |
341 struct HashTraits<MoveOnly> : public MoveOnlyHashTraits {}; | |
342 | |
343 template <> | |
344 struct DefaultHash<MoveOnly> { | |
345 using Hash = MoveOnlyHash; | |
346 }; | |
347 | |
348 namespace { | |
349 | |
350 TEST(HashSetTest, MoveOnlyValue) { | |
351 using TheSet = HashSet<MoveOnly>; | |
352 TheSet set; | |
353 { | |
354 TheSet::AddResult addResult = set.insert(MoveOnly(1, 1)); | |
355 EXPECT_TRUE(addResult.isNewEntry); | |
356 EXPECT_EQ(1, addResult.storedValue->value()); | |
357 EXPECT_EQ(1, addResult.storedValue->id()); | |
358 } | |
359 auto iter = set.find(MoveOnly(1)); | |
360 ASSERT_TRUE(iter != set.end()); | |
361 EXPECT_EQ(1, iter->value()); | |
362 | |
363 iter = set.find(MoveOnly(2)); | |
364 EXPECT_TRUE(iter == set.end()); | |
365 | |
366 for (int i = 2; i < 32; ++i) { | |
367 TheSet::AddResult addResult = set.insert(MoveOnly(i, i)); | |
368 EXPECT_TRUE(addResult.isNewEntry); | |
369 EXPECT_EQ(i, addResult.storedValue->value()); | |
370 EXPECT_EQ(i, addResult.storedValue->id()); | |
371 } | |
372 | |
373 iter = set.find(MoveOnly(1)); | |
374 ASSERT_TRUE(iter != set.end()); | |
375 EXPECT_EQ(1, iter->value()); | |
376 EXPECT_EQ(1, iter->id()); | |
377 | |
378 iter = set.find(MoveOnly(7)); | |
379 ASSERT_TRUE(iter != set.end()); | |
380 EXPECT_EQ(7, iter->value()); | |
381 EXPECT_EQ(7, iter->id()); | |
382 | |
383 { | |
384 TheSet::AddResult addResult = | |
385 set.insert(MoveOnly(7, 777)); // With different ID for identification. | |
386 EXPECT_FALSE(addResult.isNewEntry); | |
387 EXPECT_EQ(7, addResult.storedValue->value()); | |
388 EXPECT_EQ(7, addResult.storedValue->id()); | |
389 } | |
390 | |
391 set.erase(MoveOnly(11)); | |
392 iter = set.find(MoveOnly(11)); | |
393 EXPECT_TRUE(iter == set.end()); | |
394 | |
395 MoveOnly thirteen(set.take(MoveOnly(13))); | |
396 EXPECT_EQ(13, thirteen.value()); | |
397 EXPECT_EQ(13, thirteen.id()); | |
398 iter = set.find(MoveOnly(13)); | |
399 EXPECT_TRUE(iter == set.end()); | |
400 | |
401 set.clear(); | |
402 } | |
403 | |
404 TEST(HashSetTest, UniquePtr) { | |
405 using Pointer = std::unique_ptr<int>; | |
406 using Set = HashSet<Pointer>; | |
407 Set set; | |
408 int* onePointer = new int(1); | |
409 { | |
410 Set::AddResult addResult = set.insert(Pointer(onePointer)); | |
411 EXPECT_TRUE(addResult.isNewEntry); | |
412 EXPECT_EQ(onePointer, addResult.storedValue->get()); | |
413 EXPECT_EQ(1, **addResult.storedValue); | |
414 } | |
415 auto iter = set.find(onePointer); | |
416 ASSERT_TRUE(iter != set.end()); | |
417 EXPECT_EQ(onePointer, iter->get()); | |
418 | |
419 Pointer nonexistent(new int(42)); | |
420 iter = set.find(nonexistent.get()); | |
421 EXPECT_TRUE(iter == set.end()); | |
422 | |
423 // Insert more to cause a rehash. | |
424 for (int i = 2; i < 32; ++i) { | |
425 Set::AddResult addResult = set.insert(Pointer(new int(i))); | |
426 EXPECT_TRUE(addResult.isNewEntry); | |
427 EXPECT_EQ(i, **addResult.storedValue); | |
428 } | |
429 | |
430 iter = set.find(onePointer); | |
431 ASSERT_TRUE(iter != set.end()); | |
432 EXPECT_EQ(onePointer, iter->get()); | |
433 | |
434 Pointer one(set.take(onePointer)); | |
435 ASSERT_TRUE(one); | |
436 EXPECT_EQ(onePointer, one.get()); | |
437 | |
438 Pointer empty(set.take(nonexistent.get())); | |
439 EXPECT_TRUE(!empty); | |
440 | |
441 iter = set.find(onePointer); | |
442 EXPECT_TRUE(iter == set.end()); | |
443 | |
444 // Re-insert to the deleted slot. | |
445 { | |
446 Set::AddResult addResult = set.insert(std::move(one)); | |
447 EXPECT_TRUE(addResult.isNewEntry); | |
448 EXPECT_EQ(onePointer, addResult.storedValue->get()); | |
449 EXPECT_EQ(1, **addResult.storedValue); | |
450 } | |
451 } | |
452 | |
453 bool isOneTwoThree(const HashSet<int>& set) { | |
454 return set.size() == 3 && set.contains(1) && set.contains(2) && | |
455 set.contains(3); | |
456 } | |
457 | |
458 HashSet<int> returnOneTwoThree() { | |
459 return {1, 2, 3}; | |
460 } | |
461 | |
462 TEST(HashSetTest, InitializerList) { | |
463 HashSet<int> empty({}); | |
464 EXPECT_TRUE(empty.isEmpty()); | |
465 | |
466 HashSet<int> one({1}); | |
467 EXPECT_EQ(1u, one.size()); | |
468 EXPECT_TRUE(one.contains(1)); | |
469 | |
470 HashSet<int> oneTwoThree({1, 2, 3}); | |
471 EXPECT_EQ(3u, oneTwoThree.size()); | |
472 EXPECT_TRUE(oneTwoThree.contains(1)); | |
473 EXPECT_TRUE(oneTwoThree.contains(2)); | |
474 EXPECT_TRUE(oneTwoThree.contains(3)); | |
475 | |
476 // Put some jank so we can check if the assignments later can clear them. | |
477 empty.insert(9999); | |
478 one.insert(9999); | |
479 oneTwoThree.insert(9999); | |
480 | |
481 empty = {}; | |
482 EXPECT_TRUE(empty.isEmpty()); | |
483 | |
484 one = {1}; | |
485 EXPECT_EQ(1u, one.size()); | |
486 EXPECT_TRUE(one.contains(1)); | |
487 | |
488 oneTwoThree = {1, 2, 3}; | |
489 EXPECT_EQ(3u, oneTwoThree.size()); | |
490 EXPECT_TRUE(oneTwoThree.contains(1)); | |
491 EXPECT_TRUE(oneTwoThree.contains(2)); | |
492 EXPECT_TRUE(oneTwoThree.contains(3)); | |
493 | |
494 oneTwoThree = {3, 1, 1, 2, 1, 1, 3}; | |
495 EXPECT_EQ(3u, oneTwoThree.size()); | |
496 EXPECT_TRUE(oneTwoThree.contains(1)); | |
497 EXPECT_TRUE(oneTwoThree.contains(2)); | |
498 EXPECT_TRUE(oneTwoThree.contains(3)); | |
499 | |
500 // Other ways of construction: as a function parameter and in a return | |
501 // statement. | |
502 EXPECT_TRUE(isOneTwoThree({1, 2, 3})); | |
503 EXPECT_TRUE(isOneTwoThree(returnOneTwoThree())); | |
504 } | |
505 | |
506 } // anonymous namespace | |
507 | |
508 } // namespace WTF | |
OLD | NEW |