Bug 1396723 - Simplify the trait users of DoublyLinkedList need to define. r=froydnj
authorMike Hommey <mh+mozilla@glandium.org>
Sat, 02 Sep 2017 08:09:58 +0900
changeset 429643 45c68c943e97eb924e07ed701759faae4d57f569
parent 429642 fd7548ea80ed1d73f03804cb52fac6e05d8bf296
child 429644 c3565469003215c97d043d4ef0f88dc4d7e5fa6a
push id7761
push userjlund@mozilla.com
push dateFri, 15 Sep 2017 00:19:52 +0000
treeherdermozilla-beta@c38455951db4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1396723
milestone57.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 1396723 - Simplify the trait users of DoublyLinkedList need to define. r=froydnj While the flexibility of the current trait is nice, it's actually not used to its fullest anywhere, and is boilerplate-y. While it is useful to be able to put the links anywhere, there's not much usefulness from being able to split mNext and mPrev. So instead of a trait that allows to get/set mNext and mPrev independently, we just use a trait that tells how to get a reference to a DoublyLinkedListElement from a list element itself.
js/src/vm/Debugger.h
js/src/vm/Runtime.h
mfbt/DoublyLinkedList.h
mfbt/tests/TestDoublyLinkedList.cpp
--- a/js/src/vm/Debugger.h
+++ b/js/src/vm/Debugger.h
@@ -254,17 +254,17 @@ typedef mozilla::Variant<ScriptSourceObj
 // Either a AbstractFramePtr, for ordinary JS, or a wasm::DebugFrame,
 // for synthesized frame of a wasm code.
 typedef mozilla::Variant<AbstractFramePtr, wasm::DebugFrame*> DebuggerFrameReferent;
 
 class Debugger : private mozilla::LinkedListElement<Debugger>
 {
     friend class Breakpoint;
     friend class DebuggerMemory;
-    friend struct JSRuntime::GlobalObjectWatchersSiblingAccess<Debugger>;
+    friend struct JSRuntime::GlobalObjectWatchersLinkAccess<Debugger>;
     friend class SavedStacks;
     friend class ScriptedOnStepHandler;
     friend class ScriptedOnPopHandler;
     friend class mozilla::LinkedListElement<Debugger>;
     friend class mozilla::LinkedList<Debugger>;
     friend bool (::JS_DefineDebuggerObject)(JSContext* cx, JS::HandleObject obj);
     friend bool (::JS::dbg::IsDebugger)(JSObject&);
     friend bool (::JS::dbg::GetDebuggeeGlobals)(JSContext*, JSObject&, AutoObjectVector&);
@@ -384,36 +384,27 @@ class Debugger : private mozilla::Linked
     js::GCPtrObject uncaughtExceptionHook; /* Strong reference. */
     bool enabled;
     bool allowUnobservedAsmJS;
     bool allowWasmBinarySource;
 
     // Whether to enable code coverage on the Debuggee.
     bool collectCoverageInfo;
 
-    template<typename T>
-    struct DebuggerSiblingAccess {
-      static T* GetNext(T* elm) {
-        return elm->debuggerLink.mNext;
-      }
-      static void SetNext(T* elm, T* next) {
-        elm->debuggerLink.mNext = next;
-      }
-      static T* GetPrev(T* elm) {
-        return elm->debuggerLink.mPrev;
-      }
-      static void SetPrev(T* elm, T* prev) {
-        elm->debuggerLink.mPrev = prev;
+    template <typename T>
+    struct DebuggerLinkAccess {
+      static mozilla::DoublyLinkedListElement<T>& Get(T* aThis) {
+        return aThis->debuggerLink;
       }
     };
 
     // List of all js::Breakpoints in this debugger.
     using BreakpointList =
         mozilla::DoublyLinkedList<js::Breakpoint,
-                                  DebuggerSiblingAccess<js::Breakpoint>>;
+                                  DebuggerLinkAccess<js::Breakpoint>>;
     BreakpointList breakpoints;
 
     // The set of GC numbers for which one or more of this Debugger's observed
     // debuggees participated in.
     using GCNumberSet = HashSet<uint64_t, DefaultHasher<uint64_t>, RuntimeAllocPolicy>;
     GCNumberSet observedGCs;
 
     using AllocationsLog = js::TraceableFifo<AllocationsLogEntry>;
@@ -1590,36 +1581,27 @@ class BreakpointSite {
     friend class Debugger;
 
   public:
     enum class Type { JS, Wasm };
 
   private:
     Type type_;
 
-    template<typename T>
-    struct SiteSiblingAccess {
-      static T* GetNext(T* elm) {
-        return elm->siteLink.mNext;
-      }
-      static void SetNext(T* elm, T* next) {
-        elm->siteLink.mNext = next;
-      }
-      static T* GetPrev(T* elm) {
-        return elm->siteLink.mPrev;
-      }
-      static void SetPrev(T* elm, T* prev) {
-        elm->siteLink.mPrev = prev;
+    template <typename T>
+    struct SiteLinkAccess {
+      static mozilla::DoublyLinkedListElement<T>& Get(T* aThis) {
+        return aThis->siteLink;
       }
     };
 
     // List of all js::Breakpoints at this instruction.
     using BreakpointList =
         mozilla::DoublyLinkedList<js::Breakpoint,
-                                  SiteSiblingAccess<js::Breakpoint>>;
+                                  SiteLinkAccess<js::Breakpoint>>;
     BreakpointList breakpoints;
     size_t enabledCount;  /* number of breakpoints in the list that are enabled */
 
   protected:
     virtual void recompile(FreeOp* fop) = 0;
     bool isEmpty() const;
     inline bool isEnabled() const { return enabledCount > 0; }
 
--- a/js/src/vm/Runtime.h
+++ b/js/src/vm/Runtime.h
@@ -577,34 +577,25 @@ struct JSRuntime : public js::MallocProv
     js::ActiveThreadData<mozilla::LinkedList<JS::detail::WeakCacheBase>> weakCaches_;
   public:
     mozilla::LinkedList<JS::detail::WeakCacheBase>& weakCaches() { return weakCaches_.ref(); }
     void registerWeakCache(JS::detail::WeakCacheBase* cachep) {
         weakCaches().insertBack(cachep);
     }
 
     template <typename T>
-    struct GlobalObjectWatchersSiblingAccess {
-      static T* GetNext(T* elm) {
-        return elm->onNewGlobalObjectWatchersLink.mNext;
-      }
-      static void SetNext(T* elm, T* next) {
-        elm->onNewGlobalObjectWatchersLink.mNext = next;
-      }
-      static T* GetPrev(T* elm) {
-        return elm->onNewGlobalObjectWatchersLink.mPrev;
-      }
-      static void SetPrev(T* elm, T* prev) {
-        elm->onNewGlobalObjectWatchersLink.mPrev = prev;
+    struct GlobalObjectWatchersLinkAccess {
+      static mozilla::DoublyLinkedListElement<T>& Get(T* aThis) {
+        return aThis->onNewGlobalObjectWatchersLink;
       }
     };
 
     using WatchersList =
         mozilla::DoublyLinkedList<js::Debugger,
-                                  GlobalObjectWatchersSiblingAccess<js::Debugger>>;
+                                  GlobalObjectWatchersLinkAccess<js::Debugger>>;
   private:
     /*
      * List of all enabled Debuggers that have onNewGlobalObject handler
      * methods established.
      */
     js::ActiveThreadData<WatchersList> onNewGlobalObjectWatchers_;
 
   public:
--- a/mfbt/DoublyLinkedList.h
+++ b/mfbt/DoublyLinkedList.h
@@ -60,70 +60,76 @@
  *       }
  *     }
  *   };
  */
 
 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
+class DoublyLinkedListElement
 {
-  friend struct DoublyLinkedSiblingAccess<T>;
+  template<typename U, typename E> friend class DoublyLinkedList;
+  friend T;
   T* mNext;
   T* mPrev;
 
 public:
   DoublyLinkedListElement() : mNext(nullptr), mPrev(nullptr) {}
 };
 
 /**
+ * Provides access to a DoublyLinkedListElement within T.
+ *
+ * The default implementation of this template works for types that derive
+ * from DoublyLinkedListElement, but one can specialize for their class so
+ * that some appropriate DoublyLinkedListElement reference is returned.
+ *
+ * For more complex cases (multiple DoublyLinkedListElements, for example),
+ * one can define their own trait class and use that as ElementAccess for
+ * DoublyLinkedList. See TestDoublyLinkedList.cpp for an example.
+ */
+template <typename T>
+struct GetDoublyLinkedListElement
+{
+  static_assert(mozilla::IsBaseOf<DoublyLinkedListElement<T>, T>::value,
+                "You need your own specialization of GetDoublyLinkedListElement"
+                " or use a separate Trait.");
+  static DoublyLinkedListElement<T>& Get(T* aThis)
+  {
+    return *aThis;
+  }
+};
+
+/**
  * 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.
+ * The template argument |ElementAccess| provides code to tell this list how to
+ * get a reference to a DoublyLinkedListElement that may reside anywhere.
  */
-template <typename T, typename SiblingAccess = DoublyLinkedSiblingAccess<T>>
+template <typename T, typename ElementAccess = GetDoublyLinkedListElement<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);
   }
 
   bool ElementNotInList(T* aElm) {
-    if (!SiblingAccess::GetNext(aElm) && !SiblingAccess::GetPrev(aElm)) {
+    if (!ElementAccess::Get(aElm).mNext && !ElementAccess::Get(aElm).mPrev) {
       // Both mNext and mPrev being NULL can mean two things:
       // - the element is not in the list.
       // - the element is the first and only element in the list.
       // So check for the latter.
       return mHead != aElm;
     }
     return false;
   }
@@ -143,28 +149,28 @@ public:
 
     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);
+      mCurrent = ElementAccess::Get(mCurrent).mNext;
       return *this;
     }
 
     Iterator operator++(int) {
       Iterator result = *this;
       ++(*this);
       return result;
     }
 
     Iterator& operator--() {
-      mCurrent = SiblingAccess::GetPrev(mCurrent);
+      mCurrent = ElementAccess::Get(mCurrent).mPrev;
       return *this;
     }
 
     Iterator operator--(int) {
       Iterator result = *this;
       --(*this);
       return result;
     }
@@ -202,20 +208,20 @@ public:
    * 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);
+    ElementAccess::Get(aElm).mNext = mHead;
     if (mHead) {
-      MOZ_ASSERT(!SiblingAccess::GetPrev(mHead));
-      SiblingAccess::SetPrev(mHead, aElm);
+      MOZ_ASSERT(!ElementAccess::Get(mHead).mPrev);
+      ElementAccess::Get(mHead).mPrev = aElm;
     }
 
     mHead = aElm;
     if (!mTail) {
       mTail = aElm;
     }
   }
 
