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 "config.h"
27
28 #include "wtf/LinkedHashSet.h"
29 #include "wtf/ListHashSet.h"
30 #include "wtf/PassRefPtr.h"
31 #include "wtf/RefCounted.h"
32 #include "wtf/RefPtr.h"
33 #include <gtest/gtest.h>
34
35 namespace {
36
37 template<typename Set>
removeFirstHelper()38 void removeFirstHelper()
39 {
40 Set list;
41 list.add(-1);
42 list.add(0);
43 list.add(1);
44 list.add(2);
45 list.add(3);
46
47 EXPECT_EQ(-1, list.first());
48 EXPECT_EQ(3, list.last());
49
50 list.removeFirst();
51 EXPECT_EQ(0, list.first());
52
53 list.removeLast();
54 EXPECT_EQ(2, list.last());
55
56 list.removeFirst();
57 EXPECT_EQ(1, list.first());
58
59 list.removeFirst();
60 EXPECT_EQ(2, list.first());
61
62 list.removeFirst();
63 EXPECT_TRUE(list.isEmpty());
64 }
65
TEST(ListHashSetTest,RemoveFirst)66 TEST(ListHashSetTest, RemoveFirst)
67 {
68 removeFirstHelper<ListHashSet<int> >();
69 removeFirstHelper<ListHashSet<int, 1> >();
70 }
71
TEST(LinkedHashSetTest,RemoveFirst)72 TEST(LinkedHashSetTest, RemoveFirst)
73 {
74 removeFirstHelper<LinkedHashSet<int> >();
75 }
76
77 template<typename Set>
appendOrMoveToLastNewItems()78 void appendOrMoveToLastNewItems()
79 {
80 Set list;
81 typename Set::AddResult result = list.appendOrMoveToLast(1);
82 EXPECT_TRUE(result.isNewEntry);
83 result = list.add(2);
84 EXPECT_TRUE(result.isNewEntry);
85 result = list.appendOrMoveToLast(3);
86 EXPECT_TRUE(result.isNewEntry);
87
88 EXPECT_EQ(list.size(), 3UL);
89
90 // The list should be in order 1, 2, 3.
91 typename Set::iterator iterator = list.begin();
92 EXPECT_EQ(1, *iterator);
93 ++iterator;
94 EXPECT_EQ(2, *iterator);
95 ++iterator;
96 EXPECT_EQ(3, *iterator);
97 ++iterator;
98 }
99
TEST(ListHashSetTest,AppendOrMoveToLastNewItems)100 TEST(ListHashSetTest, AppendOrMoveToLastNewItems)
101 {
102 appendOrMoveToLastNewItems<ListHashSet<int> >();
103 appendOrMoveToLastNewItems<ListHashSet<int, 1> >();
104 }
105
TEST(LinkedHashSetTest,AppendOrMoveToLastNewItems)106 TEST(LinkedHashSetTest, AppendOrMoveToLastNewItems)
107 {
108 appendOrMoveToLastNewItems<LinkedHashSet<int> >();
109 }
110
111 template<typename Set>
appendOrMoveToLastWithDuplicates()112 void appendOrMoveToLastWithDuplicates()
113 {
114 Set list;
115
116 // Add a single element twice.
117 typename Set::AddResult result = list.add(1);
118 EXPECT_TRUE(result.isNewEntry);
119 result = list.appendOrMoveToLast(1);
120 EXPECT_FALSE(result.isNewEntry);
121 EXPECT_EQ(1UL, list.size());
122
123 list.add(2);
124 list.add(3);
125 EXPECT_EQ(3UL, list.size());
126
127 // Appending 2 move it to the end.
128 EXPECT_EQ(3, list.last());
129 result = list.appendOrMoveToLast(2);
130 EXPECT_FALSE(result.isNewEntry);
131 EXPECT_EQ(2, list.last());
132
133 // Inverse the list by moving each element to end end.
134 result = list.appendOrMoveToLast(3);
135 EXPECT_FALSE(result.isNewEntry);
136 result = list.appendOrMoveToLast(2);
137 EXPECT_FALSE(result.isNewEntry);
138 result = list.appendOrMoveToLast(1);
139 EXPECT_FALSE(result.isNewEntry);
140 EXPECT_EQ(3UL, list.size());
141
142 typename Set::iterator iterator = list.begin();
143 EXPECT_EQ(3, *iterator);
144 ++iterator;
145 EXPECT_EQ(2, *iterator);
146 ++iterator;
147 EXPECT_EQ(1, *iterator);
148 ++iterator;
149 }
150
TEST(ListHashSetTest,AppendOrMoveToLastWithDuplicates)151 TEST(ListHashSetTest, AppendOrMoveToLastWithDuplicates)
152 {
153 appendOrMoveToLastWithDuplicates<ListHashSet<int> >();
154 appendOrMoveToLastWithDuplicates<ListHashSet<int, 1> >();
155 }
156
TEST(LinkedHashSetTest,AppendOrMoveToLastWithDuplicates)157 TEST(LinkedHashSetTest, AppendOrMoveToLastWithDuplicates)
158 {
159 appendOrMoveToLastWithDuplicates<LinkedHashSet<int> >();
160 }
161
162 template<typename Set>
prependOrMoveToFirstNewItems()163 void prependOrMoveToFirstNewItems()
164 {
165 Set list;
166 typename Set::AddResult result = list.prependOrMoveToFirst(1);
167 EXPECT_TRUE(result.isNewEntry);
168 result = list.add(2);
169 EXPECT_TRUE(result.isNewEntry);
170 result = list.prependOrMoveToFirst(3);
171 EXPECT_TRUE(result.isNewEntry);
172
173 EXPECT_EQ(list.size(), 3UL);
174
175 // The list should be in order 3, 1, 2.
176 typename Set::iterator iterator = list.begin();
177 EXPECT_EQ(3, *iterator);
178 ++iterator;
179 EXPECT_EQ(1, *iterator);
180 ++iterator;
181 EXPECT_EQ(2, *iterator);
182 ++iterator;
183 }
184
TEST(ListHashSetTest,PrependOrMoveToFirstNewItems)185 TEST(ListHashSetTest, PrependOrMoveToFirstNewItems)
186 {
187 prependOrMoveToFirstNewItems<ListHashSet<int> >();
188 prependOrMoveToFirstNewItems<ListHashSet<int, 1> >();
189 }
190
TEST(LinkedHashSetTest,PrependOrMoveToFirstNewItems)191 TEST(LinkedHashSetTest, PrependOrMoveToFirstNewItems)
192 {
193 prependOrMoveToFirstNewItems<LinkedHashSet<int> >();
194 }
195
196 template<typename Set>
prependOrMoveToLastWithDuplicates()197 void prependOrMoveToLastWithDuplicates()
198 {
199 Set list;
200
201 // Add a single element twice.
202 typename Set::AddResult result = list.add(1);
203 EXPECT_TRUE(result.isNewEntry);
204 result = list.prependOrMoveToFirst(1);
205 EXPECT_FALSE(result.isNewEntry);
206 EXPECT_EQ(1UL, list.size());
207
208 list.add(2);
209 list.add(3);
210 EXPECT_EQ(3UL, list.size());
211
212 // Prepending 2 move it to the beginning.
213 EXPECT_EQ(1, list.first());
214 result = list.prependOrMoveToFirst(2);
215 EXPECT_FALSE(result.isNewEntry);
216 EXPECT_EQ(2, list.first());
217
218 // Inverse the list by moving each element to the first position.
219 result = list.prependOrMoveToFirst(1);
220 EXPECT_FALSE(result.isNewEntry);
221 result = list.prependOrMoveToFirst(2);
222 EXPECT_FALSE(result.isNewEntry);
223 result = list.prependOrMoveToFirst(3);
224 EXPECT_FALSE(result.isNewEntry);
225 EXPECT_EQ(3UL, list.size());
226
227 typename Set::iterator iterator = list.begin();
228 EXPECT_EQ(3, *iterator);
229 ++iterator;
230 EXPECT_EQ(2, *iterator);
231 ++iterator;
232 EXPECT_EQ(1, *iterator);
233 ++iterator;
234 }
235
TEST(ListHashSetTest,PrependOrMoveToLastWithDuplicates)236 TEST(ListHashSetTest, PrependOrMoveToLastWithDuplicates)
237 {
238 prependOrMoveToLastWithDuplicates<ListHashSet<int> >();
239 prependOrMoveToLastWithDuplicates<ListHashSet<int, 1> >();
240 }
241
TEST(LinkedHashSetTest,PrependOrMoveToLastWithDuplicates)242 TEST(LinkedHashSetTest, PrependOrMoveToLastWithDuplicates)
243 {
244 prependOrMoveToLastWithDuplicates<LinkedHashSet<int> >();
245 }
246
247 class DummyRefCounted: public WTF::RefCounted<DummyRefCounted> {
248 public:
DummyRefCounted(bool & isDeleted)249 DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { m_isDeleted = false; }
~DummyRefCounted()250 ~DummyRefCounted() { m_isDeleted = true; }
ref()251 void ref()
252 {
253 WTF::RefCounted<DummyRefCounted>::ref();
254 ++m_refInvokesCount;
255 }
256
257 static int m_refInvokesCount;
258
259 private:
260 bool& m_isDeleted;
261 };
262
263 int DummyRefCounted::m_refInvokesCount = 0;
264
265 template<typename Set>
withRefPtr()266 void withRefPtr()
267 {
268 bool isDeleted = false;
269 DummyRefCounted::m_refInvokesCount = 0;
270 RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
271 EXPECT_EQ(0, DummyRefCounted::m_refInvokesCount);
272
273 Set set;
274 set.add(ptr);
275 // Referenced only once (to store a copy in the container).
276 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
277 EXPECT_EQ(ptr, set.first());
278 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
279
280 DummyRefCounted* rawPtr = ptr.get();
281
282 EXPECT_TRUE(set.contains(ptr));
283 EXPECT_TRUE(set.contains(rawPtr));
284 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
285
286 ptr.clear();
287 EXPECT_FALSE(isDeleted);
288 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
289
290 set.remove(rawPtr);
291 EXPECT_TRUE(isDeleted);
292
293 EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
294 }
295
TEST(ListHashSetTest,WithRefPtr)296 TEST(ListHashSetTest, WithRefPtr)
297 {
298 withRefPtr<ListHashSet<RefPtr<DummyRefCounted> > >();
299 withRefPtr<ListHashSet<RefPtr<DummyRefCounted>, 1> >();
300 }
301
TEST(LinkedHashSetTest,WithRefPtr)302 TEST(LinkedHashSetTest, WithRefPtr)
303 {
304 withRefPtr<LinkedHashSet<RefPtr<DummyRefCounted> > >();
305 }
306
307 template<typename Set, typename SetRef, typename Iterator>
findHelper()308 void findHelper()
309 {
310 Set set;
311 set.add(-1);
312 set.add(0);
313 set.add(1);
314 set.add(2);
315 set.add(3);
316
317 SetRef ref = set;
318 Iterator it = ref.find(2);
319 EXPECT_EQ(2, *it);
320 ++it;
321 EXPECT_EQ(3, *it);
322 --it;
323 --it;
324 EXPECT_EQ(1, *it);
325 }
326
TEST(ListHashSetTest,Find)327 TEST(ListHashSetTest, Find)
328 {
329 findHelper<ListHashSet<int>, const ListHashSet<int>&, ListHashSet<int>::const_iterator>();
330 findHelper<ListHashSet<int>, ListHashSet<int>&, ListHashSet<int>::iterator>();
331 findHelper<ListHashSet<int, 1>, const ListHashSet<int, 1>&, ListHashSet<int, 1>::const_iterator>();
332 findHelper<ListHashSet<int, 1>, ListHashSet<int, 1>&, ListHashSet<int, 1>::iterator>();
333 }
334
TEST(LinkedHashSetTest,Find)335 TEST(LinkedHashSetTest, Find)
336 {
337 findHelper<LinkedHashSet<int>, const LinkedHashSet<int>&, LinkedHashSet<int>::const_iterator>();
338 findHelper<LinkedHashSet<int>, LinkedHashSet<int>&, LinkedHashSet<int>::iterator>();
339 }
340
341 template<typename Set>
insertBeforeHelper(bool canModifyWhileIterating)342 void insertBeforeHelper(bool canModifyWhileIterating)
343 {
344 Set set;
345 set.add(-1);
346 set.add(0);
347 set.add(2);
348 set.add(3);
349
350 typename Set::iterator it = set.find(2);
351 EXPECT_EQ(2, *it);
352 set.insertBefore(it, 1);
353 if (!canModifyWhileIterating)
354 it = set.find(2);
355 ++it;
356 EXPECT_EQ(3, *it);
357 EXPECT_EQ(5u, set.size());
358 --it;
359 --it;
360 EXPECT_EQ(1, *it);
361 if (canModifyWhileIterating) {
362 set.remove(-1);
363 set.remove(0);
364 set.remove(2);
365 set.remove(3);
366 EXPECT_EQ(1u, set.size());
367 EXPECT_EQ(1, *it);
368 ++it;
369 EXPECT_EQ(it, set.end());
370 --it;
371 EXPECT_EQ(1, *it);
372 set.insertBefore(it, -1);
373 set.insertBefore(it, 0);
374 set.add(2);
375 set.add(3);
376 }
377 set.insertBefore(2, 42);
378 set.insertBefore(-1, 103);
379 EXPECT_EQ(103, set.first());
380 if (!canModifyWhileIterating)
381 it = set.find(1);
382 ++it;
383 EXPECT_EQ(42, *it);
384 EXPECT_EQ(7u, set.size());
385 }
386
TEST(ListHashSetTest,InsertBefore)387 TEST(ListHashSetTest, InsertBefore)
388 {
389 insertBeforeHelper<ListHashSet<int> >(true);
390 insertBeforeHelper<ListHashSet<int, 1> >(true);
391 }
392
TEST(LinkedHashSetTest,InsertBefore)393 TEST(LinkedHashSetTest, InsertBefore)
394 {
395 insertBeforeHelper<LinkedHashSet<int> >(false);
396 }
397
398 template<typename Set>
addReturnIterator(bool canModifyWhileIterating)399 void addReturnIterator(bool canModifyWhileIterating)
400 {
401 Set set;
402 set.add(-1);
403 set.add(0);
404 set.add(1);
405 set.add(2);
406
407 typename Set::iterator it = set.addReturnIterator(3);
408 EXPECT_EQ(3, *it);
409 --it;
410 EXPECT_EQ(2, *it);
411 EXPECT_EQ(5u, set.size());
412 --it;
413 EXPECT_EQ(1, *it);
414 --it;
415 EXPECT_EQ(0, *it);
416 it = set.addReturnIterator(4);
417 if (canModifyWhileIterating) {
418 set.remove(3);
419 set.remove(2);
420 set.remove(1);
421 set.remove(0);
422 set.remove(-1);
423 EXPECT_EQ(1u, set.size());
424 }
425 EXPECT_EQ(4, *it);
426 ++it;
427 EXPECT_EQ(it, set.end());
428 --it;
429 EXPECT_EQ(4, *it);
430 if (canModifyWhileIterating) {
431 set.insertBefore(it, -1);
432 set.insertBefore(it, 0);
433 set.insertBefore(it, 1);
434 set.insertBefore(it, 2);
435 set.insertBefore(it, 3);
436 }
437 EXPECT_EQ(6u, set.size());
438 it = set.addReturnIterator(5);
439 EXPECT_EQ(7u, set.size());
440 set.remove(it);
441 EXPECT_EQ(6u, set.size());
442 EXPECT_EQ(4, set.last());
443 }
444
TEST(ListHashSetTest,AddReturnIterator)445 TEST(ListHashSetTest, AddReturnIterator)
446 {
447 addReturnIterator<ListHashSet<int> >(true);
448 addReturnIterator<ListHashSet<int, 1> >(true);
449 }
450
TEST(LinkedHashSetTest,AddReturnIterator)451 TEST(LinkedHashSetTest, AddReturnIterator)
452 {
453 addReturnIterator<LinkedHashSet<int> >(false);
454 }
455
456 template<typename Set>
excerciseValuePeekInType()457 void excerciseValuePeekInType()
458 {
459 Set set;
460 bool isDeleted = false;
461 bool isDeleted2 = false;
462
463 RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
464 RefPtr<DummyRefCounted> ptr2 = adoptRef(new DummyRefCounted(isDeleted2));
465
466 typename Set::AddResult addResult = set.add(ptr);
467 EXPECT_TRUE(addResult.isNewEntry);
468 set.find(ptr);
469 const Set& constSet(set);
470 constSet.find(ptr);
471 EXPECT_TRUE(set.contains(ptr));
472 typename Set::iterator it = set.addReturnIterator(ptr);
473 set.appendOrMoveToLast(ptr);
474 set.prependOrMoveToFirst(ptr);
475 set.insertBefore(ptr, ptr);
476 set.insertBefore(it, ptr);
477 EXPECT_EQ(1u, set.size());
478 set.add(ptr2);
479 ptr2.clear();
480 set.remove(ptr);
481
482 EXPECT_FALSE(isDeleted);
483 ptr.clear();
484 EXPECT_TRUE(isDeleted);
485
486 EXPECT_FALSE(isDeleted2);
487 set.removeFirst();
488 EXPECT_TRUE(isDeleted2);
489
490 EXPECT_EQ(0u, set.size());
491 }
492
TEST(ListHashSetTest,ExcerciseValuePeekInType)493 TEST(ListHashSetTest, ExcerciseValuePeekInType)
494 {
495 excerciseValuePeekInType<ListHashSet<RefPtr<DummyRefCounted> > >();
496 excerciseValuePeekInType<ListHashSet<RefPtr<DummyRefCounted>, 1> >();
497 }
498
TEST(LinkedHashSetTest,ExcerciseValuePeekInType)499 TEST(LinkedHashSetTest, ExcerciseValuePeekInType)
500 {
501 excerciseValuePeekInType<LinkedHashSet<RefPtr<DummyRefCounted> > >();
502 }
503
504 struct Simple {
Simple__anon5d93962d0111::Simple505 Simple(int value) : m_value(value) { };
506 int m_value;
507 };
508
509 struct Complicated {
Complicated__anon5d93962d0111::Complicated510 Complicated(int value) : m_simple(value)
511 {
512 s_objectsConstructed++;
513 }
514
Complicated__anon5d93962d0111::Complicated515 Complicated(const Complicated& other) : m_simple(other.m_simple)
516 {
517 s_objectsConstructed++;
518 }
519
520 Simple m_simple;
521 static int s_objectsConstructed;
522
523 private:
524 Complicated();
525 };
526
527 int Complicated::s_objectsConstructed = 0;
528
529 struct ComplicatedHashFunctions {
hash__anon5d93962d0111::ComplicatedHashFunctions530 static unsigned hash(const Complicated& key) { return key.m_simple.m_value; }
equal__anon5d93962d0111::ComplicatedHashFunctions531 static bool equal(const Complicated& a, const Complicated& b) { return a.m_simple.m_value == b.m_simple.m_value; }
532 };
533 struct ComplexityTranslator {
hash__anon5d93962d0111::ComplexityTranslator534 static unsigned hash(const Simple& key) { return key.m_value; }
equal__anon5d93962d0111::ComplexityTranslator535 static bool equal(const Complicated& a, const Simple& b) { return a.m_simple.m_value == b.m_value; }
536 };
537
538 template<typename Set>
translatorTest()539 void translatorTest()
540 {
541 Set set;
542 set.add(Complicated(42));
543 int baseLine = Complicated::s_objectsConstructed;
544
545 typename Set::iterator it = set.template find<ComplexityTranslator>(Simple(42));
546 EXPECT_NE(it, set.end());
547 EXPECT_EQ(baseLine, Complicated::s_objectsConstructed);
548
549 it = set.template find<ComplexityTranslator>(Simple(103));
550 EXPECT_EQ(it, set.end());
551 EXPECT_EQ(baseLine, Complicated::s_objectsConstructed);
552
553 const Set& constSet(set);
554
555 typename Set::const_iterator constIterator = constSet.template find<ComplexityTranslator>(Simple(42));
556 EXPECT_NE(constIterator, constSet.end());
557 EXPECT_EQ(baseLine, Complicated::s_objectsConstructed);
558
559 constIterator = constSet.template find<ComplexityTranslator>(Simple(103));
560 EXPECT_EQ(constIterator, constSet.end());
561 EXPECT_EQ(baseLine, Complicated::s_objectsConstructed);
562 }
563
TEST(ListHashSetTest,ComplexityTranslator)564 TEST(ListHashSetTest, ComplexityTranslator)
565 {
566 translatorTest<ListHashSet<Complicated, 256, ComplicatedHashFunctions> >();
567 translatorTest<ListHashSet<Complicated, 1, ComplicatedHashFunctions> >();
568 }
569
TEST(LinkedHashSetTest,ComplexityTranslator)570 TEST(LinkedHashSetTest, ComplexityTranslator)
571 {
572 translatorTest<LinkedHashSet<Complicated, ComplicatedHashFunctions> >();
573 }
574
575 struct Dummy {
Dummy__anon5d93962d0111::Dummy576 Dummy(bool& deleted) : deleted(deleted) { }
577
~Dummy__anon5d93962d0111::Dummy578 ~Dummy()
579 {
580 deleted = true;
581 }
582
583 bool& deleted;
584 };
585
TEST(ListHashSetTest,WithOwnPtr)586 TEST(ListHashSetTest, WithOwnPtr)
587 {
588 bool deleted1 = false, deleted2 = false;
589
590 typedef ListHashSet<OwnPtr<Dummy> > OwnPtrSet;
591 OwnPtrSet set;
592
593 Dummy* ptr1 = new Dummy(deleted1);
594 {
595 // AddResult in a separate scope to avoid assertion hit,
596 // since we modify the container further.
597 OwnPtrSet::AddResult res1 = set.add(adoptPtr(ptr1));
598 EXPECT_EQ(res1.storedValue->m_value.get(), ptr1);
599 }
600
601 EXPECT_FALSE(deleted1);
602 EXPECT_EQ(1UL, set.size());
603 OwnPtrSet::iterator it1 = set.find(ptr1);
604 EXPECT_NE(set.end(), it1);
605 EXPECT_EQ(ptr1, (*it1));
606
607 Dummy* ptr2 = new Dummy(deleted2);
608 {
609 OwnPtrSet::AddResult res2 = set.add(adoptPtr(ptr2));
610 EXPECT_EQ(res2.storedValue->m_value.get(), ptr2);
611 }
612
613 EXPECT_FALSE(deleted2);
614 EXPECT_EQ(2UL, set.size());
615 OwnPtrSet::iterator it2 = set.find(ptr2);
616 EXPECT_NE(set.end(), it2);
617 EXPECT_EQ(ptr2, (*it2));
618
619 set.remove(ptr1);
620 EXPECT_TRUE(deleted1);
621
622 set.clear();
623 EXPECT_TRUE(deleted2);
624 EXPECT_TRUE(set.isEmpty());
625
626 deleted1 = false;
627 deleted2 = false;
628 {
629 OwnPtrSet set;
630 set.add(adoptPtr(new Dummy(deleted1)));
631 set.add(adoptPtr(new Dummy(deleted2)));
632 }
633 EXPECT_TRUE(deleted1);
634 EXPECT_TRUE(deleted2);
635
636
637 deleted1 = false;
638 deleted2 = false;
639 OwnPtr<Dummy> ownPtr1;
640 OwnPtr<Dummy> ownPtr2;
641 ptr1 = new Dummy(deleted1);
642 ptr2 = new Dummy(deleted2);
643 {
644 OwnPtrSet set;
645 set.add(adoptPtr(ptr1));
646 set.add(adoptPtr(ptr2));
647 ownPtr1 = set.takeFirst();
648 EXPECT_EQ(1UL, set.size());
649 ownPtr2 = set.take(ptr2);
650 EXPECT_TRUE(set.isEmpty());
651 }
652 EXPECT_FALSE(deleted1);
653 EXPECT_FALSE(deleted2);
654
655 EXPECT_EQ(ptr1, ownPtr1);
656 EXPECT_EQ(ptr2, ownPtr2);
657 }
658
659 template<typename Set>
swapTestHelper()660 void swapTestHelper()
661 {
662 int num = 10;
663 Set set0;
664 Set set1;
665 Set set2;
666 for (int i = 0; i < num; ++i) {
667 set1.add(i + 1);
668 set2.add(num - i);
669 }
670
671 typename Set::iterator it1 = set1.begin();
672 typename Set::iterator it2 = set2.begin();
673 for (int i = 0; i < num; ++i, ++it1, ++it2) {
674 EXPECT_EQ(*it1, i + 1);
675 EXPECT_EQ(*it2, num - i);
676 }
677 EXPECT_EQ(set0.begin(), set0.end());
678 EXPECT_EQ(it1, set1.end());
679 EXPECT_EQ(it2, set2.end());
680
681 // Shift sets: 2->1, 1->0, 0->2
682 set1.swap(set2); // Swap with non-empty sets.
683 set0.swap(set2); // Swap with an empty set.
684
685 it1 = set0.begin();
686 it2 = set1.begin();
687 for (int i = 0; i < num; ++i, ++it1, ++it2) {
688 EXPECT_EQ(*it1, i + 1);
689 EXPECT_EQ(*it2, num - i);
690 }
691 EXPECT_EQ(it1, set0.end());
692 EXPECT_EQ(it2, set1.end());
693 EXPECT_EQ(set2.begin(), set2.end());
694
695 int removedIndex = num >> 1;
696 set0.remove(removedIndex + 1);
697 set1.remove(num - removedIndex);
698
699 it1 = set0.begin();
700 it2 = set1.begin();
701 for (int i = 0; i < num; ++i, ++it1, ++it2) {
702 if (i == removedIndex)
703 ++i;
704 EXPECT_EQ(*it1, i + 1);
705 EXPECT_EQ(*it2, num - i);
706 }
707 EXPECT_EQ(it1, set0.end());
708 EXPECT_EQ(it2, set1.end());
709 }
710
TEST(ListHashSetTest,Swap)711 TEST(ListHashSetTest, Swap)
712 {
713 swapTestHelper<ListHashSet<int> >();
714 }
715
TEST(LinkedHashSetTest,Swap)716 TEST(LinkedHashSetTest, Swap)
717 {
718 swapTestHelper<LinkedHashSet<int> >();
719 }
720
721 } // namespace
722