Home | History | Annotate | Download | only in wtf
      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>
     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 
     66 TEST(ListHashSetTest, RemoveFirst)
     67 {
     68     removeFirstHelper<ListHashSet<int> >();
     69     removeFirstHelper<ListHashSet<int, 1> >();
     70 }
     71 
     72 TEST(LinkedHashSetTest, RemoveFirst)
     73 {
     74     removeFirstHelper<LinkedHashSet<int> >();
     75 }
     76 
     77 template<typename Set>
     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 
    100 TEST(ListHashSetTest, AppendOrMoveToLastNewItems)
    101 {
    102     appendOrMoveToLastNewItems<ListHashSet<int> >();
    103     appendOrMoveToLastNewItems<ListHashSet<int, 1> >();
    104 }
    105 
    106 TEST(LinkedHashSetTest, AppendOrMoveToLastNewItems)
    107 {
    108     appendOrMoveToLastNewItems<LinkedHashSet<int> >();
    109 }
    110 
    111 template<typename Set>
    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 
    151 TEST(ListHashSetTest, AppendOrMoveToLastWithDuplicates)
    152 {
    153     appendOrMoveToLastWithDuplicates<ListHashSet<int> >();
    154     appendOrMoveToLastWithDuplicates<ListHashSet<int, 1> >();
    155 }
    156 
    157 TEST(LinkedHashSetTest, AppendOrMoveToLastWithDuplicates)
    158 {
    159     appendOrMoveToLastWithDuplicates<LinkedHashSet<int> >();
    160 }
    161 
    162 template<typename Set>
    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 
    185 TEST(ListHashSetTest, PrependOrMoveToFirstNewItems)
    186 {
    187     prependOrMoveToFirstNewItems<ListHashSet<int> >();
    188     prependOrMoveToFirstNewItems<ListHashSet<int, 1> >();
    189 }
    190 
    191 TEST(LinkedHashSetTest, PrependOrMoveToFirstNewItems)
    192 {
    193     prependOrMoveToFirstNewItems<LinkedHashSet<int> >();
    194 }
    195 
    196 template<typename Set>
    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 
    236 TEST(ListHashSetTest, PrependOrMoveToLastWithDuplicates)
    237 {
    238     prependOrMoveToLastWithDuplicates<ListHashSet<int> >();
    239     prependOrMoveToLastWithDuplicates<ListHashSet<int, 1> >();
    240 }
    241 
    242 TEST(LinkedHashSetTest, PrependOrMoveToLastWithDuplicates)
    243 {
    244     prependOrMoveToLastWithDuplicates<LinkedHashSet<int> >();
    245 }
    246 
    247 class DummyRefCounted: public WTF::RefCounted<DummyRefCounted> {
    248 public:
    249     DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { m_isDeleted = false; }
    250     ~DummyRefCounted() { m_isDeleted = true; }
    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>
    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 
    296 TEST(ListHashSetTest, WithRefPtr)
    297 {
    298     withRefPtr<ListHashSet<RefPtr<DummyRefCounted> > >();
    299     withRefPtr<ListHashSet<RefPtr<DummyRefCounted>, 1> >();
    300 }
    301 
    302 TEST(LinkedHashSetTest, WithRefPtr)
    303 {
    304     withRefPtr<LinkedHashSet<RefPtr<DummyRefCounted> > >();
    305 }
    306 
    307 template<typename Set, typename SetRef, typename Iterator>
    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 
    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 
    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>
    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 
    387 TEST(ListHashSetTest, InsertBefore)
    388 {
    389     insertBeforeHelper<ListHashSet<int> >(true);
    390     insertBeforeHelper<ListHashSet<int, 1> >(true);
    391 }
    392 
    393 TEST(LinkedHashSetTest, InsertBefore)
    394 {
    395     insertBeforeHelper<LinkedHashSet<int> >(false);
    396 }
    397 
    398 template<typename Set>
    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 
    445 TEST(ListHashSetTest, AddReturnIterator)
    446 {
    447     addReturnIterator<ListHashSet<int> >(true);
    448     addReturnIterator<ListHashSet<int, 1> >(true);
    449 }
    450 
    451 TEST(LinkedHashSetTest, AddReturnIterator)
    452 {
    453     addReturnIterator<LinkedHashSet<int> >(false);
    454 }
    455 
    456 template<typename Set>
    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 
    493 TEST(ListHashSetTest, ExcerciseValuePeekInType)
    494 {
    495     excerciseValuePeekInType<ListHashSet<RefPtr<DummyRefCounted> > >();
    496     excerciseValuePeekInType<ListHashSet<RefPtr<DummyRefCounted>, 1> >();
    497 }
    498 
    499 TEST(LinkedHashSetTest, ExcerciseValuePeekInType)
    500 {
    501     excerciseValuePeekInType<LinkedHashSet<RefPtr<DummyRefCounted> > >();
    502 }
    503 
    504 struct Simple {
    505     Simple(int value) : m_value(value) { };
    506     int m_value;
    507 };
    508 
    509 struct Complicated {
    510     Complicated(int value) : m_simple(value)
    511     {
    512         s_objectsConstructed++;
    513     }
    514 
    515     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 {
    530     static unsigned hash(const Complicated& key) { return key.m_simple.m_value; }
    531     static bool equal(const Complicated& a, const Complicated& b) { return a.m_simple.m_value == b.m_simple.m_value; }
    532 };
    533 struct ComplexityTranslator {
    534     static unsigned hash(const Simple& key) { return key.m_value; }
    535     static bool equal(const Complicated& a, const Simple& b) { return a.m_simple.m_value == b.m_value; }
    536 };
    537 
    538 template<typename Set>
    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 
    564 TEST(ListHashSetTest, ComplexityTranslator)
    565 {
    566     translatorTest<ListHashSet<Complicated, 256, ComplicatedHashFunctions> >();
    567     translatorTest<ListHashSet<Complicated, 1, ComplicatedHashFunctions> >();
    568 }
    569 
    570 TEST(LinkedHashSetTest, ComplexityTranslator)
    571 {
    572     translatorTest<LinkedHashSet<Complicated, ComplicatedHashFunctions> >();
    573 }
    574 
    575 struct Dummy {
    576     Dummy(bool& deleted) : deleted(deleted) { }
    577 
    578     ~Dummy()
    579     {
    580         deleted = true;
    581     }
    582 
    583     bool& deleted;
    584 };
    585 
    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>
    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 
    711 TEST(ListHashSetTest, Swap)
    712 {
    713     swapTestHelper<ListHashSet<int> >();
    714 }
    715 
    716 TEST(LinkedHashSetTest, Swap)
    717 {
    718     swapTestHelper<LinkedHashSet<int> >();
    719 }
    720 
    721 } // namespace
    722