Reviewed by Kevin.

	<rdar://problem/3807080> Safari so slow it seems like a hang accessing a page on an IBM website

        * khtml/xml/dom_nodeimpl.cpp:
        (NodeListImpl::NodeListImpl): Initialize isItemCacheValid, renamed isCacheValid to
	isLengthCacheValid.
        (NodeListImpl::recursiveLength): Adjusted for rename.
        (NodeListImpl::recursiveItem): Cache the last item accessed and its offset.
	If the same offset is looked up again, just return it, otherwise, if looking up
	a later offset, start at the last item and proceed from there.
        (NodeListImpl::itemById): Apply the special document optimization to all
	nodes that are either a document or in a document - just walk up to make
	sure the node found by ID has the root node as an ancestor.
        (NodeListImpl::rootNodeSubtreeModified): Adjust both cache bits.
        * khtml/xml/dom_nodeimpl.h: Prototype new stuff.

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

diff --git a/WebCore/ChangeLog-2005-08-23 b/WebCore/ChangeLog-2005-08-23
index 07d7f2629192d29e1fdbc7037e3eac917b2b301b..a05fab0132f657cfbd8cda311585f8f56bbca39e 100644 (file)
--- a/WebCore/ChangeLog-2005-08-23
+++ b/WebCore/ChangeLog-2005-08-23
@@ -1,3 +1,22 @@
+2004-11-15  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Kevin.
+
+       <rdar://problem/3807080> Safari so slow it seems like a hang accessing a page on an IBM website
+       
+        * khtml/xml/dom_nodeimpl.cpp:
+        (NodeListImpl::NodeListImpl): Initialize isItemCacheValid, renamed isCacheValid to
+       isLengthCacheValid.
+        (NodeListImpl::recursiveLength): Adjusted for rename.
+        (NodeListImpl::recursiveItem): Cache the last item accessed and its offset.
+       If the same offset is looked up again, just return it, otherwise, if looking up
+       a later offset, start at the last item and proceed from there.
+        (NodeListImpl::itemById): Apply the special document optimization to all
+       nodes that are either a document or in a document - just walk up to make
+       sure the node found by ID has the root node as an ancestor.
+        (NodeListImpl::rootNodeSubtreeModified): Adjust both cache bits.
+        * khtml/xml/dom_nodeimpl.h: Prototype new stuff.
+
 2004-11-15  John Sullivan  <sullivan@apple.com>
 
         Reviewed by Ken.

