xpcom/ds/nsSupportsArray.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this
   4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6 #include <string.h>
   7 #include "mozilla/MathAlgorithms.h"
   8 #include "nsSupportsArray.h"
   9 #include "nsSupportsArrayEnumerator.h"
  10 #include "nsIObjectInputStream.h"
  11 #include "nsIObjectOutputStream.h"
  12
  13 #if DEBUG_SUPPORTSARRAY
  14 #define MAXSUPPORTS 20
  15
  16 class SupportsStats
  17 {
  18 public:
  19   SupportsStats();
  20   ~SupportsStats();
  21
  22 };
  23
  24 static int sizesUsed; // number of the elements of the arrays used
  25 static int sizesAlloced[MAXSUPPORTS]; // sizes of the allocations.  sorted
  26 static int NumberOfSize[MAXSUPPORTS]; // number of this allocation size (1 per array)
  27 static int AllocedOfSize[MAXSUPPORTS]; // number of this allocation size (each size for array used)
  28 static int GrowInPlace[MAXSUPPORTS];
  29
  30 // these are per-allocation
  31 static int MaxElements[3000];
  32
  33 // very evil
  34 #define ADD_TO_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
  35                                   { \
  36                                     if (sizesAlloced[i] == (int)(size)) \
  37                                     { ((x)[i])++; break; } \
  38                                   } \
  39                                   if (i >= sizesUsed && sizesUsed < MAXSUPPORTS) \
  40                                   { sizesAlloced[sizesUsed] = (size); \
  41                                     ((x)[sizesUsed++])++; break; \
  42                                   } \
  43                                 } while (0);
  44
  45 #define SUB_FROM_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
  46                                     { \
  47                                       if (sizesAlloced[i] == (int)(size)) \
  48                                       { ((x)[i])--; break; } \
  49                                     } \
  50                                   } while (0);
  51
  52
  53 SupportsStats::SupportsStats()
  54 {
  55   sizesUsed = 1;
  56   sizesAlloced[0] = 0;
  57 }
  58
  59 SupportsStats::~SupportsStats()
  60 {
  61   int i;
  62   for (i = 0; i < sizesUsed; ++i) {
  63     printf("Size %d:\n", sizesAlloced[i]);
  64     printf("\tNumber of SupportsArrays this size (max):     %d\n", NumberOfSize[i]);
  65     printf("\tNumber of allocations this size (total):  %d\n", AllocedOfSize[i]);
  66     printf("\tNumber of GrowsInPlace this size (total): %d\n", GrowInPlace[i]);
  67   }
  68   printf("Max Size of SupportsArray:\n");
  69   for (i = 0; i < (int)(sizeof(MaxElements) / sizeof(MaxElements[0])); ++i) {
  70     if (MaxElements[i]) {
  71       printf("\t%d: %d\n", i, MaxElements[i]);
  72     }
  73   }
  74 }
  75
  76 // Just so constructor/destructor get called
  77 SupportsStats gSupportsStats;
  78 #endif
  79
  80 nsresult
  81 nsQueryElementAt::operator()(const nsIID& aIID, void** aResult) const
  82 {
  83   nsresult status =
  84     mCollection ? mCollection->QueryElementAt(mIndex, aIID, aResult) :
  85                   NS_ERROR_NULL_POINTER;
  86
  87   if (mErrorPtr) {
  88     *mErrorPtr = status;
  89   }
  90
  91   return status;
  92 }
  93
  94 static const int32_t kGrowArrayBy = 8;
  95 static const int32_t kLinearThreshold = 16 * sizeof(nsISupports*);
  96
  97 nsSupportsArray::nsSupportsArray()
  98 {
  99   mArray = mAutoArray;
 100   mArraySize = kAutoArraySize;
 101   mCount = 0;
 102 #if DEBUG_SUPPORTSARRAY
 103   mMaxCount = 0;
 104   mMaxSize = 0;
 105   ADD_TO_STATS(NumberOfSize, kAutoArraySize * sizeof(mArray[0]));
 106   MaxElements[0]++;
 107 #endif
 108 }
 109
 110 nsSupportsArray::~nsSupportsArray()
 111 {
 112   DeleteArray();
 113 }
 114
 115 void
 116 nsSupportsArray::GrowArrayBy(int32_t aGrowBy)
 117 {
 118   // We have to grow the array. Grow by kGrowArrayBy slots if we're smaller
 119   // than kLinearThreshold bytes, or a power of two if we're larger.
 120   // This is much more efficient with most memory allocators, especially
 121   // if it's very large, or of the allocator is binned.
 122   if (aGrowBy < kGrowArrayBy) {
 123     aGrowBy = kGrowArrayBy;
 124   }
 125
 126   uint32_t newCount = mArraySize + aGrowBy;  // Minimum increase
 127   uint32_t newSize = sizeof(mArray[0]) * newCount;
 128
 129   if (newSize >= (uint32_t)kLinearThreshold) {
 130     // newCount includes enough space for at least kGrowArrayBy new slots.
 131     // Select the next power-of-two size in bytes above that if newSize is
 132     // not a power of two.
 133     if (newSize & (newSize - 1)) {
 134       newSize = 1u << mozilla::CeilingLog2(newSize);
 135     }
 136
 137     newCount = newSize / sizeof(mArray[0]);
 138   }
 139   // XXX This would be far more efficient in many allocators if we used
 140   // XXX PR_Realloc(), etc
 141   nsISupports** oldArray = mArray;
 142
 143   mArray = new nsISupports*[newCount];
 144   mArraySize = newCount;
 145
 146 #if DEBUG_SUPPORTSARRAY
 147   if (oldArray == mArray) { // can't happen without use of realloc
 148     ADD_TO_STATS(GrowInPlace, mCount);
 149   }
 150   ADD_TO_STATS(AllocedOfSize, mArraySize * sizeof(mArray[0]));
 151   if (mArraySize > mMaxSize) {
 152     ADD_TO_STATS(NumberOfSize, mArraySize * sizeof(mArray[0]));
 153     if (oldArray != &(mAutoArray[0])) {
 154       SUB_FROM_STATS(NumberOfSize, mCount * sizeof(mArray[0]));
 155     }
 156     mMaxSize = mArraySize;
 157   }
 158 #endif
 159   if (oldArray) {                   // need to move old data
 160     if (0 < mCount) {
 161       ::memcpy(mArray, oldArray, mCount * sizeof(nsISupports*));
 162     }
 163     if (oldArray != &(mAutoArray[0])) {
 164       delete[] oldArray;
 165     }
 166   }
 167 }
 168
 169 nsresult
 170 nsSupportsArray::Create(nsISupports* aOuter, REFNSIID aIID, void** aResult)
 171 {
 172   if (aOuter) {
 173     return NS_ERROR_NO_AGGREGATION;
 174   }
 175
 176   nsCOMPtr<nsISupportsArray> it = new nsSupportsArray();
 177
 178   return it->QueryInterface(aIID, aResult);
 179 }
 180
 181 NS_IMPL_ISUPPORTS(nsSupportsArray, nsISupportsArray, nsICollection,
 182                   nsISerializable)
 183
 184 NS_IMETHODIMP
 185 nsSupportsArray::Read(nsIObjectInputStream* aStream)
 186 {
 187   nsresult rv;
 188
 189   uint32_t newArraySize;
 190   rv = aStream->Read32(&newArraySize);
 191
 192   if (newArraySize <= kAutoArraySize) {
 193     if (mArray != mAutoArray) {
 194       delete[] mArray;
 195       mArray = mAutoArray;
 196     }
 197     newArraySize = kAutoArraySize;
 198   } else {
 199     if (newArraySize <= mArraySize) {
 200       // Keep non-default-size mArray, it's more than big enough.
 201       newArraySize = mArraySize;
 202     } else {
 203       nsISupports** array = new nsISupports*[newArraySize];
 204       if (mArray != mAutoArray) {
 205         delete[] mArray;
 206       }
 207       mArray = array;
 208     }
 209   }
 210   mArraySize = newArraySize;
 211
 212   rv = aStream->Read32(&mCount);
 213   if (NS_FAILED(rv)) {
 214     return rv;
 215   }
 216
 217   NS_ASSERTION(mCount <= mArraySize, "overlarge mCount!");
 218   if (mCount > mArraySize) {
 219     mCount = mArraySize;
 220   }
 221
 222   for (uint32_t i = 0; i < mCount; i++) {
 223     rv = aStream->ReadObject(true, &mArray[i]);
 224     if (NS_FAILED(rv)) {
 225       return rv;
 226     }
 227   }
 228
 229   return NS_OK;
 230 }
 231
 232 NS_IMETHODIMP
 233 nsSupportsArray::Write(nsIObjectOutputStream* aStream)
 234 {
 235   nsresult rv;
 236
 237   rv = aStream->Write32(mArraySize);
 238   if (NS_FAILED(rv)) {
 239     return rv;
 240   }
 241
 242   rv = aStream->Write32(mCount);
 243   if (NS_FAILED(rv)) {
 244     return rv;
 245   }
 246
 247   for (uint32_t i = 0; i < mCount; i++) {
 248     rv = aStream->WriteObject(mArray[i], true);
 249     if (NS_FAILED(rv)) {
 250       return rv;
 251     }
 252   }
 253
 254   return NS_OK;
 255 }
 256
 257 void
 258 nsSupportsArray::DeleteArray(void)
 259 {
 260   Clear();
 261   if (mArray != &(mAutoArray[0])) {
 262     delete[] mArray;
 263     mArray = mAutoArray;
 264     mArraySize = kAutoArraySize;
 265   }
 266 }
 267
 268
 269 NS_IMETHODIMP_(bool)
 270 nsSupportsArray::Equals(const nsISupportsArray* aOther)
 271 {
 272   if (aOther) {
 273     uint32_t countOther;
 274     nsISupportsArray* other = const_cast<nsISupportsArray*>(aOther);
 275     nsresult rv = other->Count(&countOther);
 276     if (NS_FAILED(rv)) {
 277       return false;
 278     }
 279
 280     if (mCount == countOther) {
 281       uint32_t index = mCount;
 282       nsCOMPtr<nsISupports> otherElem;
 283       while (index--) {
 284         if (NS_FAILED(other->GetElementAt(index, getter_AddRefs(otherElem)))) {
 285           return false;
 286         }
 287         if (mArray[index] != otherElem) {
 288           return false;
 289         }
 290       }
 291       return true;
 292     }
 293   }
 294   return false;
 295 }
 296
 297 NS_IMETHODIMP
 298 nsSupportsArray::GetElementAt(uint32_t aIndex, nsISupports** aOutPtr)
 299 {
 300   *aOutPtr = nullptr;
 301   if (aIndex < mCount) {
 302     NS_IF_ADDREF(*aOutPtr = mArray[aIndex]);
 303   }
 304   return NS_OK;
 305 }
 306
 307 NS_IMETHODIMP_(int32_t)
 308 nsSupportsArray::IndexOf(const nsISupports* aPossibleElement)
 309 {
 310   return IndexOfStartingAt(aPossibleElement, 0);
 311 }
 312
 313 NS_IMETHODIMP_(int32_t)
 314 nsSupportsArray::IndexOfStartingAt(const nsISupports* aPossibleElement,
 315                                    uint32_t aStartIndex)
 316 {
 317   if (aStartIndex < mCount) {
 318     const nsISupports** start = (const nsISupports**)mArray;  // work around goofy compiler behavior
 319     const nsISupports** ep = (start + aStartIndex);
 320     const nsISupports** end = (start + mCount);
 321     while (ep < end) {
 322       if (aPossibleElement == *ep) {
 323         return (ep - start);
 324       }
 325       ep++;
 326     }
 327   }
 328   return -1;
 329 }
 330
 331 NS_IMETHODIMP_(int32_t)
 332 nsSupportsArray::LastIndexOf(const nsISupports* aPossibleElement)
 333 {
 334   if (0 < mCount) {
 335     const nsISupports** start = (const nsISupports**)mArray;  // work around goofy compiler behavior
 336     const nsISupports** ep = (start + mCount);
 337     while (start <= --ep) {
 338       if (aPossibleElement == *ep) {
 339         return (ep - start);
 340       }
 341     }
 342   }
 343   return -1;
 344 }
 345
 346 NS_IMETHODIMP_(bool)
 347 nsSupportsArray::InsertElementAt(nsISupports* aElement, uint32_t aIndex)
 348 {
 349   if (aIndex <= mCount) {
 350     if (mArraySize < (mCount + 1)) {
 351       // need to grow the array
 352       GrowArrayBy(1);
 353     }
 354
 355     // Could be slightly more efficient if GrowArrayBy knew about the
 356     // split, but the difference is trivial.
 357     uint32_t slide = (mCount - aIndex);
 358     if (0 < slide) {
 359       ::memmove(mArray + aIndex + 1, mArray + aIndex,
 360                 slide * sizeof(nsISupports*));
 361     }
 362
 363     mArray[aIndex] = aElement;
 364     NS_IF_ADDREF(aElement);
 365     mCount++;
 366
 367 #if DEBUG_SUPPORTSARRAY
 368     if (mCount > mMaxCount &&
 369         mCount < (int32_t)(sizeof(MaxElements) / sizeof(MaxElements[0]))) {
 370       MaxElements[mCount]++;
 371       MaxElements[mMaxCount]--;
 372       mMaxCount = mCount;
 373     }
 374 #endif
 375     return true;
 376   }
 377   return false;
 378 }
 379
 380 NS_IMETHODIMP_(bool)
 381 nsSupportsArray::InsertElementsAt(nsISupportsArray* aElements, uint32_t aIndex)
 382 {
 383   if (!aElements) {
 384     return false;
 385   }
 386   uint32_t countElements;
 387   if (NS_FAILED(aElements->Count(&countElements))) {
 388     return false;
 389   }
 390
 391   if (aIndex <= mCount) {
 392     if (mArraySize < (mCount + countElements)) {
 393       // need to grow the array
 394       GrowArrayBy(countElements);
 395     }
 396
 397     // Could be slightly more efficient if GrowArrayBy knew about the
 398     // split, but the difference is trivial.
 399     uint32_t slide = (mCount - aIndex);
 400     if (0 < slide) {
 401       ::memmove(mArray + aIndex + countElements, mArray + aIndex,
 402                 slide * sizeof(nsISupports*));
 403     }
 404
 405     for (uint32_t i = 0; i < countElements; ++i, ++mCount) {
 406       // use GetElementAt to copy and do AddRef for us
 407       if (NS_FAILED(aElements->GetElementAt(i, mArray + aIndex + i))) {
 408         return false;
 409       }
 410     }
 411
 412 #if DEBUG_SUPPORTSARRAY
 413     if (mCount > mMaxCount &&
 414         mCount < (int32_t)(sizeof(MaxElements) / sizeof(MaxElements[0]))) {
 415       MaxElements[mCount]++;
 416       MaxElements[mMaxCount]--;
 417       mMaxCount = mCount;
 418     }
 419 #endif
 420     return true;
 421   }
 422   return false;
 423 }
 424
 425 NS_IMETHODIMP_(bool)
 426 nsSupportsArray::ReplaceElementAt(nsISupports* aElement, uint32_t aIndex)
 427 {
 428   if (aIndex < mCount) {
 429     NS_IF_ADDREF(aElement);  // addref first in case it's the same object!
 430     NS_IF_RELEASE(mArray[aIndex]);
 431     mArray[aIndex] = aElement;
 432     return true;
 433   }
 434   return false;
 435 }
 436
 437 NS_IMETHODIMP_(bool)
 438 nsSupportsArray::RemoveElementsAt(uint32_t aIndex, uint32_t aCount)
 439 {
 440   if (aIndex + aCount <= mCount) {
 441     for (uint32_t i = 0; i < aCount; i++) {
 442       NS_IF_RELEASE(mArray[aIndex + i]);
 443     }
 444     mCount -= aCount;
 445     int32_t slide = (mCount - aIndex);
 446     if (0 < slide) {
 447       ::memmove(mArray + aIndex, mArray + aIndex + aCount,
 448                 slide * sizeof(nsISupports*));
 449     }
 450     return true;
 451   }
 452   return false;
 453 }
 454
 455 NS_IMETHODIMP_(bool)
 456 nsSupportsArray::RemoveElement(const nsISupports* aElement, uint32_t aStartIndex)
 457 {
 458   int32_t theIndex = IndexOfStartingAt(aElement, aStartIndex);
 459   if (theIndex >= 0) {
 460     return RemoveElementAt(theIndex);
 461   }
 462
 463   return false;
 464 }
 465
 466 NS_IMETHODIMP_(bool)
 467 nsSupportsArray::RemoveLastElement(const nsISupports* aElement)
 468 {
 469   int32_t theIndex = LastIndexOf(aElement);
 470   if (theIndex >= 0) {
 471     return RemoveElementAt(theIndex);
 472   }
 473
 474   return false;
 475 }
 476
 477 NS_IMETHODIMP_(bool)
 478 nsSupportsArray::MoveElement(int32_t aFrom, int32_t aTo)
 479 {
 480   nsISupports* tempElement;
 481
 482   if (aTo == aFrom) {
 483     return true;
 484   }
 485
 486   if (aTo < 0 || aFrom < 0 ||
 487       (uint32_t)aTo >= mCount || (uint32_t)aFrom >= mCount) {
 488     // can't extend the array when moving an element.  Also catches mImpl = null
 489     return false;
 490   }
 491   tempElement = mArray[aFrom];
 492
 493   if (aTo < aFrom) {
 494     // Moving one element closer to the head; the elements inbetween move down
 495     ::memmove(mArray + aTo + 1, mArray + aTo,
 496               (aFrom - aTo) * sizeof(mArray[0]));
 497     mArray[aTo] = tempElement;
 498   } else { // already handled aFrom == aTo
 499     // Moving one element closer to the tail; the elements inbetween move up
 500     ::memmove(mArray + aFrom, mArray + aFrom + 1,
 501               (aTo - aFrom) * sizeof(mArray[0]));
 502     mArray[aTo] = tempElement;
 503   }
 504
 505   return true;
 506 }
 507
 508 NS_IMETHODIMP
 509 nsSupportsArray::Clear(void)
 510 {
 511   if (0 < mCount) {
 512     do {
 513       --mCount;
 514       NS_IF_RELEASE(mArray[mCount]);
 515     } while (0 != mCount);
 516   }
 517   return NS_OK;
 518 }
 519
 520 NS_IMETHODIMP
 521 nsSupportsArray::Compact(void)
 522 {
 523 #if DEBUG_SUPPORTSARRAY
 524   uint32_t oldArraySize = mArraySize;
 525 #endif
 526   if ((mArraySize != mCount) && (kAutoArraySize < mArraySize)) {
 527     nsISupports** oldArray = mArray;
 528     if (mCount <= kAutoArraySize) {
 529       mArray = mAutoArray;
 530       mArraySize = kAutoArraySize;
 531     } else {
 532       mArray = new nsISupports*[mCount];
 533       if (!mArray) {
 534         mArray = oldArray;
 535         return NS_OK;
 536       }
 537       mArraySize = mCount;
 538     }
 539 #if DEBUG_SUPPORTSARRAY
 540     if (oldArray == mArray &&
 541         oldArray != &(mAutoArray[0])) { // can't happen without use of realloc
 542       ADD_TO_STATS(GrowInPlace, oldArraySize);
 543     }
 544     if (oldArray != &(mAutoArray[0])) {
 545       ADD_TO_STATS(AllocedOfSize, mArraySize * sizeof(mArray[0]));
 546     }
 547 #endif
 548     ::memcpy(mArray, oldArray, mCount * sizeof(nsISupports*));
 549     delete[] oldArray;
 550   }
 551   return NS_OK;
 552 }
 553
 554 NS_IMETHODIMP_(bool)
 555 nsSupportsArray::SizeTo(int32_t aSize)
 556 {
 557 #if DEBUG_SUPPORTSARRAY
 558   uint32_t oldArraySize = mArraySize;
 559 #endif
 560   NS_ASSERTION(aSize >= 0, "negative aSize!");
 561
 562   // XXX for aSize < mCount we could resize to mCount
 563   if (mArraySize == (uint32_t)aSize || (uint32_t)aSize < mCount) {
 564     return true;  // nothing to do
 565   }
 566
 567   // switch back to autoarray if possible
 568   nsISupports** oldArray = mArray;
 569   if ((uint32_t)aSize <= kAutoArraySize) {
 570     mArray = mAutoArray;
 571     mArraySize = kAutoArraySize;
 572   } else {
 573     mArray = new nsISupports*[aSize];
 574     if (!mArray) {
 575       mArray = oldArray;
 576       return false;
 577     }
 578     mArraySize = aSize;
 579   }
 580 #if DEBUG_SUPPORTSARRAY
 581   if (oldArray == mArray &&
 582       oldArray != &(mAutoArray[0])) { // can't happen without use of realloc
 583     ADD_TO_STATS(GrowInPlace, oldArraySize);
 584   }
 585   if (oldArray != &(mAutoArray[0])) {
 586     ADD_TO_STATS(AllocedOfSize, mArraySize * sizeof(mArray[0]));
 587   }
 588 #endif
 589   ::memcpy(mArray, oldArray, mCount * sizeof(nsISupports*));
 590   if (oldArray != mAutoArray) {
 591     delete[] oldArray;
 592   }
 593
 594   return true;
 595 }
 596
 597 NS_IMETHODIMP
 598 nsSupportsArray::Enumerate(nsIEnumerator** aResult)
 599 {
 600   nsSupportsArrayEnumerator* e = new nsSupportsArrayEnumerator(this);
 601   if (!e) {
 602     return NS_ERROR_OUT_OF_MEMORY;
 603   }
 604   *aResult = e;
 605   NS_ADDREF(e);
 606   return NS_OK;
 607 }
 608
 609 NS_IMETHODIMP
 610 nsSupportsArray::Clone(nsISupportsArray** aResult)
 611 {
 612   nsCOMPtr<nsISupportsArray> newArray;
 613   nsresult rv = NS_NewISupportsArray(getter_AddRefs(newArray));
 614   if (NS_WARN_IF(NS_FAILED(rv))) {
 615     return rv;
 616   }
 617
 618   uint32_t count = 0;
 619   Count(&count);
 620   for (uint32_t i = 0; i < count; i++) {
 621     if (!newArray->InsertElementAt(mArray[i], i)) {
 622       return NS_ERROR_OUT_OF_MEMORY;
 623     }
 624   }
 625
 626   newArray.forget(aResult);
 627   return NS_OK;
 628 }
 629
 630 nsresult
 631 NS_NewISupportsArray(nsISupportsArray** aInstancePtrResult)
 632 {
 633   nsresult rv;
 634   rv = nsSupportsArray::Create(nullptr, NS_GET_IID(nsISupportsArray),
 635                                (void**)aInstancePtrResult);
 636   return rv;
 637 }