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

third_party/WebKit/Source/wtf/Deque.h

-/*
- * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
- * Copyright (C) 2009 Google Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1.  Redistributions of source code must retain the above copyright
- *     notice, this list of conditions and the following disclaimer.
- * 2.  Redistributions in binary form must reproduce the above copyright
- *     notice, this list of conditions and the following disclaimer in the
- *     documentation and/or other materials provided with the distribution.
- * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
- *     its contributors may be used to endorse or promote products derived
- *     from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
- * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
+// 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_Deque_h
-#define WTF_Deque_h
+#include "platform/wtf/Deque.h"
 
-// FIXME: Could move what Vector and Deque share into a separate file.
-// Deque doesn't actually use Vector.
-
-#include "wtf/Vector.h"
-#include <iterator>
-
-namespace WTF {
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-class DequeIteratorBase;
-template <typename T, size_t inlineCapacity, typename Allocator>
-class DequeIterator;
-template <typename T, size_t inlineCapacity, typename Allocator>
-class DequeConstIterator;
-
-template <typename T,
-          size_t inlineCapacity = 0,
-          typename Allocator = PartitionAllocator>
-class Deque : public ConditionalDestructor<Deque<T, INLINE_CAPACITY, Allocator>,
-                                           (INLINE_CAPACITY == 0) &&
-                                               Allocator::isGarbageCollected> {
-  USE_ALLOCATOR(Deque, Allocator);
-
- public:
-  typedef DequeIterator<T, inlineCapacity, Allocator> iterator;
-  typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator;
-  typedef std::reverse_iterator<iterator> reverse_iterator;
-  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-
-  Deque();
-  Deque(const Deque&);
-  Deque& operator=(const Deque&);
-  Deque(Deque&&);
-  Deque& operator=(Deque&&);
-
-  void finalize();
-  void finalizeGarbageCollectedObject() { finalize(); }
-
-  void swap(Deque&);
-
-  size_t size() const {
-    return m_start <= m_end ? m_end - m_start
-                            : m_end + m_buffer.capacity() - m_start;
-  }
-  bool isEmpty() const { return m_start == m_end; }
-
-  iterator begin() { return iterator(this, m_start); }
-  iterator end() { return iterator(this, m_end); }
-  const_iterator begin() const { return const_iterator(this, m_start); }
-  const_iterator end() const { return const_iterator(this, m_end); }
-  reverse_iterator rbegin() { return reverse_iterator(end()); }
-  reverse_iterator rend() { return reverse_iterator(begin()); }
-  const_reverse_iterator rbegin() const {
-    return const_reverse_iterator(end());
-  }
-  const_reverse_iterator rend() const {
-    return const_reverse_iterator(begin());
-  }
-
-  T& front() {
-    DCHECK_NE(m_start, m_end);
-    return m_buffer.buffer()[m_start];
-  }
-  const T& front() const {
-    DCHECK_NE(m_start, m_end);
-    return m_buffer.buffer()[m_start];
-  }
-  T takeFirst();
-
-  T& back() {
-    DCHECK_NE(m_start, m_end);
-    return *(--end());
-  }
-  const T& back() const {
-    DCHECK_NE(m_start, m_end);
-    return *(--end());
-  }
-  T takeLast();
-
-  T& at(size_t i) {
-    RELEASE_ASSERT(i < size());
-    size_t right = m_buffer.capacity() - m_start;
-    return i < right ? m_buffer.buffer()[m_start + i]
-                     : m_buffer.buffer()[i - right];
-  }
-  const T& at(size_t i) const {
-    RELEASE_ASSERT(i < size());
-    size_t right = m_buffer.capacity() - m_start;
-    return i < right ? m_buffer.buffer()[m_start + i]
-                     : m_buffer.buffer()[i - right];
-  }
-
-  T& operator[](size_t i) { return at(i); }
-  const T& operator[](size_t i) const { return at(i); }
-
-  template <typename U>
-  void push_front(U&&);
-  void erase(iterator&);
-  void erase(const_iterator&);
-
-  // STL compatibility.
-  template <typename U>
-  void push_back(U&&);
-  void pop_back();
-  void pop_front();
-  bool empty() const { return isEmpty(); }
-  template <typename... Args>
-  void emplace_back(Args&&...);
-  template <typename... Args>
-  void emplace_front(Args&&...);
-
-  void clear();
-
-  template <typename VisitorDispatcher>
-  void trace(VisitorDispatcher);
-
-  static_assert(!std::is_polymorphic<T>::value ||
-                    !VectorTraits<T>::canInitializeWithMemset,
-                "Cannot initialize with memset if there is a vtable");
-  static_assert(Allocator::isGarbageCollected ||
-                    !AllowsOnlyPlacementNew<T>::value ||
-                    !IsTraceable<T>::value,
-                "Cannot put DISALLOW_NEW_EXCEPT_PLACEMENT_NEW objects that "
-                "have trace methods into an off-heap Deque");
-  static_assert(Allocator::isGarbageCollected ||
-                    !IsPointerToGarbageCollectedType<T>::value,
-                "Cannot put raw pointers to garbage-collected classes into a "
-                "Deque. Use HeapDeque<Member<T>> instead.");
-
- private:
-  friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
-
-  class BackingBuffer : public VectorBuffer<T, INLINE_CAPACITY, Allocator> {
-    WTF_MAKE_NONCOPYABLE(BackingBuffer);
-
-   private:
-    using Base = VectorBuffer<T, INLINE_CAPACITY, Allocator>;
-    using Base::m_size;
-
-   public:
-    BackingBuffer() : Base() {}
-    explicit BackingBuffer(size_t capacity) : Base(capacity) {}
-
-    void setSize(size_t size) { m_size = size; }
-  };
-
-  typedef VectorTypeOperations<T> TypeOperations;
-  typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;
-
-  void erase(size_t position);
-  void destroyAll();
-  void expandCapacityIfNeeded();
-  void expandCapacity();
-
-  BackingBuffer m_buffer;
-  unsigned m_start;
-  unsigned m_end;
-};
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-class DequeIteratorBase {
-  DISALLOW_NEW();
-
- protected:
-  DequeIteratorBase();
-  DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t);
-  DequeIteratorBase(const DequeIteratorBase&);
-  DequeIteratorBase& operator=(const DequeIteratorBase<T, 0, Allocator>&);
-  ~DequeIteratorBase();
-
-  void assign(const DequeIteratorBase& other) { *this = other; }
-
-  void increment();
-  void decrement();
-
-  T* before() const;
-  T* after() const;
-
-  bool isEqual(const DequeIteratorBase&) const;
-
- private:
-  Deque<T, inlineCapacity, Allocator>* m_deque;
-  unsigned m_index;
-
-  friend class Deque<T, inlineCapacity, Allocator>;
-};
-
-template <typename T,
-          size_t inlineCapacity = 0,
-          typename Allocator = PartitionAllocator>
-class DequeIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
- private:
-  typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
-  typedef DequeIterator<T, inlineCapacity, Allocator> Iterator;
-
- public:
-  typedef ptrdiff_t difference_type;
-  typedef T value_type;
-  typedef T* pointer;
-  typedef T& reference;
-  typedef std::bidirectional_iterator_tag iterator_category;
-
-  DequeIterator(Deque<T, inlineCapacity, Allocator>* deque, size_t index)
-      : Base(deque, index) {}
-
-  DequeIterator(const Iterator& other) : Base(other) {}
-  DequeIterator& operator=(const Iterator& other) {
-    Base::assign(other);
-    return *this;
-  }
-
-  T& operator*() const { return *Base::after(); }
-  T* operator->() const { return Base::after(); }
-
-  bool operator==(const Iterator& other) const { return Base::isEqual(other); }
-  bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
-
-  Iterator& operator++() {
-    Base::increment();
-    return *this;
-  }
-  // postfix ++ intentionally omitted
-  Iterator& operator--() {
-    Base::decrement();
-    return *this;
-  }
-  // postfix -- intentionally omitted
-};
-
-template <typename T,
-          size_t inlineCapacity = 0,
-          typename Allocator = PartitionAllocator>
-class DequeConstIterator
-    : public DequeIteratorBase<T, inlineCapacity, Allocator> {
- private:
-  typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
-  typedef DequeConstIterator<T, inlineCapacity, Allocator> Iterator;
-  typedef DequeIterator<T, inlineCapacity, Allocator> NonConstIterator;
-
- public:
-  typedef ptrdiff_t difference_type;
-  typedef T value_type;
-  typedef const T* pointer;
-  typedef const T& reference;
-  typedef std::bidirectional_iterator_tag iterator_category;
-
-  DequeConstIterator(const Deque<T, inlineCapacity, Allocator>* deque,
-                     size_t index)
-      : Base(deque, index) {}
-
-  DequeConstIterator(const Iterator& other) : Base(other) {}
-  DequeConstIterator(const NonConstIterator& other) : Base(other) {}
-  DequeConstIterator& operator=(const Iterator& other) {
-    Base::assign(other);
-    return *this;
-  }
-  DequeConstIterator& operator=(const NonConstIterator& other) {
-    Base::assign(other);
-    return *this;
-  }
-
-  const T& operator*() const { return *Base::after(); }
-  const T* operator->() const { return Base::after(); }
-
-  bool operator==(const Iterator& other) const { return Base::isEqual(other); }
-  bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }
-
-  Iterator& operator++() {
-    Base::increment();
-    return *this;
-  }
-  // postfix ++ intentionally omitted
-  Iterator& operator--() {
-    Base::decrement();
-    return *this;
-  }
-  // postfix -- intentionally omitted
-};
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline Deque<T, inlineCapacity, Allocator>::Deque() : m_start(0), m_end(0) {}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque& other)
-    : m_buffer(other.m_buffer.capacity()),
-      m_start(other.m_start),
-      m_end(other.m_end) {
-  const T* otherBuffer = other.m_buffer.buffer();
-  if (m_start <= m_end) {
-    TypeOperations::uninitializedCopy(otherBuffer + m_start,
-                                      otherBuffer + m_end,
-                                      m_buffer.buffer() + m_start);
-  } else {
-    TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end,
-                                      m_buffer.buffer());
-    TypeOperations::uninitializedCopy(otherBuffer + m_start,
-                                      otherBuffer + m_buffer.capacity(),
-                                      m_buffer.buffer() + m_start);
-  }
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline Deque<T, inlineCapacity, Allocator>&
-Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other) {
-  Deque<T> copy(other);
-  swap(copy);
-  return *this;
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline Deque<T, inlineCapacity, Allocator>::Deque(Deque&& other)
-    : m_start(0), m_end(0) {
-  swap(other);
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline Deque<T, inlineCapacity, Allocator>&
-Deque<T, inlineCapacity, Allocator>::operator=(Deque&& other) {
-  swap(other);
-  return *this;
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::destroyAll() {
-  if (m_start <= m_end) {
-    TypeOperations::destruct(m_buffer.buffer() + m_start,
-                             m_buffer.buffer() + m_end);
-    m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start,
-                              m_buffer.buffer() + m_end);
-  } else {
-    TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
-    m_buffer.clearUnusedSlots(m_buffer.buffer(), m_buffer.buffer() + m_end);
-    TypeOperations::destruct(m_buffer.buffer() + m_start,
-                             m_buffer.buffer() + m_buffer.capacity());
-    m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start,
-                              m_buffer.buffer() + m_buffer.capacity());
-  }
-}
-
-// Off-GC-heap deques: Destructor should be called.
-// On-GC-heap deques: Destructor should be called for inline buffers (if any)
-// but destructor shouldn't be called for vector backing since it is managed by
-// the traced GC heap.
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::finalize() {
-  if (!INLINE_CAPACITY && !m_buffer.buffer())
-    return;
-  if (!isEmpty() &&
-      !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
-    destroyAll();
-
-  m_buffer.destruct();
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::swap(Deque& other) {
-  typename BackingBuffer::OffsetRange thisHole;
-  if (m_start <= m_end) {
-    m_buffer.setSize(m_end);
-    thisHole.begin = 0;
-    thisHole.end = m_start;
-  } else {
-    m_buffer.setSize(m_buffer.capacity());
-    thisHole.begin = m_end;
-    thisHole.end = m_start;
-  }
-  typename BackingBuffer::OffsetRange otherHole;
-  if (other.m_start <= other.m_end) {
-    other.m_buffer.setSize(other.m_end);
-    otherHole.begin = 0;
-    otherHole.end = other.m_start;
-  } else {
-    other.m_buffer.setSize(other.m_buffer.capacity());
-    otherHole.begin = other.m_end;
-    otherHole.end = other.m_start;
-  }
-
-  m_buffer.swapVectorBuffer(other.m_buffer, thisHole, otherHole);
-
-  std::swap(m_start, other.m_start);
-  std::swap(m_end, other.m_end);
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::clear() {
-  destroyAll();
-  m_start = 0;
-  m_end = 0;
-  m_buffer.deallocateBuffer(m_buffer.buffer());
-  m_buffer.resetBufferPointer();
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded() {
-  if (m_start) {
-    if (m_end + 1 != m_start)
-      return;
-  } else if (m_end) {
-    if (m_end != m_buffer.capacity() - 1)
-      return;
-  } else if (m_buffer.capacity()) {
-    return;
-  }
-
-  expandCapacity();
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-void Deque<T, inlineCapacity, Allocator>::expandCapacity() {
-  size_t oldCapacity = m_buffer.capacity();
-  T* oldBuffer = m_buffer.buffer();
-  size_t newCapacity =
-      std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
-  if (m_buffer.expandBuffer(newCapacity)) {
-    if (m_start <= m_end) {
-      // No adjustments to be done.
-    } else {
-      size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
-      TypeOperations::moveOverlapping(oldBuffer + m_start,
-                                      oldBuffer + oldCapacity,
-                                      m_buffer.buffer() + newStart);
-      m_buffer.clearUnusedSlots(oldBuffer + m_start,
-                                oldBuffer + std::min(oldCapacity, newStart));
-      m_start = newStart;
-    }
-    return;
-  }
-  m_buffer.allocateBuffer(newCapacity);
-  if (m_start <= m_end) {
-    TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end,
-                         m_buffer.buffer() + m_start);
-    m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + m_end);
-  } else {
-    TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
-    m_buffer.clearUnusedSlots(oldBuffer, oldBuffer + m_end);
-    size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
-    TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity,
-                         m_buffer.buffer() + newStart);
-    m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + oldCapacity);
-    m_start = newStart;
-  }
-  m_buffer.deallocateBuffer(oldBuffer);
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline T Deque<T, inlineCapacity, Allocator>::takeFirst() {
-  T oldFirst = std::move(front());
-  pop_front();
-  return oldFirst;
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline T Deque<T, inlineCapacity, Allocator>::takeLast() {
-  T oldLast = std::move(back());
-  pop_back();
-  return oldLast;
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-template <typename U>
-inline void Deque<T, inlineCapacity, Allocator>::push_back(U&& value) {
-  expandCapacityIfNeeded();
-  T* newElement = &m_buffer.buffer()[m_end];
-  if (m_end == m_buffer.capacity() - 1)
-    m_end = 0;
-  else
-    ++m_end;
-  new (NotNull, newElement) T(std::forward<U>(value));
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-template <typename U>
-inline void Deque<T, inlineCapacity, Allocator>::push_front(U&& value) {
-  expandCapacityIfNeeded();
-  if (!m_start)
-    m_start = m_buffer.capacity() - 1;
-  else
-    --m_start;
-  new (NotNull, &m_buffer.buffer()[m_start]) T(std::forward<U>(value));
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-template <typename... Args>
-inline void Deque<T, inlineCapacity, Allocator>::emplace_back(Args&&... args) {
-  expandCapacityIfNeeded();
-  T* newElement = &m_buffer.buffer()[m_end];
-  if (m_end == m_buffer.capacity() - 1)
-    m_end = 0;
-  else
-    ++m_end;
-  new (NotNull, newElement) T(std::forward<Args>(args)...);
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-template <typename... Args>
-inline void Deque<T, inlineCapacity, Allocator>::emplace_front(Args&&... args) {
-  expandCapacityIfNeeded();
-  if (!m_start)
-    m_start = m_buffer.capacity() - 1;
-  else
-    --m_start;
-  new (NotNull, &m_buffer.buffer()[m_start]) T(std::forward<Args>(args)...);
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::pop_front() {
-  DCHECK(!isEmpty());
-  TypeOperations::destruct(&m_buffer.buffer()[m_start],
-                           &m_buffer.buffer()[m_start + 1]);
-  m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start],
-                            &m_buffer.buffer()[m_start + 1]);
-  if (m_start == m_buffer.capacity() - 1)
-    m_start = 0;
-  else
-    ++m_start;
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::pop_back() {
-  DCHECK(!isEmpty());
-  if (!m_end)
-    m_end = m_buffer.capacity() - 1;
-  else
-    --m_end;
-  TypeOperations::destruct(&m_buffer.buffer()[m_end],
-                           &m_buffer.buffer()[m_end + 1]);
-  m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_end],
-                            &m_buffer.buffer()[m_end + 1]);
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::erase(iterator& it) {
-  erase(it.m_index);
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::erase(const_iterator& it) {
-  erase(it.m_index);
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void Deque<T, inlineCapacity, Allocator>::erase(size_t position) {
-  if (position == m_end)
-    return;
-
-  T* buffer = m_buffer.buffer();
-  TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
-
-  // Find which segment of the circular buffer contained the remove element,
-  // and only move elements in that part.
-  if (position >= m_start) {
-    TypeOperations::moveOverlapping(buffer + m_start, buffer + position,
-                                    buffer + m_start + 1);
-    m_buffer.clearUnusedSlots(buffer + m_start, buffer + m_start + 1);
-    m_start = (m_start + 1) % m_buffer.capacity();
-  } else {
-    TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end,
-                                    buffer + position);
-    m_buffer.clearUnusedSlots(buffer + m_end - 1, buffer + m_end);
-    m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
-  }
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
-    : m_deque(0) {}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(
-    const Deque<T, inlineCapacity, Allocator>* deque,
-    size_t index)
-    : m_deque(const_cast<Deque<T, inlineCapacity, Allocator>*>(deque)),
-      m_index(index) {}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(
-    const DequeIteratorBase& other)
-    : m_deque(other.m_deque), m_index(other.m_index) {}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline DequeIteratorBase<T, inlineCapacity, Allocator>&
-DequeIteratorBase<T, inlineCapacity, Allocator>::operator=(
-    const DequeIteratorBase<T, 0, Allocator>& other) {
-  m_deque = other.m_deque;
-  m_index = other.m_index;
-  return *this;
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase() {}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual(
-    const DequeIteratorBase& other) const {
-  return m_index == other.m_index;
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment() {
-  DCHECK_NE(m_index, m_deque->m_end);
-  DCHECK(m_deque->m_buffer.capacity());
-  if (m_index == m_deque->m_buffer.capacity() - 1)
-    m_index = 0;
-  else
-    ++m_index;
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement() {
-  DCHECK_NE(m_index, m_deque->m_start);
-  DCHECK(m_deque->m_buffer.capacity());
-  if (!m_index)
-    m_index = m_deque->m_buffer.capacity() - 1;
-  else
-    --m_index;
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const {
-  RELEASE_ASSERT(m_index != m_deque->m_end);
-  return &m_deque->m_buffer.buffer()[m_index];
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const {
-  RELEASE_ASSERT(m_index != m_deque->m_start);
-  if (!m_index)
-    return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
-  return &m_deque->m_buffer.buffer()[m_index - 1];
-}
-
-// This is only called if the allocator is a HeapAllocator. It is used when
-// visiting during a tracing GC.
-template <typename T, size_t inlineCapacity, typename Allocator>
-template <typename VisitorDispatcher>
-void Deque<T, inlineCapacity, Allocator>::trace(VisitorDispatcher visitor) {
-  DCHECK(Allocator::isGarbageCollected) << "Garbage collector must be enabled.";
-  const T* bufferBegin = m_buffer.buffer();
-  const T* end = bufferBegin + m_end;
-  if (IsTraceableInCollectionTrait<VectorTraits<T>>::value) {
-    if (m_start <= m_end) {
-      for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end;
-           bufferEntry++)
-        Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(
-            visitor, *const_cast<T*>(bufferEntry));
-    } else {
-      for (const T* bufferEntry = bufferBegin; bufferEntry != end;
-           bufferEntry++)
-        Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(
-            visitor, *const_cast<T*>(bufferEntry));
-      const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
-      for (const T* bufferEntry = bufferBegin + m_start;
-           bufferEntry != bufferEnd; bufferEntry++)
-        Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(
-            visitor, *const_cast<T*>(bufferEntry));
-    }
-  }
-  if (m_buffer.hasOutOfLineBuffer()) {
-    Allocator::markNoTracing(visitor, m_buffer.buffer());
-    Allocator::registerBackingStoreReference(visitor, m_buffer.bufferSlot());
-  }
-}
-
-template <typename T, size_t inlineCapacity, typename Allocator>
-inline void swap(Deque<T, inlineCapacity, Allocator>& a,
-                 Deque<T, inlineCapacity, Allocator>& b) {
-  a.swap(b);
-}
-
-}  // namespace WTF
-
-using WTF::Deque;
-
-#endif  // WTF_Deque_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