1 /* 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved. 3 * Copyright (C) 2011, Benjamin Poulain <ikipou (at) gmail.com> 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Library General Public 7 * License as published by the Free Software Foundation; either 8 * version 2 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Library General Public License for more details. 14 * 15 * You should have received a copy of the GNU Library General Public License 16 * along with this library; see the file COPYING.LIB. If not, write to 17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 18 * Boston, MA 02110-1301, USA. 19 * 20 */ 21 22 #ifndef WTF_LinkedHashSet_h 23 #define WTF_LinkedHashSet_h 24 25 #include "wtf/DefaultAllocator.h" 26 #include "wtf/HashSet.h" 27 #include "wtf/OwnPtr.h" 28 #include "wtf/PassOwnPtr.h" 29 30 namespace WTF { 31 32 // LinkedHashSet: Just like HashSet, this class provides a Set 33 // interface - a collection of unique objects with O(1) insertion, 34 // removal and test for containership. However, it also has an 35 // order - iterating it will always give back values in the order 36 // in which they are added. 37 38 // Unlike ListHashSet, but like most WTF collections, iteration is NOT safe 39 // against mutation of the LinkedHashSet. 40 41 template<typename Value, typename HashFunctions, typename HashTraits, typename Allocator> class LinkedHashSet; 42 43 template<typename LinkedHashSet> class LinkedHashSetIterator; 44 template<typename LinkedHashSet> class LinkedHashSetConstIterator; 45 template<typename LinkedHashSet> class LinkedHashSetReverseIterator; 46 template<typename LinkedHashSet> class LinkedHashSetConstReverseIterator; 47 48 template<typename Value, typename HashFunctions> struct LinkedHashSetTranslator; 49 template<typename Value> struct LinkedHashSetExtractor; 50 template<typename Value, typename ValueTraits> struct LinkedHashSetTraits; 51 52 class LinkedHashSetNodeBase { 53 public: 54 LinkedHashSetNodeBase() : m_prev(this), m_next(this) { } 55 56 void unlink() 57 { 58 if (!m_next) 59 return; 60 ASSERT(m_prev); 61 ASSERT(m_next->m_prev == this); 62 ASSERT(m_prev->m_next == this); 63 m_next->m_prev = m_prev; 64 m_prev->m_next = m_next; 65 } 66 67 ~LinkedHashSetNodeBase() 68 { 69 unlink(); 70 } 71 72 void insertBefore(LinkedHashSetNodeBase& other) 73 { 74 other.m_next = this; 75 other.m_prev = m_prev; 76 m_prev->m_next = &other; 77 m_prev = &other; 78 ASSERT(other.m_next); 79 ASSERT(other.m_prev); 80 ASSERT(m_next); 81 ASSERT(m_prev); 82 } 83 84 void insertAfter(LinkedHashSetNodeBase& other) 85 { 86 other.m_prev = this; 87 other.m_next = m_next; 88 m_next->m_prev = &other; 89 m_next = &other; 90 ASSERT(other.m_next); 91 ASSERT(other.m_prev); 92 ASSERT(m_next); 93 ASSERT(m_prev); 94 } 95 96 LinkedHashSetNodeBase(LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next) 97 : m_prev(prev) 98 , m_next(next) 99 { 100 ASSERT((prev && next) || (!prev && !next)); 101 } 102 103 LinkedHashSetNodeBase* m_prev; 104 LinkedHashSetNodeBase* m_next; 105 106 protected: 107 // If we take a copy of a node we can't copy the next and prev pointers, 108 // since they point to something that does not point at us. This is used 109 // inside the shouldExpand() "if" in HashTable::add. 110 LinkedHashSetNodeBase(const LinkedHashSetNodeBase& other) 111 : m_prev(0) 112 , m_next(0) { } 113 114 private: 115 // Should not be used. 116 LinkedHashSetNodeBase& operator=(const LinkedHashSetNodeBase& other); 117 }; 118 119 template<typename ValueArg> 120 class LinkedHashSetNode : public LinkedHashSetNodeBase { 121 public: 122 LinkedHashSetNode(const ValueArg& value, LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next) 123 : LinkedHashSetNodeBase(prev, next) 124 , m_value(value) 125 { 126 } 127 128 ValueArg m_value; 129 130 private: 131 // Not used. 132 LinkedHashSetNode(const LinkedHashSetNode&); 133 }; 134 135 template< 136 typename ValueArg, 137 typename HashFunctions = typename DefaultHash<ValueArg>::Hash, 138 typename TraitsArg = HashTraits<ValueArg>, 139 typename Allocator = DefaultAllocator> 140 class LinkedHashSet { 141 WTF_USE_ALLOCATOR(LinkedHashSet, Allocator); 142 private: 143 typedef ValueArg Value; 144 typedef TraitsArg Traits; 145 typedef LinkedHashSetNode<Value> Node; 146 typedef LinkedHashSetNodeBase NodeBase; 147 typedef LinkedHashSetTranslator<Value, HashFunctions> NodeHashFunctions; 148 typedef LinkedHashSetTraits<Value, Traits> NodeHashTraits; 149 150 typedef HashTable<Node, Node, IdentityExtractor, 151 NodeHashFunctions, NodeHashTraits, NodeHashTraits, Allocator> ImplType; 152 153 public: 154 typedef LinkedHashSetIterator<LinkedHashSet> iterator; 155 friend class LinkedHashSetIterator<LinkedHashSet>; 156 typedef LinkedHashSetConstIterator<LinkedHashSet> const_iterator; 157 friend class LinkedHashSetConstIterator<LinkedHashSet>; 158 159 typedef LinkedHashSetReverseIterator<LinkedHashSet> reverse_iterator; 160 friend class LinkedHashSetReverseIterator<LinkedHashSet>; 161 typedef LinkedHashSetConstReverseIterator<LinkedHashSet> const_reverse_iterator; 162 friend class LinkedHashSetConstReverseIterator<LinkedHashSet>; 163 164 struct AddResult { 165 AddResult(const typename ImplType::AddResult& hashTableAddResult) 166 : storedValue(&hashTableAddResult.storedValue->m_value) 167 , isNewEntry(hashTableAddResult.isNewEntry) 168 { 169 } 170 171 Value* storedValue; 172 bool isNewEntry; 173 }; 174 175 typedef typename HashTraits<Value>::PeekInType ValuePeekInType; 176 177 LinkedHashSet(); 178 LinkedHashSet(const LinkedHashSet&); 179 LinkedHashSet& operator=(const LinkedHashSet&); 180 181 // Needs finalization. The anchor needs to unlink itself from the chain. 182 ~LinkedHashSet(); 183 184 static void finalize(void* pointer) { reinterpret_cast<LinkedHashSet*>(pointer)->~LinkedHashSet(); } 185 186 void swap(LinkedHashSet&); 187 188 unsigned size() const { return m_impl.size(); } 189 unsigned capacity() const { return m_impl.capacity(); } 190 bool isEmpty() const { return m_impl.isEmpty(); } 191 192 iterator begin() { return makeIterator(firstNode()); } 193 iterator end() { return makeIterator(anchor()); } 194 const_iterator begin() const { return makeConstIterator(firstNode()); } 195 const_iterator end() const { return makeConstIterator(anchor()); } 196 197 reverse_iterator rbegin() { return makeReverseIterator(lastNode()); } 198 reverse_iterator rend() { return makeReverseIterator(anchor()); } 199 const_reverse_iterator rbegin() const { return makeConstReverseIterator(lastNode()); } 200 const_reverse_iterator rend() const { return makeConstReverseIterator(anchor()); } 201 202 Value& first(); 203 const Value& first() const; 204 void removeFirst(); 205 206 Value& last(); 207 const Value& last() const; 208 void removeLast(); 209 210 iterator find(ValuePeekInType); 211 const_iterator find(ValuePeekInType) const; 212 bool contains(ValuePeekInType) const; 213 214 // An alternate version of find() that finds the object by hashing and comparing 215 // with some other type, to avoid the cost of type conversion. 216 // The HashTranslator interface is defined in HashSet. 217 template<typename HashTranslator, typename T> iterator find(const T&); 218 template<typename HashTranslator, typename T> const_iterator find(const T&) const; 219 template<typename HashTranslator, typename T> bool contains(const T&) const; 220 221 // The return value of add is a pair of a pointer to the stored value, 222 // and a bool that is true if an new entry was added. 223 AddResult add(ValuePeekInType); 224 225 // Same as add() except that the return value is an 226 // iterator. Useful in cases where it's needed to have the 227 // same return value as find() and where it's not possible to 228 // use a pointer to the storedValue. 229 iterator addReturnIterator(ValuePeekInType); 230 231 // Add the value to the end of the collection. If the value was already in 232 // the list, it is moved to the end. 233 AddResult appendOrMoveToLast(ValuePeekInType); 234 235 // Add the value to the beginning of the collection. If the value was already in 236 // the list, it is moved to the beginning. 237 AddResult prependOrMoveToFirst(ValuePeekInType); 238 239 AddResult insertBefore(ValuePeekInType beforeValue, ValuePeekInType newValue); 240 AddResult insertBefore(iterator it, ValuePeekInType newValue) { return m_impl.template add<NodeHashFunctions>(newValue, it.node()); } 241 242 void remove(ValuePeekInType); 243 void remove(iterator); 244 void clear() { m_impl.clear(); } 245 template<typename Collection> 246 void removeAll(const Collection& other) { WTF::removeAll(*this, other); } 247 248 void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor); } 249 250 int64_t modifications() const { return m_impl.modifications(); } 251 void checkModifications(int64_t mods) const { m_impl.checkModifications(mods); } 252 253 private: 254 Node* anchor() { return reinterpret_cast<Node*>(&m_anchor); } 255 const Node* anchor() const { return reinterpret_cast<const Node*>(&m_anchor); } 256 Node* firstNode() { return reinterpret_cast<Node*>(m_anchor.m_next); } 257 const Node* firstNode() const { return reinterpret_cast<const Node*>(m_anchor.m_next); } 258 Node* lastNode() { return reinterpret_cast<Node*>(m_anchor.m_prev); } 259 const Node* lastNode() const { return reinterpret_cast<const Node*>(m_anchor.m_prev); } 260 261 iterator makeIterator(const Node* position) { return iterator(position, this); } 262 const_iterator makeConstIterator(const Node* position) const { return const_iterator(position, this); } 263 reverse_iterator makeReverseIterator(const Node* position) { return reverse_iterator(position, this); } 264 const_reverse_iterator makeConstReverseIterator(const Node* position) const { return const_reverse_iterator(position, this); } 265 266 ImplType m_impl; 267 NodeBase m_anchor; 268 #ifndef ASSERT_ENABLED 269 uint64_t m_modifications; 270 #endif 271 }; 272 273 template<typename Value, typename HashFunctions> 274 struct LinkedHashSetTranslator { 275 typedef LinkedHashSetNode<Value> Node; 276 typedef LinkedHashSetNodeBase NodeBase; 277 typedef typename HashTraits<Value>::PeekInType ValuePeekInType; 278 static unsigned hash(const Node& node) { return HashFunctions::hash(node.m_value); } 279 static unsigned hash(const ValuePeekInType& key) { return HashFunctions::hash(key); } 280 static bool equal(const Node& a, const ValuePeekInType& b) { return HashFunctions::equal(a.m_value, b); } 281 static bool equal(const Node& a, const Node& b) { return HashFunctions::equal(a.m_value, b.m_value); } 282 static void translate(Node& location, ValuePeekInType key, NodeBase* anchor) 283 { 284 location.m_value = key; 285 anchor->insertBefore(location); 286 } 287 288 // Empty (or deleted) slots have the m_next pointer set to null, but we 289 // don't do anything to the other fields, which may contain junk. 290 // Therefore you can't compare a newly constructed empty value with a 291 // slot and get the right answer. 292 static const bool safeToCompareToEmptyOrDeleted = false; 293 }; 294 295 template<typename Value> 296 struct LinkedHashSetExtractor { 297 static const Value& extract(const LinkedHashSetNode<Value>& node) { return node.m_value; } 298 }; 299 300 template<typename Value, typename ValueTraitsArg> 301 struct LinkedHashSetTraits : public SimpleClassHashTraits<LinkedHashSetNode<Value> > { 302 typedef LinkedHashSetNode<Value> Node; 303 typedef ValueTraitsArg ValueTraits; 304 305 // The slot is empty when the m_next field is zero so it's safe to zero 306 // the backing. 307 static const bool emptyValueIsZero = true; 308 309 static const bool hasIsEmptyValueFunction = true; 310 static bool isEmptyValue(const Node& node) { return !node.m_next; } 311 312 static const int deletedValue = -1; 313 314 static void constructDeletedValue(Node& slot) { slot.m_next = reinterpret_cast<Node*>(deletedValue); } 315 static bool isDeletedValue(const Node& slot) { return slot.m_next == reinterpret_cast<Node*>(deletedValue); } 316 317 // We always need to call destructors, that's how we get linked and 318 // unlinked from the chain. 319 static const bool needsDestruction = true; 320 321 // Whether we need to trace and do weak processing depends on the traits of 322 // the type inside the node. 323 template<typename U = void> 324 struct NeedsTracingLazily { 325 static const bool value = ValueTraits::template NeedsTracingLazily<>::value; 326 }; 327 static const WeakHandlingFlag weakHandlingFlag = ValueTraits::weakHandlingFlag; 328 template<typename Visitor> 329 static bool shouldRemoveFromCollection(Visitor* visitor, LinkedHashSetNode<Value>& node) 330 { 331 return ValueTraits::shouldRemoveFromCollection(visitor, node.m_value); 332 } 333 }; 334 335 template<typename LinkedHashSetType> 336 class LinkedHashSetIterator { 337 private: 338 typedef typename LinkedHashSetType::Node Node; 339 typedef typename LinkedHashSetType::Traits Traits; 340 341 typedef typename LinkedHashSetType::Value& ReferenceType; 342 typedef typename LinkedHashSetType::Value* PointerType; 343 344 typedef LinkedHashSetConstIterator<LinkedHashSetType> const_iterator; 345 346 Node* node() { return const_cast<Node*>(m_iterator.node()); } 347 348 protected: 349 LinkedHashSetIterator(const Node* position, LinkedHashSetType* m_container) 350 : m_iterator(position , m_container) 351 { 352 } 353 354 public: 355 // Default copy, assignment and destructor are OK. 356 357 PointerType get() const { return const_cast<PointerType>(m_iterator.get()); } 358 ReferenceType operator*() const { return *get(); } 359 PointerType operator->() const { return get(); } 360 361 LinkedHashSetIterator& operator++() { ++m_iterator; return *this; } 362 LinkedHashSetIterator& operator--() { --m_iterator; return *this; } 363 364 // Postfix ++ and -- intentionally omitted. 365 366 // Comparison. 367 bool operator==(const LinkedHashSetIterator& other) const { return m_iterator == other.m_iterator; } 368 bool operator!=(const LinkedHashSetIterator& other) const { return m_iterator != other.m_iterator; } 369 370 operator const_iterator() const { return m_iterator; } 371 372 protected: 373 const_iterator m_iterator; 374 template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 375 }; 376 377 template<typename LinkedHashSetType> 378 class LinkedHashSetConstIterator { 379 private: 380 typedef typename LinkedHashSetType::Node Node; 381 typedef typename LinkedHashSetType::Traits Traits; 382 383 typedef const typename LinkedHashSetType::Value& ReferenceType; 384 typedef const typename LinkedHashSetType::Value* PointerType; 385 386 const Node* node() const { return static_cast<const Node*>(m_position); } 387 388 protected: 389 LinkedHashSetConstIterator(const LinkedHashSetNodeBase* position, const LinkedHashSetType* container) 390 : m_position(position) 391 #ifdef ASSERT_ENABLED 392 , m_container(container) 393 , m_containerModifications(container->modifications()) 394 #endif 395 { 396 } 397 398 public: 399 PointerType get() const 400 { 401 checkModifications(); 402 return &static_cast<const Node*>(m_position)->m_value; 403 } 404 ReferenceType operator*() const { return *get(); } 405 PointerType operator->() const { return get(); } 406 407 LinkedHashSetConstIterator& operator++() 408 { 409 ASSERT(m_position); 410 checkModifications(); 411 m_position = m_position->m_next; 412 return *this; 413 } 414 415 LinkedHashSetConstIterator& operator--() 416 { 417 ASSERT(m_position); 418 checkModifications(); 419 m_position = m_position->m_prev; 420 return *this; 421 } 422 423 // Postfix ++ and -- intentionally omitted. 424 425 // Comparison. 426 bool operator==(const LinkedHashSetConstIterator& other) const 427 { 428 return m_position == other.m_position; 429 } 430 bool operator!=(const LinkedHashSetConstIterator& other) const 431 { 432 return m_position != other.m_position; 433 } 434 435 private: 436 const LinkedHashSetNodeBase* m_position; 437 #ifdef ASSERT_ENABLED 438 void checkModifications() const { m_container->checkModifications(m_containerModifications); } 439 const LinkedHashSetType* m_container; 440 int64_t m_containerModifications; 441 #else 442 void checkModifications() const { } 443 #endif 444 template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 445 friend class LinkedHashSetIterator<LinkedHashSetType>; 446 }; 447 448 template<typename LinkedHashSetType> 449 class LinkedHashSetReverseIterator : public LinkedHashSetIterator<LinkedHashSetType> { 450 typedef LinkedHashSetIterator<LinkedHashSetType> Superclass; 451 typedef LinkedHashSetConstReverseIterator<LinkedHashSetType> const_reverse_iterator; 452 typedef typename LinkedHashSetType::Node Node; 453 454 protected: 455 LinkedHashSetReverseIterator(const Node* position, LinkedHashSetType* container) 456 : Superclass(position, container) { } 457 458 public: 459 LinkedHashSetReverseIterator& operator++() { Superclass::operator--(); return *this; } 460 LinkedHashSetReverseIterator& operator--() { Superclass::operator++(); return *this; } 461 462 // Postfix ++ and -- intentionally omitted. 463 464 operator const_reverse_iterator() const { return *reinterpret_cast<const_reverse_iterator*>(this); } 465 466 template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 467 }; 468 469 template<typename LinkedHashSetType> 470 class LinkedHashSetConstReverseIterator : public LinkedHashSetConstIterator<LinkedHashSetType> { 471 typedef LinkedHashSetConstIterator<LinkedHashSetType> Superclass; 472 typedef typename LinkedHashSetType::Node Node; 473 474 public: 475 LinkedHashSetConstReverseIterator(const Node* position, const LinkedHashSetType* container) 476 : Superclass(position, container) { } 477 478 LinkedHashSetConstReverseIterator& operator++() { Superclass::operator--(); return *this; } 479 LinkedHashSetConstReverseIterator& operator--() { Superclass::operator++(); return *this; } 480 481 // Postfix ++ and -- intentionally omitted. 482 483 template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 484 }; 485 486 template<typename T, typename U, typename V, typename W> 487 inline LinkedHashSet<T, U, V, W>::LinkedHashSet() { } 488 489 template<typename T, typename U, typename V, typename W> 490 inline LinkedHashSet<T, U, V, W>::LinkedHashSet(const LinkedHashSet& other) 491 : m_anchor() 492 { 493 const_iterator end = other.end(); 494 for (const_iterator it = other.begin(); it != end; ++it) 495 add(*it); 496 } 497 498 template<typename T, typename U, typename V, typename W> 499 inline LinkedHashSet<T, U, V, W>& LinkedHashSet<T, U, V, W>::operator=(const LinkedHashSet& other) 500 { 501 LinkedHashSet tmp(other); 502 swap(tmp); 503 return *this; 504 } 505 506 template<typename T, typename U, typename V, typename W> 507 inline void LinkedHashSet<T, U, V, W>::swap(LinkedHashSet& other) 508 { 509 m_impl.swap(other.m_impl); 510 swap(m_anchor, other.m_anchor); 511 } 512 513 template<typename T, typename U, typename V, typename Allocator> 514 inline LinkedHashSet<T, U, V, Allocator>::~LinkedHashSet() 515 { 516 // The destructor of m_anchor will implicitly be called here, which will 517 // unlink the anchor from the collection. 518 } 519 520 template<typename T, typename U, typename V, typename W> 521 inline T& LinkedHashSet<T, U, V, W>::first() 522 { 523 ASSERT(!isEmpty()); 524 return firstNode()->m_value; 525 } 526 527 template<typename T, typename U, typename V, typename W> 528 inline const T& LinkedHashSet<T, U, V, W>::first() const 529 { 530 ASSERT(!isEmpty()); 531 return firstNode()->m_value; 532 } 533 534 template<typename T, typename U, typename V, typename W> 535 inline void LinkedHashSet<T, U, V, W>::removeFirst() 536 { 537 ASSERT(!isEmpty()); 538 m_impl.remove(static_cast<Node*>(m_anchor.m_next)); 539 } 540 541 template<typename T, typename U, typename V, typename W> 542 inline T& LinkedHashSet<T, U, V, W>::last() 543 { 544 ASSERT(!isEmpty()); 545 return lastNode()->m_value; 546 } 547 548 template<typename T, typename U, typename V, typename W> 549 inline const T& LinkedHashSet<T, U, V, W>::last() const 550 { 551 ASSERT(!isEmpty()); 552 return lastNode()->m_value; 553 } 554 555 template<typename T, typename U, typename V, typename W> 556 inline void LinkedHashSet<T, U, V, W>::removeLast() 557 { 558 ASSERT(!isEmpty()); 559 m_impl.remove(static_cast<Node*>(m_anchor.m_prev)); 560 } 561 562 template<typename T, typename U, typename V, typename W> 563 inline typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value) 564 { 565 LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value); 566 if (!node) 567 return end(); 568 return makeIterator(node); 569 } 570 571 template<typename T, typename U, typename V, typename W> 572 inline typename LinkedHashSet<T, U, V, W>::const_iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value) const 573 { 574 const LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value); 575 if (!node) 576 return end(); 577 return makeConstIterator(node); 578 } 579 580 template<typename Translator> 581 struct LinkedHashSetTranslatorAdapter { 582 template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); } 583 template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a.m_value, b); } 584 }; 585 586 template<typename Value, typename U, typename V, typename W> 587 template<typename HashTranslator, typename T> 588 inline typename LinkedHashSet<Value, U, V, W>::iterator LinkedHashSet<Value, U, V, W>::find(const T& value) 589 { 590 typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions; 591 const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value); 592 if (!node) 593 return end(); 594 return makeIterator(node); 595 } 596 597 template<typename Value, typename U, typename V, typename W> 598 template<typename HashTranslator, typename T> 599 inline typename LinkedHashSet<Value, U, V, W>::const_iterator LinkedHashSet<Value, U, V, W>::find(const T& value) const 600 { 601 typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions; 602 const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value); 603 if (!node) 604 return end(); 605 return makeConstIterator(node); 606 } 607 608 template<typename Value, typename U, typename V, typename W> 609 template<typename HashTranslator, typename T> 610 inline bool LinkedHashSet<Value, U, V, W>::contains(const T& value) const 611 { 612 return m_impl.template contains<LinkedHashSetTranslatorAdapter<HashTranslator> >(value); 613 } 614 615 template<typename T, typename U, typename V, typename W> 616 inline bool LinkedHashSet<T, U, V, W>::contains(ValuePeekInType value) const 617 { 618 return m_impl.template contains<NodeHashFunctions>(value); 619 } 620 621 template<typename Value, typename HashFunctions, typename Traits, typename Allocator> 622 typename LinkedHashSet<Value, HashFunctions, Traits, Allocator>::AddResult LinkedHashSet<Value, HashFunctions, Traits, Allocator>::add(ValuePeekInType value) 623 { 624 return m_impl.template add<NodeHashFunctions>(value, &m_anchor); 625 } 626 627 template<typename T, typename U, typename V, typename W> 628 typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::addReturnIterator(ValuePeekInType value) 629 { 630 typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, &m_anchor); 631 return makeIterator(result.storedValue); 632 } 633 634 template<typename T, typename U, typename V, typename W> 635 typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::appendOrMoveToLast(ValuePeekInType value) 636 { 637 typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, &m_anchor); 638 Node* node = result.storedValue; 639 if (!result.isNewEntry) { 640 node->unlink(); 641 m_anchor.insertBefore(*node); 642 } 643 return result; 644 } 645 646 template<typename T, typename U, typename V, typename W> 647 typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::prependOrMoveToFirst(ValuePeekInType value) 648 { 649 typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, m_anchor.m_next); 650 Node* node = result.storedValue; 651 if (!result.isNewEntry) { 652 node->unlink(); 653 m_anchor.insertAfter(*node); 654 } 655 return result; 656 } 657 658 template<typename T, typename U, typename V, typename W> 659 typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::insertBefore(ValuePeekInType beforeValue, ValuePeekInType newValue) 660 { 661 return insertBefore(find(beforeValue), newValue); 662 } 663 664 template<typename T, typename U, typename V, typename W> 665 inline void LinkedHashSet<T, U, V, W>::remove(iterator it) 666 { 667 if (it == end()) 668 return; 669 m_impl.remove(it.node()); 670 } 671 672 template<typename T, typename U, typename V, typename W> 673 inline void LinkedHashSet<T, U, V, W>::remove(ValuePeekInType value) 674 { 675 remove(find(value)); 676 } 677 678 inline void swap(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b) 679 { 680 swap(a.m_prev, b.m_prev); 681 swap(a.m_next, b.m_next); 682 if (b.m_next) { 683 b.m_next->m_prev = &b; 684 b.m_prev->m_next = &b; 685 } 686 if (a.m_next) { 687 a.m_next->m_prev = &a; 688 a.m_prev->m_next = &a; 689 } 690 } 691 692 template<typename T> 693 inline void swap(LinkedHashSetNode<T>& a, LinkedHashSetNode<T>& b) 694 { 695 typedef LinkedHashSetNodeBase Base; 696 697 swap(static_cast<Base&>(a), static_cast<Base&>(b)); 698 swap(a.m_value, b.m_value); 699 } 700 701 // Warning: After and while calling this you have a collection with deleted 702 // pointers. Consider using a smart pointer like OwnPtr and calling clear() 703 // instead. 704 template<typename ValueType, typename T, typename U> 705 void deleteAllValues(const LinkedHashSet<ValueType, T, U>& set) 706 { 707 typedef typename LinkedHashSet<ValueType, T, U>::const_iterator iterator; 708 iterator end = set.end(); 709 for (iterator it = set.begin(); it != end; ++it) 710 delete *it; 711 } 712 713 } 714 715 using WTF::LinkedHashSet; 716 717 #endif /* WTF_LinkedHashSet_h */ 718