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/MemoryReporting.h"
  62 #include "mozilla/Move.h"
  63 #include "mozilla/NullPtr.h"
  64
  65 #ifdef __cplusplus
  66
  67 namespace mozilla {
  68
  69 template<typename T>
  70 class LinkedList;
  71
  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      */
 108
 109   private:
 110     LinkedListElement* next;
 111     LinkedListElement* prev;
 112     const bool isSentinel;
 113
 114   public:
 115     LinkedListElement()
 116       : next(MOZ_THIS_IN_INITIALIZER_LIST()),
 117         prev(MOZ_THIS_IN_INITIALIZER_LIST()),
 118         isSentinel(false)
 119     { }
 120
 121     LinkedListElement(LinkedListElement<T>&& other)
 122       : isSentinel(other.isSentinel)
 123     {
 124       if (!other.isInList()) {
 125         next = this;
 126         prev = this;
 127         return;
 128       }
 129
 130       MOZ_ASSERT(other.next->prev == &other);
 131       MOZ_ASSERT(other.prev->next == &other);
 132
 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;
 139
 140       next->prev = this;
 141       prev->next = this;
 142
 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     }
 150
 151     ~LinkedListElement() {
 152       if (!isSentinel && isInList())
 153         remove();
 154     }
 155
 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     }
 166
 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     }
 177
 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     }
 186
 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     }
 196
 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());
 203
 204       prev->next = next;
 205       next->prev = prev;
 206       next = this;
 207       prev = this;
 208     }
 209
 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     }
 218
 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     }
 226
 227   private:
 228     friend class LinkedList<T>;
 229
 230     enum NodeKind {
 231       NODE_KIND_NORMAL,
 232       NODE_KIND_SENTINEL
 233     };
 234
 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     { }
 240
 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;
 248
 249       return static_cast<T*>(this);
 250     }
 251     const T* asT() const {
 252       if (isSentinel)
 253         return nullptr;
 254
 255       return static_cast<const T*>(this);
 256     }
 257
 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());
 265
 266       listElem->next = this->next;
 267       listElem->prev = this;
 268       this->next->prev = listElem;
 269       this->next = listElem;
 270     }
 271
 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());
 279
 280       listElem->next = this;
 281       listElem->prev = this->prev;
 282       this->prev->next = listElem;
 283       this->prev = listElem;
 284     }
 285
 286   private:
 287     LinkedListElement& operator=(const LinkedListElement<T>& other) MOZ_DELETE;
 288     LinkedListElement(const LinkedListElement<T>& other) MOZ_DELETE;
 289 };
 290
 291 template<typename T>
 292 class LinkedList
 293 {
 294   private:
 295     LinkedListElement<T> sentinel;
 296
 297   public:
 298     LinkedList() : sentinel(LinkedListElement<T>::NODE_KIND_SENTINEL) { }
 299
 300     LinkedList(LinkedList<T>&& other)
 301       : sentinel(mozilla::Move(other.sentinel))
 302     { }
 303
 304     ~LinkedList() {
 305       MOZ_ASSERT(isEmpty());
 306     }
 307
 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     }
 315
 316     /*
 317      * Add elem to the back of the list.
 318      */
 319     void insertBack(T* elem) {
 320       sentinel.setPreviousUnsafe(elem);
 321     }
 322
 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     }
 332
 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     }
 342
 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     }
 353
 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     }
 364
 365     /*
 366      * Return true if the list is empty, or false otherwise.
 367      */
 368     bool isEmpty() const {
 369       return !sentinel.isInList();
 370     }
 371
 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     }
 382
 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     }
 395
 396     /*
 397      * Like sizeOfExcludingThis(), but measures |this| as well.
 398      */
 399     size_t sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const {
 400       return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
 401     }
 402
 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;
 412
 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       }
 426
 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       }
 437
 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       }
 448
 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);
 455
 456           prev = cur;
 457           cur = cur->next;
 458       } while (cur != &sentinel);
 459 #endif /* ifdef DEBUG */
 460     }
 461
 462   private:
 463     friend class LinkedListElement<T>;
 464
 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     }
 477
 478     LinkedList& operator=(const LinkedList<T>& other) MOZ_DELETE;
 479     LinkedList(const LinkedList<T>& other) MOZ_DELETE;
 480 };
 481
 482 } /* namespace mozilla */
 483
 484 #endif /* __cplusplus */
 485
 486 #endif /* mozilla_LinkedList_h */