1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 /* A type-safe doubly-linked list class. */
9 * The classes LinkedList<T> and LinkedListElement<T> together form a
10 * convenient, type-safe doubly-linked list implementation.
12 * The class T which will be inserted into the linked list must inherit from
13 * LinkedListElement<T>. A given object may be in only one linked list at a
16 * A LinkedListElement automatically removes itself from the list upon
17 * destruction, and a LinkedList will fatally assert in debug builds if it's
18 * non-empty when it's destructed.
20 * For example, you might use LinkedList in a simple observer list class as
23 * class Observer : public LinkedListElement<Observer>
26 * void observe(char* topic) { ... }
29 * class ObserverContainer
32 * LinkedList<Observer> list;
35 * void addObserver(Observer* observer) {
36 * // Will assert if |observer| is part of another list.
37 * list.insertBack(observer);
40 * void removeObserver(Observer* observer) {
41 * // Will assert if |observer| is not part of some list.
43 * // Or, will assert if |observer| is not part of |list| specifically.
44 * // observer.removeFrom(list);
47 * void notifyObservers(char* topic) {
48 * for (Observer* o = list.getFirst(); o != NULL; o = o->getNext())
55 #ifndef mozilla_LinkedList_h_
56 #define mozilla_LinkedList_h_
58 #include "mozilla/Assertions.h"
59 #include "mozilla/Attributes.h"
69 class LinkedListElement
72 * It's convenient that we return NULL when getNext() or getPrevious() hits
73 * the end of the list, but doing so costs an extra word of storage in each
74 * linked list node (to keep track of whether |this| is the sentinel node)
75 * and a branch on this value in getNext/getPrevious.
77 * We could get rid of the extra word of storage by shoving the "is
78 * sentinel" bit into one of the pointers, although this would, of course,
79 * have performance implications of its own.
81 * But the goal here isn't to win an award for the fastest or slimmest
82 * linked list; rather, we want a *convenient* linked list. So we won't
83 * waste time guessing which micro-optimization strategy is best.
86 * Speaking of unnecessary work, it's worth addressing here why we wrote
87 * mozilla::LinkedList in the first place, instead of using stl::list.
89 * The key difference between mozilla::LinkedList and stl::list is that
90 * mozilla::LinkedList stores the prev/next pointers in the object itself,
91 * while stl::list stores the prev/next pointers in a list element which
92 * itself points to the object being stored.
94 * mozilla::LinkedList's approach makes it harder to store an object in more
95 * than one list. But the upside is that you can call next() / prev() /
96 * remove() directly on the object. With stl::list, you'd need to store a
97 * pointer to its iterator in the object in order to accomplish this. Not
98 * only would this waste space, but you'd have to remember to update that
99 * pointer every time you added or removed the object from a list.
101 * In-place, constant-time removal is a killer feature of doubly-linked
102 * lists, and supporting this painlessly was a key design criterion.
106 LinkedListElement
* next
;
107 LinkedListElement
* prev
;
108 const bool isSentinel
;
112 : next(MOZ_THIS_IN_INITIALIZER_LIST()),
113 prev(MOZ_THIS_IN_INITIALIZER_LIST()),
117 ~LinkedListElement() {
118 if (!isSentinel
&& isInList())
123 * Get the next element in the list, or NULL if this is the last element in
129 const T
* getNext() const {
134 * Get the previous element in the list, or NULL if this is the first element
140 const T
* getPrevious() const {
145 * Insert elem after this element in the list. |this| must be part of a
146 * linked list when you call setNext(); otherwise, this method will assert.
148 void setNext(T
* elem
) {
149 MOZ_ASSERT(isInList());
154 * Insert elem before this element in the list. |this| must be part of a
155 * linked list when you call setPrevious(); otherwise, this method will
158 void setPrevious(T
* elem
) {
159 MOZ_ASSERT(isInList());
160 setPreviousUnsafe(elem
);
164 * Remove this element from the list which contains it. If this element is
165 * not currently part of a linked list, this method asserts.
168 MOZ_ASSERT(isInList());
177 * Identical to remove(), but also asserts in debug builds that this element
180 void removeFrom(const LinkedList
<T
>& list
) {
181 list
.assertContains(asT());
186 * Return true if |this| part is of a linked list, and false otherwise.
188 bool isInList() const {
189 MOZ_ASSERT((next
== this) == (prev
== this));
194 friend class LinkedList
<T
>;
201 LinkedListElement(NodeKind nodeKind
)
202 : next(MOZ_THIS_IN_INITIALIZER_LIST()),
203 prev(MOZ_THIS_IN_INITIALIZER_LIST()),
204 isSentinel(nodeKind
== NODE_KIND_SENTINEL
)
208 * Return |this| cast to T* if we're a normal node, or return NULL if we're
215 return static_cast<T
*>(this);
217 const T
* asT() const {
221 return static_cast<const T
*>(this);
225 * Insert elem after this element, but don't check that this element is in
226 * the list. This is called by LinkedList::insertFront().
228 void setNextUnsafe(T
* elem
) {
229 LinkedListElement
*listElem
= static_cast<LinkedListElement
*>(elem
);
230 MOZ_ASSERT(!listElem
->isInList());
232 listElem
->next
= this->next
;
233 listElem
->prev
= this;
234 this->next
->prev
= listElem
;
235 this->next
= listElem
;
239 * Insert elem before this element, but don't check that this element is in
240 * the list. This is called by LinkedList::insertBack().
242 void setPreviousUnsafe(T
* elem
) {
243 LinkedListElement
<T
>* listElem
= static_cast<LinkedListElement
<T
>*>(elem
);
244 MOZ_ASSERT(!listElem
->isInList());
246 listElem
->next
= this;
247 listElem
->prev
= this->prev
;
248 this->prev
->next
= listElem
;
249 this->prev
= listElem
;
253 LinkedListElement
& operator=(const LinkedList
<T
>& other
) MOZ_DELETE
;
254 LinkedListElement(const LinkedList
<T
>& other
) MOZ_DELETE
;
261 LinkedListElement
<T
> sentinel
;
264 LinkedList() : sentinel(LinkedListElement
<T
>::NODE_KIND_SENTINEL
) { }
267 MOZ_ASSERT(isEmpty());
271 * Add elem to the front of the list.
273 void insertFront(T
* elem
) {
274 /* Bypass setNext()'s this->isInList() assertion. */
275 sentinel
.setNextUnsafe(elem
);
279 * Add elem to the back of the list.
281 void insertBack(T
* elem
) {
282 sentinel
.setPreviousUnsafe(elem
);
286 * Get the first element of the list, or NULL if the list is empty.
289 return sentinel
.getNext();
291 const T
* getFirst() const {
292 return sentinel
.getNext();
296 * Get the last element of the list, or NULL if the list is empty.
299 return sentinel
.getPrevious();
301 const T
* getLast() const {
302 return sentinel
.getPrevious();
306 * Get and remove the first element of the list. If the list is empty,
310 T
* ret
= sentinel
.getNext();
312 static_cast<LinkedListElement
<T
>*>(ret
)->remove();
317 * Get and remove the last element of the list. If the list is empty,
321 T
* ret
= sentinel
.getPrevious();
323 static_cast<LinkedListElement
<T
>*>(ret
)->remove();
328 * Return true if the list is empty, or false otherwise.
330 bool isEmpty() const {
331 return !sentinel
.isInList();
335 * Remove all the elements from the list.
337 * This runs in time linear to the list's length, because we have to mark
338 * each element as not in the list.
346 * In a debug build, make sure that the list is sane (no cycles, consistent
347 * next/prev pointers, only one sentinel). Has no effect in release builds.
349 void debugAssertIsSane() const {
351 const LinkedListElement
<T
>* slow
;
352 const LinkedListElement
<T
>* fast1
;
353 const LinkedListElement
<T
>* fast2
;
356 * Check for cycles in the forward singly-linked list using the
357 * tortoise/hare algorithm.
359 for (slow
= sentinel
.next
,
360 fast1
= sentinel
.next
->next
,
361 fast2
= sentinel
.next
->next
->next
;
362 slow
!= sentinel
&& fast1
!= sentinel
&& fast2
!= sentinel
;
363 slow
= slow
->next
, fast1
= fast2
->next
, fast2
= fast1
->next
)
365 MOZ_ASSERT(slow
!= fast1
);
366 MOZ_ASSERT(slow
!= fast2
);
369 /* Check for cycles in the backward singly-linked list. */
370 for (slow
= sentinel
.prev
,
371 fast1
= sentinel
.prev
->prev
,
372 fast2
= sentinel
.prev
->prev
->prev
;
373 slow
!= sentinel
&& fast1
!= sentinel
&& fast2
!= sentinel
;
374 slow
= slow
->prev
, fast1
= fast2
->prev
, fast2
= fast1
->prev
)
376 MOZ_ASSERT(slow
!= fast1
);
377 MOZ_ASSERT(slow
!= fast2
);
381 * Check that |sentinel| is the only node in the list with
382 * isSentinel == true.
384 for (const LinkedListElement
<T
>* elem
= sentinel
.next
;
388 MOZ_ASSERT(!elem
->isSentinel
);
391 /* Check that the next/prev pointers match up. */
392 const LinkedListElement
<T
>* prev
= sentinel
;
393 const LinkedListElement
<T
>* cur
= sentinel
.next
;
395 MOZ_ASSERT(cur
->prev
== prev
);
396 MOZ_ASSERT(prev
->next
== cur
);
400 } while (cur
!= sentinel
);
401 #endif /* ifdef DEBUG */
405 friend class LinkedListElement
<T
>;
407 void assertContains(const T
* t
) const {
409 for (const T
* elem
= getFirst();
411 elem
= elem
->getNext())
416 MOZ_CRASH("element wasn't found in this list!");
420 LinkedList
& operator=(const LinkedList
<T
>& other
) MOZ_DELETE
;
421 LinkedList(const LinkedList
<T
>& other
) MOZ_DELETE
;
424 } /* namespace mozilla */
426 #endif /* ifdef __cplusplus */
427 #endif /* ifdef mozilla_LinkedList_h_ */