Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(628)

Side by Side Diff: third_party/WebKit/Source/wtf/HashSetTest.cpp

Issue 2771783003: Move wtf_unittests to platform/wtf/. (Closed)
Patch Set: Rebase. Created 3 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(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
OLDNEW
« no previous file with comments | « third_party/WebKit/Source/wtf/HashMapTest.cpp ('k') | third_party/WebKit/Source/wtf/ListHashSetTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698