1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */ 3 /* This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #ifndef nsTArray_h__ 8 #define nsTArray_h__ 9 10 #include "nsTArrayForwardDeclare.h" 11 #include "mozilla/Alignment.h" 12 #include "mozilla/Assertions.h" 13 #include "mozilla/Attributes.h" 14 #include "mozilla/BinarySearch.h" 15 #include "mozilla/fallible.h" 16 #include "mozilla/Function.h" 17 #include "mozilla/MathAlgorithms.h" 18 #include "mozilla/MemoryReporting.h" 19 #include "mozilla/Move.h" 20 #include "mozilla/ReverseIterator.h" 21 #include "mozilla/TypeTraits.h" 22 23 #include <string.h> 24 25 #include "nsCycleCollectionNoteChild.h" 26 #include "nsAlgorithm.h" 27 #include "nscore.h" 28 #include "nsQuickSort.h" 29 #include "nsDebug.h" 30 #include "nsISupportsImpl.h" 31 #include "nsRegionFwd.h" 32 #include <initializer_list> 33 #include <new> 34 35 namespace JS { 36 template<class T> 37 class Heap; 38 class ObjectPtr; 39 } /* namespace JS */ 40 41 class nsRegion; 42 namespace mozilla { 43 namespace layers { 44 struct TileClient; 45 } // namespace layers 46 } // namespace mozilla 47 48 namespace mozilla { 49 struct SerializedStructuredCloneBuffer; 50 } // namespace mozilla 51 52 namespace mozilla { 53 namespace dom { 54 namespace ipc { 55 class StructuredCloneData; 56 } // namespace ipc 57 } // namespace dom 58 } // namespace mozilla 59 60 namespace mozilla { 61 namespace dom { 62 class ClonedMessageData; 63 class MessagePortMessage; 64 namespace indexedDB { 65 struct StructuredCloneReadInfo; 66 class SerializedStructuredCloneReadInfo; 67 class ObjectStoreCursorResponse; 68 } // namespace indexedDB 69 } // namespace dom 70 } // namespace mozilla 71 72 class JSStructuredCloneData; 73 74 // 75 // nsTArray is a resizable array class, like std::vector. 76 // 77 // Unlike std::vector, which follows C++'s construction/destruction rules, 78 // nsTArray assumes that your "T" can be memmoved()'ed safely. 79 // 80 // The public classes defined in this header are 81 // 82 // nsTArray<T>, 83 // FallibleTArray<T>, 84 // AutoTArray<T, N>, and 85 // 86 // nsTArray and AutoTArray are infallible by default. To opt-in to fallible 87 // behaviour, use the `mozilla::fallible` parameter and check the return value. 88 // 89 // If you just want to declare the nsTArray types (e.g., if you're in a header 90 // file and don't need the full nsTArray definitions) consider including 91 // nsTArrayForwardDeclare.h instead of nsTArray.h. 92 // 93 // The template parameter (i.e., T in nsTArray<T>) specifies the type of the 94 // elements and has the following requirements: 95 // 96 // T MUST be safely memmove()'able. 97 // T MUST define a copy-constructor. 98 // T MAY define operator< for sorting. 99 // T MAY define operator== for searching. 100 // 101 // (Note that the memmove requirement may be relaxed for certain types - see 102 // nsTArray_CopyChooser below.) 103 // 104 // For methods taking a Comparator instance, the Comparator must be a class 105 // defining the following methods: 106 // 107 // class Comparator { 108 // public: 109 // /** @return True if the elements are equals; false otherwise. */ 110 // bool Equals(const elem_type& a, const Item& b) const; 111 // 112 // /** @return True if (a < b); false otherwise. */ 113 // bool LessThan(const elem_type& a, const Item& b) const; 114 // }; 115 // 116 // The Equals method is used for searching, and the LessThan method is used for 117 // searching and sorting. The |Item| type above can be arbitrary, but must 118 // match the Item type passed to the sort or search function. 119 // 120 121 122 // 123 // nsTArrayFallibleResult and nsTArrayInfallibleResult types are proxy types 124 // which are used because you cannot use a templated type which is bound to 125 // void as an argument to a void function. In order to work around that, we 126 // encode either a void or a boolean inside these proxy objects, and pass them 127 // to the aforementioned function instead, and then use the type information to 128 // decide what to do in the function. 129 // 130 // Note that public nsTArray methods should never return a proxy type. Such 131 // types are only meant to be used in the internal nsTArray helper methods. 132 // Public methods returning non-proxy types cannot be called from other 133 // nsTArray members. 134 // 135 struct nsTArrayFallibleResult 136 { 137 // Note: allows implicit conversions from and to bool nsTArrayFallibleResultnsTArrayFallibleResult138 MOZ_IMPLICIT nsTArrayFallibleResult(bool aResult) : mResult(aResult) {} 139 140 MOZ_IMPLICIT operator bool() { return mResult; } 141 142 private: 143 bool mResult; 144 }; 145 146 struct nsTArrayInfallibleResult 147 { 148 }; 149 150 // 151 // nsTArray*Allocators must all use the same |free()|, to allow swap()'ing 152 // between fallible and infallible variants. 153 // 154 155 struct nsTArrayFallibleAllocatorBase 156 { 157 typedef bool ResultType; 158 typedef nsTArrayFallibleResult ResultTypeProxy; 159 ResultnsTArrayFallibleAllocatorBase160 static ResultType Result(ResultTypeProxy aResult) { return aResult; } SuccessfulnsTArrayFallibleAllocatorBase161 static bool Successful(ResultTypeProxy aResult) { return aResult; } SuccessResultnsTArrayFallibleAllocatorBase162 static ResultTypeProxy SuccessResult() { return true; } FailureResultnsTArrayFallibleAllocatorBase163 static ResultTypeProxy FailureResult() { return false; } ConvertBoolToResultTypensTArrayFallibleAllocatorBase164 static ResultType ConvertBoolToResultType(bool aValue) { return aValue; } 165 }; 166 167 struct nsTArrayInfallibleAllocatorBase 168 { 169 typedef void ResultType; 170 typedef nsTArrayInfallibleResult ResultTypeProxy; 171 ResultnsTArrayInfallibleAllocatorBase172 static ResultType Result(ResultTypeProxy aResult) {} SuccessfulnsTArrayInfallibleAllocatorBase173 static bool Successful(ResultTypeProxy) { return true; } SuccessResultnsTArrayInfallibleAllocatorBase174 static ResultTypeProxy SuccessResult() { return ResultTypeProxy(); } 175 FailureResultnsTArrayInfallibleAllocatorBase176 static ResultTypeProxy FailureResult() 177 { 178 NS_RUNTIMEABORT("Infallible nsTArray should never fail"); 179 return ResultTypeProxy(); 180 } 181 ConvertBoolToResultTypensTArrayInfallibleAllocatorBase182 static ResultType ConvertBoolToResultType(bool aValue) 183 { 184 if (!aValue) { 185 NS_RUNTIMEABORT("infallible nsTArray should never convert false to ResultType"); 186 } 187 } 188 }; 189 190 struct nsTArrayFallibleAllocator : nsTArrayFallibleAllocatorBase 191 { MallocnsTArrayFallibleAllocator192 static void* Malloc(size_t aSize) { return malloc(aSize); } ReallocnsTArrayFallibleAllocator193 static void* Realloc(void* aPtr, size_t aSize) 194 { 195 return realloc(aPtr, aSize); 196 } 197 FreensTArrayFallibleAllocator198 static void Free(void* aPtr) { free(aPtr); } SizeTooBignsTArrayFallibleAllocator199 static void SizeTooBig(size_t) {} 200 }; 201 202 #if defined(MOZALLOC_HAVE_XMALLOC) 203 #include "mozilla/mozalloc_abort.h" 204 205 struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase 206 { MallocnsTArrayInfallibleAllocator207 static void* Malloc(size_t aSize) { return moz_xmalloc(aSize); } ReallocnsTArrayInfallibleAllocator208 static void* Realloc(void* aPtr, size_t aSize) 209 { 210 return moz_xrealloc(aPtr, aSize); 211 } 212 FreensTArrayInfallibleAllocator213 static void Free(void* aPtr) { free(aPtr); } SizeTooBignsTArrayInfallibleAllocator214 static void SizeTooBig(size_t aSize) { NS_ABORT_OOM(aSize); } 215 }; 216 217 #else 218 #include <stdlib.h> 219 220 struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase 221 { MallocnsTArrayInfallibleAllocator222 static void* Malloc(size_t aSize) 223 { 224 void* ptr = malloc(aSize); 225 if (MOZ_UNLIKELY(!ptr)) { 226 NS_ABORT_OOM(aSize); 227 } 228 return ptr; 229 } 230 ReallocnsTArrayInfallibleAllocator231 static void* Realloc(void* aPtr, size_t aSize) 232 { 233 void* newptr = realloc(aPtr, aSize); 234 if (MOZ_UNLIKELY(!newptr && aSize)) { 235 NS_ABORT_OOM(aSize); 236 } 237 return newptr; 238 } 239 FreensTArrayInfallibleAllocator240 static void Free(void* aPtr) { free(aPtr); } SizeTooBignsTArrayInfallibleAllocator241 static void SizeTooBig(size_t aSize) { NS_ABORT_OOM(aSize); } 242 }; 243 244 #endif 245 246 // nsTArray_base stores elements into the space allocated beyond 247 // sizeof(*this). This is done to minimize the size of the nsTArray 248 // object when it is empty. 249 struct nsTArrayHeader 250 { 251 static nsTArrayHeader sEmptyHdr; 252 253 uint32_t mLength; 254 uint32_t mCapacity : 31; 255 uint32_t mIsAutoArray : 1; 256 }; 257 258 // This class provides a SafeElementAt method to nsTArray<T*> which does 259 // not take a second default value parameter. 260 template<class E, class Derived> 261 struct nsTArray_SafeElementAtHelper 262 { 263 typedef E* elem_type; 264 typedef size_t index_type; 265 266 // No implementation is provided for these two methods, and that is on 267 // purpose, since we don't support these functions on non-pointer type 268 // instantiations. 269 elem_type& SafeElementAt(index_type aIndex); 270 const elem_type& SafeElementAt(index_type aIndex) const; 271 }; 272 273 template<class E, class Derived> 274 struct nsTArray_SafeElementAtHelper<E*, Derived> 275 { 276 typedef E* elem_type; 277 //typedef const E* const_elem_type; XXX: see below 278 typedef size_t index_type; 279 280 elem_type SafeElementAt(index_type aIndex) 281 { 282 return static_cast<Derived*>(this)->SafeElementAt(aIndex, nullptr); 283 } 284 285 // XXX: Probably should return const_elem_type, but callsites must be fixed. 286 // Also, the use of const_elem_type for nsTArray<xpcGCCallback> in 287 // xpcprivate.h causes build failures on Windows because xpcGCCallback is a 288 // function pointer and MSVC doesn't like qualifying it with |const|. 289 elem_type SafeElementAt(index_type aIndex) const 290 { 291 return static_cast<const Derived*>(this)->SafeElementAt(aIndex, nullptr); 292 } 293 }; 294 295 // E is the base type that the smart pointer is templated over; the 296 // smart pointer can act as E*. 297 template<class E, class Derived> 298 struct nsTArray_SafeElementAtSmartPtrHelper 299 { 300 typedef E* elem_type; 301 typedef const E* const_elem_type; 302 typedef size_t index_type; 303 304 elem_type SafeElementAt(index_type aIndex) 305 { 306 return static_cast<Derived*>(this)->SafeElementAt(aIndex, nullptr); 307 } 308 309 // XXX: Probably should return const_elem_type, but callsites must be fixed. 310 elem_type SafeElementAt(index_type aIndex) const 311 { 312 return static_cast<const Derived*>(this)->SafeElementAt(aIndex, nullptr); 313 } 314 }; 315 316 template<class T> class nsCOMPtr; 317 318 template<class E, class Derived> 319 struct nsTArray_SafeElementAtHelper<nsCOMPtr<E>, Derived> 320 : public nsTArray_SafeElementAtSmartPtrHelper<E, Derived> 321 { 322 }; 323 324 template<class E, class Derived> 325 struct nsTArray_SafeElementAtHelper<RefPtr<E>, Derived> 326 : public nsTArray_SafeElementAtSmartPtrHelper<E, Derived> 327 { 328 }; 329 330 namespace mozilla { 331 template<class T> class OwningNonNull; 332 } // namespace mozilla 333 334 template<class E, class Derived> 335 struct nsTArray_SafeElementAtHelper<mozilla::OwningNonNull<E>, Derived> 336 { 337 typedef E* elem_type; 338 typedef const E* const_elem_type; 339 typedef size_t index_type; 340 341 elem_type SafeElementAt(index_type aIndex) 342 { 343 if (aIndex < static_cast<Derived*>(this)->Length()) { 344 return static_cast<Derived*>(this)->ElementAt(aIndex); 345 } 346 return nullptr; 347 } 348 349 // XXX: Probably should return const_elem_type, but callsites must be fixed. 350 elem_type SafeElementAt(index_type aIndex) const 351 { 352 if (aIndex < static_cast<const Derived*>(this)->Length()) { 353 return static_cast<const Derived*>(this)->ElementAt(aIndex); 354 } 355 return nullptr; 356 } 357 }; 358 359 // Servo bindings. 360 extern "C" void Gecko_EnsureTArrayCapacity(void* aArray, 361 size_t aCapacity, 362 size_t aElementSize); 363 extern "C" void Gecko_ClearPODTArray(void* aArray, 364 size_t aElementSize, 365 size_t aElementAlign); 366 367 MOZ_NORETURN MOZ_COLD void 368 InvalidArrayIndex_CRASH(size_t aIndex, size_t aLength); 369 370 // 371 // This class serves as a base class for nsTArray. It shouldn't be used 372 // directly. It holds common implementation code that does not depend on the 373 // element type of the nsTArray. 374 // 375 template<class Alloc, class Copy> 376 class nsTArray_base 377 { 378 // Allow swapping elements with |nsTArray_base|s created using a 379 // different allocator. This is kosher because all allocators use 380 // the same free(). 381 template<class Allocator, class Copier> 382 friend class nsTArray_base; 383 friend void Gecko_EnsureTArrayCapacity(void* aArray, size_t aCapacity, 384 size_t aElemSize); 385 friend void Gecko_ClearPODTArray(void* aTArray, size_t aElementSize, 386 size_t aElementAlign); 387 388 protected: 389 typedef nsTArrayHeader Header; 390 391 public: 392 typedef size_t size_type; 393 typedef size_t index_type; 394 395 // @return The number of elements in the array. 396 size_type Length() const { return mHdr->mLength; } 397 398 // @return True if the array is empty or false otherwise. 399 bool IsEmpty() const { return Length() == 0; } 400 401 // @return The number of elements that can fit in the array without forcing 402 // the array to be re-allocated. The length of an array is always less 403 // than or equal to its capacity. 404 size_type Capacity() const { return mHdr->mCapacity; } 405 406 #ifdef DEBUG 407 void* DebugGetHeader() const { return mHdr; } 408 #endif 409 410 protected: 411 nsTArray_base(); 412 413 ~nsTArray_base(); 414 415 // Resize the storage if necessary to achieve the requested capacity. 416 // @param aCapacity The requested number of array elements. 417 // @param aElemSize The size of an array element. 418 // @return False if insufficient memory is available; true otherwise. 419 template<typename ActualAlloc> 420 typename ActualAlloc::ResultTypeProxy EnsureCapacity(size_type aCapacity, 421 size_type aElemSize); 422 423 // Tries to resize the storage to the minimum required amount. If this fails, 424 // the array is left as-is. 425 // @param aElemSize The size of an array element. 426 // @param aElemAlign The alignment in bytes of an array element. 427 void ShrinkCapacity(size_type aElemSize, size_t aElemAlign); 428 429 // This method may be called to resize a "gap" in the array by shifting 430 // elements around. It updates mLength appropriately. If the resulting 431 // array has zero elements, then the array's memory is free'd. 432 // @param aStart The starting index of the gap. 433 // @param aOldLen The current length of the gap. 434 // @param aNewLen The desired length of the gap. 435 // @param aElemSize The size of an array element. 436 // @param aElemAlign The alignment in bytes of an array element. 437 template<typename ActualAlloc> 438 void ShiftData(index_type aStart, size_type aOldLen, size_type aNewLen, 439 size_type aElemSize, size_t aElemAlign); 440 441 // This method increments the length member of the array's header. 442 // Note that mHdr may actually be sEmptyHdr in the case where a 443 // zero-length array is inserted into our array. But then aNum should 444 // always be 0. 445 void IncrementLength(size_t aNum) 446 { 447 if (mHdr == EmptyHdr()) { 448 if (MOZ_UNLIKELY(aNum != 0)) { 449 // Writing a non-zero length to the empty header would be extremely bad. 450 MOZ_CRASH(); 451 } 452 } else { 453 mHdr->mLength += aNum; 454 } 455 } 456 457 // This method inserts blank slots into the array. 458 // @param aIndex the place to insert the new elements. This must be no 459 // greater than the current length of the array. 460 // @param aCount the number of slots to insert 461 // @param aElementSize the size of an array element. 462 // @param aElemAlign the alignment in bytes of an array element. 463 template<typename ActualAlloc> 464 bool InsertSlotsAt(index_type aIndex, size_type aCount, 465 size_type aElementSize, size_t aElemAlign); 466 467 template<typename ActualAlloc, class Allocator> 468 typename ActualAlloc::ResultTypeProxy 469 SwapArrayElements(nsTArray_base<Allocator, Copy>& aOther, 470 size_type aElemSize, 471 size_t aElemAlign); 472 473 // This is an RAII class used in SwapArrayElements. 474 class IsAutoArrayRestorer 475 { 476 public: 477 IsAutoArrayRestorer(nsTArray_base<Alloc, Copy>& aArray, size_t aElemAlign); 478 ~IsAutoArrayRestorer(); 479 480 private: 481 nsTArray_base<Alloc, Copy>& mArray; 482 size_t mElemAlign; 483 bool mIsAuto; 484 }; 485 486 // Helper function for SwapArrayElements. Ensures that if the array 487 // is an AutoTArray that it doesn't use the built-in buffer. 488 template<typename ActualAlloc> 489 bool EnsureNotUsingAutoArrayBuffer(size_type aElemSize); 490 491 // Returns true if this nsTArray is an AutoTArray with a built-in buffer. 492 bool IsAutoArray() const { return mHdr->mIsAutoArray; } 493 494 // Returns a Header for the built-in buffer of this AutoTArray. 495 Header* GetAutoArrayBuffer(size_t aElemAlign) 496 { 497 MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this"); 498 return GetAutoArrayBufferUnsafe(aElemAlign); 499 } 500 const Header* GetAutoArrayBuffer(size_t aElemAlign) const 501 { 502 MOZ_ASSERT(IsAutoArray(), "Should be an auto array to call this"); 503 return GetAutoArrayBufferUnsafe(aElemAlign); 504 } 505 506 // Returns a Header for the built-in buffer of this AutoTArray, but doesn't 507 // assert that we are an AutoTArray. 508 Header* GetAutoArrayBufferUnsafe(size_t aElemAlign) 509 { 510 return const_cast<Header*>(static_cast<const nsTArray_base<Alloc, Copy>*>( 511 this)->GetAutoArrayBufferUnsafe(aElemAlign)); 512 } 513 const Header* GetAutoArrayBufferUnsafe(size_t aElemAlign) const; 514 515 // Returns true if this is an AutoTArray and it currently uses the 516 // built-in buffer to store its elements. 517 bool UsesAutoArrayBuffer() const; 518 519 // The array's elements (prefixed with a Header). This pointer is never 520 // null. If the array is empty, then this will point to sEmptyHdr. 521 Header* mHdr; 522 523 Header* Hdr() const { return mHdr; } 524 Header** PtrToHdr() { return &mHdr; } 525 static Header* EmptyHdr() { return &Header::sEmptyHdr; } 526 }; 527 528 // 529 // This class defines convenience functions for element specific operations. 530 // Specialize this template if necessary. 531 // 532 template<class E> 533 class nsTArrayElementTraits 534 { 535 public: 536 // Invoke the default constructor in place. 537 static inline void Construct(E* aE) 538 { 539 // Do NOT call "E()"! That triggers C++ "default initialization" 540 // which zeroes out POD ("plain old data") types such as regular 541 // ints. We don't want that because it can be a performance issue 542 // and people don't expect it; nsTArray should work like a regular 543 // C/C++ array in this respect. 544 new (static_cast<void*>(aE)) E; 545 } 546 // Invoke the copy-constructor in place. 547 template<class A> 548 static inline void Construct(E* aE, A&& aArg) 549 { 550 typedef typename mozilla::RemoveCV<E>::Type E_NoCV; 551 typedef typename mozilla::RemoveCV<A>::Type A_NoCV; 552 static_assert(!mozilla::IsSame<E_NoCV*, A_NoCV>::value, 553 "For safety, we disallow constructing nsTArray<E> elements " 554 "from E* pointers. See bug 960591."); 555 new (static_cast<void*>(aE)) E(mozilla::Forward<A>(aArg)); 556 } 557 // Invoke the destructor in place. 558 static inline void Destruct(E* aE) { aE->~E(); } 559 }; 560 561 // The default comparator used by nsTArray 562 template<class A, class B> 563 class nsDefaultComparator 564 { 565 public: 566 bool Equals(const A& aA, const B& aB) const { return aA == aB; } 567 bool LessThan(const A& aA, const B& aB) const { return aA < aB; } 568 }; 569 570 template<bool IsPod, bool IsSameType> 571 struct AssignRangeAlgorithm 572 { 573 template<class Item, class ElemType, class IndexType, class SizeType> 574 static void implementation(ElemType* aElements, IndexType aStart, 575 SizeType aCount, const Item* aValues) 576 { 577 ElemType* iter = aElements + aStart; 578 ElemType* end = iter + aCount; 579 for (; iter != end; ++iter, ++aValues) { 580 nsTArrayElementTraits<ElemType>::Construct(iter, *aValues); 581 } 582 } 583 }; 584 585 template<> 586 struct AssignRangeAlgorithm<true, true> 587 { 588 template<class Item, class ElemType, class IndexType, class SizeType> 589 static void implementation(ElemType* aElements, IndexType aStart, 590 SizeType aCount, const Item* aValues) 591 { 592 memcpy(aElements + aStart, aValues, aCount * sizeof(ElemType)); 593 } 594 }; 595 596 // 597 // Normally elements are copied with memcpy and memmove, but for some element 598 // types that is problematic. The nsTArray_CopyChooser template class can be 599 // specialized to ensure that copying calls constructors and destructors 600 // instead, as is done below for JS::Heap<E> elements. 601 // 602 603 // 604 // A class that defines how to copy elements using memcpy/memmove. 605 // 606 struct nsTArray_CopyWithMemutils 607 { 608 const static bool allowRealloc = true; 609 610 static void MoveNonOverlappingRegionWithHeader(void* aDest, const void* aSrc, 611 size_t aCount, size_t aElemSize) 612 { 613 memcpy(aDest, aSrc, sizeof(nsTArrayHeader) + aCount * aElemSize); 614 } 615 616 static void MoveOverlappingRegion(void* aDest, void* aSrc, size_t aCount, 617 size_t aElemSize) 618 { 619 memmove(aDest, aSrc, aCount * aElemSize); 620 } 621 622 static void MoveNonOverlappingRegion(void* aDest, void* aSrc, size_t aCount, 623 size_t aElemSize) 624 { 625 memcpy(aDest, aSrc, aCount * aElemSize); 626 } 627 }; 628 629 // 630 // A template class that defines how to copy elements calling their constructors 631 // and destructors appropriately. 632 // 633 template<class ElemType> 634 struct nsTArray_CopyWithConstructors 635 { 636 typedef nsTArrayElementTraits<ElemType> traits; 637 638 const static bool allowRealloc = false; 639 640 static void MoveNonOverlappingRegionWithHeader(void* aDest, void* aSrc, size_t aCount, 641 size_t aElemSize) 642 { 643 nsTArrayHeader* destHeader = static_cast<nsTArrayHeader*>(aDest); 644 nsTArrayHeader* srcHeader = static_cast<nsTArrayHeader*>(aSrc); 645 *destHeader = *srcHeader; 646 MoveNonOverlappingRegion(static_cast<uint8_t*>(aDest) + sizeof(nsTArrayHeader), 647 static_cast<uint8_t*>(aSrc) + sizeof(nsTArrayHeader), 648 aCount, aElemSize); 649 } 650 651 // These functions are defined by analogy with memmove and memcpy. 652 // What they actually do is slightly different: MoveOverlappingRegion 653 // checks to see which direction the movement needs to take place, 654 // whether from back-to-front of the range to be moved or from 655 // front-to-back. MoveNonOverlappingRegion assumes that moving 656 // front-to-back is always valid. So they're really more like 657 // std::move{_backward,} in that respect. We keep these names because 658 // we think they read slightly better, and MoveNonOverlappingRegion is 659 // only ever called on overlapping regions from MoveOverlappingRegion. 660 static void MoveOverlappingRegion(void* aDest, void* aSrc, size_t aCount, 661 size_t aElemSize) 662 { 663 ElemType* destElem = static_cast<ElemType*>(aDest); 664 ElemType* srcElem = static_cast<ElemType*>(aSrc); 665 ElemType* destElemEnd = destElem + aCount; 666 ElemType* srcElemEnd = srcElem + aCount; 667 if (destElem == srcElem) { 668 return; // In practice, we don't do this. 669 } 670 671 // Figure out whether to copy back-to-front or front-to-back. 672 if (srcElemEnd > destElem && srcElemEnd < destElemEnd) { 673 while (destElemEnd != destElem) { 674 --destElemEnd; 675 --srcElemEnd; 676 traits::Construct(destElemEnd, mozilla::Move(*srcElemEnd)); 677 traits::Destruct(srcElemEnd); 678 } 679 } else { 680 MoveNonOverlappingRegion(aDest, aSrc, aCount, aElemSize); 681 } 682 } 683 684 static void MoveNonOverlappingRegion(void* aDest, void* aSrc, size_t aCount, 685 size_t aElemSize) 686 { 687 ElemType* destElem = static_cast<ElemType*>(aDest); 688 ElemType* srcElem = static_cast<ElemType*>(aSrc); 689 ElemType* destElemEnd = destElem + aCount; 690 #ifdef DEBUG 691 ElemType* srcElemEnd = srcElem + aCount; 692 MOZ_ASSERT(srcElemEnd <= destElem || srcElemEnd > destElemEnd); 693 #endif 694 while (destElem != destElemEnd) { 695 traits::Construct(destElem, mozilla::Move(*srcElem)); 696 traits::Destruct(srcElem); 697 ++destElem; 698 ++srcElem; 699 } 700 } 701 }; 702 703 // 704 // The default behaviour is to use memcpy/memmove for everything. 705 // 706 template<class E> 707 struct MOZ_NEEDS_MEMMOVABLE_TYPE nsTArray_CopyChooser 708 { 709 using Type = nsTArray_CopyWithMemutils; 710 }; 711 712 // 713 // Some classes require constructors/destructors to be called, so they are 714 // specialized here. 715 // 716 #define DECLARE_USE_COPY_CONSTRUCTORS(T) \ 717 template<> \ 718 struct nsTArray_CopyChooser<T> \ 719 { \ 720 using Type = nsTArray_CopyWithConstructors<T>; \ 721 }; 722 723 #define DECLARE_USE_COPY_CONSTRUCTORS_FOR_TEMPLATE(T) \ 724 template<typename S> \ 725 struct nsTArray_CopyChooser<T<S>> \ 726 { \ 727 using Type = nsTArray_CopyWithConstructors<T<S>>; \ 728 }; 729 730 DECLARE_USE_COPY_CONSTRUCTORS_FOR_TEMPLATE(JS::Heap) 731 732 DECLARE_USE_COPY_CONSTRUCTORS(nsRegion) 733 DECLARE_USE_COPY_CONSTRUCTORS(nsIntRegion) 734 DECLARE_USE_COPY_CONSTRUCTORS(mozilla::layers::TileClient) 735 DECLARE_USE_COPY_CONSTRUCTORS(mozilla::SerializedStructuredCloneBuffer) 736 DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::ipc::StructuredCloneData) 737 DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::ClonedMessageData) 738 DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::indexedDB::StructuredCloneReadInfo); 739 DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::indexedDB::ObjectStoreCursorResponse) 740 DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::indexedDB::SerializedStructuredCloneReadInfo); 741 DECLARE_USE_COPY_CONSTRUCTORS(JSStructuredCloneData) 742 DECLARE_USE_COPY_CONSTRUCTORS(mozilla::dom::MessagePortMessage) 743 DECLARE_USE_COPY_CONSTRUCTORS(JS::ObjectPtr) 744 745 746 // 747 // Base class for nsTArray_Impl that is templated on element type and derived 748 // nsTArray_Impl class, to allow extra conversions to be added for specific 749 // types. 750 // 751 template<class E, class Derived> 752 struct nsTArray_TypedBase : public nsTArray_SafeElementAtHelper<E, Derived> 753 { 754 }; 755 756 // 757 // Specialization of nsTArray_TypedBase for arrays containing JS::Heap<E> 758 // elements. 759 // 760 // These conversions are safe because JS::Heap<E> and E share the same 761 // representation, and since the result of the conversions are const references 762 // we won't miss any barriers. 763 // 764 // The static_cast is necessary to obtain the correct address for the derived 765 // class since we are a base class used in multiple inheritance. 766 // 767 template<class E, class Derived> 768 struct nsTArray_TypedBase<JS::Heap<E>, Derived> 769 : public nsTArray_SafeElementAtHelper<JS::Heap<E>, Derived> 770 { 771 operator const nsTArray<E>&() 772 { 773 static_assert(sizeof(E) == sizeof(JS::Heap<E>), 774 "JS::Heap<E> must be binary compatible with E."); 775 Derived* self = static_cast<Derived*>(this); 776 return *reinterpret_cast<nsTArray<E> *>(self); 777 } 778 779 operator const FallibleTArray<E>&() 780 { 781 Derived* self = static_cast<Derived*>(this); 782 return *reinterpret_cast<FallibleTArray<E> *>(self); 783 } 784 }; 785 786 namespace detail { 787 788 template<class Item, class Comparator> 789 struct ItemComparatorEq 790 { 791 const Item& mItem; 792 const Comparator& mComp; 793 ItemComparatorEq(const Item& aItem, const Comparator& aComp) 794 : mItem(aItem) 795 , mComp(aComp) 796 {} 797 template<class T> 798 int operator()(const T& aElement) const { 799 if (mComp.Equals(aElement, mItem)) { 800 return 0; 801 } 802 803 return mComp.LessThan(aElement, mItem) ? 1 : -1; 804 } 805 }; 806 807 template<class Item, class Comparator> 808 struct ItemComparatorFirstElementGT 809 { 810 const Item& mItem; 811 const Comparator& mComp; 812 ItemComparatorFirstElementGT(const Item& aItem, const Comparator& aComp) 813 : mItem(aItem) 814 , mComp(aComp) 815 {} 816 template<class T> 817 int operator()(const T& aElement) const { 818 if (mComp.LessThan(aElement, mItem) || 819 mComp.Equals(aElement, mItem)) { 820 return 1; 821 } else { 822 return -1; 823 } 824 } 825 }; 826 827 } // namespace detail 828 829 // 830 // nsTArray_Impl contains most of the guts supporting nsTArray, FallibleTArray, 831 // AutoTArray. 832 // 833 // The only situation in which you might need to use nsTArray_Impl in your code 834 // is if you're writing code which mutates a TArray which may or may not be 835 // infallible. 836 // 837 // Code which merely reads from a TArray which may or may not be infallible can 838 // simply cast the TArray to |const nsTArray&|; both fallible and infallible 839 // TArrays can be cast to |const nsTArray&|. 840 // 841 template<class E, class Alloc> 842 class nsTArray_Impl 843 : public nsTArray_base<Alloc, typename nsTArray_CopyChooser<E>::Type> 844 , public nsTArray_TypedBase<E, nsTArray_Impl<E, Alloc>> 845 { 846 private: 847 typedef nsTArrayFallibleAllocator FallibleAlloc; 848 typedef nsTArrayInfallibleAllocator InfallibleAlloc; 849 850 public: 851 typedef typename nsTArray_CopyChooser<E>::Type copy_type; 852 typedef nsTArray_base<Alloc, copy_type> base_type; 853 typedef typename base_type::size_type size_type; 854 typedef typename base_type::index_type index_type; 855 typedef E elem_type; 856 typedef nsTArray_Impl<E, Alloc> self_type; 857 typedef nsTArrayElementTraits<E> elem_traits; 858 typedef nsTArray_SafeElementAtHelper<E, self_type> safeelementat_helper_type; 859 typedef elem_type* iterator; 860 typedef const elem_type* const_iterator; 861 typedef mozilla::ReverseIterator<elem_type*> reverse_iterator; 862 typedef mozilla::ReverseIterator<const elem_type*> const_reverse_iterator; 863 864 using safeelementat_helper_type::SafeElementAt; 865 using base_type::EmptyHdr; 866 867 // A special value that is used to indicate an invalid or unknown index 868 // into the array. 869 static const index_type NoIndex = index_type(-1); 870 871 using base_type::Length; 872 873 // 874 // Finalization method 875 // 876 877 ~nsTArray_Impl() { Clear(); } 878 879 // 880 // Initialization methods 881 // 882 883 nsTArray_Impl() {} 884 885 // Initialize this array and pre-allocate some number of elements. 886 explicit nsTArray_Impl(size_type aCapacity) { SetCapacity(aCapacity); } 887 888 // Initialize this array with an r-value. 889 // Allow different types of allocators, since the allocator doesn't matter. 890 template<typename Allocator> 891 explicit nsTArray_Impl(nsTArray_Impl<E, Allocator>&& aOther) 892 { 893 SwapElements(aOther); 894 } 895 896 // The array's copy-constructor performs a 'deep' copy of the given array. 897 // @param aOther The array object to copy. 898 // 899 // It's very important that we declare this method as taking |const 900 // self_type&| as opposed to taking |const nsTArray_Impl<E, OtherAlloc>| for 901 // an arbitrary OtherAlloc. 902 // 903 // If we don't declare a constructor taking |const self_type&|, C++ generates 904 // a copy-constructor for this class which merely copies the object's 905 // members, which is obviously wrong. 906 // 907 // You can pass an nsTArray_Impl<E, OtherAlloc> to this method because 908 // nsTArray_Impl<E, X> can be cast to const nsTArray_Impl<E, Y>&. So the 909 // effect on the API is the same as if we'd declared this method as taking 910 // |const nsTArray_Impl<E, OtherAlloc>&|. 911 explicit nsTArray_Impl(const self_type& aOther) { AppendElements(aOther); } 912 913 explicit nsTArray_Impl(std::initializer_list<E> aIL) { AppendElements(aIL.begin(), aIL.size()); } 914 // Allow converting to a const array with a different kind of allocator, 915 // Since the allocator doesn't matter for const arrays 916 template<typename Allocator> 917 operator const nsTArray_Impl<E, Allocator>&() const 918 { 919 return *reinterpret_cast<const nsTArray_Impl<E, Allocator>*>(this); 920 } 921 // And we have to do this for our subclasses too 922 operator const nsTArray<E>&() const 923 { 924 return *reinterpret_cast<const InfallibleTArray<E>*>(this); 925 } 926 operator const FallibleTArray<E>&() const 927 { 928 return *reinterpret_cast<const FallibleTArray<E>*>(this); 929 } 930 931 // The array's assignment operator performs a 'deep' copy of the given 932 // array. It is optimized to reuse existing storage if possible. 933 // @param aOther The array object to copy. 934 self_type& operator=(const self_type& aOther) 935 { 936 if (this != &aOther) { 937 ReplaceElementsAt(0, Length(), aOther.Elements(), aOther.Length()); 938 } 939 return *this; 940 } 941 942 // The array's move assignment operator steals the underlying data from 943 // the other array. 944 // @param other The array object to move from. 945 self_type& operator=(self_type&& aOther) 946 { 947 if (this != &aOther) { 948 Clear(); 949 SwapElements(aOther); 950 } 951 return *this; 952 } 953 954 // Return true if this array has the same length and the same 955 // elements as |aOther|. 956 template<typename Allocator> 957 bool operator==(const nsTArray_Impl<E, Allocator>& aOther) const 958 { 959 size_type len = Length(); 960 if (len != aOther.Length()) { 961 return false; 962 } 963 964 // XXX std::equal would be as fast or faster here 965 for (index_type i = 0; i < len; ++i) { 966 if (!(operator[](i) == aOther[i])) { 967 return false; 968 } 969 } 970 971 return true; 972 } 973 974 // Return true if this array does not have the same length and the same 975 // elements as |aOther|. 976 bool operator!=(const self_type& aOther) const { return !operator==(aOther); } 977 978 template<typename Allocator> 979 self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther) 980 { 981 ReplaceElementsAt(0, Length(), aOther.Elements(), aOther.Length()); 982 return *this; 983 } 984 985 template<typename Allocator> 986 self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther) 987 { 988 Clear(); 989 SwapElements(aOther); 990 return *this; 991 } 992 993 // @return The amount of memory used by this nsTArray_Impl, excluding 994 // sizeof(*this). If you want to measure anything hanging off the array, you 995 // must iterate over the elements and measure them individually; hence the 996 // "Shallow" prefix. 997 size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const 998 { 999 if (this->UsesAutoArrayBuffer() || Hdr() == EmptyHdr()) { 1000 return 0; 1001 } 1002 return aMallocSizeOf(this->Hdr()); 1003 } 1004 1005 // @return The amount of memory used by this nsTArray_Impl, including 1006 // sizeof(*this). If you want to measure anything hanging off the array, you 1007 // must iterate over the elements and measure them individually; hence the 1008 // "Shallow" prefix. 1009 size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const 1010 { 1011 return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf); 1012 } 1013 1014 // 1015 // Accessor methods 1016 // 1017 1018 // This method provides direct access to the array elements. 1019 // @return A pointer to the first element of the array. If the array is 1020 // empty, then this pointer must not be dereferenced. 1021 elem_type* Elements() { return reinterpret_cast<elem_type*>(Hdr() + 1); } 1022 1023 // This method provides direct, readonly access to the array elements. 1024 // @return A pointer to the first element of the array. If the array is 1025 // empty, then this pointer must not be dereferenced. 1026 const elem_type* Elements() const 1027 { 1028 return reinterpret_cast<const elem_type*>(Hdr() + 1); 1029 } 1030 1031 // This method provides direct access to an element of the array. The given 1032 // index must be within the array bounds. 1033 // @param aIndex The index of an element in the array. 1034 // @return A reference to the i'th element of the array. 1035 elem_type& ElementAt(index_type aIndex) 1036 { 1037 if (MOZ_UNLIKELY(aIndex >= Length())) { 1038 InvalidArrayIndex_CRASH(aIndex, Length()); 1039 } 1040 return Elements()[aIndex]; 1041 } 1042 1043 // This method provides direct, readonly access to an element of the array 1044 // The given index must be within the array bounds. 1045 // @param aIndex The index of an element in the array. 1046 // @return A const reference to the i'th element of the array. 1047 const elem_type& ElementAt(index_type aIndex) const 1048 { 1049 if (MOZ_UNLIKELY(aIndex >= Length())) { 1050 InvalidArrayIndex_CRASH(aIndex, Length()); 1051 } 1052 return Elements()[aIndex]; 1053 } 1054 1055 // This method provides direct access to an element of the array in a bounds 1056 // safe manner. If the requested index is out of bounds the provided default 1057 // value is returned. 1058 // @param aIndex The index of an element in the array. 1059 // @param aDef The value to return if the index is out of bounds. 1060 elem_type& SafeElementAt(index_type aIndex, elem_type& aDef) 1061 { 1062 return aIndex < Length() ? Elements()[aIndex] : aDef; 1063 } 1064 1065 // This method provides direct access to an element of the array in a bounds 1066 // safe manner. If the requested index is out of bounds the provided default 1067 // value is returned. 1068 // @param aIndex The index of an element in the array. 1069 // @param aDef The value to return if the index is out of bounds. 1070 const elem_type& SafeElementAt(index_type aIndex, const elem_type& aDef) const 1071 { 1072 return aIndex < Length() ? Elements()[aIndex] : aDef; 1073 } 1074 1075 // Shorthand for ElementAt(aIndex) 1076 elem_type& operator[](index_type aIndex) { return ElementAt(aIndex); } 1077 1078 // Shorthand for ElementAt(aIndex) 1079 const elem_type& operator[](index_type aIndex) const { return ElementAt(aIndex); } 1080 1081 // Shorthand for ElementAt(length - 1) 1082 elem_type& LastElement() { return ElementAt(Length() - 1); } 1083 1084 // Shorthand for ElementAt(length - 1) 1085 const elem_type& LastElement() const { return ElementAt(Length() - 1); } 1086 1087 // Shorthand for SafeElementAt(length - 1, def) 1088 elem_type& SafeLastElement(elem_type& aDef) 1089 { 1090 return SafeElementAt(Length() - 1, aDef); 1091 } 1092 1093 // Shorthand for SafeElementAt(length - 1, def) 1094 const elem_type& SafeLastElement(const elem_type& aDef) const 1095 { 1096 return SafeElementAt(Length() - 1, aDef); 1097 } 1098 1099 // Methods for range-based for loops. 1100 iterator begin() { return Elements(); } 1101 const_iterator begin() const { return Elements(); } 1102 const_iterator cbegin() const { return begin(); } 1103 iterator end() { return Elements() + Length(); } 1104 const_iterator end() const { return Elements() + Length(); } 1105 const_iterator cend() const { return end(); } 1106 1107 // Methods for reverse iterating. 1108 reverse_iterator rbegin() { return reverse_iterator(end()); } 1109 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 1110 const_reverse_iterator crbegin() const { return rbegin(); } 1111 reverse_iterator rend() { return reverse_iterator(begin()); } 1112 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 1113 const_reverse_iterator crend() const { return rend(); } 1114 1115 // 1116 // Search methods 1117 // 1118 1119 // This method searches for the first element in this array that is equal 1120 // to the given element. 1121 // @param aItem The item to search for. 1122 // @param aComp The Comparator used to determine element equality. 1123 // @return true if the element was found. 1124 template<class Item, class Comparator> 1125 bool Contains(const Item& aItem, const Comparator& aComp) const 1126 { 1127 return IndexOf(aItem, 0, aComp) != NoIndex; 1128 } 1129 1130 // This method searches for the first element in this array that is equal 1131 // to the given element. This method assumes that 'operator==' is defined 1132 // for elem_type. 1133 // @param aItem The item to search for. 1134 // @return true if the element was found. 1135 template<class Item> 1136 bool Contains(const Item& aItem) const 1137 { 1138 return IndexOf(aItem) != NoIndex; 1139 } 1140 1141 // This method searches for the offset of the first element in this 1142 // array that is equal to the given element. 1143 // @param aItem The item to search for. 1144 // @param aStart The index to start from. 1145 // @param aComp The Comparator used to determine element equality. 1146 // @return The index of the found element or NoIndex if not found. 1147 template<class Item, class Comparator> 1148 index_type IndexOf(const Item& aItem, index_type aStart, 1149 const Comparator& aComp) const 1150 { 1151 const elem_type* iter = Elements() + aStart; 1152 const elem_type* iend = Elements() + Length(); 1153 for (; iter != iend; ++iter) { 1154 if (aComp.Equals(*iter, aItem)) { 1155 return index_type(iter - Elements()); 1156 } 1157 } 1158 return NoIndex; 1159 } 1160 1161 // This method searches for the offset of the first element in this 1162 // array that is equal to the given element. This method assumes 1163 // that 'operator==' is defined for elem_type. 1164 // @param aItem The item to search for. 1165 // @param aStart The index to start from. 1166 // @return The index of the found element or NoIndex if not found. 1167 template<class Item> 1168 index_type IndexOf(const Item& aItem, index_type aStart = 0) const 1169 { 1170 return IndexOf(aItem, aStart, nsDefaultComparator<elem_type, Item>()); 1171 } 1172 1173 // This method searches for the offset of the last element in this 1174 // array that is equal to the given element. 1175 // @param aItem The item to search for. 1176 // @param aStart The index to start from. If greater than or equal to the 1177 // length of the array, then the entire array is searched. 1178 // @param aComp The Comparator used to determine element equality. 1179 // @return The index of the found element or NoIndex if not found. 1180 template<class Item, class Comparator> 1181 index_type LastIndexOf(const Item& aItem, index_type aStart, 1182 const Comparator& aComp) const 1183 { 1184 size_type endOffset = aStart >= Length() ? Length() : aStart + 1; 1185 const elem_type* iend = Elements() - 1; 1186 const elem_type* iter = iend + endOffset; 1187 for (; iter != iend; --iter) { 1188 if (aComp.Equals(*iter, aItem)) { 1189 return index_type(iter - Elements()); 1190 } 1191 } 1192 return NoIndex; 1193 } 1194 1195 // This method searches for the offset of the last element in this 1196 // array that is equal to the given element. This method assumes 1197 // that 'operator==' is defined for elem_type. 1198 // @param aItem The item to search for. 1199 // @param aStart The index to start from. If greater than or equal to the 1200 // length of the array, then the entire array is searched. 1201 // @return The index of the found element or NoIndex if not found. 1202 template<class Item> 1203 index_type LastIndexOf(const Item& aItem, 1204 index_type aStart = NoIndex) const 1205 { 1206 return LastIndexOf(aItem, aStart, nsDefaultComparator<elem_type, Item>()); 1207 } 1208 1209 // This method searches for the offset for the element in this array 1210 // that is equal to the given element. The array is assumed to be sorted. 1211 // If there is more than one equivalent element, there is no guarantee 1212 // on which one will be returned. 1213 // @param aItem The item to search for. 1214 // @param aComp The Comparator used. 1215 // @return The index of the found element or NoIndex if not found. 1216 template<class Item, class Comparator> 1217 index_type BinaryIndexOf(const Item& aItem, const Comparator& aComp) const 1218 { 1219 using mozilla::BinarySearchIf; 1220 typedef ::detail::ItemComparatorEq<Item, Comparator> Cmp; 1221 1222 size_t index; 1223 bool found = BinarySearchIf(*this, 0, Length(), Cmp(aItem, aComp), &index); 1224 return found ? index : NoIndex; 1225 } 1226 1227 // This method searches for the offset for the element in this array 1228 // that is equal to the given element. The array is assumed to be sorted. 1229 // This method assumes that 'operator==' and 'operator<' are defined. 1230 // @param aItem The item to search for. 1231 // @return The index of the found element or NoIndex if not found. 1232 template<class Item> 1233 index_type BinaryIndexOf(const Item& aItem) const 1234 { 1235 return BinaryIndexOf(aItem, nsDefaultComparator<elem_type, Item>()); 1236 } 1237 1238 // 1239 // Mutation methods 1240 // 1241 1242 template<class Allocator, typename ActualAlloc = Alloc> 1243 typename ActualAlloc::ResultType Assign( 1244 const nsTArray_Impl<E, Allocator>& aOther) 1245 { 1246 return ActualAlloc::ConvertBoolToResultType( 1247 !!ReplaceElementsAt<E, ActualAlloc>(0, Length(), 1248 aOther.Elements(), aOther.Length())); 1249 } 1250 1251 template<class Allocator> 1252 MOZ_MUST_USE 1253 bool Assign(const nsTArray_Impl<E, Allocator>& aOther, 1254 const mozilla::fallible_t&) 1255 { 1256 return Assign<Allocator, FallibleAlloc>(aOther); 1257 } 1258 1259 template<class Allocator> 1260 void Assign(nsTArray_Impl<E, Allocator>&& aOther) 1261 { 1262 Clear(); 1263 SwapElements(aOther); 1264 } 1265 1266 // This method call the destructor on each element of the array, empties it, 1267 // but does not shrink the array's capacity. 1268 // See also SetLengthAndRetainStorage. 1269 // Make sure to call Compact() if needed to avoid keeping a huge array 1270 // around. 1271 void ClearAndRetainStorage() 1272 { 1273 if (base_type::mHdr == EmptyHdr()) { 1274 return; 1275 } 1276 1277 DestructRange(0, Length()); 1278 base_type::mHdr->mLength = 0; 1279 } 1280 1281 // This method modifies the length of the array, but unlike SetLength 1282 // it doesn't deallocate/reallocate the current internal storage. 1283 // The new length MUST be shorter than or equal to the current capacity. 1284 // If the new length is larger than the existing length of the array, 1285 // then new elements will be constructed using elem_type's default 1286 // constructor. If shorter, elements will be destructed and removed. 1287 // See also ClearAndRetainStorage. 1288 // @param aNewLen The desired length of this array. 1289 void SetLengthAndRetainStorage(size_type aNewLen) 1290 { 1291 MOZ_ASSERT(aNewLen <= base_type::Capacity()); 1292 size_type oldLen = Length(); 1293 if (aNewLen > oldLen) { 1294 InsertElementsAt(oldLen, aNewLen - oldLen); 1295 return; 1296 } 1297 if (aNewLen < oldLen) { 1298 DestructRange(aNewLen, oldLen - aNewLen); 1299 base_type::mHdr->mLength = aNewLen; 1300 } 1301 } 1302 1303 // This method replaces a range of elements in this array. 1304 // @param aStart The starting index of the elements to replace. 1305 // @param aCount The number of elements to replace. This may be zero to 1306 // insert elements without removing any existing elements. 1307 // @param aArray The values to copy into this array. Must be non-null, 1308 // and these elements must not already exist in the array 1309 // being modified. 1310 // @param aArrayLen The number of values to copy into this array. 1311 // @return A pointer to the new elements in the array, or null if 1312 // the operation failed due to insufficient memory. 1313 protected: 1314 template<class Item, typename ActualAlloc = Alloc> 1315 elem_type* ReplaceElementsAt(index_type aStart, size_type aCount, 1316 const Item* aArray, size_type aArrayLen); 1317 1318 public: 1319 1320 template<class Item> 1321 MOZ_MUST_USE 1322 elem_type* ReplaceElementsAt(index_type aStart, size_type aCount, 1323 const Item* aArray, size_type aArrayLen, 1324 const mozilla::fallible_t&) 1325 { 1326 return ReplaceElementsAt<Item, FallibleAlloc>(aStart, aCount, 1327 aArray, aArrayLen); 1328 } 1329 1330 // A variation on the ReplaceElementsAt method defined above. 1331 protected: 1332 template<class Item, typename ActualAlloc = Alloc> 1333 elem_type* ReplaceElementsAt(index_type aStart, size_type aCount, 1334 const nsTArray<Item>& aArray) 1335 { 1336 return ReplaceElementsAt<Item, ActualAlloc>( 1337 aStart, aCount, aArray.Elements(), aArray.Length()); 1338 } 1339 public: 1340 1341 template<class Item> 1342 MOZ_MUST_USE 1343 elem_type* ReplaceElementsAt(index_type aStart, size_type aCount, 1344 const nsTArray<Item>& aArray, 1345 const mozilla::fallible_t&) 1346 { 1347 return ReplaceElementsAt<Item, FallibleAlloc>(aStart, aCount, aArray); 1348 } 1349 1350 // A variation on the ReplaceElementsAt method defined above. 1351 protected: 1352 template<class Item, typename ActualAlloc = Alloc> 1353 elem_type* ReplaceElementsAt(index_type aStart, size_type aCount, 1354 const Item& aItem) 1355 { 1356 return ReplaceElementsAt<Item, ActualAlloc>(aStart, aCount, &aItem, 1); 1357 } 1358 public: 1359 1360 template<class Item> 1361 MOZ_MUST_USE 1362 elem_type* ReplaceElementsAt(index_type aStart, size_type aCount, 1363 const Item& aItem, const mozilla::fallible_t&) 1364 { 1365 return ReplaceElementsAt<Item, FallibleAlloc>(aStart, aCount, aItem); 1366 } 1367 1368 // A variation on the ReplaceElementsAt method defined above. 1369 template<class Item> 1370 elem_type* ReplaceElementAt(index_type aIndex, const Item& aItem) 1371 { 1372 return ReplaceElementsAt(aIndex, 1, &aItem, 1); 1373 } 1374 1375 // A variation on the ReplaceElementsAt method defined above. 1376 protected: 1377 template<class Item, typename ActualAlloc = Alloc> 1378 elem_type* InsertElementsAt(index_type aIndex, const Item* aArray, 1379 size_type aArrayLen) 1380 { 1381 return ReplaceElementsAt<Item, ActualAlloc>(aIndex, 0, aArray, aArrayLen); 1382 } 1383 public: 1384 1385 template<class Item> 1386 MOZ_MUST_USE 1387 elem_type* InsertElementsAt(index_type aIndex, const Item* aArray, 1388 size_type aArrayLen, const mozilla::fallible_t&) 1389 { 1390 return InsertElementsAt<Item, FallibleAlloc>(aIndex, aArray, aArrayLen); 1391 } 1392 1393 // A variation on the ReplaceElementsAt method defined above. 1394 protected: 1395 template<class Item, class Allocator, typename ActualAlloc = Alloc> 1396 elem_type* InsertElementsAt(index_type aIndex, 1397 const nsTArray_Impl<Item, Allocator>& aArray) 1398 { 1399 return ReplaceElementsAt<Item, ActualAlloc>( 1400 aIndex, 0, aArray.Elements(), aArray.Length()); 1401 } 1402 public: 1403 1404 template<class Item, class Allocator> 1405 MOZ_MUST_USE 1406 elem_type* InsertElementsAt(index_type aIndex, 1407 const nsTArray_Impl<Item, Allocator>& aArray, 1408 const mozilla::fallible_t&) 1409 { 1410 return InsertElementsAt<Item, Allocator, FallibleAlloc>(aIndex, aArray); 1411 } 1412 1413 // Insert a new element without copy-constructing. This is useful to avoid 1414 // temporaries. 1415 // @return A pointer to the newly inserted element, or null on OOM. 1416 protected: 1417 template<typename ActualAlloc = Alloc> 1418 elem_type* InsertElementAt(index_type aIndex); 1419 1420 public: 1421 1422 MOZ_MUST_USE 1423 elem_type* InsertElementAt(index_type aIndex, const mozilla::fallible_t&) 1424 { 1425 return InsertElementAt<FallibleAlloc>(aIndex); 1426 } 1427 1428 // Insert a new element, move constructing if possible. 1429 protected: 1430 template<class Item, typename ActualAlloc = Alloc> 1431 elem_type* InsertElementAt(index_type aIndex, Item&& aItem); 1432 1433 public: 1434 1435 template<class Item> 1436 MOZ_MUST_USE 1437 elem_type* InsertElementAt(index_type aIndex, Item&& aItem, 1438 const mozilla::fallible_t&) 1439 { 1440 return InsertElementAt<Item, FallibleAlloc>(aIndex, 1441 mozilla::Forward<Item>(aItem)); 1442 } 1443 1444 // This method searches for the smallest index of an element that is strictly 1445 // greater than |aItem|. If |aItem| is inserted at this index, the array will 1446 // remain sorted and |aItem| would come after all elements that are equal to 1447 // it. If |aItem| is greater than or equal to all elements in the array, the 1448 // array length is returned. 1449 // 1450 // Note that consumers who want to know whether there are existing items equal 1451 // to |aItem| in the array can just check that the return value here is > 0 1452 // and indexing into the previous slot gives something equal to |aItem|. 1453 // 1454 // 1455 // @param aItem The item to search for. 1456 // @param aComp The Comparator used. 1457 // @return The index of greatest element <= to |aItem| 1458 // @precondition The array is sorted 1459 template<class Item, class Comparator> 1460 index_type IndexOfFirstElementGt(const Item& aItem, 1461 const Comparator& aComp) const 1462 { 1463 using mozilla::BinarySearchIf; 1464 typedef ::detail::ItemComparatorFirstElementGT<Item, Comparator> Cmp; 1465 1466 size_t index; 1467 BinarySearchIf(*this, 0, Length(), Cmp(aItem, aComp), &index); 1468 return index; 1469 } 1470 1471 // A variation on the IndexOfFirstElementGt method defined above. 1472 template<class Item> 1473 index_type 1474 IndexOfFirstElementGt(const Item& aItem) const 1475 { 1476 return IndexOfFirstElementGt(aItem, nsDefaultComparator<elem_type, Item>()); 1477 } 1478 1479 // Inserts |aItem| at such an index to guarantee that if the array 1480 // was previously sorted, it will remain sorted after this 1481 // insertion. 1482 protected: 1483 template<class Item, class Comparator, typename ActualAlloc = Alloc> 1484 elem_type* InsertElementSorted(Item&& aItem, const Comparator& aComp) 1485 { 1486 index_type index = IndexOfFirstElementGt<Item, Comparator>(aItem, aComp); 1487 return InsertElementAt<Item, ActualAlloc>( 1488 index, mozilla::Forward<Item>(aItem)); 1489 } 1490 public: 1491 1492 template<class Item, class Comparator> 1493 MOZ_MUST_USE 1494 elem_type* InsertElementSorted(Item&& aItem, const Comparator& aComp, 1495 const mozilla::fallible_t&) 1496 { 1497 return InsertElementSorted<Item, Comparator, FallibleAlloc>( 1498 mozilla::Forward<Item>(aItem), aComp); 1499 } 1500 1501 // A variation on the InsertElementSorted method defined above. 1502 protected: 1503 template<class Item, typename ActualAlloc = Alloc> 1504 elem_type* InsertElementSorted(Item&& aItem) 1505 { 1506 nsDefaultComparator<elem_type, Item> comp; 1507 return InsertElementSorted<Item, decltype(comp), ActualAlloc>( 1508 mozilla::Forward<Item>(aItem), comp); 1509 } 1510 public: 1511 1512 template<class Item> 1513 MOZ_MUST_USE 1514 elem_type* InsertElementSorted(Item&& aItem, const mozilla::fallible_t&) 1515 { 1516 return InsertElementSorted<Item, FallibleAlloc>( 1517 mozilla::Forward<Item>(aItem)); 1518 } 1519 1520 // This method appends elements to the end of this array. 1521 // @param aArray The elements to append to this array. 1522 // @param aArrayLen The number of elements to append to this array. 1523 // @return A pointer to the new elements in the array, or null if 1524 // the operation failed due to insufficient memory. 1525 protected: 1526 template<class Item, typename ActualAlloc = Alloc> 1527 elem_type* AppendElements(const Item* aArray, size_type aArrayLen); 1528 1529 public: 1530 1531 template<class Item> 1532 /* MOZ_MUST_USE */ 1533 elem_type* AppendElements(const Item* aArray, size_type aArrayLen, 1534 const mozilla::fallible_t&) 1535 { 1536 return AppendElements<Item, FallibleAlloc>(aArray, aArrayLen); 1537 } 1538 1539 // A variation on the AppendElements method defined above. 1540 protected: 1541 template<class Item, class Allocator, typename ActualAlloc = Alloc> 1542 elem_type* AppendElements(const nsTArray_Impl<Item, Allocator>& aArray) 1543 { 1544 return AppendElements<Item, ActualAlloc>(aArray.Elements(), aArray.Length()); 1545 } 1546 public: 1547 1548 template<class Item, class Allocator> 1549 /* MOZ_MUST_USE */ 1550 elem_type* AppendElements(const nsTArray_Impl<Item, Allocator>& aArray, 1551 const mozilla::fallible_t&) 1552 { 1553 return AppendElements<Item, Allocator, FallibleAlloc>(aArray); 1554 } 1555 1556 // Move all elements from another array to the end of this array. 1557 // @return A pointer to the newly appended elements, or null on OOM. 1558 protected: 1559 template<class Item, class Allocator, typename ActualAlloc = Alloc> 1560 elem_type* AppendElements(nsTArray_Impl<Item, Allocator>&& aArray); 1561 1562 public: 1563 1564 template<class Item, class Allocator, typename ActualAlloc = Alloc> 1565 /* MOZ_MUST_USE */ 1566 elem_type* AppendElements(nsTArray_Impl<Item, Allocator>&& aArray, 1567 const mozilla::fallible_t&) 1568 { 1569 return AppendElements<Item, Allocator>(mozilla::Move(aArray)); 1570 } 1571 1572 // Append a new element, move constructing if possible. 1573 protected: 1574 template<class Item, typename ActualAlloc = Alloc> 1575 elem_type* AppendElement(Item&& aItem); 1576 1577 public: 1578 1579 template<class Item> 1580 /* MOZ_MUST_USE */ 1581 elem_type* AppendElement(Item&& aItem, 1582 const mozilla::fallible_t&) 1583 { 1584 return AppendElement<Item, FallibleAlloc>(mozilla::Forward<Item>(aItem)); 1585 } 1586 1587 // Append new elements without copy-constructing. This is useful to avoid 1588 // temporaries. 1589 // @return A pointer to the newly appended elements, or null on OOM. 1590 protected: 1591 template<typename ActualAlloc = Alloc> 1592 elem_type* AppendElements(size_type aCount) { 1593 if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>( 1594 Length() + aCount, sizeof(elem_type)))) { 1595 return nullptr; 1596 } 1597 elem_type* elems = Elements() + Length(); 1598 size_type i; 1599 for (i = 0; i < aCount; ++i) { 1600 elem_traits::Construct(elems + i); 1601 } 1602 this->IncrementLength(aCount); 1603 return elems; 1604 } 1605 public: 1606 1607 /* MOZ_MUST_USE */ 1608 elem_type* AppendElements(size_type aCount, 1609 const mozilla::fallible_t&) 1610 { 1611 return AppendElements<FallibleAlloc>(aCount); 1612 } 1613 1614 // Append a new element without copy-constructing. This is useful to avoid 1615 // temporaries. 1616 // @return A pointer to the newly appended element, or null on OOM. 1617 protected: 1618 template<typename ActualAlloc = Alloc> 1619 elem_type* AppendElement() 1620 { 1621 return AppendElements<ActualAlloc>(1); 1622 } 1623 public: 1624 1625 /* MOZ_MUST_USE */ 1626 elem_type* AppendElement(const mozilla::fallible_t&) 1627 { 1628 return AppendElement<FallibleAlloc>(); 1629 } 1630 1631 // This method removes a range of elements from this array. 1632 // @param aStart The starting index of the elements to remove. 1633 // @param aCount The number of elements to remove. 1634 void RemoveElementsAt(index_type aStart, size_type aCount); 1635 1636 // A variation on the RemoveElementsAt method defined above. 1637 void RemoveElementAt(index_type aIndex) { RemoveElementsAt(aIndex, 1); } 1638 1639 // A variation on the RemoveElementsAt method defined above. 1640 void Clear() { RemoveElementsAt(0, Length()); } 1641 1642 // This method removes elements based on the return value of the 1643 // callback function aPredicate. If the function returns true for 1644 // an element, the element is removed. aPredicate will be called 1645 // for each element in order. It is not safe to access the array 1646 // inside aPredicate. 1647 template<typename Predicate> 1648 void RemoveElementsBy(Predicate aPredicate); 1649 1650 // This helper function combines IndexOf with RemoveElementAt to "search 1651 // and destroy" the first element that is equal to the given element. 1652 // @param aItem The item to search for. 1653 // @param aComp The Comparator used to determine element equality. 1654 // @return true if the element was found 1655 template<class Item, class Comparator> 1656 bool RemoveElement(const Item& aItem, const Comparator& aComp) 1657 { 1658 index_type i = IndexOf(aItem, 0, aComp); 1659 if (i == NoIndex) { 1660 return false; 1661 } 1662 1663 RemoveElementAt(i); 1664 return true; 1665 } 1666 1667 // A variation on the RemoveElement method defined above that assumes 1668 // that 'operator==' is defined for elem_type. 1669 template<class Item> 1670 bool RemoveElement(const Item& aItem) 1671 { 1672 return RemoveElement(aItem, nsDefaultComparator<elem_type, Item>()); 1673 } 1674 1675 // This helper function combines IndexOfFirstElementGt with 1676 // RemoveElementAt to "search and destroy" the last element that 1677 // is equal to the given element. 1678 // @param aItem The item to search for. 1679 // @param aComp The Comparator used to determine element equality. 1680 // @return true if the element was found 1681 template<class Item, class Comparator> 1682 bool RemoveElementSorted(const Item& aItem, const Comparator& aComp) 1683 { 1684 index_type index = IndexOfFirstElementGt(aItem, aComp); 1685 if (index > 0 && aComp.Equals(ElementAt(index - 1), aItem)) { 1686 RemoveElementAt(index - 1); 1687 return true; 1688 } 1689 return false; 1690 } 1691 1692 // A variation on the RemoveElementSorted method defined above. 1693 template<class Item> 1694 bool RemoveElementSorted(const Item& aItem) 1695 { 1696 return RemoveElementSorted(aItem, nsDefaultComparator<elem_type, Item>()); 1697 } 1698 1699 // This method causes the elements contained in this array and the given 1700 // array to be swapped. 1701 template<class Allocator> 1702 typename Alloc::ResultType SwapElements(nsTArray_Impl<E, Allocator>& aOther) 1703 { 1704 return Alloc::Result(this->template SwapArrayElements<Alloc>( 1705 aOther, sizeof(elem_type), MOZ_ALIGNOF(elem_type))); 1706 } 1707 1708 // 1709 // Allocation 1710 // 1711 1712 // This method may increase the capacity of this array object by the 1713 // specified amount. This method may be called in advance of several 1714 // AppendElement operations to minimize heap re-allocations. This method 1715 // will not reduce the number of elements in this array. 1716 // @param aCapacity The desired capacity of this array. 1717 // @return True if the operation succeeded; false if we ran out of memory 1718 protected: 1719 template<typename ActualAlloc = Alloc> 1720 typename ActualAlloc::ResultType SetCapacity(size_type aCapacity) 1721 { 1722 return ActualAlloc::Result(this->template EnsureCapacity<ActualAlloc>( 1723 aCapacity, sizeof(elem_type))); 1724 } 1725 public: 1726 1727 MOZ_MUST_USE 1728 bool SetCapacity(size_type aCapacity, const mozilla::fallible_t&) 1729 { 1730 return SetCapacity<FallibleAlloc>(aCapacity); 1731 } 1732 1733 // This method modifies the length of the array. If the new length is 1734 // larger than the existing length of the array, then new elements will be 1735 // constructed using elem_type's default constructor. Otherwise, this call 1736 // removes elements from the array (see also RemoveElementsAt). 1737 // @param aNewLen The desired length of this array. 1738 // @return True if the operation succeeded; false otherwise. 1739 // See also TruncateLength if the new length is guaranteed to be smaller than 1740 // the old. 1741 protected: 1742 template<typename ActualAlloc = Alloc> 1743 typename ActualAlloc::ResultType SetLength(size_type aNewLen) 1744 { 1745 size_type oldLen = Length(); 1746 if (aNewLen > oldLen) { 1747 return ActualAlloc::ConvertBoolToResultType( 1748 InsertElementsAt<ActualAlloc>(oldLen, aNewLen - oldLen) != nullptr); 1749 } 1750 1751 TruncateLength(aNewLen); 1752 return ActualAlloc::ConvertBoolToResultType(true); 1753 } 1754 public: 1755 1756 MOZ_MUST_USE 1757 bool SetLength(size_type aNewLen, const mozilla::fallible_t&) 1758 { 1759 return SetLength<FallibleAlloc>(aNewLen); 1760 } 1761 1762 // This method modifies the length of the array, but may only be 1763 // called when the new length is shorter than the old. It can 1764 // therefore be called when elem_type has no default constructor, 1765 // unlike SetLength. It removes elements from the array (see also 1766 // RemoveElementsAt). 1767 // @param aNewLen The desired length of this array. 1768 void TruncateLength(size_type aNewLen) 1769 { 1770 size_type oldLen = Length(); 1771 MOZ_ASSERT(aNewLen <= oldLen, 1772 "caller should use SetLength instead"); 1773 RemoveElementsAt(aNewLen, oldLen - aNewLen); 1774 } 1775 1776 // This method ensures that the array has length at least the given 1777 // length. If the current length is shorter than the given length, 1778 // then new elements will be constructed using elem_type's default 1779 // constructor. 1780 // @param aMinLen The desired minimum length of this array. 1781 // @return True if the operation succeeded; false otherwise. 1782 protected: 1783 template<typename ActualAlloc = Alloc> 1784 typename ActualAlloc::ResultType EnsureLengthAtLeast(size_type aMinLen) 1785 { 1786 size_type oldLen = Length(); 1787 if (aMinLen > oldLen) { 1788 return ActualAlloc::ConvertBoolToResultType( 1789 !!InsertElementsAt<ActualAlloc>(oldLen, aMinLen - oldLen)); 1790 } 1791 return ActualAlloc::ConvertBoolToResultType(true); 1792 } 1793 public: 1794 1795 MOZ_MUST_USE 1796 bool EnsureLengthAtLeast(size_type aMinLen, const mozilla::fallible_t&) 1797 { 1798 return EnsureLengthAtLeast<FallibleAlloc>(aMinLen); 1799 } 1800 1801 // This method inserts elements into the array, constructing 1802 // them using elem_type's default constructor. 1803 // @param aIndex the place to insert the new elements. This must be no 1804 // greater than the current length of the array. 1805 // @param aCount the number of elements to insert 1806 protected: 1807 template<typename ActualAlloc = Alloc> 1808 elem_type* InsertElementsAt(index_type aIndex, size_type aCount) 1809 { 1810 if (!base_type::template InsertSlotsAt<ActualAlloc>(aIndex, aCount, 1811 sizeof(elem_type), 1812 MOZ_ALIGNOF(elem_type))) { 1813 return nullptr; 1814 } 1815 1816 // Initialize the extra array elements 1817 elem_type* iter = Elements() + aIndex; 1818 elem_type* iend = iter + aCount; 1819 for (; iter != iend; ++iter) { 1820 elem_traits::Construct(iter); 1821 } 1822 1823 return Elements() + aIndex; 1824 } 1825 public: 1826 1827 MOZ_MUST_USE 1828 elem_type* InsertElementsAt(index_type aIndex, size_type aCount, 1829 const mozilla::fallible_t&) 1830 { 1831 return InsertElementsAt<FallibleAlloc>(aIndex, aCount); 1832 } 1833 1834 // This method inserts elements into the array, constructing them 1835 // elem_type's copy constructor (or whatever one-arg constructor 1836 // happens to match the Item type). 1837 // @param aIndex the place to insert the new elements. This must be no 1838 // greater than the current length of the array. 1839 // @param aCount the number of elements to insert. 1840 // @param aItem the value to use when constructing the new elements. 1841 protected: 1842 template<class Item, typename ActualAlloc = Alloc> 1843 elem_type* InsertElementsAt(index_type aIndex, size_type aCount, 1844 const Item& aItem); 1845 1846 public: 1847 1848 template<class Item> 1849 MOZ_MUST_USE 1850 elem_type* InsertElementsAt(index_type aIndex, size_type aCount, 1851 const Item& aItem, const mozilla::fallible_t&) 1852 { 1853 return InsertElementsAt<Item, FallibleAlloc>(aIndex, aCount, aItem); 1854 } 1855 1856 // This method may be called to minimize the memory used by this array. 1857 void Compact() 1858 { 1859 ShrinkCapacity(sizeof(elem_type), MOZ_ALIGNOF(elem_type)); 1860 } 1861 1862 // 1863 // Sorting 1864 // 1865 1866 // This function is meant to be used with the NS_QuickSort function. It 1867 // maps the callback API expected by NS_QuickSort to the Comparator API 1868 // used by nsTArray_Impl. See nsTArray_Impl::Sort. 1869 template<class Comparator> 1870 static int Compare(const void* aE1, const void* aE2, void* aData) 1871 { 1872 const Comparator* c = reinterpret_cast<const Comparator*>(aData); 1873 const elem_type* a = static_cast<const elem_type*>(aE1); 1874 const elem_type* b = static_cast<const elem_type*>(aE2); 1875 return c->LessThan(*a, *b) ? -1 : (c->Equals(*a, *b) ? 0 : 1); 1876 } 1877 1878 // This method sorts the elements of the array. It uses the LessThan 1879 // method defined on the given Comparator object to collate elements. 1880 // @param aComp The Comparator used to collate elements. 1881 template<class Comparator> 1882 void Sort(const Comparator& aComp) 1883 { 1884 NS_QuickSort(Elements(), Length(), sizeof(elem_type), 1885 Compare<Comparator>, const_cast<Comparator*>(&aComp)); 1886 } 1887 1888 // A variation on the Sort method defined above that assumes that 1889 // 'operator<' is defined for elem_type. 1890 void Sort() { Sort(nsDefaultComparator<elem_type, elem_type>()); } 1891 1892 protected: 1893 using base_type::Hdr; 1894 using base_type::ShrinkCapacity; 1895 1896 // This method invokes elem_type's destructor on a range of elements. 1897 // @param aStart The index of the first element to destroy. 1898 // @param aCount The number of elements to destroy. 1899 void DestructRange(index_type aStart, size_type aCount) 1900 { 1901 elem_type* iter = Elements() + aStart; 1902 elem_type *iend = iter + aCount; 1903 for (; iter != iend; ++iter) { 1904 elem_traits::Destruct(iter); 1905 } 1906 } 1907 1908 // This method invokes elem_type's copy-constructor on a range of elements. 1909 // @param aStart The index of the first element to construct. 1910 // @param aCount The number of elements to construct. 1911 // @param aValues The array of elements to copy. 1912 template<class Item> 1913 void AssignRange(index_type aStart, size_type aCount, const Item* aValues) 1914 { 1915 AssignRangeAlgorithm<mozilla::IsPod<Item>::value, 1916 mozilla::IsSame<Item, elem_type>::value> 1917 ::implementation(Elements(), aStart, aCount, aValues); 1918 } 1919 }; 1920 1921 template<typename E, class Alloc> 1922 template<class Item, typename ActualAlloc> 1923 auto 1924 nsTArray_Impl<E, Alloc>::ReplaceElementsAt(index_type aStart, size_type aCount, 1925 const Item* aArray, size_type aArrayLen) -> elem_type* 1926 { 1927 // Adjust memory allocation up-front to catch errors. 1928 if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>( 1929 Length() + aArrayLen - aCount, sizeof(elem_type)))) { 1930 return nullptr; 1931 } 1932 DestructRange(aStart, aCount); 1933 this->template ShiftData<ActualAlloc>(aStart, aCount, aArrayLen, 1934 sizeof(elem_type), 1935 MOZ_ALIGNOF(elem_type)); 1936 AssignRange(aStart, aArrayLen, aArray); 1937 return Elements() + aStart; 1938 } 1939 1940 template<typename E, class Alloc> 1941 void 1942 nsTArray_Impl<E, Alloc>::RemoveElementsAt(index_type aStart, size_type aCount) 1943 { 1944 MOZ_ASSERT(aCount == 0 || aStart < Length(), "Invalid aStart index"); 1945 MOZ_ASSERT(aStart + aCount <= Length(), "Invalid length"); 1946 // Check that the previous assert didn't overflow 1947 MOZ_ASSERT(aStart <= aStart + aCount, "Start index plus length overflows"); 1948 DestructRange(aStart, aCount); 1949 this->template ShiftData<InfallibleAlloc>(aStart, aCount, 0, 1950 sizeof(elem_type), 1951 MOZ_ALIGNOF(elem_type)); 1952 } 1953 1954 template<typename E, class Alloc> 1955 template<typename Predicate> 1956 void 1957 nsTArray_Impl<E, Alloc>::RemoveElementsBy(Predicate aPredicate) 1958 { 1959 if (base_type::mHdr == EmptyHdr()) { 1960 return; 1961 } 1962 1963 index_type j = 0; 1964 index_type len = Length(); 1965 for (index_type i = 0; i < len; ++i) { 1966 if (aPredicate(Elements()[i])) { 1967 elem_traits::Destruct(Elements() + i); 1968 } else { 1969 if (j < i) { 1970 copy_type::MoveNonOverlappingRegion(Elements() + j, Elements() + i, 1971 1, sizeof(elem_type)); 1972 } 1973 ++j; 1974 } 1975 } 1976 base_type::mHdr->mLength = j; 1977 } 1978 1979 template<typename E, class Alloc> 1980 template<class Item, typename ActualAlloc> 1981 auto 1982 nsTArray_Impl<E, Alloc>::InsertElementsAt(index_type aIndex, size_type aCount, 1983 const Item& aItem) -> elem_type* 1984 { 1985 if (!base_type::template InsertSlotsAt<ActualAlloc>(aIndex, aCount, 1986 sizeof(elem_type), 1987 MOZ_ALIGNOF(elem_type))) { 1988 return nullptr; 1989 } 1990 1991 // Initialize the extra array elements 1992 elem_type* iter = Elements() + aIndex; 1993 elem_type* iend = iter + aCount; 1994 for (; iter != iend; ++iter) { 1995 elem_traits::Construct(iter, aItem); 1996 } 1997 1998 return Elements() + aIndex; 1999 } 2000 2001 template<typename E, class Alloc> 2002 template<typename ActualAlloc> 2003 auto 2004 nsTArray_Impl<E, Alloc>::InsertElementAt(index_type aIndex) -> elem_type* 2005 { 2006 if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>( 2007 Length() + 1, sizeof(elem_type)))) { 2008 return nullptr; 2009 } 2010 this->template ShiftData<ActualAlloc>(aIndex, 0, 1, sizeof(elem_type), 2011 MOZ_ALIGNOF(elem_type)); 2012 elem_type* elem = Elements() + aIndex; 2013 elem_traits::Construct(elem); 2014 return elem; 2015 } 2016 2017 template<typename E, class Alloc> 2018 template<class Item, typename ActualAlloc> 2019 auto 2020 nsTArray_Impl<E, Alloc>::InsertElementAt(index_type aIndex, Item&& aItem) -> elem_type* 2021 { 2022 if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>( 2023 Length() + 1, sizeof(elem_type)))) { 2024 return nullptr; 2025 } 2026 this->template ShiftData<ActualAlloc>(aIndex, 0, 1, sizeof(elem_type), 2027 MOZ_ALIGNOF(elem_type)); 2028 elem_type* elem = Elements() + aIndex; 2029 elem_traits::Construct(elem, mozilla::Forward<Item>(aItem)); 2030 return elem; 2031 } 2032 2033 template<typename E, class Alloc> 2034 template<class Item, typename ActualAlloc> 2035 auto 2036 nsTArray_Impl<E, Alloc>::AppendElements(const Item* aArray, size_type aArrayLen) -> elem_type* 2037 { 2038 if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>( 2039 Length() + aArrayLen, sizeof(elem_type)))) { 2040 return nullptr; 2041 } 2042 index_type len = Length(); 2043 AssignRange(len, aArrayLen, aArray); 2044 this->IncrementLength(aArrayLen); 2045 return Elements() + len; 2046 } 2047 2048 template<typename E, class Alloc> 2049 template<class Item, class Allocator, typename ActualAlloc> 2050 auto 2051 nsTArray_Impl<E, Alloc>::AppendElements(nsTArray_Impl<Item, Allocator>&& aArray) -> elem_type* 2052 { 2053 MOZ_ASSERT(&aArray != this, "argument must be different aArray"); 2054 if (Length() == 0) { 2055 SwapElements<ActualAlloc>(aArray); 2056 return Elements(); 2057 } 2058 2059 index_type len = Length(); 2060 index_type otherLen = aArray.Length(); 2061 if (!Alloc::Successful(this->template EnsureCapacity<Alloc>( 2062 len + otherLen, sizeof(elem_type)))) { 2063 return nullptr; 2064 } 2065 copy_type::MoveNonOverlappingRegion(Elements() + len, aArray.Elements(), otherLen, 2066 sizeof(elem_type)); 2067 this->IncrementLength(otherLen); 2068 aArray.template ShiftData<Alloc>(0, otherLen, 0, sizeof(elem_type), 2069 MOZ_ALIGNOF(elem_type)); 2070 return Elements() + len; 2071 } 2072 2073 template<typename E, class Alloc> 2074 template<class Item, typename ActualAlloc> 2075 auto 2076 nsTArray_Impl<E, Alloc>::AppendElement(Item&& aItem) -> elem_type* 2077 { 2078 if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>( 2079 Length() + 1, sizeof(elem_type)))) { 2080 return nullptr; 2081 } 2082 elem_type* elem = Elements() + Length(); 2083 elem_traits::Construct(elem, mozilla::Forward<Item>(aItem)); 2084 this->IncrementLength(1); 2085 return elem; 2086 } 2087 2088 template<typename E, typename Alloc> 2089 inline void 2090 ImplCycleCollectionUnlink(nsTArray_Impl<E, Alloc>& aField) 2091 { 2092 aField.Clear(); 2093 } 2094 2095 template<typename E, typename Alloc> 2096 inline void 2097 ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback, 2098 nsTArray_Impl<E, Alloc>& aField, 2099 const char* aName, 2100 uint32_t aFlags = 0) 2101 { 2102 aFlags |= CycleCollectionEdgeNameArrayFlag; 2103 size_t length = aField.Length(); 2104 for (size_t i = 0; i < length; ++i) { 2105 ImplCycleCollectionTraverse(aCallback, aField[i], aName, aFlags); 2106 } 2107 } 2108 2109 // 2110 // nsTArray is an infallible vector class. See the comment at the top of this 2111 // file for more details. 2112 // 2113 template<class E> 2114 class nsTArray : public nsTArray_Impl<E, nsTArrayInfallibleAllocator> 2115 { 2116 public: 2117 typedef nsTArray_Impl<E, nsTArrayInfallibleAllocator> base_type; 2118 typedef nsTArray<E> self_type; 2119 typedef typename base_type::size_type size_type; 2120 2121 nsTArray() {} 2122 explicit nsTArray(size_type aCapacity) : base_type(aCapacity) {} 2123 explicit nsTArray(const nsTArray& aOther) : base_type(aOther) {} 2124 MOZ_IMPLICIT nsTArray(nsTArray&& aOther) : base_type(mozilla::Move(aOther)) {} 2125 MOZ_IMPLICIT nsTArray(std::initializer_list<E> aIL) : base_type(aIL) {} 2126 2127 template<class Allocator> 2128 explicit nsTArray(const nsTArray_Impl<E, Allocator>& aOther) 2129 : base_type(aOther) 2130 { 2131 } 2132 template<class Allocator> 2133 MOZ_IMPLICIT nsTArray(nsTArray_Impl<E, Allocator>&& aOther) 2134 : base_type(mozilla::Move(aOther)) 2135 { 2136 } 2137 2138 self_type& operator=(const self_type& aOther) 2139 { 2140 base_type::operator=(aOther); 2141 return *this; 2142 } 2143 template<class Allocator> 2144 self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther) 2145 { 2146 base_type::operator=(aOther); 2147 return *this; 2148 } 2149 self_type& operator=(self_type&& aOther) 2150 { 2151 base_type::operator=(mozilla::Move(aOther)); 2152 return *this; 2153 } 2154 template<class Allocator> 2155 self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther) 2156 { 2157 base_type::operator=(mozilla::Move(aOther)); 2158 return *this; 2159 } 2160 2161 using base_type::AppendElement; 2162 using base_type::AppendElements; 2163 using base_type::EnsureLengthAtLeast; 2164 using base_type::InsertElementAt; 2165 using base_type::InsertElementsAt; 2166 using base_type::InsertElementSorted; 2167 using base_type::ReplaceElementsAt; 2168 using base_type::SetCapacity; 2169 using base_type::SetLength; 2170 }; 2171 2172 // 2173 // FallibleTArray is a fallible vector class. 2174 // 2175 template<class E> 2176 class FallibleTArray : public nsTArray_Impl<E, nsTArrayFallibleAllocator> 2177 { 2178 public: 2179 typedef nsTArray_Impl<E, nsTArrayFallibleAllocator> base_type; 2180 typedef FallibleTArray<E> self_type; 2181 typedef typename base_type::size_type size_type; 2182 2183 FallibleTArray() {} 2184 explicit FallibleTArray(size_type aCapacity) : base_type(aCapacity) {} 2185 explicit FallibleTArray(const FallibleTArray<E>& aOther) : base_type(aOther) {} 2186 FallibleTArray(FallibleTArray<E>&& aOther) 2187 : base_type(mozilla::Move(aOther)) 2188 { 2189 } 2190 2191 template<class Allocator> 2192 explicit FallibleTArray(const nsTArray_Impl<E, Allocator>& aOther) 2193 : base_type(aOther) 2194 { 2195 } 2196 template<class Allocator> 2197 explicit FallibleTArray(nsTArray_Impl<E, Allocator>&& aOther) 2198 : base_type(mozilla::Move(aOther)) 2199 { 2200 } 2201 2202 self_type& operator=(const self_type& aOther) 2203 { 2204 base_type::operator=(aOther); 2205 return *this; 2206 } 2207 template<class Allocator> 2208 self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther) 2209 { 2210 base_type::operator=(aOther); 2211 return *this; 2212 } 2213 self_type& operator=(self_type&& aOther) 2214 { 2215 base_type::operator=(mozilla::Move(aOther)); 2216 return *this; 2217 } 2218 template<class Allocator> 2219 self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther) 2220 { 2221 base_type::operator=(mozilla::Move(aOther)); 2222 return *this; 2223 } 2224 }; 2225 2226 // 2227 // AutoTArray<E, N> is like nsTArray<E>, but with N elements of inline storage. 2228 // Storing more than N elements is fine, but it will cause a heap allocation. 2229 // 2230 template<class E, size_t N> 2231 class MOZ_NON_MEMMOVABLE AutoTArray : public nsTArray<E> 2232 { 2233 static_assert(N != 0, "AutoTArray<E, 0> should be specialized"); 2234 public: 2235 typedef AutoTArray<E, N> self_type; 2236 typedef nsTArray<E> base_type; 2237 typedef typename base_type::Header Header; 2238 typedef typename base_type::elem_type elem_type; 2239 2240 AutoTArray() 2241 { 2242 Init(); 2243 } 2244 2245 AutoTArray(const self_type& aOther) 2246 { 2247 Init(); 2248 this->AppendElements(aOther); 2249 } 2250 2251 explicit AutoTArray(const base_type& aOther) 2252 { 2253 Init(); 2254 this->AppendElements(aOther); 2255 } 2256 2257 explicit AutoTArray(base_type&& aOther) 2258 { 2259 Init(); 2260 this->SwapElements(aOther); 2261 } 2262 2263 template<typename Allocator> 2264 explicit AutoTArray(nsTArray_Impl<elem_type, Allocator>&& aOther) 2265 { 2266 Init(); 2267 this->SwapElements(aOther); 2268 } 2269 2270 MOZ_IMPLICIT AutoTArray(std::initializer_list<E> aIL) 2271 { 2272 Init(); 2273 this->AppendElements(aIL.begin(), aIL.size()); 2274 } 2275 2276 self_type& operator=(const self_type& aOther) 2277 { 2278 base_type::operator=(aOther); 2279 return *this; 2280 } 2281 2282 template<typename Allocator> 2283 self_type& operator=(const nsTArray_Impl<elem_type, Allocator>& aOther) 2284 { 2285 base_type::operator=(aOther); 2286 return *this; 2287 } 2288 2289 private: 2290 // nsTArray_base casts itself as an nsAutoArrayBase in order to get a pointer 2291 // to mAutoBuf. 2292 template<class Allocator, class Copier> 2293 friend class nsTArray_base; 2294 2295 void Init() 2296 { 2297 static_assert(MOZ_ALIGNOF(elem_type) <= 8, 2298 "can't handle alignments greater than 8, " 2299 "see nsTArray_base::UsesAutoArrayBuffer()"); 2300 // Temporary work around for VS2012 RC compiler crash 2301 Header** phdr = base_type::PtrToHdr(); 2302 *phdr = reinterpret_cast<Header*>(&mAutoBuf); 2303 (*phdr)->mLength = 0; 2304 (*phdr)->mCapacity = N; 2305 (*phdr)->mIsAutoArray = 1; 2306 2307 MOZ_ASSERT(base_type::GetAutoArrayBuffer(MOZ_ALIGNOF(elem_type)) == 2308 reinterpret_cast<Header*>(&mAutoBuf), 2309 "GetAutoArrayBuffer needs to be fixed"); 2310 } 2311 2312 // Declare mAutoBuf aligned to the maximum of the header's alignment and 2313 // elem_type's alignment. We need to use a union rather than 2314 // MOZ_ALIGNED_DECL because GCC is picky about what goes into 2315 // __attribute__((aligned(foo))). 2316 union 2317 { 2318 char mAutoBuf[sizeof(nsTArrayHeader) + N * sizeof(elem_type)]; 2319 // Do the max operation inline to ensure that it is a compile-time constant. 2320 mozilla::AlignedElem<(MOZ_ALIGNOF(Header) > MOZ_ALIGNOF(elem_type)) ? 2321 MOZ_ALIGNOF(Header) : MOZ_ALIGNOF(elem_type)> mAlign; 2322 }; 2323 }; 2324 2325 // 2326 // Specialization of AutoTArray<E, N> for the case where N == 0. 2327 // AutoTArray<E, 0> behaves exactly like nsTArray<E>, but without this 2328 // specialization, it stores a useless inline header. 2329 // 2330 // We do have many AutoTArray<E, 0> objects in memory: about 2,000 per tab as 2331 // of May 2014. These are typically not explicitly AutoTArray<E, 0> but rather 2332 // AutoTArray<E, N> for some value N depending on template parameters, in 2333 // generic code. 2334 // 2335 // For that reason, we optimize this case with the below partial specialization, 2336 // which ensures that AutoTArray<E, 0> is just like nsTArray<E>, without any 2337 // inline header overhead. 2338 // 2339 template<class E> 2340 class AutoTArray<E, 0> : public nsTArray<E> 2341 { 2342 }; 2343 2344 template<class E, size_t N> 2345 struct nsTArray_CopyChooser<AutoTArray<E, N>> 2346 { 2347 typedef nsTArray_CopyWithConstructors<AutoTArray<E, N>> Type; 2348 }; 2349 2350 // Assert that AutoTArray doesn't have any extra padding inside. 2351 // 2352 // It's important that the data stored in this auto array takes up a multiple of 2353 // 8 bytes; e.g. AutoTArray<uint32_t, 1> wouldn't work. Since AutoTArray 2354 // contains a pointer, its size must be a multiple of alignof(void*). (This is 2355 // because any type may be placed into an array, and there's no padding between 2356 // elements of an array.) The compiler pads the end of the structure to 2357 // enforce this rule. 2358 // 2359 // If we used AutoTArray<uint32_t, 1> below, this assertion would fail on a 2360 // 64-bit system, where the compiler inserts 4 bytes of padding at the end of 2361 // the auto array to make its size a multiple of alignof(void*) == 8 bytes. 2362 2363 static_assert(sizeof(AutoTArray<uint32_t, 2>) == 2364 sizeof(void*) + sizeof(nsTArrayHeader) + sizeof(uint32_t) * 2, 2365 "AutoTArray shouldn't contain any extra padding, " 2366 "see the comment"); 2367 2368 // Definitions of nsTArray_Impl methods 2369 #include "nsTArray-inl.h" 2370 2371 #endif // nsTArray_h__ 2372