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()) {
60 #ifndef mozilla_LinkedList_h
61 #define mozilla_LinkedList_h
63 #include "mozilla/Assertions.h"
64 #include "mozilla/Attributes.h"
65 #include "mozilla/MemoryReporting.h"
66 #include "mozilla/Move.h"
76 class LinkedListElement
79 * It's convenient that we return nullptr when getNext() or getPrevious()
80 * hits the end of the list, but doing so costs an extra word of storage in
81 * each linked list node (to keep track of whether |this| is the sentinel
82 * node) and a branch on this value in getNext/getPrevious.
84 * We could get rid of the extra word of storage by shoving the "is
85 * sentinel" bit into one of the pointers, although this would, of course,
86 * have performance implications of its own.
88 * But the goal here isn't to win an award for the fastest or slimmest
89 * linked list; rather, we want a *convenient* linked list. So we won't
90 * waste time guessing which micro-optimization strategy is best.
93 * Speaking of unnecessary work, it's worth addressing here why we wrote
94 * mozilla::LinkedList in the first place, instead of using stl::list.
96 * The key difference between mozilla::LinkedList and stl::list is that
97 * mozilla::LinkedList stores the mPrev/mNext pointers in the object itself,
98 * while stl::list stores the mPrev/mNext pointers in a list element which
99 * itself points to the object being stored.
101 * mozilla::LinkedList's approach makes it harder to store an object in more
102 * than one list. But the upside is that you can call next() / prev() /
103 * remove() directly on the object. With stl::list, you'd need to store a
104 * pointer to its iterator in the object in order to accomplish this. Not
105 * only would this waste space, but you'd have to remember to update that
106 * pointer every time you added or removed the object from a list.
108 * In-place, constant-time removal is a killer feature of doubly-linked
109 * lists, and supporting this painlessly was a key design criterion.
113 LinkedListElement
* mNext
;
114 LinkedListElement
* mPrev
;
115 const bool mIsSentinel
;
124 LinkedListElement(LinkedListElement
<T
>&& other
)
125 : mIsSentinel(other
.mIsSentinel
)
127 if (!other
.isInList()) {
133 MOZ_ASSERT(other
.mNext
->mPrev
== &other
);
134 MOZ_ASSERT(other
.mPrev
->mNext
== &other
);
137 * Initialize |this| with |other|'s mPrev/mNext pointers, and adjust those
138 * element to point to this one.
147 * Adjust |other| so it doesn't think it's in a list. This makes it
148 * safely destructable.
150 other
.mNext
= &other
;
151 other
.mPrev
= &other
;
156 if (!mIsSentinel
&& isInList()) {
162 * Get the next element in the list, or nullptr if this is the last element
165 T
* getNext() { return mNext
->asT(); }
166 const T
* getNext() const { return mNext
->asT(); }
169 * Get the previous element in the list, or nullptr if this is the first
170 * element in the list.
172 T
* getPrevious() { return mPrev
->asT(); }
173 const T
* getPrevious() const { return mPrev
->asT(); }
176 * Insert aElem after this element in the list. |this| must be part of a
177 * linked list when you call setNext(); otherwise, this method will assert.
179 void setNext(T
* aElem
)
181 MOZ_ASSERT(isInList());
182 setNextUnsafe(aElem
);
186 * Insert aElem before this element in the list. |this| must be part of a
187 * linked list when you call setPrevious(); otherwise, this method will
190 void setPrevious(T
* aElem
)
192 MOZ_ASSERT(isInList());
193 setPreviousUnsafe(aElem
);
197 * Remove this element from the list which contains it. If this element is
198 * not currently part of a linked list, this method asserts.
202 MOZ_ASSERT(isInList());
204 mPrev
->mNext
= mNext
;
205 mNext
->mPrev
= mPrev
;
211 * Identical to remove(), but also asserts in debug builds that this element
214 void removeFrom(const LinkedList
<T
>& aList
)
216 aList
.assertContains(asT());
221 * Return true if |this| part is of a linked list, and false otherwise.
223 bool isInList() const
225 MOZ_ASSERT((mNext
== this) == (mPrev
== this));
226 return mNext
!= this;
230 friend class LinkedList
<T
>;
237 explicit LinkedListElement(NodeKind nodeKind
)
240 mIsSentinel(nodeKind
== NODE_KIND_SENTINEL
)
244 * Return |this| cast to T* if we're a normal node, or return nullptr if
245 * we're a sentinel node.
249 return mIsSentinel
? nullptr : static_cast<T
*>(this);
253 return mIsSentinel
? nullptr : static_cast<const T
*>(this);
257 * Insert aElem after this element, but don't check that this element is in
258 * the list. This is called by LinkedList::insertFront().
260 void setNextUnsafe(T
* aElem
)
262 LinkedListElement
*listElem
= static_cast<LinkedListElement
*>(aElem
);
263 MOZ_ASSERT(!listElem
->isInList());
265 listElem
->mNext
= this->mNext
;
266 listElem
->mPrev
= this;
267 this->mNext
->mPrev
= listElem
;
268 this->mNext
= listElem
;
272 * Insert aElem before this element, but don't check that this element is in
273 * the list. This is called by LinkedList::insertBack().
275 void setPreviousUnsafe(T
* aElem
)
277 LinkedListElement
<T
>* listElem
= static_cast<LinkedListElement
<T
>*>(aElem
);
278 MOZ_ASSERT(!listElem
->isInList());
280 listElem
->mNext
= this;
281 listElem
->mPrev
= this->mPrev
;
282 this->mPrev
->mNext
= listElem
;
283 this->mPrev
= listElem
;
287 LinkedListElement
& operator=(const LinkedListElement
<T
>& aOther
) = delete;
288 LinkedListElement(const LinkedListElement
<T
>& aOther
) = delete;
295 LinkedListElement
<T
> sentinel
;
298 LinkedList() : sentinel(LinkedListElement
<T
>::NODE_KIND_SENTINEL
) { }
300 LinkedList(LinkedList
<T
>&& aOther
)
301 : sentinel(mozilla::Move(aOther
.sentinel
))
304 ~LinkedList() { MOZ_ASSERT(isEmpty()); }
307 * Add aElem to the front of the list.
309 void insertFront(T
* aElem
)
311 /* Bypass setNext()'s this->isInList() assertion. */
312 sentinel
.setNextUnsafe(aElem
);
316 * Add aElem to the back of the list.
318 void insertBack(T
* aElem
)
320 sentinel
.setPreviousUnsafe(aElem
);
324 * Get the first element of the list, or nullptr if the list is empty.
326 T
* getFirst() { return sentinel
.getNext(); }
327 const T
* getFirst() const { return sentinel
.getNext(); }
330 * Get the last element of the list, or nullptr if the list is empty.
332 T
* getLast() { return sentinel
.getPrevious(); }
333 const T
* getLast() const { return sentinel
.getPrevious(); }
336 * Get and remove the first element of the list. If the list is empty,
341 T
* ret
= sentinel
.getNext();
343 static_cast<LinkedListElement
<T
>*>(ret
)->remove();
349 * Get and remove the last element of the list. If the list is empty,
354 T
* ret
= sentinel
.getPrevious();
356 static_cast<LinkedListElement
<T
>*>(ret
)->remove();
362 * Return true if the list is empty, or false otherwise.
366 return !sentinel
.isInList();
370 * Remove all the elements from the list.
372 * This runs in time linear to the list's length, because we have to mark
373 * each element as not in the list.
383 * Measures the memory consumption of the list excluding |this|. Note that
384 * it only measures the list elements themselves. If the list elements
385 * contain pointers to other memory blocks, those blocks must be measured
386 * separately during a subsequent iteration over the list.
388 size_t sizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const
391 for (const T
* t
= getFirst(); t
; t
= t
->getNext()) {
392 n
+= aMallocSizeOf(t
);
398 * Like sizeOfExcludingThis(), but measures |this| as well.
400 size_t sizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const
402 return aMallocSizeOf(this) + sizeOfExcludingThis(aMallocSizeOf
);
406 * In a debug build, make sure that the list is sane (no cycles, consistent
407 * mNext/mPrev pointers, only one sentinel). Has no effect in release builds.
409 void debugAssertIsSane() const
412 const LinkedListElement
<T
>* slow
;
413 const LinkedListElement
<T
>* fast1
;
414 const LinkedListElement
<T
>* fast2
;
417 * Check for cycles in the forward singly-linked list using the
418 * tortoise/hare algorithm.
420 for (slow
= sentinel
.mNext
,
421 fast1
= sentinel
.mNext
->mNext
,
422 fast2
= sentinel
.mNext
->mNext
->mNext
;
423 slow
!= &sentinel
&& fast1
!= &sentinel
&& fast2
!= &sentinel
;
424 slow
= slow
->mNext
, fast1
= fast2
->mNext
, fast2
= fast1
->mNext
) {
425 MOZ_ASSERT(slow
!= fast1
);
426 MOZ_ASSERT(slow
!= fast2
);
429 /* Check for cycles in the backward singly-linked list. */
430 for (slow
= sentinel
.mPrev
,
431 fast1
= sentinel
.mPrev
->mPrev
,
432 fast2
= sentinel
.mPrev
->mPrev
->mPrev
;
433 slow
!= &sentinel
&& fast1
!= &sentinel
&& fast2
!= &sentinel
;
434 slow
= slow
->mPrev
, fast1
= fast2
->mPrev
, fast2
= fast1
->mPrev
) {
435 MOZ_ASSERT(slow
!= fast1
);
436 MOZ_ASSERT(slow
!= fast2
);
440 * Check that |sentinel| is the only node in the list with
441 * mIsSentinel == true.
443 for (const LinkedListElement
<T
>* elem
= sentinel
.mNext
;
445 elem
= elem
->mNext
) {
446 MOZ_ASSERT(!elem
->mIsSentinel
);
449 /* Check that the mNext/mPrev pointers match up. */
450 const LinkedListElement
<T
>* prev
= &sentinel
;
451 const LinkedListElement
<T
>* cur
= sentinel
.mNext
;
453 MOZ_ASSERT(cur
->mPrev
== prev
);
454 MOZ_ASSERT(prev
->mNext
== cur
);
458 } while (cur
!= &sentinel
);
459 #endif /* ifdef DEBUG */
463 friend class LinkedListElement
<T
>;
465 void assertContains(const T
* aValue
) const
468 for (const T
* elem
= getFirst(); elem
; elem
= elem
->getNext()) {
469 if (elem
== aValue
) {
473 MOZ_CRASH("element wasn't found in this list!");
477 LinkedList
& operator=(const LinkedList
<T
>& aOther
) = delete;
478 LinkedList(const LinkedList
<T
>& aOther
) = delete;
481 } /* namespace mozilla */
483 #endif /* __cplusplus */
485 #endif /* mozilla_LinkedList_h */