diff options
Diffstat (limited to 'mfbt/LinkedList.h')
| -rw-r--r-- | mfbt/LinkedList.h | 748 |
1 files changed, 748 insertions, 0 deletions
diff --git a/mfbt/LinkedList.h b/mfbt/LinkedList.h new file mode 100644 index 0000000000..850b8594c7 --- /dev/null +++ b/mfbt/LinkedList.h @@ -0,0 +1,748 @@ +/* -*- 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 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: + 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; + typedef LinkedListElement<T>* ElementType; + typedef const LinkedListElement<T>* ConstElementType; + + 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; + } + }; + + 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> +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 */ |