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
35namespace 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& last()
131 {
132 return at(size() - 1);
133 }
134
135 template<typename... Args>
136 void append(Args&&... args)
137 {
138 ++m_size;
139 if (!segmentExistsFor(m_size - 1))
140 allocateSegment();
141 new (NotNull, &last()) T(std::forward<Args>(args)...);
142 }
143
144 template<typename... Args>
145 T& alloc(Args&&... args)
146 {
147 append(std::forward<Args>(args)...);
148 return last();
149 }
150
151 void removeLast()
152 {
153 last().~T();
154 --m_size;
155 }
156
157 void grow(size_t size)
158 {
159 ASSERT(size > m_size);
160 ensureSegmentsFor(size);
161 size_t oldSize = m_size;
162 m_size = size;
163 for (size_t i = oldSize; i < m_size; ++i)
164 new (NotNull, &at(i)) T();
165 }
166
167 void clear()
168 {
169 deleteAllSegments();
170 m_segments.clear();
171 m_size = 0;
172 }
173
174 Iterator begin()
175 {
176 return Iterator(*this, 0);
177 }
178
179 Iterator end()
180 {
181 return Iterator(*this, m_size);
182 }
183
184 void shrinkToFit()
185 {
186 m_segments.shrinkToFit();
187 }
188
189 private:
190 struct Segment {
191#if COMPILER(MSVC)
192#pragma warning(push)
193#pragma warning(disable: 4200)
194#endif
195 T entries[0];
196#if COMPILER(MSVC)
197#pragma warning(pop)
198#endif
199 };
200
201 void deleteAllSegments()
202 {
203 for (size_t i = 0; i < m_size; ++i)
204 at(i).~T();
205 for (size_t i = 0; i < m_segments.size(); ++i)
206 fastFree(m_segments[i]);
207 }
208
209 bool segmentExistsFor(size_t index)
210 {
211 return index / SegmentSize < m_segments.size();
212 }
213
214 Segment* segmentFor(size_t index)
215 {
216 return m_segments[index / SegmentSize];
217 }
218
219 size_t subscriptFor(size_t index)
220 {
221 return index % SegmentSize;
222 }
223
224 void ensureSegmentsFor(size_t size)
225 {
226 size_t segmentCount = (m_size + SegmentSize - 1) / SegmentSize;
227 size_t neededSegmentCount = (size + SegmentSize - 1) / SegmentSize;
228
229 for (size_t i = segmentCount ? segmentCount - 1 : 0; i < neededSegmentCount; ++i)
230 ensureSegment(i);
231 }
232
233 void ensureSegment(size_t segmentIndex)
234 {
235 ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
236 if (segmentIndex == m_segments.size())
237 allocateSegment();
238 }
239
240 void allocateSegment()
241 {
242 m_segments.append(static_cast<Segment*>(fastMalloc(sizeof(T) * SegmentSize)));
243 }
244
245 size_t m_size { 0 };
246 Vector<Segment*> m_segments;
247 };
248
249} // namespace WTF
250
251using WTF::SegmentedVector;
252
253#endif // SegmentedVector_h
254