Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : // A simple segmented vector class.
8 : //
9 : // This class should be used in preference to mozilla::Vector or nsTArray when
10 : // you are simply gathering items in order to later iterate over them.
11 : //
12 : // - In the case where you don't know the final size in advance, using
13 : // SegmentedVector avoids the need to repeatedly allocate increasingly large
14 : // buffers and copy the data into them.
15 : //
16 : // - In the case where you know the final size in advance and so can set the
17 : // capacity appropriately, using SegmentedVector still avoids the need for
18 : // large allocations (which can trigger OOMs).
19 :
20 : #ifndef mozilla_SegmentedVector_h
21 : #define mozilla_SegmentedVector_h
22 :
23 : #include "mozilla/Alignment.h"
24 : #include "mozilla/AllocPolicy.h"
25 : #include "mozilla/Array.h"
26 : #include "mozilla/LinkedList.h"
27 : #include "mozilla/MemoryReporting.h"
28 : #include "mozilla/Move.h"
29 : #include "mozilla/TypeTraits.h"
30 :
31 : #include <new> // for placement new
32 :
33 : namespace mozilla {
34 :
35 : // |IdealSegmentSize| specifies how big each segment will be in bytes (or as
36 : // close as is possible). Use the following guidelines to choose a size.
37 : //
38 : // - It should be a power-of-two, to avoid slop.
39 : //
40 : // - It should not be too small, so that segment allocations are infrequent,
41 : // and so that per-segment bookkeeping overhead is low. Typically each
42 : // segment should be able to hold hundreds of elements, at least.
43 : //
44 : // - It should not be too large, so that OOMs are unlikely when allocating
45 : // segments, and so that not too much space is wasted when the final segment
46 : // is not full.
47 : //
48 : // The ideal size depends on how the SegmentedVector is used and the size of
49 : // |T|, but reasonable sizes include 1024, 4096 (the default), 8192, and 16384.
50 : //
51 : template<typename T,
52 : size_t IdealSegmentSize = 4096,
53 : typename AllocPolicy = MallocAllocPolicy>
54 : class SegmentedVector : private AllocPolicy
55 : {
56 : template<size_t SegmentCapacity>
57 : struct SegmentImpl
58 : : public mozilla::LinkedListElement<SegmentImpl<SegmentCapacity>>
59 : {
60 94 : SegmentImpl() : mLength(0) {}
61 :
62 18 : ~SegmentImpl()
63 : {
64 2565 : for (uint32_t i = 0; i < mLength; i++) {
65 2547 : (*this)[i].~T();
66 : }
67 18 : }
68 :
69 80917 : uint32_t Length() const { return mLength; }
70 :
71 89702 : T* Elems() { return reinterpret_cast<T*>(&mStorage.mBuf); }
72 :
73 89702 : T& operator[](size_t aIndex)
74 : {
75 89702 : MOZ_ASSERT(aIndex < mLength);
76 89702 : return Elems()[aIndex];
77 : }
78 :
79 : const T& operator[](size_t aIndex) const
80 : {
81 : MOZ_ASSERT(aIndex < mLength);
82 : return Elems()[aIndex];
83 : }
84 :
85 : template<typename U>
86 30184 : void Append(U&& aU)
87 : {
88 30184 : MOZ_ASSERT(mLength < SegmentCapacity);
89 : // Pre-increment mLength so that the bounds-check in operator[] passes.
90 30184 : mLength++;
91 30184 : T* elem = &(*this)[mLength - 1];
92 30184 : new (elem) T(mozilla::Forward<U>(aU));
93 30184 : }
94 :
95 1357 : void PopLast()
96 : {
97 1357 : MOZ_ASSERT(mLength > 0);
98 1357 : (*this)[mLength - 1].~T();
99 1357 : mLength--;
100 1357 : }
101 :
102 : uint32_t mLength;
103 :
104 : // The union ensures that the elements are appropriately aligned.
105 : union Storage
106 : {
107 : char mBuf[sizeof(T) * SegmentCapacity];
108 : mozilla::AlignedElem<MOZ_ALIGNOF(T)> mAlign;
109 : } mStorage;
110 :
111 : static_assert(MOZ_ALIGNOF(T) == MOZ_ALIGNOF(Storage),
112 : "SegmentedVector provides incorrect alignment");
113 : };
114 :
115 : // See how many we elements we can fit in a segment of IdealSegmentSize. If
116 : // IdealSegmentSize is too small, it'll be just one. The +1 is because
117 : // kSingleElementSegmentSize already accounts for one element.
118 : static const size_t kSingleElementSegmentSize = sizeof(SegmentImpl<1>);
119 : static const size_t kSegmentCapacity =
120 : kSingleElementSegmentSize <= IdealSegmentSize
121 : ? (IdealSegmentSize - kSingleElementSegmentSize) / sizeof(T) + 1
122 : : 1;
123 :
124 : public:
125 : typedef SegmentImpl<kSegmentCapacity> Segment;
126 :
127 : // The |aIdealSegmentSize| is only for sanity checking. If it's specified, we
128 : // check that the actual segment size is as close as possible to it. This
129 : // serves as a sanity check for SegmentedVectorCapacity's capacity
130 : // computation.
131 73 : explicit SegmentedVector(size_t aIdealSegmentSize = 0)
132 73 : {
133 : // The difference between the actual segment size and the ideal segment
134 : // size should be less than the size of a single element... unless the
135 : // ideal size was too small, in which case the capacity should be one.
136 73 : MOZ_ASSERT_IF(
137 : aIdealSegmentSize != 0,
138 : (sizeof(Segment) > aIdealSegmentSize && kSegmentCapacity == 1) ||
139 : aIdealSegmentSize - sizeof(Segment) < sizeof(T));
140 73 : }
141 :
142 1 : ~SegmentedVector() { Clear(); }
143 :
144 3990 : bool IsEmpty() const { return !mSegments.getFirst(); }
145 :
146 : // Note that this is O(n) rather than O(1), but the constant factor is very
147 : // small because it only has to do one addition per segment.
148 2 : size_t Length() const
149 : {
150 2 : size_t n = 0;
151 36 : for (auto segment = mSegments.getFirst();
152 : segment;
153 34 : segment = segment->getNext()) {
154 34 : n += segment->Length();
155 : }
156 2 : return n;
157 : }
158 :
159 : // Returns false if the allocation failed. (If you are using an infallible
160 : // allocation policy, use InfallibleAppend() instead.)
161 : template<typename U>
162 30184 : MOZ_MUST_USE bool Append(U&& aU)
163 : {
164 30184 : Segment* last = mSegments.getLast();
165 30184 : if (!last || last->Length() == kSegmentCapacity) {
166 94 : last = this->template pod_malloc<Segment>(1);
167 94 : if (!last) {
168 0 : return false;
169 : }
170 94 : new (last) Segment();
171 94 : mSegments.insertBack(last);
172 : }
173 30184 : last->Append(mozilla::Forward<U>(aU));
174 30184 : return true;
175 : }
176 :
177 : // You should probably only use this instead of Append() if you are using an
178 : // infallible allocation policy. It will crash if the allocation fails.
179 : template<typename U>
180 5375 : void InfallibleAppend(U&& aU)
181 : {
182 5375 : bool ok = Append(mozilla::Forward<U>(aU));
183 5375 : MOZ_RELEASE_ASSERT(ok);
184 5375 : }
185 :
186 55 : void Clear()
187 : {
188 : Segment* segment;
189 67 : while ((segment = mSegments.popFirst())) {
190 12 : segment->~Segment();
191 12 : this->free_(segment);
192 : }
193 43 : }
194 :
195 3720 : T& GetLast()
196 : {
197 3720 : MOZ_ASSERT(!IsEmpty());
198 3720 : Segment* last = mSegments.getLast();
199 3720 : return (*last)[last->Length() - 1];
200 : }
201 :
202 : const T& GetLast() const
203 : {
204 : MOZ_ASSERT(!IsEmpty());
205 : Segment* last = mSegments.getLast();
206 : return (*last)[last->Length() - 1];
207 : }
208 :
209 267 : void PopLast()
210 : {
211 267 : MOZ_ASSERT(!IsEmpty());
212 267 : Segment* last = mSegments.getLast();
213 267 : last->PopLast();
214 267 : if (!last->Length()) {
215 5 : mSegments.popLast();
216 5 : last->~Segment();
217 5 : this->free_(last);
218 : }
219 267 : }
220 :
221 : // Equivalent to calling |PopLast| |aNumElements| times, but potentially
222 : // more efficient.
223 1 : void PopLastN(uint32_t aNumElements)
224 : {
225 1 : MOZ_ASSERT(aNumElements <= Length());
226 :
227 : Segment* last;
228 :
229 : // Pop full segments for as long as we can. Note that this loop
230 : // cleanly handles the case when the initial last segment is not
231 : // full and we are popping more elements than said segment contains.
232 : do {
233 2 : last = mSegments.getLast();
234 :
235 : // The list is empty. We're all done.
236 2 : if (!last) {
237 0 : return;
238 : }
239 :
240 : // Check to see if the list contains too many elements. Handle
241 : // that in the epilogue.
242 2 : uint32_t segmentLen = last->Length();
243 2 : if (segmentLen > aNumElements) {
244 1 : break;
245 : }
246 :
247 : // Destroying the segment destroys all elements contained therein.
248 1 : mSegments.popLast();
249 1 : last->~Segment();
250 1 : this->free_(last);
251 :
252 1 : MOZ_ASSERT(aNumElements >= segmentLen);
253 1 : aNumElements -= segmentLen;
254 1 : if (aNumElements == 0) {
255 0 : return;
256 1 : }
257 : } while (true);
258 :
259 : // Handle the case where the last segment contains more elements
260 : // than we want to pop.
261 1 : MOZ_ASSERT(last);
262 1 : MOZ_ASSERT(last == mSegments.getLast());
263 1 : MOZ_ASSERT(aNumElements < last->Length());
264 1091 : for (uint32_t i = 0; i < aNumElements; ++i) {
265 1090 : last->PopLast();
266 : }
267 1 : MOZ_ASSERT(last->Length() != 0);
268 : }
269 :
270 : // Use this class to iterate over a SegmentedVector, like so:
271 : //
272 : // for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
273 : // MyElem& elem = iter.Get();
274 : // f(elem);
275 : // }
276 : //
277 : // Note, adding new entries to the SegmentedVector while using iterators
278 : // is supported, but removing is not!
279 : // If an iterator has entered Done() state, adding more entries to the
280 : // vector doesn't affect it.
281 : class IterImpl
282 : {
283 : friend class SegmentedVector;
284 :
285 : Segment* mSegment;
286 : size_t mIndex;
287 :
288 48 : explicit IterImpl(SegmentedVector* aVector, bool aFromFirst)
289 48 : : mSegment(aFromFirst ? aVector->mSegments.getFirst() :
290 : aVector->mSegments.getLast())
291 52 : , mIndex(aFromFirst ? 0 :
292 100 : (mSegment ? mSegment->Length() - 1 : 0))
293 : {
294 48 : MOZ_ASSERT_IF(mSegment, mSegment->Length() > 0);
295 48 : }
296 :
297 : public:
298 128201 : bool Done() const { return !mSegment; }
299 :
300 51894 : T& Get()
301 : {
302 51894 : MOZ_ASSERT(!Done());
303 51894 : return (*mSegment)[mIndex];
304 : }
305 :
306 : const T& Get() const
307 : {
308 : MOZ_ASSERT(!Done());
309 : return (*mSegment)[mIndex];
310 : }
311 :
312 46710 : void Next()
313 : {
314 46710 : MOZ_ASSERT(!Done());
315 46710 : mIndex++;
316 46710 : if (mIndex == mSegment->Length()) {
317 97 : mSegment = mSegment->getNext();
318 97 : mIndex = 0;
319 : }
320 46710 : }
321 :
322 1788 : void Prev()
323 : {
324 1788 : MOZ_ASSERT(!Done());
325 1788 : if (mIndex == 0) {
326 1 : mSegment = mSegment->getPrevious();
327 1 : if (mSegment) {
328 1 : mIndex = mSegment->Length() - 1;
329 : }
330 : } else {
331 1787 : --mIndex;
332 : }
333 1788 : }
334 : };
335 :
336 46 : IterImpl Iter() { return IterImpl(this, true); }
337 2 : IterImpl IterFromLast() { return IterImpl(this, false); }
338 :
339 : // Measure the memory consumption of the vector excluding |this|. Note that
340 : // it only measures the vector itself. If the vector elements contain
341 : // pointers to other memory blocks, those blocks must be measured separately
342 : // during a subsequent iteration over the vector.
343 0 : size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
344 : {
345 0 : return mSegments.sizeOfExcludingThis(aMallocSizeOf);
346 : }
347 :
348 : // Like sizeOfExcludingThis(), but measures |this| as well.
349 : size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
350 : {
351 : return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
352 : }
353 :
354 : private:
355 : mozilla::LinkedList<Segment> mSegments;
356 : };
357 :
358 : } // namespace mozilla
359 :
360 : #endif /* mozilla_SegmentedVector_h */
|
