The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

 /* vim:set ts=2 sw=2 sts=2 et cindent: */

 /* This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 #ifndef nsTArray_h__

 #define nsTArray_h__

 #include "nsTArrayForwardDeclare.h"

 #include "mozilla/Alignment.h"

 #include "mozilla/Assertions.h"

 #include "mozilla/MemoryReporting.h"

 #include "mozilla/TypeTraits.h"

 #include <string.h>

 #include "nsCycleCollectionNoteChild.h"

 #include "nsAlgorithm.h"

 #include "nscore.h"

 #include "nsQuickSort.h"

 #include "nsDebug.h"

 #include "nsISupportsImpl.h"

 #include <new>

 namespace JS {

 template <class T>

 class Heap;

 } /* namespace JS */

 class nsRegion;

 class nsIntRegion;

 //

 // nsTArray is a resizable array class, like std::vector.

 //

 // Unlike std::vector, which follows C++'s construction/destruction rules,

 // nsTArray assumes that your "T" can be memmoved()'ed safely.

 //

 // The public classes defined in this header are

 //

 //   nsTArray<T>,

 //   FallibleTArray<T>,

 //   nsAutoTArray<T, N>, and

 //   AutoFallibleTArray<T, N>.

 //

 // nsTArray and nsAutoTArray are infallible; if one tries to make an allocation

 // which fails, it crashes the program.  In contrast, FallibleTArray and

 // AutoFallibleTArray are fallible; if you use one of these classes, you must

 // check the return values of methods such as Append() which may allocate.  If

 // in doubt, choose an infallible type.

 //

 // InfallibleTArray and AutoInfallibleTArray are aliases for nsTArray and

 // nsAutoTArray.

 //

 // If you just want to declare the nsTArray types (e.g., if you're in a header

 // file and don't need the full nsTArray definitions) consider including

 // nsTArrayForwardDeclare.h instead of nsTArray.h.

 //

 // The template parameter (i.e., T in nsTArray<T>) specifies the type of the

 // elements and has the following requirements:

 //

 //   T MUST be safely memmove()'able.

 //   T MUST define a copy-constructor.

 //   T MAY define operator< for sorting.

 //   T MAY define operator== for searching.

 //

 // (Note that the memmove requirement may be relaxed for certain types - see

 // nsTArray_CopyChooser below.)

 //

 // For methods taking a Comparator instance, the Comparator must be a class

 // defining the following methods:

 //

 //   class Comparator {

 //     public:

 //       /** @return True if the elements are equals; false otherwise. */

 //       bool Equals(const elem_type& a, const Item& b) const;

 //

 //       /** @return True if (a < b); false otherwise. */

 //       bool LessThan(const elem_type& a, const Item& b) const;

 //   };

 //

 // The Equals method is used for searching, and the LessThan method is used for

 // searching and sorting.  The |Item| type above can be arbitrary, but must

 // match the Item type passed to the sort or search function.

 //

 //

 // nsTArrayFallibleResult and nsTArrayInfallibleResult types are proxy types

 // which are used because you cannot use a templated type which is bound to

 // void as an argument to a void function.  In order to work around that, we

 // encode either a void or a boolean inside these proxy objects, and pass them

 // to the aforementioned function instead, and then use the type information to

 // decide what to do in the function.

 //

 // Note that public nsTArray methods should never return a proxy type.  Such

 // types are only meant to be used in the internal nsTArray helper methods.

 // Public methods returning non-proxy types cannot be called from other

 // nsTArray members.

 //

 struct nsTArrayFallibleResult

 {

   // Note: allows implicit conversions from and to bool

   nsTArrayFallibleResult(bool result)

     : mResult(result)

   {}

   operator bool() {

     return mResult;

   }

 private:

   bool mResult;

 };

 struct nsTArrayInfallibleResult

 {

 };

 //

 // nsTArray*Allocators must all use the same |free()|, to allow swap()'ing

 // between fallible and infallible variants.

 //

 struct nsTArrayFallibleAllocatorBase

 {

   typedef bool ResultType;

   typedef nsTArrayFallibleResult ResultTypeProxy;

   static ResultType Result(ResultTypeProxy result) {

     return result;

   }

   static bool Successful(ResultTypeProxy result) {

     return result;

   }

   static ResultTypeProxy SuccessResult() {

     return true;

   }

   static ResultTypeProxy FailureResult() {

     return false;

   }

   static ResultType ConvertBoolToResultType(bool aValue) {

     return aValue;

   }

 };

 struct nsTArrayInfallibleAllocatorBase

 {

   typedef void ResultType;

   typedef nsTArrayInfallibleResult ResultTypeProxy;

   static ResultType Result(ResultTypeProxy result) {

   }

   static bool Successful(ResultTypeProxy) {

     return true;

   }

   static ResultTypeProxy SuccessResult() {

     return ResultTypeProxy();

   }

   static ResultTypeProxy FailureResult() {

     NS_RUNTIMEABORT("Infallible nsTArray should never fail");

     return ResultTypeProxy();

   }

   static ResultType ConvertBoolToResultType(bool aValue) {

     if (!aValue) {

       NS_RUNTIMEABORT("infallible nsTArray should never convert false to ResultType");

     }

   }

 };

 #if defined(MOZALLOC_HAVE_XMALLOC)

 #include "mozilla/mozalloc_abort.h"

 struct nsTArrayFallibleAllocator : nsTArrayFallibleAllocatorBase

 {

   static void* Malloc(size_t size) {

     return moz_malloc(size);

   }

   static void* Realloc(void* ptr, size_t size) {

     return moz_realloc(ptr, size);

   }

   static void Free(void* ptr) {

     moz_free(ptr);

   }

   static void SizeTooBig(size_t) {

   }

 };

 struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase

 {

   static void* Malloc(size_t size) {

     return moz_xmalloc(size);

   }

   static void* Realloc(void* ptr, size_t size) {

     return moz_xrealloc(ptr, size);

   }

   static void Free(void* ptr) {

     moz_free(ptr);

   }

   static void SizeTooBig(size_t size) {

     NS_ABORT_OOM(size);

   }

 };

 #else

 #include <stdlib.h>

 struct nsTArrayFallibleAllocator : nsTArrayFallibleAllocatorBase

 {

   static void* Malloc(size_t size) {

     return malloc(size);

   }

   static void* Realloc(void* ptr, size_t size) {

     return realloc(ptr, size);

   }

   static void Free(void* ptr) {

     free(ptr);

   }

   static void SizeTooBig(size_t) {

   }

 };

 struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase

 {

   static void* Malloc(size_t size) {

     void* ptr = malloc(size);

     if (MOZ_UNLIKELY(!ptr)) {

       NS_ABORT_OOM(size);

     }

     return ptr;

   }

   static void* Realloc(void* ptr, size_t size) {

     void* newptr = realloc(ptr, size);

     if (MOZ_UNLIKELY(!ptr && size)) {

       NS_ABORT_OOM(size);

     }

     return newptr;

   }

   static void Free(void* ptr) {

     free(ptr);

   }

   static void SizeTooBig(size_t size) {

     NS_ABORT_OOM(size);

   }

 };

 #endif

 // nsTArray_base stores elements into the space allocated beyond

 // sizeof(*this).  This is done to minimize the size of the nsTArray

 // object when it is empty.

 struct NS_COM_GLUE nsTArrayHeader

 {

   static nsTArrayHeader sEmptyHdr;

   uint32_t mLength;

   uint32_t mCapacity : 31;

   uint32_t mIsAutoArray : 1;

 };

 // This class provides a SafeElementAt method to nsTArray<T*> which does

 // not take a second default value parameter.

 template <class E, class Derived>

 struct nsTArray_SafeElementAtHelper

 {

   typedef E*       elem_type;

   typedef uint32_t index_type;

   // No implementation is provided for these two methods, and that is on

   // purpose, since we don't support these functions on non-pointer type

   // instantiations.

   elem_type& SafeElementAt(index_type i);

   const elem_type& SafeElementAt(index_type i) const;

 };

 template <class E, class Derived>

 struct nsTArray_SafeElementAtHelper<E*, Derived>

 {

   typedef E*       elem_type;

   typedef uint32_t index_type;

   elem_type SafeElementAt(index_type i) {

     return static_cast<Derived*> (this)->SafeElementAt(i, nullptr);

   }

   const elem_type SafeElementAt(index_type i) const {

     return static_cast<const Derived*> (this)->SafeElementAt(i, nullptr);

   }

 };

 // E is the base type that the smart pointer is templated over; the

 // smart pointer can act as E*.

 template <class E, class Derived>

 struct nsTArray_SafeElementAtSmartPtrHelper

 {

   typedef E*       elem_type;

   typedef uint32_t index_type;

   elem_type SafeElementAt(index_type i) {

     return static_cast<Derived*> (this)->SafeElementAt(i, nullptr);

   }

   const elem_type SafeElementAt(index_type i) const {

     return static_cast<const Derived*> (this)->SafeElementAt(i, nullptr);

   }

 };

 template <class T> class nsCOMPtr;

 template <class E, class Derived>

 struct nsTArray_SafeElementAtHelper<nsCOMPtr<E>, Derived> :

   public nsTArray_SafeElementAtSmartPtrHelper<E, Derived>

 {

 };

 template <class T> class nsRefPtr;

 template <class E, class Derived>

 struct nsTArray_SafeElementAtHelper<nsRefPtr<E>, Derived> :

   public nsTArray_SafeElementAtSmartPtrHelper<E, Derived>

 {

 };

 //

 // This class serves as a base class for nsTArray.  It shouldn't be used

 // directly.  It holds common implementation code that does not depend on the

 // element type of the nsTArray.

 //

 template<class Alloc, class Copy>

 class nsTArray_base

 {

   // Allow swapping elements with |nsTArray_base|s created using a

   // different allocator.  This is kosher because all allocators use

   // the same free().

   template<class Allocator, class Copier>

   friend class nsTArray_base;

 protected:

   typedef nsTArrayHeader Header;

 public:

   typedef uint32_t size_type;

   typedef uint32_t index_type;

   // @return The number of elements in the array.

   size_type Length() const {

     return mHdr->mLength;

   }

   // @return True if the array is empty or false otherwise.

   bool IsEmpty() const {

     return Length() == 0;

   }

   // @return The number of elements that can fit in the array without forcing

   // the array to be re-allocated.  The length of an array is always less

   // than or equal to its capacity.

   size_type Capacity() const {

     return mHdr->mCapacity;

   }

 #ifdef DEBUG

   void* DebugGetHeader() const {

     return mHdr;

   }

 #endif

 protected:

   nsTArray_base();

   ~nsTArray_base();

   // Resize the storage if necessary to achieve the requested capacity.

   // @param capacity     The requested number of array elements.

   // @param elemSize     The size of an array element.

   // @return False if insufficient memory is available; true otherwise.

   typename Alloc::ResultTypeProxy EnsureCapacity(size_type capacity, size_type elemSize);

   // Resize the storage to the minimum required amount.

   // @param elemSize     The size of an array element.

   // @param elemAlign    The alignment in bytes of an array element.

   void ShrinkCapacity(size_type elemSize, size_t elemAlign);

   // This method may be called to resize a "gap" in the array by shifting

   // elements around.  It updates mLength appropriately.  If the resulting

   // array has zero elements, then the array's memory is free'd.

   // @param start        The starting index of the gap.

   // @param oldLen       The current length of the gap.

   // @param newLen       The desired length of the gap.

   // @param elemSize     The size of an array element.

   // @param elemAlign    The alignment in bytes of an array element.

   void ShiftData(index_type start, size_type oldLen, size_type newLen,

                  size_type elemSize, size_t elemAlign);

   // This method increments the length member of the array's header.

   // Note that mHdr may actually be sEmptyHdr in the case where a

   // zero-length array is inserted into our array. But then n should

   // always be 0.

   void IncrementLength(uint32_t n) {

     if (mHdr == EmptyHdr()) {

       if (MOZ_UNLIKELY(n != 0)) {

         // Writing a non-zero length to the empty header would be extremely bad.

         MOZ_CRASH();

       }

     } else {

       mHdr->mLength += n;

     }

   }

   // This method inserts blank slots into the array.

   // @param index the place to insert the new elements. This must be no

   //              greater than the current length of the array.

   // @param count the number of slots to insert

   // @param elementSize the size of an array element.

   // @param elemAlign the alignment in bytes of an array element.

   bool InsertSlotsAt(index_type index, size_type count,

                        size_type elementSize, size_t elemAlign);

 protected:

   template<class Allocator>

   typename Alloc::ResultTypeProxy

   SwapArrayElements(nsTArray_base<Allocator, Copy>& other,

                     size_type elemSize,

                     size_t elemAlign);

   // This is an RAII class used in SwapArrayElements.

   class IsAutoArrayRestorer {

     public:

       IsAutoArrayRestorer(nsTArray_base<Alloc, Copy> &array, size_t elemAlign);

       ~IsAutoArrayRestorer();

     private:

       nsTArray_base<Alloc, Copy> &mArray;

       size_t mElemAlign;

       bool mIsAuto;

   };

   // Helper function for SwapArrayElements. Ensures that if the array

   // is an nsAutoTArray that it doesn't use the built-in buffer.

   bool EnsureNotUsingAutoArrayBuffer(size_type elemSize);

   // Returns true if this nsTArray is an nsAutoTArray with a built-in buffer.

   bool IsAutoArray() const {

     return mHdr->mIsAutoArray;

   }

   // Returns a Header for the built-in buffer of this nsAutoTArray.

   Header* GetAutoArrayBuffer(size_t elemAlign) {

     MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");

     return GetAutoArrayBufferUnsafe(elemAlign);

   }

   const Header* GetAutoArrayBuffer(size_t elemAlign) const {

     MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");

     return GetAutoArrayBufferUnsafe(elemAlign);

   }

   // Returns a Header for the built-in buffer of this nsAutoTArray, but doesn't

   // assert that we are an nsAutoTArray.

   Header* GetAutoArrayBufferUnsafe(size_t elemAlign) {

     return const_cast<Header*>(static_cast<const nsTArray_base<Alloc, Copy>*>(this)->

                                GetAutoArrayBufferUnsafe(elemAlign));

   }

   const Header* GetAutoArrayBufferUnsafe(size_t elemAlign) const;

   // Returns true if this is an nsAutoTArray and it currently uses the

   // built-in buffer to store its elements.

   bool UsesAutoArrayBuffer() const;

   // The array's elements (prefixed with a Header).  This pointer is never

   // null.  If the array is empty, then this will point to sEmptyHdr.

   Header *mHdr;

   Header* Hdr() const {

     return mHdr;

   }

   Header** PtrToHdr() {

     return &mHdr;

   }

   static Header* EmptyHdr() {

     return &Header::sEmptyHdr;

   }

 };

 //

 // This class defines convenience functions for element specific operations.

 // Specialize this template if necessary.

 //

 template<class E>

 class nsTArrayElementTraits

 {

 public:

   // Invoke the default constructor in place.

   static inline void Construct(E *e) {

     // Do NOT call "E()"! That triggers C++ "default initialization"

     // which zeroes out POD ("plain old data") types such as regular

     // ints.  We don't want that because it can be a performance issue

     // and people don't expect it; nsTArray should work like a regular

     // C/C++ array in this respect.

     new (static_cast<void *>(e)) E;

   }

   // Invoke the copy-constructor in place.

   template<class A>

   static inline void Construct(E *e, const A &arg) {

     typedef typename mozilla::RemoveCV<E>::Type E_NoCV;

     typedef typename mozilla::RemoveCV<A>::Type A_NoCV;

     static_assert(!mozilla::IsSame<E_NoCV*, A_NoCV>::value,

                   "For safety, we disallow constructing nsTArray<E> elements "

                   "from E* pointers. See bug 960591.");

     new (static_cast<void *>(e)) E(arg);

   }

   // Invoke the destructor in place.

   static inline void Destruct(E *e) {

     e->~E();

   }

 };

 // The default comparator used by nsTArray

 template<class A, class B>

 class nsDefaultComparator

 {

 public:

   bool Equals(const A& a, const B& b) const {

     return a == b;

   }

   bool LessThan(const A& a, const B& b) const {

     return a < b;

   }

 };

 template <class E> class InfallibleTArray;

 template <class E> class FallibleTArray;

 template<bool IsPod, bool IsSameType>

 struct AssignRangeAlgorithm {

   template<class Item, class ElemType, class IndexType, class SizeType>

   static void implementation(ElemType* elements, IndexType start,

                              SizeType count, const Item *values) {

     ElemType *iter = elements + start, *end = iter + count;

     for (; iter != end; ++iter, ++values)

       nsTArrayElementTraits<ElemType>::Construct(iter, *values);

   }

 };

 template<>

 struct AssignRangeAlgorithm<true, true> {

   template<class Item, class ElemType, class IndexType, class SizeType>

   static void implementation(ElemType* elements, IndexType start,

                              SizeType count, const Item *values) {

     memcpy(elements + start, values, count * sizeof(ElemType));

   }

 };

 //

 // Normally elements are copied with memcpy and memmove, but for some element

 // types that is problematic.  The nsTArray_CopyChooser template class can be

 // specialized to ensure that copying calls constructors and destructors

 // instead, as is done below for JS::Heap<E> elements.

 //

 //

 // A class that defines how to copy elements using memcpy/memmove.

 //

 struct nsTArray_CopyWithMemutils

 {

   const static bool allowRealloc = true;

   static void CopyElements(void* dest, const void* src, size_t count, size_t elemSize) {

     memcpy(dest, src, count * elemSize);

   }

   static void CopyHeaderAndElements(void* dest, const void* src, size_t count, size_t elemSize) {

     memcpy(dest, src, sizeof(nsTArrayHeader) + count * elemSize);

   }

   static void MoveElements(void* dest, const void* src, size_t count, size_t elemSize) {

     memmove(dest, src, count * elemSize);

   }

 };

 //

 // A template class that defines how to copy elements calling their constructors

 // and destructors appropriately.

 //

 template <class ElemType>

 struct nsTArray_CopyWithConstructors

 {

   typedef nsTArrayElementTraits<ElemType> traits;

   const static bool allowRealloc = false;

   static void CopyElements(void* dest, void* src, size_t count, size_t elemSize) {

     ElemType* destElem = static_cast<ElemType*>(dest);

     ElemType* srcElem = static_cast<ElemType*>(src);

     ElemType* destElemEnd = destElem + count;

 #ifdef DEBUG

     ElemType* srcElemEnd = srcElem + count;

     MOZ_ASSERT(srcElemEnd <= destElem || srcElemEnd > destElemEnd);

 #endif

     while (destElem != destElemEnd) {

       traits::Construct(destElem, *srcElem);

       traits::Destruct(srcElem);

       ++destElem;

       ++srcElem;

     }

   }

   static void CopyHeaderAndElements(void* dest, void* src, size_t count, size_t elemSize) {

     nsTArrayHeader* destHeader = static_cast<nsTArrayHeader*>(dest);

     nsTArrayHeader* srcHeader = static_cast<nsTArrayHeader*>(src);

     *destHeader = *srcHeader;

     CopyElements(static_cast<uint8_t*>(dest) + sizeof(nsTArrayHeader),

                  static_cast<uint8_t*>(src) + sizeof(nsTArrayHeader),

                  count, elemSize);

   }

   static void MoveElements(void* dest, void* src, size_t count, size_t elemSize) {

     ElemType* destElem = static_cast<ElemType*>(dest);

     ElemType* srcElem = static_cast<ElemType*>(src);

     ElemType* destElemEnd = destElem + count;

     ElemType* srcElemEnd = srcElem + count;

     if (destElem == srcElem) {

       return;  // In practice, we don't do this.

     } else if (srcElemEnd > destElem && srcElemEnd < destElemEnd) {

       while (destElemEnd != destElem) {

         --destElemEnd;

         --srcElemEnd;

         traits::Construct(destElemEnd, *srcElemEnd);

         traits::Destruct(srcElem);

       }

     } else {

       CopyElements(dest, src, count, elemSize);

     }

   }

 };

 //

 // The default behaviour is to use memcpy/memmove for everything.

 //

 template <class E>

 struct nsTArray_CopyChooser {

   typedef nsTArray_CopyWithMemutils Type;

 };

 //

 // Some classes require constructors/destructors to be called, so they are

 // specialized here.

 //

 template <class E>

 struct nsTArray_CopyChooser<JS::Heap<E> > {

   typedef nsTArray_CopyWithConstructors<JS::Heap<E> > Type;

 };

 template<>

 struct nsTArray_CopyChooser<nsRegion> {

   typedef nsTArray_CopyWithConstructors<nsRegion> Type;

 };

 template<>

 struct nsTArray_CopyChooser<nsIntRegion> {

   typedef nsTArray_CopyWithConstructors<nsIntRegion> Type;

 };

 //

 // Base class for nsTArray_Impl that is templated on element type and derived

 // nsTArray_Impl class, to allow extra conversions to be added for specific

 // types.

 //

 template <class E, class Derived>

 struct nsTArray_TypedBase : public nsTArray_SafeElementAtHelper<E, Derived> {};

 //

 // Specialization of nsTArray_TypedBase for arrays containing JS::Heap<E>

 // elements.

 //

 // These conversions are safe because JS::Heap<E> and E share the same

 // representation, and since the result of the conversions are const references

 // we won't miss any barriers.

 //

 // The static_cast is necessary to obtain the correct address for the derived

 // class since we are a base class used in multiple inheritance.

 //

 template <class E, class Derived>

 struct nsTArray_TypedBase<JS::Heap<E>, Derived>

  : public nsTArray_SafeElementAtHelper<JS::Heap<E>, Derived>

 {

   operator const nsTArray<E>& () {

     static_assert(sizeof(E) == sizeof(JS::Heap<E>),

                   "JS::Heap<E> must be binary compatible with E.");

     Derived* self = static_cast<Derived*>(this);

     return *reinterpret_cast<nsTArray<E> *>(self);

   }

   operator const FallibleTArray<E>& () {

     Derived* self = static_cast<Derived*>(this);

     return *reinterpret_cast<FallibleTArray<E> *>(self);

   }

 };

 //

 // nsTArray_Impl contains most of the guts supporting nsTArray, FallibleTArray,

 // nsAutoTArray, and AutoFallibleTArray.

 //

 // The only situation in which you might need to use nsTArray_Impl in your code

 // is if you're writing code which mutates a TArray which may or may not be

 // infallible.

 //

 // Code which merely reads from a TArray which may or may not be infallible can

 // simply cast the TArray to |const nsTArray&|; both fallible and infallible

 // TArrays can be cast to |const nsTArray&|.

 //

 template<class E, class Alloc>

 class nsTArray_Impl : public nsTArray_base<Alloc, typename nsTArray_CopyChooser<E>::Type>,

                       public nsTArray_TypedBase<E, nsTArray_Impl<E, Alloc> >

 {

 public:

   typedef typename nsTArray_CopyChooser<E>::Type     copy_type;

   typedef nsTArray_base<Alloc, copy_type>            base_type;

   typedef typename base_type::size_type              size_type;

   typedef typename base_type::index_type             index_type;

   typedef E                                          elem_type;

   typedef nsTArray_Impl<E, Alloc>                    self_type;

   typedef nsTArrayElementTraits<E>                   elem_traits;

   typedef nsTArray_SafeElementAtHelper<E, self_type> safeelementat_helper_type;

   using safeelementat_helper_type::SafeElementAt;

   using base_type::EmptyHdr;

   // A special value that is used to indicate an invalid or unknown index

   // into the array.

   enum {

     NoIndex = index_type(-1)

   };

   using base_type::Length;

   //

   // Finalization method

   //

   ~nsTArray_Impl() { Clear(); }

   //

   // Initialization methods

   //

   nsTArray_Impl() {}

   // Initialize this array and pre-allocate some number of elements.

   explicit nsTArray_Impl(size_type capacity) {

     SetCapacity(capacity);

   }

   // The array's copy-constructor performs a 'deep' copy of the given array.

   // @param other  The array object to copy.

   //

   // It's very important that we declare this method as taking |const

   // self_type&| as opposed to taking |const nsTArray_Impl<E, OtherAlloc>| for

   // an arbitrary OtherAlloc.

   //

   // If we don't declare a constructor taking |const self_type&|, C++ generates

   // a copy-constructor for this class which merely copies the object's

   // members, which is obviously wrong.

   //

   // You can pass an nsTArray_Impl<E, OtherAlloc> to this method because

   // nsTArray_Impl<E, X> can be cast to const nsTArray_Impl<E, Y>&.  So the

   // effect on the API is the same as if we'd declared this method as taking

   // |const nsTArray_Impl<E, OtherAlloc>&|.

   explicit nsTArray_Impl(const self_type& other) {

     AppendElements(other);

   }

   // Allow converting to a const array with a different kind of allocator,

   // Since the allocator doesn't matter for const arrays

   template<typename Allocator>

   operator const nsTArray_Impl<E, Allocator>&() const {

     return *reinterpret_cast<const nsTArray_Impl<E, Allocator>*>(this);

   }

   // And we have to do this for our subclasses too

   operator const nsTArray<E>&() const {

     return *reinterpret_cast<const InfallibleTArray<E>*>(this);

   }

   operator const FallibleTArray<E>&() const {

     return *reinterpret_cast<const FallibleTArray<E>*>(this);

   }

   // The array's assignment operator performs a 'deep' copy of the given

   // array.  It is optimized to reuse existing storage if possible.

   // @param other  The array object to copy.

   self_type& operator=(const self_type& other) {

     ReplaceElementsAt(0, Length(), other.Elements(), other.Length());

     return *this;

   }

   // Return true if this array has the same length and the same

   // elements as |other|.

   template<typename Allocator>

   bool operator==(const nsTArray_Impl<E, Allocator>& other) const {

     size_type len = Length();

     if (len != other.Length())

       return false;

     // XXX std::equal would be as fast or faster here

     for (index_type i = 0; i < len; ++i)

       if (!(operator[](i) == other[i]))

         return false;

     return true;

   }

   // Return true if this array does not have the same length and the same

   // elements as |other|.

   bool operator!=(const self_type& other) const {

     return !operator==(other);

   }

   template<typename Allocator>

   self_type& operator=(const nsTArray_Impl<E, Allocator>& other) {

     ReplaceElementsAt(0, Length(), other.Elements(), other.Length());

     return *this;

   }

   // @return The amount of memory used by this nsTArray_Impl, excluding

   // sizeof(*this).

   size_t SizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {

     if (this->UsesAutoArrayBuffer() || Hdr() == EmptyHdr())

       return 0;

     return mallocSizeOf(this->Hdr());

   }

   // @return The amount of memory used by this nsTArray_Impl, including

   // sizeof(*this).

   size_t SizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {

     return mallocSizeOf(this) + SizeOfExcludingThis(mallocSizeOf);

   }

   //

   // Accessor methods

   //

   // This method provides direct access to the array elements.

   // @return A pointer to the first element of the array.  If the array is

   // empty, then this pointer must not be dereferenced.

   elem_type* Elements() {

     return reinterpret_cast<elem_type *>(Hdr() + 1);

   }

   // This method provides direct, readonly access to the array elements.

   // @return A pointer to the first element of the array.  If the array is

   // empty, then this pointer must not be dereferenced.

   const elem_type* Elements() const {

     return reinterpret_cast<const elem_type *>(Hdr() + 1);

   }

   // This method provides direct access to the i'th element of the array.

   // The given index must be within the array bounds.

   // @param i  The index of an element in the array.

   // @return   A reference to the i'th element of the array.

   elem_type& ElementAt(index_type i) {

     MOZ_ASSERT(i < Length(), "invalid array index");

     return Elements()[i];

   }

   // This method provides direct, readonly access to the i'th element of the

   // array.  The given index must be within the array bounds.

   // @param i  The index of an element in the array.

   // @return   A const reference to the i'th element of the array.

   const elem_type& ElementAt(index_type i) const {

     MOZ_ASSERT(i < Length(), "invalid array index");

     return Elements()[i];

   }

   // This method provides direct access to the i'th element of the array in

   // a bounds safe manner. If the requested index is out of bounds the

   // provided default value is returned.

   // @param i  The index of an element in the array.

   // @param def The value to return if the index is out of bounds.

   elem_type& SafeElementAt(index_type i, elem_type& def) {

     return i < Length() ? Elements()[i] : def;

   }

   // This method provides direct access to the i'th element of the array in

   // a bounds safe manner. If the requested index is out of bounds the

   // provided default value is returned.

   // @param i  The index of an element in the array.

   // @param def The value to return if the index is out of bounds.

   const elem_type& SafeElementAt(index_type i, const elem_type& def) const {

     return i < Length() ? Elements()[i] : def;

   }

   // Shorthand for ElementAt(i)

   elem_type& operator[](index_type i) {

     return ElementAt(i);

   }

   // Shorthand for ElementAt(i)

   const elem_type& operator[](index_type i) const {

     return ElementAt(i);

   }

   // Shorthand for ElementAt(length - 1)

   elem_type& LastElement() {

     return ElementAt(Length() - 1);

   }

   // Shorthand for ElementAt(length - 1)

   const elem_type& LastElement() const {

     return ElementAt(Length() - 1);

   }

   // Shorthand for SafeElementAt(length - 1, def)

   elem_type& SafeLastElement(elem_type& def) {

     return SafeElementAt(Length() - 1, def);

   }

   // Shorthand for SafeElementAt(length - 1, def)

   const elem_type& SafeLastElement(const elem_type& def) const {

     return SafeElementAt(Length() - 1, def);

   }

   //

   // Search methods

   //

   // This method searches for the first element in this array that is equal

   // to the given element.

   // @param item   The item to search for.

   // @param comp   The Comparator used to determine element equality.

   // @return       true if the element was found.

   template<class Item, class Comparator>

   bool Contains(const Item& item, const Comparator& comp) const {

     return IndexOf(item, 0, comp) != NoIndex;

   }

   // This method searches for the first element in this array that is equal

   // to the given element.  This method assumes that 'operator==' is defined

   // for elem_type.

   // @param item   The item to search for.

   // @return       true if the element was found.

   template<class Item>

   bool Contains(const Item& item) const {

     return IndexOf(item) != NoIndex;

   }

   // This method searches for the offset of the first element in this

   // array that is equal to the given element.

   // @param item   The item to search for.

   // @param start  The index to start from.

   // @param comp   The Comparator used to determine element equality.

   // @return       The index of the found element or NoIndex if not found.

   template<class Item, class Comparator>

   index_type IndexOf(const Item& item, index_type start,

                      const Comparator& comp) const {

     const elem_type* iter = Elements() + start, *end = Elements() + Length();

     for (; iter != end; ++iter) {

       if (comp.Equals(*iter, item))

         return index_type(iter - Elements());

     }

     return NoIndex;

   }

   // This method searches for the offset of the first element in this

   // array that is equal to the given element.  This method assumes

   // that 'operator==' is defined for elem_type.

   // @param item   The item to search for.

   // @param start  The index to start from.

   // @return       The index of the found element or NoIndex if not found.

   template<class Item>

   index_type IndexOf(const Item& item, index_type start = 0) const {

     return IndexOf(item, start, nsDefaultComparator<elem_type, Item>());

   }

   // This method searches for the offset of the last element in this

   // array that is equal to the given element.

   // @param item   The item to search for.

   // @param start  The index to start from.  If greater than or equal to the

   //               length of the array, then the entire array is searched.

   // @param comp   The Comparator used to determine element equality.

   // @return       The index of the found element or NoIndex if not found.

   template<class Item, class Comparator>

   index_type LastIndexOf(const Item& item, index_type start,

                          const Comparator& comp) const {

     size_type endOffset = start >= Length() ? Length() : start + 1;

     const elem_type* end = Elements() - 1, *iter = end + endOffset;

     for (; iter != end; --iter) {

       if (comp.Equals(*iter, item))

         return index_type(iter - Elements());

     }

     return NoIndex;

   }

   // This method searches for the offset of the last element in this

   // array that is equal to the given element.  This method assumes

   // that 'operator==' is defined for elem_type.

   // @param item   The item to search for.

   // @param start  The index to start from.  If greater than or equal to the

   //               length of the array, then the entire array is searched.

   // @return       The index of the found element or NoIndex if not found.

   template<class Item>

   index_type LastIndexOf(const Item& item,

                          index_type start = NoIndex) const {

     return LastIndexOf(item, start, nsDefaultComparator<elem_type, Item>());

   }

   // This method searches for the offset for the element in this array

   // that is equal to the given element. The array is assumed to be sorted.

   // @param item   The item to search for.

   // @param comp   The Comparator used.

   // @return       The index of the found element or NoIndex if not found.

   template<class Item, class Comparator>

   index_type BinaryIndexOf(const Item& item, const Comparator& comp) const {

     index_type low = 0, high = Length();

     while (high > low) {

       index_type mid = (high + low) >> 1;

       if (comp.Equals(ElementAt(mid), item))

         return mid;

       if (comp.LessThan(ElementAt(mid), item))

         low = mid + 1;

       else

         high = mid;

     }

     return NoIndex;

   }

   // This method searches for the offset for the element in this array

   // that is equal to the given element. The array is assumed to be sorted.

   // This method assumes that 'operator==' and 'operator<' are defined.

   // @param item   The item to search for.

   // @return       The index of the found element or NoIndex if not found.

   template<class Item>

   index_type BinaryIndexOf(const Item& item) const {

     return BinaryIndexOf(item, nsDefaultComparator<elem_type, Item>());

   }

   //

   // Mutation methods

   //

   // This method call the destructor on each element of the array, empties it,

   // but does not shrink the array's capacity.

   // See also SetLengthAndRetainStorage.

   // Make sure to call Compact() if needed to avoid keeping a huge array

   // around.

   void ClearAndRetainStorage() {

     if (base_type::mHdr == EmptyHdr()) {

       return;

     }

     DestructRange(0, Length());

     base_type::mHdr->mLength = 0;

   }

   // This method modifies the length of the array, but unlike SetLength

   // it doesn't deallocate/reallocate the current internal storage.

   // The new length MUST be shorter than or equal to the current capacity.

   // If the new length is larger than the existing length of the array,

   // then new elements will be constructed using elem_type's default

   // constructor.  If shorter, elements will be destructed and removed.

   // See also ClearAndRetainStorage.

   // @param newLen  The desired length of this array.

   void SetLengthAndRetainStorage(size_type newLen) {

     MOZ_ASSERT(newLen <= base_type::Capacity());

     size_type oldLen = Length();

     if (newLen > oldLen) {

       InsertElementsAt(oldLen, newLen - oldLen);

       return;

     }

     if (newLen < oldLen) {

       DestructRange(newLen, oldLen - newLen);

       base_type::mHdr->mLength = newLen;

     }

   }

   // This method replaces a range of elements in this array.

   // @param start     The starting index of the elements to replace.

   // @param count     The number of elements to replace.  This may be zero to

   //                  insert elements without removing any existing elements.

   // @param array     The values to copy into this array.  Must be non-null,

   //                  and these elements must not already exist in the array

   //                  being modified.

   // @param arrayLen  The number of values to copy into this array.

   // @return          A pointer to the new elements in the array, or null if

   //                  the operation failed due to insufficient memory.

   template<class Item>

   elem_type *ReplaceElementsAt(index_type start, size_type count,

                                const Item* array, size_type arrayLen) {

     // Adjust memory allocation up-front to catch errors.

     if (!Alloc::Successful(this->EnsureCapacity(Length() + arrayLen - count, sizeof(elem_type))))

       return nullptr;

     DestructRange(start, count);

     this->ShiftData(start, count, arrayLen, sizeof(elem_type), MOZ_ALIGNOF(elem_type));

     AssignRange(start, arrayLen, array);

     return Elements() + start;

   }

   // A variation on the ReplaceElementsAt method defined above.

   template<class Item>

   elem_type *ReplaceElementsAt(index_type start, size_type count,

                                const nsTArray<Item>& array) {

     return ReplaceElementsAt(start, count, array.Elements(), array.Length());

   }

   // A variation on the ReplaceElementsAt method defined above.

   template<class Item>

   elem_type *ReplaceElementsAt(index_type start, size_type count,

                                const Item& item) {

     return ReplaceElementsAt(start, count, &item, 1);

   }

   // A variation on the ReplaceElementsAt method defined above.

   template<class Item>

   elem_type *ReplaceElementAt(index_type index, const Item& item) {

     return ReplaceElementsAt(index, 1, &item, 1);

   }

   // A variation on the ReplaceElementsAt method defined above.

   template<class Item>

   elem_type *InsertElementsAt(index_type index, const Item* array,

                               size_type arrayLen) {

     return ReplaceElementsAt(index, 0, array, arrayLen);

   }

   // A variation on the ReplaceElementsAt method defined above.

   template<class Item, class Allocator>

   elem_type *InsertElementsAt(index_type index, const nsTArray_Impl<Item, Allocator>& array) {

     return ReplaceElementsAt(index, 0, array.Elements(), array.Length());

   }

   // A variation on the ReplaceElementsAt method defined above.

   template<class Item>

   elem_type *InsertElementAt(index_type index, const Item& item) {

     return ReplaceElementsAt(index, 0, &item, 1);

   }

   // Insert a new element without copy-constructing. This is useful to avoid

   // temporaries.

   // @return A pointer to the newly inserted element, or null on OOM.

   elem_type* InsertElementAt(index_type index) {

     if (!Alloc::Successful(this->EnsureCapacity(Length() + 1, sizeof(elem_type))))

       return nullptr;

     this->ShiftData(index, 0, 1, sizeof(elem_type), MOZ_ALIGNOF(elem_type));

     elem_type *elem = Elements() + index;

     elem_traits::Construct(elem);

     return elem;

   }

   // This method searches for the smallest index of an element that is strictly

   // greater than |item|.  If |item| is inserted at this index, the array will

   // remain sorted and |item| would come after all elements that are equal to

   // it.  If |item| is greater than or equal to all elements in the array, the

   // array length is returned.

   //

   // Note that consumers who want to know whether there are existing items equal

   // to |item| in the array can just check that the return value here is > 0 and

   // indexing into the previous slot gives something equal to |item|.

   //

   //

   // @param item   The item to search for.

   // @param comp   The Comparator used.

   // @return        The index of greatest element <= to |item|

   // @precondition The array is sorted

   template<class Item, class Comparator>

   index_type

   IndexOfFirstElementGt(const Item& item,

                         const Comparator& comp) const {

     // invariant: low <= [idx] <= high

     index_type low = 0, high = Length();

     while (high > low) {

       index_type mid = (high + low) >> 1;

       // Comparators are not required to provide a LessThan(Item&, elem_type),

       // so we can't do comp.LessThan(item, ElementAt(mid)).

       if (comp.LessThan(ElementAt(mid), item) ||

           comp.Equals(ElementAt(mid), item)) {

         // item >= ElementAt(mid), so our desired index is at least mid+1.

         low = mid + 1;

       } else {

         // item < ElementAt(mid).  Our desired index is therefore at most mid.

         high = mid;

       }

     }

     MOZ_ASSERT(high == low);

     return low;

   }

   // A variation on the IndexOfFirstElementGt method defined above.

   template<class Item>

   index_type

   IndexOfFirstElementGt(const Item& item) const {

     return IndexOfFirstElementGt(item, nsDefaultComparator<elem_type, Item>());

   }

   // Inserts |item| at such an index to guarantee that if the array

   // was previously sorted, it will remain sorted after this

   // insertion.

   template<class Item, class Comparator>

   elem_type *InsertElementSorted(const Item& item, const Comparator& comp) {

     index_type index = IndexOfFirstElementGt(item, comp);

     return InsertElementAt(index, item);

   }

   // A variation on the InsertElementSorted method defined above.

   template<class Item>

   elem_type *InsertElementSorted(const Item& item) {

     return InsertElementSorted(item, nsDefaultComparator<elem_type, Item>());

   }

   // This method appends elements to the end of this array.

   // @param array     The elements to append to this array.

   // @param arrayLen  The number of elements to append to this array.

   // @return          A pointer to the new elements in the array, or null if

   //                  the operation failed due to insufficient memory.

   template<class Item>

   elem_type *AppendElements(const Item* array, size_type arrayLen) {

     if (!Alloc::Successful(this->EnsureCapacity(Length() + arrayLen, sizeof(elem_type))))

       return nullptr;

     index_type len = Length();

     AssignRange(len, arrayLen, array);

     this->IncrementLength(arrayLen);

     return Elements() + len;

   }

   // A variation on the AppendElements method defined above.

   template<class Item, class Allocator>

   elem_type *AppendElements(const nsTArray_Impl<Item, Allocator>& array) {

     return AppendElements(array.Elements(), array.Length());

   }

   // A variation on the AppendElements method defined above.

   template<class Item>

   elem_type *AppendElement(const Item& item) {

     return AppendElements(&item, 1);

   }

   // Append new elements without copy-constructing. This is useful to avoid

   // temporaries.

   // @return A pointer to the newly appended elements, or null on OOM.

   elem_type *AppendElements(size_type count) {

     if (!Alloc::Successful(this->EnsureCapacity(Length() + count, sizeof(elem_type))))

       return nullptr;

     elem_type *elems = Elements() + Length();

     size_type i;

     for (i = 0; i < count; ++i) {

       elem_traits::Construct(elems + i);

     }

     this->IncrementLength(count);

     return elems;

   }

   // Append a new element without copy-constructing. This is useful to avoid

   // temporaries.

   // @return A pointer to the newly appended element, or null on OOM.

   elem_type *AppendElement() {

     return AppendElements(1);

   }

   // Move all elements from another array to the end of this array without

   // calling copy constructors or destructors.

   // @return A pointer to the newly appended elements, or null on OOM.

   template<class Item, class Allocator>

   elem_type *MoveElementsFrom(nsTArray_Impl<Item, Allocator>& array) {

     MOZ_ASSERT(&array != this, "argument must be different array");

     index_type len = Length();

     index_type otherLen = array.Length();

     if (!Alloc::Successful(this->EnsureCapacity(len + otherLen, sizeof(elem_type))))

       return nullptr;

     copy_type::CopyElements(Elements() + len, array.Elements(), otherLen, sizeof(elem_type));

     this->IncrementLength(otherLen);

     array.ShiftData(0, otherLen, 0, sizeof(elem_type), MOZ_ALIGNOF(elem_type));

     return Elements() + len;

   }

   // This method removes a range of elements from this array.

   // @param start  The starting index of the elements to remove.

   // @param count  The number of elements to remove.

   void RemoveElementsAt(index_type start, size_type count) {

     MOZ_ASSERT(count == 0 || start < Length(), "Invalid start index");

     MOZ_ASSERT(start + count <= Length(), "Invalid length");

     // Check that the previous assert didn't overflow

     MOZ_ASSERT(start <= start + count, "Start index plus length overflows");

     DestructRange(start, count);

     this->ShiftData(start, count, 0, sizeof(elem_type), MOZ_ALIGNOF(elem_type));

   }

   // A variation on the RemoveElementsAt method defined above.

   void RemoveElementAt(index_type index) {

     RemoveElementsAt(index, 1);

   }

   // A variation on the RemoveElementsAt method defined above.

   void Clear() {

     RemoveElementsAt(0, Length());

   }

   // This helper function combines IndexOf with RemoveElementAt to "search

   // and destroy" the first element that is equal to the given element.

   // @param item  The item to search for.

   // @param comp  The Comparator used to determine element equality.

   // @return true if the element was found

   template<class Item, class Comparator>

   bool RemoveElement(const Item& item, const Comparator& comp) {

     index_type i = IndexOf(item, 0, comp);

     if (i == NoIndex)

       return false;

     RemoveElementAt(i);

     return true;

   }

   // A variation on the RemoveElement method defined above that assumes

   // that 'operator==' is defined for elem_type.

   template<class Item>

   bool RemoveElement(const Item& item) {

     return RemoveElement(item, nsDefaultComparator<elem_type, Item>());

   }

   // This helper function combines IndexOfFirstElementGt with

   // RemoveElementAt to "search and destroy" the last element that

   // is equal to the given element.

   // @param item  The item to search for.

   // @param comp  The Comparator used to determine element equality.

   // @return true if the element was found

   template<class Item, class Comparator>

   bool RemoveElementSorted(const Item& item, const Comparator& comp) {

     index_type index = IndexOfFirstElementGt(item, comp);

     if (index > 0 && comp.Equals(ElementAt(index - 1), item)) {

       RemoveElementAt(index - 1);

       return true;

     }

     return false;

   }

   // A variation on the RemoveElementSorted method defined above.

   template<class Item>

   bool RemoveElementSorted(const Item& item) {

     return RemoveElementSorted(item, nsDefaultComparator<elem_type, Item>());

   }

   // This method causes the elements contained in this array and the given

   // array to be swapped.

   template<class Allocator>

   typename Alloc::ResultType

   SwapElements(nsTArray_Impl<E, Allocator>& other) {

     return Alloc::Result(this->SwapArrayElements(other, sizeof(elem_type),

                                                  MOZ_ALIGNOF(elem_type)));

   }

   //

   // Allocation

   //

   // This method may increase the capacity of this array object by the

   // specified amount.  This method may be called in advance of several

   // AppendElement operations to minimize heap re-allocations.  This method

   // will not reduce the number of elements in this array.

   // @param capacity  The desired capacity of this array.

   // @return True if the operation succeeded; false if we ran out of memory

   typename Alloc::ResultType SetCapacity(size_type capacity) {

     return Alloc::Result(this->EnsureCapacity(capacity, sizeof(elem_type)));

   }

   // This method modifies the length of the array.  If the new length is

   // larger than the existing length of the array, then new elements will be

   // constructed using elem_type's default constructor.  Otherwise, this call

   // removes elements from the array (see also RemoveElementsAt).

   // @param newLen  The desired length of this array.

   // @return        True if the operation succeeded; false otherwise.

   // See also TruncateLength if the new length is guaranteed to be

   // smaller than the old.

   typename Alloc::ResultType SetLength(size_type newLen) {

     size_type oldLen = Length();

     if (newLen > oldLen) {

       return Alloc::ConvertBoolToResultType(InsertElementsAt(oldLen, newLen - oldLen) != nullptr);

     }

     TruncateLength(newLen);

     return Alloc::ConvertBoolToResultType(true);

   }

   // This method modifies the length of the array, but may only be

   // called when the new length is shorter than the old.  It can

   // therefore be called when elem_type has no default constructor,

   // unlike SetLength.  It removes elements from the array (see also

   // RemoveElementsAt).

   // @param newLen  The desired length of this array.

   void TruncateLength(size_type newLen) {

     size_type oldLen = Length();

     NS_ABORT_IF_FALSE(newLen <= oldLen,

                       "caller should use SetLength instead");

     RemoveElementsAt(newLen, oldLen - newLen);

   }

   // This method ensures that the array has length at least the given

   // length.  If the current length is shorter than the given length,

   // then new elements will be constructed using elem_type's default

   // constructor.

   // @param minLen  The desired minimum length of this array.

   // @return        True if the operation succeeded; false otherwise.

 typename Alloc::ResultType EnsureLengthAtLeast(size_type minLen) {

     size_type oldLen = Length();

     if (minLen > oldLen) {

       return Alloc::ConvertBoolToResultType(!!InsertElementsAt(oldLen, minLen - oldLen));

     }

     return Alloc::ConvertBoolToResultType(true);

   }

   // This method inserts elements into the array, constructing

   // them using elem_type's default constructor.

   // @param index the place to insert the new elements. This must be no

   //              greater than the current length of the array.

   // @param count the number of elements to insert

   elem_type *InsertElementsAt(index_type index, size_type count) {

     if (!base_type::InsertSlotsAt(index, count, sizeof(elem_type), MOZ_ALIGNOF(elem_type))) {

       return nullptr;

     }

     // Initialize the extra array elements

     elem_type *iter = Elements() + index, *end = iter + count;

     for (; iter != end; ++iter) {

       elem_traits::Construct(iter);

     }

     return Elements() + index;

   }

   // This method inserts elements into the array, constructing them

   // elem_type's copy constructor (or whatever one-arg constructor

   // happens to match the Item type).

   // @param index the place to insert the new elements. This must be no

   //              greater than the current length of the array.

   // @param count the number of elements to insert.

   // @param item the value to use when constructing the new elements.

   template<class Item>

   elem_type *InsertElementsAt(index_type index, size_type count,

                               const Item& item) {

     if (!base_type::InsertSlotsAt(index, count, sizeof(elem_type), MOZ_ALIGNOF(elem_type))) {

       return nullptr;

     }

     // Initialize the extra array elements

     elem_type *iter = Elements() + index, *end = iter + count;

     for (; iter != end; ++iter) {

       elem_traits::Construct(iter, item);

     }

     return Elements() + index;

   }

   // This method may be called to minimize the memory used by this array.

   void Compact() {

     ShrinkCapacity(sizeof(elem_type), MOZ_ALIGNOF(elem_type));

   }

   //

   // Sorting

   //

   // This function is meant to be used with the NS_QuickSort function.  It

   // maps the callback API expected by NS_QuickSort to the Comparator API

   // used by nsTArray_Impl.  See nsTArray_Impl::Sort.

   template<class Comparator>

   static int Compare(const void* e1, const void* e2, void *data) {

     const Comparator* c = reinterpret_cast<const Comparator*>(data);

     const elem_type* a = static_cast<const elem_type*>(e1);

     const elem_type* b = static_cast<const elem_type*>(e2);

     return c->LessThan(*a, *b) ? -1 : (c->Equals(*a, *b) ? 0 : 1);

   }

   // This method sorts the elements of the array.  It uses the LessThan

   // method defined on the given Comparator object to collate elements.

   // @param comp The Comparator used to collate elements.

   template<class Comparator>

   void Sort(const Comparator& comp) {

     NS_QuickSort(Elements(), Length(), sizeof(elem_type),

                  Compare<Comparator>, const_cast<Comparator*>(&comp));

   }

   // A variation on the Sort method defined above that assumes that

   // 'operator<' is defined for elem_type.

   void Sort() {

     Sort(nsDefaultComparator<elem_type, elem_type>());

   }

   //

   // Binary Heap

   //

   // Sorts the array into a binary heap.

   // @param comp The Comparator used to create the heap

   template<class Comparator>

   void MakeHeap(const Comparator& comp) {

     if (!Length()) {

       return;

     }

     index_type index = (Length() - 1) / 2;

     do {

       SiftDown(index, comp);

     } while (index--);

   }

   // A variation on the MakeHeap method defined above.

   void MakeHeap() {

     MakeHeap(nsDefaultComparator<elem_type, elem_type>());

   }

   // Adds an element to the heap

   // @param item The item to add

   // @param comp The Comparator used to sift-up the item

   template<class Item, class Comparator>

   elem_type *PushHeap(const Item& item, const Comparator& comp) {

     if (!base_type::InsertSlotsAt(Length(), 1, sizeof(elem_type), MOZ_ALIGNOF(elem_type))) {

       return nullptr;

     }

     // Sift up the new node

     elem_type *elem = Elements();

     index_type index = Length() - 1;

     index_type parent_index = (index - 1) / 2;

     while (index && comp.LessThan(elem[parent_index], item)) {

       elem[index] = elem[parent_index];

       index = parent_index;

       parent_index = (index - 1) / 2;

     }

     elem[index] = item;

     return &elem[index];

   }

   // A variation on the PushHeap method defined above.

   template<class Item>

   elem_type *PushHeap(const Item& item) {

     return PushHeap(item, nsDefaultComparator<elem_type, Item>());

   }

   // Delete the root of the heap and restore the heap

   // @param comp The Comparator used to restore the heap

   template<class Comparator>

   void PopHeap(const Comparator& comp) {

     if (!Length()) {

       return;

     }

     index_type last_index = Length() - 1;

     elem_type *elem = Elements();

     elem[0] = elem[last_index];

     TruncateLength(last_index);

     if (Length()) {

       SiftDown(0, comp);

     }

   }

   // A variation on the PopHeap method defined above.

   void PopHeap() {

     PopHeap(nsDefaultComparator<elem_type, elem_type>());

   }

 protected:

   using base_type::Hdr;

   using base_type::ShrinkCapacity;

   // This method invokes elem_type's destructor on a range of elements.

   // @param start  The index of the first element to destroy.

   // @param count  The number of elements to destroy.

   void DestructRange(index_type start, size_type count) {

     elem_type *iter = Elements() + start, *end = iter + count;

     for (; iter != end; ++iter) {

       elem_traits::Destruct(iter);

     }

   }

   // This method invokes elem_type's copy-constructor on a range of elements.

   // @param start   The index of the first element to construct.

   // @param count   The number of elements to construct.

   // @param values  The array of elements to copy.

   template<class Item>

   void AssignRange(index_type start, size_type count,

                    const Item *values) {

     AssignRangeAlgorithm<mozilla::IsPod<Item>::value,

                          mozilla::IsSame<Item, elem_type>::value>

       ::implementation(Elements(), start, count, values);

   }

   // This method sifts an item down to its proper place in a binary heap

   // @param index The index of the node to start sifting down from

   // @param comp  The Comparator used to sift down

   template<class Comparator>

   void SiftDown(index_type index, const Comparator& comp) {

     elem_type *elem = Elements();

     elem_type item = elem[index];

     index_type end = Length() - 1;

     while ((index * 2) < end) {

       const index_type left = (index * 2) + 1;

       const index_type right = (index * 2) + 2;

       const index_type parent_index = index;

       if (comp.LessThan(item, elem[left])) {

         if (left < end &&

             comp.LessThan(elem[left], elem[right])) {

           index = right;

         } else {

           index = left;

         }

       } else if (left < end &&

                  comp.LessThan(item, elem[right])) {

         index = right;

       } else {

         break;

       }

       elem[parent_index] = elem[index];

     }

     elem[index] = item;

   }

 };

 template <typename E, typename Alloc>

 inline void

 ImplCycleCollectionUnlink(nsTArray_Impl<E, Alloc>& aField)

 {

   aField.Clear();

 }

 template <typename E, typename Alloc>

 inline void

 ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,

                             nsTArray_Impl<E, Alloc>& aField,

                             const char* aName,

                             uint32_t aFlags = 0)

 {

   aFlags |= CycleCollectionEdgeNameArrayFlag;

   uint32_t length = aField.Length();

   for (uint32_t i = 0; i < length; ++i) {

     ImplCycleCollectionTraverse(aCallback, aField[i], aName, aFlags);

   }

 }

 //

 // nsTArray is an infallible vector class.  See the comment at the top of this

 // file for more details.

 //

 template <class E>

 class nsTArray : public nsTArray_Impl<E, nsTArrayInfallibleAllocator>

 {

 public:

   typedef nsTArray_Impl<E, nsTArrayInfallibleAllocator> base_type;

   typedef nsTArray<E>                                   self_type;

   typedef typename base_type::size_type                 size_type;

   nsTArray() {}

   explicit nsTArray(size_type capacity) : base_type(capacity) {}

   explicit nsTArray(const nsTArray& other) : base_type(other) {}

   template<class Allocator>

   explicit nsTArray(const nsTArray_Impl<E, Allocator>& other) : base_type(other) {}

 };

 //

 // FallibleTArray is a fallible vector class.

 //

 template <class E>

 class FallibleTArray : public nsTArray_Impl<E, nsTArrayFallibleAllocator>

 {

 public:

   typedef nsTArray_Impl<E, nsTArrayFallibleAllocator>   base_type;

   typedef FallibleTArray<E>                             self_type;

   typedef typename base_type::size_type                 size_type;

   FallibleTArray() {}

   explicit FallibleTArray(size_type capacity) : base_type(capacity) {}

   explicit FallibleTArray(const FallibleTArray<E>& other) : base_type(other) {}

   template<class Allocator>

   explicit FallibleTArray(const nsTArray_Impl<E, Allocator>& other) : base_type(other) {}

 };

 //

 // nsAutoArrayBase is a base class for AutoFallibleTArray and nsAutoTArray.

 // You shouldn't use this class directly.

 //

 template <class TArrayBase, uint32_t N>

 class nsAutoArrayBase : public TArrayBase

 {

 public:

   typedef nsAutoArrayBase<TArrayBase, N> self_type;

   typedef TArrayBase base_type;

   typedef typename base_type::Header Header;

   typedef typename base_type::elem_type elem_type;

   template<typename Allocator>

   self_type& operator=(const nsTArray_Impl<elem_type, Allocator>& other) {

     base_type::operator=(other);

     return *this;

   }

 protected:

   nsAutoArrayBase() {

     Init();

   }

   // We need this constructor because nsAutoTArray and friends all have

   // implicit copy-constructors.  If we don't have this method, those

   // copy-constructors will call nsAutoArrayBase's implicit copy-constructor,

   // which won't call Init() and set up the auto buffer!

   nsAutoArrayBase(const self_type &aOther) {

     Init();

     this->AppendElements(aOther);

   }

 private:

   // nsTArray_base casts itself as an nsAutoArrayBase in order to get a pointer

   // to mAutoBuf.

   template<class Allocator, class Copier>

   friend class nsTArray_base;

   void Init() {

     static_assert(MOZ_ALIGNOF(elem_type) <= 8,

                   "can't handle alignments greater than 8, "

                   "see nsTArray_base::UsesAutoArrayBuffer()");

     // Temporary work around for VS2012 RC compiler crash

     Header** phdr = base_type::PtrToHdr();

     *phdr = reinterpret_cast<Header*>(&mAutoBuf);

     (*phdr)->mLength = 0;

     (*phdr)->mCapacity = N;

     (*phdr)->mIsAutoArray = 1;

     MOZ_ASSERT(base_type::GetAutoArrayBuffer(MOZ_ALIGNOF(elem_type)) ==

                reinterpret_cast<Header*>(&mAutoBuf),

                "GetAutoArrayBuffer needs to be fixed");

   }

   // Declare mAutoBuf aligned to the maximum of the header's alignment and

   // elem_type's alignment.  We need to use a union rather than

   // MOZ_ALIGNED_DECL because GCC is picky about what goes into

   // __attribute__((aligned(foo))).

   union {

     char mAutoBuf[sizeof(nsTArrayHeader) + N * sizeof(elem_type)];

     // Do the max operation inline to ensure that it is a compile-time constant.

     mozilla::AlignedElem<(MOZ_ALIGNOF(Header) > MOZ_ALIGNOF(elem_type))

                          ? MOZ_ALIGNOF(Header) : MOZ_ALIGNOF(elem_type)> mAlign;

   };

 };

 //

 // nsAutoTArray<E, N> is an infallible vector class with N elements of inline

 // storage.  If you try to store more than N elements inside an

 // nsAutoTArray<E, N>, we'll call malloc() and store them all on the heap.

 //

 // Note that you can cast an nsAutoTArray<E, N> to

 // |const AutoFallibleTArray<E, N>&|.

 //

 template<class E, uint32_t N>

 class nsAutoTArray : public nsAutoArrayBase<nsTArray<E>, N>

 {

   typedef nsAutoTArray<E, N> self_type;

   typedef nsAutoArrayBase<nsTArray<E>, N> Base;

 public:

   nsAutoTArray() {}

   template<typename Allocator>

   explicit nsAutoTArray(const nsTArray_Impl<E, Allocator>& other) {

     Base::AppendElements(other);

   }

   operator const AutoFallibleTArray<E, N>&() const {

     return *reinterpret_cast<const AutoFallibleTArray<E, N>*>(this);

   }

 };

 //

 // AutoFallibleTArray<E, N> is a fallible vector class with N elements of

 // inline storage.

 //

 template<class E, uint32_t N>

 class AutoFallibleTArray : public nsAutoArrayBase<FallibleTArray<E>, N>

 {

   typedef AutoFallibleTArray<E, N> self_type;

   typedef nsAutoArrayBase<FallibleTArray<E>, N> Base;

 public:

   AutoFallibleTArray() {}

   template<typename Allocator>

   explicit AutoFallibleTArray(const nsTArray_Impl<E, Allocator>& other) {

     Base::AppendElements(other);

   }

   operator const nsAutoTArray<E, N>&() const {

     return *reinterpret_cast<const nsAutoTArray<E, N>*>(this);

   }

 };

 // Assert that nsAutoTArray doesn't have any extra padding inside.

 //

 // It's important that the data stored in this auto array takes up a multiple of

 // 8 bytes; e.g. nsAutoTArray<uint32_t, 1> wouldn't work.  Since nsAutoTArray

 // contains a pointer, its size must be a multiple of alignof(void*).  (This is

 // because any type may be placed into an array, and there's no padding between

 // elements of an array.)  The compiler pads the end of the structure to

 // enforce this rule.

 //

 // If we used nsAutoTArray<uint32_t, 1> below, this assertion would fail on a

 // 64-bit system, where the compiler inserts 4 bytes of padding at the end of

 // the auto array to make its size a multiple of alignof(void*) == 8 bytes.

 static_assert(sizeof(nsAutoTArray<uint32_t, 2>) ==

               sizeof(void*) + sizeof(nsTArrayHeader) + sizeof(uint32_t) * 2,

               "nsAutoTArray shouldn't contain any extra padding, "

               "see the comment");

 // Definitions of nsTArray_Impl methods

 #include "nsTArray-inl.h"

 #endif  // nsTArray_h__