Fix for 4010774, make sure to avoid an O(N^2) algorithm in nextRenderer() that is...

	DOM subtrees are inserted into documents via one insert/append call.

        Reviewed by kocienda

        * khtml/xml/dom_nodeimpl.cpp:
        (NodeImpl::nextRenderer):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@8709 268f45cc-cd09-0410-ab3c-d52691b4dbfc

diff --git a/WebCore/ChangeLog-2005-08-23 b/WebCore/ChangeLog-2005-08-23
index 7c5d41e31e5e620180d7513e04403dc2a39f21e1..44e2fdb059fa40239c667f0e9c4b145a71742fb1 100644 (file)
--- a/WebCore/ChangeLog-2005-08-23
+++ b/WebCore/ChangeLog-2005-08-23
@@ -1,3 +1,13 @@
+2005-02-25  David Hyatt  <hyatt@apple.com>
+
+       Fix for 4010774, make sure to avoid an O(N^2) algorithm in nextRenderer() that is triggered when large
+       DOM subtrees are inserted into documents via one insert/append call.
+       
+        Reviewed by kocienda
+
+        * khtml/xml/dom_nodeimpl.cpp:
+        (NodeImpl::nextRenderer):
+
 2005-02-25  Richard Williamson   <rjw@apple.com>
 
        Fixed <rdar://problem/3382926> Bidi neutrals at RTL/LTR boundaries not handled correctly.

diff --git a/WebCore/khtml/xml/dom_nodeimpl.cpp b/WebCore/khtml/xml/dom_nodeimpl.cpp
index aaec0e5a14ec96cd7115e0ece5ad291fac13d1b0..a6cb04fe23a54dcb6f16dc01600100eedc0e9d65 100644 (file)
--- a/WebCore/khtml/xml/dom_nodeimpl.cpp
+++ b/WebCore/khtml/xml/dom_nodeimpl.cpp
@@ -1234,6 +1234,11 @@ RenderObject * NodeImpl::previousRenderer()
 
 RenderObject * NodeImpl::nextRenderer()
 {
+    // Avoid an O(n^2) problem with this function by not checking for nextRenderer() when the parent element hasn't even 
+    // been attached yet.
+    if (parent() && !parent()->attached())
+        return 0;
+
     for (NodeImpl *n = nextSibling(); n; n = n->nextSibling()) {
         if (n->renderer())
             return n->renderer();