michael@0: /*
michael@0:  * Copyright (C) 2008 Apple Inc. All rights reserved.
michael@0:  *
michael@0:  * Redistribution and use in source and binary forms, with or without
michael@0:  * modification, are permitted provided that the following conditions
michael@0:  * are met:
michael@0:  *
michael@0:  * 1.  Redistributions of source code must retain the above copyright
michael@0:  *     notice, this list of conditions and the following disclaimer.
michael@0:  * 2.  Redistributions in binary form must reproduce the above copyright
michael@0:  *     notice, this list of conditions and the following disclaimer in the
michael@0:  *     documentation and/or other materials provided with the distribution.
michael@0:  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
michael@0:  *     its contributors may be used to endorse or promote products derived
michael@0:  *     from this software without specific prior written permission.
michael@0:  *
michael@0:  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
michael@0:  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
michael@0:  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
michael@0:  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
michael@0:  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
michael@0:  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
michael@0:  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
michael@0:  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
michael@0:  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
michael@0:  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0:  */
michael@0: 
michael@0: #ifndef assembler_wtf_SegmentedVector_h
michael@0: #define assembler_wtf_SegmentedVector_h
michael@0: 
michael@0: #include "js/Utility.h"
michael@0: #include "js/Vector.h"
michael@0: 
michael@0: namespace WTF {
michael@0: 
michael@0:     // An iterator for SegmentedVector. It supports only the pre ++ operator
michael@0:     template <typename T, size_t SegmentSize> class SegmentedVector;
michael@0:     template <typename T, size_t SegmentSize> class SegmentedVectorIterator {
michael@0:     private:
michael@0:         friend class SegmentedVector<T, SegmentSize>;
michael@0:     public:
michael@0:         typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
michael@0: 
michael@0:         ~SegmentedVectorIterator() { }
michael@0: 
michael@0:         T& operator*() const { return (*m_vector.m_segments[m_segment])[m_index]; }
michael@0:         T* operator->() const { return &(*m_vector.m_segments[m_segment])[m_index]; }
michael@0: 
michael@0:         // Only prefix ++ operator supported
michael@0:         Iterator& operator++()
michael@0:         {
michael@0:             ASSERT(m_index != SegmentSize);
michael@0:             ++m_index;
michael@0:             //if (m_index >= m_vector.m_segments.at(m_segment)->size())  {
michael@0:             if (m_index >= m_vector.m_segments[m_segment]->length())  {
michael@0:                 //if (m_segment + 1 < m_vector.m_segments.size()) {
michael@0:                 if (m_segment + 1 < m_vector.m_segments.length()) {
michael@0:                     //ASSERT(m_vector.m_segments.at(m_segment)->size() > 0);
michael@0:                     ASSERT(m_vector.m_segments[m_segment]->length() > 0);
michael@0:                     ++m_segment;
michael@0:                     m_index = 0;
michael@0:                 } else {
michael@0:                     // Points to the "end" symbol
michael@0:                     m_segment = 0;
michael@0:                     m_index = SegmentSize;
michael@0:                 }
michael@0:             }
michael@0:             return *this;
michael@0:         }
michael@0: 
michael@0:         bool operator==(const Iterator& other) const
michael@0:         {
michael@0:             return (m_index == other.m_index && m_segment = other.m_segment && &m_vector == &other.m_vector);
michael@0:         }
michael@0: 
michael@0:         bool operator!=(const Iterator& other) const
michael@0:         {
michael@0:             return (m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector);
michael@0:         }
michael@0: 
michael@0:         SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize>& other)
michael@0:         {
michael@0:             m_vector = other.m_vector;
michael@0:             m_segment = other.m_segment;
michael@0:             m_index = other.m_index;
michael@0:             return *this;
michael@0:         }
michael@0: 
michael@0:     private:
michael@0:         SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t segment, size_t index)
michael@0:             : m_vector(vector)
michael@0:             , m_segment(segment)
michael@0:             , m_index(index)
michael@0:         {
michael@0:         }
michael@0: 
michael@0:         SegmentedVector<T, SegmentSize>& m_vector;
michael@0:         size_t m_segment;
michael@0:         size_t m_index;
michael@0:     };
michael@0: 
michael@0:     // SegmentedVector is just like Vector, but it doesn't move the values
michael@0:     // stored in its buffer when it grows. Therefore, it is safe to keep
michael@0:     // pointers into a SegmentedVector.
michael@0:     template <typename T, size_t SegmentSize> class SegmentedVector {
michael@0:         friend class SegmentedVectorIterator<T, SegmentSize>;
michael@0:     public:
michael@0:         typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
michael@0: 
michael@0:         SegmentedVector()
michael@0:             : m_size(0)
michael@0:         {
michael@0:             m_segments.append(&m_inlineSegment);
michael@0:         }
michael@0: 
michael@0:         ~SegmentedVector()
michael@0:         {
michael@0:             deleteAllSegments();
michael@0:         }
michael@0: 
michael@0:         size_t size() const { return m_size; }
michael@0:         bool isEmpty() const { return !size(); }
michael@0: 
michael@0:         T& at(size_t index)
michael@0:         {
michael@0:             if (index < SegmentSize)
michael@0:                 return m_inlineSegment[index];
michael@0:             return segmentFor(index)->at(subscriptFor(index));
michael@0:         }
michael@0: 
michael@0:         T& operator[](size_t index)
michael@0:         {
michael@0:             return at(index);
michael@0:         }
michael@0: 
michael@0:         T& last()
michael@0:         {
michael@0:             return at(size() - 1);
michael@0:         }
michael@0: 
michael@0:         template <typename U> void append(const U& value)
michael@0:         {
michael@0:             ++m_size;
michael@0: 
michael@0:             if (m_size <= SegmentSize) {
michael@0:                 //m_inlineSegment.uncheckedAppend(value);
michael@0:                 m_inlineSegment.append(value);
michael@0:                 return;
michael@0:             }
michael@0: 
michael@0:             if (!segmentExistsFor(m_size - 1))
michael@0:                 m_segments.append(js_new<Segment>());
michael@0:             //segmentFor(m_size - 1)->uncheckedAppend(value);
michael@0:             segmentFor(m_size - 1)->append(value);
michael@0:         }
michael@0: 
michael@0:         T& alloc()
michael@0:         {
michael@0:             append<T>(T());
michael@0:             return last();
michael@0:         }
michael@0: 
michael@0:         void removeLast()
michael@0:         {
michael@0:             if (m_size <= SegmentSize)
michael@0:                 m_inlineSegment.removeLast();
michael@0:             else
michael@0:                 segmentFor(m_size - 1)->removeLast();
michael@0:             --m_size;
michael@0:         }
michael@0: 
michael@0:         void grow(size_t size)
michael@0:         {
michael@0:             ASSERT(size > m_size);
michael@0:             ensureSegmentsFor(size);
michael@0:             m_size = size;
michael@0:         }
michael@0: 
michael@0:         void clear()
michael@0:         {
michael@0:             deleteAllSegments();
michael@0:             m_segments.resize(1);
michael@0:             m_inlineSegment.clear();
michael@0:             m_size = 0;
michael@0:         }
michael@0: 
michael@0:         Iterator begin()
michael@0:         {
michael@0:             return Iterator(*this, 0, m_size ? 0 : SegmentSize);
michael@0:         }
michael@0: 
michael@0:         Iterator end()
michael@0:         {
michael@0:             return Iterator(*this, 0, SegmentSize);
michael@0:         }
michael@0: 
michael@0:     private:
michael@0:         typedef js::Vector<T, SegmentSize ,js::SystemAllocPolicy > Segment;
michael@0: 
michael@0:         void deleteAllSegments()
michael@0:         {
michael@0:             // Skip the first segment, because it's our inline segment, which was
michael@0:             // not created by new.
michael@0:             //for (size_t i = 1; i < m_segments.size(); i++)
michael@0:             for (size_t i = 1; i < m_segments.length(); i++)
michael@0:                 js_delete<Segment>(m_segments[i]);
michael@0:         }
michael@0: 
michael@0:         bool segmentExistsFor(size_t index)
michael@0:         {
michael@0:             //return index / SegmentSize < m_segments.size();
michael@0:             return index / SegmentSize < m_segments.length();
michael@0:         }
michael@0: 
michael@0:         Segment* segmentFor(size_t index)
michael@0:         {
michael@0:             return m_segments[index / SegmentSize];
michael@0:         }
michael@0: 
michael@0:         size_t subscriptFor(size_t index)
michael@0:         {
michael@0:             return index % SegmentSize;
michael@0:         }
michael@0: 
michael@0:         void ensureSegmentsFor(size_t size)
michael@0:         {
michael@0:             size_t segmentCount = m_size / SegmentSize;
michael@0:             if (m_size % SegmentSize)
michael@0:                 ++segmentCount;
michael@0:             //segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
michael@0:             segmentCount = segmentCount > 1 ? segmentCount : 1; // We always have at least our inline segment.
michael@0: 
michael@0:             size_t neededSegmentCount = size / SegmentSize;
michael@0:             if (size % SegmentSize)
michael@0:                 ++neededSegmentCount;
michael@0: 
michael@0:             // Fill up to N - 1 segments.
michael@0:             size_t end = neededSegmentCount - 1;
michael@0:             for (size_t i = segmentCount - 1; i < end; ++i)
michael@0:                 ensureSegment(i, SegmentSize);
michael@0: 
michael@0:             // Grow segment N to accomodate the remainder.
michael@0:             ensureSegment(end, subscriptFor(size - 1) + 1);
michael@0:         }
michael@0: 
michael@0:         void ensureSegment(size_t segmentIndex, size_t size)
michael@0:         {
michael@0:             ASSERT(segmentIndex <= m_segments.size());
michael@0:             if (segmentIndex == m_segments.size())
michael@0:                 m_segments.append(js_new<Segment>());
michael@0:             m_segments[segmentIndex]->grow(size);
michael@0:         }
michael@0: 
michael@0:         size_t m_size;
michael@0:         Segment m_inlineSegment;
michael@0:         js::Vector<Segment*, 32 ,js::SystemAllocPolicy > m_segments;
michael@0:     };
michael@0: 
michael@0: } // namespace WTF
michael@0: 
michael@0: using WTF::SegmentedVector;
michael@0: 
michael@0: #endif /* assembler_wtf_SegmentedVector_h */