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/. */
7 /* A type-safe doubly-linked list class. */
10 * The classes LinkedList<T> and LinkedListElement<T> together form a
11 * convenient, type-safe doubly-linked list implementation.
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
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.
21 * For example, you might use LinkedList in a simple observer list class as
24 * class Observer : public LinkedListElement<Observer>
27 * void observe(char* aTopic) { ... }
30 * class ObserverContainer
33 * LinkedList<Observer> list;
36 * void addObserver(Observer* aObserver)
38 * // Will assert if |aObserver| is part of another list.
39 * list.insertBack(aObserver);
42 * void removeObserver(Observer* aObserver)
44 * // Will assert if |aObserver| is not part of some list.
46 * // Or, will assert if |aObserver| is not part of |list| specifically.
47 * // aObserver.removeFrom(list);
50 * void notifyObservers(char* aTopic)
52 * for (Observer* o = list.getFirst(); o != nullptr; o = o->getNext()) {
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
64 #ifndef mozilla_LinkedList_h
65 #define mozilla_LinkedList_h
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"
78 class LinkedListElement
;
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.
88 struct LinkedListElementTraits
{
90 typedef const T
* ConstRawType
;
91 typedef T
* ClientType
;
92 typedef const T
* ConstClientType
;
94 // These static methods are called when an element is added to or removed from
95 // a linked list. It can be used to keep track ownership in lists that are
96 // supposed to own their elements. If elements are transferred from one list
97 // to another, no enter or exit calls happen since the elements still belong
99 static void enterList(LinkedListElement
<T
>* elt
) {}
100 static void exitList(LinkedListElement
<T
>* elt
) {}
102 // This method is called when AutoCleanLinkedList cleans itself
103 // during destruction. It can be used to call delete on elements if
104 // the list is the sole owner.
105 static void cleanElement(LinkedListElement
<T
>* elt
) { delete elt
->asT(); }
108 template <typename T
>
109 struct LinkedListElementTraits
<RefPtr
<T
>> {
111 typedef const T
* ConstRawType
;
112 typedef RefPtr
<T
> ClientType
;
113 typedef RefPtr
<const T
> ConstClientType
;
115 static void enterList(LinkedListElement
<RefPtr
<T
>>* elt
) {
116 elt
->asT()->AddRef();
118 static void exitList(LinkedListElement
<RefPtr
<T
>>* elt
) {
119 elt
->asT()->Release();
121 static void cleanElement(LinkedListElement
<RefPtr
<T
>>* elt
) {}
124 } /* namespace detail */
126 template <typename T
>
129 template <typename T
>
130 class LinkedListElement
{
131 typedef typename
detail::LinkedListElementTraits
<T
> Traits
;
132 typedef typename
Traits::RawType RawType
;
133 typedef typename
Traits::ConstRawType ConstRawType
;
134 typedef typename
Traits::ClientType ClientType
;
135 typedef typename
Traits::ConstClientType ConstClientType
;
138 * It's convenient that we return nullptr when getNext() or getPrevious()
139 * hits the end of the list, but doing so costs an extra word of storage in
140 * each linked list node (to keep track of whether |this| is the sentinel
141 * node) and a branch on this value in getNext/getPrevious.
143 * We could get rid of the extra word of storage by shoving the "is
144 * sentinel" bit into one of the pointers, although this would, of course,
145 * have performance implications of its own.
147 * But the goal here isn't to win an award for the fastest or slimmest
148 * linked list; rather, we want a *convenient* linked list. So we won't
149 * waste time guessing which micro-optimization strategy is best.
152 * Speaking of unnecessary work, it's worth addressing here why we wrote
153 * mozilla::LinkedList in the first place, instead of using stl::list.
155 * The key difference between mozilla::LinkedList and stl::list is that
156 * mozilla::LinkedList stores the mPrev/mNext pointers in the object itself,
157 * while stl::list stores the mPrev/mNext pointers in a list element which
158 * itself points to the object being stored.
160 * mozilla::LinkedList's approach makes it harder to store an object in more
161 * than one list. But the upside is that you can call next() / prev() /
162 * remove() directly on the object. With stl::list, you'd need to store a
163 * pointer to its iterator in the object in order to accomplish this. Not
164 * only would this waste space, but you'd have to remember to update that
165 * pointer every time you added or removed the object from a list.
167 * In-place, constant-time removal is a killer feature of doubly-linked
168 * lists, and supporting this painlessly was a key design criterion.
172 LinkedListElement
* mNext
;
173 LinkedListElement
* mPrev
;
174 const bool mIsSentinel
;
177 LinkedListElement() : mNext(this), mPrev(this), mIsSentinel(false) {}
180 * Moves |aOther| into |*this|. If |aOther| is already in a list, then
181 * |aOther| is removed from the list and replaced by |*this|.
183 LinkedListElement(LinkedListElement
<T
>&& aOther
)
184 : mIsSentinel(aOther
.mIsSentinel
) {
185 adjustLinkForMove(std::move(aOther
));
188 LinkedListElement
& operator=(LinkedListElement
<T
>&& aOther
) {
189 MOZ_ASSERT(mIsSentinel
== aOther
.mIsSentinel
, "Mismatch NodeKind!");
190 MOZ_ASSERT(!isInList(),
191 "Assigning to an element in a list messes up that list!");
192 adjustLinkForMove(std::move(aOther
));
196 ~LinkedListElement() {
197 if (!mIsSentinel
&& isInList()) {
203 * Get the next element in the list, or nullptr if this is the last element
206 RawType
getNext() { return mNext
->asT(); }
207 ConstRawType
getNext() const { return mNext
->asT(); }
210 * Get the previous element in the list, or nullptr if this is the first
211 * element in the list.
213 RawType
getPrevious() { return mPrev
->asT(); }
214 ConstRawType
getPrevious() const { return mPrev
->asT(); }
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.
220 void setNext(RawType aElem
) {
221 MOZ_ASSERT(isInList());
222 setNextUnsafe(aElem
);
226 * Insert aElem before this element in the list. |this| must be part of a
227 * linked list when you call setPrevious(); otherwise, this method will
230 void setPrevious(RawType aElem
) {
231 MOZ_ASSERT(isInList());
232 setPreviousUnsafe(aElem
);
236 * Remove this element from the list which contains it. If this element is
237 * not currently part of a linked list, this method asserts.
240 MOZ_ASSERT(isInList());
242 mPrev
->mNext
= mNext
;
243 mNext
->mPrev
= mPrev
;
247 Traits::exitList(this);
251 * Remove this element from the list containing it. Returns a pointer to the
252 * element that follows this element (before it was removed). This method
253 * asserts if the element does not belong to a list. Note: In a refcounted
254 * list, |this| may be destroyed.
256 RawType
removeAndGetNext() {
257 RawType r
= getNext();
263 * Remove this element from the list containing it. Returns a pointer to the
264 * previous element in the containing list (before the removal). This method
265 * asserts if the element does not belong to a list. Note: In a refcounted
266 * list, |this| may be destroyed.
268 RawType
removeAndGetPrevious() {
269 RawType r
= getPrevious();
275 * Identical to remove(), but also asserts in debug builds that this element
278 void removeFrom(const LinkedList
<T
>& aList
) {
279 aList
.assertContains(asT());
284 * Return true if |this| part is of a linked list, and false otherwise.
286 bool isInList() const {
287 MOZ_ASSERT((mNext
== this) == (mPrev
== this));
288 return mNext
!= this;
292 friend class LinkedList
<T
>;
293 friend struct detail::LinkedListElementTraits
<T
>;
295 enum class NodeKind
{ Normal
, Sentinel
};
297 explicit LinkedListElement(NodeKind nodeKind
)
298 : mNext(this), mPrev(this), mIsSentinel(nodeKind
== NodeKind::Sentinel
) {}
301 * Return |this| cast to T* if we're a normal node, or return nullptr if
302 * we're a sentinel node.
304 RawType
asT() { return mIsSentinel
? nullptr : static_cast<RawType
>(this); }
305 ConstRawType
asT() const {
306 return mIsSentinel
? nullptr : static_cast<ConstRawType
>(this);
310 * Insert aElem after this element, but don't check that this element is in
311 * the list. This is called by LinkedList::insertFront().
313 void setNextUnsafe(RawType aElem
) {
314 LinkedListElement
* listElem
= static_cast<LinkedListElement
*>(aElem
);
315 MOZ_ASSERT(!listElem
->isInList());
317 listElem
->mNext
= this->mNext
;
318 listElem
->mPrev
= this;
319 this->mNext
->mPrev
= listElem
;
320 this->mNext
= listElem
;
322 Traits::enterList(aElem
);
326 * Insert aElem before this element, but don't check that this element is in
327 * the list. This is called by LinkedList::insertBack().
329 void setPreviousUnsafe(RawType aElem
) {
330 LinkedListElement
<T
>* listElem
= static_cast<LinkedListElement
<T
>*>(aElem
);
331 MOZ_ASSERT(!listElem
->isInList());
333 listElem
->mNext
= this;
334 listElem
->mPrev
= this->mPrev
;
335 this->mPrev
->mNext
= listElem
;
336 this->mPrev
= listElem
;
338 Traits::enterList(aElem
);
342 * Adjust mNext and mPrev for implementing move constructor and move
345 void adjustLinkForMove(LinkedListElement
<T
>&& aOther
) {
346 if (!aOther
.isInList()) {
353 Traits::enterList(this);
356 MOZ_ASSERT(aOther
.mNext
->mPrev
== &aOther
);
357 MOZ_ASSERT(aOther
.mPrev
->mNext
== &aOther
);
360 * Initialize |this| with |aOther|'s mPrev/mNext pointers, and adjust those
361 * element to point to this one.
363 mNext
= aOther
.mNext
;
364 mPrev
= aOther
.mPrev
;
370 * Adjust |aOther| so it doesn't think it's in a list. This makes it
371 * safely destructable.
373 aOther
.mNext
= &aOther
;
374 aOther
.mPrev
= &aOther
;
377 Traits::exitList(&aOther
);
381 LinkedListElement
& operator=(const LinkedListElement
<T
>& aOther
) = delete;
382 LinkedListElement(const LinkedListElement
<T
>& aOther
) = delete;
385 template <typename T
>
388 typedef typename
detail::LinkedListElementTraits
<T
> Traits
;
389 typedef typename
Traits::RawType RawType
;
390 typedef typename
Traits::ConstRawType ConstRawType
;
391 typedef typename
Traits::ClientType ClientType
;
392 typedef typename
Traits::ConstClientType ConstClientType
;
393 typedef LinkedListElement
<T
>* ElementType
;
394 typedef const LinkedListElement
<T
>* ConstElementType
;
396 LinkedListElement
<T
> sentinel
;
399 template <typename Type
, typename Element
>
404 explicit Iterator(Type aCurrent
) : mCurrent(aCurrent
) {}
406 Type
operator*() const { return mCurrent
; }
408 const Iterator
& operator++() {
409 mCurrent
= static_cast<Element
>(mCurrent
)->getNext();
413 bool operator!=(const Iterator
& aOther
) const {
414 return mCurrent
!= aOther
.mCurrent
;
418 LinkedList() : sentinel(LinkedListElement
<T
>::NodeKind::Sentinel
) {}
420 LinkedList(LinkedList
<T
>&& aOther
) : sentinel(std::move(aOther
.sentinel
)) {}
422 LinkedList
& operator=(LinkedList
<T
>&& aOther
) {
423 MOZ_ASSERT(isEmpty(),
424 "Assigning to a non-empty list leaks elements in that list!");
425 sentinel
= std::move(aOther
.sentinel
);
430 MOZ_ASSERT(isEmpty(),
431 "failing this assertion means this LinkedList's creator is "
432 "buggy: it should have removed all this list's elements before "
433 "the list's destruction");
437 * Add aElem to the front of the list.
439 void insertFront(RawType aElem
) {
440 /* Bypass setNext()'s this->isInList() assertion. */
441 sentinel
.setNextUnsafe(aElem
);
445 * Add aElem to the back of the list.
447 void insertBack(RawType aElem
) { sentinel
.setPreviousUnsafe(aElem
); }
450 * Get the first element of the list, or nullptr if the list is empty.
452 RawType
getFirst() { return sentinel
.getNext(); }
453 ConstRawType
getFirst() const { return sentinel
.getNext(); }
456 * Get the last element of the list, or nullptr if the list is empty.
458 RawType
getLast() { return sentinel
.getPrevious(); }
459 ConstRawType
getLast() const { return sentinel
.getPrevious(); }
462 * Get and remove the first element of the list. If the list is empty,
465 ClientType
popFirst() {
466 ClientType ret
= sentinel
.getNext();
468 static_cast<LinkedListElement
<T
>*>(RawType(ret
))->remove();
474 * Get and remove the last element of the list. If the list is empty,
477 ClientType
popLast() {
478 ClientType ret
= sentinel
.getPrevious();
480 static_cast<LinkedListElement
<T
>*>(RawType(ret
))->remove();
486 * Return true if the list is empty, or false otherwise.
488 bool isEmpty() const { return !sentinel
.isInList(); }
491 * Remove all the elements from the list.
493 * This runs in time linear to the list's length, because we have to mark
494 * each element as not in the list.
502 * Allow range-based iteration:
504 * for (MyElementType* elt : myList) { ... }
506 Iterator
<RawType
, ElementType
> begin() {
507 return Iterator
<RawType
, ElementType
>(getFirst());
509 Iterator
<ConstRawType
, ConstElementType
> begin() const {
510 return Iterator
<ConstRawType
, ConstElementType
>(getFirst());
512 Iterator
<RawType
, ElementType
> end() {
513 return Iterator
<RawType
, ElementType
>(nullptr);
515 Iterator
<ConstRawType
, ConstElementType
> end() const {
516 return Iterator
<ConstRawType
, ConstElementType
>(nullptr);
520 * Measures the memory consumption of the list excluding |this|. Note that
521 * it only measures the list elements themselves. If the list elements
522 * contain pointers to other memory blocks, those blocks must be measured
523 * separately during a subsequent iteration over the list.
525 size_t sizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
527 ConstRawType t
= getFirst();
529 n
+= aMallocSizeOf(t
);
530 t
= static_cast<const LinkedListElement
<T
>*>(t
)->getNext();
536 * Like sizeOfExcludingThis(), but measures |this| as well.
538 size_t sizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
539 return aMallocSizeOf(this) + sizeOfExcludingThis(aMallocSizeOf
);
543 * In a debug build, make sure that the list is sane (no cycles, consistent
544 * mNext/mPrev pointers, only one sentinel). Has no effect in release builds.
546 void debugAssertIsSane() const {
548 const LinkedListElement
<T
>* slow
;
549 const LinkedListElement
<T
>* fast1
;
550 const LinkedListElement
<T
>* fast2
;
553 * Check for cycles in the forward singly-linked list using the
554 * tortoise/hare algorithm.
556 for (slow
= sentinel
.mNext
, fast1
= sentinel
.mNext
->mNext
,
557 fast2
= sentinel
.mNext
->mNext
->mNext
;
558 slow
!= &sentinel
&& fast1
!= &sentinel
&& fast2
!= &sentinel
;
559 slow
= slow
->mNext
, fast1
= fast2
->mNext
, fast2
= fast1
->mNext
) {
560 MOZ_ASSERT(slow
!= fast1
);
561 MOZ_ASSERT(slow
!= fast2
);
564 /* Check for cycles in the backward singly-linked list. */
565 for (slow
= sentinel
.mPrev
, fast1
= sentinel
.mPrev
->mPrev
,
566 fast2
= sentinel
.mPrev
->mPrev
->mPrev
;
567 slow
!= &sentinel
&& fast1
!= &sentinel
&& fast2
!= &sentinel
;
568 slow
= slow
->mPrev
, fast1
= fast2
->mPrev
, fast2
= fast1
->mPrev
) {
569 MOZ_ASSERT(slow
!= fast1
);
570 MOZ_ASSERT(slow
!= fast2
);
574 * Check that |sentinel| is the only node in the list with
575 * mIsSentinel == true.
577 for (const LinkedListElement
<T
>* elem
= sentinel
.mNext
; elem
!= &sentinel
;
578 elem
= elem
->mNext
) {
579 MOZ_ASSERT(!elem
->mIsSentinel
);
582 /* Check that the mNext/mPrev pointers match up. */
583 const LinkedListElement
<T
>* prev
= &sentinel
;
584 const LinkedListElement
<T
>* cur
= sentinel
.mNext
;
586 MOZ_ASSERT(cur
->mPrev
== prev
);
587 MOZ_ASSERT(prev
->mNext
== cur
);
591 } while (cur
!= &sentinel
);
592 # endif /* ifdef DEBUG */
596 friend class LinkedListElement
<T
>;
598 void assertContains(const RawType aValue
) const {
600 for (ConstRawType elem
= getFirst(); elem
; elem
= elem
->getNext()) {
601 if (elem
== aValue
) {
605 MOZ_CRASH("element wasn't found in this list!");
609 LinkedList
& operator=(const LinkedList
<T
>& aOther
) = delete;
610 LinkedList(const LinkedList
<T
>& aOther
) = delete;
613 template <typename T
>
614 class AutoCleanLinkedList
: public LinkedList
<T
> {
616 using Traits
= detail::LinkedListElementTraits
<T
>;
617 using ClientType
= typename
detail::LinkedListElementTraits
<T
>::ClientType
;
620 ~AutoCleanLinkedList() { clear(); }
622 AutoCleanLinkedList
& operator=(AutoCleanLinkedList
&& aOther
) {
623 LinkedList
<T
>::operator=(std::forward
<LinkedList
<T
>>(aOther
));
628 while (ClientType element
= this->popFirst()) {
629 Traits::cleanElement(element
);
634 } /* namespace mozilla */
636 #endif /* __cplusplus */
638 #endif /* mozilla_LinkedList_h */