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

Source/core/dom/NthIndexCache.cpp

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "config.h"
 #include "core/dom/NthIndexCache.h"
 
 #include "core/dom/Document.h"
 
 namespace blink {
@@ skipping 17 matching lines @@
         m_parentMap = adoptPtrWillBeNoop(new ParentMap());
 
     ParentMap::AddResult addResult = m_parentMap->add(&parent, nullptr);
     if (addResult.isNewEntry)
         addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData());
 
     ASSERT(addResult.storedValue->value);
     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;
     // 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()); sibling; sibling = ElementTraversal::nextSibling(*sibling)) {
         if (!(++count % spread))
             m_elementIndexMap.add(sibling, count);
         if (sibling == &element)
             index = count;
     }
     ASSERT(count && index);
     m_count = count;
     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)
     visitor->trace(m_elementIndexMap);
 #endif
 }
 
 #if !ENABLE(OILPAN)
 NthIndexCache::NthIndexData::~NthIndexData()
 {
 }
 #endif
 
 } // namespace blink