Bug 1310547 - Allow LinkedList to hold RefPtr elements (r=froydnj)
authorBill McCloskey <billm@mozilla.com>
Sun, 16 Oct 2016 18:40:49 -0700
changeset 320260 815e8f226bb9
parent 320259 9b5b04d1a15a
child 320261 b30dfbf5fe2a
push id20754
push usercbook@mozilla.com
push dateMon, 31 Oct 2016 15:58:35 +0000
treeherderfx-team@b1b66b1780c2 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1310547
milestone52.0a1
Bug 1310547 - Allow LinkedList to hold RefPtr elements (r=froydnj)
mfbt/LinkedList.h
mfbt/tests/TestLinkedList.cpp
--- a/mfbt/LinkedList.h
+++ b/mfbt/LinkedList.h
@@ -63,27 +63,75 @@
 
 #ifndef mozilla_LinkedList_h
 #define mozilla_LinkedList_h
 
 #include "mozilla/Assertions.h"
 #include "mozilla/Attributes.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Move.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) {}
+};
+
+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(); }
+};
+
+} /* 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,
@@ -150,42 +198,42 @@ public:
       remove();
     }
   }
 
   /*
    * Get the next element in the list, or nullptr if this is the last element
    * in the list.
    */
-  T* getNext()             { return mNext->asT(); }
-  const T* getNext() const { return mNext->asT(); }
+  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.
    */
