path: root/third_party/WebKit/Source/wtf/LinkedHashSet.h

/*
 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 *
 */

#ifndef WTF_LinkedHashSet_h
#define WTF_LinkedHashSet_h

#include "wtf/AddressSanitizer.h"
#include "wtf/HashSet.h"
#include "wtf/OwnPtr.h"
#include "wtf/PartitionAllocator.h"
#include "wtf/PassOwnPtr.h"

namespace WTF {

// LinkedHashSet: Just like HashSet, this class provides a Set
// interface - a collection of unique objects with O(1) insertion,
// removal and test for containership. However, it also has an
// order - iterating it will always give back values in the order
// in which they are added.

// Unlike ListHashSet, but like most WTF collections, iteration is NOT safe
// against mutation of the LinkedHashSet.

template<typename Value, typename HashFunctions, typename HashTraits, typename Allocator> class LinkedHashSet;

template<typename LinkedHashSet> class LinkedHashSetIterator;
template<typename LinkedHashSet> class LinkedHashSetConstIterator;
template<typename LinkedHashSet> class LinkedHashSetReverseIterator;
template<typename LinkedHashSet> class LinkedHashSetConstReverseIterator;

template<typename Value, typename HashFunctions, typename Allocator> struct LinkedHashSetTranslator;
template<typename Value, typename Allocator> struct LinkedHashSetExtractor;
template<typename Value, typename ValueTraits, typename Allocator> struct LinkedHashSetTraits;

class LinkedHashSetNodeBase {
    DISALLOW_NEW();
public:
    LinkedHashSetNodeBase() : m_prev(this), m_next(this) { }

    NO_LAZY_SWEEP_SANITIZE_ADDRESS
    void unlink()
    {
        if (!m_next)
            return;
        ASSERT(m_prev);
        ASSERT(m_next->m_prev == this);
        ASSERT(m_prev->m_next == this);
        m_next->m_prev = m_prev;
        m_prev->m_next = m_next;
    }

    ~LinkedHashSetNodeBase()
    {
        unlink();
    }

    void insertBefore(LinkedHashSetNodeBase& other)
    {
        other.m_next = this;
        other.m_prev = m_prev;
        m_prev->m_next = &other;
        m_prev = &other;
        ASSERT(other.m_next);
        ASSERT(other.m_prev);
        ASSERT(m_next);
        ASSERT(m_prev);
    }

    void insertAfter(LinkedHashSetNodeBase& other)
    {
        other.m_prev = this;
        other.m_next = m_next;
        m_next->m_prev = &other;
        m_next = &other;
        ASSERT(other.m_next);
        ASSERT(other.m_prev);
        ASSERT(m_next);
        ASSERT(m_prev);
    }

    LinkedHashSetNodeBase(LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next)
        : m_prev(prev)
        , m_next(next)
    {
        ASSERT((prev && next) || (!prev && !next));
    }

    LinkedHashSetNodeBase* m_prev;
    LinkedHashSetNodeBase* m_next;

protected:
    // If we take a copy of a node we can't copy the next and prev pointers,
    // since they point to something that does not point at us. This is used
    // inside the shouldExpand() "if" in HashTable::add.
    LinkedHashSetNodeBase(const LinkedHashSetNodeBase& other)
        : m_prev(0)
        , m_next(0) { }

    LinkedHashSetNodeBase(LinkedHashSetNodeBase&& other)
        : m_prev(other.m_prev)
        , m_next(other.m_next)
    {
        other.m_prev = nullptr;
        other.m_next = nullptr;
        if (m_next) {
            m_prev->m_next = this;
            m_next->m_prev = this;
        }
    }

private:
    // Should not be used.
    LinkedHashSetNodeBase& operator=(const LinkedHashSetNodeBase& other);
};

template<typename ValueArg, typename Allocator>
class LinkedHashSetNode : public LinkedHashSetNodeBase {
    DISALLOW_NEW_EXCEPT_PLACEMENT_NEW();
public:
    LinkedHashSetNode(const ValueArg& value, LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next)
        : LinkedHashSetNodeBase(prev, next)
        , m_value(value)
    {
    }

