Bug 550611: Make nsTArray optionally infallible. sr=bsmedberg a=blocking
authorChris Jones <jones.chris.g@gmail.com>
Mon, 08 Nov 2010 20:48:59 -0600
changeset 57140 f915a22def59a09afd87941311fdbd69c27de8ff
parent 57139 1c7a0925aa46c5272296983ba54c2f0b418c06e6
child 57141 15765a60e203b99d2ecc39e0f1f7ee8bf1f02c93
push idunknown
push userunknown
push dateunknown
reviewersbsmedberg, blocking
bugs550611
milestone2.0b8pre
Bug 550611: Make nsTArray optionally infallible. sr=bsmedberg a=blocking
content/base/public/nsINode.h
content/base/src/nsAttrValue.h
content/base/src/nsDocument.cpp
docshell/shistory/public/nsISHistoryInternal.idl
ipc/ipdl/ipdl/lower.py
layout/base/FrameLayerBuilder.cpp
layout/generic/nsIAnonymousContentCreator.h
layout/style/nsCSSStyleSheet.h
memory/mozalloc/mozalloc.h
modules/libpref/public/nsIPrefService.idl
storage/src/mozStorageBindingParamsArray.h
toolkit/components/places/src/nsMaybeWeakPtr.cpp
toolkit/components/places/src/nsMaybeWeakPtr.h
xpcom/glue/Makefile.in
xpcom/glue/nsTArray-inl.h
xpcom/glue/nsTArray.cpp
xpcom/glue/nsTArray.h
xpcom/glue/nsTPtrArray.h
--- a/content/base/public/nsINode.h
+++ b/content/base/public/nsINode.h
@@ -733,17 +733,17 @@ public:
    * observer that is already observing the node must not be added without
    * being removed first.
    */
   void AddMutationObserver(nsIMutationObserver* aMutationObserver)
   {
     nsSlots* s = GetSlots();
     if (s) {
       NS_ASSERTION(s->mMutationObservers.IndexOf(aMutationObserver) ==
-                   nsTArray_base::NoIndex,
+                   nsTArray<int>::NoIndex,
                    "Observer already in the list");
       s->mMutationObservers.AppendElement(aMutationObserver);
     }
   }
 
   /**
    * Same as above, but only adds the observer if its not observing
    * the node already.
--- a/content/base/src/nsAttrValue.h
+++ b/content/base/src/nsAttrValue.h
@@ -53,18 +53,19 @@
 #include "nsCOMPtr.h"
 
 typedef PRUptrdiff PtrBits;
 class nsAString;
 class nsIAtom;
 class nsICSSStyleRule;
 class nsISVGValue;
 class nsIDocument;
-template<class E> class nsTArray;
-template<class E> class nsTPtrArray;
+template<class E, class A> class nsTArray;
+template<class E, class A> class nsTPtrArray;
+struct nsTArrayDefaultAllocator;
 
 #define NS_ATTRVALUE_MAX_STRINGLENGTH_ATOM 12
 
 #define NS_ATTRVALUE_BASETYPE_MASK (PtrBits(3))
 #define NS_ATTRVALUE_POINTERVALUE_MASK (~NS_ATTRVALUE_BASETYPE_MASK)
 
 #define NS_ATTRVALUE_INTEGERTYPE_BITS 4
 #define NS_ATTRVALUE_INTEGERTYPE_MASK (PtrBits((1 << NS_ATTRVALUE_INTEGERTYPE_BITS) - 1))
@@ -376,17 +377,17 @@ private:
   // aStrict is set PR_TRUE if stringifying the return value equals with
   // aValue.
   PRInt32 StringToInteger(const nsAString& aValue,
                           PRBool* aStrict,
                           PRInt32* aErrorCode,
                           PRBool aCanBePercent = PR_FALSE,
                           PRBool* aIsPercent = nsnull) const;
 
-  static nsTPtrArray<const EnumTable>* sEnumTableArray;
+  static nsTPtrArray<const EnumTable, nsTArrayDefaultAllocator>* sEnumTableArray;
 
   PtrBits mBits;
 };
 
 /**
  * Implementation of inline methods
  */
 
