mfbt/LinkedList.h

   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 type-safe doubly-linked list class. */
   8
   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  */
  55
  56 #ifndef mozilla_LinkedList_h
  57 #define mozilla_LinkedList_h
  58
  59 #include "mozilla/Assertions.h"
  60 #include "mozilla/Attributes.h"
  61 #include "mozilla/Move.h"
  62 #include "mozilla/NullPtr.h"
  63
  64 #ifdef __cplusplus
  65
  66 namespace mozilla {
  67
  68 template<typename T>
  69 class LinkedList;
  70
  71 template<typename T>
  72 class LinkedListElement
  73 {
  74     /*
  75      * It's convenient that we return nullptr when getNext() or getPrevious()
  76      * hits the end of the list, but doing so costs an extra word of storage in
  77      * each linked list node (to keep track of whether |this| is the sentinel
  78      * node) and a branch on this value in getNext/getPrevious.
  79      *
  80      * We could get rid of the extra word of storage by shoving the "is
  81      * sentinel" bit into one of the pointers, although this would, of course,
  82      * have performance implications of its own.
  83      *
  84      * But the goal here isn't to win an award for the fastest or slimmest
  85      * linked list; rather, we want a *convenient* linked list.  So we won't
  86      * waste time guessing which micro-optimization strategy is best.
  87      *
  88      *
  89      * Speaking of unnecessary work, it's worth addressing here why we wrote
  90      * mozilla::LinkedList in the first place, instead of using stl::list.
  91      *
  92      * The key difference between mozilla::LinkedList and stl::list is that
  93      * mozilla::LinkedList stores the prev/next pointers in the object itself,
  94      * while stl::list stores the prev/next pointers in a list element which
  95      * itself points to the object being stored.
  96      *
  97      * mozilla::LinkedList's approach makes it harder to store an object in more
  98      * than one list.  But the upside is that you can call next() / prev() /
  99      * remove() directly on the object.  With stl::list, you'd need to store a
 100      * pointer to its iterator in the object in order to accomplish this.  Not
 101      * only would this waste space, but you'd have to remember to update that
 102      * pointer every time you added or removed the object from a list.
 103      *
 104      * In-place, constant-time removal is a killer feature of doubly-linked
 105      * lists, and supporting this painlessly was a key design criterion.
 106      */
 107
 108   private:
 109     LinkedListElement* next;
 110     LinkedListElement* prev;
 111     const bool isSentinel;
 112
 113   public:
 114     LinkedListElement()
 115       : next(MOZ_THIS_IN_INITIALIZER_LIST()),
 116         prev(MOZ_THIS_IN_INITIALIZER_LIST()),
 117         isSentinel(false)
 118     { }
 119
 120     LinkedListElement(LinkedListElement<T>&& other)
 121       : isSentinel(other.isSentinel)
 122     {
 123       if (!other.isInList()) {
 124         next = this;
 125         prev = this;
 126         return;
 127       }
 128
 129       MOZ_ASSERT(other.next->prev == &other);
 130       MOZ_ASSERT(other.prev->next == &other);
 131
 132       /*
 133        * Initialize |this| with |other|'s prev/next pointers, and adjust those
 134        * element to point to this one.
 135        */
 136       next = other.next;
 137       prev = other.prev;
 138
 139       next->prev = this;
 140       prev->next = this;
 141
 142       /*
 143        * Adjust |other| so it doesn't think it's in a list.  This makes it
 144        * safely destructable.
 145        */
 146       other.next = &other;
 147       other.prev = &other;
 148     }
 149
 150     ~LinkedListElement() {
 151       if (!isSentinel && isInList())
 152         remove();
 153     }
 154
 155     /*
 156      * Get the next element in the list, or nullptr if this is the last element
 157      * in the list.
 158      */
 159     T* getNext() {
 160       return next->asT();
 161     }
 162     const T* getNext() const {
 163       return next->asT();
 164     }
 165
 166     /*
 167      * Get the previous element in the list, or nullptr if this is the first
 168      * element in the list.
 169      */
 170     T* getPrevious() {
 171       return prev->asT();
 172     }
 173     const T* getPrevious() const {
 174       return prev->asT();
 175     }
 176
 177     /*
 178      * Insert elem after this element in the list.  |this| must be part of a
 179      * linked list when you call setNext(); otherwise, this method will assert.
 180      */
 181     void setNext(T* elem) {
 182       MOZ_ASSERT(isInList());
 183       setNextUnsafe(elem);
 184     }
 185
 186     /*
 187      * Insert elem before this element in the list.  |this| must be part of a
 188      * linked list when you call setPrevious(); otherwise, this method will
 189      * assert.
 190      */
 191     void setPrevious(T* elem) {
 192       MOZ_ASSERT(isInList());
 193       setPreviousUnsafe(elem);
 194     }
 195
 196     /*
 197      * Remove this element from the list which contains it.  If this element is
 198      * not currently part of a linked list, this method asserts.
 199      */
 200     void remove() {
 201       MOZ_ASSERT(isInList());
 202
 203       prev->next = next;
 204       next->prev = prev;
 205       next = this;
 206       prev = this;
 207     }
 208
 209     /*
 210      * Identical to remove(), but also asserts in debug builds that this element
 211      * is in list.
 212      */
 213     void removeFrom(const LinkedList<T>& list) {
 214       list.assertContains(asT());
 215       remove();
 216     }
 217
 218     /*
 219      * Return true if |this| part is of a linked list, and false otherwise.
 220      */
 221     bool isInList() const {
 222       MOZ_ASSERT((next == this) == (prev == this));
 223       return next != this;
 224     }
 225
 226   private:
 227     friend class LinkedList<T>;
 228
 229     enum NodeKind {
 230       NODE_KIND_NORMAL,
 231       NODE_KIND_SENTINEL
 232     };
 233
 234     LinkedListElement(NodeKind nodeKind)
 235       : next(MOZ_THIS_IN_INITIALIZER_LIST()),
 236         prev(MOZ_THIS_IN_INITIALIZER_LIST()),
 237         isSentinel(nodeKind == NODE_KIND_SENTINEL)
 238     { }
 239
 240     /*
 241      * Return |this| cast to T* if we're a normal node, or return nullptr if
 242      * we're a sentinel node.
 243      */
 244     T* asT() {
 245       if (isSentinel)
 246         return nullptr;
 247
 248       return static_cast<T*>(this);
 249     }
 250     const T* asT() const {
 251       if (isSentinel)
 252         return nullptr;
 253
 254       return static_cast<const T*>(this);
 255     }
 256
 257     /*
 258      * Insert elem after this element, but don't check that this element is in
 259      * the list.  This is called by LinkedList::insertFront().
 260      */
 261     void setNextUnsafe(T* elem) {
 262       LinkedListElement *listElem = static_cast<LinkedListElement*>(elem);
 263       MOZ_ASSERT(!listElem->isInList());
 264
 265       listElem->next = this->next;
 266       listElem->prev = this;
 267       this->next->prev = listElem;
 268       this->next = listElem;
 269     }
 270
 271     /*
 272      * Insert elem before this element, but don't check that this element is in
 273      * the list.  This is called by LinkedList::insertBack().
 274      */
 275     void setPreviousUnsafe(T* elem) {
 276       LinkedListElement<T>* listElem = static_cast<LinkedListElement<T>*>(elem);
 277       MOZ_ASSERT(!listElem->isInList());
 278
 279       listElem->next = this;
 280       listElem->prev = this->prev;
 281       this->prev->next = listElem;
 282       this->prev = listElem;
 283     }
 284
 285   private:
 286     LinkedListElement& operator=(const LinkedListElement<T>& other) MOZ_DELETE;
 287     LinkedListElement(const LinkedListElement<T>& other) MOZ_DELETE;
 288 };
 289
 290 template<typename T>
 291 class LinkedList
 292 {
 293   private:
 294     LinkedListElement<T> sentinel;
 295
 296   public:
 297     LinkedList() : sentinel(LinkedListElement<T>::NODE_KIND_SENTINEL) { }
 298
 299     LinkedList(LinkedList<T>&& other)
 300       : sentinel(mozilla::Move(other.sentinel))
 301     { }
 302
 303     ~LinkedList() {
 304       MOZ_ASSERT(isEmpty());
 305     }
 306
 307     /*
 308      * Add elem to the front of the list.
 309      */
 310     void insertFront(T* elem) {
 311       /* Bypass setNext()'s this->isInList() assertion. */
 312       sentinel.setNextUnsafe(elem);
 313     }
 314
 315     /*
 316      * Add elem to the back of the list.
 317      */
 318     void insertBack(T* elem) {
 319       sentinel.setPreviousUnsafe(elem);
 320     }
 321
 322     /*
 323      * Get the first element of the list, or nullptr if the list is empty.
 324      */
 325     T* getFirst() {
 326       return sentinel.getNext();
 327     }
 328     const T* getFirst() const {
 329       return sentinel.getNext();
 330     }
 331
 332     /*
 333      * Get the last element of the list, or nullptr if the list is empty.
 334      */
 335     T* getLast() {
 336       return sentinel.getPrevious();
 337     }
 338     const T* getLast() const {
 339       return sentinel.getPrevious();
 340     }
 341
 342     /*
 343      * Get and remove the first element of the list.  If the list is empty,
 344      * return nullptr.
 345      */
 346     T* popFirst() {
 347       T* ret = sentinel.getNext();
 348       if (ret)
 349         static_cast<LinkedListElement<T>*>(ret)->remove();
 350       return ret;
 351     }
 352
 353     /*
 354      * Get and remove the last element of the list.  If the list is empty,
 355      * return nullptr.
 356      */
 357     T* popLast() {
 358       T* ret = sentinel.getPrevious();
 359       if (ret)
 360         static_cast<LinkedListElement<T>*>(ret)->remove();
 361       return ret;
 362     }
 363
 364     /*
 365      * Return true if the list is empty, or false otherwise.
 366      */
 367     bool isEmpty() const {
 368       return !sentinel.isInList();
 369     }
 370
 371     /*
 372      * Remove all the elements from the list.
 373      *
 374      * This runs in time linear to the list's length, because we have to mark
 375      * each element as not in the list.
 376      */
 377     void clear() {
 378       while (popFirst())
 379         continue;
 380     }
 381
 382     /*
 383      * In a debug build, make sure that the list is sane (no cycles, consistent
 384      * next/prev pointers, only one sentinel).  Has no effect in release builds.
 385      */
 386     void debugAssertIsSane() const {
 387 #ifdef DEBUG
 388       const LinkedListElement<T>* slow;
 389       const LinkedListElement<T>* fast1;
 390       const LinkedListElement<T>* fast2;
 391
 392       /*
 393        * Check for cycles in the forward singly-linked list using the
 394        * tortoise/hare algorithm.
 395        */
 396       for (slow = sentinel.next,
 397            fast1 = sentinel.next->next,
 398            fast2 = sentinel.next->next->next;
 399            slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
 400            slow = slow->next, fast1 = fast2->next, fast2 = fast1->next)
 401       {
 402         MOZ_ASSERT(slow != fast1);
 403         MOZ_ASSERT(slow != fast2);
 404       }
 405
 406       /* Check for cycles in the backward singly-linked list. */
 407       for (slow = sentinel.prev,
 408            fast1 = sentinel.prev->prev,
 409            fast2 = sentinel.prev->prev->prev;
 410            slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
 411            slow = slow->prev, fast1 = fast2->prev, fast2 = fast1->prev)
 412       {
 413         MOZ_ASSERT(slow != fast1);
 414         MOZ_ASSERT(slow != fast2);
 415       }
 416
 417       /*
 418        * Check that |sentinel| is the only node in the list with
 419        * isSentinel == true.
 420        */
 421       for (const LinkedListElement<T>* elem = sentinel.next;
 422            elem != &sentinel;
 423            elem = elem->next)
 424       {
 425         MOZ_ASSERT(!elem->isSentinel);
 426       }
 427
 428       /* Check that the next/prev pointers match up. */
 429       const LinkedListElement<T>* prev = &sentinel;
 430       const LinkedListElement<T>* cur = sentinel.next;
 431       do {
 432           MOZ_ASSERT(cur->prev == prev);
 433           MOZ_ASSERT(prev->next == cur);
 434
 435           prev = cur;
 436           cur = cur->next;
 437       } while (cur != &sentinel);
 438 #endif /* ifdef DEBUG */
 439     }
 440
 441   private:
 442     friend class LinkedListElement<T>;
 443
 444     void assertContains(const T* t) const {
 445 #ifdef DEBUG
 446       for (const T* elem = getFirst();
 447            elem;
 448            elem = elem->getNext())
 449       {
 450         if (elem == t)
 451           return;
 452       }
 453       MOZ_CRASH("element wasn't found in this list!");
 454 #endif
 455     }
 456
 457     LinkedList& operator=(const LinkedList<T>& other) MOZ_DELETE;
 458     LinkedList(const LinkedList<T>& other) MOZ_DELETE;
 459 };
 460
 461 } /* namespace mozilla */
 462
 463 #endif /* __cplusplus */
 464
 465 #endif /* mozilla_LinkedList_h */