Move caching out of LiveNodeListBase and into a new CollectionIndexCache class

Source/core/html/HTMLCollection.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. 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
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
@@ skipping 164 matching lines @@
 
 HTMLCollection::~HTMLCollection()
 {
     // HTMLNameCollection removes cache by itself.
     if (type() != WindowNamedItems && type() != DocumentNamedItems)
         ownerNode()->nodeLists()->removeCacheWithAtomicName(this, type());
 }
 
 void HTMLCollection::invalidateCache() const
 {
-    LiveNodeListBase::invalidateCache();
+    m_collectionIndexCache.invalidate();
     invalidateIdNameCacheMaps();
 }
 
 template <class NodeListType>
 inline bool isMatchingElement(const NodeListType&, const Element&);
 
 template <> inline bool isMatchingElement(const HTMLCollection& htmlCollection, const Element& element)
 {
     CollectionType type = htmlCollection.type();
     if (!element.isHTMLElement() && !(type == DocAll || type == NodeChildren || type == WindowNamedItems))
@@ skipping 96 matching lines @@
             if (current->isElementNode() && isMatchingElement(static_cast<const LiveNodeList&>(*this), toElement(*current)))
                 return toElement(current);
         } else {
             if (current->isElementNode() && isMatchingElement(static_cast<const HTMLCollection&>(*this), toElement(*current)))
                 return toElement(current);
         }
     }
     return 0;
 }
 
-ALWAYS_INLINE Node* LiveNodeListBase::itemBefore(const Node* previous) const
+Node* LiveNodeListBase::itemBefore(const Node* previous) const
 {
     Node* current;
     if (LIKELY(!!previous)) // Without this LIKELY, length() and item() can be 10% slower.
         current = previousNode(rootNode(), *previous, shouldOnlyIncludeDirectChildren());
     else
         current = lastNode(rootNode(), shouldOnlyIncludeDirectChildren());
 
     if (type() == ChildNodeListType)
         return current;
     return iterateForPreviousNode(current);
@@ skipping 36 matching lines @@
     Node* next = &currentNode;
     while ((next = next->nextSibling())) {
         if (++currentOffset == offset)
             return next;
     }
     return 0;
 }
 
 // FIXME: This should be in LiveNodeList.cpp but it needs to stay here until firstMatchingElement()
 // and others are moved to a separate header.
-inline Node* LiveNodeList::traverseToFirstElement(const ContainerNode& root) const
+Node* LiveNodeList::traverseToFirstElement(const ContainerNode& root) const
 {
     ASSERT(isLiveNodeListType(type()));
     switch (type()) {
     case ChildNodeListType:
         return root.firstChild();
     case HTMLTagNodeListType:
         return firstMatchingElement(static_cast<const HTMLTagNodeList&>(*this), root);
     case ClassNodeListType:
         return firstMatchingElement(static_cast<const ClassNodeList&>(*this), root);
     default:
         return firstMatchingElement(static_cast<const LiveNodeList&>(*this), root);
     }
 }
 
 // FIXME: This should be in LiveNodeList.cpp but it needs to stay here until traverseMatchingElementsForwardToOffset()
 // and others are moved to a separate header.
-inline Node* LiveNodeList::traverseForwardToOffset(unsigned offset, Node& currentNode, unsigned& currentOffset, const ContainerNode& root) const
+Node* LiveNodeList::traverseForwardToOffset(unsigned offset, Node& currentNode, unsigned& currentOffset, const ContainerNode& root) const
 {
     switch (type()) {
     case ChildNodeListType:
         return traverseSiblingsForwardToOffset(offset, currentNode, currentOffset);
     case HTMLTagNodeListType:
         return traverseMatchingElementsForwardToOffset(static_cast<const HTMLTagNodeList&>(*this), offset, toElement(currentNode), currentOffset, root);
     case ClassNodeListType:
         return traverseMatchingElementsForwardToOffset(static_cast<const ClassNodeList&>(*this), offset, toElement(currentNode), currentOffset, root);
     default:
         return traverseMatchingElementsForwardToOffset(*this, offset, toElement(currentNode), currentOffset, root);
     }
 }
 
