Bug 1313362 - Convert nsGenConList to use mozilla::LinkedList. r=xidorn
authorTing-Yu Lin <tlin@mozilla.com>
Thu, 27 Oct 2016 18:07:52 +0800
changeset 347097 c73b60315c75974bd457b3dd89173fc0cb79f144
parent 347096 9ea9837a49424e22433ca5504d0e8a4994448cb7
child 347098 6f21095b038a644a56c6e172a7fd018e02f177ab
push id10298
push userraliiev@mozilla.com
push dateMon, 14 Nov 2016 12:33:03 +0000
treeherdermozilla-aurora@7e29173b1641 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersxidorn
bugs1313362
milestone52.0a1
Bug 1313362 - Convert nsGenConList to use mozilla::LinkedList. r=xidorn The difference between the PRCList and LinkedList is that the end of a LinkedList is represented by nullptr, so we don't need to worry about getting the first element when we iterate pass the last element. The majority of the changes is due to this difference. Also, simplify do-while loops by using for-loops in nsCounterManager and nsQuoteList. MozReview-Commit-ID: CZQxqNm2Ksm
layout/base/nsCounterManager.cpp
layout/base/nsCounterManager.h
layout/base/nsGenConList.cpp
layout/base/nsGenConList.h
layout/base/nsQuoteList.cpp
layout/base/nsQuoteList.h
--- a/layout/base/nsCounterManager.cpp
+++ b/layout/base/nsCounterManager.cpp
@@ -178,38 +178,34 @@ nsCounterList::SetScope(nsCounterNode *a
 
     aNode->mScopeStart = nullptr;
     aNode->mScopePrev  = nullptr;
 }
 
 void
 nsCounterList::RecalcAll()
 {
-    mDirty = false;
+  mDirty = false;
 
-    nsCounterNode *node = First();
-    if (!node)
-        return;
-
-    do {
-        SetScope(node);
-        node->Calc(this);
+  for (nsCounterNode* node = First(); node; node = Next(node)) {
+    SetScope(node);
+    node->Calc(this);
 
-        if (node->mType == nsCounterNode::USE) {
-            nsCounterUseNode *useNode = node->UseNode();
-            // Null-check mText, since if the frame constructor isn't
-            // batching, we could end up here while the node is being
-            // constructed.
-            if (useNode->mText) {
-                nsAutoString text;
-                useNode->GetText(text);
-                useNode->mText->SetData(text);
-            }
-        }
-    } while ((node = Next(node)) != First());
+    if (node->mType == nsCounterNode::USE) {
+      nsCounterUseNode *useNode = node->UseNode();
+      // Null-check mText, since if the frame constructor isn't
+      // batching, we could end up here while the node is being
+      // constructed.
+      if (useNode->mText) {
+        nsAutoString text;
+        useNode->GetText(text);
+        useNode->mText->SetData(text);
+      }
+    }
+  }
 }
 
 nsCounterManager::nsCounterManager()
     : mNames()
 {
 }
 
 bool
