Extending the NthIndexCache to support caching for the type of index.

Source/core/dom/NthIndexCache.cpp

Index: Source/core/dom/NthIndexCache.cpp
diff --git a/Source/core/dom/NthIndexCache.cpp b/Source/core/dom/NthIndexCache.cpp
index 498abafe26eae8179c1a6a9ad3ff00c5080761ad..547d48abbf536cec8a88ff9f935eda8a5956655e 100644
--- a/Source/core/dom/NthIndexCache.cpp
+++ b/Source/core/dom/NthIndexCache.cpp
@@ -35,9 +35,23 @@ NthIndexCache::NthIndexData& NthIndexCache::ensureNthIndexDataFor(Node& parent)
     return *addResult.storedValue->value;
 }
 
+NthIndexCache::IndexByType& NthIndexCache::ensureTypeIndexMap(Node& parent)
+{
+    if (!m_parentMapForType)
+        m_parentMapForType = adoptPtrWillBeNoop(new ParentMapForType());
+
+    ParentMapForType::AddResult addResult = m_parentMapForType->add(&parent, nullptr);
+    if (addResult.isNewEntry)
+        addResult.storedValue->value = adoptPtrWillBeNoop(new IndexByType());
+
+    ASSERT(addResult.storedValue->value);
+    return *addResult.storedValue->value;
+}
+
 unsigned NthIndexCache::NthIndexData::cacheNthIndices(Element& element)
 {
     ASSERT(!element.isPseudoElement());
+    ASSERT(m_elementIndexMap.isEmpty());
     unsigned index = 0;
     // The frequency at which we cache the nth-index for a set of siblings.
     // A spread value of 3 means every third Element will have its nth-index cached.
@@ -57,6 +71,37 @@ unsigned NthIndexCache::NthIndexData::cacheNthIndices(Element& element)
     return index;
 }
 
+unsigned NthIndexCache::NthIndexData::cacheNthIndicesOfType(Element& element, const QualifiedName& type)
+{
+    ASSERT(!element.isPseudoElement());
+    ASSERT(m_elementIndexMap.isEmpty());
+    unsigned index = 0;
+    // The frequency at which we cache the nth-index for a set of siblings.
+    // A spread value of 3 means every third Element will have its nth-index cached.
+    // Using a spread value > 1 is done to save memory. Looking up the nth-index will
+    // still be done in constant time in terms of sibling count, at most 'spread'
+    // elements will be traversed.

[rune, 2015/05/04 08:32:49]

This isn't entirely correct as you're storing every third element of a given
type. You should modify the description to make that clearer.

Note that that number of elements you need to traverse for a lookup is less
predictable than for nth-index since the distribution of elements of a given
type can be sparse, but we can use the spread like this for now.

+    const unsigned spread = 3;
+    unsigned count = 0;
+    for (Element* sibling = ElementTraversal::firstChild(*element.parentNode(), HasTagName(type)); sibling; sibling = ElementTraversal::nextSibling(*sibling, HasTagName(type))) {
+        if (!(++count % spread))
+            m_elementIndexMap.add(sibling, count);
+        if (sibling == &element)
+            index = count;
+    }
+    ASSERT(count && index);
+    m_count = count;
+    return index;
+}
+
+NthIndexCache::NthIndexData& NthIndexCache::nthIndexDataWithTagName(Element& element)
+{
+    IndexByType::AddResult addResult = ensureTypeIndexMap(*element.parentNode()).add(element.tagName(), nullptr);
+    if (addResult.isNewEntry)
+        addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData());
+    return *addResult.storedValue->value;
+}
+
 DEFINE_TRACE(NthIndexCache::NthIndexData)
 {
 #if ENABLE(OILPAN)