mfbt/LinkedList.h

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this
   4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6 /* A type-safe doubly-linked list class. */
   7
   8 /*
   9  * The classes LinkedList<T> and LinkedListElement<T> together form a
  10  * convenient, type-safe doubly-linked list implementation.
  11  *
  12  * The class T which will be inserted into the linked list must inherit from
  13  * LinkedListElement<T>.  A given object may be in only one linked list at a
  14  * time.
  15  *
  16  * A LinkedListElement automatically removes itself from the list upon
  17  * destruction, and a LinkedList will fatally assert in debug builds if it's
  18  * non-empty when it's destructed.
  19  *
  20  * For example, you might use LinkedList in a simple observer list class as
  21  * follows.
  22  *
  23  *   class Observer : public LinkedListElement<Observer>
  24  *   {
  25  *     public:
  26  *       void observe(char* topic) { ... }
  27  *   };
  28  *
  29  *   class ObserverContainer
  30  *   {
  31  *     private:
  32  *       LinkedList<Observer> list;
  33  *
  34  *     public:
  35  *       void addObserver(Observer* observer) {
  36  *         // Will assert if |observer| is part of another list.
  37  *         list.insertBack(observer);
  38  *       }
  39  *
  40  *       void removeObserver(Observer* observer) {
  41  *         // Will assert if |observer| is not part of some list.
  42  *         observer.remove();
  43  *         // Or, will assert if |observer| is not part of |list| specifically.
  44  *         // observer.removeFrom(list);
  45  *       }
  46  *
  47  *       void notifyObservers(char* topic) {
  48  *         for (Observer* o = list.getFirst(); o != NULL; o = o->getNext())
  49  *           o->Observe(topic);
  50  *       }
  51  *   };
  52  *
  53  */
  54
  55 #ifndef mozilla_LinkedList_h_
  56 #define mozilla_LinkedList_h_
  57
  58 #include "mozilla/Assertions.h"
  59 #include "mozilla/Attributes.h"
  60
  61 #ifdef __cplusplus
  62
  63 namespace mozilla {
  64
  65 template<typename T>
  66 class LinkedList;
  67
  68 template<typename T>
  69 class LinkedListElement
  70 {
  71     /*
  72      * It's convenient that we return NULL when getNext() or getPrevious() hits
  73      * the end of the list, but doing so costs an extra word of storage in each
  74      * linked list node (to keep track of whether |this| is the sentinel node)
  75      * and a branch on this value in getNext/getPrevious.
  76      *
  77      * We could get rid of the extra word of storage by shoving the "is
  78      * sentinel" bit into one of the pointers, although this would, of course,
  79      * have performance implications of its own.
  80      *
  81      * But the goal here isn't to win an award for the fastest or slimmest
  82      * linked list; rather, we want a *convenient* linked list.  So we won't
  83      * waste time guessing which micro-optimization strategy is best.
  84      *
  85      *
  86      * Speaking of unnecessary work, it's worth addressing here why we wrote
  87      * mozilla::LinkedList in the first place, instead of using stl::list.
  88      *
  89      * The key difference between mozilla::LinkedList and stl::list is that
  90      * mozilla::LinkedList stores the prev/next pointers in the object itself,
  91      * while stl::list stores the prev/next pointers in a list element which
  92      * itself points to the object being stored.
  93      *
  94      * mozilla::LinkedList's approach makes it harder to store an object in more
  95      * than one list.  But the upside is that you can call next() / prev() /
  96      * remove() directly on the object.  With stl::list, you'd need to store a
  97      * pointer to its iterator in the object in order to accomplish this.  Not
  98      * only would this waste space, but you'd have to remember to update that
  99      * pointer every time you added or removed the object from a list.
 100      *
 101      * In-place, constant-time removal is a killer feature of doubly-linked
 102      * lists, and supporting this painlessly was a key design criterion.
 103      */
 104
 105   private:
 106     LinkedListElement* next;
 107     LinkedListElement* prev;
 108     const bool isSentinel;
 109
 110     LinkedListElement* thisDuringConstruction() { return this; }
 111
 112   public:
 113     LinkedListElement()
 114       : next(thisDuringConstruction()),
 115         prev(thisDuringConstruction()),
 116         isSentinel(false)
 117     { }
 118
 119     ~LinkedListElement() {
 120       if (!isSentinel && isInList())
 121         remove();
 122     }
 123
 124     /*
 125      * Get the next element in the list, or NULL if this is the last element in
 126      * the list.
 127      */
 128     T* getNext() {
 129       return next->asT();
 130     }
 131     const T* getNext() const {
 132       return next->asT();
 133     }
 134
 135     /*
 136      * Get the previous element in the list, or NULL if this is the first element
 137      * in the list.
 138      */
 139     T* getPrevious() {
 140       return prev->asT();
 141     }
 142     const T* getPrevious() const {
 143       return prev->asT();
 144     }
 145
 146     /*
 147      * Insert elem after this element in the list.  |this| must be part of a
 148      * linked list when you call setNext(); otherwise, this method will assert.
 149      */
 150     void setNext(T* elem) {
 151         MOZ_ASSERT(isInList());
 152         setNextUnsafe(elem);
 153     }
 154
 155     /*
 156      * Insert elem before this element in the list.  |this| must be part of a
 157      * linked list when you call setPrevious(); otherwise, this method will
 158      * assert.
 159      */
 160     void setPrevious(T* elem) {
 161       MOZ_ASSERT(isInList());
 162       setPreviousUnsafe(elem);
 163     }
 164
 165     /*
 166      * Remove this element from the list which contains it.  If this element is
 167      * not currently part of a linked list, this method asserts.
 168      */
 169     void remove() {
 170       MOZ_ASSERT(isInList());
 171
 172       prev->next = next;
 173       next->prev = prev;
 174       next = this;
 175       prev = this;
 176     }
 177
 178     /*
 179      * Identical to remove(), but also asserts in debug builds that this element
 180      * is in list.
 181      */
 182     void removeFrom(const LinkedList<T>& list) {
 183       list.assertContains(asT());
 184       remove();
 185     }
 186
 187     /*
 188      * Return true if |this| part is of a linked list, and false otherwise.
 189      */
 190     bool isInList() const {
 191       MOZ_ASSERT((next == this) == (prev == this));
 192       return next != this;
 193     }
 194
 195   private:
 196     friend class LinkedList<T>;
 197
 198     enum NodeKind {
 199       NODE_KIND_NORMAL,
 200       NODE_KIND_SENTINEL
 201     };
 202
 203     LinkedListElement(NodeKind nodeKind)
 204       : next(thisDuringConstruction()),
 205         prev(thisDuringConstruction()),
 206         isSentinel(nodeKind == NODE_KIND_SENTINEL)
 207     { }
 208
 209     /*
 210      * Return |this| cast to T* if we're a normal node, or return NULL if we're
 211      * a sentinel node.
 212      */
 213     T* asT() {
 214       if (isSentinel)
 215         return NULL;
 216
 217       return static_cast<T*>(this);
 218     }
 219     const T* asT() const {
 220       if (isSentinel)
 221         return NULL;
 222
 223       return static_cast<const T*>(this);
 224     }
 225
 226     /*
 227      * Insert elem after this element, but don't check that this element is in
 228      * the list.  This is called by LinkedList::insertFront().
 229      */
 230     void setNextUnsafe(T* elem) {
 231       LinkedListElement *listElem = static_cast<LinkedListElement*>(elem);
 232       MOZ_ASSERT(!listElem->isInList());
 233
 234       listElem->next = this->next;
 235       listElem->prev = this;
 236       this->next->prev = listElem;
 237       this->next = listElem;
 238     }
 239
 240     /*
 241      * Insert elem before this element, but don't check that this element is in
 242      * the list.  This is called by LinkedList::insertBack().
 243      */
 244     void setPreviousUnsafe(T* elem) {
 245       LinkedListElement<T>* listElem = static_cast<LinkedListElement<T>*>(elem);
 246       MOZ_ASSERT(!listElem->isInList());
 247
 248       listElem->next = this;
 249       listElem->prev = this->prev;
 250       this->prev->next = listElem;
 251       this->prev = listElem;
 252     }
 253
 254   private:
 255     LinkedListElement& operator=(const LinkedList<T>& other) MOZ_DELETE;
 256     LinkedListElement(const LinkedList<T>& other) MOZ_DELETE;
 257 };
 258
 259 template<typename T>
 260 class LinkedList
 261 {
 262   private:
 263     LinkedListElement<T> sentinel;
 264
 265   public:
 266     LinkedList() : sentinel(LinkedListElement<T>::NODE_KIND_SENTINEL) { }
 267
 268     ~LinkedList() {
 269       MOZ_ASSERT(isEmpty());
 270     }
 271
 272     /*
 273      * Add elem to the front of the list.
 274      */
 275     void insertFront(T* elem) {
 276       /* Bypass setNext()'s this->isInList() assertion. */
 277       sentinel.setNextUnsafe(elem);
 278     }
 279
 280     /*
 281      * Add elem to the back of the list.
 282      */
 283     void insertBack(T* elem) {
 284       sentinel.setPreviousUnsafe(elem);
 285     }
 286
 287     /*
 288      * Get the first element of the list, or NULL if the list is empty.
 289      */
 290     T* getFirst() {
 291       return sentinel.getNext();
 292     }
 293     const T* getFirst() const {
 294       return sentinel.getNext();
 295     }
 296
 297     /*
 298      * Get the last element of the list, or NULL if the list is empty.
 299      */
 300     T* getLast() {
 301       return sentinel.getPrevious();
 302     }
 303     const T* getLast() const {
 304       return sentinel.getPrevious();
 305     }
 306
 307     /*
 308      * Get and remove the first element of the list.  If the list is empty,
 309      * return NULL.
 310      */
 311     T* popFirst() {
 312       T* ret = sentinel.getNext();
 313       if (ret)
 314         static_cast<LinkedListElement<T>*>(ret)->remove();
 315       return ret;
 316     }
 317
 318     /*
 319      * Get and remove the last element of the list.  If the list is empty,
 320      * return NULL.
 321      */
 322     T* popLast() {
 323       T* ret = sentinel.getPrevious();
 324       if (ret)
 325         static_cast<LinkedListElement<T>*>(ret)->remove();
 326       return ret;
 327     }
 328
 329     /*
 330      * Return true if the list is empty, or false otherwise.
 331      */
 332     bool isEmpty() const {
 333       return !sentinel.isInList();
 334     }
 335
 336     /*
 337      * Remove all the elements from the list.
 338      *
 339      * This runs in time linear to the list's length, because we have to mark
 340      * each element as not in the list.
 341      */
 342     void clear() {
 343       while (popFirst())
 344         continue;
 345     }
 346
 347     /*
 348      * In a debug build, make sure that the list is sane (no cycles, consistent
 349      * next/prev pointers, only one sentinel).  Has no effect in release builds.
 350      */
 351     void debugAssertIsSane() const {
 352 #ifdef DEBUG
 353       const LinkedListElement<T>* slow;
 354       const LinkedListElement<T>* fast1;
 355       const LinkedListElement<T>* fast2;
 356
 357       /*
 358        * Check for cycles in the forward singly-linked list using the
 359        * tortoise/hare algorithm.
 360        */
 361       for (slow = sentinel.next,
 362            fast1 = sentinel.next->next,
 363            fast2 = sentinel.next->next->next;
 364            slow != sentinel && fast1 != sentinel && fast2 != sentinel;
 365            slow = slow->next, fast1 = fast2->next, fast2 = fast1->next)
 366       {
 367         MOZ_ASSERT(slow != fast1);
 368         MOZ_ASSERT(slow != fast2);
 369       }
 370
 371       /* Check for cycles in the backward singly-linked list. */
 372       for (slow = sentinel.prev,
 373            fast1 = sentinel.prev->prev,
 374            fast2 = sentinel.prev->prev->prev;
 375            slow != sentinel && fast1 != sentinel && fast2 != sentinel;
 376            slow = slow->prev, fast1 = fast2->prev, fast2 = fast1->prev)
 377       {
 378         MOZ_ASSERT(slow != fast1);
 379         MOZ_ASSERT(slow != fast2);
 380       }
 381
 382       /*
 383        * Check that |sentinel| is the only node in the list with
 384        * isSentinel == true.
 385        */
 386       for (const LinkedListElement<T>* elem = sentinel.next;
 387            elem != sentinel;
 388            elem = elem->next)
 389       {
 390         MOZ_ASSERT(!elem->isSentinel);
 391       }
 392
 393       /* Check that the next/prev pointers match up. */
 394       const LinkedListElement<T>* prev = sentinel;
 395       const LinkedListElement<T>* cur = sentinel.next;
 396       do {
 397           MOZ_ASSERT(cur->prev == prev);
 398           MOZ_ASSERT(prev->next == cur);
 399
 400           prev = cur;
 401           cur = cur->next;
 402       } while (cur != sentinel);
 403 #endif /* ifdef DEBUG */
 404     }
 405
 406   private:
 407     friend class LinkedListElement<T>;
 408
 409     void assertContains(const T* t) const {
 410 #ifdef DEBUG
 411       for (const T* elem = getFirst();
 412            elem;
 413            elem = elem->getNext())
 414       {
 415         if (elem == t)
 416           return;
 417       }
 418       MOZ_NOT_REACHED("element wasn't found in this list!");
 419 #endif
 420     }
 421
 422     LinkedList& operator=(const LinkedList<T>& other) MOZ_DELETE;
 423     LinkedList(const LinkedList<T>& other) MOZ_DELETE;
 424 };
 425
 426 } /* namespace mozilla */
 427
 428 #endif /* ifdef __cplusplus */
 429 #endif /* ifdef mozilla_LinkedList_h_ */