Make rule node children destruction happen in a queue from the root rule node (or root of the subtree being destroyed) rather than using recursion. (Bug 439184.) r+sr=bzbarsky
authorL. David Baron <dbaron@dbaron.org>
Sun, 13 Jul 2008 13:57:38 -0700
changeset 15904 571dbbcf60bf079667fc6f99c382850d1ab45014
parent 15903 5b6fa5bcaccd17c95bafe39667f1b0e90817e9d4
child 15905 6a513bc88338c52e3ac875787fe9e05baf293ff8
push id592
push userdbaron@mozilla.com
push dateSun, 13 Jul 2008 20:58:08 +0000
treeherdermozilla-central@6a513bc88338 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
bugs439184
milestone1.9.1a1pre
Make rule node children destruction happen in a queue from the root rule node (or root of the subtree being destroyed) rather than using recursion. (Bug 439184.) r+sr=bzbarsky
layout/style/nsRuleNode.cpp
layout/style/nsRuleNode.h
--- a/layout/style/nsRuleNode.cpp
+++ b/layout/style/nsRuleNode.cpp
@@ -395,21 +395,71 @@ static PRBool SetColor(const nsCSSValue&
 // (which comes from the presShell) to perform the allocation.
 void* 
 nsRuleNode::operator new(size_t sz, nsPresContext* aPresContext) CPP_THROW_NEW
 {
   // Check the recycle list first.
   return aPresContext->AllocateFromShell(sz);
 }
 
+/* static */ PR_CALLBACK PLDHashOperator
+nsRuleNode::EnqueueRuleNodeChildren(PLDHashTable *table, PLDHashEntryHdr *hdr,
+                                    PRUint32 number, void *arg)
+{
+  ChildrenHashEntry *entry = static_cast<ChildrenHashEntry*>(hdr);
+  nsRuleNode ***destroyQueueTail = static_cast<nsRuleNode***>(arg);
+  **destroyQueueTail = entry->mRuleNode;
+  *destroyQueueTail = &entry->mRuleNode->mNextSibling;
+  return PL_DHASH_NEXT;
+}
+
 // Overridden to prevent the global delete from being called, since the memory
 // came out of an nsIArena instead of the global delete operator's heap.
 void 
-nsRuleNode::Destroy()
+nsRuleNode::DestroyInternal(nsRuleNode ***aDestroyQueueTail)
 {
+  nsRuleNode *destroyQueue, **destroyQueueTail;
+  if (aDestroyQueueTail) {
+    destroyQueueTail = *aDestroyQueueTail;
+  } else {
+    destroyQueue = nsnull;
+    destroyQueueTail = &destroyQueue;
+  }
+
+  if (ChildrenAreHashed()) {
+    PLDHashTable *children = ChildrenHash();
+    PL_DHashTableEnumerate(children, EnqueueRuleNodeChildren,
+                           &destroyQueueTail);
+    *destroyQueueTail = nsnull; // ensure null-termination
+    PL_DHashTableDestroy(children);
+  } else if (HaveChildren()) {
+    *destroyQueueTail = ChildrenList();
+    do {
+      destroyQueueTail = &(*destroyQueueTail)->mNextSibling;
+    } while (*destroyQueueTail);
+  }
+  mChildrenTaggedPtr = nsnull;
+
+  if (aDestroyQueueTail) {
+    // Our caller destroys the queue.
+    *aDestroyQueueTail = destroyQueueTail;
+  } else {
+    // We have to do destroy the queue.  When we destroy each node, it
+    // will add its children to the queue.
+    while (destroyQueue) {
+      nsRuleNode *cur = destroyQueue;
+      destroyQueue = destroyQueue->mNextSibling;
+      if (!destroyQueue) {
+        NS_ASSERTION(destroyQueueTail == &cur->mNextSibling, "mangled list");
+        destroyQueueTail = &destroyQueue;
+      }
+      cur->DestroyInternal(&destroyQueueTail);
+    }
+  }
+
   // Destroy ourselves.
   this->~nsRuleNode();
   
   // Don't let the memory be freed, since it will be recycled
   // instead. Don't call the global operator delete.
   mPresContext->FreeToShell(sizeof(nsRuleNode), this);
 }
 
@@ -434,42 +484,21 @@ nsRuleNode::nsRuleNode(nsPresContext* aC
 {
   MOZ_COUNT_CTOR(nsRuleNode);
   NS_IF_ADDREF(mRule);
 
   NS_ASSERTION(IsRoot() || GetLevel() == aLevel, "not enough bits");
   NS_ASSERTION(IsRoot() || IsImportantRule() == aIsImportant, "yikes");
 }
 
-PR_STATIC_CALLBACK(PLDHashOperator)
-DeleteRuleNodeChildren(PLDHashTable *table, PLDHashEntryHdr *hdr,
-                       PRUint32 number, void *arg)
-{
-  ChildrenHashEntry *entry = static_cast<ChildrenHashEntry*>(hdr);
-  entry->mRuleNode->Destroy();
-  return PL_DHASH_NEXT;
-}
-
 nsRuleNode::~nsRuleNode()
 {
   MOZ_COUNT_DTOR(nsRuleNode);
   if (mStyleData.mResetData || mStyleData.mInheritedData)
     mStyleData.Destroy(0, mPresContext);
-  if (ChildrenAreHashed()) {
-    PLDHashTable *children = ChildrenHash();
-    PL_DHashTableEnumerate(children, DeleteRuleNodeChildren, nsnull);
-    PL_DHashTableDestroy(children);
-  } else if (HaveChildren()) {
-    nsRuleNode *node = ChildrenList();
-    do {
-      nsRuleNode *next = node->mNextSibling;
-      node->Destroy();
-      node = next;
-    } while (node);
-  }
   NS_IF_RELEASE(mRule);
 }
 
 nsRuleNode*
 nsRuleNode::Transition(nsIStyleRule* aRule, PRUint8 aLevel,
                        PRPackedBool aIsImportantRule)
 {
   nsRuleNode* next = nsnull;
--- a/layout/style/nsRuleNode.h
+++ b/layout/style/nsRuleNode.h
@@ -366,16 +366,20 @@ private:
 
   static PR_CALLBACK PRBool
   ChildrenHashMatchEntry(PLDHashTable *aTable,
                          const PLDHashEntryHdr *aHdr,
                          const void *aKey);
 
   static PLDHashTableOps ChildrenHashOps;
 
+  static PR_CALLBACK PLDHashOperator
+  EnqueueRuleNodeChildren(PLDHashTable *table, PLDHashEntryHdr *hdr,
+                          PRUint32 number, void *arg);
+
   Key GetKey() const {
     return Key(mRule, GetLevel(), IsImportantRule());
   }
 
   // The children of this node are stored in either a hashtable or list
   // that maps from rules to our nsRuleNode children.  When matching
   // rules, we use this mapping to transition from node to node
   // (constructing new nodes as needed to flesh out the tree).
@@ -442,20 +446,21 @@ private:
                       // never used for reset structs since their
                       // Compute*Data functions don't initialize from
                       // inherited data.
 
 public:
   // Overloaded new operator. Initializes the memory to 0 and relies on an arena
   // (which comes from the presShell) to perform the allocation.
   NS_HIDDEN_(void*) operator new(size_t sz, nsPresContext* aContext) CPP_THROW_NEW;
-  NS_HIDDEN_(void) Destroy();
+  NS_HIDDEN_(void) Destroy() { DestroyInternal(nsnull); }
   static NS_HIDDEN_(nsILanguageAtomService*) gLangService;
 
 protected:
+  NS_HIDDEN_(void) DestroyInternal(nsRuleNode ***aDestroyQueueTail);
   NS_HIDDEN_(void) PropagateDependentBit(PRUint32 aBit,
                                          nsRuleNode* aHighestNode);
   NS_HIDDEN_(void) PropagateNoneBit(PRUint32 aBit, nsRuleNode* aHighestNode);
   
   NS_HIDDEN_(const void*) SetDefaultOnRoot(const nsStyleStructID aSID,
                                                  nsStyleContext* aContext);
 
   NS_HIDDEN_(const void*)