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; 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 } // namespace 660