--- a/content/base/src/nsDocument.cpp
+++ b/content/base/src/nsDocument.cpp
@@ -200,16 +200,18 @@ static NS_DEFINE_CID(kDOMEventGroupCID, 
 #include "nsHTMLStyleSheet.h"
 #include "nsHTMLCSSStyleSheet.h"
 
 #include "mozilla/dom/Link.h"
 #include "nsIHTMLDocument.h"
 
 using namespace mozilla::dom;
 
+typedef nsTArray<Link*> LinkArray;
+
 
 #ifdef PR_LOGGING
 static PRLogModuleInfo* gDocumentLeakPRLog;
 static PRLogModuleInfo* gCspPRLog;
 #endif
 
 #define NAME_NOT_VALID ((nsBaseContentList*)1)
 
@@ -3897,17 +3899,17 @@ nsDocument::InternalAllowXULXBL()
   return PR_FALSE;
 }
 
 // Note: We don't hold a reference to the document observer; we assume
 // that it has a live reference to the document.
 void
 nsDocument::AddObserver(nsIDocumentObserver* aObserver)
 {
-  NS_ASSERTION(mObservers.IndexOf(aObserver) == nsTArray_base::NoIndex,
+  NS_ASSERTION(mObservers.IndexOf(aObserver) == nsTArray<int>::NoIndex,
                "Observer already in the list");
   mObservers.AppendElement(aObserver);
   AddMutationObserver(aObserver);
 }
 
 PRBool
 nsDocument::RemoveObserver(nsIDocumentObserver* aObserver)
 {
@@ -7541,33 +7543,33 @@ nsDocument::DestroyElementMaps()
   mStyledLinks.Clear();
   mIdentifierMap.Clear();
 }
 
 static
 PLDHashOperator
 EnumerateStyledLinks(nsPtrHashKey<Link>* aEntry, void* aArray)
 {
-  nsTArray<Link*>* array = static_cast<nsTArray<Link*>*>(aArray);
+  LinkArray* array = static_cast<LinkArray*>(aArray);
   (void)array->AppendElement(aEntry->GetKey());
   return PL_DHASH_NEXT;
 }
 
 void
 nsDocument::RefreshLinkHrefs()
 {
   // Get a list of all links we know about.  We will reset them, which will
   // remove them from the document, so we need a copy of what is in the
   // hashtable.
-  nsTArray<Link*> linksToNotify(mStyledLinks.Count());
+  LinkArray linksToNotify(mStyledLinks.Count());
   (void)mStyledLinks.EnumerateEntries(EnumerateStyledLinks, &linksToNotify);
 
   // Reset all of our styled links.
   MOZ_AUTO_DOC_UPDATE(this, UPDATE_CONTENT_STATE, PR_TRUE);
-  for (nsTArray_base::size_type i = 0; i < linksToNotify.Length(); i++) {
+  for (LinkArray::size_type i = 0; i < linksToNotify.Length(); i++) {
     linksToNotify[i]->ResetLinkState(true);
   }
 }
 
 NS_IMETHODIMP
 nsDocument::GetScriptTypeID(PRUint32 *aScriptType)
 {
     NS_ERROR("No default script type here - ask some element");
--- a/docshell/shistory/public/nsISHistoryInternal.idl
+++ b/docshell/shistory/public/nsISHistoryInternal.idl
@@ -46,20 +46,21 @@ interface nsIDocShell;
 
 %{C++
 #define NS_SHISTORY_INTERNAL_CID \
 { 0x9c47c121, 0x1c6e, 0x4d8f, \
   { 0xb9, 0x04, 0x3a, 0xc9, 0x68, 0x11, 0x6e, 0x88 } }
 
 #define NS_SHISTORY_INTERNAL_CONTRACTID "@mozilla.org/browser/shistory-internal;1"
 
-template<class E> class nsTArray;
+template<class E, class A> class nsTArray;
+struct nsTArrayDefaultAllocator;
 %}
 
-[ref] native nsDocshellIDArray(nsTArray<PRUint64>);
+[ref] native nsDocshellIDArray(nsTArray<PRUint64, nsTArrayDefaultAllocator>);
 
 [scriptable, uuid(2dede933-25e1-47a3-8f61-0127c785ea01)]
 interface nsISHistoryInternal: nsISupports
 {
   /**
    * Add a new Entry to the History List
    * @param aEntry - The entry to add
    * @param aPersist - If true this specifies that the entry should persist
--- a/ipc/ipdl/ipdl/lower.py
+++ b/ipc/ipdl/ipdl/lower.py
@@ -331,17 +331,17 @@ def _callCxxArrayRemoveSorted(arr, elt):
     return ExprCall(ExprSelect(arr, '.', 'RemoveElementSorted'),
                     args=[ elt ])
 
 def _callCxxArrayClear(arr):
     return ExprCall(ExprSelect(arr, '.', 'Clear'))
 
 def _cxxArrayHasElementSorted(arr, elt):
     return ExprBinary(
-        ExprVar('nsTArray_base::NoIndex'), '!=',
+        ExprSelect(arr, '.', 'NoIndex'), '!=',
         ExprCall(ExprSelect(arr, '.', 'BinaryIndexOf'), args=[ elt ]))
 
 def _otherSide(side):
     if side == 'child':  return 'parent'
     if side == 'parent':  return 'child'
     assert 0
 
 def _ifLogging(stmts):
--- a/layout/base/FrameLayerBuilder.cpp
+++ b/layout/base/FrameLayerBuilder.cpp
@@ -322,17 +322,18 @@ protected:
    */
   nsIntRegion                      mInvalidThebesContent;
   nsAutoTArray<nsAutoPtr<ThebesLayerData>,1>  mThebesLayerDataStack;
   /**
    * We collect the list of children in here. During ProcessDisplayItems,
    * the layers in this array either have mContainerLayer as their parent,
    * or no parent.
    */
-  nsAutoTArray<nsRefPtr<Layer>,1>  mNewChildLayers;
+  typedef nsAutoTArray<nsRefPtr<Layer>,1> AutoLayersArray;
+  AutoLayersArray                  mNewChildLayers;
   nsTArray<nsRefPtr<ThebesLayer> > mRecycledThebesLayers;
   nsTArray<nsRefPtr<ColorLayer> >  mRecycledColorLayers;
   PRUint32                         mNextFreeRecycledThebesLayer;
   PRUint32                         mNextFreeRecycledColorLayer;
   PRPackedBool                     mInvalidateAllThebesContent;
 };
 
 class ThebesDisplayItemLayerUserData : public LayerUserData
@@ -798,18 +799,18 @@ ContainerState::PopThebesLayerData()
   ThebesLayerData* data = mThebesLayerDataStack[lastIndex];
 
   Layer* layer;
   if (data->mIsSolidColorInVisibleRegion) {
     nsRefPtr<ColorLayer> colorLayer = CreateOrRecycleColorLayer();
     colorLayer->SetColor(data->mSolidColor);
 
     NS_ASSERTION(!mNewChildLayers.Contains(colorLayer), "Layer already in list???");
-    nsTArray_base::index_type index = mNewChildLayers.IndexOf(data->mLayer);
-    NS_ASSERTION(index != nsTArray_base::NoIndex, "Thebes layer not found?");
+    AutoLayersArray::index_type index = mNewChildLayers.IndexOf(data->mLayer);
+    NS_ASSERTION(index != AutoLayersArray::NoIndex, "Thebes layer not found?");
     mNewChildLayers.InsertElementAt(index + 1, colorLayer);
 
     // Copy transform and clip rect
     colorLayer->SetTransform(data->mLayer->GetTransform());
     // Clip colorLayer to its visible region, since ColorLayers are
     // allowed to paint outside the visible region. Here we rely on the
     // fact that uniform display items fill rectangles; obviously the
     // area to fill must contain the visible region, and because it's
--- a/layout/generic/nsIAnonymousContentCreator.h
+++ b/layout/generic/nsIAnonymousContentCreator.h
@@ -42,17 +42,17 @@
 
 #ifndef nsIAnonymousContentCreator_h___
 #define nsIAnonymousContentCreator_h___
 
 #include "nsQueryFrame.h"
 #include "nsIContent.h"
 
 class nsIFrame;
-template <class T> class nsTArray;
+template <class T, class A> class nsTArray;
 
 /**
  * Any source for anonymous content can implement this interface to provide it.
  * HTML frames like nsFileControlFrame currently use this.
  *
  * @see nsCSSFrameConstructor
  */
 class nsIAnonymousContentCreator
--- a/layout/style/nsCSSStyleSheet.h
+++ b/layout/style/nsCSSStyleSheet.h
@@ -59,17 +59,17 @@ class nsMediaList;
 class nsICSSGroupRule;
 class nsICSSImportRule;
 class nsIPrincipal;
 class nsIURI;
 class nsMediaList;
 class nsMediaQueryResultCacheKey;
 class nsCSSStyleSheet;
 class nsPresContext;
-template<class E> class nsTArray;
+template<class E, class A> class nsTArray;
 
 // -------------------------------
 // CSS Style Sheet Inner Data Container
 //
 
 class nsCSSStyleSheetInner {
 public:
   friend class nsCSSStyleSheet;
--- a/memory/mozalloc/mozalloc.h
+++ b/memory/mozalloc/mozalloc.h
@@ -47,16 +47,18 @@
 
 #include <stdlib.h>
 #include <string.h>
 #if defined(__cplusplus)
 #  include <new>
 #endif
 
 
+#define MOZALLOC_HAVE_XMALLOC
+
 #if defined(MOZALLOC_EXPORT)
 /* do nothing: it's been defined to __declspec(dllexport) by
  * mozalloc*.cpp on platforms where that's required. */
 #elif defined(XP_WIN) || (defined(XP_OS2) && defined(__declspec))
 #  define MOZALLOC_EXPORT __declspec(dllimport)
 #elif defined(HAVE_VISIBILITY_ATTRIBUTE)
 /* Make sure symbols are still exported even if we're wrapped in a
  * |visibility push(hidden)| blanket. */
--- a/modules/libpref/public/nsIPrefService.idl
+++ b/modules/libpref/public/nsIPrefService.idl
@@ -37,20 +37,21 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "nsISupports.idl"
 #include "nsIPrefBranch.idl"
 
 %{C++
 struct PrefTuple;
-template<class E> class nsTArray;
+template<class E, class A> class nsTArray;
+struct nsTArrayDefaultAllocator;
 %}
 
-[ptr] native nsPreferencesArrayPtr(nsTArray<PrefTuple>);
+[ptr] native nsPreferencesArrayPtr(nsTArray<PrefTuple, nsTArrayDefaultAllocator>);
 [ptr] native nsPreferencePtr(PrefTuple);
 [ptr] native nsPreferencePtrConst(const PrefTuple);
 
 interface nsIFile;
 interface nsILocalFile;
 
 /**
  * The nsIPrefService interface is the main entry point into the back end
--- a/storage/src/mozStorageBindingParamsArray.h
+++ b/storage/src/mozStorageBindingParamsArray.h
@@ -47,23 +47,25 @@
 
 namespace mozilla {
 namespace storage {
 
 class StorageBaseStatementInternal;
 
 class BindingParamsArray : public mozIStorageBindingParamsArray
 {
+  typedef nsTArray< nsCOMPtr<mozIStorageBindingParams> > array_type;
+
 public:
   NS_DECL_ISUPPORTS
   NS_DECL_MOZISTORAGEBINDINGPARAMSARRAY
 
   BindingParamsArray(StorageBaseStatementInternal *aOwningStatement);
 
-  typedef nsTArray_base::size_type size_type;
+  typedef array_type::size_type size_type;
 
   /**
    * Locks the array and prevents further modification to it (such as adding
    * more elements to it).
    */
   void lock();
 
   /**
@@ -127,17 +129,17 @@ public:
   inline iterator end()
   {
     NS_ASSERTION(mLocked,
                  "Obtaining an iterator to the end when we are not locked!");
     return iterator(this, length());
   }
 private:
   nsCOMPtr<StorageBaseStatementInternal> mOwningStatement;
-  nsTArray< nsCOMPtr<mozIStorageBindingParams> > mArray;
+  array_type mArray;
   bool mLocked;
 
   friend class iterator;
 };
 
 } // namespace storage
 } // namespace mozilla
 
--- a/toolkit/components/places/src/nsMaybeWeakPtr.cpp
+++ b/toolkit/components/places/src/nsMaybeWeakPtr.cpp
@@ -56,60 +56,58 @@ nsMaybeWeakPtr_base::GetValueAs(const ns
     if (NS_SUCCEEDED(rv)) {
       return ref;
     }
   }
 
   return nsnull;
 }
 
-/* static */ nsresult
-nsMaybeWeakPtrArray_base::AppendWeakElementBase(nsTArray_base *aArray,
-                                                nsISupports *aElement,
-                                                PRBool aOwnsWeak)
+nsresult
+NS_AppendWeakElementBase(isupports_array_type *aArray,
+                         nsISupports *aElement,
+                         PRBool aOwnsWeak)
 {
   nsCOMPtr<nsISupports> ref;
   if (aOwnsWeak) {
     nsCOMPtr<nsIWeakReference> weakRef;
     weakRef = do_GetWeakReference(aElement);
     reinterpret_cast<nsCOMPtr<nsISupports>*>(&weakRef)->swap(ref);
   } else {
     ref = aElement;
   }
 
-  isupports_type *array = static_cast<isupports_type*>(aArray);
-  if (array->IndexOf(ref) != isupports_type::NoIndex) {
+  if (aArray->IndexOf(ref) != aArray->NoIndex) {
     return NS_ERROR_INVALID_ARG; // already present
   }
-  if (!array->AppendElement(ref)) {
+  if (!aArray->AppendElement(ref)) {
     return NS_ERROR_OUT_OF_MEMORY;
   }
   return NS_OK;
 }
 
-/* static */ nsresult
-nsMaybeWeakPtrArray_base::RemoveWeakElementBase(nsTArray_base *aArray,
-                                                nsISupports *aElement)
+nsresult
+NS_RemoveWeakElementBase(isupports_array_type *aArray,
+                         nsISupports *aElement)
 {
-  isupports_type *array = static_cast<isupports_type*>(aArray);
-  PRUint32 index = array->IndexOf(aElement);
-  if (index != isupports_type::NoIndex) {
-    array->RemoveElementAt(index);
+  PRUint32 index = aArray->IndexOf(aElement);
+  if (index != aArray->NoIndex) {
+    aArray->RemoveElementAt(index);
     return NS_OK;
   }
 
   // Don't use do_GetWeakReference; it should only be called if we know
   // the object supports weak references.
   nsCOMPtr<nsISupportsWeakReference> supWeakRef = do_QueryInterface(aElement);
   NS_ENSURE_TRUE(supWeakRef, NS_ERROR_INVALID_ARG);
 
   nsCOMPtr<nsIWeakReference> weakRef;
   nsresult rv = supWeakRef->GetWeakReference(getter_AddRefs(weakRef));
   NS_ENSURE_SUCCESS(rv, rv);
 
-  index = array->IndexOf(weakRef);
-  if (index == isupports_type::NoIndex) {
+  index = aArray->IndexOf(weakRef);
+  if (index == aArray->NoIndex) {
     return NS_ERROR_INVALID_ARG;
   }
 
-  array->RemoveElementAt(index);
+  aArray->RemoveElementAt(index);
   return NS_OK;
 }
--- a/toolkit/components/places/src/nsMaybeWeakPtr.h
+++ b/toolkit/components/places/src/nsMaybeWeakPtr.h
@@ -75,40 +75,36 @@ protected:
                                               (GetValueAs(NS_GET_TEMPLATE_IID(T)))));
   }
 };
 
 // nsMaybeWeakPtrArray is an array of MaybeWeakPtr objects, that knows how to
 // grab a weak reference to a given object if requested.  It only allows a
 // given object to appear in the array once.
 
-class nsMaybeWeakPtrArray_base
-{
-protected:
-  static nsresult AppendWeakElementBase(nsTArray_base *aArray,
-                                        nsISupports *aElement, PRBool aWeak);
-  static nsresult RemoveWeakElementBase(nsTArray_base *aArray,
-                                         nsISupports *aElement);
-
-  typedef nsTArray< nsMaybeWeakPtr<nsISupports> > isupports_type;
-};
+typedef nsTArray< nsMaybeWeakPtr<nsISupports> > isupports_array_type;
+nsresult NS_AppendWeakElementBase(isupports_array_type *aArray,
+                                  nsISupports *aElement, PRBool aWeak);
+nsresult NS_RemoveWeakElementBase(isupports_array_type *aArray,
+                                  nsISupports *aElement);
 
 template<class T>
-class nsMaybeWeakPtrArray : public nsTArray< nsMaybeWeakPtr<T> >,
-                            private nsMaybeWeakPtrArray_base
+class nsMaybeWeakPtrArray : public nsTArray< nsMaybeWeakPtr<T> >
 {
 public:
   nsresult AppendWeakElement(T *aElement, PRBool aOwnsWeak)
   {
-    return AppendWeakElementBase(this, aElement, aOwnsWeak);
+    return NS_AppendWeakElementBase(
+      reinterpret_cast<isupports_array_type*>(this), aElement, aOwnsWeak);
   }
 
   nsresult RemoveWeakElement(T *aElement)
   {
-    return RemoveWeakElementBase(this, aElement);
+    return NS_RemoveWeakElementBase(
+      reinterpret_cast<isupports_array_type*>(this), aElement);
   }
 };
 
 // Call a method on each element in the array, but only if the element is
 // non-null.
 
 #define ENUMERATE_WEAKARRAY(array, type, method)                           \
   for (PRUint32 array_idx = 0; array_idx < array.Length(); ++array_idx) {  \
--- a/xpcom/glue/Makefile.in
+++ b/xpcom/glue/Makefile.in
@@ -96,16 +96,17 @@ SDK_HEADERS = \
 		nsInterfaceHashtable.h \
 		nsMemory.h \
 		nsQuickSort.h \
 		nsRefPtrHashtable.h \
 		nsServiceManagerUtils.h \
 		nsStringAPI.h \
 		nsStringGlue.h \
 		nsTArray.h \
+		nsTArray-inl.h \
 		nsTHashtable.h \
 		nsTObserverArray.h \
 		nsTPtrArray.h \
 		nsTWeakRef.h \
 		nsTextFormatter.h \
 		nsTraceRefcnt.h \
 		nsVersionComparator.h \
 		nsVoidArray.h \
copy from xpcom/glue/nsTArray.cpp
copy to xpcom/glue/nsTArray-inl.h
--- a/xpcom/glue/nsTArray.cpp
+++ b/xpcom/glue/nsTArray-inl.h
@@ -31,132 +31,137 @@
  * use your version of this file under the terms of the MPL, indicate your
  * decision by deleting the provisions above and replace them with the notice
  * and other provisions required by the GPL or the LGPL. If you do not delete
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
-#include <string.h>
-#include "nsTArray.h"
-#include "nsXPCOM.h"
-#include "nsDebug.h"
+#ifndef nsTArray_h__
+#  error "Don't include this file directly"
+#endif
 
-nsTArray_base::Header nsTArray_base::sEmptyHdr = { 0, 0, 0 };
-
-nsTArray_base::nsTArray_base()
-  : mHdr(&sEmptyHdr) {
+template<class Alloc>
+nsTArray_base<Alloc>::nsTArray_base()
+  : mHdr(EmptyHdr()) {
   MOZ_COUNT_CTOR(nsTArray_base);
 }
 
-nsTArray_base::~nsTArray_base() {
-  if (mHdr != &sEmptyHdr && !UsesAutoArrayBuffer()) {
-    NS_Free(mHdr);
+template<class Alloc>
+nsTArray_base<Alloc>::~nsTArray_base() {
+  if (mHdr != EmptyHdr() && !UsesAutoArrayBuffer()) {
+    Alloc::Free(mHdr);
   }
   MOZ_COUNT_DTOR(nsTArray_base);
 }
 
+template<class Alloc>
 PRBool
-nsTArray_base::EnsureCapacity(size_type capacity, size_type elemSize) {
+nsTArray_base<Alloc>::EnsureCapacity(size_type capacity, size_type elemSize) {
   // This should be the most common case so test this first
   if (capacity <= mHdr->mCapacity)
     return PR_TRUE;
 
-  // If the requested memory allocation exceeds size_type(-1)/2, then our
-  // doubling algorithm may not be able to allocate it.  Additionally we
-  // couldn't fit in the Header::mCapacity member. Just bail out in cases
-  // like that.  We don't want to be allocating 2 GB+ arrays anyway.
+  // If the requested memory allocation exceeds size_type(-1)/2, then
+  // our doubling algorithm may not be able to allocate it.
+  // Additionally we couldn't fit in the Header::mCapacity
+  // member. Just bail out in cases like that.  We don't want to be
+  // allocating 2 GB+ arrays anyway.
   if ((PRUint64)capacity * elemSize > size_type(-1)/2) {
     NS_ERROR("Attempting to allocate excessively large array");
     return PR_FALSE;
   }
 
-  if (mHdr == &sEmptyHdr) {
-    // NS_Alloc new data
+  if (mHdr == EmptyHdr()) {
+    // Malloc() new data
     Header *header = static_cast<Header*>
-                                (NS_Alloc(sizeof(Header) + capacity * elemSize));
+                     (Alloc::Malloc(sizeof(Header) + capacity * elemSize));
     if (!header)
       return PR_FALSE;
     header->mLength = 0;
     header->mCapacity = capacity;
     header->mIsAutoArray = 0;
     mHdr = header;
-    
+
     return PR_TRUE;
   }
 
-  // Use doubling algorithm when forced to increase available capacity.
-  // (Note that mCapacity is only 31 bits wide, so multiplication promotes its
-  // type. We use |2u| instead of |2| to make sure it's promoted to unsigned.)
+  // Use doubling algorithm when forced to increase available
+  // capacity.  (Note that mCapacity is only 31 bits wide, so
+  // multiplication promotes its type. We use |2u| instead of |2|
+  // to make sure it's promoted to unsigned.)
   capacity = PR_MAX(capacity, mHdr->mCapacity * 2u);
 
   Header *header;
   if (UsesAutoArrayBuffer()) {
-    // NS_Alloc and copy
+    // Malloc() and copy
     header = static_cast<Header*>
-                        (NS_Alloc(sizeof(Header) + capacity * elemSize));
+             (Alloc::Malloc(sizeof(Header) + capacity * elemSize));
     if (!header)
       return PR_FALSE;
 
     memcpy(header, mHdr, sizeof(Header) + Length() * elemSize);
   } else {
-    // NS_Realloc existing data
+    // Realloc() existing data
     size_type size = sizeof(Header) + capacity * elemSize;
-    header = static_cast<Header*>(NS_Realloc(mHdr, size));
+    header = static_cast<Header*>(Alloc::Realloc(mHdr, size));
     if (!header)
       return PR_FALSE;
   }
 
   header->mCapacity = capacity;
   mHdr = header;
 
   return PR_TRUE;
 }
 
+template<class Alloc>
 void
-nsTArray_base::ShrinkCapacity(size_type elemSize) {
-  if (mHdr == &sEmptyHdr || UsesAutoArrayBuffer())
+nsTArray_base<Alloc>::ShrinkCapacity(size_type elemSize) {
+  if (mHdr == EmptyHdr() || UsesAutoArrayBuffer())
     return;
 
   if (mHdr->mLength >= mHdr->mCapacity)  // should never be greater than...
     return;
 
   size_type length = Length();
 
   if (IsAutoArray() && GetAutoArrayBuffer()->mCapacity >= length) {
     Header* header = GetAutoArrayBuffer();
 
     // Copy data, but don't copy the header to avoid overwriting mCapacity
     header->mLength = length;
     memcpy(header + 1, mHdr + 1, length * elemSize);
 
-    NS_Free(mHdr);
+    Alloc::Free(mHdr);
     mHdr = header;
     return;
   }
 
   if (length == 0) {
     NS_ASSERTION(!IsAutoArray(), "autoarray should have fit 0 elements");
-    NS_Free(mHdr);
-    mHdr = &sEmptyHdr;
+    Alloc::Free(mHdr);
+    mHdr = EmptyHdr();
     return;
   }
 
   size_type size = sizeof(Header) + length * elemSize;
-  void *ptr = NS_Realloc(mHdr, size);
+  void *ptr = Alloc::Realloc(mHdr, size);
   if (!ptr)
     return;
   mHdr = static_cast<Header*>(ptr);
   mHdr->mCapacity = length;
 }
 
+template<class Alloc>
 void
-nsTArray_base::ShiftData(index_type start, size_type oldLen, size_type newLen,
-                         size_type elemSize) {
+nsTArray_base<Alloc>::ShiftData(index_type start,
+                                size_type oldLen, size_type newLen,
+                                size_type elemSize) {
   if (oldLen == newLen)
     return;
 
   // Determine how many elements need to be shifted
   size_type num = mHdr->mLength - (start + oldLen);
 
   // Compute the resulting length of the array
   mHdr->mLength += newLen - oldLen;
@@ -171,78 +176,82 @@ nsTArray_base::ShiftData(index_type star
     newLen *= elemSize;
     oldLen *= elemSize;
     num *= elemSize;
     char *base = reinterpret_cast<char*>(mHdr + 1) + start;
     memmove(base + newLen, base + oldLen, num);
   }
 }
 
+template<class Alloc>
 PRBool
-nsTArray_base::InsertSlotsAt(index_type index, size_type count,
-                             size_type elementSize) {
+nsTArray_base<Alloc>::InsertSlotsAt(index_type index, size_type count,
+                                    size_type elementSize)  {
   NS_ASSERTION(index <= Length(), "Bogus insertion index");
   size_type newLen = Length() + count;
 
   EnsureCapacity(newLen, elementSize);
 
   // Check for out of memory conditions
   if (Capacity() < newLen)
     return PR_FALSE;
 
   // Move the existing elements as needed.  Note that this will
   // change our mLength, so no need to call IncrementLength.
   ShiftData(index, 0, count, elementSize);
       
   return PR_TRUE;
 }
 
+template<class Alloc>
+template<class Allocator>
 PRBool
-nsTArray_base::SwapArrayElements(nsTArray_base& other, size_type elemSize)
-{
+nsTArray_base<Alloc>::SwapArrayElements(nsTArray_base<Allocator>& other,
+                                        size_type elemSize) {
 #ifdef DEBUG
   PRBool isAuto = IsAutoArray();
   PRBool otherIsAuto = other.IsAutoArray();
 #endif
 
   if (!EnsureNotUsingAutoArrayBuffer(elemSize) ||
       !other.EnsureNotUsingAutoArrayBuffer(elemSize)) {
     return PR_FALSE;
   }
 
   NS_ASSERTION(isAuto == IsAutoArray(), "lost auto info");
   NS_ASSERTION(otherIsAuto == other.IsAutoArray(), "lost auto info");
   NS_ASSERTION(!UsesAutoArrayBuffer() && !other.UsesAutoArrayBuffer(),
                "both should be using an alloced buffer now");
 
-  // If the two arrays have different mIsAutoArray values (i.e. one is an
-  // autoarray and one is not) then simply switching the buffers is going to
-  // make that bit wrong. We therefore adjust these mIsAutoArray bits before
-  // switching the buffers so that once the buffers are switched the
-  // mIsAutoArray bits are right again.
+  // If the two arrays have different mIsAutoArray values (i.e. one is
+  // an autoarray and one is not) then simply switching the buffers is
+  // going to make that bit wrong. We therefore adjust these
+  // mIsAutoArray bits before switching the buffers so that once the
+  // buffers are switched the mIsAutoArray bits are right again.
   // However, we have to watch out so that we don't set the bit on
-  // sEmptyHeader. If an array (A) uses the empty header (and the other (B)
-  // therefore must be an nsAutoTArray) we make A point to the B's autobuffer
-  // so that when the buffers are switched B points to its own autobuffer.
+  // sEmptyHeader. If an array (A) uses the empty header (and the
+  // other (B) therefore must be an nsAutoTArray) we make A point to
+  // the B's autobuffer so that when the buffers are switched B points
+  // to its own autobuffer.
 
   // Adjust mIsAutoArray flags before swapping the buffers
   if (IsAutoArray() && !other.IsAutoArray()) {
-    if (other.mHdr == &sEmptyHdr) {
+    if (other.mHdr == EmptyHdr()) {
       // Set other to use our built-in buffer so that we use it
       // after the swap below.
       other.mHdr = GetAutoArrayBuffer();
       other.mHdr->mLength = 0;
     }
     else {
       other.mHdr->mIsAutoArray = 1;
     }
     mHdr->mIsAutoArray = 0;
   }
   else if (!IsAutoArray() && other.IsAutoArray()) {
-    if (mHdr == &sEmptyHdr) {
+    if (mHdr == EmptyHdr()) {
       // Set us to use other's built-in buffer so that other use it
       // after the swap below.
       mHdr = other.GetAutoArrayBuffer();
       mHdr->mLength = 0;
     }
     else {
       mHdr->mIsAutoArray = 1;
     }
@@ -255,23 +264,23 @@ nsTArray_base::SwapArrayElements(nsTArra
   mHdr = h;
 
   NS_ASSERTION(isAuto == IsAutoArray(), "lost auto info");
   NS_ASSERTION(otherIsAuto == other.IsAutoArray(), "lost auto info");
 
   return PR_TRUE;
 }
 
+template<class Alloc>
 PRBool
-nsTArray_base::EnsureNotUsingAutoArrayBuffer(size_type elemSize)
-{
+nsTArray_base<Alloc>::EnsureNotUsingAutoArrayBuffer(size_type elemSize) {
   if (UsesAutoArrayBuffer()) {
     size_type size = sizeof(Header) + Length() * elemSize;
 
-    Header* header = static_cast<Header*>(NS_Alloc(size));
+    Header* header = static_cast<Header*>(Alloc::Malloc(size));
     if (!header)
       return PR_FALSE;
 
     memcpy(header, mHdr, size);
     header->mCapacity = Length();
     mHdr = header;
   }
   
--- a/xpcom/glue/nsTArray.cpp
+++ b/xpcom/glue/nsTArray.cpp
@@ -36,244 +36,9 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include <string.h>
 #include "nsTArray.h"
 #include "nsXPCOM.h"
 #include "nsDebug.h"
 
-nsTArray_base::Header nsTArray_base::sEmptyHdr = { 0, 0, 0 };
-
-nsTArray_base::nsTArray_base()
-  : mHdr(&sEmptyHdr) {
-  MOZ_COUNT_CTOR(nsTArray_base);
-}
-
-nsTArray_base::~nsTArray_base() {
-  if (mHdr != &sEmptyHdr && !UsesAutoArrayBuffer()) {
-    NS_Free(mHdr);
-  }
-  MOZ_COUNT_DTOR(nsTArray_base);
-}
-
-PRBool
-nsTArray_base::EnsureCapacity(size_type capacity, size_type elemSize) {
-  // This should be the most common case so test this first
-  if (capacity <= mHdr->mCapacity)
-    return PR_TRUE;
-
-  // If the requested memory allocation exceeds size_type(-1)/2, then our
-  // doubling algorithm may not be able to allocate it.  Additionally we
-  // couldn't fit in the Header::mCapacity member. Just bail out in cases
-  // like that.  We don't want to be allocating 2 GB+ arrays anyway.
-  if ((PRUint64)capacity * elemSize > size_type(-1)/2) {
-    NS_ERROR("Attempting to allocate excessively large array");
-    return PR_FALSE;
-  }
-
-  if (mHdr == &sEmptyHdr) {
-    // NS_Alloc new data
-    Header *header = static_cast<Header*>
-                                (NS_Alloc(sizeof(Header) + capacity * elemSize));
-    if (!header)
-      return PR_FALSE;
-    header->mLength = 0;
-    header->mCapacity = capacity;
-    header->mIsAutoArray = 0;
-    mHdr = header;
-    
-    return PR_TRUE;
-  }
-
-  // Use doubling algorithm when forced to increase available capacity.
-  // (Note that mCapacity is only 31 bits wide, so multiplication promotes its
-  // type. We use |2u| instead of |2| to make sure it's promoted to unsigned.)
-  capacity = PR_MAX(capacity, mHdr->mCapacity * 2u);
-
-  Header *header;
-  if (UsesAutoArrayBuffer()) {
-    // NS_Alloc and copy
-    header = static_cast<Header*>
-                        (NS_Alloc(sizeof(Header) + capacity * elemSize));
-    if (!header)
-      return PR_FALSE;
-
-    memcpy(header, mHdr, sizeof(Header) + Length() * elemSize);
-  } else {
-    // NS_Realloc existing data
-    size_type size = sizeof(Header) + capacity * elemSize;
-    header = static_cast<Header*>(NS_Realloc(mHdr, size));
-    if (!header)
-      return PR_FALSE;
-  }
-
-  header->mCapacity = capacity;
-  mHdr = header;
-
-  return PR_TRUE;
-}
-
-void
-nsTArray_base::ShrinkCapacity(size_type elemSize) {
-  if (mHdr == &sEmptyHdr || UsesAutoArrayBuffer())
-    return;
-
-  if (mHdr->mLength >= mHdr->mCapacity)  // should never be greater than...
-    return;
-
-  size_type length = Length();
-
-  if (IsAutoArray() && GetAutoArrayBuffer()->mCapacity >= length) {
-    Header* header = GetAutoArrayBuffer();
-
-    // Copy data, but don't copy the header to avoid overwriting mCapacity
-    header->mLength = length;
-    memcpy(header + 1, mHdr + 1, length * elemSize);
-
-    NS_Free(mHdr);
-    mHdr = header;
-    return;
-  }
-
-  if (length == 0) {
-    NS_ASSERTION(!IsAutoArray(), "autoarray should have fit 0 elements");
-    NS_Free(mHdr);
-    mHdr = &sEmptyHdr;
-    return;
-  }
-
-  size_type size = sizeof(Header) + length * elemSize;
-  void *ptr = NS_Realloc(mHdr, size);
-  if (!ptr)
-    return;
-  mHdr = static_cast<Header*>(ptr);
-  mHdr->mCapacity = length;
-}
-
-void
-nsTArray_base::ShiftData(index_type start, size_type oldLen, size_type newLen,
-                         size_type elemSize) {
-  if (oldLen == newLen)
-    return;
-
-  // Determine how many elements need to be shifted
-  size_type num = mHdr->mLength - (start + oldLen);
-
-  // Compute the resulting length of the array
-  mHdr->mLength += newLen - oldLen;
-  if (mHdr->mLength == 0) {
-    ShrinkCapacity(elemSize);
-  } else {
-    // Maybe nothing needs to be shifted
-    if (num == 0)
-      return;
-    // Perform shift (change units to bytes first)
-    start *= elemSize;
-    newLen *= elemSize;
-    oldLen *= elemSize;
-    num *= elemSize;
-    char *base = reinterpret_cast<char*>(mHdr + 1) + start;
-    memmove(base + newLen, base + oldLen, num);
-  }
-}
-
-PRBool
-nsTArray_base::InsertSlotsAt(index_type index, size_type count,
-                             size_type elementSize) {
-  NS_ASSERTION(index <= Length(), "Bogus insertion index");
-  size_type newLen = Length() + count;
-
-  EnsureCapacity(newLen, elementSize);
-
-  // Check for out of memory conditions
-  if (Capacity() < newLen)
-    return PR_FALSE;
-
-  // Move the existing elements as needed.  Note that this will
-  // change our mLength, so no need to call IncrementLength.
-  ShiftData(index, 0, count, elementSize);
-      
-  return PR_TRUE;
-}
-
-PRBool
-nsTArray_base::SwapArrayElements(nsTArray_base& other, size_type elemSize)
-{
-#ifdef DEBUG
-  PRBool isAuto = IsAutoArray();
-  PRBool otherIsAuto = other.IsAutoArray();
-#endif
-
-  if (!EnsureNotUsingAutoArrayBuffer(elemSize) ||
-      !other.EnsureNotUsingAutoArrayBuffer(elemSize)) {
-    return PR_FALSE;
-  }
-
-  NS_ASSERTION(isAuto == IsAutoArray(), "lost auto info");
-  NS_ASSERTION(otherIsAuto == other.IsAutoArray(), "lost auto info");
-  NS_ASSERTION(!UsesAutoArrayBuffer() && !other.UsesAutoArrayBuffer(),
-               "both should be using an alloced buffer now");
-
-  // If the two arrays have different mIsAutoArray values (i.e. one is an
-  // autoarray and one is not) then simply switching the buffers is going to
-  // make that bit wrong. We therefore adjust these mIsAutoArray bits before
-  // switching the buffers so that once the buffers are switched the
-  // mIsAutoArray bits are right again.
-  // However, we have to watch out so that we don't set the bit on
-  // sEmptyHeader. If an array (A) uses the empty header (and the other (B)
-  // therefore must be an nsAutoTArray) we make A point to the B's autobuffer
-  // so that when the buffers are switched B points to its own autobuffer.
-
-  // Adjust mIsAutoArray flags before swapping the buffers
-  if (IsAutoArray() && !other.IsAutoArray()) {
-    if (other.mHdr == &sEmptyHdr) {
-      // Set other to use our built-in buffer so that we use it
-      // after the swap below.
-      other.mHdr = GetAutoArrayBuffer();
-      other.mHdr->mLength = 0;
-    }
-    else {
-      other.mHdr->mIsAutoArray = 1;
-    }
-    mHdr->mIsAutoArray = 0;
-  }
-  else if (!IsAutoArray() && other.IsAutoArray()) {
-    if (mHdr == &sEmptyHdr) {
-      // Set us to use other's built-in buffer so that other use it
-      // after the swap below.
-      mHdr = other.GetAutoArrayBuffer();
-      mHdr->mLength = 0;
-    }
-    else {
-      mHdr->mIsAutoArray = 1;
-    }
-    other.mHdr->mIsAutoArray = 0;
-  }
-
-  // Swap the buffers
-  Header *h = other.mHdr;
-  other.mHdr = mHdr;
-  mHdr = h;
-
-  NS_ASSERTION(isAuto == IsAutoArray(), "lost auto info");
-  NS_ASSERTION(otherIsAuto == other.IsAutoArray(), "lost auto info");
-
-  return PR_TRUE;
-}
-
-PRBool
-nsTArray_base::EnsureNotUsingAutoArrayBuffer(size_type elemSize)
-{
-  if (UsesAutoArrayBuffer()) {
-    size_type size = sizeof(Header) + Length() * elemSize;
-
-    Header* header = static_cast<Header*>(NS_Alloc(size));
-    if (!header)
-      return PR_FALSE;
-
-    memcpy(header, mHdr, size);
-    header->mCapacity = Length();
-    mHdr = header;
-  }
-  
-  return PR_TRUE;
-}
+nsTArrayHeader nsTArrayHeader::sEmptyHdr = { 0, 0, 0 };
--- a/xpcom/glue/nsTArray.h
+++ b/xpcom/glue/nsTArray.h
@@ -34,214 +34,289 @@
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef nsTArray_h__
 #define nsTArray_h__
 
+#include <string.h>
+
 #include "prtypes.h"
+#include "nscore.h"
 #include "nsQuickSort.h"
 #include "nsDebug.h"
 #include "nsTraceRefcnt.h"
 #include NEW_H
 
 //
+// NB: nsTArray assumes that your "T" can be memmove()d.  This is in
+// contrast to STL containers, which follow C++
+// construction/destruction rules.
+//
+// Don't use nsTArray if your "T" can't be memmove()d correctly.
+//
+
+//
+// nsTArray*Allocators must all use the same |free()|, to allow
+// swapping between fallible and infallible variants.  (NS_Free() and
+// moz_free() end up calling the same underlying free()).
+//
+
+struct nsTArrayFallibleAllocator
+{
+  static void* Malloc(size_t size) {
+    return NS_Alloc(size);
+  }
+
+  static void* Realloc(void* ptr, size_t size) {
+    return NS_Realloc(ptr, size);
+  }
+
+  static void Free(void* ptr) {
+    NS_Free(ptr);
+  }
+};
+
+#if defined(MOZALLOC_HAVE_XMALLOC)
+struct nsTArrayInfallibleAllocator
+{
+  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);
+  }
+};
+#endif
+
+struct nsTArrayDefaultAllocator : public nsTArrayFallibleAllocator { };
+
+// 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;
+
+  PRUint32 mLength;
+  PRUint32 mCapacity : 31;
+  PRUint32 mIsAutoArray : 1;
+};
+
+
+//
 // 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.
 //
-class NS_COM_GLUE nsTArray_base {
-  public:
-    typedef PRUint32 size_type;
-    typedef PRUint32 index_type;
+template<class Alloc>
+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>
+  friend class nsTArray_base;
 
-    // A special value that is used to indicate an invalid or unknown index
-    // into the array.
-    enum {
-      NoIndex = index_type(-1)
-    };
+protected:
+  typedef nsTArrayHeader Header;
+
+public:
+  typedef PRUint32 size_type;
+  typedef PRUint32 index_type;
 
-    // @return The number of elements in the array.
-    size_type Length() const {
-      return mHdr->mLength;
-    }
+  // @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.
-    PRBool IsEmpty() const {
-      return Length() == 0;
-    }
+  // @return True if the array is empty or false otherwise.
+  PRBool 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;
-    }
+  // @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;
-    }
+  void* DebugGetHeader() const {
+    return mHdr;
+  }
 #endif
 
-  protected:
-    nsTArray_base();
-    ~nsTArray_base();  
+protected:
+  nsTArray_base();
+
+  ~nsTArray_base();
 
-    // Resize the storage if necessary to achieve the requested capacity.
-    // @param capacity     The requested number of array elements.
-    // @param elementSize  The size of an array element.
-    // @return False if insufficient memory is available; true otherwise.
-    PRBool EnsureCapacity(size_type capacity, size_type elementSize);
+  // 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.
+  PRBool EnsureCapacity(size_type capacity, size_type elemSize);
 
-    // Resize the storage to the minimum required amount.
-    // @param elementSize  The size of an array element.
-    void ShrinkCapacity(size_type elementSize);
+  // Resize the storage to the minimum required amount.
+  // @param elemSize     The size of an array element.
+  void ShrinkCapacity(size_type elemSize);
     
-    // 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 elementSize  The size of an array element.
-    void ShiftData(index_type start, size_type oldLen, size_type newLen,
-                   size_type elementSize);
+  // 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.
+  void ShiftData(index_type start, size_type oldLen, size_type newLen,
+                 size_type elemSize);
+
+  // 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(PRUint32 n) {
+    NS_ASSERTION(mHdr != EmptyHdr() || n == 0, "bad data pointer");
+    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.
+  PRBool InsertSlotsAt(index_type index, size_type count,
+                       size_type elementSize);
 
-    // 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(PRUint32 n) {
-      NS_ASSERTION(mHdr != &sEmptyHdr || n == 0, "bad data pointer");
-      mHdr->mLength += n;
+protected:
+  // NOTE: This method isn't heavily optimized if either array is an
+  // nsAutoTArray.
+  template<class Allocator>
+  PRBool SwapArrayElements(nsTArray_base<Allocator>& other,
+                           size_type elemSize);
+
+  // Helper function for SwapArrayElements. Ensures that if the array
+  // is an nsAutoTArray that it doesn't use the built-in buffer.
+  PRBool EnsureNotUsingAutoArrayBuffer(size_type elemSize);
+
+  // Returns true if this nsTArray is an nsAutoTArray with a built-in buffer.
+  PRBool IsAutoArray() {
+    return mHdr->mIsAutoArray;
+  }
+
+  // Dummy struct to get the compiler to simulate the alignment of
+  // nsAutoTArray's and nsAutoTPtrArray's mAutoBuf.
+  struct AutoArray {
+    Header *mHdr;
+    PRUint64 aligned;
+  };
+
+  // Returns a Header for the built-in buffer of this nsAutoTArray.
+  Header* GetAutoArrayBuffer() {
+    NS_ASSERTION(IsAutoArray(), "Should be an auto array to call this");
+
+    return reinterpret_cast<Header*>(&(reinterpret_cast<AutoArray*>(&mHdr))->aligned);
     }
 
-    // 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.
-    PRBool InsertSlotsAt(index_type index, size_type count,
-                         size_type elementSize);
-
-  protected:
+  // Returns true if this is an nsAutoTArray and it currently uses the
+  // built-in buffer to store its elements.
+  PRBool UsesAutoArrayBuffer() {
+    return mHdr->mIsAutoArray && mHdr == GetAutoArrayBuffer();
+  }
 
-    // NOTE: This method isn't heavily optimized if either array is an
-    // nsAutoTArray.
-    PRBool SwapArrayElements(nsTArray_base& other, size_type elementSize);
-
-    // Helper function for SwapArrayElements. Ensures that if the array
-    // is an nsAutoTArray that it doesn't use the built-in buffer.
-    PRBool EnsureNotUsingAutoArrayBuffer(size_type elemSize);
-
-    // We prefix mData with a structure of this type.  This is done to minimize
-    // the size of the nsTArray object when it is empty.
-    struct Header {
-      PRUint32 mLength;
-      PRUint32 mCapacity : 31;
-      PRUint32 mIsAutoArray : 1;
-    };
+  // 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;
 
-    // Returns true if this nsTArray is an nsAutoTArray with a built-in buffer.
-    PRBool IsAutoArray() {
-      return mHdr->mIsAutoArray;
-    }
-
-    // Dummy struct to get the compiler to simulate the alignment of
-    // nsAutoTArray's and nsAutoTPtrArray's mAutoBuf.
-    struct AutoArray {
-      Header *mHdr;
-      PRUint64 aligned;
-    };
-
-    // Returns a Header for the built-in buffer of this nsAutoTArray.
-    Header* GetAutoArrayBuffer() {
-      NS_ASSERTION(IsAutoArray(), "Should be an auto array to call this");
+  Header* Hdr() const { 
+    return mHdr;
+  }
 
-      return reinterpret_cast<Header*>(&(reinterpret_cast<AutoArray*>(&mHdr))->aligned);
-    }
-
-    // Returns true if this is an nsAutoTArray and it currently uses the
-    // built-in buffer to store its elements.
-    PRBool UsesAutoArrayBuffer() {
-      return mHdr->mIsAutoArray && mHdr == GetAutoArrayBuffer();
-    }
+  Header** PtrToHdr() {
+    return &mHdr;
+  }
 
-    // This is not const since we may actually write to it. However we will
-    // always write to it the same data that it already contains. See
-    // IncrementLength
-    static Header sEmptyHdr;
-
-    // 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;
+  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) {
-      new (static_cast<void *>(e)) E(arg);
-    }
-    // Invoke the destructor in place.
-    static inline void Destruct(E *e) {
-      e->~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) {
+    new (static_cast<void *>(e)) E(arg);
+  }
+  // Invoke the destructor in place.
+  static inline void Destruct(E *e) {
+    e->~E();
+  }
 };
 
 // This class exists because VC6 cannot handle static template functions.
 // Otherwise, the Compare method would be defined directly on nsTArray.
 template <class E, class Comparator>
-class nsQuickSortComparator {
-  public:
-    typedef E elem_type;
-    // 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.  See nsTArray::Sort.
-    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);
-    }
+class nsQuickSortComparator
+{
+public:
+  typedef E elem_type;
+  // 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.  See nsTArray::Sort.
+  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);
+  }
 };
 
 // The default comparator used by nsTArray
 template<class A, class B>
-class nsDefaultComparator {
-  public:
-    PRBool Equals(const A& a, const B& b) const {
-      return a == b;
-    }
-    PRBool LessThan(const A& a, const B& b) const {
-      return a < b;
-    }
+class nsDefaultComparator
+{
+public:
+  PRBool Equals(const A& a, const B& b) const {
+    return a == b;
+  }
+  PRBool LessThan(const A& a, const B& b) const {
+    return a < b;
+  }
 };
 
 //
-// The templatized array class that dynamically resizes its storage as elements
-// are added.  This class is designed to behave a bit like std::vector.
+// The templatized array class that dynamically resizes its storage as
+// elements are added.  This class is designed to behave a bit like
+// std::vector, though note that unlike std::vector, nsTArray doesn't
+// follow C++ construction/destruction rules.
 //
 // The template parameter specifies the type of the elements (elem_type), and
 // has the following requirements:
 //
 //   elem_type MUST define a copy-constructor.
 //   elem_type MAY define operator< for sorting.
 //   elem_type MAY define operator== for searching.
 //
@@ -255,820 +330,931 @@ class nsDefaultComparator {
 //
 //       /** @return True if (a < b); false otherwise. */
 //       PRBool LessThan(const elem_type& a, const elem_type& b) const;
 //   };
 //
 // The Equals method is used for searching, and the LessThan method is used
 // for sorting.
 //
-template<class E>
-class nsTArray : public nsTArray_base {
-  public:
-    typedef E                        elem_type;
-    typedef nsTArray<E>              self_type;
-    typedef nsTArrayElementTraits<E> elem_traits;
+// The Alloc template parameter can be used to choose between
+// "fallible" and "infallible" nsTArray (if available), defaulting to
+// fallible.  If the *fallible* allocator is used, the return value of
+// methods that might allocate doesn't need to be checked; Append() is
+// one such method.  These return values don't need to be checked if
+// the *in*fallible allocator is chosen.  When in doubt, choose the
+// infallible allocator.
+//
+template<class E, class Alloc=nsTArrayDefaultAllocator>
+class nsTArray : public nsTArray_base<Alloc>
+{
+public:
+  typedef nsTArray_base<Alloc>           base_type;
+  typedef typename base_type::size_type  size_type;
+  typedef typename base_type::index_type index_type;
+  typedef E                              elem_type;
+  typedef nsTArray<E, Alloc>             self_type;
+  typedef nsTArrayElementTraits<E>       elem_traits;
 
-    //
-    // Finalization method
-    //
+  // A special value that is used to indicate an invalid or unknown index
+  // into the array.
+  enum {
+    NoIndex = index_type(-1)
+  };
 
-    ~nsTArray() { Clear(); }
+  using base_type::Length;
 
-    //
-    // Initialization methods
-    //
+  //
+  // Finalization method
+  //
 
-    nsTArray() {}
+  ~nsTArray() { Clear(); }
+
+  //
+  // Initialization methods
+  //
 
-    // Initialize this array and pre-allocate some number of elements.
-    explicit nsTArray(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.
-    nsTArray(const self_type& other) {
-      AppendElements(other);
-    }
+  nsTArray() {}
+
+  // Initialize this array and pre-allocate some number of elements.
+  explicit nsTArray(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.
+  nsTArray(const self_type& other) {
+    AppendElements(other);
+  }
+
+  template<typename Allocator>
+  nsTArray(const nsTArray<E, Allocator>& other) {
+    AppendElements(other);
+  }
 
-    // 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.
-    nsTArray& operator=(const self_type& other) {
-      ReplaceElementsAt(0, Length(), other.Elements(), other.Length());
-      return *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.
+  nsTArray& 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|.
-    bool operator==(const self_type& other) const {
-      size_type len = Length();
-      if (len != other.Length())
+  // Return true if this array has the same length and the same
+  // elements as |other|.
+  bool operator==(const self_type& 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;
 
-      // 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;
-    }
+  // 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);
+  }
 
-    // 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>
+  nsTArray& operator=(const nsTArray<E, Allocator>& other) {
+    ReplaceElementsAt(0, Length(), other.Elements(), other.Length());
+    return *this;
+  }
 
-    //
-    // Accessor methods
-    //
+  //
+  // 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 *>(mHdr + 1);
-    }
+  // 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 *>(mHdr + 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) {
-      NS_ASSERTION(i < Length(), "invalid array index");
-      return Elements()[i];
-    }
+  // 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) {
+    NS_ASSERTION(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 {
+    NS_ASSERTION(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 {
-      NS_ASSERTION(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);
+  }
 
-    // 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;
-    }
+  //
+  // 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       PR_TRUE if the element was found.
+  template<class Item, class Comparator>
+  PRBool 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       PR_TRUE if the element was found.
+  template<class Item>
+  PRBool Contains(const Item& item) const {
+    return IndexOf(item) != NoIndex;
+  }
 
-    // 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;
+  // 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 iter - Elements();
     }
+    return NoIndex;
+  }
 
-    // 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);
-    }
+  // 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>());
+  }
 
-    //
-    // Search methods
-    //
+  // 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 {
+    if (start >= Length())
+      start = Length() - 1;
+    const elem_type* end = Elements() - 1, *iter = end + start + 1;
+    for (; iter != end; --iter) {
+      if (comp.Equals(*iter, item))
+        return index_type(iter - Elements());
+    }
+    return NoIndex;
+  }
 
-    // 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       PR_TRUE if the element was found.
-    template<class Item, class Comparator>
-    PRBool Contains(const Item& item, const Comparator& comp) const {
-      return IndexOf(item, 0, comp) != 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 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       PR_TRUE if the element was found.
-    template<class Item>
-    PRBool Contains(const Item& item) const {
-      return IndexOf(item) != 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.
+  // @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 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 iter - Elements();
-      }
-      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 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 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 (!EnsureCapacity(Length() + arrayLen - count, sizeof(elem_type)))
+      return nsnull;
+    DestructRange(start, count);
+    ShiftData(start, count, arrayLen, sizeof(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());
+  }
 
-    // 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 {
-      if (start >= Length())
-        start = Length() - 1;
-      const elem_type* end = Elements() - 1, *iter = end + start + 1;
-      for (; iter != end; --iter) {
-        if (comp.Equals(*iter, item))
-          return index_type(iter - Elements());
-      }
-      return NoIndex;
-    }
+  // 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 *InsertElementsAt(index_type index, const Item* array,
+                              size_type arrayLen) {
+    return ReplaceElementsAt(index, 0, array, arrayLen);
+  }
 
-    // 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>());
-    }
+  // A variation on the ReplaceElementsAt method defined above.
+  template<class Item>
+  elem_type *InsertElementsAt(index_type index, const nsTArray<Item>& 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 (!EnsureCapacity(Length() + 1, sizeof(elem_type)))
+      return nsnull;
+    ShiftData(index, 0, 1, sizeof(elem_type));
+    elem_type *elem = Elements() + index;
+    elem_traits::Construct(elem);
+    return elem;
+  }
 
-    // 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;
+  // This method searches for the least index of the greatest
+  // element less than or equal to |item|.  If |item| is inserted at
+  // this index, the array will remain sorted.  True is returned iff
+  // this index is also equal to |item|.  In this case, the returned
+  // index may point to the start of multiple copies of |item|.
+  // @param item   The item to search for.
+  // @param comp   The Comparator used.
+  // @outparam idx The index of greatest element <= to |item|
+  // @return       True iff |item == array[*idx]|.
+  // @precondition The array is sorted
+  template<class Item, class Comparator>
+  PRBool
+  GreatestIndexLtEq(const Item& item,
+                    const Comparator& comp,
+                    index_type* idx NS_OUTPARAM) const {
+    // Nb: we could replace all the uses of "BinaryIndexOf" with this
+    // function, but BinaryIndexOf will be oh-so-slightly faster so
+    // it's not strictly desired to do.
+
+    // invariant: low <= [idx] < high
+    index_type low = 0, high = Length();
+    while (high > low) {
+      index_type mid = (high + low) >> 1;
+      if (comp.Equals(ElementAt(mid), item)) {
+        // we might have the array [..., 2, 4, 4, 4, 4, 4, 5, ...]
+        // and be searching for "4". it's arbitrary where mid ends
+        // up here, so we back it up to the first instance to maintain
+        // the "least index ..." we promised above.
+        do {
+          --mid;
+        } while (NoIndex != mid && comp.Equals(ElementAt(mid), item));
+        *idx = ++mid;
+        return PR_TRUE;
       }
-      return NoIndex;
+      if (comp.LessThan(ElementAt(mid), item))
+        // invariant: low <= idx < high
+        low = mid + 1;
+      else
+        // invariant: low <= idx < high
+        high = mid;
     }
+    // low <= idx < high, so insert at high ("shifting" high up by
+    // 1) to maintain invariant.
+    // (or insert at low, since low==high; just a matter of taste here.)
+    *idx = high;
+    return PR_FALSE;
+  }
 
-    // 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>());
-    }
+  // A variation on the GreatestIndexLtEq method defined above.
+  template<class Item, class Comparator>
+  PRBool
+  GreatestIndexLtEq(const Item& item,
+                    index_type& idx,
+                    const Comparator& comp) const {
+    return GreatestIndexLtEq(item, comp, &idx);
+  }
 
-    //
-    // Mutation methods
-    //
+  // A variation on the GreatestIndexLtEq method defined above.
+  template<class Item>
+  PRBool
+  GreatestIndexLtEq(const Item& item,
+                    index_type& idx) const {
+    return GreatestIndexLtEq(item, nsDefaultComparator<elem_type, Item>(), &idx);
+  }
 
-    // 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 (!EnsureCapacity(Length() + arrayLen - count, sizeof(elem_type)))
-        return nsnull;
-      DestructRange(start, count);
-      ShiftData(start, count, arrayLen, sizeof(elem_type));
-      AssignRange(start, arrayLen, array);
-      return Elements() + start;
-    }
+  // 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;
+    GreatestIndexLtEq(item, comp, &index);
+    return InsertElementAt(index, item);
+  }
+
+  // A variation on the InsertElementSorted metod 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 (!EnsureCapacity(Length() + arrayLen, sizeof(elem_type)))
+      return nsnull;
+    index_type len = Length();
+    AssignRange(len, arrayLen, array);
+    IncrementLength(arrayLen);
+    return Elements() + len;
+  }
 
-    // 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 AppendElements method defined above.
+  template<class Item, class Allocator>
+  elem_type *AppendElements(const nsTArray<Item, Allocator>& array) {
+    return AppendElements(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 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 (!EnsureCapacity(Length() + count, sizeof(elem_type)))
+      return nsnull;
+    elem_type *elems = Elements() + Length();
+    size_type i;
+    for (i = 0; i < count; ++i) {
+      elem_traits::Construct(elems + i);
     }
-    
-    // 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);
-    }
+    IncrementLength(count);
+    return elems;
+  }
 
-    // A variation on the ReplaceElementsAt method defined above.
-    template<class Item>
-    elem_type *InsertElementsAt(index_type index, const nsTArray<Item>& array) {
-      return ReplaceElementsAt(index, 0, array.Elements(), array.Length());
-    }
+  // 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);
+  }
 
-    // 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);
-    }
+  // 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<Item, Allocator>& array) {
+    NS_PRECONDITION(&array != this, "argument must be different array");
+    index_type len = Length();
+    index_type otherLen = array.Length();
+    if (!EnsureCapacity(len + otherLen, sizeof(elem_type)))
+      return nsnull;
+    memcpy(Elements() + len, array.Elements(), otherLen * sizeof(elem_type));
+    IncrementLength(otherLen);      
+    array.ShiftData(0, otherLen, 0, sizeof(elem_type));
+    return Elements() + len;
+  }
 
-    // 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 (!EnsureCapacity(Length() + 1, sizeof(elem_type)))
-         return nsnull;
-      ShiftData(index, 0, 1, sizeof(elem_type));
-      elem_type *elem = Elements() + index;
-      elem_traits::Construct(elem);
-      return elem;
-    }
+  // 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) {
+    NS_ASSERTION(count == 0 || start < Length(), "Invalid start index");
+    NS_ASSERTION(start + count <= Length(), "Invalid length");
+    DestructRange(start, count);
+    ShiftData(start, count, 0, sizeof(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 method searches for the least index of the greatest
-    // element less than or equal to |item|.  If |item| is inserted at
-    // this index, the array will remain sorted.  True is returned iff
-    // this index is also equal to |item|.  In this case, the returned
-    // index may point to the start of multiple copies of |item|.
-    // @param item   The item to search for.
-    // @param comp   The Comparator used.
-    // @outparam idx The index of greatest element <= to |item|
-    // @return       True iff |item == array[*idx]|.
-    // @precondition The array is sorted
-    template<class Item, class Comparator>
-    PRBool
-    GreatestIndexLtEq(const Item& item,
-                      const Comparator& comp,
-                      index_type* idx NS_OUTPARAM) const {
-      // Nb: we could replace all the uses of "BinaryIndexOf" with this
-      // function, but BinaryIndexOf will be oh-so-slightly faster so
-      // it's not strictly desired to do.
+  // 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 PR_TRUE if the element was found
+  template<class Item, class Comparator>
+  PRBool RemoveElement(const Item& item, const Comparator& comp) {
+    index_type i = IndexOf(item, 0, comp);
+    if (i == NoIndex)
+      return PR_FALSE;
+
+    RemoveElementAt(i);
+    return PR_TRUE;
+  }
+
+  // A variation on the RemoveElement method defined above that assumes
+  // that 'operator==' is defined for elem_type.
+  template<class Item>
+  PRBool RemoveElement(const Item& item) {
+    return RemoveElement(item, nsDefaultComparator<elem_type, Item>());
+  }
+
+  // This helper function combines GreatestIndexLtEq 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 PR_TRUE if the element was found
+  template<class Item, class Comparator>
+  PRBool RemoveElementSorted(const Item& item, const Comparator& comp) {
+    index_type index;
+    PRBool found = GreatestIndexLtEq(item, comp, &index);
+    if (found)
+      RemoveElementAt(index);
+    return found;
+  }
 
-      // invariant: low <= [idx] < high
-      index_type low = 0, high = Length();
-      while (high > low) {
-        index_type mid = (high + low) >> 1;
-        if (comp.Equals(ElementAt(mid), item)) {
-          // we might have the array [..., 2, 4, 4, 4, 4, 4, 5, ...]
-          // and be searching for "4". it's arbitrary where mid ends
-          // up here, so we back it up to the first instance to maintain
-          // the "least index ..." we promised above.
-          do {
-            --mid;
-          } while (NoIndex != mid && comp.Equals(ElementAt(mid), item));
-          *idx = ++mid;
-          return PR_TRUE;
-        }
-        if (comp.LessThan(ElementAt(mid), item))
-          // invariant: low <= idx < high
-          low = mid + 1;
-        else
-          // invariant: low <= idx < high
-          high = mid;
-      }
-      // low <= idx < high, so insert at high ("shifting" high up by
-      // 1) to maintain invariant.
-      // (or insert at low, since low==high; just a matter of taste here.)
-      *idx = high;
-      return PR_FALSE;
+  // A variation on the RemoveElementSorted method defined above.
+  template<class Item>
+  PRBool 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.
+  // NOTE: This method isn't heavily optimized if either array is an
+  // nsAutoTArray.
+  template<class Allocator>
+  PRBool SwapElements(nsTArray<E, Allocator>& other) {
+    return SwapArrayElements(other, sizeof(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
+  PRBool SetCapacity(size_type capacity) {
+    return 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.
+  PRBool SetLength(size_type newLen) {
+    size_type oldLen = Length();
+    if (newLen > oldLen) {
+      return InsertElementsAt(oldLen, newLen - oldLen) != nsnull;
     }
+      
+    TruncateLength(newLen);
+    return PR_TRUE;
+  }
 
-    // A variation on the GreatestIndexLtEq method defined above.
-    template<class Item, class Comparator>
-    PRBool
-    GreatestIndexLtEq(const Item& item,
-                      index_type& idx,
-                      const Comparator& comp) const {
-      return GreatestIndexLtEq(item, comp, &idx);
-    }
+  // 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);
+  }
 
-    // A variation on the GreatestIndexLtEq method defined above.
-    template<class Item>
-    PRBool
-    GreatestIndexLtEq(const Item& item,
-                      index_type& idx) const {
-      return GreatestIndexLtEq(item, nsDefaultComparator<elem_type, Item>(), &idx);
+  // 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.
+  PRBool EnsureLengthAtLeast(size_type minLen) {
+    size_type oldLen = Length();
+    if (minLen > oldLen) {
+      return InsertElementsAt(oldLen, minLen - oldLen) != nsnull;
     }
+    return PR_TRUE;
+  }
 
-    // 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;
-      GreatestIndexLtEq(item, comp, &index);
-      return InsertElementAt(index, item);
+  // 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))) {
+      return nsnull;
     }
 
-    // A variation on the InsertElementSorted metod 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 (!EnsureCapacity(Length() + arrayLen, sizeof(elem_type)))
-        return nsnull;
-      index_type len = Length();
-      AssignRange(len, arrayLen, array);
-      IncrementLength(arrayLen);
-      return Elements() + len;
-    }
-
-    // A variation on the AppendElements method defined above.
-    template<class Item>
-    elem_type *AppendElements(const nsTArray<Item>& 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 (!EnsureCapacity(Length() + count, sizeof(elem_type)))
-         return nsnull;
-      elem_type *elems = Elements() + Length();
-      size_type i;
-      for (i = 0; i < count; ++i) {
-        elem_traits::Construct(elems + i);
-      }
-      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>
-    elem_type *MoveElementsFrom(nsTArray<Item>& array) {
-      NS_PRECONDITION(&array != this, "argument must be different array");
-      index_type len = Length();
-      index_type otherLen = array.Length();
-      if (!EnsureCapacity(len + otherLen, sizeof(elem_type)))
-        return nsnull;
-      memcpy(Elements() + len, array.Elements(), otherLen * sizeof(elem_type));
-      IncrementLength(otherLen);      
-      array.ShiftData(0, otherLen, 0, sizeof(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) {
-      NS_ASSERTION(count == 0 || start < Length(), "Invalid start index");
-      NS_ASSERTION(start + count <= Length(), "Invalid length");
-      DestructRange(start, count);
-      ShiftData(start, count, 0, sizeof(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());
+    // Initialize the extra array elements
+    elem_type *iter = Elements() + index, *end = iter + count;
+    for (; iter != end; ++iter) {
+      elem_traits::Construct(iter);
     }
 
-    // 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 PR_TRUE if the element was found
-    template<class Item, class Comparator>
-    PRBool RemoveElement(const Item& item, const Comparator& comp) {
-      index_type i = IndexOf(item, 0, comp);
-      if (i == NoIndex)
-        return PR_FALSE;
-
-      RemoveElementAt(i);
-      return PR_TRUE;
-    }
+    return Elements() + index;
+  }
 
-    // A variation on the RemoveElement method defined above that assumes
-    // that 'operator==' is defined for elem_type.
-    template<class Item>
-    PRBool RemoveElement(const Item& item) {
-      return RemoveElement(item, nsDefaultComparator<elem_type, Item>());
-    }
-
-    // This helper function combines GreatestIndexLtEq 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 PR_TRUE if the element was found
-    template<class Item, class Comparator>
-    PRBool RemoveElementSorted(const Item& item, const Comparator& comp) {
-      index_type index;
-      PRBool found = GreatestIndexLtEq(item, comp, &index);
-      if (found)
-        RemoveElementAt(index);
-      return found;
-    }
-
-    // A variation on the RemoveElementSorted method defined above.
-    template<class Item>
-    PRBool RemoveElementSorted(const Item& item) {
-      return RemoveElementSorted(item, nsDefaultComparator<elem_type, Item>());
+  // 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))) {
+      return nsnull;
     }
 
-    // This method causes the elements contained in this array and the given
-    // array to be swapped.
-    // NOTE: This method isn't heavily optimized if either array is an
-    // nsAutoTArray.
-    PRBool SwapElements(self_type& other) {
-      return SwapArrayElements(other, sizeof(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
-    PRBool SetCapacity(size_type capacity) {
-      return 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.
-    PRBool SetLength(size_type newLen) {
-      size_type oldLen = Length();
-      if (newLen > oldLen) {
-        return InsertElementsAt(oldLen, newLen - oldLen) != nsnull;
-      }
-      
-      TruncateLength(newLen);
-      return PR_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);
+    // Initialize the extra array elements
+    elem_type *iter = Elements() + index, *end = iter + count;
+    for (; iter != end; ++iter) {
+      elem_traits::Construct(iter, item);
     }
 
-    // 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.
-    PRBool EnsureLengthAtLeast(size_type minLen) {
-      size_type oldLen = Length();
-      if (minLen > oldLen) {
-        return InsertElementsAt(oldLen, minLen - oldLen) != nsnull;
-      }
-      return PR_TRUE;
-    }
+    return Elements() + index;
+  }
+
+  // This method may be called to minimize the memory used by this array.
+  void Compact() {
+    ShrinkCapacity(sizeof(elem_type));
+  }
 
-    // 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 (!nsTArray_base::InsertSlotsAt(index, count, sizeof(elem_type))) {
-        return nsnull;
-      }
-
-      // Initialize the extra array elements
-      elem_type *iter = Elements() + index, *end = iter + count;
-      for (; iter != end; ++iter) {
-        elem_traits::Construct(iter);
-      }
+  //
+  // Sorting
+  //
 
-      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 (!nsTArray_base::InsertSlotsAt(index, count, sizeof(elem_type))) {
-        return nsnull;
-      }
+  // 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),
+                 nsQuickSortComparator<elem_type, Comparator>::Compare,
+                 const_cast<Comparator*>(&comp));
+  }
 
-      // 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;
-    }
+  // 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>());
+  }
 
-    // This method may be called to minimize the memory used by this array.
-    void Compact() {
-      ShrinkCapacity(sizeof(elem_type));
-    }
-
-    //
-    // Sorting
-    //
+  //
+  // Binary Heap
+  //
 
-    // 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),
-                   nsQuickSortComparator<elem_type, Comparator>::Compare,
-                   const_cast<Comparator*>(&comp));
+  // 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;
     }
-
-    // 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>());
-    }
+    index_type index = (Length() - 1) / 2;
+    do {
+      SiftDown(index, comp);
+    } while (index--);
+  }
 
-    //
-    // 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>());
+  }
 
-    // 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))) {
+      return nsnull;
     }
+    // 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];
+  }
 
-    // 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 (!nsTArray_base::InsertSlotsAt(Length(), 1, sizeof(elem_type))) {
-        return nsnull;
-      }
-      // 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>());
+  }
 
-    // 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;
     }
-
-    // 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);
-      }
+    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>());
-    }
+  // A variation on the PopHeap method defined above.
+  void PopHeap() {
+    PopHeap(nsDefaultComparator<elem_type, elem_type>());
+  }
 
