Reviewed by Adele
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 27 Jun 2006 20:36:20 +0000 (20:36 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 27 Jun 2006 20:36:20 +0000 (20:36 +0000)
        - fixed <rdar://problem/4550473> Reproducible hang on www.digg.com

        * dom/NodeList.cpp:
        (WebCore::NodeList::recursiveItem): Make NodeList caching also
        work for backwards iteration - if the requested index is before
        the last cached, but closer to it than to the start of the list,
        then search backwards from there.
        (WebCore::NodeList::itemForwardsFromCurrent): Split this out as a
        helper method.
        (WebCore::NodeList::itemBackwardsFromCurrent): New helper, similar
        to the above.
        * dom/NodeList.h:

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

WebCore/ChangeLog
WebCore/dom/NodeList.cpp
WebCore/dom/NodeList.h

index 20aa216f9a1b4743321579429d27e55c76e32f82..7a050c4691baedc7a4df6421e513b1e664995b1d 100644 (file)
@@ -1,3 +1,20 @@
+2006-06-27  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Adele
+
+        - fixed <rdar://problem/4550473> Reproducible hang on www.digg.com
+        
+        * dom/NodeList.cpp:
+        (WebCore::NodeList::recursiveItem): Make NodeList caching also
+        work for backwards iteration - if the requested index is before
+        the last cached, but closer to it than to the start of the list,
+        then search backwards from there.
+        (WebCore::NodeList::itemForwardsFromCurrent): Split this out as a
+        helper method.
+        (WebCore::NodeList::itemBackwardsFromCurrent): New helper, similar
+        to the above.
+        * dom/NodeList.h:
+
 2006-06-27  Brady Eidson  <beidson@apple.com>
 
         Reviewed by Levi
index 6ce9ca9e852e42f4414dfaca8010e81eeabb919d..2191dfd5c39bf492ee42df249ed02abef996f5e5 100644 (file)
@@ -68,22 +68,31 @@ unsigned NodeList::recursiveLength(Node* start) const
     return len;
 }
 
-Node* NodeList::recursiveItem(unsigned offset, Node* start) const
+Node* NodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
 {
-    int remainingOffset = offset;
-    if (!start) {
-        start = rootNode->firstChild();
-        if (isItemCacheValid) {
-            if (offset == lastItemOffset) {
-                return lastItem;
-            } else if (offset > lastItemOffset) {
-                start = lastItem;
-                remainingOffset -= lastItemOffset;
+    ASSERT(remainingOffset >= 0);
+
+    for (Node *n = start; n; n = n->traverseNextNode(rootNode.get())) {
+        if (n->isElementNode()) {
+            if (nodeMatches(n)) {
+                if (!remainingOffset) {
+                    lastItem = n;
+                    lastItemOffset = offset;
+                    isItemCacheValid = true;
+                    return n;
+                }
+                remainingOffset--;
             }
         }
     }
 
-    for (Node *n = start; n; n = n->traverseNextNode(rootNode.get())) {
+    return 0; // no matching node in this subtree
+}
+
+Node* NodeList::itemBackwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
+{
+    ASSERT(remainingOffset < 0);
+    for (Node *n = start; n; n = n->traversePreviousNode(rootNode.get())) {
         if (n->isElementNode()) {
             if (nodeMatches(n)) {
                 if (!remainingOffset) {
@@ -92,7 +101,7 @@ Node* NodeList::recursiveItem(unsigned offset, Node* start) const
                     isItemCacheValid = true;
                     return n;
                 }
-                remainingOffset--;
+                remainingOffset++;
             }
         }
     }
@@ -100,6 +109,27 @@ Node* NodeList::recursiveItem(unsigned offset, Node* start) const
     return 0; // no matching node in this subtree
 }
 
+Node* NodeList::recursiveItem(unsigned offset, Node* start) const
+{
+    int remainingOffset = offset;
+    if (!start) {
+        start = rootNode->firstChild();
+        if (isItemCacheValid) {
+            if (offset == lastItemOffset) {
+                return lastItem;
+            } else if (offset > lastItemOffset || lastItemOffset - offset < offset) {
+                start = lastItem;
+                remainingOffset -= lastItemOffset;
+            }
+        }
+    }
+
+    if (remainingOffset < 0)
+        return itemBackwardsFromCurrent(start, offset, remainingOffset);
+    else
+        return itemForwardsFromCurrent(start, offset, remainingOffset);
+}
+
 Node* NodeList::itemWithName(const AtomicString& elementId) const
 {
     if (rootNode->isDocumentNode() || rootNode->inDocument()) {
index 6d2dd640cc08751512238e64f941a654f4ef7b5d..f41e559014941ed63ffff58d256ed09eb7b2c338 100644 (file)
@@ -61,6 +61,10 @@ protected:
     mutable unsigned lastItemOffset;
     mutable bool isLengthCacheValid : 1;
     mutable bool isItemCacheValid : 1;
+
+ private:
+    Node* itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const;
+    Node* itemBackwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const;
 };
 
 } //namespace