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