Index: Source/core/dom/DocumentOrderedMap.cpp |
diff --git a/Source/core/dom/DocumentOrderedMap.cpp b/Source/core/dom/DocumentOrderedMap.cpp |
index 494d266768f241b113a78fb0a0392cc89a72707b..b5f8fcfe95c145c5fca7313ce935558b1d8960f1 100644 |
--- a/Source/core/dom/DocumentOrderedMap.cpp |
+++ b/Source/core/dom/DocumentOrderedMap.cpp |
@@ -65,7 +65,6 @@ inline bool keyMatchesLabelForAttribute(StringImpl* key, Element* element) |
void DocumentOrderedMap::clear() |
{ |
m_map.clear(); |
- m_duplicateCounts.clear(); |
} |
void DocumentOrderedMap::add(StringImpl* key, Element* element) |
@@ -73,29 +72,15 @@ void DocumentOrderedMap::add(StringImpl* key, Element* element) |
ASSERT(key); |
ASSERT(element); |
- 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); |
- } |
- } |
+ Map::AddResult addResult = m_map.add(key, MapEntry(element)); |
+ if (addResult.isNewEntry) |
+ return; |
- m_duplicateCounts.add(key); |
+ MapEntry& entry = addResult.iterator->value; |
+ ASSERT(entry.count); |
+ entry.element = 0; |
+ entry.count++; |
+ entry.orderedList.clear(); |
} |
void DocumentOrderedMap::remove(StringImpl* key, Element* element) |
@@ -103,11 +88,20 @@ void DocumentOrderedMap::remove(StringImpl* key, Element* element) |
ASSERT(key); |
ASSERT(element); |
- Map::iterator cachedItem = m_map.find(key); |
- if (cachedItem != m_map.end() && cachedItem->value == element) |
- m_map.remove(cachedItem); |
- else |
- m_duplicateCounts.remove(key); |
+ Map::iterator it = m_map.find(key); |
+ ASSERT(it != m_map.end()); |
esprehn
2013/12/02 20:38:04
The old code definitely didn't ASSERT this, why is
Inactive
2013/12/02 20:47:26
This believe this is actually what caused the Clus
Inactive
2013/12/02 21:24:42
Yes, I confirmed this is indeed the source of the
Inactive
2013/12/02 21:53:25
Done.
|
+ MapEntry& entry = it->value; |
+ |
+ ASSERT(entry.count); |
esprehn
2013/12/02 20:38:04
This doesn't seem right, why will find() always ge
|
+ if (entry.count == 1) { |
+ ASSERT(!entry.element || entry.element == element); |
+ m_map.remove(it); |
+ } else { |
+ if (entry.element == element) |
+ entry.element = 0; |
Inactive
2013/12/02 21:53:25
Instead of resetting it unconditionally to 0 here,
|
+ entry.count--; |
+ entry.orderedList.clear(); // FIXME: Remove the element instead if there are only few items left. |
esprehn
2013/12/02 20:38:04
a few?
Inactive
2013/12/02 21:24:42
I believe the idea on WebKit side was that it may
Inactive
2013/12/02 21:53:25
Done.
|
+ } |
} |
template<bool keyMatches(StringImpl*, Element*)> |
@@ -116,23 +110,23 @@ inline Element* DocumentOrderedMap::get(StringImpl* key, const TreeScope* scope) |
ASSERT(key); |
ASSERT(scope); |
- Element* element = m_map.get(key); |
- if (element) |
- return element; |
+ Map::iterator it = m_map.find(key); |
+ if (it == m_map.end()) |
+ return 0; |
- if (m_duplicateCounts.contains(key)) { |
- // We know there's at least one node that matches; iterate to find the first one. |
- ASSERT(scope->rootNode()); |
- 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(); |
- } |
+ 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; |
+ return element; |
+ } |
+ ASSERT_NOT_REACHED(); |
return 0; |
} |
@@ -141,6 +135,31 @@ Element* DocumentOrderedMap::getElementById(StringImpl* key, const TreeScope* sc |
return get<keyMatchesId>(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.orderedList.isEmpty()) { |
+ entry.orderedList.reserveCapacity(entry.count); |
+ for (Element* element = entry.element ? entry.element : ElementTraversal::firstWithin(*scope->rootNode()); element; element = ElementTraversal::next(*element)) { |
Inactive
2013/12/02 21:53:25
As loop condition, I now use "entry.orderedList.si
|
+ if (!keyMatchesId(key, element)) |
+ continue; |
+ entry.orderedList.append(element); |
+ } |
+ ASSERT(entry.orderedList.size() == entry.count); |
+ } |
+ |
+ return &entry.orderedList; |
+} |
+ |
Element* DocumentOrderedMap::getElementByMapName(StringImpl* key, const TreeScope* scope) const |
{ |
return get<keyMatchesMapName>(key, scope); |