Back to index

lightning-sunbird  0.9+nobinonly
nsVoidArray.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0)) -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either of the GNU General Public License Version 2 or later (the "GPL"),
00026  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 #include "nsVoidArray.h"
00038 #include "nsQuickSort.h"
00039 #include "prmem.h"
00040 #include "nsCRT.h"
00041 #include "nsString.h"
00042 #include "prbit.h"
00043 
00047 static const PRInt32 kMinGrowArrayBy = 8;
00048 static const PRInt32 kMaxGrowArrayBy = 1024;
00049 
00054 static const PRInt32 kLinearThreshold = 24 * sizeof(void *);
00055 
00060 #define SIZEOF_IMPL(n_) (sizeof(Impl) + sizeof(void *) * ((n_) - 1))
00061 
00062 
00067 #define CAPACITYOF_IMPL(n_) ((((n_) - sizeof(Impl)) / sizeof(void *)) + 1)
00068 
00069 #if DEBUG_VOIDARRAY
00070 #define MAXVOID 10
00071 
00072 class VoidStats {
00073 public:
00074   VoidStats();
00075   ~VoidStats();
00076 
00077 };
00078 
00079 static int sizesUsed; // number of the elements of the arrays used
00080 static int sizesAlloced[MAXVOID]; // sizes of the allocations.  sorted
00081 static int NumberOfSize[MAXVOID]; // number of this allocation size (1 per array)
00082 static int AllocedOfSize[MAXVOID]; // number of this allocation size (each size for array used)
00083 static int MaxAuto[MAXVOID];      // AutoArrays that maxed out at this size
00084 static int GrowInPlace[MAXVOID];  // arrays this size that grew in-place via realloc
00085 
00086 // these are per-allocation  
00087 static int MaxElements[2000];     // # of arrays that maxed out at each size.
00088 
00089 // statistics macros
00090 #define ADD_TO_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
00091                                   { \
00092                                     if (sizesAlloced[i] == (int)(size)) \
00093                                     { ((x)[i])++; break; } \
00094                                   } \
00095                                   if (i >= sizesUsed && sizesUsed < MAXVOID) \
00096                                   { sizesAlloced[sizesUsed] = (size); \
00097                                     ((x)[sizesUsed++])++; break; \
00098                                   } \
00099                                 } while (0)
00100 
00101 #define SUB_FROM_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
00102                                     { \
00103                                       if (sizesAlloced[i] == (int)(size)) \
00104                                       { ((x)[i])--; break; } \
00105                                     } \
00106                                   } while (0)
00107 
00108 
00109 VoidStats::VoidStats()
00110 {
00111   sizesUsed = 1;
00112   sizesAlloced[0] = 0;
00113 }
00114 
00115 VoidStats::~VoidStats()
00116 {
00117   int i;
00118   for (i = 0; i < sizesUsed; i++)
00119   {
00120     printf("Size %d:\n",sizesAlloced[i]);
00121     printf("\tNumber of VoidArrays this size (max):     %d\n",NumberOfSize[i]-MaxAuto[i]);
00122     printf("\tNumber of AutoVoidArrays this size (max): %d\n",MaxAuto[i]);
00123     printf("\tNumber of allocations this size (total):  %d\n",AllocedOfSize[i]);
00124     printf("\tNumber of GrowsInPlace this size (total): %d\n",GrowInPlace[i]);
00125   }
00126   printf("Max Size of VoidArray:\n");
00127   for (i = 0; i < (int)(sizeof(MaxElements)/sizeof(MaxElements[0])); i++)
00128   {
00129     if (MaxElements[i])
00130       printf("\t%d: %d\n",i,MaxElements[i]);
00131   }
00132 }
00133 
00134 // Just so constructor/destructor's get called
00135 VoidStats gVoidStats;
00136 #endif
00137 
00138 inline void
00139 nsVoidArray::SetArray(Impl *newImpl, PRInt32 aSize, PRInt32 aCount, PRBool owner)
00140 {
00141   // old mImpl has been realloced and so we don't free/delete it
00142   NS_PRECONDITION(newImpl, "can't set size");
00143   mImpl = newImpl;
00144   mImpl->mCount = aCount;
00145   mImpl->mBits = PRUint32(aSize & kArraySizeMask) |
00146                  (owner ? kArrayOwnerMask : 0);
00147 }
00148 
00149 // This does all allocation/reallocation of the array.
00150 // It also will compact down to N - good for things that might grow a lot
00151 // at times,  but usually are smaller, like JS deferred GC releases.
00152 PRBool nsVoidArray::SizeTo(PRInt32 aSize)
00153 {
00154   PRUint32 oldsize = GetArraySize();
00155 
00156   if (aSize == (PRInt32) oldsize)
00157     return PR_TRUE; // no change
00158 
00159   if (aSize <= 0)
00160   {
00161     // free the array if allocated
00162     if (mImpl)
00163     {
00164       if (IsArrayOwner())
00165       {
00166         PR_Free(NS_REINTERPRET_CAST(char *, mImpl));
00167         mImpl = nsnull;
00168       }
00169       else
00170       {
00171         mImpl->mCount = 0; // nsAutoVoidArray
00172       }
00173     }
00174     return PR_TRUE;
00175   }
00176 
00177   if (mImpl && IsArrayOwner())
00178   {
00179     // We currently own an array impl. Resize it appropriately.
00180     if (aSize < mImpl->mCount)
00181     {
00182       // XXX Note: we could also just resize to mCount
00183       return PR_TRUE;  // can't make it that small, ignore request
00184     }
00185 
00186     char* bytes = (char *) PR_Realloc(mImpl,SIZEOF_IMPL(aSize));
00187     Impl* newImpl = NS_REINTERPRET_CAST(Impl*, bytes);
00188     if (!newImpl)
00189       return PR_FALSE;
00190 
00191 #if DEBUG_VOIDARRAY
00192     if (mImpl == newImpl)
00193       ADD_TO_STATS(GrowInPlace,oldsize);
00194     ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
00195     if (aSize > mMaxSize)
00196     {
00197       ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
00198       if (oldsize)
00199         SUB_FROM_STATS(NumberOfSize,oldsize);
00200       mMaxSize = aSize;
00201       if (mIsAuto)
00202       {
00203         ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
00204         SUB_FROM_STATS(MaxAuto,oldsize);
00205       }
00206     }
00207 #endif
00208     SetArray(newImpl,aSize,newImpl->mCount,PR_TRUE);
00209     return PR_TRUE;
00210   }
00211 
00212   // just allocate an array
00213   // allocate the exact size requested
00214   char* bytes = (char *) PR_Malloc(SIZEOF_IMPL(aSize));
00215   Impl* newImpl = NS_REINTERPRET_CAST(Impl*, bytes);
00216   if (!newImpl)
00217     return PR_FALSE;
00218 
00219 #if DEBUG_VOIDARRAY
00220   ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
00221   if (aSize > mMaxSize)
00222   {
00223     ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
00224     if (oldsize && !mImpl)
00225       SUB_FROM_STATS(NumberOfSize,oldsize);
00226     mMaxSize = aSize;
00227   }
00228 #endif
00229   if (mImpl)
00230   {
00231 #if DEBUG_VOIDARRAY
00232     ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
00233     SUB_FROM_STATS(MaxAuto,0);
00234     SUB_FROM_STATS(NumberOfSize,0);
00235     mIsAuto = PR_TRUE;
00236 #endif
00237     // We must be growing an nsAutoVoidArray - copy since we didn't
00238     // realloc.
00239     memcpy(newImpl->mArray, mImpl->mArray,
00240                   mImpl->mCount * sizeof(mImpl->mArray[0]));
00241   }
00242     
00243   SetArray(newImpl,aSize,mImpl ? mImpl->mCount : 0,PR_TRUE);
00244   // no memset; handled later in ReplaceElementAt if needed
00245   return PR_TRUE;
00246 }
00247 
00248 PRBool nsVoidArray::GrowArrayBy(PRInt32 aGrowBy)
00249 {
00250   // We have to grow the array. Grow by kMinGrowArrayBy slots if we're
00251   // smaller than kLinearThreshold bytes, or a power of two if we're
00252   // larger.  This is much more efficient with most memory allocators,
00253   // especially if it's very large, or of the allocator is binned.
00254   if (aGrowBy < kMinGrowArrayBy)
00255     aGrowBy = kMinGrowArrayBy;
00256 
00257   PRUint32 newCapacity = GetArraySize() + aGrowBy;  // Minimum increase
00258   PRUint32 newSize = SIZEOF_IMPL(newCapacity);
00259 
00260   if (newSize >= (PRUint32) kLinearThreshold)
00261   {
00262     // newCount includes enough space for at least kMinGrowArrayBy new
00263     // slots. Select the next power-of-two size in bytes above or
00264     // equal to that.
00265     // Also, limit the increase in size to about a VM page or two.
00266     if (GetArraySize() >= kMaxGrowArrayBy)
00267     {
00268       newCapacity = GetArraySize() + PR_MAX(kMaxGrowArrayBy,aGrowBy);
00269       newSize = SIZEOF_IMPL(newCapacity);
00270     }
00271     else
00272     {
00273       newSize = PR_BIT(PR_CeilingLog2(newSize));
00274       newCapacity = CAPACITYOF_IMPL(newSize);
00275     }
00276   }
00277   // frees old mImpl IF this succeeds
00278   if (!SizeTo(newCapacity))
00279     return PR_FALSE;
00280 
00281   return PR_TRUE;
00282 }
00283 
00284 nsVoidArray::nsVoidArray()
00285   : mImpl(nsnull)
00286 {
00287   MOZ_COUNT_CTOR(nsVoidArray);
00288 #if DEBUG_VOIDARRAY
00289   mMaxCount = 0;
00290   mMaxSize = 0;
00291   mIsAuto = PR_FALSE;
00292   ADD_TO_STATS(NumberOfSize,0);
00293   MaxElements[0]++;
00294 #endif
00295 }
00296 
00297 nsVoidArray::nsVoidArray(PRInt32 aCount)
00298   : mImpl(nsnull)
00299 {
00300   MOZ_COUNT_CTOR(nsVoidArray);
00301 #if DEBUG_VOIDARRAY
00302   mMaxCount = 0;
00303   mMaxSize = 0;
00304   mIsAuto = PR_FALSE;
00305   MaxElements[0]++;
00306 #endif
00307   SizeTo(aCount);
00308 }
00309 
00310 nsVoidArray& nsVoidArray::operator=(const nsVoidArray& other)
00311 {
00312   PRInt32 otherCount = other.Count();
00313   PRInt32 maxCount = GetArraySize();
00314   if (otherCount)
00315   {
00316     if (otherCount > maxCount)
00317     {
00318       // frees old mImpl IF this succeeds
00319       if (!GrowArrayBy(otherCount-maxCount))
00320         return *this;      // XXX The allocation failed - don't do anything
00321 
00322       memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
00323       mImpl->mCount = otherCount;
00324     }
00325     else
00326     {
00327       // the old array can hold the new array
00328       memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
00329       mImpl->mCount = otherCount;
00330       // if it shrank a lot, compact it anyways
00331       if ((otherCount*2) < maxCount && maxCount > 100)
00332       {
00333         Compact();  // shrank by at least 50 entries
00334       }
00335     }
00336 #if DEBUG_VOIDARRAY
00337      if (mImpl->mCount > mMaxCount &&
00338          mImpl->mCount < (PRInt32)(sizeof(MaxElements)/sizeof(MaxElements[0])))
00339      {
00340        MaxElements[mImpl->mCount]++;
00341        MaxElements[mMaxCount]--;
00342        mMaxCount = mImpl->mCount;
00343      }
00344 #endif
00345   }
00346   else
00347   {
00348     if (mImpl && IsArrayOwner())
00349       PR_Free(NS_REINTERPRET_CAST(char*, mImpl));
00350 
00351     mImpl = nsnull;
00352   }
00353 
00354   return *this;
00355 }
00356 
00357 nsVoidArray::~nsVoidArray()
00358 {
00359   MOZ_COUNT_DTOR(nsVoidArray);
00360   if (mImpl && IsArrayOwner())
00361     PR_Free(NS_REINTERPRET_CAST(char*, mImpl));
00362 }
00363 
00364 PRInt32 nsVoidArray::IndexOf(void* aPossibleElement) const
00365 {
00366   if (mImpl)
00367   {
00368     void** ap = mImpl->mArray;
00369     void** end = ap + mImpl->mCount;
00370     while (ap < end)
00371     {
00372       if (*ap == aPossibleElement)
00373       {
00374         return ap - mImpl->mArray;
00375       }
00376       ap++;
00377     }
00378   }
00379   return -1;
00380 }
00381 
00382 PRBool nsVoidArray::InsertElementAt(void* aElement, PRInt32 aIndex)
00383 {
00384   PRInt32 oldCount = Count();
00385   NS_ASSERTION(aIndex >= 0,"InsertElementAt(negative index)");
00386   if (PRUint32(aIndex) > PRUint32(oldCount))
00387   {
00388     // An invalid index causes the insertion to fail
00389     // Invalid indexes are ones that add more than one entry to the
00390     // array (i.e., they can append).
00391     return PR_FALSE;
00392   }
00393 
00394   if (oldCount >= GetArraySize())
00395   {
00396     if (!GrowArrayBy(1))
00397       return PR_FALSE;
00398   }
00399   // else the array is already large enough
00400 
00401   PRInt32 slide = oldCount - aIndex;
00402   if (0 != slide)
00403   {
00404     // Slide data over to make room for the insertion
00405     memmove(mImpl->mArray + aIndex + 1, mImpl->mArray + aIndex,
00406             slide * sizeof(mImpl->mArray[0]));
00407   }
00408 
00409   mImpl->mArray[aIndex] = aElement;
00410   mImpl->mCount++;
00411 
00412 #if DEBUG_VOIDARRAY
00413   if (mImpl->mCount > mMaxCount &&
00414       mImpl->mCount < (PRInt32)(sizeof(MaxElements)/sizeof(MaxElements[0])))
00415   {
00416     MaxElements[mImpl->mCount]++;
00417     MaxElements[mMaxCount]--;
00418     mMaxCount = mImpl->mCount;
00419   }
00420 #endif
00421 
00422   return PR_TRUE;
00423 }
00424 
00425 PRBool nsVoidArray::InsertElementsAt(const nsVoidArray& other, PRInt32 aIndex)
00426 {
00427   PRInt32 oldCount = Count();
00428   PRInt32 otherCount = other.Count();
00429 
00430   NS_ASSERTION(aIndex >= 0,"InsertElementsAt(negative index)");
00431   if (PRUint32(aIndex) > PRUint32(oldCount))
00432   {
00433     // An invalid index causes the insertion to fail
00434     // Invalid indexes are ones that are more than one entry past the end of
00435     // the array (i.e., they can append).
00436     return PR_FALSE;
00437   }
00438 
00439   if (oldCount + otherCount > GetArraySize())
00440   {
00441     if (!GrowArrayBy(otherCount))
00442       return PR_FALSE;;
00443   }
00444   // else the array is already large enough
00445 
00446   PRInt32 slide = oldCount - aIndex;
00447   if (0 != slide)
00448   {
00449     // Slide data over to make room for the insertion
00450     memmove(mImpl->mArray + aIndex + otherCount, mImpl->mArray + aIndex,
00451             slide * sizeof(mImpl->mArray[0]));
00452   }
00453 
00454   for (PRInt32 i = 0; i < otherCount; i++)
00455   {
00456     // copy all the elements (destroys aIndex)
00457     mImpl->mArray[aIndex++] = other.mImpl->mArray[i];
00458     mImpl->mCount++;
00459   }
00460 
00461 #if DEBUG_VOIDARRAY
00462   if (mImpl->mCount > mMaxCount &&
00463       mImpl->mCount < (PRInt32)(sizeof(MaxElements)/sizeof(MaxElements[0])))
00464   {
00465     MaxElements[mImpl->mCount]++;
00466     MaxElements[mMaxCount]--;
00467     mMaxCount = mImpl->mCount;
00468   }
00469 #endif
00470 
00471   return PR_TRUE;
00472 }
00473 
00474 PRBool nsVoidArray::ReplaceElementAt(void* aElement, PRInt32 aIndex)
00475 {
00476   NS_ASSERTION(aIndex >= 0,"ReplaceElementAt(negative index)");
00477   if (aIndex < 0)
00478     return PR_FALSE;
00479 
00480   // Unlike InsertElementAt, ReplaceElementAt can implicitly add more
00481   // than just the one element to the array.
00482   if (PRUint32(aIndex) >= PRUint32(GetArraySize()))
00483   {
00484     PRInt32 oldCount = Count();
00485     PRInt32 requestedCount = aIndex + 1;
00486     PRInt32 growDelta = requestedCount - oldCount;
00487 
00488     // frees old mImpl IF this succeeds
00489     if (!GrowArrayBy(growDelta))
00490       return PR_FALSE;
00491   }
00492 
00493   mImpl->mArray[aIndex] = aElement;
00494   if (aIndex >= mImpl->mCount)
00495   {
00496     // Make sure that any entries implicitly added to the array by this
00497     // ReplaceElementAt are cleared to 0.  Some users of this assume that.
00498     // This code means we don't have to memset when we allocate an array.
00499     if (aIndex > mImpl->mCount) // note: not >=
00500     {
00501       // For example, if mCount is 2, and we do a ReplaceElementAt for
00502       // element[5], then we need to set three entries ([2], [3], and [4])
00503       // to 0.
00504       memset(&mImpl->mArray[mImpl->mCount], 0,
00505              (aIndex - mImpl->mCount) * sizeof(mImpl->mArray[0]));
00506     }
00507     
00508      mImpl->mCount = aIndex + 1;
00509 
00510 #if DEBUG_VOIDARRAY
00511      if (mImpl->mCount > mMaxCount &&
00512          mImpl->mCount < (PRInt32)(sizeof(MaxElements)/sizeof(MaxElements[0])))
00513      {
00514        MaxElements[mImpl->mCount]++;
00515        MaxElements[mMaxCount]--;
00516        mMaxCount = mImpl->mCount;
00517      }
00518 #endif
00519   }
00520 
00521   return PR_TRUE;
00522 }
00523 
00524 // useful for doing LRU arrays
00525 PRBool nsVoidArray::MoveElement(PRInt32 aFrom, PRInt32 aTo)
00526 {
00527   void *tempElement;
00528 
00529   if (aTo == aFrom)
00530     return PR_TRUE;
00531 
00532   NS_ASSERTION(aTo >= 0 && aFrom >= 0,"MoveElement(negative index)");
00533   if (aTo >= Count() || aFrom >= Count())
00534   {
00535     // can't extend the array when moving an element.  Also catches mImpl = null
00536     return PR_FALSE;
00537   }
00538   tempElement = mImpl->mArray[aFrom];
00539 
00540   if (aTo < aFrom)
00541   {
00542     // Moving one element closer to the head; the elements inbetween move down
00543     memmove(mImpl->mArray + aTo + 1, mImpl->mArray + aTo,
00544             (aFrom-aTo) * sizeof(mImpl->mArray[0]));
00545     mImpl->mArray[aTo] = tempElement;
00546   }
00547   else // already handled aFrom == aTo
00548   {
00549     // Moving one element closer to the tail; the elements inbetween move up
00550     memmove(mImpl->mArray + aFrom, mImpl->mArray + aFrom + 1,
00551             (aTo-aFrom) * sizeof(mImpl->mArray[0]));
00552     mImpl->mArray[aTo] = tempElement;
00553   }
00554 
00555   return PR_TRUE;
00556 }
00557 
00558 PRBool nsVoidArray::RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount)
00559 {
00560   PRInt32 oldCount = Count();
00561   NS_ASSERTION(aIndex >= 0,"RemoveElementsAt(negative index)");
00562   if (PRUint32(aIndex) >= PRUint32(oldCount))
00563   {
00564     // An invalid index causes the replace to fail
00565     return PR_FALSE;
00566   }
00567   // Limit to available entries starting at aIndex
00568   if (aCount + aIndex > oldCount)
00569     aCount = oldCount - aIndex;
00570 
00571   // We don't need to move any elements if we're removing the
00572   // last element in the array
00573   if (aIndex < (oldCount - aCount))
00574   {
00575     memmove(mImpl->mArray + aIndex, mImpl->mArray + aIndex + aCount,
00576             (oldCount - (aIndex + aCount)) * sizeof(mImpl->mArray[0]));
00577   }
00578 
00579   mImpl->mCount -= aCount;
00580   return PR_TRUE;
00581 }
00582 
00583 PRBool nsVoidArray::RemoveElement(void* aElement)
00584 {
00585   PRInt32 theIndex = IndexOf(aElement);
00586   if (theIndex != -1)
00587     return RemoveElementAt(theIndex);
00588 
00589   return PR_FALSE;
00590 }
00591 
00592 void nsVoidArray::Clear()
00593 {
00594   if (mImpl)
00595   {
00596     mImpl->mCount = 0;
00597   }
00598 }
00599 
00600 void nsVoidArray::Compact()
00601 {
00602   if (mImpl)
00603   {
00604     // XXX NOTE: this is quite inefficient in many cases if we're only
00605     // compacting by a little, but some callers care more about memory use.
00606     if (GetArraySize() > Count())
00607     {
00608       SizeTo(Count());
00609     }
00610   }
00611 }
00612 
00613 // Needed because we want to pass the pointer to the item in the array
00614 // to the comparator function, not a pointer to the pointer in the array.
00615 struct VoidArrayComparatorContext {
00616   nsVoidArrayComparatorFunc mComparatorFunc;
00617   void* mData;
00618 };
00619 
00620 PR_STATIC_CALLBACK(int)
00621 VoidArrayComparator(const void* aElement1, const void* aElement2, void* aData)
00622 {
00623   VoidArrayComparatorContext* ctx = NS_STATIC_CAST(VoidArrayComparatorContext*, aData);
00624   return (*ctx->mComparatorFunc)(*NS_STATIC_CAST(void* const*, aElement1),
00625                                  *NS_STATIC_CAST(void* const*, aElement2),
00626                                   ctx->mData);
00627 }
00628 
00629 void nsVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
00630 {
00631   if (mImpl && mImpl->mCount > 1)
00632   {
00633     VoidArrayComparatorContext ctx = {aFunc, aData};
00634     NS_QuickSort(mImpl->mArray, mImpl->mCount, sizeof(mImpl->mArray[0]),
00635                  VoidArrayComparator, &ctx);
00636   }
00637 }
00638 
00639 PRBool nsVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
00640 {
00641   PRInt32 index = -1;
00642   PRBool  running = PR_TRUE;
00643 
00644   if (mImpl)
00645   {
00646     while (running && (++index < mImpl->mCount))
00647     {
00648       running = (*aFunc)(mImpl->mArray[index], aData);
00649     }
00650   }
00651   return running;
00652 }
00653 
00654 PRBool nsVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
00655 {
00656   PRBool  running = PR_TRUE;
00657 
00658   if (mImpl)
00659   {
00660     PRInt32 index = Count();
00661     while (running && (0 <= --index))
00662     {
00663       running = (*aFunc)(mImpl->mArray[index], aData);
00664     }
00665   }
00666   return running;
00667 }
00668 
00669 //----------------------------------------------------------------
00670 // nsAutoVoidArray
00671 
00672 nsAutoVoidArray::nsAutoVoidArray()
00673   : nsVoidArray()
00674 {
00675   // Don't need to clear it.  Some users just call ReplaceElementAt(),
00676   // but we'll clear it at that time if needed to save CPU cycles.
00677 #if DEBUG_VOIDARRAY
00678   mIsAuto = PR_TRUE;
00679   ADD_TO_STATS(MaxAuto,0);
00680 #endif
00681   SetArray(NS_REINTERPRET_CAST(Impl*, mAutoBuf),kAutoBufSize,0,PR_FALSE);
00682 }
00683 
00684 void nsAutoVoidArray::Clear()
00685 {
00686   // We don't have to free on Clear, but since we have a built-in buffer,
00687   // it's worth considering.
00688   nsVoidArray::Clear();
00689   if (IsArrayOwner() && GetArraySize() > 4*kAutoBufSize)
00690     SizeTo(0);     // we override CompactTo - delete and repoint at auto array
00691 }
00692 
00693 PRBool nsAutoVoidArray::SizeTo(PRInt32 aSize)
00694 {
00695   if (!nsVoidArray::SizeTo(aSize))
00696     return PR_FALSE;
00697 
00698   if (!mImpl)
00699   {
00700     // reset the array to point to our autobuf
00701     SetArray(NS_REINTERPRET_CAST(Impl*, mAutoBuf),kAutoBufSize,0,PR_FALSE);
00702   }
00703   return PR_TRUE;
00704 }
00705 
00706 void nsAutoVoidArray::Compact()
00707 {
00708   nsVoidArray::Compact();
00709   if (!mImpl)
00710   {
00711     // reset the array to point to our autobuf
00712     SetArray(NS_REINTERPRET_CAST(Impl*, mAutoBuf),kAutoBufSize,0,PR_FALSE);
00713   }
00714 }
00715 
00716 //----------------------------------------------------------------
00717 // nsStringArray
00718 
00719 nsStringArray::nsStringArray(void)
00720   : nsVoidArray()
00721 {
00722 }
00723 
00724 nsStringArray::nsStringArray(PRInt32 aCount)
00725   : nsVoidArray(aCount)
00726 {
00727 }
00728 
00729 nsStringArray::~nsStringArray(void)
00730 {
00731   Clear();
00732 }
00733 
00734 nsStringArray& 
00735 nsStringArray::operator=(const nsStringArray& other)
00736 {
00737   // Copy the pointers
00738   nsVoidArray::operator=(other);
00739 
00740   // Now copy the strings
00741   for (PRInt32 i = Count() - 1; i >= 0; --i)
00742   {
00743     nsString* oldString = NS_STATIC_CAST(nsString*, other.ElementAt(i));
00744     mImpl->mArray[i] = new nsString(*oldString);
00745   }
00746 
00747   return *this;
00748 }
00749 
00750 void 
00751 nsStringArray::StringAt(PRInt32 aIndex, nsAString& aString) const
00752 {
00753   nsString* string = NS_STATIC_CAST(nsString*, nsVoidArray::ElementAt(aIndex));
00754   if (nsnull != string)
00755   {
00756     aString.Assign(*string);
00757   }
00758   else
00759   {
00760     aString.Truncate();
00761   }
00762 }
00763 
00764 nsString*
00765 nsStringArray::StringAt(PRInt32 aIndex) const
00766 {
00767   return NS_STATIC_CAST(nsString*, nsVoidArray::ElementAt(aIndex));
00768 }
00769 
00770 PRInt32 
00771 nsStringArray::IndexOf(const nsAString& aPossibleString) const
00772 {
00773   if (mImpl)
00774   {
00775     void** ap = mImpl->mArray;
00776     void** end = ap + mImpl->mCount;
00777     while (ap < end)
00778     {
00779       nsString* string = NS_STATIC_CAST(nsString*, *ap);
00780       if (string->Equals(aPossibleString))
00781       {
00782         return ap - mImpl->mArray;
00783       }
00784       ap++;
00785     }
00786   }
00787   return -1;
00788 }
00789 
00790 PRBool 
00791 nsStringArray::InsertStringAt(const nsAString& aString, PRInt32 aIndex)
00792 {
00793   nsString* string = new nsString(aString);
00794   if (nsVoidArray::InsertElementAt(string, aIndex))
00795   {
00796     return PR_TRUE;
00797   }
00798   delete string;
00799   return PR_FALSE;
00800 }
00801 
00802 PRBool
00803 nsStringArray::ReplaceStringAt(const nsAString& aString,
00804                                PRInt32 aIndex)
00805 {
00806   nsString* string = NS_STATIC_CAST(nsString*, nsVoidArray::ElementAt(aIndex));
00807   if (nsnull != string)
00808   {
00809     *string = aString;
00810     return PR_TRUE;
00811   }
00812   return PR_FALSE;
00813 }
00814 
00815 PRBool 
00816 nsStringArray::RemoveString(const nsAString& aString)
00817 {
00818   PRInt32 index = IndexOf(aString);
00819   if (-1 < index)
00820   {
00821     return RemoveStringAt(index);
00822   }
00823   return PR_FALSE;
00824 }
00825 
00826 PRBool nsStringArray::RemoveStringAt(PRInt32 aIndex)
00827 {
00828   nsString* string = StringAt(aIndex);
00829   if (nsnull != string)
00830   {
00831     nsVoidArray::RemoveElementAt(aIndex);
00832     delete string;
00833     return PR_TRUE;
00834   }
00835   return PR_FALSE;
00836 }
00837 
00838 void 
00839 nsStringArray::Clear(void)
00840 {
00841   PRInt32 index = Count();
00842   while (0 <= --index)
00843   {
00844     nsString* string = NS_STATIC_CAST(nsString*, mImpl->mArray[index]);
00845     delete string;
00846   }
00847   nsVoidArray::Clear();
00848 }
00849 
00850 PR_STATIC_CALLBACK(int)
00851 CompareString(const nsString* aString1, const nsString* aString2, void*)
00852 {
00853   return Compare(*aString1, *aString2);
00854 }
00855 
00856 void nsStringArray::Sort(void)
00857 {
00858   Sort(CompareString, nsnull);
00859 }
00860 
00861 void nsStringArray::Sort(nsStringArrayComparatorFunc aFunc, void* aData)
00862 {
00863   nsVoidArray::Sort(NS_REINTERPRET_CAST(nsVoidArrayComparatorFunc, aFunc), aData);
00864 }
00865 
00866 PRBool 
00867 nsStringArray::EnumerateForwards(nsStringArrayEnumFunc aFunc, void* aData)
00868 {
00869   PRInt32 index = -1;
00870   PRBool  running = PR_TRUE;
00871 
00872   if (mImpl)
00873   {
00874     while (running && (++index < mImpl->mCount))
00875     {
00876       running = (*aFunc)(*NS_STATIC_CAST(nsString*, mImpl->mArray[index]), aData);
00877     }
00878   }
00879   return running;
00880 }
00881 
00882 PRBool 
00883 nsStringArray::EnumerateBackwards(nsStringArrayEnumFunc aFunc, void* aData)
00884 {
00885   PRInt32 index = Count();
00886   PRBool  running = PR_TRUE;
00887 
00888   if (mImpl)
00889   {
00890     while (running && (0 <= --index))
00891     {
00892       running = (*aFunc)(*NS_STATIC_CAST(nsString*, mImpl->mArray[index]), aData);
00893     }
00894   }
00895   return running;
00896 }
00897 
00898 
00899 
00900 //----------------------------------------------------------------
00901 // nsCStringArray
00902 
00903 nsCStringArray::nsCStringArray(void)
00904   : nsVoidArray()
00905 {
00906 }
00907 
00908 // Parses a given string using the delimiter passed in and appends items
00909 // parsed to the array.
00910 void
00911 nsCStringArray::ParseString(const char* string, const char* delimiter)
00912 {
00913   if (string && *string && delimiter && *delimiter) {
00914     char *newStr;
00915     char *rest = nsCRT::strdup(string);
00916     char *token = nsCRT::strtok(rest, delimiter, &newStr);
00917 
00918     while (token) {
00919       if (*token) {
00920         /* calling AppendElement(void*) to avoid extra nsCString copy */
00921         AppendElement(new nsCString(token));
00922       }
00923       token = nsCRT::strtok(newStr, delimiter, &newStr);
00924     }
00925     PR_FREEIF(rest);
00926   }
00927 }
00928 
00929 nsCStringArray::nsCStringArray(PRInt32 aCount)
00930   : nsVoidArray(aCount)
00931 {
00932 }
00933 
00934 nsCStringArray::~nsCStringArray(void)
00935 {
00936   Clear();
00937 }
00938 
00939 nsCStringArray& 
00940 nsCStringArray::operator=(const nsCStringArray& other)
00941 {
00942   // Copy the pointers
00943   nsVoidArray::operator=(other);
00944 
00945   // Now copy the strings
00946   for (PRInt32 i = Count() - 1; i >= 0; --i)
00947   {
00948     nsCString* oldString = NS_STATIC_CAST(nsCString*, other.ElementAt(i));
00949     mImpl->mArray[i] = new nsCString(*oldString);
00950   }
00951 
00952   return *this;
00953 }
00954 
00955 void 
00956 nsCStringArray::CStringAt(PRInt32 aIndex, nsACString& aCString) const
00957 {
00958   nsCString* string = NS_STATIC_CAST(nsCString*, nsVoidArray::ElementAt(aIndex));
00959   if (nsnull != string)
00960   {
00961     aCString = *string;
00962   }
00963   else
00964   {
00965     aCString.Truncate();
00966   }
00967 }
00968 
00969 nsCString*
00970 nsCStringArray::CStringAt(PRInt32 aIndex) const
00971 {
00972   return NS_STATIC_CAST(nsCString*, nsVoidArray::ElementAt(aIndex));
00973 }
00974 
00975 PRInt32 
00976 nsCStringArray::IndexOf(const nsACString& aPossibleString) const
00977 {
00978   if (mImpl)
00979   {
00980     void** ap = mImpl->mArray;
00981     void** end = ap + mImpl->mCount;
00982     while (ap < end)
00983     {
00984       nsCString* string = NS_STATIC_CAST(nsCString*, *ap);
00985       if (string->Equals(aPossibleString))
00986       {
00987         return ap - mImpl->mArray;
00988       }
00989       ap++;
00990     }
00991   }
00992   return -1;
00993 }
00994 
00995 PRInt32 
00996 nsCStringArray::IndexOfIgnoreCase(const nsACString& aPossibleString) const
00997 {
00998   if (mImpl)
00999   {
01000     void** ap = mImpl->mArray;
01001     void** end = ap + mImpl->mCount;
01002     while (ap < end)
01003     {
01004       nsCString* string = NS_STATIC_CAST(nsCString*, *ap);
01005       if (string->Equals(aPossibleString, nsCaseInsensitiveCStringComparator()))
01006       {
01007         return ap - mImpl->mArray;
01008       }
01009       ap++;
01010     }
01011   }
01012   return -1;
01013 }
01014 
01015 PRBool 
01016 nsCStringArray::InsertCStringAt(const nsACString& aCString, PRInt32 aIndex)
01017 {
01018   nsCString* string = new nsCString(aCString);
01019   if (nsVoidArray::InsertElementAt(string, aIndex))
01020   {
01021     return PR_TRUE;
01022   }
01023   delete string;
01024   return PR_FALSE;
01025 }
01026 
01027 PRBool
01028 nsCStringArray::ReplaceCStringAt(const nsACString& aCString, PRInt32 aIndex)
01029 {
01030   nsCString* string = NS_STATIC_CAST(nsCString*, nsVoidArray::ElementAt(aIndex));
01031   if (nsnull != string)
01032   {
01033     *string = aCString;
01034     return PR_TRUE;
01035   }
01036   return PR_FALSE;
01037 }
01038 
01039 PRBool 
01040 nsCStringArray::RemoveCString(const nsACString& aCString)
01041 {
01042   PRInt32 index = IndexOf(aCString);
01043   if (-1 < index)
01044   {
01045     return RemoveCStringAt(index);
01046   }
01047   return PR_FALSE;
01048 }
01049 
01050 PRBool 
01051 nsCStringArray::RemoveCStringIgnoreCase(const nsACString& aCString)
01052 {
01053   PRInt32 index = IndexOfIgnoreCase(aCString);
01054   if (-1 < index)
01055   {
01056     return RemoveCStringAt(index);
01057   }
01058   return PR_FALSE;
01059 }
01060 
01061 PRBool nsCStringArray::RemoveCStringAt(PRInt32 aIndex)
01062 {
01063   nsCString* string = CStringAt(aIndex);
01064   if (nsnull != string)
01065   {
01066     nsVoidArray::RemoveElementAt(aIndex);
01067     delete string;
01068     return PR_TRUE;
01069   }
01070   return PR_FALSE;
01071 }
01072 
01073 void 
01074 nsCStringArray::Clear(void)
01075 {
01076   PRInt32 index = Count();
01077   while (0 <= --index)
01078   {
01079     nsCString* string = NS_STATIC_CAST(nsCString*, mImpl->mArray[index]);
01080     delete string;
01081   }
01082   nsVoidArray::Clear();
01083 }
01084 
01085 PR_STATIC_CALLBACK(int)
01086 CompareCString(const nsCString* aCString1, const nsCString* aCString2, void*)
01087 {
01088   return Compare(*aCString1, *aCString2);
01089 }
01090 
01091 PR_STATIC_CALLBACK(int)
01092 CompareCStringIgnoreCase(const nsCString* aCString1, const nsCString* aCString2, void*)
01093 {
01094   return Compare(*aCString1, *aCString2, nsCaseInsensitiveCStringComparator());
01095 }
01096 
01097 void nsCStringArray::Sort(void)
01098 {
01099   Sort(CompareCString, nsnull);
01100 }
01101 
01102 void nsCStringArray::SortIgnoreCase(void)
01103 {
01104   Sort(CompareCStringIgnoreCase, nsnull);
01105 }
01106 
01107 void nsCStringArray::Sort(nsCStringArrayComparatorFunc aFunc, void* aData)
01108 {
01109   nsVoidArray::Sort(NS_REINTERPRET_CAST(nsVoidArrayComparatorFunc, aFunc), aData);
01110 }
01111 
01112 PRBool 
01113 nsCStringArray::EnumerateForwards(nsCStringArrayEnumFunc aFunc, void* aData)
01114 {
01115   PRBool  running = PR_TRUE;
01116 
01117   if (mImpl)
01118   {
01119     PRInt32 index = -1;
01120     while (running && (++index < mImpl->mCount))
01121     {
01122       running = (*aFunc)(*NS_STATIC_CAST(nsCString*, mImpl->mArray[index]), aData);
01123     }
01124   }
01125   return running;
01126 }
01127 
01128 PRBool 
01129 nsCStringArray::EnumerateBackwards(nsCStringArrayEnumFunc aFunc, void* aData)
01130 {
01131   PRBool  running = PR_TRUE;
01132 
01133   if (mImpl)
01134   {
01135     PRInt32 index = Count();
01136     while (running && (0 <= --index))
01137     {
01138       running = (*aFunc)(*NS_STATIC_CAST(nsCString*, mImpl->mArray[index]), aData);
01139     }
01140   }
01141   return running;
01142 }
01143 
01144 
01145 //----------------------------------------------------------------------
01146 // NOTE: nsSmallVoidArray elements MUST all have the low bit as 0.
01147 // This means that normally it's only used for pointers, and in particular
01148 // structures or objects.
01149 nsSmallVoidArray::nsSmallVoidArray()
01150 {
01151   mChildren = nsnull;
01152 }
01153 
01154 nsSmallVoidArray::~nsSmallVoidArray()
01155 {
01156   if (HasVector())
01157   {
01158     nsVoidArray* vector = GetChildVector();
01159     delete vector;
01160   }
01161 }
01162 
01163 nsSmallVoidArray& 
01164 nsSmallVoidArray::operator=(nsSmallVoidArray& other)
01165 {
01166   nsVoidArray* ourArray = GetChildVector();
01167   nsVoidArray* otherArray = other.GetChildVector();
01168 
01169   if (HasVector())
01170   {
01171     if (other.HasVector())
01172     {
01173       // if both are real arrays, just use array= */
01174       *ourArray = *otherArray;
01175     }
01176     else
01177     {
01178       // we have an array, but the other doesn't.
01179       otherArray = other.SwitchToVector();
01180       if (otherArray)
01181         *ourArray = *otherArray;
01182     }
01183   }
01184   else
01185   {
01186     if (other.HasVector())
01187     {
01188       // we have no array, but other does
01189       ourArray = SwitchToVector();
01190       if (ourArray)
01191         *ourArray = *otherArray;
01192     }
01193     else
01194     {
01195       // neither has an array (either may have 0 or 1 items)
01196       SetSingleChild(other.GetSingleChild());
01197     }
01198   }
01199   return *this;
01200 }
01201 
01202 PRInt32
01203 nsSmallVoidArray::GetArraySize() const
01204 {
01205   nsVoidArray* vector = GetChildVector();
01206   if (vector)
01207     return vector->GetArraySize();
01208 
01209   return 1;
01210 }
01211 
01212 PRInt32
01213 nsSmallVoidArray::Count() const
01214 {
01215   if (HasSingleChild())
01216   {
01217     return 1;
01218   }
01219   else {
01220     nsVoidArray* vector = GetChildVector();
01221     if (vector)
01222       return vector->Count();
01223   }
01224 
01225   return 0;
01226 }
01227 
01228 void*
01229 nsSmallVoidArray::ElementAt(PRInt32 aIndex) const
01230 {
01231   if (HasSingleChild())
01232   {
01233     if (0 == aIndex)
01234       return (void*)GetSingleChild();
01235   }
01236   else
01237   {
01238     nsVoidArray* vector = GetChildVector();
01239     if (vector)
01240       return vector->ElementAt(aIndex);
01241   }
01242 
01243   return nsnull;
01244 }
01245 
01246 PRInt32
01247 nsSmallVoidArray::IndexOf(void* aPossibleElement) const
01248 {
01249   if (HasSingleChild())
01250   {
01251     if (aPossibleElement == (void*)GetSingleChild())
01252       return 0;
01253   }
01254   else
01255   {
01256     nsVoidArray* vector = GetChildVector();
01257     if (vector)
01258       return vector->IndexOf(aPossibleElement);
01259   }
01260 
01261   return -1;
01262 }
01263 
01264 PRBool
01265 nsSmallVoidArray::InsertElementAt(void* aElement, PRInt32 aIndex)
01266 {
01267   nsVoidArray* vector;
01268   NS_ASSERTION(!(PtrBits(aElement) & 0x1),"Attempt to add element with 0x1 bit set to nsSmallVoidArray");
01269   NS_ASSERTION(aElement != nsnull,"Attempt to add a NULL element to an nsSmallVoidArray");
01270 
01271   if (HasSingleChild())
01272   {
01273     vector = SwitchToVector();
01274   }
01275   else
01276   {
01277     vector = GetChildVector();
01278     if (!vector)
01279     {
01280       if (0 == aIndex)
01281       {
01282         SetSingleChild(aElement);
01283         return PR_TRUE;
01284       }
01285       return PR_FALSE;
01286     }
01287   }
01288 
01289   return vector->InsertElementAt(aElement, aIndex);
01290 }
01291 
01292 PRBool nsSmallVoidArray::InsertElementsAt(const nsVoidArray &other, PRInt32 aIndex)
01293 {
01294   nsVoidArray* vector;
01295   PRInt32 count = other.Count();
01296   if (count == 0)
01297     return PR_TRUE;
01298 
01299 #ifdef DEBUG  
01300   for (int i = 0; i < count; i++)
01301   {
01302     NS_ASSERTION(!(PtrBits(other.ElementAt(i)) & 0x1),"Attempt to add element with 0x1 bit set to nsSmallVoidArray");
01303     NS_ASSERTION(other.ElementAt(i) != nsnull,"Attempt to add a NULL element to an nsSmallVoidArray");
01304   }
01305 #endif
01306 
01307   if (!HasVector())
01308   {
01309     if (HasSingleChild() || count > 1 || aIndex > 0)
01310     {
01311       vector = SwitchToVector();
01312     }
01313     else
01314     {
01315       // count == 1, aIndex == 0, no elements already
01316       SetSingleChild(other[0]);
01317       return PR_TRUE;
01318     }
01319   }
01320   else
01321   {
01322     vector = GetChildVector();
01323   }
01324 
01325   if (vector)
01326   {
01327     return vector->InsertElementsAt(other,aIndex);
01328   }
01329   return PR_TRUE;
01330 }
01331 
01332 PRBool
01333 nsSmallVoidArray::ReplaceElementAt(void* aElement, PRInt32 aIndex)
01334 {
01335   NS_ASSERTION(!(PtrBits(aElement) & 0x1),"Attempt to add element with 0x1 bit set to nsSmallVoidArray");
01336   NS_ASSERTION(aElement != nsnull,"Attempt to add a NULL element to an nsSmallVoidArray");
01337 
01338   if (HasSingleChild())
01339   {
01340     if (aIndex == 0)
01341     {
01342       SetSingleChild(aElement);
01343       return PR_TRUE;
01344     }
01345   }
01346 
01347   nsVoidArray* vector = GetChildVector();
01348   if (!vector)
01349   {
01350     if (aIndex == 0)
01351     {
01352       SetSingleChild(aElement);
01353       return PR_TRUE;
01354     }
01355     vector = SwitchToVector();
01356     if (!vector)
01357       return PR_FALSE;
01358   }
01359   return vector->ReplaceElementAt(aElement, aIndex);
01360 }
01361 
01362 PRBool
01363 nsSmallVoidArray::AppendElement(void* aElement)
01364 {
01365   NS_ASSERTION(!(PtrBits(aElement) & 0x1),"Attempt to add element with 0x1 bit set to nsSmallVoidArray");
01366   NS_ASSERTION(aElement != nsnull,"Attempt to add a NULL element to an nsSmallVoidArray");
01367 
01368   nsVoidArray* vector;
01369   if (HasSingleChild())
01370   {
01371     vector = SwitchToVector();
01372   }
01373   else
01374   {
01375     vector = GetChildVector();
01376     if (!vector)
01377     {
01378       SetSingleChild(aElement);
01379       return PR_TRUE;
01380     }
01381   }
01382 
01383   return vector->AppendElement(aElement);
01384 }
01385 
01386 PRBool
01387 nsSmallVoidArray::RemoveElement(void* aElement)
01388 {
01389   if (HasSingleChild())
01390   {
01391     if (aElement == GetSingleChild())
01392     {
01393       SetSingleChild(nsnull);
01394       return PR_TRUE;
01395     }
01396   }
01397   else
01398   {
01399     nsVoidArray* vector = GetChildVector();
01400     if (vector)
01401       return vector->RemoveElement(aElement);
01402   }
01403 
01404   return PR_FALSE;
01405 }
01406 
01407 PRBool
01408 nsSmallVoidArray::RemoveElementAt(PRInt32 aIndex)
01409 {
01410   if (HasSingleChild())
01411   {
01412     if (0 == aIndex)
01413     {
01414       SetSingleChild(nsnull);
01415       return PR_TRUE;
01416     }
01417   }
01418   else
01419   {
01420     nsVoidArray* vector = GetChildVector();
01421     if (vector)
01422     {
01423       return vector->RemoveElementAt(aIndex);
01424     }
01425   }
01426 
01427   return PR_FALSE;
01428 }
01429 
01430 PRBool
01431 nsSmallVoidArray::RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount)
01432 {
01433   nsVoidArray* vector = GetChildVector();
01434 
01435   if (aCount == 0)
01436     return PR_TRUE;
01437 
01438   if (HasSingleChild())
01439   {
01440     if (aIndex == 0)
01441       SetSingleChild(nsnull);
01442     return PR_TRUE;
01443   }
01444 
01445   if (!vector)
01446     return PR_TRUE;
01447 
01448   // complex case; remove entries from an array
01449   return vector->RemoveElementsAt(aIndex,aCount);
01450 }
01451 
01452 void
01453 nsSmallVoidArray::Clear()
01454 {
01455   if (HasVector())
01456   {
01457     nsVoidArray* vector = GetChildVector();
01458     vector->Clear();
01459   }
01460   else
01461   {
01462     SetSingleChild(nsnull);
01463   }
01464 }
01465 
01466 PRBool
01467 nsSmallVoidArray::SizeTo(PRInt32 aMin)
01468 {
01469   nsVoidArray* vector;
01470   if (!HasVector())
01471   {
01472     if (aMin <= 1)
01473       return PR_TRUE;
01474     vector = SwitchToVector();
01475   }
01476   else
01477   {
01478     vector = GetChildVector();
01479     if (aMin <= 1)
01480     {
01481       void *prev = nsnull;
01482       if (vector->Count() == 1)
01483       {
01484         prev = vector->ElementAt(0);
01485       }
01486       delete vector;
01487       SetSingleChild(prev);
01488       return PR_TRUE;
01489     }
01490   }
01491   return vector->SizeTo(aMin);
01492 }
01493 
01494 void
01495 nsSmallVoidArray::Compact()
01496 {
01497   if (!HasSingleChild())
01498   {
01499     nsVoidArray* vector = GetChildVector();
01500     if (vector)
01501       vector->Compact();
01502   }
01503 }
01504 
01505 void
01506 nsSmallVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
01507 {
01508   if (HasVector())
01509   {
01510     nsVoidArray* vector = GetChildVector();
01511     vector->Sort(aFunc,aData);
01512   }
01513 }
01514 
01515 PRBool
01516 nsSmallVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
01517 {
01518   if (HasVector())
01519   {
01520     nsVoidArray* vector = GetChildVector();
01521     return vector->EnumerateForwards(aFunc,aData);
01522   }
01523   if (HasSingleChild())
01524   {
01525     return (*aFunc)(GetSingleChild(), aData);
01526   }
01527   return PR_TRUE;
01528 }
01529 
01530 PRBool
01531 nsSmallVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
01532 {
01533   if (HasVector())
01534   {
01535     nsVoidArray* vector = GetChildVector();
01536     return vector->EnumerateBackwards(aFunc,aData);
01537   }
01538   if (HasSingleChild())
01539   {
01540     return (*aFunc)(GetSingleChild(), aData);
01541   }
01542   return PR_TRUE;
01543 }
01544 
01545 void
01546 nsSmallVoidArray::SetSingleChild(void* aChild)
01547 {
01548   if (aChild)
01549     mChildren = (void*)(PtrBits(aChild) | 0x1);
01550   else
01551     mChildren = nsnull;
01552 }
01553 
01554 nsVoidArray*
01555 nsSmallVoidArray::SwitchToVector()
01556 {
01557   void* child = GetSingleChild();
01558 
01559   mChildren = (void*)new nsAutoVoidArray();
01560   nsVoidArray* vector = GetChildVector();
01561   if (vector && child)
01562     vector->AppendElement(child);
01563 
01564   return vector;
01565 }