Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1080)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: Source/wtf/Deque.h

Issue 390983010: Fix Deque.swap for deques with inline capacity Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Add more tests of Vector and Deque swap Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « Source/platform/heap/Heap.h ('k') | Source/wtf/DequeTest.cpp » ('j') | Source/wtf/DequeTest.cpp » ('J')
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: Source/wtf/Deque.h
diff --git a/Source/wtf/Deque.h b/Source/wtf/Deque.h
index 8a055175f764e7db6aea2f1780a93021c39a4519..dff4286dce14a0e2c8c600e581395fc786f1e894 100644
--- a/Source/wtf/Deque.h
+++ b/Source/wtf/Deque.h
@@ -43,8 +43,13 @@ namespace WTF {
template<typename T, size_t inlineCapacity, typename Allocator> class DequeConstIterator;
template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
- class Deque : public VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> {
+ class Deque : private VectorBuffer<T, inlineCapacity, Allocator>, public VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> {
WTF_USE_ALLOCATOR(Deque, Allocator);
+ private:
+private:
+ typedef VectorBuffer<T, inlineCapacity, Allocator> Base;
+ typedef typename Base::Range Range;
+
public:
typedef DequeIterator<T, inlineCapacity, Allocator> iterator;
typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator;
@@ -55,16 +60,14 @@ namespace WTF {
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&);
+ Deque<T, inlineCapacity, 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>&);
+ void swap(Deque<T, inlineCapacity, Allocator>&);
- size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
+ size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + capacity() - m_start; }
bool isEmpty() const { return m_start == m_end; }
iterator begin() { return iterator(this, m_start); }
@@ -76,8 +79,8 @@ namespace WTF {
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& first() { ASSERT(m_start != m_end); return buffer()[m_start]; }
+ const T& first() const { ASSERT(m_start != m_end); return buffer()[m_start]; }
PassType takeFirst();
T& last() { ASSERT(m_start != m_end); return *(--end()); }
@@ -99,9 +102,15 @@ namespace WTF {
void trace(typename Allocator::Visitor*);
private:
+ using Base::buffer;
+ using Base::capacity;
+ using Base::allocateBuffer;
+ using Base::clearUnusedSlots;
+ using Base::hasOutOfLineBuffer;
+
friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
+ friend class VectorBuffer<T, inlineCapacity, Allocator>;
- typedef VectorBuffer<T, inlineCapacity, Allocator> Buffer;
typedef VectorTypeOperations<T> TypeOperations;
typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;
@@ -110,7 +119,6 @@ namespace WTF {
void expandCapacityIfNeeded();
void expandCapacity();
- Buffer m_buffer;
unsigned m_start;
unsigned m_end;
};
@@ -213,16 +221,16 @@ namespace WTF {
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())
+ : VectorBuffer<T, inlineCapacity, Allocator>(other.capacity())
, m_start(other.m_start)
, m_end(other.m_end)
{
- const T* otherBuffer = other.m_buffer.buffer();
+ const T* otherBuffer = other.buffer();
if (m_start <= m_end)
- TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
+ TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, 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);
+ TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, buffer());
+ TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + capacity(), buffer() + m_start);
}
}
@@ -236,9 +244,9 @@ namespace WTF {
}
template<typename T, size_t inlineCapacity, typename Allocator>
- inline Deque<T, 0, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
+ inline Deque<T, inlineCapacity, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
{
- Deque<T> copy(other);
+ Deque copy(other);
swap(copy);
return *this;
}
@@ -247,13 +255,13 @@ namespace WTF {
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);
+ TypeOperations::destruct(buffer() + m_start, buffer() + m_end);
+ clearUnusedSlots(buffer() + m_start, 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());
+ TypeOperations::destruct(buffer(), buffer() + m_end);
+ clearUnusedSlots(buffer(), buffer() + m_end);
+ TypeOperations::destruct(buffer() + m_start, buffer() + capacity());
+ clearUnusedSlots(buffer() + m_start, buffer() + capacity());
}
}
@@ -264,21 +272,22 @@ namespace WTF {
template<typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::finalize()
{
- if (!inlineCapacity && !m_buffer.buffer())
+ if (!inlineCapacity && !buffer())
return;
- if (!isEmpty() && !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
+ if (!isEmpty() && !(Allocator::isGarbageCollected && hasOutOfLineBuffer()))
destroyAll();
- m_buffer.destruct();
+ Base::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)
+ inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, inlineCapacity, Allocator>& other)
{
+ Range thisRange = (m_start != m_end && m_end == 0) ? Range(m_start, capacity()) : Range(m_start, m_end);
+ Range otherRange = (other.m_start != other.m_end && other.m_end == 0) ? Range(other.m_start, other.capacity()) : Range(other.m_start, other.m_end);
+ Base::swapVectorBuffer(other, thisRange, otherRange);
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>
@@ -287,8 +296,8 @@ namespace WTF {
destroyAll();
m_start = 0;
m_end = 0;
- m_buffer.deallocateBuffer(m_buffer.buffer());
- m_buffer.resetBufferPointer();
+ Base::deallocateBuffer(buffer());
+ Base::resetBufferPointer();
}
template<typename T, size_t inlineCapacity, typename Allocator>
@@ -303,6 +312,8 @@ namespace WTF {
return end_iterator;
}
+ // Because start == end indicates an empty deque, we can never use the last
+ // element in the backing.
template<typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded()
{
@@ -310,9 +321,9 @@ namespace WTF {
if (m_end + 1 != m_start)
return;
} else if (m_end) {
- if (m_end != m_buffer.capacity() - 1)
+ if (m_end != capacity() - 1)
return;
- } else if (m_buffer.capacity())
+ } else if (capacity())
return;
expandCapacity();
@@ -321,18 +332,18 @@ namespace WTF {
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();
- m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
+ size_t oldCapacity = capacity();
+ T* oldBuffer = buffer();
+ Base::allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
if (m_start <= m_end)
- TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
+ TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, buffer() + m_start);
else {
- TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
- size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
- TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
+ TypeOperations::move(oldBuffer, oldBuffer + m_end, buffer());
+ size_t newStart = capacity() - (oldCapacity - m_start);
+ TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, buffer() + newStart);
m_start = newStart;
}
- m_buffer.deallocateBuffer(oldBuffer);
+ Base::deallocateBuffer(oldBuffer);
}
template<typename T, size_t inlineCapacity, typename Allocator>
@@ -355,8 +366,8 @@ namespace WTF {
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)
+ new (NotNull, &buffer()[m_end]) T(value);
+ if (m_end == capacity() - 1)
m_end = 0;
else
++m_end;
@@ -367,19 +378,19 @@ namespace WTF {
{
expandCapacityIfNeeded();
if (!m_start)
- m_start = m_buffer.capacity() - 1;
+ m_start = capacity() - 1;
else
--m_start;
- new (NotNull, &m_buffer.buffer()[m_start]) T(value);
+ new (NotNull, &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)
+ TypeOperations::destruct(&buffer()[m_start], &buffer()[m_start + 1]);
+ clearUnusedSlots(&buffer()[m_start], &buffer()[m_start + 1]);
+ if (m_start == capacity() - 1)
m_start = 0;
else
++m_start;
@@ -390,11 +401,11 @@ namespace WTF {
{
ASSERT(!isEmpty());
if (!m_end)
- m_end = m_buffer.capacity() - 1;
+ m_end = 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]);
+ TypeOperations::destruct(&buffer()[m_end], &buffer()[m_end + 1]);
+ clearUnusedSlots(&buffer()[m_end], &buffer()[m_end + 1]);
}
template<typename T, size_t inlineCapacity, typename Allocator>
@@ -415,18 +426,18 @@ namespace WTF {
if (position == m_end)
return;
- T* buffer = m_buffer.buffer();
- TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
+ T* buf = buffer();
+ TypeOperations::destruct(&buf[position], &buf[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();
+ TypeOperations::moveOverlapping(buf + m_start, buf + position, buf + m_start + 1);
+ clearUnusedSlots(buf + m_start, buf + m_start + 1);
+ m_start = (m_start + 1) % 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();
+ TypeOperations::moveOverlapping(buf + position + 1, buf + m_end, buf + position);
+ clearUnusedSlots(buf + m_end - 1, buf + m_end);
+ m_end = (m_end - 1 + capacity()) % capacity();
}
}
@@ -473,8 +484,8 @@ namespace WTF {
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)
+ ASSERT(m_deque->capacity());
+ if (m_index == m_deque->capacity() - 1)
m_index = 0;
else
++m_index;
@@ -484,9 +495,9 @@ namespace WTF {
inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement()
{
ASSERT(m_index != m_deque->m_start);
- ASSERT(m_deque->m_buffer.capacity());
+ ASSERT(m_deque->capacity());
if (!m_index)
- m_index = m_deque->m_buffer.capacity() - 1;
+ m_index = m_deque->capacity() - 1;
else
--m_index;
}
@@ -495,7 +506,7 @@ namespace WTF {
inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const
{
ASSERT(m_index != m_deque->m_end);
- return &m_deque->m_buffer.buffer()[m_index];
+ return &m_deque->buffer()[m_index];
}
template<typename T, size_t inlineCapacity, typename Allocator>
@@ -503,8 +514,8 @@ namespace WTF {
{
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];
+ return &m_deque->buffer()[m_deque->capacity() - 1];
+ return &m_deque->buffer()[m_index - 1];
}
// This is only called if the allocator is a HeapAllocator. It is used when
@@ -513,7 +524,7 @@ namespace WTF {
void Deque<T, inlineCapacity, Allocator>::trace(typename Allocator::Visitor* visitor)
{
ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enabled.
- const T* bufferBegin = m_buffer.buffer();
+ const T* bufferBegin = buffer();
const T* end = bufferBegin + m_end;
if (ShouldBeTraced<VectorTraits<T> >::value) {
if (m_start <= m_end) {
@@ -522,13 +533,13 @@ namespace WTF {
} else {
for (const T* bufferEntry = bufferBegin; bufferEntry != end; bufferEntry++)
Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
- const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
+ const T* bufferEnd = buffer() + capacity();
for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != bufferEnd; bufferEntry++)
Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
}
}
- if (m_buffer.hasOutOfLineBuffer())
- Allocator::markNoTracing(visitor, m_buffer.buffer());
+ if (hasOutOfLineBuffer())
+ Allocator::markNoTracing(visitor, buffer());
}
#if !ENABLE(OILPAN)
« no previous file with comments | « Source/platform/heap/Heap.h ('k') | Source/wtf/DequeTest.cpp » ('j') | Source/wtf/DequeTest.cpp » ('J')

Powered by Google App Engine
This is Rietveld 408576698