• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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