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, typename Allocator> struct LinkedHashSetTranslator; 49 template<typename Value, typename Allocator> struct LinkedHashSetExtractor; 50 template<typename Value, typename ValueTraits, typename Allocator> 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, typename Allocator> 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, Allocator> Node; 146 typedef LinkedHashSetNodeBase NodeBase; 147 typedef LinkedHashSetTranslator<Value, HashFunctions, Allocator> NodeHashFunctions; 148 typedef LinkedHashSetTraits<Value, Traits, Allocator> 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 }; 269 270 template<typename Value, typename HashFunctions, typename Allocator> 271 struct LinkedHashSetTranslator { 272 typedef LinkedHashSetNode<Value, Allocator> Node; 273 typedef LinkedHashSetNodeBase NodeBase; 274 typedef typename HashTraits<Value>::PeekInType ValuePeekInType; 275 static unsigned hash(const Node& node) { return HashFunctions::hash(node.m_value); } 276 static unsigned hash(const ValuePeekInType& key) { return HashFunctions::hash(key); } 277 static bool equal(const Node& a, const ValuePeekInType& b) { return HashFunctions::equal(a.m_value, b); } 278 static bool equal(const Node& a, const Node& b) { return HashFunctions::equal(a.m_value, b.m_value); } 279 static void translate(Node& location, ValuePeekInType key, NodeBase* anchor) 280 { 281 anchor->insertBefore(location); 282 location.m_value = key; 283 } 284 285 // Empty (or deleted) slots have the m_next pointer set to null, but we 286 // don't do anything to the other fields, which may contain junk. 287 // Therefore you can't compare a newly constructed empty value with a 288 // slot and get the right answer. 289 static const bool safeToCompareToEmptyOrDeleted = false; 290 }; 291 292 template<typename Value, typename Allocator> 293 struct LinkedHashSetExtractor { 294 static const Value& extract(const LinkedHashSetNode<Value, Allocator>& node) { return node.m_value; } 295 }; 296 297 template<typename Value, typename ValueTraitsArg, typename Allocator> 298 struct LinkedHashSetTraits : public SimpleClassHashTraits<LinkedHashSetNode<Value, Allocator> > { 299 typedef LinkedHashSetNode<Value, Allocator> Node; 300 typedef ValueTraitsArg ValueTraits; 301 302 // The slot is empty when the m_next field is zero so it's safe to zero 303 // the backing. 304 static const bool emptyValueIsZero = true; 305 306 static const bool hasIsEmptyValueFunction = true; 307 static bool isEmptyValue(const Node& node) { return !node.m_next; } 308 309 static const int deletedValue = -1; 310 311 static void constructDeletedValue(Node& slot, bool) { slot.m_next = reinterpret_cast<Node*>(deletedValue); } 312 static bool isDeletedValue(const Node& slot) { return slot.m_next == reinterpret_cast<Node*>(deletedValue); } 313 314 // We always need to call destructors, that's how we get linked and 315 // unlinked from the chain. 316 static const bool needsDestruction = true; 317 318 // Whether we need to trace and do weak processing depends on the traits of 319 // the type inside the node. 320 template<typename U = void> 321 struct NeedsTracingLazily { 322 static const bool value = ValueTraits::template NeedsTracingLazily<>::value; 323 }; 324 static const WeakHandlingFlag weakHandlingFlag = ValueTraits::weakHandlingFlag; 325 }; 326 327 template<typename LinkedHashSetType> 328 class LinkedHashSetIterator { 329 private: 330 typedef typename LinkedHashSetType::Node Node; 331 typedef typename LinkedHashSetType::Traits Traits; 332 333 typedef typename LinkedHashSetType::Value& ReferenceType; 334 typedef typename LinkedHashSetType::Value* PointerType; 335 336 typedef LinkedHashSetConstIterator<LinkedHashSetType> const_iterator; 337 338 Node* node() { return const_cast<Node*>(m_iterator.node()); } 339 340 protected: 341 LinkedHashSetIterator(const Node* position, LinkedHashSetType* m_container) 342 : m_iterator(position , m_container) 343 { 344 } 345 346 public: 347 // Default copy, assignment and destructor are OK. 348 349 PointerType get() const { return const_cast<PointerType>(m_iterator.get()); } 350 ReferenceType operator*() const { return *get(); } 351 PointerType operator->() const { return get(); } 352 353 LinkedHashSetIterator& operator++() { ++m_iterator; return *this; } 354 LinkedHashSetIterator& operator--() { --m_iterator; return *this; } 355 356 // Postfix ++ and -- intentionally omitted. 357 358 // Comparison. 359 bool operator==(const LinkedHashSetIterator& other) const { return m_iterator == other.m_iterator; } 360 bool operator!=(const LinkedHashSetIterator& other) const { return m_iterator != other.m_iterator; } 361 362 operator const_iterator() const { return m_iterator; } 363 364 protected: 365 const_iterator m_iterator; 366 template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 367 }; 368 369 template<typename LinkedHashSetType> 370 class LinkedHashSetConstIterator { 371 private: 372 typedef typename LinkedHashSetType::Node Node; 373 typedef typename LinkedHashSetType::Traits Traits; 374 375 typedef const typename LinkedHashSetType::Value& ReferenceType; 376 typedef const typename LinkedHashSetType::Value* PointerType; 377 378 const Node* node() const { return static_cast<const Node*>(m_position); } 379 380 protected: 381 LinkedHashSetConstIterator(const LinkedHashSetNodeBase* position, const LinkedHashSetType* container) 382 : m_position(position) 383 #if ENABLE(ASSERT) 384 , m_container(container) 385 , m_containerModifications(container->modifications()) 386 #endif 387 { 388 } 389 390 public: 391 PointerType get() const 392 { 393 checkModifications(); 394 return &static_cast<const Node*>(m_position)->m_value; 395 } 396 ReferenceType operator*() const { return *get(); } 397 PointerType operator->() const { return get(); } 398 399 LinkedHashSetConstIterator& operator++() 400 { 401 ASSERT(m_position); 402 checkModifications(); 403 m_position = m_position->m_next; 404 return *this; 405 } 406 407 LinkedHashSetConstIterator& operator--() 408 { 409 ASSERT(m_position); 410 checkModifications(); 411 m_position = m_position->m_prev; 412 return *this; 413 } 414 415 // Postfix ++ and -- intentionally omitted. 416 417 // Comparison. 418 bool operator==(const LinkedHashSetConstIterator& other) const 419 { 420 return m_position == other.m_position; 421 } 422 bool operator!=(const LinkedHashSetConstIterator& other) const 423 { 424 return m_position != other.m_position; 425 } 426 427 private: 428 const LinkedHashSetNodeBase* m_position; 429 #if ENABLE(ASSERT) 430 void checkModifications() const { m_container->checkModifications(m_containerModifications); } 431 const LinkedHashSetType* m_container; 432 int64_t m_containerModifications; 433 #else 434 void checkModifications() const { } 435 #endif 436 template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 437 friend class LinkedHashSetIterator<LinkedHashSetType>; 438 }; 439 440 template<typename LinkedHashSetType> 441 class LinkedHashSetReverseIterator : public LinkedHashSetIterator<LinkedHashSetType> { 442 typedef LinkedHashSetIterator<LinkedHashSetType> Superclass; 443 typedef LinkedHashSetConstReverseIterator<LinkedHashSetType> const_reverse_iterator; 444 typedef typename LinkedHashSetType::Node Node; 445 446 protected: 447 LinkedHashSetReverseIterator(const Node* position, LinkedHashSetType* container) 448 : Superclass(position, container) { } 449 450 public: 451 LinkedHashSetReverseIterator& operator++() { Superclass::operator--(); return *this; } 452 LinkedHashSetReverseIterator& operator--() { Superclass::operator++(); return *this; } 453 454 // Postfix ++ and -- intentionally omitted. 455 456 operator const_reverse_iterator() const { return *reinterpret_cast<const_reverse_iterator*>(this); } 457 458 template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 459 }; 460 461 template<typename LinkedHashSetType> 462 class LinkedHashSetConstReverseIterator : public LinkedHashSetConstIterator<LinkedHashSetType> { 463 typedef LinkedHashSetConstIterator<LinkedHashSetType> Superclass; 464 typedef typename LinkedHashSetType::Node Node; 465 466 public: 467 LinkedHashSetConstReverseIterator(const Node* position, const LinkedHashSetType* container) 468 : Superclass(position, container) { } 469 470 LinkedHashSetConstReverseIterator& operator++() { Superclass::operator--(); return *this; } 471 LinkedHashSetConstReverseIterator& operator--() { Superclass::operator++(); return *this; } 472 473 // Postfix ++ and -- intentionally omitted. 474 475 template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 476 }; 477 478 template<typename T, typename U, typename V, typename W> 479 inline LinkedHashSet<T, U, V, W>::LinkedHashSet() { } 480 481 template<typename T, typename U, typename V, typename W> 482 inline LinkedHashSet<T, U, V, W>::LinkedHashSet(const LinkedHashSet& other) 483 : m_anchor() 484 { 485 const_iterator end = other.end(); 486 for (const_iterator it = other.begin(); it != end; ++it) 487 add(*it); 488 } 489 490 template<typename T, typename U, typename V, typename W> 491 inline LinkedHashSet<T, U, V, W>& LinkedHashSet<T, U, V, W>::operator=(const LinkedHashSet& other) 492 { 493 LinkedHashSet tmp(other); 494 swap(tmp); 495 return *this; 496 } 497 498 template<typename T, typename U, typename V, typename W> 499 inline void LinkedHashSet<T, U, V, W>::swap(LinkedHashSet& other) 500 { 501 m_impl.swap(other.m_impl); 502 swapAnchor(m_anchor, other.m_anchor); 503 } 504 505 template<typename T, typename U, typename V, typename Allocator> 506 inline LinkedHashSet<T, U, V, Allocator>::~LinkedHashSet() 507 { 508 // The destructor of m_anchor will implicitly be called here, which will 509 // unlink the anchor from the collection. 510 } 511 512 template<typename T, typename U, typename V, typename W> 513 inline T& LinkedHashSet<T, U, V, W>::first() 514 { 515 ASSERT(!isEmpty()); 516 return firstNode()->m_value; 517 } 518 519 template<typename T, typename U, typename V, typename W> 520 inline const T& LinkedHashSet<T, U, V, W>::first() const 521 { 522 ASSERT(!isEmpty()); 523 return firstNode()->m_value; 524 } 525 526 template<typename T, typename U, typename V, typename W> 527 inline void LinkedHashSet<T, U, V, W>::removeFirst() 528 { 529 ASSERT(!isEmpty()); 530 m_impl.remove(static_cast<Node*>(m_anchor.m_next)); 531 } 532 533 template<typename T, typename U, typename V, typename W> 534 inline T& LinkedHashSet<T, U, V, W>::last() 535 { 536 ASSERT(!isEmpty()); 537 return lastNode()->m_value; 538 } 539 540 template<typename T, typename U, typename V, typename W> 541 inline const T& LinkedHashSet<T, U, V, W>::last() const 542 { 543 ASSERT(!isEmpty()); 544 return lastNode()->m_value; 545 } 546 547 template<typename T, typename U, typename V, typename W> 548 inline void LinkedHashSet<T, U, V, W>::removeLast() 549 { 550 ASSERT(!isEmpty()); 551 m_impl.remove(static_cast<Node*>(m_anchor.m_prev)); 552 } 553 554 template<typename T, typename U, typename V, typename W> 555 inline typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value) 556 { 557 LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value); 558 if (!node) 559 return end(); 560 return makeIterator(node); 561 } 562 563 template<typename T, typename U, typename V, typename W> 564 inline typename LinkedHashSet<T, U, V, W>::const_iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value) const 565 { 566 const LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value); 567 if (!node) 568 return end(); 569 return makeConstIterator(node); 570 } 571 572 template<typename Translator> 573 struct LinkedHashSetTranslatorAdapter { 574 template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); } 575 template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a.m_value, b); } 576 }; 577 578 template<typename Value, typename U, typename V, typename W> 579 template<typename HashTranslator, typename T> 580 inline typename LinkedHashSet<Value, U, V, W>::iterator LinkedHashSet<Value, U, V, W>::find(const T& value) 581 { 582 typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions; 583 const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value); 584 if (!node) 585 return end(); 586 return makeIterator(node); 587 } 588 589 template<typename Value, typename U, typename V, typename W> 590 template<typename HashTranslator, typename T> 591 inline typename LinkedHashSet<Value, U, V, W>::const_iterator LinkedHashSet<Value, U, V, W>::find(const T& value) const 592 { 593 typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions; 594 const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value); 595 if (!node) 596 return end(); 597 return makeConstIterator(node); 598 } 599 600 template<typename Value, typename U, typename V, typename W> 601 template<typename HashTranslator, typename T> 602 inline bool LinkedHashSet<Value, U, V, W>::contains(const T& value) const 603 { 604 return m_impl.template contains<LinkedHashSetTranslatorAdapter<HashTranslator> >(value); 605 } 606 607 template<typename T, typename U, typename V, typename W> 608 inline bool LinkedHashSet<T, U, V, W>::contains(ValuePeekInType value) const 609 { 610 return m_impl.template contains<NodeHashFunctions>(value); 611 } 612 613 template<typename Value, typename HashFunctions, typename Traits, typename Allocator> 614 typename LinkedHashSet<Value, HashFunctions, Traits, Allocator>::AddResult LinkedHashSet<Value, HashFunctions, Traits, Allocator>::add(ValuePeekInType value) 615 { 616 return m_impl.template add<NodeHashFunctions>(value, &m_anchor); 617 } 618 619 template<typename T, typename U, typename V, typename W> 620 typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::addReturnIterator(ValuePeekInType value) 621 { 622 typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, &m_anchor); 623 return makeIterator(result.storedValue); 624 } 625 626 template<typename T, typename U, typename V, typename W> 627 typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::appendOrMoveToLast(ValuePeekInType value) 628 { 629 typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, &m_anchor); 630 Node* node = result.storedValue; 631 if (!result.isNewEntry) { 632 node->unlink(); 633 m_anchor.insertBefore(*node); 634 } 635 return result; 636 } 637 638 template<typename T, typename U, typename V, typename W> 639 typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::prependOrMoveToFirst(ValuePeekInType value) 640 { 641 typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, m_anchor.m_next); 642 Node* node = result.storedValue; 643 if (!result.isNewEntry) { 644 node->unlink(); 645 m_anchor.insertAfter(*node); 646 } 647 return result; 648 } 649 650 template<typename T, typename U, typename V, typename W> 651 typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::insertBefore(ValuePeekInType beforeValue, ValuePeekInType newValue) 652 { 653 return insertBefore(find(beforeValue), newValue); 654 } 655 656 template<typename T, typename U, typename V, typename W> 657 inline void LinkedHashSet<T, U, V, W>::remove(iterator it) 658 { 659 if (it == end()) 660 return; 661 m_impl.remove(it.node()); 662 } 663 664 template<typename T, typename U, typename V, typename W> 665 inline void LinkedHashSet<T, U, V, W>::remove(ValuePeekInType value) 666 { 667 remove(find(value)); 668 } 669 670 inline void swapAnchor(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b) 671 { 672 ASSERT(a.m_prev && a.m_next && b.m_prev && b.m_next); 673 swap(a.m_prev, b.m_prev); 674 swap(a.m_next, b.m_next); 675 if (b.m_next == &a) { 676 ASSERT(b.m_prev == &a); 677 b.m_next = &b; 678 b.m_prev = &b; 679 } else { 680 b.m_next->m_prev = &b; 681 b.m_prev->m_next = &b; 682 } 683 if (a.m_next == &b) { 684 ASSERT(a.m_prev == &b); 685 a.m_next = &a; 686 a.m_prev = &a; 687 } else { 688 a.m_next->m_prev = &a; 689 a.m_prev->m_next = &a; 690 } 691 } 692 693 inline void swap(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b) 694 { 695 ASSERT(a.m_next != &a && b.m_next != &b); 696 swap(a.m_prev, b.m_prev); 697 swap(a.m_next, b.m_next); 698 if (b.m_next) { 699 b.m_next->m_prev = &b; 700 b.m_prev->m_next = &b; 701 } 702 if (a.m_next) { 703 a.m_next->m_prev = &a; 704 a.m_prev->m_next = &a; 705 } 706 } 707 708 template<typename T, typename Allocator> 709 inline void swap(LinkedHashSetNode<T, Allocator>& a, LinkedHashSetNode<T, Allocator>& b) 710 { 711 typedef LinkedHashSetNodeBase Base; 712 Allocator::enterNoAllocationScope(); 713 swap(static_cast<Base&>(a), static_cast<Base&>(b)); 714 swap(a.m_value, b.m_value); 715 Allocator::leaveNoAllocationScope(); 716 } 717 718 // Warning: After and while calling this you have a collection with deleted 719 // pointers. Consider using a smart pointer like OwnPtr and calling clear() 720 // instead. 721 template<typename ValueType, typename T, typename U> 722 void deleteAllValues(const LinkedHashSet<ValueType, T, U>& set) 723 { 724 typedef typename LinkedHashSet<ValueType, T, U>::const_iterator iterator; 725 iterator end = set.end(); 726 for (iterator it = set.begin(); it != end; ++it) 727 delete *it; 728 } 729 730 #if !ENABLE(OILPAN) 731 template<typename T, typename U, typename V> 732 struct NeedsTracing<LinkedHashSet<T, U, V> > { 733 static const bool value = false; 734 }; 735 #endif 736 737 } 738 739 using WTF::LinkedHashSet; 740 741 #endif /* WTF_LinkedHashSet_h */ 742