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