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
30namespace 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
41template<typename Value, typename HashFunctions, typename HashTraits, typename Allocator> class LinkedHashSet;
42
43template<typename LinkedHashSet> class LinkedHashSetIterator;
44template<typename LinkedHashSet> class LinkedHashSetConstIterator;
45template<typename LinkedHashSet> class LinkedHashSetReverseIterator;
46template<typename LinkedHashSet> class LinkedHashSetConstReverseIterator;
47
48template<typename Value, typename HashFunctions, typename Allocator> struct LinkedHashSetTranslator;
49template<typename Value, typename Allocator> struct LinkedHashSetExtractor;
50template<typename Value, typename ValueTraits, typename Allocator> struct LinkedHashSetTraits;
51
52class LinkedHashSetNodeBase {
53public:
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
106protected:
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
114private:
115    // Should not be used.
116    LinkedHashSetNodeBase& operator=(const LinkedHashSetNodeBase& other);
117};
118
119template<typename ValueArg, typename Allocator>
120class LinkedHashSetNode : public LinkedHashSetNodeBase {
121public:
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
130private:
131    // Not used.
132    LinkedHashSetNode(const LinkedHashSetNode&);
133};
134
135template<
136    typename ValueArg,
137    typename HashFunctions = typename DefaultHash<ValueArg>::Hash,
138    typename TraitsArg = HashTraits<ValueArg>,
139    typename Allocator = DefaultAllocator>
140class LinkedHashSet {
141    WTF_USE_ALLOCATOR(LinkedHashSet, Allocator);
142private:
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
153public:
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
253private:
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
270template<typename Value, typename HashFunctions, typename Allocator>
271struct 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
292template<typename Value, typename Allocator>
293struct LinkedHashSetExtractor {
294    static const Value& extract(const LinkedHashSetNode<Value, Allocator>& node) { return node.m_value; }
295};
296
297template<typename Value, typename ValueTraitsArg, typename Allocator>
298struct 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
327template<typename LinkedHashSetType>
328class LinkedHashSetIterator {
329private:
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
340protected:
341    LinkedHashSetIterator(const Node* position, LinkedHashSetType* m_container)
342        : m_iterator(position , m_container)
343    {
344    }
345
346public:
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
364protected:
365    const_iterator m_iterator;
366    template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
367};
368
369template<typename LinkedHashSetType>
370class LinkedHashSetConstIterator {
371private:
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
380protected:
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
390public:
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
427private:
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
440template<typename LinkedHashSetType>
441class LinkedHashSetReverseIterator : public LinkedHashSetIterator<LinkedHashSetType> {
442    typedef LinkedHashSetIterator<LinkedHashSetType> Superclass;
443    typedef LinkedHashSetConstReverseIterator<LinkedHashSetType> const_reverse_iterator;
444    typedef typename LinkedHashSetType::Node Node;
445
446protected:
447    LinkedHashSetReverseIterator(const Node* position, LinkedHashSetType* container)
448        : Superclass(position, container) { }
449
450public:
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
461template<typename LinkedHashSetType>
462class LinkedHashSetConstReverseIterator : public LinkedHashSetConstIterator<LinkedHashSetType> {
463    typedef LinkedHashSetConstIterator<LinkedHashSetType> Superclass;
464    typedef typename LinkedHashSetType::Node Node;
465
466public:
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
478template<typename T, typename U, typename V, typename W>
479inline LinkedHashSet<T, U, V, W>::LinkedHashSet() { }
480
481template<typename T, typename U, typename V, typename W>
482inline 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
490template<typename T, typename U, typename V, typename W>
491inline 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
498template<typename T, typename U, typename V, typename W>
499inline 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
505template<typename T, typename U, typename V, typename Allocator>
506inline 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
512template<typename T, typename U, typename V, typename W>
513inline T& LinkedHashSet<T, U, V, W>::first()
514{
515    ASSERT(!isEmpty());
516    return firstNode()->m_value;
517}
518
519template<typename T, typename U, typename V, typename W>
520inline const T& LinkedHashSet<T, U, V, W>::first() const
521{
522    ASSERT(!isEmpty());
523    return firstNode()->m_value;
524}
525
526template<typename T, typename U, typename V, typename W>
527inline void LinkedHashSet<T, U, V, W>::removeFirst()
528{
529    ASSERT(!isEmpty());
530    m_impl.remove(static_cast<Node*>(m_anchor.m_next));
531}
532
533template<typename T, typename U, typename V, typename W>
534inline T& LinkedHashSet<T, U, V, W>::last()
535{
536    ASSERT(!isEmpty());
537    return lastNode()->m_value;
538}
539
540template<typename T, typename U, typename V, typename W>
541inline const T& LinkedHashSet<T, U, V, W>::last() const
542{
543    ASSERT(!isEmpty());
544    return lastNode()->m_value;
545}
546
547template<typename T, typename U, typename V, typename W>
548inline void LinkedHashSet<T, U, V, W>::removeLast()
549{
550    ASSERT(!isEmpty());
551    m_impl.remove(static_cast<Node*>(m_anchor.m_prev));
552}
553
554template<typename T, typename U, typename V, typename W>
555inline 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
563template<typename T, typename U, typename V, typename W>
564inline 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
572template<typename Translator>
573struct 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
578template<typename Value, typename U, typename V, typename W>
579template<typename HashTranslator, typename T>
580inline 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
589template<typename Value, typename U, typename V, typename W>
590template<typename HashTranslator, typename T>
591inline 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
600template<typename Value, typename U, typename V, typename W>
601template<typename HashTranslator, typename T>
602inline bool LinkedHashSet<Value, U, V, W>::contains(const T& value) const
603{
604    return m_impl.template contains<LinkedHashSetTranslatorAdapter<HashTranslator> >(value);
605}
606
607template<typename T, typename U, typename V, typename W>
608inline bool LinkedHashSet<T, U, V, W>::contains(ValuePeekInType value) const
609{
610    return m_impl.template contains<NodeHashFunctions>(value);
611}
612
613template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
614typename 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
619template<typename T, typename U, typename V, typename W>
620typename 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
626template<typename T, typename U, typename V, typename W>
627typename 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
638template<typename T, typename U, typename V, typename W>
639typename 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
650template<typename T, typename U, typename V, typename W>
651typename 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
656template<typename T, typename U, typename V, typename W>
657inline void LinkedHashSet<T, U, V, W>::remove(iterator it)
658{
659    if (it == end())
660        return;
661    m_impl.remove(it.node());
662}
663
664template<typename T, typename U, typename V, typename W>
665inline void LinkedHashSet<T, U, V, W>::remove(ValuePeekInType value)
666{
667    remove(find(value));
668}
669
670inline 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
693inline 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
708template<typename T, typename Allocator>
709inline 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.
721template<typename ValueType, typename T, typename U>
722void 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)
731template<typename T, typename U, typename V>
732struct NeedsTracing<LinkedHashSet<T, U, V> > {
733    static const bool value = false;
734};
735#endif
736
737}
738
739using WTF::LinkedHashSet;
740
741#endif /* WTF_LinkedHashSet_h */
742