diff --git a/WebCore/khtml/xml/dom_nodeimpl.cpp b/WebCore/khtml/xml/dom_nodeimpl.cpp
index b6ffb4fd0234824faae3db014d58baba1ac7d4c8..7dce5076fc76705581e1326ac220893c65b9bed0 100644 (file)
--- a/WebCore/khtml/xml/dom_nodeimpl.cpp
+++ b/WebCore/khtml/xml/dom_nodeimpl.cpp
@@ -2213,7 +2213,8 @@ void NodeBaseImpl::dispatchChildRemovalEvents( NodeImpl *child, int &exceptionco
 
 NodeListImpl::NodeListImpl(NodeImpl *_rootNode)
     : rootNode(_rootNode),
-      isCacheValid(false)
+      isLengthCacheValid(false),
+      isItemCacheValid(false)
 {
     rootNode->ref();
     rootNode->registerNodeList(this);
@@ -2230,7 +2231,7 @@ unsigned long NodeListImpl::recursiveLength( NodeImpl *start ) const
     if (!start)
        start = rootNode;
 
-    if (isCacheValid && start == rootNode) {
+    if (isLengthCacheValid && start == rootNode) {
         return cachedLength;
     }
 
@@ -2246,26 +2247,51 @@ unsigned long NodeListImpl::recursiveLength( NodeImpl *start ) const
 
     if (start == rootNode) {
         cachedLength = len;
-        isCacheValid = true;
+        isLengthCacheValid = true;
     }
 
     return len;
 }
 
-NodeImpl *NodeListImpl::recursiveItem ( unsigned long &offset, NodeImpl *start ) const
+NodeImpl *NodeListImpl::recursiveItem ( unsigned long offset, NodeImpl *start) const
 {
-    if (!start)
-       start = rootNode;
+    int remainingOffset = offset;
+    if (!start) {
+        start = rootNode->firstChild();
+        if (isItemCacheValid) {
+            if (offset == lastItemOffset) {
+                return lastItem;
+            } else if (offset > lastItemOffset) {
+                start = lastItem;
+                remainingOffset -= lastItemOffset;
+            }
+        }
+    }
 
-    for(NodeImpl *n = start->firstChild(); n != 0; n = n->nextSibling()) {
+    NodeImpl *end = rootNode->nextSibling();
+    NodeImpl *n = start;
+
+    while (n != 0 && n != end) {
         if ( n->nodeType() == Node::ELEMENT_NODE ) {
-            if (nodeMatches(n))
-                if (!offset--)
+            if (nodeMatches(n)) {
+                if (!remainingOffset) {
+                    lastItem = n;
+                    lastItemOffset = offset;
+                    isItemCacheValid = 1;
                     return n;
+                }
+                remainingOffset--;
+            }
+        }
 
-            NodeImpl *depthSearch= recursiveItem(offset, n);
-            if (depthSearch)
-                return depthSearch;
+        if (n->firstChild()) {
+            n = n->firstChild();
+        } else if (n->nextSibling()) {
+            n = n->nextSibling();
+        } else if (n->parentNode()) {
+            n = n->parentNode()->nextSibling();
+        } else {
+            n = 0;
         }
     }
 
@@ -2274,10 +2300,16 @@ NodeImpl *NodeListImpl::recursiveItem ( unsigned long &offset, NodeImpl *start )
 
 NodeImpl *NodeListImpl::itemById (const DOMString& elementId) const
 {
-    if (rootNode->isDocumentNode()) {
-        DOM::NodeImpl *node = static_cast<DocumentImpl *>(rootNode)->getElementById(elementId);
-        if (nodeMatches(node))
-            return node;
+    if (rootNode->isDocumentNode() || rootNode->inDocument()) {
+        NodeImpl *node = rootNode->getDocument()->getElementById(elementId);
+
+        if (node == NULL || !nodeMatches(node))
+            return 0;
+
+        for (NodeImpl *p = node->parentNode(); p; p = p->parentNode()) {
+            if (p == rootNode)
+                return node;
+        }
 
         return 0;
     }
@@ -2285,7 +2317,7 @@ NodeImpl *NodeListImpl::itemById (const DOMString& elementId) const
     unsigned long l = length();
 
     for ( unsigned long i = 0; i < l; i++ ) {
-        DOM::NodeImpl *node = item(i);
+        NodeImpl *node = item(i);
         
         if ( static_cast<ElementImpl *>(node)->getIDAttribute() == elementId ) {
             return node;
@@ -2298,7 +2330,8 @@ NodeImpl *NodeListImpl::itemById (const DOMString& elementId) const
 
 void NodeListImpl::rootNodeSubtreeModified()
 {
-    isCacheValid = false;     
+    isLengthCacheValid = false;     
+    isItemCacheValid = false;     
 }
 
 

diff --git a/WebCore/khtml/xml/dom_nodeimpl.h b/WebCore/khtml/xml/dom_nodeimpl.h
index 18f6c002767e8442dd3f04a6d61dd8b504073403..724035ba7c21cd43018aa2c8685f24c8c0a1a23d 100644 (file)
--- a/WebCore/khtml/xml/dom_nodeimpl.h
+++ b/WebCore/khtml/xml/dom_nodeimpl.h
@@ -571,12 +571,15 @@ public:
 protected:
     // helper functions for searching all ElementImpls in a tree
     unsigned long recursiveLength(NodeImpl *start = 0) const;
-    NodeImpl *recursiveItem ( unsigned long &offset, NodeImpl *start = 0 ) const;
+    NodeImpl *recursiveItem ( unsigned long offset, NodeImpl *start = 0 ) const;
     virtual bool nodeMatches( NodeImpl *testNode ) const = 0;
 
     NodeImpl *rootNode;
     mutable int cachedLength;
-    mutable bool isCacheValid;
+    mutable NodeImpl *lastItem;
+    mutable unsigned long lastItemOffset;
+    mutable bool isLengthCacheValid : 1;
+    mutable bool isItemCacheValid : 1;
 };
 
 class ChildNodeListImpl : public NodeListImpl