Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef nsTObserverArray_h___
8 : #define nsTObserverArray_h___
9 :
10 : #include "mozilla/MemoryReporting.h"
11 : #include "nsTArray.h"
12 : #include "nsCycleCollectionNoteChild.h"
13 :
14 : #include <functional>
15 :
16 : /**
17 : * An array of observers. Like a normal array, but supports iterators that are
18 : * stable even if the array is modified during iteration.
19 : * The template parameter T is the observer type the array will hold;
20 : * N is the number of built-in storage slots that come with the array.
21 : * NOTE: You probably want to use nsTObserverArray, unless you specifically
22 : * want built-in storage. See below.
23 : * @see nsTObserverArray, nsTArray
24 : */
25 :
26 : class nsTObserverArray_base
27 : {
28 : public:
29 : typedef size_t index_type;
30 : typedef size_t size_type;
31 : typedef ptrdiff_t diff_type;
32 :
33 : protected:
34 : class Iterator_base
35 : {
36 : protected:
37 : friend class nsTObserverArray_base;
38 :
39 5853 : Iterator_base(index_type aPosition, Iterator_base* aNext)
40 5853 : : mPosition(aPosition)
41 5853 : , mNext(aNext)
42 : {
43 5853 : }
44 :
45 : // The current position of the iterator. Its exact meaning differs
46 : // depending on iterator. See nsTObserverArray<T>::ForwardIterator.
47 : index_type mPosition;
48 :
49 : // The next iterator currently iterating the same array
50 : Iterator_base* mNext;
51 : };
52 :
53 2425 : nsTObserverArray_base() : mIterators(nullptr) {}
54 :
55 43 : ~nsTObserverArray_base()
56 43 : {
57 43 : NS_ASSERTION(mIterators == nullptr, "iterators outlasting array");
58 43 : }
59 :
60 : /**
61 : * Adjusts iterators after an element has been inserted or removed
62 : * from the array.
63 : * @param aModPos Position where elements were added or removed.
64 : * @param aAdjustment -1 if an element was removed, 1 if an element was
65 : * added.
66 : */
67 : void AdjustIterators(index_type aModPos, diff_type aAdjustment);
68 :
69 : /**
70 : * Clears iterators when the array is destroyed.
71 : */
72 : void ClearIterators();
73 :
74 : mutable Iterator_base* mIterators;
75 : };
76 :
77 : template<class T, size_t N>
78 43 : class nsAutoTObserverArray : protected nsTObserverArray_base
79 : {
80 : public:
81 : typedef T elem_type;
82 : typedef nsTArray<T> array_type;
83 :
84 2418 : nsAutoTObserverArray() {}
85 :
86 : //
87 : // Accessor methods
88 : //
89 :
90 : // @return The number of elements in the array.
91 19589 : size_type Length() const { return mArray.Length(); }
92 :
93 : // @return True if the array is empty or false otherwise.
94 12501 : bool IsEmpty() const { return mArray.IsEmpty(); }
95 :
96 : // This method provides direct, readonly access to the array elements.
97 : // @return A pointer to the first element of the array. If the array is
98 : // empty, then this pointer must not be dereferenced.
99 : const elem_type* Elements() const
100 : {
101 : return mArray.Elements();
102 : }
103 27384 : elem_type* Elements()
104 : {
105 27384 : return mArray.Elements();
106 : }
107 :
108 : // This method provides direct access to an element of the array. The given
109 : // index must be within the array bounds. If the underlying array may change
110 : // during iteration, use an iterator instead of this function.
111 : // @param aIndex The index of an element in the array.
112 : // @return A reference to the i'th element of the array.
113 22985 : elem_type& ElementAt(index_type aIndex)
114 : {
115 22985 : return mArray.ElementAt(aIndex);
116 : }
117 :
118 : // Same as above, but readonly.
119 105 : const elem_type& ElementAt(index_type aIndex) const
120 : {
121 105 : return mArray.ElementAt(aIndex);
122 : }
123 :
124 : // This method provides direct access to an element of the array in a bounds
125 : // safe manner. If the requested index is out of bounds the provided default
126 : // value is returned.
127 : // @param aIndex The index of an element in the array.
128 : // @param aDef The value to return if the index is out of bounds.
129 : elem_type& SafeElementAt(index_type aIndex, elem_type& aDef)
130 : {
131 : return mArray.SafeElementAt(aIndex, aDef);
132 : }
133 :
134 : // Same as above, but readonly.
135 42 : const elem_type& SafeElementAt(index_type aIndex, const elem_type& aDef) const
136 : {
137 42 : return mArray.SafeElementAt(aIndex, aDef);
138 : }
139 :
140 : // No operator[] is provided because the point of this class is to support
141 : // allow modifying the array during iteration, and ElementAt() is not safe
142 : // in those conditions.
143 :
144 : //
145 : // Search methods
146 : //
147 :
148 : // This method searches, starting from the beginning of the array,
149 : // for the first element in this array that is equal to the given element.
150 : // 'operator==' must be defined for elem_type.
151 : // @param aItem The item to search for.
152 : // @return true if the element was found.
153 : template<class Item>
154 118 : bool Contains(const Item& aItem) const
155 : {
156 118 : return IndexOf(aItem) != array_type::NoIndex;
157 : }
158 :
159 : // This method searches for the offset of the first element in this
160 : // array that is equal to the given element.
161 : // 'operator==' must be defined for elem_type.
162 : // @param aItem The item to search for.
163 : // @param aStart The index to start from.
164 : // @return The index of the found element or NoIndex if not found.
165 : template<class Item>
166 358 : index_type IndexOf(const Item& aItem, index_type aStart = 0) const
167 : {
168 358 : return mArray.IndexOf(aItem, aStart);
169 : }
170 :
171 : //
172 : // Mutation methods
173 : //
174 :
175 : // Insert a given element at the given index.
176 : // @param aIndex The index at which to insert item.
177 : // @param aItem The item to insert,
178 : // @return A pointer to the newly inserted element, or a null on DOM
179 : template<class Item>
180 0 : elem_type* InsertElementAt(index_type aIndex, const Item& aItem)
181 : {
182 0 : elem_type* item = mArray.InsertElementAt(aIndex, aItem);
183 0 : AdjustIterators(aIndex, 1);
184 0 : return item;
185 : }
186 :
187 : // Same as above but without copy constructing.
188 : // This is useful to avoid temporaries.
189 0 : elem_type* InsertElementAt(index_type aIndex)
190 : {
191 0 : elem_type* item = mArray.InsertElementAt(aIndex);
192 0 : AdjustIterators(aIndex, 1);
193 0 : return item;
194 : }
195 :
196 : // Prepend an element to the array unless it already exists in the array.
197 : // 'operator==' must be defined for elem_type.
198 : // @param aItem The item to prepend.
199 : // @return true if the element was found, or inserted successfully.
200 : template<class Item>
201 55 : bool PrependElementUnlessExists(const Item& aItem)
202 : {
203 55 : if (Contains(aItem)) {
204 0 : return true;
205 : }
206 :
207 55 : bool inserted = mArray.InsertElementAt(0, aItem) != nullptr;
208 55 : AdjustIterators(0, 1);
209 55 : return inserted;
210 : }
211 :
212 : // Append an element to the array.
213 : // @param aItem The item to append.
214 : // @return A pointer to the newly appended element, or null on OOM.
215 : template<class Item>
216 301 : elem_type* AppendElement(const Item& aItem)
217 : {
218 301 : return mArray.AppendElement(aItem);
219 : }
220 :
221 : // Same as above, but without copy-constructing. This is useful to avoid
222 : // temporaries.
223 2280 : elem_type* AppendElement()
224 : {
225 2280 : return mArray.AppendElement();
226 : }
227 :
228 : // Append an element to the array unless it already exists in the array.
229 : // 'operator==' must be defined for elem_type.
230 : // @param aItem The item to append.
231 : // @return true if the element was found, or inserted successfully.
232 : template<class Item>
233 1 : bool AppendElementUnlessExists(const Item& aItem)
234 : {
235 1 : return Contains(aItem) || AppendElement(aItem) != nullptr;
236 : }
237 :
238 : // Remove an element from the array.
239 : // @param aIndex The index of the item to remove.
240 175 : void RemoveElementAt(index_type aIndex)
241 : {
242 175 : NS_ASSERTION(aIndex < mArray.Length(), "invalid index");
243 175 : mArray.RemoveElementAt(aIndex);
244 175 : AdjustIterators(aIndex, -1);
245 175 : }
246 :
247 : // This helper function combines IndexOf with RemoveElementAt to "search
248 : // and destroy" the first element that is equal to the given element.
249 : // 'operator==' must be defined for elem_type.
250 : // @param aItem The item to search for.
251 : // @return true if the element was found and removed.
252 : template<class Item>
253 137 : bool RemoveElement(const Item& aItem)
254 : {
255 137 : index_type index = mArray.IndexOf(aItem, 0);
256 137 : if (index == array_type::NoIndex) {
257 0 : return false;
258 : }
259 :
260 137 : mArray.RemoveElementAt(index);
261 137 : AdjustIterators(index, -1);
262 137 : return true;
263 : }
264 :
265 : // See nsTArray::RemoveElementsBy.
266 : template <typename Predicate>
267 1 : void RemoveElementsBy(Predicate aPredicate)
268 : {
269 1 : index_type i = 0;
270 12 : mArray.RemoveElementsBy([&](const elem_type& aItem) {
271 11 : if (aPredicate(aItem)) {
272 : // This element is going to be removed.
273 11 : AdjustIterators(i, -1);
274 1 : return true;
275 : }
276 10 : ++i;
277 10 : return false;
278 : });
279 1 : }
280 :
281 : // Removes all observers and collapses all iterators to the beginning of
282 : // the array. The result is that forward iterators will see all elements
283 : // in the array.
284 21 : void Clear()
285 : {
286 21 : mArray.Clear();
287 21 : ClearIterators();
288 21 : }
289 :
290 : // Compact the array to minimize the memory it uses
291 601 : void Compact() { mArray.Compact(); }
292 :
293 : // Returns the number of bytes on the heap taken up by this object, not
294 : // including sizeof(*this). If you want to measure anything hanging off the
295 : // array, you must iterate over the elements and measure them individually;
296 : // hence the "Shallow" prefix.
297 42 : size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
298 : {
299 42 : return mArray.ShallowSizeOfExcludingThis(aMallocSizeOf);
300 : }
301 :
302 : //
303 : // Iterators
304 : //
305 :
306 : // Base class for iterators. Do not use this directly.
307 : class Iterator : public Iterator_base
308 : {
309 : protected:
310 : friend class nsAutoTObserverArray;
311 : typedef nsAutoTObserverArray<T, N> array_type;
312 :
313 5853 : Iterator(index_type aPosition, const array_type& aArray)
314 : : Iterator_base(aPosition, aArray.mIterators)
315 5853 : , mArray(const_cast<array_type&>(aArray))
316 : {
317 5853 : aArray.mIterators = this;
318 5853 : }
319 :
320 5851 : ~Iterator()
321 : {
322 5851 : NS_ASSERTION(mArray.mIterators == this,
323 : "Iterators must currently be destroyed in opposite order "
324 : "from the construction order. It is suggested that you "
325 : "simply put them on the stack");
326 5851 : mArray.mIterators = mNext;
327 5851 : }
328 :
329 : // The array we're iterating
330 : array_type& mArray;
331 : };
332 :
333 : // Iterates the array forward from beginning to end. mPosition points
334 : // to the element that will be returned on next call to GetNext.
335 : // Elements:
336 : // - prepended to the array during iteration *will not* be traversed
337 : // - appended during iteration *will* be traversed
338 : // - removed during iteration *will not* be traversed.
339 : // @see EndLimitedIterator
340 5251 : class ForwardIterator : protected Iterator
341 : {
342 : public:
343 : typedef nsAutoTObserverArray<T, N> array_type;
344 : typedef Iterator base_type;
345 :
346 4268 : explicit ForwardIterator(const array_type& aArray)
347 4268 : : Iterator(0, aArray)
348 : {
349 4268 : }
350 :
351 985 : ForwardIterator(const array_type& aArray, index_type aPos)
352 985 : : Iterator(aPos, aArray)
353 : {
354 985 : }
355 :
356 43108 : bool operator<(const ForwardIterator& aOther) const
357 : {
358 43108 : NS_ASSERTION(&this->mArray == &aOther.mArray,
359 : "not iterating the same array");
360 43108 : return base_type::mPosition < aOther.mPosition;
361 : }
362 :
363 : // Returns true if there are more elements to iterate.
364 : // This must precede a call to GetNext(). If false is
365 : // returned, GetNext() must not be called.
366 13281 : bool HasMore() const
367 : {
368 13281 : return base_type::mPosition < base_type::mArray.Length();
369 : }
370 :
371 : // Returns the next element and steps one step. This must
372 : // be preceded by a call to HasMore().
373 : // @return The next observer.
374 4999 : elem_type& GetNext()
375 : {
376 4999 : NS_ASSERTION(HasMore(), "iterating beyond end of array");
377 4999 : return base_type::mArray.Elements()[base_type::mPosition++];
378 : }
379 : };
380 :
381 : // EndLimitedIterator works like ForwardIterator, but will not iterate new
382 : // observers appended to the array after the iterator was created.
383 984 : class EndLimitedIterator : protected ForwardIterator
384 : {
385 : public:
386 : typedef nsAutoTObserverArray<T, N> array_type;
387 : typedef Iterator base_type;
388 :
389 985 : explicit EndLimitedIterator(const array_type& aArray)
390 : : ForwardIterator(aArray)
391 985 : , mEnd(aArray, aArray.Length())
392 : {
393 985 : }
394 :
395 : // Returns true if there are more elements to iterate.
396 : // This must precede a call to GetNext(). If false is
397 : // returned, GetNext() must not be called.
398 43108 : bool HasMore() const { return *this < mEnd; }
399 :
400 : // Returns the next element and steps one step. This must
401 : // be preceded by a call to HasMore().
402 : // @return The next observer.
403 21062 : elem_type& GetNext()
404 : {
405 21062 : NS_ASSERTION(HasMore(), "iterating beyond end of array");
406 21062 : return base_type::mArray.Elements()[base_type::mPosition++];
407 : }
408 :
409 : private:
410 : ForwardIterator mEnd;
411 : };
412 :
413 : // Iterates the array backward from end to start. mPosition points
414 : // to the element that was returned last.
415 : // Elements:
416 : // - prepended to the array during iteration *will* be traversed,
417 : // unless the iteration already arrived at the first element
418 : // - appended during iteration *will not* be traversed
419 : // - removed during iteration *will not* be traversed.
420 600 : class BackwardIterator : protected Iterator
421 : {
422 : public:
423 : typedef nsAutoTObserverArray<T, N> array_type;
424 : typedef Iterator base_type;
425 :
426 600 : explicit BackwardIterator(const array_type& aArray)
427 600 : : Iterator(aArray.Length(), aArray)
428 : {
429 600 : }
430 :
431 : // Returns true if there are more elements to iterate.
432 : // This must precede a call to GetNext(). If false is
433 : // returned, GetNext() must not be called.
434 3246 : bool HasMore() const { return base_type::mPosition > 0; }
435 :
436 : // Returns the next element and steps one step. This must
437 : // be preceded by a call to HasMore().
438 : // @return The next observer.
439 1323 : elem_type& GetNext()
440 : {
441 1323 : NS_ASSERTION(HasMore(), "iterating beyond start of array");
442 1323 : return base_type::mArray.Elements()[--base_type::mPosition];
443 : }
444 :
445 : // Removes the element at the current iterator position.
446 : // (the last element returned from |GetNext()|)
447 : // This will not affect the next call to |GetNext()|
448 0 : void Remove()
449 : {
450 0 : return base_type::mArray.RemoveElementAt(base_type::mPosition);
451 : }
452 : };
453 :
454 : protected:
455 : AutoTArray<T, N> mArray;
456 : };
457 :
458 : template<class T>
459 7 : class nsTObserverArray : public nsAutoTObserverArray<T, 0>
460 : {
461 : public:
462 : typedef nsAutoTObserverArray<T, 0> base_type;
463 : typedef nsTObserverArray_base::size_type size_type;
464 :
465 : //
466 : // Initialization methods
467 : //
468 :
469 1387 : nsTObserverArray() {}
470 :
471 : // Initialize this array and pre-allocate some number of elements.
472 : explicit nsTObserverArray(size_type aCapacity)
473 : {
474 : base_type::mArray.SetCapacity(aCapacity);
475 : }
476 : };
477 :
478 : template<typename T, size_t N>
479 : inline void
480 0 : ImplCycleCollectionUnlink(nsAutoTObserverArray<T, N>& aField)
481 : {
482 0 : aField.Clear();
483 0 : }
484 :
485 : template<typename T, size_t N>
486 : inline void
487 1 : ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
488 : nsAutoTObserverArray<T, N>& aField,
489 : const char* aName,
490 : uint32_t aFlags = 0)
491 : {
492 1 : aFlags |= CycleCollectionEdgeNameArrayFlag;
493 1 : size_t length = aField.Length();
494 1 : for (size_t i = 0; i < length; ++i) {
495 0 : ImplCycleCollectionTraverse(aCallback, aField.ElementAt(i), aName, aFlags);
496 : }
497 1 : }
498 :
499 : // XXXbz I wish I didn't have to pass in the observer type, but I
500 : // don't see a way to get it out of array_.
501 : // Note that this macro only works if the array holds pointers to XPCOM objects.
502 : #define NS_OBSERVER_ARRAY_NOTIFY_XPCOM_OBSERVERS(array_, obstype_, func_, params_) \
503 : do { \
504 : nsTObserverArray<obstype_ *>::ForwardIterator iter_(array_); \
505 : RefPtr<obstype_> obs_; \
506 : while (iter_.HasMore()) { \
507 : obs_ = iter_.GetNext(); \
508 : obs_ -> func_ params_ ; \
509 : } \
510 : } while(0)
511 :
512 : // Note that this macro only works if the array holds pointers to XPCOM objects.
513 : #define NS_OBSERVER_ARRAY_NOTIFY_OBSERVERS(array_, obstype_, func_, params_) \
514 : do { \
515 : nsTObserverArray<obstype_ *>::ForwardIterator iter_(array_); \
516 : obstype_* obs_; \
517 : while (iter_.HasMore()) { \
518 : obs_ = iter_.GetNext(); \
519 : obs_ -> func_ params_ ; \
520 : } \
521 : } while(0)
522 :
523 : #define NS_OBSERVER_ARRAY_NOTIFY_OBSERVERS_WITH_QI(array_, basetype_, obstype_, func_, params_) \
524 : do { \
525 : nsTObserverArray<basetype_ *>::ForwardIterator iter_(array_); \
526 : basetype_* obsbase_; \
527 : while (iter_.HasMore()) { \
528 : obsbase_ = iter_.GetNext(); \
529 : nsCOMPtr<obstype_> obs_ = do_QueryInterface(obsbase_); \
530 : if (obs_) { \
531 : obs_ -> func_ params_ ; \
532 : } \
533 : } \
534 : } while(0)
535 : #endif // nsTObserverArray_h___
|
