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 type-safe doubly-linked list class. */
/*
* The classes LinkedList<T> and LinkedListElement<T> together form a
* convenient, type-safe doubly-linked list implementation.
*
* The class T which will be inserted into the linked list must inherit from
* LinkedListElement<T>. A given object may be in only one linked list at a
* time.
*
* A LinkedListElement automatically removes itself from the list upon
* destruction, and a LinkedList will fatally assert in debug builds if it's
* non-empty when it's destructed.
*
* For example, you might use LinkedList in a simple observer list class as
* follows.
*
* class Observer : public LinkedListElement<Observer>
* {
* public:
* void observe(char* aTopic) { ... }
* };
*
* class ObserverContainer
* {
* private:
* LinkedList<Observer> list;
*
* public:
* void addObserver(Observer* aObserver)
* {
* // Will assert if |aObserver| is part of another list.
* list.insertBack(aObserver);
* }
*
* void removeObserver(Observer* aObserver)
* {
* // Will assert if |aObserver| is not part of some list.
* aObserver.remove();
* // Or, will assert if |aObserver| is not part of |list| specifically.
* // aObserver.removeFrom(list);
* }
*
* void notifyObservers(char* aTopic)
* {
* for (Observer* o = list.getFirst(); o != nullptr; o = o->getNext()) {
* o->observe(aTopic);
* }
* }
* };
*
* Additionally, the class AutoCleanLinkedList<T> is a LinkedList<T> that will
* remove and delete each element still within itself upon destruction. Note
* that because each element is deleted, elements must have been allocated
* using |new|.
*/
#ifndef mozilla_LinkedList_h
#define mozilla_LinkedList_h
#include <algorithm>
#include <utility>
#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/RefPtr.h"
#ifdef __cplusplus
namespace mozilla {
template <typename T>
class LinkedListElement;
namespace detail {
/**
* LinkedList supports refcounted elements using this adapter class. Clients
* using LinkedList<RefPtr<T>> will get a data structure that holds a strong
* reference to T as long as T is in the list.
*/
template <typename T>
struct LinkedListElementTraits {
typedef T* RawType;
typedef const T* ConstRawType;
typedef T* ClientType;
typedef const T* ConstClientType;
// These static methods are called when an element is added to or removed from
// a linked list. It can be used to keep track ownership in lists that are
// supposed to own their elements. If elements are transferred from one list
// to another, no enter or exit calls happen since the elements still belong
// to a list.
static void enterList(LinkedListElement<T>* elt) {}
static void exitList(LinkedListElement<T>* elt) {}
// This method is called when AutoCleanLinkedList cleans itself
// during destruction. It can be used to call delete on elements if
// the list is the sole owner.
static void cleanElement(LinkedListElement<T>* elt) { delete elt->asT(); }
};
template <typename T>
struct LinkedListElementTraits<RefPtr<T>> {
typedef T* RawType;
typedef const T* ConstRawType;
typedef RefPtr<T> ClientType;
typedef RefPtr<const T> ConstClientType;
static void enterList(LinkedListElement<RefPtr<T>>* elt) {
elt->asT()->AddRef();
}
static void exitList(LinkedListElement<RefPtr<T>>* elt) {
elt->asT()->Release();
}
static void cleanElement(LinkedListElement<RefPtr<T>>* elt) {}
};
} /* namespace detail */
template <typename T>
class LinkedList;
template <typename T>
class LinkedListElement {
typedef typename detail::LinkedListElementTraits<T> Traits;
typedef typename Traits::RawType RawType;
typedef typename Traits::ConstRawType ConstRawType;
typedef typename Traits::ClientType ClientType;
typedef typename Traits::ConstClientType ConstClientType;
/*
* It's convenient that we return nullptr when getNext() or getPrevious()
* hits the end of the list, but doing so costs an extra word of storage in
* each linked list node (to keep track of whether |this| is the sentinel
* node) and a branch on this value in getNext/getPrevious.
*
* We could get rid of the extra word of storage by shoving the "is
* sentinel" bit into one of the pointers, although this would, of course,
* have performance implications of its own.
*
* But the goal here isn't to win an award for the fastest or slimmest
* linked list; rather, we want a *convenient* linked list. So we won't
* waste time guessing which micro-optimization strategy is best.
*
*
* Speaking of unnecessary work, it's worth addressing here why we wrote
* mozilla::LinkedList in the first place, instead of using stl::list.
*
* The key difference between mozilla::LinkedList and stl::list is that
* mozilla::LinkedList stores the mPrev/mNext pointers in the object itself,
* while stl::list stores the mPrev/mNext pointers in a list element which
* itself points to the object being stored.
*
* mozilla::LinkedList's approach makes it harder to store an object in more
* than one list. But the upside is that you can call next() / prev() /
* remove() directly on the object. With stl::list, you'd need to store a
* pointer to its iterator in the object in order to accomplish this. Not
* only would this waste space, but you'd have to remember to update that
* pointer every time you added or removed the object from a list.
*
* In-place, constant-time removal is a killer feature of doubly-linked
* lists, and supporting this painlessly was a key design criterion.
*/
private:
LinkedListElement* mNext;
LinkedListElement* mPrev;
const bool mIsSentinel;
public:
LinkedListElement() : mNext(this), mPrev(this), mIsSentinel(false) {}
/*
* Moves |aOther| into |*this|. If |aOther| is already in a list, then
* |aOther| is removed from the list and replaced by |*this|.
*/
LinkedListElement(LinkedListElement<T>&& aOther)
: mIsSentinel(aOther.mIsSentinel) {
adjustLinkForMove(std::move(aOther));
}
LinkedListElement& operator=(LinkedListElement<T>&& aOther) {
MOZ_ASSERT(mIsSentinel == aOther.mIsSentinel, "Mismatch NodeKind!");
MOZ_ASSERT(!isInList(),
"Assigning to an element in a list messes up that list!");
adjustLinkForMove(std::move(aOther));
return *this;
}
~LinkedListElement() {
if (!mIsSentinel && isInList()) {
remove();
}
}
/*
* Get the next element in the list, or nullptr if this is the last element
* in the list.
*/
RawType getNext() { return mNext->asT(); }
ConstRawType getNext() const { return mNext->asT(); }
/*
* Get the previous element in the list, or nullptr if this is the first
* element in the list.
*/
RawType getPrevious() { return mPrev->asT(); }
ConstRawType getPrevious() const { return mPrev->asT(); }
/*
* Insert aElem after this element in the list. |this| must be part of a
* linked list when you call setNext(); otherwise, this method will assert.
*/
void setNext(RawType aElem) {
MOZ_ASSERT(isInList());
setNextUnsafe(aElem);
}
/*
* Insert aElem before this element in the list. |this| must be part of a
* linked list when you call setPrevious(); otherwise, this method will
* assert.
*/
void setPrevious(RawType aElem) {
MOZ_ASSERT(isInList());
setPreviousUnsafe(aElem);
}
/*
* Remove this element from the list which contains it. If this element is
* not currently part of a linked list, this method asserts.
*/
void remove() {
MOZ_ASSERT(isInList());
mPrev->mNext = mNext;
mNext->mPrev = mPrev;
mNext = this;
mPrev = this;
Traits::exitList(this);
}
/*
* Remove this element from the list containing it. Returns a pointer to the
* element that follows this element (before it was removed). This method
* asserts if the element does not belong to a list. Note: In a refcounted
* list, |this| may be destroyed.
*/
RawType removeAndGetNext() {
RawType r = getNext();
remove();
return r;
}
/*
* Remove this element from the list containing it. Returns a pointer to the
* previous element in the containing list (before the removal). This method
* asserts if the element does not belong to a list. Note: In a refcounted
* list, |this| may be destroyed.
*/
RawType removeAndGetPrevious() {
RawType r = getPrevious();
remove();
return r;
}
/*
* Identical to remove(), but also asserts in debug builds that this element
* is in aList.
*/
void removeFrom(const LinkedList<T>& aList) {
aList.assertContains(asT());
remove();
}
/*
* Return true if |this| part is of a linked list, and false otherwise.
*/
bool isInList() const {
MOZ_ASSERT((mNext == this) == (mPrev == this));
return mNext != this;
}
private:
friend class LinkedList<T>;
friend struct detail::LinkedListElementTraits<T>;
enum class NodeKind { Normal, Sentinel };
explicit LinkedListElement(NodeKind nodeKind)
: mNext(this), mPrev(this), mIsSentinel(nodeKind == NodeKind::Sentinel) {}
/*
* Return |this| cast to T* if we're a normal node, or return nullptr if
* we're a sentinel node.
*/
RawType asT() { return mIsSentinel ? nullptr : static_cast<RawType>(this); }
ConstRawType asT() const {
return mIsSentinel ? nullptr : static_cast<ConstRawType>(this);
}
/*
* Insert aElem after this element, but don't check that this element is in
* the list. This is called by LinkedList::insertFront().
*/
void setNextUnsafe(RawType aElem) {
LinkedListElement* listElem = static_cast<LinkedListElement*>(aElem);
MOZ_RELEASE_ASSERT(!listElem->isInList());
listElem->mNext = this->mNext;
listElem->mPrev = this;
this->mNext->mPrev = listElem;
this->mNext = listElem;
Traits::enterList(aElem);
}
/*
* Insert aElem before this element, but don't check that this element is in
* the list. This is called by LinkedList::insertBack().
*/
void setPreviousUnsafe(RawType aElem) {
LinkedListElement<T>* listElem = static_cast<LinkedListElement<T>*>(aElem);
MOZ_RELEASE_ASSERT(!listElem->isInList());
listElem->mNext = this;
listElem->mPrev = this->mPrev;
this->mPrev->mNext = listElem;
this->mPrev = listElem;
Traits::enterList(aElem);
}
/*
* Transfers the elements [aBegin, aEnd) before the "this" list element.
*/
void transferBeforeUnsafe(LinkedListElement<T>& aBegin,
LinkedListElement<T>& aEnd) {
MOZ_RELEASE_ASSERT(!aBegin.mIsSentinel);
if (!aBegin.isInList() || !aEnd.isInList()) {
return;
}
auto otherPrev = aBegin.mPrev;
aBegin.mPrev = this->mPrev;
this->mPrev->mNext = &aBegin;
this->mPrev = aEnd.mPrev;
aEnd.mPrev->mNext = this;
// Patch the gap in the source list
otherPrev->mNext = &aEnd;
aEnd.mPrev = otherPrev;
}
/*
* Adjust mNext and mPrev for implementing move constructor and move
* assignment.
*/
void adjustLinkForMove(LinkedListElement<T>&& aOther) {
if (!aOther.isInList()) {
mNext = this;
mPrev = this;
return;
}
if (!mIsSentinel) {
Traits::enterList(this);
}
MOZ_ASSERT(aOther.mNext->mPrev == &aOther);
MOZ_ASSERT(aOther.mPrev->mNext == &aOther);
/*
* Initialize |this| with |aOther|'s mPrev/mNext pointers, and adjust those
* element to point to this one.
*/
mNext = aOther.mNext;
mPrev = aOther.mPrev;
mNext->mPrev = this;
mPrev->mNext = this;
/*
* Adjust |aOther| so it doesn't think it's in a list. This makes it
* safely destructable.
*/
aOther.mNext = &aOther;
aOther.mPrev = &aOther;
if (!mIsSentinel) {
Traits::exitList(&aOther);
}
}
LinkedListElement& operator=(const LinkedListElement<T>& aOther) = delete;
LinkedListElement(const LinkedListElement<T>& aOther) = delete;
};
template <typename T>
class LinkedList {
private:
using Traits = typename detail::LinkedListElementTraits<T>;
using RawType = typename Traits::RawType;
using ConstRawType = typename Traits::ConstRawType;
using ClientType = typename Traits::ClientType;
using ConstClientType = typename Traits::ConstClientType;
using ElementType = LinkedListElement<T>*;
using ConstElementType = const LinkedListElement<T>*;
LinkedListElement<T> sentinel;
public:
template <typename Type, typename Element>
class Iterator {
Type 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&;
explicit Iterator(Type aCurrent) : mCurrent(aCurrent) {}
Type operator*() const { return mCurrent; }
const Iterator& operator++() {
mCurrent = static_cast<Element>(mCurrent)->getNext();
return *this;
}
bool operator!=(const Iterator& aOther) const {
return mCurrent != aOther.mCurrent;
}
};
using const_iterator = Iterator<ConstRawType, ConstElementType>;
using iterator = Iterator<RawType, ElementType>;
LinkedList() : sentinel(LinkedListElement<T>::NodeKind::Sentinel) {}
LinkedList(LinkedList<T>&& aOther) : sentinel(std::move(aOther.sentinel)) {}
LinkedList& operator=(LinkedList<T>&& aOther) {
MOZ_ASSERT(isEmpty(),
"Assigning to a non-empty list leaks elements in that list!");
sentinel = std::move(aOther.sentinel);
return *this;
}
~LinkedList() {
# ifdef DEBUG
if (!isEmpty()) {
MOZ_CRASH_UNSAFE_PRINTF(
"%s has a buggy user: "
"it should have removed all this list's elements before "
"the list's destruction",
__PRETTY_FUNCTION__);
}
# endif
}
/*
* Add aElem to the front of the list.
*/
void insertFront(RawType aElem) {
/* Bypass setNext()'s this->isInList() assertion. */
sentinel.setNextUnsafe(aElem);
}
/*
* Add aElem to the back of the list.
*/
void insertBack(RawType aElem) { sentinel.setPreviousUnsafe(aElem); }
/*
* Move all elements from another list to the back
*/
void extendBack(LinkedList<T>&& aOther) {
MOZ_RELEASE_ASSERT(this != &aOther);
if (aOther.isEmpty()) {
return;
}
sentinel.transferBeforeUnsafe(**aOther.begin(), aOther.sentinel);
}
/*
* Move elements from another list to the specified position
*/
void splice(size_t aDestinationPos, LinkedList<T>& aListFrom,
size_t aSourceStart, size_t aSourceLen) {
MOZ_RELEASE_ASSERT(this != &aListFrom);
if (aListFrom.isEmpty() || !aSourceLen) {
return;
}
const auto safeForward = [](LinkedList<T>& aList,
LinkedListElement<T>& aBegin,
size_t aPos) -> LinkedListElement<T>& {
auto* iter = &aBegin;
for (size_t i = 0; i < aPos; ++i, (iter = iter->mNext)) {
if (iter->mIsSentinel) {
break;
}
}
return *iter;
};
auto& sourceBegin =
safeForward(aListFrom, *aListFrom.sentinel.mNext, aSourceStart);
if (sourceBegin.mIsSentinel) {
return;
}
auto& sourceEnd = safeForward(aListFrom, sourceBegin, aSourceLen);
auto& destination = safeForward(*this, *sentinel.mNext, aDestinationPos);
destination.transferBeforeUnsafe(sourceBegin, sourceEnd);
}
/*
* Get the first element of the list, or nullptr if the list is empty.
*/
RawType getFirst() { return sentinel.getNext(); }
ConstRawType getFirst() const { return sentinel.getNext(); }
/*
* Get the last element of the list, or nullptr if the list is empty.
*/
RawType getLast() { return sentinel.getPrevious(); }
ConstRawType getLast() const { return sentinel.getPrevious(); }
/*
* Get and remove the first element of the list. If the list is empty,
* return nullptr.
*/
ClientType popFirst() {
ClientType ret = sentinel.getNext();
if (ret) {
static_cast<LinkedListElement<T>*>(RawType(ret))->remove();
}
return ret;
}
/*
* Get and remove the last element of the list. If the list is empty,
* return nullptr.
*/
ClientType popLast() {
ClientType ret = sentinel.getPrevious();
if (ret) {
static_cast<LinkedListElement<T>*>(RawType(ret))->remove();
}
return ret;
}
/*
* Return true if the list is empty, or false otherwise.
*/
bool isEmpty() const { return !sentinel.isInList(); }
/**
* Returns whether the given element is in the list.
*/
bool contains(ConstRawType aElm) const {
return std::find(begin(), end(), aElm) != end();
}
/*
* Remove all the elements from the list.
*
* This runs in time linear to the list's length, because we have to mark
* each element as not in the list.
*/
void clear() {
while (popFirst()) {
}
}
/**
* Return the length of elements in the list.
*/
size_t length() const { return std::distance(begin(), end()); }
/*
* Allow range-based iteration:
*
* for (MyElementType* elt : myList) { ... }
*/
Iterator<RawType, ElementType> begin() {
return Iterator<RawType, ElementType>(getFirst());
}
Iterator<ConstRawType, ConstElementType> begin() const {
return Iterator<ConstRawType, ConstElementType>(getFirst());
}
Iterator<RawType, ElementType> end() {
return Iterator<RawType, ElementType>(nullptr);
}
Iterator<ConstRawType, ConstElementType> end() const {
return Iterator<ConstRawType, ConstElementType>(nullptr);
}
/*
* Measures the memory consumption of the list excluding |this|. Note that
* it only measures the list elements themselves. If the list elements
* contain pointers to other memory blocks, those blocks must be measured
* separately during a subsequent iteration over the list.
*/
size_t sizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
size_t n = 0;
ConstRawType t = getFirst();
while (t) {
n += aMallocSizeOf(t);
t = static_cast<const LinkedListElement<T>*>(t)->getNext();
}
return n;
}
/*
* Like sizeOfExcludingThis(), but measures |this| as well.
*/
size_t sizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
return aMallocSizeOf(this) + sizeOfExcludingThis(aMallocSizeOf);
}
/*
* In a debug build, make sure that the list is sane (no cycles, consistent
* mNext/mPrev pointers, only one sentinel). Has no effect in release builds.
*/
void debugAssertIsSane() const {
# ifdef DEBUG
const LinkedListElement<T>* slow;
const LinkedListElement<T>* fast1;
const LinkedListElement<T>* fast2;
/*
* Check for cycles in the forward singly-linked list using the
* tortoise/hare algorithm.
*/
for (slow = sentinel.mNext, fast1 = sentinel.mNext->mNext,
fast2 = sentinel.mNext->mNext->mNext;
slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
slow = slow->mNext, fast1 = fast2->mNext, fast2 = fast1->mNext) {
MOZ_ASSERT(slow != fast1);
MOZ_ASSERT(slow != fast2);
}
/* Check for cycles in the backward singly-linked list. */
for (slow = sentinel.mPrev, fast1 = sentinel.mPrev->mPrev,
fast2 = sentinel.mPrev->mPrev->mPrev;
slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
slow = slow->mPrev, fast1 = fast2->mPrev, fast2 = fast1->mPrev) {
MOZ_ASSERT(slow != fast1);
MOZ_ASSERT(slow != fast2);
}
/*
* Check that |sentinel| is the only node in the list with
* mIsSentinel == true.
*/
for (const LinkedListElement<T>* elem = sentinel.mNext; elem != &sentinel;
elem = elem->mNext) {
MOZ_ASSERT(!elem->mIsSentinel);
}
/* Check that the mNext/mPrev pointers match up. */
const LinkedListElement<T>* prev = &sentinel;
const LinkedListElement<T>* cur = sentinel.mNext;
do {
MOZ_ASSERT(cur->mPrev == prev);
MOZ_ASSERT(prev->mNext == cur);
prev = cur;
cur = cur->mNext;
} while (cur != &sentinel);
# endif /* ifdef DEBUG */
}
private:
friend class LinkedListElement<T>;
void assertContains(const RawType aValue) const {
# ifdef DEBUG
for (ConstRawType elem = getFirst(); elem; elem = elem->getNext()) {
if (elem == aValue) {
return;
}
}
MOZ_CRASH("element wasn't found in this list!");
# endif
}
LinkedList& operator=(const LinkedList<T>& aOther) = delete;
LinkedList(const LinkedList<T>& aOther) = delete;
};
template <typename T>
size_t RangeSizeEstimate(const LinkedList<T>&) {
return 0;
}
template <typename T>
inline void ImplCycleCollectionUnlink(LinkedList<RefPtr<T>>& aField) {
aField.clear();
}
template <typename T>
inline void ImplCycleCollectionTraverse(
nsCycleCollectionTraversalCallback& aCallback,
LinkedList<RefPtr<T>>& aField, const char* aName, uint32_t aFlags = 0) {
typedef typename detail::LinkedListElementTraits<T> Traits;
typedef typename Traits::RawType RawType;
for (RawType element : aField) {
// RefPtr is stored as a raw pointer in LinkedList.
// So instead of creating a new RefPtr from the raw
// pointer (which is not allowed), we simply call
// CycleCollectionNoteChild against the raw pointer
CycleCollectionNoteChild(aCallback, element, aName, aFlags);
}
}
template <typename T>
class AutoCleanLinkedList : public LinkedList<T> {
private:
using Traits = detail::LinkedListElementTraits<T>;
using ClientType = typename detail::LinkedListElementTraits<T>::ClientType;
public:
AutoCleanLinkedList() = default;
AutoCleanLinkedList(AutoCleanLinkedList&&) = default;
~AutoCleanLinkedList() { clear(); }
AutoCleanLinkedList& operator=(AutoCleanLinkedList&& aOther) = default;
void clear() {
while (ClientType element = this->popFirst()) {
Traits::cleanElement(element);
}
}
};
} /* namespace mozilla */
#endif /* __cplusplus */
#endif /* mozilla_LinkedList_h */