xpcom/glue/nsVoidArray.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "mozilla/MathAlgorithms.h"
   8 #include "mozilla/MemoryReporting.h"
   9 #include <stdlib.h>
  10
  11 #include "nsVoidArray.h"
  12 #include "nsQuickSort.h"
  13 #include "nsISupportsImpl.h" // for nsTraceRefcnt
  14 #include "nsAlgorithm.h"
  15
  16 /**
  17  * Grow the array by at least this many elements at a time.
  18  */
  19 static const int32_t kMinGrowArrayBy = 8;
  20 static const int32_t kMaxGrowArrayBy = 1024;
  21
  22 /**
  23  * This is the threshold (in bytes) of the mImpl struct, past which
  24  * we'll force the array to grow geometrically
  25  */
  26 static const int32_t kLinearThreshold = 24 * sizeof(void*);
  27
  28 /**
  29  * Compute the number of bytes requires for the mImpl struct that will
  30  * hold |n| elements.
  31  */
  32 #define SIZEOF_IMPL(n_) (sizeof(Impl) + sizeof(void *) * ((n_) - 1))
  33
  34 /**
  35  * Compute the number of elements that an mImpl struct of |n| bytes
  36  * will hold.
  37  */
  38 #define CAPACITYOF_IMPL(n_) ((((n_) - sizeof(Impl)) / sizeof(void *)) + 1)
  39
  40 #if DEBUG_VOIDARRAY
  41 #define MAXVOID 10
  42
  43 class VoidStats
  44 {
  45 public:
  46   VoidStats();
  47   ~VoidStats();
  48 };
  49
  50 static int sizesUsed; // number of the elements of the arrays used
  51 static int sizesAlloced[MAXVOID]; // sizes of the allocations.  sorted
  52 static int NumberOfSize[MAXVOID]; // number of this allocation size (1 per array)
  53 static int AllocedOfSize[MAXVOID]; // number of this allocation size (each size for array used)
  54 static int MaxAuto[MAXVOID];      // AutoArrays that maxed out at this size
  55 static int GrowInPlace[MAXVOID];  // arrays this size that grew in-place via realloc
  56
  57 // these are per-allocation
  58 static int MaxElements[2000];     // # of arrays that maxed out at each size.
  59
  60 // statistics macros
  61 #define ADD_TO_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
  62                                   { \
  63                                     if (sizesAlloced[i] == (int)(size)) \
  64                                     { ((x)[i])++; break; } \
  65                                   } \
  66                                   if (i >= sizesUsed && sizesUsed < MAXVOID) \
  67                                   { sizesAlloced[sizesUsed] = (size); \
  68                                     ((x)[sizesUsed++])++; break; \
  69                                   } \
  70                                 } while (0)
  71
  72 #define SUB_FROM_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
  73                                     { \
  74                                       if (sizesAlloced[i] == (int)(size)) \
  75                                       { ((x)[i])--; break; } \
  76                                     } \
  77                                   } while (0)
  78
  79
  80 VoidStats::VoidStats()
  81 {
  82   sizesUsed = 1;
  83   sizesAlloced[0] = 0;
  84 }
  85
  86 VoidStats::~VoidStats()
  87 {
  88   int i;
  89   for (i = 0; i < sizesUsed; ++i) {
  90     printf("Size %d:\n",sizesAlloced[i]);
  91     printf("\tNumber of VoidArrays this size (max):     %d\n",NumberOfSize[i]-MaxAuto[i]);
  92     printf("\tNumber of AutoVoidArrays this size (max): %d\n",MaxAuto[i]);
  93     printf("\tNumber of allocations this size (total):  %d\n",AllocedOfSize[i]);
  94     printf("\tNumber of GrowsInPlace this size (total): %d\n",GrowInPlace[i]);
  95   }
  96   printf("Max Size of VoidArray:\n");
  97   for (i = 0; i < (int)(sizeof(MaxElements) / sizeof(MaxElements[0])); ++i) {
  98     if (MaxElements[i]) {
  99       printf("\t%d: %d\n", i, MaxElements[i]);
 100     }
 101   }
 102 }
 103
 104 // Just so constructor/destructor's get called
 105 VoidStats gVoidStats;
 106 #endif
 107
 108 void
 109 nsVoidArray::SetArray(Impl* aNewImpl, int32_t aSize, int32_t aCount)
 110 {
 111   // old mImpl has been realloced and so we don't free/delete it
 112   NS_PRECONDITION(aNewImpl, "can't set size");
 113   mImpl = aNewImpl;
 114   mImpl->mCount = aCount;
 115   mImpl->mSize = aSize;
 116 }
 117
 118 // This does all allocation/reallocation of the array.
 119 // It also will compact down to N - good for things that might grow a lot
 120 // at times,  but usually are smaller, like JS deferred GC releases.
 121 bool
 122 nsVoidArray::SizeTo(int32_t aSize)
 123 {
 124   uint32_t oldsize = GetArraySize();
 125
 126   if (aSize == (int32_t)oldsize) {
 127     return true; // no change
 128   }
 129
 130   if (aSize <= 0) {
 131     // free the array if allocated
 132     if (mImpl) {
 133       free(reinterpret_cast<char*>(mImpl));
 134       mImpl = nullptr;
 135     }
 136     return true;
 137   }
 138
 139   if (mImpl) {
 140     // We currently own an array impl. Resize it appropriately.
 141     if (aSize < mImpl->mCount) {
 142       // XXX Note: we could also just resize to mCount
 143       return true;  // can't make it that small, ignore request
 144     }
 145
 146     char* bytes = (char*)realloc(mImpl, SIZEOF_IMPL(aSize));
 147     Impl* newImpl = reinterpret_cast<Impl*>(bytes);
 148     if (!newImpl) {
 149       return false;
 150     }
 151
 152 #if DEBUG_VOIDARRAY
 153     if (mImpl == newImpl) {
 154       ADD_TO_STATS(GrowInPlace, oldsize);
 155     }
 156     ADD_TO_STATS(AllocedOfSize, SIZEOF_IMPL(aSize));
 157     if (aSize > mMaxSize) {
 158       ADD_TO_STATS(NumberOfSize, SIZEOF_IMPL(aSize));
 159       if (oldsize) {
 160         SUB_FROM_STATS(NumberOfSize, oldsize);
 161       }
 162       mMaxSize = aSize;
 163       if (mIsAuto) {
 164         ADD_TO_STATS(MaxAuto, SIZEOF_IMPL(aSize));
 165         SUB_FROM_STATS(MaxAuto, oldsize);
 166       }
 167     }
 168 #endif
 169     SetArray(newImpl, aSize, newImpl->mCount);
 170     return true;
 171   }
 172
 173   if ((uint32_t)aSize < oldsize) {
 174     // No point in allocating if it won't free the current Impl anyway.
 175     return true;
 176   }
 177
 178   // just allocate an array
 179   // allocate the exact size requested
 180   char* bytes = (char*)malloc(SIZEOF_IMPL(aSize));
 181   Impl* newImpl = reinterpret_cast<Impl*>(bytes);
 182   if (!newImpl) {
 183     return false;
 184   }
 185
 186 #if DEBUG_VOIDARRAY
 187   ADD_TO_STATS(AllocedOfSize, SIZEOF_IMPL(aSize));
 188   if (aSize > mMaxSize) {
 189     ADD_TO_STATS(NumberOfSize, SIZEOF_IMPL(aSize));
 190     if (oldsize && !mImpl) {
 191       SUB_FROM_STATS(NumberOfSize, oldsize);
 192     }
 193     mMaxSize = aSize;
 194   }
 195 #endif
 196   if (mImpl) {
 197 #if DEBUG_VOIDARRAY
 198     ADD_TO_STATS(MaxAuto, SIZEOF_IMPL(aSize));
 199     SUB_FROM_STATS(MaxAuto, 0);
 200     SUB_FROM_STATS(NumberOfSize, 0);
 201     mIsAuto = true;
 202 #endif
 203     // We must be growing an nsAutoVoidArray - copy since we didn't
 204     // realloc.
 205     memcpy(newImpl->mArray, mImpl->mArray,
 206            mImpl->mCount * sizeof(mImpl->mArray[0]));
 207   }
 208
 209   SetArray(newImpl, aSize, mImpl ? mImpl->mCount : 0);
 210   // no memset; handled later in ReplaceElementAt if needed
 211   return true;
 212 }
 213
 214 bool
 215 nsVoidArray::GrowArrayBy(int32_t aGrowBy)
 216 {
 217   // We have to grow the array. Grow by kMinGrowArrayBy slots if we're
 218   // smaller than kLinearThreshold bytes, or a power of two if we're
 219   // larger.  This is much more efficient with most memory allocators,
 220   // especially if it's very large, or of the allocator is binned.
 221   if (aGrowBy < kMinGrowArrayBy) {
 222     aGrowBy = kMinGrowArrayBy;
 223   }
 224
 225   uint32_t newCapacity = GetArraySize() + aGrowBy;  // Minimum increase
 226   uint32_t newSize = SIZEOF_IMPL(newCapacity);
 227
 228   if (newSize >= (uint32_t)kLinearThreshold) {
 229     // newCount includes enough space for at least kMinGrowArrayBy new
 230     // slots. Select the next power-of-two size in bytes above or
 231     // equal to that.
 232     // Also, limit the increase in size to about a VM page or two.
 233     if (GetArraySize() >= kMaxGrowArrayBy) {
 234       newCapacity = GetArraySize() + XPCOM_MAX(kMaxGrowArrayBy, aGrowBy);
 235       newSize = SIZEOF_IMPL(newCapacity);
 236     } else {
 237       newSize = mozilla::CeilingLog2(newSize);
 238       newCapacity = CAPACITYOF_IMPL(1u << newSize);
 239     }
 240   }
 241   // frees old mImpl IF this succeeds
 242   if (!SizeTo(newCapacity)) {
 243     return false;
 244   }
 245
 246   return true;
 247 }
 248
 249 nsVoidArray::nsVoidArray()
 250   : mImpl(nullptr)
 251 {
 252   MOZ_COUNT_CTOR(nsVoidArray);
 253 #if DEBUG_VOIDARRAY
 254   mMaxCount = 0;
 255   mMaxSize = 0;
 256   mIsAuto = false;
 257   ADD_TO_STATS(NumberOfSize, 0);
 258   MaxElements[0]++;
 259 #endif
 260 }
 261
 262 nsVoidArray::nsVoidArray(int32_t aCount)
 263   : mImpl(nullptr)
 264 {
 265   MOZ_COUNT_CTOR(nsVoidArray);
 266 #if DEBUG_VOIDARRAY
 267   mMaxCount = 0;
 268   mMaxSize = 0;
 269   mIsAuto = false;
 270   MaxElements[0]++;
 271 #endif
 272   SizeTo(aCount);
 273 }
 274
 275 nsVoidArray&
 276 nsVoidArray::operator=(const nsVoidArray& aOther)
 277 {
 278   int32_t otherCount = aOther.Count();
 279   int32_t maxCount = GetArraySize();
 280   if (otherCount) {
 281     if (otherCount > maxCount) {
 282       // frees old mImpl IF this succeeds
 283       if (!GrowArrayBy(otherCount - maxCount)) {
 284         return *this;      // XXX The allocation failed - don't do anything
 285       }
 286
 287       memcpy(mImpl->mArray, aOther.mImpl->mArray,
 288              otherCount * sizeof(mImpl->mArray[0]));
 289       mImpl->mCount = otherCount;
 290     } else {
 291       // the old array can hold the new array
 292       memcpy(mImpl->mArray, aOther.mImpl->mArray,
 293              otherCount * sizeof(mImpl->mArray[0]));
 294       mImpl->mCount = otherCount;
 295       // if it shrank a lot, compact it anyways
 296       if ((otherCount * 2) < maxCount && maxCount > 100) {
 297         Compact();  // shrank by at least 50 entries
 298       }
 299     }
 300 #if DEBUG_VOIDARRAY
 301     if (mImpl->mCount > mMaxCount &&
 302         mImpl->mCount < (int32_t)(sizeof(MaxElements) / sizeof(MaxElements[0]))) {
 303       MaxElements[mImpl->mCount]++;
 304       MaxElements[mMaxCount]--;
 305       mMaxCount = mImpl->mCount;
 306     }
 307 #endif
 308   } else {
 309     // Why do we drop the buffer here when we don't in Clear()?
 310     SizeTo(0);
 311   }
 312
 313   return *this;
 314 }
 315
 316 nsVoidArray::~nsVoidArray()
 317 {
 318   MOZ_COUNT_DTOR(nsVoidArray);
 319   if (mImpl) {
 320     free(reinterpret_cast<char*>(mImpl));
 321   }
 322 }
 323
 324 bool
 325 nsVoidArray::SetCount(int32_t aNewCount)
 326 {
 327   NS_ASSERTION(aNewCount >= 0, "SetCount(negative index)");
 328   if (aNewCount < 0) {
 329     return false;
 330   }
 331
 332   if (aNewCount == 0) {
 333     Clear();
 334     return true;
 335   }
 336
 337   if (uint32_t(aNewCount) > uint32_t(GetArraySize())) {
 338     int32_t oldCount = Count();
 339     int32_t growDelta = aNewCount - oldCount;
 340
 341     // frees old mImpl IF this succeeds
 342     if (!GrowArrayBy(growDelta)) {
 343       return false;
 344     }
 345   }
 346
 347   if (aNewCount > mImpl->mCount) {
 348     // Make sure that new entries added to the array by this
 349     // SetCount are cleared to 0.  Some users of this assume that.
 350     // This code means we don't have to memset when we allocate an array.
 351     memset(&mImpl->mArray[mImpl->mCount], 0,
 352            (aNewCount - mImpl->mCount) * sizeof(mImpl->mArray[0]));
 353   }
 354
 355   mImpl->mCount = aNewCount;
 356
 357 #if DEBUG_VOIDARRAY
 358   if (mImpl->mCount > mMaxCount &&
 359       mImpl->mCount < (int32_t)(sizeof(MaxElements) / sizeof(MaxElements[0]))) {
 360     MaxElements[mImpl->mCount]++;
 361     MaxElements[mMaxCount]--;
 362     mMaxCount = mImpl->mCount;
 363   }
 364 #endif
 365
 366   return true;
 367 }
 368
 369 int32_t
 370 nsVoidArray::IndexOf(void* aPossibleElement) const
 371 {
 372   if (mImpl) {
 373     void** ap = mImpl->mArray;
 374     void** end = ap + mImpl->mCount;
 375     while (ap < end) {
 376       if (*ap == aPossibleElement) {
 377         return ap - mImpl->mArray;
 378       }
 379       ap++;
 380     }
 381   }
 382   return -1;
 383 }
 384
 385 bool
 386 nsVoidArray::InsertElementAt(void* aElement, int32_t aIndex)
 387 {
 388   int32_t oldCount = Count();
 389   NS_ASSERTION(aIndex >= 0, "InsertElementAt(negative index)");
 390   if (uint32_t(aIndex) > uint32_t(oldCount)) {
 391     // An invalid index causes the insertion to fail
 392     // Invalid indexes are ones that add more than one entry to the
 393     // array (i.e., they can append).
 394     return false;
 395   }
 396
 397   if (oldCount >= GetArraySize()) {
 398     if (!GrowArrayBy(1)) {
 399       return false;
 400     }
 401   }
 402   // else the array is already large enough
 403
 404   int32_t slide = oldCount - aIndex;
 405   if (0 != slide) {
 406     // Slide data over to make room for the insertion
 407     memmove(mImpl->mArray + aIndex + 1, mImpl->mArray + aIndex,
 408             slide * sizeof(mImpl->mArray[0]));
 409   }
 410
 411   mImpl->mArray[aIndex] = aElement;
 412   mImpl->mCount++;
 413
 414 #if DEBUG_VOIDARRAY
 415   if (mImpl->mCount > mMaxCount &&
 416       mImpl->mCount < (int32_t)(sizeof(MaxElements) / sizeof(MaxElements[0]))) {
 417     MaxElements[mImpl->mCount]++;
 418     MaxElements[mMaxCount]--;
 419     mMaxCount = mImpl->mCount;
 420   }
 421 #endif
 422
 423   return true;
 424 }
 425
 426 bool
 427 nsVoidArray::InsertElementsAt(const nsVoidArray& aOther, int32_t aIndex)
 428 {
 429   int32_t oldCount = Count();
 430   int32_t otherCount = aOther.Count();
 431
 432   NS_ASSERTION(aIndex >= 0, "InsertElementsAt(negative index)");
 433   if (uint32_t(aIndex) > uint32_t(oldCount)) {
 434     // An invalid index causes the insertion to fail
 435     // Invalid indexes are ones that are more than one entry past the end of
 436     // the array (i.e., they can append).
 437     return false;
 438   }
 439
 440   if (oldCount + otherCount > GetArraySize()) {
 441     if (!GrowArrayBy(otherCount)) {
 442       return false;
 443     }
 444   }
 445   // else the array is already large enough
 446
 447   int32_t slide = oldCount - aIndex;
 448   if (slide != 0) {
 449     // Slide data over to make room for the insertion
 450     memmove(mImpl->mArray + aIndex + otherCount, mImpl->mArray + aIndex,
 451             slide * sizeof(mImpl->mArray[0]));
 452   }
 453
 454   for (int32_t i = 0; i < otherCount; ++i) {
 455     // copy all the elements (destroys aIndex)
 456     mImpl->mArray[aIndex++] = aOther.mImpl->mArray[i];
 457     mImpl->mCount++;
 458   }
 459
 460 #if DEBUG_VOIDARRAY
 461   if (mImpl->mCount > mMaxCount &&
 462       mImpl->mCount < (int32_t)(sizeof(MaxElements) / sizeof(MaxElements[0]))) {
 463     MaxElements[mImpl->mCount]++;
 464     MaxElements[mMaxCount]--;
 465     mMaxCount = mImpl->mCount;
 466   }
 467 #endif
 468
 469   return true;
 470 }
 471
 472 bool
 473 nsVoidArray::ReplaceElementAt(void* aElement, int32_t aIndex)
 474 {
 475   NS_ASSERTION(aIndex >= 0, "ReplaceElementAt(negative index)");
 476   if (aIndex < 0) {
 477     return false;
 478   }
 479
 480   // Unlike InsertElementAt, ReplaceElementAt can implicitly add more
 481   // than just the one element to the array.
 482   if (uint32_t(aIndex) >= uint32_t(GetArraySize())) {
 483     int32_t oldCount = Count();
 484     int32_t requestedCount = aIndex + 1;
 485     int32_t growDelta = requestedCount - oldCount;
 486
 487     // frees old mImpl IF this succeeds
 488     if (!GrowArrayBy(growDelta)) {
 489       return false;
 490     }
 491   }
 492
 493   mImpl->mArray[aIndex] = aElement;
 494   if (aIndex >= mImpl->mCount) {
 495     // Make sure that any entries implicitly added to the array by this
 496     // ReplaceElementAt are cleared to 0.  Some users of this assume that.
 497     // This code means we don't have to memset when we allocate an array.
 498     if (aIndex > mImpl->mCount) { // note: not >=
 499       // For example, if mCount is 2, and we do a ReplaceElementAt for
 500       // element[5], then we need to set three entries ([2], [3], and [4])
 501       // to 0.
 502       memset(&mImpl->mArray[mImpl->mCount], 0,
 503              (aIndex - mImpl->mCount) * sizeof(mImpl->mArray[0]));
 504     }
 505
 506     mImpl->mCount = aIndex + 1;
 507
 508 #if DEBUG_VOIDARRAY
 509     if (mImpl->mCount > mMaxCount &&
 510         mImpl->mCount < (int32_t)(sizeof(MaxElements) / sizeof(MaxElements[0]))) {
 511       MaxElements[mImpl->mCount]++;
 512       MaxElements[mMaxCount]--;
 513       mMaxCount = mImpl->mCount;
 514     }
 515 #endif
 516   }
 517
 518   return true;
 519 }
 520
 521 // useful for doing LRU arrays
 522 bool
 523 nsVoidArray::MoveElement(int32_t aFrom, int32_t aTo)
 524 {
 525   void* tempElement;
 526
 527   if (aTo == aFrom) {
 528     return true;
 529   }
 530
 531   NS_ASSERTION(aTo >= 0 && aFrom >= 0, "MoveElement(negative index)");
 532   if (aTo >= Count() || aFrom >= Count()) {
 533     // can't extend the array when moving an element.  Also catches mImpl = null
 534     return false;
 535   }
 536   tempElement = mImpl->mArray[aFrom];
 537
 538   if (aTo < aFrom) {
 539     // Moving one element closer to the head; the elements inbetween move down
 540     memmove(mImpl->mArray + aTo + 1, mImpl->mArray + aTo,
 541             (aFrom - aTo) * sizeof(mImpl->mArray[0]));
 542     mImpl->mArray[aTo] = tempElement;
 543   } else { // already handled aFrom == aTo
 544     // Moving one element closer to the tail; the elements inbetween move up
 545     memmove(mImpl->mArray + aFrom, mImpl->mArray + aFrom + 1,
 546             (aTo - aFrom) * sizeof(mImpl->mArray[0]));
 547     mImpl->mArray[aTo] = tempElement;
 548   }
 549
 550   return true;
 551 }
 552
 553 void
 554 nsVoidArray::RemoveElementsAt(int32_t aIndex, int32_t aCount)
 555 {
 556   int32_t oldCount = Count();
 557   NS_ASSERTION(aIndex >= 0, "RemoveElementsAt(negative index)");
 558   if (uint32_t(aIndex) >= uint32_t(oldCount)) {
 559     return;
 560   }
 561   // Limit to available entries starting at aIndex
 562   if (aCount + aIndex > oldCount) {
 563     aCount = oldCount - aIndex;
 564   }
 565
 566   // We don't need to move any elements if we're removing the
 567   // last element in the array
 568   if (aIndex < (oldCount - aCount)) {
 569     memmove(mImpl->mArray + aIndex, mImpl->mArray + aIndex + aCount,
 570             (oldCount - (aIndex + aCount)) * sizeof(mImpl->mArray[0]));
 571   }
 572
 573   mImpl->mCount -= aCount;
 574   return;
 575 }
 576
 577 bool
 578 nsVoidArray::RemoveElement(void* aElement)
 579 {
 580   int32_t theIndex = IndexOf(aElement);
 581   if (theIndex != -1) {
 582     RemoveElementAt(theIndex);
 583     return true;
 584   }
 585
 586   return false;
 587 }
 588
 589 void
 590 nsVoidArray::Clear()
 591 {
 592   if (mImpl) {
 593     mImpl->mCount = 0;
 594   }
 595 }
 596
 597 void
 598 nsVoidArray::Compact()
 599 {
 600   if (mImpl) {
 601     // XXX NOTE: this is quite inefficient in many cases if we're only
 602     // compacting by a little, but some callers care more about memory use.
 603     int32_t count = Count();
 604     if (GetArraySize() > count) {
 605       SizeTo(Count());
 606     }
 607   }
 608 }
 609
 610 // Needed because we want to pass the pointer to the item in the array
 611 // to the comparator function, not a pointer to the pointer in the array.
 612 struct VoidArrayComparatorContext
 613 {
 614   nsVoidArrayComparatorFunc mComparatorFunc;
 615   void* mData;
 616 };
 617
 618 static int
 619 VoidArrayComparator(const void* aElement1, const void* aElement2, void* aData)
 620 {
 621   VoidArrayComparatorContext* ctx = static_cast<VoidArrayComparatorContext*>(aData);
 622   return (*ctx->mComparatorFunc)(*static_cast<void* const*>(aElement1),
 623                                  *static_cast<void* const*>(aElement2),
 624                                  ctx->mData);
 625 }
 626
 627 void
 628 nsVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
 629 {
 630   if (mImpl && mImpl->mCount > 1) {
 631     VoidArrayComparatorContext ctx = {aFunc, aData};
 632     NS_QuickSort(mImpl->mArray, mImpl->mCount, sizeof(mImpl->mArray[0]),
 633                  VoidArrayComparator, &ctx);
 634   }
 635 }
 636
 637 bool
 638 nsVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
 639 {
 640   int32_t index = -1;
 641   bool    running = true;
 642
 643   if (mImpl) {
 644     while (running && (++index < mImpl->mCount)) {
 645       running = (*aFunc)(mImpl->mArray[index], aData);
 646     }
 647   }
 648   return running;
 649 }
 650
 651 bool
 652 nsVoidArray::EnumerateForwards(nsVoidArrayEnumFuncConst aFunc,
 653                                void* aData) const
 654 {
 655   int32_t index = -1;
 656   bool    running = true;
 657
 658   if (mImpl) {
 659     while (running && (++index < mImpl->mCount)) {
 660       running = (*aFunc)(mImpl->mArray[index], aData);
 661     }
 662   }
 663   return running;
 664 }
 665
 666 bool
 667 nsVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
 668 {
 669   bool    running = true;
 670
 671   if (mImpl) {
 672     int32_t index = Count();
 673     while (running && (--index >= 0)) {
 674       running = (*aFunc)(mImpl->mArray[index], aData);
 675     }
 676   }
 677   return running;
 678 }
 679
 680 struct SizeOfElementIncludingThisData
 681 {
 682   size_t mSize;
 683   nsVoidArraySizeOfElementIncludingThisFunc mSizeOfElementIncludingThis;
 684   mozilla::MallocSizeOf mMallocSizeOf;
 685   void* mData;  // the arg passed by the user
 686 };
 687
 688 static bool
 689 SizeOfElementIncludingThisEnumerator(const void* aElement, void* aData)
 690 {
 691   SizeOfElementIncludingThisData* d = (SizeOfElementIncludingThisData*)aData;
 692   d->mSize += d->mSizeOfElementIncludingThis(aElement, d->mMallocSizeOf, d->mData);
 693   return true;
 694 }
 695
 696 size_t
 697 nsVoidArray::SizeOfExcludingThis(
 698   nsVoidArraySizeOfElementIncludingThisFunc aSizeOfElementIncludingThis,
 699   mozilla::MallocSizeOf aMallocSizeOf, void* aData) const
 700 {
 701   size_t n = 0;
 702   // Measure the element storage.
 703   if (mImpl) {
 704     n += aMallocSizeOf(mImpl);
 705   }
 706   // Measure things pointed to by the elements.
 707   if (aSizeOfElementIncludingThis) {
 708     SizeOfElementIncludingThisData data2 =
 709     { 0, aSizeOfElementIncludingThis, aMallocSizeOf, aData };
 710     EnumerateForwards(SizeOfElementIncludingThisEnumerator, &data2);
 711     n += data2.mSize;
 712   }
 713   return n;
 714 }
 715
 716 //----------------------------------------------------------------------
 717 // NOTE: nsSmallVoidArray elements MUST all have the low bit as 0.
 718 // This means that normally it's only used for pointers, and in particular
 719 // structures or objects.
 720 nsSmallVoidArray::~nsSmallVoidArray()
 721 {
 722   if (HasSingle()) {
 723     // Have to null out mImpl before the nsVoidArray dtor runs.
 724     mImpl = nullptr;
 725   }
 726 }
 727
 728 nsSmallVoidArray&
 729 nsSmallVoidArray::operator=(nsSmallVoidArray& aOther)
 730 {
 731   int32_t count = aOther.Count();
 732   switch (count) {
 733     case 0:
 734       Clear();
 735       break;
 736     case 1:
 737       Clear();
 738       AppendElement(aOther.ElementAt(0));
 739       break;
 740     default:
 741       if (GetArraySize() >= count || SizeTo(count)) {
 742         *AsArray() = *aOther.AsArray();
 743       }
 744   }
 745
 746   return *this;
 747 }
 748
 749 int32_t
 750 nsSmallVoidArray::GetArraySize() const
 751 {
 752   if (HasSingle()) {
 753     return 1;
 754   }
 755
 756   return AsArray()->GetArraySize();
 757 }
 758
 759 int32_t
 760 nsSmallVoidArray::Count() const
 761 {
 762   if (HasSingle()) {
 763     return 1;
 764   }
 765
 766   return AsArray()->Count();
 767 }
 768
 769 void*
 770 nsSmallVoidArray::FastElementAt(int32_t aIndex) const
 771 {
 772   NS_ASSERTION(aIndex >= 0 && aIndex < Count(),
 773                "nsSmallVoidArray::FastElementAt: index out of range");
 774
 775   if (HasSingle()) {
 776     return GetSingle();
 777   }
 778
 779   return AsArray()->FastElementAt(aIndex);
 780 }
 781
 782 int32_t
 783 nsSmallVoidArray::IndexOf(void* aPossibleElement) const
 784 {
 785   if (HasSingle()) {
 786     return aPossibleElement == GetSingle() ? 0 : -1;
 787   }
 788
 789   return AsArray()->IndexOf(aPossibleElement);
 790 }
 791
 792 bool
 793 nsSmallVoidArray::InsertElementAt(void* aElement, int32_t aIndex)
 794 {
 795   NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
 796                "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
 797
 798   if (aIndex == 0 && IsEmpty()) {
 799     SetSingle(aElement);
 800
 801     return true;
 802   }
 803
 804   if (!EnsureArray()) {
 805     return false;
 806   }
 807
 808   return AsArray()->InsertElementAt(aElement, aIndex);
 809 }
 810
 811 bool
 812 nsSmallVoidArray::InsertElementsAt(const nsVoidArray& aOther, int32_t aIndex)
 813 {
 814 #ifdef DEBUG
 815   for (int i = 0; i < aOther.Count(); ++i) {
 816     NS_ASSERTION(!(NS_PTR_TO_INT32(aOther.ElementAt(i)) & 0x1),
 817                  "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
 818   }
 819 #endif
 820
 821   if (aIndex == 0 && IsEmpty() && aOther.Count() == 1) {
 822     SetSingle(aOther.FastElementAt(0));
 823
 824     return true;
 825   }
 826
 827   if (!EnsureArray()) {
 828     return false;
 829   }
 830
 831   return AsArray()->InsertElementsAt(aOther, aIndex);
 832 }
 833
 834 bool
 835 nsSmallVoidArray::ReplaceElementAt(void* aElement, int32_t aIndex)
 836 {
 837   NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
 838                "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
 839
 840   if (aIndex == 0 && (IsEmpty() || HasSingle())) {
 841     SetSingle(aElement);
 842
 843     return true;
 844   }
 845
 846   if (!EnsureArray()) {
 847     return false;
 848   }
 849
 850   return AsArray()->ReplaceElementAt(aElement, aIndex);
 851 }
 852
 853 bool
 854 nsSmallVoidArray::AppendElement(void* aElement)
 855 {
 856   NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
 857                "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
 858
 859   if (IsEmpty()) {
 860     SetSingle(aElement);
 861
 862     return true;
 863   }
 864
 865   if (!EnsureArray()) {
 866     return false;
 867   }
 868
 869   return AsArray()->AppendElement(aElement);
 870 }
 871
 872 bool
 873 nsSmallVoidArray::RemoveElement(void* aElement)
 874 {
 875   if (HasSingle()) {
 876     if (aElement == GetSingle()) {
 877       mImpl = nullptr;
 878       return true;
 879     }
 880
 881     return false;
 882   }
 883
 884   return AsArray()->RemoveElement(aElement);
 885 }
 886
 887 void
 888 nsSmallVoidArray::RemoveElementAt(int32_t aIndex)
 889 {
 890   if (HasSingle()) {
 891     if (aIndex == 0) {
 892       mImpl = nullptr;
 893     }
 894
 895     return;
 896   }
 897
 898   AsArray()->RemoveElementAt(aIndex);
 899 }
 900
 901 void
 902 nsSmallVoidArray::RemoveElementsAt(int32_t aIndex, int32_t aCount)
 903 {
 904   if (HasSingle()) {
 905     if (aIndex == 0) {
 906       if (aCount > 0) {
 907         mImpl = nullptr;
 908       }
 909     }
 910
 911     return;
 912   }
 913
 914   AsArray()->RemoveElementsAt(aIndex, aCount);
 915 }
 916
 917 void
 918 nsSmallVoidArray::Clear()
 919 {
 920   if (HasSingle()) {
 921     mImpl = nullptr;
 922   } else {
 923     AsArray()->Clear();
 924   }
 925 }
 926
 927 bool
 928 nsSmallVoidArray::SizeTo(int32_t aMin)
 929 {
 930   if (!HasSingle()) {
 931     return AsArray()->SizeTo(aMin);
 932   }
 933
 934   if (aMin <= 0) {
 935     mImpl = nullptr;
 936
 937     return true;
 938   }
 939
 940   if (aMin == 1) {
 941     return true;
 942   }
 943
 944   void* single = GetSingle();
 945   mImpl = nullptr;
 946   if (!AsArray()->SizeTo(aMin)) {
 947     SetSingle(single);
 948
 949     return false;
 950   }
 951
 952   AsArray()->AppendElement(single);
 953
 954   return true;
 955 }
 956
 957 void
 958 nsSmallVoidArray::Compact()
 959 {
 960   if (!HasSingle()) {
 961     AsArray()->Compact();
 962   }
 963 }
 964
 965 void
 966 nsSmallVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
 967 {
 968   if (!HasSingle()) {
 969     AsArray()->Sort(aFunc, aData);
 970   }
 971 }
 972
 973 bool
 974 nsSmallVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
 975 {
 976   if (HasSingle()) {
 977     return (*aFunc)(GetSingle(), aData);
 978   }
 979   return AsArray()->EnumerateForwards(aFunc, aData);
 980 }
 981
 982 bool
 983 nsSmallVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
 984 {
 985   if (HasSingle()) {
 986     return (*aFunc)(GetSingle(), aData);
 987   }
 988   return AsArray()->EnumerateBackwards(aFunc, aData);
 989 }
 990
 991 bool
 992 nsSmallVoidArray::EnsureArray()
 993 {
 994   if (!HasSingle()) {
 995     return true;
 996   }
 997
 998   void* single = GetSingle();
 999   mImpl = nullptr;
1000   if (!AsArray()->AppendElement(single)) {
1001     SetSingle(single);
1002
1003     return false;
1004   }
1005
1006   return true;
1007 }