    LinkedHashSetNode(LinkedHashSetNode&& other)
        : LinkedHashSetNodeBase(std::move(other))
        , m_value(std::move(other.m_value))
    {
    }

    ValueArg m_value;

private:
    WTF_MAKE_NONCOPYABLE(LinkedHashSetNode);
};

template<
    typename ValueArg,
    typename HashFunctions = typename DefaultHash<ValueArg>::Hash,
    typename TraitsArg = HashTraits<ValueArg>,
    typename Allocator = PartitionAllocator>
class LinkedHashSet {
    WTF_USE_ALLOCATOR(LinkedHashSet, Allocator);
private:
    typedef ValueArg Value;
    typedef TraitsArg Traits;
    typedef LinkedHashSetNode<Value, Allocator> Node;
    typedef LinkedHashSetNodeBase NodeBase;
    typedef LinkedHashSetTranslator<Value, HashFunctions, Allocator> NodeHashFunctions;
    typedef LinkedHashSetTraits<Value, Traits, Allocator> NodeHashTraits;

    typedef HashTable<Node, Node, IdentityExtractor,
        NodeHashFunctions, NodeHashTraits, NodeHashTraits, Allocator> ImplType;

public:
    typedef LinkedHashSetIterator<LinkedHashSet> iterator;
    friend class LinkedHashSetIterator<LinkedHashSet>;
    typedef LinkedHashSetConstIterator<LinkedHashSet> const_iterator;
    friend class LinkedHashSetConstIterator<LinkedHashSet>;

    typedef LinkedHashSetReverseIterator<LinkedHashSet> reverse_iterator;
    friend class LinkedHashSetReverseIterator<LinkedHashSet>;
    typedef LinkedHashSetConstReverseIterator<LinkedHashSet> const_reverse_iterator;
    friend class LinkedHashSetConstReverseIterator<LinkedHashSet>;

    struct AddResult final {
        STACK_ALLOCATED();
        AddResult(const typename ImplType::AddResult& hashTableAddResult)
            : storedValue(&hashTableAddResult.storedValue->m_value)
            , isNewEntry(hashTableAddResult.isNewEntry)
        {
        }

        Value* storedValue;
        bool isNewEntry;
    };

    typedef typename HashTraits<Value>::PeekInType ValuePeekInType;

    LinkedHashSet();
    LinkedHashSet(const LinkedHashSet&);
    LinkedHashSet(LinkedHashSet&&);
    LinkedHashSet& operator=(const LinkedHashSet&);
    LinkedHashSet& operator=(LinkedHashSet&&);

    // Needs finalization. The anchor needs to unlink itself from the chain.
    ~LinkedHashSet();

    static void finalize(void* pointer) { reinterpret_cast<LinkedHashSet*>(pointer)->~LinkedHashSet(); }
    void finalizeGarbageCollectedObject() { finalize(this); }

    void swap(LinkedHashSet&);

    unsigned size() const { return m_impl.size(); }
    unsigned capacity() const { return m_impl.capacity(); }
    bool isEmpty() const { return m_impl.isEmpty(); }

    iterator begin() { return makeIterator(firstNode()); }
    iterator end() { return makeIterator(anchor()); }
    const_iterator begin() const { return makeConstIterator(firstNode()); }
    const_iterator end() const { return makeConstIterator(anchor()); }

    reverse_iterator rbegin() { return makeReverseIterator(lastNode()); }
    reverse_iterator rend() { return makeReverseIterator(anchor()); }
    const_reverse_iterator rbegin() const { return makeConstReverseIterator(lastNode()); }
    const_reverse_iterator rend() const { return makeConstReverseIterator(anchor()); }

    Value& first();
    const Value& first() const;
    void removeFirst();

    Value& last();
    const Value& last() const;
    void removeLast();

