From d58905123e461233ed63a131db7faa60181b88ba Mon Sep 17 00:00:00 2001 From: mjs Date: Tue, 24 Aug 2004 04:13:49 +0000 Subject: [PATCH] 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 --- WebCore/ChangeLog-2005-08-23 | 15 ++++ WebCore/khtml/xml/dom_nodeimpl.cpp | 137 +++++++++++++++-------------- WebCore/khtml/xml/dom_nodeimpl.h | 1 + 3 files changed, 88 insertions(+), 65 deletions(-) diff --git a/WebCore/ChangeLog-2005-08-23 b/WebCore/ChangeLog-2005-08-23 index 144639b80e27..2f4cc629bf44 100644 --- a/WebCore/ChangeLog-2005-08-23 +++ b/WebCore/ChangeLog-2005-08-23 @@ -1,3 +1,18 @@ +2004-08-23 Maciej Stachowiak + + 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 Fix for 3558334. diff --git a/WebCore/khtml/xml/dom_nodeimpl.cpp b/WebCore/khtml/xml/dom_nodeimpl.cpp index b7a3c2de4948..dd3452bb4c09 100644 --- 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 *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 *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(this); - NamedAttrMapImpl *attrs = el->attributes(); - unsigned long length = attrs->length(); - for (unsigned int i=0; iattributeItem(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(current); + NamedAttrMapImpl *attrs = el->attributes(); + unsigned long length = attrs->length(); + for (unsigned int i=0; iattributeItem(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 += ""; + + 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 += "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 *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 6af67086da33..b65f6c1cec9c 100644 --- 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 *nodes=NULL) const; + static QString recursive_toString(const NodeImpl *startNode, bool onlyIncludeChildren=false, const DOM::RangeImpl *range=NULL, QPtrList *nodes=NULL); void recursive_completeURLs(QString baseURL); virtual bool isContentEditable() const; -- 2.36.0