Source code

Revision control

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
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#ifndef nsTArray_h__
#define nsTArray_h__
#include <string.h>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <new>
#include <ostream>
#include <type_traits>
#include <utility>
#include "mozilla/Alignment.h"
#include "mozilla/ArrayIterator.h"
#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include "mozilla/BinarySearch.h"
#include "mozilla/CheckedInt.h"
#include "mozilla/FunctionTypeTraits.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/NotNull.h"
#include "mozilla/Span.h"
#include "mozilla/fallible.h"
#include "mozilla/mozalloc.h"
#include "nsAlgorithm.h"
#include "nsDebug.h"
#include "nsISupports.h"
#include "nsQuickSort.h"
#include "nsRegionFwd.h"
#include "nsTArrayForwardDeclare.h"
namespace JS {
template <class T>
class Heap;
} /* namespace JS */
class nsCycleCollectionTraversalCallback;
class nsRegion;
namespace mozilla::a11y {
class BatchData;
}
namespace mozilla {
namespace layers {
class Animation;
class FrameStats;
struct PropertyAnimationGroup;
struct TileClient;
} // namespace layers
} // namespace mozilla
namespace mozilla {
struct SerializedStructuredCloneBuffer;
class SourceBufferTask;
} // namespace mozilla
namespace mozilla::dom::binding_detail {
template <typename, typename>
class RecordEntry;
}
namespace mozilla::dom::ipc {
class StructuredCloneData;
} // namespace mozilla::dom::ipc
namespace mozilla::dom {
class ClonedMessageData;
class MessageData;
class MessagePortIdentifier;
struct MozPluginParameter;
template <typename T>
struct Nullable;
class OwningFileOrDirectory;
class OwningStringOrBooleanOrObject;
class OwningUTF8StringOrDouble;
class Pref;
class RefMessageData;
class ResponsiveImageCandidate;
class ServiceWorkerRegistrationData;
namespace indexedDB {
class SerializedStructuredCloneReadInfo;
class ObjectStoreCursorResponse;
class IndexCursorResponse;
} // namespace indexedDB
} // namespace mozilla::dom
namespace mozilla::ipc {
class AutoIPCStream;
class ContentSecurityPolicy;
template <class T>
class Endpoint;
} // namespace mozilla::ipc
class JSStructuredCloneData;
template <class T>
class RefPtr;
//
// nsTArray<E> is a resizable array class, like std::vector.
//
// Unlike std::vector, which follows C++'s construction/destruction rules,
// By default, nsTArray assumes that instances of E can be relocated safely
// using memory utils (memcpy/memmove).
//
// The public classes defined in this header are
//
// nsTArray<E>,
// CopyableTArray<E>,
// FallibleTArray<E>,
// AutoTArray<E, N>,
// CopyableAutoTArray<E, N>
//
// nsTArray, CopyableTArray, AutoTArray and CopyableAutoTArray are infallible by
// default. To opt-in to fallible behaviour, use the `mozilla::fallible`
// parameter and check the return value.
//
// CopyableTArray and CopyableAutoTArray< are copy-constructible and
// copy-assignable. Use these only when syntactically necessary to avoid implcit
// unintentional copies. nsTArray/AutoTArray can be conveniently copied using
// the Clone() member function. Consider using std::move where possible.
//
// If you just want to declare the nsTArray types (e.g., if you're in a header
// file and don't need the full nsTArray definitions) consider including
// nsTArrayForwardDeclare.h instead of nsTArray.h.
//
// The template parameter E specifies the type of the elements and has the
// following requirements:
//
// E MUST be safely memmove()'able.
// E MUST define a copy-constructor.
// E MAY define operator< for sorting.
// E MAY define operator== for searching.
//
// (Note that the memmove requirement may be relaxed for certain types - see
// nsTArray_RelocationStrategy below.)
//
// There is a public type elem_type defined as E within each array class, and we
// reference the type under this name below.
//
// For member functions taking a Comparator instance, Comparator must be either
// a functor with a tri-state comparison function with a signature compatible to
//
// /** @return negative iff a < b, 0 iff a == b, positive iff a > b */
// int (const elem_type& a, const elem_type& b);
//
// or a class defining member functions with signatures compatible to:
//
// class Comparator {
// public:
// /** @return True if the elements are equals; false otherwise. */
// bool Equals(const elem_type& a, const elem_type& b) const;
//
// /** @return True if (a < b); false otherwise. */
// bool LessThan(const elem_type& a, const elem_type& b) const;
// };
//
// The Equals member function is used for searching, and the LessThan member
// function is used for searching and sorting. Note that some member functions,
// e.g. Compare, are templates where a different type Item can be used for the
// element to compare to. In that case, the signatures must be compatible to
// allow those comparisons, but the details are not documented here.
//
//
// nsTArrayFallibleResult and nsTArrayInfallibleResult types are proxy types
// which are used because you cannot use a templated type which is bound to
// void as an argument to a void function. In order to work around that, we
// encode either a void or a boolean inside these proxy objects, and pass them
// to the aforementioned function instead, and then use the type information to
// decide what to do in the function.
//
// Note that public nsTArray methods should never return a proxy type. Such
// types are only meant to be used in the internal nsTArray helper methods.
// Public methods returning non-proxy types cannot be called from other
// nsTArray members.
//
struct nsTArrayFallibleResult {
// Note: allows implicit conversions from and to bool
MOZ_IMPLICIT constexpr nsTArrayFallibleResult(bool aResult)
: mResult(aResult) {}
MOZ_IMPLICIT constexpr operator bool() { return mResult; }
private:
bool mResult;
};
struct nsTArrayInfallibleResult {};
//
// nsTArray*Allocators must all use the same |free()|, to allow swap()'ing
// between fallible and infallible variants.
//
struct nsTArrayFallibleAllocatorBase {
typedef bool ResultType;
typedef nsTArrayFallibleResult ResultTypeProxy;
static constexpr ResultType Result(ResultTypeProxy aResult) {
return aResult;
}
static constexpr bool Successful(ResultTypeProxy aResult) { return aResult; }
static constexpr ResultTypeProxy SuccessResult() { return true; }
static constexpr ResultTypeProxy FailureResult() { return false; }
static constexpr ResultType ConvertBoolToResultType(bool aValue) {
return aValue;
}
};
struct nsTArrayInfallibleAllocatorBase {
typedef void ResultType;
typedef nsTArrayInfallibleResult ResultTypeProxy;
static constexpr ResultType Result(ResultTypeProxy aResult) {}
static constexpr bool Successful(ResultTypeProxy) { return true; }
static constexpr ResultTypeProxy SuccessResult() { return ResultTypeProxy(); }
[[noreturn]] static ResultTypeProxy FailureResult() {
MOZ_CRASH("Infallible nsTArray should never fail");
}
template <typename T>
static constexpr ResultType ConvertBoolToResultType(T aValue) {
if (!aValue) {
MOZ_CRASH("infallible nsTArray should never convert false to ResultType");
}
}
template <typename T>
static constexpr ResultType ConvertBoolToResultType(
const mozilla::NotNull<T>& aValue) {}
};
struct nsTArrayFallibleAllocator : nsTArrayFallibleAllocatorBase {
static void* Malloc(size_t aSize) { return malloc(aSize); }
static void* Realloc(void* aPtr, size_t aSize) {
return realloc(aPtr, aSize);
}
static void Free(void* aPtr) { free(aPtr); }
static void SizeTooBig(size_t) {}
};
struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase {
static void* Malloc(size_t aSize) MOZ_NONNULL_RETURN {
return moz_xmalloc(aSize);
}
static void* Realloc(void* aPtr, size_t aSize) MOZ_NONNULL_RETURN {
return moz_xrealloc(aPtr, aSize);
}
static void Free(void* aPtr) { free(aPtr); }
static void SizeTooBig(size_t aSize) { NS_ABORT_OOM(aSize); }
};
// nsTArray_base stores elements into the space allocated beyond
// sizeof(*this). This is done to minimize the size of the nsTArray
// object when it is empty.
struct nsTArrayHeader {
uint32_t mLength;
uint32_t mCapacity : 31;
uint32_t mIsAutoArray : 1;
};
extern "C" {
extern const nsTArrayHeader sEmptyTArrayHeader;
}
namespace detail {
// nsTArray_CopyDisabler disables copy operations.
class nsTArray_CopyDisabler {
public:
nsTArray_CopyDisabler() = default;
nsTArray_CopyDisabler(const nsTArray_CopyDisabler&) = delete;
nsTArray_CopyDisabler& operator=(const nsTArray_CopyDisabler&) = delete;
};
} // namespace detail
// This class provides a SafeElementAt method to nsTArray<E*> which does
// not take a second default value parameter.
template <class E, class Derived>
struct nsTArray_SafeElementAtHelper : public ::detail::nsTArray_CopyDisabler {
typedef E* elem_type;
typedef size_t index_type;
// No implementation is provided for these two methods, and that is on
// purpose, since we don't support these functions on non-pointer type
// instantiations.
elem_type& SafeElementAt(index_type aIndex);
const elem_type& SafeElementAt(index_type aIndex) const;
};
template <class E, class Derived>
struct nsTArray_SafeElementAtHelper<E*, Derived>
: public ::detail::nsTArray_CopyDisabler {
typedef E* elem_type;
// typedef const E* const_elem_type; XXX: see below
typedef size_t index_type;
elem_type SafeElementAt(index_type aIndex) {
return static_cast<Derived*>(this)->SafeElementAt(aIndex, nullptr);
}
// XXX: Probably should return const_elem_type, but callsites must be fixed.
// Also, the use of const_elem_type for nsTArray<xpcGCCallback> in
// xpcprivate.h causes build failures on Windows because xpcGCCallback is a
// function pointer and MSVC doesn't like qualifying it with |const|.
elem_type SafeElementAt(index_type aIndex) const {
return static_cast<const Derived*>(this)->SafeElementAt(aIndex, nullptr);
}
};
// E is a smart pointer type; the
// smart pointer can act as its element_type*.
template <class E, class Derived>
struct nsTArray_SafeElementAtSmartPtrHelper
: public ::detail::nsTArray_CopyDisabler {
typedef typename E::element_type* elem_type;
typedef const typename E::element_type* const_elem_type;
typedef size_t index_type;
elem_type SafeElementAt(index_type aIndex) {
auto* derived = static_cast<Derived*>(this);
if (aIndex < derived->Length()) {
return derived->Elements()[aIndex];
}
return nullptr;
}
// XXX: Probably should return const_elem_type, but callsites must be fixed.
elem_type SafeElementAt(index_type aIndex) const {
auto* derived = static_cast<const Derived*>(this);
if (aIndex < derived->Length()) {
return derived->Elements()[aIndex];
}
return nullptr;
}
};
template <class T>
class nsCOMPtr;
template <class E, class Derived>
struct nsTArray_SafeElementAtHelper<nsCOMPtr<E>, Derived>
: public nsTArray_SafeElementAtSmartPtrHelper<nsCOMPtr<E>, Derived> {};
template <class E, class Derived>
struct nsTArray_SafeElementAtHelper<RefPtr<E>, Derived>
: public nsTArray_SafeElementAtSmartPtrHelper<RefPtr<E>, Derived> {};
namespace mozilla {
template <class T>
class OwningNonNull;
} // namespace mozilla
template <class E, class Derived>
struct nsTArray_SafeElementAtHelper<mozilla::OwningNonNull<E>, Derived>
: public nsTArray_SafeElementAtSmartPtrHelper<mozilla::OwningNonNull<E>,
Derived> {};
// Servo bindings.
extern "C" void Gecko_EnsureTArrayCapacity(void* aArray, size_t aCapacity,
size_t aElementSize);
extern "C" void Gecko_ClearPODTArray(void* aArray, size_t aElementSize,
size_t aElementAlign);
MOZ_NORETURN MOZ_COLD void InvalidArrayIndex_CRASH(size_t aIndex,
size_t aLength);
//
// This class serves as a base class for nsTArray. It shouldn't be used
// directly. It holds common implementation code that does not depend on the
// element type of the nsTArray.
//
template <class Alloc, class RelocationStrategy>
class nsTArray_base {
// Allow swapping elements with |nsTArray_base|s created using a
// different allocator. This is kosher because all allocators use
// the same free().
template <class XAlloc, class XRelocationStrategy>
friend class nsTArray_base;
// Needed for AppendElements from an array with a different allocator, which
// calls ShiftData.
template <class E, class XAlloc>
friend class nsTArray_Impl;
friend void Gecko_EnsureTArrayCapacity(void* aArray, size_t aCapacity,
size_t aElemSize);
friend void Gecko_ClearPODTArray(void* aTArray, size_t aElementSize,
size_t aElementAlign);
protected:
typedef nsTArrayHeader Header;
public:
typedef size_t size_type;
typedef size_t index_type;
// @return The number of elements in the array.
size_type Length() const { return mHdr->mLength; }
// @return True if the array is empty or false otherwise.
bool IsEmpty() const { return Length() == 0; }
// @return The number of elements that can fit in the array without forcing
// the array to be re-allocated. The length of an array is always less
// than or equal to its capacity.
size_type Capacity() const { return mHdr->mCapacity; }
#ifdef DEBUG
void* DebugGetHeader() const { return mHdr; }
#endif
protected:
nsTArray_base();
~nsTArray_base();
nsTArray_base(const nsTArray_base&);
nsTArray_base& operator=(const nsTArray_base&);
// Resize the storage if necessary to achieve the requested capacity.
// @param aCapacity The requested number of array elements.
// @param aElemSize The size of an array element.
// @return False if insufficient memory is available; true otherwise.
template <typename ActualAlloc>
typename ActualAlloc::ResultTypeProxy EnsureCapacity(size_type aCapacity,
size_type aElemSize);
// Extend the storage to accommodate aCount extra elements.
// @param aLength The current size of the array.
// @param aCount The number of elements to add.
// @param aElemSize The size of an array element.
// @return False if insufficient memory is available or the new length
// would overflow; true otherwise.
template <typename ActualAlloc>
typename ActualAlloc::ResultTypeProxy ExtendCapacity(size_type aLength,
size_type aCount,
size_type aElemSize);
// Tries to resize the storage to the minimum required amount. If this fails,
// the array is left as-is.
// @param aElemSize The size of an array element.
// @param aElemAlign The alignment in bytes of an array element.
void ShrinkCapacity(size_type aElemSize, size_t aElemAlign);
// Resizes the storage to 0. This may only be called when Length() is already
// 0.
// @param aElemSize The size of an array element.
// @param aElemAlign The alignment in bytes of an array element.
void ShrinkCapacityToZero(size_type aElemSize, size_t aElemAlign);
// This method may be called to resize a "gap" in the array by shifting
// elements around. It updates mLength appropriately. If the resulting
// array has zero elements, then the array's memory is free'd.
// @param aStart The starting index of the gap.
// @param aOldLen The current length of the gap.
// @param aNewLen The desired length of the gap.
// @param aElemSize The size of an array element.
// @param aElemAlign The alignment in bytes of an array element.
template <typename ActualAlloc>
void ShiftData(index_type aStart, size_type aOldLen, size_type aNewLen,
size_type aElemSize, size_t aElemAlign);
// This method may be called to swap elements from the end of the array to
// fill a "gap" in the array. If the resulting array has zero elements, then
// the array's memory is free'd.
// @param aStart The starting index of the gap.
// @param aCount The length of the gap.
// @param aElemSize The size of an array element.
// @param aElemAlign The alignment in bytes of an array element.
template <typename ActualAlloc>
void SwapFromEnd(index_type aStart, size_type aCount, size_type aElemSize,
size_t aElemAlign);
// This method increments the length member of the array's header.
// Note that mHdr may actually be sEmptyTArrayHeader in the case where a
// zero-length array is inserted into our array. But then aNum should
// always be 0.
void IncrementLength(size_t aNum) {
if (HasEmptyHeader()) {
if (MOZ_UNLIKELY(aNum != 0)) {
// Writing a non-zero length to the empty header would be extremely bad.
MOZ_CRASH();
}
} else {
mHdr->mLength += aNum;
}
}
// This method inserts blank slots into the array.
// @param aIndex the place to insert the new elements. This must be no
// greater than the current length of the array.
// @param aCount the number of slots to insert
// @param aElementSize the size of an array element.
// @param aElemAlign the alignment in bytes of an array element.
template <typename ActualAlloc>
typename ActualAlloc::ResultTypeProxy InsertSlotsAt(index_type aIndex,
size_type aCount,
size_type aElementSize,
size_t aElemAlign);
template <typename ActualAlloc, class Allocator>
typename ActualAlloc::ResultTypeProxy SwapArrayElements(
nsTArray_base<Allocator, RelocationStrategy>& aOther, size_type aElemSize,
size_t aElemAlign);
template <class Allocator>
void MoveConstructNonAutoArray(
nsTArray_base<Allocator, RelocationStrategy>& aOther, size_type aElemSize,
size_t aElemAlign);
template <class Allocator>
void MoveInit(nsTArray_base<Allocator, RelocationStrategy>& aOther,
size_type aElemSize, size_t aElemAlign);
// This is an RAII class used in SwapArrayElements.
class IsAutoArrayRestorer {
public:
IsAutoArrayRestorer(nsTArray_base<Alloc, RelocationStrategy>& aArray,
size_t aElemAlign);
~IsAutoArrayRestorer();
private:
nsTArray_base<Alloc, RelocationStrategy>& mArray;
size_t mElemAlign;
bool mIsAuto;
};
// Helper function for SwapArrayElements. Ensures that if the array
// is an AutoTArray that it doesn't use the built-in buffer.
template <typename ActualAlloc>
bool EnsureNotUsingAutoArrayBuffer(size_type aElemSize);
// Returns true if this nsTArray is an AutoTArray with a built-in buffer.
bool IsAutoArray() const { return mHdr->mIsAutoArray; }
// Returns a Header for the built-in buffer of this AutoTArray.
Header* GetAutoArrayBuffer(size_t aElemAlign) {
MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");
return GetAutoArrayBufferUnsafe(aElemAlign);
}
const Header* GetAutoArrayBuffer(size_t aElemAlign) const {
MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");
return GetAutoArrayBufferUnsafe(aElemAlign);
}
// Returns a Header for the built-in buffer of this AutoTArray, but doesn't
// assert that we are an AutoTArray.
Header* GetAutoArrayBufferUnsafe(size_t aElemAlign) {
return const_cast<Header*>(
static_cast<const nsTArray_base<Alloc, RelocationStrategy>*>(this)
->GetAutoArrayBufferUnsafe(aElemAlign));
}
const Header* GetAutoArrayBufferUnsafe(size_t aElemAlign) const;
// Returns true if this is an AutoTArray and it currently uses the
// built-in buffer to store its elements.
bool UsesAutoArrayBuffer() const;
// The array's elements (prefixed with a Header). This pointer is never
// null. If the array is empty, then this will point to sEmptyTArrayHeader.
Header* mHdr;
Header* Hdr() const MOZ_NONNULL_RETURN { return mHdr; }
Header** PtrToHdr() MOZ_NONNULL_RETURN { return &mHdr; }
static Header* EmptyHdr() MOZ_NONNULL_RETURN {
return const_cast<Header*>(&sEmptyTArrayHeader);
}
[[nodiscard]] bool HasEmptyHeader() const { return mHdr == EmptyHdr(); }
};
namespace detail {
// Used for argument checking in nsTArrayElementTraits::Emplace.
template <typename... T>
struct ChooseFirst;
template <>
struct ChooseFirst<> {
// Choose a default type that is guaranteed to not match E* for any
// nsTArray<E>.
typedef void Type;
};
template <typename A, typename... Args>
struct ChooseFirst<A, Args...> {
typedef A Type;
};
} // namespace detail
//
// This class defines convenience functions for element specific operations.
// Specialize this template if necessary.
//
template <class E>
class nsTArrayElementTraits {
public:
// Invoke the default constructor in place.
static inline void Construct(E* aE) {
// Do NOT call "E()"! That triggers C++ "default initialization"
// which zeroes out POD ("plain old data") types such as regular
// ints. We don't want that because it can be a performance issue
// and people don't expect it; nsTArray should work like a regular
// C/C++ array in this respect.
new (static_cast<void*>(aE)) E;
}
// Invoke the copy-constructor in place.
template <class A>
static inline void Construct(E* aE, A&& aArg) {
using E_NoCV = std::remove_cv_t<E>;
using A_NoCV = std::remove_cv_t<A>;
static_assert(!std::is_same_v<E_NoCV*, A_NoCV>,
"For safety, we disallow constructing nsTArray<E> elements "
"from E* pointers. See bug 960591.");
new (static_cast<void*>(aE)) E(std::forward<A>(aArg));
}
// Construct in place.
template <class... Args>
static inline void Emplace(E* aE, Args&&... aArgs) {
using E_NoCV = std::remove_cv_t<E>;
using A_NoCV =
std::remove_cv_t<typename ::detail::ChooseFirst<Args...>::Type>;
static_assert(!std::is_same_v<E_NoCV*, A_NoCV>,
"For safety, we disallow constructing nsTArray<E> elements "
"from E* pointers. See bug 960591.");
new (static_cast<void*>(aE)) E(std::forward<Args>(aArgs)...);
}
// Invoke the destructor in place.
static inline void Destruct(E* aE) { aE->~E(); }
};
// The default comparator used by nsTArray
template <class A, class B>
class nsDefaultComparator {
public:
bool Equals(const A& aA, const B& aB) const { return aA == aB; }
bool LessThan(const A& aA, const B& aB) const { return aA < aB; }
};
template <bool IsTriviallyCopyConstructible, bool IsSameType>
struct AssignRangeAlgorithm {
template <class Item, class ElemType, class IndexType, class SizeType>
static void implementation(ElemType* aElements, IndexType aStart,
SizeType aCount, const Item* aValues) {
ElemType* iter = aElements + aStart;
ElemType* end = iter + aCount;
for (; iter != end; ++iter, ++aValues) {
nsTArrayElementTraits<ElemType>::Construct(iter, *aValues);
}
}
};
template <>
struct AssignRangeAlgorithm<true, true> {
template <class Item, class ElemType, class IndexType, class SizeType>
static void implementation(ElemType* aElements, IndexType aStart,
SizeType aCount, const Item* aValues) {
if (aValues) {
memcpy(aElements + aStart, aValues, aCount * sizeof(ElemType));
}
}
};
//
// Normally elements are copied with memcpy and memmove, but for some element
// types that is problematic. The nsTArray_RelocationStrategy template class
// can be specialized to ensure that copying calls constructors and destructors
// instead, as is done below for JS::Heap<E> elements.
//
//
// A class that defines how to copy elements using memcpy/memmove.
//
struct nsTArray_RelocateUsingMemutils {
const static bool allowRealloc = true;
static void RelocateNonOverlappingRegionWithHeader(void* aDest,
const void* aSrc,
size_t aCount,
size_t aElemSize) {
memcpy(aDest, aSrc, sizeof(nsTArrayHeader) + aCount * aElemSize);
}
static void RelocateOverlappingRegion(void* aDest, void* aSrc, size_t aCount,
size_t aElemSize) {
memmove(aDest, aSrc, aCount * aElemSize);
}
static void RelocateNonOverlappingRegion(void* aDest, void* aSrc,
size_t aCount, size_t aElemSize) {
memcpy(aDest, aSrc, aCount * aElemSize);
}
};
//
// A template class that defines how to relocate elements using the type's move
// constructor and destructor appropriately.
//
template <class ElemType>
struct nsTArray_RelocateUsingMoveConstructor {
typedef nsTArrayElementTraits<ElemType> traits;
const static bool allowRealloc = false;
static void RelocateNonOverlappingRegionWithHeader(void* aDest, void* aSrc,
size_t aCount,
size_t aElemSize) {
nsTArrayHeader* destHeader = static_cast<nsTArrayHeader*>(aDest);
nsTArrayHeader* srcHeader = static_cast<nsTArrayHeader*>(aSrc);
*destHeader = *srcHeader;
RelocateNonOverlappingRegion(
static_cast<uint8_t*>(aDest) + sizeof(nsTArrayHeader),
static_cast<uint8_t*>(aSrc) + sizeof(nsTArrayHeader), aCount,
aElemSize);
}
// RelocateNonOverlappingRegion and RelocateOverlappingRegion are defined by
// analogy with memmove and memcpy that are used for relocation of
// trivially-relocatable types through nsTArray_RelocateUsingMemutils. What
// they actually do is slightly different: RelocateOverlappingRegion checks to
// see which direction the movement needs to take place, whether from
// back-to-front of the range to be moved or from front-to-back.
// RelocateNonOverlappingRegion assumes that relocating front-to-back is
// always valid. They use RelocateRegionForward and RelocateRegionBackward,
// which are analogous to std::move and std::move_backward respectively,
// except they don't move-assign the destination from the source but
// move-construct the destination from the source and destroy the source.
static void RelocateOverlappingRegion(void* aDest, void* aSrc, size_t aCount,
size_t aElemSize) {
ElemType* destBegin = static_cast<ElemType*>(aDest);
ElemType* srcBegin = static_cast<ElemType*>(aSrc);
// If destination and source are the same, this is a no-op.
// In practice, we don't do this.
if (destBegin == srcBegin) {
return;
}
ElemType* srcEnd = srcBegin + aCount;
ElemType* destEnd = destBegin + aCount;
// Figure out whether to relocate back-to-front or front-to-back.
if (srcEnd > destBegin && srcEnd < destEnd) {
RelocateRegionBackward(srcBegin, srcEnd, destEnd);
} else {
RelocateRegionForward(srcBegin, srcEnd, destBegin);
}
}
static void RelocateNonOverlappingRegion(void* aDest, void* aSrc,
size_t aCount, size_t aElemSize) {
ElemType* destBegin = static_cast<ElemType*>(aDest);
ElemType* srcBegin = static_cast<ElemType*>(aSrc);
ElemType* srcEnd = srcBegin + aCount;
#ifdef DEBUG
ElemType* destEnd = destBegin + aCount;
MOZ_ASSERT(srcEnd <= destBegin || srcBegin >= destEnd);
#endif
RelocateRegionForward(srcBegin, srcEnd, destBegin);
}
private:
static void RelocateRegionForward(ElemType* srcBegin, ElemType* srcEnd,
ElemType* destBegin) {
ElemType* srcElem = srcBegin;
ElemType* destElem = destBegin;
while (srcElem != srcEnd) {
RelocateElement(srcElem, destElem);
++destElem;
++srcElem;
}
}
static void RelocateRegionBackward(ElemType* srcBegin, ElemType* srcEnd,
ElemType* destEnd) {
ElemType* srcElem = srcEnd;
ElemType* destElem = destEnd;
while (srcElem != srcBegin) {
--destElem;
--srcElem;
RelocateElement(srcElem, destElem);
}
}
static void RelocateElement(ElemType* srcElem, ElemType* destElem) {
traits::Construct(destElem, std::move(*srcElem));
traits::Destruct(srcElem);
}
};
//
// The default behaviour is to use memcpy/memmove for everything.
//
template <class E>
struct MOZ_NEEDS_MEMMOVABLE_TYPE nsTArray_RelocationStrategy {
using Type = nsTArray_RelocateUsingMemutils;
};
//
// Some classes require constructors/destructors to be called, so they are
// specialized here.
//
#define MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(E) \
template <> \
struct nsTArray_RelocationStrategy<E> { \
using Type = nsTArray_RelocateUsingMoveConstructor<E>; \
};
#define MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(T) \
template <typename S> \
struct nsTArray_RelocationStrategy<T<S>> { \
using Type = nsTArray_RelocateUsingMoveConstructor<T<S>>; \
};
// TODO mozilla::ipc::AutoIPCStream is not even movable, so memmovable use with
// nsTArray (in StructuredCloneData) seems at least quirky
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(JS::Heap)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(std::function)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(mozilla::ipc::Endpoint)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(nsRegion)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(nsIntRegion)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::layers::TileClient)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
mozilla::SerializedStructuredCloneBuffer)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
mozilla::dom::ipc::StructuredCloneData)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::dom::ClonedMessageData)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
mozilla::dom::indexedDB::ObjectStoreCursorResponse)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
mozilla::dom::indexedDB::IndexCursorResponse)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
mozilla::dom::indexedDB::SerializedStructuredCloneReadInfo);
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(JSStructuredCloneData)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::dom::MessageData)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::dom::RefMessageData)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::SourceBufferTask)
//
// Base class for nsTArray_Impl that is templated on element type and derived
// nsTArray_Impl class, to allow extra conversions to be added for specific
// types.
//
template <class E, class Derived>
struct nsTArray_TypedBase : public nsTArray_SafeElementAtHelper<E, Derived> {};
//
// Specialization of nsTArray_TypedBase for arrays containing JS::Heap<E>
// elements.
//
// These conversions are safe because JS::Heap<E> and E share the same
// representation, and since the result of the conversions are const references
// we won't miss any barriers.
//
// The static_cast is necessary to obtain the correct address for the derived
// class since we are a base class used in multiple inheritance.
//
template <class E, class Derived>
struct nsTArray_TypedBase<JS::Heap<E>, Derived>
: public nsTArray_SafeElementAtHelper<JS::Heap<E>, Derived> {
operator const nsTArray<E>&() {
static_assert(sizeof(E) == sizeof(JS::Heap<E>),
"JS::Heap<E> must be binary compatible with E.");
Derived* self = static_cast<Derived*>(this);
return *reinterpret_cast<nsTArray<E>*>(self);
}
operator const FallibleTArray<E>&() {
Derived* self = static_cast<Derived*>(this);
return *reinterpret_cast<FallibleTArray<E>*>(self);
}
};
namespace detail {
// These helpers allow us to differentiate between tri-state comparator
// functions and classes with LessThan() and Equal() methods. If an object, when
// called as a function with two instances of our element type, returns an int,
// we treat it as a tri-state comparator.
//
// T is the type of the comparator object we want to check. U is the array
// element type that we'll be comparing.
//
// V is never passed, and is only used to allow us to specialize on the return
// value of the comparator function.
template <typename T, typename U, typename V = int>
struct IsCompareMethod : std::false_type {};
template <typename T, typename U>
struct IsCompareMethod<
T, U, decltype(std::declval<T>()(std::declval<U>(), std::declval<U>()))>
: std::true_type {};
// These two wrappers allow us to use either a tri-state comparator, or an
// object with Equals() and LessThan() methods interchangeably. They provide a
// tri-state Compare() method, and Equals() method, and a LessThan() method.
//
// Depending on the type of the underlying comparator, they either pass these
// through directly, or synthesize them from the methods available on the
// comparator.
//
// Callers should always use the most-specific of these methods that match their
// purpose.
// Comparator wrapper for a tri-state comparator function
template <typename T, typename U, bool IsCompare = IsCompareMethod<T, U>::value>
struct CompareWrapper {
#ifdef _MSC_VER
# pragma warning(push)
# pragma warning(disable : 4180) /* Silence "qualifier applied to function \
type has no meaning" warning */
#endif
MOZ_IMPLICIT CompareWrapper(const T& aComparator)
: mComparator(aComparator) {}
template <typename A, typename B>
int Compare(A& aLeft, B& aRight) const {
return mComparator(aLeft, aRight);
}
template <typename A, typename B>
bool Equals(A& aLeft, B& aRight) const {
return Compare(aLeft, aRight) == 0;
}
template <typename A, typename B>
bool LessThan(A& aLeft, B& aRight) const {
return Compare(aLeft, aRight) < 0;
}
const T& mComparator;
#ifdef _MSC_VER
# pragma warning(pop)
#endif
};
// Comparator wrapper for a class with Equals() and LessThan() methods.
template <typename T, typename U>
struct CompareWrapper<T, U, false> {
MOZ_IMPLICIT CompareWrapper(const T& aComparator)
: mComparator(aComparator) {}
template <typename A, typename B>
int Compare(A& aLeft, B& aRight) const {
if (Equals(aLeft, aRight)) {
return 0;
}
return LessThan(aLeft, aRight) ? -1 : 1;
}
template <typename A, typename B>
bool Equals(A& aLeft, B& aRight) const {
return mComparator.Equals(aLeft, aRight);
}
template <typename A, typename B>
bool LessThan(A& aLeft, B& aRight) const {
return mComparator.LessThan(aLeft, aRight);
}
const T& mComparator;
};
} // namespace detail
//
// nsTArray_Impl contains most of the guts supporting nsTArray, FallibleTArray,
// AutoTArray.
//
// The only situation in which you might need to use nsTArray_Impl in your code
// is if you're writing code which mutates a TArray which may or may not be
// infallible.
//
// Code which merely reads from a TArray which may or may not be infallible can
// simply cast the TArray to |const nsTArray&|; both fallible and infallible
// TArrays can be cast to |const nsTArray&|.
//
template <class E, class Alloc>
class nsTArray_Impl
: public nsTArray_base<Alloc,
typename nsTArray_RelocationStrategy<E>::Type>,
public nsTArray_TypedBase<E, nsTArray_Impl<E, Alloc>> {
private:
friend class nsTArray<E>;
typedef nsTArrayFallibleAllocator FallibleAlloc;
typedef nsTArrayInfallibleAllocator InfallibleAlloc;
public:
typedef typename nsTArray_RelocationStrategy<E>::Type relocation_type;
typedef nsTArray_base<Alloc, relocation_type> base_type;
typedef typename base_type::size_type size_type;
typedef typename base_type::index_type index_type;
typedef E elem_type;
typedef nsTArray_Impl<E, Alloc> self_type;
typedef nsTArrayElementTraits<E> elem_traits;
typedef nsTArray_SafeElementAtHelper<E, self_type> safeelementat_helper_type;
typedef mozilla::ArrayIterator<elem_type&, self_type> iterator;
typedef mozilla::ArrayIterator<const elem_type&, self_type> const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
using base_type::EmptyHdr;
using safeelementat_helper_type::SafeElementAt;
// A special value that is used to indicate an invalid or unknown index
// into the array.
static const index_type NoIndex = index_type(-1);
using base_type::Length;
//
// Finalization method
//
~nsTArray_Impl() {
if (!base_type::IsEmpty()) {
ClearAndRetainStorage();
}
// mHdr cleanup will be handled by base destructor
}
//
// Initialization methods
//
nsTArray_Impl() = default;
// Initialize this array and pre-allocate some number of elements.
explicit nsTArray_Impl(size_type aCapacity) { SetCapacity(aCapacity); }
// Initialize this array with an r-value.
// Allow different types of allocators, since the allocator doesn't matter.
template <typename Allocator>
explicit nsTArray_Impl(nsTArray_Impl<E, Allocator>&& aOther) noexcept {
// We cannot be a (Copyable)AutoTArray because that overrides this ctor.
MOZ_ASSERT(!this->IsAutoArray());
// This does not use SwapArrayElements because that's unnecessarily complex.
this->MoveConstructNonAutoArray(aOther, sizeof(elem_type),
MOZ_ALIGNOF(elem_type));
}
// The array's copy-constructor performs a 'deep' copy of the given array.
// @param aOther The array object to copy.
//
// It's very important that we declare this method as taking |const
// self_type&| as opposed to taking |const nsTArray_Impl<E, OtherAlloc>| for
// an arbitrary OtherAlloc.
//
// If we don't declare a constructor taking |const self_type&|, C++ generates
// a copy-constructor for this class which merely copies the object's
// members, which is obviously wrong.
//
// You can pass an nsTArray_Impl<E, OtherAlloc> to this method because
// nsTArray_Impl<E, X> can be cast to const nsTArray_Impl<E, Y>&. So the
// effect on the API is the same as if we'd declared this method as taking
// |const nsTArray_Impl<E, OtherAlloc>&|.
nsTArray_Impl(const nsTArray_Impl&) = default;
// Allow converting to a const array with a different kind of allocator,
// Since the allocator doesn't matter for const arrays
template <typename Allocator>
[[nodiscard]] operator const nsTArray_Impl<E, Allocator>&() const& {
return *reinterpret_cast<const nsTArray_Impl<E, Allocator>*>(this);
}
// And we have to do this for our subclasses too
[[nodiscard]] operator const nsTArray<E>&() const& {
return *reinterpret_cast<const nsTArray<E>*>(this);
}
[[nodiscard]] operator const FallibleTArray<E>&() const& {
return *reinterpret_cast<const FallibleTArray<E>*>(this);
}
// The array's assignment operator performs a 'deep' copy of the given
// array. It is optimized to reuse existing storage if possible.
// @param aOther The array object to copy.
nsTArray_Impl& operator=(const nsTArray_Impl&) = default;
// The array's move assignment operator steals the underlying data from
// the other array.
// @param other The array object to move from.
self_type& operator=(self_type&& aOther) {
if (this != &aOther) {
Clear();
this->MoveInit(aOther, sizeof(elem_type), MOZ_ALIGNOF(elem_type));
}
return *this;
}
// Return true if this array has the same length and the same
// elements as |aOther|.
template <typename Allocator>
[[nodiscard]] bool operator==(
const nsTArray_Impl<E, Allocator>& aOther) const {
size_type len = Length();
if (len != aOther.Length()) {
return false;
}
// XXX std::equal would be as fast or faster here
for (index_type i = 0; i < len; ++i) {
if (!(operator[](i) == aOther[i])) {
return false;
}
}
return true;
}
// Return true if this array does not have the same length and the same
// elements as |aOther|.
[[nodiscard]] bool operator!=(const self_type& aOther) const {
return !operator==(aOther);
}
// If Alloc == FallibleAlloc, ReplaceElementsAt might fail, without a way to
// signal this to the caller, so we disallow copying via operator=. Callers
// should use ReplaceElementsAt with a fallible argument instead, and check
// the result.
template <typename Allocator,
typename = std::enable_if_t<std::is_same_v<Alloc, InfallibleAlloc>,
Allocator>>
self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther) {
AssignInternal<InfallibleAlloc>(aOther.Elements(), aOther.Length());
return *this;
}
template <typename Allocator>
self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther) {
Clear();
this->MoveInit(aOther, sizeof(elem_type), MOZ_ALIGNOF(elem_type));
return *this;
}
// @return The amount of memory used by this nsTArray_Impl, excluding
// sizeof(*this). If you want to measure anything hanging off the array, you
// must iterate over the elements and measure them individually; hence the
// "Shallow" prefix.
[[nodiscard]] size_t ShallowSizeOfExcludingThis(
mozilla::MallocSizeOf aMallocSizeOf) const {
if (this->UsesAutoArrayBuffer() || this->HasEmptyHeader()) {
return 0;
}
return aMallocSizeOf(this->Hdr());
}
// @return The amount of memory used by this nsTArray_Impl, including
// sizeof(*this). If you want to measure anything hanging off the array, you
// must iterate over the elements and measure them individually; hence the
// "Shallow" prefix.
[[nodiscard]] size_t ShallowSizeOfIncludingThis(
mozilla::MallocSizeOf aMallocSizeOf) const {
return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
}
//
// Accessor methods
//
// This method provides direct access to the array elements.
// @return A pointer to the first element of the array. If the array is
// empty, then this pointer must not be dereferenced.
[[nodiscard]] elem_type* Elements() MOZ_NONNULL_RETURN {
return reinterpret_cast<elem_type*>(Hdr() + 1);
}
// This method provides direct, readonly access to the array elements.
// @return A pointer to the first element of the array. If the array is
// empty, then this pointer must not be dereferenced.
[[nodiscard]] const elem_type* Elements() const MOZ_NONNULL_RETURN {
return reinterpret_cast<const elem_type*>(Hdr() + 1);
}
// This method provides direct access to an element of the array. The given
// index must be within the array bounds.
// @param aIndex The index of an element in the array.
// @return A reference to the i'th element of the array.
[[nodiscard]] elem_type& ElementAt(index_type aIndex) {
if (MOZ_UNLIKELY(aIndex >= Length())) {
InvalidArrayIndex_CRASH(aIndex, Length());
}
return Elements()[aIndex];
}
// This method provides direct, readonly access to an element of the array
// The given index must be within the array bounds.
// @param aIndex The index of an element in the array.
// @return A const reference to the i'th element of the array.
[[nodiscard]] const elem_type& ElementAt(index_type aIndex) const {
if (MOZ_UNLIKELY(aIndex >= Length())) {
InvalidArrayIndex_CRASH(aIndex, Length());
}
return Elements()[aIndex];
}
// This method provides direct access to an element of the array in a bounds
// safe manner. If the requested index is out of bounds the provided default
// value is returned.
// @param aIndex The index of an element in the array.
// @param aDef The value to return if the index is out of bounds.
[[nodiscard]] elem_type& SafeElementAt(index_type aIndex, elem_type& aDef) {
return aIndex < Length() ? Elements()[aIndex] : aDef;
}
// This method provides direct access to an element of the array in a bounds
// safe manner. If the requested index is out of bounds the provided default
// value is returned.
// @param aIndex The index of an element in the array.
// @param aDef The value to return if the index is out of bounds.
[[nodiscard]] const elem_type& SafeElementAt(index_type aIndex,
const elem_type& aDef) const {
return aIndex < Length() ? Elements()[aIndex] : aDef;
}
// Shorthand for ElementAt(aIndex)
[[nodiscard]] elem_type& operator[](index_type aIndex) {
return ElementAt(aIndex);
}
// Shorthand for ElementAt(aIndex)
[[nodiscard]] const elem_type& operator[](index_type aIndex) const {
return ElementAt(aIndex);
}
// Shorthand for ElementAt(length - 1)
[[nodiscard]] elem_type& LastElement() { return ElementAt(Length() - 1); }
// Shorthand for ElementAt(length - 1)
[[nodiscard]] const elem_type& LastElement() const {
return ElementAt(Length() - 1);
}
// Shorthand for SafeElementAt(length - 1, def)
[[nodiscard]] elem_type& SafeLastElement(elem_type& aDef) {
return SafeElementAt(Length() - 1, aDef);
}
// Shorthand for SafeElementAt(length - 1, def)
[[nodiscard]] const elem_type& SafeLastElement(const elem_type& aDef) const {
return SafeElementAt(Length() - 1, aDef);
}
// Methods for range-based for loops.
[[nodiscard]] iterator begin() { return iterator(*this, 0); }
[[nodiscard]] const_iterator begin() const {
return const_iterator(*this, 0);
}
[[nodiscard]] const_iterator cbegin() const { return begin(); }
[[nodiscard]] iterator end() { return iterator(*this, Length()); }
[[nodiscard]] const_iterator end() const {
return const_iterator(*this, Length());
}
[[nodiscard]] const_iterator cend() const { return end(); }
// Methods for reverse iterating.
[[nodiscard]] reverse_iterator rbegin() { return reverse_iterator(end()); }
[[nodiscard]] const_reverse_iterator rbegin() const {
return const_reverse_iterator(end());
}
[[nodiscard]] const_reverse_iterator crbegin() const { return rbegin(); }
[[nodiscard]] reverse_iterator rend() { return reverse_iterator(begin()); }
[[nodiscard]] const_reverse_iterator rend() const {
return const_reverse_iterator(begin());
}
[[nodiscard]] const_reverse_iterator crend() const { return rend(); }
// Span integration
[[nodiscard]] operator mozilla::Span<elem_type>() {
return mozilla::Span<elem_type>(Elements(), Length());
}
[[nodiscard]] operator mozilla::Span<const elem_type>() const {
return mozilla::Span<const elem_type>(Elements(), Length());
}
//
// Search methods
//
// This method searches for the first element in this array that is equal
// to the given element.
// @param aItem The item to search for.
// @param aComp The Comparator used to determine element equality.
// @return true if the element was found.
template <class Item, class Comparator>
[[nodiscard]] bool Contains(const Item& aItem,
const Comparator& aComp) const {
return ApplyIf(
aItem, 0, aComp, []() { return true; }, []() { return false; });
}
// Like Contains(), but assumes a sorted array.
template <class Item, class Comparator>
[[nodiscard]] bool ContainsSorted(const Item& aItem,
const Comparator& aComp) const {
return BinaryIndexOf(aItem, aComp) != NoIndex;
}
// This method searches for the first element in this array that is equal
// to the given element. This method assumes that 'operator==' is defined
// for elem_type.
// @param aItem The item to search for.
// @return true if the element was found.
template <class Item>
[[nodiscard]] bool Contains(const Item& aItem) const {
return Contains(aItem, nsDefaultComparator<elem_type, Item>());
}
// Like Contains(), but assumes a sorted array.
template <class Item>
[[nodiscard]] bool ContainsSorted(const Item& aItem) const {
return BinaryIndexOf(aItem) != NoIndex;
}
// This method searches for the offset of the first element in this
// array that is equal to the given element.
// @param aItem The item to search for.
// @param aStart The index to start from.
// @param aComp The Comparator used to determine element equality.
// @return The index of the found element or NoIndex if not found.
template <class Item, class Comparator>
[[nodiscard]] index_type IndexOf(const Item& aItem, index_type aStart,
const Comparator& aComp) const {
::detail::CompareWrapper<Comparator, Item> comp(aComp);
const elem_type* iter = Elements() + aStart;
const elem_type* iend = Elements() + Length();
for (; iter != iend; ++iter) {
if (comp.Equals(*iter, aItem)) {
return index_type(iter - Elements());
}
}
return NoIndex;
}
// This method searches for the offset of the first element in this
// array that is equal to the given element. This method assumes
// that 'operator==' is defined for elem_type.
// @param aItem The item to search for.
// @param aStart The index to start from.
// @return The index of the found element or NoIndex if not found.
template <class Item>
[[nodiscard]] index_type IndexOf(const Item& aItem,
index_type aStart = 0) const {
return IndexOf(aItem, aStart, nsDefaultComparator<elem_type, Item>());
}
// This method searches for the offset of the last element in this
// array that is equal to the given element.
// @param aItem The item to search for.
// @param aStart The index to start from. If greater than or equal to the
// length of the array, then the entire array is searched.
// @param aComp The Comparator used to determine element equality.
// @return The index of the found element or NoIndex if not found.
template <class Item, class Comparator>
[[nodiscard]] index_type LastIndexOf(const Item& aItem, index_type aStart,
const Comparator& aComp) const {
::detail::CompareWrapper<Comparator, Item> comp(aComp);
size_type endOffset = aStart >= Length() ? Length() : aStart + 1;
const elem_type* iend = Elements() - 1;
const elem_type* iter = iend + endOffset;
for (; iter != iend; --iter) {
if (comp.Equals(*iter, aItem)) {
return index_type(iter - Elements());
}
}
return NoIndex;
}
// This method searches for the offset of the last element in this
// array that is equal to the given element. This method assumes
// that 'operator==' is defined for elem_type.
// @param aItem The item to search for.
// @param aStart The index to start from. If greater than or equal to the
// length of the array, then the entire array is searched.
// @return The index of the found element or NoIndex if not found.
template <class Item>
[[nodiscard]] index_type LastIndexOf(const Item& aItem,
index_type aStart = NoIndex) const {
return LastIndexOf(aItem, aStart, nsDefaultComparator<elem_type, Item>());
}
// This method searches for the offset for the element in this array
// that is equal to the given element. The array is assumed to be sorted.
// If there is more than one equivalent element, there is no guarantee
// on which one will be returned.
// @param aItem The item to search for.
// @param aComp The Comparator used.
// @return The index of the found element or NoIndex if not found.
template <class Item, class Comparator>
[[nodiscard]] index_type BinaryIndexOf(const Item& aItem,
const Comparator& aComp) const {
using mozilla::BinarySearchIf;
::detail::CompareWrapper<Comparator, Item> comp(aComp);
size_t index;
bool found = BinarySearchIf(
Elements(), 0, Length(),
// Note: We pass the Compare() args here in reverse order and negate the
// results for compatibility reasons. Some existing callers use Equals()
// functions with first arguments which match aElement but not aItem, or
// second arguments that match aItem but not aElement. To accommodate
// those callers, we preserve the argument order of the older version of
// this API. These callers, however, should be fixed, and this special
// case removed.
[&](const elem_type& aElement) {
return -comp.Compare(aElement, aItem);
},
&index);
return found ? index : NoIndex;
}
// This method searches for the offset for the element in this array
// that is equal to the given element. The array is assumed to be sorted.
// This method assumes that 'operator==' and 'operator<' are defined.
// @param aItem The item to search for.
// @return The index of the found element or NoIndex if not found.
template <class Item>
[[nodiscard]] index_type BinaryIndexOf(const Item& aItem) const {
return BinaryIndexOf(aItem, nsDefaultComparator<elem_type, Item>());
}
//
// Mutation methods
//
private:
template <typename ActualAlloc, class Item>
typename ActualAlloc::ResultType AssignInternal(const Item* aArray,
size_type aArrayLen);
public:
template <class Allocator, typename ActualAlloc = Alloc>
[[nodiscard]] typename ActualAlloc::ResultType Assign(
const nsTArray_Impl<E, Allocator>& aOther) {
return AssignInternal<ActualAlloc>(aOther.Elements(), aOther.Length());
}
template <class Allocator>
[[nodiscard]] bool Assign(const nsTArray_Impl<E, Allocator>& aOther,
const mozilla::fallible_t&) {
return Assign<Allocator, FallibleAlloc>(aOther);
}
template <class Allocator>
void Assign(nsTArray_Impl<E, Allocator>&& aOther) {
Clear();
this->MoveInit(aOther, sizeof(elem_type), MOZ_ALIGNOF(elem_type));
}
// This method call the destructor on each element of the array, empties it,
// but does not shrink the array's capacity.
// See also SetLengthAndRetainStorage.
// Make sure to call Compact() if needed to avoid keeping a huge array
// around.
void ClearAndRetainStorage() {
if (this->HasEmptyHeader()) {
return;
}
DestructRange(0, Length());
base_type::mHdr->mLength = 0;
}
// This method modifies the length of the array, but unlike SetLength
// it doesn't deallocate/reallocate the current internal storage.
// The new length MUST be shorter than or equal to the current capacity.
// If the new length is larger than the existing length of the array,
// then new elements will be constructed using elem_type's default
// constructor. If shorter, elements will be destructed and removed.
// See also ClearAndRetainStorage.
// @param aNewLen The desired length of this array.
void SetLengthAndRetainStorage(size_type aNewLen) {
MOZ_ASSERT(aNewLen <= base_type::Capacity());
size_type oldLen = Length();
if (aNewLen > oldLen) {
/// XXX(Bug 1631367) SetLengthAndRetainStorage should be disabled for
/// FallibleTArray.
InsertElementsAtInternal<InfallibleAlloc>(oldLen, aNewLen - oldLen);
return;
}
if (aNewLen < oldLen) {
DestructRange(aNewLen, oldLen - aNewLen);
base_type::mHdr->mLength = aNewLen;
}
}
// This method replaces a range of elements in this array.
// @param aStart The starting index of the elements to replace.
// @param aCount The number of elements to replace. This may be zero to
// insert elements without removing any existing elements.
// @param aArray The values to copy into this array. Must be non-null,
// and these elements must not already exist in the array
// being modified.
// @param aArrayLen The number of values to copy into this array.
// @return A pointer to the new elements in the array, or null if
// the operation failed due to insufficient memory.
private:
template <typename ActualAlloc, class Item>
elem_type* ReplaceElementsAtInternal(index_type aStart, size_type aCount,
const Item* aArray, size_type aArrayLen);
public:
template <class Item>
[[nodiscard]] elem_type* ReplaceElementsAt(index_type aStart,
size_type aCount,
const Item* aArray,
size_type aArrayLen,
const mozilla::fallible_t&) {
return ReplaceElementsAtInternal<FallibleAlloc>(aStart, aCount, aArray,
aArrayLen);
}
// A variation on the ReplaceElementsAt method defined above.
template <class Item>
[[nodiscard]] elem_type* ReplaceElementsAt(index_type aStart,
size_type aCount,
const nsTArray<Item>& aArray,
const mozilla::fallible_t&) {
return ReplaceElementsAtInternal<FallibleAlloc>(aStart, aCount, aArray);
}
template <class Item>
[[nodiscard]] elem_type* ReplaceElementsAt(index_type aStart,
size_type aCount,
mozilla::Span<Item> aSpan,
const mozilla::fallible_t&) {
return ReplaceElementsAtInternal<FallibleAlloc>(aStart, aCount, aSpan);
}
// A variation on the ReplaceElementsAt method defined above.
template <class Item>
[[nodiscard]] elem_type* ReplaceElementsAt(index_type aStart,
size_type aCount,
const Item& aItem,
const mozilla::fallible_t&) {
return ReplaceElementsAtInternal<FallibleAlloc>(aStart, aCount, aItem);
}
// A variation on the ReplaceElementsAt method defined above.
template <class Item>
mozilla::NotNull<elem_type*> ReplaceElementAt(index_type aIndex,
Item&& aItem) {
elem_type* const elem = &ElementAt(aIndex);
elem_traits::Destruct(elem);
elem_traits::Construct(elem, std::forward<Item>(aItem));
return mozilla::WrapNotNullUnchecked(elem);
}
// InsertElementsAt is ReplaceElementsAt with 0 elements to replace.
// XXX Provide a proper documentation of InsertElementsAt.
template <class Item>
[[nodiscard]] elem_type* InsertElementsAt(index_type aIndex,
const Item* aArray,
size_type aArrayLen,
const mozilla::fallible_t&) {
return ReplaceElementsAtInternal<FallibleAlloc>(aIndex, 0, aArray,
aArrayLen);
}
template <class Item, class Allocator>
[[nodiscard]] elem_type* InsertElementsAt(
index_type aIndex, const nsTArray_Impl<Item, Allocator>& aArray,
const mozilla::fallible_t&) {
return ReplaceElementsAtInternal<FallibleAlloc>(