Bug 1396723 - Simplify the trait users of DoublyLinkedList need to define. r=froydnj
☠☠ backed out by bc13c43f6771 ☠ ☠
authorMike Hommey <mh+mozilla@glandium.org>
Sat, 02 Sep 2017 08:09:58 +0900
changeset 428730 6ca94a450b810dce5cbb82b2fa13f3a34630a27b
parent 428729 74131a35a149450b24ca17d4bde05abee558a99f
child 428731 1c0f9d069aded626bdd92b80996470ea778c8d9d
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);
   }
 
   static bool ElementNotInList(T* aElm) {
-    return !SiblingAccess::GetNext(aElm) && !SiblingAccess::GetPrev(aElm);
+    return !ElementAccess::Get(aElm).mNext && !ElementAccess::Get(aElm).mPrev;
   }
 
 public:
   DoublyLinkedList() : mHead(nullptr), mTail(nullptr) {}
 
   class Iterator final {
     T* mCurrent;
 
@@ -136,28 +142,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;
     }
@@ -195,20 +201,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;
     }
   }
 
@@ -216,47 +222,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;
     }
   }
 
@@ -264,28 +270,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|.
    */
@@ -296,50 +302,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,37 @@ 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; }
+  };
+};
+
+template<>
+struct mozilla::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); }