Avoid N^2 walk placing renderers when building the render tree

Source/core/dom/ContainerNode.cpp

Index: Source/core/dom/ContainerNode.cpp
diff --git a/Source/core/dom/ContainerNode.cpp b/Source/core/dom/ContainerNode.cpp
index 1f9b3515bbc52b750d69bf60e647c38b96bb4b40..923031a95a54357ee4a11731787e7b15b1043547 100644
--- a/Source/core/dom/ContainerNode.cpp
+++ b/Source/core/dom/ContainerNode.cpp
@@ -47,11 +47,15 @@ static void dispatchChildInsertionEvents(Node*);
 static void dispatchChildRemovalEvents(Node*);
 static void updateTreeAfterInsertion(ContainerNode*, Node*, AttachBehavior);
 
-typedef pair<NodeCallback, RefPtr<Node> > CallbackInfo;
-typedef Vector<CallbackInfo> NodeCallbackQueue;
+typedef pair<NodeCallback, RefPtr<Node> > NodeCallbackInfo;
+typedef Vector<NodeCallbackInfo> NodeCallbackQueue;
+typedef pair<ElementCallback, RefPtr<Element> > ElementCallbackInfo;
+typedef Vector<ElementCallbackInfo> ElementCallbackQueue;
 
 static NodeCallbackQueue* s_postAttachCallbackQueue;
+static ElementCallbackQueue* s_insertionCallbackQueue;
 
+static size_t s_insertionDepth;
 static size_t s_attachDepth;
 
 ChildNodesLazySnapshot* ChildNodesLazySnapshot::latestSnapshot = 0;
@@ -689,11 +693,34 @@ void ContainerNode::resumePostAttachCallbacks()
     --s_attachDepth;
 }
 
+void ContainerNode::suspendInsertionCallbacks()
+{
+    ++s_insertionDepth;
+}
+
+void ContainerNode::resumeInsertionCallbacks()
+{
+    if (s_insertionDepth == 1 && s_insertionCallbackQueue)
+        dispatchInsertionCallbacks();
+    --s_insertionDepth;
+}
+
+void ContainerNode::queueInsertionCallback(ElementCallback callback, Element* element)
+{
+    if (!s_insertionDepth) {
+        (*callback)(element);
+        return;
+    }
+    if (!s_insertionCallbackQueue)
+        s_insertionCallbackQueue = new ElementCallbackQueue;
+    s_insertionCallbackQueue->append(ElementCallbackInfo(callback, element));
+}
+
 void ContainerNode::queuePostAttachCallback(NodeCallback callback, Node* node)
 {
     if (!s_postAttachCallbackQueue)
         s_postAttachCallbackQueue = new NodeCallbackQueue;
-    s_postAttachCallbackQueue->append(CallbackInfo(callback, node));
+    s_postAttachCallbackQueue->append(NodeCallbackInfo(callback, node));
 }
 
 bool ContainerNode::postAttachCallbacksAreSuspended()
@@ -706,7 +733,7 @@ void ContainerNode::dispatchPostAttachCallbacks()
     // We recalculate size() each time through the loop because a callback
     // can add more callbacks to the end of the queue.
     for (size_t i = 0; i < s_postAttachCallbackQueue->size(); ++i) {
-        const CallbackInfo& info = (*s_postAttachCallbackQueue)[i];
+        const NodeCallbackInfo& info = (*s_postAttachCallbackQueue)[i];
         info.first(info.second.get());
     }
     s_postAttachCallbackQueue->clear();
@@ -1034,6 +1061,15 @@ static void dispatchChildRemovalEvents(Node* child)
     }
 }
 
+void ContainerNode::dispatchInsertionCallbacks()
+{
+    for (size_t i = s_insertionCallbackQueue->size(); i; --i) {
+        const ElementCallbackInfo& info = (*s_insertionCallbackQueue)[i - 1];
+        info.first(info.second.get());
+    }
+    s_insertionCallbackQueue->clear();
+}
+
 static void updateTreeAfterInsertion(ContainerNode* parent, Node* child, AttachBehavior attachBehavior)
 {
     ASSERT(parent->refCount());