-  T* getPrevious()             { return mPrev->asT(); }
-  const T* getPrevious() const { return mPrev->asT(); }
+  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(T* aElem)
+  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(T* aElem)
+  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.
@@ -193,16 +241,18 @@ public:
   void remove()
   {
     MOZ_ASSERT(isInList());
 
     mPrev->mNext = mNext;
     mNext->mPrev = mPrev;
     mNext = this;
     mPrev = this;
+
+    Traits::exitList(this);
   }
 
   /*
    * Identical to remove(), but also asserts in debug builds that this element
    * is in aList.
    */
   void removeFrom(const LinkedList<T>& aList)
   {
@@ -216,83 +266,92 @@ public:
   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.
    */
-  T* asT()
+  RawType asT()
   {
-    return mIsSentinel ? nullptr : static_cast<T*>(this);
+    return mIsSentinel ? nullptr : static_cast<RawType>(this);
   }
-  const T* asT() const
+  ConstRawType asT() const
   {
-    return mIsSentinel ? nullptr : static_cast<const T*>(this);
+    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(T* aElem)
+  void setNextUnsafe(RawType aElem)
   {
     LinkedListElement *listElem = static_cast<LinkedListElement*>(aElem);
     MOZ_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(T* aElem)
+  void setPreviousUnsafe(RawType aElem)
   {
     LinkedListElement<T>* listElem = static_cast<LinkedListElement<T>*>(aElem);
     MOZ_ASSERT(!listElem->isInList());
 
     listElem->mNext = this;
     listElem->mPrev = this->mPrev;
     this->mPrev->mNext = listElem;
     this->mPrev = listElem;
+
+    Traits::enterList(aElem);
   }
 
   /*
    * 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;
@@ -302,36 +361,46 @@ private:
     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:
+  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;
+
   LinkedListElement<T> sentinel;
 
 public:
   class Iterator {
-    T* mCurrent;
+    RawType mCurrent;
 
   public:
-    explicit Iterator(T* aCurrent) : mCurrent(aCurrent) {}
+    explicit Iterator(RawType aCurrent) : mCurrent(aCurrent) {}
 
-    T* operator *() const {
+    RawType operator *() const {
       return mCurrent;
     }
 
     const Iterator& operator++() {
       mCurrent = mCurrent->getNext();
       return *this;
     }
 
@@ -358,64 +427,64 @@ public:
                "failing this assertion means this LinkedList's creator is "
                "buggy: it should have removed all this list's elements before "
                "the list's destruction");
   }
 
   /*
    * Add aElem to the front of the list.
    */
-  void insertFront(T* aElem)
+  void insertFront(RawType aElem)
   {
     /* Bypass setNext()'s this->isInList() assertion. */
     sentinel.setNextUnsafe(aElem);
   }
 
   /*
    * Add aElem to the back of the list.
    */
-  void insertBack(T* aElem)
+  void insertBack(RawType aElem)
   {
     sentinel.setPreviousUnsafe(aElem);
   }
 
   /*
    * Get the first element of the list, or nullptr if the list is empty.
    */
-  T* getFirst()             { return sentinel.getNext(); }
-  const T* getFirst() const { return sentinel.getNext(); }
+  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.
    */
-  T* getLast()             { return sentinel.getPrevious(); }
-  const T* getLast() const { return sentinel.getPrevious(); }
+  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.
    */
-  T* popFirst()
+  ClientType popFirst()
   {
-    T* ret = sentinel.getNext();
+    ClientType ret = sentinel.getNext();
     if (ret) {
-      static_cast<LinkedListElement<T>*>(ret)->remove();
+      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.
    */
-  T* popLast()
+  ClientType popLast()
   {
-    T* ret = sentinel.getPrevious();
+    ClientType ret = sentinel.getPrevious();
     if (ret) {
-      static_cast<LinkedListElement<T>*>(ret)->remove();
+      static_cast<LinkedListElement<T>*>(RawType(ret))->remove();
     }
     return ret;
   }
 
   /*
    * Return true if the list is empty, or false otherwise.
    */
   bool isEmpty() const
@@ -526,20 +595,20 @@ public:
         cur = cur->mNext;
     } while (cur != &sentinel);
 #endif /* ifdef DEBUG */
   }
 
 private:
   friend class LinkedListElement<T>;
 
-  void assertContains(const T* aValue) const
+  void assertContains(const RawType aValue) const
   {
 #ifdef DEBUG
-    for (const T* elem = getFirst(); elem; elem = elem->getNext()) {
+    for (ConstRawType elem = getFirst(); elem; elem = elem->getNext()) {
       if (elem == aValue) {
         return;
       }
     }
     MOZ_CRASH("element wasn't found in this list!");
 #endif
   }
 
--- a/mfbt/tests/TestLinkedList.cpp
+++ b/mfbt/tests/TestLinkedList.cpp
@@ -172,16 +172,78 @@ TestPrivate()
   size_t count = 0;
   for (PrivateClass* p : list) {
     MOZ_RELEASE_ASSERT(p, "cannot have null elements in list");
     count++;
   }
   MOZ_RELEASE_ASSERT(count == 2);
 }
 
+struct CountedClass : public LinkedListElement<RefPtr<CountedClass>>
+{
+  int mCount;
+  void AddRef() { mCount++; }
+  void Release() { mCount--; }
+
+  CountedClass() : mCount(0) {}
+  ~CountedClass() { MOZ_RELEASE_ASSERT(mCount == 0); }
+};
+
+static void
+TestRefPtrList()
+{
+  LinkedList<RefPtr<CountedClass>> list;
+  CountedClass* elt1 = new CountedClass;
+  CountedClass* elt2 = new CountedClass;
+
+  list.insertBack(elt1);
+  list.insertBack(elt2);
+
+  MOZ_RELEASE_ASSERT(elt1->mCount == 1);
+  MOZ_RELEASE_ASSERT(elt2->mCount == 1);
+
+  for (RefPtr<CountedClass> p : list) {
+    MOZ_RELEASE_ASSERT(p->mCount == 2);
+  }
+
+  RefPtr<CountedClass> ptr = list.getFirst();
+  while (ptr) {
+    MOZ_RELEASE_ASSERT(ptr->mCount == 2);
+    RefPtr<CountedClass> next = ptr->getNext();
+    ptr->remove();
+    ptr = Move(next);
+  }
+  ptr = nullptr;
+
+  MOZ_RELEASE_ASSERT(elt1->mCount == 0);
+  MOZ_RELEASE_ASSERT(elt2->mCount == 0);
+
+  list.insertBack(elt1);
+  elt1->setNext(elt2);
+
+  MOZ_RELEASE_ASSERT(elt1->mCount == 1);
+  MOZ_RELEASE_ASSERT(elt2->mCount == 1);
+
+  RefPtr<CountedClass> first = list.popFirst();
+
+  MOZ_RELEASE_ASSERT(elt1->mCount == 1);
+  MOZ_RELEASE_ASSERT(elt2->mCount == 1);
+
+  RefPtr<CountedClass> second = list.popFirst();
+
+  MOZ_RELEASE_ASSERT(elt1->mCount == 1);
+  MOZ_RELEASE_ASSERT(elt2->mCount == 1);
+
+  first = second = nullptr;
+
+  delete elt1;
+  delete elt2;
+}
+
 int
 main()
 {
   TestList();
   TestPrivate();
   TestMove();
+  TestRefPtrList();
   return 0;
 }