@@ -284,31 +280,28 @@ nsCounterManager::RecalcAll()
     }
 }
 
 void
 nsCounterManager::SetAllCounterStylesDirty()
 {
   for (auto iter = mNames.Iter(); !iter.Done(); iter.Next()) {
     nsCounterList* list = iter.UserData();
-    nsCounterNode* first = list->First();
-    if (first) {
-      bool changed = false;
-      nsCounterNode* node = first;
-      do {
-        if (node->mType == nsCounterNode::USE) {
-            node->UseNode()->SetCounterStyleDirty();
-            changed = true;
-        }
-      } while ((node = list->Next(node)) != first);
+    bool changed = false;
 
-      if (changed) {
-        list->SetDirty();
+    for (nsCounterNode* node = list->First(); node; node = list->Next(node)) {
+      if (node->mType == nsCounterNode::USE) {
+        node->UseNode()->SetCounterStyleDirty();
+        changed = true;
       }
     }
+
+    if (changed) {
+      list->SetDirty();
+    }
   }
 }
 
 bool
 nsCounterManager::DestroyNodesFor(nsIFrame *aFrame)
 {
   bool destroyedAny = false;
   for (auto iter = mNames.Iter(); !iter.Done(); iter.Next()) {
@@ -326,31 +319,28 @@ void
 nsCounterManager::Dump()
 {
   printf("\n\nCounter Manager Lists:\n");
   for (auto iter = mNames.Iter(); !iter.Done(); iter.Next()) {
     printf("Counter named \"%s\":\n",
            NS_ConvertUTF16toUTF8(iter.Key()).get());
 
     nsCounterList* list = iter.UserData();
-    nsCounterNode* node = list->First();
-    if (node) {
-      int32_t i = 0;
-      do {
-        const char* types[] = { "RESET", "INCREMENT", "USE" };
-        printf("  Node #%d @%p frame=%p index=%d type=%s valAfter=%d\n"
-               "       scope-start=%p scope-prev=%p",
-               i++, (void*)node, (void*)node->mPseudoFrame,
-               node->mContentIndex, types[node->mType],
-               node->mValueAfter, (void*)node->mScopeStart,
-               (void*)node->mScopePrev);
-        if (node->mType == nsCounterNode::USE) {
-          nsAutoString text;
-          node->UseNode()->GetText(text);
-          printf(" text=%s", NS_ConvertUTF16toUTF8(text).get());
-        }
-        printf("\n");
-      } while ((node = list->Next(node)) != list->First());
+    int32_t i = 0;
+    for (nsCounterNode* node = list->First(); node; node = list->Next(node)) {
+      const char* types[] = { "RESET", "INCREMENT", "USE" };
+      printf("  Node #%d @%p frame=%p index=%d type=%s valAfter=%d\n"
+             "       scope-start=%p scope-prev=%p",
+             i++, (void*)node, (void*)node->mPseudoFrame,
+             node->mContentIndex, types[node->mType],
+             node->mValueAfter, (void*)node->mScopeStart,
+             (void*)node->mScopePrev);
+      if (node->mType == nsCounterNode::USE) {
+        nsAutoString text;
+        node->UseNode()->GetText(text);
+        printf(" text=%s", NS_ConvertUTF16toUTF8(text).get());
+      }
+      printf("\n");
     }
   }
   printf("\n\n");
 }
 #endif
--- a/layout/base/nsCounterManager.h
+++ b/layout/base/nsCounterManager.h
@@ -181,17 +181,17 @@ public:
         // Don't SetScope if we're dirty -- we'll reset all the scopes anyway,
         // and we can't usefully compute scopes right now.
         if (MOZ_LIKELY(!IsDirty())) {
             SetScope(aNode);
         }
     }
 
     nsCounterNode* First() {
-        return static_cast<nsCounterNode*>(mFirstNode);
+        return static_cast<nsCounterNode*>(mList.getFirst());
     }
 
     static nsCounterNode* Next(nsCounterNode* aNode) {
         return static_cast<nsCounterNode*>(nsGenConList::Next(aNode));
     }
     static nsCounterNode* Prev(nsCounterNode* aNode) {
         return static_cast<nsCounterNode*>(nsGenConList::Prev(aNode));
     }
--- a/layout/base/nsGenConList.cpp
+++ b/layout/base/nsGenConList.cpp
@@ -8,61 +8,44 @@
 
 #include "nsGenConList.h"
 #include "nsLayoutUtils.h"
 #include "nsIContent.h"
 
 void
 nsGenConList::Clear()
 {
-  //Delete entire list
-  if (!mFirstNode)
-    return;
-
+  // Delete entire list.
   mNodes.Clear();
-  for (nsGenConNode *node = Next(mFirstNode); node != mFirstNode;
-       node = Next(mFirstNode))
-  {
-    Destroy(node);
+  while (nsGenConNode* node = mList.popFirst()) {
+    delete node;
   }
-  delete mFirstNode;
-
-  mFirstNode = nullptr;
   mSize = 0;
 }
 
 bool
 nsGenConList::DestroyNodesFor(nsIFrame* aFrame)
 {
   // This algorithm relies on the invariant that nodes of a frame are
   // put contiguously in the linked list. This is guaranteed because
   // each frame is mapped to only one (nsIContent, pseudoType) pair,
   // and the nodes in the linked list are put in the tree order based
   // on that pair and offset inside frame.
   nsGenConNode* node = mNodes.GetAndRemove(aFrame).valueOr(nullptr);
   if (!node) {
     return false;
   }
   MOZ_ASSERT(node->mPseudoFrame == aFrame);
-  // Clear following nodes first as they must not be mFirstNode.
-  // If mFirstNode refers to a node of this frame, it should be the
-  // one retrieved from mNodes.
-  for (nsGenConNode* curNode = Next(node);
-       curNode->mPseudoFrame == aFrame && curNode != node;
-       /* curNode updated in loop body */) {
-    MOZ_ASSERT(curNode != mFirstNode);
-    nsGenConNode* nextNode = Next(curNode);
-    Destroy(curNode);
-    curNode = nextNode;
+
+  while (node && node->mPseudoFrame == aFrame) {
+    nsGenConNode* nextNode = Next(node);
+    Destroy(node);
+    node = nextNode;
   }
-  if (node == mFirstNode) {
-    nsGenConNode* nextNode = Next(mFirstNode);
-    mFirstNode = nextNode == mFirstNode ? nullptr : nextNode;
-  }
-  Destroy(node);
+
   return true;
 }
 
 /**
  * Compute the type of the pseudo and the content for the pseudo that
  * we'll use for comparison purposes.
  * @param aContent the content to use is stored here; it's the element
  * that generated the ::before or ::after content, or (if not for generated
@@ -117,82 +100,71 @@ nsGenConList::NodeAfter(const nsGenConNo
                                                      pseudoType1, -pseudoType2);
   MOZ_ASSERT(cmp != 0, "same content, different frames");
   return cmp > 0;
 }
 
 void
 nsGenConList::Insert(nsGenConNode* aNode)
 {
-  if (mFirstNode) {
-    // Check for append.
-    if (NodeAfter(aNode, Prev(mFirstNode))) {
-      PR_INSERT_BEFORE(aNode, mFirstNode);
-    }
-    else {
-      // Binary search.
+  // Check for append.
+  if (mList.isEmpty() || NodeAfter(aNode, mList.getLast())) {
+    mList.insertBack(aNode);
+  } else {
+    // Binary search.
 
-      // the range of indices at which |aNode| could end up.
-      // (We already know it can't be at index mSize.)
-      uint32_t first = 0, last = mSize - 1;
+    // the range of indices at which |aNode| could end up.
+    // (We already know it can't be at index mSize.)
+    uint32_t first = 0, last = mSize - 1;
 
-      // A cursor to avoid walking more than the length of the list.
-      nsGenConNode *curNode = Prev(mFirstNode);
-      uint32_t curIndex = mSize - 1;
+    // A cursor to avoid walking more than the length of the list.
+    nsGenConNode* curNode = mList.getLast();
+    uint32_t curIndex = mSize - 1;
 
-      while (first != last) {
-        uint32_t test = (first + last) / 2;
-        if (last == curIndex) {
-          for ( ; curIndex != test; --curIndex)
-            curNode = Prev(curNode);
-        } else {
-          for ( ; curIndex != test; ++curIndex)
-            curNode = Next(curNode);
-        }
+    while (first != last) {
+      uint32_t test = (first + last) / 2;
+      if (last == curIndex) {
+        for ( ; curIndex != test; --curIndex)
+          curNode = Prev(curNode);
+      } else {
+        for ( ; curIndex != test; ++curIndex)
+          curNode = Next(curNode);
+      }
 
-        if (NodeAfter(aNode, curNode)) {
-          first = test + 1;
-          // if we exit the loop, we need curNode to be right
-          ++curIndex;
-          curNode = Next(curNode);
-        } else {
-          last = test;
-        }
-      }
-      PR_INSERT_BEFORE(aNode, curNode);
-      if (curNode == mFirstNode) {
-        mFirstNode = aNode;
+      if (NodeAfter(aNode, curNode)) {
+        first = test + 1;
+        // if we exit the loop, we need curNode to be right
+        ++curIndex;
+        curNode = Next(curNode);
+      } else {
+        last = test;
       }
     }
-  }
-  else {
-    // initialize list with first node
-    PR_INIT_CLIST(aNode);
-    mFirstNode = aNode;
+    curNode->setPrevious(aNode);
   }
   ++mSize;
 
   // Set the mapping only if it is the first node of the frame.
   // The DEBUG blocks below are for ensuring the invariant required by
   // nsGenConList::DestroyNodesFor. See comment there.
-  if (aNode == mFirstNode ||
+  if (IsFirst(aNode) ||
       Prev(aNode)->mPseudoFrame != aNode->mPseudoFrame) {
 #ifdef DEBUG
     if (nsGenConNode* oldFrameFirstNode = mNodes.Get(aNode->mPseudoFrame)) {
       MOZ_ASSERT(Next(aNode) == oldFrameFirstNode,
                  "oldFrameFirstNode should now be immediately after "
                  "the newly-inserted one.");
     } else {
       // If the node is not the only node in the list.
-      nsGenConNode* nextNode = Next(aNode);
-      if (nextNode != aNode) {
-        MOZ_ASSERT(nextNode->mPseudoFrame != aNode->mPseudoFrame,
+      if (!IsFirst(aNode) || !IsLast(aNode)) {
+        nsGenConNode* nextNode = Next(aNode);
+        MOZ_ASSERT(!nextNode || nextNode->mPseudoFrame != aNode->mPseudoFrame,
                    "There shouldn't exist any node for this frame.");
         // If the node is neither the first nor the last node
-        if (aNode != mFirstNode && nextNode != mFirstNode) {
+        if (!IsFirst(aNode) && !IsLast(aNode)) {
           MOZ_ASSERT(Prev(aNode)->mPseudoFrame != nextNode->mPseudoFrame,
                      "New node should not break contiguity of nodes of "
                      "the same frame.");
         }
       }
     }
 #endif
     mNodes.Put(aNode->mPseudoFrame, aNode);
@@ -200,20 +172,21 @@ nsGenConList::Insert(nsGenConNode* aNode
 #ifdef DEBUG
     nsGenConNode* frameFirstNode = mNodes.Get(aNode->mPseudoFrame);
     MOZ_ASSERT(frameFirstNode, "There should exist node map for the frame.");
     for (nsGenConNode* curNode = Prev(aNode);
          curNode != frameFirstNode; curNode = Prev(curNode)) {
       MOZ_ASSERT(curNode->mPseudoFrame == aNode->mPseudoFrame,
                  "Every node between frameFirstNode and the new node inserted "
                  "should refer to the same frame.");
-      MOZ_ASSERT(curNode != mFirstNode, "The newly-inserted node should be in "
-                 "a contiguous run after frameFirstNode, thus frameFirstNode "
-                 "should be reached before mFirstNode.");
+      MOZ_ASSERT(!IsFirst(curNode),
+                 "The newly-inserted node should be in a contiguous run after "
+                 "frameFirstNode, thus frameFirstNode should be reached before "
+                 "the first node of mList.");
     }
 #endif
   }
 
-  NS_ASSERTION(aNode == mFirstNode || NodeAfter(aNode, Prev(aNode)),
+  NS_ASSERTION(IsFirst(aNode) || NodeAfter(aNode, Prev(aNode)),
                "sorting error");
   NS_ASSERTION(IsLast(aNode) || NodeAfter(Next(aNode), aNode),
                "sorting error");
 }
--- a/layout/base/nsGenConList.h
+++ b/layout/base/nsGenConList.h
@@ -3,25 +3,25 @@
  * 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/. */
 
 /* base class for nsCounterList and nsQuoteList */
 
 #ifndef nsGenConList_h___
 #define nsGenConList_h___
 
+#include "mozilla/LinkedList.h"
 #include "nsIFrame.h"
 #include "nsStyleStruct.h"
-#include "prclist.h"
 #include "nsCSSPseudoElements.h"
 #include "nsTextNode.h"
 
 class nsGenConList;
 
-struct nsGenConNode : public PRCList {
+struct nsGenConNode : public mozilla::LinkedListElement<nsGenConNode> {
   // The wrapper frame for all of the pseudo-element's content.  This
   // frame generally has useful style data and has the
   // NS_FRAME_GENERATED_CONTENT bit set (so we use it to track removal),
   // but does not necessarily for |nsCounterChangeNode|s.
   nsIFrame* mPseudoFrame;
 
   // Index within the list of things specified by the 'content' property,
   // which is needed to do 'content: open-quote open-quote' correctly,
@@ -46,17 +46,17 @@ struct nsGenConNode : public PRCList {
    * mPseudoFrame, insert the node into aList, and set aTextFrame up
    * with the correct text.
    * @param aList the list the node belongs to
    * @param aPseudoFrame the :before or :after frame
    * @param aTextFrame the textframe where the node contents will render
    * @return true iff this marked the list dirty
    */
   virtual bool InitTextFrame(nsGenConList* aList, nsIFrame* aPseudoFrame,
-                               nsIFrame* aTextFrame)
+                             nsIFrame* aTextFrame)
   {
     mPseudoFrame = aPseudoFrame;
     CheckFrameAssertions();
     return false;
   }
 
   virtual ~nsGenConNode() {} // XXX Avoid, perhaps?
 
@@ -77,41 +77,55 @@ protected:
     NS_ASSERTION(mContentIndex < 0 ||
                  mPseudoFrame->GetStateBits() & NS_FRAME_GENERATED_CONTENT,
                  "not generated content and not counter change");
   }
 };
 
 class nsGenConList {
 protected:
-  nsGenConNode* mFirstNode;
+  mozilla::LinkedList<nsGenConNode> mList;
   uint32_t mSize;
+
 public:
-  nsGenConList() : mFirstNode(nullptr), mSize(0) {}
+  nsGenConList() : mSize(0) {}
   ~nsGenConList() { Clear(); }
   void Clear();
   static nsGenConNode* Next(nsGenConNode* aNode) {
-    return static_cast<nsGenConNode*>(PR_NEXT_LINK(aNode));
+    MOZ_ASSERT(aNode, "aNode cannot be nullptr!");
+    return aNode->getNext();
   }
   static nsGenConNode* Prev(nsGenConNode* aNode) {
-    return static_cast<nsGenConNode*>(PR_PREV_LINK(aNode));
+    MOZ_ASSERT(aNode, "aNode cannot be nullptr!");
+    return aNode->getPrevious();
   }
   void Insert(nsGenConNode* aNode);
-  // returns whether any nodes have been destroyed
-  bool DestroyNodesFor(nsIFrame* aFrame); //destroy all nodes with aFrame as parent
+
+  // Destroy all nodes with aFrame as parent. Returns true if some nodes
+  // have been destroyed; otherwise false.
+  bool DestroyNodesFor(nsIFrame* aFrame);
 
   // Return true if |aNode1| is after |aNode2|.
   static bool NodeAfter(const nsGenConNode* aNode1,
-                          const nsGenConNode* aNode2);
+                        const nsGenConNode* aNode2);
 
-  bool IsLast(nsGenConNode* aNode) { return (Next(aNode) == mFirstNode); }
+  bool IsFirst(nsGenConNode* aNode) {
+    MOZ_ASSERT(aNode, "aNode cannot be nullptr!");
+    return aNode == mList.getFirst();
+  }
+
+  bool IsLast(nsGenConNode* aNode) {
+    MOZ_ASSERT(aNode, "aNode cannot be nullptr!");
+    return aNode == mList.getLast();
+  }
+
 private:
   void Destroy(nsGenConNode* aNode)
   {
-    PR_REMOVE_LINK(aNode);
+    MOZ_ASSERT(aNode, "aNode cannot be nullptr!");
     delete aNode;
     mSize--;
   }
 
   // Map from frame to the first nsGenConNode of it in the list.
   nsDataHashtable<nsPtrHashKey<nsIFrame>, nsGenConNode*> mNodes;
 };
 
--- a/layout/base/nsQuoteList.cpp
+++ b/layout/base/nsQuoteList.cpp
@@ -69,42 +69,31 @@ nsQuoteList::Calc(nsQuoteNode* aNode)
   } else {
     aNode->mDepthBefore = Prev(aNode)->DepthAfter();
   }
 }
 
 void
 nsQuoteList::RecalcAll()
 {
-  nsQuoteNode *node = FirstNode();
-  if (!node)
-    return;
-
-  do {
+  for (nsQuoteNode* node = FirstNode(); node; node = Next(node)) {
     int32_t oldDepth = node->mDepthBefore;
     Calc(node);
 
     if (node->mDepthBefore != oldDepth && node->mText && node->IsRealQuote())
       node->mText->SetData(*node->Text());
-
-    // Next node
-    node = Next(node);
-  } while (node != FirstNode());
+  }
 }
 
 #ifdef DEBUG
 void
 nsQuoteList::PrintChain()
 {
   printf("Chain: \n");
-  if (!FirstNode()) {
-    return;
-  }
-  nsQuoteNode* node = FirstNode();
-  do {
+  for (nsQuoteNode* node = FirstNode(); node; node = Next(node)) {
     printf("  %p %d - ", static_cast<void*>(node), node->mDepthBefore);
     switch(node->mType) {
         case (eStyleContentType_OpenQuote):
           printf("open");
           break;
         case (eStyleContentType_NoOpenQuote):
           printf("noOpen");
           break;
@@ -119,12 +108,11 @@ nsQuoteList::PrintChain()
     }
     printf(" %d - %d,", node->Depth(), node->DepthAfter());
     if (node->mText) {
       nsAutoString data;
       node->mText->GetData(data);
       printf(" \"%s\",", NS_ConvertUTF16toUTF8(data).get());
     }
     printf("\n");
-    node = Next(node);
-  } while (node != FirstNode());
+  }
 }
 #endif
--- a/layout/base/nsQuoteList.h
+++ b/layout/base/nsQuoteList.h
@@ -26,17 +26,17 @@ struct nsQuoteNode : public nsGenConNode
     NS_ASSERTION(aType == eStyleContentType_OpenQuote ||
                  aType == eStyleContentType_CloseQuote ||
                  aType == eStyleContentType_NoOpenQuote ||
                  aType == eStyleContentType_NoCloseQuote,
                  "incorrect type");
     NS_ASSERTION(aContentIndex <= INT32_MAX, "out of range");
   }
 
-  virtual bool InitTextFrame(nsGenConList* aList, 
+  virtual bool InitTextFrame(nsGenConList* aList,
           nsIFrame* aPseudoFrame, nsIFrame* aTextFrame) override;
 
   // is this 'open-quote' or 'no-open-quote'?
   bool IsOpenQuote() {
     return mType == eStyleContentType_OpenQuote ||
            mType == eStyleContentType_NoOpenQuote;
   }
 
@@ -65,28 +65,28 @@ struct nsQuoteNode : public nsGenConNode
   }
 
   // The text that should be displayed for this quote.
   const nsString* Text();
 };
 
 class nsQuoteList : public nsGenConList {
 private:
-  nsQuoteNode* FirstNode() { return static_cast<nsQuoteNode*>(mFirstNode); }
+  nsQuoteNode* FirstNode() { return static_cast<nsQuoteNode*>(mList.getFirst()); }
 public:
   // assign the correct |mDepthBefore| value to a node that has been inserted
   // Should be called immediately after calling |Insert|.
   void Calc(nsQuoteNode* aNode);
 
   nsQuoteNode* Next(nsQuoteNode* aNode) {
     return static_cast<nsQuoteNode*>(nsGenConList::Next(aNode));
   }
   nsQuoteNode* Prev(nsQuoteNode* aNode) {
     return static_cast<nsQuoteNode*>(nsGenConList::Prev(aNode));
   }
-  
+
   void RecalcAll();
 #ifdef DEBUG
   void PrintChain();
 #endif
 };
 
 #endif /* nsQuoteList_h___ */