    iterator find(ValuePeekInType);
    const_iterator find(ValuePeekInType) const;
    bool contains(ValuePeekInType) const;

    // An alternate version of find() that finds the object by hashing and comparing
    // with some other type, to avoid the cost of type conversion.
    // The HashTranslator interface is defined in HashSet.
    template<typename HashTranslator, typename T> iterator find(const T&);
    template<typename HashTranslator, typename T> const_iterator find(const T&) const;
    template<typename HashTranslator, typename T> bool contains(const T&) const;

    // The return value of add is a pair of a pointer to the stored value,
    // and a bool that is true if an new entry was added.
    template <typename IncomingValueType>
    AddResult add(IncomingValueType&&);

    // Same as add() except that the return value is an
    // iterator. Useful in cases where it's needed to have the
    // same return value as find() and where it's not possible to
    // use a pointer to the storedValue.
    template <typename IncomingValueType>
    iterator addReturnIterator(IncomingValueType&&);

    // Add the value to the end of the collection. If the value was already in
    // the list, it is moved to the end.
    template <typename IncomingValueType>
    AddResult appendOrMoveToLast(IncomingValueType&&);

    // Add the value to the beginning of the collection. If the value was already in
    // the list, it is moved to the beginning.
    template <typename IncomingValueType>
    AddResult prependOrMoveToFirst(IncomingValueType&&);

    template <typename IncomingValueType>
    AddResult insertBefore(ValuePeekInType beforeValue, IncomingValueType&& newValue);
    template <typename IncomingValueType>
    AddResult insertBefore(iterator it, IncomingValueType&& newValue) { return m_impl.template add<NodeHashFunctions>(std::forward<IncomingValueType>(newValue), it.node()); }

    void remove(ValuePeekInType);
    void remove(iterator);
    void clear() { m_impl.clear(); }
    template<typename Collection>
    void removeAll(const Collection& other) { WTF::removeAll(*this, other); }

    template<typename VisitorDispatcher>
    void trace(VisitorDispatcher visitor) { m_impl.trace(visitor); }

    int64_t modifications() const { return m_impl.modifications(); }
    void checkModifications(int64_t mods) const { m_impl.checkModifications(mods); }

private:
    Node* anchor() { return reinterpret_cast<Node*>(&m_anchor); }
    const Node* anchor() const { return reinterpret_cast<const Node*>(&m_anchor); }
    Node* firstNode() { return reinterpret_cast<Node*>(m_anchor.m_next); }
    const Node* firstNode() const { return reinterpret_cast<const Node*>(m_anchor.m_next); }
    Node* lastNode() { return reinterpret_cast<Node*>(m_anchor.m_prev); }
    const Node* lastNode() const { return reinterpret_cast<const Node*>(m_anchor.m_prev); }

    iterator makeIterator(const Node* position) { return iterator(position, this); }
    const_iterator makeConstIterator(const Node* position) const { return const_iterator(position, this); }
    reverse_iterator makeReverseIterator(const Node* position) { return reverse_iterator(position, this); }
    const_reverse_iterator makeConstReverseIterator(const Node* position) const { return const_reverse_iterator(position, this); }

    ImplType m_impl;
    NodeBase m_anchor;
};

template<typename Value, typename HashFunctions, typename Allocator>
struct LinkedHashSetTranslator {
    STATIC_ONLY(LinkedHashSetTranslator);
    typedef LinkedHashSetNode<Value, Allocator> Node;
    typedef LinkedHashSetNodeBase NodeBase;
    typedef typename HashTraits<Value>::PeekInType ValuePeekInType;
    static unsigned hash(const Node& node) { return HashFunctions::hash(node.m_value); }
    static unsigned hash(const ValuePeekInType& key) { return HashFunctions::hash(key); }
    static bool equal(const Node& a, const ValuePeekInType& b) { return HashFunctions::equal(a.m_value, b); }
    static bool equal(const Node& a, const Node& b) { return HashFunctions::equal(a.m_value, b.m_value); }
    template <typename IncomingValueType>
    static void translate(Node& location, IncomingValueType&& key, NodeBase* anchor)
    {
        anchor->insertBefore(location);
        location.m_value = std::forward<IncomingValueType>(key);
    }

