1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
13 #include <initializer_list>
17 #include <type_traits>
20 #include "mozilla/Alignment.h"
21 #include "mozilla/ArrayIterator.h"
22 #include "mozilla/Assertions.h"
23 #include "mozilla/Attributes.h"
24 #include "mozilla/BinarySearch.h"
25 #include "mozilla/CheckedInt.h"
26 #include "mozilla/FunctionTypeTraits.h"
27 #include "mozilla/MathAlgorithms.h"
28 #include "mozilla/MemoryReporting.h"
29 #include "mozilla/NotNull.h"
30 #include "mozilla/Span.h"
31 #include "mozilla/fallible.h"
32 #include "mozilla/mozalloc.h"
33 #include "nsAlgorithm.h"
35 #include "nsISupports.h"
36 #include "nsQuickSort.h"
37 #include "nsRegionFwd.h"
38 #include "nsTArrayForwardDeclare.h"
45 class nsCycleCollectionTraversalCallback
;
48 namespace mozilla::a11y
{
56 struct PropertyAnimationGroup
;
59 } // namespace mozilla
62 struct SerializedStructuredCloneBuffer
;
63 class SourceBufferTask
;
64 } // namespace mozilla
66 namespace mozilla::dom::binding_detail
{
67 template <typename
, typename
>
71 namespace mozilla::dom::ipc
{
72 class StructuredCloneData
;
73 } // namespace mozilla::dom::ipc
75 namespace mozilla::dom
{
76 class ClonedMessageData
;
78 class MessagePortIdentifier
;
79 struct MozPluginParameter
;
82 class OwningFileOrDirectory
;
83 class OwningStringOrBooleanOrObject
;
84 class OwningUTF8StringOrDouble
;
87 class ResponsiveImageCandidate
;
88 class ServiceWorkerRegistrationData
;
90 class SerializedStructuredCloneReadInfo
;
91 class ObjectStoreCursorResponse
;
92 class IndexCursorResponse
;
93 } // namespace indexedDB
94 } // namespace mozilla::dom
96 namespace mozilla::ipc
{
98 class ContentSecurityPolicy
;
101 } // namespace mozilla::ipc
103 class JSStructuredCloneData
;
109 // nsTArray<E> is a resizable array class, like std::vector.
111 // Unlike std::vector, which follows C++'s construction/destruction rules,
112 // By default, nsTArray assumes that instances of E can be relocated safely
113 // using memory utils (memcpy/memmove).
115 // The public classes defined in this header are
118 // CopyableTArray<E>,
119 // FallibleTArray<E>,
121 // CopyableAutoTArray<E, N>
123 // nsTArray, CopyableTArray, AutoTArray and CopyableAutoTArray are infallible by
124 // default. To opt-in to fallible behaviour, use the `mozilla::fallible`
125 // parameter and check the return value.
127 // CopyableTArray and CopyableAutoTArray< are copy-constructible and
128 // copy-assignable. Use these only when syntactically necessary to avoid implcit
129 // unintentional copies. nsTArray/AutoTArray can be conveniently copied using
130 // the Clone() member function. Consider using std::move where possible.
132 // If you just want to declare the nsTArray types (e.g., if you're in a header
133 // file and don't need the full nsTArray definitions) consider including
134 // nsTArrayForwardDeclare.h instead of nsTArray.h.
136 // The template parameter E specifies the type of the elements and has the
137 // following requirements:
139 // E MUST be safely memmove()'able.
140 // E MUST define a copy-constructor.
141 // E MAY define operator< for sorting.
142 // E MAY define operator== for searching.
144 // (Note that the memmove requirement may be relaxed for certain types - see
145 // nsTArray_RelocationStrategy below.)
147 // There is a public type elem_type defined as E within each array class, and we
148 // reference the type under this name below.
150 // For member functions taking a Comparator instance, Comparator must be either
151 // a functor with a tri-state comparison function with a signature compatible to
153 // /** @return negative iff a < b, 0 iff a == b, positive iff a > b */
154 // int (const elem_type& a, const elem_type& b);
156 // or a class defining member functions with signatures compatible to:
158 // class Comparator {
160 // /** @return True if the elements are equals; false otherwise. */
161 // bool Equals(const elem_type& a, const elem_type& b) const;
163 // /** @return True if (a < b); false otherwise. */
164 // bool LessThan(const elem_type& a, const elem_type& b) const;
167 // The Equals member function is used for searching, and the LessThan member
168 // function is used for searching and sorting. Note that some member functions,
169 // e.g. Compare, are templates where a different type Item can be used for the
170 // element to compare to. In that case, the signatures must be compatible to
171 // allow those comparisons, but the details are not documented here.
175 // nsTArrayFallibleResult and nsTArrayInfallibleResult types are proxy types
176 // which are used because you cannot use a templated type which is bound to
177 // void as an argument to a void function. In order to work around that, we
178 // encode either a void or a boolean inside these proxy objects, and pass them
179 // to the aforementioned function instead, and then use the type information to
180 // decide what to do in the function.
182 // Note that public nsTArray methods should never return a proxy type. Such
183 // types are only meant to be used in the internal nsTArray helper methods.
184 // Public methods returning non-proxy types cannot be called from other
187 struct nsTArrayFallibleResult
{
188 // Note: allows implicit conversions from and to bool
189 MOZ_IMPLICIT
constexpr nsTArrayFallibleResult(bool aResult
)
190 : mResult(aResult
) {}
192 MOZ_IMPLICIT
constexpr operator bool() { return mResult
; }
198 struct nsTArrayInfallibleResult
{};
201 // nsTArray*Allocators must all use the same |free()|, to allow swap()'ing
202 // between fallible and infallible variants.
205 struct nsTArrayFallibleAllocatorBase
{
206 typedef bool ResultType
;
207 typedef nsTArrayFallibleResult ResultTypeProxy
;
209 static constexpr ResultType
Result(ResultTypeProxy aResult
) {
212 static constexpr bool Successful(ResultTypeProxy aResult
) { return aResult
; }
213 static constexpr ResultTypeProxy
SuccessResult() { return true; }
214 static constexpr ResultTypeProxy
FailureResult() { return false; }
215 static constexpr ResultType
ConvertBoolToResultType(bool aValue
) {
220 struct nsTArrayInfallibleAllocatorBase
{
221 typedef void ResultType
;
222 typedef nsTArrayInfallibleResult ResultTypeProxy
;
224 static constexpr ResultType
Result(ResultTypeProxy aResult
) {}
225 static constexpr bool Successful(ResultTypeProxy
) { return true; }
226 static constexpr ResultTypeProxy
SuccessResult() { return ResultTypeProxy(); }
228 [[noreturn
]] static ResultTypeProxy
FailureResult() {
229 MOZ_CRASH("Infallible nsTArray should never fail");
232 template <typename T
>
233 static constexpr ResultType
ConvertBoolToResultType(T aValue
) {
235 MOZ_CRASH("infallible nsTArray should never convert false to ResultType");
239 template <typename T
>
240 static constexpr ResultType
ConvertBoolToResultType(
241 const mozilla::NotNull
<T
>& aValue
) {}
244 struct nsTArrayFallibleAllocator
: nsTArrayFallibleAllocatorBase
{
245 static void* Malloc(size_t aSize
) { return malloc(aSize
); }
246 static void* Realloc(void* aPtr
, size_t aSize
) {
247 return realloc(aPtr
, aSize
);
250 static void Free(void* aPtr
) { free(aPtr
); }
251 static void SizeTooBig(size_t) {}
254 struct nsTArrayInfallibleAllocator
: nsTArrayInfallibleAllocatorBase
{
255 static void* Malloc(size_t aSize
) MOZ_NONNULL_RETURN
{
256 return moz_xmalloc(aSize
);
258 static void* Realloc(void* aPtr
, size_t aSize
) MOZ_NONNULL_RETURN
{
259 return moz_xrealloc(aPtr
, aSize
);
262 static void Free(void* aPtr
) { free(aPtr
); }
263 static void SizeTooBig(size_t aSize
) { NS_ABORT_OOM(aSize
); }
266 // nsTArray_base stores elements into the space allocated beyond
267 // sizeof(*this). This is done to minimize the size of the nsTArray
268 // object when it is empty.
269 struct nsTArrayHeader
{
271 uint32_t mCapacity
: 31;
272 uint32_t mIsAutoArray
: 1;
276 extern const nsTArrayHeader sEmptyTArrayHeader
;
280 // nsTArray_CopyDisabler disables copy operations.
281 class nsTArray_CopyDisabler
{
283 nsTArray_CopyDisabler() = default;
285 nsTArray_CopyDisabler(const nsTArray_CopyDisabler
&) = delete;
286 nsTArray_CopyDisabler
& operator=(const nsTArray_CopyDisabler
&) = delete;
289 } // namespace detail
291 // This class provides a SafeElementAt method to nsTArray<E*> which does
292 // not take a second default value parameter.
293 template <class E
, class Derived
>
294 struct nsTArray_SafeElementAtHelper
: public ::detail::nsTArray_CopyDisabler
{
295 typedef E
* elem_type
;
296 typedef size_t index_type
;
298 // No implementation is provided for these two methods, and that is on
299 // purpose, since we don't support these functions on non-pointer type
301 elem_type
& SafeElementAt(index_type aIndex
);
302 const elem_type
& SafeElementAt(index_type aIndex
) const;
305 template <class E
, class Derived
>
306 struct nsTArray_SafeElementAtHelper
<E
*, Derived
>
307 : public ::detail::nsTArray_CopyDisabler
{
308 typedef E
* elem_type
;
309 // typedef const E* const_elem_type; XXX: see below
310 typedef size_t index_type
;
312 elem_type
SafeElementAt(index_type aIndex
) {
313 return static_cast<Derived
*>(this)->SafeElementAt(aIndex
, nullptr);
316 // XXX: Probably should return const_elem_type, but callsites must be fixed.
317 // Also, the use of const_elem_type for nsTArray<xpcGCCallback> in
318 // xpcprivate.h causes build failures on Windows because xpcGCCallback is a
319 // function pointer and MSVC doesn't like qualifying it with |const|.
320 elem_type
SafeElementAt(index_type aIndex
) const {
321 return static_cast<const Derived
*>(this)->SafeElementAt(aIndex
, nullptr);
325 // E is a smart pointer type; the
326 // smart pointer can act as its element_type*.
327 template <class E
, class Derived
>
328 struct nsTArray_SafeElementAtSmartPtrHelper
329 : public ::detail::nsTArray_CopyDisabler
{
330 typedef typename
E::element_type
* elem_type
;
331 typedef const typename
E::element_type
* const_elem_type
;
332 typedef size_t index_type
;
334 elem_type
SafeElementAt(index_type aIndex
) {
335 auto* derived
= static_cast<Derived
*>(this);
336 if (aIndex
< derived
->Length()) {
337 return derived
->Elements()[aIndex
];
342 // XXX: Probably should return const_elem_type, but callsites must be fixed.
343 elem_type
SafeElementAt(index_type aIndex
) const {
344 auto* derived
= static_cast<const Derived
*>(this);
345 if (aIndex
< derived
->Length()) {
346 return derived
->Elements()[aIndex
];
355 template <class E
, class Derived
>
356 struct nsTArray_SafeElementAtHelper
<nsCOMPtr
<E
>, Derived
>
357 : public nsTArray_SafeElementAtSmartPtrHelper
<nsCOMPtr
<E
>, Derived
> {};
359 template <class E
, class Derived
>
360 struct nsTArray_SafeElementAtHelper
<RefPtr
<E
>, Derived
>
361 : public nsTArray_SafeElementAtSmartPtrHelper
<RefPtr
<E
>, Derived
> {};
366 } // namespace mozilla
368 template <class E
, class Derived
>
369 struct nsTArray_SafeElementAtHelper
<mozilla::OwningNonNull
<E
>, Derived
>
370 : public nsTArray_SafeElementAtSmartPtrHelper
<mozilla::OwningNonNull
<E
>,
374 extern "C" void Gecko_EnsureTArrayCapacity(void* aArray
, size_t aCapacity
,
375 size_t aElementSize
);
376 extern "C" void Gecko_ClearPODTArray(void* aArray
, size_t aElementSize
,
377 size_t aElementAlign
);
379 MOZ_NORETURN MOZ_COLD
void InvalidArrayIndex_CRASH(size_t aIndex
,
383 // This class serves as a base class for nsTArray. It shouldn't be used
384 // directly. It holds common implementation code that does not depend on the
385 // element type of the nsTArray.
387 template <class Alloc
, class RelocationStrategy
>
388 class nsTArray_base
{
389 // Allow swapping elements with |nsTArray_base|s created using a
390 // different allocator. This is kosher because all allocators use
392 template <class XAlloc
, class XRelocationStrategy
>
393 friend class nsTArray_base
;
395 // Needed for AppendElements from an array with a different allocator, which
397 template <class E
, class XAlloc
>
398 friend class nsTArray_Impl
;
400 friend void Gecko_EnsureTArrayCapacity(void* aArray
, size_t aCapacity
,
402 friend void Gecko_ClearPODTArray(void* aTArray
, size_t aElementSize
,
403 size_t aElementAlign
);
406 typedef nsTArrayHeader Header
;
409 typedef size_t size_type
;
410 typedef size_t index_type
;
412 // @return The number of elements in the array.
413 size_type
Length() const { return mHdr
->mLength
; }
415 // @return True if the array is empty or false otherwise.
416 bool IsEmpty() const { return Length() == 0; }
418 // @return The number of elements that can fit in the array without forcing
419 // the array to be re-allocated. The length of an array is always less
420 // than or equal to its capacity.
421 size_type
Capacity() const { return mHdr
->mCapacity
; }
424 void* DebugGetHeader() const { return mHdr
; }
432 nsTArray_base(const nsTArray_base
&);
433 nsTArray_base
& operator=(const nsTArray_base
&);
435 // Resize the storage if necessary to achieve the requested capacity.
436 // @param aCapacity The requested number of array elements.
437 // @param aElemSize The size of an array element.
438 // @return False if insufficient memory is available; true otherwise.
439 template <typename ActualAlloc
>
440 typename
ActualAlloc::ResultTypeProxy
EnsureCapacity(size_type aCapacity
,
441 size_type aElemSize
);
443 // Extend the storage to accommodate aCount extra elements.
444 // @param aLength The current size of the array.
445 // @param aCount The number of elements to add.
446 // @param aElemSize The size of an array element.
447 // @return False if insufficient memory is available or the new length
448 // would overflow; true otherwise.
449 template <typename ActualAlloc
>
450 typename
ActualAlloc::ResultTypeProxy
ExtendCapacity(size_type aLength
,
452 size_type aElemSize
);
454 // Tries to resize the storage to the minimum required amount. If this fails,
455 // the array is left as-is.
456 // @param aElemSize The size of an array element.
457 // @param aElemAlign The alignment in bytes of an array element.
458 void ShrinkCapacity(size_type aElemSize
, size_t aElemAlign
);
460 // Resizes the storage to 0. This may only be called when Length() is already
462 // @param aElemSize The size of an array element.
463 // @param aElemAlign The alignment in bytes of an array element.
464 void ShrinkCapacityToZero(size_type aElemSize
, size_t aElemAlign
);
466 // This method may be called to resize a "gap" in the array by shifting
467 // elements around. It updates mLength appropriately. If the resulting
468 // array has zero elements, then the array's memory is free'd.
469 // @param aStart The starting index of the gap.
470 // @param aOldLen The current length of the gap.
471 // @param aNewLen The desired length of the gap.
472 // @param aElemSize The size of an array element.
473 // @param aElemAlign The alignment in bytes of an array element.
474 template <typename ActualAlloc
>
475 void ShiftData(index_type aStart
, size_type aOldLen
, size_type aNewLen
,
476 size_type aElemSize
, size_t aElemAlign
);
478 // This method may be called to swap elements from the end of the array to
479 // fill a "gap" in the array. If the resulting array has zero elements, then
480 // the array's memory is free'd.
481 // @param aStart The starting index of the gap.
482 // @param aCount The length of the gap.
483 // @param aElemSize The size of an array element.
484 // @param aElemAlign The alignment in bytes of an array element.
485 template <typename ActualAlloc
>
486 void SwapFromEnd(index_type aStart
, size_type aCount
, size_type aElemSize
,
489 // This method increments the length member of the array's header.
490 // Note that mHdr may actually be sEmptyTArrayHeader in the case where a
491 // zero-length array is inserted into our array. But then aNum should
493 void IncrementLength(size_t aNum
) {
494 if (HasEmptyHeader()) {
495 if (MOZ_UNLIKELY(aNum
!= 0)) {
496 // Writing a non-zero length to the empty header would be extremely bad.
500 mHdr
->mLength
+= aNum
;
504 // This method inserts blank slots into the array.
505 // @param aIndex the place to insert the new elements. This must be no
506 // greater than the current length of the array.
507 // @param aCount the number of slots to insert
508 // @param aElementSize the size of an array element.
509 // @param aElemAlign the alignment in bytes of an array element.
510 template <typename ActualAlloc
>
511 typename
ActualAlloc::ResultTypeProxy
InsertSlotsAt(index_type aIndex
,
513 size_type aElementSize
,
516 template <typename ActualAlloc
, class Allocator
>
517 typename
ActualAlloc::ResultTypeProxy
SwapArrayElements(
518 nsTArray_base
<Allocator
, RelocationStrategy
>& aOther
, size_type aElemSize
,
521 template <class Allocator
>
522 void MoveConstructNonAutoArray(
523 nsTArray_base
<Allocator
, RelocationStrategy
>& aOther
, size_type aElemSize
,
526 template <class Allocator
>
527 void MoveInit(nsTArray_base
<Allocator
, RelocationStrategy
>& aOther
,
528 size_type aElemSize
, size_t aElemAlign
);
530 // This is an RAII class used in SwapArrayElements.
531 class IsAutoArrayRestorer
{
533 IsAutoArrayRestorer(nsTArray_base
<Alloc
, RelocationStrategy
>& aArray
,
535 ~IsAutoArrayRestorer();
538 nsTArray_base
<Alloc
, RelocationStrategy
>& mArray
;
543 // Helper function for SwapArrayElements. Ensures that if the array
544 // is an AutoTArray that it doesn't use the built-in buffer.
545 template <typename ActualAlloc
>
546 bool EnsureNotUsingAutoArrayBuffer(size_type aElemSize
);
548 // Returns true if this nsTArray is an AutoTArray with a built-in buffer.
549 bool IsAutoArray() const { return mHdr
->mIsAutoArray
; }
551 // Returns a Header for the built-in buffer of this AutoTArray.
552 Header
* GetAutoArrayBuffer(size_t aElemAlign
) {
553 MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");
554 return GetAutoArrayBufferUnsafe(aElemAlign
);
556 const Header
* GetAutoArrayBuffer(size_t aElemAlign
) const {
557 MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");
558 return GetAutoArrayBufferUnsafe(aElemAlign
);
561 // Returns a Header for the built-in buffer of this AutoTArray, but doesn't
562 // assert that we are an AutoTArray.
563 Header
* GetAutoArrayBufferUnsafe(size_t aElemAlign
) {
564 return const_cast<Header
*>(
565 static_cast<const nsTArray_base
<Alloc
, RelocationStrategy
>*>(this)
566 ->GetAutoArrayBufferUnsafe(aElemAlign
));
568 const Header
* GetAutoArrayBufferUnsafe(size_t aElemAlign
) const;
570 // Returns true if this is an AutoTArray and it currently uses the
571 // built-in buffer to store its elements.
572 bool UsesAutoArrayBuffer() const;
574 // The array's elements (prefixed with a Header). This pointer is never
575 // null. If the array is empty, then this will point to sEmptyTArrayHeader.
578 Header
* Hdr() const MOZ_NONNULL_RETURN
{ return mHdr
; }
579 Header
** PtrToHdr() MOZ_NONNULL_RETURN
{ return &mHdr
; }
580 static Header
* EmptyHdr() MOZ_NONNULL_RETURN
{
581 return const_cast<Header
*>(&sEmptyTArrayHeader
);
584 [[nodiscard
]] bool HasEmptyHeader() const { return mHdr
== EmptyHdr(); }
589 // Used for argument checking in nsTArrayElementTraits::Emplace.
590 template <typename
... T
>
594 struct ChooseFirst
<> {
595 // Choose a default type that is guaranteed to not match E* for any
600 template <typename A
, typename
... Args
>
601 struct ChooseFirst
<A
, Args
...> {
605 } // namespace detail
608 // This class defines convenience functions for element specific operations.
609 // Specialize this template if necessary.
612 class nsTArrayElementTraits
{
614 // Invoke the default constructor in place.
615 static inline void Construct(E
* aE
) {
616 // Do NOT call "E()"! That triggers C++ "default initialization"
617 // which zeroes out POD ("plain old data") types such as regular
618 // ints. We don't want that because it can be a performance issue
619 // and people don't expect it; nsTArray should work like a regular
620 // C/C++ array in this respect.
621 new (static_cast<void*>(aE
)) E
;
623 // Invoke the copy-constructor in place.
625 static inline void Construct(E
* aE
, A
&& aArg
) {
626 using E_NoCV
= std::remove_cv_t
<E
>;
627 using A_NoCV
= std::remove_cv_t
<A
>;
628 static_assert(!std::is_same_v
<E_NoCV
*, A_NoCV
>,
629 "For safety, we disallow constructing nsTArray<E> elements "
630 "from E* pointers. See bug 960591.");
631 new (static_cast<void*>(aE
)) E(std::forward
<A
>(aArg
));
633 // Construct in place.
634 template <class... Args
>
635 static inline void Emplace(E
* aE
, Args
&&... aArgs
) {
636 using E_NoCV
= std::remove_cv_t
<E
>;
638 std::remove_cv_t
<typename ::detail::ChooseFirst
<Args
...>::Type
>;
639 static_assert(!std::is_same_v
<E_NoCV
*, A_NoCV
>,
640 "For safety, we disallow constructing nsTArray<E> elements "
641 "from E* pointers. See bug 960591.");
642 new (static_cast<void*>(aE
)) E(std::forward
<Args
>(aArgs
)...);
644 // Invoke the destructor in place.
645 static inline void Destruct(E
* aE
) { aE
->~E(); }
648 // The default comparator used by nsTArray
649 template <class A
, class B
>
650 class nsDefaultComparator
{
652 bool Equals(const A
& aA
, const B
& aB
) const { return aA
== aB
; }
653 bool LessThan(const A
& aA
, const B
& aB
) const { return aA
< aB
; }
656 template <bool IsTriviallyCopyConstructible
, bool IsSameType
>
657 struct AssignRangeAlgorithm
{
658 template <class Item
, class ElemType
, class IndexType
, class SizeType
>
659 static void implementation(ElemType
* aElements
, IndexType aStart
,
660 SizeType aCount
, const Item
* aValues
) {
661 ElemType
* iter
= aElements
+ aStart
;
662 ElemType
* end
= iter
+ aCount
;
663 for (; iter
!= end
; ++iter
, ++aValues
) {
664 nsTArrayElementTraits
<ElemType
>::Construct(iter
, *aValues
);
670 struct AssignRangeAlgorithm
<true, true> {
671 template <class Item
, class ElemType
, class IndexType
, class SizeType
>
672 static void implementation(ElemType
* aElements
, IndexType aStart
,
673 SizeType aCount
, const Item
* aValues
) {
675 memcpy(aElements
+ aStart
, aValues
, aCount
* sizeof(ElemType
));
681 // Normally elements are copied with memcpy and memmove, but for some element
682 // types that is problematic. The nsTArray_RelocationStrategy template class
683 // can be specialized to ensure that copying calls constructors and destructors
684 // instead, as is done below for JS::Heap<E> elements.
688 // A class that defines how to copy elements using memcpy/memmove.
690 struct nsTArray_RelocateUsingMemutils
{
691 const static bool allowRealloc
= true;
693 static void RelocateNonOverlappingRegionWithHeader(void* aDest
,
697 memcpy(aDest
, aSrc
, sizeof(nsTArrayHeader
) + aCount
* aElemSize
);
700 static void RelocateOverlappingRegion(void* aDest
, void* aSrc
, size_t aCount
,
702 memmove(aDest
, aSrc
, aCount
* aElemSize
);
705 static void RelocateNonOverlappingRegion(void* aDest
, void* aSrc
,
706 size_t aCount
, size_t aElemSize
) {
707 memcpy(aDest
, aSrc
, aCount
* aElemSize
);
712 // A template class that defines how to copy elements calling their constructors
713 // and destructors appropriately.
715 template <class ElemType
>
716 struct nsTArray_RelocateUsingMoveConstructor
{
717 typedef nsTArrayElementTraits
<ElemType
> traits
;
719 const static bool allowRealloc
= false;
721 static void RelocateNonOverlappingRegionWithHeader(void* aDest
, void* aSrc
,
724 nsTArrayHeader
* destHeader
= static_cast<nsTArrayHeader
*>(aDest
);
725 nsTArrayHeader
* srcHeader
= static_cast<nsTArrayHeader
*>(aSrc
);
726 *destHeader
= *srcHeader
;
727 RelocateNonOverlappingRegion(
728 static_cast<uint8_t*>(aDest
) + sizeof(nsTArrayHeader
),
729 static_cast<uint8_t*>(aSrc
) + sizeof(nsTArrayHeader
), aCount
,
733 // These functions are defined by analogy with memmove and memcpy.
734 // What they actually do is slightly different: RelocateOverlappingRegion
735 // checks to see which direction the movement needs to take place,
736 // whether from back-to-front of the range to be moved or from
737 // front-to-back. RelocateNonOverlappingRegion assumes that moving
738 // front-to-back is always valid. So they're really more like
739 // std::move{_backward,} in that respect. We keep these names because
740 // we think they read slightly better, and RelocateNonOverlappingRegion is
741 // only ever called on overlapping regions from RelocateOverlappingRegion.
742 static void RelocateOverlappingRegion(void* aDest
, void* aSrc
, size_t aCount
,
744 ElemType
* destElem
= static_cast<ElemType
*>(aDest
);
745 ElemType
* srcElem
= static_cast<ElemType
*>(aSrc
);
746 ElemType
* destElemEnd
= destElem
+ aCount
;
747 ElemType
* srcElemEnd
= srcElem
+ aCount
;
748 if (destElem
== srcElem
) {
749 return; // In practice, we don't do this.
752 // Figure out whether to copy back-to-front or front-to-back.
753 if (srcElemEnd
> destElem
&& srcElemEnd
< destElemEnd
) {
754 while (destElemEnd
!= destElem
) {
757 traits::Construct(destElemEnd
, std::move(*srcElemEnd
));
758 traits::Destruct(srcElemEnd
);
761 RelocateNonOverlappingRegion(aDest
, aSrc
, aCount
, aElemSize
);
765 static void RelocateNonOverlappingRegion(void* aDest
, void* aSrc
,
766 size_t aCount
, size_t aElemSize
) {
767 ElemType
* destElem
= static_cast<ElemType
*>(aDest
);
768 ElemType
* srcElem
= static_cast<ElemType
*>(aSrc
);
769 ElemType
* destElemEnd
= destElem
+ aCount
;
771 ElemType
* srcElemEnd
= srcElem
+ aCount
;
772 MOZ_ASSERT(srcElemEnd
<= destElem
|| srcElemEnd
> destElemEnd
);
774 while (destElem
!= destElemEnd
) {
775 traits::Construct(destElem
, std::move(*srcElem
));
776 traits::Destruct(srcElem
);
784 // The default behaviour is to use memcpy/memmove for everything.
787 struct MOZ_NEEDS_MEMMOVABLE_TYPE nsTArray_RelocationStrategy
{
788 using Type
= nsTArray_RelocateUsingMemutils
;
792 // Some classes require constructors/destructors to be called, so they are
795 #define MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(E) \
797 struct nsTArray_RelocationStrategy<E> { \
798 using Type = nsTArray_RelocateUsingMoveConstructor<E>; \
801 #define MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(T) \
802 template <typename S> \
803 struct nsTArray_RelocationStrategy<T<S>> { \
804 using Type = nsTArray_RelocateUsingMoveConstructor<T<S>>; \
807 // TODO mozilla::ipc::AutoIPCStream is not even movable, so memmovable use with
808 // nsTArray (in StructuredCloneData) seems at least quirky
810 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(JS::Heap
)
811 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(std::function
)
812 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(mozilla::ipc::Endpoint
)
814 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(nsRegion
)
815 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(nsIntRegion
)
816 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::layers::TileClient
)
817 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
818 mozilla::SerializedStructuredCloneBuffer
)
819 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
820 mozilla::dom::ipc::StructuredCloneData
)
821 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::dom::ClonedMessageData
)
822 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
823 mozilla::dom::indexedDB::ObjectStoreCursorResponse
)
824 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
825 mozilla::dom::indexedDB::IndexCursorResponse
)
826 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
827 mozilla::dom::indexedDB::SerializedStructuredCloneReadInfo
);
828 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(JSStructuredCloneData
)
829 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::dom::MessageData
)
830 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::dom::RefMessageData
)
831 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::SourceBufferTask
)
834 // Base class for nsTArray_Impl that is templated on element type and derived
835 // nsTArray_Impl class, to allow extra conversions to be added for specific
838 template <class E
, class Derived
>
839 struct nsTArray_TypedBase
: public nsTArray_SafeElementAtHelper
<E
, Derived
> {};
842 // Specialization of nsTArray_TypedBase for arrays containing JS::Heap<E>
845 // These conversions are safe because JS::Heap<E> and E share the same
846 // representation, and since the result of the conversions are const references
847 // we won't miss any barriers.
849 // The static_cast is necessary to obtain the correct address for the derived
850 // class since we are a base class used in multiple inheritance.
852 template <class E
, class Derived
>
853 struct nsTArray_TypedBase
<JS::Heap
<E
>, Derived
>
854 : public nsTArray_SafeElementAtHelper
<JS::Heap
<E
>, Derived
> {
855 operator const nsTArray
<E
>&() {
856 static_assert(sizeof(E
) == sizeof(JS::Heap
<E
>),
857 "JS::Heap<E> must be binary compatible with E.");
858 Derived
* self
= static_cast<Derived
*>(this);
859 return *reinterpret_cast<nsTArray
<E
>*>(self
);
862 operator const FallibleTArray
<E
>&() {
863 Derived
* self
= static_cast<Derived
*>(this);
864 return *reinterpret_cast<FallibleTArray
<E
>*>(self
);
870 // These helpers allow us to differentiate between tri-state comparator
871 // functions and classes with LessThan() and Equal() methods. If an object, when
872 // called as a function with two instances of our element type, returns an int,
873 // we treat it as a tri-state comparator.
875 // T is the type of the comparator object we want to check. U is the array
876 // element type that we'll be comparing.
878 // V is never passed, and is only used to allow us to specialize on the return
879 // value of the comparator function.
880 template <typename T
, typename U
, typename V
= int>
881 struct IsCompareMethod
: std::false_type
{};
883 template <typename T
, typename U
>
884 struct IsCompareMethod
<
885 T
, U
, decltype(std::declval
<T
>()(std::declval
<U
>(), std::declval
<U
>()))>
888 // These two wrappers allow us to use either a tri-state comparator, or an
889 // object with Equals() and LessThan() methods interchangeably. They provide a
890 // tri-state Compare() method, and Equals() method, and a LessThan() method.
892 // Depending on the type of the underlying comparator, they either pass these
893 // through directly, or synthesize them from the methods available on the
896 // Callers should always use the most-specific of these methods that match their
899 // Comparator wrapper for a tri-state comparator function
900 template <typename T
, typename U
, bool IsCompare
= IsCompareMethod
<T
, U
>::value
>
901 struct CompareWrapper
{
903 # pragma warning(push)
904 # pragma warning(disable : 4180) /* Silence "qualifier applied to function \
905 type has no meaning" warning */
907 MOZ_IMPLICIT
CompareWrapper(const T
& aComparator
)
908 : mComparator(aComparator
) {}
910 template <typename A
, typename B
>
911 int Compare(A
& aLeft
, B
& aRight
) const {
912 return mComparator(aLeft
, aRight
);
915 template <typename A
, typename B
>
916 bool Equals(A
& aLeft
, B
& aRight
) const {
917 return Compare(aLeft
, aRight
) == 0;
920 template <typename A
, typename B
>
921 bool LessThan(A
& aLeft
, B
& aRight
) const {
922 return Compare(aLeft
, aRight
) < 0;
925 const T
& mComparator
;
927 # pragma warning(pop)
931 // Comparator wrapper for a class with Equals() and LessThan() methods.
932 template <typename T
, typename U
>
933 struct CompareWrapper
<T
, U
, false> {
934 MOZ_IMPLICIT
CompareWrapper(const T
& aComparator
)
935 : mComparator(aComparator
) {}
937 template <typename A
, typename B
>
938 int Compare(A
& aLeft
, B
& aRight
) const {
939 if (Equals(aLeft
, aRight
)) {
942 return LessThan(aLeft
, aRight
) ? -1 : 1;
945 template <typename A
, typename B
>
946 bool Equals(A
& aLeft
, B
& aRight
) const {
947 return mComparator
.Equals(aLeft
, aRight
);
950 template <typename A
, typename B
>
951 bool LessThan(A
& aLeft
, B
& aRight
) const {
952 return mComparator
.LessThan(aLeft
, aRight
);
955 const T
& mComparator
;
958 } // namespace detail
961 // nsTArray_Impl contains most of the guts supporting nsTArray, FallibleTArray,
964 // The only situation in which you might need to use nsTArray_Impl in your code
965 // is if you're writing code which mutates a TArray which may or may not be
968 // Code which merely reads from a TArray which may or may not be infallible can
969 // simply cast the TArray to |const nsTArray&|; both fallible and infallible
970 // TArrays can be cast to |const nsTArray&|.
972 template <class E
, class Alloc
>
974 : public nsTArray_base
<Alloc
,
975 typename nsTArray_RelocationStrategy
<E
>::Type
>,
976 public nsTArray_TypedBase
<E
, nsTArray_Impl
<E
, Alloc
>> {
978 friend class nsTArray
<E
>;
980 typedef nsTArrayFallibleAllocator FallibleAlloc
;
981 typedef nsTArrayInfallibleAllocator InfallibleAlloc
;
984 typedef typename nsTArray_RelocationStrategy
<E
>::Type relocation_type
;
985 typedef nsTArray_base
<Alloc
, relocation_type
> base_type
;
986 typedef typename
base_type::size_type size_type
;
987 typedef typename
base_type::index_type index_type
;
989 typedef nsTArray_Impl
<E
, Alloc
> self_type
;
990 typedef nsTArrayElementTraits
<E
> elem_traits
;
991 typedef nsTArray_SafeElementAtHelper
<E
, self_type
> safeelementat_helper_type
;
992 typedef mozilla::ArrayIterator
<elem_type
&, self_type
> iterator
;
993 typedef mozilla::ArrayIterator
<const elem_type
&, self_type
> const_iterator
;
994 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
995 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
997 using base_type::EmptyHdr
;
998 using safeelementat_helper_type::SafeElementAt
;
1000 // A special value that is used to indicate an invalid or unknown index
1002 static const index_type NoIndex
= index_type(-1);
1004 using base_type::Length
;
1007 // Finalization method
1011 if (!base_type::IsEmpty()) {
1012 ClearAndRetainStorage();
1014 // mHdr cleanup will be handled by base destructor
1018 // Initialization methods
1021 nsTArray_Impl() = default;
1023 // Initialize this array and pre-allocate some number of elements.
1024 explicit nsTArray_Impl(size_type aCapacity
) { SetCapacity(aCapacity
); }
1026 // Initialize this array with an r-value.
1027 // Allow different types of allocators, since the allocator doesn't matter.
1028 template <typename Allocator
>
1029 explicit nsTArray_Impl(nsTArray_Impl
<E
, Allocator
>&& aOther
) noexcept
{
1030 // We cannot be a (Copyable)AutoTArray because that overrides this ctor.
1031 MOZ_ASSERT(!this->IsAutoArray());
1033 // This does not use SwapArrayElements because that's unnecessarily complex.
1034 this->MoveConstructNonAutoArray(aOther
, sizeof(elem_type
),
1035 MOZ_ALIGNOF(elem_type
));
1038 // The array's copy-constructor performs a 'deep' copy of the given array.
1039 // @param aOther The array object to copy.
1041 // It's very important that we declare this method as taking |const
1042 // self_type&| as opposed to taking |const nsTArray_Impl<E, OtherAlloc>| for
1043 // an arbitrary OtherAlloc.
1045 // If we don't declare a constructor taking |const self_type&|, C++ generates
1046 // a copy-constructor for this class which merely copies the object's
1047 // members, which is obviously wrong.
1049 // You can pass an nsTArray_Impl<E, OtherAlloc> to this method because
1050 // nsTArray_Impl<E, X> can be cast to const nsTArray_Impl<E, Y>&. So the
1051 // effect on the API is the same as if we'd declared this method as taking
1052 // |const nsTArray_Impl<E, OtherAlloc>&|.
1053 nsTArray_Impl(const nsTArray_Impl
&) = default;
1055 // Allow converting to a const array with a different kind of allocator,
1056 // Since the allocator doesn't matter for const arrays
1057 template <typename Allocator
>
1058 [[nodiscard
]] operator const nsTArray_Impl
<E
, Allocator
>&() const& {
1059 return *reinterpret_cast<const nsTArray_Impl
<E
, Allocator
>*>(this);
1061 // And we have to do this for our subclasses too
1062 [[nodiscard
]] operator const nsTArray
<E
>&() const& {
1063 return *reinterpret_cast<const nsTArray
<E
>*>(this);
1065 [[nodiscard
]] operator const FallibleTArray
<E
>&() const& {
1066 return *reinterpret_cast<const FallibleTArray
<E
>*>(this);
1069 // The array's assignment operator performs a 'deep' copy of the given
1070 // array. It is optimized to reuse existing storage if possible.
1071 // @param aOther The array object to copy.
1072 nsTArray_Impl
& operator=(const nsTArray_Impl
&) = default;
1074 // The array's move assignment operator steals the underlying data from
1076 // @param other The array object to move from.
1077 self_type
& operator=(self_type
&& aOther
) {
1078 if (this != &aOther
) {
1080 this->MoveInit(aOther
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
1085 // Return true if this array has the same length and the same
1086 // elements as |aOther|.
1087 template <typename Allocator
>
1088 [[nodiscard
]] bool operator==(
1089 const nsTArray_Impl
<E
, Allocator
>& aOther
) const {
1090 size_type len
= Length();
1091 if (len
!= aOther
.Length()) {
1095 // XXX std::equal would be as fast or faster here
1096 for (index_type i
= 0; i
< len
; ++i
) {
1097 if (!(operator[](i
) == aOther
[i
])) {
1105 // Return true if this array does not have the same length and the same
1106 // elements as |aOther|.
1107 [[nodiscard
]] bool operator!=(const self_type
& aOther
) const {
1108 return !operator==(aOther
);
1111 // If Alloc == FallibleAlloc, ReplaceElementsAt might fail, without a way to
1112 // signal this to the caller, so we disallow copying via operator=. Callers
1113 // should use ReplaceElementsAt with a fallible argument instead, and check
1115 template <typename Allocator
,
1116 typename
= std::enable_if_t
<std::is_same_v
<Alloc
, InfallibleAlloc
>,
1118 self_type
& operator=(const nsTArray_Impl
<E
, Allocator
>& aOther
) {
1119 AssignInternal
<InfallibleAlloc
>(aOther
.Elements(), aOther
.Length());
1123 template <typename Allocator
>
1124 self_type
& operator=(nsTArray_Impl
<E
, Allocator
>&& aOther
) {
1126 this->MoveInit(aOther
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
1130 // @return The amount of memory used by this nsTArray_Impl, excluding
1131 // sizeof(*this). If you want to measure anything hanging off the array, you
1132 // must iterate over the elements and measure them individually; hence the
1133 // "Shallow" prefix.
1134 [[nodiscard
]] size_t ShallowSizeOfExcludingThis(
1135 mozilla::MallocSizeOf aMallocSizeOf
) const {
1136 if (this->UsesAutoArrayBuffer() || this->HasEmptyHeader()) {
1139 return aMallocSizeOf(this->Hdr());
1142 // @return The amount of memory used by this nsTArray_Impl, including
1143 // sizeof(*this). If you want to measure anything hanging off the array, you
1144 // must iterate over the elements and measure them individually; hence the
1145 // "Shallow" prefix.
1146 [[nodiscard
]] size_t ShallowSizeOfIncludingThis(
1147 mozilla::MallocSizeOf aMallocSizeOf
) const {
1148 return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf
);
1155 // This method provides direct access to the array elements.
1156 // @return A pointer to the first element of the array. If the array is
1157 // empty, then this pointer must not be dereferenced.
1158 [[nodiscard
]] elem_type
* Elements() MOZ_NONNULL_RETURN
{
1159 return reinterpret_cast<elem_type
*>(Hdr() + 1);
1162 // This method provides direct, readonly access to the array elements.
1163 // @return A pointer to the first element of the array. If the array is
1164 // empty, then this pointer must not be dereferenced.
1165 [[nodiscard
]] const elem_type
* Elements() const MOZ_NONNULL_RETURN
{
1166 return reinterpret_cast<const elem_type
*>(Hdr() + 1);
1169 // This method provides direct access to an element of the array. The given
1170 // index must be within the array bounds.
1171 // @param aIndex The index of an element in the array.
1172 // @return A reference to the i'th element of the array.
1173 [[nodiscard
]] elem_type
& ElementAt(index_type aIndex
) {
1174 if (MOZ_UNLIKELY(aIndex
>= Length())) {
1175 InvalidArrayIndex_CRASH(aIndex
, Length());
1177 return Elements()[aIndex
];
1180 // This method provides direct, readonly access to an element of the array
1181 // The given index must be within the array bounds.
1182 // @param aIndex The index of an element in the array.
1183 // @return A const reference to the i'th element of the array.
1184 [[nodiscard
]] const elem_type
& ElementAt(index_type aIndex
) const {
1185 if (MOZ_UNLIKELY(aIndex
>= Length())) {
1186 InvalidArrayIndex_CRASH(aIndex
, Length());
1188 return Elements()[aIndex
];
1191 // This method provides direct access to an element of the array in a bounds
1192 // safe manner. If the requested index is out of bounds the provided default
1193 // value is returned.
1194 // @param aIndex The index of an element in the array.
1195 // @param aDef The value to return if the index is out of bounds.
1196 [[nodiscard
]] elem_type
& SafeElementAt(index_type aIndex
, elem_type
& aDef
) {
1197 return aIndex
< Length() ? Elements()[aIndex
] : aDef
;
1200 // This method provides direct access to an element of the array in a bounds
1201 // safe manner. If the requested index is out of bounds the provided default
1202 // value is returned.
1203 // @param aIndex The index of an element in the array.
1204 // @param aDef The value to return if the index is out of bounds.
1205 [[nodiscard
]] const elem_type
& SafeElementAt(index_type aIndex
,
1206 const elem_type
& aDef
) const {
1207 return aIndex
< Length() ? Elements()[aIndex
] : aDef
;
1210 // Shorthand for ElementAt(aIndex)
1211 [[nodiscard
]] elem_type
& operator[](index_type aIndex
) {
1212 return ElementAt(aIndex
);
1215 // Shorthand for ElementAt(aIndex)
1216 [[nodiscard
]] const elem_type
& operator[](index_type aIndex
) const {
1217 return ElementAt(aIndex
);
1220 // Shorthand for ElementAt(length - 1)
1221 [[nodiscard
]] elem_type
& LastElement() { return ElementAt(Length() - 1); }
1223 // Shorthand for ElementAt(length - 1)
1224 [[nodiscard
]] const elem_type
& LastElement() const {
1225 return ElementAt(Length() - 1);
1228 // Shorthand for SafeElementAt(length - 1, def)
1229 [[nodiscard
]] elem_type
& SafeLastElement(elem_type
& aDef
) {
1230 return SafeElementAt(Length() - 1, aDef
);
1233 // Shorthand for SafeElementAt(length - 1, def)
1234 [[nodiscard
]] const elem_type
& SafeLastElement(const elem_type
& aDef
) const {
1235 return SafeElementAt(Length() - 1, aDef
);
1238 // Methods for range-based for loops.
1239 [[nodiscard
]] iterator
begin() { return iterator(*this, 0); }
1240 [[nodiscard
]] const_iterator
begin() const {
1241 return const_iterator(*this, 0);
1243 [[nodiscard
]] const_iterator
cbegin() const { return begin(); }
1244 [[nodiscard
]] iterator
end() { return iterator(*this, Length()); }
1245 [[nodiscard
]] const_iterator
end() const {
1246 return const_iterator(*this, Length());
1248 [[nodiscard
]] const_iterator
cend() const { return end(); }
1250 // Methods for reverse iterating.
1251 [[nodiscard
]] reverse_iterator
rbegin() { return reverse_iterator(end()); }
1252 [[nodiscard
]] const_reverse_iterator
rbegin() const {
1253 return const_reverse_iterator(end());
1255 [[nodiscard
]] const_reverse_iterator
crbegin() const { return rbegin(); }
1256 [[nodiscard
]] reverse_iterator
rend() { return reverse_iterator(begin()); }
1257 [[nodiscard
]] const_reverse_iterator
rend() const {
1258 return const_reverse_iterator(begin());
1260 [[nodiscard
]] const_reverse_iterator
crend() const { return rend(); }
1264 [[nodiscard
]] operator mozilla::Span
<elem_type
>() {
1265 return mozilla::Span
<elem_type
>(Elements(), Length());
1268 [[nodiscard
]] operator mozilla::Span
<const elem_type
>() const {
1269 return mozilla::Span
<const elem_type
>(Elements(), Length());
1276 // This method searches for the first element in this array that is equal
1277 // to the given element.
1278 // @param aItem The item to search for.
1279 // @param aComp The Comparator used to determine element equality.
1280 // @return true if the element was found.
1281 template <class Item
, class Comparator
>
1282 [[nodiscard
]] bool Contains(const Item
& aItem
,
1283 const Comparator
& aComp
) const {
1285 aItem
, 0, aComp
, []() { return true; }, []() { return false; });
1288 // Like Contains(), but assumes a sorted array.
1289 template <class Item
, class Comparator
>
1290 [[nodiscard
]] bool ContainsSorted(const Item
& aItem
,
1291 const Comparator
& aComp
) const {
1292 return BinaryIndexOf(aItem
, aComp
) != NoIndex
;
1295 // This method searches for the first element in this array that is equal
1296 // to the given element. This method assumes that 'operator==' is defined
1298 // @param aItem The item to search for.
1299 // @return true if the element was found.
1300 template <class Item
>
1301 [[nodiscard
]] bool Contains(const Item
& aItem
) const {
1302 return Contains(aItem
, nsDefaultComparator
<elem_type
, Item
>());
1305 // Like Contains(), but assumes a sorted array.
1306 template <class Item
>
1307 [[nodiscard
]] bool ContainsSorted(const Item
& aItem
) const {
1308 return BinaryIndexOf(aItem
) != NoIndex
;
1311 // This method searches for the offset of the first element in this
1312 // array that is equal to the given element.
1313 // @param aItem The item to search for.
1314 // @param aStart The index to start from.
1315 // @param aComp The Comparator used to determine element equality.
1316 // @return The index of the found element or NoIndex if not found.
1317 template <class Item
, class Comparator
>
1318 [[nodiscard
]] index_type
IndexOf(const Item
& aItem
, index_type aStart
,
1319 const Comparator
& aComp
) const {
1320 ::detail::CompareWrapper
<Comparator
, Item
> comp(aComp
);
1322 const elem_type
* iter
= Elements() + aStart
;
1323 const elem_type
* iend
= Elements() + Length();
1324 for (; iter
!= iend
; ++iter
) {
1325 if (comp
.Equals(*iter
, aItem
)) {
1326 return index_type(iter
- Elements());
1332 // This method searches for the offset of the first element in this
1333 // array that is equal to the given element. This method assumes
1334 // that 'operator==' is defined for elem_type.
1335 // @param aItem The item to search for.
1336 // @param aStart The index to start from.
1337 // @return The index of the found element or NoIndex if not found.
1338 template <class Item
>
1339 [[nodiscard
]] index_type
IndexOf(const Item
& aItem
,
1340 index_type aStart
= 0) const {
1341 return IndexOf(aItem
, aStart
, nsDefaultComparator
<elem_type
, Item
>());
1344 // This method searches for the offset of the last element in this
1345 // array that is equal to the given element.
1346 // @param aItem The item to search for.
1347 // @param aStart The index to start from. If greater than or equal to the
1348 // length of the array, then the entire array is searched.
1349 // @param aComp The Comparator used to determine element equality.
1350 // @return The index of the found element or NoIndex if not found.
1351 template <class Item
, class Comparator
>
1352 [[nodiscard
]] index_type
LastIndexOf(const Item
& aItem
, index_type aStart
,
1353 const Comparator
& aComp
) const {
1354 ::detail::CompareWrapper
<Comparator
, Item
> comp(aComp
);
1356 size_type endOffset
= aStart
>= Length() ? Length() : aStart
+ 1;
1357 const elem_type
* iend
= Elements() - 1;
1358 const elem_type
* iter
= iend
+ endOffset
;
1359 for (; iter
!= iend
; --iter
) {
1360 if (comp
.Equals(*iter
, aItem
)) {
1361 return index_type(iter
- Elements());
1367 // This method searches for the offset of the last element in this
1368 // array that is equal to the given element. This method assumes
1369 // that 'operator==' is defined for elem_type.
1370 // @param aItem The item to search for.
1371 // @param aStart The index to start from. If greater than or equal to the
1372 // length of the array, then the entire array is searched.
1373 // @return The index of the found element or NoIndex if not found.
1374 template <class Item
>
1375 [[nodiscard
]] index_type
LastIndexOf(const Item
& aItem
,
1376 index_type aStart
= NoIndex
) const {
1377 return LastIndexOf(aItem
, aStart
, nsDefaultComparator
<elem_type
, Item
>());
1380 // This method searches for the offset for the element in this array
1381 // that is equal to the given element. The array is assumed to be sorted.
1382 // If there is more than one equivalent element, there is no guarantee
1383 // on which one will be returned.
1384 // @param aItem The item to search for.
1385 // @param aComp The Comparator used.
1386 // @return The index of the found element or NoIndex if not found.
1387 template <class Item
, class Comparator
>
1388 [[nodiscard
]] index_type
BinaryIndexOf(const Item
& aItem
,
1389 const Comparator
& aComp
) const {
1390 using mozilla::BinarySearchIf
;
1391 ::detail::CompareWrapper
<Comparator
, Item
> comp(aComp
);
1394 bool found
= BinarySearchIf(
1395 Elements(), 0, Length(),
1396 // Note: We pass the Compare() args here in reverse order and negate the
1397 // results for compatibility reasons. Some existing callers use Equals()
1398 // functions with first arguments which match aElement but not aItem, or
1399 // second arguments that match aItem but not aElement. To accommodate
1400 // those callers, we preserve the argument order of the older version of
1401 // this API. These callers, however, should be fixed, and this special
1403 [&](const elem_type
& aElement
) {
1404 return -comp
.Compare(aElement
, aItem
);
1407 return found
? index
: NoIndex
;
1410 // This method searches for the offset for the element in this array
1411 // that is equal to the given element. The array is assumed to be sorted.
1412 // This method assumes that 'operator==' and 'operator<' are defined.
1413 // @param aItem The item to search for.
1414 // @return The index of the found element or NoIndex if not found.
1415 template <class Item
>
1416 [[nodiscard
]] index_type
BinaryIndexOf(const Item
& aItem
) const {
1417 return BinaryIndexOf(aItem
, nsDefaultComparator
<elem_type
, Item
>());
1424 template <typename ActualAlloc
, class Item
>
1425 typename
ActualAlloc::ResultType
AssignInternal(const Item
* aArray
,
1426 size_type aArrayLen
);
1429 template <class Allocator
, typename ActualAlloc
= Alloc
>
1430 [[nodiscard
]] typename
ActualAlloc::ResultType
Assign(
1431 const nsTArray_Impl
<E
, Allocator
>& aOther
) {
1432 return AssignInternal
<ActualAlloc
>(aOther
.Elements(), aOther
.Length());
1435 template <class Allocator
>
1436 [[nodiscard
]] bool Assign(const nsTArray_Impl
<E
, Allocator
>& aOther
,
1437 const mozilla::fallible_t
&) {
1438 return Assign
<Allocator
, FallibleAlloc
>(aOther
);
1441 template <class Allocator
>
1442 void Assign(nsTArray_Impl
<E
, Allocator
>&& aOther
) {
1444 this->MoveInit(aOther
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
1447 // This method call the destructor on each element of the array, empties it,
1448 // but does not shrink the array's capacity.
1449 // See also SetLengthAndRetainStorage.
1450 // Make sure to call Compact() if needed to avoid keeping a huge array
1452 void ClearAndRetainStorage() {
1453 if (this->HasEmptyHeader()) {
1457 DestructRange(0, Length());
1458 base_type::mHdr
->mLength
= 0;
1461 // This method modifies the length of the array, but unlike SetLength
1462 // it doesn't deallocate/reallocate the current internal storage.
1463 // The new length MUST be shorter than or equal to the current capacity.
1464 // If the new length is larger than the existing length of the array,
1465 // then new elements will be constructed using elem_type's default
1466 // constructor. If shorter, elements will be destructed and removed.
1467 // See also ClearAndRetainStorage.
1468 // @param aNewLen The desired length of this array.
1469 void SetLengthAndRetainStorage(size_type aNewLen
) {
1470 MOZ_ASSERT(aNewLen
<= base_type::Capacity());
1471 size_type oldLen
= Length();
1472 if (aNewLen
> oldLen
) {
1473 /// XXX(Bug 1631367) SetLengthAndRetainStorage should be disabled for
1475 InsertElementsAtInternal
<InfallibleAlloc
>(oldLen
, aNewLen
- oldLen
);
1478 if (aNewLen
< oldLen
) {
1479 DestructRange(aNewLen
, oldLen
- aNewLen
);
1480 base_type::mHdr
->mLength
= aNewLen
;
1484 // This method replaces a range of elements in this array.
1485 // @param aStart The starting index of the elements to replace.
1486 // @param aCount The number of elements to replace. This may be zero to
1487 // insert elements without removing any existing elements.
1488 // @param aArray The values to copy into this array. Must be non-null,
1489 // and these elements must not already exist in the array
1491 // @param aArrayLen The number of values to copy into this array.
1492 // @return A pointer to the new elements in the array, or null if
1493 // the operation failed due to insufficient memory.
1495 template <typename ActualAlloc
, class Item
>
1496 elem_type
* ReplaceElementsAtInternal(index_type aStart
, size_type aCount
,
1497 const Item
* aArray
, size_type aArrayLen
);
1500 template <class Item
>
1501 [[nodiscard
]] elem_type
* ReplaceElementsAt(index_type aStart
,
1504 size_type aArrayLen
,
1505 const mozilla::fallible_t
&) {
1506 return ReplaceElementsAtInternal
<FallibleAlloc
>(aStart
, aCount
, aArray
,
1510 // A variation on the ReplaceElementsAt method defined above.
1511 template <class Item
>
1512 [[nodiscard
]] elem_type
* ReplaceElementsAt(index_type aStart
,
1514 const nsTArray
<Item
>& aArray
,
1515 const mozilla::fallible_t
&) {
1516 return ReplaceElementsAtInternal
<FallibleAlloc
>(aStart
, aCount
, aArray
);
1519 template <class Item
>
1520 [[nodiscard
]] elem_type
* ReplaceElementsAt(index_type aStart
,
1522 mozilla::Span
<Item
> aSpan
,
1523 const mozilla::fallible_t
&) {
1524 return ReplaceElementsAtInternal
<FallibleAlloc
>(aStart
, aCount
, aSpan
);
1527 // A variation on the ReplaceElementsAt method defined above.
1528 template <class Item
>
1529 [[nodiscard
]] elem_type
* ReplaceElementsAt(index_type aStart
,
1532 const mozilla::fallible_t
&) {
1533 return ReplaceElementsAtInternal
<FallibleAlloc
>(aStart
, aCount
, aItem
);
1536 // A variation on the ReplaceElementsAt method defined above.
1537 template <class Item
>
1538 mozilla::NotNull
<elem_type
*> ReplaceElementAt(index_type aIndex
,
1540 elem_type
* const elem
= &ElementAt(aIndex
);
1541 elem_traits::Destruct(elem
);
1542 elem_traits::Construct(elem
, std::forward
<Item
>(aItem
));
1543 return mozilla::WrapNotNullUnchecked(elem
);
1546 // InsertElementsAt is ReplaceElementsAt with 0 elements to replace.
1547 // XXX Provide a proper documentation of InsertElementsAt.
1548 template <class Item
>
1549 [[nodiscard
]] elem_type
* InsertElementsAt(index_type aIndex
,
1551 size_type aArrayLen
,
1552 const mozilla::fallible_t
&) {
1553 return ReplaceElementsAtInternal
<FallibleAlloc
>(aIndex
, 0, aArray
,
1557 template <class Item
, class Allocator
>
1558 [[nodiscard
]] elem_type
* InsertElementsAt(
1559 index_type aIndex
, const nsTArray_Impl
<Item
, Allocator
>& aArray
,
1560 const mozilla::fallible_t
&) {
1561 return ReplaceElementsAtInternal
<FallibleAlloc
>(
1562 aIndex
, 0, aArray
.Elements(), aArray
.Length());
1565 template <class Item
>
1566 [[nodiscard
]] elem_type
* InsertElementsAt(index_type aIndex
,
1567 mozilla::Span
<Item
> aSpan
,
1568 const mozilla::fallible_t
&) {
1569 return ReplaceElementsAtInternal
<FallibleAlloc
>(aIndex
, 0, aSpan
.Elements(),
1574 template <typename ActualAlloc
>
1575 elem_type
* InsertElementAtInternal(index_type aIndex
);
1577 // Insert a new element without copy-constructing. This is useful to avoid
1579 // @return A pointer to the newly inserted element, or null on OOM.
1581 [[nodiscard
]] elem_type
* InsertElementAt(index_type aIndex
,
1582 const mozilla::fallible_t
&) {
1583 return InsertElementAtInternal
<FallibleAlloc
>(aIndex
);
1587 template <typename ActualAlloc
, class Item
>
1588 elem_type
* InsertElementAtInternal(index_type aIndex
, Item
&& aItem
);
1590 // Insert a new element, move constructing if possible.
1592 template <class Item
>
1593 [[nodiscard
]] elem_type
* InsertElementAt(index_type aIndex
, Item
&& aItem
,
1594 const mozilla::fallible_t
&) {
1595 return InsertElementAtInternal
<FallibleAlloc
>(aIndex
,
1596 std::forward
<Item
>(aItem
));
1599 // Reconstruct the element at the given index, and return a pointer to the
1600 // reconstructed element. This will destroy the existing element and
1601 // default-construct a new one, giving you a state much like what single-arg
1602 // InsertElementAt(), or no-arg AppendElement() does, but without changing the
1603 // length of the array.
1605 // array[idx] = elem_type()
1607 // would accomplish the same thing as long as elem_type has the appropriate
1608 // moving operator=, but some types don't for various reasons.
1609 mozilla::NotNull
<elem_type
*> ReconstructElementAt(index_type aIndex
) {
1610 elem_type
* elem
= &ElementAt(aIndex
);
1611 elem_traits::Destruct(elem
);
1612 elem_traits::Construct(elem
);
1613 return mozilla::WrapNotNullUnchecked(elem
);
1616 // This method searches for the smallest index of an element that is strictly
1617 // greater than |aItem|. If |aItem| is inserted at this index, the array will
1618 // remain sorted and |aItem| would come after all elements that are equal to
1619 // it. If |aItem| is greater than or equal to all elements in the array, the
1620 // array length is returned.
1622 // Note that consumers who want to know whether there are existing items equal
1623 // to |aItem| in the array can just check that the return value here is > 0
1624 // and indexing into the previous slot gives something equal to |aItem|.
1627 // @param aItem The item to search for.
1628 // @param aComp The Comparator used.
1629 // @return The index of greatest element <= to |aItem|
1630 // @precondition The array is sorted
1631 template <class Item
, class Comparator
>
1632 [[nodiscard
]] index_type
IndexOfFirstElementGt(
1633 const Item
& aItem
, const Comparator
& aComp
) const {
1634 using mozilla::BinarySearchIf
;
1635 ::detail::CompareWrapper
<Comparator
, Item
> comp(aComp
);
1639 Elements(), 0, Length(),
1640 [&](const elem_type
& aElement
) {
1641 return comp
.Compare(aElement
, aItem
) <= 0 ? 1 : -1;
1647 // A variation on the IndexOfFirstElementGt method defined above.
1648 template <class Item
>
1649 [[nodiscard
]] index_type
IndexOfFirstElementGt(const Item
& aItem
) const {
1650 return IndexOfFirstElementGt(aItem
, nsDefaultComparator
<elem_type
, Item
>());
1654 template <typename ActualAlloc
, class Item
, class Comparator
>
1655 elem_type
* InsertElementSortedInternal(Item
&& aItem
,
1656 const Comparator
& aComp
) {
1657 index_type index
= IndexOfFirstElementGt
<Item
, Comparator
>(aItem
, aComp
);
1658 return InsertElementAtInternal
<ActualAlloc
>(index
,
1659 std::forward
<Item
>(aItem
));
1662 // Inserts |aItem| at such an index to guarantee that if the array
1663 // was previously sorted, it will remain sorted after this
1666 template <class Item
, class Comparator
>
1667 [[nodiscard
]] elem_type
* InsertElementSorted(Item
&& aItem
,
1668 const Comparator
& aComp
,
1669 const mozilla::fallible_t
&) {
1670 return InsertElementSortedInternal
<FallibleAlloc
>(std::forward
<Item
>(aItem
),
1674 // A variation on the InsertElementSorted method defined above.
1676 template <class Item
>
1677 [[nodiscard
]] elem_type
* InsertElementSorted(Item
&& aItem
,
1678 const mozilla::fallible_t
&) {
1679 return InsertElementSortedInternal
<FallibleAlloc
>(
1680 std::forward
<Item
>(aItem
), nsDefaultComparator
<elem_type
, Item
>{});
1684 template <typename ActualAlloc
, class Item
>
1685 elem_type
* AppendElementsInternal(const Item
* aArray
, size_type aArrayLen
);
1687 // This method appends elements to the end of this array.
1688 // @param aArray The elements to append to this array.
1689 // @param aArrayLen The number of elements to append to this array.
1690 // @return A pointer to the new elements in the array, or null if
1691 // the operation failed due to insufficient memory.
1693 template <class Item
>
1694 [[nodiscard
]] elem_type
* AppendElements(const Item
* aArray
,
1695 size_type aArrayLen
,
1696 const mozilla::fallible_t
&) {
1697 return AppendElementsInternal
<FallibleAlloc
>(aArray
, aArrayLen
);
1700 template <class Item
>
1701 [[nodiscard
]] elem_type
* AppendElements(mozilla::Span
<Item
> aSpan
,
1702 const mozilla::fallible_t
&) {
1703 return AppendElementsInternal
<FallibleAlloc
>(aSpan
.Elements(),
1707 // A variation on the AppendElements method defined above.
1708 template <class Item
, class Allocator
>
1709 [[nodiscard
]] elem_type
* AppendElements(
1710 const nsTArray_Impl
<Item
, Allocator
>& aArray
,
1711 const mozilla::fallible_t
&) {
1712 return AppendElementsInternal
<FallibleAlloc
>(aArray
.Elements(),
1717 template <typename ActualAlloc
, class Item
, class Allocator
>
1718 elem_type
* AppendElementsInternal(nsTArray_Impl
<Item
, Allocator
>&& aArray
);
1720 // Move all elements from another array to the end of this array.
1721 // @return A pointer to the newly appended elements, or null on OOM.
1723 template <class Item
, class Allocator
>
1724 [[nodiscard
]] elem_type
* AppendElements(
1725 nsTArray_Impl
<Item
, Allocator
>&& aArray
, const mozilla::fallible_t
&) {
1726 return AppendElementsInternal
<FallibleAlloc
>(std::move(aArray
));
1729 // Append a new element, constructed in place from the provided arguments.
1731 template <typename ActualAlloc
, class... Args
>
1732 elem_type
* EmplaceBackInternal(Args
&&... aItem
);
1735 template <class... Args
>
1736 [[nodiscard
]] elem_type
* EmplaceBack(const mozilla::fallible_t
&,
1738 return EmplaceBackInternal
<FallibleAlloc
, Args
...>(
1739 std::forward
<Args
>(aArgs
)...);
1743 template <typename ActualAlloc
, class Item
>
1744 elem_type
* AppendElementInternal(Item
&& aItem
);
1746 // Append a new element, move constructing if possible.
1748 template <class Item
>
1749 [[nodiscard
]] elem_type
* AppendElement(Item
&& aItem
,
1750 const mozilla::fallible_t
&) {
1751 return AppendElementInternal
<FallibleAlloc
>(std::forward
<Item
>(aItem
));
1755 template <typename ActualAlloc
>
1756 elem_type
* AppendElementsInternal(size_type aCount
) {
1757 if (!ActualAlloc::Successful(this->template ExtendCapacity
<ActualAlloc
>(
1758 Length(), aCount
, sizeof(elem_type
)))) {
1761 elem_type
* elems
= Elements() + Length();
1763 for (i
= 0; i
< aCount
; ++i
) {
1764 elem_traits::Construct(elems
+ i
);
1766 this->IncrementLength(aCount
);
1770 // Append new elements without copy-constructing. This is useful to avoid
1772 // @return A pointer to the newly appended elements, or null on OOM.
1774 [[nodiscard
]] elem_type
* AppendElements(size_type aCount
,
1775 const mozilla::fallible_t
&) {
1776 return AppendElementsInternal
<FallibleAlloc
>(aCount
);
1780 // Append a new element without copy-constructing. This is useful to avoid
1782 // @return A pointer to the newly appended element, or null on OOM.
1784 [[nodiscard
]] elem_type
* AppendElement(const mozilla::fallible_t
&) {
1785 return AppendElements(1, mozilla::fallible
);
1788 // This method removes a single element from this array, like
1789 // std::vector::erase.
1790 // @param pos to the element to remove
1791 const_iterator
RemoveElementAt(const_iterator pos
) {
1792 MOZ_ASSERT(pos
.GetArray() == this);
1794 RemoveElementAt(pos
.GetIndex());
1798 // This method removes a range of elements from this array, like
1799 // std::vector::erase.
1800 // @param first iterator to the first of elements to remove
1801 // @param last iterator to the last of elements to remove
1802 const_iterator
RemoveElementsRange(const_iterator first
,
1803 const_iterator last
) {
1804 MOZ_ASSERT(first
.GetArray() == this);
1805 MOZ_ASSERT(last
.GetArray() == this);
1806 MOZ_ASSERT(last
.GetIndex() >= first
.GetIndex());
1808 RemoveElementsAt(first
.GetIndex(), last
.GetIndex() - first
.GetIndex());
1812 // This method removes a range of elements from this array.
1813 // @param aStart The starting index of the elements to remove.
1814 // @param aCount The number of elements to remove.
1815 void RemoveElementsAt(index_type aStart
, size_type aCount
);
1818 // Remove a range of elements from this array, but do not check that
1819 // the range is in bounds.
1820 // @param aStart The starting index of the elements to remove.
1821 // @param aCount The number of elements to remove.
1822 void RemoveElementsAtUnsafe(index_type aStart
, size_type aCount
);
1825 // A variation on the RemoveElementsAt method defined above.
1826 void RemoveElementAt(index_type aIndex
) { RemoveElementsAt(aIndex
, 1); }
1828 // A variation on RemoveElementAt that removes the last element.
1829 void RemoveLastElement() { RemoveLastElements(1); }
1831 // A variation on RemoveElementsAt that removes the last 'aCount' elements.
1832 void RemoveLastElements(const size_type aCount
) {
1833 // This assertion is redundant, but produces a better error message than the
1834 // release assertion within TruncateLength.
1835 MOZ_ASSERT(aCount
<= Length());
1836 TruncateLength(Length() - aCount
);
1839 // Removes the last element of the array and returns a copy of it.
1840 [[nodiscard
]] elem_type
PopLastElement() {
1841 // This function intentionally does not call ElementsAt and calls
1842 // TruncateLengthUnsafe directly to avoid multiple release checks for
1844 // This debug assertion is redundant, but produces a better error message
1845 // than the release assertion below.
1846 MOZ_ASSERT(!base_type::IsEmpty());
1847 const size_type oldLen
= Length();
1848 if (MOZ_UNLIKELY(0 == oldLen
)) {
1849 InvalidArrayIndex_CRASH(1, 0);
1851 elem_type elem
= std::move(Elements()[oldLen
- 1]);
1852 TruncateLengthUnsafe(oldLen
- 1);
1856 // This method performs index-based removals from an array without preserving
1857 // the order of the array. This is useful if you are using the array as a
1858 // set-like data structure.
1860 // These removals are efficient, as they move as few elements as possible. At
1861 // most N elements, where N is the number of removed elements, will have to
1866 // When removing an element from the end of the array, it can be removed in
1867 // place, by destroying it and decrementing the length.
1869 // [ 1, 2, 3 ] => [ 1, 2 ]
1872 // When removing any other single element, it is removed by swapping it with
1873 // the last element, and then decrementing the length as before.
1875 // [ 1, 2, 3, 4, 5, 6 ] => [ 1, 6, 3, 4, 5 ]
1878 // This method also supports efficiently removing a range of elements. If they
1879 // are at the end, then they can all be removed like in the one element case.
1881 // [ 1, 2, 3, 4, 5, 6 ] => [ 1, 2 ]
1884 // If more elements are removed than exist after the removed section, the
1885 // remaining elements will be shifted down like in a normal removal.
1887 // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 2, 7, 8 ]
1890 // And if fewer elements are removed than exist after the removed section,
1891 // elements will be moved from the end of the array to fill the vacated space.
1893 // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 7, 8, 4, 5, 6 ]
1896 // @param aStart The starting index of the elements to remove. @param aCount
1897 // The number of elements to remove.
1898 void UnorderedRemoveElementsAt(index_type aStart
, size_type aCount
);
1900 // A variation on the UnorderedRemoveElementsAt method defined above to remove
1901 // a single element. This operation is sometimes called `SwapRemove`.
1903 // This method is O(1), but does not preserve the order of the elements.
1904 void UnorderedRemoveElementAt(index_type aIndex
) {
1905 UnorderedRemoveElementsAt(aIndex
, 1);
1909 ClearAndRetainStorage();
1910 base_type::ShrinkCapacityToZero(sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
1913 // This method removes elements based on the return value of the
1914 // callback function aPredicate. If the function returns true for
1915 // an element, the element is removed. aPredicate will be called
1916 // for each element in order. It is not safe to access the array
1917 // inside aPredicate.
1918 template <typename Predicate
>
1919 void RemoveElementsBy(Predicate aPredicate
);
1921 // This helper function combines IndexOf with RemoveElementAt to "search
1922 // and destroy" the first element that is equal to the given element.
1923 // @param aItem The item to search for.
1924 // @param aComp The Comparator used to determine element equality.
1925 // @return true if the element was found
1926 template <class Item
, class Comparator
>
1927 bool RemoveElement(const Item
& aItem
, const Comparator
& aComp
) {
1928 index_type i
= IndexOf(aItem
, 0, aComp
);
1933 RemoveElementsAtUnsafe(i
, 1);
1937 // A variation on the RemoveElement method defined above that assumes
1938 // that 'operator==' is defined for elem_type.
1939 template <class Item
>
1940 bool RemoveElement(const Item
& aItem
) {
1941 return RemoveElement(aItem
, nsDefaultComparator
<elem_type
, Item
>());
1944 // This helper function combines IndexOfFirstElementGt with
1945 // RemoveElementAt to "search and destroy" the last element that
1946 // is equal to the given element.
1947 // @param aItem The item to search for.
1948 // @param aComp The Comparator used to determine element equality.
1949 // @return true if the element was found
1950 template <class Item
, class Comparator
>
1951 bool RemoveElementSorted(const Item
& aItem
, const Comparator
& aComp
) {
1952 index_type index
= IndexOfFirstElementGt(aItem
, aComp
);
1953 if (index
> 0 && aComp
.Equals(ElementAt(index
- 1), aItem
)) {
1954 RemoveElementsAtUnsafe(index
- 1, 1);
1960 // A variation on the RemoveElementSorted method defined above.
1961 template <class Item
>
1962 bool RemoveElementSorted(const Item
& aItem
) {
1963 return RemoveElementSorted(aItem
, nsDefaultComparator
<elem_type
, Item
>());
1966 // This method causes the elements contained in this array and the given
1967 // array to be swapped.
1968 template <class Allocator
>
1969 void SwapElements(nsTArray_Impl
<E
, Allocator
>& aOther
) {
1970 // The only case this might fail were if someone called this with a
1971 // AutoTArray upcast to nsTArray_Impl, under the conditions mentioned in the
1972 // overload for AutoTArray below.
1973 this->template SwapArrayElements
<InfallibleAlloc
>(aOther
, sizeof(elem_type
),
1974 MOZ_ALIGNOF(elem_type
));
1978 void SwapElements(AutoTArray
<E
, N
>& aOther
) {
1979 // Allocation might fail if Alloc==FallibleAlloc and
1980 // Allocator==InfallibleAlloc and aOther uses auto storage. Allow this for
1981 // small inline sizes, and crash in the rare case of a small OOM error.
1982 static_assert(!std::is_same_v
<Alloc
, FallibleAlloc
> ||
1983 sizeof(E
) * N
<= 1024);
1984 this->template SwapArrayElements
<InfallibleAlloc
>(aOther
, sizeof(elem_type
),
1985 MOZ_ALIGNOF(elem_type
));
1988 template <class Allocator
>
1989 [[nodiscard
]] auto SwapElements(nsTArray_Impl
<E
, Allocator
>& aOther
,
1990 const mozilla::fallible_t
&) {
1991 // Allocation might fail if Alloc==FallibleAlloc and
1992 // Allocator==InfallibleAlloc and aOther uses auto storage.
1993 return FallibleAlloc::Result(
1994 this->template SwapArrayElements
<FallibleAlloc
>(
1995 aOther
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
)));
1999 // Used by ApplyIf functions to invoke a callable that takes either:
2000 // - Nothing: F(void)
2001 // - Index only: F(size_t)
2002 // - Reference to element only: F(maybe-const elem_type&)
2003 // - Both index and reference: F(size_t, maybe-const elem_type&)
2004 // `elem_type` must be const when called from const method.
2005 template <typename T
, typename Param0
, typename Param1
>
2006 struct InvokeWithIndexAndOrReferenceHelper
{
2007 static constexpr bool valid
= false;
2009 template <typename T
>
2010 struct InvokeWithIndexAndOrReferenceHelper
<T
, void, void> {
2011 static constexpr bool valid
= true;
2012 template <typename F
>
2013 static auto Invoke(F
&& f
, size_t, T
&) {
2017 template <typename T
>
2018 struct InvokeWithIndexAndOrReferenceHelper
<T
, size_t, void> {
2019 static constexpr bool valid
= true;
2020 template <typename F
>
2021 static auto Invoke(F
&& f
, size_t i
, T
&) {
2025 template <typename T
>
2026 struct InvokeWithIndexAndOrReferenceHelper
<T
, T
&, void> {
2027 static constexpr bool valid
= true;
2028 template <typename F
>
2029 static auto Invoke(F
&& f
, size_t, T
& e
) {
2033 template <typename T
>
2034 struct InvokeWithIndexAndOrReferenceHelper
<T
, const T
&, void> {
2035 static constexpr bool valid
= true;
2036 template <typename F
>
2037 static auto Invoke(F
&& f
, size_t, T
& e
) {
2041 template <typename T
>
2042 struct InvokeWithIndexAndOrReferenceHelper
<T
, size_t, T
&> {
2043 static constexpr bool valid
= true;
2044 template <typename F
>
2045 static auto Invoke(F
&& f
, size_t i
, T
& e
) {
2049 template <typename T
>
2050 struct InvokeWithIndexAndOrReferenceHelper
<T
, size_t, const T
&> {
2051 static constexpr bool valid
= true;
2052 template <typename F
>
2053 static auto Invoke(F
&& f
, size_t i
, T
& e
) {
2057 template <typename T
, typename F
>
2058 static auto InvokeWithIndexAndOrReference(F
&& f
, size_t i
, T
& e
) {
2059 using Invoker
= InvokeWithIndexAndOrReferenceHelper
<
2060 T
, typename
mozilla::FunctionTypeTraits
<F
>::template ParameterType
<0>,
2061 typename
mozilla::FunctionTypeTraits
<F
>::template ParameterType
<1>>;
2062 static_assert(Invoker::valid
,
2063 "ApplyIf's Function parameters must match either: (void), "
2064 "(size_t), (maybe-const elem_type&), or "
2065 "(size_t, maybe-const elem_type&)");
2066 return Invoker::Invoke(std::forward
<F
>(f
), i
, e
);
2070 // 'Apply' family of methods.
2072 // The advantages of using Apply methods with lambdas include:
2073 // - Safety of accessing elements from within the call, when the array cannot
2074 // have been modified between the iteration and the subsequent access.
2075 // - Avoiding moot conversions: pointer->index during a search, followed by
2076 // index->pointer after the search when accessing the element.
2077 // - Embedding your code into the algorithm, giving the compiler more chances
2080 // Search for the first element comparing equal to aItem with the given
2081 // comparator (`==` by default).
2082 // If such an element exists, return the result of evaluating either:
2084 // - `aFunction(index_type)`
2085 // - `aFunction(maybe-const? elem_type&)`
2086 // - `aFunction(index_type, maybe-const? elem_type&)`
2087 // (`aFunction` must have one of the above signatures with these exact types,
2088 // including references; implicit conversions or generic types not allowed.
2089 // If `this` array is const, the referenced `elem_type` must be const too;
2090 // otherwise it may be either const or non-const.)
2091 // But if the element is not found, return the result of evaluating
2092 // `aFunctionElse()`.
2093 template <class Item
, class Comparator
, class Function
, class FunctionElse
>
2094 auto ApplyIf(const Item
& aItem
, index_type aStart
, const Comparator
& aComp
,
2095 Function
&& aFunction
, FunctionElse
&& aFunctionElse
) const {
2098 typename
mozilla::FunctionTypeTraits
<Function
>::ReturnType
,
2099 typename
mozilla::FunctionTypeTraits
<FunctionElse
>::ReturnType
>,
2100 "ApplyIf's `Function` and `FunctionElse` must return the same type.");
2102 ::detail::CompareWrapper
<Comparator
, Item
> comp(aComp
);
2104 const elem_type
* const elements
= Elements();
2105 const elem_type
* const iend
= elements
+ Length();
2106 for (const elem_type
* iter
= elements
+ aStart
; iter
!= iend
; ++iter
) {
2107 if (comp
.Equals(*iter
, aItem
)) {
2108 return InvokeWithIndexAndOrReference
<const elem_type
>(
2109 std::forward
<Function
>(aFunction
), iter
- elements
, *iter
);
2112 return aFunctionElse();
2114 template <class Item
, class Comparator
, class Function
, class FunctionElse
>
2115 auto ApplyIf(const Item
& aItem
, index_type aStart
, const Comparator
& aComp
,
2116 Function
&& aFunction
, FunctionElse
&& aFunctionElse
) {
2119 typename
mozilla::FunctionTypeTraits
<Function
>::ReturnType
,
2120 typename
mozilla::FunctionTypeTraits
<FunctionElse
>::ReturnType
>,
2121 "ApplyIf's `Function` and `FunctionElse` must return the same type.");
2123 ::detail::CompareWrapper
<Comparator
, Item
> comp(aComp
);
2125 elem_type
* const elements
= Elements();
2126 elem_type
* const iend
= elements
+ Length();
2127 for (elem_type
* iter
= elements
+ aStart
; iter
!= iend
; ++iter
) {
2128 if (comp
.Equals(*iter
, aItem
)) {
2129 return InvokeWithIndexAndOrReference
<elem_type
>(
2130 std::forward
<Function
>(aFunction
), iter
- elements
, *iter
);
2133 return aFunctionElse();
2135 template <class Item
, class Function
, class FunctionElse
>
2136 auto ApplyIf(const Item
& aItem
, index_type aStart
, Function
&& aFunction
,
2137 FunctionElse
&& aFunctionElse
) const {
2138 return ApplyIf(aItem
, aStart
, nsDefaultComparator
<elem_type
, Item
>(),
2139 std::forward
<Function
>(aFunction
),
2140 std::forward
<FunctionElse
>(aFunctionElse
));
2142 template <class Item
, class Function
, class FunctionElse
>
2143 auto ApplyIf(const Item
& aItem
, index_type aStart
, Function
&& aFunction
,
2144 FunctionElse
&& aFunctionElse
) {
2145 return ApplyIf(aItem
, aStart
, nsDefaultComparator
<elem_type
, Item
>(),
2146 std::forward
<Function
>(aFunction
),
2147 std::forward
<FunctionElse
>(aFunctionElse
));
2149 template <class Item
, class Function
, class FunctionElse
>
2150 auto ApplyIf(const Item
& aItem
, Function
&& aFunction
,
2151 FunctionElse
&& aFunctionElse
) const {
2152 return ApplyIf(aItem
, 0, std::forward
<Function
>(aFunction
),
2153 std::forward
<FunctionElse
>(aFunctionElse
));
2155 template <class Item
, class Function
, class FunctionElse
>
2156 auto ApplyIf(const Item
& aItem
, Function
&& aFunction
,
2157 FunctionElse
&& aFunctionElse
) {
2158 return ApplyIf(aItem
, 0, std::forward
<Function
>(aFunction
),
2159 std::forward
<FunctionElse
>(aFunctionElse
));
2166 // This method may increase the capacity of this array object to the
2167 // specified amount. This method may be called in advance of several
2168 // AppendElement operations to minimize heap re-allocations. This method
2169 // will not reduce the number of elements in this array.
2170 // @param aCapacity The desired capacity of this array.
2171 // @return True if the operation succeeded; false if we ran out of memory
2173 template <typename ActualAlloc
= Alloc
>
2174 typename
ActualAlloc::ResultType
SetCapacity(size_type aCapacity
) {
2175 return ActualAlloc::Result(this->template EnsureCapacity
<ActualAlloc
>(
2176 aCapacity
, sizeof(elem_type
)));
2180 [[nodiscard
]] bool SetCapacity(size_type aCapacity
,
2181 const mozilla::fallible_t
&) {
2182 return SetCapacity
<FallibleAlloc
>(aCapacity
);
2185 // This method modifies the length of the array. If the new length is
2186 // larger than the existing length of the array, then new elements will be
2187 // constructed using elem_type's default constructor. Otherwise, this call
2188 // removes elements from the array (see also RemoveElementsAt).
2189 // @param aNewLen The desired length of this array.
2190 // @return True if the operation succeeded; false otherwise.
2191 // See also TruncateLength for a more efficient variant if the new length is
2192 // guaranteed to be smaller than the old.
2194 template <typename ActualAlloc
= Alloc
>
2195 typename
ActualAlloc::ResultType
SetLength(size_type aNewLen
) {
2196 const size_type oldLen
= Length();
2197 if (aNewLen
> oldLen
) {
2198 return ActualAlloc::ConvertBoolToResultType(
2199 InsertElementsAtInternal
<ActualAlloc
>(oldLen
, aNewLen
- oldLen
) !=
2203 TruncateLengthUnsafe(aNewLen
);
2204 return ActualAlloc::ConvertBoolToResultType(true);
2208 [[nodiscard
]] bool SetLength(size_type aNewLen
, const mozilla::fallible_t
&) {
2209 return SetLength
<FallibleAlloc
>(aNewLen
);
2212 // This method modifies the length of the array, but may only be
2213 // called when the new length is shorter than the old. It can
2214 // therefore be called when elem_type has no default constructor,
2215 // unlike SetLength. It removes elements from the array (see also
2216 // RemoveElementsAt).
2217 // @param aNewLen The desired length of this array.
2218 void TruncateLength(size_type aNewLen
) {
2219 // This assertion is redundant, but produces a better error message than the
2220 // release assertion below.
2221 MOZ_ASSERT(aNewLen
<= Length(), "caller should use SetLength instead");
2223 if (MOZ_UNLIKELY(aNewLen
> Length())) {
2224 InvalidArrayIndex_CRASH(aNewLen
, Length());
2227 TruncateLengthUnsafe(aNewLen
);
2231 void TruncateLengthUnsafe(size_type aNewLen
) {
2232 const size_type oldLen
= Length();
2234 DestructRange(aNewLen
, oldLen
- aNewLen
);
2235 base_type::mHdr
->mLength
= aNewLen
;
2239 // This method ensures that the array has length at least the given
2240 // length. If the current length is shorter than the given length,
2241 // then new elements will be constructed using elem_type's default
2243 // @param aMinLen The desired minimum length of this array.
2244 // @return True if the operation succeeded; false otherwise.
2246 template <typename ActualAlloc
= Alloc
>
2247 typename
ActualAlloc::ResultType
EnsureLengthAtLeast(size_type aMinLen
) {
2248 size_type oldLen
= Length();
2249 if (aMinLen
> oldLen
) {
2250 return ActualAlloc::ConvertBoolToResultType(
2251 !!InsertElementsAtInternal
<ActualAlloc
>(oldLen
, aMinLen
- oldLen
));
2253 return ActualAlloc::ConvertBoolToResultType(true);
2257 [[nodiscard
]] bool EnsureLengthAtLeast(size_type aMinLen
,
2258 const mozilla::fallible_t
&) {
2259 return EnsureLengthAtLeast
<FallibleAlloc
>(aMinLen
);
2262 // This method inserts elements into the array, constructing
2263 // them using elem_type's default constructor.
2264 // @param aIndex the place to insert the new elements. This must be no
2265 // greater than the current length of the array.
2266 // @param aCount the number of elements to insert
2268 template <typename ActualAlloc
>
2269 elem_type
* InsertElementsAtInternal(index_type aIndex
, size_type aCount
) {
2270 if (!ActualAlloc::Successful(this->template InsertSlotsAt
<ActualAlloc
>(
2271 aIndex
, aCount
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
)))) {
2275 // Initialize the extra array elements
2276 elem_type
* iter
= Elements() + aIndex
;
2277 elem_type
* iend
= iter
+ aCount
;
2278 for (; iter
!= iend
; ++iter
) {
2279 elem_traits::Construct(iter
);
2282 return Elements() + aIndex
;
2286 [[nodiscard
]] elem_type
* InsertElementsAt(index_type aIndex
, size_type aCount
,
2287 const mozilla::fallible_t
&) {
2288 return InsertElementsAtInternal
<FallibleAlloc
>(aIndex
, aCount
);
2291 // This method inserts elements into the array, constructing them
2292 // elem_type's copy constructor (or whatever one-arg constructor
2293 // happens to match the Item type).
2294 // @param aIndex the place to insert the new elements. This must be no
2295 // greater than the current length of the array.
2296 // @param aCount the number of elements to insert.
2297 // @param aItem the value to use when constructing the new elements.
2299 template <typename ActualAlloc
, class Item
>
2300 elem_type
* InsertElementsAtInternal(index_type aIndex
, size_type aCount
,
2304 template <class Item
>
2305 [[nodiscard
]] elem_type
* InsertElementsAt(index_type aIndex
, size_type aCount
,
2307 const mozilla::fallible_t
&) {
2308 return InsertElementsAt
<Item
, FallibleAlloc
>(aIndex
, aCount
, aItem
);
2311 // This method may be called to minimize the memory used by this array.
2312 void Compact() { ShrinkCapacity(sizeof(elem_type
), MOZ_ALIGNOF(elem_type
)); }
2318 // This function is meant to be used with the NS_QuickSort function. It
2319 // maps the callback API expected by NS_QuickSort to the Comparator API
2320 // used by nsTArray_Impl. See nsTArray_Impl::Sort.
2321 template <class Comparator
>
2322 static int Compare(const void* aE1
, const void* aE2
, void* aData
) {
2323 const Comparator
* c
= reinterpret_cast<const Comparator
*>(aData
);
2324 const elem_type
* a
= static_cast<const elem_type
*>(aE1
);
2325 const elem_type
* b
= static_cast<const elem_type
*>(aE2
);
2326 return c
->Compare(*a
, *b
);
2329 // This method sorts the elements of the array. It uses the LessThan
2330 // method defined on the given Comparator object to collate elements.
2331 // @param aComp The Comparator used to collate elements.
2332 template <class Comparator
>
2333 void Sort(const Comparator
& aComp
) {
2334 ::detail::CompareWrapper
<Comparator
, elem_type
> comp(aComp
);
2336 NS_QuickSort(Elements(), Length(), sizeof(elem_type
),
2337 Compare
<decltype(comp
)>, &comp
);
2340 // A variation on the Sort method defined above that assumes that
2341 // 'operator<' is defined for elem_type.
2342 void Sort() { Sort(nsDefaultComparator
<elem_type
, elem_type
>()); }
2344 // This method sorts the elements of the array in a stable way (i.e. not
2345 // changing the relative order of elements considered equal by the
2346 // Comparator). It uses the LessThan
2347 // method defined on the given Comparator object to collate elements.
2348 // @param aComp The Comparator used to collate elements.
2349 template <class Comparator
>
2350 void StableSort(const Comparator
& aComp
) {
2351 const ::detail::CompareWrapper
<Comparator
, elem_type
> comp(aComp
);
2353 std::stable_sort(Elements(), Elements() + Length(),
2354 [&comp
](const auto& lhs
, const auto& rhs
) {
2355 return comp
.LessThan(lhs
, rhs
);
2359 // This method reverses the array in place.
2361 elem_type
* elements
= Elements();
2362 const size_type len
= Length();
2363 for (index_type i
= 0, iend
= len
/ 2; i
< iend
; ++i
) {
2364 std::swap(elements
[i
], elements
[len
- i
- 1]);
2369 using base_type::Hdr
;
2370 using base_type::ShrinkCapacity
;
2372 // This method invokes elem_type's destructor on a range of elements.
2373 // @param aStart The index of the first element to destroy.
2374 // @param aCount The number of elements to destroy.
2375 void DestructRange(index_type aStart
, size_type aCount
) {
2376 elem_type
* iter
= Elements() + aStart
;
2377 elem_type
* iend
= iter
+ aCount
;
2378 for (; iter
!= iend
; ++iter
) {
2379 elem_traits::Destruct(iter
);
2383 // This method invokes elem_type's copy-constructor on a range of elements.
2384 // @param aStart The index of the first element to construct.
2385 // @param aCount The number of elements to construct.
2386 // @param aValues The array of elements to copy.
2387 template <class Item
>
2388 void AssignRange(index_type aStart
, size_type aCount
, const Item
* aValues
) {
2389 AssignRangeAlgorithm
<
2390 std::is_trivially_copy_constructible_v
<Item
>,
2391 std::is_same_v
<Item
, elem_type
>>::implementation(Elements(), aStart
,
2396 template <typename E
, class Alloc
>
2397 template <typename ActualAlloc
, class Item
>
2398 auto nsTArray_Impl
<E
, Alloc
>::AssignInternal(const Item
* aArray
,
2399 size_type aArrayLen
) ->
2400 typename
ActualAlloc::ResultType
{
2401 static_assert(std::is_same_v
<ActualAlloc
, InfallibleAlloc
> ||
2402 std::is_same_v
<ActualAlloc
, FallibleAlloc
>);
2404 if constexpr (std::is_same_v
<ActualAlloc
, InfallibleAlloc
>) {
2405 ClearAndRetainStorage();
2407 // Adjust memory allocation up-front to catch errors in the fallible case.
2408 // We might relocate the elements to be destroyed unnecessarily. This could be
2409 // optimized, but would make things more complicated.
2410 if (!ActualAlloc::Successful(this->template EnsureCapacity
<ActualAlloc
>(
2411 aArrayLen
, sizeof(elem_type
)))) {
2412 return ActualAlloc::ConvertBoolToResultType(false);
2415 MOZ_ASSERT_IF(this->HasEmptyHeader(), aArrayLen
== 0);
2416 if (!this->HasEmptyHeader()) {
2417 if constexpr (std::is_same_v
<ActualAlloc
, FallibleAlloc
>) {
2418 ClearAndRetainStorage();
2420 AssignRange(0, aArrayLen
, aArray
);
2421 base_type::mHdr
->mLength
= aArrayLen
;
2424 return ActualAlloc::ConvertBoolToResultType(true);
2427 template <typename E
, class Alloc
>
2428 template <typename ActualAlloc
, class Item
>
2429 auto nsTArray_Impl
<E
, Alloc
>::ReplaceElementsAtInternal(index_type aStart
,
2432 size_type aArrayLen
)
2434 if (MOZ_UNLIKELY(aStart
> Length())) {
2435 InvalidArrayIndex_CRASH(aStart
, Length());
2438 // Adjust memory allocation up-front to catch errors.
2439 if (!ActualAlloc::Successful(this->template EnsureCapacity
<ActualAlloc
>(
2440 Length() + aArrayLen
- aCount
, sizeof(elem_type
)))) {
2443 DestructRange(aStart
, aCount
);
2444 this->template ShiftData
<ActualAlloc
>(
2445 aStart
, aCount
, aArrayLen
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
2446 AssignRange(aStart
, aArrayLen
, aArray
);
2447 return Elements() + aStart
;
2450 template <typename E
, class Alloc
>
2451 void nsTArray_Impl
<E
, Alloc
>::RemoveElementsAt(index_type aStart
,
2453 MOZ_ASSERT(aCount
== 0 || aStart
< Length(), "Invalid aStart index");
2455 mozilla::CheckedInt
<index_type
> rangeEnd
= aStart
;
2458 if (MOZ_UNLIKELY(!rangeEnd
.isValid() || rangeEnd
.value() > Length())) {
2459 InvalidArrayIndex_CRASH(aStart
, Length());
2462 RemoveElementsAtUnsafe(aStart
, aCount
);
2465 template <typename E
, class Alloc
>
2466 void nsTArray_Impl
<E
, Alloc
>::RemoveElementsAtUnsafe(index_type aStart
,
2468 DestructRange(aStart
, aCount
);
2469 this->template ShiftData
<InfallibleAlloc
>(
2470 aStart
, aCount
, 0, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
2473 template <typename E
, class Alloc
>
2474 void nsTArray_Impl
<E
, Alloc
>::UnorderedRemoveElementsAt(index_type aStart
,
2476 MOZ_ASSERT(aCount
== 0 || aStart
< Length(), "Invalid aStart index");
2478 mozilla::CheckedInt
<index_type
> rangeEnd
= aStart
;
2481 if (MOZ_UNLIKELY(!rangeEnd
.isValid() || rangeEnd
.value() > Length())) {
2482 InvalidArrayIndex_CRASH(aStart
, Length());
2485 // Destroy the elements which are being removed, and then swap elements in to
2486 // replace them from the end. See the docs on the declaration of this
2488 DestructRange(aStart
, aCount
);
2489 this->template SwapFromEnd
<InfallibleAlloc
>(aStart
, aCount
, sizeof(elem_type
),
2490 MOZ_ALIGNOF(elem_type
));
2493 template <typename E
, class Alloc
>
2494 template <typename Predicate
>
2495 void nsTArray_Impl
<E
, Alloc
>::RemoveElementsBy(Predicate aPredicate
) {
2496 if (this->HasEmptyHeader()) {
2501 const index_type len
= Length();
2502 elem_type
* const elements
= Elements();
2503 for (index_type i
= 0; i
< len
; ++i
) {
2504 const bool result
= aPredicate(elements
[i
]);
2506 // Check that the array has not been modified by the predicate.
2507 MOZ_DIAGNOSTIC_ASSERT(len
== base_type::mHdr
->mLength
&&
2508 elements
== Elements());
2511 elem_traits::Destruct(elements
+ i
);
2514 relocation_type::RelocateNonOverlappingRegion(
2515 elements
+ j
, elements
+ i
, 1, sizeof(elem_type
));
2521 base_type::mHdr
->mLength
= j
;
2524 template <typename E
, class Alloc
>
2525 template <typename ActualAlloc
, class Item
>
2526 auto nsTArray_Impl
<E
, Alloc
>::InsertElementsAtInternal(index_type aIndex
,
2530 if (!ActualAlloc::Successful(this->template InsertSlotsAt
<ActualAlloc
>(
2531 aIndex
, aCount
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
)))) {
2535 // Initialize the extra array elements
2536 elem_type
* iter
= Elements() + aIndex
;
2537 elem_type
* iend
= iter
+ aCount
;
2538 for (; iter
!= iend
; ++iter
) {
2539 elem_traits::Construct(iter
, aItem
);
2542 return Elements() + aIndex
;
2545 template <typename E
, class Alloc
>
2546 template <typename ActualAlloc
>
2547 auto nsTArray_Impl
<E
, Alloc
>::InsertElementAtInternal(index_type aIndex
)
2549 if (MOZ_UNLIKELY(aIndex
> Length())) {
2550 InvalidArrayIndex_CRASH(aIndex
, Length());
2553 // Length() + 1 is guaranteed to not overflow, so EnsureCapacity is OK.
2554 if (!ActualAlloc::Successful(this->template EnsureCapacity
<ActualAlloc
>(
2555 Length() + 1, sizeof(elem_type
)))) {
2558 this->template ShiftData
<ActualAlloc
>(aIndex
, 0, 1, sizeof(elem_type
),
2559 MOZ_ALIGNOF(elem_type
));
2560 elem_type
* elem
= Elements() + aIndex
;
2561 elem_traits::Construct(elem
);
2565 template <typename E
, class Alloc
>
2566 template <typename ActualAlloc
, class Item
>
2567 auto nsTArray_Impl
<E
, Alloc
>::InsertElementAtInternal(index_type aIndex
,
2570 if (MOZ_UNLIKELY(aIndex
> Length())) {
2571 InvalidArrayIndex_CRASH(aIndex
, Length());
2574 // Length() + 1 is guaranteed to not overflow, so EnsureCapacity is OK.
2575 if (!ActualAlloc::Successful(this->template EnsureCapacity
<ActualAlloc
>(
2576 Length() + 1, sizeof(elem_type
)))) {
2579 this->template ShiftData
<ActualAlloc
>(aIndex
, 0, 1, sizeof(elem_type
),
2580 MOZ_ALIGNOF(elem_type
));
2581 elem_type
* elem
= Elements() + aIndex
;
2582 elem_traits::Construct(elem
, std::forward
<Item
>(aItem
));
2586 template <typename E
, class Alloc
>
2587 template <typename ActualAlloc
, class Item
>
2588 auto nsTArray_Impl
<E
, Alloc
>::AppendElementsInternal(const Item
* aArray
,
2589 size_type aArrayLen
)
2591 if (!ActualAlloc::Successful(this->template ExtendCapacity
<ActualAlloc
>(
2592 Length(), aArrayLen
, sizeof(elem_type
)))) {
2595 index_type len
= Length();
2596 AssignRange(len
, aArrayLen
, aArray
);
2597 this->IncrementLength(aArrayLen
);
2598 return Elements() + len
;
2601 template <typename E
, class Alloc
>
2602 template <typename ActualAlloc
, class Item
, class Allocator
>
2603 auto nsTArray_Impl
<E
, Alloc
>::AppendElementsInternal(
2604 nsTArray_Impl
<Item
, Allocator
>&& aArray
) -> elem_type
* {
2605 if constexpr (std::is_same_v
<Alloc
, Allocator
>) {
2606 MOZ_ASSERT(&aArray
!= this, "argument must be different aArray");
2608 if (Length() == 0) {
2609 // XXX This might still be optimized. If aArray uses auto-storage but we
2610 // won't, we might better retain our storage if it's sufficiently large.
2611 this->ShrinkCapacityToZero(sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
2612 this->MoveInit(aArray
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
2616 index_type len
= Length();
2617 index_type otherLen
= aArray
.Length();
2618 if (!ActualAlloc::Successful(this->template ExtendCapacity
<ActualAlloc
>(
2619 len
, otherLen
, sizeof(elem_type
)))) {
2622 relocation_type::RelocateNonOverlappingRegion(
2623 Elements() + len
, aArray
.Elements(), otherLen
, sizeof(elem_type
));
2624 this->IncrementLength(otherLen
);
2625 aArray
.template ShiftData
<ActualAlloc
>(0, otherLen
, 0, sizeof(elem_type
),
2626 MOZ_ALIGNOF(elem_type
));
2627 return Elements() + len
;
2630 template <typename E
, class Alloc
>
2631 template <typename ActualAlloc
, class Item
>
2632 auto nsTArray_Impl
<E
, Alloc
>::AppendElementInternal(Item
&& aItem
)
2634 // Length() + 1 is guaranteed to not overflow, so EnsureCapacity is OK.
2635 if (!ActualAlloc::Successful(this->template EnsureCapacity
<ActualAlloc
>(
2636 Length() + 1, sizeof(elem_type
)))) {
2639 elem_type
* elem
= Elements() + Length();
2640 elem_traits::Construct(elem
, std::forward
<Item
>(aItem
));
2641 this->mHdr
->mLength
+= 1;
2645 template <typename E
, class Alloc
>
2646 template <typename ActualAlloc
, class... Args
>
2647 auto nsTArray_Impl
<E
, Alloc
>::EmplaceBackInternal(Args
&&... aArgs
)
2649 // Length() + 1 is guaranteed to not overflow, so EnsureCapacity is OK.
2650 if (!ActualAlloc::Successful(this->template EnsureCapacity
<ActualAlloc
>(
2651 Length() + 1, sizeof(elem_type
)))) {
2654 elem_type
* elem
= Elements() + Length();
2655 elem_traits::Emplace(elem
, std::forward
<Args
>(aArgs
)...);
2656 this->mHdr
->mLength
+= 1;
2660 template <typename E
, typename Alloc
>
2661 inline void ImplCycleCollectionUnlink(nsTArray_Impl
<E
, Alloc
>& aField
) {
2666 // This is defined in the cpp file to avoid including
2667 // nsCycleCollectionNoteChild.h in this header file.
2668 void SetCycleCollectionArrayFlag(uint32_t& aFlags
);
2669 } // namespace detail
2671 template <typename E
, typename Alloc
>
2672 inline void ImplCycleCollectionTraverse(
2673 nsCycleCollectionTraversalCallback
& aCallback
,
2674 nsTArray_Impl
<E
, Alloc
>& aField
, const char* aName
, uint32_t aFlags
= 0) {
2675 ::detail::SetCycleCollectionArrayFlag(aFlags
);
2676 size_t length
= aField
.Length();
2677 for (size_t i
= 0; i
< length
; ++i
) {
2678 ImplCycleCollectionTraverse(aCallback
, aField
[i
], aName
, aFlags
);
2683 // nsTArray is an infallible vector class. See the comment at the top of this
2684 // file for more details.
2687 class nsTArray
: public nsTArray_Impl
<E
, nsTArrayInfallibleAllocator
> {
2689 using InfallibleAlloc
= nsTArrayInfallibleAllocator
;
2690 using base_type
= nsTArray_Impl
<E
, InfallibleAlloc
>;
2691 using self_type
= nsTArray
<E
>;
2692 using typename
base_type::elem_type
;
2693 using typename
base_type::index_type
;
2694 using typename
base_type::size_type
;
2697 explicit nsTArray(size_type aCapacity
) : base_type(aCapacity
) {}
2698 MOZ_IMPLICIT
nsTArray(std::initializer_list
<E
> aIL
) {
2699 AppendElements(aIL
.begin(), aIL
.size());
2702 template <class Item
>
2703 nsTArray(const Item
* aArray
, size_type aArrayLen
) {
2704 AppendElements(aArray
, aArrayLen
);
2707 template <class Item
>
2708 explicit nsTArray(mozilla::Span
<Item
> aSpan
) {
2709 AppendElements(aSpan
);
2712 template <class Allocator
>
2713 explicit nsTArray(const nsTArray_Impl
<E
, Allocator
>& aOther
)
2714 : base_type(aOther
) {}
2715 template <class Allocator
>
2716 MOZ_IMPLICIT
nsTArray(nsTArray_Impl
<E
, Allocator
>&& aOther
)
2717 : base_type(std::move(aOther
)) {}
2719 template <class Allocator
>
2720 self_type
& operator=(const nsTArray_Impl
<E
, Allocator
>& aOther
) {
2721 base_type::operator=(aOther
);
2724 template <class Allocator
>
2725 self_type
& operator=(nsTArray_Impl
<E
, Allocator
>&& aOther
) {
2726 // This is quite complex, since we don't know if we are an AutoTArray. While
2727 // AutoTArray overrides this operator=, this might be called on a nsTArray&
2728 // bound to an AutoTArray.
2729 base_type::operator=(std::move(aOther
));
2733 using base_type::AppendElement
;
2734 using base_type::AppendElements
;
2735 using base_type::EmplaceBack
;
2736 using base_type::EnsureLengthAtLeast
;
2737 using base_type::InsertElementAt
;
2738 using base_type::InsertElementsAt
;
2739 using base_type::InsertElementSorted
;
2740 using base_type::ReplaceElementsAt
;
2741 using base_type::SetCapacity
;
2742 using base_type::SetLength
;
2744 template <class Item
>
2745 mozilla::NotNull
<elem_type
*> AppendElements(const Item
* aArray
,
2746 size_type aArrayLen
) {
2747 return mozilla::WrapNotNullUnchecked(
2748 this->template AppendElementsInternal
<InfallibleAlloc
>(aArray
,
2752 template <class Item
>
2753 mozilla::NotNull
<elem_type
*> AppendElements(mozilla::Span
<Item
> aSpan
) {
2754 return mozilla::WrapNotNullUnchecked(
2755 this->template AppendElementsInternal
<InfallibleAlloc
>(aSpan
.Elements(),
2759 template <class Item
, class Allocator
>
2760 mozilla::NotNull
<elem_type
*> AppendElements(
2761 const nsTArray_Impl
<Item
, Allocator
>& aArray
) {
2762 return mozilla::WrapNotNullUnchecked(
2763 this->template AppendElementsInternal
<InfallibleAlloc
>(
2764 aArray
.Elements(), aArray
.Length()));
2767 template <class Item
, class Allocator
>
2768 mozilla::NotNull
<elem_type
*> AppendElements(
2769 nsTArray_Impl
<Item
, Allocator
>&& aArray
) {
2770 return mozilla::WrapNotNullUnchecked(
2771 this->template AppendElementsInternal
<InfallibleAlloc
>(
2772 std::move(aArray
)));
2775 template <class Item
>
2776 mozilla::NotNull
<elem_type
*> AppendElement(Item
&& aItem
) {
2777 return mozilla::WrapNotNullUnchecked(
2778 this->template AppendElementInternal
<InfallibleAlloc
>(
2779 std::forward
<Item
>(aItem
)));
2782 mozilla::NotNull
<elem_type
*> AppendElements(size_type aCount
) {
2783 return mozilla::WrapNotNullUnchecked(
2784 this->template AppendElementsInternal
<InfallibleAlloc
>(aCount
));
2787 mozilla::NotNull
<elem_type
*> AppendElement() {
2788 return mozilla::WrapNotNullUnchecked(
2789 this->template AppendElementsInternal
<InfallibleAlloc
>(1));
2792 self_type
Clone() const {
2794 result
.Assign(*this);
2798 mozilla::NotNull
<elem_type
*> InsertElementsAt(index_type aIndex
,
2800 return mozilla::WrapNotNullUnchecked(
2801 this->template InsertElementsAtInternal
<InfallibleAlloc
>(aIndex
,
2805 template <class Item
>
2806 mozilla::NotNull
<elem_type
*> InsertElementsAt(index_type aIndex
,
2808 const Item
& aItem
) {
2809 return mozilla::WrapNotNullUnchecked(
2810 this->template InsertElementsAtInternal
<InfallibleAlloc
>(aIndex
, aCount
,
2814 template <class Item
>
2815 mozilla::NotNull
<elem_type
*> InsertElementsAt(index_type aIndex
,
2817 size_type aArrayLen
) {
2818 return mozilla::WrapNotNullUnchecked(
2819 this->template ReplaceElementsAtInternal
<InfallibleAlloc
>(
2820 aIndex
, 0, aArray
, aArrayLen
));
2823 template <class Item
, class Allocator
>
2824 mozilla::NotNull
<elem_type
*> InsertElementsAt(
2825 index_type aIndex
, const nsTArray_Impl
<Item
, Allocator
>& aArray
) {
2826 return mozilla::WrapNotNullUnchecked(
2827 this->template ReplaceElementsAtInternal
<InfallibleAlloc
>(
2828 aIndex
, 0, aArray
.Elements(), aArray
.Length()));
2831 template <class Item
>
2832 mozilla::NotNull
<elem_type
*> InsertElementsAt(index_type aIndex
,
2833 mozilla::Span
<Item
> aSpan
) {
2834 return mozilla::WrapNotNullUnchecked(
2835 this->template ReplaceElementsAtInternal
<InfallibleAlloc
>(
2836 aIndex
, 0, aSpan
.Elements(), aSpan
.Length()));
2839 mozilla::NotNull
<elem_type
*> InsertElementAt(index_type aIndex
) {
2840 return mozilla::WrapNotNullUnchecked(
2841 this->template InsertElementAtInternal
<InfallibleAlloc
>(aIndex
));
2844 template <class Item
>
2845 mozilla::NotNull
<elem_type
*> InsertElementAt(index_type aIndex
,
2847 return mozilla::WrapNotNullUnchecked(
2848 this->template InsertElementAtInternal
<InfallibleAlloc
>(
2849 aIndex
, std::forward
<Item
>(aItem
)));
2852 template <class Item
>
2853 mozilla::NotNull
<elem_type
*> ReplaceElementsAt(index_type aStart
,
2856 size_type aArrayLen
) {
2857 return mozilla::WrapNotNullUnchecked(
2858 this->template ReplaceElementsAtInternal
<InfallibleAlloc
>(
2859 aStart
, aCount
, aArray
, aArrayLen
));
2862 template <class Item
>
2863 mozilla::NotNull
<elem_type
*> ReplaceElementsAt(index_type aStart
,
2865 const nsTArray
<Item
>& aArray
) {
2866 return ReplaceElementsAt(aStart
, aCount
, aArray
.Elements(),
2870 template <class Item
>
2871 mozilla::NotNull
<elem_type
*> ReplaceElementsAt(index_type aStart
,
2873 mozilla::Span
<Item
> aSpan
) {
2874 return ReplaceElementsAt(aStart
, aCount
, aSpan
.Elements(), aSpan
.Length());
2877 template <class Item
>
2878 mozilla::NotNull
<elem_type
*> ReplaceElementsAt(index_type aStart
,
2880 const Item
& aItem
) {
2881 return ReplaceElementsAt(aStart
, aCount
, &aItem
, 1);
2884 template <class Item
, class Comparator
>
2885 mozilla::NotNull
<elem_type
*> InsertElementSorted(Item
&& aItem
,
2886 const Comparator
& aComp
) {
2887 return mozilla::WrapNotNullUnchecked(
2888 this->template InsertElementSortedInternal
<InfallibleAlloc
>(
2889 std::forward
<Item
>(aItem
), aComp
));
2892 template <class Item
>
2893 mozilla::NotNull
<elem_type
*> InsertElementSorted(Item
&& aItem
) {
2894 return mozilla::WrapNotNullUnchecked(
2895 this->template InsertElementSortedInternal
<InfallibleAlloc
>(
2896 std::forward
<Item
>(aItem
), nsDefaultComparator
<elem_type
, Item
>{}));
2899 template <class... Args
>
2900 mozilla::NotNull
<elem_type
*> EmplaceBack(Args
&&... aArgs
) {
2901 return mozilla::WrapNotNullUnchecked(
2902 this->template EmplaceBackInternal
<InfallibleAlloc
, Args
...>(
2903 std::forward
<Args
>(aArgs
)...));
2908 class CopyableTArray
: public nsTArray
<E
> {
2910 using nsTArray
<E
>::nsTArray
;
2912 CopyableTArray(const CopyableTArray
& aOther
) : nsTArray
<E
>() {
2913 this->Assign(aOther
);
2915 CopyableTArray
& operator=(const CopyableTArray
& aOther
) {
2916 if (this != &aOther
) {
2917 this->Assign(aOther
);
2921 template <typename Allocator
>
2922 MOZ_IMPLICIT
CopyableTArray(const nsTArray_Impl
<E
, Allocator
>& aOther
) {
2923 this->Assign(aOther
);
2925 template <typename Allocator
>
2926 CopyableTArray
& operator=(const nsTArray_Impl
<E
, Allocator
>& aOther
) {
2927 if constexpr (std::is_same_v
<Allocator
, nsTArrayInfallibleAllocator
>) {
2928 if (this == &aOther
) {
2932 this->Assign(aOther
);
2935 template <typename Allocator
>
2936 MOZ_IMPLICIT
CopyableTArray(nsTArray_Impl
<E
, Allocator
>&& aOther
)
2937 : nsTArray
<E
>{std::move(aOther
)} {}
2938 template <typename Allocator
>
2939 CopyableTArray
& operator=(nsTArray_Impl
<E
, Allocator
>&& aOther
) {
2940 static_cast<nsTArray
<E
>&>(*this) = std::move(aOther
);
2944 CopyableTArray(CopyableTArray
&&) = default;
2945 CopyableTArray
& operator=(CopyableTArray
&&) = default;
2949 // FallibleTArray is a fallible vector class.
2952 class FallibleTArray
: public nsTArray_Impl
<E
, nsTArrayFallibleAllocator
> {
2954 typedef nsTArray_Impl
<E
, nsTArrayFallibleAllocator
> base_type
;
2955 typedef FallibleTArray
<E
> self_type
;
2956 typedef typename
base_type::size_type size_type
;
2958 FallibleTArray() = default;
2959 explicit FallibleTArray(size_type aCapacity
) : base_type(aCapacity
) {}
2961 template <class Allocator
>
2962 explicit FallibleTArray(const nsTArray_Impl
<E
, Allocator
>& aOther
)
2963 : base_type(aOther
) {}
2964 template <class Allocator
>
2965 explicit FallibleTArray(nsTArray_Impl
<E
, Allocator
>&& aOther
)
2966 : base_type(std::move(aOther
)) {}
2968 template <class Allocator
>
2969 self_type
& operator=(const nsTArray_Impl
<E
, Allocator
>& aOther
) {
2970 base_type::operator=(aOther
);
2973 template <class Allocator
>
2974 self_type
& operator=(nsTArray_Impl
<E
, Allocator
>&& aOther
) {
2975 base_type::operator=(std::move(aOther
));
2981 // AutoTArray<E, N> is like nsTArray<E>, but with N elements of inline storage.
2982 // Storing more than N elements is fine, but it will cause a heap allocation.
2984 template <class E
, size_t N
>
2985 class MOZ_NON_MEMMOVABLE AutoTArray
: public nsTArray
<E
> {
2986 static_assert(N
!= 0, "AutoTArray<E, 0> should be specialized");
2989 typedef AutoTArray
<E
, N
> self_type
;
2990 typedef nsTArray
<E
> base_type
;
2991 typedef typename
base_type::Header Header
;
2992 typedef typename
base_type::elem_type elem_type
;
2994 AutoTArray() : mAlign() { Init(); }
2996 AutoTArray(self_type
&& aOther
) : nsTArray
<E
>() {
2998 this->MoveInit(aOther
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
3001 explicit AutoTArray(base_type
&& aOther
) : mAlign() {
3003 this->MoveInit(aOther
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
3006 template <typename Allocator
>
3007 explicit AutoTArray(nsTArray_Impl
<elem_type
, Allocator
>&& aOther
) {
3009 this->MoveInit(aOther
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
3012 MOZ_IMPLICIT
AutoTArray(std::initializer_list
<E
> aIL
) : mAlign() {
3014 this->AppendElements(aIL
.begin(), aIL
.size());
3017 self_type
& operator=(self_type
&& aOther
) {
3018 base_type::operator=(std::move(aOther
));
3022 template <typename Allocator
>
3023 self_type
& operator=(nsTArray_Impl
<elem_type
, Allocator
>&& aOther
) {
3024 base_type::operator=(std::move(aOther
));
3028 // Intentionally hides nsTArray_Impl::Clone to make clones usually be
3029 // AutoTArray as well.
3030 self_type
Clone() const {
3032 result
.Assign(*this);
3037 // nsTArray_base casts itself as an nsAutoArrayBase in order to get a pointer
3039 template <class Allocator
, class RelocationStrategy
>
3040 friend class nsTArray_base
;
3043 static_assert(MOZ_ALIGNOF(elem_type
) <= 8,
3044 "can't handle alignments greater than 8, "
3045 "see nsTArray_base::UsesAutoArrayBuffer()");
3046 // Temporary work around for VS2012 RC compiler crash
3047 Header
** phdr
= base_type::PtrToHdr();
3048 *phdr
= reinterpret_cast<Header
*>(&mAutoBuf
);
3049 (*phdr
)->mLength
= 0;
3050 (*phdr
)->mCapacity
= N
;
3051 (*phdr
)->mIsAutoArray
= 1;
3053 MOZ_ASSERT(base_type::GetAutoArrayBuffer(MOZ_ALIGNOF(elem_type
)) ==
3054 reinterpret_cast<Header
*>(&mAutoBuf
),
3055 "GetAutoArrayBuffer needs to be fixed");
3058 // Declare mAutoBuf aligned to the maximum of the header's alignment and
3059 // elem_type's alignment. We need to use a union rather than
3060 // MOZ_ALIGNED_DECL because GCC is picky about what goes into
3061 // __attribute__((aligned(foo))).
3063 char mAutoBuf
[sizeof(nsTArrayHeader
) + N
* sizeof(elem_type
)];
3064 // Do the max operation inline to ensure that it is a compile-time constant.
3065 mozilla::AlignedElem
<(MOZ_ALIGNOF(Header
) > MOZ_ALIGNOF(elem_type
))
3066 ? MOZ_ALIGNOF(Header
)
3067 : MOZ_ALIGNOF(elem_type
)>
3073 // Specialization of AutoTArray<E, N> for the case where N == 0.
3074 // AutoTArray<E, 0> behaves exactly like nsTArray<E>, but without this
3075 // specialization, it stores a useless inline header.
3077 // We do have many AutoTArray<E, 0> objects in memory: about 2,000 per tab as
3078 // of May 2014. These are typically not explicitly AutoTArray<E, 0> but rather
3079 // AutoTArray<E, N> for some value N depending on template parameters, in
3082 // For that reason, we optimize this case with the below partial specialization,
3083 // which ensures that AutoTArray<E, 0> is just like nsTArray<E>, without any
3084 // inline header overhead.
3087 class AutoTArray
<E
, 0> : public nsTArray
<E
> {
3088 using nsTArray
<E
>::nsTArray
;
3091 template <class E
, size_t N
>
3092 struct nsTArray_RelocationStrategy
<AutoTArray
<E
, N
>> {
3093 using Type
= nsTArray_RelocateUsingMoveConstructor
<AutoTArray
<E
, N
>>;
3096 template <class E
, size_t N
>
3097 class CopyableAutoTArray
: public AutoTArray
<E
, N
> {
3099 typedef CopyableAutoTArray
<E
, N
> self_type
;
3100 using AutoTArray
<E
, N
>::AutoTArray
;
3102 CopyableAutoTArray(const CopyableAutoTArray
& aOther
) : AutoTArray
<E
, N
>() {
3103 this->Assign(aOther
);
3105 CopyableAutoTArray
& operator=(const CopyableAutoTArray
& aOther
) {
3106 if (this != &aOther
) {
3107 this->Assign(aOther
);
3111 template <typename Allocator
>
3112 MOZ_IMPLICIT
CopyableAutoTArray(const nsTArray_Impl
<E
, Allocator
>& aOther
) {
3113 this->Assign(aOther
);
3115 template <typename Allocator
>
3116 CopyableAutoTArray
& operator=(const nsTArray_Impl
<E
, Allocator
>& aOther
) {
3117 if constexpr (std::is_same_v
<Allocator
, nsTArrayInfallibleAllocator
>) {
3118 if (this == &aOther
) {
3122 this->Assign(aOther
);
3125 template <typename Allocator
>
3126 MOZ_IMPLICIT
CopyableAutoTArray(nsTArray_Impl
<E
, Allocator
>&& aOther
)
3127 : AutoTArray
<E
, N
>{std::move(aOther
)} {}
3128 template <typename Allocator
>
3129 CopyableAutoTArray
& operator=(nsTArray_Impl
<E
, Allocator
>&& aOther
) {
3130 static_cast<AutoTArray
<E
, N
>&>(*this) = std::move(aOther
);
3134 // CopyableTArray exists for cases where an explicit Clone is not possible.
3135 // These uses should not be mixed, so we delete Clone() here.
3136 self_type
Clone() const = delete;
3138 CopyableAutoTArray(CopyableAutoTArray
&&) = default;
3139 CopyableAutoTArray
& operator=(CopyableAutoTArray
&&) = default;
3144 template <typename E
, typename ArrayT
>
3145 class nsTArrayBackInserter
3146 : public std::iterator
<std::output_iterator_tag
, void, void, void, void> {
3150 explicit nsTArrayBackInserter(ArrayT
& aArray
) : mArray
{&aArray
} {}
3152 nsTArrayBackInserter
& operator=(const E
& aValue
) {
3153 mArray
->AppendElement(aValue
);
3157 nsTArrayBackInserter
& operator=(E
&& aValue
) {
3158 mArray
->AppendElement(std::move(aValue
));
3162 nsTArrayBackInserter
& operator*() { return *this; }
3164 nsTArrayBackInserter
& operator++() { return *this; }
3165 nsTArrayBackInserter
& operator++(int) { return *this; }
3168 template <typename E
>
3169 auto MakeBackInserter(nsTArray
<E
>& aArray
) {
3170 return nsTArrayBackInserter
<E
, nsTArray
<E
>>{aArray
};
3173 template <typename E
, class Alloc
>
3174 Span(nsTArray_Impl
<E
, Alloc
>&) -> Span
<E
>;
3176 template <typename E
, class Alloc
>
3177 Span(const nsTArray_Impl
<E
, Alloc
>&) -> Span
<const E
>;
3179 // Provides a view on a nsTArray through which the existing array elements can
3180 // be accessed in a non-const way, but the array itself cannot be modified, so
3181 // that references to elements are guaranteed to be stable.
3182 template <typename E
>
3183 class nsTArrayView
{
3185 using element_type
= E
;
3186 using pointer
= element_type
*;
3187 using reference
= element_type
&;
3188 using index_type
= typename Span
<element_type
>::index_type
;
3189 using size_type
= typename Span
<element_type
>::index_type
;
3191 explicit nsTArrayView(nsTArray
<element_type
> aArray
)
3192 : mArray(std::move(aArray
)), mSpan(mArray
) {}
3194 element_type
& operator[](index_type aIndex
) { return mSpan
[aIndex
]; }
3196 const element_type
& operator[](index_type aIndex
) const {
3197 return mSpan
[aIndex
];
3200 size_type
Length() const { return mSpan
.Length(); }
3202 auto begin() { return mSpan
.begin(); }
3203 auto end() { return mSpan
.end(); }
3204 auto begin() const { return mSpan
.begin(); }
3205 auto end() const { return mSpan
.end(); }
3206 auto cbegin() const { return mSpan
.cbegin(); }
3207 auto cend() const { return mSpan
.cend(); }
3209 Span
<element_type
> AsSpan() { return mSpan
; }
3210 Span
<const element_type
> AsSpan() const { return mSpan
; }
3213 nsTArray
<element_type
> mArray
;
3214 const Span
<element_type
> mSpan
;
3217 } // namespace mozilla
3221 template <class E
, class Alloc
>
3222 std::ostream
& operator<<(std::ostream
& aOut
,
3223 const nsTArray_Impl
<E
, Alloc
>& aTArray
) {
3224 return aOut
<< mozilla::Span(aTArray
);
3227 // Assert that AutoTArray doesn't have any extra padding inside.
3229 // It's important that the data stored in this auto array takes up a multiple of
3230 // 8 bytes; e.g. AutoTArray<uint32_t, 1> wouldn't work. Since AutoTArray
3231 // contains a pointer, its size must be a multiple of alignof(void*). (This is
3232 // because any type may be placed into an array, and there's no padding between
3233 // elements of an array.) The compiler pads the end of the structure to
3234 // enforce this rule.
3236 // If we used AutoTArray<uint32_t, 1> below, this assertion would fail on a
3237 // 64-bit system, where the compiler inserts 4 bytes of padding at the end of
3238 // the auto array to make its size a multiple of alignof(void*) == 8 bytes.
3240 static_assert(sizeof(AutoTArray
<uint32_t, 2>) ==
3241 sizeof(void*) + sizeof(nsTArrayHeader
) + sizeof(uint32_t) * 2,
3242 "AutoTArray shouldn't contain any extra padding, "
3245 // Definitions of nsTArray_Impl methods
3246 #include "nsTArray-inl.h"
3248 #endif // nsTArray_h__