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

Source/core/dom/ContainerNode.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
@@ skipping 29 matching lines @@
 #include "wtf/Vector.h"
 
 using namespace std;
 
 namespace WebCore {
 
 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;
 
 #ifndef NDEBUG
 unsigned NoEventDispatchAssertion::s_count = 0;
 #endif
 
 static void collectChildrenAndRemoveFromOldParent(Node* node, NodeVector& nodes, ExceptionCode& ec)
 {
@@ skipping 617 matching lines @@
 {
     if (s_attachDepth == 1) {
         RefPtr<ContainerNode> protect(this);
 
         if (s_postAttachCallbackQueue)
             dispatchPostAttachCallbacks();
     }
     --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()
 {
     return s_attachDepth;
 }
 
 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();
 }
 
 void ContainerNode::attach(const AttachContext& context)
 {
     attachChildren(context);
     Node::attach(context);
 }
@@ skipping 307 matching lines @@
     if (c->parentNode() && document->hasListenerType(Document::DOMNODEREMOVED_LISTENER))
         c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeRemovedEvent, true, c->parentNode()));
 
     // dispatch the DOMNodeRemovedFromDocument event to all descendants
     if (c->inDocument() && document->hasListenerType(Document::DOMNODEREMOVEDFROMDOCUMENT_LISTENER)) {
         for (; c; c = NodeTraversal::next(c.get(), child))
             c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeRemovedFromDocumentEvent, false));
     }
 }
 
+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());
     ASSERT(child->refCount());
 
     ChildListMutationScope(parent).childAdded(child);
 
     parent->childrenChanged(false, child->previousSibling(), child->nextSibling(), 1);
 
     ChildNodeInsertionNotifier(parent).notify(child);
@@ skipping 20 matching lines @@
         return true;
 
     if (node->isElementNode() && toElement(node)->shadow())
         return true;
 
     return false;
 }
 #endif
 
 } // namespace WebCore