diff options
Diffstat (limited to 'xpcom/glue/nsTObserverArray.h')
| -rw-r--r-- | xpcom/glue/nsTObserverArray.h | 520 |
1 files changed, 520 insertions, 0 deletions
diff --git a/xpcom/glue/nsTObserverArray.h b/xpcom/glue/nsTObserverArray.h new file mode 100644 index 000000000..e9966d080 --- /dev/null +++ b/xpcom/glue/nsTObserverArray.h @@ -0,0 +1,520 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* 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 nsTObserverArray_h___ +#define nsTObserverArray_h___ + +#include "mozilla/MemoryReporting.h" +#include "nsTArray.h" +#include "nsCycleCollectionNoteChild.h" + +/** + * An array of observers. Like a normal array, but supports iterators that are + * stable even if the array is modified during iteration. + * The template parameter T is the observer type the array will hold; + * N is the number of built-in storage slots that come with the array. + * NOTE: You probably want to use nsTObserverArray, unless you specifically + * want built-in storage. See below. + * @see nsTObserverArray, nsTArray + */ + +class nsTObserverArray_base +{ +public: + typedef size_t index_type; + typedef size_t size_type; + typedef ptrdiff_t diff_type; + +protected: + class Iterator_base + { + protected: + friend class nsTObserverArray_base; + + Iterator_base(index_type aPosition, Iterator_base* aNext) + : mPosition(aPosition) + , mNext(aNext) + { + } + + // The current position of the iterator. Its exact meaning differs + // depending on iterator. See nsTObserverArray<T>::ForwardIterator. + index_type mPosition; + + // The next iterator currently iterating the same array + Iterator_base* mNext; + }; + + nsTObserverArray_base() : mIterators(nullptr) {} + + ~nsTObserverArray_base() + { + NS_ASSERTION(mIterators == nullptr, "iterators outlasting array"); + } + + /** + * Adjusts iterators after an element has been inserted or removed + * from the array. + * @param aModPos Position where elements were added or removed. + * @param aAdjustment -1 if an element was removed, 1 if an element was + * added. + */ + void AdjustIterators(index_type aModPos, diff_type aAdjustment); + + /** + * Clears iterators when the array is destroyed. + */ + void ClearIterators(); + + mutable Iterator_base* mIterators; +}; + +template<class T, size_t N> +class nsAutoTObserverArray : protected nsTObserverArray_base +{ +public: + typedef T elem_type; + typedef nsTArray<T> array_type; + + nsAutoTObserverArray() {} + + // + // Accessor methods + // + + // @return The number of elements in the array. + size_type Length() const { return mArray.Length(); } + + // @return True if the array is empty or false otherwise. + bool IsEmpty() const { return mArray.IsEmpty(); } + + // This method provides direct access to an element of the array. The given + // index must be within the array bounds. If the underlying array may change + // during iteration, use an iterator instead of this function. + // @param aIndex The index of an element in the array. + // @return A reference to the i'th element of the array. + elem_type& ElementAt(index_type aIndex) + { + return mArray.ElementAt(aIndex); + } + + // Same as above, but readonly. + const elem_type& ElementAt(index_type aIndex) const + { + return mArray.ElementAt(aIndex); + } + + // This method provides direct access to an element of the array in a bounds + // safe manner. If the requested index is out of bounds the provided default + // value is returned. + // @param aIndex The index of an element in the array. + // @param aDef The value to return if the index is out of bounds. + elem_type& SafeElementAt(index_type aIndex, elem_type& aDef) + { + return mArray.SafeElementAt(aIndex, aDef); + } + + // Same as above, but readonly. + const elem_type& SafeElementAt(index_type aIndex, const elem_type& aDef) const + { + return mArray.SafeElementAt(aIndex, aDef); + } + + // No operator[] is provided because the point of this class is to support + // allow modifying the array during iteration, and ElementAt() is not safe + // in those conditions. + + // + // Search methods + // + + // This method searches, starting from the beginning of the array, + // for the first element in this array that is equal to the given element. + // 'operator==' must be defined for elem_type. + // @param aItem The item to search for. + // @return true if the element was found. + template<class Item> + bool Contains(const Item& aItem) const + { + return IndexOf(aItem) != array_type::NoIndex; + } + + // This method searches for the offset of the first element in this + // array that is equal to the given element. + // 'operator==' must be defined for elem_type. + // @param aItem The item to search for. + // @param aStart The index to start from. + // @return The index of the found element or NoIndex if not found. + template<class Item> + index_type IndexOf(const Item& aItem, index_type aStart = 0) const + { + return mArray.IndexOf(aItem, aStart); + } + + // + // Mutation methods + // + + // Insert a given element at the given index. + // @param aIndex The index at which to insert item. + // @param aItem The item to insert, + // @return A pointer to the newly inserted element, or a null on DOM + template<class Item> + elem_type* InsertElementAt(index_type aIndex, const Item& aItem) + { + elem_type* item = mArray.InsertElementAt(aIndex, aItem); + AdjustIterators(aIndex, 1); + return item; + } + + // Same as above but without copy constructing. + // This is useful to avoid temporaries. + elem_type* InsertElementAt(index_type aIndex) + { + elem_type* item = mArray.InsertElementAt(aIndex); + AdjustIterators(aIndex, 1); + return item; + } + + // Prepend an element to the array unless it already exists in the array. + // 'operator==' must be defined for elem_type. + // @param aItem The item to prepend. + // @return true if the element was found, or inserted successfully. + template<class Item> + bool PrependElementUnlessExists(const Item& aItem) + { + if (Contains(aItem)) { + return true; + } + + bool inserted = mArray.InsertElementAt(0, aItem) != nullptr; + AdjustIterators(0, 1); + return inserted; + } + + // Append an element to the array. + // @param aItem The item to append. + // @return A pointer to the newly appended element, or null on OOM. + template<class Item> + elem_type* AppendElement(const Item& aItem) + { + return mArray.AppendElement(aItem); + } + + // Same as above, but without copy-constructing. This is useful to avoid + // temporaries. + elem_type* AppendElement() + { + return mArray.AppendElement(); + } + + // Append an element to the array unless it already exists in the array. + // 'operator==' must be defined for elem_type. + // @param aItem The item to append. + // @return true if the element was found, or inserted successfully. + template<class Item> + bool AppendElementUnlessExists(const Item& aItem) + { + return Contains(aItem) || AppendElement(aItem) != nullptr; + } + + // Remove an element from the array. + // @param aIndex The index of the item to remove. + void RemoveElementAt(index_type aIndex) + { + NS_ASSERTION(aIndex < mArray.Length(), "invalid index"); + mArray.RemoveElementAt(aIndex); + AdjustIterators(aIndex, -1); + } + + // This helper function combines IndexOf with RemoveElementAt to "search + // and destroy" the first element that is equal to the given element. + // 'operator==' must be defined for elem_type. + // @param aItem The item to search for. + // @return true if the element was found and removed. + template<class Item> + bool RemoveElement(const Item& aItem) + { + index_type index = mArray.IndexOf(aItem, 0); + if (index == array_type::NoIndex) { + return false; + } + + mArray.RemoveElementAt(index); + AdjustIterators(index, -1); + return true; + } + + // See nsTArray::RemoveElementsBy. + void RemoveElementsBy(mozilla::function<bool(const elem_type&)> aPredicate) + { + index_type i = 0; + mArray.RemoveElementsBy([&](const elem_type& aItem) { + if (aPredicate(aItem)) { + // This element is going to be removed. + AdjustIterators(i, -1); + return true; + } + ++i; + return false; + }); + } + + // Removes all observers and collapses all iterators to the beginning of + // the array. The result is that forward iterators will see all elements + // in the array. + void Clear() + { + mArray.Clear(); + ClearIterators(); + } + + // Compact the array to minimize the memory it uses + void Compact() { mArray.Compact(); } + + // Returns the number of bytes on the heap taken up by this object, not + // including sizeof(*this). If you want to measure anything hanging off the + // array, you must iterate over the elements and measure them individually; + // hence the "Shallow" prefix. + size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const + { + return mArray.ShallowSizeOfExcludingThis(aMallocSizeOf); + } + + // + // Iterators + // + + // Base class for iterators. Do not use this directly. + class Iterator : public Iterator_base + { + protected: + friend class nsAutoTObserverArray; + typedef nsAutoTObserverArray<T, N> array_type; + + Iterator(index_type aPosition, const array_type& aArray) + : Iterator_base(aPosition, aArray.mIterators) + , mArray(const_cast<array_type&>(aArray)) + { + aArray.mIterators = this; + } + + ~Iterator() + { + NS_ASSERTION(mArray.mIterators == this, + "Iterators must currently be destroyed in opposite order " + "from the construction order. It is suggested that you " + "simply put them on the stack"); + mArray.mIterators = mNext; + } + + // The array we're iterating + array_type& mArray; + }; + + // Iterates the array forward from beginning to end. mPosition points + // to the element that will be returned on next call to GetNext. + // Elements: + // - prepended to the array during iteration *will not* be traversed + // - appended during iteration *will* be traversed + // - removed during iteration *will not* be traversed. + // @see EndLimitedIterator + class ForwardIterator : protected Iterator + { + public: + typedef nsAutoTObserverArray<T, N> array_type; + typedef Iterator base_type; + + explicit ForwardIterator(const array_type& aArray) + : Iterator(0, aArray) + { + } + + ForwardIterator(const array_type& aArray, index_type aPos) + : Iterator(aPos, aArray) + { + } + + bool operator<(const ForwardIterator& aOther) const + { + NS_ASSERTION(&this->mArray == &aOther.mArray, + "not iterating the same array"); + return base_type::mPosition < aOther.mPosition; + } + + // Returns true if there are more elements to iterate. + // This must precede a call to GetNext(). If false is + // returned, GetNext() must not be called. + bool HasMore() const + { + return base_type::mPosition < base_type::mArray.Length(); + } + + // Returns the next element and steps one step. This must + // be preceded by a call to HasMore(). + // @return The next observer. + elem_type& GetNext() + { + NS_ASSERTION(HasMore(), "iterating beyond end of array"); + return base_type::mArray.ElementAt(base_type::mPosition++); + } + }; + + // EndLimitedIterator works like ForwardIterator, but will not iterate new + // observers appended to the array after the iterator was created. + class EndLimitedIterator : protected ForwardIterator + { + public: + typedef nsAutoTObserverArray<T, N> array_type; + typedef Iterator base_type; + + explicit EndLimitedIterator(const array_type& aArray) + : ForwardIterator(aArray) + , mEnd(aArray, aArray.Length()) + { + } + + // Returns true if there are more elements to iterate. + // This must precede a call to GetNext(). If false is + // returned, GetNext() must not be called. + bool HasMore() const { return *this < mEnd; } + + // Returns the next element and steps one step. This must + // be preceded by a call to HasMore(). + // @return The next observer. + elem_type& GetNext() + { + NS_ASSERTION(HasMore(), "iterating beyond end of array"); + return base_type::mArray.ElementAt(base_type::mPosition++); + } + + private: + ForwardIterator mEnd; + }; + + // Iterates the array backward from end to start. mPosition points + // to the element that was returned last. + // Elements: + // - prepended to the array during iteration *will* be traversed, + // unless the iteration already arrived at the first element + // - appended during iteration *will not* be traversed + // - removed during iteration *will not* be traversed. + class BackwardIterator : protected Iterator + { + public: + typedef nsAutoTObserverArray<T, N> array_type; + typedef Iterator base_type; + + explicit BackwardIterator(const array_type& aArray) + : Iterator(aArray.Length(), aArray) + { + } + + // Returns true if there are more elements to iterate. + // This must precede a call to GetNext(). If false is + // returned, GetNext() must not be called. + bool HasMore() const { return base_type::mPosition > 0; } + + // Returns the next element and steps one step. This must + // be preceded by a call to HasMore(). + // @return The next observer. + elem_type& GetNext() + { + NS_ASSERTION(HasMore(), "iterating beyond start of array"); + return base_type::mArray.ElementAt(--base_type::mPosition); + } + + // Removes the element at the current iterator position. + // (the last element returned from |GetNext()|) + // This will not affect the next call to |GetNext()| + void Remove() + { + return base_type::mArray.RemoveElementAt(base_type::mPosition); + } + }; + +protected: + AutoTArray<T, N> mArray; +}; + +template<class T> +class nsTObserverArray : public nsAutoTObserverArray<T, 0> +{ +public: + typedef nsAutoTObserverArray<T, 0> base_type; + typedef nsTObserverArray_base::size_type size_type; + + // + // Initialization methods + // + + nsTObserverArray() {} + + // Initialize this array and pre-allocate some number of elements. + explicit nsTObserverArray(size_type aCapacity) + { + base_type::mArray.SetCapacity(aCapacity); + } +}; + +template<typename T, size_t N> +inline void +ImplCycleCollectionUnlink(nsAutoTObserverArray<T, N>& aField) +{ + aField.Clear(); +} + +template<typename T, size_t N> +inline void +ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback, + nsAutoTObserverArray<T, N>& aField, + const char* aName, + uint32_t aFlags = 0) +{ + aFlags |= CycleCollectionEdgeNameArrayFlag; + size_t length = aField.Length(); + for (size_t i = 0; i < length; ++i) { + ImplCycleCollectionTraverse(aCallback, aField.ElementAt(i), aName, aFlags); + } +} + +// XXXbz I wish I didn't have to pass in the observer type, but I +// don't see a way to get it out of array_. +// Note that this macro only works if the array holds pointers to XPCOM objects. +#define NS_OBSERVER_ARRAY_NOTIFY_XPCOM_OBSERVERS(array_, obstype_, func_, params_) \ + PR_BEGIN_MACRO \ + nsTObserverArray<obstype_ *>::ForwardIterator iter_(array_); \ + RefPtr<obstype_> obs_; \ + while (iter_.HasMore()) { \ + obs_ = iter_.GetNext(); \ + obs_ -> func_ params_ ; \ + } \ + PR_END_MACRO + +// Note that this macro only works if the array holds pointers to XPCOM objects. +#define NS_OBSERVER_ARRAY_NOTIFY_OBSERVERS(array_, obstype_, func_, params_) \ + PR_BEGIN_MACRO \ + nsTObserverArray<obstype_ *>::ForwardIterator iter_(array_); \ + obstype_* obs_; \ + while (iter_.HasMore()) { \ + obs_ = iter_.GetNext(); \ + obs_ -> func_ params_ ; \ + } \ + PR_END_MACRO + +#define NS_OBSERVER_ARRAY_NOTIFY_OBSERVERS_WITH_QI(array_, basetype_, obstype_, func_, params_) \ + PR_BEGIN_MACRO \ + nsTObserverArray<basetype_ *>::ForwardIterator iter_(array_); \ + basetype_* obsbase_; \ + while (iter_.HasMore()) { \ + obsbase_ = iter_.GetNext(); \ + nsCOMPtr<obstype_> obs_ = do_QueryInterface(obsbase_); \ + if (obs_) { \ + obs_ -> func_ params_ ; \ + } \ + } \ + PR_END_MACRO +#endif // nsTObserverArray_h___ |