OLD | NEW |
---|---|
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 Loading... | |
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 |
OLD | NEW |