Back to index

lightning-sunbird  0.9+nobinonly
nsTArray.h
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* vim:set ts=2 sw=2 sts=2 et cindent: */
00003 /* ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is C++ array template.
00017  *
00018  * The Initial Developer of the Original Code is Google Inc.
00019  * Portions created by the Initial Developer are Copyright (C) 2005
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *  Darin Fisher <darin@meer.net>
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 #ifndef nsTArray_h__
00040 #define nsTArray_h__
00041 
00042 #include "prtypes.h"
00043 #include "nsQuickSort.h"
00044 #include "nsDebug.h"
00045 #include NEW_H
00046 
00047 //
00048 // This class serves as a base class for nsTArray.  It shouldn't be used
00049 // directly.  It holds common implementation code that does not depend on the
00050 // element type of the nsTArray.
00051 //
00052 class NS_COM_GLUE nsTArray_base {
00053   public:
00054     typedef PRUint32 size_type;
00055     typedef PRUint32 index_type;
00056 
00057     // A special value that is used to indicate an invalid or unknown index
00058     // into the array.
00059     enum {
00060       NoIndex = index_type(-1)
00061     };
00062 
00063     // @return The number of elements in the array.
00064     size_type Length() const {
00065       return mHdr->mLength;
00066     }
00067 
00068     // @return True if the array is empty or false otherwise.
00069     PRBool IsEmpty() const {
00070       return Length() == 0;
00071     }
00072 
00073     // @return The number of elements that can fit in the array without forcing
00074     // the array to be re-allocated.  The length of an array is always less
00075     // than or equal to its capacity.
00076     size_type Capacity() const {
00077       return mHdr->mCapacity;
00078     }
00079 
00080   protected:
00081     nsTArray_base()
00082       : mHdr(NS_CONST_CAST(Header *, &sEmptyHdr)) {
00083     }
00084 
00085     // Resize the storage if necessary to achieve the requested capacity.
00086     // @param capacity     The requested number of array elements.
00087     // @param elementSize  The size of an array element.
00088     // @return False if insufficient memory is available; true otherwise.
00089     PRBool EnsureCapacity(size_type capacity, size_type elementSize);
00090 
00091     // Resize the storage to the minimum required amount.
00092     // @param elementSize  The size of an array element.
00093     void ShrinkCapacity(size_type elementSize);
00094     
00095     // This method may be called to resize a "gap" in the array by shifting
00096     // elements around.  It updates mLength appropriately.  If the resulting
00097     // array has zero elements, then the array's memory is free'd.
00098     // @param start        The starting index of the gap.
00099     // @param oldLen       The current length of the gap.
00100     // @param newLen       The desired length of the gap.
00101     // @param elementSize  The size of an array element.
00102     void ShiftData(index_type start, size_type oldLen, size_type newLen,
00103                    size_type elementSize);
00104 
00105     // This method increments the length member of the array's header.
00106     void IncrementLength(PRUint32 n) {
00107       NS_ASSERTION(mHdr != &sEmptyHdr, "bad data pointer");
00108       mHdr->mLength += n;
00109     }
00110 
00111   protected:
00112 
00113     // We prefix mData with a structure of this type.  This is done to minimize
00114     // the size of the nsTArray object when it is empty.
00115     struct Header {
00116       PRUint32 mLength;
00117       PRUint32 mCapacity;
00118     };
00119 
00120     static const Header sEmptyHdr;
00121 
00122     // The array's elements (prefixed with a Header).  This pointer is never
00123     // null.  If the array is empty, then this will point to sEmptyHdr.
00124     Header *mHdr;
00125 };
00126 
00127 //
00128 // This class defines convenience functions for element specific operations.
00129 // Specialize this template if necessary.
00130 //
00131 template<class E>
00132 class nsTArrayElementTraits {
00133   public:
00134     // Invoke the default constructor in place.
00135     static inline void Construct(E *e) {
00136       new (NS_STATIC_CAST(void *, e)) E();
00137     }
00138     // Invoke the copy-constructor in place.
00139     template<class A>
00140     static inline void Construct(E *e, const A &arg) {
00141       new (NS_STATIC_CAST(void *, e)) E(arg);
00142     }
00143     // Invoke the destructor in place.
00144     static inline void Destruct(E *e) {
00145       e->~E();
00146     }
00147 };
00148 
00149 // This class exists because VC6 cannot handle static template functions.
00150 // Otherwise, the Compare method would be defined directly on nsTArray.
00151 template <class E, class Comparator>
00152 class nsQuickSortComparator {
00153   public:
00154     typedef E elem_type;
00155     // This function is meant to be used with the NS_QuickSort function.  It
00156     // maps the callback API expected by NS_QuickSort to the Comparator API
00157     // used by nsTArray.  See nsTArray::Sort.
00158     static int Compare(const void* e1, const void* e2, void *data) {
00159       const Comparator* c = NS_REINTERPRET_CAST(const Comparator*, data);
00160       const elem_type* a = NS_STATIC_CAST(const elem_type*, e1);
00161       const elem_type* b = NS_STATIC_CAST(const elem_type*, e2);
00162       return c->LessThan(*a, *b) ? -1 : (c->Equals(*a, *b) ? 0 : 1);
00163     }
00164 };
00165 
00166 // The default comparator used by nsTArray
00167 template<class A, class B>
00168 class nsDefaultComparator {
00169   public:
00170     PRBool Equals(const A& a, const B& b) const {
00171       return a == b;
00172     }
00173     PRBool LessThan(const A& a, const B& b) const {
00174       return a < b;
00175     }
00176 };
00177 
00178 //
00179 // The templatized array class that dynamically resizes its storage as elements
00180 // are added.  This class is designed to behave a bit like std::vector.
00181 //
00182 // The template parameter specifies the type of the elements (elem_type), and
00183 // has the following requirements:
00184 //
00185 //   elem_type MUST define a copy-constructor.
00186 //   elem_type MAY define operator< for sorting.
00187 //   elem_type MAY define operator== for searching.
00188 //
00189 // For methods taking a Comparator instance, the Comparator must be a class
00190 // defining the following methods:
00191 //
00192 //   class Comparator {
00193 //     public:
00194 //       /** @return True if the elements are equals; false otherwise. */
00195 //       PRBool Equals(const elem_type& a, const elem_type& b) const;
00196 //
00197 //       /** @return True if (a < b); false otherwise. */
00198 //       PRBool LessThan(const elem_type& a, const elem_type& b) const;
00199 //   };
00200 //
00201 // The Equals method is used for searching, and the LessThan method is used
00202 // for sorting.
00203 //
00204 template<class E>
00205 class nsTArray : public nsTArray_base {
00206   public:
00207     typedef E                        elem_type;
00208     typedef nsTArray<E>              self_type;
00209     typedef nsTArrayElementTraits<E> elem_traits;
00210 
00211     //
00212     // Finalization method
00213     //
00214 
00215     ~nsTArray() { Clear(); }
00216 
00217     //
00218     // Initialization methods
00219     //
00220 
00221     nsTArray() {}
00222 
00223     // Initialize this array and pre-allocate some number of elements.
00224     explicit nsTArray(size_type capacity) {
00225       SetCapacity(capacity);
00226     }
00227     
00228     // The array's copy-constructor performs a 'deep' copy of the given array.
00229     // @param other  The array object to copy.
00230     nsTArray(const self_type& other) {
00231       AppendElements(other);
00232     }
00233 
00234     // The array's assignment operator performs a 'deep' copy of the given
00235     // array.  It is optimized to reuse existing storage if possible.
00236     // @param other  The array object to copy.
00237     nsTArray& operator=(const self_type& other) {
00238       ReplaceElementsAt(0, Length(), other.Elements(), other.Length());
00239       return *this;
00240     }
00241 
00242     //
00243     // Accessor methods
00244     //
00245 
00246     // This method provides direct access to the array elements.
00247     // @return A pointer to the first element of the array.  If the array is
00248     // empty, then this pointer must not be dereferenced.
00249     elem_type* Elements() {
00250       return NS_REINTERPRET_CAST(elem_type *, mHdr + 1);
00251     }
00252 
00253     // This method provides direct, readonly access to the array elements.
00254     // @return A pointer to the first element of the array.  If the array is
00255     // empty, then this pointer must not be dereferenced.
00256     const elem_type* Elements() const {
00257       return NS_REINTERPRET_CAST(const elem_type *, mHdr + 1);
00258     }
00259     
00260     // This method provides direct access to the i'th element of the array.
00261     // The given index must be within the array bounds.
00262     // @param i  The index of an element in the array.
00263     // @return   A reference to the i'th element of the array.
00264     elem_type& ElementAt(index_type i) {
00265       NS_ASSERTION(i < Length(), "invalid array index");
00266       return Elements()[i];
00267     }
00268 
00269     // This method provides direct, readonly access to the i'th element of the
00270     // array.  The given index must be within the array bounds.
00271     // @param i  The index of an element in the array.
00272     // @return   A const reference to the i'th element of the array.
00273     const elem_type& ElementAt(index_type i) const {
00274       NS_ASSERTION(i < Length(), "invalid array index");
00275       return Elements()[i];
00276     }
00277 
00278     // Shorthand for ElementAt(i)
00279     elem_type& operator[](index_type i) {
00280       return ElementAt(i);
00281     }
00282 
00283     // Shorthand for ElementAt(i)
00284     const elem_type& operator[](index_type i) const {
00285       return ElementAt(i);
00286     }
00287 
00288     //
00289     // Search methods
00290     //
00291 
00292     // This method searches for the offset of the first element in this
00293     // array that is equal to the given element.
00294     // @param item   The item to search for.
00295     // @param start  The index to start from.
00296     // @param comp   The Comparator used to determine element equality.
00297     // @return       The index of the found element or NoIndex if not found.
00298     template<class Item, class Comparator>
00299     index_type IndexOf(const Item& item, index_type start,
00300                        const Comparator& comp) const {
00301       const elem_type* iter = Elements() + start, *end = iter + Length();
00302       for (; iter != end; ++iter) {
00303         if (comp.Equals(*iter, item))
00304           return iter - Elements();
00305       }
00306       return NoIndex;
00307     }
00308 
00309     // This method searches for the offset of the first element in this
00310     // array that is equal to the given element.  This method assumes
00311     // that 'operator==' is defined for elem_type.
00312     // @param item   The item to search for.
00313     // @param start  The index to start from.
00314     // @return       The index of the found element or NoIndex if not found.
00315     template<class Item>
00316     index_type IndexOf(const Item& item, index_type start = 0) const {
00317       return IndexOf(item, start, nsDefaultComparator<elem_type, Item>());
00318     }
00319 
00320     // This method searches for the offset of the last element in this
00321     // array that is equal to the given element.
00322     // @param item   The item to search for.
00323     // @param start  The index to start from.  If greater than or equal to the
00324     //               length of the array, then the entire array is searched.
00325     // @param comp   The Comparator used to determine element equality.
00326     // @return       The index of the found element or NoIndex if not found.
00327     template<class Item, class Comparator>
00328     index_type LastIndexOf(const Item& item, index_type start,
00329                            const Comparator& comp) const {
00330       if (start >= Length())
00331         start = Length() - 1;
00332       const elem_type* end = Elements() - 1, *iter = end + start + 1;
00333       for (; iter != end; --iter) {
00334         if (comp.Equals(*iter, item))
00335           return iter - Elements();
00336       }
00337       return NoIndex;
00338     }
00339 
00340     // This method searches for the offset of the last element in this
00341     // array that is equal to the given element.  This method assumes
00342     // that 'operator==' is defined for elem_type.
00343     // @param item   The item to search for.
00344     // @param start  The index to start from.  If greater than or equal to the
00345     //               length of the array, then the entire array is searched.
00346     // @return       The index of the found element or NoIndex if not found.
00347     template<class Item>
00348     index_type LastIndexOf(const Item& item,
00349                            index_type start = NoIndex) const {
00350       return LastIndexOf(item, start, nsDefaultComparator<elem_type, Item>());
00351     }
00352 
00353     //
00354     // Mutation methods
00355     //
00356 
00357     // This method replaces a range of elements in this array.
00358     // @param start     The starting index of the elements to replace.
00359     // @param count     The number of elements to replace.  This may be zero to
00360     //                  insert elements without removing any existing elements.
00361     // @param array     The values to copy into this array.  Must be non-null,
00362     //                  and these elements must not already exist in the array
00363     //                  being modified.
00364     // @param arrayLen  The number of values to copy into this array.
00365     // @return          A pointer to the new elements in the array, or null if
00366     //                  the operation failed due to insufficient memory.
00367     template<class Item>
00368     elem_type *ReplaceElementsAt(index_type start, size_type count,
00369                                  const Item* array, size_type arrayLen) {
00370       // Adjust memory allocation up-front to catch errors.
00371       if (!EnsureCapacity(Length() + arrayLen - count, sizeof(elem_type)))
00372         return nsnull;
00373       DestructRange(start, count);
00374       ShiftData(start, count, arrayLen, sizeof(elem_type));
00375       AssignRange(start, arrayLen, array);
00376       return Elements() + start;
00377     }
00378 
00379     // A variation on the ReplaceElementsAt method defined above.
00380     template<class Item>
00381     elem_type *ReplaceElementsAt(index_type start, size_type count,
00382                                  const nsTArray<Item>& array) {
00383       return ReplaceElementsAt(start, count, array.Elements(), array.Length());
00384     }
00385 
00386     // A variation on the ReplaceElementsAt method defined above.
00387     template<class Item>
00388     elem_type *ReplaceElementsAt(index_type start, size_type count,
00389                                  const Item& item) {
00390       return ReplaceElementsAt(start, count, &item, 1);
00391     }
00392     
00393     // A variation on the ReplaceElementsAt method defined above.
00394     template<class Item>
00395     elem_type *InsertElementsAt(index_type index, const Item* array,
00396                                 size_type arrayLen) {
00397       return ReplaceElementsAt(index, 0, array, arrayLen);
00398     }
00399 
00400     // A variation on the ReplaceElementsAt method defined above.
00401     template<class Item>
00402     elem_type *InsertElementsAt(index_type index, const nsTArray<Item>& array) {
00403       return ReplaceElementsAt(index, 0, array.Elements(), array.Length());
00404     }
00405 
00406     // A variation on the ReplaceElementsAt method defined above.
00407     template<class Item>
00408     elem_type *InsertElementAt(index_type index, const Item& item) {
00409       return ReplaceElementsAt(index, 0, &item, 1);
00410     }
00411 
00412     // Insert a new element without copy-constructing. This is useful to avoid
00413     // temporaries.
00414     // @return A pointer to the newly inserted element, or null on OOM.
00415     elem_type* InsertElementAt(index_type index) {
00416       if (!EnsureCapacity(Length() + 1, sizeof(elem_type)))
00417          return nsnull;
00418       ShiftData(index, 0, 1, sizeof(elem_type));
00419       elem_type *elem = Elements() + index;
00420       elem_traits::Construct(elem);
00421       return elem;
00422     }
00423 
00424     // This method appends elements to the end of this array.
00425     // @param array     The elements to append to this array.
00426     // @param arrayLen  The number of elements to append to this array.
00427     // @return          A pointer to the new elements in the array, or null if
00428     //                  the operation failed due to insufficient memory.
00429     template<class Item>
00430     elem_type *AppendElements(const Item* array, size_type arrayLen) {
00431       if (!EnsureCapacity(Length() + arrayLen, sizeof(elem_type)))
00432         return nsnull;
00433       index_type len = Length();
00434       AssignRange(len, arrayLen, array);
00435       IncrementLength(arrayLen);
00436       return Elements() + len;
00437     }
00438 
00439     // A variation on the AppendElements method defined above.
00440     template<class Item>
00441     elem_type *AppendElements(const nsTArray<Item>& array) {
00442       return AppendElements(array.Elements(), array.Length());
00443     }
00444 
00445     // A variation on the AppendElements method defined above.
00446     template<class Item>
00447     elem_type *AppendElement(const Item& item) {
00448       return AppendElements(&item, 1);
00449     }
00450 
00451     // Append a new element without copy-constructing. This is useful to avoid
00452     // temporaries.
00453     // @return A pointer to the newly appended element, or null on OOM.
00454     elem_type *AppendElement() {
00455       if (!EnsureCapacity(Length() + 1, sizeof(elem_type)))
00456          return nsnull;
00457       elem_type *elem = Elements() + Length();
00458       elem_traits::Construct(elem);
00459       IncrementLength(1);
00460       return elem;
00461     }
00462 
00463     // This method removes a range of elements from this array.
00464     // @param start  The starting index of the elements to remove.
00465     // @param count  The number of elements to remove.
00466     void RemoveElementsAt(index_type start, size_type count) {
00467       DestructRange(start, count);
00468       ShiftData(start, count, 0, sizeof(elem_type));
00469     }
00470 
00471     // A variation on the RemoveElementsAt method defined above.
00472     void RemoveElementAt(index_type index) {
00473       RemoveElementsAt(index, 1);
00474     }
00475 
00476     // A variation on the RemoveElementsAt method defined above.
00477     void Clear() {
00478       RemoveElementsAt(0, Length());
00479     }
00480 
00481     // This helper function combines IndexOf with RemoveElementAt to "search
00482     // and destroy" the first element that is equal to the given element.
00483     // @param item  The item to search for.
00484     // @param comp  The Comparator used to determine element equality.
00485     template<class Item, class Comparator>
00486     void RemoveElement(const Item& item, const Comparator& comp) {
00487       index_type i = IndexOf(item, 0, comp);
00488       if (i != NoIndex)
00489         RemoveElementAt(i);
00490     }
00491 
00492     // A variation on the RemoveElement method defined above that assumes
00493     // that 'operator==' is defined for elem_type.
00494     template<class Item>
00495     void RemoveElement(const Item& item) {
00496       RemoveElement(item, nsDefaultComparator<elem_type, Item>());
00497     }
00498 
00499     //
00500     // Allocation
00501     //
00502 
00503     // This method may increase the capacity of this array object by the
00504     // specified amount.  This method may be called in advance of several
00505     // AppendElement operations to minimize heap re-allocations.  This method
00506     // will not reduce the number of elements in this array.
00507     // @param capacity  The desired capacity of this array.
00508     void SetCapacity(size_type capacity) {
00509       EnsureCapacity(capacity, sizeof(elem_type));
00510     }
00511 
00512     // This method modifies the length of the array.  If the new length is
00513     // larger than the existing length of the array, then new elements will be
00514     // constructed using elem_type's default constructor.  Otherwise, this call
00515     // removes elements from the array (see also RemoveElementsAt).
00516     // @param newLen  The desired length of this array.
00517     // @return        True if the operation succeeded; false otherwise.
00518     PRBool SetLength(size_type newLen) {
00519       size_type oldLen = Length();
00520       if (newLen > oldLen) {
00521         SetCapacity(newLen);
00522         // Check for out of memory conditions
00523         if (Capacity() < newLen)
00524           return PR_FALSE;
00525         // Initialize the extra array elements
00526         elem_type *iter = Elements() + oldLen, *end = Elements() + newLen;
00527         for (; iter != end; ++iter) {
00528           elem_traits::Construct(iter);
00529         }
00530         IncrementLength(newLen - oldLen);
00531       } else {
00532         RemoveElementsAt(newLen, oldLen - newLen);
00533       }
00534       return PR_TRUE;
00535     }
00536 
00537     // This method may be called to minimize the memory used by this array.
00538     void Compact() {
00539       ShrinkCapacity(sizeof(elem_type));
00540     }
00541 
00542     //
00543     // Sorting
00544     //
00545 
00546     // This method sorts the elements of the array.  It uses the LessThan
00547     // method defined on the given Comparator object to collate elements.
00548     // @param c  The Comparator to used to collate elements.
00549     template<class Comparator>
00550     void Sort(const Comparator& comp) {
00551       NS_QuickSort(Elements(), Length(), sizeof(elem_type),
00552                    nsQuickSortComparator<elem_type, Comparator>::Compare,
00553                    NS_CONST_CAST(Comparator*, &comp));
00554     }
00555 
00556     // A variation on the Sort method defined above that assumes that
00557     // 'operator<' is defined for elem_type.
00558     void Sort() {
00559       Sort(nsDefaultComparator<elem_type, elem_type>());
00560     }
00561 
00562   protected:
00563 
00564     // This method invokes elem_type's destructor on a range of elements.
00565     // @param start  The index of the first element to destroy.
00566     // @param count  The number of elements to destroy.
00567     void DestructRange(index_type start, size_type count) {
00568       elem_type *iter = Elements() + start, *end = iter + count;
00569       for (; iter != end; ++iter) {
00570         elem_traits::Destruct(iter);
00571       }
00572     }
00573 
00574     // This method invokes elem_type's copy-constructor on a range of elements.
00575     // @param start   The index of the first element to construct.
00576     // @param count   The number of elements to construct. 
00577     // @param values  The array of elements to copy. 
00578     template<class Item>
00579     void AssignRange(index_type start, size_type count,
00580                      const Item *values) {
00581       elem_type *iter = Elements() + start, *end = iter + count;
00582       for (; iter != end; ++iter, ++values) {
00583         elem_traits::Construct(iter, *values);
00584       }
00585     }
00586 };
00587 
00588 #endif  // nsTArray_h__