1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/nsTObserverArray.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,418 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
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 +
1.9 +#ifndef nsTObserverArray_h___
1.10 +#define nsTObserverArray_h___
1.11 +
1.12 +#include "mozilla/MemoryReporting.h"
1.13 +#include "nsTArray.h"
1.14 +#include "nsCycleCollectionNoteChild.h"
1.15 +
1.16 +/**
1.17 + * An array of observers. Like a normal array, but supports iterators that are
1.18 + * stable even if the array is modified during iteration.
1.19 + * The template parameter T is the observer type the array will hold;
1.20 + * N is the number of built-in storage slots that come with the array.
1.21 + * NOTE: You probably want to use nsTObserverArray, unless you specifically
1.22 + * want built-in storage. See below.
1.23 + * @see nsTObserverArray, nsTArray
1.24 + */
1.25 +
1.26 +class NS_COM_GLUE nsTObserverArray_base {
1.27 + public:
1.28 + typedef uint32_t index_type;
1.29 + typedef uint32_t size_type;
1.30 + typedef int32_t diff_type;
1.31 +
1.32 + protected:
1.33 + class Iterator_base {
1.34 + protected:
1.35 + friend class nsTObserverArray_base;
1.36 +
1.37 + Iterator_base(index_type aPosition, Iterator_base* aNext)
1.38 + : mPosition(aPosition),
1.39 + mNext(aNext) {
1.40 + }
1.41 +
1.42 + // The current position of the iterator. Its exact meaning differs
1.43 + // depending on iterator. See nsTObserverArray<T>::ForwardIterator.
1.44 + index_type mPosition;
1.45 +
1.46 + // The next iterator currently iterating the same array
1.47 + Iterator_base* mNext;
1.48 + };
1.49 +
1.50 + nsTObserverArray_base()
1.51 + : mIterators(nullptr) {
1.52 + }
1.53 +
1.54 + ~nsTObserverArray_base() {
1.55 + NS_ASSERTION(mIterators == nullptr, "iterators outlasting array");
1.56 + }
1.57 +
1.58 + /**
1.59 + * Adjusts iterators after an element has been inserted or removed
1.60 + * from the array.
1.61 + * @param modPos Position where elements were added or removed.
1.62 + * @param adjustment -1 if an element was removed, 1 if an element was
1.63 + * added.
1.64 + */
1.65 + void AdjustIterators(index_type aModPos, diff_type aAdjustment);
1.66 +
1.67 + /**
1.68 + * Clears iterators when the array is destroyed.
1.69 + */
1.70 + void ClearIterators();
1.71 +
1.72 + mutable Iterator_base* mIterators;
1.73 +};
1.74 +
1.75 +template<class T, uint32_t N>
1.76 +class nsAutoTObserverArray : protected nsTObserverArray_base {
1.77 + public:
1.78 + typedef T elem_type;
1.79 + typedef nsTArray<T> array_type;
1.80 +
1.81 + nsAutoTObserverArray() {
1.82 + }
1.83 +
1.84 + //
1.85 + // Accessor methods
1.86 + //
1.87 +
1.88 + // @return The number of elements in the array.
1.89 + size_type Length() const {
1.90 + return mArray.Length();
1.91 + }
1.92 +
1.93 + // @return True if the array is empty or false otherwise.
1.94 + bool IsEmpty() const {
1.95 + return mArray.IsEmpty();
1.96 + }
1.97 +
1.98 + // This method provides direct access to the i'th element of the array.
1.99 + // The given index must be within the array bounds. If the underlying array
1.100 + // may change during iteration, use an iterator instead of this function.
1.101 + // @param i The index of an element in the array.
1.102 + // @return A reference to the i'th element of the array.
1.103 + elem_type& ElementAt(index_type i) {
1.104 + return mArray.ElementAt(i);
1.105 + }
1.106 +
1.107 + // Same as above, but readonly.
1.108 + const elem_type& ElementAt(index_type i) const {
1.109 + return mArray.ElementAt(i);
1.110 + }
1.111 +
1.112 + // This method provides direct access to the i'th element of the array in
1.113 + // a bounds safe manner. If the requested index is out of bounds the
1.114 + // provided default value is returned.
1.115 + // @param i The index of an element in the array.
1.116 + // @param def The value to return if the index is out of bounds.
1.117 + elem_type& SafeElementAt(index_type i, elem_type& def) {
1.118 + return mArray.SafeElementAt(i, def);
1.119 + }
1.120 +
1.121 + // Same as above, but readonly.
1.122 + const elem_type& SafeElementAt(index_type i, const elem_type& def) const {
1.123 + return mArray.SafeElementAt(i, def);
1.124 + }
1.125 +
1.126 + // No operator[] is provided because the point of this class is to support
1.127 + // allow modifying the array during iteration, and ElementAt() is not safe
1.128 + // in those conditions.
1.129 +
1.130 + //
1.131 + // Search methods
1.132 + //
1.133 +
1.134 + // This method searches, starting from the beginning of the array,
1.135 + // for the first element in this array that is equal to the given element.
1.136 + // 'operator==' must be defined for elem_type.
1.137 + // @param item The item to search for.
1.138 + // @return true if the element was found.
1.139 + template<class Item>
1.140 + bool Contains(const Item& item) const {
1.141 + return IndexOf(item) != array_type::NoIndex;
1.142 + }
1.143 +
1.144 + // This method searches for the offset of the first element in this
1.145 + // array that is equal to the given element.
1.146 + // 'operator==' must be defined for elem_type.
1.147 + // @param item The item to search for.
1.148 + // @param start The index to start from.
1.149 + // @return The index of the found element or NoIndex if not found.
1.150 + template<class Item>
1.151 + index_type IndexOf(const Item& item, index_type start = 0) const {
1.152 + return mArray.IndexOf(item, start);
1.153 + }
1.154 +
1.155 + //
1.156 + // Mutation methods
1.157 + //
1.158 +
1.159 + // Insert a given element at the given index.
1.160 + // @param index The index at which to insert item.
1.161 + // @param item The item to insert,
1.162 + // @return A pointer to the newly inserted element, or a null on DOM
1.163 + template<class Item>
1.164 + elem_type *InsertElementAt(index_type aIndex, const Item& aItem) {
1.165 + elem_type* item = mArray.InsertElementAt(aIndex, aItem);
1.166 + AdjustIterators(aIndex, 1);
1.167 + return item;
1.168 + }
1.169 +
1.170 + // Same as above but without copy constructing.
1.171 + // This is useful to avoid temporaries.
1.172 + elem_type* InsertElementAt(index_type aIndex) {
1.173 + elem_type* item = mArray.InsertElementAt(aIndex);
1.174 + AdjustIterators(aIndex, 1);
1.175 + return item;
1.176 + }
1.177 +
1.178 + // Prepend an element to the array unless it already exists in the array.
1.179 + // 'operator==' must be defined for elem_type.
1.180 + // @param item The item to prepend.
1.181 + // @return true if the element was found, or inserted successfully.
1.182 + template<class Item>
1.183 + bool PrependElementUnlessExists(const Item& item) {
1.184 + if (Contains(item)) {
1.185 + return true;
1.186 + }
1.187 +
1.188 + bool inserted = mArray.InsertElementAt(0, item) != nullptr;
1.189 + AdjustIterators(0, 1);
1.190 + return inserted;
1.191 + }
1.192 +
1.193 + // Append an element to the array.
1.194 + // @param item The item to append.
1.195 + // @return A pointer to the newly appended element, or null on OOM.
1.196 + template<class Item>
1.197 + elem_type* AppendElement(const Item& item) {
1.198 + return mArray.AppendElement(item);
1.199 + }
1.200 +
1.201 + // Same as above, but without copy-constructing. This is useful to avoid
1.202 + // temporaries.
1.203 + elem_type* AppendElement() {
1.204 + return mArray.AppendElement();
1.205 + }
1.206 +
1.207 + // Append an element to the array unless it already exists in the array.
1.208 + // 'operator==' must be defined for elem_type.
1.209 + // @param item The item to append.
1.210 + // @return true if the element was found, or inserted successfully.
1.211 + template<class Item>
1.212 + bool AppendElementUnlessExists(const Item& item) {
1.213 + return Contains(item) || AppendElement(item) != nullptr;
1.214 + }
1.215 +
1.216 + // Remove an element from the array.
1.217 + // @param index The index of the item to remove.
1.218 + void RemoveElementAt(index_type index) {
1.219 + NS_ASSERTION(index < mArray.Length(), "invalid index");
1.220 + mArray.RemoveElementAt(index);
1.221 + AdjustIterators(index, -1);
1.222 + }
1.223 +
1.224 + // This helper function combines IndexOf with RemoveElementAt to "search
1.225 + // and destroy" the first element that is equal to the given element.
1.226 + // 'operator==' must be defined for elem_type.
1.227 + // @param item The item to search for.
1.228 + // @return true if the element was found and removed.
1.229 + template<class Item>
1.230 + bool RemoveElement(const Item& item) {
1.231 + index_type index = mArray.IndexOf(item, 0);
1.232 + if (index == array_type::NoIndex)
1.233 + return false;
1.234 +
1.235 + mArray.RemoveElementAt(index);
1.236 + AdjustIterators(index, -1);
1.237 + return true;
1.238 + }
1.239 +
1.240 + // Removes all observers and collapses all iterators to the beginning of
1.241 + // the array. The result is that forward iterators will see all elements
1.242 + // in the array.
1.243 + void Clear() {
1.244 + mArray.Clear();
1.245 + ClearIterators();
1.246 + }
1.247 +
1.248 + // Returns the number of bytes on the heap taken up by this object, not
1.249 + // including sizeof(*this).
1.250 + size_t SizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
1.251 + return mArray.SizeOfExcludingThis(mallocSizeOf);
1.252 + }
1.253 +
1.254 + //
1.255 + // Iterators
1.256 + //
1.257 +
1.258 + // Base class for iterators. Do not use this directly.
1.259 + class Iterator : public Iterator_base {
1.260 + protected:
1.261 + friend class nsAutoTObserverArray;
1.262 + typedef nsAutoTObserverArray<T, N> array_type;
1.263 +
1.264 + Iterator(index_type aPosition, const array_type& aArray)
1.265 + : Iterator_base(aPosition, aArray.mIterators),
1.266 + mArray(const_cast<array_type&>(aArray)) {
1.267 + aArray.mIterators = this;
1.268 + }
1.269 +
1.270 + ~Iterator() {
1.271 + NS_ASSERTION(mArray.mIterators == this,
1.272 + "Iterators must currently be destroyed in opposite order "
1.273 + "from the construction order. It is suggested that you "
1.274 + "simply put them on the stack");
1.275 + mArray.mIterators = mNext;
1.276 + }
1.277 +
1.278 + // The array we're iterating
1.279 + array_type& mArray;
1.280 + };
1.281 +
1.282 + // Iterates the array forward from beginning to end. mPosition points
1.283 + // to the element that will be returned on next call to GetNext.
1.284 + // Elements:
1.285 + // - prepended to the array during iteration *will not* be traversed
1.286 + // - appended during iteration *will* be traversed
1.287 + // - removed during iteration *will not* be traversed.
1.288 + // @see EndLimitedIterator
1.289 + class ForwardIterator : protected Iterator {
1.290 + public:
1.291 + typedef nsAutoTObserverArray<T, N> array_type;
1.292 + typedef Iterator base_type;
1.293 +
1.294 + ForwardIterator(const array_type& aArray)
1.295 + : Iterator(0, aArray) {
1.296 + }
1.297 +
1.298 + ForwardIterator(const array_type& aArray, index_type aPos)
1.299 + : Iterator(aPos, aArray) {
1.300 + }
1.301 +
1.302 + bool operator <(const ForwardIterator& aOther) const {
1.303 + NS_ASSERTION(&this->mArray == &aOther.mArray,
1.304 + "not iterating the same array");
1.305 + return base_type::mPosition < aOther.mPosition;
1.306 + }
1.307 +
1.308 + // Returns true if there are more elements to iterate.
1.309 + // This must precede a call to GetNext(). If false is
1.310 + // returned, GetNext() must not be called.
1.311 + bool HasMore() const {
1.312 + return base_type::mPosition < base_type::mArray.Length();
1.313 + }
1.314 +
1.315 + // Returns the next element and steps one step. This must
1.316 + // be preceded by a call to HasMore().
1.317 + // @return The next observer.
1.318 + elem_type& GetNext() {
1.319 + NS_ASSERTION(HasMore(), "iterating beyond end of array");
1.320 + return base_type::mArray.ElementAt(base_type::mPosition++);
1.321 + }
1.322 + };
1.323 +
1.324 + // EndLimitedIterator works like ForwardIterator, but will not iterate new
1.325 + // observers appended to the array after the iterator was created.
1.326 + class EndLimitedIterator : protected ForwardIterator {
1.327 + public:
1.328 + typedef nsAutoTObserverArray<T, N> array_type;
1.329 + typedef Iterator base_type;
1.330 +
1.331 + EndLimitedIterator(const array_type& aArray)
1.332 + : ForwardIterator(aArray),
1.333 + mEnd(aArray, aArray.Length()) {
1.334 + }
1.335 +
1.336 + // Returns true if there are more elements to iterate.
1.337 + // This must precede a call to GetNext(). If false is
1.338 + // returned, GetNext() must not be called.
1.339 + bool HasMore() const {
1.340 + return *this < mEnd;
1.341 + }
1.342 +
1.343 + // Returns the next element and steps one step. This must
1.344 + // be preceded by a call to HasMore().
1.345 + // @return The next observer.
1.346 + elem_type& GetNext() {
1.347 + NS_ASSERTION(HasMore(), "iterating beyond end of array");
1.348 + return base_type::mArray.ElementAt(base_type::mPosition++);
1.349 + }
1.350 +
1.351 + private:
1.352 + ForwardIterator mEnd;
1.353 + };
1.354 +
1.355 + protected:
1.356 + nsAutoTArray<T, N> mArray;
1.357 +};
1.358 +
1.359 +template<class T>
1.360 +class nsTObserverArray : public nsAutoTObserverArray<T, 0> {
1.361 + public:
1.362 + typedef nsAutoTObserverArray<T, 0> base_type;
1.363 + typedef nsTObserverArray_base::size_type size_type;
1.364 +
1.365 + //
1.366 + // Initialization methods
1.367 + //
1.368 +
1.369 + nsTObserverArray() {}
1.370 +
1.371 + // Initialize this array and pre-allocate some number of elements.
1.372 + explicit nsTObserverArray(size_type capacity) {
1.373 + base_type::mArray.SetCapacity(capacity);
1.374 + }
1.375 +};
1.376 +
1.377 +template <typename T, uint32_t N>
1.378 +inline void
1.379 +ImplCycleCollectionUnlink(nsAutoTObserverArray<T, N>& aField)
1.380 +{
1.381 + aField.Clear();
1.382 +}
1.383 +
1.384 +template <typename T, uint32_t N>
1.385 +inline void
1.386 +ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
1.387 + nsAutoTObserverArray<T, N>& aField,
1.388 + const char* aName,
1.389 + uint32_t aFlags = 0)
1.390 +{
1.391 + aFlags |= CycleCollectionEdgeNameArrayFlag;
1.392 + uint32_t length = aField.Length();
1.393 + for (uint32_t i = 0; i < length; ++i) {
1.394 + ImplCycleCollectionTraverse(aCallback, aField.ElementAt(i), aName, aFlags);
1.395 + }
1.396 +}
1.397 +
1.398 +// XXXbz I wish I didn't have to pass in the observer type, but I
1.399 +// don't see a way to get it out of array_.
1.400 +// Note that this macro only works if the array holds pointers to XPCOM objects.
1.401 +#define NS_OBSERVER_ARRAY_NOTIFY_XPCOM_OBSERVERS(array_, obstype_, func_, params_) \
1.402 + PR_BEGIN_MACRO \
1.403 + nsTObserverArray<obstype_ *>::ForwardIterator iter_(array_); \
1.404 + nsRefPtr<obstype_> obs_; \
1.405 + while (iter_.HasMore()) { \
1.406 + obs_ = iter_.GetNext(); \
1.407 + obs_ -> func_ params_ ; \
1.408 + } \
1.409 + PR_END_MACRO
1.410 +
1.411 +// Note that this macro only works if the array holds pointers to XPCOM objects.
1.412 +#define NS_OBSERVER_ARRAY_NOTIFY_OBSERVERS(array_, obstype_, func_, params_) \
1.413 + PR_BEGIN_MACRO \
1.414 + nsTObserverArray<obstype_ *>::ForwardIterator iter_(array_); \
1.415 + obstype_* obs_; \
1.416 + while (iter_.HasMore()) { \
1.417 + obs_ = iter_.GetNext(); \
1.418 + obs_ -> func_ params_ ; \
1.419 + } \
1.420 + PR_END_MACRO
1.421 +#endif // nsTObserverArray_h___
