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

Source/core/dom/ContainerNode.h

 /*
  * 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, 2009, 2010, 2011 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 266 matching lines @@
     ASSERT(!nodes.size());
     for (Node* child = node->firstChild(); child; child = child->nextSibling())
         nodes.append(child);
 }
 
 class ChildNodesLazySnapshot {
     WTF_MAKE_NONCOPYABLE(ChildNodesLazySnapshot);
     WTF_MAKE_FAST_ALLOCATED;
 public:
     explicit ChildNodesLazySnapshot(Node* parentNode)
-        : m_currentNode(parentNode->firstChild())
+        : m_currentNode(parentNode->lastChild())
         , m_currentIndex(0)
     {
         m_nextSnapshot = latestSnapshot;
         latestSnapshot = this;
     }
 
     ~ChildNodesLazySnapshot()
     {
         latestSnapshot = m_nextSnapshot;
     }
 
     // Returns 0 if there is no next Node.

[esprehn, 2013/06/05 00:12:26]

is no previous node?

-    PassRefPtr<Node> nextNode()
+    PassRefPtr<Node> previousNode()
     {
         if (LIKELY(!hasSnapshot())) {
             RefPtr<Node> node = m_currentNode;
             if (node)
-                m_currentNode = node->nextSibling();
+                m_currentNode = node->previousSibling();
             return node.release();
         }
         Vector<RefPtr<Node> >& nodeVector = *m_childNodes;
         if (m_currentIndex >= nodeVector.size())
             return 0;
         return nodeVector[m_currentIndex++];
     }
 
     void takeSnapshot()
     {
         if (hasSnapshot())
             return;
         m_childNodes = adoptPtr(new Vector<RefPtr<Node> >());
         Node* node = m_currentNode.get();
         while (node) {
             m_childNodes->append(node);
-            node = node->nextSibling();
+            node = node->previousSibling();
         }
     }
 
     ChildNodesLazySnapshot* nextSnapshot() { return m_nextSnapshot; }
     bool hasSnapshot() { return !!m_childNodes.get(); }
 
     static void takeChildNodesLazySnapshot()
     {
         ChildNodesLazySnapshot* snapshot = latestSnapshot;
         while (snapshot && !snapshot->hasSnapshot()) {
@@ skipping 25 matching lines @@
         m_node->resumePostAttachCallbacks();
     }
 
 private:
     ContainerNode* m_node;
 };
 
 } // namespace WebCore
 
 #endif // ContainerNode_h