    // Empty (or deleted) slots have the m_next pointer set to null, but we
    // don't do anything to the other fields, which may contain junk.
    // Therefore you can't compare a newly constructed empty value with a
    // slot and get the right answer.
    static const bool safeToCompareToEmptyOrDeleted = false;
};

template<typename Value, typename Allocator>
struct LinkedHashSetExtractor {
    STATIC_ONLY(LinkedHashSetExtractor);
    static const Value& extract(const LinkedHashSetNode<Value, Allocator>& node) { return node.m_value; }
};

template<typename Value, typename ValueTraitsArg, typename Allocator>
struct LinkedHashSetTraits : public SimpleClassHashTraits<LinkedHashSetNode<Value, Allocator>> {
    STATIC_ONLY(LinkedHashSetTraits);
    typedef LinkedHashSetNode<Value, Allocator> Node;
    typedef ValueTraitsArg ValueTraits;

    // The slot is empty when the m_next field is zero so it's safe to zero
    // the backing.
    static const bool emptyValueIsZero = true;

    static const bool hasIsEmptyValueFunction = true;
    static bool isEmptyValue(const Node& node) { return !node.m_next; }

    static const int deletedValue = -1;

    static void constructDeletedValue(Node& slot, bool) { slot.m_next = reinterpret_cast<Node*>(deletedValue); }
    static bool isDeletedValue(const Node& slot) { return slot.m_next == reinterpret_cast<Node*>(deletedValue); }

    // Whether we need to trace and do weak processing depends on the traits of
    // the type inside the node.
    template<typename U = void>
    struct NeedsTracingLazily {
        STATIC_ONLY(NeedsTracingLazily);
        static const bool value = ValueTraits::template NeedsTracingLazily<>::value;
    };
    static const WeakHandlingFlag weakHandlingFlag = ValueTraits::weakHandlingFlag;
};

template<typename LinkedHashSetType>
class LinkedHashSetIterator {
    DISALLOW_NEW();
private:
    typedef typename LinkedHashSetType::Node Node;
    typedef typename LinkedHashSetType::Traits Traits;

    typedef typename LinkedHashSetType::Value& ReferenceType;
    typedef typename LinkedHashSetType::Value* PointerType;

    typedef LinkedHashSetConstIterator<LinkedHashSetType> const_iterator;

    Node* node() { return const_cast<Node*>(m_iterator.node()); }

protected:
    LinkedHashSetIterator(const Node* position, LinkedHashSetType* m_container)
        : m_iterator(position , m_container)
    {
    }

public:
    // Default copy, assignment and destructor are OK.

    PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
    ReferenceType operator*() const { return *get(); }
    PointerType operator->() const { return get(); }

    LinkedHashSetIterator& operator++() { ++m_iterator; return *this; }
    LinkedHashSetIterator& operator--() { --m_iterator; return *this; }

    // Postfix ++ and -- intentionally omitted.

    // Comparison.
    bool operator==(const LinkedHashSetIterator& other) const { return m_iterator == other.m_iterator; }
    bool operator!=(const LinkedHashSetIterator& other) const { return m_iterator != other.m_iterator; }

    operator const_iterator() const { return m_iterator; }

protected:
    const_iterator m_iterator;
    template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
};

template<typename LinkedHashSetType>
class LinkedHashSetConstIterator {
    DISALLOW_NEW();
private:
    typedef typename LinkedHashSetType::Node Node;
    typedef typename LinkedHashSetType::Traits Traits;

    typedef const typename LinkedHashSetType::Value& ReferenceType;
    typedef const typename LinkedHashSetType::Value* PointerType;

