LinkedList.h

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