Cache element indices for :nth-child and :nth-last-child selectors.

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
new file mode 100644
index 0000000000000000000000000000000000000000..da0041d13d27a290810c5621390bba66a13ae9b1
--- /dev/null
+++ b/Source/core/dom/NthIndexCache.cpp
@@ -0,0 +1,70 @@
+// 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 {
+
+NthIndexCache* NthIndexCache::s_instance = nullptr;
+
+NthIndexCache::NthIndexCache(Document& document)
+    : m_document(&document)
+    , m_domTreeVersion(document.domTreeVersion())
+{
+    ASSERT(!s_instance);
+    s_instance = this;
+}
+
+NthIndexCache::~NthIndexCache()
+{
+    ASSERT(m_domTreeVersion == m_document->domTreeVersion());
+    s_instance = nullptr;
+}
+
+NthIndexCache::NthIndexData& NthIndexCache::ensureNthIndexDataFor(Node& parent)
+{
+    if (!m_parentMap)
+        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;
+}
+
+unsigned NthIndexCache::NthIndexData::cacheNthIndices(Element& element)
+{
+    unsigned index = 0;
+    const unsigned spread = 3;

[esprehn, 2015/03/31 17:35:15]

You might want a comment that explains what spread does.

[rune, 2015/03/31 20:57:37]

Done.

+    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;
+}
+
+DEFINE_TRACE(NthIndexCache::NthIndexData)
+{
+#if ENABLE(OILPAN)
+    visitor->trace(m_elementIndexMap);
+#endif
+}
+
+#if !ENABLE(OILPAN)
+NthIndexCache::NthIndexData::~NthIndexData()
+{
+}
+#endif
+
+} // namespace blink