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 : /* A type-safe doubly-linked list class. */
8 :
9 : /*
10 : * The classes LinkedList<T> and LinkedListElement<T> together form a
11 : * convenient, type-safe doubly-linked list implementation.
12 : *
13 : * The class T which will be inserted into the linked list must inherit from
14 : * LinkedListElement<T>. A given object may be in only one linked list at a
15 : * time.
16 : *
17 : * A LinkedListElement automatically removes itself from the list upon
18 : * destruction, and a LinkedList will fatally assert in debug builds if it's
19 : * non-empty when it's destructed.
20 : *
21 : * For example, you might use LinkedList in a simple observer list class as
22 : * follows.
23 : *
24 : * class Observer : public LinkedListElement<Observer>
25 : * {
26 : * public:
27 : * void observe(char* aTopic) { ... }
28 : * };
29 : *
30 : * class ObserverContainer
31 : * {
32 : * private:
33 : * LinkedList<Observer> list;
34 : *
35 : * public:
36 : * void addObserver(Observer* aObserver)
37 : * {
38 : * // Will assert if |aObserver| is part of another list.
39 : * list.insertBack(aObserver);
40 : * }
41 : *
42 : * void removeObserver(Observer* aObserver)
43 : * {
44 : * // Will assert if |aObserver| is not part of some list.
45 : * aObserver.remove();
46 : * // Or, will assert if |aObserver| is not part of |list| specifically.
47 : * // aObserver.removeFrom(list);
48 : * }
49 : *
50 : * void notifyObservers(char* aTopic)
51 : * {
52 : * for (Observer* o = list.getFirst(); o != nullptr; o = o->getNext()) {
53 : * o->observe(aTopic);
54 : * }
55 : * }
56 : * };
57 : *
58 : * Additionally, the class AutoCleanLinkedList<T> is a LinkedList<T> that will
59 : * remove and delete each element still within itself upon destruction. Note
60 : * that because each element is deleted, elements must have been allocated
61 : * using |new|.
62 : */
63 :
64 : #ifndef mozilla_LinkedList_h
65 : #define mozilla_LinkedList_h
66 :
67 : #include "mozilla/Assertions.h"
68 : #include "mozilla/Attributes.h"
69 : #include "mozilla/MemoryReporting.h"
70 : #include "mozilla/Move.h"
71 : #include "mozilla/RefPtr.h"
72 :
73 : #ifdef __cplusplus
74 :
75 : namespace mozilla {
76 :
77 : template<typename T>
78 : class LinkedListElement;
79 :
80 : namespace detail {
81 :
82 : /**
83 : * LinkedList supports refcounted elements using this adapter class. Clients
84 : * using LinkedList<RefPtr<T>> will get a data structure that holds a strong
85 : * reference to T as long as T is in the list.
86 : */
87 : template<typename T>
88 : struct LinkedListElementTraits
89 : {
90 : typedef T* RawType;
91 : typedef const T* ConstRawType;
92 : typedef T* ClientType;
93 : typedef const T* ConstClientType;
94 :
95 : // These static methods are called when an element is added to or removed from
96 : // a linked list. It can be used to keep track ownership in lists that are
97 : // supposed to own their elements. If elements are transferred from one list
98 : // to another, no enter or exit calls happen since the elements still belong
99 : // to a list.
100 12717 : static void enterList(LinkedListElement<T>* elt) {}
101 9177 : static void exitList(LinkedListElement<T>* elt) {}
102 : };
103 :
104 : template<typename T>
105 : struct LinkedListElementTraits<RefPtr<T>>
106 : {
107 : typedef T* RawType;
108 : typedef const T* ConstRawType;
109 : typedef RefPtr<T> ClientType;
110 : typedef RefPtr<const T> ConstClientType;
111 :
112 486 : static void enterList(LinkedListElement<RefPtr<T>>* elt) { elt->asT()->AddRef(); }
113 464 : static void exitList(LinkedListElement<RefPtr<T>>* elt) { elt->asT()->Release(); }
114 : };
115 :
116 : } /* namespace detail */
117 :
118 : template<typename T>
119 : class LinkedList;
120 :
121 : template<typename T>
122 : class LinkedListElement
123 : {
124 : typedef typename detail::LinkedListElementTraits<T> Traits;
125 : typedef typename Traits::RawType RawType;
126 : typedef typename Traits::ConstRawType ConstRawType;
127 : typedef typename Traits::ClientType ClientType;
128 : typedef typename Traits::ConstClientType ConstClientType;
129 :
130 : /*
131 : * It's convenient that we return nullptr when getNext() or getPrevious()
132 : * hits the end of the list, but doing so costs an extra word of storage in
133 : * each linked list node (to keep track of whether |this| is the sentinel
134 : * node) and a branch on this value in getNext/getPrevious.
135 : *
136 : * We could get rid of the extra word of storage by shoving the "is
137 : * sentinel" bit into one of the pointers, although this would, of course,
138 : * have performance implications of its own.
139 : *
140 : * But the goal here isn't to win an award for the fastest or slimmest
141 : * linked list; rather, we want a *convenient* linked list. So we won't
142 : * waste time guessing which micro-optimization strategy is best.
143 : *
144 : *
145 : * Speaking of unnecessary work, it's worth addressing here why we wrote
146 : * mozilla::LinkedList in the first place, instead of using stl::list.
147 : *
148 : * The key difference between mozilla::LinkedList and stl::list is that
149 : * mozilla::LinkedList stores the mPrev/mNext pointers in the object itself,
150 : * while stl::list stores the mPrev/mNext pointers in a list element which
151 : * itself points to the object being stored.
152 : *
153 : * mozilla::LinkedList's approach makes it harder to store an object in more
154 : * than one list. But the upside is that you can call next() / prev() /
155 : * remove() directly on the object. With stl::list, you'd need to store a
156 : * pointer to its iterator in the object in order to accomplish this. Not
157 : * only would this waste space, but you'd have to remember to update that
158 : * pointer every time you added or removed the object from a list.
159 : *
160 : * In-place, constant-time removal is a killer feature of doubly-linked
161 : * lists, and supporting this painlessly was a key design criterion.
162 : */
163 :
164 : private:
165 : LinkedListElement* mNext;
166 : LinkedListElement* mPrev;
167 : const bool mIsSentinel;
168 :
169 : public:
170 17209 : LinkedListElement()
171 : : mNext(this),
172 : mPrev(this),
173 17209 : mIsSentinel(false)
174 17209 : { }
175 :
176 : /*
177 : * Moves |aOther| into |*this|. If |aOther| is already in a list, then
178 : * |aOther| is removed from the list and replaced by |*this|.
179 : */
180 0 : LinkedListElement(LinkedListElement<T>&& aOther)
181 0 : : mIsSentinel(aOther.mIsSentinel)
182 : {
183 0 : adjustLinkForMove(Move(aOther));
184 0 : }
185 :
186 4 : LinkedListElement& operator=(LinkedListElement<T>&& aOther)
187 : {
188 4 : MOZ_ASSERT(mIsSentinel == aOther.mIsSentinel, "Mismatch NodeKind!");
189 4 : MOZ_ASSERT(!isInList(),
190 : "Assigning to an element in a list messes up that list!");
191 4 : adjustLinkForMove(Move(aOther));
192 4 : return *this;
193 : }
194 :
195 13290 : ~LinkedListElement()
196 : {
197 13290 : if (!mIsSentinel && isInList()) {
198 4942 : remove();
199 : }
200 13290 : }
201 :
202 : /*
203 : * Get the next element in the list, or nullptr if this is the last element
204 : * in the list.
205 : */
206 17628 : RawType getNext() { return mNext->asT(); }
207 158826 : ConstRawType getNext() const { return mNext->asT(); }
208 :
209 : /*
210 : * Get the previous element in the list, or nullptr if this is the first
211 : * element in the list.
212 : */
213 34503 : RawType getPrevious() { return mPrev->asT(); }
214 0 : ConstRawType getPrevious() const { return mPrev->asT(); }
215 :
216 : /*
217 : * Insert aElem after this element in the list. |this| must be part of a
218 : * linked list when you call setNext(); otherwise, this method will assert.
219 : */
220 9 : void setNext(RawType aElem)
221 : {
222 9 : MOZ_ASSERT(isInList());
223 9 : setNextUnsafe(aElem);
224 9 : }
225 :
226 : /*
227 : * Insert aElem before this element in the list. |this| must be part of a
228 : * linked list when you call setPrevious(); otherwise, this method will
229 : * assert.
230 : */
231 167 : void setPrevious(RawType aElem)
232 : {
233 167 : MOZ_ASSERT(isInList());
234 167 : setPreviousUnsafe(aElem);
235 167 : }
236 :
237 : /*
238 : * Remove this element from the list which contains it. If this element is
239 : * not currently part of a linked list, this method asserts.
240 : */
241 9641 : void remove()
242 : {
243 9641 : MOZ_ASSERT(isInList());
244 :
245 9641 : mPrev->mNext = mNext;
246 9641 : mNext->mPrev = mPrev;
247 9641 : mNext = this;
248 9641 : mPrev = this;
249 :
250 9641 : Traits::exitList(this);
251 9641 : }
252 :
253 : /*
254 : * Remove this element from the list containing it. Returns a pointer to the
255 : * element that follows this element (before it was removed). This method
256 : * asserts if the element does not belong to a list. Note: In a refcounted list,
257 : * |this| may be destroyed.
258 : */
259 0 : RawType removeAndGetNext()
260 : {
261 0 : RawType r = getNext();
262 0 : remove();
263 0 : return r;
264 : }
265 :
266 : /*
267 : * Remove this element from the list containing it. Returns a pointer to the
268 : * previous element in the containing list (before the removal). This method
269 : * asserts if the element does not belong to a list. Note: In a refcounted list,
270 : * |this| may be destroyed.
271 : */
272 : RawType removeAndGetPrevious()
273 : {
274 : RawType r = getPrevious();
275 : remove();
276 : return r;
277 : }
278 :
279 : /*
280 : * Identical to remove(), but also asserts in debug builds that this element
281 : * is in aList.
282 : */
283 2205 : void removeFrom(const LinkedList<T>& aList)
284 : {
285 2205 : aList.assertContains(asT());
286 2205 : remove();
287 2205 : }
288 :
289 : /*
290 : * Return true if |this| part is of a linked list, and false otherwise.
291 : */
292 190742 : bool isInList() const
293 : {
294 190742 : MOZ_ASSERT((mNext == this) == (mPrev == this));
295 190742 : return mNext != this;
296 : }
297 :
298 : private:
299 : friend class LinkedList<T>;
300 : friend struct detail::LinkedListElementTraits<T>;
301 :
302 : enum class NodeKind {
303 : Normal,
304 : Sentinel
305 : };
306 :
307 2400 : explicit LinkedListElement(NodeKind nodeKind)
308 : : mNext(this),
309 : mPrev(this),
310 2400 : mIsSentinel(nodeKind == NodeKind::Sentinel)
311 2400 : { }
312 :
313 : /*
314 : * Return |this| cast to T* if we're a normal node, or return nullptr if
315 : * we're a sentinel node.
316 : */
317 214112 : RawType asT()
318 : {
319 214112 : return mIsSentinel ? nullptr : static_cast<RawType>(this);
320 : }
321 : ConstRawType asT() const
322 : {
323 : return mIsSentinel ? nullptr : static_cast<ConstRawType>(this);
324 : }
325 :
326 : /*
327 : * Insert aElem after this element, but don't check that this element is in
328 : * the list. This is called by LinkedList::insertFront().
329 : */
330 148 : void setNextUnsafe(RawType aElem)
331 : {
332 148 : LinkedListElement *listElem = static_cast<LinkedListElement*>(aElem);
333 148 : MOZ_ASSERT(!listElem->isInList());
334 :
335 148 : listElem->mNext = this->mNext;
336 148 : listElem->mPrev = this;
337 148 : this->mNext->mPrev = listElem;
338 148 : this->mNext = listElem;
339 :
340 148 : Traits::enterList(aElem);
341 148 : }
342 :
343 : /*
344 : * Insert aElem before this element, but don't check that this element is in
345 : * the list. This is called by LinkedList::insertBack().
346 : */
347 13055 : void setPreviousUnsafe(RawType aElem)
348 : {
349 13055 : LinkedListElement<T>* listElem = static_cast<LinkedListElement<T>*>(aElem);
350 13055 : MOZ_ASSERT(!listElem->isInList());
351 :
352 13055 : listElem->mNext = this;
353 13055 : listElem->mPrev = this->mPrev;
354 13055 : this->mPrev->mNext = listElem;
355 13055 : this->mPrev = listElem;
356 :
357 13055 : Traits::enterList(aElem);
358 13055 : }
359 :
360 : /*
361 : * Adjust mNext and mPrev for implementing move constructor and move
362 : * assignment.
363 : */
364 4 : void adjustLinkForMove(LinkedListElement<T>&& aOther)
365 : {
366 4 : if (!aOther.isInList()) {
367 0 : mNext = this;
368 0 : mPrev = this;
369 0 : return;
370 : }
371 :
372 4 : if (!mIsSentinel) {
373 0 : Traits::enterList(this);
374 : }
375 :
376 4 : MOZ_ASSERT(aOther.mNext->mPrev == &aOther);
377 4 : MOZ_ASSERT(aOther.mPrev->mNext == &aOther);
378 :
379 : /*
380 : * Initialize |this| with |aOther|'s mPrev/mNext pointers, and adjust those
381 : * element to point to this one.
382 : */
383 4 : mNext = aOther.mNext;
384 4 : mPrev = aOther.mPrev;
385 :
386 4 : mNext->mPrev = this;
387 4 : mPrev->mNext = this;
388 :
389 : /*
390 : * Adjust |aOther| so it doesn't think it's in a list. This makes it
391 : * safely destructable.
392 : */
393 4 : aOther.mNext = &aOther;
394 4 : aOther.mPrev = &aOther;
395 :
396 4 : if (!mIsSentinel) {
397 0 : Traits::exitList(&aOther);
398 : }
399 : }
400 :
401 : LinkedListElement& operator=(const LinkedListElement<T>& aOther) = delete;
402 : LinkedListElement(const LinkedListElement<T>& aOther) = delete;
403 : };
404 :
405 : template<typename T>
406 : class LinkedList
407 : {
408 : private:
409 : typedef typename detail::LinkedListElementTraits<T> Traits;
410 : typedef typename Traits::RawType RawType;
411 : typedef typename Traits::ConstRawType ConstRawType;
412 : typedef typename Traits::ClientType ClientType;
413 : typedef typename Traits::ConstClientType ConstClientType;
414 :
415 : LinkedListElement<T> sentinel;
416 :
417 : public:
418 : class Iterator {
419 : RawType mCurrent;
420 :
421 : public:
422 2068 : explicit Iterator(RawType aCurrent) : mCurrent(aCurrent) {}
423 :
424 5050 : RawType operator *() const {
425 5050 : return mCurrent;
426 : }
427 :
428 4595 : const Iterator& operator++() {
429 4595 : mCurrent = mCurrent->getNext();
430 4595 : return *this;
431 : }
432 :
433 5629 : bool operator!=(Iterator& aOther) const {
434 5629 : return mCurrent != aOther.mCurrent;
435 : }
436 : };
437 :
438 2400 : LinkedList() : sentinel(LinkedListElement<T>::NodeKind::Sentinel) { }
439 :
440 0 : LinkedList(LinkedList<T>&& aOther)
441 0 : : sentinel(mozilla::Move(aOther.sentinel))
442 0 : { }
443 :
444 4 : LinkedList& operator=(LinkedList<T>&& aOther)
445 : {
446 4 : MOZ_ASSERT(isEmpty(), "Assigning to a non-empty list leaks elements in that list!");
447 4 : sentinel = mozilla::Move(aOther.sentinel);
448 4 : return *this;
449 : }
450 :
451 1099 : ~LinkedList() {
452 1099 : MOZ_ASSERT(isEmpty(),
453 : "failing this assertion means this LinkedList's creator is "
454 : "buggy: it should have removed all this list's elements before "
455 : "the list's destruction");
456 1099 : }
457 :
458 : /*
459 : * Add aElem to the front of the list.
460 : */
461 139 : void insertFront(RawType aElem)
462 : {
463 : /* Bypass setNext()'s this->isInList() assertion. */
464 139 : sentinel.setNextUnsafe(aElem);
465 139 : }
466 :
467 : /*
468 : * Add aElem to the back of the list.
469 : */
470 12888 : void insertBack(RawType aElem)
471 : {
472 12888 : sentinel.setPreviousUnsafe(aElem);
473 12888 : }
474 :
475 : /*
476 : * Get the first element of the list, or nullptr if the list is empty.
477 : */
478 3988 : RawType getFirst() { return sentinel.getNext(); }
479 6213 : ConstRawType getFirst() const { return sentinel.getNext(); }
480 :
481 : /*
482 : * Get the last element of the list, or nullptr if the list is empty.
483 : */
484 34427 : RawType getLast() { return sentinel.getPrevious(); }
485 : ConstRawType getLast() const { return sentinel.getPrevious(); }
486 :
487 : /*
488 : * Get and remove the first element of the list. If the list is empty,
489 : * return nullptr.
490 : */
491 2765 : ClientType popFirst()
492 : {
493 2765 : ClientType ret = sentinel.getNext();
494 2765 : if (ret) {
495 1757 : static_cast<LinkedListElement<T>*>(RawType(ret))->remove();
496 : }
497 2765 : return ret;
498 : }
499 :
500 : /*
501 : * Get and remove the last element of the list. If the list is empty,
502 : * return nullptr.
503 : */
504 6 : ClientType popLast()
505 : {
506 6 : ClientType ret = sentinel.getPrevious();
507 6 : if (ret) {
508 6 : static_cast<LinkedListElement<T>*>(RawType(ret))->remove();
509 : }
510 6 : return ret;
511 : }
512 :
513 : /*
514 : * Return true if the list is empty, or false otherwise.
515 : */
516 3957 : bool isEmpty() const
517 : {
518 3957 : return !sentinel.isInList();
519 : }
520 :
521 : /*
522 : * Remove all the elements from the list.
523 : *
524 : * This runs in time linear to the list's length, because we have to mark
525 : * each element as not in the list.
526 : */
527 6 : void clear()
528 : {
529 6 : while (popFirst()) {
530 0 : continue;
531 : }
532 6 : }
533 :
534 : /*
535 : * Allow range-based iteration:
536 : *
537 : * for (MyElementType* elt : myList) { ... }
538 : */
539 1034 : Iterator begin() {
540 1034 : return Iterator(getFirst());
541 : }
542 1034 : Iterator end() {
543 1034 : return Iterator(nullptr);
544 : }
545 :
546 : /*
547 : * Measures the memory consumption of the list excluding |this|. Note that
548 : * it only measures the list elements themselves. If the list elements
549 : * contain pointers to other memory blocks, those blocks must be measured
550 : * separately during a subsequent iteration over the list.
551 : */
552 0 : size_t sizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
553 : {
554 0 : size_t n = 0;
555 0 : for (const T* t = getFirst(); t; t = t->getNext()) {
556 0 : n += aMallocSizeOf(t);
557 : }
558 0 : return n;
559 : }
560 :
561 : /*
562 : * Like sizeOfExcludingThis(), but measures |this| as well.
563 : */
564 : size_t sizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
565 : {
566 : return aMallocSizeOf(this) + sizeOfExcludingThis(aMallocSizeOf);
567 : }
568 :
569 : /*
570 : * In a debug build, make sure that the list is sane (no cycles, consistent
571 : * mNext/mPrev pointers, only one sentinel). Has no effect in release builds.
572 : */
573 : void debugAssertIsSane() const
574 : {
575 : #ifdef DEBUG
576 : const LinkedListElement<T>* slow;
577 : const LinkedListElement<T>* fast1;
578 : const LinkedListElement<T>* fast2;
579 :
580 : /*
581 : * Check for cycles in the forward singly-linked list using the
582 : * tortoise/hare algorithm.
583 : */
584 : for (slow = sentinel.mNext,
585 : fast1 = sentinel.mNext->mNext,
586 : fast2 = sentinel.mNext->mNext->mNext;
587 : slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
588 : slow = slow->mNext, fast1 = fast2->mNext, fast2 = fast1->mNext) {
589 : MOZ_ASSERT(slow != fast1);
590 : MOZ_ASSERT(slow != fast2);
591 : }
592 :
593 : /* Check for cycles in the backward singly-linked list. */
594 : for (slow = sentinel.mPrev,
595 : fast1 = sentinel.mPrev->mPrev,
596 : fast2 = sentinel.mPrev->mPrev->mPrev;
597 : slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
598 : slow = slow->mPrev, fast1 = fast2->mPrev, fast2 = fast1->mPrev) {
599 : MOZ_ASSERT(slow != fast1);
600 : MOZ_ASSERT(slow != fast2);
601 : }
602 :
603 : /*
604 : * Check that |sentinel| is the only node in the list with
605 : * mIsSentinel == true.
606 : */
607 : for (const LinkedListElement<T>* elem = sentinel.mNext;
608 : elem != &sentinel;
609 : elem = elem->mNext) {
610 : MOZ_ASSERT(!elem->mIsSentinel);
611 : }
612 :
613 : /* Check that the mNext/mPrev pointers match up. */
614 : const LinkedListElement<T>* prev = &sentinel;
615 : const LinkedListElement<T>* cur = sentinel.mNext;
616 : do {
617 : MOZ_ASSERT(cur->mPrev == prev);
618 : MOZ_ASSERT(prev->mNext == cur);
619 :
620 : prev = cur;
621 : cur = cur->mNext;
622 : } while (cur != &sentinel);
623 : #endif /* ifdef DEBUG */
624 : }
625 :
626 : private:
627 : friend class LinkedListElement<T>;
628 :
629 2205 : void assertContains(const RawType aValue) const
630 : {
631 : #ifdef DEBUG
632 154784 : for (ConstRawType elem = getFirst(); elem; elem = elem->getNext()) {
633 154784 : if (elem == aValue) {
634 4410 : return;
635 : }
636 : }
637 0 : MOZ_CRASH("element wasn't found in this list!");
638 : #endif
639 : }
640 :
641 : LinkedList& operator=(const LinkedList<T>& aOther) = delete;
642 : LinkedList(const LinkedList<T>& aOther) = delete;
643 : };
644 :
645 : template <typename T>
646 3 : class AutoCleanLinkedList : public LinkedList<T>
647 : {
648 : public:
649 0 : ~AutoCleanLinkedList()
650 : {
651 0 : clear();
652 0 : }
653 :
654 : AutoCleanLinkedList& operator=(AutoCleanLinkedList&& aOther)
655 : {
656 : LinkedList<T>::operator=(Forward<LinkedList<T>>(aOther));
657 : return *this;
658 : }
659 :
660 0 : void clear()
661 : {
662 0 : while (T* element = this->popFirst()) {
663 0 : delete element;
664 : }
665 0 : }
666 : };
667 :
668 : } /* namespace mozilla */
669 :
670 : #endif /* __cplusplus */
671 :
672 : #endif /* mozilla_LinkedList_h */
|