-  protected:
+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 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) {
-      elem_type *iter = Elements() + start, *end = iter + count;
-      for (; iter != end; ++iter, ++values) {
-        elem_traits::Construct(iter, *values);
-      }
+  // 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) {
+    elem_type *iter = Elements() + start, *end = iter + count;
+    for (; iter != end; ++iter, ++values) {
+      elem_traits::Construct(iter, *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])) {
+  // 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 {
-          break;
+          index = left;
         }
-        elem[parent_index] = elem[index];
+      } else if (left < end &&
+                 comp.LessThan(item, elem[right])) {
+        index = right;
+      } else {
+        break;
       }
-      elem[index] = item;
+      elem[parent_index] = elem[index];
     }
+    elem[index] = item;
+  }
+};
+
+//
+// Convenience subtypes of nsTArray.
+//
+template<class E>
+class FallibleTArray : public nsTArray<E, nsTArrayFallibleAllocator>
+{
+public:
+  typedef nsTArray<E, nsTArrayFallibleAllocator>   base_type;
+  typedef typename base_type::size_type            size_type;
+
+  FallibleTArray() {}
+  explicit FallibleTArray(size_type capacity) : base_type(capacity) {}
+  FallibleTArray(const FallibleTArray& other) : base_type(other) {}
+};
+
+#ifdef MOZALLOC_HAVE_XMALLOC
+template<class E>
+class InfallibleTArray : public nsTArray<E, nsTArrayInfallibleAllocator>
+{
+public:
+  typedef nsTArray<E, nsTArrayInfallibleAllocator> base_type;
+  typedef typename base_type::size_type            size_type;
+ 
+  InfallibleTArray() {}
+  explicit InfallibleTArray(size_type capacity) : base_type(capacity) {}
+  InfallibleTArray(const InfallibleTArray& other) : base_type(other) {}
+};
+#endif
+
+
+template<class TArrayBase, PRUint32 N>
+class nsAutoArrayBase : public TArrayBase
+{
+public:
+  typedef TArrayBase base_type;
+  typedef typename base_type::Header Header;
+  typedef typename base_type::elem_type elem_type;
+
+  nsAutoArrayBase() {
+    *base_type::PtrToHdr() = reinterpret_cast<Header*>(&mAutoBuf);
+    base_type::Hdr()->mLength = 0;
+    base_type::Hdr()->mCapacity = N;
+    base_type::Hdr()->mIsAutoArray = 1;
+
+    NS_ASSERTION(base_type::GetAutoArrayBuffer() ==
+                 reinterpret_cast<Header*>(&mAutoBuf),
+                 "GetAutoArrayBuffer needs to be fixed");
+  }
+
+protected:
+  union {
+    char mAutoBuf[sizeof(Header) + N * sizeof(elem_type)];
+    PRUint64 dummy;
+  };
+};
+
+template<class E, PRUint32 N, class Alloc=nsTArrayDefaultAllocator>
+class nsAutoTArray : public nsAutoArrayBase<nsTArray<E, Alloc>, N>
+{
+public:
+  nsAutoTArray() {}
 };
 
 template<class E, PRUint32 N>
