src/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/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& value) { return !value.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 bool isWeak = ValueTraits::isWeak;
 328 };
 329
 330 template<typename LinkedHashSetType>
 331 class LinkedHashSetIterator {
 332 private:
 333     typedef typename LinkedHashSetType::Node Node;
 334     typedef typename LinkedHashSetType::Traits Traits;
 335
 336     typedef typename LinkedHashSetType::Value& ReferenceType;
 337     typedef typename LinkedHashSetType::Value* PointerType;
 338
 339     typedef LinkedHashSetConstIterator<LinkedHashSetType> const_iterator;
 340
 341     Node* node() { return const_cast<Node*>(m_iterator.node()); }
 342
 343 protected:
 344     LinkedHashSetIterator(const Node* position, LinkedHashSetType* m_container)
 345         : m_iterator(position , m_container)
 346     {
 347     }
 348
 349 public:
 350     // Default copy, assignment and destructor are OK.
 351
 352     PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
 353     ReferenceType operator*() const { return *get(); }
 354     PointerType operator->() const { return get(); }
 355
 356     LinkedHashSetIterator& operator++() { ++m_iterator; return *this; }
 357     LinkedHashSetIterator& operator--() { --m_iterator; return *this; }
 358
 359     // Postfix ++ and -- intentionally omitted.
 360
 361     // Comparison.
 362     bool operator==(const LinkedHashSetIterator& other) const { return m_iterator == other.m_iterator; }
 363     bool operator!=(const LinkedHashSetIterator& other) const { return m_iterator != other.m_iterator; }
 364
 365     operator const_iterator() const { return m_iterator; }
 366
 367 protected:
 368     const_iterator m_iterator;
 369     template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
 370 };
 371
 372 template<typename LinkedHashSetType>
 373 class LinkedHashSetConstIterator {
 374 private:
 375     typedef typename LinkedHashSetType::Node Node;
 376     typedef typename LinkedHashSetType::Traits Traits;
 377
 378     typedef const typename LinkedHashSetType::Value& ReferenceType;
 379     typedef const typename LinkedHashSetType::Value* PointerType;
 380
 381     const Node* node() const { return static_cast<const Node*>(m_position); }
 382
 383 protected:
 384     LinkedHashSetConstIterator(const LinkedHashSetNodeBase* position, const LinkedHashSetType* container)
 385         : m_position(position)
 386 #ifdef ASSERT_ENABLED
 387         , m_container(container)
 388         , m_containerModifications(container->modifications())
 389 #endif
 390     {
 391     }
 392
 393 public:
 394     PointerType get() const
 395     {
 396         checkModifications();
 397         return &static_cast<const Node*>(m_position)->m_value;
 398     }
 399     ReferenceType operator*() const { return *get(); }
 400     PointerType operator->() const { return get(); }
 401
 402     LinkedHashSetConstIterator& operator++()
 403     {
 404         ASSERT(m_position);
 405         checkModifications();
 406         m_position = m_position->m_next;
 407         return *this;
 408     }
 409
 410     LinkedHashSetConstIterator& operator--()
 411     {
 412         ASSERT(m_position);
 413         checkModifications();
 414         m_position = m_position->m_prev;
 415         return *this;
 416     }
 417
 418     // Postfix ++ and -- intentionally omitted.
 419
 420     // Comparison.
 421     bool operator==(const LinkedHashSetConstIterator& other) const
 422     {
 423         return m_position == other.m_position;
 424     }
 425     bool operator!=(const LinkedHashSetConstIterator& other) const
 426     {
 427         return m_position != other.m_position;
 428     }
 429
 430 private:
 431     const LinkedHashSetNodeBase* m_position;
 432 #ifdef ASSERT_ENABLED
 433     void checkModifications() const { m_container->checkModifications(m_containerModifications); }
 434     const LinkedHashSetType* m_container;
 435     int64_t m_containerModifications;
 436 #else
 437     void checkModifications() const { }
 438 #endif
 439     template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
 440     friend class LinkedHashSetIterator<LinkedHashSetType>;
 441 };
 442
 443 template<typename LinkedHashSetType>
 444 class LinkedHashSetReverseIterator : public LinkedHashSetIterator<LinkedHashSetType> {
 445     typedef LinkedHashSetIterator<LinkedHashSetType> Superclass;
 446     typedef LinkedHashSetConstReverseIterator<LinkedHashSetType> const_reverse_iterator;
 447     typedef typename LinkedHashSetType::Node Node;
 448
 449 protected:
 450     LinkedHashSetReverseIterator(const Node* position, LinkedHashSetType* container)
 451         : Superclass(position, container) { }
 452
 453 public:
 454     LinkedHashSetReverseIterator& operator++() { Superclass::operator--(); return *this; }
 455     LinkedHashSetReverseIterator& operator--() { Superclass::operator++(); return *this; }
 456
 457     // Postfix ++ and -- intentionally omitted.
 458
 459     operator const_reverse_iterator() const { return *reinterpret_cast<const_reverse_iterator*>(this); }
 460
 461     template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
 462 };
 463
 464 template<typename LinkedHashSetType>
 465 class LinkedHashSetConstReverseIterator : public LinkedHashSetConstIterator<LinkedHashSetType> {
 466     typedef LinkedHashSetConstIterator<LinkedHashSetType> Superclass;
 467     typedef typename LinkedHashSetType::Node Node;
 468
 469 public:
 470     LinkedHashSetConstReverseIterator(const Node* position, const LinkedHashSetType* container)
 471         : Superclass(position, container) { }
 472
 473     LinkedHashSetConstReverseIterator& operator++() { Superclass::operator--(); return *this; }
 474     LinkedHashSetConstReverseIterator& operator--() { Superclass::operator++(); return *this; }
 475
 476     // Postfix ++ and -- intentionally omitted.
 477
 478     template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
 479 };
 480
 481 template<typename T, typename U, typename V, typename W>
 482 inline LinkedHashSet<T, U, V, W>::LinkedHashSet() { }
 483
 484 template<typename T, typename U, typename V, typename W>
 485 inline LinkedHashSet<T, U, V, W>::LinkedHashSet(const LinkedHashSet& other)
 486     : m_anchor()
 487 {
 488     const_iterator end = other.end();
 489     for (const_iterator it = other.begin(); it != end; ++it)
 490         add(*it);
 491 }
 492
 493 template<typename T, typename U, typename V, typename W>
 494 inline LinkedHashSet<T, U, V, W>& LinkedHashSet<T, U, V, W>::operator=(const LinkedHashSet& other)
 495 {
 496     LinkedHashSet tmp(other);
 497     swap(tmp);
 498     return *this;
 499 }
 500
 501 template<typename T, typename U, typename V, typename W>
 502 inline void LinkedHashSet<T, U, V, W>::swap(LinkedHashSet& other)
 503 {
 504     m_impl.swap(other.m_impl);
 505     swap(m_anchor, other.m_anchor);
 506 }
 507
 508 template<typename T, typename U, typename V, typename Allocator>
 509 inline LinkedHashSet<T, U, V, Allocator>::~LinkedHashSet()
 510 {
 511     // The destructor of m_anchor will implicitly be called here, which will
 512     // unlink the anchor from the collection.
 513 }
 514
 515 template<typename T, typename U, typename V, typename W>
 516 inline T& LinkedHashSet<T, U, V, W>::first()
 517 {
 518     ASSERT(!isEmpty());
 519     return firstNode()->m_value;
 520 }
 521
 522 template<typename T, typename U, typename V, typename W>
 523 inline const T& LinkedHashSet<T, U, V, W>::first() const
 524 {
 525     ASSERT(!isEmpty());
 526     return firstNode()->m_value;
 527 }
 528
 529 template<typename T, typename U, typename V, typename W>
 530 inline void LinkedHashSet<T, U, V, W>::removeFirst()
 531 {
 532     ASSERT(!isEmpty());
 533     m_impl.remove(static_cast<Node*>(m_anchor.m_next));
 534 }
 535
 536 template<typename T, typename U, typename V, typename W>
 537 inline T& LinkedHashSet<T, U, V, W>::last()
 538 {
 539     ASSERT(!isEmpty());
 540     return lastNode()->m_value;
 541 }
 542
 543 template<typename T, typename U, typename V, typename W>
 544 inline const T& LinkedHashSet<T, U, V, W>::last() const
 545 {
 546     ASSERT(!isEmpty());
 547     return lastNode()->m_value;
 548 }
 549
 550 template<typename T, typename U, typename V, typename W>
 551 inline void LinkedHashSet<T, U, V, W>::removeLast()
 552 {
 553     ASSERT(!isEmpty());
 554     m_impl.remove(static_cast<Node*>(m_anchor.m_prev));
 555 }
 556
 557 template<typename T, typename U, typename V, typename W>
 558 inline typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value)
 559 {
 560     LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value);
 561     if (!node)
 562         return end();
 563     return makeIterator(node);
 564 }
 565
 566 template<typename T, typename U, typename V, typename W>
 567 inline typename LinkedHashSet<T, U, V, W>::const_iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value) const
 568 {
 569     const LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value);
 570     if (!node)
 571         return end();
 572     return makeConstIterator(node);
 573 }
 574
 575 template<typename Translator>
 576 struct LinkedHashSetTranslatorAdapter {
 577     template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
 578     template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a.m_value, b); }
 579 };
 580
 581 template<typename Value, typename U, typename V, typename W>
 582 template<typename HashTranslator, typename T>
 583 inline typename LinkedHashSet<Value, U, V, W>::iterator LinkedHashSet<Value, U, V, W>::find(const T& value)
 584 {
 585     typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions;
 586     const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value);
 587     if (!node)
 588         return end();
 589     return makeIterator(node);
 590 }
 591
 592 template<typename Value, typename U, typename V, typename W>
 593 template<typename HashTranslator, typename T>
 594 inline typename LinkedHashSet<Value, U, V, W>::const_iterator LinkedHashSet<Value, U, V, W>::find(const T& value) const
 595 {
 596     typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions;
 597     const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value);
 598     if (!node)
 599         return end();
 600     return makeConstIterator(node);
 601 }
 602
 603 template<typename Value, typename U, typename V, typename W>
 604 template<typename HashTranslator, typename T>
 605 inline bool LinkedHashSet<Value, U, V, W>::contains(const T& value) const
 606 {
 607     return m_impl.template contains<LinkedHashSetTranslatorAdapter<HashTranslator> >(value);
 608 }
 609
 610 template<typename T, typename U, typename V, typename W>
 611 inline bool LinkedHashSet<T, U, V, W>::contains(ValuePeekInType value) const
 612 {
 613     return m_impl.template contains<NodeHashFunctions>(value);
 614 }
 615
 616 template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
 617 typename LinkedHashSet<Value, HashFunctions, Traits, Allocator>::AddResult LinkedHashSet<Value, HashFunctions, Traits, Allocator>::add(ValuePeekInType value)
 618 {
 619     return m_impl.template add<NodeHashFunctions>(value, &m_anchor);
 620 }
 621
 622 template<typename T, typename U, typename V, typename W>
 623 typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::addReturnIterator(ValuePeekInType value)
 624 {
 625     typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, &m_anchor);
 626     return makeIterator(result.storedValue);
 627 }
 628
 629 template<typename T, typename U, typename V, typename W>
 630 typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::appendOrMoveToLast(ValuePeekInType value)
 631 {
 632     typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, &m_anchor);
 633     Node* node = result.storedValue;
 634     if (!result.isNewEntry) {
 635         node->unlink();
 636         m_anchor.insertBefore(*node);
 637     }
 638     return result;
 639 }
 640
 641 template<typename T, typename U, typename V, typename W>
 642 typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::prependOrMoveToFirst(ValuePeekInType value)
 643 {
 644     typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, m_anchor.m_next);
 645     Node* node = result.storedValue;
 646     if (!result.isNewEntry) {
 647         node->unlink();
 648         m_anchor.insertAfter(*node);
 649     }
 650     return result;
 651 }
 652
 653 template<typename T, typename U, typename V, typename W>
 654 typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::insertBefore(ValuePeekInType beforeValue, ValuePeekInType newValue)
 655 {
 656     return insertBefore(find(beforeValue), newValue);
 657 }
 658
 659 template<typename T, typename U, typename V, typename W>
 660 inline void LinkedHashSet<T, U, V, W>::remove(iterator it)
 661 {
 662     if (it == end())
 663         return;
 664     m_impl.remove(it.node());
 665 }
 666
 667 template<typename T, typename U, typename V, typename W>
 668 inline void LinkedHashSet<T, U, V, W>::remove(ValuePeekInType value)
 669 {
 670     remove(find(value));
 671 }
 672
 673 template<typename T>
 674 struct IsWeak<LinkedHashSetNode<T> > {
 675     static const bool value = IsWeak<T>::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 */