Bug 1277725 - Implement a list class that is both usable and efficient. r=waldo
authorTerrence Cole <terrence@mozilla.com>
Thu, 02 Jun 2016 09:18:40 -0700
changeset 404468 feb9622d58ab943909b06461da6c5fa8658186e4
parent 404467 748b099ff0e967750e4fdda279a705a36fd13c0a
child 404469 4126ffda915309da1578a2b57d8d726000cc91f0
push id1490
push usermtabara@mozilla.com
push dateMon, 31 Jul 2017 14:08:16 +0000
treeherdermozilla-release@70e32e6bf15e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo
bugs1277725
milestone55.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1277725 - Implement a list class that is both usable and efficient. r=waldo MozReview-Commit-ID: JnhnomQwSja
mfbt/DoublyLinkedList.h
mfbt/moz.build
mfbt/tests/TestDoublyLinkedList.cpp
mfbt/tests/moz.build
new file mode 100644
--- /dev/null
+++ b/mfbt/DoublyLinkedList.h
@@ -0,0 +1,357 @@
+/* -*- 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 doubly-linked list with flexible next/prev naming. */
+
+#ifndef mozilla_DoublyLinkedList_h
+#define mozilla_DoublyLinkedList_h
+
+#include <algorithm>
+#include <iterator>
+
+/**
+ * Where mozilla::LinkedList strives for ease of use above all other
+ * considerations, mozilla::DoublyLinkedList strives for flexibility. The
+ * following are things that can be done with mozilla::DoublyLinkedList that
+ * cannot be done with mozilla::LinkedList:
+ *
+ *   * Arbitrary next/prev placement and naming. With the tools provided here,
+ *     the next and previous pointers can be at the end of the structure, in a
+ *     sub-structure, stored with a tag, in a union, wherever, as long as you
+ *     can look them up and set them on demand.
+ *   * Can be used without deriving from a new base and, thus, does not require
+ *     use of constructors.
+ *
+ * Example:
+ *
+ *   class Observer : public DoublyLinkedListElement<Observer>
+ *   {
+ *   public:
+ *     void observe(char* aTopic) { ... }
+ *   };
+ *
+ *   class ObserverContainer
+ *   {
+ *   private:
+ *     DoublyLinkedList<Observer> mList;
+ *
+ *   public:
+ *     void addObserver(Observer* aObserver)
+ *     {
+ *       // Will assert if |aObserver| is part of another list.
+ *       mList.pushBack(aObserver);
+ *     }
+ *
+ *     void removeObserver(Observer* aObserver)
+ *     {
+ *       // Will assert if |aObserver| is not part of |list|.
+ *       mList.remove(aObserver);
+ *     }
+ *
+ *     void notifyObservers(char* aTopic)
+ *     {
+ *       for (Observer* o : mList) {
+ *         o->observe(aTopic);
+ *       }
+ *     }
+ *   };
+ */
+
+namespace mozilla {
+
+/**
+ * Provides access to a next and previous element pointer named |mNext| and
+ * |mPrev| respectively. This class is the default and will work if the list
+ * element derives from DoublyLinkedListElement.
+ *
+ * Although designed to work with DoublyLinkedListElement this will als work
+ * with any class that defines |mNext| and |mPrev| members with the correct
+ * type.
+ */
+template <typename T>
+struct DoublyLinkedSiblingAccess {
+  static void SetNext(T* aElm, T* aNext) { aElm->mNext = aNext; }
+  static T* GetNext(T* aElm) { return aElm->mNext; }
+  static void SetPrev(T* aElm, T* aPrev) { aElm->mPrev = aPrev; }
+  static T* GetPrev(T* aElm) { return aElm->mPrev; }
+};
+
+/**
+ *  Deriving from this will allow T to be inserted into and removed from a
+ *  DoublyLinkedList.
+ */
+template <typename T>
+struct DoublyLinkedListElement
+{
+  friend struct DoublyLinkedSiblingAccess<T>;
+  T* mNext;
+  T* mPrev;
+
+public:
+  DoublyLinkedListElement() : mNext(nullptr), mPrev(nullptr) {}
+};
+
+/**
+ * A doubly linked list. |T| is the type of element stored in this list. |T|
+ * must contain or have access to unique next and previous element pointers.
+ * The template argument |SiblingAccess| provides code to tell this list how to
+ * get and set the next and previous pointers. The actual storage of next/prev
+ * links may reside anywhere and be encoded in any way.
+ */
+template <typename T, typename SiblingAccess = DoublyLinkedSiblingAccess<T>>
+class DoublyLinkedList final
+{
+  T* mHead;
+  T* mTail;
+
+  /**
+   * Checks that either the list is empty and both mHead and mTail are nullptr
+   * or the list has entries and both mHead and mTail are non-null.
+   */
+  bool isStateValid() const {
+    return (mHead != nullptr) == (mTail != nullptr);
+  }
+
+  static bool ElementNotInList(T* aElm) {
+    return !SiblingAccess::GetNext(aElm) && !SiblingAccess::GetPrev(aElm);
+  }
+
+public:
+  DoublyLinkedList() : mHead(nullptr), mTail(nullptr) {}
+
+  class Iterator final {
+    T* 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&;
+
+    Iterator() : mCurrent(nullptr) {}
+    explicit Iterator(T* aCurrent) : mCurrent(aCurrent) {}
+
+    T& operator *() const { return *mCurrent; }
+    T* operator ->() const { return mCurrent; }
+
+    Iterator& operator++() {
+      mCurrent = SiblingAccess::GetNext(mCurrent);
+      return *this;
+    }
+
+    Iterator operator++(int) {
+      Iterator result = *this;
+      ++(*this);
+      return result;
+    }
+
+    Iterator& operator--() {
+      mCurrent = SiblingAccess::GetPrev(mCurrent);
+      return *this;
+    }
+
+    Iterator operator--(int) {
+      Iterator result = *this;
+      --(*this);
+      return result;
+    }
+
+    bool operator!=(const Iterator& aOther) const {
+      return mCurrent != aOther.mCurrent;
+    }
+
+    bool operator==(const Iterator& aOther) const {
+      return mCurrent == aOther.mCurrent;
+    }
+
+    explicit operator bool() const {
+      return mCurrent;
+    }
+  };
+
+  Iterator begin() { return Iterator(mHead); }
+  const Iterator begin() const { return Iterator(mHead); }
+  const Iterator cbegin() const { return Iterator(mHead); }
+
+  Iterator end() { return Iterator(); }
+  const Iterator end() const { return Iterator(); }
+  const Iterator cend() const { return Iterator(); }
+
+  /**
+   * Returns true if the list contains no elements.
+   */
+  bool isEmpty() const {
+    MOZ_ASSERT(isStateValid());
+    return mHead == nullptr;
+  }
+
+  /**
+   * Inserts aElm into the list at the head position. |aElm| must not already
+   * be in a list.
+   */
+  void pushFront(T* aElm) {
+    MOZ_ASSERT(aElm);
+    MOZ_ASSERT(ElementNotInList(aElm));
+    MOZ_ASSERT(isStateValid());
+
+    SiblingAccess::SetNext(aElm, mHead);
+    if (mHead) {
+      MOZ_ASSERT(!SiblingAccess::GetPrev(mHead));
+      SiblingAccess::SetPrev(mHead, aElm);
+    }
+
+    mHead = aElm;
+    if (!mTail) {
+      mTail = aElm;
+    }
+  }
+
+  /**
+   * Remove the head of the list and return it. Calling this on an empty list
+   * will assert.
+   */
+  T* popFront() {
+    MOZ_ASSERT(!isEmpty());
+    MOZ_ASSERT(isStateValid());
+
+    T* result = mHead;
+    mHead = result ? SiblingAccess::GetNext(result) : nullptr;
+    if (mHead) {
+      SiblingAccess::SetPrev(mHead, nullptr);
+    }
+
+    if (mTail == result) {
+      mTail = nullptr;
+    }
+
+    if (result) {
+      SiblingAccess::SetNext(result, nullptr);
+      SiblingAccess::SetPrev(result, nullptr);
+    }
+
+    return result;
+  }
+
+  /**
+   * Inserts aElm into the list at the tail position. |aElm| must not already
+   * be in a list.
+   */
+  void pushBack(T* aElm) {
+    MOZ_ASSERT(aElm);
+    MOZ_ASSERT(ElementNotInList(aElm));
+    MOZ_ASSERT(isStateValid());
+
+    SiblingAccess::SetNext(aElm, nullptr);
+    SiblingAccess::SetPrev(aElm, mTail);
+    if (mTail) {
+      MOZ_ASSERT(!SiblingAccess::GetNext(mTail));
+      SiblingAccess::SetNext(mTail, aElm);
+    }
+
+    mTail = aElm;
+    if (!mHead) {
+      mHead = aElm;
+    }
+  }
+
+  /**
+   * Remove the tail of the list and return it. Calling this on an empty list
+   * will assert.
+   */
+  T* popBack() {
+    MOZ_ASSERT(!isEmpty());
+    MOZ_ASSERT(isStateValid());
+
+    T* result = mTail;
+    mTail = result ? SiblingAccess::GetPrev(result) : nullptr;
+    if (mTail) {
+      SiblingAccess::SetNext(mTail, nullptr);
+    }
+
+    if (mHead == result) {
+      mHead = nullptr;
+    }
+
+    if (result) {
+      SiblingAccess::SetNext(result, nullptr);
+      SiblingAccess::SetPrev(result, nullptr);
+    }
+
+    return result;
+  }
+
+  /**
+   * Insert the given |aElm| *before* |aIter|.
+   */
+  void insertBefore(const Iterator& aIter, T* aElm) {
+    MOZ_ASSERT(aElm);
+    MOZ_ASSERT(ElementNotInList(aElm));
+    MOZ_ASSERT(isStateValid());
+
+    if (!aIter) {
+      return pushBack(aElm);
+    } else if (aIter == begin()) {
+      return pushFront(aElm);
+    }
+
+    T* after = &(*aIter);
+    T* before = SiblingAccess::GetPrev(after);
+    MOZ_ASSERT(before);
+
+    SiblingAccess::SetNext(before, aElm);
+    SiblingAccess::SetPrev(aElm, before);
+    SiblingAccess::SetNext(aElm, after);
+    SiblingAccess::SetPrev(after, aElm);
+  }
+
+  /**
+   * Removes the given element from the list. The element must be in this list.
+   */
+  void remove(T* aElm) {
+    MOZ_ASSERT(aElm);
+    MOZ_ASSERT(SiblingAccess::GetNext(aElm) || SiblingAccess::GetPrev(aElm) ||
+               (aElm == mHead && aElm == mTail),
+               "Attempted to remove element not in this list");
+
+    if (T* prev = SiblingAccess::GetPrev(aElm)) {
+      SiblingAccess::SetNext(prev, SiblingAccess::GetNext(aElm));
+    } else {
+      MOZ_ASSERT(mHead == aElm);
+      mHead = SiblingAccess::GetNext(aElm);
+    }
+
+    if (T* next = SiblingAccess::GetNext(aElm)) {
+      SiblingAccess::SetPrev(next, SiblingAccess::GetPrev(aElm));
+    } else {
+      MOZ_ASSERT(mTail == aElm);
+      mTail = SiblingAccess::GetPrev(aElm);
+    }
+
+    SiblingAccess::SetNext(aElm, nullptr);
+    SiblingAccess::SetPrev(aElm, nullptr);
+  }
+
+  /**
+   * Returns an iterator referencing the first found element whose value matches
+   * the given element according to operator==.
+   */
+  Iterator find(const T& aElm) {
+    return std::find(begin(), end(), aElm);
+  }
+
+  /**
+   * Returns whether the given element is in the list. Note that this uses
+   * T::operator==, not pointer comparison.
+   */
+  bool contains(const T& aElm) {
+    return find(aElm) != Iterator();
+  }
+};
+
+} // namespace mozilla
+
+#endif // mozilla_DoublyLinkedList_h
--- a/mfbt/moz.build
+++ b/mfbt/moz.build
@@ -30,16 +30,17 @@ EXPORTS.mozilla = [
     'Char16.h',
     'CheckedInt.h',
     'Compiler.h',
     'Compression.h',
     'DebugOnly.h',
     'decimal/Decimal.h',
     'double-conversion/source/double-conversion.h',
     'double-conversion/source/utils.h',
+    'DoublyLinkedList.h',
     'EndianUtils.h',
     'EnumeratedArray.h',
     'EnumeratedRange.h',
     'EnumSet.h',
     'EnumTypeTraits.h',
     'FastBernoulliTrial.h',
     'FloatingPoint.h',
     'GuardObjects.h',
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestDoublyLinkedList.cpp
@@ -0,0 +1,173 @@
+/* -*- 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/. */
+
+#include "mozilla/Assertions.h"
+#include "mozilla/DoublyLinkedList.h"
+
+using mozilla::DoublyLinkedList;
+using mozilla::DoublyLinkedListElement;
+
+struct SomeClass : public DoublyLinkedListElement<SomeClass> {
+  unsigned int mValue;
+  explicit SomeClass(int aValue) : mValue(aValue) {}
+  void incr() { ++mValue; }
+  bool operator==(const SomeClass& other) { return mValue == other.mValue; }
+};
+
+template <typename ListType, size_t N>
+static void
+CheckListValues(ListType& list, unsigned int (&values)[N])
+{
+  size_t count = 0;
+  for (auto& x : list) {
+    MOZ_RELEASE_ASSERT(x.mValue == values[count]);
+    ++count;
+  }
+  MOZ_RELEASE_ASSERT(count == N);
+}
+
+static void
+TestDoublyLinkedList()
+{
+  DoublyLinkedList<SomeClass> list;
+
+  SomeClass one(1), two(2), three(3);
+
+  MOZ_RELEASE_ASSERT(list.isEmpty());
+  MOZ_RELEASE_ASSERT(!list.begin());
+  MOZ_RELEASE_ASSERT(!list.end());
+
+  for (SomeClass& x : list) {
+    MOZ_RELEASE_ASSERT(x.mValue);
+    MOZ_RELEASE_ASSERT(false);
+  }
+
+  list.pushFront(&one);
+  { unsigned int check[] { 1 }; CheckListValues(list, check); }
+
+  MOZ_RELEASE_ASSERT(list.contains(one));
+  MOZ_RELEASE_ASSERT(!list.contains(two));
+  MOZ_RELEASE_ASSERT(!list.contains(three));
+
+  MOZ_RELEASE_ASSERT(!list.isEmpty());
+  MOZ_RELEASE_ASSERT(list.begin()->mValue == 1);
+  MOZ_RELEASE_ASSERT(!list.end());
+
+  list.pushFront(&two);
+  { unsigned int check[] { 2, 1 }; CheckListValues(list, check); }
+
+  MOZ_RELEASE_ASSERT(list.begin()->mValue == 2);
+  MOZ_RELEASE_ASSERT(!list.end());
+  MOZ_RELEASE_ASSERT(!list.contains(three));
+
+  list.pushBack(&three);
+  { unsigned int check[] { 2, 1, 3 }; CheckListValues(list, check); }
+
+  MOZ_RELEASE_ASSERT(list.begin()->mValue == 2);
+  MOZ_RELEASE_ASSERT(!list.end());
+
+  list.remove(&one);
+  { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
+
+  list.insertBefore(list.find(three), &one);
+  { unsigned int check[] { 2, 1, 3 }; CheckListValues(list, check); }
+
+  list.remove(&three);
+  { unsigned int check[] { 2, 1 }; CheckListValues(list, check); }
+
+  list.insertBefore(list.find(two), &three);
+  { unsigned int check[] { 3, 2, 1 }; CheckListValues(list, check); }
+
+  list.remove(&three);
+  { unsigned int check[] { 2, 1 }; CheckListValues(list, check); }
+
+  list.insertBefore(++list.find(two), &three);
+  { unsigned int check[] { 2, 3, 1 }; CheckListValues(list, check); }
+
+  list.remove(&one);
+  { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
+
+  list.remove(&two);
+  { unsigned int check[] { 3 }; CheckListValues(list, check); }
+
+  list.insertBefore(list.find(three), &two);
+  { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
+
+  list.remove(&three);
+  { unsigned int check[] { 2 }; CheckListValues(list, check); }
+
+  list.remove(&two);
+  MOZ_RELEASE_ASSERT(list.isEmpty());
+
+  list.pushBack(&three);
+  { unsigned int check[] { 3 }; CheckListValues(list, check); }
+
+  list.pushFront(&two);
+  { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
+
+  // This should modify the values of |two| and |three| as pointers to them are
+  // stored in the list, not copies.
+  for (SomeClass& x : list) {
+    x.incr();
+  }
+
+  MOZ_RELEASE_ASSERT(*list.begin() == two);
+  MOZ_RELEASE_ASSERT(*++list.begin() == three);
+
+  SomeClass four(4);
+  MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));
+}
+
+static void
+TestCustomAccessor()
+{
+  struct InTwoLists {
+    explicit InTwoLists(unsigned int aValue) : mValue(aValue) {}
+    DoublyLinkedListElement<InTwoLists> mListOne;
+    DoublyLinkedListElement<InTwoLists> mListTwo;
+    unsigned int mValue;
+  };
+
+  struct ListOneSiblingAccess {
+    static void SetNext(InTwoLists* aElm, InTwoLists* aNext) { aElm->mListOne.mNext = aNext; }
+    static InTwoLists* GetNext(InTwoLists* aElm) { return aElm->mListOne.mNext; }
+    static void SetPrev(InTwoLists* aElm, InTwoLists* aPrev) { aElm->mListOne.mPrev = aPrev; }
+    static InTwoLists* GetPrev(InTwoLists* aElm) { return aElm->mListOne.mPrev; }
+  };
+
+  struct ListTwoSiblingAccess {
+    static void SetNext(InTwoLists* aElm, InTwoLists* aNext) { aElm->mListTwo.mNext = aNext; }
+    static InTwoLists* GetNext(InTwoLists* aElm) { return aElm->mListTwo.mNext; }
+    static void SetPrev(InTwoLists* aElm, InTwoLists* aPrev) { aElm->mListTwo.mPrev = aPrev; }
+    static InTwoLists* GetPrev(InTwoLists* aElm) { return aElm->mListTwo.mPrev; }
+  };
+
+  DoublyLinkedList<InTwoLists, ListOneSiblingAccess> listOne;
+  DoublyLinkedList<InTwoLists, ListTwoSiblingAccess> listTwo;
+
+  InTwoLists one(1);
+  InTwoLists two(2);
+
+  listOne.pushBack(&one);
+  listOne.pushBack(&two);
+  { unsigned int check[] { 1, 2 }; CheckListValues(listOne, check); }
+
+  listTwo.pushBack(&one);
+  listTwo.pushBack(&two);
+  { unsigned int check[] { 1, 2 }; CheckListValues(listTwo, check); }
+
+  (void)listTwo.popBack();
+  { unsigned int check[] { 1, 2 }; CheckListValues(listOne, check); }
+  { unsigned int check[] { 1 }; CheckListValues(listTwo, check); }
+}
+
+int
+main()
+{
+  TestDoublyLinkedList();
+  TestCustomAccessor();
+  return 0;
+}
--- a/mfbt/tests/moz.build
+++ b/mfbt/tests/moz.build
@@ -16,16 +16,17 @@ CppUnitTests([
     'TestBinarySearch',
     'TestBloomFilter',
     'TestBufferList',
     'TestCasting',
     'TestCeilingFloor',
     'TestCheckedInt',
     'TestCountPopulation',
     'TestCountZeroes',
+    'TestDoublyLinkedList',
     'TestEndian',
     'TestEnumeratedArray',
     'TestEnumSet',
     'TestEnumTypeTraits',
     'TestFastBernoulliTrial',
     'TestFloatingPoint',
     'TestIntegerPrintfMacros',
     'TestIntegerRange',