Make SegmentedVector Noncopyable
[WebKit-https.git] / 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         const T& at(size_t index) const
135         {
136             return const_cast<SegmentedVector<T, SegmentSize, InlineCapacity>*>(this)->at(index);
137         }
138
139         T& operator[](size_t index)
140         {
141             return at(index);
142         }
143
144         const T& operator[](size_t index) const
145         {
146             return at(index);
147         }
148
149         T& last()
150         {
151             return at(size() - 1);
152         }
153
154         template <typename U> void append(const U& value)
155         {
156             ++m_size;
157
158             if (m_size <= SegmentSize) {
159                 m_inlineSegment.uncheckedAppend(value);
160                 return;
161             }
162
163             if (!segmentExistsFor(m_size - 1))
164                 m_segments.append(new Segment);
165             segmentFor(m_size - 1)->uncheckedAppend(value);
166         }
167
168         T& alloc()
169         {
170             append<T>(T());
171             return last();
172         }
173
174         void removeLast()
175         {
176             if (m_size <= SegmentSize)
177                 m_inlineSegment.removeLast();
178             else
179                 segmentFor(m_size - 1)->removeLast();
180             --m_size;
181         }
182
183         void grow(size_t size)
184         {
185             ASSERT(size > m_size);
186             ensureSegmentsFor(size);
187             m_size = size;
188         }
189
190         void clear()
191         {
192             deleteAllSegments();
193             m_segments.resize(1);
194             m_inlineSegment.clear();
195             m_size = 0;
196         }
197
198         Iterator begin()
199         {
200             return Iterator(*this, 0, m_size ? 0 : SegmentSize);
201         }
202
203         Iterator end()
204         {
205             return Iterator(*this, 0, SegmentSize);
206         }
207         
208         void shrinkToFit()
209         {
210             m_segments.shrinkToFit();
211         }
212
213     private:
214         typedef Vector<T, SegmentSize> Segment;
215
216         void deleteAllSegments()
217         {
218             // Skip the first segment, because it's our inline segment, which was
219             // not created by new.
220             for (size_t i = 1; i < m_segments.size(); i++)
221                 delete m_segments[i];
222         }
223
224         bool segmentExistsFor(size_t index)
225         {
226             return index / SegmentSize < m_segments.size();
227         }
228
229         Segment* segmentFor(size_t index)
230         {
231             return m_segments[index / SegmentSize];
232         }
233
234         size_t subscriptFor(size_t index)
235         {
236             return index % SegmentSize;
237         }
238
239         void ensureSegmentsFor(size_t size)
240         {
241             size_t segmentCount = m_size / SegmentSize;
242             if (m_size % SegmentSize)
243                 ++segmentCount;
244             segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
245
246             size_t neededSegmentCount = size / SegmentSize;
247             if (size % SegmentSize)
248                 ++neededSegmentCount;
249
250             // Fill up to N - 1 segments.
251             size_t end = neededSegmentCount - 1;
252             for (size_t i = segmentCount - 1; i < end; ++i)
253                 ensureSegment(i, SegmentSize);
254
255             // Grow segment N to accomodate the remainder.
256             ensureSegment(end, subscriptFor(size - 1) + 1);
257         }
258
259         void ensureSegment(size_t segmentIndex, size_t size)
260         {
261             ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
262             if (segmentIndex == m_segments.size())
263                 m_segments.append(new Segment);
264             m_segments[segmentIndex]->grow(size);
265         }
266
267         size_t m_size;
268         Segment m_inlineSegment;
269         Vector<Segment*, InlineCapacity> m_segments;
270     };
271
272 } // namespace WTF
273
274 using WTF::SegmentedVector;
275
276 #endif // SegmentedVector_h