@@ -223,47 +229,47 @@ public:
    * 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;
+    mHead = result ? ElementAccess::Get(result).mNext : nullptr;
     if (mHead) {
-      SiblingAccess::SetPrev(mHead, nullptr);
+      ElementAccess::Get(mHead).mPrev = nullptr;
     }
 
     if (mTail == result) {
       mTail = nullptr;
     }
 
     if (result) {
-      SiblingAccess::SetNext(result, nullptr);
-      SiblingAccess::SetPrev(result, nullptr);
+      ElementAccess::Get(result).mNext = nullptr;
+      ElementAccess::Get(result).mPrev = 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);
+    ElementAccess::Get(aElm).mNext = nullptr;
+    ElementAccess::Get(aElm).mPrev = mTail;
     if (mTail) {
-      MOZ_ASSERT(!SiblingAccess::GetNext(mTail));
-      SiblingAccess::SetNext(mTail, aElm);
+      MOZ_ASSERT(!ElementAccess::Get(mTail).mNext);
+      ElementAccess::Get(mTail).mNext = aElm;
     }
 
     mTail = aElm;
     if (!mHead) {
       mHead = aElm;
     }
   }
 
@@ -271,28 +277,28 @@ public:
    * 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;
+    mTail = result ? ElementAccess::Get(result).mPrev : nullptr;
     if (mTail) {
-      SiblingAccess::SetNext(mTail, nullptr);
+      ElementAccess::Get(mTail).mNext = nullptr;
     }
 
     if (mHead == result) {
       mHead = nullptr;
     }
 
     if (result) {
-      SiblingAccess::SetNext(result, nullptr);
-      SiblingAccess::SetPrev(result, nullptr);
+      ElementAccess::Get(result).mNext = nullptr;
+      ElementAccess::Get(result).mPrev = nullptr;
     }
 
     return result;
   }
 
   /**
    * Insert the given |aElm| *before* |aIter|.
    */
