Source code
Revision control
Copy as Markdown
Other Tools
/* -*- 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
/** 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