/*
 * 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/allocator/PartitionAllocator.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_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.getNode());
  }

  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 IsTraceableInCollection {
    STATIC_ONLY(IsTraceableInCollection);
    static const bool value =
        ValueTraits::template IsTraceableInCollection<>::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* getNode() { return const_cast<Node*>(m_iterator.getNode()); }

 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* getNode() 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;
}

inline void swapAnchor(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b);

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.getNode());
}

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();
}

}  // namespace WTF

using WTF::LinkedHashSet;

#endif /* WTF_LinkedHashSet_h */