michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim: set ts=8 sts=2 et sw=2 tw=80: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /* A type-safe doubly-linked list class. */
michael@0: 
michael@0: /*
michael@0:  * The classes LinkedList<T> and LinkedListElement<T> together form a
michael@0:  * convenient, type-safe doubly-linked list implementation.
michael@0:  *
michael@0:  * The class T which will be inserted into the linked list must inherit from
michael@0:  * LinkedListElement<T>.  A given object may be in only one linked list at a
michael@0:  * time.
michael@0:  *
michael@0:  * A LinkedListElement automatically removes itself from the list upon
michael@0:  * destruction, and a LinkedList will fatally assert in debug builds if it's
michael@0:  * non-empty when it's destructed.
michael@0:  *
michael@0:  * For example, you might use LinkedList in a simple observer list class as
michael@0:  * follows.
michael@0:  *
michael@0:  *   class Observer : public LinkedListElement<Observer>
michael@0:  *   {
michael@0:  *     public:
michael@0:  *       void observe(char* topic) { ... }
michael@0:  *   };
michael@0:  *
michael@0:  *   class ObserverContainer
michael@0:  *   {
michael@0:  *     private:
michael@0:  *       LinkedList<Observer> list;
michael@0:  *
michael@0:  *     public:
michael@0:  *       void addObserver(Observer* observer) {
michael@0:  *         // Will assert if |observer| is part of another list.
michael@0:  *         list.insertBack(observer);
michael@0:  *       }
michael@0:  *
michael@0:  *       void removeObserver(Observer* observer) {
michael@0:  *         // Will assert if |observer| is not part of some list.
michael@0:  *         observer.remove();
michael@0:  *         // Or, will assert if |observer| is not part of |list| specifically.
michael@0:  *         // observer.removeFrom(list);
michael@0:  *       }
michael@0:  *
michael@0:  *       void notifyObservers(char* topic) {
michael@0:  *         for (Observer* o = list.getFirst(); o != nullptr; o = o->getNext())
michael@0:  *           o->observe(topic);
michael@0:  *       }
michael@0:  *   };
michael@0:  *
michael@0:  */
michael@0: 
michael@0: #ifndef mozilla_LinkedList_h
michael@0: #define mozilla_LinkedList_h
michael@0: 
michael@0: #include "mozilla/Assertions.h"
michael@0: #include "mozilla/Attributes.h"
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include "mozilla/Move.h"
michael@0: #include "mozilla/NullPtr.h"
michael@0: 
michael@0: #ifdef __cplusplus
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: template<typename T>
michael@0: class LinkedList;
michael@0: 
michael@0: template<typename T>
michael@0: class LinkedListElement
michael@0: {
michael@0:     /*
michael@0:      * It's convenient that we return nullptr when getNext() or getPrevious()
michael@0:      * hits the end of the list, but doing so costs an extra word of storage in
michael@0:      * each linked list node (to keep track of whether |this| is the sentinel
michael@0:      * node) and a branch on this value in getNext/getPrevious.
michael@0:      *
michael@0:      * We could get rid of the extra word of storage by shoving the "is
michael@0:      * sentinel" bit into one of the pointers, although this would, of course,
michael@0:      * have performance implications of its own.
michael@0:      *
michael@0:      * But the goal here isn't to win an award for the fastest or slimmest
michael@0:      * linked list; rather, we want a *convenient* linked list.  So we won't
michael@0:      * waste time guessing which micro-optimization strategy is best.
michael@0:      *
michael@0:      *
michael@0:      * Speaking of unnecessary work, it's worth addressing here why we wrote
michael@0:      * mozilla::LinkedList in the first place, instead of using stl::list.
michael@0:      *
michael@0:      * The key difference between mozilla::LinkedList and stl::list is that
michael@0:      * mozilla::LinkedList stores the prev/next pointers in the object itself,
michael@0:      * while stl::list stores the prev/next pointers in a list element which
michael@0:      * itself points to the object being stored.
michael@0:      *
michael@0:      * mozilla::LinkedList's approach makes it harder to store an object in more
michael@0:      * than one list.  But the upside is that you can call next() / prev() /
michael@0:      * remove() directly on the object.  With stl::list, you'd need to store a
michael@0:      * pointer to its iterator in the object in order to accomplish this.  Not
michael@0:      * only would this waste space, but you'd have to remember to update that
michael@0:      * pointer every time you added or removed the object from a list.
michael@0:      *
michael@0:      * In-place, constant-time removal is a killer feature of doubly-linked
michael@0:      * lists, and supporting this painlessly was a key design criterion.
michael@0:      */
michael@0: 
michael@0:   private:
michael@0:     LinkedListElement* next;
michael@0:     LinkedListElement* prev;
michael@0:     const bool isSentinel;
michael@0: 
michael@0:   public:
michael@0:     LinkedListElement()
michael@0:       : next(MOZ_THIS_IN_INITIALIZER_LIST()),
michael@0:         prev(MOZ_THIS_IN_INITIALIZER_LIST()),
michael@0:         isSentinel(false)
michael@0:     { }
michael@0: 
michael@0:     LinkedListElement(LinkedListElement<T>&& other)
michael@0:       : isSentinel(other.isSentinel)
michael@0:     {
michael@0:       if (!other.isInList()) {
michael@0:         next = this;
michael@0:         prev = this;
michael@0:         return;
michael@0:       }
michael@0: 
michael@0:       MOZ_ASSERT(other.next->prev == &other);
michael@0:       MOZ_ASSERT(other.prev->next == &other);
michael@0: 
michael@0:       /*
michael@0:        * Initialize |this| with |other|'s prev/next pointers, and adjust those
michael@0:        * element to point to this one.
michael@0:        */
michael@0:       next = other.next;
michael@0:       prev = other.prev;
michael@0: 
michael@0:       next->prev = this;
michael@0:       prev->next = this;
michael@0: 
michael@0:       /*
michael@0:        * Adjust |other| so it doesn't think it's in a list.  This makes it
michael@0:        * safely destructable.
michael@0:        */
michael@0:       other.next = &other;
michael@0:       other.prev = &other;
michael@0:     }
michael@0: 
michael@0:     ~LinkedListElement() {
michael@0:       if (!isSentinel && isInList())
michael@0:         remove();
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Get the next element in the list, or nullptr if this is the last element
michael@0:      * in the list.
michael@0:      */
michael@0:     T* getNext() {
michael@0:       return next->asT();
michael@0:     }
michael@0:     const T* getNext() const {
michael@0:       return next->asT();
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Get the previous element in the list, or nullptr if this is the first
michael@0:      * element in the list.
michael@0:      */
michael@0:     T* getPrevious() {
michael@0:       return prev->asT();
michael@0:     }
michael@0:     const T* getPrevious() const {
michael@0:       return prev->asT();
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Insert elem after this element in the list.  |this| must be part of a
michael@0:      * linked list when you call setNext(); otherwise, this method will assert.
michael@0:      */
michael@0:     void setNext(T* elem) {
michael@0:       MOZ_ASSERT(isInList());
michael@0:       setNextUnsafe(elem);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Insert elem before this element in the list.  |this| must be part of a
michael@0:      * linked list when you call setPrevious(); otherwise, this method will
michael@0:      * assert.
michael@0:      */
michael@0:     void setPrevious(T* elem) {
michael@0:       MOZ_ASSERT(isInList());
michael@0:       setPreviousUnsafe(elem);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Remove this element from the list which contains it.  If this element is
michael@0:      * not currently part of a linked list, this method asserts.
michael@0:      */
michael@0:     void remove() {
michael@0:       MOZ_ASSERT(isInList());
michael@0: 
michael@0:       prev->next = next;
michael@0:       next->prev = prev;
michael@0:       next = this;
michael@0:       prev = this;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Identical to remove(), but also asserts in debug builds that this element
michael@0:      * is in list.
michael@0:      */
michael@0:     void removeFrom(const LinkedList<T>& list) {
michael@0:       list.assertContains(asT());
michael@0:       remove();
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Return true if |this| part is of a linked list, and false otherwise.
michael@0:      */
michael@0:     bool isInList() const {
michael@0:       MOZ_ASSERT((next == this) == (prev == this));
michael@0:       return next != this;
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     friend class LinkedList<T>;
michael@0: 
michael@0:     enum NodeKind {
michael@0:       NODE_KIND_NORMAL,
michael@0:       NODE_KIND_SENTINEL
michael@0:     };
michael@0: 
michael@0:     LinkedListElement(NodeKind nodeKind)
michael@0:       : next(MOZ_THIS_IN_INITIALIZER_LIST()),
michael@0:         prev(MOZ_THIS_IN_INITIALIZER_LIST()),
michael@0:         isSentinel(nodeKind == NODE_KIND_SENTINEL)
michael@0:     { }
michael@0: 
michael@0:     /*
michael@0:      * Return |this| cast to T* if we're a normal node, or return nullptr if
michael@0:      * we're a sentinel node.
michael@0:      */
michael@0:     T* asT() {
michael@0:       if (isSentinel)
michael@0:         return nullptr;
michael@0: 
michael@0:       return static_cast<T*>(this);
michael@0:     }
michael@0:     const T* asT() const {
michael@0:       if (isSentinel)
michael@0:         return nullptr;
michael@0: 
michael@0:       return static_cast<const T*>(this);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Insert elem after this element, but don't check that this element is in
michael@0:      * the list.  This is called by LinkedList::insertFront().
michael@0:      */
michael@0:     void setNextUnsafe(T* elem) {
michael@0:       LinkedListElement *listElem = static_cast<LinkedListElement*>(elem);
michael@0:       MOZ_ASSERT(!listElem->isInList());
michael@0: 
michael@0:       listElem->next = this->next;
michael@0:       listElem->prev = this;
michael@0:       this->next->prev = listElem;
michael@0:       this->next = listElem;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Insert elem before this element, but don't check that this element is in
michael@0:      * the list.  This is called by LinkedList::insertBack().
michael@0:      */
michael@0:     void setPreviousUnsafe(T* elem) {
michael@0:       LinkedListElement<T>* listElem = static_cast<LinkedListElement<T>*>(elem);
michael@0:       MOZ_ASSERT(!listElem->isInList());
michael@0: 
michael@0:       listElem->next = this;
michael@0:       listElem->prev = this->prev;
michael@0:       this->prev->next = listElem;
michael@0:       this->prev = listElem;
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     LinkedListElement& operator=(const LinkedListElement<T>& other) MOZ_DELETE;
michael@0:     LinkedListElement(const LinkedListElement<T>& other) MOZ_DELETE;
michael@0: };
michael@0: 
michael@0: template<typename T>
michael@0: class LinkedList
michael@0: {
michael@0:   private:
michael@0:     LinkedListElement<T> sentinel;
michael@0: 
michael@0:   public:
michael@0:     LinkedList() : sentinel(LinkedListElement<T>::NODE_KIND_SENTINEL) { }
michael@0: 
michael@0:     LinkedList(LinkedList<T>&& other)
michael@0:       : sentinel(mozilla::Move(other.sentinel))
michael@0:     { }
michael@0: 
michael@0:     ~LinkedList() {
michael@0:       MOZ_ASSERT(isEmpty());
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Add elem to the front of the list.
michael@0:      */
michael@0:     void insertFront(T* elem) {
michael@0:       /* Bypass setNext()'s this->isInList() assertion. */
michael@0:       sentinel.setNextUnsafe(elem);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Add elem to the back of the list.
michael@0:      */
michael@0:     void insertBack(T* elem) {
michael@0:       sentinel.setPreviousUnsafe(elem);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Get the first element of the list, or nullptr if the list is empty.
michael@0:      */
michael@0:     T* getFirst() {
michael@0:       return sentinel.getNext();
michael@0:     }
michael@0:     const T* getFirst() const {
michael@0:       return sentinel.getNext();
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Get the last element of the list, or nullptr if the list is empty.
michael@0:      */
michael@0:     T* getLast() {
michael@0:       return sentinel.getPrevious();
michael@0:     }
michael@0:     const T* getLast() const {
michael@0:       return sentinel.getPrevious();
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Get and remove the first element of the list.  If the list is empty,
michael@0:      * return nullptr.
michael@0:      */
michael@0:     T* popFirst() {
michael@0:       T* ret = sentinel.getNext();
michael@0:       if (ret)
michael@0:         static_cast<LinkedListElement<T>*>(ret)->remove();
michael@0:       return ret;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Get and remove the last element of the list.  If the list is empty,
michael@0:      * return nullptr.
michael@0:      */
michael@0:     T* popLast() {
michael@0:       T* ret = sentinel.getPrevious();
michael@0:       if (ret)
michael@0:         static_cast<LinkedListElement<T>*>(ret)->remove();
michael@0:       return ret;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Return true if the list is empty, or false otherwise.
michael@0:      */
michael@0:     bool isEmpty() const {
michael@0:       return !sentinel.isInList();
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Remove all the elements from the list.
michael@0:      *
michael@0:      * This runs in time linear to the list's length, because we have to mark
michael@0:      * each element as not in the list.
michael@0:      */
michael@0:     void clear() {
michael@0:       while (popFirst())
michael@0:         continue;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Measures the memory consumption of the list excluding |this|.  Note that
michael@0:      * it only measures the list elements themselves.  If the list elements
michael@0:      * contain pointers to other memory blocks, those blocks must be measured
michael@0:      * separately during a subsequent iteration over the list.
michael@0:      */
michael@0:     size_t sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const {
michael@0:       size_t n = 0;
michael@0:       for (const T* t = getFirst(); t; t = t->getNext())
michael@0:         n += mallocSizeOf(t);
michael@0:       return n;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Like sizeOfExcludingThis(), but measures |this| as well.
michael@0:      */
michael@0:     size_t sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const {
michael@0:       return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * In a debug build, make sure that the list is sane (no cycles, consistent
michael@0:      * next/prev pointers, only one sentinel).  Has no effect in release builds.
michael@0:      */
michael@0:     void debugAssertIsSane() const {
michael@0: #ifdef DEBUG
michael@0:       const LinkedListElement<T>* slow;
michael@0:       const LinkedListElement<T>* fast1;
michael@0:       const LinkedListElement<T>* fast2;
michael@0: 
michael@0:       /*
michael@0:        * Check for cycles in the forward singly-linked list using the
michael@0:        * tortoise/hare algorithm.
michael@0:        */
michael@0:       for (slow = sentinel.next,
michael@0:            fast1 = sentinel.next->next,
michael@0:            fast2 = sentinel.next->next->next;
michael@0:            slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
michael@0:            slow = slow->next, fast1 = fast2->next, fast2 = fast1->next)
michael@0:       {
michael@0:         MOZ_ASSERT(slow != fast1);
michael@0:         MOZ_ASSERT(slow != fast2);
michael@0:       }
michael@0: 
michael@0:       /* Check for cycles in the backward singly-linked list. */
michael@0:       for (slow = sentinel.prev,
michael@0:            fast1 = sentinel.prev->prev,
michael@0:            fast2 = sentinel.prev->prev->prev;
michael@0:            slow != &sentinel && fast1 != &sentinel && fast2 != &sentinel;
michael@0:            slow = slow->prev, fast1 = fast2->prev, fast2 = fast1->prev)
michael@0:       {
michael@0:         MOZ_ASSERT(slow != fast1);
michael@0:         MOZ_ASSERT(slow != fast2);
michael@0:       }
michael@0: 
michael@0:       /*
michael@0:        * Check that |sentinel| is the only node in the list with
michael@0:        * isSentinel == true.
michael@0:        */
michael@0:       for (const LinkedListElement<T>* elem = sentinel.next;
michael@0:            elem != &sentinel;
michael@0:            elem = elem->next)
michael@0:       {
michael@0:         MOZ_ASSERT(!elem->isSentinel);
michael@0:       }
michael@0: 
michael@0:       /* Check that the next/prev pointers match up. */
michael@0:       const LinkedListElement<T>* prev = &sentinel;
michael@0:       const LinkedListElement<T>* cur = sentinel.next;
michael@0:       do {
michael@0:           MOZ_ASSERT(cur->prev == prev);
michael@0:           MOZ_ASSERT(prev->next == cur);
michael@0: 
michael@0:           prev = cur;
michael@0:           cur = cur->next;
michael@0:       } while (cur != &sentinel);
michael@0: #endif /* ifdef DEBUG */
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     friend class LinkedListElement<T>;
michael@0: 
michael@0:     void assertContains(const T* t) const {
michael@0: #ifdef DEBUG
michael@0:       for (const T* elem = getFirst();
michael@0:            elem;
michael@0:            elem = elem->getNext())
michael@0:       {
michael@0:         if (elem == t)
michael@0:           return;
michael@0:       }
michael@0:       MOZ_CRASH("element wasn't found in this list!");
michael@0: #endif
michael@0:     }
michael@0: 
michael@0:     LinkedList& operator=(const LinkedList<T>& other) MOZ_DELETE;
michael@0:     LinkedList(const LinkedList<T>& other) MOZ_DELETE;
michael@0: };
michael@0: 
michael@0: } /* namespace mozilla */
michael@0: 
michael@0: #endif /* __cplusplus */
michael@0: 
michael@0: #endif /* mozilla_LinkedList_h */