third_party/WebKit/Source/wtf/LinkedHashSet.h

   1 /*
   2  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
   3  * Copyright (C) 2011, Benjamin Poulain <ikipou@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/AddressSanitizer.h"
  26 #include "wtf/DefaultAllocator.h"
  27 #include "wtf/HashSet.h"
  28 #include "wtf/OwnPtr.h"
  29 #include "wtf/PassOwnPtr.h"
  30
  31 namespace WTF {
  32
  33 // LinkedHashSet: Just like HashSet, this class provides a Set
  34 // interface - a collection of unique objects with O(1) insertion,
  35 // removal and test for containership. However, it also has an
  36 // order - iterating it will always give back values in the order
  37 // in which they are added.
  38
  39 // Unlike ListHashSet, but like most WTF collections, iteration is NOT safe
  40 // against mutation of the LinkedHashSet.
  41
  42 template<typename Value, typename HashFunctions, typename HashTraits, typename Allocator> class LinkedHashSet;
  43
  44 template<typename LinkedHashSet> class LinkedHashSetIterator;
  45 template<typename LinkedHashSet> class LinkedHashSetConstIterator;
  46 template<typename LinkedHashSet> class LinkedHashSetReverseIterator;
  47 template<typename LinkedHashSet> class LinkedHashSetConstReverseIterator;
  48
  49 template<typename Value, typename HashFunctions, typename Allocator> struct LinkedHashSetTranslator;
  50 template<typename Value, typename Allocator> struct LinkedHashSetExtractor;
  51 template<typename Value, typename ValueTraits, typename Allocator> struct LinkedHashSetTraits;
  52
  53 class LinkedHashSetNodeBase {
  54 public:
  55     LinkedHashSetNodeBase() : m_prev(this), m_next(this) { }
  56
  57     NO_LAZY_SWEEP_SANITIZE_ADDRESS
  58     void unlink()
  59     {
  60         if (!m_next)
  61             return;
  62         ASSERT(m_prev);
  63         ASSERT(m_next->m_prev == this);
  64         ASSERT(m_prev->m_next == this);
  65         m_next->m_prev = m_prev;
  66         m_prev->m_next = m_next;
  67     }
  68
  69     ~LinkedHashSetNodeBase()
  70     {
  71         unlink();
  72     }
  73
  74     void insertBefore(LinkedHashSetNodeBase& other)
  75     {
  76         other.m_next = this;
  77         other.m_prev = m_prev;
  78         m_prev->m_next = &other;
  79         m_prev = &other;
  80         ASSERT(other.m_next);
  81         ASSERT(other.m_prev);
  82         ASSERT(m_next);
  83         ASSERT(m_prev);
  84     }
  85
  86     void insertAfter(LinkedHashSetNodeBase& other)
  87     {
  88         other.m_prev = this;
  89         other.m_next = m_next;
  90         m_next->m_prev = &other;
  91         m_next = &other;
  92         ASSERT(other.m_next);
  93         ASSERT(other.m_prev);
  94         ASSERT(m_next);
  95         ASSERT(m_prev);
  96     }
  97
  98     LinkedHashSetNodeBase(LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next)
  99         : m_prev(prev)
 100         , m_next(next)
 101     {
 102         ASSERT((prev && next) || (!prev && !next));
 103     }
 104
 105     LinkedHashSetNodeBase* m_prev;
 106     LinkedHashSetNodeBase* m_next;
 107
 108 protected:
 109     // If we take a copy of a node we can't copy the next and prev pointers,
 110     // since they point to something that does not point at us. This is used
 111     // inside the shouldExpand() "if" in HashTable::add.
 112     LinkedHashSetNodeBase(const LinkedHashSetNodeBase& other)
 113         : m_prev(0)
 114         , m_next(0) { }
 115
 116 private:
 117     // Should not be used.
 118     LinkedHashSetNodeBase& operator=(const LinkedHashSetNodeBase& other);
 119 };
 120
 121 template<typename ValueArg, typename Allocator>
 122 class LinkedHashSetNode : public LinkedHashSetNodeBase {
 123 public:
 124     LinkedHashSetNode(const ValueArg& value, LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next)
 125         : LinkedHashSetNodeBase(prev, next)
 126         , m_value(value)
 127     {
 128     }
 129
 130     ValueArg m_value;
 131
 132 private:
 133     // Not used.
 134     LinkedHashSetNode(const LinkedHashSetNode&);
 135 };
 136
 137 template<
 138     typename ValueArg,
 139     typename HashFunctions = typename DefaultHash<ValueArg>::Hash,
 140     typename TraitsArg = HashTraits<ValueArg>,
 141     typename Allocator = DefaultAllocator>
 142 class LinkedHashSet {
 143     WTF_USE_ALLOCATOR(LinkedHashSet, Allocator);
 144 private:
 145     typedef ValueArg Value;
 146     typedef TraitsArg Traits;
 147     typedef LinkedHashSetNode<Value, Allocator> Node;
 148     typedef LinkedHashSetNodeBase NodeBase;
 149     typedef LinkedHashSetTranslator<Value, HashFunctions, Allocator> NodeHashFunctions;
 150     typedef LinkedHashSetTraits<Value, Traits, Allocator> NodeHashTraits;
 151
 152     typedef HashTable<Node, Node, IdentityExtractor,
 153         NodeHashFunctions, NodeHashTraits, NodeHashTraits, Allocator> ImplType;
 154
 155 public:
 156     typedef LinkedHashSetIterator<LinkedHashSet> iterator;
 157     friend class LinkedHashSetIterator<LinkedHashSet>;
 158     typedef LinkedHashSetConstIterator<LinkedHashSet> const_iterator;
 159     friend class LinkedHashSetConstIterator<LinkedHashSet>;
 160
 161     typedef LinkedHashSetReverseIterator<LinkedHashSet> reverse_iterator;
 162     friend class LinkedHashSetReverseIterator<LinkedHashSet>;
 163     typedef LinkedHashSetConstReverseIterator<LinkedHashSet> const_reverse_iterator;
 164     friend class LinkedHashSetConstReverseIterator<LinkedHashSet>;
 165
 166     struct AddResult {
 167         AddResult(const typename ImplType::AddResult& hashTableAddResult)
 168             : storedValue(&hashTableAddResult.storedValue->m_value)
 169             , isNewEntry(hashTableAddResult.isNewEntry)
 170         {
 171         }
 172
 173         Value* storedValue;
 174         bool isNewEntry;
 175     };
 176
 177     typedef typename HashTraits<Value>::PeekInType ValuePeekInType;
 178
 179     LinkedHashSet();
 180     LinkedHashSet(const LinkedHashSet&);
 181     LinkedHashSet& operator=(const LinkedHashSet&);
 182
 183     // Needs finalization. The anchor needs to unlink itself from the chain.
 184     ~LinkedHashSet();
 185
 186     static void finalize(void* pointer) { reinterpret_cast<LinkedHashSet*>(pointer)->~LinkedHashSet(); }
 187     void finalizeGarbageCollectedObject() { finalize(this); }
 188
 189     void swap(LinkedHashSet&);
 190
 191     unsigned size() const { return m_impl.size(); }
 192     unsigned capacity() const { return m_impl.capacity(); }
 193     bool isEmpty() const { return m_impl.isEmpty(); }
 194
 195     iterator begin() { return makeIterator(firstNode()); }
 196     iterator end() { return makeIterator(anchor()); }
 197     const_iterator begin() const { return makeConstIterator(firstNode()); }
 198     const_iterator end() const { return makeConstIterator(anchor()); }
 199
 200     reverse_iterator rbegin() { return makeReverseIterator(lastNode()); }
 201     reverse_iterator rend() { return makeReverseIterator(anchor()); }
 202     const_reverse_iterator rbegin() const { return makeConstReverseIterator(lastNode()); }
 203     const_reverse_iterator rend() const { return makeConstReverseIterator(anchor()); }
 204
 205     Value& first();
 206     const Value& first() const;
 207     void removeFirst();
 208
 209     Value& last();
 210     const Value& last() const;
 211     void removeLast();
 212
 213     iterator find(ValuePeekInType);
 214     const_iterator find(ValuePeekInType) const;
 215     bool contains(ValuePeekInType) const;
 216
 217     // An alternate version of find() that finds the object by hashing and comparing
 218     // with some other type, to avoid the cost of type conversion.
 219     // The HashTranslator interface is defined in HashSet.
 220     template<typename HashTranslator, typename T> iterator find(const T&);
 221     template<typename HashTranslator, typename T> const_iterator find(const T&) const;
 222     template<typename HashTranslator, typename T> bool contains(const T&) const;
 223
 224     // The return value of add is a pair of a pointer to the stored value,
 225     // and a bool that is true if an new entry was added.
 226     AddResult add(ValuePeekInType);
 227
 228     // Same as add() except that the return value is an
 229     // iterator. Useful in cases where it's needed to have the
 230     // same return value as find() and where it's not possible to
 231     // use a pointer to the storedValue.
 232     iterator addReturnIterator(ValuePeekInType);
 233
 234     // Add the value to the end of the collection. If the value was already in
 235     // the list, it is moved to the end.
 236     AddResult appendOrMoveToLast(ValuePeekInType);
 237
 238     // Add the value to the beginning of the collection. If the value was already in
 239     // the list, it is moved to the beginning.
 240     AddResult prependOrMoveToFirst(ValuePeekInType);
 241
 242     AddResult insertBefore(ValuePeekInType beforeValue, ValuePeekInType newValue);
 243     AddResult insertBefore(iterator it, ValuePeekInType newValue) { return m_impl.template add<NodeHashFunctions>(newValue, it.node()); }
 244
 245     void remove(ValuePeekInType);
 246     void remove(iterator);
 247     void clear() { m_impl.clear(); }
 248     template<typename Collection>
 249     void removeAll(const Collection& other) { WTF::removeAll(*this, other); }
 250
 251     template<typename VisitorDispatcher>
 252     void trace(VisitorDispatcher visitor) { m_impl.trace(visitor); }
 253
 254     int64_t modifications() const { return m_impl.modifications(); }
 255     void checkModifications(int64_t mods) const { m_impl.checkModifications(mods); }
 256
 257 private:
 258     Node* anchor() { return reinterpret_cast<Node*>(&m_anchor); }
 259     const Node* anchor() const { return reinterpret_cast<const Node*>(&m_anchor); }
 260     Node* firstNode() { return reinterpret_cast<Node*>(m_anchor.m_next); }
 261     const Node* firstNode() const { return reinterpret_cast<const Node*>(m_anchor.m_next); }
 262     Node* lastNode() { return reinterpret_cast<Node*>(m_anchor.m_prev); }
 263     const Node* lastNode() const { return reinterpret_cast<const Node*>(m_anchor.m_prev); }
 264
 265     iterator makeIterator(const Node* position) { return iterator(position, this); }
 266     const_iterator makeConstIterator(const Node* position) const { return const_iterator(position, this); }
 267     reverse_iterator makeReverseIterator(const Node* position) { return reverse_iterator(position, this); }
 268     const_reverse_iterator makeConstReverseIterator(const Node* position) const { return const_reverse_iterator(position, this); }
 269
 270     ImplType m_impl;
 271     NodeBase m_anchor;
 272 };
 273
 274 template<typename Value, typename HashFunctions, typename Allocator>
 275 struct LinkedHashSetTranslator {
 276     typedef LinkedHashSetNode<Value, Allocator> Node;
 277     typedef LinkedHashSetNodeBase NodeBase;
 278     typedef typename HashTraits<Value>::PeekInType ValuePeekInType;
 279     static unsigned hash(const Node& node) { return HashFunctions::hash(node.m_value); }
 280     static unsigned hash(const ValuePeekInType& key) { return HashFunctions::hash(key); }
 281     static bool equal(const Node& a, const ValuePeekInType& b) { return HashFunctions::equal(a.m_value, b); }
 282     static bool equal(const Node& a, const Node& b) { return HashFunctions::equal(a.m_value, b.m_value); }
 283     static void translate(Node& location, ValuePeekInType key, NodeBase* anchor)
 284     {
 285         anchor->insertBefore(location);
 286         location.m_value = key;
 287     }
 288
 289     // Empty (or deleted) slots have the m_next pointer set to null, but we
 290     // don't do anything to the other fields, which may contain junk.
 291     // Therefore you can't compare a newly constructed empty value with a
 292     // slot and get the right answer.
 293     static const bool safeToCompareToEmptyOrDeleted = false;
 294 };
 295
 296 template<typename Value, typename Allocator>
 297 struct LinkedHashSetExtractor {
 298     static const Value& extract(const LinkedHashSetNode<Value, Allocator>& node) { return node.m_value; }
 299 };
 300
 301 template<typename Value, typename ValueTraitsArg, typename Allocator>
 302 struct LinkedHashSetTraits : public SimpleClassHashTraits<LinkedHashSetNode<Value, Allocator>> {
 303     typedef LinkedHashSetNode<Value, Allocator> Node;
 304     typedef ValueTraitsArg ValueTraits;
 305
 306     // The slot is empty when the m_next field is zero so it's safe to zero
 307     // the backing.
 308     static const bool emptyValueIsZero = true;
 309
 310     static const bool hasIsEmptyValueFunction = true;
 311     static bool isEmptyValue(const Node& node) { return !node.m_next; }
 312
 313     static const int deletedValue = -1;
 314
 315     static void constructDeletedValue(Node& slot, bool) { slot.m_next = reinterpret_cast<Node*>(deletedValue); }
 316     static bool isDeletedValue(const Node& slot) { return slot.m_next == reinterpret_cast<Node*>(deletedValue); }
 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     // The key and value cannot be swapped atomically, and it would be
 713     // wrong to have a GC when only one was swapped and the other still
 714     // contained garbage (eg. from a previous use of the same slot).
 715     // Therefore we forbid a GC until both the key and the value are
 716     // swapped.
 717     Allocator::enterGCForbiddenScope();
 718     swap(static_cast<Base&>(a), static_cast<Base&>(b));
 719     swap(a.m_value, b.m_value);
 720     Allocator::leaveGCForbiddenScope();
 721 }
 722
 723 #if !ENABLE(OILPAN)
 724 template<typename T, typename U, typename V>
 725 struct NeedsTracing<LinkedHashSet<T, U, V>> {
 726     static const bool value = false;
 727 };
 728 #endif
 729
 730 }
 731
 732 using WTF::LinkedHashSet;
 733
 734 #endif /* WTF_LinkedHashSet_h */