/*
 * 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.
 */

#ifndef WTF_Deque_h
#define 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> {
  WTF_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& first() {
    ASSERT(m_start != m_end);
    return m_buffer.buffer()[m_start];
  }
  const T& first() const {
    ASSERT(m_start != m_end);
    return m_buffer.buffer()[m_start];
  }
  T takeFirst();

  T& last() {
    ASSERT(m_start != m_end);
    return *(--end());
  }
  const T& last() const {
    ASSERT(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 append(U&&);
  template <typename U>
  void prepend(U&&);
  void removeFirst();
  void removeLast();
  void remove(iterator&);
  void remove(const_iterator&);

  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 remove(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(first());
  removeFirst();
  return oldFirst;
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline T Deque<T, inlineCapacity, Allocator>::takeLast() {
  T oldLast = std::move(last());
  removeLast();
  return oldLast;
}

template <typename T, size_t inlineCapacity, typename Allocator>
template <typename U>
inline void Deque<T, inlineCapacity, Allocator>::append(U&& value) {
  expandCapacityIfNeeded();
  new (NotNull, &m_buffer.buffer()[m_end]) T(std::forward<U>(value));
  if (m_end == m_buffer.capacity() - 1)
    m_end = 0;
  else
    ++m_end;
}

template <typename T, size_t inlineCapacity, typename Allocator>
template <typename U>
inline void Deque<T, inlineCapacity, Allocator>::prepend(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>
inline void Deque<T, inlineCapacity, Allocator>::removeFirst() {
  ASSERT(!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>::removeLast() {
  ASSERT(!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>::remove(iterator& it) {
  remove(it.m_index);
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it) {
  remove(it.m_index);
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::remove(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() {
  ASSERT(m_index != m_deque->m_end);
  ASSERT(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() {
  ASSERT(m_index != m_deque->m_start);
  ASSERT(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) {
  ASSERT(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());
}

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