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