blob: 062e610f295d59a656d1eaa46b2f9ce408cc5f81 [file] [log] [blame]
/*
* 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/PassTraits.h"
#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;
typedef PassTraits<T> Pass;
typedef typename PassTraits<T>::PassType PassType;
Deque();
Deque(const Deque<T, inlineCapacity, Allocator>&);
// FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
Deque<T, 0, Allocator>& operator=(const Deque&);
void finalize();
void finalizeGarbageCollectedObject() { finalize(); }
// We hard wire the inlineCapacity to zero here, due to crbug.com/360572
void swap(Deque<T, 0, Allocator>&);
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]; }
PassType takeFirst();
T& last() { ASSERT(m_start != m_end); return *(--end()); }
const T& last() const { ASSERT(m_start != m_end); return *(--end()); }
PassType 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(const U&);
template <typename U> void prepend(const U&);
void removeFirst();
void removeLast();
void remove(iterator&);
void remove(const_iterator&);
void clear();
template <typename Predicate>
iterator findIf(Predicate&);
template <typename VisitorDispatcher> void trace(VisitorDispatcher);
private:
friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
typedef VectorBuffer<T, INLINE_CAPACITY, Allocator> Buffer;
typedef VectorTypeOperations<T> TypeOperations;
typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;
void remove(size_t position);
void destroyAll();
void expandCapacityIfNeeded();
void expandCapacity();
Buffer m_buffer;
unsigned m_start;
unsigned m_end;
};
template <typename T, size_t inlineCapacity, typename Allocator>
class DequeIteratorBase {
protected:
DequeIteratorBase();
DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t);
DequeIteratorBase(const DequeIteratorBase&);
DequeIteratorBase<T, 0, Allocator>& 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)
{
static_assert(!IsPolymorphic<T>::value || !VectorTraits<T>::canInitializeWithMemset, "Cannot initialize with memset if there is a vtable");
#if ENABLE(OILPAN)
static_assert(Allocator::isGarbageCollected || !AllowsOnlyPlacementNew<T>::value || !NeedsTracing<T>::value, "Cannot put DISALLOW_NEW_EXCEPT_PLACEMENT_NEW objects that have trace methods into an off-heap Deque");
#endif
static_assert(Allocator::isGarbageCollected || !IsPointerToGarbageCollectedType<T>::value, "Cannot put raw pointers to garbage-collected classes into a Deque. Use HeapDeque<Member<T>> instead.");
}
template <typename T, size_t inlineCapacity, typename Allocator>
inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque<T, inlineCapacity, Allocator>& 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, 0, 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 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();
}
// FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, 0, Allocator>& other)
{
std::swap(m_start, other.m_start);
std::swap(m_end, other.m_end);
m_buffer.swapVectorBuffer(other.m_buffer);
}
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>
template <typename Predicate>
inline DequeIterator<T, inlineCapacity, Allocator> Deque<T, inlineCapacity, Allocator>::findIf(Predicate& predicate)
{
iterator endIterator = end();
for (iterator it = begin(); it != endIterator; ++it) {
if (predicate(*it))
return it;
}
return endIterator;
}
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 typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeFirst()
{
T oldFirst = Pass::transfer(first());
removeFirst();
return Pass::transfer(oldFirst);
}
template <typename T, size_t inlineCapacity, typename Allocator>
inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeLast()
{
T oldLast = Pass::transfer(last());
removeLast();
return Pass::transfer(oldLast);
}
template <typename T, size_t inlineCapacity, typename Allocator>
template <typename U>
inline void Deque<T, inlineCapacity, Allocator>::append(const U& value)
{
expandCapacityIfNeeded();
new (NotNull, &m_buffer.buffer()[m_end]) T(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(const U& value)
{
expandCapacityIfNeeded();
if (!m_start)
m_start = m_buffer.capacity() - 1;
else
--m_start;
new (NotNull, &m_buffer.buffer()[m_start]) T(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, 0, 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
{
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
{
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 (NeedsTracingTrait<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);
}
#if !ENABLE(OILPAN)
template <typename T, size_t N>
struct NeedsTracing<Deque<T, N>> {
static const bool value = false;
};
#endif
} // namespace WTF
using WTF::Deque;
#endif // WTF_Deque_h