1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim:set ts=2 sw=2 sts=2 et cindent: */
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/. */
10 #include "nsTArrayForwardDeclare.h"
11 #include "mozilla/Assertions.h"
12 #include "mozilla/MemoryReporting.h"
13 #include "mozilla/TypeTraits.h"
14 #include "mozilla/Util.h"
18 #include "nsCycleCollectionNoteChild.h"
19 #include "nsAlgorithm.h"
21 #include "nsQuickSort.h"
23 #include "nsTraceRefcnt.h"
32 // nsTArray is a resizable array class, like std::vector.
34 // Unlike std::vector, which follows C++'s construction/destruction rules,
35 // nsTArray assumes that your "T" can be memmoved()'ed safely.
37 // The public classes defined in this header are
41 // nsAutoTArray<T, N>, and
42 // AutoFallibleTArray<T, N>.
44 // nsTArray and nsAutoTArray are infallible; if one tries to make an allocation
45 // which fails, it crashes the program. In contrast, FallibleTArray and
46 // AutoFallibleTArray are fallible; if you use one of these classes, you must
47 // check the return values of methods such as Append() which may allocate. If
48 // in doubt, choose an infallible type.
50 // InfallibleTArray and AutoInfallibleTArray are aliases for nsTArray and
53 // If you just want to declare the nsTArray types (e.g., if you're in a header
54 // file and don't need the full nsTArray definitions) consider including
55 // nsTArrayForwardDeclare.h instead of nsTArray.h.
57 // The template parameter (i.e., T in nsTArray<T>) specifies the type of the
58 // elements and has the following requirements:
60 // T MUST be safely memmove()'able.
61 // T MUST define a copy-constructor.
62 // T MAY define operator< for sorting.
63 // T MAY define operator== for searching.
65 // (Note that the memmove requirement may be relaxed for certain types - see
66 // nsTArray_CopyElements below.)
68 // For methods taking a Comparator instance, the Comparator must be a class
69 // defining the following methods:
73 // /** @return True if the elements are equals; false otherwise. */
74 // bool Equals(const elem_type& a, const Item& b) const;
76 // /** @return True if (a < b); false otherwise. */
77 // bool LessThan(const elem_type& a, const Item& b) const;
80 // The Equals method is used for searching, and the LessThan method is used for
81 // searching and sorting. The |Item| type above can be arbitrary, but must
82 // match the Item type passed to the sort or search function.
87 // nsTArrayFallibleResult and nsTArrayInfallibleResult types are proxy types
88 // which are used because you cannot use a templated type which is bound to
89 // void as an argument to a void function. In order to work around that, we
90 // encode either a void or a boolean inside these proxy objects, and pass them
91 // to the aforementioned function instead, and then use the type information to
92 // decide what to do in the function.
94 // Note that public nsTArray methods should never return a proxy type. Such
95 // types are only meant to be used in the internal nsTArray helper methods.
96 // Public methods returning non-proxy types cannot be called from other
99 struct nsTArrayFallibleResult
101 // Note: allows implicit conversions from and to bool
102 nsTArrayFallibleResult(bool result
)
114 struct nsTArrayInfallibleResult
119 // nsTArray*Allocators must all use the same |free()|, to allow swap()'ing
120 // between fallible and infallible variants.
123 struct nsTArrayFallibleAllocatorBase
125 typedef bool ResultType
;
126 typedef nsTArrayFallibleResult ResultTypeProxy
;
128 static ResultType
Result(ResultTypeProxy result
) {
132 static bool Successful(ResultTypeProxy result
) {
136 static ResultTypeProxy
SuccessResult() {
140 static ResultTypeProxy
FailureResult() {
144 static ResultType
ConvertBoolToResultType(bool aValue
) {
149 struct nsTArrayInfallibleAllocatorBase
151 typedef void ResultType
;
152 typedef nsTArrayInfallibleResult ResultTypeProxy
;
154 static ResultType
Result(ResultTypeProxy result
) {
157 static bool Successful(ResultTypeProxy
) {
161 static ResultTypeProxy
SuccessResult() {
162 return ResultTypeProxy();
165 static ResultTypeProxy
FailureResult() {
166 NS_RUNTIMEABORT("Infallible nsTArray should never fail");
167 return ResultTypeProxy();
170 static ResultType
ConvertBoolToResultType(bool aValue
) {
172 NS_RUNTIMEABORT("infallible nsTArray should never convert false to ResultType");
177 #if defined(MOZALLOC_HAVE_XMALLOC)
178 #include "mozilla/mozalloc_abort.h"
180 struct nsTArrayFallibleAllocator
: nsTArrayFallibleAllocatorBase
182 static void* Malloc(size_t size
) {
183 return moz_malloc(size
);
186 static void* Realloc(void* ptr
, size_t size
) {
187 return moz_realloc(ptr
, size
);
190 static void Free(void* ptr
) {
194 static void SizeTooBig() {
198 struct nsTArrayInfallibleAllocator
: nsTArrayInfallibleAllocatorBase
200 static void* Malloc(size_t size
) {
201 return moz_xmalloc(size
);
204 static void* Realloc(void* ptr
, size_t size
) {
205 return moz_xrealloc(ptr
, size
);
208 static void Free(void* ptr
) {
212 static void SizeTooBig() {
213 mozalloc_abort("Trying to allocate an infallible array that's too big");
220 struct nsTArrayFallibleAllocator
: nsTArrayFallibleAllocatorBase
222 static void* Malloc(size_t size
) {
226 static void* Realloc(void* ptr
, size_t size
) {
227 return realloc(ptr
, size
);
230 static void Free(void* ptr
) {
234 static void SizeTooBig() {
238 struct nsTArrayInfallibleAllocator
: nsTArrayInfallibleAllocatorBase
240 static void* Malloc(size_t size
) {
241 void* ptr
= malloc(size
);
242 if (MOZ_UNLIKELY(!ptr
)) {
248 static void* Realloc(void* ptr
, size_t size
) {
249 void* newptr
= realloc(ptr
, size
);
250 if (MOZ_UNLIKELY(!ptr
&& size
)) {
256 static void Free(void* ptr
) {
260 static void SizeTooBig() {
265 static void HandleOOM() {
266 fputs("Out of memory allocating nsTArray buffer.\n", stderr
);
273 // nsTArray_base stores elements into the space allocated beyond
274 // sizeof(*this). This is done to minimize the size of the nsTArray
275 // object when it is empty.
276 struct NS_COM_GLUE nsTArrayHeader
278 static nsTArrayHeader sEmptyHdr
;
281 uint32_t mCapacity
: 31;
282 uint32_t mIsAutoArray
: 1;
285 // This class provides a SafeElementAt method to nsTArray<T*> which does
286 // not take a second default value parameter.
287 template <class E
, class Derived
>
288 struct nsTArray_SafeElementAtHelper
290 typedef E
* elem_type
;
291 typedef uint32_t index_type
;
293 // No implementation is provided for these two methods, and that is on
294 // purpose, since we don't support these functions on non-pointer type
296 elem_type
& SafeElementAt(index_type i
);
297 const elem_type
& SafeElementAt(index_type i
) const;
300 template <class E
, class Derived
>
301 struct nsTArray_SafeElementAtHelper
<E
*, Derived
>
303 typedef E
* elem_type
;
304 typedef uint32_t index_type
;
306 elem_type
SafeElementAt(index_type i
) {
307 return static_cast<Derived
*> (this)->SafeElementAt(i
, nullptr);
310 const elem_type
SafeElementAt(index_type i
) const {
311 return static_cast<const Derived
*> (this)->SafeElementAt(i
, nullptr);
315 // E is the base type that the smart pointer is templated over; the
316 // smart pointer can act as E*.
317 template <class E
, class Derived
>
318 struct nsTArray_SafeElementAtSmartPtrHelper
320 typedef E
* elem_type
;
321 typedef uint32_t index_type
;
323 elem_type
SafeElementAt(index_type i
) {
324 return static_cast<Derived
*> (this)->SafeElementAt(i
, nullptr);
327 const elem_type
SafeElementAt(index_type i
) const {
328 return static_cast<const Derived
*> (this)->SafeElementAt(i
, nullptr);
332 template <class T
> class nsCOMPtr
;
334 template <class E
, class Derived
>
335 struct nsTArray_SafeElementAtHelper
<nsCOMPtr
<E
>, Derived
> :
336 public nsTArray_SafeElementAtSmartPtrHelper
<E
, Derived
>
340 template <class T
> class nsRefPtr
;
342 template <class E
, class Derived
>
343 struct nsTArray_SafeElementAtHelper
<nsRefPtr
<E
>, Derived
> :
344 public nsTArray_SafeElementAtSmartPtrHelper
<E
, Derived
>
349 // This class serves as a base class for nsTArray. It shouldn't be used
350 // directly. It holds common implementation code that does not depend on the
351 // element type of the nsTArray.
353 template<class Alloc
, class Copy
>
356 // Allow swapping elements with |nsTArray_base|s created using a
357 // different allocator. This is kosher because all allocators use
359 template<class Allocator
, class Copier
>
360 friend class nsTArray_base
;
363 typedef nsTArrayHeader Header
;
366 typedef uint32_t size_type
;
367 typedef uint32_t index_type
;
369 // @return The number of elements in the array.
370 size_type
Length() const {
371 return mHdr
->mLength
;
374 // @return True if the array is empty or false otherwise.
375 bool IsEmpty() const {
376 return Length() == 0;
379 // @return The number of elements that can fit in the array without forcing
380 // the array to be re-allocated. The length of an array is always less
381 // than or equal to its capacity.
382 size_type
Capacity() const {
383 return mHdr
->mCapacity
;
387 void* DebugGetHeader() const {
397 // Resize the storage if necessary to achieve the requested capacity.
398 // @param capacity The requested number of array elements.
399 // @param elemSize The size of an array element.
400 // @return False if insufficient memory is available; true otherwise.
401 typename
Alloc::ResultTypeProxy
EnsureCapacity(size_type capacity
, size_type elemSize
);
403 // Resize the storage to the minimum required amount.
404 // @param elemSize The size of an array element.
405 // @param elemAlign The alignment in bytes of an array element.
406 void ShrinkCapacity(size_type elemSize
, size_t elemAlign
);
408 // This method may be called to resize a "gap" in the array by shifting
409 // elements around. It updates mLength appropriately. If the resulting
410 // array has zero elements, then the array's memory is free'd.
411 // @param start The starting index of the gap.
412 // @param oldLen The current length of the gap.
413 // @param newLen The desired length of the gap.
414 // @param elemSize The size of an array element.
415 // @param elemAlign The alignment in bytes of an array element.
416 void ShiftData(index_type start
, size_type oldLen
, size_type newLen
,
417 size_type elemSize
, size_t elemAlign
);
419 // This method increments the length member of the array's header.
420 // Note that mHdr may actually be sEmptyHdr in the case where a
421 // zero-length array is inserted into our array. But then n should
423 void IncrementLength(uint32_t n
) {
424 if (mHdr
== EmptyHdr()) {
425 if (MOZ_UNLIKELY(n
!= 0)) {
426 // Writing a non-zero length to the empty header would be extremely bad.
434 // This method inserts blank slots into the array.
435 // @param index the place to insert the new elements. This must be no
436 // greater than the current length of the array.
437 // @param count the number of slots to insert
438 // @param elementSize the size of an array element.
439 // @param elemAlign the alignment in bytes of an array element.
440 bool InsertSlotsAt(index_type index
, size_type count
,
441 size_type elementSize
, size_t elemAlign
);
444 template<class Allocator
>
445 typename
Alloc::ResultTypeProxy
446 SwapArrayElements(nsTArray_base
<Allocator
, Copy
>& other
,
450 // This is an RAII class used in SwapArrayElements.
451 class IsAutoArrayRestorer
{
453 IsAutoArrayRestorer(nsTArray_base
<Alloc
, Copy
> &array
, size_t elemAlign
);
454 ~IsAutoArrayRestorer();
457 nsTArray_base
<Alloc
, Copy
> &mArray
;
462 // Helper function for SwapArrayElements. Ensures that if the array
463 // is an nsAutoTArray that it doesn't use the built-in buffer.
464 bool EnsureNotUsingAutoArrayBuffer(size_type elemSize
);
466 // Returns true if this nsTArray is an nsAutoTArray with a built-in buffer.
467 bool IsAutoArray() const {
468 return mHdr
->mIsAutoArray
;
471 // Returns a Header for the built-in buffer of this nsAutoTArray.
472 Header
* GetAutoArrayBuffer(size_t elemAlign
) {
473 MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");
474 return GetAutoArrayBufferUnsafe(elemAlign
);
476 const Header
* GetAutoArrayBuffer(size_t elemAlign
) const {
477 MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");
478 return GetAutoArrayBufferUnsafe(elemAlign
);
481 // Returns a Header for the built-in buffer of this nsAutoTArray, but doesn't
482 // assert that we are an nsAutoTArray.
483 Header
* GetAutoArrayBufferUnsafe(size_t elemAlign
) {
484 return const_cast<Header
*>(static_cast<const nsTArray_base
<Alloc
, Copy
>*>(this)->
485 GetAutoArrayBufferUnsafe(elemAlign
));
487 const Header
* GetAutoArrayBufferUnsafe(size_t elemAlign
) const;
489 // Returns true if this is an nsAutoTArray and it currently uses the
490 // built-in buffer to store its elements.
491 bool UsesAutoArrayBuffer() const;
493 // The array's elements (prefixed with a Header). This pointer is never
494 // null. If the array is empty, then this will point to sEmptyHdr.
497 Header
* Hdr() const {
501 Header
** PtrToHdr() {
505 static Header
* EmptyHdr() {
506 return &Header::sEmptyHdr
;
511 // This class defines convenience functions for element specific operations.
512 // Specialize this template if necessary.
515 class nsTArrayElementTraits
518 // Invoke the default constructor in place.
519 static inline void Construct(E
*e
) {
520 // Do NOT call "E()"! That triggers C++ "default initialization"
521 // which zeroes out POD ("plain old data") types such as regular
522 // ints. We don't want that because it can be a performance issue
523 // and people don't expect it; nsTArray should work like a regular
524 // C/C++ array in this respect.
525 new (static_cast<void *>(e
)) E
;
527 // Invoke the copy-constructor in place.
529 static inline void Construct(E
*e
, const A
&arg
) {
530 new (static_cast<void *>(e
)) E(arg
);
532 // Invoke the destructor in place.
533 static inline void Destruct(E
*e
) {
538 // The default comparator used by nsTArray
539 template<class A
, class B
>
540 class nsDefaultComparator
543 bool Equals(const A
& a
, const B
& b
) const {
546 bool LessThan(const A
& a
, const B
& b
) const {
551 template <class E
> class InfallibleTArray
;
552 template <class E
> class FallibleTArray
;
554 template<bool IsPod
, bool IsSameType
>
555 struct AssignRangeAlgorithm
{
556 template<class Item
, class ElemType
, class IndexType
, class SizeType
>
557 static void implementation(ElemType
* elements
, IndexType start
,
558 SizeType count
, const Item
*values
) {
559 ElemType
*iter
= elements
+ start
, *end
= iter
+ count
;
560 for (; iter
!= end
; ++iter
, ++values
)
561 nsTArrayElementTraits
<ElemType
>::Construct(iter
, *values
);
566 struct AssignRangeAlgorithm
<true, true> {
567 template<class Item
, class ElemType
, class IndexType
, class SizeType
>
568 static void implementation(ElemType
* elements
, IndexType start
,
569 SizeType count
, const Item
*values
) {
570 memcpy(elements
+ start
, values
, count
* sizeof(ElemType
));
575 // Normally elements are copied with memcpy and memmove, but for some element
576 // types that is problematic. The nsTArray_CopyElements template class can be
577 // specialized to ensure that copying calls constructors and destructors
578 // instead, as is done below for JS::Heap<E> elements.
582 // A class that defines how to copy elements using memcpy/memmove.
584 struct nsTArray_CopyWithMemutils
586 const static bool allowRealloc
= true;
588 static void CopyElements(void* dest
, const void* src
, size_t count
, size_t elemSize
) {
589 memcpy(dest
, src
, count
* elemSize
);
592 static void CopyHeaderAndElements(void* dest
, const void* src
, size_t count
, size_t elemSize
) {
593 memcpy(dest
, src
, sizeof(nsTArrayHeader
) + count
* elemSize
);
596 static void MoveElements(void* dest
, const void* src
, size_t count
, size_t elemSize
) {
597 memmove(dest
, src
, count
* elemSize
);
602 // A template class that defines how to copy elements calling their constructors
603 // and destructors appropriately.
605 template <class ElemType
>
606 struct nsTArray_CopyWithConstructors
608 typedef nsTArrayElementTraits
<ElemType
> traits
;
610 const static bool allowRealloc
= false;
612 static void CopyElements(void* dest
, void* src
, size_t count
, size_t elemSize
) {
613 ElemType
* destElem
= static_cast<ElemType
*>(dest
);
614 ElemType
* srcElem
= static_cast<ElemType
*>(src
);
615 ElemType
* destElemEnd
= destElem
+ count
;
617 ElemType
* srcElemEnd
= srcElem
+ count
;
618 MOZ_ASSERT(srcElemEnd
<= destElem
|| srcElemEnd
> destElemEnd
);
620 while (destElem
!= destElemEnd
) {
621 traits::Construct(destElem
, *srcElem
);
622 traits::Destruct(srcElem
);
628 static void CopyHeaderAndElements(void* dest
, void* src
, size_t count
, size_t elemSize
) {
629 nsTArrayHeader
* destHeader
= static_cast<nsTArrayHeader
*>(dest
);
630 nsTArrayHeader
* srcHeader
= static_cast<nsTArrayHeader
*>(src
);
631 *destHeader
= *srcHeader
;
632 CopyElements(static_cast<uint8_t*>(dest
) + sizeof(nsTArrayHeader
),
633 static_cast<uint8_t*>(src
) + sizeof(nsTArrayHeader
),
637 static void MoveElements(void* dest
, void* src
, size_t count
, size_t elemSize
) {
638 ElemType
* destElem
= static_cast<ElemType
*>(dest
);
639 ElemType
* srcElem
= static_cast<ElemType
*>(src
);
640 ElemType
* destElemEnd
= destElem
+ count
;
641 ElemType
* srcElemEnd
= srcElem
+ count
;
642 if (destElem
== srcElem
) {
643 return; // In practice, we don't do this.
644 } else if (srcElemEnd
> destElem
&& srcElemEnd
< destElemEnd
) {
645 while (destElemEnd
!= destElem
) {
648 traits::Construct(destElemEnd
, *srcElemEnd
);
649 traits::Destruct(srcElem
);
652 CopyElements(dest
, src
, count
, elemSize
);
658 // The default behaviour is to use memcpy/memmove for everything.
661 struct nsTArray_CopyElements
: public nsTArray_CopyWithMemutils
{};
664 // JS::Heap<E> elements require constructors/destructors to be called and so is
668 struct nsTArray_CopyElements
<JS::Heap
<E
> > : public nsTArray_CopyWithConstructors
<E
> {};
671 // Base class for nsTArray_Impl that is templated on element type and derived
672 // nsTArray_Impl class, to allow extra conversions to be added for specific
675 template <class E
, class Derived
>
676 struct nsTArray_TypedBase
: public nsTArray_SafeElementAtHelper
<E
, Derived
> {};
679 // Specialization of nsTArray_TypedBase for arrays containing JS::Heap<E>
682 // These conversions are safe because JS::Heap<E> and E share the same
683 // representation, and since the result of the conversions are const references
684 // we won't miss any barriers.
686 // The static_cast is necessary to obtain the correct address for the derived
687 // class since we are a base class used in multiple inheritance.
689 template <class E
, class Derived
>
690 struct nsTArray_TypedBase
<JS::Heap
<E
>, Derived
>
691 : public nsTArray_SafeElementAtHelper
<JS::Heap
<E
>, Derived
>
693 operator const nsTArray
<E
>& () {
694 MOZ_STATIC_ASSERT(sizeof(E
) == sizeof(JS::Heap
<E
>),
695 "JS::Heap<E> must be binary compatible with E.");
696 Derived
* self
= static_cast<Derived
*>(this);
697 return *reinterpret_cast<nsTArray
<E
> *>(self
);
700 operator const FallibleTArray
<E
>& () {
701 Derived
* self
= static_cast<Derived
*>(this);
702 return *reinterpret_cast<FallibleTArray
<E
> *>(self
);
708 // nsTArray_Impl contains most of the guts supporting nsTArray, FallibleTArray,
709 // nsAutoTArray, and AutoFallibleTArray.
711 // The only situation in which you might need to use nsTArray_Impl in your code
712 // is if you're writing code which mutates a TArray which may or may not be
715 // Code which merely reads from a TArray which may or may not be infallible can
716 // simply cast the TArray to |const nsTArray&|; both fallible and infallible
717 // TArrays can be cast to |const nsTArray&|.
719 template<class E
, class Alloc
>
720 class nsTArray_Impl
: public nsTArray_base
<Alloc
, nsTArray_CopyElements
<E
> >,
721 public nsTArray_TypedBase
<E
, nsTArray_Impl
<E
, Alloc
> >
724 typedef nsTArray_CopyElements
<E
> copy_type
;
725 typedef nsTArray_base
<Alloc
, copy_type
> base_type
;
726 typedef typename
base_type::size_type size_type
;
727 typedef typename
base_type::index_type index_type
;
729 typedef nsTArray_Impl
<E
, Alloc
> self_type
;
730 typedef nsTArrayElementTraits
<E
> elem_traits
;
731 typedef nsTArray_SafeElementAtHelper
<E
, self_type
> safeelementat_helper_type
;
733 using safeelementat_helper_type::SafeElementAt
;
734 using base_type::EmptyHdr
;
736 // A special value that is used to indicate an invalid or unknown index
739 NoIndex
= index_type(-1)
742 using base_type::Length
;
745 // Finalization method
748 ~nsTArray_Impl() { Clear(); }
751 // Initialization methods
756 // Initialize this array and pre-allocate some number of elements.
757 explicit nsTArray_Impl(size_type capacity
) {
758 SetCapacity(capacity
);
761 // The array's copy-constructor performs a 'deep' copy of the given array.
762 // @param other The array object to copy.
764 // It's very important that we declare this method as taking |const
765 // self_type&| as opposed to taking |const nsTArray_Impl<E, OtherAlloc>| for
766 // an arbitrary OtherAlloc.
768 // If we don't declare a constructor taking |const self_type&|, C++ generates
769 // a copy-constructor for this class which merely copies the object's
770 // members, which is obviously wrong.
772 // You can pass an nsTArray_Impl<E, OtherAlloc> to this method because
773 // nsTArray_Impl<E, X> can be cast to const nsTArray_Impl<E, Y>&. So the
774 // effect on the API is the same as if we'd declared this method as taking
775 // |const nsTArray_Impl<E, OtherAlloc>&|.
776 explicit nsTArray_Impl(const self_type
& other
) {
777 AppendElements(other
);
780 // Allow converting to a const array with a different kind of allocator,
781 // Since the allocator doesn't matter for const arrays
782 template<typename Allocator
>
783 operator const nsTArray_Impl
<E
, Allocator
>&() const {
784 return *reinterpret_cast<const nsTArray_Impl
<E
, Allocator
>*>(this);
786 // And we have to do this for our subclasses too
787 operator const nsTArray
<E
>&() const {
788 return *reinterpret_cast<const InfallibleTArray
<E
>*>(this);
790 operator const FallibleTArray
<E
>&() const {
791 return *reinterpret_cast<const FallibleTArray
<E
>*>(this);
794 // The array's assignment operator performs a 'deep' copy of the given
795 // array. It is optimized to reuse existing storage if possible.
796 // @param other The array object to copy.
797 self_type
& operator=(const self_type
& other
) {
798 ReplaceElementsAt(0, Length(), other
.Elements(), other
.Length());
802 // Return true if this array has the same length and the same
803 // elements as |other|.
804 template<typename Allocator
>
805 bool operator==(const nsTArray_Impl
<E
, Allocator
>& other
) const {
806 size_type len
= Length();
807 if (len
!= other
.Length())
810 // XXX std::equal would be as fast or faster here
811 for (index_type i
= 0; i
< len
; ++i
)
812 if (!(operator[](i
) == other
[i
]))
818 // Return true if this array does not have the same length and the same
819 // elements as |other|.
820 bool operator!=(const self_type
& other
) const {
821 return !operator==(other
);
824 template<typename Allocator
>
825 self_type
& operator=(const nsTArray_Impl
<E
, Allocator
>& other
) {
826 ReplaceElementsAt(0, Length(), other
.Elements(), other
.Length());
830 // @return The amount of memory used by this nsTArray_Impl, excluding
832 size_t SizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf
) const {
833 if (this->UsesAutoArrayBuffer() || Hdr() == EmptyHdr())
835 return mallocSizeOf(this->Hdr());
838 // @return The amount of memory used by this nsTArray_Impl, including
840 size_t SizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf
) const {
841 return mallocSizeOf(this) + SizeOfExcludingThis(mallocSizeOf
);
848 // This method provides direct access to the array elements.
849 // @return A pointer to the first element of the array. If the array is
850 // empty, then this pointer must not be dereferenced.
851 elem_type
* Elements() {
852 return reinterpret_cast<elem_type
*>(Hdr() + 1);
855 // This method provides direct, readonly access to the array elements.
856 // @return A pointer to the first element of the array. If the array is
857 // empty, then this pointer must not be dereferenced.
858 const elem_type
* Elements() const {
859 return reinterpret_cast<const elem_type
*>(Hdr() + 1);
862 // This method provides direct access to the i'th element of the array.
863 // The given index must be within the array bounds.
864 // @param i The index of an element in the array.
865 // @return A reference to the i'th element of the array.
866 elem_type
& ElementAt(index_type i
) {
867 MOZ_ASSERT(i
< Length(), "invalid array index");
868 return Elements()[i
];
871 // This method provides direct, readonly access to the i'th element of the
872 // array. The given index must be within the array bounds.
873 // @param i The index of an element in the array.
874 // @return A const reference to the i'th element of the array.
875 const elem_type
& ElementAt(index_type i
) const {
876 MOZ_ASSERT(i
< Length(), "invalid array index");
877 return Elements()[i
];
880 // This method provides direct access to the i'th element of the array in
881 // a bounds safe manner. If the requested index is out of bounds the
882 // provided default value is returned.
883 // @param i The index of an element in the array.
884 // @param def The value to return if the index is out of bounds.
885 elem_type
& SafeElementAt(index_type i
, elem_type
& def
) {
886 return i
< Length() ? Elements()[i
] : def
;
889 // This method provides direct access to the i'th element of the array in
890 // a bounds safe manner. If the requested index is out of bounds the
891 // provided default value is returned.
892 // @param i The index of an element in the array.
893 // @param def The value to return if the index is out of bounds.
894 const elem_type
& SafeElementAt(index_type i
, const elem_type
& def
) const {
895 return i
< Length() ? Elements()[i
] : def
;
898 // Shorthand for ElementAt(i)
899 elem_type
& operator[](index_type i
) {
903 // Shorthand for ElementAt(i)
904 const elem_type
& operator[](index_type i
) const {
908 // Shorthand for ElementAt(length - 1)
909 elem_type
& LastElement() {
910 return ElementAt(Length() - 1);
913 // Shorthand for ElementAt(length - 1)
914 const elem_type
& LastElement() const {
915 return ElementAt(Length() - 1);
918 // Shorthand for SafeElementAt(length - 1, def)
919 elem_type
& SafeLastElement(elem_type
& def
) {
920 return SafeElementAt(Length() - 1, def
);
923 // Shorthand for SafeElementAt(length - 1, def)
924 const elem_type
& SafeLastElement(const elem_type
& def
) const {
925 return SafeElementAt(Length() - 1, def
);
932 // This method searches for the first element in this array that is equal
933 // to the given element.
934 // @param item The item to search for.
935 // @param comp The Comparator used to determine element equality.
936 // @return true if the element was found.
937 template<class Item
, class Comparator
>
938 bool Contains(const Item
& item
, const Comparator
& comp
) const {
939 return IndexOf(item
, 0, comp
) != NoIndex
;
942 // This method searches for the first element in this array that is equal
943 // to the given element. This method assumes that 'operator==' is defined
945 // @param item The item to search for.
946 // @return true if the element was found.
948 bool Contains(const Item
& item
) const {
949 return IndexOf(item
) != NoIndex
;
952 // This method searches for the offset of the first element in this
953 // array that is equal to the given element.
954 // @param item The item to search for.
955 // @param start The index to start from.
956 // @param comp The Comparator used to determine element equality.
957 // @return The index of the found element or NoIndex if not found.
958 template<class Item
, class Comparator
>
959 index_type
IndexOf(const Item
& item
, index_type start
,
960 const Comparator
& comp
) const {
961 const elem_type
* iter
= Elements() + start
, *end
= Elements() + Length();
962 for (; iter
!= end
; ++iter
) {
963 if (comp
.Equals(*iter
, item
))
964 return index_type(iter
- Elements());
969 // This method searches for the offset of the first element in this
970 // array that is equal to the given element. This method assumes
971 // that 'operator==' is defined for elem_type.
972 // @param item The item to search for.
973 // @param start The index to start from.
974 // @return The index of the found element or NoIndex if not found.
976 index_type
IndexOf(const Item
& item
, index_type start
= 0) const {
977 return IndexOf(item
, start
, nsDefaultComparator
<elem_type
, Item
>());
980 // This method searches for the offset of the last element in this
981 // array that is equal to the given element.
982 // @param item The item to search for.
983 // @param start The index to start from. If greater than or equal to the
984 // length of the array, then the entire array is searched.
985 // @param comp The Comparator used to determine element equality.
986 // @return The index of the found element or NoIndex if not found.
987 template<class Item
, class Comparator
>
988 index_type
LastIndexOf(const Item
& item
, index_type start
,
989 const Comparator
& comp
) const {
990 size_type endOffset
= start
>= Length() ? Length() : start
+ 1;
991 const elem_type
* end
= Elements() - 1, *iter
= end
+ endOffset
;
992 for (; iter
!= end
; --iter
) {
993 if (comp
.Equals(*iter
, item
))
994 return index_type(iter
- Elements());
999 // This method searches for the offset of the last element in this
1000 // array that is equal to the given element. This method assumes
1001 // that 'operator==' is defined for elem_type.
1002 // @param item The item to search for.
1003 // @param start The index to start from. If greater than or equal to the
1004 // length of the array, then the entire array is searched.
1005 // @return The index of the found element or NoIndex if not found.
1006 template<class Item
>
1007 index_type
LastIndexOf(const Item
& item
,
1008 index_type start
= NoIndex
) const {
1009 return LastIndexOf(item
, start
, nsDefaultComparator
<elem_type
, Item
>());
1012 // This method searches for the offset for the element in this array
1013 // that is equal to the given element. The array is assumed to be sorted.
1014 // @param item The item to search for.
1015 // @param comp The Comparator used.
1016 // @return The index of the found element or NoIndex if not found.
1017 template<class Item
, class Comparator
>
1018 index_type
BinaryIndexOf(const Item
& item
, const Comparator
& comp
) const {
1019 index_type low
= 0, high
= Length();
1020 while (high
> low
) {
1021 index_type mid
= (high
+ low
) >> 1;
1022 if (comp
.Equals(ElementAt(mid
), item
))
1024 if (comp
.LessThan(ElementAt(mid
), item
))
1032 // This method searches for the offset for the element in this array
1033 // that is equal to the given element. The array is assumed to be sorted.
1034 // This method assumes that 'operator==' and 'operator<' are defined.
1035 // @param item The item to search for.
1036 // @return The index of the found element or NoIndex if not found.
1037 template<class Item
>
1038 index_type
BinaryIndexOf(const Item
& item
) const {
1039 return BinaryIndexOf(item
, nsDefaultComparator
<elem_type
, Item
>());
1045 // This method call the destructor on each element of the array, empties it,
1046 // but does not shrink the array's capacity.
1048 // Make sure to call Compact() if needed to avoid keeping a huge array
1050 void ClearAndRetainStorage() {
1051 if (base_type::mHdr
== EmptyHdr()) {
1055 DestructRange(0, Length());
1056 base_type::mHdr
->mLength
= 0;
1060 // This method replaces a range of elements in this array.
1061 // @param start The starting index of the elements to replace.
1062 // @param count The number of elements to replace. This may be zero to
1063 // insert elements without removing any existing elements.
1064 // @param array The values to copy into this array. Must be non-null,
1065 // and these elements must not already exist in the array
1067 // @param arrayLen The number of values to copy into this array.
1068 // @return A pointer to the new elements in the array, or null if
1069 // the operation failed due to insufficient memory.
1070 template<class Item
>
1071 elem_type
*ReplaceElementsAt(index_type start
, size_type count
,
1072 const Item
* array
, size_type arrayLen
) {
1073 // Adjust memory allocation up-front to catch errors.
1074 if (!Alloc::Successful(this->EnsureCapacity(Length() + arrayLen
- count
, sizeof(elem_type
))))
1076 DestructRange(start
, count
);
1077 this->ShiftData(start
, count
, arrayLen
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
1078 AssignRange(start
, arrayLen
, array
);
1079 return Elements() + start
;
1082 // A variation on the ReplaceElementsAt method defined above.
1083 template<class Item
>
1084 elem_type
*ReplaceElementsAt(index_type start
, size_type count
,
1085 const nsTArray
<Item
>& array
) {
1086 return ReplaceElementsAt(start
, count
, array
.Elements(), array
.Length());
1089 // A variation on the ReplaceElementsAt method defined above.
1090 template<class Item
>
1091 elem_type
*ReplaceElementsAt(index_type start
, size_type count
,
1093 return ReplaceElementsAt(start
, count
, &item
, 1);
1096 // A variation on the ReplaceElementsAt method defined above.
1097 template<class Item
>
1098 elem_type
*ReplaceElementAt(index_type index
, const Item
& item
) {
1099 return ReplaceElementsAt(index
, 1, &item
, 1);
1102 // A variation on the ReplaceElementsAt method defined above.
1103 template<class Item
>
1104 elem_type
*InsertElementsAt(index_type index
, const Item
* array
,
1105 size_type arrayLen
) {
1106 return ReplaceElementsAt(index
, 0, array
, arrayLen
);
1109 // A variation on the ReplaceElementsAt method defined above.
1110 template<class Item
, class Allocator
>
1111 elem_type
*InsertElementsAt(index_type index
, const nsTArray_Impl
<Item
, Allocator
>& array
) {
1112 return ReplaceElementsAt(index
, 0, array
.Elements(), array
.Length());
1115 // A variation on the ReplaceElementsAt method defined above.
1116 template<class Item
>
1117 elem_type
*InsertElementAt(index_type index
, const Item
& item
) {
1118 return ReplaceElementsAt(index
, 0, &item
, 1);
1121 // Insert a new element without copy-constructing. This is useful to avoid
1123 // @return A pointer to the newly inserted element, or null on OOM.
1124 elem_type
* InsertElementAt(index_type index
) {
1125 if (!Alloc::Successful(this->EnsureCapacity(Length() + 1, sizeof(elem_type
))))
1127 this->ShiftData(index
, 0, 1, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
1128 elem_type
*elem
= Elements() + index
;
1129 elem_traits::Construct(elem
);
1133 // This method searches for the smallest index of an element that is strictly
1134 // greater than |item|. If |item| is inserted at this index, the array will
1135 // remain sorted and |item| would come after all elements that are equal to
1136 // it. If |item| is greater than or equal to all elements in the array, the
1137 // array length is returned.
1139 // Note that consumers who want to know whether there are existing items equal
1140 // to |item| in the array can just check that the return value here is > 0 and
1141 // indexing into the previous slot gives something equal to |item|.
1144 // @param item The item to search for.
1145 // @param comp The Comparator used.
1146 // @return The index of greatest element <= to |item|
1147 // @precondition The array is sorted
1148 template<class Item
, class Comparator
>
1150 IndexOfFirstElementGt(const Item
& item
,
1151 const Comparator
& comp
) const {
1152 // invariant: low <= [idx] <= high
1153 index_type low
= 0, high
= Length();
1154 while (high
> low
) {
1155 index_type mid
= (high
+ low
) >> 1;
1156 // Comparators are not required to provide a LessThan(Item&, elem_type),
1157 // so we can't do comp.LessThan(item, ElementAt(mid)).
1158 if (comp
.LessThan(ElementAt(mid
), item
) ||
1159 comp
.Equals(ElementAt(mid
), item
)) {
1160 // item >= ElementAt(mid), so our desired index is at least mid+1.
1163 // item < ElementAt(mid). Our desired index is therefore at most mid.
1167 MOZ_ASSERT(high
== low
);
1171 // A variation on the IndexOfFirstElementGt method defined above.
1172 template<class Item
>
1174 IndexOfFirstElementGt(const Item
& item
) const {
1175 return IndexOfFirstElementGt(item
, nsDefaultComparator
<elem_type
, Item
>());
1178 // Inserts |item| at such an index to guarantee that if the array
1179 // was previously sorted, it will remain sorted after this
1181 template<class Item
, class Comparator
>
1182 elem_type
*InsertElementSorted(const Item
& item
, const Comparator
& comp
) {
1183 index_type index
= IndexOfFirstElementGt(item
, comp
);
1184 return InsertElementAt(index
, item
);
1187 // A variation on the InsertElementSorted method defined above.
1188 template<class Item
>
1189 elem_type
*InsertElementSorted(const Item
& item
) {
1190 return InsertElementSorted(item
, nsDefaultComparator
<elem_type
, Item
>());
1193 // This method appends elements to the end of this array.
1194 // @param array The elements to append to this array.
1195 // @param arrayLen The number of elements to append to this array.
1196 // @return A pointer to the new elements in the array, or null if
1197 // the operation failed due to insufficient memory.
1198 template<class Item
>
1199 elem_type
*AppendElements(const Item
* array
, size_type arrayLen
) {
1200 if (!Alloc::Successful(this->EnsureCapacity(Length() + arrayLen
, sizeof(elem_type
))))
1202 index_type len
= Length();
1203 AssignRange(len
, arrayLen
, array
);
1204 this->IncrementLength(arrayLen
);
1205 return Elements() + len
;
1208 // A variation on the AppendElements method defined above.
1209 template<class Item
, class Allocator
>
1210 elem_type
*AppendElements(const nsTArray_Impl
<Item
, Allocator
>& array
) {
1211 return AppendElements(array
.Elements(), array
.Length());
1214 // A variation on the AppendElements method defined above.
1215 template<class Item
>
1216 elem_type
*AppendElement(const Item
& item
) {
1217 return AppendElements(&item
, 1);
1220 // Append new elements without copy-constructing. This is useful to avoid
1222 // @return A pointer to the newly appended elements, or null on OOM.
1223 elem_type
*AppendElements(size_type count
) {
1224 if (!Alloc::Successful(this->EnsureCapacity(Length() + count
, sizeof(elem_type
))))
1226 elem_type
*elems
= Elements() + Length();
1228 for (i
= 0; i
< count
; ++i
) {
1229 elem_traits::Construct(elems
+ i
);
1231 this->IncrementLength(count
);
1235 // Append a new element without copy-constructing. This is useful to avoid
1237 // @return A pointer to the newly appended element, or null on OOM.
1238 elem_type
*AppendElement() {
1239 return AppendElements(1);
1242 // Move all elements from another array to the end of this array without
1243 // calling copy constructors or destructors.
1244 // @return A pointer to the newly appended elements, or null on OOM.
1245 template<class Item
, class Allocator
>
1246 elem_type
*MoveElementsFrom(nsTArray_Impl
<Item
, Allocator
>& array
) {
1247 MOZ_ASSERT(&array
!= this, "argument must be different array");
1248 index_type len
= Length();
1249 index_type otherLen
= array
.Length();
1250 if (!Alloc::Successful(this->EnsureCapacity(len
+ otherLen
, sizeof(elem_type
))))
1252 copy_type::CopyElements(Elements() + len
, array
.Elements(), otherLen
, sizeof(elem_type
));
1253 this->IncrementLength(otherLen
);
1254 array
.ShiftData(0, otherLen
, 0, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
1255 return Elements() + len
;
1258 // This method removes a range of elements from this array.
1259 // @param start The starting index of the elements to remove.
1260 // @param count The number of elements to remove.
1261 void RemoveElementsAt(index_type start
, size_type count
) {
1262 MOZ_ASSERT(count
== 0 || start
< Length(), "Invalid start index");
1263 MOZ_ASSERT(start
+ count
<= Length(), "Invalid length");
1264 // Check that the previous assert didn't overflow
1265 MOZ_ASSERT(start
<= start
+ count
, "Start index plus length overflows");
1266 DestructRange(start
, count
);
1267 this->ShiftData(start
, count
, 0, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
1270 // A variation on the RemoveElementsAt method defined above.
1271 void RemoveElementAt(index_type index
) {
1272 RemoveElementsAt(index
, 1);
1275 // A variation on the RemoveElementsAt method defined above.
1277 RemoveElementsAt(0, Length());
1280 // This helper function combines IndexOf with RemoveElementAt to "search
1281 // and destroy" the first element that is equal to the given element.
1282 // @param item The item to search for.
1283 // @param comp The Comparator used to determine element equality.
1284 // @return true if the element was found
1285 template<class Item
, class Comparator
>
1286 bool RemoveElement(const Item
& item
, const Comparator
& comp
) {
1287 index_type i
= IndexOf(item
, 0, comp
);
1295 // A variation on the RemoveElement method defined above that assumes
1296 // that 'operator==' is defined for elem_type.
1297 template<class Item
>
1298 bool RemoveElement(const Item
& item
) {
1299 return RemoveElement(item
, nsDefaultComparator
<elem_type
, Item
>());
1302 // This helper function combines IndexOfFirstElementGt with
1303 // RemoveElementAt to "search and destroy" the last element that
1304 // is equal to the given element.
1305 // @param item The item to search for.
1306 // @param comp The Comparator used to determine element equality.
1307 // @return true if the element was found
1308 template<class Item
, class Comparator
>
1309 bool RemoveElementSorted(const Item
& item
, const Comparator
& comp
) {
1310 index_type index
= IndexOfFirstElementGt(item
, comp
);
1311 if (index
> 0 && comp
.Equals(ElementAt(index
- 1), item
)) {
1312 RemoveElementAt(index
- 1);
1318 // A variation on the RemoveElementSorted method defined above.
1319 template<class Item
>
1320 bool RemoveElementSorted(const Item
& item
) {
1321 return RemoveElementSorted(item
, nsDefaultComparator
<elem_type
, Item
>());
1324 // This method causes the elements contained in this array and the given
1325 // array to be swapped.
1326 template<class Allocator
>
1327 typename
Alloc::ResultType
1328 SwapElements(nsTArray_Impl
<E
, Allocator
>& other
) {
1329 return Alloc::Result(this->SwapArrayElements(other
, sizeof(elem_type
),
1330 MOZ_ALIGNOF(elem_type
)));
1337 // This method may increase the capacity of this array object by the
1338 // specified amount. This method may be called in advance of several
1339 // AppendElement operations to minimize heap re-allocations. This method
1340 // will not reduce the number of elements in this array.
1341 // @param capacity The desired capacity of this array.
1342 // @return True if the operation succeeded; false if we ran out of memory
1343 typename
Alloc::ResultType
SetCapacity(size_type capacity
) {
1344 return Alloc::Result(this->EnsureCapacity(capacity
, sizeof(elem_type
)));
1347 // This method modifies the length of the array. If the new length is
1348 // larger than the existing length of the array, then new elements will be
1349 // constructed using elem_type's default constructor. Otherwise, this call
1350 // removes elements from the array (see also RemoveElementsAt).
1351 // @param newLen The desired length of this array.
1352 // @return True if the operation succeeded; false otherwise.
1353 // See also TruncateLength if the new length is guaranteed to be
1354 // smaller than the old.
1355 bool SetLength(size_type newLen
) {
1356 size_type oldLen
= Length();
1357 if (newLen
> oldLen
) {
1358 return InsertElementsAt(oldLen
, newLen
- oldLen
) != nullptr;
1361 TruncateLength(newLen
);
1365 // This method modifies the length of the array, but may only be
1366 // called when the new length is shorter than the old. It can
1367 // therefore be called when elem_type has no default constructor,
1368 // unlike SetLength. It removes elements from the array (see also
1369 // RemoveElementsAt).
1370 // @param newLen The desired length of this array.
1371 void TruncateLength(size_type newLen
) {
1372 size_type oldLen
= Length();
1373 NS_ABORT_IF_FALSE(newLen
<= oldLen
,
1374 "caller should use SetLength instead");
1375 RemoveElementsAt(newLen
, oldLen
- newLen
);
1378 // This method ensures that the array has length at least the given
1379 // length. If the current length is shorter than the given length,
1380 // then new elements will be constructed using elem_type's default
1382 // @param minLen The desired minimum length of this array.
1383 // @return True if the operation succeeded; false otherwise.
1384 typename
Alloc::ResultType
EnsureLengthAtLeast(size_type minLen
) {
1385 size_type oldLen
= Length();
1386 if (minLen
> oldLen
) {
1387 return Alloc::ConvertBoolToResultType(!!InsertElementsAt(oldLen
, minLen
- oldLen
));
1389 return Alloc::ConvertBoolToResultType(true);
1392 // This method inserts elements into the array, constructing
1393 // them using elem_type's default constructor.
1394 // @param index the place to insert the new elements. This must be no
1395 // greater than the current length of the array.
1396 // @param count the number of elements to insert
1397 elem_type
*InsertElementsAt(index_type index
, size_type count
) {
1398 if (!base_type::InsertSlotsAt(index
, count
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
))) {
1402 // Initialize the extra array elements
1403 elem_type
*iter
= Elements() + index
, *end
= iter
+ count
;
1404 for (; iter
!= end
; ++iter
) {
1405 elem_traits::Construct(iter
);
1408 return Elements() + index
;
1411 // This method inserts elements into the array, constructing them
1412 // elem_type's copy constructor (or whatever one-arg constructor
1413 // happens to match the Item type).
1414 // @param index the place to insert the new elements. This must be no
1415 // greater than the current length of the array.
1416 // @param count the number of elements to insert.
1417 // @param item the value to use when constructing the new elements.
1418 template<class Item
>
1419 elem_type
*InsertElementsAt(index_type index
, size_type count
,
1421 if (!base_type::InsertSlotsAt(index
, count
, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
))) {
1425 // Initialize the extra array elements
1426 elem_type
*iter
= Elements() + index
, *end
= iter
+ count
;
1427 for (; iter
!= end
; ++iter
) {
1428 elem_traits::Construct(iter
, item
);
1431 return Elements() + index
;
1434 // This method may be called to minimize the memory used by this array.
1436 ShrinkCapacity(sizeof(elem_type
), MOZ_ALIGNOF(elem_type
));
1443 // This function is meant to be used with the NS_QuickSort function. It
1444 // maps the callback API expected by NS_QuickSort to the Comparator API
1445 // used by nsTArray_Impl. See nsTArray_Impl::Sort.
1446 template<class Comparator
>
1447 static int Compare(const void* e1
, const void* e2
, void *data
) {
1448 const Comparator
* c
= reinterpret_cast<const Comparator
*>(data
);
1449 const elem_type
* a
= static_cast<const elem_type
*>(e1
);
1450 const elem_type
* b
= static_cast<const elem_type
*>(e2
);
1451 return c
->LessThan(*a
, *b
) ? -1 : (c
->Equals(*a
, *b
) ? 0 : 1);
1454 // This method sorts the elements of the array. It uses the LessThan
1455 // method defined on the given Comparator object to collate elements.
1456 // @param comp The Comparator used to collate elements.
1457 template<class Comparator
>
1458 void Sort(const Comparator
& comp
) {
1459 NS_QuickSort(Elements(), Length(), sizeof(elem_type
),
1460 Compare
<Comparator
>, const_cast<Comparator
*>(&comp
));
1463 // A variation on the Sort method defined above that assumes that
1464 // 'operator<' is defined for elem_type.
1466 Sort(nsDefaultComparator
<elem_type
, elem_type
>());
1473 // Sorts the array into a binary heap.
1474 // @param comp The Comparator used to create the heap
1475 template<class Comparator
>
1476 void MakeHeap(const Comparator
& comp
) {
1480 index_type index
= (Length() - 1) / 2;
1482 SiftDown(index
, comp
);
1486 // A variation on the MakeHeap method defined above.
1488 MakeHeap(nsDefaultComparator
<elem_type
, elem_type
>());
1491 // Adds an element to the heap
1492 // @param item The item to add
1493 // @param comp The Comparator used to sift-up the item
1494 template<class Item
, class Comparator
>
1495 elem_type
*PushHeap(const Item
& item
, const Comparator
& comp
) {
1496 if (!base_type::InsertSlotsAt(Length(), 1, sizeof(elem_type
), MOZ_ALIGNOF(elem_type
))) {
1499 // Sift up the new node
1500 elem_type
*elem
= Elements();
1501 index_type index
= Length() - 1;
1502 index_type parent_index
= (index
- 1) / 2;
1503 while (index
&& comp
.LessThan(elem
[parent_index
], item
)) {
1504 elem
[index
] = elem
[parent_index
];
1505 index
= parent_index
;
1506 parent_index
= (index
- 1) / 2;
1509 return &elem
[index
];
1512 // A variation on the PushHeap method defined above.
1513 template<class Item
>
1514 elem_type
*PushHeap(const Item
& item
) {
1515 return PushHeap(item
, nsDefaultComparator
<elem_type
, Item
>());
1518 // Delete the root of the heap and restore the heap
1519 // @param comp The Comparator used to restore the heap
1520 template<class Comparator
>
1521 void PopHeap(const Comparator
& comp
) {
1525 index_type last_index
= Length() - 1;
1526 elem_type
*elem
= Elements();
1527 elem
[0] = elem
[last_index
];
1528 TruncateLength(last_index
);
1534 // A variation on the PopHeap method defined above.
1536 PopHeap(nsDefaultComparator
<elem_type
, elem_type
>());
1540 using base_type::Hdr
;
1541 using base_type::ShrinkCapacity
;
1543 // This method invokes elem_type's destructor on a range of elements.
1544 // @param start The index of the first element to destroy.
1545 // @param count The number of elements to destroy.
1546 void DestructRange(index_type start
, size_type count
) {
1547 elem_type
*iter
= Elements() + start
, *end
= iter
+ count
;
1548 for (; iter
!= end
; ++iter
) {
1549 elem_traits::Destruct(iter
);
1553 // This method invokes elem_type's copy-constructor on a range of elements.
1554 // @param start The index of the first element to construct.
1555 // @param count The number of elements to construct.
1556 // @param values The array of elements to copy.
1557 template<class Item
>
1558 void AssignRange(index_type start
, size_type count
,
1559 const Item
*values
) {
1560 AssignRangeAlgorithm
<mozilla::IsPod
<Item
>::value
,
1561 mozilla::IsSame
<Item
, elem_type
>::value
>
1562 ::implementation(Elements(), start
, count
, values
);
1565 // This method sifts an item down to its proper place in a binary heap
1566 // @param index The index of the node to start sifting down from
1567 // @param comp The Comparator used to sift down
1568 template<class Comparator
>
1569 void SiftDown(index_type index
, const Comparator
& comp
) {
1570 elem_type
*elem
= Elements();
1571 elem_type item
= elem
[index
];
1572 index_type end
= Length() - 1;
1573 while ((index
* 2) < end
) {
1574 const index_type left
= (index
* 2) + 1;
1575 const index_type right
= (index
* 2) + 2;
1576 const index_type parent_index
= index
;
1577 if (comp
.LessThan(item
, elem
[left
])) {
1579 comp
.LessThan(elem
[left
], elem
[right
])) {
1584 } else if (left
< end
&&
1585 comp
.LessThan(item
, elem
[right
])) {
1590 elem
[parent_index
] = elem
[index
];
1596 template <typename E
, typename Alloc
>
1598 ImplCycleCollectionUnlink(nsTArray_Impl
<E
, Alloc
>& aField
)
1603 template <typename E
, typename Alloc
>
1605 ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback
& aCallback
,
1606 nsTArray_Impl
<E
, Alloc
>& aField
,
1608 uint32_t aFlags
= 0)
1610 aFlags
|= CycleCollectionEdgeNameArrayFlag
;
1611 size_t length
= aField
.Length();
1612 for (size_t i
= 0; i
< length
; ++i
) {
1613 ImplCycleCollectionTraverse(aCallback
, aField
[i
], aName
, aFlags
);
1618 // nsTArray is an infallible vector class. See the comment at the top of this
1619 // file for more details.
1622 class nsTArray
: public nsTArray_Impl
<E
, nsTArrayInfallibleAllocator
>
1625 typedef nsTArray_Impl
<E
, nsTArrayInfallibleAllocator
> base_type
;
1626 typedef nsTArray
<E
> self_type
;
1627 typedef typename
base_type::size_type size_type
;
1630 explicit nsTArray(size_type capacity
) : base_type(capacity
) {}
1631 explicit nsTArray(const nsTArray
& other
) : base_type(other
) {}
1633 template<class Allocator
>
1634 explicit nsTArray(const nsTArray_Impl
<E
, Allocator
>& other
) : base_type(other
) {}
1638 // FallibleTArray is a fallible vector class.
1641 class FallibleTArray
: public nsTArray_Impl
<E
, nsTArrayFallibleAllocator
>
1644 typedef nsTArray_Impl
<E
, nsTArrayFallibleAllocator
> base_type
;
1645 typedef FallibleTArray
<E
> self_type
;
1646 typedef typename
base_type::size_type size_type
;
1649 explicit FallibleTArray(size_type capacity
) : base_type(capacity
) {}
1650 explicit FallibleTArray(const FallibleTArray
<E
>& other
) : base_type(other
) {}
1652 template<class Allocator
>
1653 explicit FallibleTArray(const nsTArray_Impl
<E
, Allocator
>& other
) : base_type(other
) {}
1657 // nsAutoArrayBase is a base class for AutoFallibleTArray and nsAutoTArray.
1658 // You shouldn't use this class directly.
1660 template <class TArrayBase
, uint32_t N
>
1661 class nsAutoArrayBase
: public TArrayBase
1664 typedef nsAutoArrayBase
<TArrayBase
, N
> self_type
;
1665 typedef TArrayBase base_type
;
1666 typedef typename
base_type::Header Header
;
1667 typedef typename
base_type::elem_type elem_type
;
1669 template<typename Allocator
>
1670 self_type
& operator=(const nsTArray_Impl
<elem_type
, Allocator
>& other
) {
1671 base_type::operator=(other
);
1680 // We need this constructor because nsAutoTArray and friends all have
1681 // implicit copy-constructors. If we don't have this method, those
1682 // copy-constructors will call nsAutoArrayBase's implicit copy-constructor,
1683 // which won't call Init() and set up the auto buffer!
1684 nsAutoArrayBase(const TArrayBase
&aOther
) {
1686 AppendElements(aOther
);
1690 // nsTArray_base casts itself as an nsAutoArrayBase in order to get a pointer
1692 template<class Allocator
, class Copier
>
1693 friend class nsTArray_base
;
1696 MOZ_STATIC_ASSERT(MOZ_ALIGNOF(elem_type
) <= 8,
1697 "can't handle alignments greater than 8, "
1698 "see nsTArray_base::UsesAutoArrayBuffer()");
1699 // Temporary work around for VS2012 RC compiler crash
1700 Header
** phdr
= base_type::PtrToHdr();
1701 *phdr
= reinterpret_cast<Header
*>(&mAutoBuf
);
1702 (*phdr
)->mLength
= 0;
1703 (*phdr
)->mCapacity
= N
;
1704 (*phdr
)->mIsAutoArray
= 1;
1706 MOZ_ASSERT(base_type::GetAutoArrayBuffer(MOZ_ALIGNOF(elem_type
)) ==
1707 reinterpret_cast<Header
*>(&mAutoBuf
),
1708 "GetAutoArrayBuffer needs to be fixed");
1711 // Declare mAutoBuf aligned to the maximum of the header's alignment and
1712 // elem_type's alignment. We need to use a union rather than
1713 // MOZ_ALIGNED_DECL because GCC is picky about what goes into
1714 // __attribute__((aligned(foo))).
1716 char mAutoBuf
[sizeof(nsTArrayHeader
) + N
* sizeof(elem_type
)];
1717 // Do the max operation inline to ensure that it is a compile-time constant.
1718 mozilla::AlignedElem
<(MOZ_ALIGNOF(Header
) > MOZ_ALIGNOF(elem_type
))
1719 ? MOZ_ALIGNOF(Header
) : MOZ_ALIGNOF(elem_type
)> mAlign
;
1724 // nsAutoTArray<E, N> is an infallible vector class with N elements of inline
1725 // storage. If you try to store more than N elements inside an
1726 // nsAutoTArray<E, N>, we'll call malloc() and store them all on the heap.
1728 // Note that you can cast an nsAutoTArray<E, N> to
1729 // |const AutoFallibleTArray<E, N>&|.
1731 template<class E
, uint32_t N
>
1732 class nsAutoTArray
: public nsAutoArrayBase
<nsTArray
<E
>, N
>
1734 typedef nsAutoTArray
<E
, N
> self_type
;
1735 typedef nsAutoArrayBase
<nsTArray
<E
>, N
> Base
;
1740 template<typename Allocator
>
1741 explicit nsAutoTArray(const nsTArray_Impl
<E
, Allocator
>& other
) {
1742 Base::AppendElements(other
);
1745 operator const AutoFallibleTArray
<E
, N
>&() const {
1746 return *reinterpret_cast<const AutoFallibleTArray
<E
, N
>*>(this);
1751 // AutoFallibleTArray<E, N> is a fallible vector class with N elements of
1754 template<class E
, uint32_t N
>
1755 class AutoFallibleTArray
: public nsAutoArrayBase
<FallibleTArray
<E
>, N
>
1757 typedef AutoFallibleTArray
<E
, N
> self_type
;
1758 typedef nsAutoArrayBase
<FallibleTArray
<E
>, N
> Base
;
1761 AutoFallibleTArray() {}
1763 template<typename Allocator
>
1764 explicit AutoFallibleTArray(const nsTArray_Impl
<E
, Allocator
>& other
) {
1765 Base::AppendElements(other
);
1768 operator const nsAutoTArray
<E
, N
>&() const {
1769 return *reinterpret_cast<const nsAutoTArray
<E
, N
>*>(this);
1773 // Assert that nsAutoTArray doesn't have any extra padding inside.
1775 // It's important that the data stored in this auto array takes up a multiple of
1776 // 8 bytes; e.g. nsAutoTArray<uint32_t, 1> wouldn't work. Since nsAutoTArray
1777 // contains a pointer, its size must be a multiple of alignof(void*). (This is
1778 // because any type may be placed into an array, and there's no padding between
1779 // elements of an array.) The compiler pads the end of the structure to
1780 // enforce this rule.
1782 // If we used nsAutoTArray<uint32_t, 1> below, this assertion would fail on a
1783 // 64-bit system, where the compiler inserts 4 bytes of padding at the end of
1784 // the auto array to make its size a multiple of alignof(void*) == 8 bytes.
1786 MOZ_STATIC_ASSERT(sizeof(nsAutoTArray
<uint32_t, 2>) ==
1787 sizeof(void*) + sizeof(nsTArrayHeader
) + sizeof(uint32_t) * 2,
1788 "nsAutoTArray shouldn't contain any extra padding, "
1791 // Definitions of nsTArray_Impl methods
1792 #include "nsTArray-inl.h"
1794 #endif // nsTArray_h__