1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/LinkedList.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,486 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set ts=8 sts=2 et sw=2 tw=80: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/* A type-safe doubly-linked list class. */
1.11 +
1.12 +/*
1.13 + * The classes LinkedList<T> and LinkedListElement<T> together form a
1.14 + * convenient, type-safe doubly-linked list implementation.
1.15 + *
1.16 + * The class T which will be inserted into the linked list must inherit from
1.17 + * LinkedListElement<T>. A given object may be in only one linked list at a
1.18 + * time.
1.19 + *
1.20 + * A LinkedListElement automatically removes itself from the list upon
1.21 + * destruction, and a LinkedList will fatally assert in debug builds if it's
1.22 + * non-empty when it's destructed.
1.23 + *
1.24 + * For example, you might use LinkedList in a simple observer list class as
1.25 + * follows.
1.26 + *
1.27 + * class Observer : public LinkedListElement<Observer>
1.28 + * {
1.29 + * public:
1.30 + * void observe(char* topic) { ... }
1.31 + * };
1.32 + *
1.33 + * class ObserverContainer
1.34 + * {
1.35 + * private:
1.36 + * LinkedList<Observer> list;
1.37 + *
1.38 + * public:
1.39 + * void addObserver(Observer* observer) {
1.40 + * // Will assert if |observer| is part of another list.
1.41 + * list.insertBack(observer);
1.42 + * }
1.43 + *
1.44 + * void removeObserver(Observer* observer) {
1.45 + * // Will assert if |observer| is not part of some list.
1.46 + * observer.remove();
1.47 + * // Or, will assert if |observer| is not part of |list| specifically.
1.48 + * // observer.removeFrom(list);
1.49 + * }
1.50 + *
1.51 + * void notifyObservers(char* topic) {
1.52 + * for (Observer* o = list.getFirst(); o != nullptr; o = o->getNext())
1.53 + * o->observe(topic);
1.54 + * }
1.55 + * };
1.56 + *
1.57 + */
1.58 +
1.59 +#ifndef mozilla_LinkedList_h
1.60 +#define mozilla_LinkedList_h
1.61 +
1.62 +#include "mozilla/Assertions.h"
1.63 +#include "mozilla/Attributes.h"
1.64 +#include "mozilla/MemoryReporting.h"
1.65 +#include "mozilla/Move.h"
1.66 +#include "mozilla/NullPtr.h"
1.67 +
1.68 +#ifdef __cplusplus
1.69 +
1.70 +namespace mozilla {
1.71 +
1.72 +template<typename T>
1.73 +class LinkedList;
1.74 +
1.75 +template<typename T>
1.76 +class LinkedListElement
1.77 +{
1.78 + /*
1.79 + * It's convenient that we return nullptr when getNext() or getPrevious()
1.80 + * hits the end of the list, but doing so costs an extra word of storage in
1.81 + * each linked list node (to keep track of whether |this| is the sentinel
1.82 + * node) and a branch on this value in getNext/getPrevious.
1.83 + *
1.84 + * We could get rid of the extra word of storage by shoving the "is
1.85 + * sentinel" bit into one of the pointers, although this would, of course,
1.86 + * have performance implications of its own.
1.87 + *
1.88 + * But the goal here isn't to win an award for the fastest or slimmest
1.89 + * linked list; rather, we want a *convenient* linked list. So we won't
1.90 + * waste time guessing which micro-optimization strategy is best.
1.91 + *
1.92 + *
1.93 + * Speaking of unnecessary work, it's worth addressing here why we wrote
1.94 + * mozilla::LinkedList in the first place, instead of using stl::list.
1.95 + *
1.96 + * The key difference between mozilla::LinkedList and stl::list is that
1.97 + * mozilla::LinkedList stores the prev/next pointers in the object itself,
1.98 + * while stl::list stores the prev/next pointers in a list element which
1.99 + * itself points to the object being stored.
1.100 + *
1.101 + * mozilla::LinkedList's approach makes it harder to store an object in more
1.102 + * than one list. But the upside is that you can call next() / prev() /
1.103 + * remove() directly on the object. With stl::list, you'd need to store a
1.104 + * pointer to its iterator in the object in order to accomplish this. Not
1.105 + * only would this waste space, but you'd have to remember to update that
1.106 + * pointer every time you added or removed the object from a list.
1.107 + *
1.108 + * In-place, constant-time removal is a killer feature of doubly-linked
1.109 + * lists, and supporting this painlessly was a key design criterion.
1.110 + */
1.111 +
1.112 + private:
1.113 + LinkedListElement* next;
1.114 + LinkedListElement* prev;
1.115 + const bool isSentinel;
1.116 +
1.117 + public:
1.118 + LinkedListElement()
1.119 + : next(MOZ_THIS_IN_INITIALIZER_LIST()),
1.120 + prev(MOZ_THIS_IN_INITIALIZER_LIST()),
1.121 + isSentinel(false)
1.122 + { }
1.123 +
1.124 + LinkedListElement(LinkedListElement<T>&& other)
1.125 + : isSentinel(other.isSentinel)
1.126 + {
1.127 + if (!other.isInList()) {
1.128 + next = this;
1.129 + prev = this;
1.130 + return;
1.131 + }
1.132 +
1.133 + MOZ_ASSERT(other.next->prev == &other);
1.134 + MOZ_ASSERT(other.prev->next == &other);
1.135 +
1.136 + /*
1.137 + * Initialize |this| with |other|'s prev/next pointers, and adjust those
1.138 + * element to point to this one.
1.139 + */
1.140 + next = other.next;
1.141 + prev = other.prev;
1.142 +
1.143 + next->prev = this;
1.144 + prev->next = this;
1.145 +
1.146 + /*
1.147 + * Adjust |other| so it doesn't think it's in a list. This makes it
1.148 + * safely destructable.
1.149 + */
1.150 + other.next = &other;
1.151 + other.prev = &other;
1.152 + }
1.153 +
1.154 + ~LinkedListElement() {
1.155 + if (!isSentinel && isInList())
1.156 + remove();
1.157 + }
1.158 +
1.159 + /*
1.160 + * Get the next element in the list, or nullptr if this is the last element
1.161 + * in the list.
1.162 + */
1.163 + T* getNext() {
1.164 + return next->asT();
1.165 + }
1.166 + const T* getNext() const {
1.167 + return next->asT();
1.168 + }
1.169 +
1.170 + /*
1.171 + * Get the previous element in the list, or nullptr if this is the first
1.172 + * element in the list.
1.173 + */
1.174 + T* getPrevious() {
1.175 + return prev->asT();
1.176 + }
1.177 + const T* getPrevious() const {
1.178 + return prev->asT();
1.179 + }
1.180 +
1.181 + /*
1.182 + * Insert elem after this element in the list. |this| must be part of a
1.183 + * linked list when you call setNext(); otherwise, this method will assert.
1.184 + */
1.185 + void setNext(T* elem) {
1.186 + MOZ_ASSERT(isInList());
1.187 + setNextUnsafe(elem);
1.188 + }
1.189 +
1.190 + /*
1.191 + * Insert elem before this element in the list. |this| must be part of a
1.192 + * linked list when you call setPrevious(); otherwise, this method will
1.193 + * assert.
1.194 + */
1.195 + void setPrevious(T* elem) {
1.196 + MOZ_ASSERT(isInList());
1.197 + setPreviousUnsafe(elem);
1.198 + }
1.199 +
1.200 + /*
1.201 + * Remove this element from the list which contains it. If this element is
1.202 + * not currently part of a linked list, this method asserts.
1.203 + */
1.204 + void remove() {
1.205 + MOZ_ASSERT(isInList());
1.206 +
1.207 + prev->next = next;
1.208 + next->prev = prev;
1.209 + next = this;
1.210 + prev = this;
1.211 + }
1.212 +
1.213 + /*
1.214 + * Identical to remove(), but also asserts in debug builds that this element
1.215 + * is in list.
1.216 + */
1.217 + void removeFrom(const LinkedList<T>& list) {
1.218 + list.assertContains(asT());
1.219 + remove();
1.220 + }
1.221 +
1.222 + /*
1.223 + * Return true if |this| part is of a linked list, and false otherwise.
1.224 + */
1.225 + bool isInList() const {
1.226 + MOZ_ASSERT((next == this) == (prev == this));
1.227 + return next != this;
1.228 + }
1.229 +
1.230 + private:
1.231 + friend class LinkedList<T>;
1.232 +
1.233 + enum NodeKind {
1.234 + NODE_KIND_NORMAL,
1.235 + NODE_KIND_SENTINEL
1.236 + };
1.237 +
1.238 + LinkedListElement(NodeKind nodeKind)
1.239 + : next(MOZ_THIS_IN_INITIALIZER_LIST()),
1.240 + prev(MOZ_THIS_IN_INITIALIZER_LIST()),
1.241 + isSentinel(nodeKind == NODE_KIND_SENTINEL)
1.242 + { }
1.243 +
1.244 + /*
1.245 + * Return |this| cast to T* if we're a normal node, or return nullptr if
1.246 + * we're a sentinel node.
1.247 + */
1.248 + T* asT() {
1.249 + if (isSentinel)
1.250 + return nullptr;
1.251 +
1.252 + return static_cast<T*>(this);
1.253 + }
1.254 + const T* asT() const {
1.255 + if (isSentinel)
1.256 + return nullptr;
1.257 +
1.258 + return static_cast<const T*>(this);
1.259 + }
1.260 +
1.261 + /*
1.262 + * Insert elem after this element, but don't check that this element is in
1.263 + * the list. This is called by LinkedList::insertFront().
1.264 + */
1.265 + void setNextUnsafe(T* elem) {
1.266 + LinkedListElement *listElem = static_cast<LinkedListElement*>(elem);
1.267 + MOZ_ASSERT(!listElem->isInList());
1.268 +
1.269 + listElem->next = this->next;
1.270 + listElem->prev = this;
1.271 + this->next->prev = listElem;
1.272 + this->next = listElem;
1.273 + }
1.274 +
1.275 + /*
1.276 + * Insert elem before this element, but don't check that this element is in
1.277 + * the list. This is called by LinkedList::insertBack().
1.278 + */
1.279 + void setPreviousUnsafe(T* elem) {
1.280 + LinkedListElement<T>* listElem = static_cast<LinkedListElement<T>*>(elem);
1.281 + MOZ_ASSERT(!listElem->isInList());
1.282 +
1.283 + listElem->next = this;
1.284 + listElem->prev = this->prev;
1.285 + this->prev->next = listElem;
1.286 + this->prev = listElem;
1.287 + }
1.288 +
1.289 + private:
1.290 + LinkedListElement& operator=(const LinkedListElement<T>& other) MOZ_DELETE;
1.291 + LinkedListElement(const LinkedListElement<T>& other) MOZ_DELETE;
1.292 +};
1.293 +
1.294 +template<typename T>
1.295 +class LinkedList
1.296 +{
1.297 + private:
1.298 + LinkedListElement<T> sentinel;
1.299 +
1.300 + public:
1.301 + LinkedList() : sentinel(LinkedListElement<T>::NODE_KIND_SENTINEL) { }
1.302 +
1.303 + LinkedList(LinkedList<T>&& other)
1.304 + : sentinel(mozilla::Move(other.sentinel))
1.305 + { }
1.306 +
1.307 + ~LinkedList() {
1.308 + MOZ_ASSERT(isEmpty());
1.309 + }
1.310 +
1.311 + /*
1.312 + * Add elem to the front of the list.
1.313 + */
1.314 + void insertFront(T* elem) {
1.315 + /* Bypass setNext()'s this->isInList() assertion. */
1.316 + sentinel.setNextUnsafe(elem);
1.317 + }
1.318 +
1.319 + /*
1.320 + * Add elem to the back of the list.
1.321 + */
1.322 + void insertBack(T* elem) {
1.323 + sentinel.setPreviousUnsafe(elem);
1.324 + }
1.325 +
1.326 + /*
1.327 + * Get the first element of the list, or nullptr if the list is empty.
1.328 + */
1.329 + T* getFirst() {
1.330 + return sentinel.getNext();
1.331 + }
1.332 + const T* getFirst() const {
1.333 + return sentinel.getNext();
1.334 + }
1.335 +
1.336 + /*
1.337 + * Get the last element of the list, or nullptr if the list is empty.
1.338 + */
1.339 + T* getLast() {
1.340 + return sentinel.getPrevious();
1.341 + }
1.342 + const T* getLast() const {
1.343 + return sentinel.getPrevious();
1.344 + }
1.345 +
1.346 + /*
1.347 + * Get and remove the first element of the list. If the list is empty,
1.348 + * return nullptr.
1.349 + */
1.350 + T* popFirst() {
1.351 + T* ret = sentinel.getNext();
1.352 + if (ret)
1.353 + static_cast<LinkedListElement<T>*>(ret)->remove();
1.354 + return ret;
1.355 + }
1.356 +
1.357 + /*
1.358 + * Get and remove the last element of the list. If the list is empty,
1.359 + * return nullptr.
1.360 + */
1.361 + T* popLast() {
1.362 + T* ret = sentinel.getPrevious();
1.363 + if (ret)
1.364 + static_cast<LinkedListElement<T>*>(ret)->remove();
1.365 + return ret;
1.366 + }
1.367 +
1.368 + /*
1.369 + * Return true if the list is empty, or false otherwise.
1.370 + */
1.371 + bool isEmpty() const {
1.372 + return !sentinel.isInList();
1.373 + }
1.374 +
1.375 + /*
1.376 + * Remove all the elements from the list.
1.377 + *
1.378 + * This runs in time linear to the list's length, because we have to mark
1.379 + * each element as not in the list.
1.380 + */
1.381 + void clear() {
1.382 + while (popFirst())
1.383 + continue;
1.384 + }
1.385 +
1.386 + /*
1.387 + * Measures the memory consumption of the list excluding |this|. Note that
1.388 + * it only measures the list elements themselves. If the list elements
1.389 + * contain pointers to other memory blocks, those blocks must be measured
1.390 + * separately during a subsequent iteration over the list.
1.391 + */
1.392 + size_t sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const {
1.393 + size_t n = 0;
1.394 + for (const T* t = getFirst(); t; t = t->getNext())
1.395 + n += mallocSizeOf(t);
1.396 + return n;
1.397 + }
1.398 +
1.399 + /*
1.400 + * Like sizeOfExcludingThis(), but measures |this| as well.
1.401 + */
1.402 + size_t sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const {
1.403 + return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
1.404 + }
1.405 +
1.406 + /*
1.407 + * In a debug build, make sure that the list is sane (no cycles, consistent
1.408 + * next/prev pointers, only one sentinel). Has no effect in release builds.
1.409 + */
1.410 + void debugAssertIsSane() const {
1.411 +#ifdef DEBUG
1.412 + const LinkedListElement<T>* slow;
1.413 + const LinkedListElement<T>* fast1;
1.414 + const LinkedListElement<T>* fast2;
1.415 +
1.416 + /*
1.417 + * Check for cycles in the forward singly-linked list using the
1.418 + * tortoise/hare algorithm.
1.419 + */
1.420 + for (slow = sentinel.next,
1.421 + fast1 = sentinel.next->next,
1.422 + fast2 = sentinel.next->next->next;
1.423 + slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
1.424 + slow = slow->next, fast1 = fast2->next, fast2 = fast1->next)
1.425 + {
1.426 + MOZ_ASSERT(slow != fast1);
1.427 + MOZ_ASSERT(slow != fast2);
1.428 + }
1.429 +
1.430 + /* Check for cycles in the backward singly-linked list. */
1.431 + for (slow = sentinel.prev,
1.432 + fast1 = sentinel.prev->prev,
1.433 + fast2 = sentinel.prev->prev->prev;
1.434 + slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
1.435 + slow = slow->prev, fast1 = fast2->prev, fast2 = fast1->prev)
1.436 + {
1.437 + MOZ_ASSERT(slow != fast1);
1.438 + MOZ_ASSERT(slow != fast2);
1.439 + }
1.440 +
1.441 + /*
1.442 + * Check that |sentinel| is the only node in the list with
1.443 + * isSentinel == true.
1.444 + */
1.445 + for (const LinkedListElement<T>* elem = sentinel.next;
1.446 + elem != &sentinel;
1.447 + elem = elem->next)
1.448 + {
1.449 + MOZ_ASSERT(!elem->isSentinel);
1.450 + }
1.451 +
1.452 + /* Check that the next/prev pointers match up. */
1.453 + const LinkedListElement<T>* prev = &sentinel;
1.454 + const LinkedListElement<T>* cur = sentinel.next;
1.455 + do {
1.456 + MOZ_ASSERT(cur->prev == prev);
1.457 + MOZ_ASSERT(prev->next == cur);
1.458 +
1.459 + prev = cur;
1.460 + cur = cur->next;
1.461 + } while (cur != &sentinel);
1.462 +#endif /* ifdef DEBUG */
1.463 + }
1.464 +
1.465 + private:
1.466 + friend class LinkedListElement<T>;
1.467 +
1.468 + void assertContains(const T* t) const {
1.469 +#ifdef DEBUG
1.470 + for (const T* elem = getFirst();
1.471 + elem;
1.472 + elem = elem->getNext())
1.473 + {
1.474 + if (elem == t)
1.475 + return;
1.476 + }
1.477 + MOZ_CRASH("element wasn't found in this list!");
1.478 +#endif
1.479 + }
1.480 +
1.481 + LinkedList& operator=(const LinkedList<T>& other) MOZ_DELETE;
1.482 + LinkedList(const LinkedList<T>& other) MOZ_DELETE;
1.483 +};
1.484 +
1.485 +} /* namespace mozilla */
1.486 +
1.487 +#endif /* __cplusplus */
1.488 +
1.489 +#endif /* mozilla_LinkedList_h */
