Back to index

lightning-sunbird  0.9+nobinonly
nsVoidArray.h
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0))  -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either of the GNU General Public License Version 2 or later (the "GPL"),
00026  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 #ifndef nsVoidArray_h___
00038 #define nsVoidArray_h___
00039 
00040 //#define DEBUG_VOIDARRAY 1
00041 
00042 #include "nscore.h"
00043 #include "nsAString.h"
00044 
00045 // Comparator callback function for sorting array values.
00046 typedef int (* PR_CALLBACK nsVoidArrayComparatorFunc)
00047             (const void* aElement1, const void* aElement2, void* aData);
00048 
00049 // Enumerator callback function. Return PR_FALSE to stop
00050 typedef PRBool (* PR_CALLBACK nsVoidArrayEnumFunc)(void* aElement, void *aData);
00051 
00053 class NS_COM nsVoidArray {
00054 public:
00055   nsVoidArray();
00056   nsVoidArray(PRInt32 aCount);  // initial count of aCount elements set to nsnull
00057   virtual ~nsVoidArray();
00058 
00059   nsVoidArray& operator=(const nsVoidArray& other);
00060 
00061   inline PRInt32 Count() const {
00062     return mImpl ? mImpl->mCount : 0;
00063   }
00064   // returns the max number that can be held without allocating
00065   inline PRInt32 GetArraySize() const {
00066     return mImpl ? (PRInt32(mImpl->mBits) & kArraySizeMask) : 0;
00067   }
00068 
00069   void* FastElementAt(PRInt32 aIndex) const
00070   {
00071     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "index out of range");
00072     return mImpl->mArray[aIndex];
00073   }
00074 
00075   // This both asserts and bounds-checks, because (1) we don't want
00076   // people to write bad code, but (2) we don't want to change it to
00077   // crashing for backwards compatibility.  See bug 96108.
00078   void* ElementAt(PRInt32 aIndex) const
00079   {
00080     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "index out of range");
00081     return SafeElementAt(aIndex);
00082   }
00083 
00084   // bounds-checked version
00085   void* SafeElementAt(PRInt32 aIndex) const
00086   {
00087     if (PRUint32(aIndex) >= PRUint32(Count())) // handles aIndex < 0 too
00088     {
00089       return nsnull;
00090     }
00091     // The bounds check ensures mImpl is non-null.
00092     return mImpl->mArray[aIndex];
00093   }
00094 
00095   void* operator[](PRInt32 aIndex) const { return ElementAt(aIndex); }
00096 
00097   PRInt32 IndexOf(void* aPossibleElement) const;
00098 
00099   PRBool InsertElementAt(void* aElement, PRInt32 aIndex);
00100   PRBool InsertElementsAt(const nsVoidArray &other, PRInt32 aIndex);
00101 
00102   PRBool ReplaceElementAt(void* aElement, PRInt32 aIndex);
00103 
00104   // useful for doing LRU arrays, sorting, etc
00105   PRBool MoveElement(PRInt32 aFrom, PRInt32 aTo);
00106 
00107   PRBool AppendElement(void* aElement) {
00108     return InsertElementAt(aElement, Count());
00109   }
00110 
00111   PRBool AppendElements(nsVoidArray& aElements) {
00112     return InsertElementsAt(aElements, Count());
00113   }
00114 
00115   PRBool RemoveElement(void* aElement);
00116   PRBool RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount);
00117   PRBool RemoveElementAt(PRInt32 aIndex) { return RemoveElementsAt(aIndex,1); }
00118 
00119   virtual void   Clear();
00120 
00121   virtual PRBool SizeTo(PRInt32 aMin);
00122   // Subtly different - Compact() tries to be smart about whether we
00123   // should reallocate the array; SizeTo() just does it.
00124   virtual void Compact();
00125 
00126   void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
00127 
00128   PRBool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
00129   PRBool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
00130 
00131 protected:
00132   virtual PRBool GrowArrayBy(PRInt32 aGrowBy);
00133 
00134   struct Impl {
00141     PRUint32 mBits;
00142 
00146     PRInt32 mCount;
00147 
00151     void*   mArray[1];
00152   };
00153 
00154   Impl* mImpl;
00155 #if DEBUG_VOIDARRAY
00156   PRInt32 mMaxCount;
00157   PRInt32 mMaxSize;
00158   PRBool  mIsAuto;
00159 #endif
00160 
00161   enum {
00162     kArrayOwnerMask = 1 << 31,
00163     kArraySizeMask = ~kArrayOwnerMask
00164   };
00165 
00166 
00167   // bit twiddlers
00168   void SetArray(Impl *newImpl, PRInt32 aSize, PRInt32 aCount, PRBool owner);
00169   inline PRBool IsArrayOwner() const {
00170     return mImpl ? (PRBool(mImpl->mBits) & kArrayOwnerMask) : PR_FALSE;
00171   }
00172 
00173 private:
00175   nsVoidArray(const nsVoidArray& other);
00176 };
00177 
00178 
00179 // A zero-based array with a bit of automatic internal storage
00180 class NS_COM nsAutoVoidArray : public nsVoidArray {
00181 public:
00182   nsAutoVoidArray();
00183   void Clear();
00184 
00185   virtual PRBool SizeTo(PRInt32 aMin);
00186   virtual void Compact();
00187   
00188 protected:
00189   // The internal storage
00190   enum { kAutoBufSize = 8 };
00191   char mAutoBuf[sizeof(Impl) + (kAutoBufSize - 1) * sizeof(void*)];
00192 };
00193 
00194 
00195 class nsString;
00196 
00197 typedef int (* PR_CALLBACK nsStringArrayComparatorFunc)
00198             (const nsString* aElement1, const nsString* aElement2, void* aData);
00199 
00200 typedef PRBool (*nsStringArrayEnumFunc)(nsString& aElement, void *aData);
00201 
00202 class NS_COM nsStringArray: protected nsVoidArray
00203 {
00204 public:
00205   nsStringArray(void);
00206   nsStringArray(PRInt32 aCount);  // Storage for aCount elements will be pre-allocated
00207   virtual ~nsStringArray(void);
00208 
00209   nsStringArray& operator=(const nsStringArray& other);
00210 
00211   PRInt32 Count(void) const {
00212     return nsVoidArray::Count();
00213   }
00214 
00215   void StringAt(PRInt32 aIndex, nsAString& aString) const;
00216   nsString* StringAt(PRInt32 aIndex) const;
00217   nsString* operator[](PRInt32 aIndex) const { return StringAt(aIndex); }
00218 
00219   PRInt32 IndexOf(const nsAString& aPossibleString) const;
00220 
00221   PRBool InsertStringAt(const nsAString& aString, PRInt32 aIndex);
00222 
00223   PRBool ReplaceStringAt(const nsAString& aString, PRInt32 aIndex);
00224 
00225   PRBool AppendString(const nsAString& aString) {
00226     return InsertStringAt(aString, Count());
00227   }
00228 
00229   PRBool RemoveString(const nsAString& aString);
00230   PRBool RemoveStringAt(PRInt32 aIndex);
00231   void   Clear(void);
00232 
00233   void Compact(void) {
00234     nsVoidArray::Compact();
00235   }
00236 
00237   void Sort(void);
00238   void Sort(nsStringArrayComparatorFunc aFunc, void* aData);
00239 
00240   PRBool EnumerateForwards(nsStringArrayEnumFunc aFunc, void* aData);
00241   PRBool EnumerateBackwards(nsStringArrayEnumFunc aFunc, void* aData);
00242 
00243 private:
00245   nsStringArray(const nsStringArray& other);
00246 };
00247 
00248 
00249 class nsCString;
00250 
00251 typedef int (* PR_CALLBACK nsCStringArrayComparatorFunc)
00252             (const nsCString* aElement1, const nsCString* aElement2, void* aData);
00253 
00254 typedef PRBool (*nsCStringArrayEnumFunc)(nsCString& aElement, void *aData);
00255 
00256 class NS_COM nsCStringArray: protected nsVoidArray
00257 {
00258 public:
00259   nsCStringArray(void);
00260   nsCStringArray(PRInt32 aCount); // Storage for aCount elements will be pre-allocated
00261   virtual ~nsCStringArray(void);
00262 
00263   nsCStringArray& operator=(const nsCStringArray& other);
00264 
00265   // Parses a given string using the delimiter passed in. If the array
00266   // already has some elements, items parsed from string will be appended 
00267   // to array. For example, array.ParseString("a,b,c", ","); will add strings
00268   // "a", "b" and "c" to the array. Parsing process has the same tokenizing 
00269   // behavior as strtok().  
00270   void ParseString(const char* string, const char* delimiter);
00271 
00272   PRInt32 Count(void) const {
00273     return nsVoidArray::Count();
00274   }
00275 
00276   void CStringAt(PRInt32 aIndex, nsACString& aCString) const;
00277   nsCString* CStringAt(PRInt32 aIndex) const;
00278   nsCString* operator[](PRInt32 aIndex) const { return CStringAt(aIndex); }
00279 
00280   PRInt32 IndexOf(const nsACString& aPossibleString) const;
00281   PRInt32 IndexOfIgnoreCase(const nsACString& aPossibleString) const;
00282 
00283   PRBool InsertCStringAt(const nsACString& aCString, PRInt32 aIndex);
00284 
00285   PRBool ReplaceCStringAt(const nsACString& aCString, PRInt32 aIndex);
00286 
00287   PRBool AppendCString(const nsACString& aCString) {
00288     return InsertCStringAt(aCString, Count());
00289   }
00290 
00291   PRBool RemoveCString(const nsACString& aCString);
00292   PRBool RemoveCStringIgnoreCase(const nsACString& aCString);
00293   PRBool RemoveCStringAt(PRInt32 aIndex);
00294   void   Clear(void);
00295 
00296   void Compact(void) {
00297     nsVoidArray::Compact();
00298   }
00299 
00300   void Sort(void);
00301   void SortIgnoreCase(void);
00302   void Sort(nsCStringArrayComparatorFunc aFunc, void* aData);
00303 
00304   PRBool EnumerateForwards(nsCStringArrayEnumFunc aFunc, void* aData);
00305   PRBool EnumerateBackwards(nsCStringArrayEnumFunc aFunc, void* aData);
00306 
00307 private:
00309   nsCStringArray(const nsCStringArray& other);
00310 };
00311 
00312 
00313 //===================================================================
00314 //  nsSmallVoidArray is not a general-purpose replacement for
00315 //  ns(Auto)VoidArray because there is (some) extra CPU overhead for arrays
00316 //  larger than 1 element, though not a lot.  It is appropriate for
00317 //  space-sensitive uses where sizes of 0 or 1 are moderately common or
00318 //  more, and where we're NOT storing arbitrary integers or arbitrary
00319 //  pointers.
00320 
00321 // NOTE: nsSmallVoidArray can ONLY be used for holding items that always
00322 // have the low bit as a 0 - i.e. element & 1 == 0.  This happens to be
00323 // true for allocated and object pointers for all the architectures we run
00324 // on, but conceivably there might be some architectures/compilers for
00325 // which it is NOT true.  We know this works for all existing architectures
00326 // because if it didn't then nsCheapVoidArray would have failed.  Also note
00327 // that we will ASSERT if this assumption is violated in DEBUG builds.
00328 
00329 // XXX we're really re-implementing the whole nsVoidArray interface here -
00330 // some form of abstract class would be useful
00331 
00332 // I disagree on the abstraction here.  If the point of this class is to be
00333 // as small as possible, and no one will ever derive from it, as I found
00334 // today, there should not be any virtualness to it to avoid the vtable
00335 // ptr overhead.
00336 
00337 class NS_COM nsSmallVoidArray
00338 {
00339 public:
00340   nsSmallVoidArray();
00341   ~nsSmallVoidArray();
00342 
00343   nsSmallVoidArray& operator=(nsSmallVoidArray& other);
00344   void* operator[](PRInt32 aIndex) const { return ElementAt(aIndex); }
00345 
00346   PRInt32 GetArraySize() const;
00347 
00348   PRInt32 Count() const;
00349   void* ElementAt(PRInt32 aIndex) const;
00350   void* SafeElementAt(PRInt32 aIndex) const {
00351     // let compiler inline; it may be able to remove these checks
00352     if (aIndex < 0 || aIndex >= Count())
00353       return nsnull;
00354     return ElementAt(aIndex);
00355   }
00356   PRInt32 IndexOf(void* aPossibleElement) const;
00357   PRBool InsertElementAt(void* aElement, PRInt32 aIndex);
00358   PRBool InsertElementsAt(const nsVoidArray &other, PRInt32 aIndex);
00359   PRBool ReplaceElementAt(void* aElement, PRInt32 aIndex);
00360   PRBool MoveElement(PRInt32 aFrom, PRInt32 aTo);
00361   PRBool AppendElement(void* aElement);
00362   PRBool AppendElements(nsVoidArray& aElements) {
00363     return InsertElementsAt(aElements, Count());
00364   }
00365   PRBool RemoveElement(void* aElement);
00366   PRBool RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount);
00367   PRBool RemoveElementAt(PRInt32 aIndex);
00368 
00369   void Clear();
00370   PRBool SizeTo(PRInt32 aMin);
00371   void Compact();
00372   void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
00373 
00374   PRBool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
00375   PRBool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
00376 
00377 private:
00378   typedef unsigned long PtrBits;
00379 
00380   PRBool HasSingleChild() const
00381   {
00382     return (mChildren && (PtrBits(mChildren) & 0x1));
00383   }
00384   PRBool HasVector() const
00385   {
00386     return (mChildren && !(PtrBits(mChildren) & 0x1));
00387   }
00388   void* GetSingleChild() const
00389   {
00390     return (mChildren ? ((void*)(PtrBits(mChildren) & ~0x1)) : nsnull);
00391   }
00392   void SetSingleChild(void *aChild);
00393   nsVoidArray* GetChildVector() const
00394   {
00395     return (nsVoidArray*)mChildren;
00396   }
00397   nsVoidArray* SwitchToVector();
00398 
00399   // A tagged pointer that's either a pointer to a single child
00400   // or a pointer to a vector of multiple children. This is a space
00401   // optimization since a large number of containers have only a 
00402   // single child.
00403   void *mChildren;  
00404 };
00405 
00406 #endif /* nsVoidArray_h___ */