Home | History | Annotate | Download | only in wtf 
      1 /*
      2  * Copyright (C) 2008 Apple Inc. All rights reserved.
      3  *
      4  * Redistribution and use in source and binary forms, with or without
      5  * modification, are permitted provided that the following conditions
      6  * are met:
      7  *
      8  * 1.  Redistributions of source code must retain the above copyright
      9  *     notice, this list of conditions and the following disclaimer.
     10  * 2.  Redistributions in binary form must reproduce the above copyright
     11  *     notice, this list of conditions and the following disclaimer in the
     12  *     documentation and/or other materials provided with the distribution.
     13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
     14  *     its contributors may be used to endorse or promote products derived
     15  *     from this software without specific prior written permission.
     16  *
     17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
     18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
     19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
     20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
     21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
     22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
     23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
     24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27  */
     28 
     29 #ifndef SegmentedVector_h
     30 #define SegmentedVector_h
     31 
     32 #include <wtf/Vector.h>
     33 
     34 namespace WTF {
     35 
     36     // An iterator for SegmentedVector. It supports only the pre ++ operator
     37     template <typename T, size_t SegmentSize> class SegmentedVector;
     38     template <typename T, size_t SegmentSize> class SegmentedVectorIterator {
     39     private:
     40         friend class SegmentedVector<T, SegmentSize>;
     41     public:
     42         typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
     43 
     44         ~SegmentedVectorIterator() { }
     45 
     46         T& operator*() const { return m_vector.m_segments.at(m_segment)->at(m_index); }
     47         T* operator->() const { return &m_vector.m_segments.at(m_segment)->at(m_index); }
     48 
     49         // Only prefix ++ operator supported
     50         Iterator& operator++()
     51         {
     52             ASSERT(m_index != SegmentSize);
     53             ++m_index;
     54             if (m_index >= m_vector.m_segments.at(m_segment)->size())  {
     55                 if (m_segment + 1 < m_vector.m_segments.size()) {
     56                     ASSERT(m_vector.m_segments.at(m_segment)->size() > 0);
     57                     ++m_segment;
     58                     m_index = 0;
     59                 } else {
     60                     // Points to the "end" symbol
     61                     m_segment = 0;
     62                     m_index = SegmentSize;
     63                 }
     64             }
     65             return *this;
     66         }
     67 
     68         bool operator==(const Iterator& other) const
     69         {
     70             return (m_index == other.m_index && m_segment = other.m_segment && &m_vector == &other.m_vector);
     71         }
     72 
     73         bool operator!=(const Iterator& other) const
     74         {
     75             return (m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector);
     76         }
     77 
     78         SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize>& other)
     79         {
     80             m_vector = other.m_vector;
     81             m_segment = other.m_segment;
     82             m_index = other.m_index;
     83             return *this;
     84         }
     85 
     86     private:
     87         SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t segment, size_t index)
     88             : m_vector(vector)
     89             , m_segment(segment)
     90             , m_index(index)
     91         {
     92         }
     93 
     94         SegmentedVector<T, SegmentSize>& m_vector;
     95         size_t m_segment;
     96         size_t m_index;
     97     };
     98 
     99     // SegmentedVector is just like Vector, but it doesn't move the values
    100     // stored in its buffer when it grows. Therefore, it is safe to keep
    101     // pointers into a SegmentedVector.
    102     template <typename T, size_t SegmentSize> class SegmentedVector {
    103         friend class SegmentedVectorIterator<T, SegmentSize>;
    104     public:
    105         typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
    106 
    107         SegmentedVector()
    108             : m_size(0)
    109         {
    110             m_segments.append(&m_inlineSegment);
    111         }
    112 
    113         ~SegmentedVector()
    114         {
    115             deleteAllSegments();
    116         }
    117 
    118         size_t size() const { return m_size; }
    119         bool isEmpty() const { return !size(); }
    120 
    121         T& at(size_t index)
    122         {
    123             if (index < SegmentSize)
    124                 return m_inlineSegment[index];
    125             return segmentFor(index)->at(subscriptFor(index));
    126         }
    127 
    128         T& operator[](size_t index)
    129         {
    130             return at(index);
    131         }
    132 
    133         T& last()
    134         {
    135             return at(size() - 1);
    136         }
    137 
    138         template <typename U> void append(const U& value)
    139         {
    140             ++m_size;
    141 
    142             if (m_size <= SegmentSize) {
    143                 m_inlineSegment.uncheckedAppend(value);
    144                 return;
    145             }
    146 
    147             if (!segmentExistsFor(m_size - 1))
    148                 m_segments.append(new Segment);
    149             segmentFor(m_size - 1)->uncheckedAppend(value);
    150         }
    151 
    152         T& alloc()
    153         {
    154             append<T>(T());
    155             return last();
    156         }
    157 
    158         void removeLast()
    159         {
    160             if (m_size <= SegmentSize)
    161                 m_inlineSegment.removeLast();
    162             else
    163                 segmentFor(m_size - 1)->removeLast();
    164             --m_size;
    165         }
    166 
    167         void grow(size_t size)
    168         {
    169             ASSERT(size > m_size);
    170             ensureSegmentsFor(size);
    171             m_size = size;
    172         }
    173 
    174         void clear()
    175         {
    176             deleteAllSegments();
    177             m_segments.resize(1);
    178             m_inlineSegment.clear();
    179             m_size = 0;
    180         }
    181 
    182         Iterator begin()
    183         {
    184             return Iterator(*this, 0, m_size ? 0 : SegmentSize);
    185         }
    186 
    187         Iterator end()
    188         {
    189             return Iterator(*this, 0, SegmentSize);
    190         }
    191 
    192     private:
    193         typedef Vector<T, SegmentSize> Segment;
    194 
    195         void deleteAllSegments()
    196         {
    197             // Skip the first segment, because it's our inline segment, which was
    198             // not created by new.
    199             for (size_t i = 1; i < m_segments.size(); i++)
    200                 delete m_segments[i];
    201         }
    202 
    203         bool segmentExistsFor(size_t index)
    204         {
    205             return index / SegmentSize < m_segments.size();
    206         }
    207 
    208         Segment* segmentFor(size_t index)
    209         {
    210             return m_segments[index / SegmentSize];
    211         }
    212 
    213         size_t subscriptFor(size_t index)
    214         {
    215             return index % SegmentSize;
    216         }
    217 
    218         void ensureSegmentsFor(size_t size)
    219         {
    220             size_t segmentCount = m_size / SegmentSize;
    221             if (m_size % SegmentSize)
    222                 ++segmentCount;
    223             segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
    224 
    225             size_t neededSegmentCount = size / SegmentSize;
    226             if (size % SegmentSize)
    227                 ++neededSegmentCount;
    228 
    229             // Fill up to N - 1 segments.
    230             size_t end = neededSegmentCount - 1;
    231             for (size_t i = segmentCount - 1; i < end; ++i)
    232                 ensureSegment(i, SegmentSize);
    233 
    234             // Grow segment N to accomodate the remainder.
    235             ensureSegment(end, subscriptFor(size - 1) + 1);
    236         }
    237 
    238         void ensureSegment(size_t segmentIndex, size_t size)
    239         {
    240             ASSERT(segmentIndex <= m_segments.size());
    241             if (segmentIndex == m_segments.size())
    242                 m_segments.append(new Segment);
    243             m_segments[segmentIndex]->grow(size);
    244         }
    245 
    246         size_t m_size;
    247         Segment m_inlineSegment;
    248         Vector<Segment*, 32> m_segments;
    249     };
    250 
    251 } // namespace WTF
    252 
    253 using WTF::SegmentedVector;
    254 
    255 #endif // SegmentedVector_h
    256