1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/nsVoidArray.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,261 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0)) -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +#ifndef nsVoidArray_h___
1.9 +#define nsVoidArray_h___
1.10 +
1.11 +//#define DEBUG_VOIDARRAY 1
1.12 +
1.13 +#include "nsDebug.h"
1.14 +
1.15 +#include "mozilla/MemoryReporting.h"
1.16 +#include <stdint.h>
1.17 +
1.18 +// Comparator callback function for sorting array values.
1.19 +typedef int (* nsVoidArrayComparatorFunc)
1.20 + (const void* aElement1, const void* aElement2, void* aData);
1.21 +
1.22 +// Enumerator callback function. Return false to stop
1.23 +typedef bool (* nsVoidArrayEnumFunc)(void* aElement, void *aData);
1.24 +typedef bool (* nsVoidArrayEnumFuncConst)(const void* aElement, void *aData);
1.25 +
1.26 +// SizeOfExcludingThis callback function.
1.27 +typedef size_t (* nsVoidArraySizeOfElementIncludingThisFunc)(const void* aElement,
1.28 + mozilla::MallocSizeOf aMallocSizeOf,
1.29 + void *aData);
1.30 +
1.31 +/// A basic zero-based array of void*'s that manages its own memory
1.32 +class NS_COM_GLUE nsVoidArray {
1.33 +public:
1.34 + nsVoidArray();
1.35 + nsVoidArray(int32_t aCount); // initial count of aCount elements set to nullptr
1.36 + ~nsVoidArray();
1.37 +
1.38 + nsVoidArray& operator=(const nsVoidArray& other);
1.39 +
1.40 + inline int32_t Count() const {
1.41 + return mImpl ? mImpl->mCount : 0;
1.42 + }
1.43 + // If the array grows, the newly created entries will all be null
1.44 + bool SetCount(int32_t aNewCount);
1.45 + // returns the max number that can be held without allocating
1.46 + inline int32_t GetArraySize() const {
1.47 + return mImpl ? mImpl->mSize : 0;
1.48 + }
1.49 +
1.50 + void* FastElementAt(int32_t aIndex) const
1.51 + {
1.52 + NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsVoidArray::FastElementAt: index out of range");
1.53 + return mImpl->mArray[aIndex];
1.54 + }
1.55 +
1.56 + // This both asserts and bounds-checks, because (1) we don't want
1.57 + // people to write bad code, but (2) we don't want to change it to
1.58 + // crashing for backwards compatibility. See bug 96108.
1.59 + void* ElementAt(int32_t aIndex) const
1.60 + {
1.61 + NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsVoidArray::ElementAt: index out of range");
1.62 + return SafeElementAt(aIndex);
1.63 + }
1.64 +
1.65 + // bounds-checked version
1.66 + void* SafeElementAt(int32_t aIndex) const
1.67 + {
1.68 + if (uint32_t(aIndex) >= uint32_t(Count())) // handles aIndex < 0 too
1.69 + {
1.70 + return nullptr;
1.71 + }
1.72 + // The bounds check ensures mImpl is non-null.
1.73 + return mImpl->mArray[aIndex];
1.74 + }
1.75 +
1.76 + void* operator[](int32_t aIndex) const { return ElementAt(aIndex); }
1.77 +
1.78 + int32_t IndexOf(void* aPossibleElement) const;
1.79 +
1.80 + bool InsertElementAt(void* aElement, int32_t aIndex);
1.81 + bool InsertElementsAt(const nsVoidArray &other, int32_t aIndex);
1.82 +
1.83 + bool ReplaceElementAt(void* aElement, int32_t aIndex);
1.84 +
1.85 + // useful for doing LRU arrays, sorting, etc
1.86 + bool MoveElement(int32_t aFrom, int32_t aTo);
1.87 +
1.88 + bool AppendElement(void* aElement) {
1.89 + return InsertElementAt(aElement, Count());
1.90 + }
1.91 +
1.92 + bool AppendElements(nsVoidArray& aElements) {
1.93 + return InsertElementsAt(aElements, Count());
1.94 + }
1.95 +
1.96 + bool RemoveElement(void* aElement);
1.97 + void RemoveElementsAt(int32_t aIndex, int32_t aCount);
1.98 + void RemoveElementAt(int32_t aIndex) { return RemoveElementsAt(aIndex,1); }
1.99 +
1.100 + void Clear();
1.101 +
1.102 + bool SizeTo(int32_t aMin);
1.103 + // Subtly different - Compact() tries to be smart about whether we
1.104 + // should reallocate the array; SizeTo() always reallocates.
1.105 + void Compact();
1.106 +
1.107 + void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
1.108 +
1.109 + bool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
1.110 + bool EnumerateForwards(nsVoidArrayEnumFuncConst aFunc, void* aData) const;
1.111 + bool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
1.112 +
1.113 + // Measures the size of the array's element storage, and if
1.114 + // |aSizeOfElementIncludingThis| is non-nullptr, measures the size of things
1.115 + // pointed to by elements.
1.116 + size_t SizeOfExcludingThis(
1.117 + nsVoidArraySizeOfElementIncludingThisFunc aSizeOfElementIncludingThis,
1.118 + mozilla::MallocSizeOf aMallocSizeOf, void* aData = nullptr) const;
1.119 +
1.120 +protected:
1.121 + bool GrowArrayBy(int32_t aGrowBy);
1.122 +
1.123 + struct Impl {
1.124 + /**
1.125 + * The actual array size.
1.126 + */
1.127 + int32_t mSize;
1.128 +
1.129 + /**
1.130 + * The number of elements in the array
1.131 + */
1.132 + int32_t mCount;
1.133 +
1.134 + /**
1.135 + * Array data, padded out to the actual size of the array.
1.136 + */
1.137 + void* mArray[1];
1.138 + };
1.139 +
1.140 + Impl* mImpl;
1.141 +#if DEBUG_VOIDARRAY
1.142 + int32_t mMaxCount;
1.143 + int32_t mMaxSize;
1.144 + bool mIsAuto;
1.145 +#endif
1.146 +
1.147 + // bit twiddlers
1.148 + void SetArray(Impl *newImpl, int32_t aSize, int32_t aCount);
1.149 +
1.150 +private:
1.151 + /// Copy constructors are not allowed
1.152 + nsVoidArray(const nsVoidArray& other);
1.153 +};
1.154 +
1.155 +//===================================================================
1.156 +// nsSmallVoidArray is not a general-purpose replacement for
1.157 +// ns(Auto)VoidArray because there is (some) extra CPU overhead for arrays
1.158 +// larger than 1 element, though not a lot. It is appropriate for
1.159 +// space-sensitive uses where sizes of 0 or 1 are moderately common or
1.160 +// more, and where we're NOT storing arbitrary integers or arbitrary
1.161 +// pointers.
1.162 +
1.163 +// NOTE: nsSmallVoidArray can ONLY be used for holding items that always
1.164 +// have the low bit as a 0 - i.e. element & 1 == 0. This happens to be
1.165 +// true for allocated and object pointers for all the architectures we run
1.166 +// on, but conceivably there might be some architectures/compilers for
1.167 +// which it is NOT true. We know this works for all existing architectures
1.168 +// because if it didn't then nsCheapVoidArray would have failed. Also note
1.169 +// that we will ASSERT if this assumption is violated in DEBUG builds.
1.170 +
1.171 +// XXX we're really re-implementing the whole nsVoidArray interface here -
1.172 +// some form of abstract class would be useful
1.173 +
1.174 +// I disagree on the abstraction here. If the point of this class is to be
1.175 +// as small as possible, and no one will ever derive from it, as I found
1.176 +// today, there should not be any virtualness to it to avoid the vtable
1.177 +// ptr overhead.
1.178 +
1.179 +class NS_COM_GLUE nsSmallVoidArray : private nsVoidArray
1.180 +{
1.181 +public:
1.182 + ~nsSmallVoidArray();
1.183 +
1.184 + nsSmallVoidArray& operator=(nsSmallVoidArray& other);
1.185 + void* operator[](int32_t aIndex) const { return ElementAt(aIndex); }
1.186 +
1.187 + int32_t GetArraySize() const;
1.188 +
1.189 + int32_t Count() const;
1.190 + void* FastElementAt(int32_t aIndex) const;
1.191 + // This both asserts and bounds-checks, because (1) we don't want
1.192 + // people to write bad code, but (2) we don't want to change it to
1.193 + // crashing for backwards compatibility. See bug 96108.
1.194 + void* ElementAt(int32_t aIndex) const
1.195 + {
1.196 + NS_ASSERTION(0 <= aIndex && aIndex < Count(), "nsSmallVoidArray::ElementAt: index out of range");
1.197 + return SafeElementAt(aIndex);
1.198 + }
1.199 + void* SafeElementAt(int32_t aIndex) const {
1.200 + // let compiler inline; it may be able to remove these checks
1.201 + if (uint32_t(aIndex) >= uint32_t(Count())) // handles aIndex < 0 too
1.202 + {
1.203 + return nullptr;
1.204 + }
1.205 + return FastElementAt(aIndex);
1.206 + }
1.207 + int32_t IndexOf(void* aPossibleElement) const;
1.208 + bool InsertElementAt(void* aElement, int32_t aIndex);
1.209 + bool InsertElementsAt(const nsVoidArray &other, int32_t aIndex);
1.210 + bool ReplaceElementAt(void* aElement, int32_t aIndex);
1.211 + bool MoveElement(int32_t aFrom, int32_t aTo);
1.212 + bool AppendElement(void* aElement);
1.213 + bool AppendElements(nsVoidArray& aElements) {
1.214 + return InsertElementsAt(aElements, Count());
1.215 + }
1.216 + bool RemoveElement(void* aElement);
1.217 + void RemoveElementsAt(int32_t aIndex, int32_t aCount);
1.218 + void RemoveElementAt(int32_t aIndex);
1.219 +
1.220 + void Clear();
1.221 + bool SizeTo(int32_t aMin);
1.222 + void Compact();
1.223 + void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
1.224 +
1.225 + bool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
1.226 + bool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
1.227 +
1.228 +private:
1.229 +
1.230 + bool HasSingle() const
1.231 + {
1.232 + return !!(reinterpret_cast<intptr_t>(mImpl) & 0x1);
1.233 + }
1.234 + void* GetSingle() const
1.235 + {
1.236 + NS_ASSERTION(HasSingle(), "wrong type");
1.237 + return reinterpret_cast<void*>
1.238 + (reinterpret_cast<intptr_t>(mImpl) & ~0x1);
1.239 + }
1.240 + void SetSingle(void *aChild)
1.241 + {
1.242 + NS_ASSERTION(HasSingle() || !mImpl, "overwriting array");
1.243 + mImpl = reinterpret_cast<Impl*>
1.244 + (reinterpret_cast<intptr_t>(aChild) | 0x1);
1.245 + }
1.246 + bool IsEmpty() const
1.247 + {
1.248 + // Note that this isn't the same as Count()==0
1.249 + return !mImpl;
1.250 + }
1.251 + const nsVoidArray* AsArray() const
1.252 + {
1.253 + NS_ASSERTION(!HasSingle(), "This is a single");
1.254 + return this;
1.255 + }
1.256 + nsVoidArray* AsArray()
1.257 + {
1.258 + NS_ASSERTION(!HasSingle(), "This is a single");
1.259 + return this;
1.260 + }
1.261 + bool EnsureArray();
1.262 +};
1.263 +
1.264 +#endif /* nsVoidArray_h___ */
