bytecompiler/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 JSC {
  35
  36     // SegmentedVector is just like Vector, but it doesn't move the values
  37     // stored in its buffer when it grows. Therefore, it is safe to keep
  38     // pointers into a SegmentedVector.
  39     template <typename T, size_t SegmentSize> class SegmentedVector {
  40     public:
  41         SegmentedVector()
  42             : m_size(0)
  43         {
  44             m_segments.append(&m_inlineSegment);
  45         }
  46
  47         ~SegmentedVector()
  48         {
  49             deleteAllSegments();
  50         }
  51
  52         size_t size() const { return m_size; }
  53
  54         T& at(size_t index)
  55         {
  56             if (index < SegmentSize)
  57                 return m_inlineSegment[index];
  58             return segmentFor(index)->at(subscriptFor(index));
  59         }
  60
  61         T& operator[](size_t index)
  62         {
  63             return at(index);
  64         }
  65
  66         T& last()
  67         {
  68             return at(size() - 1);
  69         }
  70
  71         template <typename U> void append(const U& value)
  72         {
  73             ++m_size;
  74
  75             if (m_size <= SegmentSize) {
  76                 m_inlineSegment.uncheckedAppend(value);
  77                 return;
  78             }
  79
  80             if (!segmentExistsFor(m_size - 1))
  81                 m_segments.append(new Segment);
  82             segmentFor(m_size - 1)->uncheckedAppend(value);
  83         }
  84
  85         void removeLast()
  86         {
  87             if (m_size <= SegmentSize)
  88                 m_inlineSegment.removeLast();
  89             else
  90                 segmentFor(m_size - 1)->removeLast();
  91             --m_size;
  92         }
  93
  94         void grow(size_t size)
  95         {
  96             ASSERT(size > m_size);
  97             ensureSegmentsFor(size);
  98             m_size = size;
  99         }
 100
 101         void clear()
 102         {
 103             deleteAllSegments();
 104             m_segments.resize(1);
 105             m_inlineSegment.clear();
 106             m_size = 0;
 107         }
 108
 109     private:
 110         typedef Vector<T, SegmentSize> Segment;
 111
 112         void deleteAllSegments()
 113         {
 114             // Skip the first segment, because it's our inline segment, which was
 115             // not created by new.
 116             for (size_t i = 1; i < m_segments.size(); i++)
 117                 delete m_segments[i];
 118         }
 119
 120         bool segmentExistsFor(size_t index)
 121         {
 122             return index / SegmentSize < m_segments.size();
 123         }
 124
 125         Segment* segmentFor(size_t index)
 126         {
 127             return m_segments[index / SegmentSize];
 128         }
 129
 130         size_t subscriptFor(size_t index)
 131         {
 132             return index % SegmentSize;
 133         }
 134
 135         void ensureSegmentsFor(size_t size)
 136         {
 137             size_t segmentCount = m_size / SegmentSize;
 138             if (m_size % SegmentSize)
 139                 ++segmentCount;
 140             segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
 141
 142             size_t neededSegmentCount = size / SegmentSize;
 143             if (size % SegmentSize)
 144                 ++neededSegmentCount;
 145
 146             // Fill up to N - 1 segments.
 147             size_t end = neededSegmentCount - 1;
 148             for (size_t i = segmentCount - 1; i < end; ++i)
 149                 ensureSegment(i, SegmentSize);
 150
 151             // Grow segment N to accomodate the remainder.
 152             ensureSegment(end, subscriptFor(size - 1) + 1);
 153         }
 154
 155         void ensureSegment(size_t segmentIndex, size_t size)
 156         {
 157             ASSERT(segmentIndex <= m_segments.size());
 158             if (segmentIndex == m_segments.size())
 159                 m_segments.append(new Segment);
 160             m_segments[segmentIndex]->grow(size);
 161         }
 162
 163         size_t m_size;
 164         Segment m_inlineSegment;
 165         Vector<Segment*, 32> m_segments;
 166     };
 167
 168 } // namespace JSC
 169
 170 #endif // SegmentedVector_h