Source/WTF/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/Noncopyable.h>
  33 #include <wtf/Vector.h>
  34
  35 namespace WTF {
  36
  37     // An iterator for SegmentedVector. It supports only the pre ++ operator
  38     template <typename T, size_t SegmentSize = 8, size_t InlineCapacity = 32> class SegmentedVector;
  39     template <typename T, size_t SegmentSize = 8, size_t InlineCapacity = 32> class SegmentedVectorIterator {
  40     private:
  41         friend class SegmentedVector<T, SegmentSize, InlineCapacity>;
  42     public:
  43         typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator;
  44
  45         ~SegmentedVectorIterator() { }
  46
  47         T& operator*() const { return m_vector.m_segments.at(m_segment)->at(m_index); }
  48         T* operator->() const { return &m_vector.m_segments.at(m_segment)->at(m_index); }
  49
  50         // Only prefix ++ operator supported
  51         Iterator& operator++()
  52         {
  53             ASSERT(m_index != SegmentSize);
  54             ++m_index;
  55             if (m_index >= m_vector.m_segments.at(m_segment)->size())  {
  56                 if (m_segment + 1 < m_vector.m_segments.size()) {
  57                     ASSERT(m_vector.m_segments.at(m_segment)->size() > 0);
  58                     ++m_segment;
  59                     m_index = 0;
  60                 } else {
  61                     // Points to the "end" symbol
  62                     m_segment = 0;
  63                     m_index = SegmentSize;
  64                 }
  65             }
  66             return *this;
  67         }
  68
  69         bool operator==(const Iterator& other) const
  70         {
  71             return m_index == other.m_index && m_segment == other.m_segment && &m_vector == &other.m_vector;
  72         }
  73
  74         bool operator!=(const Iterator& other) const
  75         {
  76             return m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector;
  77         }
  78
  79         SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize, InlineCapacity>& other)
  80         {
  81             m_vector = other.m_vector;
  82             m_segment = other.m_segment;
  83             m_index = other.m_index;
  84             return *this;
  85         }
  86
  87     private:
  88         SegmentedVectorIterator(SegmentedVector<T, SegmentSize, InlineCapacity>& vector, size_t segment, size_t index)
  89             : m_vector(vector)
  90             , m_segment(segment)
  91             , m_index(index)
  92         {
  93         }
  94
  95         SegmentedVector<T, SegmentSize, InlineCapacity>& m_vector;
  96         size_t m_segment;
  97         size_t m_index;
  98     };
  99
 100     // SegmentedVector is just like Vector, but it doesn't move the values
 101     // stored in its buffer when it grows. Therefore, it is safe to keep
 102     // pointers into a SegmentedVector. The default tuning values are
 103     // optimized for segmented vectors that get large; you may want to use
 104     // SegmentedVector<thingy, 1, 0> if you don't expect a lot of entries.
 105     template <typename T, size_t SegmentSize, size_t InlineCapacity>
 106     class SegmentedVector {
 107         friend class SegmentedVectorIterator<T, SegmentSize, InlineCapacity>;
 108         WTF_MAKE_NONCOPYABLE(SegmentedVector);
 109
 110     public:
 111         typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator;
 112
 113         SegmentedVector()
 114             : m_size(0)
 115         {
 116             m_segments.append(&m_inlineSegment);
 117         }
 118
 119         ~SegmentedVector()
 120         {
 121             deleteAllSegments();
 122         }
 123
 124         size_t size() const { return m_size; }
 125         bool isEmpty() const { return !size(); }
 126
 127         T& at(size_t index)
 128         {
 129             if (index < SegmentSize)
 130                 return m_inlineSegment[index];
 131             return segmentFor(index)->at(subscriptFor(index));
 132         }
 133
 134         T& operator[](size_t index)
 135         {
 136             return at(index);
 137         }
 138
 139         T& last()
 140         {
 141             return at(size() - 1);
 142         }
 143
 144         template <typename U> void append(const U& value)
 145         {
 146             ++m_size;
 147
 148             if (m_size <= SegmentSize) {
 149                 m_inlineSegment.uncheckedAppend(value);
 150                 return;
 151             }
 152
 153             if (!segmentExistsFor(m_size - 1))
 154                 m_segments.append(new Segment);
 155             segmentFor(m_size - 1)->uncheckedAppend(value);
 156         }
 157
 158         T& alloc()
 159         {
 160             append<T>(T());
 161             return last();
 162         }
 163
 164         void removeLast()
 165         {
 166             if (m_size <= SegmentSize)
 167                 m_inlineSegment.removeLast();
 168             else
 169                 segmentFor(m_size - 1)->removeLast();
 170             --m_size;
 171         }
 172
 173         void grow(size_t size)
 174         {
 175             ASSERT(size > m_size);
 176             ensureSegmentsFor(size);
 177             m_size = size;
 178         }
 179
 180         void clear()
 181         {
 182             deleteAllSegments();
 183             m_segments.resize(1);
 184             m_inlineSegment.clear();
 185             m_size = 0;
 186         }
 187
 188         Iterator begin()
 189         {
 190             return Iterator(*this, 0, m_size ? 0 : SegmentSize);
 191         }
 192
 193         Iterator end()
 194         {
 195             return Iterator(*this, 0, SegmentSize);
 196         }
 197
 198         void shrinkToFit()
 199         {
 200             m_segments.shrinkToFit();
 201         }
 202
 203     private:
 204         typedef Vector<T, SegmentSize> Segment;
 205
 206         void deleteAllSegments()
 207         {
 208             // Skip the first segment, because it's our inline segment, which was
 209             // not created by new.
 210             for (size_t i = 1; i < m_segments.size(); i++)
 211                 delete m_segments[i];
 212         }
 213
 214         bool segmentExistsFor(size_t index)
 215         {
 216             return index / SegmentSize < m_segments.size();
 217         }
 218
 219         Segment* segmentFor(size_t index)
 220         {
 221             return m_segments[index / SegmentSize];
 222         }
 223
 224         size_t subscriptFor(size_t index)
 225         {
 226             return index % SegmentSize;
 227         }
 228
 229         void ensureSegmentsFor(size_t size)
 230         {
 231             size_t segmentCount = m_size / SegmentSize;
 232             if (m_size % SegmentSize)
 233                 ++segmentCount;
 234             segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
 235
 236             size_t neededSegmentCount = size / SegmentSize;
 237             if (size % SegmentSize)
 238                 ++neededSegmentCount;
 239
 240             // Fill up to N - 1 segments.
 241             size_t end = neededSegmentCount - 1;
 242             for (size_t i = segmentCount - 1; i < end; ++i)
 243                 ensureSegment(i, SegmentSize);
 244
 245             // Grow segment N to accomodate the remainder.
 246             ensureSegment(end, subscriptFor(size - 1) + 1);
 247         }
 248
 249         void ensureSegment(size_t segmentIndex, size_t size)
 250         {
 251             ASSERT(segmentIndex <= m_segments.size());
 252             if (segmentIndex == m_segments.size())
 253                 m_segments.append(new Segment);
 254             m_segments[segmentIndex]->grow(size);
 255         }
 256
 257         size_t m_size;
 258         Segment m_inlineSegment;
 259         Vector<Segment*, InlineCapacity> m_segments;
 260     };
 261
 262 } // namespace WTF
 263
 264 using WTF::SegmentedVector;
 265
 266 #endif // SegmentedVector_h