Source code
Revision control
Copy as Markdown
Other Tools
/* -*- 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
#ifndef nsTObserverArray_h___
#define nsTObserverArray_h___
#include "mozilla/MemoryReporting.h"
#include "mozilla/ReverseIterator.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 {
public:
Iterator_base(const Iterator_base&) = delete;
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 value_type;
typedef nsTArray<T> array_type;
nsAutoTObserverArray() = default;
//
// 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, readonly access to the array elements.
// @return A pointer to the first element of the array. If the array is
// empty, then this pointer must not be dereferenced.
const value_type* Elements() const { return mArray.Elements(); }
value_type* Elements() { return mArray.Elements(); }
// 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.
value_type& ElementAt(index_type aIndex) { return mArray.ElementAt(aIndex); }
// Same as above, but readonly.
const value_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.
value_type& SafeElementAt(index_type aIndex, value_type& aDef) {
return mArray.SafeElementAt(aIndex, aDef);
}
// Same as above, but readonly.
const value_type& SafeElementAt(index_type aIndex,
const value_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 value_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 value_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,
template <class Item>
void InsertElementAt(index_type aIndex, const Item& aItem) {
mArray.InsertElementAt(aIndex, aItem);
AdjustIterators(aIndex, 1);
}
// Same as above but without copy constructing.
// This is useful to avoid temporaries.
value_type* InsertElementAt(index_type aIndex) {
value_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 value_type.
// @param aItem The item to prepend.
template <class Item>
void PrependElementUnlessExists(const Item& aItem) {
if (!Contains(aItem)) {
mArray.InsertElementAt(0, aItem);
AdjustIterators(0, 1);
}
}
// Append an element to the array.
// @param aItem The item to append.
template <class Item>
void AppendElement(Item&& aItem) {
mArray.AppendElement(std::forward<Item>(aItem));
}
// Same as above, but without copy-constructing. This is useful to avoid
// temporaries.
value_type* AppendElement() { return mArray.AppendElement(); }
// Append an element to the array unless it already exists in the array.
// 'operator==' must be defined for value_type.
// @param aItem The item to append.
template <class Item>
void AppendElementUnlessExists(const Item& aItem) {
if (!Contains(aItem)) {
mArray.AppendElement(aItem);
}
}
// 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 value_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. Neither the predicate nor the removal of
// elements from the array must have any side effects that modify the array.
template <typename Predicate>
void NonObservingRemoveElementsBy(Predicate aPredicate) {
index_type i = 0;
mArray.RemoveElementsBy([&](const value_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(const Iterator& aOther)
: Iterator(aOther.mPosition, aOther.mArray) {}
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.
value_type& GetNext() {
NS_ASSERTION(HasMore(), "iterating beyond end of array");
return base_type::mArray.Elements()[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 - 1);
}
};
// 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.
value_type& GetNext() {
NS_ASSERTION(HasMore(), "iterating beyond end of array");
return base_type::mArray.Elements()[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 - 1);
}
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.
value_type& GetNext() {
NS_ASSERTION(HasMore(), "iterating beyond start of array");
return base_type::mArray.Elements()[--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);
}
};
struct EndSentinel {};
// Internal type, do not use directly, see
// ForwardRange()/EndLimitedRange()/BackwardRange().
template <typename Iterator, typename U>
struct STLIterator {
using value_type = std::remove_reference_t<U>;
explicit STLIterator(const nsAutoTObserverArray<T, N>& aArray)
: mIterator{aArray} {
operator++();
}
bool operator!=(const EndSentinel&) const {
// We are a non-end-sentinel and the other is an end-sentinel, so we are
// still valid if mCurrent is valid.
return mCurrent;
}
STLIterator& operator++() {
mCurrent = mIterator.HasMore() ? &mIterator.GetNext() : nullptr;
return *this;
}
value_type* operator->() { return mCurrent; }
U& operator*() { return *mCurrent; }
private:
Iterator mIterator;
value_type* mCurrent;
};
// Internal type, do not use directly, see
// ForwardRange()/EndLimitedRange()/BackwardRange().
template <typename Iterator, typename U>
class STLIteratorRange {
public:
using iterator = STLIterator<Iterator, U>;
explicit STLIteratorRange(const nsAutoTObserverArray<T, N>& aArray)
: mArray{aArray} {}
STLIteratorRange(const STLIteratorRange& aOther) = delete;
iterator begin() const { return iterator{mArray}; }
EndSentinel end() const { return {}; }
private:
const nsAutoTObserverArray<T, N>& mArray;
};
template <typename U>
using STLForwardIteratorRange = STLIteratorRange<ForwardIterator, U>;
template <typename U>
using STLEndLimitedIteratorRange = STLIteratorRange<EndLimitedIterator, U>;
template <typename U>
using STLBackwardIteratorRange = STLIteratorRange<BackwardIterator, U>;
// Constructs a range (usable with range-based for) based on the
// ForwardIterator semantics. Note that this range does not provide
// full-feature STL-style iterators usable with STL-style algorithms.
auto ForwardRange() { return STLForwardIteratorRange<T>{*this}; }
// Constructs a const range (usable with range-based for) based on the
// ForwardIterator semantics. Note that this range does not provide
// full-feature STL-style iterators usable with STL-style algorithms.
auto ForwardRange() const { return STLForwardIteratorRange<const T>{*this}; }
// Constructs a range (usable with range-based for) based on the
// EndLimitedIterator semantics. Note that this range does not provide
// full-feature STL-style iterators usable with STL-style algorithms.
auto EndLimitedRange() { return STLEndLimitedIteratorRange<T>{*this}; }
// Constructs a const range (usable with range-based for) based on the
// EndLimitedIterator semantics. Note that this range does not provide
// full-feature STL-style iterators usable with STL-style algorithms.
auto EndLimitedRange() const {
return STLEndLimitedIteratorRange<const T>{*this};
}
// Constructs a range (usable with range-based for) based on the
// BackwardIterator semantics. Note that this range does not provide
// full-feature STL-style iterators usable with STL-style algorithms.
auto BackwardRange() { return STLBackwardIteratorRange<T>{*this}; }
// Constructs a const range (usable with range-based for) based on the
// BackwardIterator semantics. Note that this range does not provide
// full-feature STL-style iterators usable with STL-style algorithms.
auto BackwardRange() const {
return STLBackwardIteratorRange<const T>{*this};
}
// Constructs a const range (usable with range-based for and STL-style
// algorithms) based on a non-observing iterator. The array must not be
// modified during iteration.
auto NonObservingRange() const {
return mozilla::detail::IteratorRange<
typename AutoTArray<T, N>::const_iterator,
typename AutoTArray<T, N>::const_reverse_iterator>{mArray.cbegin(),
mArray.cend()};
}
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() = default;
// Initialize this array and pre-allocate some number of elements.
explicit nsTObserverArray(size_type aCapacity) {
base_type::mArray.SetCapacity(aCapacity);
}
nsTObserverArray Clone() const {
auto result = nsTObserverArray{};
result.mArray.Assign(this->mArray);
return result;
}
};
template <typename T, size_t N>
auto MakeBackInserter(nsAutoTObserverArray<T, N>& aArray) {
return mozilla::nsTArrayBackInserter<T, nsAutoTObserverArray<T, N>>{aArray};
}
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);
}
}
// Note that this macro only works if the array holds pointers to XPCOM objects.
#define NS_OBSERVER_ARRAY_NOTIFY_XPCOM_OBSERVERS(array_, func_, params_) \
do { \
for (RefPtr obs_ : (array_).ForwardRange()) { \
obs_->func_ params_; \
} \
} while (0)
// Note that this macro only works if the array holds pointers to XPCOM objects.
#define NS_OBSERVER_ARRAY_NOTIFY_OBSERVERS(array_, func_, params_) \
do { \
for (auto* obs_ : (array_).ForwardRange()) { \
obs_->func_ params_; \
} \
} while (0)
#endif // nsTObserverArray_h___