1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/nsVoidArray.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1022 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0)) -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "mozilla/MathAlgorithms.h"
1.10 +#include "mozilla/MemoryReporting.h"
1.11 +#include <stdlib.h>
1.12 +
1.13 +#include "nsVoidArray.h"
1.14 +#include "nsQuickSort.h"
1.15 +#include "nsISupportsImpl.h" // for nsTraceRefcnt
1.16 +#include "nsAlgorithm.h"
1.17 +
1.18 +/**
1.19 + * Grow the array by at least this many elements at a time.
1.20 + */
1.21 +static const int32_t kMinGrowArrayBy = 8;
1.22 +static const int32_t kMaxGrowArrayBy = 1024;
1.23 +
1.24 +/**
1.25 + * This is the threshold (in bytes) of the mImpl struct, past which
1.26 + * we'll force the array to grow geometrically
1.27 + */
1.28 +static const int32_t kLinearThreshold = 24 * sizeof(void *);
1.29 +
1.30 +/**
1.31 + * Compute the number of bytes requires for the mImpl struct that will
1.32 + * hold |n| elements.
1.33 + */
1.34 +#define SIZEOF_IMPL(n_) (sizeof(Impl) + sizeof(void *) * ((n_) - 1))
1.35 +
1.36 +/**
1.37 + * Compute the number of elements that an mImpl struct of |n| bytes
1.38 + * will hold.
1.39 + */
1.40 +#define CAPACITYOF_IMPL(n_) ((((n_) - sizeof(Impl)) / sizeof(void *)) + 1)
1.41 +
1.42 +#if DEBUG_VOIDARRAY
1.43 +#define MAXVOID 10
1.44 +
1.45 +class VoidStats {
1.46 +public:
1.47 + VoidStats();
1.48 + ~VoidStats();
1.49 +
1.50 +};
1.51 +
1.52 +static int sizesUsed; // number of the elements of the arrays used
1.53 +static int sizesAlloced[MAXVOID]; // sizes of the allocations. sorted
1.54 +static int NumberOfSize[MAXVOID]; // number of this allocation size (1 per array)
1.55 +static int AllocedOfSize[MAXVOID]; // number of this allocation size (each size for array used)
1.56 +static int MaxAuto[MAXVOID]; // AutoArrays that maxed out at this size
1.57 +static int GrowInPlace[MAXVOID]; // arrays this size that grew in-place via realloc
1.58 +
1.59 +// these are per-allocation
1.60 +static int MaxElements[2000]; // # of arrays that maxed out at each size.
1.61 +
1.62 +// statistics macros
1.63 +#define ADD_TO_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
1.64 + { \
1.65 + if (sizesAlloced[i] == (int)(size)) \
1.66 + { ((x)[i])++; break; } \
1.67 + } \
1.68 + if (i >= sizesUsed && sizesUsed < MAXVOID) \
1.69 + { sizesAlloced[sizesUsed] = (size); \
1.70 + ((x)[sizesUsed++])++; break; \
1.71 + } \
1.72 + } while (0)
1.73 +
1.74 +#define SUB_FROM_STATS(x,size) do {int i; for (i = 0; i < sizesUsed; i++) \
1.75 + { \
1.76 + if (sizesAlloced[i] == (int)(size)) \
1.77 + { ((x)[i])--; break; } \
1.78 + } \
1.79 + } while (0)
1.80 +
1.81 +
1.82 +VoidStats::VoidStats()
1.83 +{
1.84 + sizesUsed = 1;
1.85 + sizesAlloced[0] = 0;
1.86 +}
1.87 +
1.88 +VoidStats::~VoidStats()
1.89 +{
1.90 + int i;
1.91 + for (i = 0; i < sizesUsed; i++)
1.92 + {
1.93 + printf("Size %d:\n",sizesAlloced[i]);
1.94 + printf("\tNumber of VoidArrays this size (max): %d\n",NumberOfSize[i]-MaxAuto[i]);
1.95 + printf("\tNumber of AutoVoidArrays this size (max): %d\n",MaxAuto[i]);
1.96 + printf("\tNumber of allocations this size (total): %d\n",AllocedOfSize[i]);
1.97 + printf("\tNumber of GrowsInPlace this size (total): %d\n",GrowInPlace[i]);
1.98 + }
1.99 + printf("Max Size of VoidArray:\n");
1.100 + for (i = 0; i < (int)(sizeof(MaxElements)/sizeof(MaxElements[0])); i++)
1.101 + {
1.102 + if (MaxElements[i])
1.103 + printf("\t%d: %d\n",i,MaxElements[i]);
1.104 + }
1.105 +}
1.106 +
1.107 +// Just so constructor/destructor's get called
1.108 +VoidStats gVoidStats;
1.109 +#endif
1.110 +
1.111 +void
1.112 +nsVoidArray::SetArray(Impl *newImpl, int32_t aSize, int32_t aCount)
1.113 +{
1.114 + // old mImpl has been realloced and so we don't free/delete it
1.115 + NS_PRECONDITION(newImpl, "can't set size");
1.116 + mImpl = newImpl;
1.117 + mImpl->mCount = aCount;
1.118 + mImpl->mSize = aSize;
1.119 +}
1.120 +
1.121 +// This does all allocation/reallocation of the array.
1.122 +// It also will compact down to N - good for things that might grow a lot
1.123 +// at times, but usually are smaller, like JS deferred GC releases.
1.124 +bool nsVoidArray::SizeTo(int32_t aSize)
1.125 +{
1.126 + uint32_t oldsize = GetArraySize();
1.127 +
1.128 + if (aSize == (int32_t) oldsize)
1.129 + return true; // no change
1.130 +
1.131 + if (aSize <= 0)
1.132 + {
1.133 + // free the array if allocated
1.134 + if (mImpl)
1.135 + {
1.136 + free(reinterpret_cast<char *>(mImpl));
1.137 + mImpl = nullptr;
1.138 + }
1.139 + return true;
1.140 + }
1.141 +
1.142 + if (mImpl)
1.143 + {
1.144 + // We currently own an array impl. Resize it appropriately.
1.145 + if (aSize < mImpl->mCount)
1.146 + {
1.147 + // XXX Note: we could also just resize to mCount
1.148 + return true; // can't make it that small, ignore request
1.149 + }
1.150 +
1.151 + char* bytes = (char *) realloc(mImpl,SIZEOF_IMPL(aSize));
1.152 + Impl* newImpl = reinterpret_cast<Impl*>(bytes);
1.153 + if (!newImpl)
1.154 + return false;
1.155 +
1.156 +#if DEBUG_VOIDARRAY
1.157 + if (mImpl == newImpl)
1.158 + ADD_TO_STATS(GrowInPlace,oldsize);
1.159 + ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
1.160 + if (aSize > mMaxSize)
1.161 + {
1.162 + ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
1.163 + if (oldsize)
1.164 + SUB_FROM_STATS(NumberOfSize,oldsize);
1.165 + mMaxSize = aSize;
1.166 + if (mIsAuto)
1.167 + {
1.168 + ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
1.169 + SUB_FROM_STATS(MaxAuto,oldsize);
1.170 + }
1.171 + }
1.172 +#endif
1.173 + SetArray(newImpl, aSize, newImpl->mCount);
1.174 + return true;
1.175 + }
1.176 +
1.177 + if ((uint32_t) aSize < oldsize) {
1.178 + // No point in allocating if it won't free the current Impl anyway.
1.179 + return true;
1.180 + }
1.181 +
1.182 + // just allocate an array
1.183 + // allocate the exact size requested
1.184 + char* bytes = (char *) malloc(SIZEOF_IMPL(aSize));
1.185 + Impl* newImpl = reinterpret_cast<Impl*>(bytes);
1.186 + if (!newImpl)
1.187 + return false;
1.188 +
1.189 +#if DEBUG_VOIDARRAY
1.190 + ADD_TO_STATS(AllocedOfSize,SIZEOF_IMPL(aSize));
1.191 + if (aSize > mMaxSize)
1.192 + {
1.193 + ADD_TO_STATS(NumberOfSize,SIZEOF_IMPL(aSize));
1.194 + if (oldsize && !mImpl)
1.195 + SUB_FROM_STATS(NumberOfSize,oldsize);
1.196 + mMaxSize = aSize;
1.197 + }
1.198 +#endif
1.199 + if (mImpl)
1.200 + {
1.201 +#if DEBUG_VOIDARRAY
1.202 + ADD_TO_STATS(MaxAuto,SIZEOF_IMPL(aSize));
1.203 + SUB_FROM_STATS(MaxAuto,0);
1.204 + SUB_FROM_STATS(NumberOfSize,0);
1.205 + mIsAuto = true;
1.206 +#endif
1.207 + // We must be growing an nsAutoVoidArray - copy since we didn't
1.208 + // realloc.
1.209 + memcpy(newImpl->mArray, mImpl->mArray,
1.210 + mImpl->mCount * sizeof(mImpl->mArray[0]));
1.211 + }
1.212 +
1.213 + SetArray(newImpl, aSize, mImpl ? mImpl->mCount : 0);
1.214 + // no memset; handled later in ReplaceElementAt if needed
1.215 + return true;
1.216 +}
1.217 +
1.218 +bool nsVoidArray::GrowArrayBy(int32_t aGrowBy)
1.219 +{
1.220 + // We have to grow the array. Grow by kMinGrowArrayBy slots if we're
1.221 + // smaller than kLinearThreshold bytes, or a power of two if we're
1.222 + // larger. This is much more efficient with most memory allocators,
1.223 + // especially if it's very large, or of the allocator is binned.
1.224 + if (aGrowBy < kMinGrowArrayBy)
1.225 + aGrowBy = kMinGrowArrayBy;
1.226 +
1.227 + uint32_t newCapacity = GetArraySize() + aGrowBy; // Minimum increase
1.228 + uint32_t newSize = SIZEOF_IMPL(newCapacity);
1.229 +
1.230 + if (newSize >= (uint32_t) kLinearThreshold)
1.231 + {
1.232 + // newCount includes enough space for at least kMinGrowArrayBy new
1.233 + // slots. Select the next power-of-two size in bytes above or
1.234 + // equal to that.
1.235 + // Also, limit the increase in size to about a VM page or two.
1.236 + if (GetArraySize() >= kMaxGrowArrayBy)
1.237 + {
1.238 + newCapacity = GetArraySize() + XPCOM_MAX(kMaxGrowArrayBy,aGrowBy);
1.239 + newSize = SIZEOF_IMPL(newCapacity);
1.240 + }
1.241 + else
1.242 + {
1.243 + newSize = mozilla::CeilingLog2(newSize);
1.244 + newCapacity = CAPACITYOF_IMPL(1u << newSize);
1.245 + }
1.246 + }
1.247 + // frees old mImpl IF this succeeds
1.248 + if (!SizeTo(newCapacity))
1.249 + return false;
1.250 +
1.251 + return true;
1.252 +}
1.253 +
1.254 +nsVoidArray::nsVoidArray()
1.255 + : mImpl(nullptr)
1.256 +{
1.257 + MOZ_COUNT_CTOR(nsVoidArray);
1.258 +#if DEBUG_VOIDARRAY
1.259 + mMaxCount = 0;
1.260 + mMaxSize = 0;
1.261 + mIsAuto = false;
1.262 + ADD_TO_STATS(NumberOfSize,0);
1.263 + MaxElements[0]++;
1.264 +#endif
1.265 +}
1.266 +
1.267 +nsVoidArray::nsVoidArray(int32_t aCount)
1.268 + : mImpl(nullptr)
1.269 +{
1.270 + MOZ_COUNT_CTOR(nsVoidArray);
1.271 +#if DEBUG_VOIDARRAY
1.272 + mMaxCount = 0;
1.273 + mMaxSize = 0;
1.274 + mIsAuto = false;
1.275 + MaxElements[0]++;
1.276 +#endif
1.277 + SizeTo(aCount);
1.278 +}
1.279 +
1.280 +nsVoidArray& nsVoidArray::operator=(const nsVoidArray& other)
1.281 +{
1.282 + int32_t otherCount = other.Count();
1.283 + int32_t maxCount = GetArraySize();
1.284 + if (otherCount)
1.285 + {
1.286 + if (otherCount > maxCount)
1.287 + {
1.288 + // frees old mImpl IF this succeeds
1.289 + if (!GrowArrayBy(otherCount-maxCount))
1.290 + return *this; // XXX The allocation failed - don't do anything
1.291 +
1.292 + memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
1.293 + mImpl->mCount = otherCount;
1.294 + }
1.295 + else
1.296 + {
1.297 + // the old array can hold the new array
1.298 + memcpy(mImpl->mArray, other.mImpl->mArray, otherCount * sizeof(mImpl->mArray[0]));
1.299 + mImpl->mCount = otherCount;
1.300 + // if it shrank a lot, compact it anyways
1.301 + if ((otherCount*2) < maxCount && maxCount > 100)
1.302 + {
1.303 + Compact(); // shrank by at least 50 entries
1.304 + }
1.305 + }
1.306 +#if DEBUG_VOIDARRAY
1.307 + if (mImpl->mCount > mMaxCount &&
1.308 + mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
1.309 + {
1.310 + MaxElements[mImpl->mCount]++;
1.311 + MaxElements[mMaxCount]--;
1.312 + mMaxCount = mImpl->mCount;
1.313 + }
1.314 +#endif
1.315 + }
1.316 + else
1.317 + {
1.318 + // Why do we drop the buffer here when we don't in Clear()?
1.319 + SizeTo(0);
1.320 + }
1.321 +
1.322 + return *this;
1.323 +}
1.324 +
1.325 +nsVoidArray::~nsVoidArray()
1.326 +{
1.327 + MOZ_COUNT_DTOR(nsVoidArray);
1.328 + if (mImpl)
1.329 + free(reinterpret_cast<char*>(mImpl));
1.330 +}
1.331 +
1.332 +bool nsVoidArray::SetCount(int32_t aNewCount)
1.333 +{
1.334 + NS_ASSERTION(aNewCount >= 0,"SetCount(negative index)");
1.335 + if (aNewCount < 0)
1.336 + return false;
1.337 +
1.338 + if (aNewCount == 0)
1.339 + {
1.340 + Clear();
1.341 + return true;
1.342 + }
1.343 +
1.344 + if (uint32_t(aNewCount) > uint32_t(GetArraySize()))
1.345 + {
1.346 + int32_t oldCount = Count();
1.347 + int32_t growDelta = aNewCount - oldCount;
1.348 +
1.349 + // frees old mImpl IF this succeeds
1.350 + if (!GrowArrayBy(growDelta))
1.351 + return false;
1.352 + }
1.353 +
1.354 + if (aNewCount > mImpl->mCount)
1.355 + {
1.356 + // Make sure that new entries added to the array by this
1.357 + // SetCount are cleared to 0. Some users of this assume that.
1.358 + // This code means we don't have to memset when we allocate an array.
1.359 + memset(&mImpl->mArray[mImpl->mCount], 0,
1.360 + (aNewCount - mImpl->mCount) * sizeof(mImpl->mArray[0]));
1.361 + }
1.362 +
1.363 + mImpl->mCount = aNewCount;
1.364 +
1.365 +#if DEBUG_VOIDARRAY
1.366 + if (mImpl->mCount > mMaxCount &&
1.367 + mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
1.368 + {
1.369 + MaxElements[mImpl->mCount]++;
1.370 + MaxElements[mMaxCount]--;
1.371 + mMaxCount = mImpl->mCount;
1.372 + }
1.373 +#endif
1.374 +
1.375 + return true;
1.376 +}
1.377 +
1.378 +int32_t nsVoidArray::IndexOf(void* aPossibleElement) const
1.379 +{
1.380 + if (mImpl)
1.381 + {
1.382 + void** ap = mImpl->mArray;
1.383 + void** end = ap + mImpl->mCount;
1.384 + while (ap < end)
1.385 + {
1.386 + if (*ap == aPossibleElement)
1.387 + {
1.388 + return ap - mImpl->mArray;
1.389 + }
1.390 + ap++;
1.391 + }
1.392 + }
1.393 + return -1;
1.394 +}
1.395 +
1.396 +bool nsVoidArray::InsertElementAt(void* aElement, int32_t aIndex)
1.397 +{
1.398 + int32_t oldCount = Count();
1.399 + NS_ASSERTION(aIndex >= 0,"InsertElementAt(negative index)");
1.400 + if (uint32_t(aIndex) > uint32_t(oldCount))
1.401 + {
1.402 + // An invalid index causes the insertion to fail
1.403 + // Invalid indexes are ones that add more than one entry to the
1.404 + // array (i.e., they can append).
1.405 + return false;
1.406 + }
1.407 +
1.408 + if (oldCount >= GetArraySize())
1.409 + {
1.410 + if (!GrowArrayBy(1))
1.411 + return false;
1.412 + }
1.413 + // else the array is already large enough
1.414 +
1.415 + int32_t slide = oldCount - aIndex;
1.416 + if (0 != slide)
1.417 + {
1.418 + // Slide data over to make room for the insertion
1.419 + memmove(mImpl->mArray + aIndex + 1, mImpl->mArray + aIndex,
1.420 + slide * sizeof(mImpl->mArray[0]));
1.421 + }
1.422 +
1.423 + mImpl->mArray[aIndex] = aElement;
1.424 + mImpl->mCount++;
1.425 +
1.426 +#if DEBUG_VOIDARRAY
1.427 + if (mImpl->mCount > mMaxCount &&
1.428 + mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
1.429 + {
1.430 + MaxElements[mImpl->mCount]++;
1.431 + MaxElements[mMaxCount]--;
1.432 + mMaxCount = mImpl->mCount;
1.433 + }
1.434 +#endif
1.435 +
1.436 + return true;
1.437 +}
1.438 +
1.439 +bool nsVoidArray::InsertElementsAt(const nsVoidArray& other, int32_t aIndex)
1.440 +{
1.441 + int32_t oldCount = Count();
1.442 + int32_t otherCount = other.Count();
1.443 +
1.444 + NS_ASSERTION(aIndex >= 0,"InsertElementsAt(negative index)");
1.445 + if (uint32_t(aIndex) > uint32_t(oldCount))
1.446 + {
1.447 + // An invalid index causes the insertion to fail
1.448 + // Invalid indexes are ones that are more than one entry past the end of
1.449 + // the array (i.e., they can append).
1.450 + return false;
1.451 + }
1.452 +
1.453 + if (oldCount + otherCount > GetArraySize())
1.454 + {
1.455 + if (!GrowArrayBy(otherCount))
1.456 + return false;;
1.457 + }
1.458 + // else the array is already large enough
1.459 +
1.460 + int32_t slide = oldCount - aIndex;
1.461 + if (0 != slide)
1.462 + {
1.463 + // Slide data over to make room for the insertion
1.464 + memmove(mImpl->mArray + aIndex + otherCount, mImpl->mArray + aIndex,
1.465 + slide * sizeof(mImpl->mArray[0]));
1.466 + }
1.467 +
1.468 + for (int32_t i = 0; i < otherCount; i++)
1.469 + {
1.470 + // copy all the elements (destroys aIndex)
1.471 + mImpl->mArray[aIndex++] = other.mImpl->mArray[i];
1.472 + mImpl->mCount++;
1.473 + }
1.474 +
1.475 +#if DEBUG_VOIDARRAY
1.476 + if (mImpl->mCount > mMaxCount &&
1.477 + mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
1.478 + {
1.479 + MaxElements[mImpl->mCount]++;
1.480 + MaxElements[mMaxCount]--;
1.481 + mMaxCount = mImpl->mCount;
1.482 + }
1.483 +#endif
1.484 +
1.485 + return true;
1.486 +}
1.487 +
1.488 +bool nsVoidArray::ReplaceElementAt(void* aElement, int32_t aIndex)
1.489 +{
1.490 + NS_ASSERTION(aIndex >= 0,"ReplaceElementAt(negative index)");
1.491 + if (aIndex < 0)
1.492 + return false;
1.493 +
1.494 + // Unlike InsertElementAt, ReplaceElementAt can implicitly add more
1.495 + // than just the one element to the array.
1.496 + if (uint32_t(aIndex) >= uint32_t(GetArraySize()))
1.497 + {
1.498 + int32_t oldCount = Count();
1.499 + int32_t requestedCount = aIndex + 1;
1.500 + int32_t growDelta = requestedCount - oldCount;
1.501 +
1.502 + // frees old mImpl IF this succeeds
1.503 + if (!GrowArrayBy(growDelta))
1.504 + return false;
1.505 + }
1.506 +
1.507 + mImpl->mArray[aIndex] = aElement;
1.508 + if (aIndex >= mImpl->mCount)
1.509 + {
1.510 + // Make sure that any entries implicitly added to the array by this
1.511 + // ReplaceElementAt are cleared to 0. Some users of this assume that.
1.512 + // This code means we don't have to memset when we allocate an array.
1.513 + if (aIndex > mImpl->mCount) // note: not >=
1.514 + {
1.515 + // For example, if mCount is 2, and we do a ReplaceElementAt for
1.516 + // element[5], then we need to set three entries ([2], [3], and [4])
1.517 + // to 0.
1.518 + memset(&mImpl->mArray[mImpl->mCount], 0,
1.519 + (aIndex - mImpl->mCount) * sizeof(mImpl->mArray[0]));
1.520 + }
1.521 +
1.522 + mImpl->mCount = aIndex + 1;
1.523 +
1.524 +#if DEBUG_VOIDARRAY
1.525 + if (mImpl->mCount > mMaxCount &&
1.526 + mImpl->mCount < (int32_t)(sizeof(MaxElements)/sizeof(MaxElements[0])))
1.527 + {
1.528 + MaxElements[mImpl->mCount]++;
1.529 + MaxElements[mMaxCount]--;
1.530 + mMaxCount = mImpl->mCount;
1.531 + }
1.532 +#endif
1.533 + }
1.534 +
1.535 + return true;
1.536 +}
1.537 +
1.538 +// useful for doing LRU arrays
1.539 +bool nsVoidArray::MoveElement(int32_t aFrom, int32_t aTo)
1.540 +{
1.541 + void *tempElement;
1.542 +
1.543 + if (aTo == aFrom)
1.544 + return true;
1.545 +
1.546 + NS_ASSERTION(aTo >= 0 && aFrom >= 0,"MoveElement(negative index)");
1.547 + if (aTo >= Count() || aFrom >= Count())
1.548 + {
1.549 + // can't extend the array when moving an element. Also catches mImpl = null
1.550 + return false;
1.551 + }
1.552 + tempElement = mImpl->mArray[aFrom];
1.553 +
1.554 + if (aTo < aFrom)
1.555 + {
1.556 + // Moving one element closer to the head; the elements inbetween move down
1.557 + memmove(mImpl->mArray + aTo + 1, mImpl->mArray + aTo,
1.558 + (aFrom-aTo) * sizeof(mImpl->mArray[0]));
1.559 + mImpl->mArray[aTo] = tempElement;
1.560 + }
1.561 + else // already handled aFrom == aTo
1.562 + {
1.563 + // Moving one element closer to the tail; the elements inbetween move up
1.564 + memmove(mImpl->mArray + aFrom, mImpl->mArray + aFrom + 1,
1.565 + (aTo-aFrom) * sizeof(mImpl->mArray[0]));
1.566 + mImpl->mArray[aTo] = tempElement;
1.567 + }
1.568 +
1.569 + return true;
1.570 +}
1.571 +
1.572 +void nsVoidArray::RemoveElementsAt(int32_t aIndex, int32_t aCount)
1.573 +{
1.574 + int32_t oldCount = Count();
1.575 + NS_ASSERTION(aIndex >= 0,"RemoveElementsAt(negative index)");
1.576 + if (uint32_t(aIndex) >= uint32_t(oldCount))
1.577 + {
1.578 + return;
1.579 + }
1.580 + // Limit to available entries starting at aIndex
1.581 + if (aCount + aIndex > oldCount)
1.582 + aCount = oldCount - aIndex;
1.583 +
1.584 + // We don't need to move any elements if we're removing the
1.585 + // last element in the array
1.586 + if (aIndex < (oldCount - aCount))
1.587 + {
1.588 + memmove(mImpl->mArray + aIndex, mImpl->mArray + aIndex + aCount,
1.589 + (oldCount - (aIndex + aCount)) * sizeof(mImpl->mArray[0]));
1.590 + }
1.591 +
1.592 + mImpl->mCount -= aCount;
1.593 + return;
1.594 +}
1.595 +
1.596 +bool nsVoidArray::RemoveElement(void* aElement)
1.597 +{
1.598 + int32_t theIndex = IndexOf(aElement);
1.599 + if (theIndex != -1)
1.600 + {
1.601 + RemoveElementAt(theIndex);
1.602 + return true;
1.603 + }
1.604 +
1.605 + return false;
1.606 +}
1.607 +
1.608 +void nsVoidArray::Clear()
1.609 +{
1.610 + if (mImpl)
1.611 + {
1.612 + mImpl->mCount = 0;
1.613 + }
1.614 +}
1.615 +
1.616 +void nsVoidArray::Compact()
1.617 +{
1.618 + if (mImpl)
1.619 + {
1.620 + // XXX NOTE: this is quite inefficient in many cases if we're only
1.621 + // compacting by a little, but some callers care more about memory use.
1.622 + int32_t count = Count();
1.623 + if (GetArraySize() > count)
1.624 + {
1.625 + SizeTo(Count());
1.626 + }
1.627 + }
1.628 +}
1.629 +
1.630 +// Needed because we want to pass the pointer to the item in the array
1.631 +// to the comparator function, not a pointer to the pointer in the array.
1.632 +struct VoidArrayComparatorContext {
1.633 + nsVoidArrayComparatorFunc mComparatorFunc;
1.634 + void* mData;
1.635 +};
1.636 +
1.637 +static int
1.638 +VoidArrayComparator(const void* aElement1, const void* aElement2, void* aData)
1.639 +{
1.640 + VoidArrayComparatorContext* ctx = static_cast<VoidArrayComparatorContext*>(aData);
1.641 + return (*ctx->mComparatorFunc)(*static_cast<void* const*>(aElement1),
1.642 + *static_cast<void* const*>(aElement2),
1.643 + ctx->mData);
1.644 +}
1.645 +
1.646 +void nsVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
1.647 +{
1.648 + if (mImpl && mImpl->mCount > 1)
1.649 + {
1.650 + VoidArrayComparatorContext ctx = {aFunc, aData};
1.651 + NS_QuickSort(mImpl->mArray, mImpl->mCount, sizeof(mImpl->mArray[0]),
1.652 + VoidArrayComparator, &ctx);
1.653 + }
1.654 +}
1.655 +
1.656 +bool nsVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
1.657 +{
1.658 + int32_t index = -1;
1.659 + bool running = true;
1.660 +
1.661 + if (mImpl) {
1.662 + while (running && (++index < mImpl->mCount)) {
1.663 + running = (*aFunc)(mImpl->mArray[index], aData);
1.664 + }
1.665 + }
1.666 + return running;
1.667 +}
1.668 +
1.669 +bool nsVoidArray::EnumerateForwards(nsVoidArrayEnumFuncConst aFunc,
1.670 + void* aData) const
1.671 +{
1.672 + int32_t index = -1;
1.673 + bool running = true;
1.674 +
1.675 + if (mImpl) {
1.676 + while (running && (++index < mImpl->mCount)) {
1.677 + running = (*aFunc)(mImpl->mArray[index], aData);
1.678 + }
1.679 + }
1.680 + return running;
1.681 +}
1.682 +
1.683 +bool nsVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
1.684 +{
1.685 + bool running = true;
1.686 +
1.687 + if (mImpl)
1.688 + {
1.689 + int32_t index = Count();
1.690 + while (running && (0 <= --index))
1.691 + {
1.692 + running = (*aFunc)(mImpl->mArray[index], aData);
1.693 + }
1.694 + }
1.695 + return running;
1.696 +}
1.697 +
1.698 +struct SizeOfElementIncludingThisData
1.699 +{
1.700 + size_t mSize;
1.701 + nsVoidArraySizeOfElementIncludingThisFunc mSizeOfElementIncludingThis;
1.702 + mozilla::MallocSizeOf mMallocSizeOf;
1.703 + void *mData; // the arg passed by the user
1.704 +};
1.705 +
1.706 +static bool
1.707 +SizeOfElementIncludingThisEnumerator(const void *aElement, void *aData)
1.708 +{
1.709 + SizeOfElementIncludingThisData *d = (SizeOfElementIncludingThisData *)aData;
1.710 + d->mSize += d->mSizeOfElementIncludingThis(aElement, d->mMallocSizeOf, d->mData);
1.711 + return true;
1.712 +}
1.713 +
1.714 +size_t
1.715 +nsVoidArray::SizeOfExcludingThis(
1.716 + nsVoidArraySizeOfElementIncludingThisFunc aSizeOfElementIncludingThis,
1.717 + mozilla::MallocSizeOf aMallocSizeOf, void* aData) const
1.718 +{
1.719 + size_t n = 0;
1.720 + // Measure the element storage.
1.721 + if (mImpl) {
1.722 + n += aMallocSizeOf(mImpl);
1.723 + }
1.724 + // Measure things pointed to by the elements.
1.725 + if (aSizeOfElementIncludingThis) {
1.726 + SizeOfElementIncludingThisData data2 =
1.727 + { 0, aSizeOfElementIncludingThis, aMallocSizeOf, aData };
1.728 + EnumerateForwards(SizeOfElementIncludingThisEnumerator, &data2);
1.729 + n += data2.mSize;
1.730 + }
1.731 + return n;
1.732 +}
1.733 +
1.734 +//----------------------------------------------------------------------
1.735 +// NOTE: nsSmallVoidArray elements MUST all have the low bit as 0.
1.736 +// This means that normally it's only used for pointers, and in particular
1.737 +// structures or objects.
1.738 +nsSmallVoidArray::~nsSmallVoidArray()
1.739 +{
1.740 + if (HasSingle())
1.741 + {
1.742 + // Have to null out mImpl before the nsVoidArray dtor runs.
1.743 + mImpl = nullptr;
1.744 + }
1.745 +}
1.746 +
1.747 +nsSmallVoidArray&
1.748 +nsSmallVoidArray::operator=(nsSmallVoidArray& other)
1.749 +{
1.750 + int32_t count = other.Count();
1.751 + switch (count) {
1.752 + case 0:
1.753 + Clear();
1.754 + break;
1.755 + case 1:
1.756 + Clear();
1.757 + AppendElement(other.ElementAt(0));
1.758 + break;
1.759 + default:
1.760 + if (GetArraySize() >= count || SizeTo(count)) {
1.761 + *AsArray() = *other.AsArray();
1.762 + }
1.763 + }
1.764 +
1.765 + return *this;
1.766 +}
1.767 +
1.768 +int32_t
1.769 +nsSmallVoidArray::GetArraySize() const
1.770 +{
1.771 + if (HasSingle()) {
1.772 + return 1;
1.773 + }
1.774 +
1.775 + return AsArray()->GetArraySize();
1.776 +}
1.777 +
1.778 +int32_t
1.779 +nsSmallVoidArray::Count() const
1.780 +{
1.781 + if (HasSingle()) {
1.782 + return 1;
1.783 + }
1.784 +
1.785 + return AsArray()->Count();
1.786 +}
1.787 +
1.788 +void*
1.789 +nsSmallVoidArray::FastElementAt(int32_t aIndex) const
1.790 +{
1.791 + NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::FastElementAt: index out of range");
1.792 +
1.793 + if (HasSingle()) {
1.794 + return GetSingle();
1.795 + }
1.796 +
1.797 + return AsArray()->FastElementAt(aIndex);
1.798 +}
1.799 +
1.800 +int32_t
1.801 +nsSmallVoidArray::IndexOf(void* aPossibleElement) const
1.802 +{
1.803 + if (HasSingle()) {
1.804 + return aPossibleElement == GetSingle() ? 0 : -1;
1.805 + }
1.806 +
1.807 + return AsArray()->IndexOf(aPossibleElement);
1.808 +}
1.809 +
1.810 +bool
1.811 +nsSmallVoidArray::InsertElementAt(void* aElement, int32_t aIndex)
1.812 +{
1.813 + NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
1.814 + "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1.815 +
1.816 + if (aIndex == 0 && IsEmpty()) {
1.817 + SetSingle(aElement);
1.818 +
1.819 + return true;
1.820 + }
1.821 +
1.822 + if (!EnsureArray()) {
1.823 + return false;
1.824 + }
1.825 +
1.826 + return AsArray()->InsertElementAt(aElement, aIndex);
1.827 +}
1.828 +
1.829 +bool nsSmallVoidArray::InsertElementsAt(const nsVoidArray &aOther, int32_t aIndex)
1.830 +{
1.831 +#ifdef DEBUG
1.832 + for (int i = 0; i < aOther.Count(); i++) {
1.833 + NS_ASSERTION(!(NS_PTR_TO_INT32(aOther.ElementAt(i)) & 0x1),
1.834 + "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1.835 + }
1.836 +#endif
1.837 +
1.838 + if (aIndex == 0 && IsEmpty() && aOther.Count() == 1) {
1.839 + SetSingle(aOther.FastElementAt(0));
1.840 +
1.841 + return true;
1.842 + }
1.843 +
1.844 + if (!EnsureArray()) {
1.845 + return false;
1.846 + }
1.847 +
1.848 + return AsArray()->InsertElementsAt(aOther, aIndex);
1.849 +}
1.850 +
1.851 +bool
1.852 +nsSmallVoidArray::ReplaceElementAt(void* aElement, int32_t aIndex)
1.853 +{
1.854 + NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
1.855 + "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1.856 +
1.857 + if (aIndex == 0 && (IsEmpty() || HasSingle())) {
1.858 + SetSingle(aElement);
1.859 +
1.860 + return true;
1.861 + }
1.862 +
1.863 + if (!EnsureArray()) {
1.864 + return false;
1.865 + }
1.866 +
1.867 + return AsArray()->ReplaceElementAt(aElement, aIndex);
1.868 +}
1.869 +
1.870 +bool
1.871 +nsSmallVoidArray::AppendElement(void* aElement)
1.872 +{
1.873 + NS_ASSERTION(!(NS_PTR_TO_INT32(aElement) & 0x1),
1.874 + "Attempt to add element with 0x1 bit set to nsSmallVoidArray");
1.875 +
1.876 + if (IsEmpty()) {
1.877 + SetSingle(aElement);
1.878 +
1.879 + return true;
1.880 + }
1.881 +
1.882 + if (!EnsureArray()) {
1.883 + return false;
1.884 + }
1.885 +
1.886 + return AsArray()->AppendElement(aElement);
1.887 +}
1.888 +
1.889 +bool
1.890 +nsSmallVoidArray::RemoveElement(void* aElement)
1.891 +{
1.892 + if (HasSingle()) {
1.893 + if (aElement == GetSingle()) {
1.894 + mImpl = nullptr;
1.895 + return true;
1.896 + }
1.897 +
1.898 + return false;
1.899 + }
1.900 +
1.901 + return AsArray()->RemoveElement(aElement);
1.902 +}
1.903 +
1.904 +void
1.905 +nsSmallVoidArray::RemoveElementAt(int32_t aIndex)
1.906 +{
1.907 + if (HasSingle()) {
1.908 + if (aIndex == 0) {
1.909 + mImpl = nullptr;
1.910 + }
1.911 +
1.912 + return;
1.913 + }
1.914 +
1.915 + AsArray()->RemoveElementAt(aIndex);
1.916 +}
1.917 +
1.918 +void
1.919 +nsSmallVoidArray::RemoveElementsAt(int32_t aIndex, int32_t aCount)
1.920 +{
1.921 + if (HasSingle()) {
1.922 + if (aIndex == 0) {
1.923 + if (aCount > 0) {
1.924 + mImpl = nullptr;
1.925 + }
1.926 + }
1.927 +
1.928 + return;
1.929 + }
1.930 +
1.931 + AsArray()->RemoveElementsAt(aIndex, aCount);
1.932 +}
1.933 +
1.934 +void
1.935 +nsSmallVoidArray::Clear()
1.936 +{
1.937 + if (HasSingle()) {
1.938 + mImpl = nullptr;
1.939 + }
1.940 + else {
1.941 + AsArray()->Clear();
1.942 + }
1.943 +}
1.944 +
1.945 +bool
1.946 +nsSmallVoidArray::SizeTo(int32_t aMin)
1.947 +{
1.948 + if (!HasSingle()) {
1.949 + return AsArray()->SizeTo(aMin);
1.950 + }
1.951 +
1.952 + if (aMin <= 0) {
1.953 + mImpl = nullptr;
1.954 +
1.955 + return true;
1.956 + }
1.957 +
1.958 + if (aMin == 1) {
1.959 + return true;
1.960 + }
1.961 +
1.962 + void* single = GetSingle();
1.963 + mImpl = nullptr;
1.964 + if (!AsArray()->SizeTo(aMin)) {
1.965 + SetSingle(single);
1.966 +
1.967 + return false;
1.968 + }
1.969 +
1.970 + AsArray()->AppendElement(single);
1.971 +
1.972 + return true;
1.973 +}
1.974 +
1.975 +void
1.976 +nsSmallVoidArray::Compact()
1.977 +{
1.978 + if (!HasSingle()) {
1.979 + AsArray()->Compact();
1.980 + }
1.981 +}
1.982 +
1.983 +void
1.984 +nsSmallVoidArray::Sort(nsVoidArrayComparatorFunc aFunc, void* aData)
1.985 +{
1.986 + if (!HasSingle()) {
1.987 + AsArray()->Sort(aFunc,aData);
1.988 + }
1.989 +}
1.990 +
1.991 +bool
1.992 +nsSmallVoidArray::EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData)
1.993 +{
1.994 + if (HasSingle()) {
1.995 + return (*aFunc)(GetSingle(), aData);
1.996 + }
1.997 + return AsArray()->EnumerateForwards(aFunc,aData);
1.998 +}
1.999 +
1.1000 +bool
1.1001 +nsSmallVoidArray::EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData)
1.1002 +{
1.1003 + if (HasSingle()) {
1.1004 + return (*aFunc)(GetSingle(), aData);
1.1005 + }
1.1006 + return AsArray()->EnumerateBackwards(aFunc,aData);
1.1007 +}
1.1008 +
1.1009 +bool
1.1010 +nsSmallVoidArray::EnsureArray()
1.1011 +{
1.1012 + if (!HasSingle()) {
1.1013 + return true;
1.1014 + }
1.1015 +
1.1016 + void* single = GetSingle();
1.1017 + mImpl = nullptr;
1.1018 + if (!AsArray()->AppendElement(single)) {
1.1019 + SetSingle(single);
1.1020 +
1.1021 + return false;
1.1022 + }
1.1023 +
1.1024 + return true;
1.1025 +}
