Refactor CollectionIndexCache for clarity and performance

Source/core/html/CollectionIndexCache.h

Index: Source/core/html/CollectionIndexCache.h
diff --git a/Source/core/html/CollectionIndexCache.h b/Source/core/html/CollectionIndexCache.h
index 39b60017c195f03f430a2b9eccefcb8087636f4a..4efcebb37d843f1c505432f7fb0a91a89bb56226 100644
--- a/Source/core/html/CollectionIndexCache.h
+++ b/Source/core/html/CollectionIndexCache.h
@@ -64,9 +64,8 @@ public:
     void invalidate();
 
 private:
-    NodeType* nodeBeforeOrAfterCachedNode(const Collection&, unsigned index, const ContainerNode& root);
-    bool isLastNodeCloserThanLastOrCachedNode(unsigned index) const;
-    bool isFirstNodeCloserThanCachedNode(unsigned index) const;
+    NodeType* nodeBeforeCachedNode(const Collection&, unsigned index, const ContainerNode& root);
+    NodeType* nodeAfterCachedNode(const Collection&, unsigned index, const ContainerNode& root);
 
     ALWAYS_INLINE NodeType* cachedNode() const { return m_currentNode; }
     ALWAYS_INLINE unsigned cachedNodeIndex() const { ASSERT(cachedNode()); return m_cachedNodeIndex; }
@@ -122,56 +121,81 @@ inline unsigned CollectionIndexCache<Collection, NodeType>::nodeCount(const Coll
 template <typename Collection, typename NodeType>
 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAt(const Collection& collection, unsigned index)
 {
-    if (cachedNode() && cachedNodeIndex() == index)
+    if (isCachedNodeCountValid() && index >= cachedNodeCount())
+        return 0;
+
+    ContainerNode& root = collection.rootNode();
+    if (cachedNode()) {
+        if (index > cachedNodeIndex())
+            return nodeAfterCachedNode(collection, index, root);
+        if (index < cachedNodeIndex())
+            return nodeBeforeCachedNode(collection, index, root);
         return cachedNode();
+    }
 
-    if (isCachedNodeCountValid() && cachedNodeCount() <= index)
+    // No valid cache yet, let's find the first matching element.
+    ASSERT(!isCachedNodeCountValid());
+    NodeType* firstNode = collection.traverseToFirstElement(root);
+    if (!firstNode) {
+        // The collection is empty.
+        setCachedNodeCount(0);
         return 0;
+    }
+    setCachedNode(firstNode, 0);
+    return index ? nodeAfterCachedNode(collection, index, root) : firstNode;
+}
 
-    ContainerNode& root = collection.rootNode();
-    if (isCachedNodeCountValid() && collection.canTraverseBackward() && isLastNodeCloserThanLastOrCachedNode(index)) {
-        NodeType* lastNode = collection.itemBefore(0);
-        ASSERT(lastNode);
-        setCachedNode(lastNode, cachedNodeCount() - 1);
-    } else if (!cachedNode() || isFirstNodeCloserThanCachedNode(index) || (!collection.canTraverseBackward() && index < cachedNodeIndex())) {
+template <typename Collection, typename NodeType>
+inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeCachedNode(const Collection& collection, unsigned index, const ContainerNode& root)
+{
+    ASSERT(cachedNode()); // Cache should be valid.
+    unsigned currentIndex = cachedNodeIndex();
+    ASSERT(currentIndex > index);
+
+    // Determine if we should traverse from the beginning of the collection instead of the cached node.
+    bool firstIsCloser = index < currentIndex - index;
+    if (firstIsCloser || !collection.canTraverseBackward()) {
         NodeType* firstNode = collection.traverseToFirstElement(root);
-        if (!firstNode) {
-            setCachedNodeCount(0);
-            return 0;
-        }
+        ASSERT(firstNode);
         setCachedNode(firstNode, 0);
-        ASSERT(!cachedNodeIndex());
+        return index ? nodeAfterCachedNode(collection, index, root) : firstNode;
     }
 
-    if (cachedNodeIndex() == index)
-        return cachedNode();
-
-    return nodeBeforeOrAfterCachedNode(collection, index, root);
+    // Backward traversal from the cached node to the requested index.
+    NodeType* currentNode = cachedNode();
+    ASSERT(collection.canTraverseBackward());
+    while ((currentNode = collection.itemBefore(currentNode))) {
+        ASSERT(currentIndex);
+        --currentIndex;
+        if (currentIndex == index) {
+            setCachedNode(currentNode, currentIndex);
+            return currentNode;
+        }
+    }
+    ASSERT_NOT_REACHED();
+    return 0;
 }
 
 template <typename Collection, typename NodeType>
-inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeOrAfterCachedNode(const Collection& collection, unsigned index, const ContainerNode &root)
+inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAfterCachedNode(const Collection& collection, unsigned index, const ContainerNode& root)
 {
+    ASSERT(cachedNode()); // Cache should be valid.
     unsigned currentIndex = cachedNodeIndex();
-    NodeType* currentNode = cachedNode();
-    ASSERT(currentNode);
-    ASSERT(currentIndex != index);
-
-    if (index < cachedNodeIndex()) {
-        ASSERT(collection.canTraverseBackward());
-        while ((currentNode = collection.itemBefore(currentNode))) {
-            ASSERT(currentIndex);
-            currentIndex--;
-            if (currentIndex == index) {
-                setCachedNode(currentNode, currentIndex);
-                return currentNode;
-            }
-        }
-        ASSERT_NOT_REACHED();
-        return 0;
+    ASSERT(currentIndex < index);
+
+    // Determine if we should traverse from the end of the collection instead of the cached node.
+    bool lastIsCloser = isCachedNodeCountValid() && cachedNodeCount() - index < index - currentIndex;
+    if (lastIsCloser && collection.canTraverseBackward()) {
+        NodeType* lastItem = collection.itemBefore(0);
+        ASSERT(lastItem);
+        setCachedNode(lastItem, cachedNodeCount() - 1);
+        if (index < cachedNodeCount() - 1)
+            return nodeBeforeCachedNode(collection, index, root);
+        return lastItem;
     }
 
-    currentNode = collection.traverseForwardToOffset(index, *currentNode, currentIndex, root);
+    // Forward traversal from the cached node to the requested index.
+    NodeType* currentNode = collection.traverseForwardToOffset(index, *cachedNode(), currentIndex, root);
     if (!currentNode) {
         // Did not find the node. On plus side, we now know the length.
         setCachedNodeCount(currentIndex + 1);
@@ -181,27 +205,6 @@ inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeOrAfterCa
     return currentNode;
 }
 
-template <typename Collection, typename NodeType>
-ALWAYS_INLINE bool CollectionIndexCache<Collection, NodeType>::isLastNodeCloserThanLastOrCachedNode(unsigned index) const
-{
-    ASSERT(isCachedNodeCountValid());
-    unsigned distanceFromLastNode = cachedNodeCount() - index;
-    if (!cachedNode())
-        return distanceFromLastNode < index;
-
-    return cachedNodeIndex() < index && distanceFromLastNode < index - cachedNodeIndex();
-}
-
-template <typename Collection, typename NodeType>
-ALWAYS_INLINE bool CollectionIndexCache<Collection, NodeType>::isFirstNodeCloserThanCachedNode(unsigned index) const
-{
-    if (cachedNodeIndex() < index)
-        return false;
-
-    unsigned distanceFromCachedNode = cachedNodeIndex() - index;
-    return index < distanceFromCachedNode;
-}
-
 } // namespace WebCore
 
 #endif // CollectionIndexCache_h