    const Node* node() const { return static_cast<const Node*>(m_position); }

protected:
    LinkedHashSetConstIterator(const LinkedHashSetNodeBase* position, const LinkedHashSetType* container)
        : m_position(position)
#if ENABLE(ASSERT)
        , m_container(container)
        , m_containerModifications(container->modifications())
#endif
    {
    }

public:
    PointerType get() const
    {
        checkModifications();
        return &static_cast<const Node*>(m_position)->m_value;
    }
    ReferenceType operator*() const { return *get(); }
    PointerType operator->() const { return get(); }

    LinkedHashSetConstIterator& operator++()
    {
        ASSERT(m_position);
        checkModifications();
        m_position = m_position->m_next;
        return *this;
    }

    LinkedHashSetConstIterator& operator--()
    {
        ASSERT(m_position);
        checkModifications();
        m_position = m_position->m_prev;
        return *this;
    }

    // Postfix ++ and -- intentionally omitted.

    // Comparison.
    bool operator==(const LinkedHashSetConstIterator& other) const
    {
        return m_position == other.m_position;
    }
    bool operator!=(const LinkedHashSetConstIterator& other) const
    {
        return m_position != other.m_position;
    }

private:
    const LinkedHashSetNodeBase* m_position;
#if ENABLE(ASSERT)
    void checkModifications() const { m_container->checkModifications(m_containerModifications); }
    const LinkedHashSetType* m_container;
    int64_t m_containerModifications;
#else
    void checkModifications() const { }
#endif
    template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
    friend class LinkedHashSetIterator<LinkedHashSetType>;
};

template<typename LinkedHashSetType>
class LinkedHashSetReverseIterator : public LinkedHashSetIterator<LinkedHashSetType> {
    typedef LinkedHashSetIterator<LinkedHashSetType> Superclass;
    typedef LinkedHashSetConstReverseIterator<LinkedHashSetType> const_reverse_iterator;
    typedef typename LinkedHashSetType::Node Node;

protected:
    LinkedHashSetReverseIterator(const Node* position, LinkedHashSetType* container)
        : Superclass(position, container) { }

public:
    LinkedHashSetReverseIterator& operator++() { Superclass::operator--(); return *this; }
    LinkedHashSetReverseIterator& operator--() { Superclass::operator++(); return *this; }

    // Postfix ++ and -- intentionally omitted.

    operator const_reverse_iterator() const { return *reinterpret_cast<const_reverse_iterator*>(this); }

    template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
};

template<typename LinkedHashSetType>
class LinkedHashSetConstReverseIterator : public LinkedHashSetConstIterator<LinkedHashSetType> {
    typedef LinkedHashSetConstIterator<LinkedHashSetType> Superclass;
    typedef typename LinkedHashSetType::Node Node;

public:
    LinkedHashSetConstReverseIterator(const Node* position, const LinkedHashSetType* container)
        : Superclass(position, container) { }

    LinkedHashSetConstReverseIterator& operator++() { Superclass::operator--(); return *this; }
    LinkedHashSetConstReverseIterator& operator--() { Superclass::operator++(); return *this; }

    // Postfix ++ and -- intentionally omitted.

