Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
/* A type/length-parametrized vector class. */
#ifndef mozilla_Vector_h
#define mozilla_Vector_h
#include <new> // for placement new
#include <type_traits>
#include <utility>
#include "mozilla/Alignment.h"
#include "mozilla/AllocPolicy.h"
#include "mozilla/ArrayUtils.h" // for PointerRangeSize
#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/OperatorNewExtensions.h"
#include "mozilla/ReentrancyGuard.h"
#include "mozilla/Span.h"
#include "mozilla/TemplateLib.h"
namespace mozilla {
template <typename T, size_t N, class AllocPolicy>
class Vector;
namespace detail {
/*
* Check that the given capacity wastes the minimal amount of space if
* allocated on the heap. This means that aCapacity*EltSize is as close to a
* power-of-two as possible. growStorageBy() is responsible for ensuring this.
*/
template <size_t EltSize>
static bool CapacityHasExcessSpace(size_t aCapacity) {
size_t size = aCapacity * EltSize;
return RoundUpPow2(size) - size >= EltSize;
}
/*
* AllocPolicy can optionally provide a `computeGrowth<T>(size_t aOldElts,
* size_t aIncr)` method that returns the new number of elements to allocate
* when the current capacity is `aOldElts` and `aIncr` more are being
* requested. If the AllocPolicy does not have such a method, a fallback
* will be used that mostly will just round the new requested capacity up to
* the next power of two, which results in doubling capacity for the most part.
*
* If the new size would overflow some limit, `computeGrowth` returns 0.
*
* A simpler way would be to make computeGrowth() part of the API for all
* AllocPolicy classes, but this turns out to be rather complex because
* mozalloc.h defines a very widely-used InfallibleAllocPolicy, and yet it
* can only be compiled in limited contexts, eg within `extern "C"` and with
* -std=c++11 rather than a later version. That makes the headers that are
* necessary for the computation unavailable (eg mfbt/MathAlgorithms.h).
*/
// Fallback version.
template <size_t EltSize>
inline size_t GrowEltsByDoubling(size_t aOldElts, size_t aIncr) {
/*
* When choosing a new capacity, its size in bytes should is as close to 2**N
* bytes as possible. 2**N-sized requests are best because they are unlikely
* to be rounded up by the allocator. Asking for a 2**N number of elements
* isn't as good, because if EltSize is not a power-of-two that would
* result in a non-2**N request size.
*/
if (aIncr == 1) {
if (aOldElts == 0) {
return 1;
}
/* This case occurs in ~15--20% of the calls to Vector::growStorageBy. */
/*
* Will aOldSize * 4 * sizeof(T) overflow? This condition limits a
* collection to 1GB of memory on a 32-bit system, which is a reasonable
* limit. It also ensures that
*
* static_cast<char*>(end()) - static_cast<char*>(begin())
*
*/
if (MOZ_UNLIKELY(aOldElts &
mozilla::tl::MulOverflowMask<4 * EltSize>::value)) {
return 0;
}
/*
* If we reach here, the existing capacity will have a size that is already
* as close to 2^N as sizeof(T) will allow. Just double the capacity, and
* then there might be space for one more element.
*/
size_t newElts = aOldElts * 2;
if (CapacityHasExcessSpace<EltSize>(newElts)) {
newElts += 1;
}
return newElts;
}
/* This case occurs in ~2% of the calls to Vector::growStorageBy. */
size_t newMinCap = aOldElts + aIncr;
/* Did aOldElts + aIncr overflow? Will newMinCap * EltSize rounded up to the
* next power of two overflow PTRDIFF_MAX? */
if (MOZ_UNLIKELY(newMinCap < aOldElts ||
newMinCap & tl::MulOverflowMask<4 * EltSize>::value)) {
return 0;
}
size_t newMinSize = newMinCap * EltSize;
size_t newSize = RoundUpPow2(newMinSize);
return newSize / EltSize;
};
// Fallback version.
template <typename AP, size_t EltSize>
static size_t ComputeGrowth(size_t aOldElts, size_t aIncr, int) {
return GrowEltsByDoubling<EltSize>(aOldElts, aIncr);
}
// If the AllocPolicy provides its own computeGrowth<EltSize> implementation,
// use that.
template <typename AP, size_t EltSize>
static size_t ComputeGrowth(
size_t aOldElts, size_t aIncr,
decltype(std::declval<AP>().template computeGrowth<EltSize>(0, 0),
bool()) aOverloadSelector) {
size_t newElts = AP::template computeGrowth<EltSize>(aOldElts, aIncr);
MOZ_ASSERT(newElts <= PTRDIFF_MAX && newElts * EltSize <= PTRDIFF_MAX,
return newElts;
}
/*
* This template class provides a default implementation for vector operations
* when the element type is not known to be a POD, as judged by IsPod.
*/
template <typename T, size_t N, class AP, bool IsPod>
struct VectorImpl {
/*
* Constructs an object in the uninitialized memory at *aDst with aArgs.
*/
template <typename... Args>
MOZ_NONNULL(1)
static inline void new_(T* aDst, Args&&... aArgs) {
new (KnownNotNull, aDst) T(std::forward<Args>(aArgs)...);
}
/* Destroys constructed objects in the range [aBegin, aEnd). */
static inline void destroy(T* aBegin, T* aEnd) {
MOZ_ASSERT(aBegin <= aEnd);
for (T* p = aBegin; p < aEnd; ++p) {
p->~T();
}
}
/* Constructs objects in the uninitialized range [aBegin, aEnd). */
static inline void initialize(T* aBegin, T* aEnd) {
MOZ_ASSERT(aBegin <= aEnd);
for (T* p = aBegin; p < aEnd; ++p) {
new_(p);
}
}
/*
* Copy-constructs objects in the uninitialized range
* [aDst, aDst+(aSrcEnd-aSrcStart)) from the range [aSrcStart, aSrcEnd).
*/
template <typename U>
static inline void copyConstruct(T* aDst, const U* aSrcStart,
const U* aSrcEnd) {
MOZ_ASSERT(aSrcStart <= aSrcEnd);
for (const U* p = aSrcStart; p < aSrcEnd; ++p, ++aDst) {
new_(aDst, *p);
}
}
/*
* Move-constructs objects in the uninitialized range
* [aDst, aDst+(aSrcEnd-aSrcStart)) from the range [aSrcStart, aSrcEnd).
*/
template <typename U>
static inline void moveConstruct(T* aDst, U* aSrcStart, U* aSrcEnd) {
MOZ_ASSERT(aSrcStart <= aSrcEnd);
for (U* p = aSrcStart; p < aSrcEnd; ++p, ++aDst) {
new_(aDst, std::move(*p));
}
}
/*
* Copy-constructs objects in the uninitialized range [aDst, aDst+aN) from
* the same object aU.
*/
template <typename U>
static inline void copyConstructN(T* aDst, size_t aN, const U& aU) {
for (T* end = aDst + aN; aDst < end; ++aDst) {
new_(aDst, aU);
}
}
/*
* Grows the given buffer to have capacity aNewCap, preserving the objects
* constructed in the range [begin, end) and updating aV. Assumes that (1)
* aNewCap has not overflowed, and (2) multiplying aNewCap by sizeof(T) will
* not overflow.
*/
[[nodiscard]] static inline bool growTo(Vector<T, N, AP>& aV,
size_t aNewCap) {
MOZ_ASSERT(!aV.usingInlineStorage());
MOZ_ASSERT(!CapacityHasExcessSpace<sizeof(T)>(aNewCap));
T* newbuf = aV.template pod_malloc<T>(aNewCap);
if (MOZ_UNLIKELY(!newbuf)) {
return false;
}
T* dst = newbuf;
T* src = aV.beginNoCheck();
for (; src < aV.endNoCheck(); ++dst, ++src) {
new_(dst, std::move(*src));
}
VectorImpl::destroy(aV.beginNoCheck(), aV.endNoCheck());
aV.free_(aV.mBegin, aV.mTail.mCapacity);
aV.mBegin = newbuf;
/* aV.mLength is unchanged. */
aV.mTail.mCapacity = aNewCap;
return true;
}
};
/*
* This partial template specialization provides a default implementation for
* vector operations when the element type is known to be a POD, as judged by
* IsPod.
*/
template <typename T, size_t N, class AP>
struct VectorImpl<T, N, AP, true> {
template <typename... Args>
MOZ_NONNULL(1)
static inline void new_(T* aDst, Args&&... aArgs) {
// Explicitly construct a local object instead of using a temporary since
// T(args...) will be treated like a C-style cast in the unary case and
// allow unsafe conversions. Both forms should be equivalent to an
// optimizing compiler.
T temp(std::forward<Args>(aArgs)...);
*aDst = temp;
}
static inline void destroy(T*, T*) {}
static inline void initialize(T* aBegin, T* aEnd) {
/*
* You would think that memset would be a big win (or even break even)
* when we know T is a POD. But currently it's not. This is probably
* because |append| tends to be given small ranges and memset requires
* a function call that doesn't get inlined.
*
* memset(aBegin, 0, sizeof(T) * (aEnd - aBegin));
*/
MOZ_ASSERT(aBegin <= aEnd);
for (T* p = aBegin; p < aEnd; ++p) {
new_(p);
}
}
template <typename U>
static inline void copyConstruct(T* aDst, const U* aSrcStart,
const U* aSrcEnd) {
/*
* See above memset comment. Also, notice that copyConstruct is
* currently templated (T != U), so memcpy won't work without
* requiring T == U.
*
* memcpy(aDst, aSrcStart, sizeof(T) * (aSrcEnd - aSrcStart));
*/
MOZ_ASSERT(aSrcStart <= aSrcEnd);
for (const U* p = aSrcStart; p < aSrcEnd; ++p, ++aDst) {
new_(aDst, *p);
}
}
template <typename U>
static inline void moveConstruct(T* aDst, const U* aSrcStart,
const U* aSrcEnd) {
copyConstruct(aDst, aSrcStart, aSrcEnd);
}
static inline void copyConstructN(T* aDst, size_t aN, const T& aT) {
for (T* end = aDst + aN; aDst < end; ++aDst) {
new_(aDst, aT);
}
}
[[nodiscard]] static inline bool growTo(Vector<T, N, AP>& aV,
size_t aNewCap) {
MOZ_ASSERT(!aV.usingInlineStorage());
MOZ_ASSERT(!CapacityHasExcessSpace<sizeof(T)>(aNewCap));
T* newbuf =
aV.template pod_realloc<T>(aV.mBegin, aV.mTail.mCapacity, aNewCap);
if (MOZ_UNLIKELY(!newbuf)) {
return false;
}
aV.mBegin = newbuf;
/* aV.mLength is unchanged. */
aV.mTail.mCapacity = aNewCap;
return true;
}
};
// A struct for TestVector.cpp to access private internal fields.
// DO NOT DEFINE IN YOUR OWN CODE.
struct VectorTesting;
} // namespace detail
/*
* STL-like container providing a short-lived, dynamic buffer. Vector calls the
* constructors/destructors of all elements stored in its internal buffer, so
* non-PODs may be safely used. Additionally, Vector will store the first N
* elements in-place before resorting to dynamic allocation.
*
* T requirements:
* - default and copy constructible, assignable, destructible
* - operations do not throw
* MinInlineCapacity requirements:
* - any value, however, MinInlineCapacity is clamped to min/max values
* AllocPolicy:
* - see "Allocation policies" in AllocPolicy.h (defaults to
* mozilla::MallocAllocPolicy)
*
* Vector is not reentrant: T member functions called during Vector member
* functions must not call back into the same object!
*/
template <typename T, size_t MinInlineCapacity = 0,
class AllocPolicy = MallocAllocPolicy>
class MOZ_NON_PARAM Vector final : private AllocPolicy {
/* utilities */
static constexpr bool kElemIsPod =
std::is_trivial_v<T> && std::is_standard_layout_v<T>;
typedef detail::VectorImpl<T, MinInlineCapacity, AllocPolicy, kElemIsPod>
Impl;
friend struct detail::VectorImpl<T, MinInlineCapacity, AllocPolicy,
kElemIsPod>;
friend struct detail::VectorTesting;
[[nodiscard]] bool growStorageBy(size_t aIncr);
[[nodiscard]] bool convertToHeapStorage(size_t aNewCap);
[[nodiscard]] bool maybeCheckSimulatedOOM(size_t aRequestedSize);
/* magic constants */
/**
* The maximum space allocated for inline element storage.
*
* We reduce space by what the AllocPolicy base class and prior Vector member
* fields likely consume to attempt to play well with binary size classes.
*/
static constexpr size_t kMaxInlineBytes =
1024 -
(sizeof(AllocPolicy) + sizeof(T*) + sizeof(size_t) + sizeof(size_t));
/**
* The number of T elements of inline capacity built into this Vector. This
* is usually |MinInlineCapacity|, but it may be less (or zero!) for large T.
*
* We use a partially-specialized template (not explicit specialization, which
* is only allowed at namespace scope) to compute this value. The benefit is
* that |sizeof(T)| need not be computed, and |T| doesn't have to be fully
* defined at the time |Vector<T>| appears, if no inline storage is requested.
*/
template <size_t MinimumInlineCapacity, size_t Dummy>
struct ComputeCapacity {
static constexpr size_t value =
tl::Min<MinimumInlineCapacity, kMaxInlineBytes / sizeof(T)>::value;
};
template <size_t Dummy>
struct ComputeCapacity<0, Dummy> {
static constexpr size_t value = 0;
};
/** The actual inline capacity in number of elements T. This may be zero! */
static constexpr size_t kInlineCapacity =
ComputeCapacity<MinInlineCapacity, 0>::value;
/* member data */
/*
* Pointer to the buffer, be it inline or heap-allocated. Only [mBegin,
* mBegin + mLength) hold valid constructed T objects. The range [mBegin +
* mLength, mBegin + mCapacity) holds uninitialized memory. The range
* [mBegin + mLength, mBegin + mReserved) also holds uninitialized memory
* previously allocated by a call to reserve().
*/
T* mBegin;
/* Number of elements in the vector. */
size_t mLength;
/*
* Memory used to store capacity, reserved element count (debug builds only),
* and inline storage. The simple "answer" is:
*
* size_t mCapacity;
* #ifdef DEBUG
* size_t mReserved;
* #endif
* alignas(T) unsigned char mBytes[kInlineCapacity * sizeof(T)];
*
* but there are complications. First, C++ forbids zero-sized arrays that
* might result. Second, we don't want zero capacity to affect Vector's size
* (even empty classes take up a byte, unless they're base classes).
*
* Yet again, we eliminate the zero-sized array using partial specialization.
* And we eliminate potential size hit by putting capacity/reserved in one
* struct, then putting the array (if any) in a derived struct. If no array
* is needed, the derived struct won't consume extra space.
*/
struct CapacityAndReserved {
explicit CapacityAndReserved(size_t aCapacity, size_t aReserved)
: mCapacity(aCapacity)
#ifdef DEBUG
,
mReserved(aReserved)
#endif
{
}
CapacityAndReserved() = default;
/* Max number of elements storable in the vector without resizing. */
size_t mCapacity;
#ifdef DEBUG
/* Max elements of reserved or used space in this vector. */
size_t mReserved;
#endif
};
// Silence warnings about this struct possibly being padded dued to the
// alignas() in it -- there's nothing we can do to avoid it.
#ifdef _MSC_VER
# pragma warning(push)
# pragma warning(disable : 4324)
#endif // _MSC_VER
template <size_t Capacity, size_t Dummy>
struct CRAndStorage : CapacityAndReserved {
explicit CRAndStorage(size_t aCapacity, size_t aReserved)
: CapacityAndReserved(aCapacity, aReserved) {}
CRAndStorage() = default;
alignas(T) unsigned char mBytes[Capacity * sizeof(T)];
// GCC fails due to -Werror=strict-aliasing if |mBytes| is directly cast to
// T*. Indirecting through this function addresses the problem.
void* data() { return mBytes; }
T* storage() { return static_cast<T*>(data()); }
};
template <size_t Dummy>
struct CRAndStorage<0, Dummy> : CapacityAndReserved {
explicit CRAndStorage(size_t aCapacity, size_t aReserved)
: CapacityAndReserved(aCapacity, aReserved) {}
CRAndStorage() = default;
T* storage() {
// If this returns |nullptr|, functions like |Vector::begin()| would too,
// breaking callers that pass a vector's elements as pointer/length to
// code that bounds its operation by length but (even just as a sanity
// check) always wants a non-null pointer. Fake up an aligned, non-null
// pointer to support these callers.
return reinterpret_cast<T*>(sizeof(T));
}
};
CRAndStorage<kInlineCapacity, 0> mTail;
#ifdef _MSC_VER
# pragma warning(pop)
#endif // _MSC_VER
#ifdef DEBUG
friend class ReentrancyGuard;
bool mEntered;
#endif
/* private accessors */
bool usingInlineStorage() const {
return mBegin == const_cast<Vector*>(this)->inlineStorage();
}
T* inlineStorage() { return mTail.storage(); }
T* beginNoCheck() const { return mBegin; }
T* endNoCheck() { return mBegin + mLength; }
const T* endNoCheck() const { return mBegin + mLength; }
#ifdef DEBUG
/**
* The amount of explicitly allocated space in this vector that is immediately
* available to be filled by appending additional elements. This value is
* always greater than or equal to |length()| -- the vector's actual elements
* are implicitly reserved. This value is always less than or equal to
* |capacity()|. It may be explicitly increased using the |reserve()| method.
*/
size_t reserved() const {
MOZ_ASSERT(mLength <= mTail.mReserved);
MOZ_ASSERT(mTail.mReserved <= mTail.mCapacity);
return mTail.mReserved;
}
#endif
bool internalEnsureCapacity(size_t aNeeded);
/* Append operations guaranteed to succeed due to pre-reserved space. */
template <typename U>
void internalAppend(U&& aU);
template <typename U, size_t O, class BP>
void internalAppendAll(const Vector<U, O, BP>& aU);
void internalAppendN(const T& aT, size_t aN);
template <typename U>
void internalAppend(const U* aBegin, size_t aLength);
template <typename U>
void internalMoveAppend(U* aBegin, size_t aLength);
public:
static const size_t sMaxInlineStorage = MinInlineCapacity;
typedef T ElementType;
explicit Vector(AllocPolicy);
Vector() : Vector(AllocPolicy()) {}
Vector(Vector&&); /* Move constructor. */
Vector& operator=(Vector&&); /* Move assignment. */
~Vector();
/* accessors */
const AllocPolicy& allocPolicy() const { return *this; }
AllocPolicy& allocPolicy() { return *this; }
enum { InlineLength = MinInlineCapacity };
size_t length() const { return mLength; }
bool empty() const { return mLength == 0; }
size_t capacity() const { return mTail.mCapacity; }
T* begin() {
MOZ_ASSERT(!mEntered);
return mBegin;
}
const T* begin() const {
MOZ_ASSERT(!mEntered);
return mBegin;
}
T* end() {
MOZ_ASSERT(!mEntered);
return mBegin + mLength;
}
const T* end() const {
MOZ_ASSERT(!mEntered);
return mBegin + mLength;
}
T& operator[](size_t aIndex) {
MOZ_ASSERT(!mEntered);
MOZ_ASSERT(aIndex < mLength);
return begin()[aIndex];
}
const T& operator[](size_t aIndex) const {
MOZ_ASSERT(!mEntered);
MOZ_ASSERT(aIndex < mLength);
return begin()[aIndex];
}
T& back() {
MOZ_ASSERT(!mEntered);
MOZ_ASSERT(!empty());
return *(end() - 1);
}
const T& back() const {
MOZ_ASSERT(!mEntered);
MOZ_ASSERT(!empty());
return *(end() - 1);
}
operator mozilla::Span<const T>() const {
// Explicitly specify template argument here to avoid instantiating Span<T>
// first and then implicitly converting to Span<const T>
return mozilla::Span<const T>{mBegin, mLength};
}
operator mozilla::Span<T>() { return mozilla::Span{mBegin, mLength}; }
class Range {
friend class Vector;
T* mCur;
T* mEnd;
Range(T* aCur, T* aEnd) : mCur(aCur), mEnd(aEnd) {
MOZ_ASSERT(aCur <= aEnd);
}
public:
bool empty() const { return mCur == mEnd; }
size_t remain() const { return PointerRangeSize(mCur, mEnd); }
T& front() const {
MOZ_ASSERT(!empty());
return *mCur;
}
void popFront() {
MOZ_ASSERT(!empty());
++mCur;
}
T popCopyFront() {
MOZ_ASSERT(!empty());
return *mCur++;
}
};
class ConstRange {
friend class Vector;
const T* mCur;
const T* mEnd;
ConstRange(const T* aCur, const T* aEnd) : mCur(aCur), mEnd(aEnd) {
MOZ_ASSERT(aCur <= aEnd);
}
public:
bool empty() const { return mCur == mEnd; }
size_t remain() const { return PointerRangeSize(mCur, mEnd); }
const T& front() const {