diff -r 000000000000 -r 6474c204b198 xpcom/glue/nsVoidArray.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/xpcom/glue/nsVoidArray.h Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,261 @@ +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0)) -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ +#ifndef nsVoidArray_h___ +#define nsVoidArray_h___ + +//#define DEBUG_VOIDARRAY 1 + +#include "nsDebug.h" + +#include "mozilla/MemoryReporting.h" +#include + +// Comparator callback function for sorting array values. +typedef int (* nsVoidArrayComparatorFunc) + (const void* aElement1, const void* aElement2, void* aData); + +// Enumerator callback function. Return false to stop +typedef bool (* nsVoidArrayEnumFunc)(void* aElement, void *aData); +typedef bool (* nsVoidArrayEnumFuncConst)(const void* aElement, void *aData); + +// SizeOfExcludingThis callback function. +typedef size_t (* nsVoidArraySizeOfElementIncludingThisFunc)(const void* aElement, + mozilla::MallocSizeOf aMallocSizeOf, + void *aData); + +/// A basic zero-based array of void*'s that manages its own memory +class NS_COM_GLUE nsVoidArray { +public: + nsVoidArray(); + nsVoidArray(int32_t aCount); // initial count of aCount elements set to nullptr + ~nsVoidArray(); + + nsVoidArray& operator=(const nsVoidArray& other); + + inline int32_t Count() const { + return mImpl ? mImpl->mCount : 0; + } + // If the array grows, the newly created entries will all be null + bool SetCount(int32_t aNewCount); + // returns the max number that can be held without allocating + inline int32_t GetArraySize() const { + return mImpl ? mImpl->mSize : 0; + } + + void* FastElementAt(int32_t 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(int32_t aIndex) const + { + NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsVoidArray::ElementAt: index out of range"); + return SafeElementAt(aIndex); + } + + // bounds-checked version + void* SafeElementAt(int32_t aIndex) const + { + if (uint32_t(aIndex) >= uint32_t(Count())) // handles aIndex < 0 too + { + return nullptr; + } + // The bounds check ensures mImpl is non-null. + return mImpl->mArray[aIndex]; + } + + void* operator[](int32_t aIndex) const { return ElementAt(aIndex); } + + int32_t IndexOf(void* aPossibleElement) const; + + bool InsertElementAt(void* aElement, int32_t aIndex); + bool InsertElementsAt(const nsVoidArray &other, int32_t aIndex); + + bool ReplaceElementAt(void* aElement, int32_t aIndex); + + // useful for doing LRU arrays, sorting, etc + bool MoveElement(int32_t aFrom, int32_t aTo); + + bool AppendElement(void* aElement) { + return InsertElementAt(aElement, Count()); + } + + bool AppendElements(nsVoidArray& aElements) { + return InsertElementsAt(aElements, Count()); + } + + bool RemoveElement(void* aElement); + void RemoveElementsAt(int32_t aIndex, int32_t aCount); + void RemoveElementAt(int32_t aIndex) { return RemoveElementsAt(aIndex,1); } + + void Clear(); + + bool SizeTo(int32_t 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); + + bool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData); + bool EnumerateForwards(nsVoidArrayEnumFuncConst aFunc, void* aData) const; + bool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData); + + // Measures the size of the array's element storage, and if + // |aSizeOfElementIncludingThis| is non-nullptr, measures the size of things + // pointed to by elements. + size_t SizeOfExcludingThis( + nsVoidArraySizeOfElementIncludingThisFunc aSizeOfElementIncludingThis, + mozilla::MallocSizeOf aMallocSizeOf, void* aData = nullptr) const; + +protected: + bool GrowArrayBy(int32_t aGrowBy); + + struct Impl { + /** + * The actual array size. + */ + int32_t mSize; + + /** + * The number of elements in the array + */ + int32_t mCount; + + /** + * Array data, padded out to the actual size of the array. + */ + void* mArray[1]; + }; + + Impl* mImpl; +#if DEBUG_VOIDARRAY + int32_t mMaxCount; + int32_t mMaxSize; + bool mIsAuto; +#endif + + // bit twiddlers + void SetArray(Impl *newImpl, int32_t aSize, int32_t aCount); + +private: + /// Copy constructors are not allowed + nsVoidArray(const nsVoidArray& 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[](int32_t aIndex) const { return ElementAt(aIndex); } + + int32_t GetArraySize() const; + + int32_t Count() const; + void* FastElementAt(int32_t 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(int32_t aIndex) const + { + NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::ElementAt: index out of range"); + return SafeElementAt(aIndex); + } + void* SafeElementAt(int32_t aIndex) const { + // let compiler inline; it may be able to remove these checks + if (uint32_t(aIndex) >= uint32_t(Count())) // handles aIndex < 0 too + { + return nullptr; + } + return FastElementAt(aIndex); + } + int32_t IndexOf(void* aPossibleElement) const; + bool InsertElementAt(void* aElement, int32_t aIndex); + bool InsertElementsAt(const nsVoidArray &other, int32_t aIndex); + bool ReplaceElementAt(void* aElement, int32_t aIndex); + bool MoveElement(int32_t aFrom, int32_t aTo); + bool AppendElement(void* aElement); + bool AppendElements(nsVoidArray& aElements) { + return InsertElementsAt(aElements, Count()); + } + bool RemoveElement(void* aElement); + void RemoveElementsAt(int32_t aIndex, int32_t aCount); + void RemoveElementAt(int32_t aIndex); + + void Clear(); + bool SizeTo(int32_t aMin); + void Compact(); + void Sort(nsVoidArrayComparatorFunc aFunc, void* aData); + + bool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData); + bool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData); + +private: + + bool HasSingle() const + { + return !!(reinterpret_cast(mImpl) & 0x1); + } + void* GetSingle() const + { + NS_ASSERTION(HasSingle(), "wrong type"); + return reinterpret_cast + (reinterpret_cast(mImpl) & ~0x1); + } + void SetSingle(void *aChild) + { + NS_ASSERTION(HasSingle() || !mImpl, "overwriting array"); + mImpl = reinterpret_cast + (reinterpret_cast(aChild) | 0x1); + } + bool 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; + } + bool EnsureArray(); +}; + +#endif /* nsVoidArray_h___ */