    template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
};

template<typename T, typename U, typename V, typename W>
inline LinkedHashSet<T, U, V, W>::LinkedHashSet() { }

template<typename T, typename U, typename V, typename W>
inline LinkedHashSet<T, U, V, W>::LinkedHashSet(const LinkedHashSet& other)
    : m_anchor()
{
    const_iterator end = other.end();
    for (const_iterator it = other.begin(); it != end; ++it)
        add(*it);
}

template<typename T, typename U, typename V, typename W>
inline LinkedHashSet<T, U, V, W>::LinkedHashSet(LinkedHashSet&& other)
    : m_anchor()
{
    swap(other);
}

template<typename T, typename U, typename V, typename W>
inline LinkedHashSet<T, U, V, W>& LinkedHashSet<T, U, V, W>::operator=(const LinkedHashSet& other)
{
    LinkedHashSet tmp(other);
    swap(tmp);
    return *this;
}

template<typename T, typename U, typename V, typename W>
inline LinkedHashSet<T, U, V, W>& LinkedHashSet<T, U, V, W>::operator=(LinkedHashSet&& other)
{
    swap(other);
    return *this;
}

template<typename T, typename U, typename V, typename W>
inline void LinkedHashSet<T, U, V, W>::swap(LinkedHashSet& other)
{
    m_impl.swap(other.m_impl);
    swapAnchor(m_anchor, other.m_anchor);
}

template<typename T, typename U, typename V, typename Allocator>
inline LinkedHashSet<T, U, V, Allocator>::~LinkedHashSet()
{
    // The destructor of m_anchor will implicitly be called here, which will
    // unlink the anchor from the collection.
}

template<typename T, typename U, typename V, typename W>
inline T& LinkedHashSet<T, U, V, W>::first()
{
    ASSERT(!isEmpty());
    return firstNode()->m_value;
}

template<typename T, typename U, typename V, typename W>
inline const T& LinkedHashSet<T, U, V, W>::first() const
{
    ASSERT(!isEmpty());
    return firstNode()->m_value;
}

template<typename T, typename U, typename V, typename W>
inline void LinkedHashSet<T, U, V, W>::removeFirst()
{
    ASSERT(!isEmpty());
    m_impl.remove(static_cast<Node*>(m_anchor.m_next));
}

template<typename T, typename U, typename V, typename W>
inline T& LinkedHashSet<T, U, V, W>::last()
{
    ASSERT(!isEmpty());
    return lastNode()->m_value;
}

template<typename T, typename U, typename V, typename W>
inline const T& LinkedHashSet<T, U, V, W>::last() const
{
    ASSERT(!isEmpty());
    return lastNode()->m_value;
}

template<typename T, typename U, typename V, typename W>
inline void LinkedHashSet<T, U, V, W>::removeLast()
{
    ASSERT(!isEmpty());
    m_impl.remove(static_cast<Node*>(m_anchor.m_prev));
}

template<typename T, typename U, typename V, typename W>
inline typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value)
{
    LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value);
    if (!node)
        return end();
    return makeIterator(node);
}

template<typename T, typename U, typename V, typename W>
inline typename LinkedHashSet<T, U, V, W>::const_iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value) const
{
    const LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value);
    if (!node)
        return end();
    return makeConstIterator(node);
}

template<typename Translator>
struct LinkedHashSetTranslatorAdapter {
    STATIC_ONLY(LinkedHashSetTranslatorAdapter);
    template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
    template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a.m_value, b); }
};

template<typename Value, typename U, typename V, typename W>
template<typename HashTranslator, typename T>
inline typename LinkedHashSet<Value, U, V, W>::iterator LinkedHashSet<Value, U, V, W>::find(const T& value)
{
    typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions;
    const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value);
    if (!node)
        return end();
    return makeIterator(node);
}

template<typename Value, typename U, typename V, typename W>
template<typename HashTranslator, typename T>
inline typename LinkedHashSet<Value, U, V, W>::const_iterator LinkedHashSet<Value, U, V, W>::find(const T& value) const
{
    typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions;
    const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value);
    if (!node)
        return end();
    return makeConstIterator(node);
}

template<typename Value, typename U, typename V, typename W>
template<typename HashTranslator, typename T>
inline bool LinkedHashSet<Value, U, V, W>::contains(const T& value) const
{
    return m_impl.template contains<LinkedHashSetTranslatorAdapter<HashTranslator>>(value);
}

template<typename T, typename U, typename V, typename W>
inline bool LinkedHashSet<T, U, V, W>::contains(ValuePeekInType value) const
{
    return m_impl.template contains<NodeHashFunctions>(value);
}

template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
template<typename IncomingValueType>
typename LinkedHashSet<Value, HashFunctions, Traits, Allocator>::AddResult LinkedHashSet<Value, HashFunctions, Traits, Allocator>::add(IncomingValueType&& value)
{
    return m_impl.template add<NodeHashFunctions>(std::forward<IncomingValueType>(value), &m_anchor);
}

