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

Source/core/dom/ContainerNodeAlgorithms.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, 2010, 2011 Apple Inc. All rights reserved.
  * Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies)
  * Copyright (C) 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (C) 2012 Google Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
@@ skipping 17 matching lines @@
 
 #include "core/dom/Element.h"
 #include "core/dom/shadow/ElementShadow.h"
 #include "core/html/HTMLFrameOwnerElement.h"
 
 namespace WebCore {
 
 void ChildNodeInsertionNotifier::notifyDescendantInsertedIntoDocument(ContainerNode* node)
 {
     ChildNodesLazySnapshot snapshot(node);
-    while (RefPtr<Node> child = snapshot.nextNode()) {
+    while (RefPtr<Node> child = snapshot.previousNode()) {
         // If we have been removed from the document during this loop, then
         // we don't want to tell the rest of our children that they've been
         // inserted into the document because they haven't.
         if (node->inDocument() && child->parentNode() == node)
             notifyNodeInsertedIntoDocument(child.get());
     }
 
     if (!node->isElementNode())
         return;
 
@@ skipping 13 matching lines @@
             notifyNodeInsertedIntoTree(toContainerNode(child));
     }
 
     for (ShadowRoot* root = node->youngestShadowRoot(); root; root = root->olderShadowRoot())
         notifyNodeInsertedIntoTree(root);
 }
 
 void ChildNodeRemovalNotifier::notifyDescendantRemovedFromDocument(ContainerNode* node)
 {
     ChildNodesLazySnapshot snapshot(node);
-    while (RefPtr<Node> child = snapshot.nextNode()) {
+    while (RefPtr<Node> child = snapshot.previousNode()) {
         // If we have been added to the document during this loop, then we
         // don't want to tell the rest of our children that they've been
         // removed from the document because they haven't.
         if (!node->inDocument() && child->parentNode() == node)
             notifyNodeRemovedFromDocument(child.get());
     }
 
     if (!node->isElementNode())
         return;
 
@@ skipping 57 matching lines @@
     // If we overcount it's safe, but not optimal because it means we'll traverse
     // through the document in ChildFrameDisconnector looking for frames that have
     // already been disconnected.
     ASSERT(node->connectedSubframeCount() == count);
 
     return count;
 }
 #endif
 
 }