summaryrefslogtreecommitdiffstats
path: root/xpcom/glue/nsTArray.h
diff options
context:
space:
mode:
Diffstat (limited to 'xpcom/glue/nsTArray.h')
-rw-r--r--xpcom/glue/nsTArray.h2371
1 files changed, 2371 insertions, 0 deletions
diff --git a/xpcom/glue/nsTArray.h b/xpcom/glue/nsTArray.h
new file mode 100644
index 000000000..ca74a41f7
--- /dev/null
+++ b/xpcom/glue/nsTArray.h
@@ -0,0 +1,2371 @@
+/* -*- 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 "nsTArrayForwardDeclare.h"
+#include "mozilla/Alignment.h"
+#include "mozilla/Assertions.h"
+#include "mozilla/Attributes.h"
+#include "mozilla/BinarySearch.h"
+#include "mozilla/fallible.h"
+#include "mozilla/Function.h"
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/MemoryReporting.h"
+#include "mozilla/Move.h"
+#include "mozilla/ReverseIterator.h"
+#include "mozilla/TypeTraits.h"
+
+#include <string.h>
+
+#include "nsCycleCollectionNoteChild.h"
+#include "nsAlgorithm.h"
+#include "nscore.h"
+#include "nsQuickSort.h"
+#include "nsDebug.h"
+#include "nsISupportsImpl.h"
+#include "nsRegionFwd.h"
+#include <initializer_list>
+#include <new>
+
+namespace JS {
+template<class T>
+class Heap;
+class ObjectPtr;
+} /* namespace JS */
+
+class nsRegion;
+namespace mozilla {
+namespace layers {
+struct TileClient;
+} // namespace layers
+} // namespace mozilla
+
+namespace mozilla {
+struct SerializedStructuredCloneBuffer;
+} // namespace mozilla
+
+namespace mozilla {
+namespace dom {
+namespace ipc {
+class StructuredCloneData;
+} // namespace ipc
+} // namespace dom
+} // namespace mozilla
+
+namespace mozilla {
+namespace dom {
+class ClonedMessageData;
+class MessagePortMessage;
+namespace indexedDB {
+struct StructuredCloneReadInfo;
+class SerializedStructuredCloneReadInfo;
+class ObjectStoreCursorResponse;
+} // namespace indexedDB
+} // namespace dom
+} // namespace mozilla
+
+class JSStructuredCloneData;
+
+//
+// nsTArray is a resizable array class, like std::vector.
+//
+// Unlike std::vector, which follows C++'s construction/destruction rules,
+// nsTArray assumes that your "T" can be memmoved()'ed safely.
+//
+// The public classes defined in this header are
+//
+// nsTArray<T>,
+// FallibleTArray<T>,
+// AutoTArray<T, N>, and
+//
+// nsTArray and AutoTArray are infallible by default. To opt-in to fallible
+// behaviour, use the `mozilla::fallible` parameter and check the return value.
+//
+// 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 (i.e., T in nsTArray<T>) specifies the type of the
+// elements and has the following requirements:
+//
+// T MUST be safely memmove()'able.
+// T MUST define a copy-constructor.
+// T MAY define operator< for sorting.
+// T MAY define operator== for searching.
+//
+// (Note that the memmove requirement may be relaxed for certain types - see
+// nsTArray_CopyChooser below.)
+//
+// For methods taking a Comparator instance, the Comparator must be a class
+// defining the following methods:
+//
+// class Comparator {
+// public:
+// /** @return True if the elements are equals; false otherwise. */
+// bool Equals(const elem_type& a, const Item& b) const;
+//
+// /** @return True if (a < b); false otherwise. */
+// bool LessThan(const elem_type& a, const Item& b) const;
+// };
+//
+// The Equals method is used for searching, and the LessThan method is used for
+// searching and sorting. The |Item| type above can be arbitrary, but must
+// match the Item type passed to the sort or search function.
+//
+
+
+//
+// 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 nsTArrayFallibleResult(bool aResult) : mResult(aResult) {}
+
+ MOZ_IMPLICIT 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 ResultType Result(ResultTypeProxy aResult) { return aResult; }
+ static bool Successful(ResultTypeProxy aResult) { return aResult; }
+ static ResultTypeProxy SuccessResult() { return true; }
+ static ResultTypeProxy FailureResult() { return false; }
+ static ResultType ConvertBoolToResultType(bool aValue) { return aValue; }
+};
+
+struct nsTArrayInfallibleAllocatorBase
+{
+ typedef void ResultType;
+ typedef nsTArrayInfallibleResult ResultTypeProxy;
+
+ static ResultType Result(ResultTypeProxy aResult) {}
+ static bool Successful(ResultTypeProxy) { return true; }
+ static ResultTypeProxy SuccessResult() { return ResultTypeProxy(); }
+
+ static ResultTypeProxy FailureResult()
+ {
+ NS_RUNTIMEABORT("Infallible nsTArray should never fail");
+ return ResultTypeProxy();
+ }
+
+ static ResultType ConvertBoolToResultType(bool aValue)
+ {
+ if (!aValue) {
+ NS_RUNTIMEABORT("infallible nsTArray should never convert false to ResultType");
+ }
+ }
+};
+
+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) {}
+};
+
+#if defined(MOZALLOC_HAVE_XMALLOC)
+#include "mozilla/mozalloc_abort.h"
+
+struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase
+{
+ static void* Malloc(size_t aSize) { return moz_xmalloc(aSize); }
+ static void* Realloc(void* aPtr, size_t aSize)
+ {
+ return moz_xrealloc(aPtr, aSize);
+ }
+
+ static void Free(void* aPtr) { free(aPtr); }
+ static void SizeTooBig(size_t aSize) { NS_ABORT_OOM(aSize); }
+};
+
+#else
+#include <stdlib.h>
+
+struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase
+{
+ static void* Malloc(size_t aSize)
+ {
+ void* ptr = malloc(aSize);
+ if (MOZ_UNLIKELY(!ptr)) {
+ NS_ABORT_OOM(aSize);
+ }
+ return ptr;
+ }
+
+ static void* Realloc(void* aPtr, size_t aSize)
+ {
+ void* newptr = realloc(aPtr, aSize);
+ if (MOZ_UNLIKELY(!newptr && aSize)) {
+ NS_ABORT_OOM(aSize);
+ }
+ return newptr;
+ }
+
+ static void Free(void* aPtr) { free(aPtr); }
+ static void SizeTooBig(size_t aSize) { NS_ABORT_OOM(aSize); }
+};
+
+#endif
+
+// 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
+{
+ static nsTArrayHeader sEmptyHdr;
+
+ uint32_t mLength;
+ uint32_t mCapacity : 31;
+ uint32_t mIsAutoArray : 1;
+};
+
+// This class provides a SafeElementAt method to nsTArray<T*> which does
+// not take a second default value parameter.
+template<class E, class Derived>
+struct nsTArray_SafeElementAtHelper
+{
+ 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>
+{
+ 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 the base type that the smart pointer is templated over; the
+// smart pointer can act as E*.
+template<class E, class Derived>
+struct nsTArray_SafeElementAtSmartPtrHelper
+{
+ typedef E* elem_type;
+ typedef const E* const_elem_type;
+ 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.
+ elem_type SafeElementAt(index_type aIndex) const
+ {
+ return static_cast<const Derived*>(this)->SafeElementAt(aIndex, nullptr);
+ }
+};
+
+template<class T> class nsCOMPtr;
+
+template<class E, class Derived>
+struct nsTArray_SafeElementAtHelper<nsCOMPtr<E>, Derived>
+ : public nsTArray_SafeElementAtSmartPtrHelper<E, Derived>
+{
+};
+
+template<class E, class Derived>
+struct nsTArray_SafeElementAtHelper<RefPtr<E>, Derived>
+ : public nsTArray_SafeElementAtSmartPtrHelper<E, Derived>
+{
+};
+
+namespace mozilla {
+template<class T> class OwningNonNull;
+} // namespace mozilla
+
+template<class E, class Derived>
+struct nsTArray_SafeElementAtHelper<mozilla::OwningNonNull<E>, Derived>
+{
+ typedef E* elem_type;
+ typedef const E* const_elem_type;
+ typedef size_t index_type;
+
+ elem_type SafeElementAt(index_type aIndex)
+ {
+ if (aIndex < static_cast<Derived*>(this)->Length()) {
+ return static_cast<Derived*>(this)->ElementAt(aIndex);
+ }
+ return nullptr;
+ }
+
+ // XXX: Probably should return const_elem_type, but callsites must be fixed.
+ elem_type SafeElementAt(index_type aIndex) const
+ {
+ if (aIndex < static_cast<const Derived*>(this)->Length()) {
+ return static_cast<const Derived*>(this)->ElementAt(aIndex);
+ }
+ return nullptr;
+ }
+};
+
+// 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 Copy>
+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 Allocator, class Copier>
+ friend class nsTArray_base;
+ 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();
+
+ // 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);
+
+ // 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);
+
+ // 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 increments the length member of the array's header.
+ // Note that mHdr may actually be sEmptyHdr 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 (mHdr == EmptyHdr()) {
+ 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>
+ bool 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, Copy>& aOther,
+ size_type aElemSize,
+ size_t aElemAlign);
+
+ // This is an RAII class used in SwapArrayElements.
+ class IsAutoArrayRestorer
+ {
+ public:
+ IsAutoArrayRestorer(nsTArray_base<Alloc, Copy>& aArray, size_t aElemAlign);
+ ~IsAutoArrayRestorer();
+
+ private:
+ nsTArray_base<Alloc, Copy>& 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, Copy>*>(
+ 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 sEmptyHdr.
+ Header* mHdr;
+
+ Header* Hdr() const { return mHdr; }
+ Header** PtrToHdr() { return &mHdr; }
+ static Header* EmptyHdr() { return &Header::sEmptyHdr; }
+};
+
+//
+// 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)
+ {
+ typedef typename mozilla::RemoveCV<E>::Type E_NoCV;
+ typedef typename mozilla::RemoveCV<A>::Type A_NoCV;
+ static_assert(!mozilla::IsSame<E_NoCV*, A_NoCV>::value,
+ "For safety, we disallow constructing nsTArray<E> elements "
+ "from E* pointers. See bug 960591.");
+ new (static_cast<void*>(aE)) E(mozilla::Forward<A>(aArg));
+ }
+ // 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 IsPod, 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)
+ {
+ 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_CopyChooser 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_CopyWithMemutils
+{
+ const static bool allowRealloc = true;
+
+ static void MoveNonOverlappingRegionWithHeader(void* aDest, const void* aSrc,
+ size_t aCount, size_t aElemSize)
+ {
+ memcpy(aDest, aSrc, sizeof(nsTArrayHeader) + aCount * aElemSize);
+ }
+
+ static void MoveOverlappingRegion(void* aDest, void* aSrc, size_t aCount,
+ size_t aElemSize)
+ {
+ memmove(aDest, aSrc, aCount * aElemSize);
+ }
+
+ static void MoveNonOverlappingRegion(void* aDest, void* aSrc, size_t aCount,
+ size_t aElemSize)
+ {
+ memcpy(aDest, aSrc, aCount * aElemSize);
+ }
+};
+
+//
+// A template class that defines how to copy elements calling their constructors
+// and destructors appropriately.
+//
+template<class ElemType>
+struct nsTArray_CopyWithConstructors
+{
+ typedef nsTArrayElementTraits<ElemType> traits;
+
+ const static bool allowRealloc = false;
+
+ static void MoveNonOverlappingRegionWithHeader(void* aDest, void* aSrc, size_t aCount,
+ size_t aElemSize)
+ {
+ nsTArrayHeader* destHeader = static_cast<nsTArrayHeader*>(aDest);
+ nsTArrayHeader* srcHeader = static_cast<nsTArrayHeader*>(aSrc);
+ *destHeader = *srcHeader;
+ MoveNonOverlappingRegion(static_cast<uint8_t*>(aDest) + sizeof(nsTArrayHeader),
+ static_cast<uint8_t*>(aSrc) + sizeof(nsTArrayHeader),
+ aCount, aElemSize);
+ }
+
+ // These functions are defined by analogy with memmove and memcpy.
+ // What they actually do is slightly different: MoveOverlappingRegion
+ // 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. MoveNonOverlappingRegion assumes that moving
+ // front-to-back is always valid. So they're really more like
+ // std::move{_backward,} in that respect. We keep these names because
+ // we think they read slightly better, and MoveNonOverlappingRegion is
+ // only ever called on overlapping regions from MoveOverlappingRegion.
+ static void MoveOverlappingRegion(void* aDest, void* aSrc, size_t aCount,
+ size_t aElemSize)
+ {
+ ElemType* destElem = static_cast<ElemType*>(aDest);
+ ElemType* srcElem = static_cast<ElemType*>(aSrc);
+ ElemType* destElemEnd = destElem + aCount;
+ ElemType* srcElemEnd = srcElem + aCount;
+ if (destElem == srcElem) {
+ return; // In practice, we don't do this.
+ }
+
+ // Figure out whether to copy back-to-front or front-to-back.
+ if (srcElemEnd > destElem && srcElemEnd < destElemEnd) {
+ while (destElemEnd != destElem) {
+ --destElemEnd;
+ --srcElemEnd;
+ traits::Construct(destElemEnd, mozilla::Move(*srcElemEnd));
+ traits::Destruct(srcElemEnd);
+ }
+ } else {
+ MoveNonOverlappingRegion(aDest, aSrc, aCount, aElemSize);
+ }
+ }
+
+ static void MoveNonOverlappingRegion(void* aDest, void* aSrc, size_t aCount,
+ size_t aElemSize)
+ {
+ ElemType* destElem = static_cast<ElemType*>(aDest);
+ ElemType* srcElem = static_cast<ElemType*>(aSrc);
+ ElemType* destElemEnd = destElem + aCount;
+#ifdef DEBUG
+ ElemType* srcElemEnd = srcElem + aCount;
+ MOZ_ASSERT(srcElemEnd <= destElem || srcElemEnd > destElemEnd);
+#endif
+ while (destElem != destElemEnd) {
+ traits::Construct(destElem, mozilla::Move(*srcElem));
+ traits::Destruct(srcElem);
+ ++destElem;
+ ++srcElem;
+ }
+ }
+};
+
+//
+// The default behaviour is to use memcpy/memmove for everything.
+//
+template<class E>
+struct MOZ_NEEDS_MEMMOVABLE_TYPE nsTArray_CopyChooser
+{
+ using Type = nsTArray_CopyWithMemutils;
+};
+
+//
+// Some classes require constructors/destructors to be called, so they are
+// specialized here.
+//
+#define DECLARE_USE_COPY_CONSTRUCTORS(T) \
+ template<> \
+ struct nsTArray_CopyChooser<T> \
+ { \
+ using Type = nsTArray_CopyWithConstructors<T>; \
+ };
+
+#define DECLARE_USE_COPY_CONSTRUCTORS_FOR_TEMPLATE(T) \
+ template<typename S> \
+ struct nsTArray_CopyChooser<T<S>> \
+ { \
+ using Type = nsTArray_CopyWithConstructors<T<S>>; \
+ };
+
+DECLARE_USE_COPY_CONSTRUCTORS_FOR_TEMPLATE(JS::Heap)
+
+DECLARE_USE_COPY_CONSTRUCTORS(nsRegion)
+DECLARE_USE_COPY_CONSTRUCTORS(nsIntRegion)
+DECLARE_USE_COPY_CONSTRUCTORS(mozilla::layers::TileClient)
+DECLARE_USE_COPY_CONSTRUCTORS(mozilla::SerializedStructuredCloneBuffer)
+DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::ipc::StructuredCloneData)
+DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::ClonedMessageData)
+DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::indexedDB::StructuredCloneReadInfo);
+DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::indexedDB::ObjectStoreCursorResponse)
+DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::indexedDB::SerializedStructuredCloneReadInfo);
+DECLARE_USE_COPY_CONSTRUCTORS(JSStructuredCloneData)
+DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::MessagePortMessage)
+DECLARE_USE_COPY_CONSTRUCTORS(JS::ObjectPtr)
+
+
+//
+// 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 {
+
+template<class Item, class Comparator>
+struct ItemComparatorEq
+{
+ const Item& mItem;
+ const Comparator& mComp;
+ ItemComparatorEq(const Item& aItem, const Comparator& aComp)
+ : mItem(aItem)
+ , mComp(aComp)
+ {}
+ template<class T>
+ int operator()(const T& aElement) const {
+ if (mComp.Equals(aElement, mItem)) {
+ return 0;
+ }
+
+ return mComp.LessThan(aElement, mItem) ? 1 : -1;
+ }
+};
+
+template<class Item, class Comparator>
+struct ItemComparatorFirstElementGT
+{
+ const Item& mItem;
+ const Comparator& mComp;
+ ItemComparatorFirstElementGT(const Item& aItem, const Comparator& aComp)
+ : mItem(aItem)
+ , mComp(aComp)
+ {}
+ template<class T>
+ int operator()(const T& aElement) const {
+ if (mComp.LessThan(aElement, mItem) ||
+ mComp.Equals(aElement, mItem)) {
+ return 1;
+ } else {
+ return -1;
+ }
+ }
+};
+
+} // 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_CopyChooser<E>::Type>
+ , public nsTArray_TypedBase<E, nsTArray_Impl<E, Alloc>>
+{
+private:
+ typedef nsTArrayFallibleAllocator FallibleAlloc;
+ typedef nsTArrayInfallibleAllocator InfallibleAlloc;
+
+public:
+ typedef typename nsTArray_CopyChooser<E>::Type copy_type;
+ typedef nsTArray_base<Alloc, copy_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 elem_type* iterator;
+ typedef const elem_type* const_iterator;
+ typedef mozilla::ReverseIterator<elem_type*> reverse_iterator;
+ typedef mozilla::ReverseIterator<const elem_type*> const_reverse_iterator;
+
+ using safeelementat_helper_type::SafeElementAt;
+ using base_type::EmptyHdr;
+
+ // 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() { Clear(); }
+
+ //
+ // Initialization methods
+ //
+
+ nsTArray_Impl() {}
+
+ // 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)
+ {
+ SwapElements(aOther);
+ }
+
+ // 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>&|.
+ explicit nsTArray_Impl(const self_type& aOther) { AppendElements(aOther); }
+
+ explicit nsTArray_Impl(std::initializer_list<E> aIL) { AppendElements(aIL.begin(), aIL.size()); }
+ // Allow converting to a const array with a different kind of allocator,
+ // Since the allocator doesn't matter for const arrays
+ template<typename Allocator>
+ 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
+ operator const nsTArray<E>&() const
+ {
+ return *reinterpret_cast<const InfallibleTArray<E>*>(this);
+ }
+ 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.
+ self_type& operator=(const self_type& aOther)
+ {
+ if (this != &aOther) {
+ ReplaceElementsAt(0, Length(), aOther.Elements(), aOther.Length());
+ }
+ return *this;
+ }
+
+ // 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();
+ SwapElements(aOther);
+ }
+ return *this;
+ }
+
+ // Return true if this array has the same length and the same
+ // elements as |aOther|.
+ template<typename Allocator>
+ 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|.
+ bool operator!=(const self_type& aOther) const { return !operator==(aOther); }
+
+ template<typename Allocator>
+ self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther)
+ {
+ ReplaceElementsAt(0, Length(), aOther.Elements(), aOther.Length());
+ return *this;
+ }
+
+ template<typename Allocator>
+ self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther)
+ {
+ Clear();
+ SwapElements(aOther);
+ 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.
+ size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
+ {
+ if (this->UsesAutoArrayBuffer() || Hdr() == EmptyHdr()) {
+ 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.
+ 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.
+ elem_type* Elements() { 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.
+ const elem_type* Elements() const
+ {
+ 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.
+ 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.
+ 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.
+ 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.
+ const elem_type& SafeElementAt(index_type aIndex, const elem_type& aDef) const
+ {
+ return aIndex < Length() ? Elements()[aIndex] : aDef;
+ }
+
+ // Shorthand for ElementAt(aIndex)
+ elem_type& operator[](index_type aIndex) { return ElementAt(aIndex); }
+
+ // Shorthand for ElementAt(aIndex)
+ const elem_type& operator[](index_type aIndex) const { return ElementAt(aIndex); }
+
+ // Shorthand for ElementAt(length - 1)
+ elem_type& LastElement() { return ElementAt(Length() - 1); }
+
+ // Shorthand for ElementAt(length - 1)
+ const elem_type& LastElement() const { return ElementAt(Length() - 1); }
+
+ // Shorthand for SafeElementAt(length - 1, def)
+ elem_type& SafeLastElement(elem_type& aDef)
+ {
+ return SafeElementAt(Length() - 1, aDef);
+ }
+
+ // Shorthand for SafeElementAt(length - 1, def)
+ const elem_type& SafeLastElement(const elem_type& aDef) const
+ {
+ return SafeElementAt(Length() - 1, aDef);
+ }
+
+ // Methods for range-based for loops.
+ iterator begin() { return Elements(); }
+ const_iterator begin() const { return Elements(); }
+ const_iterator cbegin() const { return begin(); }
+ iterator end() { return Elements() + Length(); }
+ const_iterator end() const { return Elements() + Length(); }
+ const_iterator cend() const { return end(); }
+
+ // Methods for reverse iterating.
+ reverse_iterator rbegin() { return reverse_iterator(end()); }
+ const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
+ const_reverse_iterator crbegin() const { return rbegin(); }
+ reverse_iterator rend() { return reverse_iterator(begin()); }
+ const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
+ const_reverse_iterator crend() const { return rend(); }
+
+ //
+ // 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>
+ bool Contains(const Item& aItem, const Comparator& aComp) const
+ {
+ return IndexOf(aItem, 0, 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>
+ bool Contains(const Item& aItem) const
+ {
+ return IndexOf(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>
+ index_type IndexOf(const Item& aItem, index_type aStart,
+ const Comparator& aComp) const
+ {
+ const elem_type* iter = Elements() + aStart;
+ const elem_type* iend = Elements() + Length();
+ for (; iter != iend; ++iter) {
+ if (aComp.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>
+ 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>
+ index_type LastIndexOf(const Item& aItem, index_type aStart,
+ const Comparator& aComp) const
+ {
+ 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 (aComp.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>
+ 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>
+ index_type BinaryIndexOf(const Item& aItem, const Comparator& aComp) const
+ {
+ using mozilla::BinarySearchIf;
+ typedef ::detail::ItemComparatorEq<Item, Comparator> Cmp;
+
+ size_t index;
+ bool found = BinarySearchIf(*this, 0, Length(), Cmp(aItem, aComp), &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>
+ index_type BinaryIndexOf(const Item& aItem) const
+ {
+ return BinaryIndexOf(aItem, nsDefaultComparator<elem_type, Item>());
+ }
+
+ //
+ // Mutation methods
+ //
+
+ template<class Allocator, typename ActualAlloc = Alloc>
+ typename ActualAlloc::ResultType Assign(
+ const nsTArray_Impl<E, Allocator>& aOther)
+ {
+ return ActualAlloc::ConvertBoolToResultType(
+ !!ReplaceElementsAt<E, ActualAlloc>(0, Length(),
+ aOther.Elements(), aOther.Length()));
+ }
+
+ template<class Allocator>
+ MOZ_MUST_USE
+ 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();
+ SwapElements(aOther);
+ }
+
+ // 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 (base_type::mHdr == EmptyHdr()) {
+ 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) {
+ InsertElementsAt(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.
+protected:
+ template<class Item, typename ActualAlloc = Alloc>
+ elem_type* ReplaceElementsAt(index_type aStart, size_type aCount,
+ const Item* aArray, size_type aArrayLen);
+
+public:
+
+ template<class Item>
+ MOZ_MUST_USE
+ elem_type* ReplaceElementsAt(index_type aStart, size_type aCount,
+ const Item* aArray, size_type aArrayLen,
+ const mozilla::fallible_t&)
+ {
+ return ReplaceElementsAt<Item, FallibleAlloc>(aStart, aCount,
+ aArray, aArrayLen);
+ }
+
+ // A variation on the ReplaceElementsAt method defined above.
+protected:
+ template<class Item, typename ActualAlloc = Alloc>
+ elem_type* ReplaceElementsAt(index_type aStart, size_type aCount,
+ const nsTArray<Item>& aArray)
+ {
+ return ReplaceElementsAt<Item, ActualAlloc>(
+ aStart, aCount, aArray.Elements(), aArray.Length());
+ }
+public:
+
+ template<class Item>
+ MOZ_MUST_USE
+ elem_type* ReplaceElementsAt(index_type aStart, size_type aCount,
+ const nsTArray<Item>& aArray,
+ const mozilla::fallible_t&)
+ {
+ return ReplaceElementsAt<Item, FallibleAlloc>(aStart, aCount, aArray);
+ }
+
+ // A variation on the ReplaceElementsAt method defined above.
+protected:
+ template<class Item, typename ActualAlloc = Alloc>
+ elem_type* ReplaceElementsAt(index_type aStart, size_type aCount,
+ const Item& aItem)
+ {
+ return ReplaceElementsAt<Item, ActualAlloc>(aStart, aCount, &aItem, 1);
+ }
+public:
+
+ template<class Item>
+ MOZ_MUST_USE
+ elem_type* ReplaceElementsAt(index_type aStart, size_type aCount,
+ const Item& aItem, const mozilla::fallible_t&)
+ {
+ return ReplaceElementsAt<Item, FallibleAlloc>(aStart, aCount, aItem);
+ }
+
+ // A variation on the ReplaceElementsAt method defined above.
+ template<class Item>
+ elem_type* ReplaceElementAt(index_type aIndex, const Item& aItem)
+ {
+ return ReplaceElementsAt(aIndex, 1, &aItem, 1);
+ }
+
+ // A variation on the ReplaceElementsAt method defined above.
+protected:
+ template<class Item, typename ActualAlloc = Alloc>
+ elem_type* InsertElementsAt(index_type aIndex, const Item* aArray,
+ size_type aArrayLen)
+ {
+ return ReplaceElementsAt<Item, ActualAlloc>(aIndex, 0, aArray, aArrayLen);
+ }
+public:
+
+ template<class Item>
+ MOZ_MUST_USE
+ elem_type* InsertElementsAt(index_type aIndex, const Item* aArray,
+ size_type aArrayLen, const mozilla::fallible_t&)
+ {
+ return InsertElementsAt<Item, FallibleAlloc>(aIndex, aArray, aArrayLen);
+ }
+
+ // A variation on the ReplaceElementsAt method defined above.
+protected:
+ template<class Item, class Allocator, typename ActualAlloc = Alloc>
+ elem_type* InsertElementsAt(index_type aIndex,
+ const nsTArray_Impl<Item, Allocator>& aArray)
+ {
+ return ReplaceElementsAt<Item, ActualAlloc>(
+ aIndex, 0, aArray.Elements(), aArray.Length());
+ }
+public:
+
+ template<class Item, class Allocator>
+ MOZ_MUST_USE
+ elem_type* InsertElementsAt(index_type aIndex,
+ const nsTArray_Impl<Item, Allocator>& aArray,
+ const mozilla::fallible_t&)
+ {
+ return InsertElementsAt<Item, Allocator, FallibleAlloc>(aIndex, aArray);
+ }
+
+ // Insert a new element without copy-constructing. This is useful to avoid
+ // temporaries.
+ // @return A pointer to the newly inserted element, or null on OOM.
+protected:
+ template<typename ActualAlloc = Alloc>
+ elem_type* InsertElementAt(index_type aIndex);
+
+public:
+
+ MOZ_MUST_USE
+ elem_type* InsertElementAt(index_type aIndex, const mozilla::fallible_t&)
+ {
+ return InsertElementAt<FallibleAlloc>(aIndex);
+ }
+
+ // Insert a new element, move constructing if possible.
+protected:
+ template<class Item, typename ActualAlloc = Alloc>
+ elem_type* InsertElementAt(index_type aIndex, Item&& aItem);
+
+public:
+
+ template<class Item>
+ MOZ_MUST_USE
+ elem_type* InsertElementAt(index_type aIndex, Item&& aItem,
+ const mozilla::fallible_t&)
+ {
+ return InsertElementAt<Item, FallibleAlloc>(aIndex,
+ mozilla::Forward<Item>(aItem));
+ }
+
+ // This method searches for the smallest index of an element that is strictly
+ // greater than |aItem|. If |aItem| is inserted at this index, the array will
+ // remain sorted and |aItem| would come after all elements that are equal to
+ // it. If |aItem| is greater than or equal to all elements in the array, the
+ // array length is returned.
+ //
+ // Note that consumers who want to know whether there are existing items equal
+ // to |aItem| in the array can just check that the return value here is > 0
+ // and indexing into the previous slot gives something equal to |aItem|.
+ //
+ //
+ // @param aItem The item to search for.
+ // @param aComp The Comparator used.
+ // @return The index of greatest element <= to |aItem|
+ // @precondition The array is sorted
+ template<class Item, class Comparator>
+ index_type IndexOfFirstElementGt(const Item& aItem,
+ const Comparator& aComp) const
+ {
+ using mozilla::BinarySearchIf;
+ typedef ::detail::ItemComparatorFirstElementGT<Item, Comparator> Cmp;
+
+ size_t index;
+ BinarySearchIf(*this, 0, Length(), Cmp(aItem, aComp), &index);
+ return index;
+ }
+
+ // A variation on the IndexOfFirstElementGt method defined above.
+ template<class Item>
+ index_type
+ IndexOfFirstElementGt(const Item& aItem) const
+ {
+ return IndexOfFirstElementGt(aItem, nsDefaultComparator<elem_type, Item>());
+ }
+
+ // Inserts |aItem| at such an index to guarantee that if the array
+ // was previously sorted, it will remain sorted after this
+ // insertion.
+protected:
+ template<class Item, class Comparator, typename ActualAlloc = Alloc>
+ elem_type* InsertElementSorted(Item&& aItem, const Comparator& aComp)
+ {
+ index_type index = IndexOfFirstElementGt<Item, Comparator>(aItem, aComp);
+ return InsertElementAt<Item, ActualAlloc>(
+ index, mozilla::Forward<Item>(aItem));
+ }
+public:
+
+ template<class Item, class Comparator>
+ MOZ_MUST_USE
+ elem_type* InsertElementSorted(Item&& aItem, const Comparator& aComp,
+ const mozilla::fallible_t&)
+ {
+ return InsertElementSorted<Item, Comparator, FallibleAlloc>(
+ mozilla::Forward<Item>(aItem), aComp);
+ }
+
+ // A variation on the InsertElementSorted method defined above.
+protected:
+ template<class Item, typename ActualAlloc = Alloc>
+ elem_type* InsertElementSorted(Item&& aItem)
+ {
+ nsDefaultComparator<elem_type, Item> comp;
+ return InsertElementSorted<Item, decltype(comp), ActualAlloc>(
+ mozilla::Forward<Item>(aItem), comp);
+ }
+public:
+
+ template<class Item>
+ MOZ_MUST_USE
+ elem_type* InsertElementSorted(Item&& aItem, const mozilla::fallible_t&)
+ {
+ return InsertElementSorted<Item, FallibleAlloc>(
+ mozilla::Forward<Item>(aItem));
+ }
+
+ // This method appends elements to the end of this array.
+ // @param aArray The elements to append to this array.
+ // @param aArrayLen The number of elements to append to this array.
+ // @return A pointer to the new elements in the array, or null if
+ // the operation failed due to insufficient memory.
+protected:
+ template<class Item, typename ActualAlloc = Alloc>
+ elem_type* AppendElements(const Item* aArray, size_type aArrayLen);
+
+public:
+
+ template<class Item>
+ /* MOZ_MUST_USE */
+ elem_type* AppendElements(const Item* aArray, size_type aArrayLen,
+ const mozilla::fallible_t&)
+ {
+ return AppendElements<Item, FallibleAlloc>(aArray, aArrayLen);
+ }
+
+ // A variation on the AppendElements method defined above.
+protected:
+ template<class Item, class Allocator, typename ActualAlloc = Alloc>
+ elem_type* AppendElements(const nsTArray_Impl<Item, Allocator>& aArray)
+ {
+ return AppendElements<Item, ActualAlloc>(aArray.Elements(), aArray.Length());
+ }
+public:
+
+ template<class Item, class Allocator>
+ /* MOZ_MUST_USE */
+ elem_type* AppendElements(const nsTArray_Impl<Item, Allocator>& aArray,
+ const mozilla::fallible_t&)
+ {
+ return AppendElements<Item, Allocator, FallibleAlloc>(aArray);
+ }
+
+ // Move all elements from another array to the end of this array.
+ // @return A pointer to the newly appended elements, or null on OOM.
+protected:
+ template<class Item, class Allocator, typename ActualAlloc = Alloc>
+ elem_type* AppendElements(nsTArray_Impl<Item, Allocator>&& aArray);
+
+public:
+
+ template<class Item, class Allocator, typename ActualAlloc = Alloc>
+ /* MOZ_MUST_USE */
+ elem_type* AppendElements(nsTArray_Impl<Item, Allocator>&& aArray,
+ const mozilla::fallible_t&)
+ {
+ return AppendElements<Item, Allocator>(mozilla::Move(aArray));
+ }
+
+ // Append a new element, move constructing if possible.
+protected:
+ template<class Item, typename ActualAlloc = Alloc>
+ elem_type* AppendElement(Item&& aItem);
+
+public:
+
+ template<class Item>
+ /* MOZ_MUST_USE */
+ elem_type* AppendElement(Item&& aItem,
+ const mozilla::fallible_t&)
+ {
+ return AppendElement<Item, FallibleAlloc>(mozilla::Forward<Item>(aItem));
+ }
+
+ // Append new elements without copy-constructing. This is useful to avoid
+ // temporaries.
+ // @return A pointer to the newly appended elements, or null on OOM.
+protected:
+ template<typename ActualAlloc = Alloc>
+ elem_type* AppendElements(size_type aCount) {
+ if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
+ Length() + aCount, sizeof(elem_type)))) {
+ return nullptr;
+ }
+ elem_type* elems = Elements() + Length();
+ size_type i;
+ for (i = 0; i < aCount; ++i) {
+ elem_traits::Construct(elems + i);
+ }
+ this->IncrementLength(aCount);
+ return elems;
+ }
+public:
+
+ /* MOZ_MUST_USE */
+ elem_type* AppendElements(size_type aCount,
+ const mozilla::fallible_t&)
+ {
+ return AppendElements<FallibleAlloc>(aCount);
+ }
+
+ // Append a new element without copy-constructing. This is useful to avoid
+ // temporaries.
+ // @return A pointer to the newly appended element, or null on OOM.
+protected:
+ template<typename ActualAlloc = Alloc>
+ elem_type* AppendElement()
+ {
+ return AppendElements<ActualAlloc>(1);
+ }
+public:
+
+ /* MOZ_MUST_USE */
+ elem_type* AppendElement(const mozilla::fallible_t&)
+ {
+ return AppendElement<FallibleAlloc>();
+ }
+
+ // This method removes a range of elements from this array.
+ // @param aStart The starting index of the elements to remove.
+ // @param aCount The number of elements to remove.
+ void RemoveElementsAt(index_type aStart, size_type aCount);
+
+ // A variation on the RemoveElementsAt method defined above.
+ void RemoveElementAt(index_type aIndex) { RemoveElementsAt(aIndex, 1); }
+
+ // A variation on the RemoveElementsAt method defined above.
+ void Clear() { RemoveElementsAt(0, Length()); }
+
+ // This method removes elements based on the return value of the
+ // callback function aPredicate. If the function returns true for
+ // an element, the element is removed. aPredicate will be called
+ // for each element in order. It is not safe to access the array
+ // inside aPredicate.
+ template<typename Predicate>
+ void RemoveElementsBy(Predicate aPredicate);
+
+ // This helper function combines IndexOf with RemoveElementAt to "search
+ // and destroy" the first element 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>
+ bool RemoveElement(const Item& aItem, const Comparator& aComp)
+ {
+ index_type i = IndexOf(aItem, 0, aComp);
+ if (i == NoIndex) {
+ return false;
+ }
+
+ RemoveElementAt(i);
+ return true;
+ }
+
+ // A variation on the RemoveElement method defined above that assumes
+ // that 'operator==' is defined for elem_type.
+ template<class Item>
+ bool RemoveElement(const Item& aItem)
+ {
+ return RemoveElement(aItem, nsDefaultComparator<elem_type, Item>());
+ }
+
+ // This helper function combines IndexOfFirstElementGt with
+ // RemoveElementAt to "search and destroy" the last element 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>
+ bool RemoveElementSorted(const Item& aItem, const Comparator& aComp)
+ {
+ index_type index = IndexOfFirstElementGt(aItem, aComp);
+ if (index > 0 && aComp.Equals(ElementAt(index - 1), aItem)) {
+ RemoveElementAt(index - 1);
+ return true;
+ }
+ return false;
+ }
+
+ // A variation on the RemoveElementSorted method defined above.
+ template<class Item>
+ bool RemoveElementSorted(const Item& aItem)
+ {
+ return RemoveElementSorted(aItem, nsDefaultComparator<elem_type, Item>());
+ }
+
+ // This method causes the elements contained in this array and the given
+ // array to be swapped.
+ template<class Allocator>
+ typename Alloc::ResultType SwapElements(nsTArray_Impl<E, Allocator>& aOther)
+ {
+ return Alloc::Result(this->template SwapArrayElements<Alloc>(
+ aOther, sizeof(elem_type), MOZ_ALIGNOF(elem_type)));
+ }
+
+ //
+ // Allocation
+ //
+
+ // This method may increase the capacity of this array object by the
+ // specified amount. This method may be called in advance of several
+ // AppendElement operations to minimize heap re-allocations. This method
+ // will not reduce the number of elements in this array.
+ // @param aCapacity The desired capacity of this array.
+ // @return True if the operation succeeded; false if we ran out of memory
+protected:
+ template<typename ActualAlloc = Alloc>
+ typename ActualAlloc::ResultType SetCapacity(size_type aCapacity)
+ {
+ return ActualAlloc::Result(this->template EnsureCapacity<ActualAlloc>(
+ aCapacity, sizeof(elem_type)));
+ }
+public:
+
+ MOZ_MUST_USE
+ bool SetCapacity(size_type aCapacity, const mozilla::fallible_t&)
+ {
+ return SetCapacity<FallibleAlloc>(aCapacity);
+ }
+
+ // This method modifies the length of the array. 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. Otherwise, this call
+ // removes elements from the array (see also RemoveElementsAt).
+ // @param aNewLen The desired length of this array.
+ // @return True if the operation succeeded; false otherwise.
+ // See also TruncateLength if the new length is guaranteed to be smaller than
+ // the old.
+protected:
+ template<typename ActualAlloc = Alloc>
+ typename ActualAlloc::ResultType SetLength(size_type aNewLen)
+ {
+ size_type oldLen = Length();
+ if (aNewLen > oldLen) {
+ return ActualAlloc::ConvertBoolToResultType(
+ InsertElementsAt<ActualAlloc>(oldLen, aNewLen - oldLen) != nullptr);
+ }
+
+ TruncateLength(aNewLen);
+ return ActualAlloc::ConvertBoolToResultType(true);
+ }
+public:
+
+ MOZ_MUST_USE
+ bool SetLength(size_type aNewLen, const mozilla::fallible_t&)
+ {
+ return SetLength<FallibleAlloc>(aNewLen);
+ }
+
+ // This method modifies the length of the array, but may only be
+ // called when the new length is shorter than the old. It can
+ // therefore be called when elem_type has no default constructor,
+ // unlike SetLength. It removes elements from the array (see also
+ // RemoveElementsAt).
+ // @param aNewLen The desired length of this array.
+ void TruncateLength(size_type aNewLen)
+ {
+ size_type oldLen = Length();
+ MOZ_ASSERT(aNewLen <= oldLen,
+ "caller should use SetLength instead");
+ RemoveElementsAt(aNewLen, oldLen - aNewLen);
+ }
+
+ // This method ensures that the array has length at least the given
+ // length. If the current length is shorter than the given length,
+ // then new elements will be constructed using elem_type's default
+ // constructor.
+ // @param aMinLen The desired minimum length of this array.
+ // @return True if the operation succeeded; false otherwise.
+protected:
+ template<typename ActualAlloc = Alloc>
+ typename ActualAlloc::ResultType EnsureLengthAtLeast(size_type aMinLen)
+ {
+ size_type oldLen = Length();
+ if (aMinLen > oldLen) {
+ return ActualAlloc::ConvertBoolToResultType(
+ !!InsertElementsAt<ActualAlloc>(oldLen, aMinLen - oldLen));
+ }
+ return ActualAlloc::ConvertBoolToResultType(true);
+ }
+public:
+
+ MOZ_MUST_USE
+ bool EnsureLengthAtLeast(size_type aMinLen, const mozilla::fallible_t&)
+ {
+ return EnsureLengthAtLeast<FallibleAlloc>(aMinLen);
+ }
+
+ // This method inserts elements into the array, constructing
+ // them using elem_type's default constructor.
+ // @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 elements to insert
+protected:
+ template<typename ActualAlloc = Alloc>
+ elem_type* InsertElementsAt(index_type aIndex, size_type aCount)
+ {
+ if (!base_type::template InsertSlotsAt<ActualAlloc>(aIndex, aCount,
+ sizeof(elem_type),
+ MOZ_ALIGNOF(elem_type))) {
+ return nullptr;
+ }
+
+ // Initialize the extra array elements
+ elem_type* iter = Elements() + aIndex;
+ elem_type* iend = iter + aCount;
+ for (; iter != iend; ++iter) {
+ elem_traits::Construct(iter);
+ }
+
+ return Elements() + aIndex;
+ }
+public:
+
+ MOZ_MUST_USE
+ elem_type* InsertElementsAt(index_type aIndex, size_type aCount,
+ const mozilla::fallible_t&)
+ {
+ return InsertElementsAt<FallibleAlloc>(aIndex, aCount);
+ }
+
+ // This method inserts elements into the array, constructing them
+ // elem_type's copy constructor (or whatever one-arg constructor
+ // happens to match the Item type).
+ // @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 elements to insert.
+ // @param aItem the value to use when constructing the new elements.
+protected:
+ template<class Item, typename ActualAlloc = Alloc>
+ elem_type* InsertElementsAt(index_type aIndex, size_type aCount,
+ const Item& aItem);
+
+public:
+
+ template<class Item>
+ MOZ_MUST_USE
+ elem_type* InsertElementsAt(index_type aIndex, size_type aCount,
+ const Item& aItem, const mozilla::fallible_t&)
+ {
+ return InsertElementsAt<Item, FallibleAlloc>(aIndex, aCount, aItem);
+ }
+
+ // This method may be called to minimize the memory used by this array.
+ void Compact()
+ {
+ ShrinkCapacity(sizeof(elem_type), MOZ_ALIGNOF(elem_type));
+ }
+
+ //
+ // Sorting
+ //
+
+ // This function is meant to be used with the NS_QuickSort function. It
+ // maps the callback API expected by NS_QuickSort to the Comparator API
+ // used by nsTArray_Impl. See nsTArray_Impl::Sort.
+ template<class Comparator>
+ static int Compare(const void* aE1, const void* aE2, void* aData)
+ {
+ const Comparator* c = reinterpret_cast<const Comparator*>(aData);
+ const elem_type* a = static_cast<const elem_type*>(aE1);
+ const elem_type* b = static_cast<const elem_type*>(aE2);
+ return c->LessThan(*a, *b) ? -1 : (c->Equals(*a, *b) ? 0 : 1);
+ }
+
+ // This method sorts the elements of the array. It uses the LessThan
+ // method defined on the given Comparator object to collate elements.
+ // @param aComp The Comparator used to collate elements.
+ template<class Comparator>
+ void Sort(const Comparator& aComp)
+ {
+ NS_QuickSort(Elements(), Length(), sizeof(elem_type),
+ Compare<Comparator>, const_cast<Comparator*>(&aComp));
+ }
+
+ // A variation on the Sort method defined above that assumes that
+ // 'operator<' is defined for elem_type.
+ void Sort() { Sort(nsDefaultComparator<elem_type, elem_type>()); }
+
+protected:
+ using base_type::Hdr;
+ using base_type::ShrinkCapacity;
+
+ // This method invokes elem_type's destructor on a range of elements.
+ // @param aStart The index of the first element to destroy.
+ // @param aCount The number of elements to destroy.
+ void DestructRange(index_type aStart, size_type aCount)
+ {
+ elem_type* iter = Elements() + aStart;
+ elem_type *iend = iter + aCount;
+ for (; iter != iend; ++iter) {
+ elem_traits::Destruct(iter);
+ }
+ }
+
+ // This method invokes elem_type's copy-constructor on a range of elements.
+ // @param aStart The index of the first element to construct.
+ // @param aCount The number of elements to construct.
+ // @param aValues The array of elements to copy.
+ template<class Item>
+ void AssignRange(index_type aStart, size_type aCount, const Item* aValues)
+ {
+ AssignRangeAlgorithm<mozilla::IsPod<Item>::value,
+ mozilla::IsSame<Item, elem_type>::value>
+ ::implementation(Elements(), aStart, aCount, aValues);
+ }
+};
+
+template<typename E, class Alloc>
+template<class Item, typename ActualAlloc>
+auto
+nsTArray_Impl<E, Alloc>::ReplaceElementsAt(index_type aStart, size_type aCount,
+ const Item* aArray, size_type aArrayLen) -> elem_type*
+{
+ // Adjust memory allocation up-front to catch errors.
+ if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
+ Length() + aArrayLen - aCount, sizeof(elem_type)))) {
+ return nullptr;
+ }
+ DestructRange(aStart, aCount);
+ this->template ShiftData<ActualAlloc>(aStart, aCount, aArrayLen,
+ sizeof(elem_type),
+ MOZ_ALIGNOF(elem_type));
+ AssignRange(aStart, aArrayLen, aArray);
+ return Elements() + aStart;
+}
+
+template<typename E, class Alloc>
+void
+nsTArray_Impl<E, Alloc>::RemoveElementsAt(index_type aStart, size_type aCount)
+{
+ MOZ_ASSERT(aCount == 0 || aStart < Length(), "Invalid aStart index");
+ MOZ_ASSERT(aStart + aCount <= Length(), "Invalid length");
+ // Check that the previous assert didn't overflow
+ MOZ_ASSERT(aStart <= aStart + aCount, "Start index plus length overflows");
+ DestructRange(aStart, aCount);
+ this->template ShiftData<InfallibleAlloc>(aStart, aCount, 0,
+ sizeof(elem_type),
+ MOZ_ALIGNOF(elem_type));
+}
+
+template<typename E, class Alloc>
+template<typename Predicate>
+void
+nsTArray_Impl<E, Alloc>::RemoveElementsBy(Predicate aPredicate)
+{
+ if (base_type::mHdr == EmptyHdr()) {
+ return;
+ }
+
+ index_type j = 0;
+ index_type len = Length();
+ for (index_type i = 0; i < len; ++i) {
+ if (aPredicate(Elements()[i])) {
+ elem_traits::Destruct(Elements() + i);
+ } else {
+ if (j < i) {
+ copy_type::MoveNonOverlappingRegion(Elements() + j, Elements() + i,
+ 1, sizeof(elem_type));
+ }
+ ++j;
+ }
+ }
+ base_type::mHdr->mLength = j;
+}
+
+template<typename E, class Alloc>
+template<class Item, typename ActualAlloc>
+auto
+nsTArray_Impl<E, Alloc>::InsertElementsAt(index_type aIndex, size_type aCount,
+ const Item& aItem) -> elem_type*
+{
+ if (!base_type::template InsertSlotsAt<ActualAlloc>(aIndex, aCount,
+ sizeof(elem_type),
+ MOZ_ALIGNOF(elem_type))) {
+ return nullptr;
+ }
+
+ // Initialize the extra array elements
+ elem_type* iter = Elements() + aIndex;
+ elem_type* iend = iter + aCount;
+ for (; iter != iend; ++iter) {
+ elem_traits::Construct(iter, aItem);
+ }
+
+ return Elements() + aIndex;
+}
+
+template<typename E, class Alloc>
+template<typename ActualAlloc>
+auto
+nsTArray_Impl<E, Alloc>::InsertElementAt(index_type aIndex) -> elem_type*
+{
+ if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
+ Length() + 1, sizeof(elem_type)))) {
+ return nullptr;
+ }
+ this->template ShiftData<ActualAlloc>(aIndex, 0, 1, sizeof(elem_type),
+ MOZ_ALIGNOF(elem_type));
+ elem_type* elem = Elements() + aIndex;
+ elem_traits::Construct(elem);
+ return elem;
+}
+
+template<typename E, class Alloc>
+template<class Item, typename ActualAlloc>
+auto
+nsTArray_Impl<E, Alloc>::InsertElementAt(index_type aIndex, Item&& aItem) -> elem_type*
+{
+ if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
+ Length() + 1, sizeof(elem_type)))) {
+ return nullptr;
+ }
+ this->template ShiftData<ActualAlloc>(aIndex, 0, 1, sizeof(elem_type),
+ MOZ_ALIGNOF(elem_type));
+ elem_type* elem = Elements() + aIndex;
+ elem_traits::Construct(elem, mozilla::Forward<Item>(aItem));
+ return elem;
+}
+
+template<typename E, class Alloc>
+template<class Item, typename ActualAlloc>
+auto
+nsTArray_Impl<E, Alloc>::AppendElements(const Item* aArray, size_type aArrayLen) -> elem_type*
+{
+ if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
+ Length() + aArrayLen, sizeof(elem_type)))) {
+ return nullptr;
+ }
+ index_type len = Length();
+ AssignRange(len, aArrayLen, aArray);
+ this->IncrementLength(aArrayLen);
+ return Elements() + len;
+}
+
+template<typename E, class Alloc>
+template<class Item, class Allocator, typename ActualAlloc>
+auto
+nsTArray_Impl<E, Alloc>::AppendElements(nsTArray_Impl<Item, Allocator>&& aArray) -> elem_type*
+{
+ MOZ_ASSERT(&aArray != this, "argument must be different aArray");
+ if (Length() == 0) {
+ SwapElements<ActualAlloc>(aArray);
+ return Elements();
+ }
+
+ index_type len = Length();
+ index_type otherLen = aArray.Length();
+ if (!Alloc::Successful(this->template EnsureCapacity<Alloc>(
+ len + otherLen, sizeof(elem_type)))) {
+ return nullptr;
+ }
+ copy_type::MoveNonOverlappingRegion(Elements() + len, aArray.Elements(), otherLen,
+ sizeof(elem_type));
+ this->IncrementLength(otherLen);
+ aArray.template ShiftData<Alloc>(0, otherLen, 0, sizeof(elem_type),
+ MOZ_ALIGNOF(elem_type));
+ return Elements() + len;
+}
+
+template<typename E, class Alloc>
+template<class Item, typename ActualAlloc>
+auto
+nsTArray_Impl<E, Alloc>::AppendElement(Item&& aItem) -> elem_type*
+{
+ if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
+ Length() + 1, sizeof(elem_type)))) {
+ return nullptr;
+ }
+ elem_type* elem = Elements() + Length();
+ elem_traits::Construct(elem, mozilla::Forward<Item>(aItem));
+ this->IncrementLength(1);
+ return elem;
+}
+
+template<typename E, typename Alloc>
+inline void
+ImplCycleCollectionUnlink(nsTArray_Impl<E, Alloc>& aField)
+{
+ aField.Clear();
+}
+
+template<typename E, typename Alloc>
+inline void
+ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
+ nsTArray_Impl<E, Alloc>& aField,
+ const char* aName,
+ uint32_t aFlags = 0)
+{
+ aFlags |= CycleCollectionEdgeNameArrayFlag;
+ size_t length = aField.Length();
+ for (size_t i = 0; i < length; ++i) {
+ ImplCycleCollectionTraverse(aCallback, aField[i], aName, aFlags);
+ }
+}
+
+//
+// nsTArray is an infallible vector class. See the comment at the top of this
+// file for more details.
+//
+template<class E>
+class nsTArray : public nsTArray_Impl<E, nsTArrayInfallibleAllocator>
+{
+public:
+ typedef nsTArray_Impl<E, nsTArrayInfallibleAllocator> base_type;
+ typedef nsTArray<E> self_type;
+ typedef typename base_type::size_type size_type;
+
+ nsTArray() {}
+ explicit nsTArray(size_type aCapacity) : base_type(aCapacity) {}
+ explicit nsTArray(const nsTArray& aOther) : base_type(aOther) {}
+ MOZ_IMPLICIT nsTArray(nsTArray&& aOther) : base_type(mozilla::Move(aOther)) {}
+ MOZ_IMPLICIT nsTArray(std::initializer_list<E> aIL) : base_type(aIL) {}
+
+ template<class Allocator>
+ explicit nsTArray(const nsTArray_Impl<E, Allocator>& aOther)
+ : base_type(aOther)
+ {
+ }
+ template<class Allocator>
+ MOZ_IMPLICIT nsTArray(nsTArray_Impl<E, Allocator>&& aOther)
+ : base_type(mozilla::Move(aOther))
+ {
+ }
+
+ self_type& operator=(const self_type& aOther)
+ {
+ base_type::operator=(aOther);
+ return *this;
+ }
+ template<class Allocator>
+ self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther)
+ {
+ base_type::operator=(aOther);
+ return *this;
+ }
+ self_type& operator=(self_type&& aOther)
+ {
+ base_type::operator=(mozilla::Move(aOther));
+ return *this;
+ }
+ template<class Allocator>
+ self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther)
+ {
+ base_type::operator=(mozilla::Move(aOther));
+ return *this;
+ }
+
+ using base_type::AppendElement;
+ using base_type::AppendElements;
+ using base_type::EnsureLengthAtLeast;
+ using base_type::InsertElementAt;
+ using base_type::InsertElementsAt;
+ using base_type::InsertElementSorted;
+ using base_type::ReplaceElementsAt;
+ using base_type::SetCapacity;
+ using base_type::SetLength;
+};
+
+//
+// FallibleTArray is a fallible vector class.
+//
+template<class E>
+class FallibleTArray : public nsTArray_Impl<E, nsTArrayFallibleAllocator>
+{
+public:
+ typedef nsTArray_Impl<E, nsTArrayFallibleAllocator> base_type;
+ typedef FallibleTArray<E> self_type;
+ typedef typename base_type::size_type size_type;
+
+ FallibleTArray() {}
+ explicit FallibleTArray(size_type aCapacity) : base_type(aCapacity) {}
+ explicit FallibleTArray(const FallibleTArray<E>& aOther) : base_type(aOther) {}
+ FallibleTArray(FallibleTArray<E>&& aOther)
+ : base_type(mozilla::Move(aOther))
+ {
+ }
+
+ template<class Allocator>
+ explicit FallibleTArray(const nsTArray_Impl<E, Allocator>& aOther)
+ : base_type(aOther)
+ {
+ }
+ template<class Allocator>
+ explicit FallibleTArray(nsTArray_Impl<E, Allocator>&& aOther)
+ : base_type(mozilla::Move(aOther))
+ {
+ }
+
+ self_type& operator=(const self_type& aOther)
+ {
+ base_type::operator=(aOther);
+ return *this;
+ }
+ template<class Allocator>
+ self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther)
+ {
+ base_type::operator=(aOther);
+ return *this;
+ }
+ self_type& operator=(self_type&& aOther)
+ {
+ base_type::operator=(mozilla::Move(aOther));
+ return *this;
+ }
+ template<class Allocator>
+ self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther)
+ {
+ base_type::operator=(mozilla::Move(aOther));
+ return *this;
+ }
+};
+
+//
+// AutoTArray<E, N> is like nsTArray<E>, but with N elements of inline storage.
+// Storing more than N elements is fine, but it will cause a heap allocation.
+//
+template<class E, size_t N>
+class MOZ_NON_MEMMOVABLE AutoTArray : public nsTArray<E>
+{
+ static_assert(N != 0, "AutoTArray<E, 0> should be specialized");
+public:
+ typedef AutoTArray<E, N> self_type;
+ typedef nsTArray<E> base_type;
+ typedef typename base_type::Header Header;
+ typedef typename base_type::elem_type elem_type;
+
+ AutoTArray()
+ {
+ Init();
+ }
+
+ AutoTArray(const self_type& aOther)
+ {
+ Init();
+ this->AppendElements(aOther);
+ }
+
+ explicit AutoTArray(const base_type& aOther)
+ {
+ Init();
+ this->AppendElements(aOther);
+ }
+
+ explicit AutoTArray(base_type&& aOther)
+ {
+ Init();
+ this->SwapElements(aOther);
+ }
+
+ template<typename Allocator>
+ explicit AutoTArray(nsTArray_Impl<elem_type, Allocator>&& aOther)
+ {
+ Init();
+ this->SwapElements(aOther);
+ }
+
+ MOZ_IMPLICIT AutoTArray(std::initializer_list<E> aIL)
+ {
+ Init();
+ this->AppendElements(aIL.begin(), aIL.size());
+ }
+
+ self_type& operator=(const self_type& aOther)
+ {
+ base_type::operator=(aOther);
+ return *this;
+ }
+
+ template<typename Allocator>
+ self_type& operator=(const nsTArray_Impl<elem_type, Allocator>& aOther)
+ {
+ base_type::operator=(aOther);
+ return *this;
+ }
+
+private:
+ // nsTArray_base casts itself as an nsAutoArrayBase in order to get a pointer
+ // to mAutoBuf.
+ template<class Allocator, class Copier>
+ friend class nsTArray_base;
+
+ void Init()
+ {
+ static_assert(MOZ_ALIGNOF(elem_type) <= 8,
+ "can't handle alignments greater than 8, "
+ "see nsTArray_base::UsesAutoArrayBuffer()");
+ // Temporary work around for VS2012 RC compiler crash
+ Header** phdr = base_type::PtrToHdr();
+ *phdr = reinterpret_cast<Header*>(&mAutoBuf);
+ (*phdr)->mLength = 0;
+ (*phdr)->mCapacity = N;
+ (*phdr)->mIsAutoArray = 1;
+
+ MOZ_ASSERT(base_type::GetAutoArrayBuffer(MOZ_ALIGNOF(elem_type)) ==
+ reinterpret_cast<Header*>(&mAutoBuf),
+ "GetAutoArrayBuffer needs to be fixed");
+ }
+
+ // Declare mAutoBuf aligned to the maximum of the header's alignment and
+ // elem_type's alignment. We need to use a union rather than
+ // MOZ_ALIGNED_DECL because GCC is picky about what goes into
+ // __attribute__((aligned(foo))).
+ union
+ {
+ char mAutoBuf[sizeof(nsTArrayHeader) + N * sizeof(elem_type)];
+ // Do the max operation inline to ensure that it is a compile-time constant.
+ mozilla::AlignedElem<(MOZ_ALIGNOF(Header) > MOZ_ALIGNOF(elem_type)) ?
+ MOZ_ALIGNOF(Header) : MOZ_ALIGNOF(elem_type)> mAlign;
+ };
+};
+
+//
+// Specialization of AutoTArray<E, N> for the case where N == 0.
+// AutoTArray<E, 0> behaves exactly like nsTArray<E>, but without this
+// specialization, it stores a useless inline header.
+//
+// We do have many AutoTArray<E, 0> objects in memory: about 2,000 per tab as
+// of May 2014. These are typically not explicitly AutoTArray<E, 0> but rather
+// AutoTArray<E, N> for some value N depending on template parameters, in
+// generic code.
+//
+// For that reason, we optimize this case with the below partial specialization,
+// which ensures that AutoTArray<E, 0> is just like nsTArray<E>, without any
+// inline header overhead.
+//
+template<class E>
+class AutoTArray<E, 0> : public nsTArray<E>
+{
+};
+
+template<class E, size_t N>
+struct nsTArray_CopyChooser<AutoTArray<E, N>>
+{
+ typedef nsTArray_CopyWithConstructors<AutoTArray<E, N>> Type;
+};
+
+// Assert that AutoTArray doesn't have any extra padding inside.
+//
+// It's important that the data stored in this auto array takes up a multiple of
+// 8 bytes; e.g. AutoTArray<uint32_t, 1> wouldn't work. Since AutoTArray
+// contains a pointer, its size must be a multiple of alignof(void*). (This is
+// because any type may be placed into an array, and there's no padding between
+// elements of an array.) The compiler pads the end of the structure to
+// enforce this rule.
+//
+// If we used AutoTArray<uint32_t, 1> below, this assertion would fail on a
+// 64-bit system, where the compiler inserts 4 bytes of padding at the end of
+// the auto array to make its size a multiple of alignof(void*) == 8 bytes.
+
+static_assert(sizeof(AutoTArray<uint32_t, 2>) ==
+ sizeof(void*) + sizeof(nsTArrayHeader) + sizeof(uint32_t) * 2,
+ "AutoTArray shouldn't contain any extra padding, "
+ "see the comment");
+
+// Definitions of nsTArray_Impl methods
+#include "nsTArray-inl.h"
+
+#endif // nsTArray_h__