xpcom/glue/nsVoidArray.h

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0))  -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is mozilla.org code.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Netscape Communications Corporation.
  19  * Portions created by the Initial Developer are Copyright (C) 1998
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either of the GNU General Public License Version 2 or later (the "GPL"),
  26  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37 #ifndef nsVoidArray_h___
  38 #define nsVoidArray_h___
  39
  40 //#define DEBUG_VOIDARRAY 1
  41
  42 #include "nscore.h"
  43 #include "nsStringGlue.h"
  44 #include "nsDebug.h"
  45
  46 // Comparator callback function for sorting array values.
  47 typedef int (* nsVoidArrayComparatorFunc)
  48             (const void* aElement1, const void* aElement2, void* aData);
  49
  50 // Enumerator callback function. Return PR_FALSE to stop
  51 typedef PRBool (* nsVoidArrayEnumFunc)(void* aElement, void *aData);
  52
  53 /// A basic zero-based array of void*'s that manages its own memory
  54 class NS_COM_GLUE nsVoidArray {
  55 public:
  56   nsVoidArray();
  57   nsVoidArray(PRInt32 aCount);  // initial count of aCount elements set to nsnull
  58   ~nsVoidArray();
  59
  60   nsVoidArray& operator=(const nsVoidArray& other);
  61
  62   inline PRInt32 Count() const {
  63     return mImpl ? mImpl->mCount : 0;
  64   }
  65   // returns the max number that can be held without allocating
  66   inline PRInt32 GetArraySize() const {
  67     return mImpl ? (PRInt32(mImpl->mBits) & kArraySizeMask) : 0;
  68   }
  69
  70   void* FastElementAt(PRInt32 aIndex) const
  71   {
  72     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsVoidArray::FastElementAt: index out of range");
  73     return mImpl->mArray[aIndex];
  74   }
  75
  76   // This both asserts and bounds-checks, because (1) we don't want
  77   // people to write bad code, but (2) we don't want to change it to
  78   // crashing for backwards compatibility.  See bug 96108.
  79   void* ElementAt(PRInt32 aIndex) const
  80   {
  81     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsVoidArray::ElementAt: index out of range");
  82     return SafeElementAt(aIndex);
  83   }
  84
  85   // bounds-checked version
  86   void* SafeElementAt(PRInt32 aIndex) const
  87   {
  88     if (PRUint32(aIndex) >= PRUint32(Count())) // handles aIndex < 0 too
  89     {
  90       return nsnull;
  91     }
  92     // The bounds check ensures mImpl is non-null.
  93     return mImpl->mArray[aIndex];
  94   }
  95
  96   void* operator[](PRInt32 aIndex) const { return ElementAt(aIndex); }
  97
  98   PRInt32 IndexOf(void* aPossibleElement) const;
  99
 100   PRBool InsertElementAt(void* aElement, PRInt32 aIndex);
 101   PRBool InsertElementsAt(const nsVoidArray &other, PRInt32 aIndex);
 102
 103   PRBool ReplaceElementAt(void* aElement, PRInt32 aIndex);
 104
 105   // useful for doing LRU arrays, sorting, etc
 106   PRBool MoveElement(PRInt32 aFrom, PRInt32 aTo);
 107
 108   PRBool AppendElement(void* aElement) {
 109     return InsertElementAt(aElement, Count());
 110   }
 111
 112   PRBool AppendElements(nsVoidArray& aElements) {
 113     return InsertElementsAt(aElements, Count());
 114   }
 115
 116   PRBool RemoveElement(void* aElement);
 117   PRBool RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount);
 118   PRBool RemoveElementAt(PRInt32 aIndex) { return RemoveElementsAt(aIndex,1); }
 119
 120   void   Clear();
 121
 122   PRBool SizeTo(PRInt32 aMin);
 123   // Subtly different - Compact() tries to be smart about whether we
 124   // should reallocate the array; SizeTo() always reallocates.
 125   void Compact();
 126
 127   void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
 128
 129   PRBool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
 130   PRBool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
 131
 132 protected:
 133   PRBool GrowArrayBy(PRInt32 aGrowBy);
 134
 135   struct Impl {
 136     /**
 137      * Packed bits. The low 30 bits are the array's size.
 138      * The two highest bits indicate whether or not we "own" mImpl and
 139      * must free() it when destroyed, and whether we have a preallocated
 140      * nsAutoVoidArray buffer.
 141      */
 142     PRUint32 mBits;
 143
 144     /**
 145      * The number of elements in the array
 146      */
 147     PRInt32 mCount;
 148
 149     /**
 150      * Array data, padded out to the actual size of the array.
 151      */
 152     void*   mArray[1];
 153   };
 154
 155   Impl* mImpl;
 156 #if DEBUG_VOIDARRAY
 157   PRInt32 mMaxCount;
 158   PRInt32 mMaxSize;
 159   PRBool  mIsAuto;
 160 #endif
 161
 162   enum {
 163     kArrayOwnerMask = 1 << 31,
 164     kArrayHasAutoBufferMask = 1 << 30,
 165     kArraySizeMask = ~(kArrayOwnerMask | kArrayHasAutoBufferMask)
 166   };
 167   enum { kAutoBufSize = 8 };
 168
 169
 170   // bit twiddlers
 171   void SetArray(Impl *newImpl, PRInt32 aSize, PRInt32 aCount, PRBool aOwner,
 172                 PRBool aHasAuto);
 173   inline PRBool IsArrayOwner() const {
 174     return mImpl && (mImpl->mBits & kArrayOwnerMask);
 175   }
 176   inline PRBool HasAutoBuffer() const {
 177     return mImpl && (mImpl->mBits & kArrayHasAutoBufferMask);
 178   }
 179
 180 private:
 181   /// Copy constructors are not allowed
 182   nsVoidArray(const nsVoidArray& other);
 183 };
 184
 185
 186 // A zero-based array with a bit of automatic internal storage
 187 class NS_COM_GLUE nsAutoVoidArray : public nsVoidArray {
 188 public:
 189   nsAutoVoidArray();
 190
 191   void ResetToAutoBuffer()
 192   {
 193     SetArray(reinterpret_cast<Impl*>(mAutoBuf), kAutoBufSize, 0, PR_FALSE,
 194              PR_TRUE);
 195   }
 196
 197 protected:
 198   // The internal storage
 199   char mAutoBuf[sizeof(Impl) + (kAutoBufSize - 1) * sizeof(void*)];
 200 };
 201
 202
 203 class nsString;
 204
 205 typedef int (* nsStringArrayComparatorFunc)
 206             (const nsString* aElement1, const nsString* aElement2, void* aData);
 207
 208 typedef PRBool (*nsStringArrayEnumFunc)(nsString& aElement, void *aData);
 209
 210 class NS_COM_GLUE nsStringArray: private nsVoidArray
 211 {
 212 public:
 213   nsStringArray(void);
 214   nsStringArray(PRInt32 aCount);  // Storage for aCount elements will be pre-allocated
 215   ~nsStringArray(void);
 216
 217   nsStringArray& operator=(const nsStringArray& other);
 218
 219   PRInt32 Count(void) const {
 220     return nsVoidArray::Count();
 221   }
 222
 223   void StringAt(PRInt32 aIndex, nsAString& aString) const;
 224   nsString* StringAt(PRInt32 aIndex) const;
 225   nsString* operator[](PRInt32 aIndex) const { return StringAt(aIndex); }
 226
 227   PRInt32 IndexOf(const nsAString& aPossibleString) const;
 228
 229   PRBool InsertStringAt(const nsAString& aString, PRInt32 aIndex);
 230
 231   PRBool ReplaceStringAt(const nsAString& aString, PRInt32 aIndex);
 232
 233   PRBool AppendString(const nsAString& aString) {
 234     return InsertStringAt(aString, Count());
 235   }
 236
 237   PRBool RemoveString(const nsAString& aString);
 238   PRBool RemoveStringAt(PRInt32 aIndex);
 239   void   Clear(void);
 240
 241   void Compact(void) {
 242     nsVoidArray::Compact();
 243   }
 244
 245   void Sort(void);
 246   void Sort(nsStringArrayComparatorFunc aFunc, void* aData);
 247
 248   PRBool EnumerateForwards(nsStringArrayEnumFunc aFunc, void* aData);
 249   PRBool EnumerateBackwards(nsStringArrayEnumFunc aFunc, void* aData);
 250
 251 private:
 252   /// Copy constructors are not allowed
 253   nsStringArray(const nsStringArray& other);
 254 };
 255
 256
 257 class nsCString;
 258
 259 typedef int (* nsCStringArrayComparatorFunc)
 260             (const nsCString* aElement1, const nsCString* aElement2, void* aData);
 261
 262 typedef PRBool (*nsCStringArrayEnumFunc)(nsCString& aElement, void *aData);
 263
 264 class NS_COM_GLUE nsCStringArray: private nsVoidArray
 265 {
 266 public:
 267   nsCStringArray(void);
 268   nsCStringArray(PRInt32 aCount); // Storage for aCount elements will be pre-allocated
 269   ~nsCStringArray(void);
 270
 271   nsCStringArray& operator=(const nsCStringArray& other);
 272
 273   // Parses a given string using the delimiter passed in. If the array
 274   // already has some elements, items parsed from string will be appended
 275   // to array. For example, array.ParseString("a,b,c", ","); will add strings
 276   // "a", "b" and "c" to the array. Parsing process has the same tokenizing
 277   // behavior as strtok().
 278   PRBool ParseString(const char* string, const char* delimiter);
 279
 280   PRInt32 Count(void) const {
 281     return nsVoidArray::Count();
 282   }
 283
 284   void CStringAt(PRInt32 aIndex, nsACString& aCString) const;
 285   nsCString* CStringAt(PRInt32 aIndex) const;
 286   nsCString* operator[](PRInt32 aIndex) const { return CStringAt(aIndex); }
 287
 288   PRInt32 IndexOf(const nsACString& aPossibleString) const;
 289
 290 #ifdef MOZILLA_INTERNAL_API
 291   PRInt32 IndexOfIgnoreCase(const nsACString& aPossibleString) const;
 292 #endif
 293
 294   PRBool InsertCStringAt(const nsACString& aCString, PRInt32 aIndex);
 295
 296   PRBool ReplaceCStringAt(const nsACString& aCString, PRInt32 aIndex);
 297
 298   PRBool AppendCString(const nsACString& aCString) {
 299     return InsertCStringAt(aCString, Count());
 300   }
 301
 302   PRBool RemoveCString(const nsACString& aCString);
 303
 304 #ifdef MOZILLA_INTERNAL_API
 305   PRBool RemoveCStringIgnoreCase(const nsACString& aCString);
 306 #endif
 307
 308   PRBool RemoveCStringAt(PRInt32 aIndex);
 309   void   Clear(void);
 310
 311   void Compact(void) {
 312     nsVoidArray::Compact();
 313   }
 314
 315   void Sort(void);
 316
 317 #ifdef MOZILLA_INTERNAL_API
 318   void SortIgnoreCase(void);
 319 #endif
 320
 321   void Sort(nsCStringArrayComparatorFunc aFunc, void* aData);
 322
 323   PRBool EnumerateForwards(nsCStringArrayEnumFunc aFunc, void* aData);
 324   PRBool EnumerateBackwards(nsCStringArrayEnumFunc aFunc, void* aData);
 325
 326 private:
 327   /// Copy constructors are not allowed
 328   nsCStringArray(const nsCStringArray& other);
 329 };
 330
 331
 332 //===================================================================
 333 //  nsSmallVoidArray is not a general-purpose replacement for
 334 //  ns(Auto)VoidArray because there is (some) extra CPU overhead for arrays
 335 //  larger than 1 element, though not a lot.  It is appropriate for
 336 //  space-sensitive uses where sizes of 0 or 1 are moderately common or
 337 //  more, and where we're NOT storing arbitrary integers or arbitrary
 338 //  pointers.
 339
 340 // NOTE: nsSmallVoidArray can ONLY be used for holding items that always
 341 // have the low bit as a 0 - i.e. element & 1 == 0.  This happens to be
 342 // true for allocated and object pointers for all the architectures we run
 343 // on, but conceivably there might be some architectures/compilers for
 344 // which it is NOT true.  We know this works for all existing architectures
 345 // because if it didn't then nsCheapVoidArray would have failed.  Also note
 346 // that we will ASSERT if this assumption is violated in DEBUG builds.
 347
 348 // XXX we're really re-implementing the whole nsVoidArray interface here -
 349 // some form of abstract class would be useful
 350
 351 // I disagree on the abstraction here.  If the point of this class is to be
 352 // as small as possible, and no one will ever derive from it, as I found
 353 // today, there should not be any virtualness to it to avoid the vtable
 354 // ptr overhead.
 355
 356 class NS_COM_GLUE nsSmallVoidArray : private nsVoidArray
 357 {
 358 public:
 359   ~nsSmallVoidArray();
 360
 361   nsSmallVoidArray& operator=(nsSmallVoidArray& other);
 362   void* operator[](PRInt32 aIndex) const { return ElementAt(aIndex); }
 363
 364   PRInt32 GetArraySize() const;
 365
 366   PRInt32 Count() const;
 367   void* FastElementAt(PRInt32 aIndex) const;
 368   // This both asserts and bounds-checks, because (1) we don't want
 369   // people to write bad code, but (2) we don't want to change it to
 370   // crashing for backwards compatibility.  See bug 96108.
 371   void* ElementAt(PRInt32 aIndex) const
 372   {
 373     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::ElementAt: index out of range");
 374     return SafeElementAt(aIndex);
 375   }
 376   void* SafeElementAt(PRInt32 aIndex) const {
 377     // let compiler inline; it may be able to remove these checks
 378     if (PRUint32(aIndex) >= PRUint32(Count())) // handles aIndex < 0 too
 379     {
 380       return nsnull;
 381     }
 382     return FastElementAt(aIndex);
 383   }
 384   PRInt32 IndexOf(void* aPossibleElement) const;
 385   PRBool InsertElementAt(void* aElement, PRInt32 aIndex);
 386   PRBool InsertElementsAt(const nsVoidArray &other, PRInt32 aIndex);
 387   PRBool ReplaceElementAt(void* aElement, PRInt32 aIndex);
 388   PRBool MoveElement(PRInt32 aFrom, PRInt32 aTo);
 389   PRBool AppendElement(void* aElement);
 390   PRBool AppendElements(nsVoidArray& aElements) {
 391     return InsertElementsAt(aElements, Count());
 392   }
 393   PRBool RemoveElement(void* aElement);
 394   PRBool RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount);
 395   PRBool RemoveElementAt(PRInt32 aIndex);
 396
 397   void Clear();
 398   PRBool SizeTo(PRInt32 aMin);
 399   void Compact();
 400   void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
 401
 402   PRBool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
 403   PRBool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
 404
 405 private:
 406
 407   PRBool HasSingle() const
 408   {
 409     return !!(reinterpret_cast<PRWord>(mImpl) & 0x1);
 410   }
 411   void* GetSingle() const
 412   {
 413     NS_ASSERTION(HasSingle(), "wrong type");
 414     return reinterpret_cast<void*>
 415                            (reinterpret_cast<PRWord>(mImpl) & ~0x1);
 416   }
 417   void SetSingle(void *aChild)
 418   {
 419     NS_ASSERTION(HasSingle() || !mImpl, "overwriting array");
 420     mImpl = reinterpret_cast<Impl*>
 421                             (reinterpret_cast<PRWord>(aChild) | 0x1);
 422   }
 423   PRBool IsEmpty() const
 424   {
 425     // Note that this isn't the same as Count()==0
 426     return !mImpl;
 427   }
 428   const nsVoidArray* AsArray() const
 429   {
 430     NS_ASSERTION(!HasSingle(), "This is a single");
 431     return this;
 432   }
 433   nsVoidArray* AsArray()
 434   {
 435     NS_ASSERTION(!HasSingle(), "This is a single");
 436     return this;
 437   }
 438   PRBool EnsureArray();
 439 };
 440
 441 #endif /* nsVoidArray_h___ */