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