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: SegmentedVector()41 SegmentedVector() 42 : m_size(0) 43 { 44 m_segments.append(&m_inlineSegment); 45 } 46 ~SegmentedVector()47 ~SegmentedVector() 48 { 49 deleteAllSegments(); 50 } 51 size()52 size_t size() const { return m_size; } 53 at(size_t index)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 last()66 T& last() 67 { 68 return at(size() - 1); 69 } 70 append(const U & value)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 removeLast()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 grow(size_t size)94 void grow(size_t size) 95 { 96 ASSERT(size > m_size); 97 ensureSegmentsFor(size); 98 m_size = size; 99 } 100 clear()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 deleteAllSegments()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 segmentExistsFor(size_t index)120 bool segmentExistsFor(size_t index) 121 { 122 return index / SegmentSize < m_segments.size(); 123 } 124 segmentFor(size_t index)125 Segment* segmentFor(size_t index) 126 { 127 return m_segments[index / SegmentSize]; 128 } 129 subscriptFor(size_t index)130 size_t subscriptFor(size_t index) 131 { 132 return index % SegmentSize; 133 } 134 ensureSegmentsFor(size_t size)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 ensureSegment(size_t segmentIndex,size_t size)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 171