text: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0))  -*- */
  /* ***** BEGIN LICENSE BLOCK *****
   * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   *
   * The contents of this file are subject to the Mozilla Public License Version
   * 1.1 (the "License"); you may not use this file except in compliance with
   * the License. You may obtain a copy of the License at
   * http://www.mozilla.org/MPL/
   *
   * Software distributed under the License is distributed on an "AS IS" basis,
   * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
   * for the specific language governing rights and limitations under the
   * License.
   *
   * The Original Code is mozilla.org code.
   *
   * The Initial Developer of the Original Code is
   * Netscape Communications Corporation.
   * Portions created by the Initial Developer are Copyright (C) 1998
   * the Initial Developer. All Rights Reserved.
   *
   * Contributor(s):
   *
   * Alternatively, the contents of this file may be used under the terms of
   * either of the GNU General Public License Version 2 or later (the "GPL"),
   * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
   * in which case the provisions of the GPL or the LGPL are applicable instead
   * of those above. If you wish to allow use of your version of this file only
   * under the terms of either the GPL or the LGPL, and not to allow others to
   * use your version of this file under the terms of the MPL, indicate your
   * decision by deleting the provisions above and replace them with the notice
   * and other provisions required by the GPL or the LGPL. If you do not delete
   * the provisions above, a recipient may use your version of this file under
   * the terms of any one of the MPL, the GPL or the LGPL.
   *
   * ***** END LICENSE BLOCK ***** */
  #ifndef nsVoidArray_h___
  #define nsVoidArray_h___
  
  //#define DEBUG_VOIDARRAY 1
  
  #include "nscore.h"
  #include "nsStringGlue.h"
  #include "nsDebug.h"
  
  // Comparator callback function for sorting array values.
  typedef int (* nsVoidArrayComparatorFunc)
              (const void* aElement1, const void* aElement2, void* aData);
  
  // Enumerator callback function. Return PR_FALSE to stop
  typedef PRBool (* nsVoidArrayEnumFunc)(void* aElement, void *aData);
  
  /// A basic zero-based array of void*'s that manages its own memory
  class NS_COM_GLUE nsVoidArray {
  public:
    nsVoidArray();
    nsVoidArray(PRInt32 aCount);  // initial count of aCount elements set to nsnull
    ~nsVoidArray();
  
    nsVoidArray& operator=(const nsVoidArray& other);
  
    inline PRInt32 Count() const {
      return mImpl ? mImpl->mCount : 0;
    }
    // returns the max number that can be held without allocating
    inline PRInt32 GetArraySize() const {
      return mImpl ? (PRInt32(mImpl->mBits) & kArraySizeMask) : 0;
    }
  
    void* FastElementAt(PRInt32 aIndex) const
    {
      NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsVoidArray::FastElementAt: index out of range");
      return mImpl->mArray[aIndex];
    }
  
    // This both asserts and bounds-checks, because (1) we don't want
    // people to write bad code, but (2) we don't want to change it to
    // crashing for backwards compatibility.  See bug 96108.
    void* ElementAt(PRInt32 aIndex) const
    {
      NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsVoidArray::ElementAt: index out of range");
      return SafeElementAt(aIndex);
    }
  
    // bounds-checked version
    void* SafeElementAt(PRInt32 aIndex) const
    {
      if (PRUint32(aIndex) >= PRUint32(Count())) // handles aIndex < 0 too
      {
        return nsnull;
      }
      // The bounds check ensures mImpl is non-null.
      return mImpl->mArray[aIndex];
    }
  
    void* operator[](PRInt32 aIndex) const { return ElementAt(aIndex); }
  
    PRInt32 IndexOf(void* aPossibleElement) const;
  
    PRBool InsertElementAt(void* aElement, PRInt32 aIndex);
    PRBool InsertElementsAt(const nsVoidArray &other, PRInt32 aIndex);
  
    PRBool ReplaceElementAt(void* aElement, PRInt32 aIndex);
  
    // useful for doing LRU arrays, sorting, etc
    PRBool MoveElement(PRInt32 aFrom, PRInt32 aTo);
  
    PRBool AppendElement(void* aElement) {
      return InsertElementAt(aElement, Count());
    }
  
    PRBool AppendElements(nsVoidArray& aElements) {
      return InsertElementsAt(aElements, Count());
    }
  
    PRBool RemoveElement(void* aElement);
    PRBool RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount);
    PRBool RemoveElementAt(PRInt32 aIndex) { return RemoveElementsAt(aIndex,1); }
  
    void   Clear();
  
    PRBool SizeTo(PRInt32 aMin);
    // Subtly different - Compact() tries to be smart about whether we
    // should reallocate the array; SizeTo() always reallocates.
    void Compact();
  
    void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
  
    PRBool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
    PRBool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
  
  protected:
    PRBool GrowArrayBy(PRInt32 aGrowBy);
  
    struct Impl {
      /**
       * Packed bits. The low 30 bits are the array's size.
       * The two highest bits indicate whether or not we "own" mImpl and
       * must free() it when destroyed, and whether we have a preallocated
       * nsAutoVoidArray buffer.
       */
      PRUint32 mBits;
  
      /**
       * The number of elements in the array
       */
      PRInt32 mCount;
  
      /**
       * Array data, padded out to the actual size of the array.
       */
      void*   mArray[1];
    };
  
    Impl* mImpl;
  #if DEBUG_VOIDARRAY
    PRInt32 mMaxCount;
    PRInt32 mMaxSize;
    PRBool  mIsAuto;
  #endif
  
    enum {
      kArrayOwnerMask = 1 << 31,
      kArrayHasAutoBufferMask = 1 << 30,
      kArraySizeMask = ~(kArrayOwnerMask | kArrayHasAutoBufferMask)
    };
    enum { kAutoBufSize = 8 };
  
  
    // bit twiddlers
    void SetArray(Impl *newImpl, PRInt32 aSize, PRInt32 aCount, PRBool aOwner,
                  PRBool aHasAuto);
    inline PRBool IsArrayOwner() const {
      return mImpl && (mImpl->mBits & kArrayOwnerMask);
    }
    inline PRBool HasAutoBuffer() const {
      return mImpl && (mImpl->mBits & kArrayHasAutoBufferMask);
    }
  
  private:
    /// Copy constructors are not allowed
    nsVoidArray(const nsVoidArray& other);
  };
  
  
  // A zero-based array with a bit of automatic internal storage
  class NS_COM_GLUE nsAutoVoidArray : public nsVoidArray {
  public:
    nsAutoVoidArray();
  
    void ResetToAutoBuffer()
    {
      SetArray(reinterpret_cast<Impl*>(mAutoBuf), kAutoBufSize, 0, PR_FALSE,
               PR_TRUE);
    }
    
  protected:
    // The internal storage
    char mAutoBuf[sizeof(Impl) + (kAutoBufSize - 1) * sizeof(void*)];
  };
  
  
  class nsString;
  
  typedef int (* nsStringArrayComparatorFunc)
              (const nsString* aElement1, const nsString* aElement2, void* aData);
  
  typedef PRBool (*nsStringArrayEnumFunc)(nsString& aElement, void *aData);
  
  class NS_COM_GLUE nsStringArray: private nsVoidArray
  {
  public:
    nsStringArray(void);
    nsStringArray(PRInt32 aCount);  // Storage for aCount elements will be pre-allocated
    ~nsStringArray(void);
  
    nsStringArray& operator=(const nsStringArray& other);
  
    PRInt32 Count(void) const {
      return nsVoidArray::Count();
    }
  
    void StringAt(PRInt32 aIndex, nsAString& aString) const;
    nsString* StringAt(PRInt32 aIndex) const;
    nsString* operator[](PRInt32 aIndex) const { return StringAt(aIndex); }
  
    PRInt32 IndexOf(const nsAString& aPossibleString) const;
  
    PRBool InsertStringAt(const nsAString& aString, PRInt32 aIndex);
  
    PRBool ReplaceStringAt(const nsAString& aString, PRInt32 aIndex);
  
    PRBool AppendString(const nsAString& aString) {
      return InsertStringAt(aString, Count());
    }
  
    PRBool RemoveString(const nsAString& aString);
    PRBool RemoveStringAt(PRInt32 aIndex);
    void   Clear(void);
  
    void Compact(void) {
      nsVoidArray::Compact();
    }
  
    void Sort(void);
    void Sort(nsStringArrayComparatorFunc aFunc, void* aData);
  
    PRBool EnumerateForwards(nsStringArrayEnumFunc aFunc, void* aData);
    PRBool EnumerateBackwards(nsStringArrayEnumFunc aFunc, void* aData);
  
  private:
    /// Copy constructors are not allowed
    nsStringArray(const nsStringArray& other);
  };
  
  
  class nsCString;
  
  typedef int (* nsCStringArrayComparatorFunc)
              (const nsCString* aElement1, const nsCString* aElement2, void* aData);
  
  typedef PRBool (*nsCStringArrayEnumFunc)(nsCString& aElement, void *aData);
  
  class NS_COM_GLUE nsCStringArray: private nsVoidArray
  {
  public:
    nsCStringArray(void);
    nsCStringArray(PRInt32 aCount); // Storage for aCount elements will be pre-allocated
    ~nsCStringArray(void);
  
    nsCStringArray& operator=(const nsCStringArray& other);
  
    // Parses a given string using the delimiter passed in. If the array
    // already has some elements, items parsed from string will be appended 
    // to array. For example, array.ParseString("a,b,c", ","); will add strings
    // "a", "b" and "c" to the array. Parsing process has the same tokenizing 
    // behavior as strtok().  
    PRBool ParseString(const char* string, const char* delimiter);
  
    PRInt32 Count(void) const {
      return nsVoidArray::Count();
    }
  
    void CStringAt(PRInt32 aIndex, nsACString& aCString) const;
    nsCString* CStringAt(PRInt32 aIndex) const;
    nsCString* operator[](PRInt32 aIndex) const { return CStringAt(aIndex); }
  
    PRInt32 IndexOf(const nsACString& aPossibleString) const;
  
  #ifdef MOZILLA_INTERNAL_API
    PRInt32 IndexOfIgnoreCase(const nsACString& aPossibleString) const;
  #endif
  
    PRBool InsertCStringAt(const nsACString& aCString, PRInt32 aIndex);
  
    PRBool ReplaceCStringAt(const nsACString& aCString, PRInt32 aIndex);
  
    PRBool AppendCString(const nsACString& aCString) {
      return InsertCStringAt(aCString, Count());
    }
  
    PRBool RemoveCString(const nsACString& aCString);
  
  #ifdef MOZILLA_INTERNAL_API
    PRBool RemoveCStringIgnoreCase(const nsACString& aCString);
  #endif
  
    PRBool RemoveCStringAt(PRInt32 aIndex);
    void   Clear(void);
  
    void Compact(void) {
      nsVoidArray::Compact();
    }
  
    void Sort(void);
  
  #ifdef MOZILLA_INTERNAL_API
    void SortIgnoreCase(void);
  #endif
  
    void Sort(nsCStringArrayComparatorFunc aFunc, void* aData);
  
    PRBool EnumerateForwards(nsCStringArrayEnumFunc aFunc, void* aData);
    PRBool EnumerateBackwards(nsCStringArrayEnumFunc aFunc, void* aData);
  
  private:
    /// Copy constructors are not allowed
    nsCStringArray(const nsCStringArray& other);
  };
  
  
  //===================================================================
  //  nsSmallVoidArray is not a general-purpose replacement for
  //  ns(Auto)VoidArray because there is (some) extra CPU overhead for arrays
  //  larger than 1 element, though not a lot.  It is appropriate for
  //  space-sensitive uses where sizes of 0 or 1 are moderately common or
  //  more, and where we're NOT storing arbitrary integers or arbitrary
  //  pointers.
  
  // NOTE: nsSmallVoidArray can ONLY be used for holding items that always
  // have the low bit as a 0 - i.e. element & 1 == 0.  This happens to be
  // true for allocated and object pointers for all the architectures we run
  // on, but conceivably there might be some architectures/compilers for
  // which it is NOT true.  We know this works for all existing architectures
  // because if it didn't then nsCheapVoidArray would have failed.  Also note
  // that we will ASSERT if this assumption is violated in DEBUG builds.
  
  // XXX we're really re-implementing the whole nsVoidArray interface here -
  // some form of abstract class would be useful
  
  // I disagree on the abstraction here.  If the point of this class is to be
  // as small as possible, and no one will ever derive from it, as I found
  // today, there should not be any virtualness to it to avoid the vtable
  // ptr overhead.
  
  class NS_COM_GLUE nsSmallVoidArray : private nsVoidArray
  {
  public:
    ~nsSmallVoidArray();
  
    nsSmallVoidArray& operator=(nsSmallVoidArray& other);
    void* operator[](PRInt32 aIndex) const { return ElementAt(aIndex); }
  
    PRInt32 GetArraySize() const;
  
    PRInt32 Count() const;
    void* FastElementAt(PRInt32 aIndex) const;
    // This both asserts and bounds-checks, because (1) we don't want
    // people to write bad code, but (2) we don't want to change it to
    // crashing for backwards compatibility.  See bug 96108.
    void* ElementAt(PRInt32 aIndex) const
    {
      NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::ElementAt: index out of range");
      return SafeElementAt(aIndex);
    }
    void* SafeElementAt(PRInt32 aIndex) const {
      // let compiler inline; it may be able to remove these checks
      if (PRUint32(aIndex) >= PRUint32(Count())) // handles aIndex < 0 too
      {
        return nsnull;
      }
      return FastElementAt(aIndex);
    }
    PRInt32 IndexOf(void* aPossibleElement) const;
    PRBool InsertElementAt(void* aElement, PRInt32 aIndex);
    PRBool InsertElementsAt(const nsVoidArray &other, PRInt32 aIndex);
    PRBool ReplaceElementAt(void* aElement, PRInt32 aIndex);
    PRBool MoveElement(PRInt32 aFrom, PRInt32 aTo);
    PRBool AppendElement(void* aElement);
    PRBool AppendElements(nsVoidArray& aElements) {
      return InsertElementsAt(aElements, Count());
    }
    PRBool RemoveElement(void* aElement);
    PRBool RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount);
    PRBool RemoveElementAt(PRInt32 aIndex);
  
    void Clear();
    PRBool SizeTo(PRInt32 aMin);
    void Compact();
    void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
  
    PRBool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
    PRBool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
  
  private:
  
    PRBool HasSingle() const
    {
      return !!(reinterpret_cast<PRWord>(mImpl) & 0x1);
    }
    void* GetSingle() const
    {
      NS_ASSERTION(HasSingle(), "wrong type");
      return reinterpret_cast<void*>
                             (reinterpret_cast<PRWord>(mImpl) & ~0x1);
    }
    void SetSingle(void *aChild)
    {
      NS_ASSERTION(HasSingle() || !mImpl, "overwriting array");
      mImpl = reinterpret_cast<Impl*>
                              (reinterpret_cast<PRWord>(aChild) | 0x1);
    }
    PRBool IsEmpty() const
    {
      // Note that this isn't the same as Count()==0
      return !mImpl;
    }
    const nsVoidArray* AsArray() const
    {
      NS_ASSERTION(!HasSingle(), "This is a single");
      return this;
    }
    nsVoidArray* AsArray()
    {
      NS_ASSERTION(!HasSingle(), "This is a single");
      return this;
    }
    PRBool EnsureArray();
  };
  
  #endif /* nsVoidArray_h___ */
  