Line data Source code
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/. */
6 :
7 : /** A doubly-linked list with flexible next/prev naming. */
8 :
9 : #ifndef mozilla_DoublyLinkedList_h
10 : #define mozilla_DoublyLinkedList_h
11 :
12 : #include <algorithm>
13 : #include <iterator>
14 :
15 : #include "mozilla/Assertions.h"
16 :
17 : /**
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:
22 : *
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.
29 : *
30 : * Example:
31 : *
32 : * class Observer : public DoublyLinkedListElement<Observer>
33 : * {
34 : * public:
35 : * void observe(char* aTopic) { ... }
36 : * };
37 : *
38 : * class ObserverContainer
39 : * {
40 : * private:
41 : * DoublyLinkedList<Observer> mList;
42 : *
43 : * public:
44 : * void addObserver(Observer* aObserver)
45 : * {
46 : * // Will assert if |aObserver| is part of another list.
47 : * mList.pushBack(aObserver);
48 : * }
49 : *
50 : * void removeObserver(Observer* aObserver)
51 : * {
52 : * // Will assert if |aObserver| is not part of |list|.
53 : * mList.remove(aObserver);
54 : * }
55 : *
56 : * void notifyObservers(char* aTopic)
57 : * {
58 : * for (Observer* o : mList) {
59 : * o->observe(aTopic);
60 : * }
61 : * }
62 : * };
63 : */
64 :
65 : namespace mozilla {
66 :
67 : /**
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.
71 : *
72 : * Although designed to work with DoublyLinkedListElement this will als work
73 : * with any class that defines |mNext| and |mPrev| members with the correct
74 : * type.
75 : */
76 : template <typename T>
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; }
82 : };
83 :
84 : /**
85 : * Deriving from this will allow T to be inserted into and removed from a
86 : * DoublyLinkedList.
87 : */
88 : template <typename T>
89 : struct DoublyLinkedListElement
90 : {
91 : friend struct DoublyLinkedSiblingAccess<T>;
92 : T* mNext;
93 : T* mPrev;
94 :
95 : public:
96 0 : DoublyLinkedListElement() : mNext(nullptr), mPrev(nullptr) {}
97 : };
98 :
99 : /**
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.
105 : */
106 : template <typename T, typename SiblingAccess = DoublyLinkedSiblingAccess<T>>
107 : class DoublyLinkedList final
108 : {
109 : T* mHead;
110 : T* mTail;
111 :
112 : /**
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.
115 : */
116 311 : bool isStateValid() const {
117 311 : return (mHead != nullptr) == (mTail != nullptr);
118 : }
119 :
120 0 : static bool ElementNotInList(T* aElm) {
121 0 : return !SiblingAccess::GetNext(aElm) && !SiblingAccess::GetPrev(aElm);
122 : }
123 :
124 : public:
125 4 : DoublyLinkedList() : mHead(nullptr), mTail(nullptr) {}
126 :
127 : class Iterator final {
128 : T* mCurrent;
129 :
130 : public:
131 : using iterator_category = std::forward_iterator_tag;
132 : using value_type = T;
133 : using difference_type = std::ptrdiff_t;
134 : using pointer = T*;
135 : using reference = T&;
136 :
137 0 : Iterator() : mCurrent(nullptr) {}
138 0 : explicit Iterator(T* aCurrent) : mCurrent(aCurrent) {}
139 :
140 0 : T& operator *() const { return *mCurrent; }
141 : T* operator ->() const { return mCurrent; }
142 :
143 0 : Iterator& operator++() {
144 0 : mCurrent = SiblingAccess::GetNext(mCurrent);
145 0 : return *this;
146 : }
147 :
148 0 : Iterator operator++(int) {
149 0 : Iterator result = *this;
150 0 : ++(*this);
151 0 : return result;
152 : }
153 :
154 : Iterator& operator--() {
155 : mCurrent = SiblingAccess::GetPrev(mCurrent);
156 : return *this;
157 : }
158 :
159 : Iterator operator--(int) {
160 : Iterator result = *this;
161 : --(*this);
162 : return result;
163 : }
164 :
165 0 : bool operator!=(const Iterator& aOther) const {
166 0 : return mCurrent != aOther.mCurrent;
167 : }
168 :
169 0 : bool operator==(const Iterator& aOther) const {
170 0 : return mCurrent == aOther.mCurrent;
171 : }
172 :
173 0 : explicit operator bool() const {
174 0 : return mCurrent;
175 : }
176 : };
177 :
178 0 : Iterator begin() { return Iterator(mHead); }
179 0 : const Iterator begin() const { return Iterator(mHead); }
180 : const Iterator cbegin() const { return Iterator(mHead); }
181 :
182 0 : Iterator end() { return Iterator(); }
183 : const Iterator end() const { return Iterator(); }
184 : const Iterator cend() const { return Iterator(); }
185 :
186 : /**
187 : * Returns true if the list contains no elements.
188 : */
189 311 : bool isEmpty() const {
190 311 : MOZ_ASSERT(isStateValid());
191 311 : return mHead == nullptr;
192 : }
193 :
194 : /**
195 : * Inserts aElm into the list at the head position. |aElm| must not already
196 : * be in a list.
197 : */
198 : void pushFront(T* aElm) {
199 : MOZ_ASSERT(aElm);
200 : MOZ_ASSERT(ElementNotInList(aElm));
201 : MOZ_ASSERT(isStateValid());
202 :
203 : SiblingAccess::SetNext(aElm, mHead);
204 : if (mHead) {
205 : MOZ_ASSERT(!SiblingAccess::GetPrev(mHead));
206 : SiblingAccess::SetPrev(mHead, aElm);
207 : }
208 :
209 : mHead = aElm;
210 : if (!mTail) {
211 : mTail = aElm;
212 : }
213 : }
214 :
215 : /**
216 : * Remove the head of the list and return it. Calling this on an empty list
217 : * will assert.
218 : */
219 : T* popFront() {
220 : MOZ_ASSERT(!isEmpty());
221 : MOZ_ASSERT(isStateValid());
222 :
223 : T* result = mHead;
224 : mHead = result ? SiblingAccess::GetNext(result) : nullptr;
225 : if (mHead) {
226 : SiblingAccess::SetPrev(mHead, nullptr);
227 : }
228 :
229 : if (mTail == result) {
230 : mTail = nullptr;
231 : }
232 :
233 : if (result) {
234 : SiblingAccess::SetNext(result, nullptr);
235 : SiblingAccess::SetPrev(result, nullptr);
236 : }
237 :
238 : return result;
239 : }
240 :
241 : /**
242 : * Inserts aElm into the list at the tail position. |aElm| must not already
243 : * be in a list.
244 : */
245 0 : void pushBack(T* aElm) {
246 0 : MOZ_ASSERT(aElm);
247 0 : MOZ_ASSERT(ElementNotInList(aElm));
248 0 : MOZ_ASSERT(isStateValid());
249 :
250 0 : SiblingAccess::SetNext(aElm, nullptr);
251 0 : SiblingAccess::SetPrev(aElm, mTail);
252 0 : if (mTail) {
253 0 : MOZ_ASSERT(!SiblingAccess::GetNext(mTail));
254 0 : SiblingAccess::SetNext(mTail, aElm);
255 : }
256 :
257 0 : mTail = aElm;
258 0 : if (!mHead) {
259 0 : mHead = aElm;
260 : }
261 0 : }
262 :
263 : /**
264 : * Remove the tail of the list and return it. Calling this on an empty list
265 : * will assert.
266 : */
267 : T* popBack() {
268 : MOZ_ASSERT(!isEmpty());
269 : MOZ_ASSERT(isStateValid());
270 :
271 : T* result = mTail;
272 : mTail = result ? SiblingAccess::GetPrev(result) : nullptr;
273 : if (mTail) {
274 : SiblingAccess::SetNext(mTail, nullptr);
275 : }
276 :
277 : if (mHead == result) {
278 : mHead = nullptr;
279 : }
280 :
281 : if (result) {
282 : SiblingAccess::SetNext(result, nullptr);
283 : SiblingAccess::SetPrev(result, nullptr);
284 : }
285 :
286 : return result;
287 : }
288 :
289 : /**
290 : * Insert the given |aElm| *before* |aIter|.
291 : */
292 : void insertBefore(const Iterator& aIter, T* aElm) {
293 : MOZ_ASSERT(aElm);
294 : MOZ_ASSERT(ElementNotInList(aElm));
295 : MOZ_ASSERT(isStateValid());
296 :
297 : if (!aIter) {
298 : return pushBack(aElm);
299 : } else if (aIter == begin()) {
300 : return pushFront(aElm);
301 : }
302 :
303 : T* after = &(*aIter);
304 : T* before = SiblingAccess::GetPrev(after);
305 : MOZ_ASSERT(before);
306 :
307 : SiblingAccess::SetNext(before, aElm);
308 : SiblingAccess::SetPrev(aElm, before);
309 : SiblingAccess::SetNext(aElm, after);
310 : SiblingAccess::SetPrev(after, aElm);
311 : }
312 :
313 : /**
314 : * Removes the given element from the list. The element must be in this list.
315 : */
316 0 : void remove(T* aElm) {
317 0 : MOZ_ASSERT(aElm);
318 0 : MOZ_ASSERT(SiblingAccess::GetNext(aElm) || SiblingAccess::GetPrev(aElm) ||
319 : (aElm == mHead && aElm == mTail),
320 : "Attempted to remove element not in this list");
321 :
322 0 : if (T* prev = SiblingAccess::GetPrev(aElm)) {
323 0 : SiblingAccess::SetNext(prev, SiblingAccess::GetNext(aElm));
324 : } else {
325 0 : MOZ_ASSERT(mHead == aElm);
326 0 : mHead = SiblingAccess::GetNext(aElm);
327 : }
328 :
329 0 : if (T* next = SiblingAccess::GetNext(aElm)) {
330 0 : SiblingAccess::SetPrev(next, SiblingAccess::GetPrev(aElm));
331 : } else {
332 0 : MOZ_ASSERT(mTail == aElm);
333 0 : mTail = SiblingAccess::GetPrev(aElm);
334 : }
335 :
336 0 : SiblingAccess::SetNext(aElm, nullptr);
337 0 : SiblingAccess::SetPrev(aElm, nullptr);
338 0 : }
339 :
340 : /**
341 : * Returns an iterator referencing the first found element whose value matches
342 : * the given element according to operator==.
343 : */
344 : Iterator find(const T& aElm) {
345 : return std::find(begin(), end(), aElm);
346 : }
347 :
348 : /**
349 : * Returns whether the given element is in the list. Note that this uses
350 : * T::operator==, not pointer comparison.
351 : */
352 : bool contains(const T& aElm) {
353 : return find(aElm) != Iterator();
354 : }
355 : };
356 :
357 : } // namespace mozilla
358 :
359 : #endif // mozilla_DoublyLinkedList_h
|
