Reviewed by Richard.

	- reduce cost of innerHTML from O(N^2) to O(N*D) where N is the
	number of nodes and D is the maximum DOM tree depth.

        * khtml/xml/dom_nodeimpl.cpp:
        (NodeImpl::recursive_toString): New static helper method for
	recursive_toHTML - this is recursive for children but iterative
	for siblings.
        (NodeImpl::recursive_toHTML): Call the helper with this as the
	first argument.
        * khtml/xml/dom_nodeimpl.h:

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

diff --git a/WebCore/ChangeLog-2005-08-23 b/WebCore/ChangeLog-2005-08-23
index 144639b80e27bed41617b24a903395913b408e9e..2f4cc629bf445966e3ec86278749b3f08ce77974 100644 (file)
--- a/WebCore/ChangeLog-2005-08-23
+++ b/WebCore/ChangeLog-2005-08-23
@@ -1,3 +1,18 @@
+2004-08-23  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Richard.
+
+       - reduce cost of innerHTML from O(N^2) to O(N*D) where N is the
+       number of nodes and D is the maximum DOM tree depth.
+       
+        * khtml/xml/dom_nodeimpl.cpp:
+        (NodeImpl::recursive_toString): New static helper method for
+       recursive_toHTML - this is recursive for children but iterative
+       for siblings.
+        (NodeImpl::recursive_toHTML): Call the helper with this as the
+       first argument.
+        * khtml/xml/dom_nodeimpl.h:
+
 2004-08-23  David Hyatt  <hyatt@apple.com>
 
        Fix for 3558334. 

diff --git a/WebCore/khtml/xml/dom_nodeimpl.cpp b/WebCore/khtml/xml/dom_nodeimpl.cpp
index b7a3c2de4948cf83f1e942b5af843f55c129a47b..dd3452bb4c096c9c3e009ca98c2c72b05aecbc66 100644 (file)
--- a/WebCore/khtml/xml/dom_nodeimpl.cpp
+++ b/WebCore/khtml/xml/dom_nodeimpl.cpp
@@ -283,83 +283,90 @@ static QString escapeHTML( const QString& in )
     return s;
 }
 
