wtf/SegmentedVector.h

   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