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