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/. */
7 /* A type/length-parametrized vector class. */
9 #ifndef mozilla_Vector_h
10 #define mozilla_Vector_h
12 #include <new> // for placement new
15 #include "mozilla/Alignment.h"
16 #include "mozilla/AllocPolicy.h"
17 #include "mozilla/ArrayUtils.h" // for PointerRangeSize
18 #include "mozilla/Assertions.h"
19 #include "mozilla/Attributes.h"
20 #include "mozilla/MathAlgorithms.h"
21 #include "mozilla/MemoryReporting.h"
22 #include "mozilla/OperatorNewExtensions.h"
23 #include "mozilla/ReentrancyGuard.h"
24 #include "mozilla/Span.h"
25 #include "mozilla/TemplateLib.h"
26 #include "mozilla/TypeTraits.h"
30 template <typename T
, size_t N
, class AllocPolicy
>
36 * Check that the given capacity wastes the minimal amount of space if
37 * allocated on the heap. This means that aCapacity*sizeof(T) is as close to a
38 * power-of-two as possible. growStorageBy() is responsible for ensuring this.
41 static bool CapacityHasExcessSpace(size_t aCapacity
) {
42 size_t size
= aCapacity
* sizeof(T
);
43 return RoundUpPow2(size
) - size
>= sizeof(T
);
47 * This template class provides a default implementation for vector operations
48 * when the element type is not known to be a POD, as judged by IsPod.
50 template <typename T
, size_t N
, class AP
, bool IsPod
>
53 * Constructs an object in the uninitialized memory at *aDst with aArgs.
55 template <typename
... Args
>
57 static inline void new_(T
* aDst
, Args
&&... aArgs
) {
58 new (KnownNotNull
, aDst
) T(std::forward
<Args
>(aArgs
)...);
61 /* Destroys constructed objects in the range [aBegin, aEnd). */
62 static inline void destroy(T
* aBegin
, T
* aEnd
) {
63 MOZ_ASSERT(aBegin
<= aEnd
);
64 for (T
* p
= aBegin
; p
< aEnd
; ++p
) {
69 /* Constructs objects in the uninitialized range [aBegin, aEnd). */
70 static inline void initialize(T
* aBegin
, T
* aEnd
) {
71 MOZ_ASSERT(aBegin
<= aEnd
);
72 for (T
* p
= aBegin
; p
< aEnd
; ++p
) {
78 * Copy-constructs objects in the uninitialized range
79 * [aDst, aDst+(aSrcEnd-aSrcStart)) from the range [aSrcStart, aSrcEnd).
82 static inline void copyConstruct(T
* aDst
, const U
* aSrcStart
,
84 MOZ_ASSERT(aSrcStart
<= aSrcEnd
);
85 for (const U
* p
= aSrcStart
; p
< aSrcEnd
; ++p
, ++aDst
) {
91 * Move-constructs objects in the uninitialized range
92 * [aDst, aDst+(aSrcEnd-aSrcStart)) from the range [aSrcStart, aSrcEnd).
95 static inline void moveConstruct(T
* aDst
, U
* aSrcStart
, U
* aSrcEnd
) {
96 MOZ_ASSERT(aSrcStart
<= aSrcEnd
);
97 for (U
* p
= aSrcStart
; p
< aSrcEnd
; ++p
, ++aDst
) {
98 new_(aDst
, std::move(*p
));
103 * Copy-constructs objects in the uninitialized range [aDst, aDst+aN) from
104 * the same object aU.
106 template <typename U
>
107 static inline void copyConstructN(T
* aDst
, size_t aN
, const U
& aU
) {
108 for (T
* end
= aDst
+ aN
; aDst
< end
; ++aDst
) {
114 * Grows the given buffer to have capacity aNewCap, preserving the objects
115 * constructed in the range [begin, end) and updating aV. Assumes that (1)
116 * aNewCap has not overflowed, and (2) multiplying aNewCap by sizeof(T) will
119 static inline MOZ_MUST_USE
bool growTo(Vector
<T
, N
, AP
>& aV
, size_t aNewCap
) {
120 MOZ_ASSERT(!aV
.usingInlineStorage());
121 MOZ_ASSERT(!CapacityHasExcessSpace
<T
>(aNewCap
));
122 T
* newbuf
= aV
.template pod_malloc
<T
>(aNewCap
);
123 if (MOZ_UNLIKELY(!newbuf
)) {
127 T
* src
= aV
.beginNoCheck();
128 for (; src
< aV
.endNoCheck(); ++dst
, ++src
) {
129 new_(dst
, std::move(*src
));
131 VectorImpl::destroy(aV
.beginNoCheck(), aV
.endNoCheck());
132 aV
.free_(aV
.mBegin
, aV
.mTail
.mCapacity
);
134 /* aV.mLength is unchanged. */
135 aV
.mTail
.mCapacity
= aNewCap
;
141 * This partial template specialization provides a default implementation for
142 * vector operations when the element type is known to be a POD, as judged by
145 template <typename T
, size_t N
, class AP
>
146 struct VectorImpl
<T
, N
, AP
, true> {
147 template <typename
... Args
>
149 static inline void new_(T
* aDst
, Args
&&... aArgs
) {
150 // Explicitly construct a local object instead of using a temporary since
151 // T(args...) will be treated like a C-style cast in the unary case and
152 // allow unsafe conversions. Both forms should be equivalent to an
153 // optimizing compiler.
154 T
temp(std::forward
<Args
>(aArgs
)...);
158 static inline void destroy(T
*, T
*) {}
160 static inline void initialize(T
* aBegin
, T
* aEnd
) {
162 * You would think that memset would be a big win (or even break even)
163 * when we know T is a POD. But currently it's not. This is probably
164 * because |append| tends to be given small ranges and memset requires
165 * a function call that doesn't get inlined.
167 * memset(aBegin, 0, sizeof(T) * (aEnd - aBegin));
169 MOZ_ASSERT(aBegin
<= aEnd
);
170 for (T
* p
= aBegin
; p
< aEnd
; ++p
) {
175 template <typename U
>
176 static inline void copyConstruct(T
* aDst
, const U
* aSrcStart
,
179 * See above memset comment. Also, notice that copyConstruct is
180 * currently templated (T != U), so memcpy won't work without
183 * memcpy(aDst, aSrcStart, sizeof(T) * (aSrcEnd - aSrcStart));
185 MOZ_ASSERT(aSrcStart
<= aSrcEnd
);
186 for (const U
* p
= aSrcStart
; p
< aSrcEnd
; ++p
, ++aDst
) {
191 template <typename U
>
192 static inline void moveConstruct(T
* aDst
, const U
* aSrcStart
,
194 copyConstruct(aDst
, aSrcStart
, aSrcEnd
);
197 static inline void copyConstructN(T
* aDst
, size_t aN
, const T
& aT
) {
198 for (T
* end
= aDst
+ aN
; aDst
< end
; ++aDst
) {
203 static inline MOZ_MUST_USE
bool growTo(Vector
<T
, N
, AP
>& aV
, size_t aNewCap
) {
204 MOZ_ASSERT(!aV
.usingInlineStorage());
205 MOZ_ASSERT(!CapacityHasExcessSpace
<T
>(aNewCap
));
207 aV
.template pod_realloc
<T
>(aV
.mBegin
, aV
.mTail
.mCapacity
, aNewCap
);
208 if (MOZ_UNLIKELY(!newbuf
)) {
212 /* aV.mLength is unchanged. */
213 aV
.mTail
.mCapacity
= aNewCap
;
218 // A struct for TestVector.cpp to access private internal fields.
219 // DO NOT DEFINE IN YOUR OWN CODE.
220 struct VectorTesting
;
222 } // namespace detail
225 * STL-like container providing a short-lived, dynamic buffer. Vector calls the
226 * constructors/destructors of all elements stored in its internal buffer, so
227 * non-PODs may be safely used. Additionally, Vector will store the first N
228 * elements in-place before resorting to dynamic allocation.
231 * - default and copy constructible, assignable, destructible
232 * - operations do not throw
233 * MinInlineCapacity requirements:
234 * - any value, however, MinInlineCapacity is clamped to min/max values
236 * - see "Allocation policies" in AllocPolicy.h (defaults to
237 * mozilla::MallocAllocPolicy)
239 * Vector is not reentrant: T member functions called during Vector member
240 * functions must not call back into the same object!
242 template <typename T
, size_t MinInlineCapacity
= 0,
243 class AllocPolicy
= MallocAllocPolicy
>
244 class MOZ_NON_PARAM Vector final
: private AllocPolicy
{
247 static constexpr bool kElemIsPod
= IsPod
<T
>::value
;
248 typedef detail::VectorImpl
<T
, MinInlineCapacity
, AllocPolicy
, kElemIsPod
>
250 friend struct detail::VectorImpl
<T
, MinInlineCapacity
, AllocPolicy
,
253 friend struct detail::VectorTesting
;
255 MOZ_MUST_USE
bool growStorageBy(size_t aIncr
);
256 MOZ_MUST_USE
bool convertToHeapStorage(size_t aNewCap
);
257 MOZ_MUST_USE
bool maybeCheckSimulatedOOM(size_t aRequestedSize
);
259 /* magic constants */
262 * The maximum space allocated for inline element storage.
264 * We reduce space by what the AllocPolicy base class and prior Vector member
265 * fields likely consume to attempt to play well with binary size classes.
267 static constexpr size_t kMaxInlineBytes
=
269 (sizeof(AllocPolicy
) + sizeof(T
*) + sizeof(size_t) + sizeof(size_t));
272 * The number of T elements of inline capacity built into this Vector. This
273 * is usually |MinInlineCapacity|, but it may be less (or zero!) for large T.
275 * We use a partially-specialized template (not explicit specialization, which
276 * is only allowed at namespace scope) to compute this value. The benefit is
277 * that |sizeof(T)| need not be computed, and |T| doesn't have to be fully
278 * defined at the time |Vector<T>| appears, if no inline storage is requested.
280 template <size_t MinimumInlineCapacity
, size_t Dummy
>
281 struct ComputeCapacity
{
282 static constexpr size_t value
=
283 tl::Min
<MinimumInlineCapacity
, kMaxInlineBytes
/ sizeof(T
)>::value
;
286 template <size_t Dummy
>
287 struct ComputeCapacity
<0, Dummy
> {
288 static constexpr size_t value
= 0;
291 /** The actual inline capacity in number of elements T. This may be zero! */
292 static constexpr size_t kInlineCapacity
=
293 ComputeCapacity
<MinInlineCapacity
, 0>::value
;
298 * Pointer to the buffer, be it inline or heap-allocated. Only [mBegin,
299 * mBegin + mLength) hold valid constructed T objects. The range [mBegin +
300 * mLength, mBegin + mCapacity) holds uninitialized memory. The range
301 * [mBegin + mLength, mBegin + mReserved) also holds uninitialized memory
302 * previously allocated by a call to reserve().
306 /* Number of elements in the vector. */
310 * Memory used to store capacity, reserved element count (debug builds only),
311 * and inline storage. The simple "answer" is:
317 * alignas(T) unsigned char mBytes[kInlineCapacity * sizeof(T)];
319 * but there are complications. First, C++ forbids zero-sized arrays that
320 * might result. Second, we don't want zero capacity to affect Vector's size
321 * (even empty classes take up a byte, unless they're base classes).
323 * Yet again, we eliminate the zero-sized array using partial specialization.
324 * And we eliminate potential size hit by putting capacity/reserved in one
325 * struct, then putting the array (if any) in a derived struct. If no array
326 * is needed, the derived struct won't consume extra space.
328 struct CapacityAndReserved
{
329 explicit CapacityAndReserved(size_t aCapacity
, size_t aReserved
)
330 : mCapacity(aCapacity
)
337 CapacityAndReserved() = default;
339 /* Max number of elements storable in the vector without resizing. */
343 /* Max elements of reserved or used space in this vector. */
348 // Silence warnings about this struct possibly being padded dued to the
349 // alignas() in it -- there's nothing we can do to avoid it.
351 # pragma warning(push)
352 # pragma warning(disable : 4324)
355 template <size_t Capacity
, size_t Dummy
>
356 struct CRAndStorage
: CapacityAndReserved
{
357 explicit CRAndStorage(size_t aCapacity
, size_t aReserved
)
358 : CapacityAndReserved(aCapacity
, aReserved
) {}
359 CRAndStorage() = default;
361 alignas(T
) unsigned char mBytes
[Capacity
* sizeof(T
)];
363 // GCC fails due to -Werror=strict-aliasing if |mBytes| is directly cast to
364 // T*. Indirecting through this function addresses the problem.
365 void* data() { return mBytes
; }
367 T
* storage() { return static_cast<T
*>(data()); }
370 template <size_t Dummy
>
371 struct CRAndStorage
<0, Dummy
> : CapacityAndReserved
{
372 explicit CRAndStorage(size_t aCapacity
, size_t aReserved
)
373 : CapacityAndReserved(aCapacity
, aReserved
) {}
374 CRAndStorage() = default;
377 // If this returns |nullptr|, functions like |Vector::begin()| would too,
378 // breaking callers that pass a vector's elements as pointer/length to
379 // code that bounds its operation by length but (even just as a sanity
380 // check) always wants a non-null pointer. Fake up an aligned, non-null
381 // pointer to support these callers.
382 return reinterpret_cast<T
*>(sizeof(T
));
386 CRAndStorage
<kInlineCapacity
, 0> mTail
;
389 # pragma warning(pop)
393 friend class ReentrancyGuard
;
397 /* private accessors */
399 bool usingInlineStorage() const {
400 return mBegin
== const_cast<Vector
*>(this)->inlineStorage();
403 T
* inlineStorage() { return mTail
.storage(); }
405 T
* beginNoCheck() const { return mBegin
; }
407 T
* endNoCheck() { return mBegin
+ mLength
; }
409 const T
* endNoCheck() const { return mBegin
+ mLength
; }
413 * The amount of explicitly allocated space in this vector that is immediately
414 * available to be filled by appending additional elements. This value is
415 * always greater than or equal to |length()| -- the vector's actual elements
416 * are implicitly reserved. This value is always less than or equal to
417 * |capacity()|. It may be explicitly increased using the |reserve()| method.
419 size_t reserved() const {
420 MOZ_ASSERT(mLength
<= mTail
.mReserved
);
421 MOZ_ASSERT(mTail
.mReserved
<= mTail
.mCapacity
);
422 return mTail
.mReserved
;
426 /* Append operations guaranteed to succeed due to pre-reserved space. */
427 template <typename U
>
428 void internalAppend(U
&& aU
);
429 template <typename U
, size_t O
, class BP
>
430 void internalAppendAll(const Vector
<U
, O
, BP
>& aU
);
431 void internalAppendN(const T
& aT
, size_t aN
);
432 template <typename U
>
433 void internalAppend(const U
* aBegin
, size_t aLength
);
436 static const size_t sMaxInlineStorage
= MinInlineCapacity
;
438 typedef T ElementType
;
440 explicit Vector(AllocPolicy
= AllocPolicy());
441 Vector(Vector
&&); /* Move constructor. */
442 Vector
& operator=(Vector
&&); /* Move assignment. */
447 const AllocPolicy
& allocPolicy() const { return *this; }
449 AllocPolicy
& allocPolicy() { return *this; }
451 enum { InlineLength
= MinInlineCapacity
};
453 size_t length() const { return mLength
; }
455 bool empty() const { return mLength
== 0; }
457 size_t capacity() const { return mTail
.mCapacity
; }
460 MOZ_ASSERT(!mEntered
);
464 const T
* begin() const {
465 MOZ_ASSERT(!mEntered
);
470 MOZ_ASSERT(!mEntered
);
471 return mBegin
+ mLength
;
474 const T
* end() const {
475 MOZ_ASSERT(!mEntered
);
476 return mBegin
+ mLength
;
479 T
& operator[](size_t aIndex
) {
480 MOZ_ASSERT(!mEntered
);
481 MOZ_ASSERT(aIndex
< mLength
);
482 return begin()[aIndex
];
485 const T
& operator[](size_t aIndex
) const {
486 MOZ_ASSERT(!mEntered
);
487 MOZ_ASSERT(aIndex
< mLength
);
488 return begin()[aIndex
];
492 MOZ_ASSERT(!mEntered
);
493 MOZ_ASSERT(!empty());
497 const T
& back() const {
498 MOZ_ASSERT(!mEntered
);
499 MOZ_ASSERT(!empty());
503 operator mozilla::Span
<const T
>() const {
504 // Explicitly specify template argument here to avoid instantiating Span<T>
505 // first and then implicitly converting to Span<const T>
506 return mozilla::Span
<const T
>{mBegin
, mLength
};
509 operator mozilla::Span
<T
>() { return mozilla::Span
{mBegin
, mLength
}; }
515 Range(T
* aCur
, T
* aEnd
) : mCur(aCur
), mEnd(aEnd
) {
516 MOZ_ASSERT(aCur
<= aEnd
);
520 bool empty() const { return mCur
== mEnd
; }
521 size_t remain() const { return PointerRangeSize(mCur
, mEnd
); }
523 MOZ_ASSERT(!empty());
527 MOZ_ASSERT(!empty());
531 MOZ_ASSERT(!empty());
540 ConstRange(const T
* aCur
, const T
* aEnd
) : mCur(aCur
), mEnd(aEnd
) {
541 MOZ_ASSERT(aCur
<= aEnd
);
545 bool empty() const { return mCur
== mEnd
; }
546 size_t remain() const { return PointerRangeSize(mCur
, mEnd
); }
547 const T
& front() const {
548 MOZ_ASSERT(!empty());
552 MOZ_ASSERT(!empty());
556 MOZ_ASSERT(!empty());
561 Range
all() { return Range(begin(), end()); }
562 ConstRange
all() const { return ConstRange(begin(), end()); }
567 * Reverse the order of the elements in the vector in place.
572 * Given that the vector is empty, grow the internal capacity to |aRequest|,
573 * keeping the length 0.
575 MOZ_MUST_USE
bool initCapacity(size_t aRequest
);
578 * Given that the vector is empty, grow the internal capacity and length to
579 * |aRequest| leaving the elements' memory completely uninitialized (with all
580 * the associated hazards and caveats). This avoids the usual allocation-size
581 * rounding that happens in resize and overhead of initialization for elements
582 * that are about to be overwritten.
584 MOZ_MUST_USE
bool initLengthUninitialized(size_t aRequest
);
587 * If reserve(aRequest) succeeds and |aRequest >= length()|, then appending
588 * |aRequest - length()| elements, in any sequence of append/appendAll calls,
589 * is guaranteed to succeed.
591 * A request to reserve an amount less than the current length does not affect
594 MOZ_MUST_USE
bool reserve(size_t aRequest
);
597 * Destroy elements in the range [end() - aIncr, end()). Does not deallocate
598 * or unreserve storage for those elements.
600 void shrinkBy(size_t aIncr
);
603 * Destroy elements in the range [aNewLength, end()). Does not deallocate
604 * or unreserve storage for those elements.
606 void shrinkTo(size_t aNewLength
);
608 /** Grow the vector by aIncr elements. */
609 MOZ_MUST_USE
bool growBy(size_t aIncr
);
611 /** Call shrinkBy or growBy based on whether newSize > length(). */
612 MOZ_MUST_USE
bool resize(size_t aNewLength
);
615 * Increase the length of the vector, but don't initialize the new elements
616 * -- leave them as uninitialized memory.
618 MOZ_MUST_USE
bool growByUninitialized(size_t aIncr
);
619 void infallibleGrowByUninitialized(size_t aIncr
);
620 MOZ_MUST_USE
bool resizeUninitialized(size_t aNewLength
);
622 /** Shorthand for shrinkBy(length()). */
625 /** Clears and releases any heap-allocated storage. */
629 * Shrinks the storage to drop excess capacity if possible.
631 * The return value indicates whether the operation succeeded, otherwise, it
632 * represents an OOM. The bool can be safely ignored unless you want to
633 * provide the guarantee that `length() == capacity()`.
635 * For PODs, it calls the AllocPolicy's pod_realloc. For non-PODs, it moves
636 * the elements into the new storage.
638 bool shrinkStorageToFit();
641 * If true, appending |aNeeded| elements won't reallocate elements storage.
642 * This *doesn't* mean that infallibleAppend may be used! You still must
643 * reserve the extra space, even if this method indicates that appends won't
644 * need to reallocate elements storage.
646 bool canAppendWithoutRealloc(size_t aNeeded
) const;
648 /** Potentially fallible append operations. */
651 * This can take either a T& or a T&&. Given a T&&, it moves |aU| into the
652 * vector, instead of copying it. If it fails, |aU| is left unmoved. ("We are
655 template <typename U
>
656 MOZ_MUST_USE
bool append(U
&& aU
);
659 * Construct a T in-place as a new entry at the end of this vector.
661 template <typename
... Args
>
662 MOZ_MUST_USE
bool emplaceBack(Args
&&... aArgs
) {
663 if (!growByUninitialized(1)) return false;
664 Impl::new_(&back(), std::forward
<Args
>(aArgs
)...);
668 template <typename U
, size_t O
, class BP
>
669 MOZ_MUST_USE
bool appendAll(const Vector
<U
, O
, BP
>& aU
);
670 MOZ_MUST_USE
bool appendN(const T
& aT
, size_t aN
);
671 template <typename U
>
672 MOZ_MUST_USE
bool append(const U
* aBegin
, const U
* aEnd
);
673 template <typename U
>
674 MOZ_MUST_USE
bool append(const U
* aBegin
, size_t aLength
);
677 * Guaranteed-infallible append operations for use upon vectors whose
678 * memory has been pre-reserved. Don't use this if you haven't reserved the
681 template <typename U
>
682 void infallibleAppend(U
&& aU
) {
683 internalAppend(std::forward
<U
>(aU
));
685 void infallibleAppendN(const T
& aT
, size_t aN
) { internalAppendN(aT
, aN
); }
686 template <typename U
>
687 void infallibleAppend(const U
* aBegin
, const U
* aEnd
) {
688 internalAppend(aBegin
, PointerRangeSize(aBegin
, aEnd
));
690 template <typename U
>
691 void infallibleAppend(const U
* aBegin
, size_t aLength
) {
692 internalAppend(aBegin
, aLength
);
694 template <typename
... Args
>
695 void infallibleEmplaceBack(Args
&&... aArgs
) {
696 infallibleGrowByUninitialized(1);
697 Impl::new_(&back(), std::forward
<Args
>(aArgs
)...);
705 * If elements are stored in-place, return nullptr and leave this vector
708 * Otherwise return this vector's elements buffer, and clear this vector as if
709 * by clearAndFree(). The caller now owns the buffer and is responsible for
710 * deallocating it consistent with this vector's AllocPolicy.
712 * N.B. Although a T*, only the range [0, length()) is constructed.
714 MOZ_MUST_USE T
* extractRawBuffer();
717 * If elements are stored in-place, allocate a new buffer, move this vector's
718 * elements into it, and return that buffer.
720 * Otherwise return this vector's elements buffer. The caller now owns the
721 * buffer and is responsible for deallocating it consistent with this vector's
724 * This vector is cleared, as if by clearAndFree(), when this method
725 * succeeds. This method fails and returns nullptr only if new elements buffer
728 * N.B. Only the range [0, length()) of the returned buffer is constructed.
729 * If any of these elements are uninitialized (as growByUninitialized
730 * enables), behavior is undefined.
732 MOZ_MUST_USE T
* extractOrCopyRawBuffer();
735 * Transfer ownership of an array of objects into the vector. The caller
736 * must have allocated the array in accordance with this vector's
739 * N.B. This call assumes that there are no uninitialized elements in the
740 * passed range [aP, aP + aLength). The range [aP + aLength, aP +
741 * aCapacity) must be allocated uninitialized memory.
743 void replaceRawBuffer(T
* aP
, size_t aLength
, size_t aCapacity
);
746 * Transfer ownership of an array of objects into the vector. The caller
747 * must have allocated the array in accordance with this vector's
750 * N.B. This call assumes that there are no uninitialized elements in the
753 void replaceRawBuffer(T
* aP
, size_t aLength
);
756 * Places |aVal| at position |aP|, shifting existing elements from |aP| onward
757 * one position higher. On success, |aP| should not be reused because it'll
758 * be a dangling pointer if reallocation of the vector storage occurred; the
759 * return value should be used instead. On failure, nullptr is returned.
763 * if (!(p = vec.insert(p, val))) {
766 * <keep working with p>
768 * This is inherently a linear-time operation. Be careful!
770 template <typename U
>
771 MOZ_MUST_USE T
* insert(T
* aP
, U
&& aVal
);
774 * Removes the element |aT|, which must fall in the bounds [begin, end),
775 * shifting existing elements from |aT + 1| onward one position lower.
780 * Removes the elements [|aBegin|, |aEnd|), which must fall in the bounds
781 * [begin, end), shifting existing elements from |aEnd| onward to aBegin's old
784 void erase(T
* aBegin
, T
* aEnd
);
787 * Removes all elements that satisfy the predicate, shifting existing elements
788 * lower to fill erased gaps.
790 template <typename Pred
>
791 void eraseIf(Pred aPred
);
794 * Removes all elements that compare equal to |aU|, shifting existing elements
795 * lower to fill erased gaps.
797 template <typename U
>
798 void eraseIfEqual(const U
& aU
);
801 * Measure the size of the vector's heap-allocated storage.
803 size_t sizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const;
806 * Like sizeOfExcludingThis, but also measures the size of the vector
807 * object (which must be heap-allocated) itself.
809 size_t sizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const;
811 void swap(Vector
& aOther
);
814 Vector(const Vector
&) = delete;
815 void operator=(const Vector
&) = delete;
818 /* This does the re-entrancy check plus several other sanity checks. */
819 #define MOZ_REENTRANCY_GUARD_ET_AL \
820 ReentrancyGuard g(*this); \
821 MOZ_ASSERT_IF(usingInlineStorage(), mTail.mCapacity == kInlineCapacity); \
822 MOZ_ASSERT(reserved() <= mTail.mCapacity); \
823 MOZ_ASSERT(mLength <= reserved()); \
824 MOZ_ASSERT(mLength <= mTail.mCapacity)
826 /* Vector Implementation */
828 template <typename T
, size_t N
, class AP
>
829 MOZ_ALWAYS_INLINE Vector
<T
, N
, AP
>::Vector(AP aAP
)
830 : AP(std::move(aAP
)),
832 mTail(kInlineCapacity
, 0)
838 mBegin
= inlineStorage();
841 /* Move constructor. */
842 template <typename T
, size_t N
, class AllocPolicy
>
843 MOZ_ALWAYS_INLINE Vector
<T
, N
, AllocPolicy
>::Vector(Vector
&& aRhs
)
844 : AllocPolicy(std::move(aRhs
))
850 mLength
= aRhs
.mLength
;
851 mTail
.mCapacity
= aRhs
.mTail
.mCapacity
;
853 mTail
.mReserved
= aRhs
.mTail
.mReserved
;
856 if (aRhs
.usingInlineStorage()) {
857 /* We can't move the buffer over in this case, so copy elements. */
858 mBegin
= inlineStorage();
859 Impl::moveConstruct(mBegin
, aRhs
.beginNoCheck(), aRhs
.endNoCheck());
861 * Leave aRhs's mLength, mBegin, mCapacity, and mReserved as they are.
862 * The elements in its in-line storage still need to be destroyed.
866 * Take src's buffer, and turn src into an empty vector using
869 mBegin
= aRhs
.mBegin
;
870 aRhs
.mBegin
= aRhs
.inlineStorage();
871 aRhs
.mTail
.mCapacity
= kInlineCapacity
;
874 aRhs
.mTail
.mReserved
= 0;
879 /* Move assignment. */
880 template <typename T
, size_t N
, class AP
>
881 MOZ_ALWAYS_INLINE Vector
<T
, N
, AP
>& Vector
<T
, N
, AP
>::operator=(Vector
&& aRhs
) {
882 MOZ_ASSERT(this != &aRhs
, "self-move assignment is prohibited");
884 new (KnownNotNull
, this) Vector(std::move(aRhs
));
888 template <typename T
, size_t N
, class AP
>
889 MOZ_ALWAYS_INLINE Vector
<T
, N
, AP
>::~Vector() {
890 MOZ_REENTRANCY_GUARD_ET_AL
;
891 Impl::destroy(beginNoCheck(), endNoCheck());
892 if (!usingInlineStorage()) {
893 this->free_(beginNoCheck(), mTail
.mCapacity
);
897 template <typename T
, size_t N
, class AP
>
898 MOZ_ALWAYS_INLINE
void Vector
<T
, N
, AP
>::reverse() {
899 MOZ_REENTRANCY_GUARD_ET_AL
;
901 size_t len
= mLength
;
902 size_t mid
= len
/ 2;
903 for (size_t i
= 0; i
< mid
; i
++) {
904 std::swap(elems
[i
], elems
[len
- i
- 1]);
909 * This function will create a new heap buffer with capacity aNewCap,
910 * move all elements in the inline buffer to this new buffer,
913 template <typename T
, size_t N
, class AP
>
914 inline bool Vector
<T
, N
, AP
>::convertToHeapStorage(size_t aNewCap
) {
915 MOZ_ASSERT(usingInlineStorage());
917 /* Allocate buffer. */
918 MOZ_ASSERT(!detail::CapacityHasExcessSpace
<T
>(aNewCap
));
919 T
* newBuf
= this->template pod_malloc
<T
>(aNewCap
);
920 if (MOZ_UNLIKELY(!newBuf
)) {
924 /* Copy inline elements into heap buffer. */
925 Impl::moveConstruct(newBuf
, beginNoCheck(), endNoCheck());
926 Impl::destroy(beginNoCheck(), endNoCheck());
928 /* Switch in heap buffer. */
930 /* mLength is unchanged. */
931 mTail
.mCapacity
= aNewCap
;
935 template <typename T
, size_t N
, class AP
>
936 MOZ_NEVER_INLINE
bool Vector
<T
, N
, AP
>::growStorageBy(size_t aIncr
) {
937 MOZ_ASSERT(mLength
+ aIncr
> mTail
.mCapacity
);
940 * When choosing a new capacity, its size should is as close to 2**N bytes
941 * as possible. 2**N-sized requests are best because they are unlikely to
942 * be rounded up by the allocator. Asking for a 2**N number of elements
943 * isn't as good, because if sizeof(T) is not a power-of-two that would
944 * result in a non-2**N request size.
950 if (usingInlineStorage()) {
951 /* This case occurs in ~70--80% of the calls to this function. */
953 tl::RoundUpPow2
<(kInlineCapacity
+ 1) * sizeof(T
)>::value
;
954 newCap
= newSize
/ sizeof(T
);
959 /* This case occurs in ~0--10% of the calls to this function. */
964 /* This case occurs in ~15--20% of the calls to this function. */
967 * Will mLength * 4 *sizeof(T) overflow? This condition limits a vector
968 * to 1GB of memory on a 32-bit system, which is a reasonable limit. It
971 * static_cast<char*>(end()) - static_cast<char*>(begin())
973 * doesn't overflow ptrdiff_t (see bug 510319).
975 if (MOZ_UNLIKELY(mLength
& tl::MulOverflowMask
<4 * sizeof(T
)>::value
)) {
976 this->reportAllocOverflow();
981 * If we reach here, the existing capacity will have a size that is already
982 * as close to 2^N as sizeof(T) will allow. Just double the capacity, and
983 * then there might be space for one more element.
985 newCap
= mLength
* 2;
986 if (detail::CapacityHasExcessSpace
<T
>(newCap
)) {
990 /* This case occurs in ~2% of the calls to this function. */
991 size_t newMinCap
= mLength
+ aIncr
;
993 /* Did mLength + aIncr overflow? Will newCap * sizeof(T) overflow? */
994 if (MOZ_UNLIKELY(newMinCap
< mLength
||
995 newMinCap
& tl::MulOverflowMask
<2 * sizeof(T
)>::value
)) {
996 this->reportAllocOverflow();
1000 size_t newMinSize
= newMinCap
* sizeof(T
);
1001 size_t newSize
= RoundUpPow2(newMinSize
);
1002 newCap
= newSize
/ sizeof(T
);
1005 if (usingInlineStorage()) {
1007 return convertToHeapStorage(newCap
);
1011 return Impl::growTo(*this, newCap
);
1014 template <typename T
, size_t N
, class AP
>
1015 inline bool Vector
<T
, N
, AP
>::initCapacity(size_t aRequest
) {
1016 MOZ_ASSERT(empty());
1017 MOZ_ASSERT(usingInlineStorage());
1018 if (aRequest
== 0) {
1021 T
* newbuf
= this->template pod_malloc
<T
>(aRequest
);
1022 if (MOZ_UNLIKELY(!newbuf
)) {
1026 mTail
.mCapacity
= aRequest
;
1028 mTail
.mReserved
= aRequest
;
1033 template <typename T
, size_t N
, class AP
>
1034 inline bool Vector
<T
, N
, AP
>::initLengthUninitialized(size_t aRequest
) {
1035 if (!initCapacity(aRequest
)) {
1038 infallibleGrowByUninitialized(aRequest
);
1042 template <typename T
, size_t N
, class AP
>
1043 inline bool Vector
<T
, N
, AP
>::maybeCheckSimulatedOOM(size_t aRequestedSize
) {
1044 if (aRequestedSize
<= N
) {
1049 if (aRequestedSize
<= mTail
.mReserved
) {
1054 return allocPolicy().checkSimulatedOOM();
1057 template <typename T
, size_t N
, class AP
>
1058 inline bool Vector
<T
, N
, AP
>::reserve(size_t aRequest
) {
1059 MOZ_REENTRANCY_GUARD_ET_AL
;
1060 if (aRequest
> mTail
.mCapacity
) {
1061 if (MOZ_UNLIKELY(!growStorageBy(aRequest
- mLength
))) {
1064 } else if (!maybeCheckSimulatedOOM(aRequest
)) {
1068 if (aRequest
> mTail
.mReserved
) {
1069 mTail
.mReserved
= aRequest
;
1071 MOZ_ASSERT(mLength
<= mTail
.mReserved
);
1072 MOZ_ASSERT(mTail
.mReserved
<= mTail
.mCapacity
);
1077 template <typename T
, size_t N
, class AP
>
1078 inline void Vector
<T
, N
, AP
>::shrinkBy(size_t aIncr
) {
1079 MOZ_REENTRANCY_GUARD_ET_AL
;
1080 MOZ_ASSERT(aIncr
<= mLength
);
1081 Impl::destroy(endNoCheck() - aIncr
, endNoCheck());
1085 template <typename T
, size_t N
, class AP
>
1086 MOZ_ALWAYS_INLINE
void Vector
<T
, N
, AP
>::shrinkTo(size_t aNewLength
) {
1087 MOZ_ASSERT(aNewLength
<= mLength
);
1088 shrinkBy(mLength
- aNewLength
);
1091 template <typename T
, size_t N
, class AP
>
1092 MOZ_ALWAYS_INLINE
bool Vector
<T
, N
, AP
>::growBy(size_t aIncr
) {
1093 MOZ_REENTRANCY_GUARD_ET_AL
;
1094 if (aIncr
> mTail
.mCapacity
- mLength
) {
1095 if (MOZ_UNLIKELY(!growStorageBy(aIncr
))) {
1098 } else if (!maybeCheckSimulatedOOM(mLength
+ aIncr
)) {
1101 MOZ_ASSERT(mLength
+ aIncr
<= mTail
.mCapacity
);
1102 T
* newend
= endNoCheck() + aIncr
;
1103 Impl::initialize(endNoCheck(), newend
);
1106 if (mLength
> mTail
.mReserved
) {
1107 mTail
.mReserved
= mLength
;
1113 template <typename T
, size_t N
, class AP
>
1114 MOZ_ALWAYS_INLINE
bool Vector
<T
, N
, AP
>::growByUninitialized(size_t aIncr
) {
1115 MOZ_REENTRANCY_GUARD_ET_AL
;
1116 if (aIncr
> mTail
.mCapacity
- mLength
) {
1117 if (MOZ_UNLIKELY(!growStorageBy(aIncr
))) {
1120 } else if (!maybeCheckSimulatedOOM(mLength
+ aIncr
)) {
1124 if (mLength
+ aIncr
> mTail
.mReserved
) {
1125 mTail
.mReserved
= mLength
+ aIncr
;
1128 infallibleGrowByUninitialized(aIncr
);
1132 template <typename T
, size_t N
, class AP
>
1133 MOZ_ALWAYS_INLINE
void Vector
<T
, N
, AP
>::infallibleGrowByUninitialized(
1135 MOZ_ASSERT(mLength
+ aIncr
<= reserved());
1139 template <typename T
, size_t N
, class AP
>
1140 inline bool Vector
<T
, N
, AP
>::resize(size_t aNewLength
) {
1141 size_t curLength
= mLength
;
1142 if (aNewLength
> curLength
) {
1143 return growBy(aNewLength
- curLength
);
1145 shrinkBy(curLength
- aNewLength
);
1149 template <typename T
, size_t N
, class AP
>
1150 MOZ_ALWAYS_INLINE
bool Vector
<T
, N
, AP
>::resizeUninitialized(
1151 size_t aNewLength
) {
1152 size_t curLength
= mLength
;
1153 if (aNewLength
> curLength
) {
1154 return growByUninitialized(aNewLength
- curLength
);
1156 shrinkBy(curLength
- aNewLength
);
1160 template <typename T
, size_t N
, class AP
>
1161 inline void Vector
<T
, N
, AP
>::clear() {
1162 MOZ_REENTRANCY_GUARD_ET_AL
;
1163 Impl::destroy(beginNoCheck(), endNoCheck());
1167 template <typename T
, size_t N
, class AP
>
1168 inline void Vector
<T
, N
, AP
>::clearAndFree() {
1171 if (usingInlineStorage()) {
1174 this->free_(beginNoCheck(), mTail
.mCapacity
);
1175 mBegin
= inlineStorage();
1176 mTail
.mCapacity
= kInlineCapacity
;
1178 mTail
.mReserved
= 0;
1182 template <typename T
, size_t N
, class AP
>
1183 inline bool Vector
<T
, N
, AP
>::shrinkStorageToFit() {
1184 MOZ_REENTRANCY_GUARD_ET_AL
;
1186 const auto length
= this->length();
1187 if (usingInlineStorage() || length
== capacity()) {
1192 this->free_(beginNoCheck(), mTail
.mCapacity
);
1193 mBegin
= inlineStorage();
1194 mTail
.mCapacity
= kInlineCapacity
;
1196 mTail
.mReserved
= 0;
1203 if (length
<= kInlineCapacity
) {
1204 newBuf
= inlineStorage();
1205 newCap
= kInlineCapacity
;
1208 newBuf
= this->template pod_realloc
<T
>(beginNoCheck(), mTail
.mCapacity
,
1211 newBuf
= this->template pod_malloc
<T
>(length
);
1213 if (MOZ_UNLIKELY(!newBuf
)) {
1218 if (!kElemIsPod
|| newBuf
== inlineStorage()) {
1219 Impl::moveConstruct(newBuf
, beginNoCheck(), endNoCheck());
1220 Impl::destroy(beginNoCheck(), endNoCheck());
1223 this->free_(beginNoCheck(), mTail
.mCapacity
);
1226 mTail
.mCapacity
= newCap
;
1228 mTail
.mReserved
= length
;
1233 template <typename T
, size_t N
, class AP
>
1234 inline bool Vector
<T
, N
, AP
>::canAppendWithoutRealloc(size_t aNeeded
) const {
1235 return mLength
+ aNeeded
<= mTail
.mCapacity
;
1238 template <typename T
, size_t N
, class AP
>
1239 template <typename U
, size_t O
, class BP
>
1240 MOZ_ALWAYS_INLINE
void Vector
<T
, N
, AP
>::internalAppendAll(
1241 const Vector
<U
, O
, BP
>& aOther
) {
1242 internalAppend(aOther
.begin(), aOther
.length());
1245 template <typename T
, size_t N
, class AP
>
1246 template <typename U
>
1247 MOZ_ALWAYS_INLINE
void Vector
<T
, N
, AP
>::internalAppend(U
&& aU
) {
1248 MOZ_ASSERT(mLength
+ 1 <= mTail
.mReserved
);
1249 MOZ_ASSERT(mTail
.mReserved
<= mTail
.mCapacity
);
1250 Impl::new_(endNoCheck(), std::forward
<U
>(aU
));
1254 template <typename T
, size_t N
, class AP
>
1255 MOZ_ALWAYS_INLINE
bool Vector
<T
, N
, AP
>::appendN(const T
& aT
, size_t aNeeded
) {
1256 MOZ_REENTRANCY_GUARD_ET_AL
;
1257 if (mLength
+ aNeeded
> mTail
.mCapacity
) {
1258 if (MOZ_UNLIKELY(!growStorageBy(aNeeded
))) {
1261 } else if (!maybeCheckSimulatedOOM(mLength
+ aNeeded
)) {
1265 if (mLength
+ aNeeded
> mTail
.mReserved
) {
1266 mTail
.mReserved
= mLength
+ aNeeded
;
1269 internalAppendN(aT
, aNeeded
);
1273 template <typename T
, size_t N
, class AP
>
1274 MOZ_ALWAYS_INLINE
void Vector
<T
, N
, AP
>::internalAppendN(const T
& aT
,
1276 MOZ_ASSERT(mLength
+ aNeeded
<= mTail
.mReserved
);
1277 MOZ_ASSERT(mTail
.mReserved
<= mTail
.mCapacity
);
1278 Impl::copyConstructN(endNoCheck(), aNeeded
, aT
);
1282 template <typename T
, size_t N
, class AP
>
1283 template <typename U
>
1284 inline T
* Vector
<T
, N
, AP
>::insert(T
* aP
, U
&& aVal
) {
1285 MOZ_ASSERT(begin() <= aP
);
1286 MOZ_ASSERT(aP
<= end());
1287 size_t pos
= aP
- begin();
1288 MOZ_ASSERT(pos
<= mLength
);
1289 size_t oldLength
= mLength
;
1290 if (pos
== oldLength
) {
1291 if (!append(std::forward
<U
>(aVal
))) {
1295 T oldBack
= std::move(back());
1296 if (!append(std::move(oldBack
))) {
1299 for (size_t i
= oldLength
- 1; i
> pos
; --i
) {
1300 (*this)[i
] = std::move((*this)[i
- 1]);
1302 (*this)[pos
] = std::forward
<U
>(aVal
);
1304 return begin() + pos
;
1307 template <typename T
, size_t N
, class AP
>
1308 inline void Vector
<T
, N
, AP
>::erase(T
* aIt
) {
1309 MOZ_ASSERT(begin() <= aIt
);
1310 MOZ_ASSERT(aIt
< end());
1311 while (aIt
+ 1 < end()) {
1312 *aIt
= std::move(*(aIt
+ 1));
1318 template <typename T
, size_t N
, class AP
>
1319 inline void Vector
<T
, N
, AP
>::erase(T
* aBegin
, T
* aEnd
) {
1320 MOZ_ASSERT(begin() <= aBegin
);
1321 MOZ_ASSERT(aBegin
<= aEnd
);
1322 MOZ_ASSERT(aEnd
<= end());
1323 while (aEnd
< end()) {
1324 *aBegin
++ = std::move(*aEnd
++);
1326 shrinkBy(aEnd
- aBegin
);
1329 template <typename T
, size_t N
, class AP
>
1330 template <typename Pred
>
1331 void Vector
<T
, N
, AP
>::eraseIf(Pred aPred
) {
1332 // remove_if finds the first element to be erased, and then efficiently move-
1333 // assigns elements to effectively overwrite elements that satisfy the
1334 // predicate. It returns the new end pointer, after which there are only
1335 // moved-from elements ready to be destroyed, so we just need to shrink the
1336 // vector accordingly.
1337 T
* newEnd
= std::remove_if(begin(), end(),
1338 [&aPred
](const T
& aT
) { return aPred(aT
); });
1339 MOZ_ASSERT(newEnd
<= end());
1340 shrinkBy(end() - newEnd
);
1343 template <typename T
, size_t N
, class AP
>
1344 template <typename U
>
1345 void Vector
<T
, N
, AP
>::eraseIfEqual(const U
& aU
) {
1346 return eraseIf([&aU
](const T
& aT
) { return aT
== aU
; });
1349 template <typename T
, size_t N
, class AP
>
1350 template <typename U
>
1351 MOZ_ALWAYS_INLINE
bool Vector
<T
, N
, AP
>::append(const U
* aInsBegin
,
1353 MOZ_REENTRANCY_GUARD_ET_AL
;
1354 size_t aNeeded
= PointerRangeSize(aInsBegin
, aInsEnd
);
1355 if (mLength
+ aNeeded
> mTail
.mCapacity
) {
1356 if (MOZ_UNLIKELY(!growStorageBy(aNeeded
))) {
1359 } else if (!maybeCheckSimulatedOOM(mLength
+ aNeeded
)) {
1363 if (mLength
+ aNeeded
> mTail
.mReserved
) {
1364 mTail
.mReserved
= mLength
+ aNeeded
;
1367 internalAppend(aInsBegin
, aNeeded
);
1371 template <typename T
, size_t N
, class AP
>
1372 template <typename U
>
1373 MOZ_ALWAYS_INLINE
void Vector
<T
, N
, AP
>::internalAppend(const U
* aInsBegin
,
1374 size_t aInsLength
) {
1375 MOZ_ASSERT(mLength
+ aInsLength
<= mTail
.mReserved
);
1376 MOZ_ASSERT(mTail
.mReserved
<= mTail
.mCapacity
);
1377 Impl::copyConstruct(endNoCheck(), aInsBegin
, aInsBegin
+ aInsLength
);
1378 mLength
+= aInsLength
;
1381 template <typename T
, size_t N
, class AP
>
1382 template <typename U
>
1383 MOZ_ALWAYS_INLINE
bool Vector
<T
, N
, AP
>::append(U
&& aU
) {
1384 MOZ_REENTRANCY_GUARD_ET_AL
;
1385 if (mLength
== mTail
.mCapacity
) {
1386 if (MOZ_UNLIKELY(!growStorageBy(1))) {
1389 } else if (!maybeCheckSimulatedOOM(mLength
+ 1)) {
1393 if (mLength
+ 1 > mTail
.mReserved
) {
1394 mTail
.mReserved
= mLength
+ 1;
1397 internalAppend(std::forward
<U
>(aU
));
1401 template <typename T
, size_t N
, class AP
>
1402 template <typename U
, size_t O
, class BP
>
1403 MOZ_ALWAYS_INLINE
bool Vector
<T
, N
, AP
>::appendAll(
1404 const Vector
<U
, O
, BP
>& aOther
) {
1405 return append(aOther
.begin(), aOther
.length());
1408 template <typename T
, size_t N
, class AP
>
1410 MOZ_ALWAYS_INLINE
bool Vector
<T
, N
, AP
>::append(const U
* aInsBegin
,
1411 size_t aInsLength
) {
1412 return append(aInsBegin
, aInsBegin
+ aInsLength
);
1415 template <typename T
, size_t N
, class AP
>
1416 MOZ_ALWAYS_INLINE
void Vector
<T
, N
, AP
>::popBack() {
1417 MOZ_REENTRANCY_GUARD_ET_AL
;
1418 MOZ_ASSERT(!empty());
1423 template <typename T
, size_t N
, class AP
>
1424 MOZ_ALWAYS_INLINE T Vector
<T
, N
, AP
>::popCopy() {
1430 template <typename T
, size_t N
, class AP
>
1431 inline T
* Vector
<T
, N
, AP
>::extractRawBuffer() {
1432 MOZ_REENTRANCY_GUARD_ET_AL
;
1434 if (usingInlineStorage()) {
1439 mBegin
= inlineStorage();
1441 mTail
.mCapacity
= kInlineCapacity
;
1443 mTail
.mReserved
= 0;
1448 template <typename T
, size_t N
, class AP
>
1449 inline T
* Vector
<T
, N
, AP
>::extractOrCopyRawBuffer() {
1450 if (T
* ret
= extractRawBuffer()) {
1454 MOZ_REENTRANCY_GUARD_ET_AL
;
1456 T
* copy
= this->template pod_malloc
<T
>(mLength
);
1461 Impl::moveConstruct(copy
, beginNoCheck(), endNoCheck());
1462 Impl::destroy(beginNoCheck(), endNoCheck());
1463 mBegin
= inlineStorage();
1465 mTail
.mCapacity
= kInlineCapacity
;
1467 mTail
.mReserved
= 0;
1472 template <typename T
, size_t N
, class AP
>
1473 inline void Vector
<T
, N
, AP
>::replaceRawBuffer(T
* aP
, size_t aLength
,
1475 MOZ_REENTRANCY_GUARD_ET_AL
;
1477 /* Destroy what we have. */
1478 Impl::destroy(beginNoCheck(), endNoCheck());
1479 if (!usingInlineStorage()) {
1480 this->free_(beginNoCheck(), mTail
.mCapacity
);
1483 /* Take in the new buffer. */
1484 if (aCapacity
<= kInlineCapacity
) {
1486 * We convert to inline storage if possible, even though aP might
1487 * otherwise be acceptable. Maybe this behaviour should be
1488 * specifiable with an argument to this function.
1490 mBegin
= inlineStorage();
1492 mTail
.mCapacity
= kInlineCapacity
;
1493 Impl::moveConstruct(mBegin
, aP
, aP
+ aLength
);
1494 Impl::destroy(aP
, aP
+ aLength
);
1495 this->free_(aP
, aCapacity
);
1499 mTail
.mCapacity
= aCapacity
;
1502 mTail
.mReserved
= aCapacity
;
1506 template <typename T
, size_t N
, class AP
>
1507 inline void Vector
<T
, N
, AP
>::replaceRawBuffer(T
* aP
, size_t aLength
) {
1508 replaceRawBuffer(aP
, aLength
, aLength
);
1511 template <typename T
, size_t N
, class AP
>
1512 inline size_t Vector
<T
, N
, AP
>::sizeOfExcludingThis(
1513 MallocSizeOf aMallocSizeOf
) const {
1514 return usingInlineStorage() ? 0 : aMallocSizeOf(beginNoCheck());
1517 template <typename T
, size_t N
, class AP
>
1518 inline size_t Vector
<T
, N
, AP
>::sizeOfIncludingThis(
1519 MallocSizeOf aMallocSizeOf
) const {
1520 return aMallocSizeOf(this) + sizeOfExcludingThis(aMallocSizeOf
);
1523 template <typename T
, size_t N
, class AP
>
1524 inline void Vector
<T
, N
, AP
>::swap(Vector
& aOther
) {
1525 static_assert(N
== 0, "still need to implement this for N != 0");
1527 // This only works when inline storage is always empty.
1528 if (!usingInlineStorage() && aOther
.usingInlineStorage()) {
1529 aOther
.mBegin
= mBegin
;
1530 mBegin
= inlineStorage();
1531 } else if (usingInlineStorage() && !aOther
.usingInlineStorage()) {
1532 mBegin
= aOther
.mBegin
;
1533 aOther
.mBegin
= aOther
.inlineStorage();
1534 } else if (!usingInlineStorage() && !aOther
.usingInlineStorage()) {
1535 std::swap(mBegin
, aOther
.mBegin
);
1537 // This case is a no-op, since we'd set both to use their inline storage.
1540 std::swap(mLength
, aOther
.mLength
);
1541 std::swap(mTail
.mCapacity
, aOther
.mTail
.mCapacity
);
1543 std::swap(mTail
.mReserved
, aOther
.mTail
.mReserved
);
1547 } // namespace mozilla
1549 #endif /* mozilla_Vector_h */