Unreviewed, rolling out r234489.
[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 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> class SegmentedVector;
39     template <typename T, size_t SegmentSize = 8> class SegmentedVectorIterator {
40     private:
41         friend class SegmentedVector<T, SegmentSize>;
42     public:
43         typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
44
45         ~SegmentedVectorIterator() { }
46
47         T& operator*() const { return m_vector.at(m_index); }
48         T* operator->() const { return &m_vector.at(m_index); }
49
50         // Only prefix ++ operator supported
51         Iterator& operator++()
52         {
53             m_index++;
54             return *this;
55         }
56
57         bool operator==(const Iterator& other) const
58         {
59             return m_index == other.m_index && &m_vector == &other.m_vector;
60         }
61
62         bool operator!=(const Iterator& other) const
63         {
64             return m_index != other.m_index || &m_vector != &other.m_vector;
65         }
66
67         SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize>& other)
68         {
69             m_vector = other.m_vector;
70             m_index = other.m_index;
71             return *this;
72         }
73
74     private:
75         SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t index)
76             : m_vector(vector)
77             , m_index(index)
78         {
79         }
80
81         SegmentedVector<T, SegmentSize>& m_vector;
82         size_t m_index;
83     };
84
85     // SegmentedVector is just like Vector, but it doesn't move the values
86     // stored in its buffer when it grows. Therefore, it is safe to keep
87     // pointers into a SegmentedVector. The default tuning values are
88     // optimized for segmented vectors that get large; you may want to use
89     // SegmentedVector<thingy, 1> if you don't expect a lot of entries.
90     template <typename T, size_t SegmentSize>
91     class SegmentedVector {
92         friend class SegmentedVectorIterator<T, SegmentSize>;
93         WTF_MAKE_NONCOPYABLE(SegmentedVector);
94         WTF_MAKE_FAST_ALLOCATED;
95
96     public:
97         typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
98
99         SegmentedVector() = default;
100
101         ~SegmentedVector()
102         {
103             deleteAllSegments();
104         }
105
106         size_t size() const { return m_size; }
107         bool isEmpty() const { return !size(); }
108
109         T& at(size_t index)
110         {
111             ASSERT_WITH_SECURITY_IMPLICATION(index < m_size);
112             return segmentFor(index)->entries[subscriptFor(index)];
113         }
114
115         const T& at(size_t index) const
116         {
117             return const_cast<SegmentedVector<T, SegmentSize>*>(this)->at(index);
118         }
119
120         T& operator[](size_t index)
121         {
122             return at(index);
123         }
124
125         const T& operator[](size_t index) const
126         {
127             return at(index);
128         }
129
130         T& first()
131         {
132             ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
133             return at(0);
134         }
135         const T& first() const
136         {
137             ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
138             return at(0);
139         }
140         T& last()
141         {
142             ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
143             return at(size() - 1);
144         }
145         const T& last() const
146         {
147             ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
148             return at(size() - 1);
149         }
150
151         T takeLast()
152         {
153             ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
154             T result = WTFMove(last());
155             --m_size;
156             return result;
157         }
158
159         template<typename... Args>
160         void append(Args&&... args)
161         {
162             ++m_size;
163             if (!segmentExistsFor(m_size - 1))
164                 allocateSegment();
165             new (NotNull, &last()) T(std::forward<Args>(args)...);
166         }
167
168         template<typename... Args>
169         T& alloc(Args&&... args)
170         {
171             append(std::forward<Args>(args)...);
172             return last();
173         }
174
175         void removeLast()
176         {
177             last().~T();
178             --m_size;
179         }
180
181         void grow(size_t size)
182         {
183             ASSERT(size > m_size);
184             ensureSegmentsFor(size);
185             size_t oldSize = m_size;
186             m_size = size;
187             for (size_t i = oldSize; i < m_size; ++i)
188                 new (NotNull, &at(i)) T();
189         }
190
191         void clear()
192         {
193             deleteAllSegments();
194             m_segments.clear();
195             m_size = 0;
196         }
197
198         Iterator begin()
199         {
200             return Iterator(*this, 0);
201         }
202
203         Iterator end()
204         {
205             return Iterator(*this, m_size);
206         }
207         
208         void shrinkToFit()
209         {
210             m_segments.shrinkToFit();
211         }
212
213     private:
214         struct Segment {
215 #if COMPILER(MSVC)
216 #pragma warning(push)
217 #pragma warning(disable: 4200)
218 #endif
219             T entries[0];
220 #if COMPILER(MSVC)
221 #pragma warning(pop)
222 #endif
223         };
224
225         void deleteAllSegments()
226         {
227             for (size_t i = 0; i < m_size; ++i)
228                 at(i).~T();
229             for (size_t i = 0; i < m_segments.size(); ++i)
230                 fastFree(m_segments[i]);
231         }
232
233         bool segmentExistsFor(size_t index)
234         {
235             return index / SegmentSize < m_segments.size();
236         }
237
238         Segment* segmentFor(size_t index)
239         {
240             return m_segments[index / SegmentSize];
241         }
242
243         size_t subscriptFor(size_t index)
244         {
245             return index % SegmentSize;
246         }
247
248         void ensureSegmentsFor(size_t size)
249         {
250             size_t segmentCount = (m_size + SegmentSize - 1) / SegmentSize;
251             size_t neededSegmentCount = (size + SegmentSize - 1) / SegmentSize;
252
253             for (size_t i = segmentCount ? segmentCount - 1 : 0; i < neededSegmentCount; ++i)
254                 ensureSegment(i);
255         }
256
257         void ensureSegment(size_t segmentIndex)
258         {
259             ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
260             if (segmentIndex == m_segments.size())
261                 allocateSegment();
262         }
263
264         void allocateSegment()
265         {
266             m_segments.append(static_cast<Segment*>(fastMalloc(sizeof(T) * SegmentSize)));
267         }
268
269         size_t m_size { 0 };
270         Vector<Segment*> m_segments;
271     };
272
273 } // namespace WTF
274
275 using WTF::SegmentedVector;
276
277 #endif // SegmentedVector_h