-class nsAutoTArray : public nsTArray<E> {
-  public:
-    typedef nsTArray<E> base_type;
-    typedef typename base_type::Header Header;
-    typedef typename base_type::elem_type elem_type;
-
-    nsAutoTArray() {
-      base_type::mHdr = reinterpret_cast<Header*>(&mAutoBuf);
-      base_type::mHdr->mLength = 0;
-      base_type::mHdr->mCapacity = N;
-      base_type::mHdr->mIsAutoArray = 1;
-
-      NS_ASSERTION(base_type::GetAutoArrayBuffer() ==
-                   reinterpret_cast<Header*>(&mAutoBuf),
-                   "GetAutoArrayBuffer needs to be fixed");
-    }
-
-  protected:
-    union {
-      char mAutoBuf[sizeof(Header) + N * sizeof(elem_type)];
-      PRUint64 dummy;
-    };
+class AutoFallibleTArray : public nsAutoArrayBase<FallibleTArray<E>, N>
+{
+public:
+  AutoFallibleTArray() {}
 };
 
-// specialization for N = 0. this makes the inheritance model easier for
+#if defined(MOZALLOC_HAVE_XMALLOC)
+template<class E, PRUint32 N>
+class AutoInfallibleTArray : public nsAutoArrayBase<InfallibleTArray<E>, N>
+{
+public:
+  AutoInfallibleTArray() {}
+};
+#endif
+
+// specializations for N = 0. this makes the inheritance model easier for
 // templated users of nsAutoTArray.
 template<class E>
-class nsAutoTArray<E, 0> : public nsTArray<E> {
-  public:
-    nsAutoTArray() {}
+class nsAutoTArray<E, 0, nsTArrayDefaultAllocator> :
+  public nsAutoArrayBase< nsTArray<E, nsTArrayDefaultAllocator>, 0>
+{
+public:
+  nsAutoTArray() {}
+};
+
+template<class E>
+class AutoFallibleTArray<E, 0> :
+  public nsAutoArrayBase< FallibleTArray<E>, 0>
+{
+public:
+  AutoFallibleTArray() {}
 };
 
+#if defined(MOZALLOC_HAVE_XMALLOC)
+template<class E>
+class AutoInfallibleTArray<E, 0> :
+  public nsAutoArrayBase< InfallibleTArray<E>, 0>
+{
+public:
+  AutoInfallibleTArray() {}
+};
+#endif
+ 
+// Definitions of nsTArray methods
+#include "nsTArray-inl.h"
+
 #endif  // nsTArray_h__
--- a/xpcom/glue/nsTPtrArray.h
+++ b/xpcom/glue/nsTPtrArray.h
@@ -42,21 +42,21 @@
 
 #include "nsTArray.h"
 
 //
 // The templatized array class for storing pointers. The class is based on
 // nsTArray and has all the features of that class, in addition to an
 // implementation of SafeElementAt that returns null for out of bounds access
 //
-template<class E>
-class nsTPtrArray : public nsTArray<E*> {
+template<class E, class Alloc=nsTArrayDefaultAllocator>
+class nsTPtrArray : public nsTArray<E*, Alloc> {
   public:
-    typedef nsTPtrArray<E> self_type;
-    typedef nsTArray<E*> base_type;
+  typedef nsTPtrArray<E, Alloc> self_type;
+  typedef nsTArray<E*, Alloc> base_type;
     typedef typename base_type::size_type size_type;
     typedef typename base_type::elem_type elem_type;
     typedef typename base_type::index_type index_type;
 
     //
     // Initialization methods
     //
 
@@ -89,28 +89,28 @@ class nsTPtrArray : public nsTArray<E*> 
     // a bounds safe manner. If the requested index is out of bounds null is
     // returned.
     // @param i  The index of an element in the array.
     elem_type SafeElementAt(index_type i) const {
       return SafeElementAt(i, nsnull);
     }
 };
 
-template<class E, PRUint32 N>
-class nsAutoTPtrArray : public nsTPtrArray<E> {
+template<class E, PRUint32 N, class Alloc=nsTArrayDefaultAllocator>
+class nsAutoTPtrArray : public nsTPtrArray<E, Alloc> {
   public:
-    typedef nsTPtrArray<E> base_type;
+    typedef nsTPtrArray<E, Alloc> base_type;
     typedef typename base_type::Header Header;
     typedef typename base_type::elem_type elem_type;
 
     nsAutoTPtrArray() {
-      base_type::mHdr = reinterpret_cast<Header*>(&mAutoBuf);
-      base_type::mHdr->mLength = 0;
-      base_type::mHdr->mCapacity = N;
-      base_type::mHdr->mIsAutoArray = 1;
+      *base_type::PtrToHdr() = reinterpret_cast<Header*>(&mAutoBuf);
+      base_type::Hdr()->mLength = 0;
+      base_type::Hdr()->mCapacity = N;
+      base_type::Hdr()->mIsAutoArray = 1;
 
       NS_ASSERTION(base_type::GetAutoArrayBuffer() ==
                    reinterpret_cast<Header*>(&mAutoBuf),
                    "GetAutoArrayBuffer needs to be fixed");
     }
 
   protected:
     union {