Move files in wtf/ to platform/wtf/ (Part 8).

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.
- *
- */
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
 
-#ifndef WTF_LinkedHashSet_h
-#define WTF_LinkedHashSet_h
+#include "platform/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;
-    DCHECK(m_prev);
-    DCHECK(m_next->m_prev == this);
-    DCHECK(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;
-    DCHECK(other.m_next);
-    DCHECK(other.m_prev);
-    DCHECK(m_next);
-    DCHECK(m_prev);
-  }
-
-  void insertAfter(LinkedHashSetNodeBase& other) {
-    other.m_prev = this;
-    other.m_next = m_next;
-    m_next->m_prev = &other;
-    m_next = &other;
-    DCHECK(other.m_next);
-    DCHECK(other.m_prev);
-    DCHECK(m_next);
-    DCHECK(m_prev);
-  }
-
-  LinkedHashSetNodeBase(LinkedHashSetNodeBase* prev,
-                        LinkedHashSetNodeBase* next)
-      : m_prev(prev), m_next(next) {
-    DCHECK((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 {
-  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& front();
-  const Value& front() const;
-  void removeFirst();
-
-  Value& back();
-  const Value& back() const;
-  void pop_back();
-
-  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 insert 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 insert(IncomingValueType&&);
-
-  // Same as insert() 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 erase(ValuePeekInType);
-  void erase(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);
-    // Should the underlying table be moved by GC, register a callback
-    // that fixes up the interior pointers that the (Heap)LinkedHashSet keeps.
-    if (m_impl.m_table) {
-      Allocator::registerBackingStoreCallback(
-          visitor, m_impl.m_table, moveBackingCallback,
-          reinterpret_cast<void*>(&m_anchor));
-    }
-  }
-
-  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);
-  }
-
-  static void moveBackingCallback(void* anchor,
-                                  void* from,
-                                  void* to,
-                                  size_t size) {
-    // Note: the hash table move may have been overlapping; linearly scan the
-    // entire table and fixup interior pointers into the old region with
-    // correspondingly offset ones into the new.
-    size_t tableSize = size / sizeof(Node);
-    Node* table = reinterpret_cast<Node*>(to);
-    NodeBase* fromStart = reinterpret_cast<NodeBase*>(from);
-    NodeBase* fromEnd =
-        reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(from) + size);
-    for (Node* element = table + tableSize - 1; element >= table; element--) {
-      Node& node = *element;
-      if (ImplType::isEmptyOrDeletedBucket(node))
-        continue;
-      if (node.m_next >= fromStart && node.m_next < fromEnd) {
-        size_t diff = reinterpret_cast<uintptr_t>(node.m_next) -
-                      reinterpret_cast<uintptr_t>(from);
-        node.m_next =
-            reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(to) + diff);
-      }
-      if (node.m_prev >= fromStart && node.m_prev < fromEnd) {
-        size_t diff = reinterpret_cast<uintptr_t>(node.m_prev) -
-                      reinterpret_cast<uintptr_t>(from);
-        node.m_prev =
-            reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(to) + diff);
-      }
-    }
-    NodeBase* anchorNode = reinterpret_cast<NodeBase*>(anchor);
-    if (anchorNode->m_next >= fromStart && anchorNode->m_next < fromEnd) {
-      size_t diff = reinterpret_cast<uintptr_t>(anchorNode->m_next) -
-                    reinterpret_cast<uintptr_t>(from);
-      anchorNode->m_next =
-          reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(to) + diff);
-    }
-    if (anchorNode->m_prev >= fromStart && anchorNode->m_prev < fromEnd) {
-      size_t diff = reinterpret_cast<uintptr_t>(anchorNode->m_prev) -
-                    reinterpret_cast<uintptr_t>(from);
-      anchorNode->m_prev =
-          reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(to) + diff);
-    }
-  }
-
-  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 DCHECK_IS_ON()
-        ,
-        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++() {
-    DCHECK(m_position);
-    checkModifications();
-    m_position = m_position->m_next;
-    return *this;
-  }
-
-  LinkedHashSetConstIterator& operator--() {
-    DCHECK(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 DCHECK_IS_ON()
-  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 Allocator>
-inline LinkedHashSet<T, U, V, Allocator>::LinkedHashSet() {
-  static_assert(
-      Allocator::isGarbageCollected ||
-          !IsPointerToGarbageCollectedType<T>::value,
-      "Cannot put raw pointers to garbage-collected classes into "
-      "an off-heap LinkedHashSet. Use HeapLinkedHashSet<Member<T>> instead.");
-}
-
-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)
-    insert(*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>::front() {
-  DCHECK(!isEmpty());
-  return firstNode()->m_value;
-}
-
-template <typename T, typename U, typename V, typename W>
-inline const T& LinkedHashSet<T, U, V, W>::front() const {
-  DCHECK(!isEmpty());
-  return firstNode()->m_value;
-}
-
-template <typename T, typename U, typename V, typename W>
-inline void LinkedHashSet<T, U, V, W>::removeFirst() {
-  DCHECK(!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>::back() {
-  DCHECK(!isEmpty());
-  return lastNode()->m_value;
-}
-
-template <typename T, typename U, typename V, typename W>
-inline const T& LinkedHashSet<T, U, V, W>::back() const {
-  DCHECK(!isEmpty());
-  return lastNode()->m_value;
-}
-
-template <typename T, typename U, typename V, typename W>
-inline void LinkedHashSet<T, U, V, W>::pop_back() {
-  DCHECK(!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>::insert(
-    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>::erase(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>::erase(ValuePeekInType value) {
-  erase(find(value));
-}
-
-inline void swapAnchor(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b) {
-  DCHECK(a.m_prev);
-  DCHECK(a.m_next);
-  DCHECK(b.m_prev);
-  DCHECK(b.m_next);
-  swap(a.m_prev, b.m_prev);
-  swap(a.m_next, b.m_next);
-  if (b.m_next == &a) {
-    DCHECK_EQ(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) {
-    DCHECK_EQ(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) {
-  DCHECK_NE(a.m_next, &a);
-  DCHECK_NE(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 */
+// The contents of this header was moved to platform/wtf as part of
+// WTF migration project. See the following post for details:
+// https://groups.google.com/a/chromium.org/d/msg/blink-dev/tLdAZCTlcAA/bYXVT8gYCAAJ