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 doubly-linked list with flexible next/prev naming. */
9 #ifndef mozilla_DoublyLinkedList_h
10 #define mozilla_DoublyLinkedList_h
15 #include "mozilla/Assertions.h"
18 * Where mozilla::LinkedList strives for ease of use above all other
19 * considerations, mozilla::DoublyLinkedList strives for flexibility. The
20 * following are things that can be done with mozilla::DoublyLinkedList that
21 * cannot be done with mozilla::LinkedList:
23 * * Arbitrary next/prev placement and naming. With the tools provided here,
24 * the next and previous pointers can be at the end of the structure, in a
25 * sub-structure, stored with a tag, in a union, wherever, as long as you
26 * can look them up and set them on demand.
27 * * Can be used without deriving from a new base and, thus, does not require
28 * use of constructors.
32 * class Observer : public DoublyLinkedListElement<Observer>
35 * void observe(char* aTopic) { ... }
38 * class ObserverContainer
41 * DoublyLinkedList<Observer> mList;
44 * void addObserver(Observer* aObserver)
46 * // Will assert if |aObserver| is part of another list.
47 * mList.pushBack(aObserver);
50 * void removeObserver(Observer* aObserver)
52 * // Will assert if |aObserver| is not part of |list|.
53 * mList.remove(aObserver);
56 * void notifyObservers(char* aTopic)
58 * for (Observer* o : mList) {
68 * Deriving from this will allow T to be inserted into and removed from a
72 class DoublyLinkedListElement
{
73 template <typename U
, typename E
>
74 friend class DoublyLinkedList
;
80 DoublyLinkedListElement() : mNext(nullptr), mPrev(nullptr) {}
84 * Provides access to a DoublyLinkedListElement within T.
86 * The default implementation of this template works for types that derive
87 * from DoublyLinkedListElement, but one can specialize for their class so
88 * that some appropriate DoublyLinkedListElement reference is returned.
90 * For more complex cases (multiple DoublyLinkedListElements, for example),
91 * one can define their own trait class and use that as ElementAccess for
92 * DoublyLinkedList. See TestDoublyLinkedList.cpp for an example.
95 struct GetDoublyLinkedListElement
{
96 static_assert(mozilla::IsBaseOf
<DoublyLinkedListElement
<T
>, T
>::value
,
97 "You need your own specialization of GetDoublyLinkedListElement"
98 " or use a separate Trait.");
99 static DoublyLinkedListElement
<T
>& Get(T
* aThis
) { return *aThis
; }
103 * A doubly linked list. |T| is the type of element stored in this list. |T|
104 * must contain or have access to unique next and previous element pointers.
105 * The template argument |ElementAccess| provides code to tell this list how to
106 * get a reference to a DoublyLinkedListElement that may reside anywhere.
108 template <typename T
, typename ElementAccess
= GetDoublyLinkedListElement
<T
>>
109 class DoublyLinkedList final
{
114 * Checks that either the list is empty and both mHead and mTail are nullptr
115 * or the list has entries and both mHead and mTail are non-null.
117 bool isStateValid() const { return (mHead
!= nullptr) == (mTail
!= nullptr); }
119 bool ElementNotInList(T
* aElm
) {
120 if (!ElementAccess::Get(aElm
).mNext
&& !ElementAccess::Get(aElm
).mPrev
) {
121 // Both mNext and mPrev being NULL can mean two things:
122 // - the element is not in the list.
123 // - the element is the first and only element in the list.
124 // So check for the latter.
125 return mHead
!= aElm
;
131 DoublyLinkedList() : mHead(nullptr), mTail(nullptr) {}
133 class Iterator final
{
137 using iterator_category
= std::forward_iterator_tag
;
138 using value_type
= T
;
139 using difference_type
= std::ptrdiff_t;
141 using reference
= T
&;
143 Iterator() : mCurrent(nullptr) {}
144 explicit Iterator(T
* aCurrent
) : mCurrent(aCurrent
) {}
146 T
& operator*() const { return *mCurrent
; }
147 T
* operator->() const { return mCurrent
; }
149 Iterator
& operator++() {
150 mCurrent
= ElementAccess::Get(mCurrent
).mNext
;
154 Iterator
operator++(int) {
155 Iterator result
= *this;
160 Iterator
& operator--() {
161 mCurrent
= ElementAccess::Get(mCurrent
).mPrev
;
165 Iterator
operator--(int) {
166 Iterator result
= *this;
171 bool operator!=(const Iterator
& aOther
) const {
172 return mCurrent
!= aOther
.mCurrent
;
175 bool operator==(const Iterator
& aOther
) const {
176 return mCurrent
== aOther
.mCurrent
;
179 explicit operator bool() const { return mCurrent
; }
182 Iterator
begin() { return Iterator(mHead
); }
183 const Iterator
begin() const { return Iterator(mHead
); }
184 const Iterator
cbegin() const { return Iterator(mHead
); }
186 Iterator
end() { return Iterator(); }
187 const Iterator
end() const { return Iterator(); }
188 const Iterator
cend() const { return Iterator(); }
191 * Returns true if the list contains no elements.
193 bool isEmpty() const {
194 MOZ_ASSERT(isStateValid());
195 return mHead
== nullptr;
199 * Inserts aElm into the list at the head position. |aElm| must not already
202 void pushFront(T
* aElm
) {
204 MOZ_ASSERT(ElementNotInList(aElm
));
205 MOZ_ASSERT(isStateValid());
207 ElementAccess::Get(aElm
).mNext
= mHead
;
209 MOZ_ASSERT(!ElementAccess::Get(mHead
).mPrev
);
210 ElementAccess::Get(mHead
).mPrev
= aElm
;
220 * Remove the head of the list and return it. Calling this on an empty list
224 MOZ_ASSERT(!isEmpty());
225 MOZ_ASSERT(isStateValid());
228 mHead
= result
? ElementAccess::Get(result
).mNext
: nullptr;
230 ElementAccess::Get(mHead
).mPrev
= nullptr;
233 if (mTail
== result
) {
238 ElementAccess::Get(result
).mNext
= nullptr;
239 ElementAccess::Get(result
).mPrev
= nullptr;
246 * Inserts aElm into the list at the tail position. |aElm| must not already
249 void pushBack(T
* aElm
) {
251 MOZ_ASSERT(ElementNotInList(aElm
));
252 MOZ_ASSERT(isStateValid());
254 ElementAccess::Get(aElm
).mNext
= nullptr;
255 ElementAccess::Get(aElm
).mPrev
= mTail
;
257 MOZ_ASSERT(!ElementAccess::Get(mTail
).mNext
);
258 ElementAccess::Get(mTail
).mNext
= aElm
;
268 * Remove the tail of the list and return it. Calling this on an empty list
272 MOZ_ASSERT(!isEmpty());
273 MOZ_ASSERT(isStateValid());
276 mTail
= result
? ElementAccess::Get(result
).mPrev
: nullptr;
278 ElementAccess::Get(mTail
).mNext
= nullptr;
281 if (mHead
== result
) {
286 ElementAccess::Get(result
).mNext
= nullptr;
287 ElementAccess::Get(result
).mPrev
= nullptr;
294 * Insert the given |aElm| *before* |aIter|.
296 void insertBefore(const Iterator
& aIter
, T
* aElm
) {
298 MOZ_ASSERT(ElementNotInList(aElm
));
299 MOZ_ASSERT(isStateValid());
302 return pushBack(aElm
);
303 } else if (aIter
== begin()) {
304 return pushFront(aElm
);
307 T
* after
= &(*aIter
);
308 T
* before
= ElementAccess::Get(after
).mPrev
;
311 ElementAccess::Get(before
).mNext
= aElm
;
312 ElementAccess::Get(aElm
).mPrev
= before
;
313 ElementAccess::Get(aElm
).mNext
= after
;
314 ElementAccess::Get(after
).mPrev
= aElm
;
318 * Removes the given element from the list. The element must be in this list.
320 void remove(T
* aElm
) {
322 MOZ_ASSERT(ElementAccess::Get(aElm
).mNext
||
323 ElementAccess::Get(aElm
).mPrev
||
324 (aElm
== mHead
&& aElm
== mTail
),
325 "Attempted to remove element not in this list");
327 if (T
* prev
= ElementAccess::Get(aElm
).mPrev
) {
328 ElementAccess::Get(prev
).mNext
= ElementAccess::Get(aElm
).mNext
;
330 MOZ_ASSERT(mHead
== aElm
);
331 mHead
= ElementAccess::Get(aElm
).mNext
;
334 if (T
* next
= ElementAccess::Get(aElm
).mNext
) {
335 ElementAccess::Get(next
).mPrev
= ElementAccess::Get(aElm
).mPrev
;
337 MOZ_ASSERT(mTail
== aElm
);
338 mTail
= ElementAccess::Get(aElm
).mPrev
;
341 ElementAccess::Get(aElm
).mNext
= nullptr;
342 ElementAccess::Get(aElm
).mPrev
= nullptr;
346 * Returns an iterator referencing the first found element whose value matches
347 * the given element according to operator==.
349 Iterator
find(const T
& aElm
) { return std::find(begin(), end(), aElm
); }
352 * Returns whether the given element is in the list. Note that this uses
353 * T::operator==, not pointer comparison.
355 bool contains(const T
& aElm
) { return find(aElm
) != Iterator(); }
358 * Returns whether the given element might be in the list. Note that this
359 * assumes the element is either in the list or not in the list, and ignores
360 * the case where the element might be in another list in order to make the
363 bool ElementProbablyInList(T
* aElm
) {
367 return !ElementNotInList(aElm
);
371 } // namespace mozilla
373 #endif // mozilla_DoublyLinkedList_h