diff -r 000000000000 -r 6474c204b198 xpcom/glue/nsVoidArray.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/xpcom/glue/nsVoidArray.cpp	Wed Dec 31 06:09:35 2014 +0100
@@ -0,0 +1,1022 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0)) -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/MemoryReporting.h"
+#include <stdlib.h>
+
+#include "nsVoidArray.h"
+#include "nsQuickSort.h"
+#include "nsISupportsImpl.h" // for nsTraceRefcnt
+#include "nsAlgorithm.h"
+
+/**
+ * Grow the array by at least this many elements at a time.
+ */
+static const int32_t kMinGrowArrayBy = 8;
+static const int32_t kMaxGrowArrayBy = 1024;
+
+/**
+ * This is the threshold (in bytes) of the mImpl struct, past which
+ * we'll force the array to grow geometrically
+ */
+static const int32_t kLinearThreshold = 24 * sizeof(void *);
+
+/**
+ * Compute the number of bytes requires for the mImpl struct that will
+ * hold |n| elements.
+ */
+#define SIZEOF_IMPL(n_) (sizeof(Impl) + sizeof(void *) * ((n_) - 1))
+
+/**
+ * Compute the number of elements that an mImpl struct of |n| bytes
+ * will hold.
+ */
+#define CAPACITYOF_IMPL(n_) ((((n_) - sizeof(Impl)) / sizeof(void *)) + 1)
+
+#if DEBUG_VOIDARRAY
+#define MAXVOID 10
+
+class VoidStats {
+public:
+  VoidStats();
+  ~VoidStats();
+
+};
+
+static int sizesUsed; // number of the elements of the arrays used
+static int sizesAlloced[MAXVOID]; // sizes of the allocations.  sorted
+static int NumberOfSize[MAXVOID]; // number of this allocation size (1 per array)
+static int AllocedOfSize[MAXVOID]; // number of this allocation size (each size for array used)
+static int MaxAuto[MAXVOID];      // AutoArrays that maxed out at this size
+static int GrowInPlace[MAXVOID];  // arrays this size that grew in-place via realloc
+
+// these are per-allocation  
+static int MaxElements[2000];     // # of arrays that maxed out at each size.
+
+// statistics macros
+#define ADD_TO_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
+                                  { \
+                                    if (sizesAlloced[i] == (int)(size)) \
+                                    { ((x)[i])++; break; } \
+                                  } \
+                                  if (i >= sizesUsed && sizesUsed < MAXVOID) \
+                                  { sizesAlloced[sizesUsed] = (size); \
+                                    ((x)[sizesUsed++])++; break; \
+                                  } \
+                                } while (0)
+
+#define SUB_FROM_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
+                                    { \
+                                      if (sizesAlloced[i] == (int)(size)) \
+                                      { ((x)[i])--; break; } \
+                                    } \
+                                  } while (0)
+
+
+VoidStats::VoidStats()
+{
+  sizesUsed = 1;
+  sizesAlloced[0] = 0;
+}
+
+VoidStats::~VoidStats()
+{
+  int i;
+  for (i = 0; i < sizesUsed; i++)
+  {
+    printf("Size %d:\n",sizesAlloced[i]);
+    printf("\tNumber of VoidArrays this size (max):     %d\n",NumberOfSize[i]-MaxAuto[i]);
+    printf("\tNumber of AutoVoidArrays this size (max): %d\n",MaxAuto[i]);
+    printf("\tNumber of allocations this size (total):  %d\n",AllocedOfSize[i]);
+    printf("\tNumber of GrowsInPlace this size (total): %d\n",GrowInPlace[i]);
+  }
+  printf("Max Size of VoidArray:\n");
+  for (i = 0; i < (int)(sizeof(MaxElements)/sizeof(MaxElements[0])); i++)
+  {
+    if (MaxElements[i])
+      printf("\t%d: %d\n",i,MaxElements[i]);
+  }
+}
+
+// Just so constructor/destructor's get called
+VoidStats gVoidStats;
+#endif
+
+void
+nsVoidArray::SetArray(Impl *newImpl, int32_t aSize, int32_t aCount)
+{
+  // old mImpl has been realloced and so we don't free/delete it
+  NS_PRECONDITION(newImpl, "can't set size");
+  mImpl = newImpl;
+  mImpl->mCount = aCount;
+  mImpl->mSize = aSize;
+}
+
+// This does all allocation/reallocation of the array.
+// It also will compact down to N - good for things that might grow a lot
+// at times,  but usually are smaller, like JS deferred GC releases.
+bool nsVoidArray::SizeTo(int32_t aSize)
+{
+  uint32_t oldsize = GetArraySize();
+
+  if (aSize == (int32_t) oldsize)
+    return true; // no change
+
+  if (aSize <= 0)
+  {
+    // free the array if allocated
+    if (mImpl)
+    {
+      free(reinterpret_cast<char *>(mImpl));
+      mImpl = nullptr;
+    }
+    return true;
+  }
+
+  if (mImpl)
+  {
+    // We currently own an array impl. Resize it appropriately.
+    if (aSize < mImpl->mCount)
+    {
+      // XXX Note: we could also just resize to mCount
+      return true;  // can't make it that small, ignore request
+    }
+
+    char* bytes = (char *) realloc(mImpl,SIZEOF_IMPL(aSize));
+    Impl* newImpl = reinterpret_cast<Impl*>(bytes);
+    if (!newImpl)
+      return false;
+
+#if DEBUG_VOIDARRAY
+    if (mImpl == newImpl)
+      ADD_TO_STATS(GrowInPlace,oldsize);
+    ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
+    if (aSize > mMaxSize)
+    {
+      ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
+      if (oldsize)
+        SUB_FROM_STATS(NumberOfSize,oldsize);
+      mMaxSize = aSize;
+      if (mIsAuto)
+      {
+        ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
+        SUB_FROM_STATS(MaxAuto,oldsize);
+      }
+    }
+#endif
+    SetArray(newImpl, aSize, newImpl->mCount);
+    return true;
+  }
+
+  if ((uint32_t) aSize < oldsize) {
+    // No point in allocating if it won't free the current Impl anyway.
+    return true;
+  }
+
+  // just allocate an array
+  // allocate the exact size requested
+  char* bytes = (char *) malloc(SIZEOF_IMPL(aSize));
+  Impl* newImpl = reinterpret_cast<Impl*>(bytes);
+  if (!newImpl)
+    return false;
+
+#if DEBUG_VOIDARRAY
+  ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
+  if (aSize > mMaxSize)
+  {
+    ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
+    if (oldsize && !mImpl)
+      SUB_FROM_STATS(NumberOfSize,oldsize);
+    mMaxSize = aSize;
+  }
+#endif
+  if (mImpl)
+  {
+#if DEBUG_VOIDARRAY
+    ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
+    SUB_FROM_STATS(MaxAuto,0);
+    SUB_FROM_STATS(NumberOfSize,0);
+    mIsAuto = true;
+#endif
+    // We must be growing an nsAutoVoidArray - copy since we didn't
+    // realloc.
+    memcpy(newImpl->mArray, mImpl->mArray,
+                  mImpl->mCount * sizeof(mImpl->mArray[0]));
+  }
+
+  SetArray(newImpl, aSize, mImpl ? mImpl->mCount : 0);
+  // no memset; handled later in ReplaceElementAt if needed
+  return true;
+}
+
+bool nsVoidArray::GrowArrayBy(int32_t aGrowBy)
+{
+  // We have to grow the array. Grow by kMinGrowArrayBy slots if we're
+  // smaller than kLinearThreshold bytes, or a power of two if we're
+  // larger.  This is much more efficient with most memory allocators,
+  // especially if it's very large, or of the allocator is binned.
+  if (aGrowBy < kMinGrowArrayBy)
+    aGrowBy = kMinGrowArrayBy;
+
+  uint32_t newCapacity = GetArraySize() + aGrowBy;  // Minimum increase
+  uint32_t newSize = SIZEOF_IMPL(newCapacity);
+
+  if (newSize >= (uint32_t) kLinearThreshold)
+  {
+    // newCount includes enough space for at least kMinGrowArrayBy new
+    // slots. Select the next power-of-two size in bytes above or
+    // equal to that.
+    // Also, limit the increase in size to about a VM page or two.
+    if (GetArraySize() >= kMaxGrowArrayBy)
+    {
+      newCapacity = GetArraySize() + XPCOM_MAX(kMaxGrowArrayBy,aGrowBy);
+      newSize = SIZEOF_IMPL(newCapacity);
+    }
+    else
+    {
+      newSize = mozilla::CeilingLog2(newSize);
+      newCapacity = CAPACITYOF_IMPL(1u << newSize);
+    }
+  }
+  // frees old mImpl IF this succeeds
+  if (!SizeTo(newCapacity))
+    return false;
+
+  return true;
+}
+
+nsVoidArray::nsVoidArray()
+  : mImpl(nullptr)
+{
+  MOZ_COUNT_CTOR(nsVoidArray);
+#if DEBUG_VOIDARRAY
+  mMaxCount = 0;
+  mMaxSize = 0;
+  mIsAuto = false;
+  ADD_TO_STATS(NumberOfSize,0);
+  MaxElements[0]++;
+#endif
+}
+
+nsVoidArray::nsVoidArray(int32_t aCount)
+  : mImpl(nullptr)
+{
+  MOZ_COUNT_CTOR(nsVoidArray);
+#if DEBUG_VOIDARRAY
+  mMaxCount = 0;
+  mMaxSize = 0;
+  mIsAuto = false;
+  MaxElements[0]++;
+#endif
+  SizeTo(aCount);
+}
+
+nsVoidArray& nsVoidArray::operator=(const nsVoidArray& other)
+{
+  int32_t otherCount = other.Count();
+  int32_t maxCount = GetArraySize();
+  if (otherCount)
+  {
+    if (otherCount > maxCount)
+    {
+      // frees old mImpl IF this succeeds
+      if (!GrowArrayBy(otherCount-maxCount))
+        return *this;      // XXX The allocation failed - don't do anything
+
+      memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
+      mImpl->mCount = otherCount;
+    }
+    else
+    {
+      // the old array can hold the new array
+      memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
+      mImpl->mCount = otherCount;
+      // if it shrank a lot, compact it anyways
+      if ((otherCount*2) < maxCount && maxCount > 100)
+      {
+        Compact();  // shrank by at least 50 entries
+      }
+    }
+#if DEBUG_VOIDARRAY
+     if (mImpl->mCount > mMaxCount &&
+         mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
+     {
+       MaxElements[mImpl->mCount]++;
+       MaxElements[mMaxCount]--;
+       mMaxCount = mImpl->mCount;
+     }
+#endif
+  }
+  else
+  {
+    // Why do we drop the buffer here when we don't in Clear()?
+    SizeTo(0);
+  }
+
+  return *this;
+}
+
+nsVoidArray::~nsVoidArray()
+{
+  MOZ_COUNT_DTOR(nsVoidArray);
+  if (mImpl)
+    free(reinterpret_cast<char*>(mImpl));
+}
+
+bool nsVoidArray::SetCount(int32_t aNewCount)
+{
+  NS_ASSERTION(aNewCount >= 0,"SetCount(negative index)");
+  if (aNewCount < 0)
+    return false;
+
+  if (aNewCount == 0)
+  {
+    Clear();
+    return true;
+  }
+
+  if (uint32_t(aNewCount) > uint32_t(GetArraySize()))
+  {
+    int32_t oldCount = Count();
+    int32_t growDelta = aNewCount - oldCount;
+
+    // frees old mImpl IF this succeeds
+    if (!GrowArrayBy(growDelta))
+      return false;
+  }
+
+  if (aNewCount > mImpl->mCount)
+  {
+    // Make sure that new entries added to the array by this
+    // SetCount are cleared to 0.  Some users of this assume that.
+    // This code means we don't have to memset when we allocate an array.
+    memset(&mImpl->mArray[mImpl->mCount], 0,
+           (aNewCount - mImpl->mCount) * sizeof(mImpl->mArray[0]));
+  }
+
+  mImpl->mCount = aNewCount;
+
+#if DEBUG_VOIDARRAY
+  if (mImpl->mCount > mMaxCount &&
+      mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
+  {
+    MaxElements[mImpl->mCount]++;
+    MaxElements[mMaxCount]--;
+    mMaxCount = mImpl->mCount;
+  }
+#endif
+
+  return true;
+}
+
+int32_t nsVoidArray::IndexOf(void* aPossibleElement) const
+{
+  if (mImpl)
+  {
+    void** ap = mImpl->mArray;
+    void** end = ap + mImpl->mCount;
+    while (ap < end)
+    {
+      if (*ap == aPossibleElement)
+      {
+        return ap - mImpl->mArray;
+      }
+      ap++;
+    }
+  }
+  return -1;
+}
+
+bool nsVoidArray::InsertElementAt(void* aElement, int32_t aIndex)
+{
+  int32_t oldCount = Count();
+  NS_ASSERTION(aIndex >= 0,"InsertElementAt(negative index)");
+  if (uint32_t(aIndex) > uint32_t(oldCount))
+  {
+    // An invalid index causes the insertion to fail
+    // Invalid indexes are ones that add more than one entry to the
+    // array (i.e., they can append).
+    return false;
+  }
+
+  if (oldCount >= GetArraySize())
+  {
+    if (!GrowArrayBy(1))
+      return false;
+  }
+  // else the array is already large enough
+
+  int32_t slide = oldCount - aIndex;
+  if (0 != slide)
+  {
+    // Slide data over to make room for the insertion
+    memmove(mImpl->mArray + aIndex + 1, mImpl->mArray + aIndex,
+            slide * sizeof(mImpl->mArray[0]));
+  }
+
+  mImpl->mArray[aIndex] = aElement;
+  mImpl->mCount++;
+
+#if DEBUG_VOIDARRAY
+  if (mImpl->mCount > mMaxCount &&
+      mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
+  {
+    MaxElements[mImpl->mCount]++;
+    MaxElements[mMaxCount]--;
+    mMaxCount = mImpl->mCount;
+  }
+#endif
+
+  return true;
+}
+
+bool nsVoidArray::InsertElementsAt(const nsVoidArray& other, int32_t aIndex)
+{
+  int32_t oldCount = Count();
+  int32_t otherCount = other.Count();
+
+  NS_ASSERTION(aIndex >= 0,"InsertElementsAt(negative index)");
+  if (uint32_t(aIndex) > uint32_t(oldCount))
+  {
+    // An invalid index causes the insertion to fail
+    // Invalid indexes are ones that are more than one entry past the end of
+    // the array (i.e., they can append).
+    return false;
+  }
+
+  if (oldCount + otherCount > GetArraySize())
+  {
+    if (!GrowArrayBy(otherCount))
+      return false;;
+  }
+  // else the array is already large enough
+
+  int32_t slide = oldCount - aIndex;
+  if (0 != slide)
+  {
+    // Slide data over to make room for the insertion
+    memmove(mImpl->mArray + aIndex + otherCount, mImpl->mArray + aIndex,
+            slide * sizeof(mImpl->mArray[0]));
+  }
+
+  for (int32_t i = 0; i < otherCount; i++)
+  {
+    // copy all the elements (destroys aIndex)
+    mImpl->mArray[aIndex++] = other.mImpl->mArray[i];
+    mImpl->mCount++;
+  }
+
+#if DEBUG_VOIDARRAY
+  if (mImpl->mCount > mMaxCount &&
+      mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
+  {
+    MaxElements[mImpl->mCount]++;
+    MaxElements[mMaxCount]--;
+    mMaxCount = mImpl->mCount;
+  }
+#endif
+
+  return true;
+}
+
+bool nsVoidArray::ReplaceElementAt(void* aElement, int32_t aIndex)
+{
+  NS_ASSERTION(aIndex >= 0,"ReplaceElementAt(negative index)");
+  if (aIndex < 0)
+    return false;
+
+  // Unlike InsertElementAt, ReplaceElementAt can implicitly add more
+  // than just the one element to the array.
+  if (uint32_t(aIndex) >= uint32_t(GetArraySize()))
+  {
+    int32_t oldCount = Count();
+    int32_t requestedCount = aIndex + 1;
+    int32_t growDelta = requestedCount - oldCount;
+
+    // frees old mImpl IF this succeeds
+    if (!GrowArrayBy(growDelta))
+      return false;
+  }
+
+  mImpl->mArray[aIndex] = aElement;
+  if (aIndex >= mImpl->mCount)
+  {
+    // Make sure that any entries implicitly added to the array by this
+    // ReplaceElementAt are cleared to 0.  Some users of this assume that.
+    // This code means we don't have to memset when we allocate an array.
+    if (aIndex > mImpl->mCount) // note: not >=
+    {
+      // For example, if mCount is 2, and we do a ReplaceElementAt for
+      // element[5], then we need to set three entries ([2], [3], and [4])
+      // to 0.
+      memset(&mImpl->mArray[mImpl->mCount], 0,
+             (aIndex - mImpl->mCount) * sizeof(mImpl->mArray[0]));
+    }
+    
+     mImpl->mCount = aIndex + 1;
+
+#if DEBUG_VOIDARRAY
+     if (mImpl->mCount > mMaxCount &&
+         mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
+     {
+       MaxElements[mImpl->mCount]++;
+       MaxElements[mMaxCount]--;
+       mMaxCount = mImpl->mCount;
+     }
+#endif
+  }
+
+  return true;
+}
+
+// useful for doing LRU arrays
+bool nsVoidArray::MoveElement(int32_t aFrom, int32_t aTo)
+{
+  void *tempElement;
+
+  if (aTo == aFrom)
+    return true;
+
+  NS_ASSERTION(aTo >= 0 && aFrom >= 0,"MoveElement(negative index)");
+  if (aTo >= Count() || aFrom >= Count())
+  {
+    // can't extend the array when moving an element.  Also catches mImpl = null
+    return false;
+  }
+  tempElement = mImpl->mArray[aFrom];
+
+  if (aTo < aFrom)
+  {
+    // Moving one element closer to the head; the elements inbetween move down
+    memmove(mImpl->mArray + aTo + 1, mImpl->mArray + aTo,
+            (aFrom-aTo) * sizeof(mImpl->mArray[0]));
+    mImpl->mArray[aTo] = tempElement;
+  }
+  else // already handled aFrom == aTo
+  {
+    // Moving one element closer to the tail; the elements inbetween move up
+    memmove(mImpl->mArray + aFrom, mImpl->mArray + aFrom + 1,
+            (aTo-aFrom) * sizeof(mImpl->mArray[0]));
+    mImpl->mArray[aTo] = tempElement;
+  }
+
+  return true;
+}
+
+void nsVoidArray::RemoveElementsAt(int32_t aIndex, int32_t aCount)
+{
+  int32_t oldCount = Count();
+  NS_ASSERTION(aIndex >= 0,"RemoveElementsAt(negative index)");
+  if (uint32_t(aIndex) >= uint32_t(oldCount))
+  {
+    return;
+  }
+  // Limit to available entries starting at aIndex
+  if (aCount + aIndex > oldCount)
+    aCount = oldCount - aIndex;
+
+  // We don't need to move any elements if we're removing the
+  // last element in the array
+  if (aIndex < (oldCount - aCount))
+  {
+    memmove(mImpl->mArray + aIndex, mImpl->mArray + aIndex + aCount,
+            (oldCount - (aIndex + aCount)) * sizeof(mImpl->mArray[0]));
+  }
+
+  mImpl->mCount -= aCount;
+  return;
+}
+
+bool nsVoidArray::RemoveElement(void* aElement)
+{
+  int32_t theIndex = IndexOf(aElement);
+  if (theIndex != -1)
+  {
+    RemoveElementAt(theIndex);
+    return true;
+  }
+
+  return false;
+}
+
+void nsVoidArray::Clear()
+{
+  if (mImpl)
+  {
+    mImpl->mCount = 0;
+  }
+}
+
+void nsVoidArray::Compact()
+{
+  if (mImpl)
+  {
+    // XXX NOTE: this is quite inefficient in many cases if we're only
+    // compacting by a little, but some callers care more about memory use.
+    int32_t count = Count();
+    if (GetArraySize() > count)
+    {
+      SizeTo(Count());
+    }
+  }
+}
+
+// Needed because we want to pass the pointer to the item in the array
+// to the comparator function, not a pointer to the pointer in the array.
+struct VoidArrayComparatorContext {
+  nsVoidArrayComparatorFunc mComparatorFunc;
+  void* mData;
+};
+
+static int
+VoidArrayComparator(const void* aElement1, const void* aElement2, void* aData)
+{
+  VoidArrayComparatorContext* ctx = static_cast<VoidArrayComparatorContext*>(aData);
+  return (*ctx->mComparatorFunc)(*static_cast<void* const*>(aElement1),
+                                 *static_cast<void* const*>(aElement2),
+                                  ctx->mData);
+}
+
+void nsVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
+{
+  if (mImpl && mImpl->mCount > 1)
+  {
+    VoidArrayComparatorContext ctx = {aFunc, aData};
+    NS_QuickSort(mImpl->mArray, mImpl->mCount, sizeof(mImpl->mArray[0]),
+                 VoidArrayComparator, &ctx);
+  }
+}
+
+bool nsVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
+{
+  int32_t index = -1;
+  bool    running = true;
+
+  if (mImpl) {
+    while (running && (++index < mImpl->mCount)) {
+      running = (*aFunc)(mImpl->mArray[index], aData);
+    }
+  }
+  return running;
+}
+
+bool nsVoidArray::EnumerateForwards(nsVoidArrayEnumFuncConst aFunc,
+                                    void* aData) const
+{
+  int32_t index = -1;
+  bool    running = true;
+
+  if (mImpl) {
+    while (running && (++index < mImpl->mCount)) {
+      running = (*aFunc)(mImpl->mArray[index], aData);
+    }
+  }
+  return running;
+}
+
+bool nsVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
+{
+  bool    running = true;
+
+  if (mImpl)
+  {
+    int32_t index = Count();
+    while (running && (0 <= --index))
+    {
+      running = (*aFunc)(mImpl->mArray[index], aData);
+    }
+  }
+  return running;
+}
+
+struct SizeOfElementIncludingThisData
+{
+  size_t mSize;
+  nsVoidArraySizeOfElementIncludingThisFunc mSizeOfElementIncludingThis;
+  mozilla::MallocSizeOf mMallocSizeOf;
+  void *mData;      // the arg passed by the user
+};
+
+static bool
+SizeOfElementIncludingThisEnumerator(const void *aElement, void *aData)
+{
+  SizeOfElementIncludingThisData *d = (SizeOfElementIncludingThisData *)aData;
+  d->mSize += d->mSizeOfElementIncludingThis(aElement, d->mMallocSizeOf, d->mData);
+  return true;
+}
+
+size_t
+nsVoidArray::SizeOfExcludingThis(
+  nsVoidArraySizeOfElementIncludingThisFunc aSizeOfElementIncludingThis,
+  mozilla::MallocSizeOf aMallocSizeOf, void* aData) const
+{
+  size_t n = 0;
+  // Measure the element storage.
+  if (mImpl) {
+    n += aMallocSizeOf(mImpl);
+  }
+  // Measure things pointed to by the elements.
+  if (aSizeOfElementIncludingThis) { 
+    SizeOfElementIncludingThisData data2 =
+      { 0, aSizeOfElementIncludingThis, aMallocSizeOf, aData };
+    EnumerateForwards(SizeOfElementIncludingThisEnumerator, &data2);
+    n += data2.mSize;
+  }
+  return n;
+}
+
+//----------------------------------------------------------------------
+// NOTE: nsSmallVoidArray elements MUST all have the low bit as 0.
+// This means that normally it's only used for pointers, and in particular
+// structures or objects.
+nsSmallVoidArray::~nsSmallVoidArray()
+{
+  if (HasSingle())
+  {
+    // Have to null out mImpl before the nsVoidArray dtor runs.
+    mImpl = nullptr;
+  }
+}
+
+nsSmallVoidArray& 
+nsSmallVoidArray::operator=(nsSmallVoidArray& other)
+{
+  int32_t count = other.Count();
+  switch (count) {
+    case 0:
+      Clear();
+      break;
+    case 1:
+      Clear();
+      AppendElement(other.ElementAt(0));
+      break;
+    default:
+      if (GetArraySize() >= count || SizeTo(count)) {
+        *AsArray() = *other.AsArray();
+      }
+  }
+    
+  return *this;
+}
+
+int32_t
+nsSmallVoidArray::GetArraySize() const
+{
+  if (HasSingle()) {
+    return 1;
+  }
+
+  return AsArray()->GetArraySize();
+}
+
+int32_t
+nsSmallVoidArray::Count() const
+{
+  if (HasSingle()) {
+    return 1;
+  }
+
+  return AsArray()->Count();
+}
+
+void*
+nsSmallVoidArray::FastElementAt(int32_t aIndex) const
+{
+  NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::FastElementAt: index out of range");
+
+  if (HasSingle()) {
+    return GetSingle();
+  }
+
+  return AsArray()->FastElementAt(aIndex);
+}
+
+int32_t
+nsSmallVoidArray::IndexOf(void* aPossibleElement) const
+{
+  if (HasSingle()) {
+    return aPossibleElement == GetSingle() ? 0 : -1;
+  }
+
+  return AsArray()->IndexOf(aPossibleElement);
+}
+
+bool
+nsSmallVoidArray::InsertElementAt(void* aElement, int32_t aIndex)
+{
+  NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
+               "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
+
+  if (aIndex == 0 && IsEmpty()) {
+    SetSingle(aElement);
+
+    return true;
+  }
+
+  if (!EnsureArray()) {
+    return false;
+  }
+
+  return AsArray()->InsertElementAt(aElement, aIndex);
+}
+
+bool nsSmallVoidArray::InsertElementsAt(const nsVoidArray &aOther, int32_t aIndex)
+{
+#ifdef DEBUG  
+  for (int i = 0; i < aOther.Count(); i++) {
+    NS_ASSERTION(!(NS_PTR_TO_INT32(aOther.ElementAt(i)) & 0x1),
+                 "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
+  }
+#endif
+
+  if (aIndex == 0 && IsEmpty() && aOther.Count() == 1) {
+    SetSingle(aOther.FastElementAt(0));
+    
+    return true;
+  }
+
+  if (!EnsureArray()) {
+    return false;
+  }
+
+  return AsArray()->InsertElementsAt(aOther, aIndex);
+}
+
+bool
+nsSmallVoidArray::ReplaceElementAt(void* aElement, int32_t aIndex)
+{
+  NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
+               "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
+
+  if (aIndex == 0 && (IsEmpty() || HasSingle())) {
+    SetSingle(aElement);
+    
+    return true;
+  }
+
+  if (!EnsureArray()) {
+    return false;
+  }
+
+  return AsArray()->ReplaceElementAt(aElement, aIndex);
+}
+
+bool
+nsSmallVoidArray::AppendElement(void* aElement)
+{
+  NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
+               "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
+
+  if (IsEmpty()) {
+    SetSingle(aElement);
+    
+    return true;
+  }
+
+  if (!EnsureArray()) {
+    return false;
+  }
+
+  return AsArray()->AppendElement(aElement);
+}
+
+bool
+nsSmallVoidArray::RemoveElement(void* aElement)
+{
+  if (HasSingle()) {
+    if (aElement == GetSingle()) {
+      mImpl = nullptr;
+      return true;
+    }
+    
+    return false;
+  }
+
+  return AsArray()->RemoveElement(aElement);
+}
+
+void
+nsSmallVoidArray::RemoveElementAt(int32_t aIndex)
+{
+  if (HasSingle()) {
+    if (aIndex == 0) {
+      mImpl = nullptr;
+    }
+    
+    return;
+  }
+
+  AsArray()->RemoveElementAt(aIndex);
+}
+
+void
+nsSmallVoidArray::RemoveElementsAt(int32_t aIndex, int32_t aCount)
+{
+  if (HasSingle()) {
+    if (aIndex == 0) {
+      if (aCount > 0) {
+        mImpl = nullptr;
+      }
+    }
+
+    return;
+  }
+
+  AsArray()->RemoveElementsAt(aIndex, aCount);
+}
+
+void
+nsSmallVoidArray::Clear()
+{
+  if (HasSingle()) {
+    mImpl = nullptr;
+  }
+  else {
+    AsArray()->Clear();
+  }
+}
+
+bool
+nsSmallVoidArray::SizeTo(int32_t aMin)
+{
+  if (!HasSingle()) {
+    return AsArray()->SizeTo(aMin);
+  }
+
+  if (aMin <= 0) {
+    mImpl = nullptr;
+
+    return true;
+  }
+
+  if (aMin == 1) {
+    return true;
+  }
+
+  void* single = GetSingle();
+  mImpl = nullptr;
+  if (!AsArray()->SizeTo(aMin)) {
+    SetSingle(single);
+
+    return false;
+  }
+
+  AsArray()->AppendElement(single);
+
+  return true;
+}
+
+void
+nsSmallVoidArray::Compact()
+{
+  if (!HasSingle()) {
+    AsArray()->Compact();
+  }
+}
+
+void
+nsSmallVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
+{
+  if (!HasSingle()) {
+    AsArray()->Sort(aFunc,aData);
+  }
+}
+
+bool
+nsSmallVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
+{
+  if (HasSingle()) {
+    return (*aFunc)(GetSingle(), aData);
+  }
+  return AsArray()->EnumerateForwards(aFunc,aData);
+}
+
+bool
+nsSmallVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
+{
+  if (HasSingle()) {
+    return (*aFunc)(GetSingle(), aData);
+  }
+  return AsArray()->EnumerateBackwards(aFunc,aData);
+}
+
+bool
+nsSmallVoidArray::EnsureArray()
+{
+  if (!HasSingle()) {
+    return true;
+  }
+
+  void* single = GetSingle();
+  mImpl = nullptr;
+  if (!AsArray()->AppendElement(single)) {
+    SetSingle(single);
+
+    return false;
+  }
+
+  return true;
+}