tor-browser

LinkedList.h (23869B)

---

/* -*- 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 <iterator>
#include <utility>

#include "mozilla/Assertions.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 {
 using RawType = T*;
 using ConstRawType = const T*;
 using ClientType = T*;
 using ConstClientType = const T*;

 // 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>> {
 using RawType = T*;
 using ConstRawType = const T*;
 using ClientType = RefPtr<T>;
 using ConstClientType = RefPtr<const T>;

 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 {
 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;

 /*
  * 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>*;

 // The sentinel node always closes the circle of the list, making it possible
 // to add/remove elements directly from a LinkedListElement without having a
 // reference to the list. Iterators stop when they reach the sentinel node.
 LinkedListElement<T> mSentinel;

 // Forward and reverse iterator implementation.
 template <bool Const = false, bool Reverse = false>
 class IteratorImpl {
  private:
   using elem_type = std::conditional_t<Const, ConstElementType, ElementType>;
   elem_type mCurrent;

  public:
   using iterator_category = std::forward_iterator_tag;
   using value_type = std::conditional_t<Const, ConstRawType, RawType>;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type*;
   using reference = value_type&;

   explicit IteratorImpl(elem_type aCurrent) : mCurrent(aCurrent) {
     MOZ_ASSERT(mCurrent);
   }

   value_type operator*() const { return mCurrent->asT(); }

   const IteratorImpl& operator++() {
     MOZ_ASSERT(!mCurrent->mIsSentinel);
     mCurrent = Reverse ? mCurrent->mPrev : mCurrent->mNext;
     return *this;
   }

   const IteratorImpl& operator--() {
     // We allow decrementing end() to get the last element.
     mCurrent = Reverse ? mCurrent->mNext : mCurrent->mPrev;
     return *this;
   }

   bool operator==(const IteratorImpl& aOther) const {
     return mCurrent == aOther.mCurrent;
   }

   bool operator!=(const IteratorImpl& aOther) const {
     return mCurrent != aOther.mCurrent;
   }
 };

public:
 LinkedList() : mSentinel(LinkedListElement<T>::NodeKind::Sentinel) {}

 LinkedList(LinkedList<T>&& aOther) : mSentinel(std::move(aOther.mSentinel)) {}

 LinkedList& operator=(LinkedList<T>&& aOther) {
   MOZ_ASSERT(isEmpty(),
              "Assigning to a non-empty list leaks elements in that list!");
   mSentinel = std::move(aOther.mSentinel);
   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
 }

 using iterator = IteratorImpl<false, false>;
 using const_iterator = IteratorImpl<true, false>;
 using reverse_iterator = IteratorImpl<false, true>;
 using const_reverse_iterator = IteratorImpl<true, true>;

 // C++11 Iterator Support
 iterator begin() { return iterator(mSentinel.mNext); }
 const_iterator begin() const { return const_iterator(mSentinel.mNext); }
 const_iterator cbegin() const { return begin(); }
 iterator end() { return iterator(&mSentinel); }
 const_iterator end() const { return const_iterator(&mSentinel); }
 const_iterator cend() const { return end(); }

 reverse_iterator rbegin() { return reverse_iterator(mSentinel.mPrev); }
 const_reverse_iterator rbegin() const {
   return const_reverse_iterator(mSentinel.mPrev);
 }
 const_reverse_iterator crbegin() const { return rbegin(); }
 reverse_iterator rend() { return reverse_iterator(&mSentinel); }
 const_reverse_iterator rend() const {
   return const_reverse_iterator(&mSentinel);
 }
 const_reverse_iterator crend() const { return rend(); }

 /*
  * Add aElem to the front of the list.
  */
 void insertFront(RawType aElem) {
   /* Bypass setNext()'s this->isInList() assertion. */
   mSentinel.setNextUnsafe(aElem);
 }

 /*
  * Add aElem to the back of the list.
  */
 void insertBack(RawType aElem) { mSentinel.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;
   }
   mSentinel.transferBeforeUnsafe(**aOther.begin(), aOther.mSentinel);
 }

 /*
  * 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.mSentinel.mNext, aSourceStart);
   if (sourceBegin.mIsSentinel) {
     return;
   }
   auto& sourceEnd = safeForward(aListFrom, sourceBegin, aSourceLen);
   auto& destination = safeForward(*this, *mSentinel.mNext, aDestinationPos);

   destination.transferBeforeUnsafe(sourceBegin, sourceEnd);
 }

 /*
  * Get the first element of the list, or nullptr if the list is empty.
  */
 RawType getFirst() { return mSentinel.getNext(); }
 ConstRawType getFirst() const { return mSentinel.getNext(); }

 /*
  * Get the last element of the list, or nullptr if the list is empty.
  */
 RawType getLast() { return mSentinel.getPrevious(); }
 ConstRawType getLast() const { return mSentinel.getPrevious(); }

 /*
  * Get and remove the first element of the list.  If the list is empty,
  * return nullptr.
  */
 ClientType popFirst() {
   ClientType ret = mSentinel.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 = mSentinel.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 !mSentinel.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()); }

 /*
  * 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 = mSentinel.mNext, fast1 = mSentinel.mNext->mNext,
       fast2 = mSentinel.mNext->mNext->mNext;
        slow != &mSentinel && fast1 != &mSentinel && fast2 != &mSentinel;
        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 = mSentinel.mPrev, fast1 = mSentinel.mPrev->mPrev,
       fast2 = mSentinel.mPrev->mPrev->mPrev;
        slow != &mSentinel && fast1 != &mSentinel && fast2 != &mSentinel;
        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 = mSentinel.mNext; elem != &mSentinel;
        elem = elem->mNext) {
     MOZ_ASSERT(!elem->mIsSentinel);
   }

   /* Check that the mNext/mPrev pointers match up. */
   const LinkedListElement<T>* prev = &mSentinel;
   const LinkedListElement<T>* cur = mSentinel.mNext;
   do {
     MOZ_ASSERT(cur->mPrev == prev);
     MOZ_ASSERT(prev->mNext == cur);

     prev = cur;
     cur = cur->mNext;
   } while (cur != &mSentinel);
#  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) {
 using Traits = typename detail::LinkedListElementTraits<T>;
 using RawType = typename Traits::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 */