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

Side by Side 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 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 unified diff | Download patch
OLDNEW
1 /* 1 /*
2 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserv ed. 2 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserv ed.
3 * 3 *
4 * Redistribution and use in source and binary forms, with or without 4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are 5 * modification, are permitted provided that the following conditions are
6 * met: 6 * met:
7 * 7 *
8 * * Redistributions of source code must retain the above copyright 8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer. 9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above 10 * * Redistributions in binary form must reproduce the above
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after
58 } 58 }
59 59
60 inline bool keyMatchesLabelForAttribute(StringImpl* key, Element* element) 60 inline bool keyMatchesLabelForAttribute(StringImpl* key, Element* element)
61 { 61 {
62 return isHTMLLabelElement(element) && element->getAttribute(forAttr).impl() == key; 62 return isHTMLLabelElement(element) && element->getAttribute(forAttr).impl() == key;
63 } 63 }
64 64
65 void DocumentOrderedMap::clear() 65 void DocumentOrderedMap::clear()
66 { 66 {
67 m_map.clear(); 67 m_map.clear();
68 m_duplicateCounts.clear();
69 } 68 }
70 69
71 void DocumentOrderedMap::add(StringImpl* key, Element* element) 70 void DocumentOrderedMap::add(StringImpl* key, Element* element)
72 { 71 {
73 ASSERT(key); 72 ASSERT(key);
74 ASSERT(element); 73 ASSERT(element);
75 74
76 if (!m_duplicateCounts.contains(key)) { 75 Map::AddResult addResult = m_map.add(key, MapEntry(element));
77 // Fast path. The key is not already in m_duplicateCounts, so we assume that it's 76 if (addResult.isNewEntry)
78 // also not already in m_map and try to add it. If that add succeeds, we 're done. 77 return;
79 Map::AddResult addResult = m_map.add(key, element);
80 if (addResult.isNewEntry)
81 return;
82 78
83 // The add failed, so this key was already cached in m_map. 79 MapEntry& entry = addResult.iterator->value;
84 // There are multiple elements with this key. Remove the m_map 80 ASSERT(entry.count);
85 // cache for this key so get searches for it next time it is called. 81 entry.element = 0;
86 m_map.remove(addResult.iterator); 82 entry.count++;
87 m_duplicateCounts.add(key); 83 entry.orderedList.clear();
88 } else {
89 // There are multiple elements with this key. Remove the m_map
90 // cache for this key so get will search for it next time it is called.
91 Map::iterator cachedItem = m_map.find(key);
92 if (cachedItem != m_map.end()) {
93 m_map.remove(cachedItem);
94 m_duplicateCounts.add(key);
95 }
96 }
97
98 m_duplicateCounts.add(key);
99 } 84 }
100 85
101 void DocumentOrderedMap::remove(StringImpl* key, Element* element) 86 void DocumentOrderedMap::remove(StringImpl* key, Element* element)
102 { 87 {
103 ASSERT(key); 88 ASSERT(key);
104 ASSERT(element); 89 ASSERT(element);
105 90
106 Map::iterator cachedItem = m_map.find(key); 91 Map::iterator it = m_map.find(key);
107 if (cachedItem != m_map.end() && cachedItem->value == element) 92 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.
108 m_map.remove(cachedItem); 93 MapEntry& entry = it->value;
109 else 94
110 m_duplicateCounts.remove(key); 95 ASSERT(entry.count);
esprehn 2013/12/02 20:38:04 This doesn't seem right, why will find() always ge
96 if (entry.count == 1) {
97 ASSERT(!entry.element || entry.element == element);
98 m_map.remove(it);
99 } else {
100 if (entry.element == element)
101 entry.element = 0;
Inactive 2013/12/02 21:53:25 Instead of resetting it unconditionally to 0 here,
102 entry.count--;
103 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.
104 }
111 } 105 }
112 106
113 template<bool keyMatches(StringImpl*, Element*)> 107 template<bool keyMatches(StringImpl*, Element*)>
114 inline Element* DocumentOrderedMap::get(StringImpl* key, const TreeScope* scope) const 108 inline Element* DocumentOrderedMap::get(StringImpl* key, const TreeScope* scope) const
115 { 109 {
116 ASSERT(key); 110 ASSERT(key);
117 ASSERT(scope); 111 ASSERT(scope);
118 112
119 Element* element = m_map.get(key); 113 Map::iterator it = m_map.find(key);
120 if (element) 114 if (it == m_map.end())
115 return 0;
116
117 MapEntry& entry = it->value;
118 ASSERT(entry.count);
119 if (entry.element)
120 return entry.element;
121
122 // We know there's at least one node that matches; iterate to find the first one.
123 for (Element* element = ElementTraversal::firstWithin(*scope->rootNode()); e lement; element = ElementTraversal::next(*element)) {
124 if (!keyMatches(key, element))
125 continue;
126 entry.element = element;
121 return element; 127 return element;
122
123 if (m_duplicateCounts.contains(key)) {
124 // We know there's at least one node that matches; iterate to find the f irst one.
125 ASSERT(scope->rootNode());
126 for (element = ElementTraversal::firstWithin(*scope->rootNode()); elemen t; element = ElementTraversal::next(*element)) {
127 if (!keyMatches(key, element))
128 continue;
129 m_duplicateCounts.remove(key);
130 m_map.set(key, element);
131 return element;
132 }
133 ASSERT_NOT_REACHED();
134 } 128 }
135 129 ASSERT_NOT_REACHED();
136 return 0; 130 return 0;
137 } 131 }
138 132
139 Element* DocumentOrderedMap::getElementById(StringImpl* key, const TreeScope* sc ope) const 133 Element* DocumentOrderedMap::getElementById(StringImpl* key, const TreeScope* sc ope) const
140 { 134 {
141 return get<keyMatchesId>(key, scope); 135 return get<keyMatchesId>(key, scope);
142 } 136 }
143 137
138 const Vector<Element*>* DocumentOrderedMap::getAllElementsById(StringImpl* key, const TreeScope* scope) const
139 {
140 ASSERT(key);
141 ASSERT(scope);
142
143 Map::iterator it = m_map.find(key);
144 if (it == m_map.end())
145 return 0;
146
147 MapEntry& entry = it->value;
148 ASSERT(entry.count);
149
150 if (entry.orderedList.isEmpty()) {
151 entry.orderedList.reserveCapacity(entry.count);
152 for (Element* element = entry.element ? entry.element : ElementTraversal ::firstWithin(*scope->rootNode()); element; element = ElementTraversal::next(*el ement)) {
Inactive 2013/12/02 21:53:25 As loop condition, I now use "entry.orderedList.si
153 if (!keyMatchesId(key, element))
154 continue;
155 entry.orderedList.append(element);
156 }
157 ASSERT(entry.orderedList.size() == entry.count);
158 }
159
160 return &entry.orderedList;
161 }
162
144 Element* DocumentOrderedMap::getElementByMapName(StringImpl* key, const TreeScop e* scope) const 163 Element* DocumentOrderedMap::getElementByMapName(StringImpl* key, const TreeScop e* scope) const
145 { 164 {
146 return get<keyMatchesMapName>(key, scope); 165 return get<keyMatchesMapName>(key, scope);
147 } 166 }
148 167
149 Element* DocumentOrderedMap::getElementByLowercasedMapName(StringImpl* key, cons t TreeScope* scope) const 168 Element* DocumentOrderedMap::getElementByLowercasedMapName(StringImpl* key, cons t TreeScope* scope) const
150 { 169 {
151 return get<keyMatchesLowercasedMapName>(key, scope); 170 return get<keyMatchesLowercasedMapName>(key, scope);
152 } 171 }
153 172
154 Element* DocumentOrderedMap::getElementByLabelForAttribute(StringImpl* key, cons t TreeScope* scope) const 173 Element* DocumentOrderedMap::getElementByLabelForAttribute(StringImpl* key, cons t TreeScope* scope) const
155 { 174 {
156 return get<keyMatchesLabelForAttribute>(key, scope); 175 return get<keyMatchesLabelForAttribute>(key, scope);
157 } 176 }
158 177
159 } // namespace WebCore 178 } // namespace WebCore
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698