xpcom/glue/nsVoidArray.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0)) -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is mozilla.org code.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Netscape Communications Corporation.
  19  * Portions created by the Initial Developer are Copyright (C) 1998
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either of the GNU General Public License Version 2 or later (the "GPL"),
  26  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37
  38 #include <stdlib.h>
  39
  40 #include "nsVoidArray.h"
  41 #include "nsQuickSort.h"
  42 #include "prbit.h"
  43 #include "nsISupportsImpl.h" // for nsTraceRefcnt
  44 #include "nsCRTGlue.h"
  45
  46 /**
  47  * Grow the array by at least this many elements at a time.
  48  */
  49 static const PRInt32 kMinGrowArrayBy = 8;
  50 static const PRInt32 kMaxGrowArrayBy = 1024;
  51 static const PRInt32 kAutoClearCompactSizeFactor = 4;
  52
  53 /**
  54  * This is the threshold (in bytes) of the mImpl struct, past which
  55  * we'll force the array to grow geometrically
  56  */
  57 static const PRInt32 kLinearThreshold = 24 * sizeof(void *);
  58
  59 /**
  60  * Compute the number of bytes requires for the mImpl struct that will
  61  * hold |n| elements.
  62  */
  63 #define SIZEOF_IMPL(n_) (sizeof(Impl) + sizeof(void *) * ((n_) - 1))
  64
  65
  66 /**
  67  * Compute the number of elements that an mImpl struct of |n| bytes
  68  * will hold.
  69  */
  70 #define CAPACITYOF_IMPL(n_) ((((n_) - sizeof(Impl)) / sizeof(void *)) + 1)
  71
  72 #if DEBUG_VOIDARRAY
  73 #define MAXVOID 10
  74
  75 class VoidStats {
  76 public:
  77   VoidStats();
  78   ~VoidStats();
  79
  80 };
  81
  82 static int sizesUsed; // number of the elements of the arrays used
  83 static int sizesAlloced[MAXVOID]; // sizes of the allocations.  sorted
  84 static int NumberOfSize[MAXVOID]; // number of this allocation size (1 per array)
  85 static int AllocedOfSize[MAXVOID]; // number of this allocation size (each size for array used)
  86 static int MaxAuto[MAXVOID];      // AutoArrays that maxed out at this size
  87 static int GrowInPlace[MAXVOID];  // arrays this size that grew in-place via realloc
  88
  89 // these are per-allocation
  90 static int MaxElements[2000];     // # of arrays that maxed out at each size.
  91
  92 // statistics macros
  93 #define ADD_TO_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
  94                                   { \
  95                                     if (sizesAlloced[i] == (int)(size)) \
  96                                     { ((x)[i])++; break; } \
  97                                   } \
  98                                   if (i >= sizesUsed && sizesUsed < MAXVOID) \
  99                                   { sizesAlloced[sizesUsed] = (size); \
 100                                     ((x)[sizesUsed++])++; break; \
 101                                   } \
 102                                 } while (0)
 103
 104 #define SUB_FROM_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
 105                                     { \
 106                                       if (sizesAlloced[i] == (int)(size)) \
 107                                       { ((x)[i])--; break; } \
 108                                     } \
 109                                   } while (0)
 110
 111
 112 VoidStats::VoidStats()
 113 {
 114   sizesUsed = 1;
 115   sizesAlloced[0] = 0;
 116 }
 117
 118 VoidStats::~VoidStats()
 119 {
 120   int i;
 121   for (i = 0; i < sizesUsed; i++)
 122   {
 123     printf("Size %d:\n",sizesAlloced[i]);
 124     printf("\tNumber of VoidArrays this size (max):     %d\n",NumberOfSize[i]-MaxAuto[i]);
 125     printf("\tNumber of AutoVoidArrays this size (max): %d\n",MaxAuto[i]);
 126     printf("\tNumber of allocations this size (total):  %d\n",AllocedOfSize[i]);
 127     printf("\tNumber of GrowsInPlace this size (total): %d\n",GrowInPlace[i]);
 128   }
 129   printf("Max Size of VoidArray:\n");
 130   for (i = 0; i < (int)(sizeof(MaxElements)/sizeof(MaxElements[0])); i++)
 131   {
 132     if (MaxElements[i])
 133       printf("\t%d: %d\n",i,MaxElements[i]);
 134   }
 135 }
 136
 137 // Just so constructor/destructor's get called
 138 VoidStats gVoidStats;
 139 #endif
 140
 141 void
 142 nsVoidArray::SetArray(Impl *newImpl, PRInt32 aSize, PRInt32 aCount,
 143                       PRBool aOwner, PRBool aHasAuto)
 144 {
 145   // old mImpl has been realloced and so we don't free/delete it
 146   NS_PRECONDITION(newImpl, "can't set size");
 147   mImpl = newImpl;
 148   mImpl->mCount = aCount;
 149   mImpl->mBits = static_cast<PRUint32>(aSize & kArraySizeMask) |
 150                  (aOwner ? kArrayOwnerMask : 0) |
 151                  (aHasAuto ? kArrayHasAutoBufferMask : 0);
 152 }
 153
 154 // This does all allocation/reallocation of the array.
 155 // It also will compact down to N - good for things that might grow a lot
 156 // at times,  but usually are smaller, like JS deferred GC releases.
 157 PRBool nsVoidArray::SizeTo(PRInt32 aSize)
 158 {
 159   PRUint32 oldsize = GetArraySize();
 160   PRBool isOwner = IsArrayOwner();
 161   PRBool hasAuto = HasAutoBuffer();
 162
 163   if (aSize == (PRInt32) oldsize)
 164     return PR_TRUE; // no change
 165
 166   if (aSize <= 0)
 167   {
 168     // free the array if allocated
 169     if (mImpl)
 170     {
 171       if (isOwner)
 172       {
 173         free(reinterpret_cast<char *>(mImpl));
 174         if (hasAuto) {
 175           static_cast<nsAutoVoidArray*>(this)->ResetToAutoBuffer();
 176         }
 177         else {
 178           mImpl = nsnull;
 179         }
 180       }
 181       else
 182       {
 183         mImpl->mCount = 0; // nsAutoVoidArray
 184       }
 185     }
 186     return PR_TRUE;
 187   }
 188
 189   if (mImpl && isOwner)
 190   {
 191     // We currently own an array impl. Resize it appropriately.
 192     if (aSize < mImpl->mCount)
 193     {
 194       // XXX Note: we could also just resize to mCount
 195       return PR_TRUE;  // can't make it that small, ignore request
 196     }
 197
 198     char* bytes = (char *) realloc(mImpl,SIZEOF_IMPL(aSize));
 199     Impl* newImpl = reinterpret_cast<Impl*>(bytes);
 200     if (!newImpl)
 201       return PR_FALSE;
 202
 203 #if DEBUG_VOIDARRAY
 204     if (mImpl == newImpl)
 205       ADD_TO_STATS(GrowInPlace,oldsize);
 206     ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
 207     if (aSize > mMaxSize)
 208     {
 209       ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
 210       if (oldsize)
 211         SUB_FROM_STATS(NumberOfSize,oldsize);
 212       mMaxSize = aSize;
 213       if (mIsAuto)
 214       {
 215         ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
 216         SUB_FROM_STATS(MaxAuto,oldsize);
 217       }
 218     }
 219 #endif
 220     SetArray(newImpl, aSize, newImpl->mCount, PR_TRUE, hasAuto);
 221     return PR_TRUE;
 222   }
 223
 224   if ((PRUint32) aSize < oldsize) {
 225     // No point in allocating if it won't free the current Impl anyway.
 226     return PR_TRUE;
 227   }
 228
 229   // just allocate an array
 230   // allocate the exact size requested
 231   char* bytes = (char *) malloc(SIZEOF_IMPL(aSize));
 232   Impl* newImpl = reinterpret_cast<Impl*>(bytes);
 233   if (!newImpl)
 234     return PR_FALSE;
 235
 236 #if DEBUG_VOIDARRAY
 237   ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
 238   if (aSize > mMaxSize)
 239   {
 240     ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
 241     if (oldsize && !mImpl)
 242       SUB_FROM_STATS(NumberOfSize,oldsize);
 243     mMaxSize = aSize;
 244   }
 245 #endif
 246   if (mImpl)
 247   {
 248 #if DEBUG_VOIDARRAY
 249     ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
 250     SUB_FROM_STATS(MaxAuto,0);
 251     SUB_FROM_STATS(NumberOfSize,0);
 252     mIsAuto = PR_TRUE;
 253 #endif
 254     // We must be growing an nsAutoVoidArray - copy since we didn't
 255     // realloc.
 256     memcpy(newImpl->mArray, mImpl->mArray,
 257                   mImpl->mCount * sizeof(mImpl->mArray[0]));
 258   }
 259
 260   SetArray(newImpl, aSize, mImpl ? mImpl->mCount : 0, PR_TRUE, hasAuto);
 261   // no memset; handled later in ReplaceElementAt if needed
 262   return PR_TRUE;
 263 }
 264
 265 PRBool nsVoidArray::GrowArrayBy(PRInt32 aGrowBy)
 266 {
 267   // We have to grow the array. Grow by kMinGrowArrayBy slots if we're
 268   // smaller than kLinearThreshold bytes, or a power of two if we're
 269   // larger.  This is much more efficient with most memory allocators,
 270   // especially if it's very large, or of the allocator is binned.
 271   if (aGrowBy < kMinGrowArrayBy)
 272     aGrowBy = kMinGrowArrayBy;
 273
 274   PRUint32 newCapacity = GetArraySize() + aGrowBy;  // Minimum increase
 275   PRUint32 newSize = SIZEOF_IMPL(newCapacity);
 276
 277   if (newSize >= (PRUint32) kLinearThreshold)
 278   {
 279     // newCount includes enough space for at least kMinGrowArrayBy new
 280     // slots. Select the next power-of-two size in bytes above or
 281     // equal to that.
 282     // Also, limit the increase in size to about a VM page or two.
 283     if (GetArraySize() >= kMaxGrowArrayBy)
 284     {
 285       newCapacity = GetArraySize() + PR_MAX(kMaxGrowArrayBy,aGrowBy);
 286       newSize = SIZEOF_IMPL(newCapacity);
 287     }
 288     else
 289     {
 290       PR_CEILING_LOG2(newSize, newSize);
 291       newCapacity = CAPACITYOF_IMPL(PR_BIT(newSize));
 292     }
 293   }
 294   // frees old mImpl IF this succeeds
 295   if (!SizeTo(newCapacity))
 296     return PR_FALSE;
 297
 298   return PR_TRUE;
 299 }
 300
 301 nsVoidArray::nsVoidArray()
 302   : mImpl(nsnull)
 303 {
 304   MOZ_COUNT_CTOR(nsVoidArray);
 305 #if DEBUG_VOIDARRAY
 306   mMaxCount = 0;
 307   mMaxSize = 0;
 308   mIsAuto = PR_FALSE;
 309   ADD_TO_STATS(NumberOfSize,0);
 310   MaxElements[0]++;
 311 #endif
 312 }
 313
 314 nsVoidArray::nsVoidArray(PRInt32 aCount)
 315   : mImpl(nsnull)
 316 {
 317   MOZ_COUNT_CTOR(nsVoidArray);
 318 #if DEBUG_VOIDARRAY
 319   mMaxCount = 0;
 320   mMaxSize = 0;
 321   mIsAuto = PR_FALSE;
 322   MaxElements[0]++;
 323 #endif
 324   SizeTo(aCount);
 325 }
 326
 327 nsVoidArray& nsVoidArray::operator=(const nsVoidArray& other)
 328 {
 329   PRInt32 otherCount = other.Count();
 330   PRInt32 maxCount = GetArraySize();
 331   if (otherCount)
 332   {
 333     if (otherCount > maxCount)
 334     {
 335       // frees old mImpl IF this succeeds
 336       if (!GrowArrayBy(otherCount-maxCount))
 337         return *this;      // XXX The allocation failed - don't do anything
 338
 339       memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
 340       mImpl->mCount = otherCount;
 341     }
 342     else
 343     {
 344       // the old array can hold the new array
 345       memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
 346       mImpl->mCount = otherCount;
 347       // if it shrank a lot, compact it anyways
 348       if ((otherCount*2) < maxCount && maxCount > 100)
 349       {
 350         Compact();  // shrank by at least 50 entries
 351       }
 352     }
 353 #if DEBUG_VOIDARRAY
 354      if (mImpl->mCount > mMaxCount &&
 355          mImpl->mCount < (PRInt32)(sizeof(MaxElements)/sizeof(MaxElements[0])))
 356      {
 357        MaxElements[mImpl->mCount]++;
 358        MaxElements[mMaxCount]--;
 359        mMaxCount = mImpl->mCount;
 360      }
 361 #endif
 362   }
 363   else
 364   {
 365     // Why do we drop the buffer here when we don't in Clear()?
 366     SizeTo(0);
 367   }
 368
 369   return *this;
 370 }
 371
 372 nsVoidArray::~nsVoidArray()
 373 {
 374   MOZ_COUNT_DTOR(nsVoidArray);
 375   if (mImpl && IsArrayOwner())
 376     free(reinterpret_cast<char*>(mImpl));
 377 }
 378
 379 PRInt32 nsVoidArray::IndexOf(void* aPossibleElement) const
 380 {
 381   if (mImpl)
 382   {
 383     void** ap = mImpl->mArray;
 384     void** end = ap + mImpl->mCount;
 385     while (ap < end)
 386     {
 387       if (*ap == aPossibleElement)
 388       {
 389         return ap - mImpl->mArray;
 390       }
 391       ap++;
 392     }
 393   }
 394   return -1;
 395 }
 396
 397 PRBool nsVoidArray::InsertElementAt(void* aElement, PRInt32 aIndex)
 398 {
 399   PRInt32 oldCount = Count();
 400   NS_ASSERTION(aIndex >= 0,"InsertElementAt(negative index)");
 401   if (PRUint32(aIndex) > PRUint32(oldCount))
 402   {
 403     // An invalid index causes the insertion to fail
 404     // Invalid indexes are ones that add more than one entry to the
 405     // array (i.e., they can append).
 406     return PR_FALSE;
 407   }
 408
 409   if (oldCount >= GetArraySize())
 410   {
 411     if (!GrowArrayBy(1))
 412       return PR_FALSE;
 413   }
 414   // else the array is already large enough
 415
 416   PRInt32 slide = oldCount - aIndex;
 417   if (0 != slide)
 418   {
 419     // Slide data over to make room for the insertion
 420     memmove(mImpl->mArray + aIndex + 1, mImpl->mArray + aIndex,
 421             slide * sizeof(mImpl->mArray[0]));
 422   }
 423
 424   mImpl->mArray[aIndex] = aElement;
 425   mImpl->mCount++;
 426
 427 #if DEBUG_VOIDARRAY
 428   if (mImpl->mCount > mMaxCount &&
 429       mImpl->mCount < (PRInt32)(sizeof(MaxElements)/sizeof(MaxElements[0])))
 430   {
 431     MaxElements[mImpl->mCount]++;
 432     MaxElements[mMaxCount]--;
 433     mMaxCount = mImpl->mCount;
 434   }
 435 #endif
 436
 437   return PR_TRUE;
 438 }
 439
 440 PRBool nsVoidArray::InsertElementsAt(const nsVoidArray& other, PRInt32 aIndex)
 441 {
 442   PRInt32 oldCount = Count();
 443   PRInt32 otherCount = other.Count();
 444
 445   NS_ASSERTION(aIndex >= 0,"InsertElementsAt(negative index)");
 446   if (PRUint32(aIndex) > PRUint32(oldCount))
 447   {
 448     // An invalid index causes the insertion to fail
 449     // Invalid indexes are ones that are more than one entry past the end of
 450     // the array (i.e., they can append).
 451     return PR_FALSE;
 452   }
 453
 454   if (oldCount + otherCount > GetArraySize())
 455   {
 456     if (!GrowArrayBy(otherCount))
 457       return PR_FALSE;;
 458   }
 459   // else the array is already large enough
 460
 461   PRInt32 slide = oldCount - aIndex;
 462   if (0 != slide)
 463   {
 464     // Slide data over to make room for the insertion
 465     memmove(mImpl->mArray + aIndex + otherCount, mImpl->mArray + aIndex,
 466             slide * sizeof(mImpl->mArray[0]));
 467   }
 468
 469   for (PRInt32 i = 0; i < otherCount; i++)
 470   {
 471     // copy all the elements (destroys aIndex)
 472     mImpl->mArray[aIndex++] = other.mImpl->mArray[i];
 473     mImpl->mCount++;
 474   }
 475
 476 #if DEBUG_VOIDARRAY
 477   if (mImpl->mCount > mMaxCount &&
 478       mImpl->mCount < (PRInt32)(sizeof(MaxElements)/sizeof(MaxElements[0])))
 479   {
 480     MaxElements[mImpl->mCount]++;
 481     MaxElements[mMaxCount]--;
 482     mMaxCount = mImpl->mCount;
 483   }
 484 #endif
 485
 486   return PR_TRUE;
 487 }
 488
 489 PRBool nsVoidArray::ReplaceElementAt(void* aElement, PRInt32 aIndex)
 490 {
 491   NS_ASSERTION(aIndex >= 0,"ReplaceElementAt(negative index)");
 492   if (aIndex < 0)
 493     return PR_FALSE;
 494
 495   // Unlike InsertElementAt, ReplaceElementAt can implicitly add more
 496   // than just the one element to the array.
 497   if (PRUint32(aIndex) >= PRUint32(GetArraySize()))
 498   {
 499     PRInt32 oldCount = Count();
 500     PRInt32 requestedCount = aIndex + 1;
 501     PRInt32 growDelta = requestedCount - oldCount;
 502
 503     // frees old mImpl IF this succeeds
 504     if (!GrowArrayBy(growDelta))
 505       return PR_FALSE;
 506   }
 507
 508   mImpl->mArray[aIndex] = aElement;
 509   if (aIndex >= mImpl->mCount)
 510   {
 511     // Make sure that any entries implicitly added to the array by this
 512     // ReplaceElementAt are cleared to 0.  Some users of this assume that.
 513     // This code means we don't have to memset when we allocate an array.
 514     if (aIndex > mImpl->mCount) // note: not >=
 515     {
 516       // For example, if mCount is 2, and we do a ReplaceElementAt for
 517       // element[5], then we need to set three entries ([2], [3], and [4])
 518       // to 0.
 519       memset(&mImpl->mArray[mImpl->mCount], 0,
 520              (aIndex - mImpl->mCount) * sizeof(mImpl->mArray[0]));
 521     }
 522
 523      mImpl->mCount = aIndex + 1;
 524
 525 #if DEBUG_VOIDARRAY
 526      if (mImpl->mCount > mMaxCount &&
 527          mImpl->mCount < (PRInt32)(sizeof(MaxElements)/sizeof(MaxElements[0])))
 528      {
 529        MaxElements[mImpl->mCount]++;
 530        MaxElements[mMaxCount]--;
 531        mMaxCount = mImpl->mCount;
 532      }
 533 #endif
 534   }
 535
 536   return PR_TRUE;
 537 }
 538
 539 // useful for doing LRU arrays
 540 PRBool nsVoidArray::MoveElement(PRInt32 aFrom, PRInt32 aTo)
 541 {
 542   void *tempElement;
 543
 544   if (aTo == aFrom)
 545     return PR_TRUE;
 546
 547   NS_ASSERTION(aTo >= 0 && aFrom >= 0,"MoveElement(negative index)");
 548   if (aTo >= Count() || aFrom >= Count())
 549   {
 550     // can't extend the array when moving an element.  Also catches mImpl = null
 551     return PR_FALSE;
 552   }
 553   tempElement = mImpl->mArray[aFrom];
 554
 555   if (aTo < aFrom)
 556   {
 557     // Moving one element closer to the head; the elements inbetween move down
 558     memmove(mImpl->mArray + aTo + 1, mImpl->mArray + aTo,
 559             (aFrom-aTo) * sizeof(mImpl->mArray[0]));
 560     mImpl->mArray[aTo] = tempElement;
 561   }
 562   else // already handled aFrom == aTo
 563   {
 564     // Moving one element closer to the tail; the elements inbetween move up
 565     memmove(mImpl->mArray + aFrom, mImpl->mArray + aFrom + 1,
 566             (aTo-aFrom) * sizeof(mImpl->mArray[0]));
 567     mImpl->mArray[aTo] = tempElement;
 568   }
 569
 570   return PR_TRUE;
 571 }
 572
 573 PRBool nsVoidArray::RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount)
 574 {
 575   PRInt32 oldCount = Count();
 576   NS_ASSERTION(aIndex >= 0,"RemoveElementsAt(negative index)");
 577   if (PRUint32(aIndex) >= PRUint32(oldCount))
 578   {
 579     // An invalid index causes the replace to fail
 580     return PR_FALSE;
 581   }
 582   // Limit to available entries starting at aIndex
 583   if (aCount + aIndex > oldCount)
 584     aCount = oldCount - aIndex;
 585
 586   // We don't need to move any elements if we're removing the
 587   // last element in the array
 588   if (aIndex < (oldCount - aCount))
 589   {
 590     memmove(mImpl->mArray + aIndex, mImpl->mArray + aIndex + aCount,
 591             (oldCount - (aIndex + aCount)) * sizeof(mImpl->mArray[0]));
 592   }
 593
 594   mImpl->mCount -= aCount;
 595   return PR_TRUE;
 596 }
 597
 598 PRBool nsVoidArray::RemoveElement(void* aElement)
 599 {
 600   PRInt32 theIndex = IndexOf(aElement);
 601   if (theIndex != -1)
 602     return RemoveElementAt(theIndex);
 603
 604   return PR_FALSE;
 605 }
 606
 607 void nsVoidArray::Clear()
 608 {
 609   if (mImpl)
 610   {
 611     mImpl->mCount = 0;
 612     // We don't have to free on Clear, but if we have a built-in buffer,
 613     // it's worth considering.
 614     if (HasAutoBuffer() && IsArrayOwner() &&
 615         GetArraySize() > kAutoClearCompactSizeFactor * kAutoBufSize) {
 616       SizeTo(0);
 617     }
 618   }
 619 }
 620
 621 void nsVoidArray::Compact()
 622 {
 623   if (mImpl)
 624   {
 625     // XXX NOTE: this is quite inefficient in many cases if we're only
 626     // compacting by a little, but some callers care more about memory use.
 627     PRInt32 count = Count();
 628     if (HasAutoBuffer() && count <= kAutoBufSize)
 629     {
 630       Impl* oldImpl = mImpl;
 631       static_cast<nsAutoVoidArray*>(this)->ResetToAutoBuffer();
 632       memcpy(mImpl->mArray, oldImpl->mArray,
 633              count * sizeof(mImpl->mArray[0]));
 634       free(reinterpret_cast<char *>(oldImpl));
 635     }
 636     else if (GetArraySize() > count)
 637     {
 638       SizeTo(Count());
 639     }
 640   }
 641 }
 642
 643 // Needed because we want to pass the pointer to the item in the array
 644 // to the comparator function, not a pointer to the pointer in the array.
 645 struct VoidArrayComparatorContext {
 646   nsVoidArrayComparatorFunc mComparatorFunc;
 647   void* mData;
 648 };
 649
 650 PR_STATIC_CALLBACK(int)
 651 VoidArrayComparator(const void* aElement1, const void* aElement2, void* aData)
 652 {
 653   VoidArrayComparatorContext* ctx = static_cast<VoidArrayComparatorContext*>(aData);
 654   return (*ctx->mComparatorFunc)(*static_cast<void* const*>(aElement1),
 655                                  *static_cast<void* const*>(aElement2),
 656                                   ctx->mData);
 657 }
 658
 659 void nsVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
 660 {
 661   if (mImpl && mImpl->mCount > 1)
 662   {
 663     VoidArrayComparatorContext ctx = {aFunc, aData};
 664     NS_QuickSort(mImpl->mArray, mImpl->mCount, sizeof(mImpl->mArray[0]),
 665                  VoidArrayComparator, &ctx);
 666   }
 667 }
 668
 669 PRBool nsVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
 670 {
 671   PRInt32 index = -1;
 672   PRBool  running = PR_TRUE;
 673
 674   if (mImpl)
 675   {
 676     while (running && (++index < mImpl->mCount))
 677     {
 678       running = (*aFunc)(mImpl->mArray[index], aData);
 679     }
 680   }
 681   return running;
 682 }
 683
 684 PRBool nsVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
 685 {
 686   PRBool  running = PR_TRUE;
 687
 688   if (mImpl)
 689   {
 690     PRInt32 index = Count();
 691     while (running && (0 <= --index))
 692     {
 693       running = (*aFunc)(mImpl->mArray[index], aData);
 694     }
 695   }
 696   return running;
 697 }
 698
 699 //----------------------------------------------------------------
 700 // nsAutoVoidArray
 701
 702 nsAutoVoidArray::nsAutoVoidArray()
 703   : nsVoidArray()
 704 {
 705   // Don't need to clear it.  Some users just call ReplaceElementAt(),
 706   // but we'll clear it at that time if needed to save CPU cycles.
 707 #if DEBUG_VOIDARRAY
 708   mIsAuto = PR_TRUE;
 709   ADD_TO_STATS(MaxAuto,0);
 710 #endif
 711   ResetToAutoBuffer();
 712 }
 713
 714 //----------------------------------------------------------------
 715 // nsStringArray
 716
 717 nsStringArray::nsStringArray(void)
 718   : nsVoidArray()
 719 {
 720 }
 721
 722 nsStringArray::nsStringArray(PRInt32 aCount)
 723   : nsVoidArray(aCount)
 724 {
 725 }
 726
 727 nsStringArray::~nsStringArray(void)
 728 {
 729   Clear();
 730 }
 731
 732 nsStringArray&
 733 nsStringArray::operator=(const nsStringArray& other)
 734 {
 735   // Copy the pointers
 736   nsVoidArray::operator=(other);
 737
 738   // Now copy the strings
 739   PRInt32 count = Count();
 740   for (PRInt32 i = 0; i < count; ++i)
 741   {
 742     nsString* oldString = static_cast<nsString*>(other.ElementAt(i));
 743     nsString* newString = new nsString(*oldString);
 744     if (!newString)
 745     {
 746       mImpl->mCount = i;
 747       return *this;
 748     }
 749     mImpl->mArray[i] = newString;
 750   }
 751
 752   return *this;
 753 }
 754
 755 void
 756 nsStringArray::StringAt(PRInt32 aIndex, nsAString& aString) const
 757 {
 758   nsString* string = static_cast<nsString*>(nsVoidArray::ElementAt(aIndex));
 759   if (nsnull != string)
 760   {
 761     aString.Assign(*string);
 762   }
 763   else
 764   {
 765     aString.Truncate();
 766   }
 767 }
 768
 769 nsString*
 770 nsStringArray::StringAt(PRInt32 aIndex) const
 771 {
 772   return static_cast<nsString*>(nsVoidArray::ElementAt(aIndex));
 773 }
 774
 775 PRInt32
 776 nsStringArray::IndexOf(const nsAString& aPossibleString) const
 777 {
 778   if (mImpl)
 779   {
 780     void** ap = mImpl->mArray;
 781     void** end = ap + mImpl->mCount;
 782     while (ap < end)
 783     {
 784       nsString* string = static_cast<nsString*>(*ap);
 785       if (string->Equals(aPossibleString))
 786       {
 787         return ap - mImpl->mArray;
 788       }
 789       ap++;
 790     }
 791   }
 792   return -1;
 793 }
 794
 795 PRBool
 796 nsStringArray::InsertStringAt(const nsAString& aString, PRInt32 aIndex)
 797 {
 798   nsString* string = new nsString(aString);
 799   if (!string)
 800     return PR_FALSE;
 801   if (nsVoidArray::InsertElementAt(string, aIndex))
 802     return PR_TRUE;
 803
 804   delete string;
 805   return PR_FALSE;
 806 }
 807
 808 PRBool
 809 nsStringArray::ReplaceStringAt(const nsAString& aString,
 810                                PRInt32 aIndex)
 811 {
 812   nsString* string = static_cast<nsString*>(nsVoidArray::ElementAt(aIndex));
 813   if (nsnull != string)
 814   {
 815     *string = aString;
 816     return PR_TRUE;
 817   }
 818   return PR_FALSE;
 819 }
 820
 821 PRBool
 822 nsStringArray::RemoveString(const nsAString& aString)
 823 {
 824   PRInt32 index = IndexOf(aString);
 825   if (-1 < index)
 826   {
 827     return RemoveStringAt(index);
 828   }
 829   return PR_FALSE;
 830 }
 831
 832 PRBool nsStringArray::RemoveStringAt(PRInt32 aIndex)
 833 {
 834   nsString* string = StringAt(aIndex);
 835   if (nsnull != string)
 836   {
 837     nsVoidArray::RemoveElementAt(aIndex);
 838     delete string;
 839     return PR_TRUE;
 840   }
 841   return PR_FALSE;
 842 }
 843
 844 void
 845 nsStringArray::Clear(void)
 846 {
 847   PRInt32 index = Count();
 848   while (0 <= --index)
 849   {
 850     nsString* string = static_cast<nsString*>(mImpl->mArray[index]);
 851     delete string;
 852   }
 853   nsVoidArray::Clear();
 854 }
 855
 856 PR_STATIC_CALLBACK(int)
 857 CompareString(const nsString* aString1, const nsString* aString2, void*)
 858 {
 859 #ifdef MOZILLA_INTERNAL_API
 860   return Compare(*aString1, *aString2);
 861 #else
 862   const PRUnichar* s1;
 863   const PRUnichar* s2;
 864   PRUint32 len1 = NS_StringGetData(*aString1, &s1);
 865   PRUint32 len2 = NS_StringGetData(*aString2, &s2);
 866   int r = memcmp(s1, s2, sizeof(PRUnichar) * PR_MIN(len1, len2));
 867   if (r)
 868     return r;
 869
 870   if (len1 < len2)
 871     return -1;
 872
 873   if (len1 > len2)
 874     return 1;
 875
 876   return 0;
 877 #endif
 878 }
 879
 880 void nsStringArray::Sort(void)
 881 {
 882   Sort(CompareString, nsnull);
 883 }
 884
 885 void nsStringArray::Sort(nsStringArrayComparatorFunc aFunc, void* aData)
 886 {
 887   nsVoidArray::Sort(reinterpret_cast<nsVoidArrayComparatorFunc>(aFunc), aData);
 888 }
 889
 890 PRBool
 891 nsStringArray::EnumerateForwards(nsStringArrayEnumFunc aFunc, void* aData)
 892 {
 893   PRInt32 index = -1;
 894   PRBool  running = PR_TRUE;
 895
 896   if (mImpl)
 897   {
 898     while (running && (++index < mImpl->mCount))
 899     {
 900       running = (*aFunc)(*static_cast<nsString*>(mImpl->mArray[index]), aData);
 901     }
 902   }
 903   return running;
 904 }
 905
 906 PRBool
 907 nsStringArray::EnumerateBackwards(nsStringArrayEnumFunc aFunc, void* aData)
 908 {
 909   PRInt32 index = Count();
 910   PRBool  running = PR_TRUE;
 911
 912   if (mImpl)
 913   {
 914     while (running && (0 <= --index))
 915     {
 916       running = (*aFunc)(*static_cast<nsString*>(mImpl->mArray[index]), aData);
 917     }
 918   }
 919   return running;
 920 }
 921
 922
 923
 924 //----------------------------------------------------------------
 925 // nsCStringArray
 926
 927 nsCStringArray::nsCStringArray(void)
 928   : nsVoidArray()
 929 {
 930 }
 931
 932 // Parses a given string using the delimiter passed in and appends items
 933 // parsed to the array.
 934 PRBool
 935 nsCStringArray::ParseString(const char* string, const char* delimiter)
 936 {
 937   if (string && *string && delimiter && *delimiter) {
 938     char *rest = strdup(string);
 939     if (!rest)
 940       return PR_FALSE;
 941     char *newStr = rest;
 942     char *token = NS_strtok(delimiter, &newStr);
 943
 944     PRInt32 count = Count();
 945     while (token) {
 946       if (*token) {
 947         /* calling AppendElement(void*) to avoid extra nsCString copy */
 948         nsCString *cstring = new nsCString(token);
 949         if (cstring && !AppendElement(cstring)) {
 950           // AppendElement failed, release and null cstring so we fall
 951           // through to the case below.
 952           delete cstring;
 953           cstring = nsnull;
 954         }
 955         if (!cstring) {
 956           // We've run out of memory. Remove all newly appended elements from
 957           // our array so we don't leave ourselves in a partially added state.
 958           // When we return, the array will be precisely as it was when this
 959           // function was called.
 960           RemoveElementsAt(count, Count() - count);
 961           free(rest);
 962           return PR_FALSE;
 963         }
 964       }
 965       token = NS_strtok(delimiter, &newStr);
 966     }
 967     free(rest);
 968   }
 969   return PR_TRUE;
 970 }
 971
 972 nsCStringArray::nsCStringArray(PRInt32 aCount)
 973   : nsVoidArray(aCount)
 974 {
 975 }
 976
 977 nsCStringArray::~nsCStringArray(void)
 978 {
 979   Clear();
 980 }
 981
 982 nsCStringArray&
 983 nsCStringArray::operator=(const nsCStringArray& other)
 984 {
 985   // Copy the pointers
 986   nsVoidArray::operator=(other);
 987
 988   // Now copy the strings
 989   PRInt32 count = Count();
 990   for (PRInt32 i = 0; i < count; ++i)
 991   {
 992     nsCString* oldString = static_cast<nsCString*>(other.ElementAt(i));
 993     nsCString* newString = new nsCString(*oldString);
 994     if (!newString)
 995     {
 996       mImpl->mCount = i;
 997       return *this;
 998     }
 999     mImpl->mArray[i] = newString;
1000   }
1001
1002   return *this;
1003 }
1004
1005 void
1006 nsCStringArray::CStringAt(PRInt32 aIndex, nsACString& aCString) const
1007 {
1008   nsCString* string = static_cast<nsCString*>(nsVoidArray::ElementAt(aIndex));
1009   if (nsnull != string)
1010   {
1011     aCString = *string;
1012   }
1013   else
1014   {
1015     aCString.Truncate();
1016   }
1017 }
1018
1019 nsCString*
1020 nsCStringArray::CStringAt(PRInt32 aIndex) const
1021 {
1022   return static_cast<nsCString*>(nsVoidArray::ElementAt(aIndex));
1023 }
1024
1025 PRInt32
1026 nsCStringArray::IndexOf(const nsACString& aPossibleString) const
1027 {
1028   if (mImpl)
1029   {
1030     void** ap = mImpl->mArray;
1031     void** end = ap + mImpl->mCount;
1032     while (ap < end)
1033     {
1034       nsCString* string = static_cast<nsCString*>(*ap);
1035       if (string->Equals(aPossibleString))
1036       {
1037         return ap - mImpl->mArray;
1038       }
1039       ap++;
1040     }
1041   }
1042   return -1;
1043 }
1044
1045 #ifdef MOZILLA_INTERNAL_API
1046 PRInt32
1047 nsCStringArray::IndexOfIgnoreCase(const nsACString& aPossibleString) const
1048 {
1049   if (mImpl)
1050   {
1051     void** ap = mImpl->mArray;
1052     void** end = ap + mImpl->mCount;
1053     while (ap < end)
1054     {
1055       nsCString* string = static_cast<nsCString*>(*ap);
1056       if (string->Equals(aPossibleString, nsCaseInsensitiveCStringComparator()))
1057       {
1058         return ap - mImpl->mArray;
1059       }
1060       ap++;
1061     }
1062   }
1063   return -1;
1064 }
1065 #endif
1066
1067 PRBool
1068 nsCStringArray::InsertCStringAt(const nsACString& aCString, PRInt32 aIndex)
1069 {
1070   nsCString* string = new nsCString(aCString);
1071   if (!string)
1072     return PR_FALSE;
1073   if (nsVoidArray::InsertElementAt(string, aIndex))
1074     return PR_TRUE;
1075
1076   delete string;
1077   return PR_FALSE;
1078 }
1079
1080 PRBool
1081 nsCStringArray::ReplaceCStringAt(const nsACString& aCString, PRInt32 aIndex)
1082 {
1083   nsCString* string = static_cast<nsCString*>(nsVoidArray::ElementAt(aIndex));
1084   if (nsnull != string)
1085   {
1086     *string = aCString;
1087     return PR_TRUE;
1088   }
1089   return PR_FALSE;
1090 }
1091
1092 PRBool
1093 nsCStringArray::RemoveCString(const nsACString& aCString)
1094 {
1095   PRInt32 index = IndexOf(aCString);
1096   if (-1 < index)
1097   {
1098     return RemoveCStringAt(index);
1099   }
1100   return PR_FALSE;
1101 }
1102
1103 #ifdef MOZILLA_INTERNAL_API
1104 PRBool
1105 nsCStringArray::RemoveCStringIgnoreCase(const nsACString& aCString)
1106 {
1107   PRInt32 index = IndexOfIgnoreCase(aCString);
1108   if (-1 < index)
1109   {
1110     return RemoveCStringAt(index);
1111   }
1112   return PR_FALSE;
1113 }
1114 #endif
1115
1116 PRBool nsCStringArray::RemoveCStringAt(PRInt32 aIndex)
1117 {
1118   nsCString* string = CStringAt(aIndex);
1119   if (nsnull != string)
1120   {
1121     nsVoidArray::RemoveElementAt(aIndex);
1122     delete string;
1123     return PR_TRUE;
1124   }
1125   return PR_FALSE;
1126 }
1127
1128 void
1129 nsCStringArray::Clear(void)
1130 {
1131   PRInt32 index = Count();
1132   while (0 <= --index)
1133   {
1134     nsCString* string = static_cast<nsCString*>(mImpl->mArray[index]);
1135     delete string;
1136   }
1137   nsVoidArray::Clear();
1138 }
1139
1140 PR_STATIC_CALLBACK(int)
1141 CompareCString(const nsCString* aCString1, const nsCString* aCString2, void*)
1142 {
1143 #ifdef MOZILLA_INTERNAL_API
1144   return Compare(*aCString1, *aCString2);
1145 #else
1146   const char* s1;
1147   const char* s2;
1148   PRUint32 len1 = NS_CStringGetData(*aCString1, &s1);
1149   PRUint32 len2 = NS_CStringGetData(*aCString2, &s2);
1150   int r = memcmp(s1, s2, PR_MIN(len1, len2));
1151   if (r)
1152     return r;
1153
1154   if (len1 < len2)
1155     return -1;
1156
1157   if (len1 > len2)
1158     return 1;
1159
1160   return 0;
1161 #endif
1162 }
1163
1164 #ifdef MOZILLA_INTERNAL_API
1165 PR_STATIC_CALLBACK(int)
1166 CompareCStringIgnoreCase(const nsCString* aCString1, const nsCString* aCString2, void*)
1167 {
1168   return Compare(*aCString1, *aCString2, nsCaseInsensitiveCStringComparator());
1169 }
1170 #endif
1171
1172 void nsCStringArray::Sort(void)
1173 {
1174   Sort(CompareCString, nsnull);
1175 }
1176
1177 #ifdef MOZILLA_INTERNAL_API
1178 void nsCStringArray::SortIgnoreCase(void)
1179 {
1180   Sort(CompareCStringIgnoreCase, nsnull);
1181 }
1182 #endif
1183
1184 void nsCStringArray::Sort(nsCStringArrayComparatorFunc aFunc, void* aData)
1185 {
1186   nsVoidArray::Sort(reinterpret_cast<nsVoidArrayComparatorFunc>(aFunc), aData);
1187 }
1188
1189 PRBool
1190 nsCStringArray::EnumerateForwards(nsCStringArrayEnumFunc aFunc, void* aData)
1191 {
1192   PRBool  running = PR_TRUE;
1193
1194   if (mImpl)
1195   {
1196     PRInt32 index = -1;
1197     while (running && (++index < mImpl->mCount))
1198     {
1199       running = (*aFunc)(*static_cast<nsCString*>(mImpl->mArray[index]), aData);
1200     }
1201   }
1202   return running;
1203 }
1204
1205 PRBool
1206 nsCStringArray::EnumerateBackwards(nsCStringArrayEnumFunc aFunc, void* aData)
1207 {
1208   PRBool  running = PR_TRUE;
1209
1210   if (mImpl)
1211   {
1212     PRInt32 index = Count();
1213     while (running && (0 <= --index))
1214     {
1215       running = (*aFunc)(*static_cast<nsCString*>(mImpl->mArray[index]), aData);
1216     }
1217   }
1218   return running;
1219 }
1220
1221
1222 //----------------------------------------------------------------------
1223 // NOTE: nsSmallVoidArray elements MUST all have the low bit as 0.
1224 // This means that normally it's only used for pointers, and in particular
1225 // structures or objects.
1226 nsSmallVoidArray::~nsSmallVoidArray()
1227 {
1228   if (HasSingle())
1229   {
1230     // Have to null out mImpl before the nsVoidArray dtor runs.
1231     mImpl = nsnull;
1232   }
1233 }
1234
1235 nsSmallVoidArray&
1236 nsSmallVoidArray::operator=(nsSmallVoidArray& other)
1237 {
1238   PRInt32 count = other.Count();
1239   switch (count) {
1240     case 0:
1241       Clear();
1242       break;
1243     case 1:
1244       Clear();
1245       AppendElement(other.ElementAt(0));
1246       break;
1247     default:
1248       if (GetArraySize() >= count || SizeTo(count)) {
1249         *AsArray() = *other.AsArray();
1250       }
1251   }
1252
1253   return *this;
1254 }
1255
1256 PRInt32
1257 nsSmallVoidArray::GetArraySize() const
1258 {
1259   if (HasSingle()) {
1260     return 1;
1261   }
1262
1263   return AsArray()->GetArraySize();
1264 }
1265
1266 PRInt32
1267 nsSmallVoidArray::Count() const
1268 {
1269   if (HasSingle()) {
1270     return 1;
1271   }
1272
1273   return AsArray()->Count();
1274 }
1275
1276 void*
1277 nsSmallVoidArray::FastElementAt(PRInt32 aIndex) const
1278 {
1279   NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::FastElementAt: index out of range");
1280
1281   if (HasSingle()) {
1282     return GetSingle();
1283   }
1284
1285   return AsArray()->FastElementAt(aIndex);
1286 }
1287
1288 PRInt32
1289 nsSmallVoidArray::IndexOf(void* aPossibleElement) const
1290 {
1291   if (HasSingle()) {
1292     return aPossibleElement == GetSingle() ? 0 : -1;
1293   }
1294
1295   return AsArray()->IndexOf(aPossibleElement);
1296 }
1297
1298 PRBool
1299 nsSmallVoidArray::InsertElementAt(void* aElement, PRInt32 aIndex)
1300 {
1301   NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
1302                "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1303
1304   if (aIndex == 0 && IsEmpty()) {
1305     SetSingle(aElement);
1306
1307     return PR_TRUE;
1308   }
1309
1310   if (!EnsureArray()) {
1311     return PR_FALSE;
1312   }
1313
1314   return AsArray()->InsertElementAt(aElement, aIndex);
1315 }
1316
1317 PRBool nsSmallVoidArray::InsertElementsAt(const nsVoidArray &aOther, PRInt32 aIndex)
1318 {
1319 #ifdef DEBUG
1320   for (int i = 0; i < aOther.Count(); i++) {
1321     NS_ASSERTION(!(NS_PTR_TO_INT32(aOther.ElementAt(i)) & 0x1),
1322                  "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1323   }
1324 #endif
1325
1326   if (aIndex == 0 && IsEmpty() && aOther.Count() == 1) {
1327     SetSingle(aOther.FastElementAt(0));
1328
1329     return PR_TRUE;
1330   }
1331
1332   if (!EnsureArray()) {
1333     return PR_FALSE;
1334   }
1335
1336   return AsArray()->InsertElementsAt(aOther, aIndex);
1337 }
1338
1339 PRBool
1340 nsSmallVoidArray::ReplaceElementAt(void* aElement, PRInt32 aIndex)
1341 {
1342   NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
1343                "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1344
1345   if (aIndex == 0 && (IsEmpty() || HasSingle())) {
1346     SetSingle(aElement);
1347
1348     return PR_TRUE;
1349   }
1350
1351   if (!EnsureArray()) {
1352     return PR_FALSE;
1353   }
1354
1355   return AsArray()->ReplaceElementAt(aElement, aIndex);
1356 }
1357
1358 PRBool
1359 nsSmallVoidArray::AppendElement(void* aElement)
1360 {
1361   NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
1362                "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1363
1364   if (IsEmpty()) {
1365     SetSingle(aElement);
1366
1367     return PR_TRUE;
1368   }
1369
1370   if (!EnsureArray()) {
1371     return PR_FALSE;
1372   }
1373
1374   return AsArray()->AppendElement(aElement);
1375 }
1376
1377 PRBool
1378 nsSmallVoidArray::RemoveElement(void* aElement)
1379 {
1380   if (HasSingle()) {
1381     if (aElement == GetSingle()) {
1382       mImpl = nsnull;
1383       return PR_TRUE;
1384     }
1385
1386     return PR_FALSE;
1387   }
1388
1389   return AsArray()->RemoveElement(aElement);
1390 }
1391
1392 PRBool
1393 nsSmallVoidArray::RemoveElementAt(PRInt32 aIndex)
1394 {
1395   if (HasSingle()) {
1396     if (aIndex == 0) {
1397       mImpl = nsnull;
1398
1399       return PR_TRUE;
1400     }
1401
1402     return PR_FALSE;
1403   }
1404
1405   return AsArray()->RemoveElementAt(aIndex);
1406 }
1407
1408 PRBool
1409 nsSmallVoidArray::RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount)
1410 {
1411   if (HasSingle()) {
1412     if (aIndex == 0) {
1413       if (aCount > 0) {
1414         mImpl = nsnull;
1415       }
1416
1417       return PR_TRUE;
1418     }
1419
1420     return PR_FALSE;
1421   }
1422
1423   return AsArray()->RemoveElementsAt(aIndex, aCount);
1424 }
1425
1426 void
1427 nsSmallVoidArray::Clear()
1428 {
1429   if (HasSingle()) {
1430     mImpl = nsnull;
1431   }
1432   else {
1433     AsArray()->Clear();
1434   }
1435 }
1436
1437 PRBool
1438 nsSmallVoidArray::SizeTo(PRInt32 aMin)
1439 {
1440   if (!HasSingle()) {
1441     return AsArray()->SizeTo(aMin);
1442   }
1443
1444   if (aMin <= 0) {
1445     mImpl = nsnull;
1446
1447     return PR_TRUE;
1448   }
1449
1450   if (aMin == 1) {
1451     return PR_TRUE;
1452   }
1453
1454   void* single = GetSingle();
1455   mImpl = nsnull;
1456   if (!AsArray()->SizeTo(aMin)) {
1457     SetSingle(single);
1458
1459     return PR_FALSE;
1460   }
1461
1462   AsArray()->AppendElement(single);
1463
1464   return PR_TRUE;
1465 }
1466
1467 void
1468 nsSmallVoidArray::Compact()
1469 {
1470   if (!HasSingle()) {
1471     AsArray()->Compact();
1472   }
1473 }
1474
1475 void
1476 nsSmallVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
1477 {
1478   if (!HasSingle()) {
1479     AsArray()->Sort(aFunc,aData);
1480   }
1481 }
1482
1483 PRBool
1484 nsSmallVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
1485 {
1486   if (HasSingle()) {
1487     return (*aFunc)(GetSingle(), aData);
1488   }
1489   return AsArray()->EnumerateForwards(aFunc,aData);
1490 }
1491
1492 PRBool
1493 nsSmallVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
1494 {
1495   if (HasSingle()) {
1496     return (*aFunc)(GetSingle(), aData);
1497   }
1498   return AsArray()->EnumerateBackwards(aFunc,aData);
1499 }
1500
1501 PRBool
1502 nsSmallVoidArray::EnsureArray()
1503 {
1504   if (!HasSingle()) {
1505     return PR_TRUE;
1506   }
1507
1508   void* single = GetSingle();
1509   mImpl = nsnull;
1510   if (!AsArray()->AppendElement(single)) {
1511     SetSingle(single);
1512
1513     return PR_FALSE;
1514   }
1515
1516   return PR_TRUE;
1517 }