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 static 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   if (this == &other)
 736   {
 737     return *this;
 738   }
 739
 740   // Free our strings
 741   Clear();
 742
 743   // Copy the pointers
 744   nsVoidArray::operator=(other);
 745
 746   // Now copy the strings
 747   PRInt32 count = Count();
 748   for (PRInt32 i = 0; i < count; ++i)
 749   {
 750     nsString* oldString = static_cast<nsString*>(other.ElementAt(i));
 751     nsString* newString = new nsString(*oldString);
 752     if (!newString)
 753     {
 754       mImpl->mCount = i;
 755       return *this;
 756     }
 757     mImpl->mArray[i] = newString;
 758   }
 759
 760   return *this;
 761 }
 762
 763 void
 764 nsStringArray::StringAt(PRInt32 aIndex, nsAString& aString) const
 765 {
 766   nsString* string = static_cast<nsString*>(nsVoidArray::ElementAt(aIndex));
 767   if (nsnull != string)
 768   {
 769     aString.Assign(*string);
 770   }
 771   else
 772   {
 773     aString.Truncate();
 774   }
 775 }
 776
 777 nsString*
 778 nsStringArray::StringAt(PRInt32 aIndex) const
 779 {
 780   return static_cast<nsString*>(nsVoidArray::ElementAt(aIndex));
 781 }
 782
 783 PRInt32
 784 nsStringArray::IndexOf(const nsAString& aPossibleString) const
 785 {
 786   if (mImpl)
 787   {
 788     void** ap = mImpl->mArray;
 789     void** end = ap + mImpl->mCount;
 790     while (ap < end)
 791     {
 792       nsString* string = static_cast<nsString*>(*ap);
 793       if (string->Equals(aPossibleString))
 794       {
 795         return ap - mImpl->mArray;
 796       }
 797       ap++;
 798     }
 799   }
 800   return -1;
 801 }
 802
 803 PRBool
 804 nsStringArray::InsertStringAt(const nsAString& aString, PRInt32 aIndex)
 805 {
 806   nsString* string = new nsString(aString);
 807   if (!string)
 808     return PR_FALSE;
 809   if (nsVoidArray::InsertElementAt(string, aIndex))
 810     return PR_TRUE;
 811
 812   delete string;
 813   return PR_FALSE;
 814 }
 815
 816 PRBool
 817 nsStringArray::ReplaceStringAt(const nsAString& aString,
 818                                PRInt32 aIndex)
 819 {
 820   nsString* string = static_cast<nsString*>(nsVoidArray::ElementAt(aIndex));
 821   if (nsnull != string)
 822   {
 823     *string = aString;
 824     return PR_TRUE;
 825   }
 826   return PR_FALSE;
 827 }
 828
 829 PRBool
 830 nsStringArray::RemoveString(const nsAString& aString)
 831 {
 832   PRInt32 index = IndexOf(aString);
 833   if (-1 < index)
 834   {
 835     return RemoveStringAt(index);
 836   }
 837   return PR_FALSE;
 838 }
 839
 840 PRBool nsStringArray::RemoveStringAt(PRInt32 aIndex)
 841 {
 842   nsString* string = StringAt(aIndex);
 843   if (nsnull != string)
 844   {
 845     nsVoidArray::RemoveElementAt(aIndex);
 846     delete string;
 847     return PR_TRUE;
 848   }
 849   return PR_FALSE;
 850 }
 851
 852 void
 853 nsStringArray::Clear(void)
 854 {
 855   PRInt32 index = Count();
 856   while (0 <= --index)
 857   {
 858     nsString* string = static_cast<nsString*>(mImpl->mArray[index]);
 859     delete string;
 860   }
 861   nsVoidArray::Clear();
 862 }
 863
 864 static int
 865 CompareString(const nsString* aString1, const nsString* aString2, void*)
 866 {
 867 #ifdef MOZILLA_INTERNAL_API
 868   return Compare(*aString1, *aString2);
 869 #else
 870   const PRUnichar* s1;
 871   const PRUnichar* s2;
 872   PRUint32 len1 = NS_StringGetData(*aString1, &s1);
 873   PRUint32 len2 = NS_StringGetData(*aString2, &s2);
 874   int r = memcmp(s1, s2, sizeof(PRUnichar) * PR_MIN(len1, len2));
 875   if (r)
 876     return r;
 877
 878   if (len1 < len2)
 879     return -1;
 880
 881   if (len1 > len2)
 882     return 1;
 883
 884   return 0;
 885 #endif
 886 }
 887
 888 void nsStringArray::Sort(void)
 889 {
 890   Sort(CompareString, nsnull);
 891 }
 892
 893 void nsStringArray::Sort(nsStringArrayComparatorFunc aFunc, void* aData)
 894 {
 895   nsVoidArray::Sort(reinterpret_cast<nsVoidArrayComparatorFunc>(aFunc), aData);
 896 }
 897
 898 PRBool
 899 nsStringArray::EnumerateForwards(nsStringArrayEnumFunc aFunc, void* aData)
 900 {
 901   PRInt32 index = -1;
 902   PRBool  running = PR_TRUE;
 903
 904   if (mImpl)
 905   {
 906     while (running && (++index < mImpl->mCount))
 907     {
 908       running = (*aFunc)(*static_cast<nsString*>(mImpl->mArray[index]), aData);
 909     }
 910   }
 911   return running;
 912 }
 913
 914 PRBool
 915 nsStringArray::EnumerateBackwards(nsStringArrayEnumFunc aFunc, void* aData)
 916 {
 917   PRInt32 index = Count();
 918   PRBool  running = PR_TRUE;
 919
 920   if (mImpl)
 921   {
 922     while (running && (0 <= --index))
 923     {
 924       running = (*aFunc)(*static_cast<nsString*>(mImpl->mArray[index]), aData);
 925     }
 926   }
 927   return running;
 928 }
 929
 930
 931
 932 //----------------------------------------------------------------
 933 // nsCStringArray
 934
 935 nsCStringArray::nsCStringArray(void)
 936   : nsVoidArray()
 937 {
 938 }
 939
 940 // Parses a given string using the delimiter passed in and appends items
 941 // parsed to the array.
 942 PRBool
 943 nsCStringArray::ParseString(const char* string, const char* delimiter)
 944 {
 945   if (string && *string && delimiter && *delimiter) {
 946     char *rest = strdup(string);
 947     if (!rest)
 948       return PR_FALSE;
 949     char *newStr = rest;
 950     char *token = NS_strtok(delimiter, &newStr);
 951
 952     PRInt32 count = Count();
 953     while (token) {
 954       if (*token) {
 955         /* calling AppendElement(void*) to avoid extra nsCString copy */
 956         nsCString *cstring = new nsCString(token);
 957         if (cstring && !AppendElement(cstring)) {
 958           // AppendElement failed, release and null cstring so we fall
 959           // through to the case below.
 960           delete cstring;
 961           cstring = nsnull;
 962         }
 963         if (!cstring) {
 964           // We've run out of memory. Remove all newly appended elements from
 965           // our array so we don't leave ourselves in a partially added state.
 966           // When we return, the array will be precisely as it was when this
 967           // function was called.
 968           RemoveElementsAt(count, Count() - count);
 969           free(rest);
 970           return PR_FALSE;
 971         }
 972       }
 973       token = NS_strtok(delimiter, &newStr);
 974     }
 975     free(rest);
 976   }
 977   return PR_TRUE;
 978 }
 979
 980 nsCStringArray::nsCStringArray(PRInt32 aCount)
 981   : nsVoidArray(aCount)
 982 {
 983 }
 984
 985 nsCStringArray::~nsCStringArray(void)
 986 {
 987   Clear();
 988 }
 989
 990 nsCStringArray&
 991 nsCStringArray::operator=(const nsCStringArray& other)
 992 {
 993   if (this == &other)
 994   {
 995     return *this;
 996   }
 997
 998   // Free our strings
 999   Clear();
1000
1001   // Copy the pointers
1002   nsVoidArray::operator=(other);
1003
1004   // Now copy the strings
1005   PRInt32 count = Count();
1006   for (PRInt32 i = 0; i < count; ++i)
1007   {
1008     nsCString* oldString = static_cast<nsCString*>(other.ElementAt(i));
1009     nsCString* newString = new nsCString(*oldString);
1010     if (!newString)
1011     {
1012       mImpl->mCount = i;
1013       return *this;
1014     }
1015     mImpl->mArray[i] = newString;
1016   }
1017
1018   return *this;
1019 }
1020
1021 void
1022 nsCStringArray::CStringAt(PRInt32 aIndex, nsACString& aCString) const
1023 {
1024   nsCString* string = static_cast<nsCString*>(nsVoidArray::ElementAt(aIndex));
1025   if (nsnull != string)
1026   {
1027     aCString = *string;
1028   }
1029   else
1030   {
1031     aCString.Truncate();
1032   }
1033 }
1034
1035 nsCString*
1036 nsCStringArray::CStringAt(PRInt32 aIndex) const
1037 {
1038   return static_cast<nsCString*>(nsVoidArray::ElementAt(aIndex));
1039 }
1040
1041 PRInt32
1042 nsCStringArray::IndexOf(const nsACString& aPossibleString) const
1043 {
1044   if (mImpl)
1045   {
1046     void** ap = mImpl->mArray;
1047     void** end = ap + mImpl->mCount;
1048     while (ap < end)
1049     {
1050       nsCString* string = static_cast<nsCString*>(*ap);
1051       if (string->Equals(aPossibleString))
1052       {
1053         return ap - mImpl->mArray;
1054       }
1055       ap++;
1056     }
1057   }
1058   return -1;
1059 }
1060
1061 #ifdef MOZILLA_INTERNAL_API
1062 PRInt32
1063 nsCStringArray::IndexOfIgnoreCase(const nsACString& aPossibleString) const
1064 {
1065   if (mImpl)
1066   {
1067     void** ap = mImpl->mArray;
1068     void** end = ap + mImpl->mCount;
1069     while (ap < end)
1070     {
1071       nsCString* string = static_cast<nsCString*>(*ap);
1072       if (string->Equals(aPossibleString, nsCaseInsensitiveCStringComparator()))
1073       {
1074         return ap - mImpl->mArray;
1075       }
1076       ap++;
1077     }
1078   }
1079   return -1;
1080 }
1081 #endif
1082
1083 PRBool
1084 nsCStringArray::InsertCStringAt(const nsACString& aCString, PRInt32 aIndex)
1085 {
1086   nsCString* string = new nsCString(aCString);
1087   if (!string)
1088     return PR_FALSE;
1089   if (nsVoidArray::InsertElementAt(string, aIndex))
1090     return PR_TRUE;
1091
1092   delete string;
1093   return PR_FALSE;
1094 }
1095
1096 PRBool
1097 nsCStringArray::ReplaceCStringAt(const nsACString& aCString, PRInt32 aIndex)
1098 {
1099   nsCString* string = static_cast<nsCString*>(nsVoidArray::ElementAt(aIndex));
1100   if (nsnull != string)
1101   {
1102     *string = aCString;
1103     return PR_TRUE;
1104   }
1105   return PR_FALSE;
1106 }
1107
1108 PRBool
1109 nsCStringArray::RemoveCString(const nsACString& aCString)
1110 {
1111   PRInt32 index = IndexOf(aCString);
1112   if (-1 < index)
1113   {
1114     return RemoveCStringAt(index);
1115   }
1116   return PR_FALSE;
1117 }
1118
1119 #ifdef MOZILLA_INTERNAL_API
1120 PRBool
1121 nsCStringArray::RemoveCStringIgnoreCase(const nsACString& aCString)
1122 {
1123   PRInt32 index = IndexOfIgnoreCase(aCString);
1124   if (-1 < index)
1125   {
1126     return RemoveCStringAt(index);
1127   }
1128   return PR_FALSE;
1129 }
1130 #endif
1131
1132 PRBool nsCStringArray::RemoveCStringAt(PRInt32 aIndex)
1133 {
1134   nsCString* string = CStringAt(aIndex);
1135   if (nsnull != string)
1136   {
1137     nsVoidArray::RemoveElementAt(aIndex);
1138     delete string;
1139     return PR_TRUE;
1140   }
1141   return PR_FALSE;
1142 }
1143
1144 void
1145 nsCStringArray::Clear(void)
1146 {
1147   PRInt32 index = Count();
1148   while (0 <= --index)
1149   {
1150     nsCString* string = static_cast<nsCString*>(mImpl->mArray[index]);
1151     delete string;
1152   }
1153   nsVoidArray::Clear();
1154 }
1155
1156 static int
1157 CompareCString(const nsCString* aCString1, const nsCString* aCString2, void*)
1158 {
1159 #ifdef MOZILLA_INTERNAL_API
1160   return Compare(*aCString1, *aCString2);
1161 #else
1162   const char* s1;
1163   const char* s2;
1164   PRUint32 len1 = NS_CStringGetData(*aCString1, &s1);
1165   PRUint32 len2 = NS_CStringGetData(*aCString2, &s2);
1166   int r = memcmp(s1, s2, PR_MIN(len1, len2));
1167   if (r)
1168     return r;
1169
1170   if (len1 < len2)
1171     return -1;
1172
1173   if (len1 > len2)
1174     return 1;
1175
1176   return 0;
1177 #endif
1178 }
1179
1180 #ifdef MOZILLA_INTERNAL_API
1181 static int
1182 CompareCStringIgnoreCase(const nsCString* aCString1, const nsCString* aCString2, void*)
1183 {
1184   return Compare(*aCString1, *aCString2, nsCaseInsensitiveCStringComparator());
1185 }
1186 #endif
1187
1188 void nsCStringArray::Sort(void)
1189 {
1190   Sort(CompareCString, nsnull);
1191 }
1192
1193 #ifdef MOZILLA_INTERNAL_API
1194 void nsCStringArray::SortIgnoreCase(void)
1195 {
1196   Sort(CompareCStringIgnoreCase, nsnull);
1197 }
1198 #endif
1199
1200 void nsCStringArray::Sort(nsCStringArrayComparatorFunc aFunc, void* aData)
1201 {
1202   nsVoidArray::Sort(reinterpret_cast<nsVoidArrayComparatorFunc>(aFunc), aData);
1203 }
1204
1205 PRBool
1206 nsCStringArray::EnumerateForwards(nsCStringArrayEnumFunc aFunc, void* aData)
1207 {
1208   PRBool  running = PR_TRUE;
1209
1210   if (mImpl)
1211   {
1212     PRInt32 index = -1;
1213     while (running && (++index < mImpl->mCount))
1214     {
1215       running = (*aFunc)(*static_cast<nsCString*>(mImpl->mArray[index]), aData);
1216     }
1217   }
1218   return running;
1219 }
1220
1221 PRBool
1222 nsCStringArray::EnumerateBackwards(nsCStringArrayEnumFunc aFunc, void* aData)
1223 {
1224   PRBool  running = PR_TRUE;
1225
1226   if (mImpl)
1227   {
1228     PRInt32 index = Count();
1229     while (running && (0 <= --index))
1230     {
1231       running = (*aFunc)(*static_cast<nsCString*>(mImpl->mArray[index]), aData);
1232     }
1233   }
1234   return running;
1235 }
1236
1237
1238 //----------------------------------------------------------------------
1239 // NOTE: nsSmallVoidArray elements MUST all have the low bit as 0.
1240 // This means that normally it's only used for pointers, and in particular
1241 // structures or objects.
1242 nsSmallVoidArray::~nsSmallVoidArray()
1243 {
1244   if (HasSingle())
1245   {
1246     // Have to null out mImpl before the nsVoidArray dtor runs.
1247     mImpl = nsnull;
1248   }
1249 }
1250
1251 nsSmallVoidArray&
1252 nsSmallVoidArray::operator=(nsSmallVoidArray& other)
1253 {
1254   PRInt32 count = other.Count();
1255   switch (count) {
1256     case 0:
1257       Clear();
1258       break;
1259     case 1:
1260       Clear();
1261       AppendElement(other.ElementAt(0));
1262       break;
1263     default:
1264       if (GetArraySize() >= count || SizeTo(count)) {
1265         *AsArray() = *other.AsArray();
1266       }
1267   }
1268
1269   return *this;
1270 }
1271
1272 PRInt32
1273 nsSmallVoidArray::GetArraySize() const
1274 {
1275   if (HasSingle()) {
1276     return 1;
1277   }
1278
1279   return AsArray()->GetArraySize();
1280 }
1281
1282 PRInt32
1283 nsSmallVoidArray::Count() const
1284 {
1285   if (HasSingle()) {
1286     return 1;
1287   }
1288
1289   return AsArray()->Count();
1290 }
1291
1292 void*
1293 nsSmallVoidArray::FastElementAt(PRInt32 aIndex) const
1294 {
1295   NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::FastElementAt: index out of range");
1296
1297   if (HasSingle()) {
1298     return GetSingle();
1299   }
1300
1301   return AsArray()->FastElementAt(aIndex);
1302 }
1303
1304 PRInt32
1305 nsSmallVoidArray::IndexOf(void* aPossibleElement) const
1306 {
1307   if (HasSingle()) {
1308     return aPossibleElement == GetSingle() ? 0 : -1;
1309   }
1310
1311   return AsArray()->IndexOf(aPossibleElement);
1312 }
1313
1314 PRBool
1315 nsSmallVoidArray::InsertElementAt(void* aElement, PRInt32 aIndex)
1316 {
1317   NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
1318                "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1319
1320   if (aIndex == 0 && IsEmpty()) {
1321     SetSingle(aElement);
1322
1323     return PR_TRUE;
1324   }
1325
1326   if (!EnsureArray()) {
1327     return PR_FALSE;
1328   }
1329
1330   return AsArray()->InsertElementAt(aElement, aIndex);
1331 }
1332
1333 PRBool nsSmallVoidArray::InsertElementsAt(const nsVoidArray &aOther, PRInt32 aIndex)
1334 {
1335 #ifdef DEBUG
1336   for (int i = 0; i < aOther.Count(); i++) {
1337     NS_ASSERTION(!(NS_PTR_TO_INT32(aOther.ElementAt(i)) & 0x1),
1338                  "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1339   }
1340 #endif
1341
1342   if (aIndex == 0 && IsEmpty() && aOther.Count() == 1) {
1343     SetSingle(aOther.FastElementAt(0));
1344
1345     return PR_TRUE;
1346   }
1347
1348   if (!EnsureArray()) {
1349     return PR_FALSE;
1350   }
1351
1352   return AsArray()->InsertElementsAt(aOther, aIndex);
1353 }
1354
1355 PRBool
1356 nsSmallVoidArray::ReplaceElementAt(void* aElement, PRInt32 aIndex)
1357 {
1358   NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
1359                "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1360
1361   if (aIndex == 0 && (IsEmpty() || HasSingle())) {
1362     SetSingle(aElement);
1363
1364     return PR_TRUE;
1365   }
1366
1367   if (!EnsureArray()) {
1368     return PR_FALSE;
1369   }
1370
1371   return AsArray()->ReplaceElementAt(aElement, aIndex);
1372 }
1373
1374 PRBool
1375 nsSmallVoidArray::AppendElement(void* aElement)
1376 {
1377   NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
1378                "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1379
1380   if (IsEmpty()) {
1381     SetSingle(aElement);
1382
1383     return PR_TRUE;
1384   }
1385
1386   if (!EnsureArray()) {
1387     return PR_FALSE;
1388   }
1389
1390   return AsArray()->AppendElement(aElement);
1391 }
1392
1393 PRBool
1394 nsSmallVoidArray::RemoveElement(void* aElement)
1395 {
1396   if (HasSingle()) {
1397     if (aElement == GetSingle()) {
1398       mImpl = nsnull;
1399       return PR_TRUE;
1400     }
1401
1402     return PR_FALSE;
1403   }
1404
1405   return AsArray()->RemoveElement(aElement);
1406 }
1407
1408 PRBool
1409 nsSmallVoidArray::RemoveElementAt(PRInt32 aIndex)
1410 {
1411   if (HasSingle()) {
1412     if (aIndex == 0) {
1413       mImpl = nsnull;
1414
1415       return PR_TRUE;
1416     }
1417
1418     return PR_FALSE;
1419   }
1420
1421   return AsArray()->RemoveElementAt(aIndex);
1422 }
1423
1424 PRBool
1425 nsSmallVoidArray::RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount)
1426 {
1427   if (HasSingle()) {
1428     if (aIndex == 0) {
1429       if (aCount > 0) {
1430         mImpl = nsnull;
1431       }
1432
1433       return PR_TRUE;
1434     }
1435
1436     return PR_FALSE;
1437   }
1438
1439   return AsArray()->RemoveElementsAt(aIndex, aCount);
1440 }
1441
1442 void
1443 nsSmallVoidArray::Clear()
1444 {
1445   if (HasSingle()) {
1446     mImpl = nsnull;
1447   }
1448   else {
1449     AsArray()->Clear();
1450   }
1451 }
1452
1453 PRBool
1454 nsSmallVoidArray::SizeTo(PRInt32 aMin)
1455 {
1456   if (!HasSingle()) {
1457     return AsArray()->SizeTo(aMin);
1458   }
1459
1460   if (aMin <= 0) {
1461     mImpl = nsnull;
1462
1463     return PR_TRUE;
1464   }
1465
1466   if (aMin == 1) {
1467     return PR_TRUE;
1468   }
1469
1470   void* single = GetSingle();
1471   mImpl = nsnull;
1472   if (!AsArray()->SizeTo(aMin)) {
1473     SetSingle(single);
1474
1475     return PR_FALSE;
1476   }
1477
1478   AsArray()->AppendElement(single);
1479
1480   return PR_TRUE;
1481 }
1482
1483 void
1484 nsSmallVoidArray::Compact()
1485 {
1486   if (!HasSingle()) {
1487     AsArray()->Compact();
1488   }
1489 }
1490
1491 void
1492 nsSmallVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
1493 {
1494   if (!HasSingle()) {
1495     AsArray()->Sort(aFunc,aData);
1496   }
1497 }
1498
1499 PRBool
1500 nsSmallVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
1501 {
1502   if (HasSingle()) {
1503     return (*aFunc)(GetSingle(), aData);
1504   }
1505   return AsArray()->EnumerateForwards(aFunc,aData);
1506 }
1507
1508 PRBool
1509 nsSmallVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
1510 {
1511   if (HasSingle()) {
1512     return (*aFunc)(GetSingle(), aData);
1513   }
1514   return AsArray()->EnumerateBackwards(aFunc,aData);
1515 }
1516
1517 PRBool
1518 nsSmallVoidArray::EnsureArray()
1519 {
1520   if (!HasSingle()) {
1521     return PR_TRUE;
1522   }
1523
1524   void* single = GetSingle();
1525   mImpl = nsnull;
1526   if (!AsArray()->AppendElement(single)) {
1527     SetSingle(single);
1528
1529     return PR_FALSE;
1530   }
1531
1532   return PR_TRUE;
1533 }