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 type/length-parametrized vector class. */
8 :
9 : #ifndef mozilla_Vector_h
10 : #define mozilla_Vector_h
11 :
12 : #include "mozilla/Alignment.h"
13 : #include "mozilla/AllocPolicy.h"
14 : #include "mozilla/ArrayUtils.h" // for PointerRangeSize
15 : #include "mozilla/Assertions.h"
16 : #include "mozilla/Attributes.h"
17 : #include "mozilla/MathAlgorithms.h"
18 : #include "mozilla/MemoryReporting.h"
19 : #include "mozilla/Move.h"
20 : #include "mozilla/OperatorNewExtensions.h"
21 : #include "mozilla/ReentrancyGuard.h"
22 : #include "mozilla/TemplateLib.h"
23 : #include "mozilla/TypeTraits.h"
24 :
25 : #include <new> // for placement new
26 :
27 : /* Silence dire "bugs in previous versions of MSVC have been fixed" warnings */
28 : #ifdef _MSC_VER
29 : #pragma warning(push)
30 : #pragma warning(disable:4345)
31 : #endif
32 :
33 : namespace mozilla {
34 :
35 : template<typename T, size_t N, class AllocPolicy>
36 : class Vector;
37 :
38 : namespace detail {
39 :
40 : /*
41 : * Check that the given capacity wastes the minimal amount of space if
42 : * allocated on the heap. This means that aCapacity*sizeof(T) is as close to a
43 : * power-of-two as possible. growStorageBy() is responsible for ensuring this.
44 : */
45 : template<typename T>
46 139654 : static bool CapacityHasExcessSpace(size_t aCapacity)
47 : {
48 139654 : size_t size = aCapacity * sizeof(T);
49 139654 : return RoundUpPow2(size) - size >= sizeof(T);
50 : }
51 :
52 : /*
53 : * This template class provides a default implementation for vector operations
54 : * when the element type is not known to be a POD, as judged by IsPod.
55 : */
56 : template<typename T, size_t N, class AP, bool IsPod>
57 : struct VectorImpl
58 : {
59 : /*
60 : * Constructs an object in the uninitialized memory at *aDst with aArgs.
61 : */
62 : template<typename... Args>
63 : MOZ_NONNULL(1)
64 633172 : static inline void new_(T* aDst, Args&&... aArgs)
65 : {
66 633172 : new(KnownNotNull, aDst) T(Forward<Args>(aArgs)...);
67 633172 : }
68 :
69 : /* Destroys constructed objects in the range [aBegin, aEnd). */
70 497837 : static inline void destroy(T* aBegin, T* aEnd)
71 : {
72 497837 : MOZ_ASSERT(aBegin <= aEnd);
73 527543 : for (T* p = aBegin; p < aEnd; ++p) {
74 29706 : p->~T();
75 : }
76 497837 : }
77 :
78 : /* Constructs objects in the uninitialized range [aBegin, aEnd). */
79 8871 : static inline void initialize(T* aBegin, T* aEnd)
80 : {
81 8871 : MOZ_ASSERT(aBegin <= aEnd);
82 40577 : for (T* p = aBegin; p < aEnd; ++p) {
83 31706 : new_(p);
84 : }
85 8871 : }
86 :
87 : /*
88 : * Copy-constructs objects in the uninitialized range
89 : * [aDst, aDst+(aSrcEnd-aSrcStart)) from the range [aSrcStart, aSrcEnd).
90 : */
91 : template<typename U>
92 7153 : static inline void copyConstruct(T* aDst,
93 : const U* aSrcStart, const U* aSrcEnd)
94 : {
95 7153 : MOZ_ASSERT(aSrcStart <= aSrcEnd);
96 7309 : for (const U* p = aSrcStart; p < aSrcEnd; ++p, ++aDst) {
97 156 : new_(aDst, *p);
98 : }
99 7153 : }
100 :
101 : /*
102 : * Move-constructs objects in the uninitialized range
103 : * [aDst, aDst+(aSrcEnd-aSrcStart)) from the range [aSrcStart, aSrcEnd).
104 : */
105 : template<typename U>
106 89520 : static inline void moveConstruct(T* aDst, U* aSrcStart, U* aSrcEnd)
107 : {
108 89520 : MOZ_ASSERT(aSrcStart <= aSrcEnd);
109 145197 : for (U* p = aSrcStart; p < aSrcEnd; ++p, ++aDst) {
110 55677 : new_(aDst, Move(*p));
111 : }
112 89520 : }
113 :
114 : /*
115 : * Copy-constructs objects in the uninitialized range [aDst, aDst+aN) from
116 : * the same object aU.
117 : */
118 : template<typename U>
119 8004 : static inline void copyConstructN(T* aDst, size_t aN, const U& aU)
120 : {
121 32418 : for (T* end = aDst + aN; aDst < end; ++aDst) {
122 24414 : new_(aDst, aU);
123 : }
124 8004 : }
125 :
126 : /*
127 : * Grows the given buffer to have capacity aNewCap, preserving the objects
128 : * constructed in the range [begin, end) and updating aV. Assumes that (1)
129 : * aNewCap has not overflowed, and (2) multiplying aNewCap by sizeof(T) will
130 : * not overflow.
131 : */
132 : static inline MOZ_MUST_USE bool
133 19253 : growTo(Vector<T, N, AP>& aV, size_t aNewCap)
134 : {
135 19253 : MOZ_ASSERT(!aV.usingInlineStorage());
136 19253 : MOZ_ASSERT(!CapacityHasExcessSpace<T>(aNewCap));
137 19253 : T* newbuf = aV.template pod_malloc<T>(aNewCap);
138 19253 : if (MOZ_UNLIKELY(!newbuf)) {
139 0 : return false;
140 : }
141 19253 : T* dst = newbuf;
142 19253 : T* src = aV.beginNoCheck();
143 393143 : for (; src < aV.endNoCheck(); ++dst, ++src) {
144 186945 : new_(dst, Move(*src));
145 : }
146 19253 : VectorImpl::destroy(aV.beginNoCheck(), aV.endNoCheck());
147 19253 : aV.free_(aV.mBegin);
148 19253 : aV.mBegin = newbuf;
149 : /* aV.mLength is unchanged. */
150 19253 : aV.mTail.mCapacity = aNewCap;
151 19253 : return true;
152 : }
153 : };
154 :
155 : /*
156 : * This partial template specialization provides a default implementation for
157 : * vector operations when the element type is known to be a POD, as judged by
158 : * IsPod.
159 : */
160 : template<typename T, size_t N, class AP>
161 : struct VectorImpl<T, N, AP, true>
162 : {
163 : template<typename... Args>
164 : MOZ_NONNULL(1)
165 8748445 : static inline void new_(T* aDst, Args&&... aArgs)
166 : {
167 : // Explicitly construct a local object instead of using a temporary since
168 : // T(args...) will be treated like a C-style cast in the unary case and
169 : // allow unsafe conversions. Both forms should be equivalent to an
170 : // optimizing compiler.
171 8748445 : T temp(Forward<Args>(aArgs)...);
172 8748417 : *aDst = temp;
173 8748417 : }
174 :
175 393339 : static inline void destroy(T*, T*) {}
176 :
177 709128 : static inline void initialize(T* aBegin, T* aEnd)
178 : {
179 : /*
180 : * You would think that memset would be a big win (or even break even)
181 : * when we know T is a POD. But currently it's not. This is probably
182 : * because |append| tends to be given small ranges and memset requires
183 : * a function call that doesn't get inlined.
184 : *
185 : * memset(aBegin, 0, sizeof(T) * (aEnd - aBegin));
186 : */
187 709128 : MOZ_ASSERT(aBegin <= aEnd);
188 2153744 : for (T* p = aBegin; p < aEnd; ++p) {
189 1444616 : new_(p);
190 : }
191 709128 : }
192 :
193 : template<typename U>
194 3844740 : static inline void copyConstruct(T* aDst,
195 : const U* aSrcStart, const U* aSrcEnd)
196 : {
197 : /*
198 : * See above memset comment. Also, notice that copyConstruct is
199 : * currently templated (T != U), so memcpy won't work without
200 : * requiring T == U.
201 : *
202 : * memcpy(aDst, aSrcStart, sizeof(T) * (aSrcEnd - aSrcStart));
203 : */
204 3844740 : MOZ_ASSERT(aSrcStart <= aSrcEnd);
205 9849672 : for (const U* p = aSrcStart; p < aSrcEnd; ++p, ++aDst) {
206 6004794 : new_(aDst, *p);
207 : }
208 3844878 : }
209 :
210 : template<typename U>
211 79339 : static inline void moveConstruct(T* aDst,
212 : const U* aSrcStart, const U* aSrcEnd)
213 : {
214 79339 : copyConstruct(aDst, aSrcStart, aSrcEnd);
215 79339 : }
216 :
217 51 : static inline void copyConstructN(T* aDst, size_t aN, const T& aT)
218 : {
219 6028 : for (T* end = aDst + aN; aDst < end; ++aDst) {
220 5977 : new_(aDst, aT);
221 : }
222 51 : }
223 :
224 : static inline MOZ_MUST_USE bool
225 16663 : growTo(Vector<T, N, AP>& aV, size_t aNewCap)
226 : {
227 16663 : MOZ_ASSERT(!aV.usingInlineStorage());
228 16663 : MOZ_ASSERT(!CapacityHasExcessSpace<T>(aNewCap));
229 : T* newbuf =
230 16663 : aV.template pod_realloc<T>(aV.mBegin, aV.mTail.mCapacity, aNewCap);
231 16663 : if (MOZ_UNLIKELY(!newbuf)) {
232 0 : return false;
233 : }
234 16663 : aV.mBegin = newbuf;
235 : /* aV.mLength is unchanged. */
236 16663 : aV.mTail.mCapacity = aNewCap;
237 16663 : return true;
238 : }
239 :
240 : static inline void
241 0 : podResizeToFit(Vector<T, N, AP>& aV)
242 : {
243 0 : if (aV.usingInlineStorage() || aV.mLength == aV.mTail.mCapacity) {
244 0 : return;
245 : }
246 : T* newbuf =
247 0 : aV.template pod_realloc<T>(aV.mBegin, aV.mTail.mCapacity, aV.mLength);
248 0 : if (MOZ_UNLIKELY(!newbuf)) {
249 0 : return;
250 : }
251 0 : aV.mBegin = newbuf;
252 0 : aV.mTail.mCapacity = aV.mLength;
253 : }
254 : };
255 :
256 : // A struct for TestVector.cpp to access private internal fields.
257 : // DO NOT DEFINE IN YOUR OWN CODE.
258 : struct VectorTesting;
259 :
260 : } // namespace detail
261 :
262 : /*
263 : * STL-like container providing a short-lived, dynamic buffer. Vector calls the
264 : * constructors/destructors of all elements stored in its internal buffer, so
265 : * non-PODs may be safely used. Additionally, Vector will store the first N
266 : * elements in-place before resorting to dynamic allocation.
267 : *
268 : * T requirements:
269 : * - default and copy constructible, assignable, destructible
270 : * - operations do not throw
271 : * MinInlineCapacity requirements:
272 : * - any value, however, MinInlineCapacity is clamped to min/max values
273 : * AllocPolicy:
274 : * - see "Allocation policies" in AllocPolicy.h (defaults to
275 : * mozilla::MallocAllocPolicy)
276 : *
277 : * Vector is not reentrant: T member functions called during Vector member
278 : * functions must not call back into the same object!
279 : */
280 : template<typename T,
281 : size_t MinInlineCapacity = 0,
282 : class AllocPolicy = MallocAllocPolicy>
283 : class MOZ_NON_PARAM Vector final : private AllocPolicy
284 : {
285 : /* utilities */
286 :
287 : static const bool kElemIsPod = IsPod<T>::value;
288 : typedef detail::VectorImpl<T, MinInlineCapacity, AllocPolicy, kElemIsPod> Impl;
289 : friend struct detail::VectorImpl<T, MinInlineCapacity, AllocPolicy, kElemIsPod>;
290 :
291 : friend struct detail::VectorTesting;
292 :
293 : MOZ_MUST_USE bool growStorageBy(size_t aIncr);
294 : MOZ_MUST_USE bool convertToHeapStorage(size_t aNewCap);
295 : MOZ_MUST_USE bool maybeCheckSimulatedOOM(size_t aRequestedSize);
296 :
297 : /* magic constants */
298 :
299 : /**
300 : * The maximum space allocated for inline element storage.
301 : *
302 : * We reduce space by what the AllocPolicy base class and prior Vector member
303 : * fields likely consume to attempt to play well with binary size classes.
304 : */
305 : static constexpr size_t kMaxInlineBytes =
306 : 1024 - (sizeof(AllocPolicy) + sizeof(T*) + sizeof(size_t) + sizeof(size_t));
307 :
308 : /**
309 : * The number of T elements of inline capacity built into this Vector. This
310 : * is usually |MinInlineCapacity|, but it may be less (or zero!) for large T.
311 : *
312 : * We use a partially-specialized template (not explicit specialization, which
313 : * is only allowed at namespace scope) to compute this value. The benefit is
314 : * that |sizeof(T)| need not be computed, and |T| doesn't have to be fully
315 : * defined at the time |Vector<T>| appears, if no inline storage is requested.
316 : */
317 : template<size_t MinimumInlineCapacity, size_t Dummy>
318 : struct ComputeCapacity
319 : {
320 : static constexpr size_t value =
321 : tl::Min<MinimumInlineCapacity, kMaxInlineBytes / sizeof(T)>::value;
322 : };
323 :
324 : template<size_t Dummy>
325 : struct ComputeCapacity<0, Dummy>
326 : {
327 : static constexpr size_t value = 0;
328 : };
329 :
330 : /** The actual inline capacity in number of elements T. This may be zero! */
331 : static constexpr size_t kInlineCapacity =
332 : ComputeCapacity<MinInlineCapacity, 0>::value;
333 :
334 : /* member data */
335 :
336 : /*
337 : * Pointer to the buffer, be it inline or heap-allocated. Only [mBegin,
338 : * mBegin + mLength) hold valid constructed T objects. The range [mBegin +
339 : * mLength, mBegin + mCapacity) holds uninitialized memory. The range
340 : * [mBegin + mLength, mBegin + mReserved) also holds uninitialized memory
341 : * previously allocated by a call to reserve().
342 : */
343 : T* mBegin;
344 :
345 : /* Number of elements in the vector. */
346 : size_t mLength;
347 :
348 : /*
349 : * Memory used to store capacity, reserved element count (debug builds only),
350 : * and inline storage. The simple "answer" is:
351 : *
352 : * size_t mCapacity;
353 : * #ifdef DEBUG
354 : * size_t mReserved;
355 : * #endif
356 : * alignas(T) unsigned char mBytes[kInlineCapacity * sizeof(T)];
357 : *
358 : * but there are complications. First, C++ forbids zero-sized arrays that
359 : * might result. Second, we don't want zero capacity to affect Vector's size
360 : * (even empty classes take up a byte, unless they're base classes).
361 : *
362 : * Yet again, we eliminate the zero-sized array using partial specialization.
363 : * And we eliminate potential size hit by putting capacity/reserved in one
364 : * struct, then putting the array (if any) in a derived struct. If no array
365 : * is needed, the derived struct won't consume extra space.
366 : */
367 : struct CapacityAndReserved
368 : {
369 622150 : explicit CapacityAndReserved(size_t aCapacity, size_t aReserved)
370 : : mCapacity(aCapacity)
371 : #ifdef DEBUG
372 622150 : , mReserved(aReserved)
373 : #endif
374 622150 : {}
375 98639 : CapacityAndReserved() = default;
376 :
377 : /* Max number of elements storable in the vector without resizing. */
378 : size_t mCapacity;
379 :
380 : #ifdef DEBUG
381 : /* Max elements of reserved or used space in this vector. */
382 : size_t mReserved;
383 : #endif
384 : };
385 :
386 : // Silence warnings about this struct possibly being padded dued to the
387 : // alignas() in it -- there's nothing we can do to avoid it.
388 : #ifdef _MSC_VER
389 : # pragma warning(push)
390 : # pragma warning(disable:4324)
391 : #endif // _MSC_VER
392 :
393 : template<size_t Capacity, size_t Dummy>
394 : struct CRAndStorage : CapacityAndReserved
395 : {
396 431891 : explicit CRAndStorage(size_t aCapacity, size_t aReserved)
397 431891 : : CapacityAndReserved(aCapacity, aReserved)
398 431890 : {}
399 61241 : CRAndStorage() = default;
400 :
401 : alignas(T) unsigned char mBytes[Capacity * sizeof(T)];
402 :
403 : // GCC fails due to -Werror=strict-aliasing if |mBytes| is directly cast to
404 : // T*. Indirecting through this function addresses the problem.
405 4119988 : void* data() { return mBytes; }
406 :
407 4119988 : T* storage() { return static_cast<T*>(data()); }
408 : };
409 :
410 : template<size_t Dummy>
411 : struct CRAndStorage<0, Dummy> : CapacityAndReserved
412 : {
413 190261 : explicit CRAndStorage(size_t aCapacity, size_t aReserved)
414 190261 : : CapacityAndReserved(aCapacity, aReserved)
415 190261 : {}
416 37398 : CRAndStorage() = default;
417 :
418 2494835 : T* storage() { return nullptr; }
419 : };
420 :
421 : CRAndStorage<kInlineCapacity, 0> mTail;
422 :
423 : #ifdef _MSC_VER
424 : # pragma warning(pop)
425 : #endif // _MSC_VER
426 :
427 : #ifdef DEBUG
428 : friend class ReentrancyGuard;
429 : bool mEntered;
430 : #endif
431 :
432 : /* private accessors */
433 :
434 5893592 : bool usingInlineStorage() const
435 : {
436 5893592 : return mBegin == const_cast<Vector*>(this)->inlineStorage();
437 : }
438 :
439 6614862 : T* inlineStorage()
440 : {
441 6614862 : return mTail.storage();
442 : }
443 :
444 1144172 : T* beginNoCheck() const
445 : {
446 1144172 : return mBegin;
447 : }
448 :
449 8411588 : T* endNoCheck()
450 : {
451 8411588 : return mBegin + mLength;
452 : }
453 :
454 : const T* endNoCheck() const
455 : {
456 : return mBegin + mLength;
457 : }
458 :
459 : #ifdef DEBUG
460 : /**
461 : * The amount of explicitly allocated space in this vector that is immediately
462 : * available to be filled by appending additional elements. This value is
463 : * always greater than or equal to |length()| -- the vector's actual elements
464 : * are implicitly reserved. This value is always less than or equal to
465 : * |capacity()|. It may be explicitly increased using the |reserve()| method.
466 : */
467 9978392 : size_t reserved() const
468 : {
469 9978392 : MOZ_ASSERT(mLength <= mTail.mReserved);
470 9978392 : MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
471 9978392 : return mTail.mReserved;
472 : }
473 : #endif
474 :
475 : /* Append operations guaranteed to succeed due to pre-reserved space. */
476 : template<typename U> void internalAppend(U&& aU);
477 : template<typename U, size_t O, class BP>
478 : void internalAppendAll(const Vector<U, O, BP>& aU);
479 : void internalAppendN(const T& aT, size_t aN);
480 : template<typename U> void internalAppend(const U* aBegin, size_t aLength);
481 :
482 : public:
483 : static const size_t sMaxInlineStorage = MinInlineCapacity;
484 :
485 : typedef T ElementType;
486 :
487 : explicit Vector(AllocPolicy = AllocPolicy());
488 : Vector(Vector&&); /* Move constructor. */
489 : Vector& operator=(Vector&&); /* Move assignment. */
490 : ~Vector();
491 :
492 : /* accessors */
493 :
494 15 : const AllocPolicy& allocPolicy() const { return *this; }
495 :
496 1678086 : AllocPolicy& allocPolicy() { return *this; }
497 :
498 : enum { InlineLength = MinInlineCapacity };
499 :
500 6010037 : size_t length() const { return mLength; }
501 :
502 1868092 : bool empty() const { return mLength == 0; }
503 :
504 1841563 : size_t capacity() const { return mTail.mCapacity; }
505 :
506 6215259 : T* begin()
507 : {
508 6215259 : MOZ_ASSERT(!mEntered);
509 6215259 : return mBegin;
510 : }
511 :
512 2642317 : const T* begin() const
513 : {
514 2642317 : MOZ_ASSERT(!mEntered);
515 2642317 : return mBegin;
516 : }
517 :
518 2415057 : T* end()
519 : {
520 2415057 : MOZ_ASSERT(!mEntered);
521 2415057 : return mBegin + mLength;
522 : }
523 :
524 107121 : const T* end() const
525 : {
526 107121 : MOZ_ASSERT(!mEntered);
527 107121 : return mBegin + mLength;
528 : }
529 :
530 4121945 : T& operator[](size_t aIndex)
531 : {
532 4121945 : MOZ_ASSERT(!mEntered);
533 4121945 : MOZ_ASSERT(aIndex < mLength);
534 4121945 : return begin()[aIndex];
535 : }
536 :
537 2529019 : const T& operator[](size_t aIndex) const
538 : {
539 2529019 : MOZ_ASSERT(!mEntered);
540 2529019 : MOZ_ASSERT(aIndex < mLength);
541 2529019 : return begin()[aIndex];
542 : }
543 :
544 682558 : T& back()
545 : {
546 682558 : MOZ_ASSERT(!mEntered);
547 682558 : MOZ_ASSERT(!empty());
548 682558 : return *(end() - 1);
549 : }
550 :
551 7812 : const T& back() const
552 : {
553 7812 : MOZ_ASSERT(!mEntered);
554 7812 : MOZ_ASSERT(!empty());
555 7812 : return *(end() - 1);
556 : }
557 :
558 : class Range
559 : {
560 : friend class Vector;
561 : T* mCur;
562 : T* mEnd;
563 0 : Range(T* aCur, T* aEnd)
564 : : mCur(aCur)
565 0 : , mEnd(aEnd)
566 : {
567 0 : MOZ_ASSERT(aCur <= aEnd);
568 0 : }
569 :
570 : public:
571 0 : bool empty() const { return mCur == mEnd; }
572 : size_t remain() const { return PointerRangeSize(mCur, mEnd); }
573 0 : T& front() const { MOZ_ASSERT(!empty()); return *mCur; }
574 0 : void popFront() { MOZ_ASSERT(!empty()); ++mCur; }
575 : T popCopyFront() { MOZ_ASSERT(!empty()); return *mCur++; }
576 : };
577 :
578 : class ConstRange
579 : {
580 : friend class Vector;
581 : const T* mCur;
582 : const T* mEnd;
583 0 : ConstRange(const T* aCur, const T* aEnd)
584 : : mCur(aCur)
585 0 : , mEnd(aEnd)
586 : {
587 0 : MOZ_ASSERT(aCur <= aEnd);
588 0 : }
589 :
590 : public:
591 0 : bool empty() const { return mCur == mEnd; }
592 : size_t remain() const { return PointerRangeSize(mCur, mEnd); }
593 0 : const T& front() const { MOZ_ASSERT(!empty()); return *mCur; }
594 0 : void popFront() { MOZ_ASSERT(!empty()); ++mCur; }
595 0 : T popCopyFront() { MOZ_ASSERT(!empty()); return *mCur++; }
596 : };
597 :
598 0 : Range all() { return Range(begin(), end()); }
599 0 : ConstRange all() const { return ConstRange(begin(), end()); }
600 :
601 : /* mutators */
602 :
603 : /**
604 : * Reverse the order of the elements in the vector in place.
605 : */
606 : void reverse();
607 :
608 : /**
609 : * Given that the vector is empty, grow the internal capacity to |aRequest|,
610 : * keeping the length 0.
611 : */
612 : MOZ_MUST_USE bool initCapacity(size_t aRequest);
613 :
614 : /**
615 : * Given that the vector is empty, grow the internal capacity and length to
616 : * |aRequest| leaving the elements' memory completely uninitialized (with all
617 : * the associated hazards and caveats). This avoids the usual allocation-size
618 : * rounding that happens in resize and overhead of initialization for elements
619 : * that are about to be overwritten.
620 : */
621 : MOZ_MUST_USE bool initLengthUninitialized(size_t aRequest);
622 :
623 : /**
624 : * If reserve(aRequest) succeeds and |aRequest >= length()|, then appending
625 : * |aRequest - length()| elements, in any sequence of append/appendAll calls,
626 : * is guaranteed to succeed.
627 : *
628 : * A request to reserve an amount less than the current length does not affect
629 : * reserved space.
630 : */
631 : MOZ_MUST_USE bool reserve(size_t aRequest);
632 :
633 : /**
634 : * Destroy elements in the range [end() - aIncr, end()). Does not deallocate
635 : * or unreserve storage for those elements.
636 : */
637 : void shrinkBy(size_t aIncr);
638 :
639 : /**
640 : * Destroy elements in the range [aNewLength, end()). Does not deallocate
641 : * or unreserve storage for those elements.
642 : */
643 : void shrinkTo(size_t aNewLength);
644 :
645 : /** Grow the vector by aIncr elements. */
646 : MOZ_MUST_USE bool growBy(size_t aIncr);
647 :
648 : /** Call shrinkBy or growBy based on whether newSize > length(). */
649 : MOZ_MUST_USE bool resize(size_t aNewLength);
650 :
651 : /**
652 : * Increase the length of the vector, but don't initialize the new elements
653 : * -- leave them as uninitialized memory.
654 : */
655 : MOZ_MUST_USE bool growByUninitialized(size_t aIncr);
656 : void infallibleGrowByUninitialized(size_t aIncr);
657 : MOZ_MUST_USE bool resizeUninitialized(size_t aNewLength);
658 :
659 : /** Shorthand for shrinkBy(length()). */
660 : void clear();
661 :
662 : /** Clears and releases any heap-allocated storage. */
663 : void clearAndFree();
664 :
665 : /**
666 : * Calls the AllocPolicy's pod_realloc to release excess capacity. Since
667 : * realloc is only safe on PODs, this method fails to compile if IsPod<T>
668 : * is false.
669 : */
670 : void podResizeToFit();
671 :
672 : /**
673 : * If true, appending |aNeeded| elements won't reallocate elements storage.
674 : * This *doesn't* mean that infallibleAppend may be used! You still must
675 : * reserve the extra space, even if this method indicates that appends won't
676 : * need to reallocate elements storage.
677 : */
678 : bool canAppendWithoutRealloc(size_t aNeeded) const;
679 :
680 : /** Potentially fallible append operations. */
681 :
682 : /**
683 : * This can take either a T& or a T&&. Given a T&&, it moves |aU| into the
684 : * vector, instead of copying it. If it fails, |aU| is left unmoved. ("We are
685 : * not amused.")
686 : */
687 : template<typename U> MOZ_MUST_USE bool append(U&& aU);
688 :
689 : /**
690 : * Construct a T in-place as a new entry at the end of this vector.
691 : */
692 : template<typename... Args>
693 20826 : MOZ_MUST_USE bool emplaceBack(Args&&... aArgs)
694 : {
695 20826 : if (!growByUninitialized(1))
696 0 : return false;
697 20826 : Impl::new_(&back(), Forward<Args>(aArgs)...);
698 20826 : return true;
699 : }
700 :
701 : template<typename U, size_t O, class BP>
702 : MOZ_MUST_USE bool appendAll(const Vector<U, O, BP>& aU);
703 : MOZ_MUST_USE bool appendN(const T& aT, size_t aN);
704 : template<typename U> MOZ_MUST_USE bool append(const U* aBegin, const U* aEnd);
705 : template<typename U> MOZ_MUST_USE bool append(const U* aBegin, size_t aLength);
706 :
707 : /*
708 : * Guaranteed-infallible append operations for use upon vectors whose
709 : * memory has been pre-reserved. Don't use this if you haven't reserved the
710 : * memory!
711 : */
712 79115 : template<typename U> void infallibleAppend(U&& aU)
713 : {
714 79115 : internalAppend(Forward<U>(aU));
715 79115 : }
716 : void infallibleAppendN(const T& aT, size_t aN)
717 : {
718 : internalAppendN(aT, aN);
719 : }
720 : template<typename U> void infallibleAppend(const U* aBegin, const U* aEnd)
721 : {
722 : internalAppend(aBegin, PointerRangeSize(aBegin, aEnd));
723 : }
724 3724133 : template<typename U> void infallibleAppend(const U* aBegin, size_t aLength)
725 : {
726 3724133 : internalAppend(aBegin, aLength);
727 3724332 : }
728 : template<typename... Args>
729 9832 : void infallibleEmplaceBack(Args&&... aArgs)
730 : {
731 9832 : infallibleGrowByUninitialized(1);
732 9832 : Impl::new_(&back(), Forward<Args>(aArgs)...);
733 9832 : }
734 :
735 : void popBack();
736 :
737 : T popCopy();
738 :
739 : /**
740 : * If elements are stored in-place, return nullptr and leave this vector
741 : * unmodified.
742 : *
743 : * Otherwise return this vector's elements buffer, and clear this vector as if
744 : * by clearAndFree(). The caller now owns the buffer and is responsible for
745 : * deallocating it consistent with this vector's AllocPolicy.
746 : *
747 : * N.B. Although a T*, only the range [0, length()) is constructed.
748 : */
749 : MOZ_MUST_USE T* extractRawBuffer();
750 :
751 : /**
752 : * If elements are stored in-place, allocate a new buffer, move this vector's
753 : * elements into it, and return that buffer.
754 : *
755 : * Otherwise return this vector's elements buffer. The caller now owns the
756 : * buffer and is responsible for deallocating it consistent with this vector's
757 : * AllocPolicy.
758 : *
759 : * This vector is cleared, as if by clearAndFree(), when this method
760 : * succeeds. This method fails and returns nullptr only if new elements buffer
761 : * allocation fails.
762 : *
763 : * N.B. Only the range [0, length()) of the returned buffer is constructed.
764 : * If any of these elements are uninitialized (as growByUninitialized
765 : * enables), behavior is undefined.
766 : */
767 : MOZ_MUST_USE T* extractOrCopyRawBuffer();
768 :
769 : /**
770 : * Transfer ownership of an array of objects into the vector. The caller
771 : * must have allocated the array in accordance with this vector's
772 : * AllocPolicy.
773 : *
774 : * N.B. This call assumes that there are no uninitialized elements in the
775 : * passed array.
776 : */
777 : void replaceRawBuffer(T* aP, size_t aLength);
778 :
779 : /**
780 : * Places |aVal| at position |aP|, shifting existing elements from |aP| onward
781 : * one position higher. On success, |aP| should not be reused because it'll
782 : * be a dangling pointer if reallocation of the vector storage occurred; the
783 : * return value should be used instead. On failure, nullptr is returned.
784 : *
785 : * Example usage:
786 : *
787 : * if (!(p = vec.insert(p, val))) {
788 : * <handle failure>
789 : * }
790 : * <keep working with p>
791 : *
792 : * This is inherently a linear-time operation. Be careful!
793 : */
794 : template<typename U>
795 : MOZ_MUST_USE T* insert(T* aP, U&& aVal);
796 :
797 : /**
798 : * Removes the element |aT|, which must fall in the bounds [begin, end),
799 : * shifting existing elements from |aT + 1| onward one position lower.
800 : */
801 : void erase(T* aT);
802 :
803 : /**
804 : * Removes the elements [|aBegin|, |aEnd|), which must fall in the bounds
805 : * [begin, end), shifting existing elements from |aEnd + 1| onward to aBegin's
806 : * old position.
807 : */
808 : void erase(T* aBegin, T* aEnd);
809 :
810 : /**
811 : * Measure the size of the vector's heap-allocated storage.
812 : */
813 : size_t sizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const;
814 :
815 : /**
816 : * Like sizeOfExcludingThis, but also measures the size of the vector
817 : * object (which must be heap-allocated) itself.
818 : */
819 : size_t sizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const;
820 :
821 : void swap(Vector& aOther);
822 :
823 : private:
824 : Vector(const Vector&) = delete;
825 : void operator=(const Vector&) = delete;
826 : };
827 :
828 : /* This does the re-entrancy check plus several other sanity checks. */
829 : #define MOZ_REENTRANCY_GUARD_ET_AL \
830 : ReentrancyGuard g(*this); \
831 : MOZ_ASSERT_IF(usingInlineStorage(), mTail.mCapacity == kInlineCapacity); \
832 : MOZ_ASSERT(reserved() <= mTail.mCapacity); \
833 : MOZ_ASSERT(mLength <= reserved()); \
834 : MOZ_ASSERT(mLength <= mTail.mCapacity)
835 :
836 : /* Vector Implementation */
837 :
838 : template<typename T, size_t N, class AP>
839 : MOZ_ALWAYS_INLINE
840 622151 : Vector<T, N, AP>::Vector(AP aAP)
841 : : AP(aAP)
842 : , mLength(0)
843 : , mTail(kInlineCapacity, 0)
844 : #ifdef DEBUG
845 622151 : , mEntered(false)
846 : #endif
847 : {
848 622149 : mBegin = inlineStorage();
849 622150 : }
850 :
851 : /* Move constructor. */
852 : template<typename T, size_t N, class AllocPolicy>
853 : MOZ_ALWAYS_INLINE
854 98639 : Vector<T, N, AllocPolicy>::Vector(Vector&& aRhs)
855 98639 : : AllocPolicy(Move(aRhs))
856 : #ifdef DEBUG
857 98639 : , mEntered(false)
858 : #endif
859 : {
860 98639 : mLength = aRhs.mLength;
861 98639 : mTail.mCapacity = aRhs.mTail.mCapacity;
862 : #ifdef DEBUG
863 98639 : mTail.mReserved = aRhs.mTail.mReserved;
864 : #endif
865 :
866 98639 : if (aRhs.usingInlineStorage()) {
867 : /* We can't move the buffer over in this case, so copy elements. */
868 96887 : mBegin = inlineStorage();
869 96887 : Impl::moveConstruct(mBegin, aRhs.beginNoCheck(), aRhs.endNoCheck());
870 : /*
871 : * Leave aRhs's mLength, mBegin, mCapacity, and mReserved as they are.
872 : * The elements in its in-line storage still need to be destroyed.
873 : */
874 : } else {
875 : /*
876 : * Take src's buffer, and turn src into an empty vector using
877 : * in-line storage.
878 : */
879 1752 : mBegin = aRhs.mBegin;
880 1752 : aRhs.mBegin = aRhs.inlineStorage();
881 1752 : aRhs.mTail.mCapacity = kInlineCapacity;
882 1752 : aRhs.mLength = 0;
883 : #ifdef DEBUG
884 1752 : aRhs.mTail.mReserved = 0;
885 : #endif
886 : }
887 98639 : }
888 :
889 : /* Move assignment. */
890 : template<typename T, size_t N, class AP>
891 : MOZ_ALWAYS_INLINE Vector<T, N, AP>&
892 730 : Vector<T, N, AP>::operator=(Vector&& aRhs)
893 : {
894 730 : MOZ_ASSERT(this != &aRhs, "self-move assignment is prohibited");
895 730 : this->~Vector();
896 730 : new(KnownNotNull, this) Vector(Move(aRhs));
897 730 : return *this;
898 : }
899 :
900 : template<typename T, size_t N, class AP>
901 : MOZ_ALWAYS_INLINE
902 698595 : Vector<T, N, AP>::~Vector()
903 : {
904 1397188 : MOZ_REENTRANCY_GUARD_ET_AL;
905 698594 : Impl::destroy(beginNoCheck(), endNoCheck());
906 698594 : if (!usingInlineStorage()) {
907 66539 : this->free_(beginNoCheck());
908 : }
909 698593 : }
910 :
911 : template<typename T, size_t N, class AP>
912 : MOZ_ALWAYS_INLINE void
913 0 : Vector<T, N, AP>::reverse() {
914 0 : MOZ_REENTRANCY_GUARD_ET_AL;
915 0 : T* elems = mBegin;
916 0 : size_t len = mLength;
917 0 : size_t mid = len / 2;
918 0 : for (size_t i = 0; i < mid; i++) {
919 0 : Swap(elems[i], elems[len - i - 1]);
920 : }
921 0 : }
922 :
923 : /*
924 : * This function will create a new heap buffer with capacity aNewCap,
925 : * move all elements in the inline buffer to this new buffer,
926 : * and fail on OOM.
927 : */
928 : template<typename T, size_t N, class AP>
929 : inline bool
930 71473 : Vector<T, N, AP>::convertToHeapStorage(size_t aNewCap)
931 : {
932 71473 : MOZ_ASSERT(usingInlineStorage());
933 :
934 : /* Allocate buffer. */
935 71473 : MOZ_ASSERT(!detail::CapacityHasExcessSpace<T>(aNewCap));
936 71473 : T* newBuf = this->template pod_malloc<T>(aNewCap);
937 71473 : if (MOZ_UNLIKELY(!newBuf)) {
938 0 : return false;
939 : }
940 :
941 : /* Copy inline elements into heap buffer. */
942 71473 : Impl::moveConstruct(newBuf, beginNoCheck(), endNoCheck());
943 71473 : Impl::destroy(beginNoCheck(), endNoCheck());
944 :
945 : /* Switch in heap buffer. */
946 71473 : mBegin = newBuf;
947 : /* mLength is unchanged. */
948 71473 : mTail.mCapacity = aNewCap;
949 71473 : return true;
950 : }
951 :
952 : template<typename T, size_t N, class AP>
953 : MOZ_NEVER_INLINE bool
954 107389 : Vector<T, N, AP>::growStorageBy(size_t aIncr)
955 : {
956 107389 : MOZ_ASSERT(mLength + aIncr > mTail.mCapacity);
957 :
958 : /*
959 : * When choosing a new capacity, its size should is as close to 2**N bytes
960 : * as possible. 2**N-sized requests are best because they are unlikely to
961 : * be rounded up by the allocator. Asking for a 2**N number of elements
962 : * isn't as good, because if sizeof(T) is not a power-of-two that would
963 : * result in a non-2**N request size.
964 : */
965 :
966 : size_t newCap;
967 :
968 107389 : if (aIncr == 1) {
969 76874 : if (usingInlineStorage()) {
970 : /* This case occurs in ~70--80% of the calls to this function. */
971 : size_t newSize =
972 44602 : tl::RoundUpPow2<(kInlineCapacity + 1) * sizeof(T)>::value;
973 44602 : newCap = newSize / sizeof(T);
974 44602 : goto convert;
975 : }
976 :
977 32272 : if (mLength == 0) {
978 : /* This case occurs in ~0--10% of the calls to this function. */
979 8 : newCap = 1;
980 8 : goto grow;
981 : }
982 :
983 : /* This case occurs in ~15--20% of the calls to this function. */
984 :
985 : /*
986 : * Will mLength * 4 *sizeof(T) overflow? This condition limits a vector
987 : * to 1GB of memory on a 32-bit system, which is a reasonable limit. It
988 : * also ensures that
989 : *
990 : * static_cast<char*>(end()) - static_cast<char*>(begin())
991 : *
992 : * doesn't overflow ptrdiff_t (see bug 510319).
993 : */
994 32264 : if (MOZ_UNLIKELY(mLength & tl::MulOverflowMask<4 * sizeof(T)>::value)) {
995 0 : this->reportAllocOverflow();
996 0 : return false;
997 : }
998 :
999 : /*
1000 : * If we reach here, the existing capacity will have a size that is already
1001 : * as close to 2^N as sizeof(T) will allow. Just double the capacity, and
1002 : * then there might be space for one more element.
1003 : */
1004 32264 : newCap = mLength * 2;
1005 32264 : if (detail::CapacityHasExcessSpace<T>(newCap)) {
1006 2097 : newCap += 1;
1007 : }
1008 : } else {
1009 : /* This case occurs in ~2% of the calls to this function. */
1010 30515 : size_t newMinCap = mLength + aIncr;
1011 :
1012 : /* Did mLength + aIncr overflow? Will newCap * sizeof(T) overflow? */
1013 30515 : if (MOZ_UNLIKELY(newMinCap < mLength ||
1014 : newMinCap & tl::MulOverflowMask<2 * sizeof(T)>::value))
1015 : {
1016 0 : this->reportAllocOverflow();
1017 0 : return false;
1018 : }
1019 :
1020 30515 : size_t newMinSize = newMinCap * sizeof(T);
1021 30515 : size_t newSize = RoundUpPow2(newMinSize);
1022 30515 : newCap = newSize / sizeof(T);
1023 : }
1024 :
1025 62779 : if (usingInlineStorage()) {
1026 : convert:
1027 71473 : return convertToHeapStorage(newCap);
1028 : }
1029 :
1030 : grow:
1031 35916 : return Impl::growTo(*this, newCap);
1032 : }
1033 :
1034 : template<typename T, size_t N, class AP>
1035 : inline bool
1036 15 : Vector<T, N, AP>::initCapacity(size_t aRequest)
1037 : {
1038 15 : MOZ_ASSERT(empty());
1039 15 : MOZ_ASSERT(usingInlineStorage());
1040 15 : if (aRequest == 0) {
1041 0 : return true;
1042 : }
1043 15 : T* newbuf = this->template pod_malloc<T>(aRequest);
1044 15 : if (MOZ_UNLIKELY(!newbuf)) {
1045 0 : return false;
1046 : }
1047 15 : mBegin = newbuf;
1048 15 : mTail.mCapacity = aRequest;
1049 : #ifdef DEBUG
1050 15 : mTail.mReserved = aRequest;
1051 : #endif
1052 15 : return true;
1053 : }
1054 :
1055 : template<typename T, size_t N, class AP>
1056 : inline bool
1057 0 : Vector<T, N, AP>::initLengthUninitialized(size_t aRequest)
1058 : {
1059 0 : if (!initCapacity(aRequest)) {
1060 0 : return false;
1061 : }
1062 0 : infallibleGrowByUninitialized(aRequest);
1063 0 : return true;
1064 : }
1065 :
1066 : template<typename T, size_t N, class AP>
1067 : inline bool
1068 3608565 : Vector<T, N, AP>::maybeCheckSimulatedOOM(size_t aRequestedSize)
1069 : {
1070 3608565 : if (aRequestedSize <= N) {
1071 983105 : return true;
1072 : }
1073 :
1074 : #ifdef DEBUG
1075 2625460 : if (aRequestedSize <= mTail.mReserved) {
1076 947374 : return true;
1077 : }
1078 : #endif
1079 :
1080 1678086 : return allocPolicy().checkSimulatedOOM();
1081 : }
1082 :
1083 : template<typename T, size_t N, class AP>
1084 : inline bool
1085 1144253 : Vector<T, N, AP>::reserve(size_t aRequest)
1086 : {
1087 2288522 : MOZ_REENTRANCY_GUARD_ET_AL;
1088 1144277 : if (aRequest > mTail.mCapacity) {
1089 21104 : if (MOZ_UNLIKELY(!growStorageBy(aRequest - mLength))) {
1090 0 : return false;
1091 : }
1092 1123173 : } else if (!maybeCheckSimulatedOOM(aRequest)) {
1093 0 : return false;
1094 : }
1095 : #ifdef DEBUG
1096 1144269 : if (aRequest > mTail.mReserved) {
1097 1143741 : mTail.mReserved = aRequest;
1098 : }
1099 1144269 : MOZ_ASSERT(mLength <= mTail.mReserved);
1100 1144269 : MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
1101 : #endif
1102 1144269 : return true;
1103 : }
1104 :
1105 : template<typename T, size_t N, class AP>
1106 : inline void
1107 1689 : Vector<T, N, AP>::shrinkBy(size_t aIncr)
1108 : {
1109 3378 : MOZ_REENTRANCY_GUARD_ET_AL;
1110 1689 : MOZ_ASSERT(aIncr <= mLength);
1111 1689 : Impl::destroy(endNoCheck() - aIncr, endNoCheck());
1112 1689 : mLength -= aIncr;
1113 1689 : }
1114 :
1115 : template<typename T, size_t N, class AP>
1116 : MOZ_ALWAYS_INLINE void
1117 4 : Vector<T, N, AP>::shrinkTo(size_t aNewLength)
1118 : {
1119 4 : MOZ_ASSERT(aNewLength <= mLength);
1120 4 : shrinkBy(mLength - aNewLength);
1121 4 : }
1122 :
1123 : template<typename T, size_t N, class AP>
1124 : MOZ_ALWAYS_INLINE bool
1125 717999 : Vector<T, N, AP>::growBy(size_t aIncr)
1126 : {
1127 1435998 : MOZ_REENTRANCY_GUARD_ET_AL;
1128 717999 : if (aIncr > mTail.mCapacity - mLength) {
1129 3404 : if (MOZ_UNLIKELY(!growStorageBy(aIncr))) {
1130 0 : return false;
1131 : }
1132 714595 : } else if (!maybeCheckSimulatedOOM(mLength + aIncr)) {
1133 0 : return false;
1134 : }
1135 717999 : MOZ_ASSERT(mLength + aIncr <= mTail.mCapacity);
1136 717999 : T* newend = endNoCheck() + aIncr;
1137 717999 : Impl::initialize(endNoCheck(), newend);
1138 717999 : mLength += aIncr;
1139 : #ifdef DEBUG
1140 717999 : if (mLength > mTail.mReserved) {
1141 97685 : mTail.mReserved = mLength;
1142 : }
1143 : #endif
1144 717999 : return true;
1145 : }
1146 :
1147 : template<typename T, size_t N, class AP>
1148 : MOZ_ALWAYS_INLINE bool
1149 278509 : Vector<T, N, AP>::growByUninitialized(size_t aIncr)
1150 : {
1151 557018 : MOZ_REENTRANCY_GUARD_ET_AL;
1152 278509 : if (aIncr > mTail.mCapacity - mLength) {
1153 2855 : if (MOZ_UNLIKELY(!growStorageBy(aIncr))) {
1154 0 : return false;
1155 : }
1156 275654 : } else if (!maybeCheckSimulatedOOM(mLength + aIncr)) {
1157 0 : return false;
1158 : }
1159 : #ifdef DEBUG
1160 278509 : if (mLength + aIncr > mTail.mReserved) {
1161 276784 : mTail.mReserved = mLength + aIncr;
1162 : }
1163 : #endif
1164 278509 : infallibleGrowByUninitialized(aIncr);
1165 278509 : return true;
1166 : }
1167 :
1168 : template<typename T, size_t N, class AP>
1169 : MOZ_ALWAYS_INLINE void
1170 288341 : Vector<T, N, AP>::infallibleGrowByUninitialized(size_t aIncr)
1171 : {
1172 288341 : MOZ_ASSERT(mLength + aIncr <= reserved());
1173 288341 : mLength += aIncr;
1174 288341 : }
1175 :
1176 : template<typename T, size_t N, class AP>
1177 : inline bool
1178 24788 : Vector<T, N, AP>::resize(size_t aNewLength)
1179 : {
1180 24788 : size_t curLength = mLength;
1181 24788 : if (aNewLength > curLength) {
1182 24521 : return growBy(aNewLength - curLength);
1183 : }
1184 267 : shrinkBy(curLength - aNewLength);
1185 267 : return true;
1186 : }
1187 :
1188 : template<typename T, size_t N, class AP>
1189 : MOZ_ALWAYS_INLINE bool
1190 89 : Vector<T, N, AP>::resizeUninitialized(size_t aNewLength)
1191 : {
1192 89 : size_t curLength = mLength;
1193 89 : if (aNewLength > curLength) {
1194 28 : return growByUninitialized(aNewLength - curLength);
1195 : }
1196 61 : shrinkBy(curLength - aNewLength);
1197 61 : return true;
1198 : }
1199 :
1200 : template<typename T, size_t N, class AP>
1201 : inline void
1202 98415 : Vector<T, N, AP>::clear()
1203 : {
1204 196830 : MOZ_REENTRANCY_GUARD_ET_AL;
1205 98415 : Impl::destroy(beginNoCheck(), endNoCheck());
1206 98415 : mLength = 0;
1207 98415 : }
1208 :
1209 : template<typename T, size_t N, class AP>
1210 : inline void
1211 2442 : Vector<T, N, AP>::clearAndFree()
1212 : {
1213 2442 : clear();
1214 :
1215 2442 : if (usingInlineStorage()) {
1216 2421 : return;
1217 : }
1218 21 : this->free_(beginNoCheck());
1219 21 : mBegin = inlineStorage();
1220 21 : mTail.mCapacity = kInlineCapacity;
1221 : #ifdef DEBUG
1222 21 : mTail.mReserved = 0;
1223 : #endif
1224 : }
1225 :
1226 : template<typename T, size_t N, class AP>
1227 : inline void
1228 0 : Vector<T, N, AP>::podResizeToFit()
1229 : {
1230 : // This function is only defined if IsPod is true and will fail to compile
1231 : // otherwise.
1232 0 : Impl::podResizeToFit(*this);
1233 0 : }
1234 :
1235 : template<typename T, size_t N, class AP>
1236 : inline bool
1237 0 : Vector<T, N, AP>::canAppendWithoutRealloc(size_t aNeeded) const
1238 : {
1239 0 : return mLength + aNeeded <= mTail.mCapacity;
1240 : }
1241 :
1242 : template<typename T, size_t N, class AP>
1243 : template<typename U, size_t O, class BP>
1244 : MOZ_ALWAYS_INLINE void
1245 : Vector<T, N, AP>::internalAppendAll(const Vector<U, O, BP>& aOther)
1246 : {
1247 : internalAppend(aOther.begin(), aOther.length());
1248 : }
1249 :
1250 : template<typename T, size_t N, class AP>
1251 : template<typename U>
1252 : MOZ_ALWAYS_INLINE void
1253 1596524 : Vector<T, N, AP>::internalAppend(U&& aU)
1254 : {
1255 1596524 : MOZ_ASSERT(mLength + 1 <= mTail.mReserved);
1256 1596524 : MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
1257 1596524 : Impl::new_(endNoCheck(), Forward<U>(aU));
1258 1596461 : ++mLength;
1259 1596461 : }
1260 :
1261 : template<typename T, size_t N, class AP>
1262 : MOZ_ALWAYS_INLINE bool
1263 8055 : Vector<T, N, AP>::appendN(const T& aT, size_t aNeeded)
1264 : {
1265 16110 : MOZ_REENTRANCY_GUARD_ET_AL;
1266 8055 : if (mLength + aNeeded > mTail.mCapacity) {
1267 6330 : if (MOZ_UNLIKELY(!growStorageBy(aNeeded))) {
1268 0 : return false;
1269 : }
1270 1725 : } else if (!maybeCheckSimulatedOOM(mLength + aNeeded)) {
1271 0 : return false;
1272 : }
1273 : #ifdef DEBUG
1274 8055 : if (mLength + aNeeded > mTail.mReserved) {
1275 6797 : mTail.mReserved = mLength + aNeeded;
1276 : }
1277 : #endif
1278 8055 : internalAppendN(aT, aNeeded);
1279 8055 : return true;
1280 : }
1281 :
1282 : template<typename T, size_t N, class AP>
1283 : MOZ_ALWAYS_INLINE void
1284 8055 : Vector<T, N, AP>::internalAppendN(const T& aT, size_t aNeeded)
1285 : {
1286 8055 : MOZ_ASSERT(mLength + aNeeded <= mTail.mReserved);
1287 8055 : MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
1288 8055 : Impl::copyConstructN(endNoCheck(), aNeeded, aT);
1289 8055 : mLength += aNeeded;
1290 8055 : }
1291 :
1292 : template<typename T, size_t N, class AP>
1293 : template<typename U>
1294 : inline T*
1295 55075 : Vector<T, N, AP>::insert(T* aP, U&& aVal)
1296 : {
1297 55075 : MOZ_ASSERT(begin() <= aP);
1298 55075 : MOZ_ASSERT(aP <= end());
1299 55075 : size_t pos = aP - begin();
1300 55075 : MOZ_ASSERT(pos <= mLength);
1301 55075 : size_t oldLength = mLength;
1302 55075 : if (pos == oldLength) {
1303 9 : if (!append(Forward<U>(aVal))) {
1304 0 : return nullptr;
1305 : }
1306 : } else {
1307 55066 : T oldBack = Move(back());
1308 55066 : if (!append(Move(oldBack))) {
1309 0 : return nullptr;
1310 : }
1311 433198 : for (size_t i = oldLength - 1; i > pos; --i) {
1312 378132 : (*this)[i] = Move((*this)[i - 1]);
1313 : }
1314 55066 : (*this)[pos] = Forward<U>(aVal);
1315 : }
1316 55075 : return begin() + pos;
1317 : }
1318 :
1319 : template<typename T, size_t N, class AP>
1320 : inline void
1321 284 : Vector<T, N, AP>::erase(T* aIt)
1322 : {
1323 284 : MOZ_ASSERT(begin() <= aIt);
1324 284 : MOZ_ASSERT(aIt < end());
1325 804 : while (aIt + 1 < end()) {
1326 260 : *aIt = Move(*(aIt + 1));
1327 260 : ++aIt;
1328 : }
1329 284 : popBack();
1330 284 : }
1331 :
1332 : template<typename T, size_t N, class AP>
1333 : inline void
1334 40 : Vector<T, N, AP>::erase(T* aBegin, T* aEnd)
1335 : {
1336 40 : MOZ_ASSERT(begin() <= aBegin);
1337 40 : MOZ_ASSERT(aBegin <= aEnd);
1338 40 : MOZ_ASSERT(aEnd <= end());
1339 120 : while (aEnd < end()) {
1340 40 : *aBegin++ = Move(*aEnd++);
1341 : }
1342 40 : shrinkBy(aEnd - aBegin);
1343 40 : }
1344 :
1345 : template<typename T, size_t N, class AP>
1346 : template<typename U>
1347 : MOZ_ALWAYS_INLINE bool
1348 48358 : Vector<T, N, AP>::append(const U* aInsBegin, const U* aInsEnd)
1349 : {
1350 96716 : MOZ_REENTRANCY_GUARD_ET_AL;
1351 48358 : size_t aNeeded = PointerRangeSize(aInsBegin, aInsEnd);
1352 48358 : if (mLength + aNeeded > mTail.mCapacity) {
1353 294 : if (MOZ_UNLIKELY(!growStorageBy(aNeeded))) {
1354 0 : return false;
1355 : }
1356 48064 : } else if (!maybeCheckSimulatedOOM(mLength + aNeeded)) {
1357 0 : return false;
1358 : }
1359 : #ifdef DEBUG
1360 48358 : if (mLength + aNeeded > mTail.mReserved) {
1361 36160 : mTail.mReserved = mLength + aNeeded;
1362 : }
1363 : #endif
1364 48358 : internalAppend(aInsBegin, aNeeded);
1365 48358 : return true;
1366 : }
1367 :
1368 : template<typename T, size_t N, class AP>
1369 : template<typename U>
1370 : MOZ_ALWAYS_INLINE void
1371 3772858 : Vector<T, N, AP>::internalAppend(const U* aInsBegin, size_t aInsLength)
1372 : {
1373 3772858 : MOZ_ASSERT(mLength + aInsLength <= mTail.mReserved);
1374 3772858 : MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
1375 3772858 : Impl::copyConstruct(endNoCheck(), aInsBegin, aInsBegin + aInsLength);
1376 3772705 : mLength += aInsLength;
1377 3772705 : }
1378 :
1379 : template<typename T, size_t N, class AP>
1380 : template<typename U>
1381 : MOZ_ALWAYS_INLINE bool
1382 1517413 : Vector<T, N, AP>::append(U&& aU)
1383 : {
1384 3034761 : MOZ_REENTRANCY_GUARD_ET_AL;
1385 1517415 : if (mLength == mTail.mCapacity) {
1386 73382 : if (MOZ_UNLIKELY(!growStorageBy(1))) {
1387 0 : return false;
1388 : }
1389 1444033 : } else if (!maybeCheckSimulatedOOM(mLength + 1)) {
1390 0 : return false;
1391 : }
1392 : #ifdef DEBUG
1393 1517417 : if (mLength + 1 > mTail.mReserved) {
1394 866682 : mTail.mReserved = mLength + 1;
1395 : }
1396 : #endif
1397 1517417 : internalAppend(Forward<U>(aU));
1398 1517348 : return true;
1399 : }
1400 :
1401 : template<typename T, size_t N, class AP>
1402 : template<typename U, size_t O, class BP>
1403 : MOZ_ALWAYS_INLINE bool
1404 8602 : Vector<T, N, AP>::appendAll(const Vector<U, O, BP>& aOther)
1405 : {
1406 8602 : return append(aOther.begin(), aOther.length());
1407 : }
1408 :
1409 : template<typename T, size_t N, class AP>
1410 : template<class U>
1411 : MOZ_ALWAYS_INLINE bool
1412 29460 : Vector<T, N, AP>::append(const U* aInsBegin, size_t aInsLength)
1413 : {
1414 29460 : return append(aInsBegin, aInsBegin + aInsLength);
1415 : }
1416 :
1417 : template<typename T, size_t N, class AP>
1418 : MOZ_ALWAYS_INLINE void
1419 328296 : Vector<T, N, AP>::popBack()
1420 : {
1421 656590 : MOZ_REENTRANCY_GUARD_ET_AL;
1422 328294 : MOZ_ASSERT(!empty());
1423 328294 : --mLength;
1424 328294 : endNoCheck()->~T();
1425 328294 : }
1426 :
1427 : template<typename T, size_t N, class AP>
1428 : MOZ_ALWAYS_INLINE T
1429 72091 : Vector<T, N, AP>::popCopy()
1430 : {
1431 72091 : T ret = back();
1432 72091 : popBack();
1433 72091 : return ret;
1434 : }
1435 :
1436 : template<typename T, size_t N, class AP>
1437 : inline T*
1438 551 : Vector<T, N, AP>::extractRawBuffer()
1439 : {
1440 1102 : MOZ_REENTRANCY_GUARD_ET_AL;
1441 :
1442 551 : if (usingInlineStorage()) {
1443 494 : return nullptr;
1444 : }
1445 :
1446 57 : T* ret = mBegin;
1447 57 : mBegin = inlineStorage();
1448 57 : mLength = 0;
1449 57 : mTail.mCapacity = kInlineCapacity;
1450 : #ifdef DEBUG
1451 57 : mTail.mReserved = 0;
1452 : #endif
1453 57 : return ret;
1454 : }
1455 :
1456 : template<typename T, size_t N, class AP>
1457 : inline T*
1458 551 : Vector<T, N, AP>::extractOrCopyRawBuffer()
1459 : {
1460 551 : if (T* ret = extractRawBuffer()) {
1461 57 : return ret;
1462 : }
1463 :
1464 988 : MOZ_REENTRANCY_GUARD_ET_AL;
1465 :
1466 494 : T* copy = this->template pod_malloc<T>(mLength);
1467 494 : if (!copy) {
1468 0 : return nullptr;
1469 : }
1470 :
1471 494 : Impl::moveConstruct(copy, beginNoCheck(), endNoCheck());
1472 494 : Impl::destroy(beginNoCheck(), endNoCheck());
1473 494 : mBegin = inlineStorage();
1474 494 : mLength = 0;
1475 494 : mTail.mCapacity = kInlineCapacity;
1476 : #ifdef DEBUG
1477 494 : mTail.mReserved = 0;
1478 : #endif
1479 494 : return copy;
1480 : }
1481 :
1482 : template<typename T, size_t N, class AP>
1483 : inline void
1484 1167 : Vector<T, N, AP>::replaceRawBuffer(T* aP, size_t aLength)
1485 : {
1486 2334 : MOZ_REENTRANCY_GUARD_ET_AL;
1487 :
1488 : /* Destroy what we have. */
1489 1167 : Impl::destroy(beginNoCheck(), endNoCheck());
1490 1167 : if (!usingInlineStorage()) {
1491 0 : this->free_(beginNoCheck());
1492 : }
1493 :
1494 : /* Take in the new buffer. */
1495 1167 : if (aLength <= kInlineCapacity) {
1496 : /*
1497 : * We convert to inline storage if possible, even though aP might
1498 : * otherwise be acceptable. Maybe this behaviour should be
1499 : * specifiable with an argument to this function.
1500 : */
1501 4 : mBegin = inlineStorage();
1502 4 : mLength = aLength;
1503 4 : mTail.mCapacity = kInlineCapacity;
1504 4 : Impl::moveConstruct(mBegin, aP, aP + aLength);
1505 4 : Impl::destroy(aP, aP + aLength);
1506 4 : this->free_(aP);
1507 : } else {
1508 1163 : mBegin = aP;
1509 1163 : mLength = aLength;
1510 1163 : mTail.mCapacity = aLength;
1511 : }
1512 : #ifdef DEBUG
1513 1167 : mTail.mReserved = aLength;
1514 : #endif
1515 1167 : }
1516 :
1517 : template<typename T, size_t N, class AP>
1518 : inline size_t
1519 0 : Vector<T, N, AP>::sizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
1520 : {
1521 0 : return usingInlineStorage() ? 0 : aMallocSizeOf(beginNoCheck());
1522 : }
1523 :
1524 : template<typename T, size_t N, class AP>
1525 : inline size_t
1526 0 : Vector<T, N, AP>::sizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
1527 : {
1528 0 : return aMallocSizeOf(this) + sizeOfExcludingThis(aMallocSizeOf);
1529 : }
1530 :
1531 : template<typename T, size_t N, class AP>
1532 : inline void
1533 0 : Vector<T, N, AP>::swap(Vector& aOther)
1534 : {
1535 : static_assert(N == 0,
1536 : "still need to implement this for N != 0");
1537 :
1538 : // This only works when inline storage is always empty.
1539 0 : if (!usingInlineStorage() && aOther.usingInlineStorage()) {
1540 0 : aOther.mBegin = mBegin;
1541 0 : mBegin = inlineStorage();
1542 0 : } else if (usingInlineStorage() && !aOther.usingInlineStorage()) {
1543 0 : mBegin = aOther.mBegin;
1544 0 : aOther.mBegin = aOther.inlineStorage();
1545 0 : } else if (!usingInlineStorage() && !aOther.usingInlineStorage()) {
1546 0 : Swap(mBegin, aOther.mBegin);
1547 : } else {
1548 : // This case is a no-op, since we'd set both to use their inline storage.
1549 : }
1550 :
1551 0 : Swap(mLength, aOther.mLength);
1552 0 : Swap(mTail.mCapacity, aOther.mTail.mCapacity);
1553 : #ifdef DEBUG
1554 0 : Swap(mTail.mReserved, aOther.mTail.mReserved);
1555 : #endif
1556 0 : }
1557 :
1558 : } // namespace mozilla
1559 :
1560 : #ifdef _MSC_VER
1561 : #pragma warning(pop)
1562 : #endif
1563 :
1564 : #endif /* mozilla_Vector_h */
|
