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 15fd869a65c06c9bd338302a333a6ff9d0f3f168..44ddbc088cf207c3aa5e83ebffb88c953a5f7084 100644
--- a/Source/core/dom/ContainerNode.cpp
+++ b/Source/core/dom/ContainerNode.cpp
@@ -50,7 +50,9 @@ typedef pair<NodeCallback, RefPtr<Node> > CallbackInfo;
 typedef Vector<CallbackInfo> NodeCallbackQueue;
 
 static NodeCallbackQueue* s_postAttachCallbackQueue;
+static NodeCallbackQueue* s_insertionCallbackQueue;
 
+static size_t s_insertionDepth;
 static size_t s_attachDepth;
 
 ChildNodesLazySnapshot* ChildNodesLazySnapshot::latestSnapshot = 0;
@@ -683,6 +685,29 @@ 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(NodeCallback callback, Node* node)
+{
+    if (!s_insertionDepth) {
+        (*callback)(node);
+        return;
+    }
+    if (!s_insertionCallbackQueue)
+        s_insertionCallbackQueue = new NodeCallbackQueue;
+    s_insertionCallbackQueue->append(CallbackInfo(callback, node));
+}
+
 void ContainerNode::queuePostAttachCallback(NodeCallback callback, Node* node)
 {
     if (!s_postAttachCallbackQueue)
@@ -884,6 +909,15 @@ static void dispatchChildRemovalEvents(Node* child)
     }
 }
 
+void ContainerNode::dispatchInsertionCallbacks()
+{
+    for (size_t i = s_insertionCallbackQueue->size(); i; --i) {
+        const CallbackInfo& 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());