@@ -303,50 +309,50 @@ public:
 
     if (!aIter) {
       return pushBack(aElm);
     } else if (aIter == begin()) {
       return pushFront(aElm);
     }
 
     T* after = &(*aIter);
-    T* before = SiblingAccess::GetPrev(after);
+    T* before = ElementAccess::Get(after).mPrev;
     MOZ_ASSERT(before);
 
-    SiblingAccess::SetNext(before, aElm);
-    SiblingAccess::SetPrev(aElm, before);
-    SiblingAccess::SetNext(aElm, after);
-    SiblingAccess::SetPrev(after, aElm);
+    ElementAccess::Get(before).mNext = aElm;
+    ElementAccess::Get(aElm).mPrev = before;
+    ElementAccess::Get(aElm).mNext = after;
+    ElementAccess::Get(after).mPrev = 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) ||
+    MOZ_ASSERT(ElementAccess::Get(aElm).mNext || ElementAccess::Get(aElm).mPrev ||
                (aElm == mHead && aElm == mTail),
                "Attempted to remove element not in this list");
 
-    if (T* prev = SiblingAccess::GetPrev(aElm)) {
-      SiblingAccess::SetNext(prev, SiblingAccess::GetNext(aElm));
+    if (T* prev = ElementAccess::Get(aElm).mPrev) {
+      ElementAccess::Get(prev).mNext = ElementAccess::Get(aElm).mNext;
     } else {
       MOZ_ASSERT(mHead == aElm);
-      mHead = SiblingAccess::GetNext(aElm);
+      mHead = ElementAccess::Get(aElm).mNext;
     }
 
-    if (T* next = SiblingAccess::GetNext(aElm)) {
-      SiblingAccess::SetPrev(next, SiblingAccess::GetPrev(aElm));
+    if (T* next = ElementAccess::Get(aElm).mNext) {
+      ElementAccess::Get(next).mPrev = ElementAccess::Get(aElm).mPrev;
     } else {
       MOZ_ASSERT(mTail == aElm);
-      mTail = SiblingAccess::GetPrev(aElm);
+      mTail = ElementAccess::Get(aElm).mPrev;
     }
 
-    SiblingAccess::SetNext(aElm, nullptr);
-    SiblingAccess::SetPrev(aElm, nullptr);
+    ElementAccess::Get(aElm).mNext = nullptr;
+    ElementAccess::Get(aElm).mPrev = 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);
--- a/mfbt/tests/TestDoublyLinkedList.cpp
+++ b/mfbt/tests/TestDoublyLinkedList.cpp
@@ -116,42 +116,41 @@ TestDoublyLinkedList()
 
   MOZ_RELEASE_ASSERT(*list.begin() == two);
   MOZ_RELEASE_ASSERT(*++list.begin() == three);
 
   SomeClass four(4);
   MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));
 }
 
+struct InTwoLists {
+  explicit InTwoLists(unsigned int aValue) : mValue(aValue) {}
+  DoublyLinkedListElement<InTwoLists> mListOne;
+  DoublyLinkedListElement<InTwoLists> mListTwo;
+  unsigned int mValue;
+
+  struct GetListOneTrait {
+    static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists *aThis) { return aThis->mListOne; }
+  };
+};
+
+namespace mozilla {
+
+template<>
+struct GetDoublyLinkedListElement<InTwoLists> {
+  static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists* aThis) { return aThis->mListTwo; }
+};
+
+}
+
 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;
+  DoublyLinkedList<InTwoLists, InTwoLists::GetListOneTrait> listOne;
+  DoublyLinkedList<InTwoLists> listTwo;
 
   InTwoLists one(1);
   InTwoLists two(2);
 
   listOne.pushBack(&one);
   listOne.pushBack(&two);
   { unsigned int check[] { 1, 2 }; CheckListValues(listOne, check); }