Revert "Simplify DocumentOrderedMap"

Source/core/dom/DocumentOrderedMap.cpp

Index: Source/core/dom/DocumentOrderedMap.cpp
diff --git a/Source/core/dom/DocumentOrderedMap.cpp b/Source/core/dom/DocumentOrderedMap.cpp
index ee4c3895b3888bf5238f16dc7fdc7ee964c86ecc..f77af0a4fcbb7f8ab142b4d3a7a06c906229290f 100644
--- a/Source/core/dom/DocumentOrderedMap.cpp
+++ b/Source/core/dom/DocumentOrderedMap.cpp
@@ -37,7 +37,6 @@
 #include "core/dom/TreeScope.h"
 #include "core/html/HTMLLabelElement.h"
 #include "core/html/HTMLMapElement.h"
-#include "core/html/HTMLNameCollection.h"
 
 namespace WebCore {
 
@@ -48,11 +47,6 @@ inline bool keyMatchesId(StringImpl* key, Element* element)
     return element->getIdAttribute().impl() == key;
 }
 
-inline bool keyMatchesName(StringImpl* key, Element* element)
-{
-    return element->getNameAttribute().impl() == key;
-}
-
 inline bool keyMatchesMapName(StringImpl* key, Element* element)
 {
     return element->hasTagName(mapTag) && toHTMLMapElement(element)->getName().impl() == key;
@@ -71,6 +65,7 @@ inline bool keyMatchesLabelForAttribute(StringImpl* key, Element* element)
 void DocumentOrderedMap::clear()
 {
     m_map.clear();
+    m_duplicateCounts.clear();
 }
 
 void DocumentOrderedMap::add(StringImpl* key, Element* element)
@@ -78,15 +73,29 @@ void DocumentOrderedMap::add(StringImpl* key, Element* element)
     ASSERT(key);
     ASSERT(element);
 
-    Map::AddResult addResult = m_map.add(key, MapEntry(element));
-    if (addResult.isNewEntry)
-        return;
+    if (!m_duplicateCounts.contains(key)) {
+        // Fast path. The key is not already in m_duplicateCounts, so we assume that it's
+        // also not already in m_map and try to add it. If that add succeeds, we're done.
+        Map::AddResult addResult = m_map.add(key, element);
+        if (addResult.isNewEntry)
+            return;
+
+        // The add failed, so this key was already cached in m_map.
+        // There are multiple elements with this key. Remove the m_map
+        // cache for this key so get searches for it next time it is called.
+        m_map.remove(addResult.iterator);
+        m_duplicateCounts.add(key);
+    } else {
+        // There are multiple elements with this key. Remove the m_map
+        // cache for this key so get will search for it next time it is called.
+        Map::iterator cachedItem = m_map.find(key);
+        if (cachedItem != m_map.end()) {
+            m_map.remove(cachedItem);
+            m_duplicateCounts.add(key);
+        }
+    }
 
-    MapEntry& entry = addResult.iterator->value;
-    ASSERT(entry.count);
-    entry.element = 0;
-    entry.count++;
-    entry.orderedList.clear();
+    m_duplicateCounts.add(key);
 }
 
 void DocumentOrderedMap::remove(StringImpl* key, Element* element)
@@ -94,20 +103,11 @@ void DocumentOrderedMap::remove(StringImpl* key, Element* element)
     ASSERT(key);
     ASSERT(element);
 
-    Map::iterator it = m_map.find(key);
-    ASSERT(it != m_map.end());
-    MapEntry& entry = it->value;
-
-    ASSERT(entry.count);
-    if (entry.count == 1) {
-        ASSERT(!entry.element || entry.element == element);
-        m_map.remove(it);
-    } else {
-        if (entry.element == element)
-            entry.element = 0;
-        entry.count--;
-        entry.orderedList.clear(); // FIXME: Remove the element instead if there are only few items left.
-    }
+    Map::iterator cachedItem = m_map.find(key);
+    if (cachedItem != m_map.end() && cachedItem->value == element)
+        m_map.remove(cachedItem);
+    else
+        m_duplicateCounts.remove(key);
 }
 
 template<bool keyMatches(StringImpl*, Element*)>
@@ -116,23 +116,22 @@ inline Element* DocumentOrderedMap::get(StringImpl* key, const TreeScope* scope)
     ASSERT(key);
     ASSERT(scope);
 
-    Map::iterator it = m_map.find(key);
-    if (it == m_map.end())
-        return 0;
-
-    MapEntry& entry = it->value;
-    ASSERT(entry.count);
-    if (entry.element)
-        return entry.element;
-
-    // We know there's at least one node that matches; iterate to find the first one.
-    for (Element* element = ElementTraversal::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(element)) {
-        if (!keyMatches(key, element))
-            continue;
-        entry.element = element;
+    Element* element = m_map.get(key);
+    if (element)
         return element;
+
+    if (m_duplicateCounts.contains(key)) {
+        // We know there's at least one node that matches; iterate to find the first one.
+        for (element = ElementTraversal::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(element)) {
+            if (!keyMatches(key, element))
+                continue;
+            m_duplicateCounts.remove(key);
+            m_map.set(key, element);
+            return element;
+        }
+        ASSERT_NOT_REACHED();
     }
-    ASSERT_NOT_REACHED();
+
     return 0;
 }
 
@@ -141,11 +140,6 @@ Element* DocumentOrderedMap::getElementById(StringImpl* key, const TreeScope* sc
     return get<keyMatchesId>(key, scope);
 }
 
-Element* DocumentOrderedMap::getElementByName(StringImpl* key, const TreeScope* scope) const
-{
-    return get<keyMatchesName>(key, scope);
-}
-
 Element* DocumentOrderedMap::getElementByMapName(StringImpl* key, const TreeScope* scope) const
 {
     return get<keyMatchesMapName>(key, scope);
@@ -161,31 +155,4 @@ Element* DocumentOrderedMap::getElementByLabelForAttribute(StringImpl* key, cons
     return get<keyMatchesLabelForAttribute>(key, scope);
 }
 
-const Vector<Element*>* DocumentOrderedMap::getAllElementsById(StringImpl* key, const TreeScope* scope) const
-{
-    ASSERT(key);
-    ASSERT(scope);
-
-    Map::iterator it = m_map.find(key);
-    if (it == m_map.end())
-        return 0;
-
-    MapEntry& entry = it->value;
-    ASSERT(entry.count);
-    if (!entry.count)
-        return 0;
-
-    if (entry.orderedList.isEmpty()) {
-        entry.orderedList.reserveCapacity(entry.count);
-        for (Element* element = entry.element ? entry.element : ElementTraversal::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(element)) {
-            if (!keyMatchesId(key, element))
-                continue;
-            entry.orderedList.append(element);
-        }
-        ASSERT(entry.orderedList.size() == entry.count);
-    }
-
-    return &entry.orderedList;
-}
-
 } // namespace WebCore