DOM Optimizations

DOM traversal optimizations
DOM Core optimizations
Prefetch optimization for DOM Tree Traversal

Conflicts:

	Source/WebKit/android/jni/WebViewCore.cpp

Change-Id: Icbb8a7229ee9cff1a5401b57c8181f18b9a6d6e0

1 files changed, 40 insertions, 6 deletions

diff --git a/Source/WebCore/dom/DynamicNodeList.cpp b/Source/WebCore/dom/DynamicNodeList.cpp
index 23664e8..bba1678 100644
--- a/Source/WebCore/dom/DynamicNodeList.cpp
+++ b/Source/WebCore/dom/DynamicNodeList.cpp
@@ -3,6 +3,7 @@
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2004, 2006, 2007, 2008, 2010 Apple Inc. All rights reserved.
+ * Copyright (C) 2012 The Linux Foundation All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -56,8 +57,18 @@ unsigned DynamicNodeList::length() const
 
     unsigned length = 0;
 
-    for (Node* n = m_rootNode->firstChild(); n; n = n->traverseNextNode(m_rootNode.get()))
-        length += n->isElementNode() && nodeMatches(static_cast<Element*>(n));
+    Node* lastNode = m_rootNode->lastDescendantNode();
+    Vector<Node* >& cachedNodes = m_caches->cachedNodes;
+    for (Node* n = m_rootNode->firstChild(); n; n = n->traverseNextNodeFastPath()) {
+        if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
+            if (length >= cachedNodes.size())
+                cachedNodes.resize(length + 1);
+            cachedNodes.data()[length] = n;
+            length ++;
+        }
+        if (n == lastNode)
+            break;
+    }
 
     m_caches->cachedLength = length;
     m_caches->isLengthCacheValid = true;
@@ -68,7 +79,9 @@ unsigned DynamicNodeList::length() const
 Node* DynamicNodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
 {
     ASSERT(remainingOffset >= 0);
-    for (Node* n = start; n; n = n->traverseNextNode(m_rootNode.get())) {
+    if (!m_caches->lastDecendantOfRoot)
+        m_caches->lastDecendantOfRoot = m_rootNode->lastDescendantNode();
+    for (Node* n = start; n; n = n->traverseNextNodeFastPath()) {
         if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
             if (!remainingOffset) {
                 m_caches->lastItem = n;
@@ -78,6 +91,8 @@ Node* DynamicNodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int
             }
             --remainingOffset;
         }
+        if (n == m_caches->lastDecendantOfRoot)
+            break;
     }
 
     return 0; // no matching node in this subtree
@@ -103,6 +118,14 @@ Node* DynamicNodeList::itemBackwardsFromCurrent(Node* start, unsigned offset, in
 
 Node* DynamicNodeList::item(unsigned offset) const
 {
+    Node* result;
+    Vector<Node* >& cachedNodes = m_caches->cachedNodes;
+    if (offset < cachedNodes.size()) {
+        result = cachedNodes[offset];
+        if (result)
+            return result;
+    }
+
     int remainingOffset = offset;
     Node* start = m_rootNode->firstChild();
     if (m_caches->isItemCacheValid) {
@@ -115,8 +138,16 @@ Node* DynamicNodeList::item(unsigned offset) const
     }
 
     if (remainingOffset < 0)
-        return itemBackwardsFromCurrent(start, offset, remainingOffset);
-    return itemForwardsFromCurrent(start, offset, remainingOffset);
+        result = itemBackwardsFromCurrent(start, offset, remainingOffset);
+    else
+        result = itemForwardsFromCurrent(start, offset, remainingOffset);
+
+    if (result) {
+        if (offset >= cachedNodes.size())
+            cachedNodes.resize(offset + 1);
+        cachedNodes.data()[offset] = result;
+    }
+    return result;
 }
 
 Node* DynamicNodeList::itemWithName(const AtomicString& elementId) const
@@ -159,6 +190,7 @@ void DynamicNodeList::invalidateCache()
 
 DynamicNodeList::Caches::Caches()
     : lastItem(0)
+    , lastDecendantOfRoot(0)
     , isLengthCacheValid(false)
     , isItemCacheValid(false)
 {
@@ -172,8 +204,10 @@ PassRefPtr<DynamicNodeList::Caches> DynamicNodeList::Caches::create()
 void DynamicNodeList::Caches::reset()
 {
     lastItem = 0;
+    lastDecendantOfRoot = 0;
     isLengthCacheValid = false;
-    isItemCacheValid = false;     
+    isItemCacheValid = false;
+    cachedNodes.clear();
 }
 
 } // namespace WebCore