diff options
Diffstat (limited to 'JavaScriptCore/VM/SegmentedVector.h')
-rw-r--r-- | JavaScriptCore/VM/SegmentedVector.h | 174 |
1 files changed, 88 insertions, 86 deletions
diff --git a/JavaScriptCore/VM/SegmentedVector.h b/JavaScriptCore/VM/SegmentedVector.h index 36ffee0..bbab04f 100644 --- a/JavaScriptCore/VM/SegmentedVector.h +++ b/JavaScriptCore/VM/SegmentedVector.h @@ -33,6 +33,9 @@ namespace JSC { + // SegmentedVector is just like Vector, but it doesn't move the values + // stored in its buffer when it grows. Therefore, it is safe to keep + // pointers into a SegmentedVector. template <typename T, size_t SegmentSize> class SegmentedVector { public: SegmentedVector() @@ -43,121 +46,120 @@ namespace JSC { ~SegmentedVector() { - for (size_t i = 1; i < m_segments.size(); i++) - delete m_segments[i]; + deleteAllSegments(); } - T& last() + size_t size() const { return m_size; } + + T& at(size_t index) { - ASSERT(m_size); - return m_segments.last()->last(); + if (index < SegmentSize) + return m_inlineSegment[index]; + return segmentFor(index)->at(subscriptFor(index)); } - template <typename U> void append(const U& value) + T& operator[](size_t index) { - if (!(m_size % SegmentSize) && m_size) - m_segments.append(new Segment); - m_segments.last()->uncheckedAppend(value); - m_size++; + return at(index); } - void removeLast() + T& last() + { + return at(size() - 1); + } + + template <typename U> void append(const U& value) { - ASSERT(m_size); - m_size--; - m_segments.last()->removeLast(); - if (!(m_size % SegmentSize) && m_size >= SegmentSize) { - delete m_segments.last(); - m_segments.removeLast(); + ++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); } - size_t size() const + void removeLast() { - return m_size; + if (m_size <= SegmentSize) + m_inlineSegment.removeLast(); + else + segmentFor(m_size - 1)->removeLast(); + --m_size; } - T& operator[](size_t index) + void grow(size_t size) { - ASSERT(index < m_size); - if (index < SegmentSize) - return m_inlineSegment[index]; - return m_segments[index / SegmentSize]->at(index % SegmentSize); + ASSERT(size > m_size); + ensureSegmentsFor(size); + m_size = size; } - void resize(size_t size) + void clear() { - if (size < m_size) - shrink(size); - else if (size > m_size) - grow(size); - ASSERT(size == m_size); + deleteAllSegments(); + m_segments.resize(1); + m_inlineSegment.clear(); + m_size = 0; } private: - void shrink(size_t size) + typedef Vector<T, SegmentSize> Segment; + + void deleteAllSegments() { - ASSERT(size < m_size); - size_t numSegments = size / SegmentSize; - size_t extra = size % SegmentSize; - if (extra) - numSegments++; - if (!numSegments) { - for (size_t i = 1; i < m_segments.size(); i++) - delete m_segments[i]; - m_segments.resize(1); - m_inlineSegment.resize(0); - return; - } - - for (size_t i = numSegments; i < m_segments.size(); i++) + // Skip the first segment, because it's our inline segment, which was + // not created by new. + for (size_t i = 1; i < m_segments.size(); i++) delete m_segments[i]; - - m_segments.resize(numSegments); - if (extra) - m_segments.last()->resize(extra); - m_size = size; } - - void grow(size_t size) + + bool segmentExistsFor(size_t index) { - ASSERT(size > m_size); - if (size <= SegmentSize) { - m_inlineSegment.resize(size); - m_size = size; - return; - } - - size_t numSegments = size / SegmentSize; - size_t extra = size % SegmentSize; - if (extra) - numSegments++; - size_t oldSize = m_segments.size(); - - if (numSegments == oldSize) { - m_segments.last()->resize(extra); - m_size = size; - return; - } - - m_segments.last()->resize(SegmentSize); - - m_segments.resize(numSegments); - - ASSERT(oldSize < m_segments.size()); - for (size_t i = oldSize; i < (numSegments - 1); i++) { - Segment* segment = new Segment; - segment->resize(SegmentSize); - m_segments[i] = segment; - } + 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); // We always have at least our inline segment. + + size_t neededSegmentCount = size / SegmentSize; + if (size % SegmentSize) + ++neededSegmentCount; + + // Fill up to N - 1 segments. + size_t end = neededSegmentCount - 1; + for (size_t i = segmentCount - 1; i < end; ++i) + ensureSegment(i, SegmentSize); + + // Grow segment N to accomodate the remainder. + ensureSegment(end, subscriptFor(size - 1) + 1); + } - Segment* segment = new Segment; - segment->resize(extra ? extra : SegmentSize); - m_segments[numSegments - 1] = segment; - m_size = size; + 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); } - typedef Vector<T, SegmentSize> Segment; size_t m_size; Segment m_inlineSegment; Vector<Segment*, 32> m_segments; |