1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim:set ts=2 sw=2 sts=2 et cindent: */
3 /* ***** BEGIN LICENSE BLOCK *****
4 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6 * The contents of this file are subject to the Mozilla Public License Version
7 * 1.1 (the "License"); you may not use this file except in compliance with
8 * the License. You may obtain a copy of the License at
9 * http://www.mozilla.org/MPL/
11 * Software distributed under the License is distributed on an "AS IS" basis,
12 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13 * for the specific language governing rights and limitations under the
16 * The Original Code is C++ array template.
18 * The Initial Developer of the Original Code is Google Inc.
19 * Portions created by the Initial Developer are Copyright (C) 2005
20 * the Initial Developer. All Rights Reserved.
23 * Darin Fisher <darin@meer.net>
25 * Alternatively, the contents of this file may be used under the terms of
26 * either the GNU General Public License Version 2 or later (the "GPL"), or
27 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
28 * in which case the provisions of the GPL or the LGPL are applicable instead
29 * of those above. If you wish to allow use of your version of this file only
30 * under the terms of either the GPL or the LGPL, and not to allow others to
31 * use your version of this file under the terms of the MPL, indicate your
32 * decision by deleting the provisions above and replace them with the notice
33 * and other provisions required by the GPL or the LGPL. If you do not delete
34 * the provisions above, a recipient may use your version of this file under
35 * the terms of any one of the MPL, the GPL or the LGPL.
37 * ***** END LICENSE BLOCK ***** */
43 #include "nsQuickSort.h"
45 #include "nsTraceRefcnt.h"
49 // This class serves as a base class for nsTArray. It shouldn't be used
50 // directly. It holds common implementation code that does not depend on the
51 // element type of the nsTArray.
53 class NS_COM_GLUE nsTArray_base
{
55 typedef PRUint32 size_type
;
56 typedef PRUint32 index_type
;
58 // A special value that is used to indicate an invalid or unknown index
61 NoIndex
= index_type(-1)
64 // @return The number of elements in the array.
65 size_type
Length() const {
69 // @return True if the array is empty or false otherwise.
70 PRBool
IsEmpty() const {
74 // @return The number of elements that can fit in the array without forcing
75 // the array to be re-allocated. The length of an array is always less
76 // than or equal to its capacity.
77 size_type
Capacity() const {
78 return mHdr
->mCapacity
;
82 void* DebugGetHeader() const {
91 // Resize the storage if necessary to achieve the requested capacity.
92 // @param capacity The requested number of array elements.
93 // @param elementSize The size of an array element.
94 // @return False if insufficient memory is available; true otherwise.
95 PRBool
EnsureCapacity(size_type capacity
, size_type elementSize
);
97 // Resize the storage to the minimum required amount.
98 // @param elementSize The size of an array element.
99 void ShrinkCapacity(size_type elementSize
);
101 // This method may be called to resize a "gap" in the array by shifting
102 // elements around. It updates mLength appropriately. If the resulting
103 // array has zero elements, then the array's memory is free'd.
104 // @param start The starting index of the gap.
105 // @param oldLen The current length of the gap.
106 // @param newLen The desired length of the gap.
107 // @param elementSize The size of an array element.
108 void ShiftData(index_type start
, size_type oldLen
, size_type newLen
,
109 size_type elementSize
);
111 // This method increments the length member of the array's header.
112 // Note that mHdr may actually be sEmptyHdr in the case where a
113 // zero-length array is inserted into our array. But then n should
115 void IncrementLength(PRUint32 n
) {
116 NS_ASSERTION(mHdr
!= &sEmptyHdr
|| n
== 0, "bad data pointer");
120 // This method inserts blank slots into the array.
121 // @param index the place to insert the new elements. This must be no
122 // greater than the current length of the array.
123 // @param count the number of slots to insert
124 // @param elementSize the size of an array element.
125 PRBool
InsertSlotsAt(index_type index
, size_type count
,
126 size_type elementSize
);
130 // NOTE: This method isn't heavily optimized if either array is an
132 PRBool
SwapArrayElements(nsTArray_base
& other
, size_type elementSize
);
134 // Helper function for SwapArrayElements. Ensures that if the array
135 // is an nsAutoTArray that it doesn't use the built-in buffer.
136 PRBool
EnsureNotUsingAutoArrayBuffer(size_type elemSize
);
138 // We prefix mData with a structure of this type. This is done to minimize
139 // the size of the nsTArray object when it is empty.
142 PRUint32 mCapacity
: 31;
143 PRUint32 mIsAutoArray
: 1;
146 // Returns true if this nsTArray is an nsAutoTArray with a built-in buffer.
147 PRBool
IsAutoArray() {
148 return mHdr
->mIsAutoArray
;
151 // Dummy struct to get the compiler to simulate the alignment of
152 // nsAutoTArray's and nsAutoTPtrArray's mAutoBuf.
158 // Returns a Header for the built-in buffer of this nsAutoTArray.
159 Header
* GetAutoArrayBuffer() {
160 NS_ASSERTION(IsAutoArray(), "Should be an auto array to call this");
162 return reinterpret_cast<Header
*>(&(reinterpret_cast<AutoArray
*>(&mHdr
))->aligned
);
165 // Returns true if this is an nsAutoTArray and it currently uses the
166 // built-in buffer to store its elements.
167 PRBool
UsesAutoArrayBuffer() {
168 return mHdr
->mIsAutoArray
&& mHdr
== GetAutoArrayBuffer();
171 // This is not const since we may actually write to it. However we will
172 // always write to it the same data that it already contains. See
174 static Header sEmptyHdr
;
176 // The array's elements (prefixed with a Header). This pointer is never
177 // null. If the array is empty, then this will point to sEmptyHdr.
182 // This class defines convenience functions for element specific operations.
183 // Specialize this template if necessary.
186 class nsTArrayElementTraits
{
188 // Invoke the default constructor in place.
189 static inline void Construct(E
*e
) {
190 // Do NOT call "E()"! That triggers C++ "default initialization"
191 // which zeroes out POD ("plain old data") types such as regular ints.
192 // We don't want that because it can be a performance issue and people
193 // don't expect it; nsTArray should work like a regular C/C++ array in
195 new (static_cast<void *>(e
)) E
;
197 // Invoke the copy-constructor in place.
199 static inline void Construct(E
*e
, const A
&arg
) {
200 new (static_cast<void *>(e
)) E(arg
);
202 // Invoke the destructor in place.
203 static inline void Destruct(E
*e
) {
208 // This class exists because VC6 cannot handle static template functions.
209 // Otherwise, the Compare method would be defined directly on nsTArray.
210 template <class E
, class Comparator
>
211 class nsQuickSortComparator
{
214 // This function is meant to be used with the NS_QuickSort function. It
215 // maps the callback API expected by NS_QuickSort to the Comparator API
216 // used by nsTArray. See nsTArray::Sort.
217 static int Compare(const void* e1
, const void* e2
, void *data
) {
218 const Comparator
* c
= reinterpret_cast<const Comparator
*>(data
);
219 const elem_type
* a
= static_cast<const elem_type
*>(e1
);
220 const elem_type
* b
= static_cast<const elem_type
*>(e2
);
221 return c
->LessThan(*a
, *b
) ? -1 : (c
->Equals(*a
, *b
) ? 0 : 1);
225 // The default comparator used by nsTArray
226 template<class A
, class B
>
227 class nsDefaultComparator
{
229 PRBool
Equals(const A
& a
, const B
& b
) const {
232 PRBool
LessThan(const A
& a
, const B
& b
) const {
238 // The templatized array class that dynamically resizes its storage as elements
239 // are added. This class is designed to behave a bit like std::vector.
241 // The template parameter specifies the type of the elements (elem_type), and
242 // has the following requirements:
244 // elem_type MUST define a copy-constructor.
245 // elem_type MAY define operator< for sorting.
246 // elem_type MAY define operator== for searching.
248 // For methods taking a Comparator instance, the Comparator must be a class
249 // defining the following methods:
251 // class Comparator {
253 // /** @return True if the elements are equals; false otherwise. */
254 // PRBool Equals(const elem_type& a, const elem_type& b) const;
256 // /** @return True if (a < b); false otherwise. */
257 // PRBool LessThan(const elem_type& a, const elem_type& b) const;
260 // The Equals method is used for searching, and the LessThan method is used
264 class nsTArray
: public nsTArray_base
{
267 typedef nsTArray
<E
> self_type
;
268 typedef nsTArrayElementTraits
<E
> elem_traits
;
271 // Finalization method
274 ~nsTArray() { Clear(); }
277 // Initialization methods
282 // Initialize this array and pre-allocate some number of elements.
283 explicit nsTArray(size_type capacity
) {
284 SetCapacity(capacity
);
287 // The array's copy-constructor performs a 'deep' copy of the given array.
288 // @param other The array object to copy.
289 nsTArray(const self_type
& other
) {
290 AppendElements(other
);
293 // The array's assignment operator performs a 'deep' copy of the given
294 // array. It is optimized to reuse existing storage if possible.
295 // @param other The array object to copy.
296 nsTArray
& operator=(const self_type
& other
) {
297 ReplaceElementsAt(0, Length(), other
.Elements(), other
.Length());
305 // This method provides direct access to the array elements.
306 // @return A pointer to the first element of the array. If the array is
307 // empty, then this pointer must not be dereferenced.
308 elem_type
* Elements() {
309 return reinterpret_cast<elem_type
*>(mHdr
+ 1);
312 // This method provides direct, readonly access to the array elements.
313 // @return A pointer to the first element of the array. If the array is
314 // empty, then this pointer must not be dereferenced.
315 const elem_type
* Elements() const {
316 return reinterpret_cast<const elem_type
*>(mHdr
+ 1);
319 // This method provides direct access to the i'th element of the array.
320 // The given index must be within the array bounds.
321 // @param i The index of an element in the array.
322 // @return A reference to the i'th element of the array.
323 elem_type
& ElementAt(index_type i
) {
324 NS_ASSERTION(i
< Length(), "invalid array index");
325 return Elements()[i
];
328 // This method provides direct, readonly access to the i'th element of the
329 // array. The given index must be within the array bounds.
330 // @param i The index of an element in the array.
331 // @return A const reference to the i'th element of the array.
332 const elem_type
& ElementAt(index_type i
) const {
333 NS_ASSERTION(i
< Length(), "invalid array index");
334 return Elements()[i
];
337 // This method provides direct access to the i'th element of the array in
338 // a bounds safe manner. If the requested index is out of bounds the
339 // provided default value is returned.
340 // @param i The index of an element in the array.
341 // @param def The value to return if the index is out of bounds.
342 elem_type
& SafeElementAt(index_type i
, elem_type
& def
) {
343 return i
< Length() ? Elements()[i
] : def
;
346 // This method provides direct access to the i'th element of the array in
347 // a bounds safe manner. If the requested index is out of bounds the
348 // provided default value is returned.
349 // @param i The index of an element in the array.
350 // @param def The value to return if the index is out of bounds.
351 const elem_type
& SafeElementAt(index_type i
, const elem_type
& def
) const {
352 return i
< Length() ? Elements()[i
] : def
;
355 // Shorthand for ElementAt(i)
356 elem_type
& operator[](index_type i
) {
360 // Shorthand for ElementAt(i)
361 const elem_type
& operator[](index_type i
) const {
369 // This method searches for the first element in this array that is equal
370 // to the given element.
371 // @param item The item to search for.
372 // @param comp The Comparator used to determine element equality.
373 // @return PR_TRUE if the element was found.
374 template<class Item
, class Comparator
>
375 PRBool
Contains(const Item
& item
, const Comparator
& comp
) const {
376 return IndexOf(item
, 0, comp
) != NoIndex
;
379 // This method searches for the first element in this array that is equal
380 // to the given element. This method assumes that 'operator==' is defined
382 // @param item The item to search for.
383 // @return PR_TRUE if the element was found.
385 PRBool
Contains(const Item
& item
) const {
386 return IndexOf(item
) != NoIndex
;
389 // This method searches for the offset of the first element in this
390 // array that is equal to the given element.
391 // @param item The item to search for.
392 // @param start The index to start from.
393 // @param comp The Comparator used to determine element equality.
394 // @return The index of the found element or NoIndex if not found.
395 template<class Item
, class Comparator
>
396 index_type
IndexOf(const Item
& item
, index_type start
,
397 const Comparator
& comp
) const {
398 const elem_type
* iter
= Elements() + start
, *end
= Elements() + Length();
399 for (; iter
!= end
; ++iter
) {
400 if (comp
.Equals(*iter
, item
))
401 return iter
- Elements();
406 // This method searches for the offset of the first element in this
407 // array that is equal to the given element. This method assumes
408 // that 'operator==' is defined for elem_type.
409 // @param item The item to search for.
410 // @param start The index to start from.
411 // @return The index of the found element or NoIndex if not found.
413 index_type
IndexOf(const Item
& item
, index_type start
= 0) const {
414 return IndexOf(item
, start
, nsDefaultComparator
<elem_type
, Item
>());
417 // This method searches for the offset of the last element in this
418 // array that is equal to the given element.
419 // @param item The item to search for.
420 // @param start The index to start from. If greater than or equal to the
421 // length of the array, then the entire array is searched.
422 // @param comp The Comparator used to determine element equality.
423 // @return The index of the found element or NoIndex if not found.
424 template<class Item
, class Comparator
>
425 index_type
LastIndexOf(const Item
& item
, index_type start
,
426 const Comparator
& comp
) const {
427 if (start
>= Length())
428 start
= Length() - 1;
429 const elem_type
* end
= Elements() - 1, *iter
= end
+ start
+ 1;
430 for (; iter
!= end
; --iter
) {
431 if (comp
.Equals(*iter
, item
))
432 return iter
- Elements();
437 // This method searches for the offset of the last element in this
438 // array that is equal to the given element. This method assumes
439 // that 'operator==' is defined for elem_type.
440 // @param item The item to search for.
441 // @param start The index to start from. If greater than or equal to the
442 // length of the array, then the entire array is searched.
443 // @return The index of the found element or NoIndex if not found.
445 index_type
LastIndexOf(const Item
& item
,
446 index_type start
= NoIndex
) const {
447 return LastIndexOf(item
, start
, nsDefaultComparator
<elem_type
, Item
>());
450 // This method searches for the offset for the element in this array
451 // that is equal to the given element. The array is assumed to be sorted.
452 // @param item The item to search for.
453 // @param comp The Comparator used.
454 // @return The index of the found element or NoIndex if not found.
455 template<class Item
, class Comparator
>
456 index_type
BinaryIndexOf(const Item
& item
, const Comparator
& comp
) const {
457 index_type low
= 0, high
= Length();
459 index_type mid
= (high
+ low
) >> 1;
460 if (comp
.Equals(ElementAt(mid
), item
))
462 if (comp
.LessThan(ElementAt(mid
), item
))
470 // This method searches for the offset for the element in this array
471 // that is equal to the given element. The array is assumed to be sorted.
472 // This method assumes that 'operator==' and 'operator<' are defined.
473 // @param item The item to search for.
474 // @return The index of the found element or NoIndex if not found.
476 index_type
BinaryIndexOf(const Item
& item
) const {
477 return BinaryIndexOf(item
, nsDefaultComparator
<elem_type
, Item
>());
484 // This method replaces a range of elements in this array.
485 // @param start The starting index of the elements to replace.
486 // @param count The number of elements to replace. This may be zero to
487 // insert elements without removing any existing elements.
488 // @param array The values to copy into this array. Must be non-null,
489 // and these elements must not already exist in the array
491 // @param arrayLen The number of values to copy into this array.
492 // @return A pointer to the new elements in the array, or null if
493 // the operation failed due to insufficient memory.
495 elem_type
*ReplaceElementsAt(index_type start
, size_type count
,
496 const Item
* array
, size_type arrayLen
) {
497 // Adjust memory allocation up-front to catch errors.
498 if (!EnsureCapacity(Length() + arrayLen
- count
, sizeof(elem_type
)))
500 DestructRange(start
, count
);
501 ShiftData(start
, count
, arrayLen
, sizeof(elem_type
));
502 AssignRange(start
, arrayLen
, array
);
503 return Elements() + start
;
506 // A variation on the ReplaceElementsAt method defined above.
508 elem_type
*ReplaceElementsAt(index_type start
, size_type count
,
509 const nsTArray
<Item
>& array
) {
510 return ReplaceElementsAt(start
, count
, array
.Elements(), array
.Length());
513 // A variation on the ReplaceElementsAt method defined above.
515 elem_type
*ReplaceElementsAt(index_type start
, size_type count
,
517 return ReplaceElementsAt(start
, count
, &item
, 1);
520 // A variation on the ReplaceElementsAt method defined above.
522 elem_type
*InsertElementsAt(index_type index
, const Item
* array
,
523 size_type arrayLen
) {
524 return ReplaceElementsAt(index
, 0, array
, arrayLen
);
527 // A variation on the ReplaceElementsAt method defined above.
529 elem_type
*InsertElementsAt(index_type index
, const nsTArray
<Item
>& array
) {
530 return ReplaceElementsAt(index
, 0, array
.Elements(), array
.Length());
533 // A variation on the ReplaceElementsAt method defined above.
535 elem_type
*InsertElementAt(index_type index
, const Item
& item
) {
536 return ReplaceElementsAt(index
, 0, &item
, 1);
539 // Insert a new element without copy-constructing. This is useful to avoid
541 // @return A pointer to the newly inserted element, or null on OOM.
542 elem_type
* InsertElementAt(index_type index
) {
543 if (!EnsureCapacity(Length() + 1, sizeof(elem_type
)))
545 ShiftData(index
, 0, 1, sizeof(elem_type
));
546 elem_type
*elem
= Elements() + index
;
547 elem_traits::Construct(elem
);
551 // This method searches for the least index of the greatest
552 // element less than or equal to |item|. If |item| is inserted at
553 // this index, the array will remain sorted. True is returned iff
554 // this index is also equal to |item|. In this case, the returned
555 // index may point to the start of multiple copies of |item|.
556 // @param item The item to search for.
557 // @param comp The Comparator used.
558 // @outparam idx The index of greatest element <= to |item|
559 // @return True iff |item == array[*idx]|.
560 // @precondition The array is sorted
561 template<class Item
, class Comparator
>
563 GreatestIndexLtEq(const Item
& item
,
564 const Comparator
& comp
,
565 index_type
* idx NS_OUTPARAM
) const {
566 // Nb: we could replace all the uses of "BinaryIndexOf" with this
567 // function, but BinaryIndexOf will be oh-so-slightly faster so
568 // it's not strictly desired to do.
570 // invariant: low <= [idx] < high
571 index_type low
= 0, high
= Length();
573 index_type mid
= (high
+ low
) >> 1;
574 if (comp
.Equals(ElementAt(mid
), item
)) {
575 // we might have the array [..., 2, 4, 4, 4, 4, 4, 5, ...]
576 // and be searching for "4". it's arbitrary where mid ends
577 // up here, so we back it up to the first instance to maintain
578 // the "least index ..." we promised above.
581 } while (NoIndex
!= mid
&& comp
.Equals(ElementAt(mid
), item
));
585 if (comp
.LessThan(ElementAt(mid
), item
))
586 // invariant: low <= idx < high
589 // invariant: low <= idx < high
592 // low <= idx < high, so insert at high ("shifting" high up by
593 // 1) to maintain invariant.
594 // (or insert at low, since low==high; just a matter of taste here.)
599 // A variation on the GreatestIndexLtEq method defined above.
600 template<class Item
, class Comparator
>
602 GreatestIndexLtEq(const Item
& item
,
604 const Comparator
& comp
) const {
605 return GreatestIndexLtEq(item
, comp
, &idx
);
608 // A variation on the GreatestIndexLtEq method defined above.
611 GreatestIndexLtEq(const Item
& item
,
612 index_type
& idx
) const {
613 return GreatestIndexLtEq(item
, nsDefaultComparator
<elem_type
, Item
>(), &idx
);
616 // Inserts |item| at such an index to guarantee that if the array
617 // was previously sorted, it will remain sorted after this
619 template<class Item
, class Comparator
>
620 elem_type
*InsertElementSorted(const Item
& item
, const Comparator
& comp
) {
622 GreatestIndexLtEq(item
, comp
, &index
);
623 return InsertElementAt(index
, item
);
626 // A variation on the InsertElementSorted metod defined above.
628 elem_type
*InsertElementSorted(const Item
& item
) {
629 return InsertElementSorted(item
, nsDefaultComparator
<elem_type
, Item
>());
632 // This method appends elements to the end of this array.
633 // @param array The elements to append to this array.
634 // @param arrayLen The number of elements to append to this array.
635 // @return A pointer to the new elements in the array, or null if
636 // the operation failed due to insufficient memory.
638 elem_type
*AppendElements(const Item
* array
, size_type arrayLen
) {
639 if (!EnsureCapacity(Length() + arrayLen
, sizeof(elem_type
)))
641 index_type len
= Length();
642 AssignRange(len
, arrayLen
, array
);
643 IncrementLength(arrayLen
);
644 return Elements() + len
;
647 // A variation on the AppendElements method defined above.
649 elem_type
*AppendElements(const nsTArray
<Item
>& array
) {
650 return AppendElements(array
.Elements(), array
.Length());
653 // A variation on the AppendElements method defined above.
655 elem_type
*AppendElement(const Item
& item
) {
656 return AppendElements(&item
, 1);
659 // Append new elements without copy-constructing. This is useful to avoid
661 // @return A pointer to the newly appended elements, or null on OOM.
662 elem_type
*AppendElements(size_type count
) {
663 if (!EnsureCapacity(Length() + count
, sizeof(elem_type
)))
665 elem_type
*elems
= Elements() + Length();
667 for (i
= 0; i
< count
; ++i
) {
668 elem_traits::Construct(elems
+ i
);
670 IncrementLength(count
);
674 // Append a new element without copy-constructing. This is useful to avoid
676 // @return A pointer to the newly appended element, or null on OOM.
677 elem_type
*AppendElement() {
678 return AppendElements(1);
681 // Move all elements from another array to the end of this array without
682 // calling copy constructors or destructors.
683 // @return A pointer to the newly appended elements, or null on OOM.
685 elem_type
*MoveElementsFrom(nsTArray
<Item
>& array
) {
686 NS_PRECONDITION(&array
!= this, "argument must be different array");
687 index_type len
= Length();
688 index_type otherLen
= array
.Length();
689 if (!EnsureCapacity(len
+ otherLen
, sizeof(elem_type
)))
691 memcpy(Elements() + len
, array
.Elements(), otherLen
* sizeof(elem_type
));
692 IncrementLength(otherLen
);
693 array
.ShiftData(0, otherLen
, 0, sizeof(elem_type
));
694 return Elements() + len
;
697 // This method removes a range of elements from this array.
698 // @param start The starting index of the elements to remove.
699 // @param count The number of elements to remove.
700 void RemoveElementsAt(index_type start
, size_type count
) {
701 NS_ASSERTION(count
== 0 || start
< Length(), "Invalid start index");
702 NS_ASSERTION(start
+ count
<= Length(), "Invalid length");
703 DestructRange(start
, count
);
704 ShiftData(start
, count
, 0, sizeof(elem_type
));
707 // A variation on the RemoveElementsAt method defined above.
708 void RemoveElementAt(index_type index
) {
709 RemoveElementsAt(index
, 1);
712 // A variation on the RemoveElementsAt method defined above.
714 RemoveElementsAt(0, Length());
717 // This helper function combines IndexOf with RemoveElementAt to "search
718 // and destroy" the first element that is equal to the given element.
719 // @param item The item to search for.
720 // @param comp The Comparator used to determine element equality.
721 // @return PR_TRUE if the element was found
722 template<class Item
, class Comparator
>
723 PRBool
RemoveElement(const Item
& item
, const Comparator
& comp
) {
724 index_type i
= IndexOf(item
, 0, comp
);
732 // A variation on the RemoveElement method defined above that assumes
733 // that 'operator==' is defined for elem_type.
735 PRBool
RemoveElement(const Item
& item
) {
736 return RemoveElement(item
, nsDefaultComparator
<elem_type
, Item
>());
739 // This helper function combines GreatestIndexLtEq with
740 // RemoveElementAt to "search and destroy" the first element that
741 // is equal to the given element.
742 // @param item The item to search for.
743 // @param comp The Comparator used to determine element equality.
744 // @return PR_TRUE if the element was found
745 template<class Item
, class Comparator
>
746 PRBool
RemoveElementSorted(const Item
& item
, const Comparator
& comp
) {
748 PRBool found
= GreatestIndexLtEq(item
, comp
, &index
);
750 RemoveElementAt(index
);
754 // A variation on the RemoveElementSorted method defined above.
756 PRBool
RemoveElementSorted(const Item
& item
) {
757 return RemoveElementSorted(item
, nsDefaultComparator
<elem_type
, Item
>());
760 // This method causes the elements contained in this array and the given
761 // array to be swapped.
762 // NOTE: This method isn't heavily optimized if either array is an
764 PRBool
SwapElements(self_type
& other
) {
765 return SwapArrayElements(other
, sizeof(elem_type
));
772 // This method may increase the capacity of this array object by the
773 // specified amount. This method may be called in advance of several
774 // AppendElement operations to minimize heap re-allocations. This method
775 // will not reduce the number of elements in this array.
776 // @param capacity The desired capacity of this array.
777 // @return True if the operation succeeded; false if we ran out of memory
778 PRBool
SetCapacity(size_type capacity
) {
779 return EnsureCapacity(capacity
, sizeof(elem_type
));
782 // This method modifies the length of the array. If the new length is
783 // larger than the existing length of the array, then new elements will be
784 // constructed using elem_type's default constructor. Otherwise, this call
785 // removes elements from the array (see also RemoveElementsAt).
786 // @param newLen The desired length of this array.
787 // @return True if the operation succeeded; false otherwise.
788 // See also TruncateLength if the new length is guaranteed to be
789 // smaller than the old.
790 PRBool
SetLength(size_type newLen
) {
791 size_type oldLen
= Length();
792 if (newLen
> oldLen
) {
793 return InsertElementsAt(oldLen
, newLen
- oldLen
) != nsnull
;
796 TruncateLength(newLen
);
800 // This method modifies the length of the array, but may only be
801 // called when the new length is shorter than the old. It can
802 // therefore be called when elem_type has no default constructor,
803 // unlike SetLength. It removes elements from the array (see also
804 // RemoveElementsAt).
805 // @param newLen The desired length of this array.
806 void TruncateLength(size_type newLen
) {
807 size_type oldLen
= Length();
808 NS_ABORT_IF_FALSE(newLen
<= oldLen
,
809 "caller should use SetLength instead");
810 RemoveElementsAt(newLen
, oldLen
- newLen
);
813 // This method ensures that the array has length at least the given
814 // length. If the current length is shorter than the given length,
815 // then new elements will be constructed using elem_type's default
817 // @param minLen The desired minimum length of this array.
818 // @return True if the operation succeeded; false otherwise.
819 PRBool
EnsureLengthAtLeast(size_type minLen
) {
820 size_type oldLen
= Length();
821 if (minLen
> oldLen
) {
822 return InsertElementsAt(oldLen
, minLen
- oldLen
) != nsnull
;
827 // This method inserts elements into the array, constructing
828 // them using elem_type's default constructor.
829 // @param index the place to insert the new elements. This must be no
830 // greater than the current length of the array.
831 // @param count the number of elements to insert
832 elem_type
*InsertElementsAt(index_type index
, size_type count
) {
833 if (!nsTArray_base::InsertSlotsAt(index
, count
, sizeof(elem_type
))) {
837 // Initialize the extra array elements
838 elem_type
*iter
= Elements() + index
, *end
= iter
+ count
;
839 for (; iter
!= end
; ++iter
) {
840 elem_traits::Construct(iter
);
843 return Elements() + index
;
846 // This method inserts elements into the array, constructing them
847 // elem_type's copy constructor (or whatever one-arg constructor
848 // happens to match the Item type).
849 // @param index the place to insert the new elements. This must be no
850 // greater than the current length of the array.
851 // @param count the number of elements to insert.
852 // @param item the value to use when constructing the new elements.
854 elem_type
*InsertElementsAt(index_type index
, size_type count
,
856 if (!nsTArray_base::InsertSlotsAt(index
, count
, sizeof(elem_type
))) {
860 // Initialize the extra array elements
861 elem_type
*iter
= Elements() + index
, *end
= iter
+ count
;
862 for (; iter
!= end
; ++iter
) {
863 elem_traits::Construct(iter
, item
);
866 return Elements() + index
;
869 // This method may be called to minimize the memory used by this array.
871 ShrinkCapacity(sizeof(elem_type
));
878 // This method sorts the elements of the array. It uses the LessThan
879 // method defined on the given Comparator object to collate elements.
880 // @param c The Comparator to used to collate elements.
881 template<class Comparator
>
882 void Sort(const Comparator
& comp
) {
883 NS_QuickSort(Elements(), Length(), sizeof(elem_type
),
884 nsQuickSortComparator
<elem_type
, Comparator
>::Compare
,
885 const_cast<Comparator
*>(&comp
));
888 // A variation on the Sort method defined above that assumes that
889 // 'operator<' is defined for elem_type.
891 Sort(nsDefaultComparator
<elem_type
, elem_type
>());
896 // This method invokes elem_type's destructor on a range of elements.
897 // @param start The index of the first element to destroy.
898 // @param count The number of elements to destroy.
899 void DestructRange(index_type start
, size_type count
) {
900 elem_type
*iter
= Elements() + start
, *end
= iter
+ count
;
901 for (; iter
!= end
; ++iter
) {
902 elem_traits::Destruct(iter
);
906 // This method invokes elem_type's copy-constructor on a range of elements.
907 // @param start The index of the first element to construct.
908 // @param count The number of elements to construct.
909 // @param values The array of elements to copy.
911 void AssignRange(index_type start
, size_type count
,
912 const Item
*values
) {
913 elem_type
*iter
= Elements() + start
, *end
= iter
+ count
;
914 for (; iter
!= end
; ++iter
, ++values
) {
915 elem_traits::Construct(iter
, *values
);
920 template<class E
, PRUint32 N
>
921 class nsAutoTArray
: public nsTArray
<E
> {
923 typedef nsTArray
<E
> base_type
;
924 typedef typename
base_type::Header Header
;
925 typedef typename
base_type::elem_type elem_type
;
928 base_type::mHdr
= reinterpret_cast<Header
*>(&mAutoBuf
);
929 base_type::mHdr
->mLength
= 0;
930 base_type::mHdr
->mCapacity
= N
;
931 base_type::mHdr
->mIsAutoArray
= 1;
933 NS_ASSERTION(base_type::GetAutoArrayBuffer() ==
934 reinterpret_cast<Header
*>(&mAutoBuf
),
935 "GetAutoArrayBuffer needs to be fixed");
940 char mAutoBuf
[sizeof(Header
) + N
* sizeof(elem_type
)];
945 // specialization for N = 0. this makes the inheritance model easier for
946 // templated users of nsAutoTArray.
948 class nsAutoTArray
<E
, 0> : public nsTArray
<E
> {
953 #endif // nsTArray_h__