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