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 01e721902a361ff88abae6757071ce9300d8dd05..8d4e80b7c69bde718831233d98e7a5471828e6c9 100644
--- a/Source/core/dom/NthIndexCache.cpp
+++ b/Source/core/dom/NthIndexCache.cpp
@@ -35,6 +35,19 @@ NthIndexCache::NthIndexData& NthIndexCache::ensureNthIndexDataFor(Node& parent)
     return *addResult.storedValue->value;
 }
 
+NthIndexCache::ElementTagNameAndNthIndexMap& NthIndexCache::ensureElementTagNameAndNthIndexMapForType(Node& parent)

[esprehn, 2015/04/30 04:55:05]

ensureTypeIndexMap(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 ElementTagNameAndNthIndexMap());
+
+    ASSERT(addResult.storedValue->value);
+    return *addResult.storedValue->value;
+}
+
 unsigned NthIndexCache::NthIndexData::cacheNthIndices(Element& element)
 {
     unsigned index = 0;
@@ -56,6 +69,40 @@ unsigned NthIndexCache::NthIndexData::cacheNthIndices(Element& element)
     return index;
 }
 
+unsigned NthIndexCache::NthIndexData::cacheNthIndicesOfType(Element& element, const QualifiedName& type)

[esprehn, 2015/04/30 04:55:05]

We should make NthIndexData not a nested class.

+{
+    unsigned index = 0;

[esprehn, 2015/04/30 04:55:05]

This and the other method should both ASSERT(m_elementIndexMap.isEmpty())

+    // 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.
+    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(ElementTagNameAndNthIndexMap& m_elementTagNameAndNthIndexMap, Element& element)
+{
+
+    auto it = m_elementTagNameAndNthIndexMap.find(element.tagName());

[esprehn, 2015/04/30 04:55:05]

You should not call find() and then add(), always call add() and then check
isNewEntry. You're doing the hash lookup twice here and also have duplicate
code.

This should call the ensureTypeMap internally.

+    if (it != m_elementTagNameAndNthIndexMap.end())
+        return *(it->value);

[esprehn, 2015/04/30 04:55:05]

Delete this.

+    ElementTagNameAndNthIndexMap::AddResult addResult = m_elementTagNameAndNthIndexMap.add(element.tagName(), nullptr);

[esprehn, 2015/04/30 04:55:05]

m_indexByType, you don't need these verbose names.

+    if (addResult.isNewEntry)
+        addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData());
+    return *addResult.storedValue->value;
+    }
+}
+
 DEFINE_TRACE(NthIndexCache::NthIndexData)
 {
 #if ENABLE(OILPAN)