mfbt/LinkedList.h@97036ab72558
mfbt/LinkedList.h
Tue, 06 Jan 2015 21:39:09 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Tue, 06 Jan 2015 21:39:09 +0100
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
- permissions
- -rw-r--r--
Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.
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. */
9 /*
10 * The classes LinkedList<T> and LinkedListElement<T> together form a
11 * convenient, type-safe doubly-linked list implementation.
12 *
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
15 * time.
16 *
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.
20 *
21 * For example, you might use LinkedList in a simple observer list class as
22 * follows.
23 *
24 * class Observer : public LinkedListElement<Observer>
25 * {
26 * public:
27 * void observe(char* topic) { ... }
28 * };
29 *
30 * class ObserverContainer
31 * {
32 * private:
33 * LinkedList<Observer> list;
34 *
35 * public:
36 * void addObserver(Observer* observer) {
37 * // Will assert if |observer| is part of another list.
38 * list.insertBack(observer);
39 * }
40 *
41 * void removeObserver(Observer* observer) {
42 * // Will assert if |observer| is not part of some list.
43 * observer.remove();
44 * // Or, will assert if |observer| is not part of |list| specifically.
45 * // observer.removeFrom(list);
46 * }
47 *
48 * void notifyObservers(char* topic) {
49 * for (Observer* o = list.getFirst(); o != nullptr; o = o->getNext())
50 * o->observe(topic);
51 * }
52 * };
53 *
54 */
56 #ifndef mozilla_LinkedList_h
57 #define mozilla_LinkedList_h
59 #include "mozilla/Assertions.h"
60 #include "mozilla/Attributes.h"
61 #include "mozilla/MemoryReporting.h"
62 #include "mozilla/Move.h"
63 #include "mozilla/NullPtr.h"
65 #ifdef __cplusplus
67 namespace mozilla {
69 template<typename T>
70 class LinkedList;
72 template<typename T>
73 class LinkedListElement
74 {
75 /*
76 * It's convenient that we return nullptr when getNext() or getPrevious()
77 * hits the end of the list, but doing so costs an extra word of storage in
78 * each linked list node (to keep track of whether |this| is the sentinel
79 * node) and a branch on this value in getNext/getPrevious.
80 *
81 * We could get rid of the extra word of storage by shoving the "is
82 * sentinel" bit into one of the pointers, although this would, of course,
83 * have performance implications of its own.
84 *
85 * But the goal here isn't to win an award for the fastest or slimmest
86 * linked list; rather, we want a *convenient* linked list. So we won't
87 * waste time guessing which micro-optimization strategy is best.
88 *
89 *
90 * Speaking of unnecessary work, it's worth addressing here why we wrote
91 * mozilla::LinkedList in the first place, instead of using stl::list.
92 *
93 * The key difference between mozilla::LinkedList and stl::list is that
94 * mozilla::LinkedList stores the prev/next pointers in the object itself,
95 * while stl::list stores the prev/next pointers in a list element which
96 * itself points to the object being stored.
97 *
98 * mozilla::LinkedList's approach makes it harder to store an object in more
99 * than one list. But the upside is that you can call next() / prev() /
100 * remove() directly on the object. With stl::list, you'd need to store a
101 * pointer to its iterator in the object in order to accomplish this. Not
102 * only would this waste space, but you'd have to remember to update that
103 * pointer every time you added or removed the object from a list.
104 *
105 * In-place, constant-time removal is a killer feature of doubly-linked
106 * lists, and supporting this painlessly was a key design criterion.
107 */
109 private:
110 LinkedListElement* next;
111 LinkedListElement* prev;
112 const bool isSentinel;
114 public:
115 LinkedListElement()
116 : next(MOZ_THIS_IN_INITIALIZER_LIST()),
117 prev(MOZ_THIS_IN_INITIALIZER_LIST()),
118 isSentinel(false)
119 { }
121 LinkedListElement(LinkedListElement<T>&& other)
122 : isSentinel(other.isSentinel)
123 {
124 if (!other.isInList()) {
125 next = this;
126 prev = this;
127 return;
128 }
130 MOZ_ASSERT(other.next->prev == &other);
131 MOZ_ASSERT(other.prev->next == &other);
133 /*
134 * Initialize |this| with |other|'s prev/next pointers, and adjust those
135 * element to point to this one.
136 */
137 next = other.next;
138 prev = other.prev;
140 next->prev = this;
141 prev->next = this;
143 /*
144 * Adjust |other| so it doesn't think it's in a list. This makes it
145 * safely destructable.
146 */
147 other.next = &other;
148 other.prev = &other;
149 }
151 ~LinkedListElement() {
152 if (!isSentinel && isInList())
153 remove();
154 }
156 /*
157 * Get the next element in the list, or nullptr if this is the last element
158 * in the list.
159 */
160 T* getNext() {
161 return next->asT();
162 }
163 const T* getNext() const {
164 return next->asT();
165 }
167 /*
168 * Get the previous element in the list, or nullptr if this is the first
169 * element in the list.
170 */
171 T* getPrevious() {
172 return prev->asT();
173 }
174 const T* getPrevious() const {
175 return prev->asT();
176 }
178 /*
179 * Insert elem after this element in the list. |this| must be part of a
180 * linked list when you call setNext(); otherwise, this method will assert.
181 */
182 void setNext(T* elem) {
183 MOZ_ASSERT(isInList());
184 setNextUnsafe(elem);
185 }
187 /*
188 * Insert elem before this element in the list. |this| must be part of a
189 * linked list when you call setPrevious(); otherwise, this method will
190 * assert.
191 */
192 void setPrevious(T* elem) {
193 MOZ_ASSERT(isInList());
194 setPreviousUnsafe(elem);
195 }
197 /*
198 * Remove this element from the list which contains it. If this element is
199 * not currently part of a linked list, this method asserts.
200 */
201 void remove() {
202 MOZ_ASSERT(isInList());
204 prev->next = next;
205 next->prev = prev;
206 next = this;
207 prev = this;
208 }
210 /*
211 * Identical to remove(), but also asserts in debug builds that this element
212 * is in list.
213 */
214 void removeFrom(const LinkedList<T>& list) {
215 list.assertContains(asT());
216 remove();
217 }
219 /*
220 * Return true if |this| part is of a linked list, and false otherwise.
221 */
222 bool isInList() const {
223 MOZ_ASSERT((next == this) == (prev == this));
224 return next != this;
225 }
227 private:
228 friend class LinkedList<T>;
230 enum NodeKind {
231 NODE_KIND_NORMAL,
232 NODE_KIND_SENTINEL
233 };
235 LinkedListElement(NodeKind nodeKind)
236 : next(MOZ_THIS_IN_INITIALIZER_LIST()),
237 prev(MOZ_THIS_IN_INITIALIZER_LIST()),
238 isSentinel(nodeKind == NODE_KIND_SENTINEL)
239 { }
241 /*
242 * Return |this| cast to T* if we're a normal node, or return nullptr if
243 * we're a sentinel node.
244 */
245 T* asT() {
246 if (isSentinel)
247 return nullptr;
249 return static_cast<T*>(this);
250 }
251 const T* asT() const {
252 if (isSentinel)
253 return nullptr;
255 return static_cast<const T*>(this);
256 }
258 /*
259 * Insert elem after this element, but don't check that this element is in
260 * the list. This is called by LinkedList::insertFront().
261 */
262 void setNextUnsafe(T* elem) {
263 LinkedListElement *listElem = static_cast<LinkedListElement*>(elem);
264 MOZ_ASSERT(!listElem->isInList());
266 listElem->next = this->next;
267 listElem->prev = this;
268 this->next->prev = listElem;
269 this->next = listElem;
270 }
272 /*
273 * Insert elem before this element, but don't check that this element is in
274 * the list. This is called by LinkedList::insertBack().
275 */
276 void setPreviousUnsafe(T* elem) {
277 LinkedListElement<T>* listElem = static_cast<LinkedListElement<T>*>(elem);
278 MOZ_ASSERT(!listElem->isInList());
280 listElem->next = this;
281 listElem->prev = this->prev;
282 this->prev->next = listElem;
283 this->prev = listElem;
284 }
286 private:
287 LinkedListElement& operator=(const LinkedListElement<T>& other) MOZ_DELETE;
288 LinkedListElement(const LinkedListElement<T>& other) MOZ_DELETE;
289 };
291 template<typename T>
292 class LinkedList
293 {
294 private:
295 LinkedListElement<T> sentinel;
297 public:
298 LinkedList() : sentinel(LinkedListElement<T>::NODE_KIND_SENTINEL) { }
300 LinkedList(LinkedList<T>&& other)
301 : sentinel(mozilla::Move(other.sentinel))
302 { }
304 ~LinkedList() {
305 MOZ_ASSERT(isEmpty());
306 }
308 /*
309 * Add elem to the front of the list.
310 */
311 void insertFront(T* elem) {
312 /* Bypass setNext()'s this->isInList() assertion. */
313 sentinel.setNextUnsafe(elem);
314 }
316 /*
317 * Add elem to the back of the list.
318 */
319 void insertBack(T* elem) {
320 sentinel.setPreviousUnsafe(elem);
321 }
323 /*
324 * Get the first element of the list, or nullptr if the list is empty.
325 */
326 T* getFirst() {
327 return sentinel.getNext();
328 }
329 const T* getFirst() const {
330 return sentinel.getNext();
331 }
333 /*
334 * Get the last element of the list, or nullptr if the list is empty.
335 */
336 T* getLast() {
337 return sentinel.getPrevious();
338 }
339 const T* getLast() const {
340 return sentinel.getPrevious();
341 }
343 /*
344 * Get and remove the first element of the list. If the list is empty,
345 * return nullptr.
346 */
347 T* popFirst() {
348 T* ret = sentinel.getNext();
349 if (ret)
350 static_cast<LinkedListElement<T>*>(ret)->remove();
351 return ret;
352 }
354 /*
355 * Get and remove the last element of the list. If the list is empty,
356 * return nullptr.
357 */
358 T* popLast() {
359 T* ret = sentinel.getPrevious();
360 if (ret)
361 static_cast<LinkedListElement<T>*>(ret)->remove();
362 return ret;
363 }
365 /*
366 * Return true if the list is empty, or false otherwise.
367 */
368 bool isEmpty() const {
369 return !sentinel.isInList();
370 }
372 /*
373 * Remove all the elements from the list.
374 *
375 * This runs in time linear to the list's length, because we have to mark
376 * each element as not in the list.
377 */
378 void clear() {
379 while (popFirst())
380 continue;
381 }
383 /*
384 * Measures the memory consumption of the list excluding |this|. Note that
385 * it only measures the list elements themselves. If the list elements
386 * contain pointers to other memory blocks, those blocks must be measured
387 * separately during a subsequent iteration over the list.
388 */
389 size_t sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const {
390 size_t n = 0;
391 for (const T* t = getFirst(); t; t = t->getNext())
392 n += mallocSizeOf(t);
393 return n;
394 }
396 /*
397 * Like sizeOfExcludingThis(), but measures |this| as well.
398 */
399 size_t sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const {
400 return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
401 }
403 /*
404 * In a debug build, make sure that the list is sane (no cycles, consistent
405 * next/prev pointers, only one sentinel). Has no effect in release builds.
406 */
407 void debugAssertIsSane() const {
408 #ifdef DEBUG
409 const LinkedListElement<T>* slow;
410 const LinkedListElement<T>* fast1;
411 const LinkedListElement<T>* fast2;
413 /*
414 * Check for cycles in the forward singly-linked list using the
415 * tortoise/hare algorithm.
416 */
417 for (slow = sentinel.next,
418 fast1 = sentinel.next->next,
419 fast2 = sentinel.next->next->next;
420 slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
421 slow = slow->next, fast1 = fast2->next, fast2 = fast1->next)
422 {
423 MOZ_ASSERT(slow != fast1);
424 MOZ_ASSERT(slow != fast2);
425 }
427 /* Check for cycles in the backward singly-linked list. */
428 for (slow = sentinel.prev,
429 fast1 = sentinel.prev->prev,
430 fast2 = sentinel.prev->prev->prev;
431 slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
432 slow = slow->prev, fast1 = fast2->prev, fast2 = fast1->prev)
433 {
434 MOZ_ASSERT(slow != fast1);
435 MOZ_ASSERT(slow != fast2);
436 }
438 /*
439 * Check that |sentinel| is the only node in the list with
440 * isSentinel == true.
441 */
442 for (const LinkedListElement<T>* elem = sentinel.next;
443 elem != &sentinel;
444 elem = elem->next)
445 {
446 MOZ_ASSERT(!elem->isSentinel);
447 }
449 /* Check that the next/prev pointers match up. */
450 const LinkedListElement<T>* prev = &sentinel;
451 const LinkedListElement<T>* cur = sentinel.next;
452 do {
453 MOZ_ASSERT(cur->prev == prev);
454 MOZ_ASSERT(prev->next == cur);
456 prev = cur;
457 cur = cur->next;
458 } while (cur != &sentinel);
459 #endif /* ifdef DEBUG */
460 }
462 private:
463 friend class LinkedListElement<T>;
465 void assertContains(const T* t) const {
466 #ifdef DEBUG
467 for (const T* elem = getFirst();
468 elem;
469 elem = elem->getNext())
470 {
471 if (elem == t)
472 return;
473 }
474 MOZ_CRASH("element wasn't found in this list!");
475 #endif
476 }
478 LinkedList& operator=(const LinkedList<T>& other) MOZ_DELETE;
479 LinkedList(const LinkedList<T>& other) MOZ_DELETE;
480 };
482 } /* namespace mozilla */
484 #endif /* __cplusplus */
486 #endif /* mozilla_LinkedList_h */
