1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/nsTArray.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1830 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim:set ts=2 sw=2 sts=2 et cindent: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef nsTArray_h__
1.11 +#define nsTArray_h__
1.12 +
1.13 +#include "nsTArrayForwardDeclare.h"
1.14 +#include "mozilla/Alignment.h"
1.15 +#include "mozilla/Assertions.h"
1.16 +#include "mozilla/MemoryReporting.h"
1.17 +#include "mozilla/TypeTraits.h"
1.18 +
1.19 +#include <string.h>
1.20 +
1.21 +#include "nsCycleCollectionNoteChild.h"
1.22 +#include "nsAlgorithm.h"
1.23 +#include "nscore.h"
1.24 +#include "nsQuickSort.h"
1.25 +#include "nsDebug.h"
1.26 +#include "nsISupportsImpl.h"
1.27 +#include <new>
1.28 +
1.29 +namespace JS {
1.30 +template <class T>
1.31 +class Heap;
1.32 +} /* namespace JS */
1.33 +
1.34 +class nsRegion;
1.35 +class nsIntRegion;
1.36 +
1.37 +//
1.38 +// nsTArray is a resizable array class, like std::vector.
1.39 +//
1.40 +// Unlike std::vector, which follows C++'s construction/destruction rules,
1.41 +// nsTArray assumes that your "T" can be memmoved()'ed safely.
1.42 +//
1.43 +// The public classes defined in this header are
1.44 +//
1.45 +// nsTArray<T>,
1.46 +// FallibleTArray<T>,
1.47 +// nsAutoTArray<T, N>, and
1.48 +// AutoFallibleTArray<T, N>.
1.49 +//
1.50 +// nsTArray and nsAutoTArray are infallible; if one tries to make an allocation
1.51 +// which fails, it crashes the program. In contrast, FallibleTArray and
1.52 +// AutoFallibleTArray are fallible; if you use one of these classes, you must
1.53 +// check the return values of methods such as Append() which may allocate. If
1.54 +// in doubt, choose an infallible type.
1.55 +//
1.56 +// InfallibleTArray and AutoInfallibleTArray are aliases for nsTArray and
1.57 +// nsAutoTArray.
1.58 +//
1.59 +// If you just want to declare the nsTArray types (e.g., if you're in a header
1.60 +// file and don't need the full nsTArray definitions) consider including
1.61 +// nsTArrayForwardDeclare.h instead of nsTArray.h.
1.62 +//
1.63 +// The template parameter (i.e., T in nsTArray<T>) specifies the type of the
1.64 +// elements and has the following requirements:
1.65 +//
1.66 +// T MUST be safely memmove()'able.
1.67 +// T MUST define a copy-constructor.
1.68 +// T MAY define operator< for sorting.
1.69 +// T MAY define operator== for searching.
1.70 +//
1.71 +// (Note that the memmove requirement may be relaxed for certain types - see
1.72 +// nsTArray_CopyChooser below.)
1.73 +//
1.74 +// For methods taking a Comparator instance, the Comparator must be a class
1.75 +// defining the following methods:
1.76 +//
1.77 +// class Comparator {
1.78 +// public:
1.79 +// /** @return True if the elements are equals; false otherwise. */
1.80 +// bool Equals(const elem_type& a, const Item& b) const;
1.81 +//
1.82 +// /** @return True if (a < b); false otherwise. */
1.83 +// bool LessThan(const elem_type& a, const Item& b) const;
1.84 +// };
1.85 +//
1.86 +// The Equals method is used for searching, and the LessThan method is used for
1.87 +// searching and sorting. The |Item| type above can be arbitrary, but must
1.88 +// match the Item type passed to the sort or search function.
1.89 +//
1.90 +
1.91 +
1.92 +//
1.93 +// nsTArrayFallibleResult and nsTArrayInfallibleResult types are proxy types
1.94 +// which are used because you cannot use a templated type which is bound to
1.95 +// void as an argument to a void function. In order to work around that, we
1.96 +// encode either a void or a boolean inside these proxy objects, and pass them
1.97 +// to the aforementioned function instead, and then use the type information to
1.98 +// decide what to do in the function.
1.99 +//
1.100 +// Note that public nsTArray methods should never return a proxy type. Such
1.101 +// types are only meant to be used in the internal nsTArray helper methods.
1.102 +// Public methods returning non-proxy types cannot be called from other
1.103 +// nsTArray members.
1.104 +//
1.105 +struct nsTArrayFallibleResult
1.106 +{
1.107 + // Note: allows implicit conversions from and to bool
1.108 + nsTArrayFallibleResult(bool result)
1.109 + : mResult(result)
1.110 + {}
1.111 +
1.112 + operator bool() {
1.113 + return mResult;
1.114 + }
1.115 +
1.116 +private:
1.117 + bool mResult;
1.118 +};
1.119 +
1.120 +struct nsTArrayInfallibleResult
1.121 +{
1.122 +};
1.123 +
1.124 +//
1.125 +// nsTArray*Allocators must all use the same |free()|, to allow swap()'ing
1.126 +// between fallible and infallible variants.
1.127 +//
1.128 +
1.129 +struct nsTArrayFallibleAllocatorBase
1.130 +{
1.131 + typedef bool ResultType;
1.132 + typedef nsTArrayFallibleResult ResultTypeProxy;
1.133 +
1.134 + static ResultType Result(ResultTypeProxy result) {
1.135 + return result;
1.136 + }
1.137 +
1.138 + static bool Successful(ResultTypeProxy result) {
1.139 + return result;
1.140 + }
1.141 +
1.142 + static ResultTypeProxy SuccessResult() {
1.143 + return true;
1.144 + }
1.145 +
1.146 + static ResultTypeProxy FailureResult() {
1.147 + return false;
1.148 + }
1.149 +
1.150 + static ResultType ConvertBoolToResultType(bool aValue) {
1.151 + return aValue;
1.152 + }
1.153 +};
1.154 +
1.155 +struct nsTArrayInfallibleAllocatorBase
1.156 +{
1.157 + typedef void ResultType;
1.158 + typedef nsTArrayInfallibleResult ResultTypeProxy;
1.159 +
1.160 + static ResultType Result(ResultTypeProxy result) {
1.161 + }
1.162 +
1.163 + static bool Successful(ResultTypeProxy) {
1.164 + return true;
1.165 + }
1.166 +
1.167 + static ResultTypeProxy SuccessResult() {
1.168 + return ResultTypeProxy();
1.169 + }
1.170 +
1.171 + static ResultTypeProxy FailureResult() {
1.172 + NS_RUNTIMEABORT("Infallible nsTArray should never fail");
1.173 + return ResultTypeProxy();
1.174 + }
1.175 +
1.176 + static ResultType ConvertBoolToResultType(bool aValue) {
1.177 + if (!aValue) {
1.178 + NS_RUNTIMEABORT("infallible nsTArray should never convert false to ResultType");
1.179 + }
1.180 + }
1.181 +};
1.182 +
1.183 +#if defined(MOZALLOC_HAVE_XMALLOC)
1.184 +#include "mozilla/mozalloc_abort.h"
1.185 +
1.186 +struct nsTArrayFallibleAllocator : nsTArrayFallibleAllocatorBase
1.187 +{
1.188 + static void* Malloc(size_t size) {
1.189 + return moz_malloc(size);
1.190 + }
1.191 +
1.192 + static void* Realloc(void* ptr, size_t size) {
1.193 + return moz_realloc(ptr, size);
1.194 + }
1.195 +
1.196 + static void Free(void* ptr) {
1.197 + moz_free(ptr);
1.198 + }
1.199 +
1.200 + static void SizeTooBig(size_t) {
1.201 + }
1.202 +};
1.203 +
1.204 +struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase
1.205 +{
1.206 + static void* Malloc(size_t size) {
1.207 + return moz_xmalloc(size);
1.208 + }
1.209 +
1.210 + static void* Realloc(void* ptr, size_t size) {
1.211 + return moz_xrealloc(ptr, size);
1.212 + }
1.213 +
1.214 + static void Free(void* ptr) {
1.215 + moz_free(ptr);
1.216 + }
1.217 +
1.218 + static void SizeTooBig(size_t size) {
1.219 + NS_ABORT_OOM(size);
1.220 + }
1.221 +};
1.222 +
1.223 +#else
1.224 +#include <stdlib.h>
1.225 +
1.226 +struct nsTArrayFallibleAllocator : nsTArrayFallibleAllocatorBase
1.227 +{
1.228 + static void* Malloc(size_t size) {
1.229 + return malloc(size);
1.230 + }
1.231 +
1.232 + static void* Realloc(void* ptr, size_t size) {
1.233 + return realloc(ptr, size);
1.234 + }
1.235 +
1.236 + static void Free(void* ptr) {
1.237 + free(ptr);
1.238 + }
1.239 +
1.240 + static void SizeTooBig(size_t) {
1.241 + }
1.242 +};
1.243 +
1.244 +struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase
1.245 +{
1.246 + static void* Malloc(size_t size) {
1.247 + void* ptr = malloc(size);
1.248 + if (MOZ_UNLIKELY(!ptr)) {
1.249 + NS_ABORT_OOM(size);
1.250 + }
1.251 + return ptr;
1.252 + }
1.253 +
1.254 + static void* Realloc(void* ptr, size_t size) {
1.255 + void* newptr = realloc(ptr, size);
1.256 + if (MOZ_UNLIKELY(!ptr && size)) {
1.257 + NS_ABORT_OOM(size);
1.258 + }
1.259 + return newptr;
1.260 + }
1.261 +
1.262 + static void Free(void* ptr) {
1.263 + free(ptr);
1.264 + }
1.265 +
1.266 + static void SizeTooBig(size_t size) {
1.267 + NS_ABORT_OOM(size);
1.268 + }
1.269 +};
1.270 +
1.271 +#endif
1.272 +
1.273 +// nsTArray_base stores elements into the space allocated beyond
1.274 +// sizeof(*this). This is done to minimize the size of the nsTArray
1.275 +// object when it is empty.
1.276 +struct NS_COM_GLUE nsTArrayHeader
1.277 +{
1.278 + static nsTArrayHeader sEmptyHdr;
1.279 +
1.280 + uint32_t mLength;
1.281 + uint32_t mCapacity : 31;
1.282 + uint32_t mIsAutoArray : 1;
1.283 +};
1.284 +
1.285 +// This class provides a SafeElementAt method to nsTArray<T*> which does
1.286 +// not take a second default value parameter.
1.287 +template <class E, class Derived>
1.288 +struct nsTArray_SafeElementAtHelper
1.289 +{
1.290 + typedef E* elem_type;
1.291 + typedef uint32_t index_type;
1.292 +
1.293 + // No implementation is provided for these two methods, and that is on
1.294 + // purpose, since we don't support these functions on non-pointer type
1.295 + // instantiations.
1.296 + elem_type& SafeElementAt(index_type i);
1.297 + const elem_type& SafeElementAt(index_type i) const;
1.298 +};
1.299 +
1.300 +template <class E, class Derived>
1.301 +struct nsTArray_SafeElementAtHelper<E*, Derived>
1.302 +{
1.303 + typedef E* elem_type;
1.304 + typedef uint32_t index_type;
1.305 +
1.306 + elem_type SafeElementAt(index_type i) {
1.307 + return static_cast<Derived*> (this)->SafeElementAt(i, nullptr);
1.308 + }
1.309 +
1.310 + const elem_type SafeElementAt(index_type i) const {
1.311 + return static_cast<const Derived*> (this)->SafeElementAt(i, nullptr);
1.312 + }
1.313 +};
1.314 +
1.315 +// E is the base type that the smart pointer is templated over; the
1.316 +// smart pointer can act as E*.
1.317 +template <class E, class Derived>
1.318 +struct nsTArray_SafeElementAtSmartPtrHelper
1.319 +{
1.320 + typedef E* elem_type;
1.321 + typedef uint32_t index_type;
1.322 +
1.323 + elem_type SafeElementAt(index_type i) {
1.324 + return static_cast<Derived*> (this)->SafeElementAt(i, nullptr);
1.325 + }
1.326 +
1.327 + const elem_type SafeElementAt(index_type i) const {
1.328 + return static_cast<const Derived*> (this)->SafeElementAt(i, nullptr);
1.329 + }
1.330 +};
1.331 +
1.332 +template <class T> class nsCOMPtr;
1.333 +
1.334 +template <class E, class Derived>
1.335 +struct nsTArray_SafeElementAtHelper<nsCOMPtr<E>, Derived> :
1.336 + public nsTArray_SafeElementAtSmartPtrHelper<E, Derived>
1.337 +{
1.338 +};
1.339 +
1.340 +template <class T> class nsRefPtr;
1.341 +
1.342 +template <class E, class Derived>
1.343 +struct nsTArray_SafeElementAtHelper<nsRefPtr<E>, Derived> :
1.344 + public nsTArray_SafeElementAtSmartPtrHelper<E, Derived>
1.345 +{
1.346 +};
1.347 +
1.348 +//
1.349 +// This class serves as a base class for nsTArray. It shouldn't be used
1.350 +// directly. It holds common implementation code that does not depend on the
1.351 +// element type of the nsTArray.
1.352 +//
1.353 +template<class Alloc, class Copy>
1.354 +class nsTArray_base
1.355 +{
1.356 + // Allow swapping elements with |nsTArray_base|s created using a
1.357 + // different allocator. This is kosher because all allocators use
1.358 + // the same free().
1.359 + template<class Allocator, class Copier>
1.360 + friend class nsTArray_base;
1.361 +
1.362 +protected:
1.363 + typedef nsTArrayHeader Header;
1.364 +
1.365 +public:
1.366 + typedef uint32_t size_type;
1.367 + typedef uint32_t index_type;
1.368 +
1.369 + // @return The number of elements in the array.
1.370 + size_type Length() const {
1.371 + return mHdr->mLength;
1.372 + }
1.373 +
1.374 + // @return True if the array is empty or false otherwise.
1.375 + bool IsEmpty() const {
1.376 + return Length() == 0;
1.377 + }
1.378 +
1.379 + // @return The number of elements that can fit in the array without forcing
1.380 + // the array to be re-allocated. The length of an array is always less
1.381 + // than or equal to its capacity.
1.382 + size_type Capacity() const {
1.383 + return mHdr->mCapacity;
1.384 + }
1.385 +
1.386 +#ifdef DEBUG
1.387 + void* DebugGetHeader() const {
1.388 + return mHdr;
1.389 + }
1.390 +#endif
1.391 +
1.392 +protected:
1.393 + nsTArray_base();
1.394 +
1.395 + ~nsTArray_base();
1.396 +
1.397 + // Resize the storage if necessary to achieve the requested capacity.
1.398 + // @param capacity The requested number of array elements.
1.399 + // @param elemSize The size of an array element.
1.400 + // @return False if insufficient memory is available; true otherwise.
1.401 + typename Alloc::ResultTypeProxy EnsureCapacity(size_type capacity, size_type elemSize);
1.402 +
1.403 + // Resize the storage to the minimum required amount.
1.404 + // @param elemSize The size of an array element.
1.405 + // @param elemAlign The alignment in bytes of an array element.
1.406 + void ShrinkCapacity(size_type elemSize, size_t elemAlign);
1.407 +
1.408 + // This method may be called to resize a "gap" in the array by shifting
1.409 + // elements around. It updates mLength appropriately. If the resulting
1.410 + // array has zero elements, then the array's memory is free'd.
1.411 + // @param start The starting index of the gap.
1.412 + // @param oldLen The current length of the gap.
1.413 + // @param newLen The desired length of the gap.
1.414 + // @param elemSize The size of an array element.
1.415 + // @param elemAlign The alignment in bytes of an array element.
1.416 + void ShiftData(index_type start, size_type oldLen, size_type newLen,
1.417 + size_type elemSize, size_t elemAlign);
1.418 +
1.419 + // This method increments the length member of the array's header.
1.420 + // Note that mHdr may actually be sEmptyHdr in the case where a
1.421 + // zero-length array is inserted into our array. But then n should
1.422 + // always be 0.
1.423 + void IncrementLength(uint32_t n) {
1.424 + if (mHdr == EmptyHdr()) {
1.425 + if (MOZ_UNLIKELY(n != 0)) {
1.426 + // Writing a non-zero length to the empty header would be extremely bad.
1.427 + MOZ_CRASH();
1.428 + }
1.429 + } else {
1.430 + mHdr->mLength += n;
1.431 + }
1.432 + }
1.433 +
1.434 + // This method inserts blank slots into the array.
1.435 + // @param index the place to insert the new elements. This must be no
1.436 + // greater than the current length of the array.
1.437 + // @param count the number of slots to insert
1.438 + // @param elementSize the size of an array element.
1.439 + // @param elemAlign the alignment in bytes of an array element.
1.440 + bool InsertSlotsAt(index_type index, size_type count,
1.441 + size_type elementSize, size_t elemAlign);
1.442 +
1.443 +protected:
1.444 + template<class Allocator>
1.445 + typename Alloc::ResultTypeProxy
1.446 + SwapArrayElements(nsTArray_base<Allocator, Copy>& other,
1.447 + size_type elemSize,
1.448 + size_t elemAlign);
1.449 +
1.450 + // This is an RAII class used in SwapArrayElements.
1.451 + class IsAutoArrayRestorer {
1.452 + public:
1.453 + IsAutoArrayRestorer(nsTArray_base<Alloc, Copy> &array, size_t elemAlign);
1.454 + ~IsAutoArrayRestorer();
1.455 +
1.456 + private:
1.457 + nsTArray_base<Alloc, Copy> &mArray;
1.458 + size_t mElemAlign;
1.459 + bool mIsAuto;
1.460 + };
1.461 +
1.462 + // Helper function for SwapArrayElements. Ensures that if the array
1.463 + // is an nsAutoTArray that it doesn't use the built-in buffer.
1.464 + bool EnsureNotUsingAutoArrayBuffer(size_type elemSize);
1.465 +
1.466 + // Returns true if this nsTArray is an nsAutoTArray with a built-in buffer.
1.467 + bool IsAutoArray() const {
1.468 + return mHdr->mIsAutoArray;
1.469 + }
1.470 +
1.471 + // Returns a Header for the built-in buffer of this nsAutoTArray.
1.472 + Header* GetAutoArrayBuffer(size_t elemAlign) {
1.473 + MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");
1.474 + return GetAutoArrayBufferUnsafe(elemAlign);
1.475 + }
1.476 + const Header* GetAutoArrayBuffer(size_t elemAlign) const {
1.477 + MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this");
1.478 + return GetAutoArrayBufferUnsafe(elemAlign);
1.479 + }
1.480 +
1.481 + // Returns a Header for the built-in buffer of this nsAutoTArray, but doesn't
1.482 + // assert that we are an nsAutoTArray.
1.483 + Header* GetAutoArrayBufferUnsafe(size_t elemAlign) {
1.484 + return const_cast<Header*>(static_cast<const nsTArray_base<Alloc, Copy>*>(this)->
1.485 + GetAutoArrayBufferUnsafe(elemAlign));
1.486 + }
1.487 + const Header* GetAutoArrayBufferUnsafe(size_t elemAlign) const;
1.488 +
1.489 + // Returns true if this is an nsAutoTArray and it currently uses the
1.490 + // built-in buffer to store its elements.
1.491 + bool UsesAutoArrayBuffer() const;
1.492 +
1.493 + // The array's elements (prefixed with a Header). This pointer is never
1.494 + // null. If the array is empty, then this will point to sEmptyHdr.
1.495 + Header *mHdr;
1.496 +
1.497 + Header* Hdr() const {
1.498 + return mHdr;
1.499 + }
1.500 +
1.501 + Header** PtrToHdr() {
1.502 + return &mHdr;
1.503 + }
1.504 +
1.505 + static Header* EmptyHdr() {
1.506 + return &Header::sEmptyHdr;
1.507 + }
1.508 +};
1.509 +
1.510 +//
1.511 +// This class defines convenience functions for element specific operations.
1.512 +// Specialize this template if necessary.
1.513 +//
1.514 +template<class E>
1.515 +class nsTArrayElementTraits
1.516 +{
1.517 +public:
1.518 + // Invoke the default constructor in place.
1.519 + static inline void Construct(E *e) {
1.520 + // Do NOT call "E()"! That triggers C++ "default initialization"
1.521 + // which zeroes out POD ("plain old data") types such as regular
1.522 + // ints. We don't want that because it can be a performance issue
1.523 + // and people don't expect it; nsTArray should work like a regular
1.524 + // C/C++ array in this respect.
1.525 + new (static_cast<void *>(e)) E;
1.526 + }
1.527 + // Invoke the copy-constructor in place.
1.528 + template<class A>
1.529 + static inline void Construct(E *e, const A &arg) {
1.530 + typedef typename mozilla::RemoveCV<E>::Type E_NoCV;
1.531 + typedef typename mozilla::RemoveCV<A>::Type A_NoCV;
1.532 + static_assert(!mozilla::IsSame<E_NoCV*, A_NoCV>::value,
1.533 + "For safety, we disallow constructing nsTArray<E> elements "
1.534 + "from E* pointers. See bug 960591.");
1.535 + new (static_cast<void *>(e)) E(arg);
1.536 + }
1.537 + // Invoke the destructor in place.
1.538 + static inline void Destruct(E *e) {
1.539 + e->~E();
1.540 + }
1.541 +};
1.542 +
1.543 +// The default comparator used by nsTArray
1.544 +template<class A, class B>
1.545 +class nsDefaultComparator
1.546 +{
1.547 +public:
1.548 + bool Equals(const A& a, const B& b) const {
1.549 + return a == b;
1.550 + }
1.551 + bool LessThan(const A& a, const B& b) const {
1.552 + return a < b;
1.553 + }
1.554 +};
1.555 +
1.556 +template <class E> class InfallibleTArray;
1.557 +template <class E> class FallibleTArray;
1.558 +
1.559 +template<bool IsPod, bool IsSameType>
1.560 +struct AssignRangeAlgorithm {
1.561 + template<class Item, class ElemType, class IndexType, class SizeType>
1.562 + static void implementation(ElemType* elements, IndexType start,
1.563 + SizeType count, const Item *values) {
1.564 + ElemType *iter = elements + start, *end = iter + count;
1.565 + for (; iter != end; ++iter, ++values)
1.566 + nsTArrayElementTraits<ElemType>::Construct(iter, *values);
1.567 + }
1.568 +};
1.569 +
1.570 +template<>
1.571 +struct AssignRangeAlgorithm<true, true> {
1.572 + template<class Item, class ElemType, class IndexType, class SizeType>
1.573 + static void implementation(ElemType* elements, IndexType start,
1.574 + SizeType count, const Item *values) {
1.575 + memcpy(elements + start, values, count * sizeof(ElemType));
1.576 + }
1.577 +};
1.578 +
1.579 +//
1.580 +// Normally elements are copied with memcpy and memmove, but for some element
1.581 +// types that is problematic. The nsTArray_CopyChooser template class can be
1.582 +// specialized to ensure that copying calls constructors and destructors
1.583 +// instead, as is done below for JS::Heap<E> elements.
1.584 +//
1.585 +
1.586 +//
1.587 +// A class that defines how to copy elements using memcpy/memmove.
1.588 +//
1.589 +struct nsTArray_CopyWithMemutils
1.590 +{
1.591 + const static bool allowRealloc = true;
1.592 +
1.593 + static void CopyElements(void* dest, const void* src, size_t count, size_t elemSize) {
1.594 + memcpy(dest, src, count * elemSize);
1.595 + }
1.596 +
1.597 + static void CopyHeaderAndElements(void* dest, const void* src, size_t count, size_t elemSize) {
1.598 + memcpy(dest, src, sizeof(nsTArrayHeader) + count * elemSize);
1.599 + }
1.600 +
1.601 + static void MoveElements(void* dest, const void* src, size_t count, size_t elemSize) {
1.602 + memmove(dest, src, count * elemSize);
1.603 + }
1.604 +};
1.605 +
1.606 +//
1.607 +// A template class that defines how to copy elements calling their constructors
1.608 +// and destructors appropriately.
1.609 +//
1.610 +template <class ElemType>
1.611 +struct nsTArray_CopyWithConstructors
1.612 +{
1.613 + typedef nsTArrayElementTraits<ElemType> traits;
1.614 +
1.615 + const static bool allowRealloc = false;
1.616 +
1.617 + static void CopyElements(void* dest, void* src, size_t count, size_t elemSize) {
1.618 + ElemType* destElem = static_cast<ElemType*>(dest);
1.619 + ElemType* srcElem = static_cast<ElemType*>(src);
1.620 + ElemType* destElemEnd = destElem + count;
1.621 +#ifdef DEBUG
1.622 + ElemType* srcElemEnd = srcElem + count;
1.623 + MOZ_ASSERT(srcElemEnd <= destElem || srcElemEnd > destElemEnd);
1.624 +#endif
1.625 + while (destElem != destElemEnd) {
1.626 + traits::Construct(destElem, *srcElem);
1.627 + traits::Destruct(srcElem);
1.628 + ++destElem;
1.629 + ++srcElem;
1.630 + }
1.631 + }
1.632 +
1.633 + static void CopyHeaderAndElements(void* dest, void* src, size_t count, size_t elemSize) {
1.634 + nsTArrayHeader* destHeader = static_cast<nsTArrayHeader*>(dest);
1.635 + nsTArrayHeader* srcHeader = static_cast<nsTArrayHeader*>(src);
1.636 + *destHeader = *srcHeader;
1.637 + CopyElements(static_cast<uint8_t*>(dest) + sizeof(nsTArrayHeader),
1.638 + static_cast<uint8_t*>(src) + sizeof(nsTArrayHeader),
1.639 + count, elemSize);
1.640 + }
1.641 +
1.642 + static void MoveElements(void* dest, void* src, size_t count, size_t elemSize) {
1.643 + ElemType* destElem = static_cast<ElemType*>(dest);
1.644 + ElemType* srcElem = static_cast<ElemType*>(src);
1.645 + ElemType* destElemEnd = destElem + count;
1.646 + ElemType* srcElemEnd = srcElem + count;
1.647 + if (destElem == srcElem) {
1.648 + return; // In practice, we don't do this.
1.649 + } else if (srcElemEnd > destElem && srcElemEnd < destElemEnd) {
1.650 + while (destElemEnd != destElem) {
1.651 + --destElemEnd;
1.652 + --srcElemEnd;
1.653 + traits::Construct(destElemEnd, *srcElemEnd);
1.654 + traits::Destruct(srcElem);
1.655 + }
1.656 + } else {
1.657 + CopyElements(dest, src, count, elemSize);
1.658 + }
1.659 + }
1.660 +};
1.661 +
1.662 +//
1.663 +// The default behaviour is to use memcpy/memmove for everything.
1.664 +//
1.665 +template <class E>
1.666 +struct nsTArray_CopyChooser {
1.667 + typedef nsTArray_CopyWithMemutils Type;
1.668 +};
1.669 +
1.670 +//
1.671 +// Some classes require constructors/destructors to be called, so they are
1.672 +// specialized here.
1.673 +//
1.674 +template <class E>
1.675 +struct nsTArray_CopyChooser<JS::Heap<E> > {
1.676 + typedef nsTArray_CopyWithConstructors<JS::Heap<E> > Type;
1.677 +};
1.678 +
1.679 +template<>
1.680 +struct nsTArray_CopyChooser<nsRegion> {
1.681 + typedef nsTArray_CopyWithConstructors<nsRegion> Type;
1.682 +};
1.683 +
1.684 +template<>
1.685 +struct nsTArray_CopyChooser<nsIntRegion> {
1.686 + typedef nsTArray_CopyWithConstructors<nsIntRegion> Type;
1.687 +};
1.688 +
1.689 +//
1.690 +// Base class for nsTArray_Impl that is templated on element type and derived
1.691 +// nsTArray_Impl class, to allow extra conversions to be added for specific
1.692 +// types.
1.693 +//
1.694 +template <class E, class Derived>
1.695 +struct nsTArray_TypedBase : public nsTArray_SafeElementAtHelper<E, Derived> {};
1.696 +
1.697 +//
1.698 +// Specialization of nsTArray_TypedBase for arrays containing JS::Heap<E>
1.699 +// elements.
1.700 +//
1.701 +// These conversions are safe because JS::Heap<E> and E share the same
1.702 +// representation, and since the result of the conversions are const references
1.703 +// we won't miss any barriers.
1.704 +//
1.705 +// The static_cast is necessary to obtain the correct address for the derived
1.706 +// class since we are a base class used in multiple inheritance.
1.707 +//
1.708 +template <class E, class Derived>
1.709 +struct nsTArray_TypedBase<JS::Heap<E>, Derived>
1.710 + : public nsTArray_SafeElementAtHelper<JS::Heap<E>, Derived>
1.711 +{
1.712 + operator const nsTArray<E>& () {
1.713 + static_assert(sizeof(E) == sizeof(JS::Heap<E>),
1.714 + "JS::Heap<E> must be binary compatible with E.");
1.715 + Derived* self = static_cast<Derived*>(this);
1.716 + return *reinterpret_cast<nsTArray<E> *>(self);
1.717 + }
1.718 +
1.719 + operator const FallibleTArray<E>& () {
1.720 + Derived* self = static_cast<Derived*>(this);
1.721 + return *reinterpret_cast<FallibleTArray<E> *>(self);
1.722 + }
1.723 +};
1.724 +
1.725 +
1.726 +//
1.727 +// nsTArray_Impl contains most of the guts supporting nsTArray, FallibleTArray,
1.728 +// nsAutoTArray, and AutoFallibleTArray.
1.729 +//
1.730 +// The only situation in which you might need to use nsTArray_Impl in your code
1.731 +// is if you're writing code which mutates a TArray which may or may not be
1.732 +// infallible.
1.733 +//
1.734 +// Code which merely reads from a TArray which may or may not be infallible can
1.735 +// simply cast the TArray to |const nsTArray&|; both fallible and infallible
1.736 +// TArrays can be cast to |const nsTArray&|.
1.737 +//
1.738 +template<class E, class Alloc>
1.739 +class nsTArray_Impl : public nsTArray_base<Alloc, typename nsTArray_CopyChooser<E>::Type>,
1.740 + public nsTArray_TypedBase<E, nsTArray_Impl<E, Alloc> >
1.741 +{
1.742 +public:
1.743 + typedef typename nsTArray_CopyChooser<E>::Type copy_type;
1.744 + typedef nsTArray_base<Alloc, copy_type> base_type;
1.745 + typedef typename base_type::size_type size_type;
1.746 + typedef typename base_type::index_type index_type;
1.747 + typedef E elem_type;
1.748 + typedef nsTArray_Impl<E, Alloc> self_type;
1.749 + typedef nsTArrayElementTraits<E> elem_traits;
1.750 + typedef nsTArray_SafeElementAtHelper<E, self_type> safeelementat_helper_type;
1.751 +
1.752 + using safeelementat_helper_type::SafeElementAt;
1.753 + using base_type::EmptyHdr;
1.754 +
1.755 + // A special value that is used to indicate an invalid or unknown index
1.756 + // into the array.
1.757 + enum {
1.758 + NoIndex = index_type(-1)
1.759 + };
1.760 +
1.761 + using base_type::Length;
1.762 +
1.763 + //
1.764 + // Finalization method
1.765 + //
1.766 +
1.767 + ~nsTArray_Impl() { Clear(); }
1.768 +
1.769 + //
1.770 + // Initialization methods
1.771 + //
1.772 +
1.773 + nsTArray_Impl() {}
1.774 +
1.775 + // Initialize this array and pre-allocate some number of elements.
1.776 + explicit nsTArray_Impl(size_type capacity) {
1.777 + SetCapacity(capacity);
1.778 + }
1.779 +
1.780 + // The array's copy-constructor performs a 'deep' copy of the given array.
1.781 + // @param other The array object to copy.
1.782 + //
1.783 + // It's very important that we declare this method as taking |const
1.784 + // self_type&| as opposed to taking |const nsTArray_Impl<E, OtherAlloc>| for
1.785 + // an arbitrary OtherAlloc.
1.786 + //
1.787 + // If we don't declare a constructor taking |const self_type&|, C++ generates
1.788 + // a copy-constructor for this class which merely copies the object's
1.789 + // members, which is obviously wrong.
1.790 + //
1.791 + // You can pass an nsTArray_Impl<E, OtherAlloc> to this method because
1.792 + // nsTArray_Impl<E, X> can be cast to const nsTArray_Impl<E, Y>&. So the
1.793 + // effect on the API is the same as if we'd declared this method as taking
1.794 + // |const nsTArray_Impl<E, OtherAlloc>&|.
1.795 + explicit nsTArray_Impl(const self_type& other) {
1.796 + AppendElements(other);
1.797 + }
1.798 +
1.799 + // Allow converting to a const array with a different kind of allocator,
1.800 + // Since the allocator doesn't matter for const arrays
1.801 + template<typename Allocator>
1.802 + operator const nsTArray_Impl<E, Allocator>&() const {
1.803 + return *reinterpret_cast<const nsTArray_Impl<E, Allocator>*>(this);
1.804 + }
1.805 + // And we have to do this for our subclasses too
1.806 + operator const nsTArray<E>&() const {
1.807 + return *reinterpret_cast<const InfallibleTArray<E>*>(this);
1.808 + }
1.809 + operator const FallibleTArray<E>&() const {
1.810 + return *reinterpret_cast<const FallibleTArray<E>*>(this);
1.811 + }
1.812 +
1.813 + // The array's assignment operator performs a 'deep' copy of the given
1.814 + // array. It is optimized to reuse existing storage if possible.
1.815 + // @param other The array object to copy.
1.816 + self_type& operator=(const self_type& other) {
1.817 + ReplaceElementsAt(0, Length(), other.Elements(), other.Length());
1.818 + return *this;
1.819 + }
1.820 +
1.821 + // Return true if this array has the same length and the same
1.822 + // elements as |other|.
1.823 + template<typename Allocator>
1.824 + bool operator==(const nsTArray_Impl<E, Allocator>& other) const {
1.825 + size_type len = Length();
1.826 + if (len != other.Length())
1.827 + return false;
1.828 +
1.829 + // XXX std::equal would be as fast or faster here
1.830 + for (index_type i = 0; i < len; ++i)
1.831 + if (!(operator[](i) == other[i]))
1.832 + return false;
1.833 +
1.834 + return true;
1.835 + }
1.836 +
1.837 + // Return true if this array does not have the same length and the same
1.838 + // elements as |other|.
1.839 + bool operator!=(const self_type& other) const {
1.840 + return !operator==(other);
1.841 + }
1.842 +
1.843 + template<typename Allocator>
1.844 + self_type& operator=(const nsTArray_Impl<E, Allocator>& other) {
1.845 + ReplaceElementsAt(0, Length(), other.Elements(), other.Length());
1.846 + return *this;
1.847 + }
1.848 +
1.849 + // @return The amount of memory used by this nsTArray_Impl, excluding
1.850 + // sizeof(*this).
1.851 + size_t SizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
1.852 + if (this->UsesAutoArrayBuffer() || Hdr() == EmptyHdr())
1.853 + return 0;
1.854 + return mallocSizeOf(this->Hdr());
1.855 + }
1.856 +
1.857 + // @return The amount of memory used by this nsTArray_Impl, including
1.858 + // sizeof(*this).
1.859 + size_t SizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
1.860 + return mallocSizeOf(this) + SizeOfExcludingThis(mallocSizeOf);
1.861 + }
1.862 +
1.863 + //
1.864 + // Accessor methods
1.865 + //
1.866 +
1.867 + // This method provides direct access to the array elements.
1.868 + // @return A pointer to the first element of the array. If the array is
1.869 + // empty, then this pointer must not be dereferenced.
1.870 + elem_type* Elements() {
1.871 + return reinterpret_cast<elem_type *>(Hdr() + 1);
1.872 + }
1.873 +
1.874 + // This method provides direct, readonly access to the array elements.
1.875 + // @return A pointer to the first element of the array. If the array is
1.876 + // empty, then this pointer must not be dereferenced.
1.877 + const elem_type* Elements() const {
1.878 + return reinterpret_cast<const elem_type *>(Hdr() + 1);
1.879 + }
1.880 +
1.881 + // This method provides direct access to the i'th element of the array.
1.882 + // The given index must be within the array bounds.
1.883 + // @param i The index of an element in the array.
1.884 + // @return A reference to the i'th element of the array.
1.885 + elem_type& ElementAt(index_type i) {
1.886 + MOZ_ASSERT(i < Length(), "invalid array index");
1.887 + return Elements()[i];
1.888 + }
1.889 +
1.890 + // This method provides direct, readonly access to the i'th element of the
1.891 + // array. The given index must be within the array bounds.
1.892 + // @param i The index of an element in the array.
1.893 + // @return A const reference to the i'th element of the array.
1.894 + const elem_type& ElementAt(index_type i) const {
1.895 + MOZ_ASSERT(i < Length(), "invalid array index");
1.896 + return Elements()[i];
1.897 + }
1.898 +
1.899 + // This method provides direct access to the i'th element of the array in
1.900 + // a bounds safe manner. If the requested index is out of bounds the
1.901 + // provided default value is returned.
1.902 + // @param i The index of an element in the array.
1.903 + // @param def The value to return if the index is out of bounds.
1.904 + elem_type& SafeElementAt(index_type i, elem_type& def) {
1.905 + return i < Length() ? Elements()[i] : def;
1.906 + }
1.907 +
1.908 + // This method provides direct access to the i'th element of the array in
1.909 + // a bounds safe manner. If the requested index is out of bounds the
1.910 + // provided default value is returned.
1.911 + // @param i The index of an element in the array.
1.912 + // @param def The value to return if the index is out of bounds.
1.913 + const elem_type& SafeElementAt(index_type i, const elem_type& def) const {
1.914 + return i < Length() ? Elements()[i] : def;
1.915 + }
1.916 +
1.917 + // Shorthand for ElementAt(i)
1.918 + elem_type& operator[](index_type i) {
1.919 + return ElementAt(i);
1.920 + }
1.921 +
1.922 + // Shorthand for ElementAt(i)
1.923 + const elem_type& operator[](index_type i) const {
1.924 + return ElementAt(i);
1.925 + }
1.926 +
1.927 + // Shorthand for ElementAt(length - 1)
1.928 + elem_type& LastElement() {
1.929 + return ElementAt(Length() - 1);
1.930 + }
1.931 +
1.932 + // Shorthand for ElementAt(length - 1)
1.933 + const elem_type& LastElement() const {
1.934 + return ElementAt(Length() - 1);
1.935 + }
1.936 +
1.937 + // Shorthand for SafeElementAt(length - 1, def)
1.938 + elem_type& SafeLastElement(elem_type& def) {
1.939 + return SafeElementAt(Length() - 1, def);
1.940 + }
1.941 +
1.942 + // Shorthand for SafeElementAt(length - 1, def)
1.943 + const elem_type& SafeLastElement(const elem_type& def) const {
1.944 + return SafeElementAt(Length() - 1, def);
1.945 + }
1.946 +
1.947 + //
1.948 + // Search methods
1.949 + //
1.950 +
1.951 + // This method searches for the first element in this array that is equal
1.952 + // to the given element.
1.953 + // @param item The item to search for.
1.954 + // @param comp The Comparator used to determine element equality.
1.955 + // @return true if the element was found.
1.956 + template<class Item, class Comparator>
1.957 + bool Contains(const Item& item, const Comparator& comp) const {
1.958 + return IndexOf(item, 0, comp) != NoIndex;
1.959 + }
1.960 +
1.961 + // This method searches for the first element in this array that is equal
1.962 + // to the given element. This method assumes that 'operator==' is defined
1.963 + // for elem_type.
1.964 + // @param item The item to search for.
1.965 + // @return true if the element was found.
1.966 + template<class Item>
1.967 + bool Contains(const Item& item) const {
1.968 + return IndexOf(item) != NoIndex;
1.969 + }
1.970 +
1.971 + // This method searches for the offset of the first element in this
1.972 + // array that is equal to the given element.
1.973 + // @param item The item to search for.
1.974 + // @param start The index to start from.
1.975 + // @param comp The Comparator used to determine element equality.
1.976 + // @return The index of the found element or NoIndex if not found.
1.977 + template<class Item, class Comparator>
1.978 + index_type IndexOf(const Item& item, index_type start,
1.979 + const Comparator& comp) const {
1.980 + const elem_type* iter = Elements() + start, *end = Elements() + Length();
1.981 + for (; iter != end; ++iter) {
1.982 + if (comp.Equals(*iter, item))
1.983 + return index_type(iter - Elements());
1.984 + }
1.985 + return NoIndex;
1.986 + }
1.987 +
1.988 + // This method searches for the offset of the first element in this
1.989 + // array that is equal to the given element. This method assumes
1.990 + // that 'operator==' is defined for elem_type.
1.991 + // @param item The item to search for.
1.992 + // @param start The index to start from.
1.993 + // @return The index of the found element or NoIndex if not found.
1.994 + template<class Item>
1.995 + index_type IndexOf(const Item& item, index_type start = 0) const {
1.996 + return IndexOf(item, start, nsDefaultComparator<elem_type, Item>());
1.997 + }
1.998 +
1.999 + // This method searches for the offset of the last element in this
1.1000 + // array that is equal to the given element.
1.1001 + // @param item The item to search for.
1.1002 + // @param start The index to start from. If greater than or equal to the
1.1003 + // length of the array, then the entire array is searched.
1.1004 + // @param comp The Comparator used to determine element equality.
1.1005 + // @return The index of the found element or NoIndex if not found.
1.1006 + template<class Item, class Comparator>
1.1007 + index_type LastIndexOf(const Item& item, index_type start,
1.1008 + const Comparator& comp) const {
1.1009 + size_type endOffset = start >= Length() ? Length() : start + 1;
1.1010 + const elem_type* end = Elements() - 1, *iter = end + endOffset;
1.1011 + for (; iter != end; --iter) {
1.1012 + if (comp.Equals(*iter, item))
1.1013 + return index_type(iter - Elements());
1.1014 + }
1.1015 + return NoIndex;
1.1016 + }
1.1017 +
1.1018 + // This method searches for the offset of the last element in this
1.1019 + // array that is equal to the given element. This method assumes
1.1020 + // that 'operator==' is defined for elem_type.
1.1021 + // @param item The item to search for.
1.1022 + // @param start The index to start from. If greater than or equal to the
1.1023 + // length of the array, then the entire array is searched.
1.1024 + // @return The index of the found element or NoIndex if not found.
1.1025 + template<class Item>
1.1026 + index_type LastIndexOf(const Item& item,
1.1027 + index_type start = NoIndex) const {
1.1028 + return LastIndexOf(item, start, nsDefaultComparator<elem_type, Item>());
1.1029 + }
1.1030 +
1.1031 + // This method searches for the offset for the element in this array
1.1032 + // that is equal to the given element. The array is assumed to be sorted.
1.1033 + // @param item The item to search for.
1.1034 + // @param comp The Comparator used.
1.1035 + // @return The index of the found element or NoIndex if not found.
1.1036 + template<class Item, class Comparator>
1.1037 + index_type BinaryIndexOf(const Item& item, const Comparator& comp) const {
1.1038 + index_type low = 0, high = Length();
1.1039 + while (high > low) {
1.1040 + index_type mid = (high + low) >> 1;
1.1041 + if (comp.Equals(ElementAt(mid), item))
1.1042 + return mid;
1.1043 + if (comp.LessThan(ElementAt(mid), item))
1.1044 + low = mid + 1;
1.1045 + else
1.1046 + high = mid;
1.1047 + }
1.1048 + return NoIndex;
1.1049 + }
1.1050 +
1.1051 + // This method searches for the offset for the element in this array
1.1052 + // that is equal to the given element. The array is assumed to be sorted.
1.1053 + // This method assumes that 'operator==' and 'operator<' are defined.
1.1054 + // @param item The item to search for.
1.1055 + // @return The index of the found element or NoIndex if not found.
1.1056 + template<class Item>
1.1057 + index_type BinaryIndexOf(const Item& item) const {
1.1058 + return BinaryIndexOf(item, nsDefaultComparator<elem_type, Item>());
1.1059 + }
1.1060 +
1.1061 + //
1.1062 + // Mutation methods
1.1063 + //
1.1064 + // This method call the destructor on each element of the array, empties it,
1.1065 + // but does not shrink the array's capacity.
1.1066 + // See also SetLengthAndRetainStorage.
1.1067 + // Make sure to call Compact() if needed to avoid keeping a huge array
1.1068 + // around.
1.1069 + void ClearAndRetainStorage() {
1.1070 + if (base_type::mHdr == EmptyHdr()) {
1.1071 + return;
1.1072 + }
1.1073 +
1.1074 + DestructRange(0, Length());
1.1075 + base_type::mHdr->mLength = 0;
1.1076 + }
1.1077 +
1.1078 + // This method modifies the length of the array, but unlike SetLength
1.1079 + // it doesn't deallocate/reallocate the current internal storage.
1.1080 + // The new length MUST be shorter than or equal to the current capacity.
1.1081 + // If the new length is larger than the existing length of the array,
1.1082 + // then new elements will be constructed using elem_type's default
1.1083 + // constructor. If shorter, elements will be destructed and removed.
1.1084 + // See also ClearAndRetainStorage.
1.1085 + // @param newLen The desired length of this array.
1.1086 + void SetLengthAndRetainStorage(size_type newLen) {
1.1087 + MOZ_ASSERT(newLen <= base_type::Capacity());
1.1088 + size_type oldLen = Length();
1.1089 + if (newLen > oldLen) {
1.1090 + InsertElementsAt(oldLen, newLen - oldLen);
1.1091 + return;
1.1092 + }
1.1093 + if (newLen < oldLen) {
1.1094 + DestructRange(newLen, oldLen - newLen);
1.1095 + base_type::mHdr->mLength = newLen;
1.1096 + }
1.1097 + }
1.1098 +
1.1099 + // This method replaces a range of elements in this array.
1.1100 + // @param start The starting index of the elements to replace.
1.1101 + // @param count The number of elements to replace. This may be zero to
1.1102 + // insert elements without removing any existing elements.
1.1103 + // @param array The values to copy into this array. Must be non-null,
1.1104 + // and these elements must not already exist in the array
1.1105 + // being modified.
1.1106 + // @param arrayLen The number of values to copy into this array.
1.1107 + // @return A pointer to the new elements in the array, or null if
1.1108 + // the operation failed due to insufficient memory.
1.1109 + template<class Item>
1.1110 + elem_type *ReplaceElementsAt(index_type start, size_type count,
1.1111 + const Item* array, size_type arrayLen) {
1.1112 + // Adjust memory allocation up-front to catch errors.
1.1113 + if (!Alloc::Successful(this->EnsureCapacity(Length() + arrayLen - count, sizeof(elem_type))))
1.1114 + return nullptr;
1.1115 + DestructRange(start, count);
1.1116 + this->ShiftData(start, count, arrayLen, sizeof(elem_type), MOZ_ALIGNOF(elem_type));
1.1117 + AssignRange(start, arrayLen, array);
1.1118 + return Elements() + start;
1.1119 + }
1.1120 +
1.1121 + // A variation on the ReplaceElementsAt method defined above.
1.1122 + template<class Item>
1.1123 + elem_type *ReplaceElementsAt(index_type start, size_type count,
1.1124 + const nsTArray<Item>& array) {
1.1125 + return ReplaceElementsAt(start, count, array.Elements(), array.Length());
1.1126 + }
1.1127 +
1.1128 + // A variation on the ReplaceElementsAt method defined above.
1.1129 + template<class Item>
1.1130 + elem_type *ReplaceElementsAt(index_type start, size_type count,
1.1131 + const Item& item) {
1.1132 + return ReplaceElementsAt(start, count, &item, 1);
1.1133 + }
1.1134 +
1.1135 + // A variation on the ReplaceElementsAt method defined above.
1.1136 + template<class Item>
1.1137 + elem_type *ReplaceElementAt(index_type index, const Item& item) {
1.1138 + return ReplaceElementsAt(index, 1, &item, 1);
1.1139 + }
1.1140 +
1.1141 + // A variation on the ReplaceElementsAt method defined above.
1.1142 + template<class Item>
1.1143 + elem_type *InsertElementsAt(index_type index, const Item* array,
1.1144 + size_type arrayLen) {
1.1145 + return ReplaceElementsAt(index, 0, array, arrayLen);
1.1146 + }
1.1147 +
1.1148 + // A variation on the ReplaceElementsAt method defined above.
1.1149 + template<class Item, class Allocator>
1.1150 + elem_type *InsertElementsAt(index_type index, const nsTArray_Impl<Item, Allocator>& array) {
1.1151 + return ReplaceElementsAt(index, 0, array.Elements(), array.Length());
1.1152 + }
1.1153 +
1.1154 + // A variation on the ReplaceElementsAt method defined above.
1.1155 + template<class Item>
1.1156 + elem_type *InsertElementAt(index_type index, const Item& item) {
1.1157 + return ReplaceElementsAt(index, 0, &item, 1);
1.1158 + }
1.1159 +
1.1160 + // Insert a new element without copy-constructing. This is useful to avoid
1.1161 + // temporaries.
1.1162 + // @return A pointer to the newly inserted element, or null on OOM.
1.1163 + elem_type* InsertElementAt(index_type index) {
1.1164 + if (!Alloc::Successful(this->EnsureCapacity(Length() + 1, sizeof(elem_type))))
1.1165 + return nullptr;
1.1166 + this->ShiftData(index, 0, 1, sizeof(elem_type), MOZ_ALIGNOF(elem_type));
1.1167 + elem_type *elem = Elements() + index;
1.1168 + elem_traits::Construct(elem);
1.1169 + return elem;
1.1170 + }
1.1171 +
1.1172 + // This method searches for the smallest index of an element that is strictly
1.1173 + // greater than |item|. If |item| is inserted at this index, the array will
1.1174 + // remain sorted and |item| would come after all elements that are equal to
1.1175 + // it. If |item| is greater than or equal to all elements in the array, the
1.1176 + // array length is returned.
1.1177 + //
1.1178 + // Note that consumers who want to know whether there are existing items equal
1.1179 + // to |item| in the array can just check that the return value here is > 0 and
1.1180 + // indexing into the previous slot gives something equal to |item|.
1.1181 + //
1.1182 + //
1.1183 + // @param item The item to search for.
1.1184 + // @param comp The Comparator used.
1.1185 + // @return The index of greatest element <= to |item|
1.1186 + // @precondition The array is sorted
1.1187 + template<class Item, class Comparator>
1.1188 + index_type
1.1189 + IndexOfFirstElementGt(const Item& item,
1.1190 + const Comparator& comp) const {
1.1191 + // invariant: low <= [idx] <= high
1.1192 + index_type low = 0, high = Length();
1.1193 + while (high > low) {
1.1194 + index_type mid = (high + low) >> 1;
1.1195 + // Comparators are not required to provide a LessThan(Item&, elem_type),
1.1196 + // so we can't do comp.LessThan(item, ElementAt(mid)).
1.1197 + if (comp.LessThan(ElementAt(mid), item) ||
1.1198 + comp.Equals(ElementAt(mid), item)) {
1.1199 + // item >= ElementAt(mid), so our desired index is at least mid+1.
1.1200 + low = mid + 1;
1.1201 + } else {
1.1202 + // item < ElementAt(mid). Our desired index is therefore at most mid.
1.1203 + high = mid;
1.1204 + }
1.1205 + }
1.1206 + MOZ_ASSERT(high == low);
1.1207 + return low;
1.1208 + }
1.1209 +
1.1210 + // A variation on the IndexOfFirstElementGt method defined above.
1.1211 + template<class Item>
1.1212 + index_type
1.1213 + IndexOfFirstElementGt(const Item& item) const {
1.1214 + return IndexOfFirstElementGt(item, nsDefaultComparator<elem_type, Item>());
1.1215 + }
1.1216 +
1.1217 + // Inserts |item| at such an index to guarantee that if the array
1.1218 + // was previously sorted, it will remain sorted after this
1.1219 + // insertion.
1.1220 + template<class Item, class Comparator>
1.1221 + elem_type *InsertElementSorted(const Item& item, const Comparator& comp) {
1.1222 + index_type index = IndexOfFirstElementGt(item, comp);
1.1223 + return InsertElementAt(index, item);
1.1224 + }
1.1225 +
1.1226 + // A variation on the InsertElementSorted method defined above.
1.1227 + template<class Item>
1.1228 + elem_type *InsertElementSorted(const Item& item) {
1.1229 + return InsertElementSorted(item, nsDefaultComparator<elem_type, Item>());
1.1230 + }
1.1231 +
1.1232 + // This method appends elements to the end of this array.
1.1233 + // @param array The elements to append to this array.
1.1234 + // @param arrayLen The number of elements to append to this array.
1.1235 + // @return A pointer to the new elements in the array, or null if
1.1236 + // the operation failed due to insufficient memory.
1.1237 + template<class Item>
1.1238 + elem_type *AppendElements(const Item* array, size_type arrayLen) {
1.1239 + if (!Alloc::Successful(this->EnsureCapacity(Length() + arrayLen, sizeof(elem_type))))
1.1240 + return nullptr;
1.1241 + index_type len = Length();
1.1242 + AssignRange(len, arrayLen, array);
1.1243 + this->IncrementLength(arrayLen);
1.1244 + return Elements() + len;
1.1245 + }
1.1246 +
1.1247 + // A variation on the AppendElements method defined above.
1.1248 + template<class Item, class Allocator>
1.1249 + elem_type *AppendElements(const nsTArray_Impl<Item, Allocator>& array) {
1.1250 + return AppendElements(array.Elements(), array.Length());
1.1251 + }
1.1252 +
1.1253 + // A variation on the AppendElements method defined above.
1.1254 + template<class Item>
1.1255 + elem_type *AppendElement(const Item& item) {
1.1256 + return AppendElements(&item, 1);
1.1257 + }
1.1258 +
1.1259 + // Append new elements without copy-constructing. This is useful to avoid
1.1260 + // temporaries.
1.1261 + // @return A pointer to the newly appended elements, or null on OOM.
1.1262 + elem_type *AppendElements(size_type count) {
1.1263 + if (!Alloc::Successful(this->EnsureCapacity(Length() + count, sizeof(elem_type))))
1.1264 + return nullptr;
1.1265 + elem_type *elems = Elements() + Length();
1.1266 + size_type i;
1.1267 + for (i = 0; i < count; ++i) {
1.1268 + elem_traits::Construct(elems + i);
1.1269 + }
1.1270 + this->IncrementLength(count);
1.1271 + return elems;
1.1272 + }
1.1273 +
1.1274 + // Append a new element without copy-constructing. This is useful to avoid
1.1275 + // temporaries.
1.1276 + // @return A pointer to the newly appended element, or null on OOM.
1.1277 + elem_type *AppendElement() {
1.1278 + return AppendElements(1);
1.1279 + }
1.1280 +
1.1281 + // Move all elements from another array to the end of this array without
1.1282 + // calling copy constructors or destructors.
1.1283 + // @return A pointer to the newly appended elements, or null on OOM.
1.1284 + template<class Item, class Allocator>
1.1285 + elem_type *MoveElementsFrom(nsTArray_Impl<Item, Allocator>& array) {
1.1286 + MOZ_ASSERT(&array != this, "argument must be different array");
1.1287 + index_type len = Length();
1.1288 + index_type otherLen = array.Length();
1.1289 + if (!Alloc::Successful(this->EnsureCapacity(len + otherLen, sizeof(elem_type))))
1.1290 + return nullptr;
1.1291 + copy_type::CopyElements(Elements() + len, array.Elements(), otherLen, sizeof(elem_type));
1.1292 + this->IncrementLength(otherLen);
1.1293 + array.ShiftData(0, otherLen, 0, sizeof(elem_type), MOZ_ALIGNOF(elem_type));
1.1294 + return Elements() + len;
1.1295 + }
1.1296 +
1.1297 + // This method removes a range of elements from this array.
1.1298 + // @param start The starting index of the elements to remove.
1.1299 + // @param count The number of elements to remove.
1.1300 + void RemoveElementsAt(index_type start, size_type count) {
1.1301 + MOZ_ASSERT(count == 0 || start < Length(), "Invalid start index");
1.1302 + MOZ_ASSERT(start + count <= Length(), "Invalid length");
1.1303 + // Check that the previous assert didn't overflow
1.1304 + MOZ_ASSERT(start <= start + count, "Start index plus length overflows");
1.1305 + DestructRange(start, count);
1.1306 + this->ShiftData(start, count, 0, sizeof(elem_type), MOZ_ALIGNOF(elem_type));
1.1307 + }
1.1308 +
1.1309 + // A variation on the RemoveElementsAt method defined above.
1.1310 + void RemoveElementAt(index_type index) {
1.1311 + RemoveElementsAt(index, 1);
1.1312 + }
1.1313 +
1.1314 + // A variation on the RemoveElementsAt method defined above.
1.1315 + void Clear() {
1.1316 + RemoveElementsAt(0, Length());
1.1317 + }
1.1318 +
1.1319 + // This helper function combines IndexOf with RemoveElementAt to "search
1.1320 + // and destroy" the first element that is equal to the given element.
1.1321 + // @param item The item to search for.
1.1322 + // @param comp The Comparator used to determine element equality.
1.1323 + // @return true if the element was found
1.1324 + template<class Item, class Comparator>
1.1325 + bool RemoveElement(const Item& item, const Comparator& comp) {
1.1326 + index_type i = IndexOf(item, 0, comp);
1.1327 + if (i == NoIndex)
1.1328 + return false;
1.1329 +
1.1330 + RemoveElementAt(i);
1.1331 + return true;
1.1332 + }
1.1333 +
1.1334 + // A variation on the RemoveElement method defined above that assumes
1.1335 + // that 'operator==' is defined for elem_type.
1.1336 + template<class Item>
1.1337 + bool RemoveElement(const Item& item) {
1.1338 + return RemoveElement(item, nsDefaultComparator<elem_type, Item>());
1.1339 + }
1.1340 +
1.1341 + // This helper function combines IndexOfFirstElementGt with
1.1342 + // RemoveElementAt to "search and destroy" the last element that
1.1343 + // is equal to the given element.
1.1344 + // @param item The item to search for.
1.1345 + // @param comp The Comparator used to determine element equality.
1.1346 + // @return true if the element was found
1.1347 + template<class Item, class Comparator>
1.1348 + bool RemoveElementSorted(const Item& item, const Comparator& comp) {
1.1349 + index_type index = IndexOfFirstElementGt(item, comp);
1.1350 + if (index > 0 && comp.Equals(ElementAt(index - 1), item)) {
1.1351 + RemoveElementAt(index - 1);
1.1352 + return true;
1.1353 + }
1.1354 + return false;
1.1355 + }
1.1356 +
1.1357 + // A variation on the RemoveElementSorted method defined above.
1.1358 + template<class Item>
1.1359 + bool RemoveElementSorted(const Item& item) {
1.1360 + return RemoveElementSorted(item, nsDefaultComparator<elem_type, Item>());
1.1361 + }
1.1362 +
1.1363 + // This method causes the elements contained in this array and the given
1.1364 + // array to be swapped.
1.1365 + template<class Allocator>
1.1366 + typename Alloc::ResultType
1.1367 + SwapElements(nsTArray_Impl<E, Allocator>& other) {
1.1368 + return Alloc::Result(this->SwapArrayElements(other, sizeof(elem_type),
1.1369 + MOZ_ALIGNOF(elem_type)));
1.1370 + }
1.1371 +
1.1372 + //
1.1373 + // Allocation
1.1374 + //
1.1375 +
1.1376 + // This method may increase the capacity of this array object by the
1.1377 + // specified amount. This method may be called in advance of several
1.1378 + // AppendElement operations to minimize heap re-allocations. This method
1.1379 + // will not reduce the number of elements in this array.
1.1380 + // @param capacity The desired capacity of this array.
1.1381 + // @return True if the operation succeeded; false if we ran out of memory
1.1382 + typename Alloc::ResultType SetCapacity(size_type capacity) {
1.1383 + return Alloc::Result(this->EnsureCapacity(capacity, sizeof(elem_type)));
1.1384 + }
1.1385 +
1.1386 + // This method modifies the length of the array. If the new length is
1.1387 + // larger than the existing length of the array, then new elements will be
1.1388 + // constructed using elem_type's default constructor. Otherwise, this call
1.1389 + // removes elements from the array (see also RemoveElementsAt).
1.1390 + // @param newLen The desired length of this array.
1.1391 + // @return True if the operation succeeded; false otherwise.
1.1392 + // See also TruncateLength if the new length is guaranteed to be
1.1393 + // smaller than the old.
1.1394 + typename Alloc::ResultType SetLength(size_type newLen) {
1.1395 + size_type oldLen = Length();
1.1396 + if (newLen > oldLen) {
1.1397 + return Alloc::ConvertBoolToResultType(InsertElementsAt(oldLen, newLen - oldLen) != nullptr);
1.1398 + }
1.1399 +
1.1400 + TruncateLength(newLen);
1.1401 + return Alloc::ConvertBoolToResultType(true);
1.1402 + }
1.1403 +
1.1404 + // This method modifies the length of the array, but may only be
1.1405 + // called when the new length is shorter than the old. It can
1.1406 + // therefore be called when elem_type has no default constructor,
1.1407 + // unlike SetLength. It removes elements from the array (see also
1.1408 + // RemoveElementsAt).
1.1409 + // @param newLen The desired length of this array.
1.1410 + void TruncateLength(size_type newLen) {
1.1411 + size_type oldLen = Length();
1.1412 + NS_ABORT_IF_FALSE(newLen <= oldLen,
1.1413 + "caller should use SetLength instead");
1.1414 + RemoveElementsAt(newLen, oldLen - newLen);
1.1415 + }
1.1416 +
1.1417 + // This method ensures that the array has length at least the given
1.1418 + // length. If the current length is shorter than the given length,
1.1419 + // then new elements will be constructed using elem_type's default
1.1420 + // constructor.
1.1421 + // @param minLen The desired minimum length of this array.
1.1422 + // @return True if the operation succeeded; false otherwise.
1.1423 +typename Alloc::ResultType EnsureLengthAtLeast(size_type minLen) {
1.1424 + size_type oldLen = Length();
1.1425 + if (minLen > oldLen) {
1.1426 + return Alloc::ConvertBoolToResultType(!!InsertElementsAt(oldLen, minLen - oldLen));
1.1427 + }
1.1428 + return Alloc::ConvertBoolToResultType(true);
1.1429 + }
1.1430 +
1.1431 + // This method inserts elements into the array, constructing
1.1432 + // them using elem_type's default constructor.
1.1433 + // @param index the place to insert the new elements. This must be no
1.1434 + // greater than the current length of the array.
1.1435 + // @param count the number of elements to insert
1.1436 + elem_type *InsertElementsAt(index_type index, size_type count) {
1.1437 + if (!base_type::InsertSlotsAt(index, count, sizeof(elem_type), MOZ_ALIGNOF(elem_type))) {
1.1438 + return nullptr;
1.1439 + }
1.1440 +
1.1441 + // Initialize the extra array elements
1.1442 + elem_type *iter = Elements() + index, *end = iter + count;
1.1443 + for (; iter != end; ++iter) {
1.1444 + elem_traits::Construct(iter);
1.1445 + }
1.1446 +
1.1447 + return Elements() + index;
1.1448 + }
1.1449 +
1.1450 + // This method inserts elements into the array, constructing them
1.1451 + // elem_type's copy constructor (or whatever one-arg constructor
1.1452 + // happens to match the Item type).
1.1453 + // @param index the place to insert the new elements. This must be no
1.1454 + // greater than the current length of the array.
1.1455 + // @param count the number of elements to insert.
1.1456 + // @param item the value to use when constructing the new elements.
1.1457 + template<class Item>
1.1458 + elem_type *InsertElementsAt(index_type index, size_type count,
1.1459 + const Item& item) {
1.1460 + if (!base_type::InsertSlotsAt(index, count, sizeof(elem_type), MOZ_ALIGNOF(elem_type))) {
1.1461 + return nullptr;
1.1462 + }
1.1463 +
1.1464 + // Initialize the extra array elements
1.1465 + elem_type *iter = Elements() + index, *end = iter + count;
1.1466 + for (; iter != end; ++iter) {
1.1467 + elem_traits::Construct(iter, item);
1.1468 + }
1.1469 +
1.1470 + return Elements() + index;
1.1471 + }
1.1472 +
1.1473 + // This method may be called to minimize the memory used by this array.
1.1474 + void Compact() {
1.1475 + ShrinkCapacity(sizeof(elem_type), MOZ_ALIGNOF(elem_type));
1.1476 + }
1.1477 +
1.1478 + //
1.1479 + // Sorting
1.1480 + //
1.1481 +
1.1482 + // This function is meant to be used with the NS_QuickSort function. It
1.1483 + // maps the callback API expected by NS_QuickSort to the Comparator API
1.1484 + // used by nsTArray_Impl. See nsTArray_Impl::Sort.
1.1485 + template<class Comparator>
1.1486 + static int Compare(const void* e1, const void* e2, void *data) {
1.1487 + const Comparator* c = reinterpret_cast<const Comparator*>(data);
1.1488 + const elem_type* a = static_cast<const elem_type*>(e1);
1.1489 + const elem_type* b = static_cast<const elem_type*>(e2);
1.1490 + return c->LessThan(*a, *b) ? -1 : (c->Equals(*a, *b) ? 0 : 1);
1.1491 + }
1.1492 +
1.1493 + // This method sorts the elements of the array. It uses the LessThan
1.1494 + // method defined on the given Comparator object to collate elements.
1.1495 + // @param comp The Comparator used to collate elements.
1.1496 + template<class Comparator>
1.1497 + void Sort(const Comparator& comp) {
1.1498 + NS_QuickSort(Elements(), Length(), sizeof(elem_type),
1.1499 + Compare<Comparator>, const_cast<Comparator*>(&comp));
1.1500 + }
1.1501 +
1.1502 + // A variation on the Sort method defined above that assumes that
1.1503 + // 'operator<' is defined for elem_type.
1.1504 + void Sort() {
1.1505 + Sort(nsDefaultComparator<elem_type, elem_type>());
1.1506 + }
1.1507 +
1.1508 + //
1.1509 + // Binary Heap
1.1510 + //
1.1511 +
1.1512 + // Sorts the array into a binary heap.
1.1513 + // @param comp The Comparator used to create the heap
1.1514 + template<class Comparator>
1.1515 + void MakeHeap(const Comparator& comp) {
1.1516 + if (!Length()) {
1.1517 + return;
1.1518 + }
1.1519 + index_type index = (Length() - 1) / 2;
1.1520 + do {
1.1521 + SiftDown(index, comp);
1.1522 + } while (index--);
1.1523 + }
1.1524 +
1.1525 + // A variation on the MakeHeap method defined above.
1.1526 + void MakeHeap() {
1.1527 + MakeHeap(nsDefaultComparator<elem_type, elem_type>());
1.1528 + }
1.1529 +
1.1530 + // Adds an element to the heap
1.1531 + // @param item The item to add
1.1532 + // @param comp The Comparator used to sift-up the item
1.1533 + template<class Item, class Comparator>
1.1534 + elem_type *PushHeap(const Item& item, const Comparator& comp) {
1.1535 + if (!base_type::InsertSlotsAt(Length(), 1, sizeof(elem_type), MOZ_ALIGNOF(elem_type))) {
1.1536 + return nullptr;
1.1537 + }
1.1538 + // Sift up the new node
1.1539 + elem_type *elem = Elements();
1.1540 + index_type index = Length() - 1;
1.1541 + index_type parent_index = (index - 1) / 2;
1.1542 + while (index && comp.LessThan(elem[parent_index], item)) {
1.1543 + elem[index] = elem[parent_index];
1.1544 + index = parent_index;
1.1545 + parent_index = (index - 1) / 2;
1.1546 + }
1.1547 + elem[index] = item;
1.1548 + return &elem[index];
1.1549 + }
1.1550 +
1.1551 + // A variation on the PushHeap method defined above.
1.1552 + template<class Item>
1.1553 + elem_type *PushHeap(const Item& item) {
1.1554 + return PushHeap(item, nsDefaultComparator<elem_type, Item>());
1.1555 + }
1.1556 +
1.1557 + // Delete the root of the heap and restore the heap
1.1558 + // @param comp The Comparator used to restore the heap
1.1559 + template<class Comparator>
1.1560 + void PopHeap(const Comparator& comp) {
1.1561 + if (!Length()) {
1.1562 + return;
1.1563 + }
1.1564 + index_type last_index = Length() - 1;
1.1565 + elem_type *elem = Elements();
1.1566 + elem[0] = elem[last_index];
1.1567 + TruncateLength(last_index);
1.1568 + if (Length()) {
1.1569 + SiftDown(0, comp);
1.1570 + }
1.1571 + }
1.1572 +
1.1573 + // A variation on the PopHeap method defined above.
1.1574 + void PopHeap() {
1.1575 + PopHeap(nsDefaultComparator<elem_type, elem_type>());
1.1576 + }
1.1577 +
1.1578 +protected:
1.1579 + using base_type::Hdr;
1.1580 + using base_type::ShrinkCapacity;
1.1581 +
1.1582 + // This method invokes elem_type's destructor on a range of elements.
1.1583 + // @param start The index of the first element to destroy.
1.1584 + // @param count The number of elements to destroy.
1.1585 + void DestructRange(index_type start, size_type count) {
1.1586 + elem_type *iter = Elements() + start, *end = iter + count;
1.1587 + for (; iter != end; ++iter) {
1.1588 + elem_traits::Destruct(iter);
1.1589 + }
1.1590 + }
1.1591 +
1.1592 + // This method invokes elem_type's copy-constructor on a range of elements.
1.1593 + // @param start The index of the first element to construct.
1.1594 + // @param count The number of elements to construct.
1.1595 + // @param values The array of elements to copy.
1.1596 + template<class Item>
1.1597 + void AssignRange(index_type start, size_type count,
1.1598 + const Item *values) {
1.1599 + AssignRangeAlgorithm<mozilla::IsPod<Item>::value,
1.1600 + mozilla::IsSame<Item, elem_type>::value>
1.1601 + ::implementation(Elements(), start, count, values);
1.1602 + }
1.1603 +
1.1604 + // This method sifts an item down to its proper place in a binary heap
1.1605 + // @param index The index of the node to start sifting down from
1.1606 + // @param comp The Comparator used to sift down
1.1607 + template<class Comparator>
1.1608 + void SiftDown(index_type index, const Comparator& comp) {
1.1609 + elem_type *elem = Elements();
1.1610 + elem_type item = elem[index];
1.1611 + index_type end = Length() - 1;
1.1612 + while ((index * 2) < end) {
1.1613 + const index_type left = (index * 2) + 1;
1.1614 + const index_type right = (index * 2) + 2;
1.1615 + const index_type parent_index = index;
1.1616 + if (comp.LessThan(item, elem[left])) {
1.1617 + if (left < end &&
1.1618 + comp.LessThan(elem[left], elem[right])) {
1.1619 + index = right;
1.1620 + } else {
1.1621 + index = left;
1.1622 + }
1.1623 + } else if (left < end &&
1.1624 + comp.LessThan(item, elem[right])) {
1.1625 + index = right;
1.1626 + } else {
1.1627 + break;
1.1628 + }
1.1629 + elem[parent_index] = elem[index];
1.1630 + }
1.1631 + elem[index] = item;
1.1632 + }
1.1633 +};
1.1634 +
1.1635 +template <typename E, typename Alloc>
1.1636 +inline void
1.1637 +ImplCycleCollectionUnlink(nsTArray_Impl<E, Alloc>& aField)
1.1638 +{
1.1639 + aField.Clear();
1.1640 +}
1.1641 +
1.1642 +template <typename E, typename Alloc>
1.1643 +inline void
1.1644 +ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
1.1645 + nsTArray_Impl<E, Alloc>& aField,
1.1646 + const char* aName,
1.1647 + uint32_t aFlags = 0)
1.1648 +{
1.1649 + aFlags |= CycleCollectionEdgeNameArrayFlag;
1.1650 + uint32_t length = aField.Length();
1.1651 + for (uint32_t i = 0; i < length; ++i) {
1.1652 + ImplCycleCollectionTraverse(aCallback, aField[i], aName, aFlags);
1.1653 + }
1.1654 +}
1.1655 +
1.1656 +//
1.1657 +// nsTArray is an infallible vector class. See the comment at the top of this
1.1658 +// file for more details.
1.1659 +//
1.1660 +template <class E>
1.1661 +class nsTArray : public nsTArray_Impl<E, nsTArrayInfallibleAllocator>
1.1662 +{
1.1663 +public:
1.1664 + typedef nsTArray_Impl<E, nsTArrayInfallibleAllocator> base_type;
1.1665 + typedef nsTArray<E> self_type;
1.1666 + typedef typename base_type::size_type size_type;
1.1667 +
1.1668 + nsTArray() {}
1.1669 + explicit nsTArray(size_type capacity) : base_type(capacity) {}
1.1670 + explicit nsTArray(const nsTArray& other) : base_type(other) {}
1.1671 +
1.1672 + template<class Allocator>
1.1673 + explicit nsTArray(const nsTArray_Impl<E, Allocator>& other) : base_type(other) {}
1.1674 +};
1.1675 +
1.1676 +//
1.1677 +// FallibleTArray is a fallible vector class.
1.1678 +//
1.1679 +template <class E>
1.1680 +class FallibleTArray : public nsTArray_Impl<E, nsTArrayFallibleAllocator>
1.1681 +{
1.1682 +public:
1.1683 + typedef nsTArray_Impl<E, nsTArrayFallibleAllocator> base_type;
1.1684 + typedef FallibleTArray<E> self_type;
1.1685 + typedef typename base_type::size_type size_type;
1.1686 +
1.1687 + FallibleTArray() {}
1.1688 + explicit FallibleTArray(size_type capacity) : base_type(capacity) {}
1.1689 + explicit FallibleTArray(const FallibleTArray<E>& other) : base_type(other) {}
1.1690 +
1.1691 + template<class Allocator>
1.1692 + explicit FallibleTArray(const nsTArray_Impl<E, Allocator>& other) : base_type(other) {}
1.1693 +};
1.1694 +
1.1695 +//
1.1696 +// nsAutoArrayBase is a base class for AutoFallibleTArray and nsAutoTArray.
1.1697 +// You shouldn't use this class directly.
1.1698 +//
1.1699 +template <class TArrayBase, uint32_t N>
1.1700 +class nsAutoArrayBase : public TArrayBase
1.1701 +{
1.1702 +public:
1.1703 + typedef nsAutoArrayBase<TArrayBase, N> self_type;
1.1704 + typedef TArrayBase base_type;
1.1705 + typedef typename base_type::Header Header;
1.1706 + typedef typename base_type::elem_type elem_type;
1.1707 +
1.1708 + template<typename Allocator>
1.1709 + self_type& operator=(const nsTArray_Impl<elem_type, Allocator>& other) {
1.1710 + base_type::operator=(other);
1.1711 + return *this;
1.1712 + }
1.1713 +
1.1714 +protected:
1.1715 + nsAutoArrayBase() {
1.1716 + Init();
1.1717 + }
1.1718 +
1.1719 + // We need this constructor because nsAutoTArray and friends all have
1.1720 + // implicit copy-constructors. If we don't have this method, those
1.1721 + // copy-constructors will call nsAutoArrayBase's implicit copy-constructor,
1.1722 + // which won't call Init() and set up the auto buffer!
1.1723 + nsAutoArrayBase(const self_type &aOther) {
1.1724 + Init();
1.1725 + this->AppendElements(aOther);
1.1726 + }
1.1727 +
1.1728 +private:
1.1729 + // nsTArray_base casts itself as an nsAutoArrayBase in order to get a pointer
1.1730 + // to mAutoBuf.
1.1731 + template<class Allocator, class Copier>
1.1732 + friend class nsTArray_base;
1.1733 +
1.1734 + void Init() {
1.1735 + static_assert(MOZ_ALIGNOF(elem_type) <= 8,
1.1736 + "can't handle alignments greater than 8, "
1.1737 + "see nsTArray_base::UsesAutoArrayBuffer()");
1.1738 + // Temporary work around for VS2012 RC compiler crash
1.1739 + Header** phdr = base_type::PtrToHdr();
1.1740 + *phdr = reinterpret_cast<Header*>(&mAutoBuf);
1.1741 + (*phdr)->mLength = 0;
1.1742 + (*phdr)->mCapacity = N;
1.1743 + (*phdr)->mIsAutoArray = 1;
1.1744 +
1.1745 + MOZ_ASSERT(base_type::GetAutoArrayBuffer(MOZ_ALIGNOF(elem_type)) ==
1.1746 + reinterpret_cast<Header*>(&mAutoBuf),
1.1747 + "GetAutoArrayBuffer needs to be fixed");
1.1748 + }
1.1749 +
1.1750 + // Declare mAutoBuf aligned to the maximum of the header's alignment and
1.1751 + // elem_type's alignment. We need to use a union rather than
1.1752 + // MOZ_ALIGNED_DECL because GCC is picky about what goes into
1.1753 + // __attribute__((aligned(foo))).
1.1754 + union {
1.1755 + char mAutoBuf[sizeof(nsTArrayHeader) + N * sizeof(elem_type)];
1.1756 + // Do the max operation inline to ensure that it is a compile-time constant.
1.1757 + mozilla::AlignedElem<(MOZ_ALIGNOF(Header) > MOZ_ALIGNOF(elem_type))
1.1758 + ? MOZ_ALIGNOF(Header) : MOZ_ALIGNOF(elem_type)> mAlign;
1.1759 + };
1.1760 +};
1.1761 +
1.1762 +//
1.1763 +// nsAutoTArray<E, N> is an infallible vector class with N elements of inline
1.1764 +// storage. If you try to store more than N elements inside an
1.1765 +// nsAutoTArray<E, N>, we'll call malloc() and store them all on the heap.
1.1766 +//
1.1767 +// Note that you can cast an nsAutoTArray<E, N> to
1.1768 +// |const AutoFallibleTArray<E, N>&|.
1.1769 +//
1.1770 +template<class E, uint32_t N>
1.1771 +class nsAutoTArray : public nsAutoArrayBase<nsTArray<E>, N>
1.1772 +{
1.1773 + typedef nsAutoTArray<E, N> self_type;
1.1774 + typedef nsAutoArrayBase<nsTArray<E>, N> Base;
1.1775 +
1.1776 +public:
1.1777 + nsAutoTArray() {}
1.1778 +
1.1779 + template<typename Allocator>
1.1780 + explicit nsAutoTArray(const nsTArray_Impl<E, Allocator>& other) {
1.1781 + Base::AppendElements(other);
1.1782 + }
1.1783 +
1.1784 + operator const AutoFallibleTArray<E, N>&() const {
1.1785 + return *reinterpret_cast<const AutoFallibleTArray<E, N>*>(this);
1.1786 + }
1.1787 +};
1.1788 +
1.1789 +//
1.1790 +// AutoFallibleTArray<E, N> is a fallible vector class with N elements of
1.1791 +// inline storage.
1.1792 +//
1.1793 +template<class E, uint32_t N>
1.1794 +class AutoFallibleTArray : public nsAutoArrayBase<FallibleTArray<E>, N>
1.1795 +{
1.1796 + typedef AutoFallibleTArray<E, N> self_type;
1.1797 + typedef nsAutoArrayBase<FallibleTArray<E>, N> Base;
1.1798 +
1.1799 +public:
1.1800 + AutoFallibleTArray() {}
1.1801 +
1.1802 + template<typename Allocator>
1.1803 + explicit AutoFallibleTArray(const nsTArray_Impl<E, Allocator>& other) {
1.1804 + Base::AppendElements(other);
1.1805 + }
1.1806 +
1.1807 + operator const nsAutoTArray<E, N>&() const {
1.1808 + return *reinterpret_cast<const nsAutoTArray<E, N>*>(this);
1.1809 + }
1.1810 +};
1.1811 +
1.1812 +// Assert that nsAutoTArray doesn't have any extra padding inside.
1.1813 +//
1.1814 +// It's important that the data stored in this auto array takes up a multiple of
1.1815 +// 8 bytes; e.g. nsAutoTArray<uint32_t, 1> wouldn't work. Since nsAutoTArray
1.1816 +// contains a pointer, its size must be a multiple of alignof(void*). (This is
1.1817 +// because any type may be placed into an array, and there's no padding between
1.1818 +// elements of an array.) The compiler pads the end of the structure to
1.1819 +// enforce this rule.
1.1820 +//
1.1821 +// If we used nsAutoTArray<uint32_t, 1> below, this assertion would fail on a
1.1822 +// 64-bit system, where the compiler inserts 4 bytes of padding at the end of
1.1823 +// the auto array to make its size a multiple of alignof(void*) == 8 bytes.
1.1824 +
1.1825 +static_assert(sizeof(nsAutoTArray<uint32_t, 2>) ==
1.1826 + sizeof(void*) + sizeof(nsTArrayHeader) + sizeof(uint32_t) * 2,
1.1827 + "nsAutoTArray shouldn't contain any extra padding, "
1.1828 + "see the comment");
1.1829 +
1.1830 +// Definitions of nsTArray_Impl methods
1.1831 +#include "nsTArray-inl.h"
1.1832 +
1.1833 +#endif // nsTArray_h__
