third_party/WebKit/Source/wtf/ListHashSetTest.cpp

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