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 * Provides access to a next and previous element pointer named |mNext| and
69 * |mPrev| respectively. This class is the default and will work if the list
70 * element derives from DoublyLinkedListElement.
72 * Although designed to work with DoublyLinkedListElement this will als work
73 * with any class that defines |mNext| and |mPrev| members with the correct
77 struct DoublyLinkedSiblingAccess
{
78 static void SetNext(T
* aElm
, T
* aNext
) { aElm
->mNext
= aNext
; }
79 static T
* GetNext(T
* aElm
) { return aElm
->mNext
; }
80 static void SetPrev(T
* aElm
, T
* aPrev
) { aElm
->mPrev
= aPrev
; }
81 static T
* GetPrev(T
* aElm
) { return aElm
->mPrev
; }
85 * Deriving from this will allow T to be inserted into and removed from a
89 struct DoublyLinkedListElement
91 friend struct DoublyLinkedSiblingAccess
<T
>;
96 DoublyLinkedListElement() : mNext(nullptr), mPrev(nullptr) {}
100 * A doubly linked list. |T| is the type of element stored in this list. |T|
101 * must contain or have access to unique next and previous element pointers.
102 * The template argument |SiblingAccess| provides code to tell this list how to
103 * get and set the next and previous pointers. The actual storage of next/prev
104 * links may reside anywhere and be encoded in any way.
106 template <typename T
, typename SiblingAccess
= DoublyLinkedSiblingAccess
<T
>>
107 class DoublyLinkedList final
113 * Checks that either the list is empty and both mHead and mTail are nullptr
114 * or the list has entries and both mHead and mTail are non-null.
116 bool isStateValid() const {
117 return (mHead
!= nullptr) == (mTail
!= nullptr);
120 static bool ElementNotInList(T
* aElm
) {
121 return !SiblingAccess::GetNext(aElm
) && !SiblingAccess::GetPrev(aElm
);
125 DoublyLinkedList() : mHead(nullptr), mTail(nullptr) {}
127 class Iterator final
{
131 using iterator_category
= std::forward_iterator_tag
;
132 using value_type
= T
;
133 using difference_type
= std::ptrdiff_t;
135 using reference
= T
&;
137 Iterator() : mCurrent(nullptr) {}
138 explicit Iterator(T
* aCurrent
) : mCurrent(aCurrent
) {}
140 T
& operator *() const { return *mCurrent
; }
141 T
* operator ->() const { return mCurrent
; }
143 Iterator
& operator++() {
144 mCurrent
= SiblingAccess::GetNext(mCurrent
);
148 Iterator
operator++(int) {
149 Iterator result
= *this;
154 Iterator
& operator--() {
155 mCurrent
= SiblingAccess::GetPrev(mCurrent
);
159 Iterator
operator--(int) {
160 Iterator result
= *this;
165 bool operator!=(const Iterator
& aOther
) const {
166 return mCurrent
!= aOther
.mCurrent
;
169 bool operator==(const Iterator
& aOther
) const {
170 return mCurrent
== aOther
.mCurrent
;
173 explicit operator bool() const {
178 Iterator
begin() { return Iterator(mHead
); }
179 const Iterator
begin() const { return Iterator(mHead
); }
180 const Iterator
cbegin() const { return Iterator(mHead
); }
182 Iterator
end() { return Iterator(); }
183 const Iterator
end() const { return Iterator(); }
184 const Iterator
cend() const { return Iterator(); }
187 * Returns true if the list contains no elements.
189 bool isEmpty() const {
190 MOZ_ASSERT(isStateValid());
191 return mHead
== nullptr;
195 * Inserts aElm into the list at the head position. |aElm| must not already
198 void pushFront(T
* aElm
) {
200 MOZ_ASSERT(ElementNotInList(aElm
));
201 MOZ_ASSERT(isStateValid());
203 SiblingAccess::SetNext(aElm
, mHead
);
205 MOZ_ASSERT(!SiblingAccess::GetPrev(mHead
));
206 SiblingAccess::SetPrev(mHead
, aElm
);
216 * Remove the head of the list and return it. Calling this on an empty list
220 MOZ_ASSERT(!isEmpty());
221 MOZ_ASSERT(isStateValid());
224 mHead
= result
? SiblingAccess::GetNext(result
) : nullptr;
226 SiblingAccess::SetPrev(mHead
, nullptr);
229 if (mTail
== result
) {
234 SiblingAccess::SetNext(result
, nullptr);
235 SiblingAccess::SetPrev(result
, nullptr);
242 * Inserts aElm into the list at the tail position. |aElm| must not already
245 void pushBack(T
* aElm
) {
247 MOZ_ASSERT(ElementNotInList(aElm
));
248 MOZ_ASSERT(isStateValid());
250 SiblingAccess::SetNext(aElm
, nullptr);
251 SiblingAccess::SetPrev(aElm
, mTail
);
253 MOZ_ASSERT(!SiblingAccess::GetNext(mTail
));
254 SiblingAccess::SetNext(mTail
, aElm
);
264 * Remove the tail of the list and return it. Calling this on an empty list
268 MOZ_ASSERT(!isEmpty());
269 MOZ_ASSERT(isStateValid());
272 mTail
= result
? SiblingAccess::GetPrev(result
) : nullptr;
274 SiblingAccess::SetNext(mTail
, nullptr);
277 if (mHead
== result
) {
282 SiblingAccess::SetNext(result
, nullptr);
283 SiblingAccess::SetPrev(result
, nullptr);
290 * Insert the given |aElm| *before* |aIter|.
292 void insertBefore(const Iterator
& aIter
, T
* aElm
) {
294 MOZ_ASSERT(ElementNotInList(aElm
));
295 MOZ_ASSERT(isStateValid());
298 return pushBack(aElm
);
299 } else if (aIter
== begin()) {
300 return pushFront(aElm
);
303 T
* after
= &(*aIter
);
304 T
* before
= SiblingAccess::GetPrev(after
);
307 SiblingAccess::SetNext(before
, aElm
);
308 SiblingAccess::SetPrev(aElm
, before
);
309 SiblingAccess::SetNext(aElm
, after
);
310 SiblingAccess::SetPrev(after
, aElm
);
314 * Removes the given element from the list. The element must be in this list.
316 void remove(T
* aElm
) {
318 MOZ_ASSERT(SiblingAccess::GetNext(aElm
) || SiblingAccess::GetPrev(aElm
) ||
319 (aElm
== mHead
&& aElm
== mTail
),
320 "Attempted to remove element not in this list");
322 if (T
* prev
= SiblingAccess::GetPrev(aElm
)) {
323 SiblingAccess::SetNext(prev
, SiblingAccess::GetNext(aElm
));
325 MOZ_ASSERT(mHead
== aElm
);
326 mHead
= SiblingAccess::GetNext(aElm
);
329 if (T
* next
= SiblingAccess::GetNext(aElm
)) {
330 SiblingAccess::SetPrev(next
, SiblingAccess::GetPrev(aElm
));
332 MOZ_ASSERT(mTail
== aElm
);
333 mTail
= SiblingAccess::GetPrev(aElm
);
336 SiblingAccess::SetNext(aElm
, nullptr);
337 SiblingAccess::SetPrev(aElm
, nullptr);
341 * Returns an iterator referencing the first found element whose value matches
342 * the given element according to operator==.
344 Iterator
find(const T
& aElm
) {
345 return std::find(begin(), end(), aElm
);
349 * Returns whether the given element is in the list. Note that this uses
350 * T::operator==, not pointer comparison.
352 bool contains(const T
& aElm
) {
353 return find(aElm
) != Iterator();
357 } // namespace mozilla
359 #endif // mozilla_DoublyLinkedList_h