summaryrefslogtreecommitdiffstats
path: root/mfbt/DoublyLinkedList.h
diff options
context:
space:
mode:
Diffstat (limited to 'mfbt/DoublyLinkedList.h')
-rw-r--r--mfbt/DoublyLinkedList.h578
1 files changed, 578 insertions, 0 deletions
diff --git a/mfbt/DoublyLinkedList.h b/mfbt/DoublyLinkedList.h
new file mode 100644
index 0000000000..df178440d2
--- /dev/null
+++ b/mfbt/DoublyLinkedList.h
@@ -0,0 +1,578 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/** A doubly-linked list with flexible next/prev naming. */
+
+#ifndef mozilla_DoublyLinkedList_h
+#define mozilla_DoublyLinkedList_h
+
+#include <algorithm>
+#include <iosfwd>
+#include <iterator>
+#include <type_traits>
+
+#include "mozilla/Assertions.h"
+
+/**
+ * Where mozilla::LinkedList strives for ease of use above all other
+ * considerations, mozilla::DoublyLinkedList strives for flexibility. The
+ * following are things that can be done with mozilla::DoublyLinkedList that
+ * cannot be done with mozilla::LinkedList:
+ *
+ * * Arbitrary next/prev placement and naming. With the tools provided here,
+ * the next and previous pointers can be at the end of the structure, in a
+ * sub-structure, stored with a tag, in a union, wherever, as long as you
+ * can look them up and set them on demand.
+ * * Can be used without deriving from a new base and, thus, does not require
+ * use of constructors.
+ *
+ * Example:
+ *
+ * class Observer : public DoublyLinkedListElement<Observer>
+ * {
+ * public:
+ * void observe(char* aTopic) { ... }
+ * };
+ *
+ * class ObserverContainer
+ * {
+ * private:
+ * DoublyLinkedList<Observer> mList;
+ *
+ * public:
+ * void addObserver(Observer* aObserver)
+ * {
+ * // Will assert if |aObserver| is part of another list.
+ * mList.pushBack(aObserver);
+ * }
+ *
+ * void removeObserver(Observer* aObserver)
+ * {
+ * // Will assert if |aObserver| is not part of |list|.
+ * mList.remove(aObserver);
+ * }
+ *
+ * void notifyObservers(char* aTopic)
+ * {
+ * for (Observer* o : mList) {
+ * o->observe(aTopic);
+ * }
+ * }
+ * };
+ */
+
+namespace mozilla {
+
+/**
+ * Deriving from this will allow T to be inserted into and removed from a
+ * DoublyLinkedList.
+ */
+template <typename T>
+class DoublyLinkedListElement {
+ template <typename U, typename E>
+ friend class DoublyLinkedList;
+ friend T;
+ T* mNext;
+ T* mPrev;
+
+ public:
+ DoublyLinkedListElement() : mNext(nullptr), mPrev(nullptr) {}
+};
+
+/**
+ * Provides access to a DoublyLinkedListElement within T.
+ *
+ * The default implementation of this template works for types that derive
+ * from DoublyLinkedListElement, but one can specialize for their class so
+ * that some appropriate DoublyLinkedListElement reference is returned.
+ *
+ * For more complex cases (multiple DoublyLinkedListElements, for example),
+ * one can define their own trait class and use that as ElementAccess for
+ * DoublyLinkedList. See TestDoublyLinkedList.cpp for an example.
+ */
+template <typename T>
+struct GetDoublyLinkedListElement {
+ static_assert(std::is_base_of<DoublyLinkedListElement<T>, T>::value,
+ "You need your own specialization of GetDoublyLinkedListElement"
+ " or use a separate Trait.");
+ static DoublyLinkedListElement<T>& Get(T* aThis) { return *aThis; }
+};
+
+/**
+ * A doubly linked list. |T| is the type of element stored in this list. |T|
+ * must contain or have access to unique next and previous element pointers.
+ * The template argument |ElementAccess| provides code to tell this list how to
+ * get a reference to a DoublyLinkedListElement that may reside anywhere.
+ */
+template <typename T, typename ElementAccess = GetDoublyLinkedListElement<T>>
+class DoublyLinkedList final {
+ T* mHead;
+ T* mTail;
+
+ /**
+ * Checks that either the list is empty and both mHead and mTail are nullptr
+ * or the list has entries and both mHead and mTail are non-null.
+ */
+ bool isStateValid() const { return (mHead != nullptr) == (mTail != nullptr); }
+
+ bool ElementNotInList(T* aElm) {
+ if (!ElementAccess::Get(aElm).mNext && !ElementAccess::Get(aElm).mPrev) {
+ // Both mNext and mPrev being NULL can mean two things:
+ // - the element is not in the list.
+ // - the element is the first and only element in the list.
+ // So check for the latter.
+ return mHead != aElm;
+ }
+ return false;
+ }
+
+ public:
+ DoublyLinkedList() : mHead(nullptr), mTail(nullptr) {}
+
+ class Iterator final {
+ T* mCurrent;
+
+ public:
+ using iterator_category = std::forward_iterator_tag;
+ using value_type = T;
+ using difference_type = std::ptrdiff_t;
+ using pointer = T*;
+ using reference = T&;
+
+ Iterator() : mCurrent(nullptr) {}
+ explicit Iterator(T* aCurrent) : mCurrent(aCurrent) {}
+
+ T& operator*() const { return *mCurrent; }
+ T* operator->() const { return mCurrent; }
+
+ Iterator& operator++() {
+ mCurrent = mCurrent ? ElementAccess::Get(mCurrent).mNext : nullptr;
+ return *this;
+ }
+
+ Iterator operator++(int) {
+ Iterator result = *this;
+ ++(*this);
+ return result;
+ }
+
+ Iterator& operator--() {
+ mCurrent = ElementAccess::Get(mCurrent).mPrev;
+ return *this;
+ }
+
+ Iterator operator--(int) {
+ Iterator result = *this;
+ --(*this);
+ return result;
+ }
+
+ bool operator!=(const Iterator& aOther) const {
+ return mCurrent != aOther.mCurrent;
+ }
+
+ bool operator==(const Iterator& aOther) const {
+ return mCurrent == aOther.mCurrent;
+ }
+
+ explicit operator bool() const { return mCurrent; }
+ };
+
+ Iterator begin() { return Iterator(mHead); }
+ const Iterator begin() const { return Iterator(mHead); }
+ const Iterator cbegin() const { return Iterator(mHead); }
+
+ Iterator end() { return Iterator(); }
+ const Iterator end() const { return Iterator(); }
+ const Iterator cend() const { return Iterator(); }
+
+ /**
+ * Returns true if the list contains no elements.
+ */
+ bool isEmpty() const {
+ MOZ_ASSERT(isStateValid());
+ return mHead == nullptr;
+ }
+
+ /**
+ * Inserts aElm into the list at the head position. |aElm| must not already
+ * be in a list.
+ */
+ void pushFront(T* aElm) {
+ MOZ_ASSERT(aElm);
+ MOZ_ASSERT(ElementNotInList(aElm));
+ MOZ_ASSERT(isStateValid());
+
+ ElementAccess::Get(aElm).mNext = mHead;
+ if (mHead) {
+ MOZ_ASSERT(!ElementAccess::Get(mHead).mPrev);
+ ElementAccess::Get(mHead).mPrev = aElm;
+ }
+
+ mHead = aElm;
+ if (!mTail) {
+ mTail = aElm;
+ }
+ }
+
+ /**
+ * Remove the head of the list and return it. Calling this on an empty list
+ * will assert.
+ */
+ T* popFront() {
+ MOZ_ASSERT(!isEmpty());
+ MOZ_ASSERT(isStateValid());
+
+ T* result = mHead;
+ mHead = result ? ElementAccess::Get(result).mNext : nullptr;
+ if (mHead) {
+ ElementAccess::Get(mHead).mPrev = nullptr;
+ }
+
+ if (mTail == result) {
+ mTail = nullptr;
+ }
+
+ if (result) {
+ ElementAccess::Get(result).mNext = nullptr;
+ ElementAccess::Get(result).mPrev = nullptr;
+ }
+
+ return result;
+ }
+
+ /**
+ * Inserts aElm into the list at the tail position. |aElm| must not already
+ * be in a list.
+ */
+ void pushBack(T* aElm) {
+ MOZ_ASSERT(aElm);
+ MOZ_ASSERT(ElementNotInList(aElm));
+ MOZ_ASSERT(isStateValid());
+
+ ElementAccess::Get(aElm).mNext = nullptr;
+ ElementAccess::Get(aElm).mPrev = mTail;
+ if (mTail) {
+ MOZ_ASSERT(!ElementAccess::Get(mTail).mNext);
+ ElementAccess::Get(mTail).mNext = aElm;
+ }
+
+ mTail = aElm;
+ if (!mHead) {
+ mHead = aElm;
+ }
+ }
+
+ /**
+ * Remove the tail of the list and return it. Calling this on an empty list
+ * will assert.
+ */
+ T* popBack() {
+ MOZ_ASSERT(!isEmpty());
+ MOZ_ASSERT(isStateValid());
+
+ T* result = mTail;
+ mTail = result ? ElementAccess::Get(result).mPrev : nullptr;
+ if (mTail) {
+ ElementAccess::Get(mTail).mNext = nullptr;
+ }
+
+ if (mHead == result) {
+ mHead = nullptr;
+ }
+
+ if (result) {
+ ElementAccess::Get(result).mNext = nullptr;
+ ElementAccess::Get(result).mPrev = nullptr;
+ }
+
+ return result;
+ }
+
+ /**
+ * Insert the given |aElm| *before* |aIter|.
+ */
+ void insertBefore(const Iterator& aIter, T* aElm) {
+ MOZ_ASSERT(aElm);
+ MOZ_ASSERT(ElementNotInList(aElm));
+ MOZ_ASSERT(isStateValid());
+
+ if (!aIter) {
+ return pushBack(aElm);
+ } else if (aIter == begin()) {
+ return pushFront(aElm);
+ }
+
+ T* after = &(*aIter);
+ T* before = ElementAccess::Get(after).mPrev;
+ MOZ_ASSERT(before);
+
+ ElementAccess::Get(before).mNext = aElm;
+ ElementAccess::Get(aElm).mPrev = before;
+ ElementAccess::Get(aElm).mNext = after;
+ ElementAccess::Get(after).mPrev = aElm;
+ }
+
+ /**
+ * Removes the given element from the list. The element must be in this list.
+ */
+ void remove(T* aElm) {
+ MOZ_ASSERT(aElm);
+ MOZ_ASSERT(ElementAccess::Get(aElm).mNext ||
+ ElementAccess::Get(aElm).mPrev ||
+ (aElm == mHead && aElm == mTail),
+ "Attempted to remove element not in this list");
+
+ if (T* prev = ElementAccess::Get(aElm).mPrev) {
+ ElementAccess::Get(prev).mNext = ElementAccess::Get(aElm).mNext;
+ } else {
+ MOZ_ASSERT(mHead == aElm);
+ mHead = ElementAccess::Get(aElm).mNext;
+ }
+
+ if (T* next = ElementAccess::Get(aElm).mNext) {
+ ElementAccess::Get(next).mPrev = ElementAccess::Get(aElm).mPrev;
+ } else {
+ MOZ_ASSERT(mTail == aElm);
+ mTail = ElementAccess::Get(aElm).mPrev;
+ }
+
+ ElementAccess::Get(aElm).mNext = nullptr;
+ ElementAccess::Get(aElm).mPrev = nullptr;
+ }
+
+ /**
+ * Returns an iterator referencing the first found element whose value matches
+ * the given element according to operator==.
+ */
+ Iterator find(const T& aElm) { return std::find(begin(), end(), aElm); }
+
+ /**
+ * Returns whether the given element is in the list. Note that this uses
+ * T::operator==, not pointer comparison.
+ */
+ bool contains(const T& aElm) { return find(aElm) != Iterator(); }
+
+ /**
+ * Returns whether the given element might be in the list. Note that this
+ * assumes the element is either in the list or not in the list, and ignores
+ * the case where the element might be in another list in order to make the
+ * check fast.
+ */
+ bool ElementProbablyInList(T* aElm) {
+ if (isEmpty()) {
+ return false;
+ }
+ return !ElementNotInList(aElm);
+ }
+};
+
+/**
+ * @brief Double linked list that allows insertion/removal during iteration.
+ *
+ * This class uses the mozilla::DoublyLinkedList internally and keeps
+ * track of created iterator instances by putting them on a simple list on stack
+ * (compare nsTAutoObserverArray).
+ * This allows insertion or removal operations to adjust iterators and therefore
+ * keeping them valid during iteration.
+ */
+template <typename T, typename ElementAccess = GetDoublyLinkedListElement<T>>
+class SafeDoublyLinkedList {
+ public:
+ /**
+ * @brief Iterator class for SafeDoublyLinkedList.
+ *
+ * The iterator contains two iterators of the underlying list:
+ * - mCurrent points to the current list element of the iterator.
+ * - mNext points to the next element of the list.
+ *
+ * When removing an element from the list, mCurrent and mNext may
+ * be adjusted:
+ * - If mCurrent is the element to be deleted, it is set to empty. mNext can
+ * still be used to advance to the next element.
+ * - If mNext is the element to be deleted, it is set to its next element
+ * (or to empty if mNext is the last element of the list).
+ */
+ class SafeIterator {
+ using BaseIterator = typename DoublyLinkedList<T, ElementAccess>::Iterator;
+ friend class SafeDoublyLinkedList<T, ElementAccess>;
+
+ public:
+ using iterator_category = std::forward_iterator_tag;
+ using value_type = T;
+ using difference_type = std::ptrdiff_t;
+ using pointer = T*;
+ using const_pointer = const T*;
+ using reference = T&;
+ using const_reference = const T&;
+
+ SafeIterator() = default;
+ SafeIterator(SafeIterator const& aOther)
+ : SafeIterator(aOther.mCurrent, aOther.mList) {}
+
+ SafeIterator(BaseIterator aBaseIter,
+ SafeDoublyLinkedList<T, ElementAccess>* aList)
+ : mCurrent(aBaseIter),
+ mNext(aBaseIter ? ++aBaseIter : BaseIterator()),
+ mList(aList) {
+ if (mList) {
+ mNextIterator = mList->mIter;
+ mList->mIter = this;
+ }
+ }
+ ~SafeIterator() {
+ if (mList) {
+ MOZ_ASSERT(mList->mIter == this,
+ "Iterators must currently be destroyed in opposite order "
+ "from the construction order. It is suggested that you "
+ "simply put them on the stack");
+ mList->mIter = mNextIterator;
+ }
+ }
+
+ SafeIterator& operator++() {
+ mCurrent = mNext;
+ if (mNext) {
+ ++mNext;
+ }
+ return *this;
+ }
+
+ pointer operator->() { return &*mCurrent; }
+ const_pointer operator->() const { return &*mCurrent; }
+ reference operator*() { return *mCurrent; }
+ const_reference operator*() const { return *mCurrent; }
+
+ pointer current() { return mCurrent ? &*mCurrent : nullptr; }
+ const_pointer current() const { return mCurrent ? &*mCurrent : nullptr; }
+
+ explicit operator bool() const { return bool(mCurrent); }
+ bool operator==(SafeIterator const& other) const {
+ return mCurrent == other.mCurrent;
+ }
+ bool operator!=(SafeIterator const& other) const {
+ return mCurrent != other.mCurrent;
+ }
+
+ BaseIterator& next() { return mNext; } // mainly needed for unittests.
+ private:
+ /**
+ * Base list iterator pointing to the current list element of the iteration.
+ * If element mCurrent points to gets removed, the iterator will be set to
+ * empty. mNext keeps the iterator valid.
+ */
+ BaseIterator mCurrent{nullptr};
+ /**
+ * Base list iterator pointing to the next list element of the iteration.
+ * If element mCurrent points to gets removed, mNext is still valid.
+ * If element mNext points to gets removed, mNext advances, keeping this
+ * iterator valid.
+ */
+ BaseIterator mNext{nullptr};
+
+ /**
+ * Next element in the stack-allocated list of iterators stored in the
+ * SafeLinkedList object.
+ */
+ SafeIterator* mNextIterator{nullptr};
+ SafeDoublyLinkedList<T, ElementAccess>* mList{nullptr};
+
+ void setNext(T* aElm) { mNext = BaseIterator(aElm); }
+ void setCurrent(T* aElm) { mCurrent = BaseIterator(aElm); }
+ };
+
+ private:
+ using BaseListType = DoublyLinkedList<T, ElementAccess>;
+ friend class SafeIterator;
+
+ public:
+ SafeDoublyLinkedList() = default;
+
+ bool isEmpty() const { return mList.isEmpty(); }
+ bool contains(T* aElm) {
+ for (auto iter = mList.begin(); iter != mList.end(); ++iter) {
+ if (&*iter == aElm) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ SafeIterator begin() { return SafeIterator(mList.begin(), this); }
+ SafeIterator begin() const { return SafeIterator(mList.begin(), this); }
+ SafeIterator cbegin() const { return begin(); }
+
+ SafeIterator end() { return SafeIterator(); }
+ SafeIterator end() const { return SafeIterator(); }
+ SafeIterator cend() const { return SafeIterator(); }
+
+ void pushFront(T* aElm) { mList.pushFront(aElm); }
+
+ void pushBack(T* aElm) {
+ mList.pushBack(aElm);
+ auto* iter = mIter;
+ while (iter) {
+ if (!iter->mNext) {
+ iter->setNext(aElm);
+ }
+ iter = iter->mNextIterator;
+ }
+ }
+
+ T* popFront() {
+ T* firstElm = mList.popFront();
+ auto* iter = mIter;
+ while (iter) {
+ if (iter->current() == firstElm) {
+ iter->setCurrent(nullptr);
+ }
+ iter = iter->mNextIterator;
+ }
+
+ return firstElm;
+ }
+
+ T* popBack() {
+ T* lastElm = mList.popBack();
+ auto* iter = mIter;
+ while (iter) {
+ if (iter->current() == lastElm) {
+ iter->setCurrent(nullptr);
+ } else if (iter->mNext && &*(iter->mNext) == lastElm) {
+ iter->setNext(nullptr);
+ }
+ iter = iter->mNextIterator;
+ }
+
+ return lastElm;
+ }
+
+ void remove(T* aElm) {
+ if (!mList.ElementProbablyInList(aElm)) {
+ return;
+ }
+ auto* iter = mIter;
+ while (iter) {
+ if (iter->mNext && &*(iter->mNext) == aElm) {
+ ++(iter->mNext);
+ }
+ if (iter->current() == aElm) {
+ iter->setCurrent(nullptr);
+ }
+ iter = iter->mNextIterator;
+ }
+
+ mList.remove(aElm);
+ }
+
+ private:
+ BaseListType mList;
+ SafeIterator* mIter{nullptr};
+};
+
+} // namespace mozilla
+
+#endif // mozilla_DoublyLinkedList_h