#ifndef SegmentedVector_h
#define SegmentedVector_h
#include <wtf/Vector.h>
namespace JSC {
template <typename T, size_t SegmentSize> class SegmentedVector {
public:
SegmentedVector()
: m_size(0)
{
m_segments.append(&m_inlineSegment);
}
~SegmentedVector()
{
deleteAllSegments();
}
size_t size() const { return m_size; }
T& at(size_t index)
{
if (index < SegmentSize)
return m_inlineSegment[index];
return segmentFor(index)->at(subscriptFor(index));
}
T& operator[](size_t index)
{
return at(index);
}
T& last()
{
return at(size() - 1);
}
template <typename U> void append(const U& value)
{
++m_size;
if (m_size <= SegmentSize) {
m_inlineSegment.uncheckedAppend(value);
return;
}
if (!segmentExistsFor(m_size - 1))
m_segments.append(new Segment);
segmentFor(m_size - 1)->uncheckedAppend(value);
}
void removeLast()
{
if (m_size <= SegmentSize)
m_inlineSegment.removeLast();
else
segmentFor(m_size - 1)->removeLast();
--m_size;
}
void grow(size_t size)
{
ASSERT(size > m_size);
ensureSegmentsFor(size);
m_size = size;
}
void clear()
{
deleteAllSegments();
m_segments.resize(1);
m_inlineSegment.clear();
m_size = 0;
}
private:
typedef Vector<T, SegmentSize> Segment;
void deleteAllSegments()
{
for (size_t i = 1; i < m_segments.size(); i++)
delete m_segments[i];
}
bool segmentExistsFor(size_t index)
{
return index / SegmentSize < m_segments.size();
}
Segment* segmentFor(size_t index)
{
return m_segments[index / SegmentSize];
}
size_t subscriptFor(size_t index)
{
return index % SegmentSize;
}
void ensureSegmentsFor(size_t size)
{
size_t segmentCount = m_size / SegmentSize;
if (m_size % SegmentSize)
++segmentCount;
segmentCount = std::max<size_t>(segmentCount, 1);
size_t neededSegmentCount = size / SegmentSize;
if (size % SegmentSize)
++neededSegmentCount;
size_t end = neededSegmentCount - 1;
for (size_t i = segmentCount - 1; i < end; ++i)
ensureSegment(i, SegmentSize);
ensureSegment(end, subscriptFor(size - 1) + 1);
}
void ensureSegment(size_t segmentIndex, size_t size)
{
ASSERT(segmentIndex <= m_segments.size());
if (segmentIndex == m_segments.size())
m_segments.append(new Segment);
m_segments[segmentIndex]->grow(size);
}
size_t m_size;
Segment m_inlineSegment;
Vector<Segment*, 32> m_segments;
};
}
#endif // SegmentedVector_h