mfbt/DoublyLinkedList.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 doubly-linked list with flexible next/prev naming. */
   8
   9 #ifndef mozilla_DoublyLinkedList_h
  10 #define mozilla_DoublyLinkedList_h
  11
  12 #include <algorithm>
  13 #include <iterator>
  14
  15 #include "mozilla/Assertions.h"
  16
  17 /**
  18  * Where mozilla::LinkedList strives for ease of use above all other
  19  * considerations, mozilla::DoublyLinkedList strives for flexibility. The
  20  * following are things that can be done with mozilla::DoublyLinkedList that
  21  * cannot be done with mozilla::LinkedList:
  22  *
  23  *   * Arbitrary next/prev placement and naming. With the tools provided here,
  24  *     the next and previous pointers can be at the end of the structure, in a
  25  *     sub-structure, stored with a tag, in a union, wherever, as long as you
  26  *     can look them up and set them on demand.
  27  *   * Can be used without deriving from a new base and, thus, does not require
  28  *     use of constructors.
  29  *
  30  * Example:
  31  *
  32  *   class Observer : public DoublyLinkedListElement<Observer>
  33  *   {
  34  *   public:
  35  *     void observe(char* aTopic) { ... }
  36  *   };
  37  *
  38  *   class ObserverContainer
  39  *   {
  40  *   private:
  41  *     DoublyLinkedList<Observer> mList;
  42  *
  43  *   public:
  44  *     void addObserver(Observer* aObserver)
  45  *     {
  46  *       // Will assert if |aObserver| is part of another list.
  47  *       mList.pushBack(aObserver);
  48  *     }
  49  *
  50  *     void removeObserver(Observer* aObserver)
  51  *     {
  52  *       // Will assert if |aObserver| is not part of |list|.
  53  *       mList.remove(aObserver);
  54  *     }
  55  *
  56  *     void notifyObservers(char* aTopic)
  57  *     {
  58  *       for (Observer* o : mList) {
  59  *         o->observe(aTopic);
  60  *       }
  61  *     }
  62  *   };
  63  */
  64
  65 namespace mozilla {
  66
  67 /**
  68  *  Deriving from this will allow T to be inserted into and removed from a
  69  *  DoublyLinkedList.
  70  */
  71 template <typename T>
  72 class DoublyLinkedListElement {
  73   template <typename U, typename E>
  74   friend class DoublyLinkedList;
  75   friend T;
  76   T* mNext;
  77   T* mPrev;
  78
  79  public:
  80   DoublyLinkedListElement() : mNext(nullptr), mPrev(nullptr) {}
  81 };
  82
  83 /**
  84  * Provides access to a DoublyLinkedListElement within T.
  85  *
  86  * The default implementation of this template works for types that derive
  87  * from DoublyLinkedListElement, but one can specialize for their class so
  88  * that some appropriate DoublyLinkedListElement reference is returned.
  89  *
  90  * For more complex cases (multiple DoublyLinkedListElements, for example),
  91  * one can define their own trait class and use that as ElementAccess for
  92  * DoublyLinkedList. See TestDoublyLinkedList.cpp for an example.
  93  */
  94 template <typename T>
  95 struct GetDoublyLinkedListElement {
  96   static_assert(mozilla::IsBaseOf<DoublyLinkedListElement<T>, T>::value,
  97                 "You need your own specialization of GetDoublyLinkedListElement"
  98                 " or use a separate Trait.");
  99   static DoublyLinkedListElement<T>& Get(T* aThis) { return *aThis; }
 100 };
 101
 102 /**
 103  * A doubly linked list. |T| is the type of element stored in this list. |T|
 104  * must contain or have access to unique next and previous element pointers.
 105  * The template argument |ElementAccess| provides code to tell this list how to
 106  * get a reference to a DoublyLinkedListElement that may reside anywhere.
 107  */
 108 template <typename T, typename ElementAccess = GetDoublyLinkedListElement<T>>
 109 class DoublyLinkedList final {
 110   T* mHead;
 111   T* mTail;
 112
 113   /**
 114    * Checks that either the list is empty and both mHead and mTail are nullptr
 115    * or the list has entries and both mHead and mTail are non-null.
 116    */
 117   bool isStateValid() const { return (mHead != nullptr) == (mTail != nullptr); }
 118
 119   bool ElementNotInList(T* aElm) {
 120     if (!ElementAccess::Get(aElm).mNext && !ElementAccess::Get(aElm).mPrev) {
 121       // Both mNext and mPrev being NULL can mean two things:
 122       // - the element is not in the list.
 123       // - the element is the first and only element in the list.
 124       // So check for the latter.
 125       return mHead != aElm;
 126     }
 127     return false;
 128   }
 129
 130  public:
 131   DoublyLinkedList() : mHead(nullptr), mTail(nullptr) {}
 132
 133   class Iterator final {
 134     T* mCurrent;
 135
 136    public:
 137     using iterator_category = std::forward_iterator_tag;
 138     using value_type = T;
 139     using difference_type = std::ptrdiff_t;
 140     using pointer = T*;
 141     using reference = T&;
 142
 143     Iterator() : mCurrent(nullptr) {}
 144     explicit Iterator(T* aCurrent) : mCurrent(aCurrent) {}
 145
 146     T& operator*() const { return *mCurrent; }
 147     T* operator->() const { return mCurrent; }
 148
 149     Iterator& operator++() {
 150       mCurrent = ElementAccess::Get(mCurrent).mNext;
 151       return *this;
 152     }
 153
 154     Iterator operator++(int) {
 155       Iterator result = *this;
 156       ++(*this);
 157       return result;
 158     }
 159
 160     Iterator& operator--() {
 161       mCurrent = ElementAccess::Get(mCurrent).mPrev;
 162       return *this;
 163     }
 164
 165     Iterator operator--(int) {
 166       Iterator result = *this;
 167       --(*this);
 168       return result;
 169     }
 170
 171     bool operator!=(const Iterator& aOther) const {
 172       return mCurrent != aOther.mCurrent;
 173     }
 174
 175     bool operator==(const Iterator& aOther) const {
 176       return mCurrent == aOther.mCurrent;
 177     }
 178
 179     explicit operator bool() const { return mCurrent; }
 180   };
 181
 182   Iterator begin() { return Iterator(mHead); }
 183   const Iterator begin() const { return Iterator(mHead); }
 184   const Iterator cbegin() const { return Iterator(mHead); }
 185
 186   Iterator end() { return Iterator(); }
 187   const Iterator end() const { return Iterator(); }
 188   const Iterator cend() const { return Iterator(); }
 189
 190   /**
 191    * Returns true if the list contains no elements.
 192    */
 193   bool isEmpty() const {
 194     MOZ_ASSERT(isStateValid());
 195     return mHead == nullptr;
 196   }
 197
 198   /**
 199    * Inserts aElm into the list at the head position. |aElm| must not already
 200    * be in a list.
 201    */
 202   void pushFront(T* aElm) {
 203     MOZ_ASSERT(aElm);
 204     MOZ_ASSERT(ElementNotInList(aElm));
 205     MOZ_ASSERT(isStateValid());
 206
 207     ElementAccess::Get(aElm).mNext = mHead;
 208     if (mHead) {
 209       MOZ_ASSERT(!ElementAccess::Get(mHead).mPrev);
 210       ElementAccess::Get(mHead).mPrev = aElm;
 211     }
 212
 213     mHead = aElm;
 214     if (!mTail) {
 215       mTail = aElm;
 216     }
 217   }
 218
 219   /**
 220    * Remove the head of the list and return it. Calling this on an empty list
 221    * will assert.
 222    */
 223   T* popFront() {
 224     MOZ_ASSERT(!isEmpty());
 225     MOZ_ASSERT(isStateValid());
 226
 227     T* result = mHead;
 228     mHead = result ? ElementAccess::Get(result).mNext : nullptr;
 229     if (mHead) {
 230       ElementAccess::Get(mHead).mPrev = nullptr;
 231     }
 232
 233     if (mTail == result) {
 234       mTail = nullptr;
 235     }
 236
 237     if (result) {
 238       ElementAccess::Get(result).mNext = nullptr;
 239       ElementAccess::Get(result).mPrev = nullptr;
 240     }
 241
 242     return result;
 243   }
 244
 245   /**
 246    * Inserts aElm into the list at the tail position. |aElm| must not already
 247    * be in a list.
 248    */
 249   void pushBack(T* aElm) {
 250     MOZ_ASSERT(aElm);
 251     MOZ_ASSERT(ElementNotInList(aElm));
 252     MOZ_ASSERT(isStateValid());
 253
 254     ElementAccess::Get(aElm).mNext = nullptr;
 255     ElementAccess::Get(aElm).mPrev = mTail;
 256     if (mTail) {
 257       MOZ_ASSERT(!ElementAccess::Get(mTail).mNext);
 258       ElementAccess::Get(mTail).mNext = aElm;
 259     }
 260
 261     mTail = aElm;
 262     if (!mHead) {
 263       mHead = aElm;
 264     }
 265   }
 266
 267   /**
 268    * Remove the tail of the list and return it. Calling this on an empty list
 269    * will assert.
 270    */
 271   T* popBack() {
 272     MOZ_ASSERT(!isEmpty());
 273     MOZ_ASSERT(isStateValid());
 274
 275     T* result = mTail;
 276     mTail = result ? ElementAccess::Get(result).mPrev : nullptr;
 277     if (mTail) {
 278       ElementAccess::Get(mTail).mNext = nullptr;
 279     }
 280
 281     if (mHead == result) {
 282       mHead = nullptr;
 283     }
 284
 285     if (result) {
 286       ElementAccess::Get(result).mNext = nullptr;
 287       ElementAccess::Get(result).mPrev = nullptr;
 288     }
 289
 290     return result;
 291   }
 292
 293   /**
 294    * Insert the given |aElm| *before* |aIter|.
 295    */
 296   void insertBefore(const Iterator& aIter, T* aElm) {
 297     MOZ_ASSERT(aElm);
 298     MOZ_ASSERT(ElementNotInList(aElm));
 299     MOZ_ASSERT(isStateValid());
 300
 301     if (!aIter) {
 302       return pushBack(aElm);
 303     } else if (aIter == begin()) {
 304       return pushFront(aElm);
 305     }
 306
 307     T* after = &(*aIter);
 308     T* before = ElementAccess::Get(after).mPrev;
 309     MOZ_ASSERT(before);
 310
 311     ElementAccess::Get(before).mNext = aElm;
 312     ElementAccess::Get(aElm).mPrev = before;
 313     ElementAccess::Get(aElm).mNext = after;
 314     ElementAccess::Get(after).mPrev = aElm;
 315   }
 316
 317   /**
 318    * Removes the given element from the list. The element must be in this list.
 319    */
 320   void remove(T* aElm) {
 321     MOZ_ASSERT(aElm);
 322     MOZ_ASSERT(ElementAccess::Get(aElm).mNext ||
 323                    ElementAccess::Get(aElm).mPrev ||
 324                    (aElm == mHead && aElm == mTail),
 325                "Attempted to remove element not in this list");
 326
 327     if (T* prev = ElementAccess::Get(aElm).mPrev) {
 328       ElementAccess::Get(prev).mNext = ElementAccess::Get(aElm).mNext;
 329     } else {
 330       MOZ_ASSERT(mHead == aElm);
 331       mHead = ElementAccess::Get(aElm).mNext;
 332     }
 333
 334     if (T* next = ElementAccess::Get(aElm).mNext) {
 335       ElementAccess::Get(next).mPrev = ElementAccess::Get(aElm).mPrev;
 336     } else {
 337       MOZ_ASSERT(mTail == aElm);
 338       mTail = ElementAccess::Get(aElm).mPrev;
 339     }
 340
 341     ElementAccess::Get(aElm).mNext = nullptr;
 342     ElementAccess::Get(aElm).mPrev = nullptr;
 343   }
 344
 345   /**
 346    * Returns an iterator referencing the first found element whose value matches
 347    * the given element according to operator==.
 348    */
 349   Iterator find(const T& aElm) { return std::find(begin(), end(), aElm); }
 350
 351   /**
 352    * Returns whether the given element is in the list. Note that this uses
 353    * T::operator==, not pointer comparison.
 354    */
 355   bool contains(const T& aElm) { return find(aElm) != Iterator(); }
 356
 357   /**
 358    * Returns whether the given element might be in the list. Note that this
 359    * assumes the element is either in the list or not in the list, and ignores
 360    * the case where the element might be in another list in order to make the
 361    * check fast.
 362    */
 363   bool ElementProbablyInList(T* aElm) {
 364     if (isEmpty()) {
 365       return false;
 366     }
 367     return !ElementNotInList(aElm);
 368   }
 369 };
 370
 371 }  // namespace mozilla
 372
 373 #endif  // mozilla_DoublyLinkedList_h