Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(707)

Unified Diff: Source/core/dom/DocumentOrderedMap.cpp

Issue 92083002: Add fast path for tag#id selector queries (Closed) Base URL: https://chromium.googlesource.com/chromium/blink.git@master
Patch Set: Created 7 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
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);

Powered by Google App Engine
This is Rietveld 408576698