michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0))  -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: #ifndef nsVoidArray_h___
michael@0: #define nsVoidArray_h___
michael@0: 
michael@0: //#define DEBUG_VOIDARRAY 1
michael@0: 
michael@0: #include "nsDebug.h"
michael@0: 
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include <stdint.h>
michael@0: 
michael@0: // Comparator callback function for sorting array values.
michael@0: typedef int (* nsVoidArrayComparatorFunc)
michael@0:             (const void* aElement1, const void* aElement2, void* aData);
michael@0: 
michael@0: // Enumerator callback function. Return false to stop
michael@0: typedef bool (* nsVoidArrayEnumFunc)(void* aElement, void *aData);
michael@0: typedef bool (* nsVoidArrayEnumFuncConst)(const void* aElement, void *aData);
michael@0: 
michael@0: // SizeOfExcludingThis callback function.
michael@0: typedef size_t (* nsVoidArraySizeOfElementIncludingThisFunc)(const void* aElement,
michael@0:                                                              mozilla::MallocSizeOf aMallocSizeOf,
michael@0:                                                              void *aData);
michael@0: 
michael@0: /// A basic zero-based array of void*'s that manages its own memory
michael@0: class NS_COM_GLUE nsVoidArray {
michael@0: public:
michael@0:   nsVoidArray();
michael@0:   nsVoidArray(int32_t aCount);  // initial count of aCount elements set to nullptr
michael@0:   ~nsVoidArray();
michael@0: 
michael@0:   nsVoidArray& operator=(const nsVoidArray& other);
michael@0: 
michael@0:   inline int32_t Count() const {
michael@0:     return mImpl ? mImpl->mCount : 0;
michael@0:   }
michael@0:   // If the array grows, the newly created entries will all be null
michael@0:   bool SetCount(int32_t aNewCount);
michael@0:   // returns the max number that can be held without allocating
michael@0:   inline int32_t GetArraySize() const {
michael@0:     return mImpl ? mImpl->mSize : 0;
michael@0:   }
michael@0: 
michael@0:   void* FastElementAt(int32_t aIndex) const
michael@0:   {
michael@0:     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsVoidArray::FastElementAt: index out of range");
michael@0:     return mImpl->mArray[aIndex];
michael@0:   }
michael@0: 
michael@0:   // This both asserts and bounds-checks, because (1) we don't want
michael@0:   // people to write bad code, but (2) we don't want to change it to
michael@0:   // crashing for backwards compatibility.  See bug 96108.
michael@0:   void* ElementAt(int32_t aIndex) const
michael@0:   {
michael@0:     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsVoidArray::ElementAt: index out of range");
michael@0:     return SafeElementAt(aIndex);
michael@0:   }
michael@0: 
michael@0:   // bounds-checked version
michael@0:   void* SafeElementAt(int32_t aIndex) const
michael@0:   {
michael@0:     if (uint32_t(aIndex) >= uint32_t(Count())) // handles aIndex < 0 too
michael@0:     {
michael@0:       return nullptr;
michael@0:     }
michael@0:     // The bounds check ensures mImpl is non-null.
michael@0:     return mImpl->mArray[aIndex];
michael@0:   }
michael@0: 
michael@0:   void* operator[](int32_t aIndex) const { return ElementAt(aIndex); }
michael@0: 
michael@0:   int32_t IndexOf(void* aPossibleElement) const;
michael@0: 
michael@0:   bool InsertElementAt(void* aElement, int32_t aIndex);
michael@0:   bool InsertElementsAt(const nsVoidArray &other, int32_t aIndex);
michael@0: 
michael@0:   bool ReplaceElementAt(void* aElement, int32_t aIndex);
michael@0: 
michael@0:   // useful for doing LRU arrays, sorting, etc
michael@0:   bool MoveElement(int32_t aFrom, int32_t aTo);
michael@0: 
michael@0:   bool AppendElement(void* aElement) {
michael@0:     return InsertElementAt(aElement, Count());
michael@0:   }
michael@0: 
michael@0:   bool AppendElements(nsVoidArray& aElements) {
michael@0:     return InsertElementsAt(aElements, Count());
michael@0:   }
michael@0: 
michael@0:   bool RemoveElement(void* aElement);
michael@0:   void RemoveElementsAt(int32_t aIndex, int32_t aCount);
michael@0:   void RemoveElementAt(int32_t aIndex) { return RemoveElementsAt(aIndex,1); }
michael@0: 
michael@0:   void   Clear();
michael@0: 
michael@0:   bool SizeTo(int32_t aMin);
michael@0:   // Subtly different - Compact() tries to be smart about whether we
michael@0:   // should reallocate the array; SizeTo() always reallocates.
michael@0:   void Compact();
michael@0: 
michael@0:   void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
michael@0: 
michael@0:   bool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
michael@0:   bool EnumerateForwards(nsVoidArrayEnumFuncConst aFunc, void* aData) const;
michael@0:   bool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
michael@0: 
michael@0:   // Measures the size of the array's element storage, and if
michael@0:   // |aSizeOfElementIncludingThis| is non-nullptr, measures the size of things
michael@0:   // pointed to by elements.
michael@0:   size_t SizeOfExcludingThis(
michael@0:            nsVoidArraySizeOfElementIncludingThisFunc aSizeOfElementIncludingThis,
michael@0:            mozilla::MallocSizeOf aMallocSizeOf, void* aData = nullptr) const;
michael@0: 
michael@0: protected:
michael@0:   bool GrowArrayBy(int32_t aGrowBy);
michael@0: 
michael@0:   struct Impl {
michael@0:     /**
michael@0:      * The actual array size.
michael@0:      */
michael@0:     int32_t mSize;
michael@0: 
michael@0:     /**
michael@0:      * The number of elements in the array
michael@0:      */
michael@0:     int32_t mCount;
michael@0: 
michael@0:     /**
michael@0:      * Array data, padded out to the actual size of the array.
michael@0:      */
michael@0:     void*   mArray[1];
michael@0:   };
michael@0: 
michael@0:   Impl* mImpl;
michael@0: #if DEBUG_VOIDARRAY
michael@0:   int32_t mMaxCount;
michael@0:   int32_t mMaxSize;
michael@0:   bool    mIsAuto;
michael@0: #endif
michael@0: 
michael@0:   // bit twiddlers
michael@0:   void SetArray(Impl *newImpl, int32_t aSize, int32_t aCount);
michael@0: 
michael@0: private:
michael@0:   /// Copy constructors are not allowed
michael@0:   nsVoidArray(const nsVoidArray& other);
michael@0: };
michael@0: 
michael@0: //===================================================================
michael@0: //  nsSmallVoidArray is not a general-purpose replacement for
michael@0: //  ns(Auto)VoidArray because there is (some) extra CPU overhead for arrays
michael@0: //  larger than 1 element, though not a lot.  It is appropriate for
michael@0: //  space-sensitive uses where sizes of 0 or 1 are moderately common or
michael@0: //  more, and where we're NOT storing arbitrary integers or arbitrary
michael@0: //  pointers.
michael@0: 
michael@0: // NOTE: nsSmallVoidArray can ONLY be used for holding items that always
michael@0: // have the low bit as a 0 - i.e. element & 1 == 0.  This happens to be
michael@0: // true for allocated and object pointers for all the architectures we run
michael@0: // on, but conceivably there might be some architectures/compilers for
michael@0: // which it is NOT true.  We know this works for all existing architectures
michael@0: // because if it didn't then nsCheapVoidArray would have failed.  Also note
michael@0: // that we will ASSERT if this assumption is violated in DEBUG builds.
michael@0: 
michael@0: // XXX we're really re-implementing the whole nsVoidArray interface here -
michael@0: // some form of abstract class would be useful
michael@0: 
michael@0: // I disagree on the abstraction here.  If the point of this class is to be
michael@0: // as small as possible, and no one will ever derive from it, as I found
michael@0: // today, there should not be any virtualness to it to avoid the vtable
michael@0: // ptr overhead.
michael@0: 
michael@0: class NS_COM_GLUE nsSmallVoidArray : private nsVoidArray
michael@0: {
michael@0: public:
michael@0:   ~nsSmallVoidArray();
michael@0: 
michael@0:   nsSmallVoidArray& operator=(nsSmallVoidArray& other);
michael@0:   void* operator[](int32_t aIndex) const { return ElementAt(aIndex); }
michael@0: 
michael@0:   int32_t GetArraySize() const;
michael@0: 
michael@0:   int32_t Count() const;
michael@0:   void* FastElementAt(int32_t aIndex) const;
michael@0:   // This both asserts and bounds-checks, because (1) we don't want
michael@0:   // people to write bad code, but (2) we don't want to change it to
michael@0:   // crashing for backwards compatibility.  See bug 96108.
michael@0:   void* ElementAt(int32_t aIndex) const
michael@0:   {
michael@0:     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::ElementAt: index out of range");
michael@0:     return SafeElementAt(aIndex);
michael@0:   }
michael@0:   void* SafeElementAt(int32_t aIndex) const {
michael@0:     // let compiler inline; it may be able to remove these checks
michael@0:     if (uint32_t(aIndex) >= uint32_t(Count())) // handles aIndex < 0 too
michael@0:     {
michael@0:       return nullptr;
michael@0:     }
michael@0:     return FastElementAt(aIndex);
michael@0:   }
michael@0:   int32_t IndexOf(void* aPossibleElement) const;
michael@0:   bool InsertElementAt(void* aElement, int32_t aIndex);
michael@0:   bool InsertElementsAt(const nsVoidArray &other, int32_t aIndex);
michael@0:   bool ReplaceElementAt(void* aElement, int32_t aIndex);
michael@0:   bool MoveElement(int32_t aFrom, int32_t aTo);
michael@0:   bool AppendElement(void* aElement);
michael@0:   bool AppendElements(nsVoidArray& aElements) {
michael@0:     return InsertElementsAt(aElements, Count());
michael@0:   }
michael@0:   bool RemoveElement(void* aElement);
michael@0:   void RemoveElementsAt(int32_t aIndex, int32_t aCount);
michael@0:   void RemoveElementAt(int32_t aIndex);
michael@0: 
michael@0:   void Clear();
michael@0:   bool SizeTo(int32_t aMin);
michael@0:   void Compact();
michael@0:   void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
michael@0: 
michael@0:   bool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
michael@0:   bool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
michael@0: 
michael@0: private:
michael@0: 
michael@0:   bool HasSingle() const
michael@0:   {
michael@0:     return !!(reinterpret_cast<intptr_t>(mImpl) & 0x1);
michael@0:   }
michael@0:   void* GetSingle() const
michael@0:   {
michael@0:     NS_ASSERTION(HasSingle(), "wrong type");
michael@0:     return reinterpret_cast<void*>
michael@0:                            (reinterpret_cast<intptr_t>(mImpl) & ~0x1);
michael@0:   }
michael@0:   void SetSingle(void *aChild)
michael@0:   {
michael@0:     NS_ASSERTION(HasSingle() || !mImpl, "overwriting array");
michael@0:     mImpl = reinterpret_cast<Impl*>
michael@0:                             (reinterpret_cast<intptr_t>(aChild) | 0x1);
michael@0:   }
michael@0:   bool IsEmpty() const
michael@0:   {
michael@0:     // Note that this isn't the same as Count()==0
michael@0:     return !mImpl;
michael@0:   }
michael@0:   const nsVoidArray* AsArray() const
michael@0:   {
michael@0:     NS_ASSERTION(!HasSingle(), "This is a single");
michael@0:     return this;
michael@0:   }
michael@0:   nsVoidArray* AsArray()
michael@0:   {
michael@0:     NS_ASSERTION(!HasSingle(), "This is a single");
michael@0:     return this;
michael@0:   }
michael@0:   bool EnsureArray();
michael@0: };
michael@0: 
michael@0: #endif /* nsVoidArray_h___ */