-QString NodeImpl::recursive_toHTML(bool onlyIncludeChildren, const DOM::RangeImpl *range, QPtrList<NodeImpl> *nodes) const
-{      
-    bool include = true;
-    
-    if (onlyIncludeChildren) {
-        // Don't include the HTML of this node, but include the children in the next recursion.
-        include = false;
-    } else if (range) {
-        // If a range is passed, only include the node and its children's HTML if they are in the range or parents on nodes in the range.
-        include = false;
-        NodeImpl *pastEnd = range->pastEndNode();
-        for (NodeImpl *n = range->startNode(); n != pastEnd; n = n->traverseNextNode()) {
-            for (NodeImpl *ancestor = n; ancestor; ancestor = ancestor->parentNode()) {
-                if (this == ancestor) {
-                    include = true;
+QString NodeImpl::recursive_toString(const NodeImpl *startNode, bool onlyIncludeChildren, const DOM::RangeImpl *range, QPtrList<NodeImpl> *nodes)
+
+{
+    QString me = "";
+
+    for (const NodeImpl *current = startNode; current != NULL; current = current->nextSibling()) {
+        bool include = true;
+        if (onlyIncludeChildren) {
+            // Don't include the HTML of this node, but include the children in the next recursion.
+            include = false;
+        } else if (range) {
+            // If a range is passed, only include the node and its children's HTML if they are in the range or parents on nodes in the range.
+            include = false;
+            NodeImpl *pastEnd = range->pastEndNode();
+            for (NodeImpl *n = range->startNode(); n != pastEnd; n = n->traverseNextNode()) {
+                for (NodeImpl *ancestor = n; ancestor; ancestor = ancestor->parentNode()) {
+                    if (current == ancestor) {
+                        include = true;
+                        break;
+                    }
+                }
+                if (include) {
                     break;
                 }
             }
-            if (include) {
-                break;
-            }
-        }
-    }
-    
-    QString me = "";
-    
-    if (include) {
-        if (nodes) {
-            nodes->append(this);
         }
-        // Copy who I am into the me string
-        if (nodeType() == Node::TEXT_NODE) {
-            DOMString str = nodeValue().copy();
-            if (range) {
-                int exceptionCode;
-                if (this == range->endContainer(exceptionCode)) {
-                    str.truncate(range->endOffset(exceptionCode));
-                }
-                if (this == range->startContainer(exceptionCode)) {
-                    str.remove(0, range->startOffset(exceptionCode));
-                }
+        
+        if (include) {
+            if (nodes) {
+                nodes->append(current);
             }
-            Id parentID = parentNode()->id();
-            bool dontEscape = (parentID == ID_SCRIPT || parentID == ID_TEXTAREA || parentID == ID_STYLE);
-            me += dontEscape ? str.string() : escapeHTML(str.string());
-        } else if (nodeType() != Node::DOCUMENT_NODE) {
-            // If I am an element, not a text
-            me += QChar('<') + nodeName().string();
-            if (nodeType() == Node::ELEMENT_NODE) {
-                const ElementImpl *el = static_cast<const ElementImpl *>(this);
-                NamedAttrMapImpl *attrs = el->attributes();
-                unsigned long length = attrs->length();
-                for (unsigned int i=0; i<length; i++) {
-                    AttributeImpl *attr = attrs->attributeItem(i);
-                    me += " " + getDocument()->attrName(attr->id()).string() + "=\"" + attr->value().string() + "\"";
+            // Copy who I am into the me string
+            if (current->nodeType() == Node::TEXT_NODE) {
+                DOMString str = current->nodeValue().copy();
+                if (range) {
+                    int exceptionCode;
+                    if (current == range->endContainer(exceptionCode)) {
+                        str.truncate(range->endOffset(exceptionCode));
+                    }
+                    if (current == range->startContainer(exceptionCode)) {
+                        str.remove(0, range->startOffset(exceptionCode));
+                    }
                 }
+                Id parentID = current->parentNode()->id();
+                bool dontEscape = (parentID == ID_SCRIPT || parentID == ID_TEXTAREA || parentID == ID_STYLE);
+                me += dontEscape ? str.string() : escapeHTML(str.string());
+            } else if (current->nodeType() != Node::DOCUMENT_NODE) {
+                // If I am an element, not a text
+                me += QChar('<') + current->nodeName().string();
+                if (current->nodeType() == Node::ELEMENT_NODE) {
+                    const ElementImpl *el = static_cast<const ElementImpl *>(current);
+                    NamedAttrMapImpl *attrs = el->attributes();
+                    unsigned long length = attrs->length();
+                    for (unsigned int i=0; i<length; i++) {
+                        AttributeImpl *attr = attrs->attributeItem(i);
+                        me += " " + current->getDocument()->attrName(attr->id()).string() + "=\"" + attr->value().string() + "\"";
+                    }
+                }
+                me += current->isHTMLElement() ? ">" : "/>";
             }
-            me += isHTMLElement() ? ">" : "/>";
-        }
-    }
-    
-    if (!isHTMLElement() || endTag[id()] != FORBIDDEN) {
-        // print firstChild
-        if (NodeImpl *n = firstChild()) {
-            me += n->recursive_toHTML(false, range, nodes);
         }
-        // Print my ending tag
-        if (include && nodeType() != Node::TEXT_NODE && nodeType() != Node::DOCUMENT_NODE) {
-            me += "</" + nodeName().string() + ">";
+        
+        if (!current->isHTMLElement() || endTag[current->id()] != FORBIDDEN) {
+            // print children
+            if (NodeImpl *n = current->firstChild()) {
+                me += recursive_toString(n, false, range, nodes);
+            }
+            // Print my ending tag
+            if (include && current->nodeType() != Node::TEXT_NODE && current->nodeType() != Node::DOCUMENT_NODE) {
+                me += "</" + current->nodeName().string() + ">";
+            }
         }
-    }
-    // print next sibling
-    if (NodeImpl *n = nextSibling()) {
-        me += n->recursive_toHTML(false, range, nodes);
+        
+        // always include children for our siblings
+        onlyIncludeChildren = false;
     }
     
     return me;
+
+}
+
+QString NodeImpl::recursive_toHTML(bool onlyIncludeChildren, const DOM::RangeImpl *range, QPtrList<NodeImpl> *nodes) const
+{      
+    return NodeImpl::recursive_toString(this, onlyIncludeChildren, range, nodes);
 }
 
 void NodeImpl::recursive_completeURLs(QString baseURL)

diff --git a/WebCore/khtml/xml/dom_nodeimpl.h b/WebCore/khtml/xml/dom_nodeimpl.h
index 6af67086da33d9df1b07928d7a6a2ff7aa406e27..b65f6c1cec9cda598a4fa17cddcc70e299998c2e 100644 (file)
--- a/WebCore/khtml/xml/dom_nodeimpl.h
+++ b/WebCore/khtml/xml/dom_nodeimpl.h
@@ -261,6 +261,7 @@ public:
     virtual bool isInline() const;
     virtual QString toHTML() const;
     QString recursive_toHTML(bool onlyIncludeChildren=false, const DOM::RangeImpl *range=NULL, QPtrList<NodeImpl> *nodes=NULL) const;
+    static QString recursive_toString(const NodeImpl *startNode, bool onlyIncludeChildren=false, const DOM::RangeImpl *range=NULL, QPtrList<NodeImpl> *nodes=NULL);
     void recursive_completeURLs(QString baseURL);
     
     virtual bool isContentEditable() const;