-bool ALWAYS_INLINE LiveNodeListBase::isLastItemCloserThanLastOrCachedItem(unsigned offset) const
-{
-    ASSERT(isLengthCacheValid());
-    unsigned distanceFromLastItem = cachedLength() - offset;
-    if (!cachedItem())
-        return distanceFromLastItem < offset;
-
-    return cachedItemOffset() < offset && distanceFromLastItem < offset - cachedItemOffset();
-}
-
-bool ALWAYS_INLINE LiveNodeListBase::isFirstItemCloserThanCachedItem(unsigned offset) const
-{
-    if (cachedItemOffset() < offset)
-        return false;
-
-    unsigned distanceFromCachedItem = cachedItemOffset() - offset;
-    return offset < distanceFromCachedItem;
-}
-
-unsigned LiveNodeListBase::length() const
-{
-    if (isLengthCacheValid())
-        return cachedLength();
-
-    item(UINT_MAX);
-    ASSERT(isLengthCacheValid());
-
-    return cachedLength();
-}
-
-// FIXME: It is silly that these functions are in HTMLCollection.cpp.
-Node* LiveNodeListBase::item(unsigned offset) const
-{
-    if (cachedItem() && cachedItemOffset() == offset)
-        return cachedItem();
-
-    if (isLengthCacheValid() && cachedLength() <= offset)
-        return 0;
-
-    ContainerNode& root = rootNode();
-    if (isLengthCacheValid() && !overridesItemAfter() && isLastItemCloserThanLastOrCachedItem(offset)) {
-        Node* lastItem = itemBefore(0);
-        ASSERT(lastItem);
-        setItemCache(lastItem, cachedLength() - 1);
-    } else if (!cachedItem() || isFirstItemCloserThanCachedItem(offset) || (overridesItemAfter() && offset < cachedItemOffset())) {
-        Node* firstItem;
-        if (isLiveNodeListType(type()))
-            firstItem = static_cast<const LiveNodeList*>(this)->traverseToFirstElement(root);
-        else
-            firstItem = static_cast<const HTMLCollection*>(this)->traverseToFirstElement(root);
-
-        if (!firstItem) {
-            setLengthCache(0);
-            return 0;
-        }
-        setItemCache(firstItem, 0);
-        ASSERT(!cachedItemOffset());
-    }
-
-    if (cachedItemOffset() == offset)
-        return cachedItem();
-
-    return itemBeforeOrAfterCachedItem(offset, root);
-}
-
-inline Node* LiveNodeListBase::itemBeforeOrAfterCachedItem(unsigned offset, const ContainerNode& root) const
-{
-    unsigned currentOffset = cachedItemOffset();
-    Node* currentItem = cachedItem();
-    ASSERT(currentItem);
-    ASSERT(currentOffset != offset);
-
-    if (offset < cachedItemOffset()) {
-        ASSERT(!overridesItemAfter());
-        while ((currentItem = itemBefore(currentItem))) {
-            ASSERT(currentOffset);
-            currentOffset--;
-            if (currentOffset == offset) {
-                setItemCache(currentItem, currentOffset);
-                return currentItem;
-            }
-        }
-        ASSERT_NOT_REACHED();
-        return 0;
-    }
-
-    if (isLiveNodeListType(type()))
-        currentItem = static_cast<const LiveNodeList*>(this)->traverseForwardToOffset(offset, *currentItem, currentOffset, root);
-    else
-        currentItem = static_cast<const HTMLCollection*>(this)->traverseForwardToOffset(offset, toElement(*currentItem), currentOffset, root);
-
-    if (!currentItem) {
-        // Did not find the item. On plus side, we now know the length.
-        setLengthCache(currentOffset + 1);
-        return 0;
-    }
-    setItemCache(currentItem, currentOffset);
-    return currentItem;
-}
-
 Element* HTMLCollection::virtualItemAfter(Element*) const
 {
     ASSERT_NOT_REACHED();
     return 0;
 }
 
 static inline bool nameShouldBeVisibleInDocumentAll(const HTMLElement& element)
 {
     // The document.all collection returns only certain types of elements by name,
     // although it returns any type of element by id.
@@ skipping 31 matching lines @@
 
 inline Element* nextMatchingChildElement(const HTMLCollection& nodeList, Element& current, const ContainerNode& root)
 {
     Element* next = &current;
     do {
         next = ElementTraversal::nextSkippingChildren(*next, &root);
     } while (next && !isMatchingElement(nodeList, *next));
     return next;
 }
 
-inline Element* HTMLCollection::traverseToFirstElement(const ContainerNode& root) const
+Element* HTMLCollection::traverseToFirstElement(const ContainerNode& root) const
 {
     if (overridesItemAfter())
         return virtualItemAfter(0);
     if (shouldOnlyIncludeDirectChildren())
         return firstMatchingChildElement(*this, root);
     return firstMatchingElement(*this, root);
 }
 
 inline Element* HTMLCollection::traverseNextElement(Element& previous, const ContainerNode& root) const
 {
     if (overridesItemAfter())
         return virtualItemAfter(&previous);
     if (shouldOnlyIncludeDirectChildren())
         return nextMatchingChildElement(*this, previous, root);
     return nextMatchingElement(*this, previous, root);
 }
 
-inline Element* HTMLCollection::traverseForwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset, const ContainerNode& root) const
+Element* HTMLCollection::traverseForwardToOffset(unsigned offset, Node& currentElement, unsigned& currentOffset, const ContainerNode& root) const
 {
     ASSERT(currentOffset < offset);
     if (overridesItemAfter()) {
-        Element* next = &currentElement;
+        Element* next = &toElement(currentElement);
         while ((next = virtualItemAfter(next))) {
             if (++currentOffset == offset)
                 return next;
         }
         return 0;
     }
     if (shouldOnlyIncludeDirectChildren()) {
-        Element* next = &currentElement;
+        Element* next = &toElement(currentElement);
         while ((next = nextMatchingChildElement(*this, *next, root))) {
             if (++currentOffset == offset)
                 return next;
         }
         return 0;
     }
-    return traverseMatchingElementsForwardToOffset(*this, offset, currentElement, currentOffset, root);
+    return traverseMatchingElementsForwardToOffset(*this, offset, toElement(currentElement), currentOffset, root);
 }
 
 Element* HTMLCollection::namedItem(const AtomicString& name) const
 {
     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
     // This method first searches for an object with a matching id
     // attribute. If a match is not found, the method then searches for an
     // object with a matching name attribute, but only on those elements
     // that are allowed a name attribute.
 
     ContainerNode& root = rootNode();
     unsigned i = 0;
     for (Element* element = traverseToFirstElement(root); element; element = traverseNextElement(*element, root)) {
         if (checkForNameMatch(*element, /* checkName */ false, name)) {
-            setItemCache(element, i);
+            m_collectionIndexCache.setCachedNode(element, i);
             return element;
         }
         i++;
     }
 
     i = 0;
     for (Element* element = traverseToFirstElement(root); element; element = traverseNextElement(*element, root)) {
         if (checkForNameMatch(*element, /* checkName */ true, name)) {
-            setItemCache(element, i);
+            m_collectionIndexCache.setCachedNode(element, i);
             return element;
         }
         i++;
     }
 
     return 0;
 }
 
 void HTMLCollection::updateNameCache() const
 {
@@ skipping 35 matching lines @@
 
 void HTMLCollection::append(NodeCacheMap& map, const AtomicString& key, Element* element)
 {
     OwnPtr<Vector<Element*> >& vector = map.add(key.impl(), nullptr).iterator->value;
     if (!vector)
         vector = adoptPtr(new Vector<Element*>);
     vector->append(element);
 }
 
 } // namespace WebCore