template<typename T, typename U, typename V, typename W>
template<typename IncomingValueType>
typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::addReturnIterator(IncomingValueType&& value)
{
    typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(std::forward<IncomingValueType>(value), &m_anchor);
    return makeIterator(result.storedValue);
}

template<typename T, typename U, typename V, typename W>
template<typename IncomingValueType>
typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::appendOrMoveToLast(IncomingValueType&& value)
{
    typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(std::forward<IncomingValueType>(value), &m_anchor);
    Node* node = result.storedValue;
    if (!result.isNewEntry) {
        node->unlink();
        m_anchor.insertBefore(*node);
    }
    return result;
}

template<typename T, typename U, typename V, typename W>
template<typename IncomingValueType>
typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::prependOrMoveToFirst(IncomingValueType&& value)
{
    typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(std::forward<IncomingValueType>(value), m_anchor.m_next);
    Node* node = result.storedValue;
    if (!result.isNewEntry) {
        node->unlink();
        m_anchor.insertAfter(*node);
    }
    return result;
}

template<typename T, typename U, typename V, typename W>
template<typename IncomingValueType>
typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::insertBefore(ValuePeekInType beforeValue, IncomingValueType&& newValue)
{
    return insertBefore(find(beforeValue), std::forward<IncomingValueType>(newValue));
}

template<typename T, typename U, typename V, typename W>
inline void LinkedHashSet<T, U, V, W>::remove(iterator it)
{
    if (it == end())
        return;
    m_impl.remove(it.node());
}

template<typename T, typename U, typename V, typename W>
inline void LinkedHashSet<T, U, V, W>::remove(ValuePeekInType value)
{
    remove(find(value));
}

inline void swapAnchor(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b)
{
    ASSERT(a.m_prev && a.m_next && b.m_prev && b.m_next);
    swap(a.m_prev, b.m_prev);
    swap(a.m_next, b.m_next);
    if (b.m_next == &a) {
        ASSERT(b.m_prev == &a);
        b.m_next = &b;
        b.m_prev = &b;
    } else {
        b.m_next->m_prev = &b;
        b.m_prev->m_next = &b;
    }
    if (a.m_next == &b) {
        ASSERT(a.m_prev == &b);
        a.m_next = &a;
        a.m_prev = &a;
    } else {
        a.m_next->m_prev = &a;
        a.m_prev->m_next = &a;
    }
}

inline void swap(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b)
{
    ASSERT(a.m_next != &a && b.m_next != &b);
    swap(a.m_prev, b.m_prev);
    swap(a.m_next, b.m_next);
    if (b.m_next) {
        b.m_next->m_prev = &b;
        b.m_prev->m_next = &b;
    }
    if (a.m_next) {
        a.m_next->m_prev = &a;
        a.m_prev->m_next = &a;
    }
}

template<typename T, typename Allocator>
inline void swap(LinkedHashSetNode<T, Allocator>& a, LinkedHashSetNode<T, Allocator>& b)
{
    typedef LinkedHashSetNodeBase Base;
    // The key and value cannot be swapped atomically, and it would be
    // wrong to have a GC when only one was swapped and the other still
    // contained garbage (eg. from a previous use of the same slot).
    // Therefore we forbid a GC until both the key and the value are
    // swapped.
    Allocator::enterGCForbiddenScope();
    swap(static_cast<Base&>(a), static_cast<Base&>(b));
    swap(a.m_value, b.m_value);
    Allocator::leaveGCForbiddenScope();
}

#if !ENABLE(OILPAN)
template<typename T, typename U, typename V>
struct NeedsTracing<LinkedHashSet<T, U, V>> {
    STATIC_ONLY(NeedsTracing);
    static const bool value = false;
};
#endif

} // namespace WTF

using WTF::LinkedHashSet;

#endif /* WTF_LinkedHashSet_h */