OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2010 Google, Inc. All Rights Reserved. | 2 * Copyright (C) 2010 Google, Inc. All Rights Reserved. |
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 | 5 * modification, are permitted provided that the following conditions |
6 * are met: | 6 * are met: |
7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
(...skipping 14 matching lines...) Expand all Loading... |
25 | 25 |
26 #include "core/html/parser/HTMLFormattingElementList.h" | 26 #include "core/html/parser/HTMLFormattingElementList.h" |
27 | 27 |
28 #ifndef NDEBUG | 28 #ifndef NDEBUG |
29 #include <stdio.h> | 29 #include <stdio.h> |
30 #endif | 30 #endif |
31 | 31 |
32 namespace blink { | 32 namespace blink { |
33 | 33 |
34 // Biblically, Noah's Ark only had room for two of each animal, but in the | 34 // Biblically, Noah's Ark only had room for two of each animal, but in the |
35 // Book of Hixie (aka http://www.whatwg.org/specs/web-apps/current-work/multipag
e/parsing.html#list-of-active-formatting-elements), | 35 // Book of Hixie (aka |
| 36 // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#list
-of-active-formatting-elements), |
36 // Noah's Ark of Formatting Elements can fit three of each element. | 37 // Noah's Ark of Formatting Elements can fit three of each element. |
37 static const size_t kNoahsArkCapacity = 3; | 38 static const size_t kNoahsArkCapacity = 3; |
38 | 39 |
39 HTMLFormattingElementList::HTMLFormattingElementList() {} | 40 HTMLFormattingElementList::HTMLFormattingElementList() {} |
40 | 41 |
41 HTMLFormattingElementList::~HTMLFormattingElementList() {} | 42 HTMLFormattingElementList::~HTMLFormattingElementList() {} |
42 | 43 |
43 Element* HTMLFormattingElementList::closestElementInScopeWithName( | 44 Element* HTMLFormattingElementList::closestElementInScopeWithName( |
44 const AtomicString& targetName) { | 45 const AtomicString& targetName) { |
45 for (unsigned i = 1; i <= m_entries.size(); ++i) { | 46 for (unsigned i = 1; i <= m_entries.size(); ++i) { |
(...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
115 } | 116 } |
116 | 117 |
117 void HTMLFormattingElementList::tryToEnsureNoahsArkConditionQuickly( | 118 void HTMLFormattingElementList::tryToEnsureNoahsArkConditionQuickly( |
118 HTMLStackItem* newItem, | 119 HTMLStackItem* newItem, |
119 HeapVector<Member<HTMLStackItem>>& remainingCandidates) { | 120 HeapVector<Member<HTMLStackItem>>& remainingCandidates) { |
120 ASSERT(remainingCandidates.isEmpty()); | 121 ASSERT(remainingCandidates.isEmpty()); |
121 | 122 |
122 if (m_entries.size() < kNoahsArkCapacity) | 123 if (m_entries.size() < kNoahsArkCapacity) |
123 return; | 124 return; |
124 | 125 |
125 // Use a vector with inline capacity to avoid a malloc in the common case | 126 // Use a vector with inline capacity to avoid a malloc in the common case of a |
126 // of a quickly ensuring the condition. | 127 // quickly ensuring the condition. |
127 HeapVector<Member<HTMLStackItem>, 10> candidates; | 128 HeapVector<Member<HTMLStackItem>, 10> candidates; |
128 | 129 |
129 size_t newItemAttributeCount = newItem->attributes().size(); | 130 size_t newItemAttributeCount = newItem->attributes().size(); |
130 | 131 |
131 for (size_t i = m_entries.size(); i;) { | 132 for (size_t i = m_entries.size(); i;) { |
132 --i; | 133 --i; |
133 Entry& entry = m_entries[i]; | 134 Entry& entry = m_entries[i]; |
134 if (entry.isMarker()) | 135 if (entry.isMarker()) |
135 break; | 136 break; |
136 | 137 |
137 // Quickly reject obviously non-matching candidates. | 138 // Quickly reject obviously non-matching candidates. |
138 HTMLStackItem* candidate = entry.stackItem(); | 139 HTMLStackItem* candidate = entry.stackItem(); |
139 if (newItem->localName() != candidate->localName() || | 140 if (newItem->localName() != candidate->localName() || |
140 newItem->namespaceURI() != candidate->namespaceURI()) | 141 newItem->namespaceURI() != candidate->namespaceURI()) |
141 continue; | 142 continue; |
142 if (candidate->attributes().size() != newItemAttributeCount) | 143 if (candidate->attributes().size() != newItemAttributeCount) |
143 continue; | 144 continue; |
144 | 145 |
145 candidates.append(candidate); | 146 candidates.append(candidate); |
146 } | 147 } |
147 | 148 |
| 149 // There's room for the new element in the ark. There's no need to copy out |
| 150 // the remainingCandidates. |
148 if (candidates.size() < kNoahsArkCapacity) | 151 if (candidates.size() < kNoahsArkCapacity) |
149 return; // There's room for the new element in the ark. There's no need to
copy out the remainingCandidates. | 152 return; |
150 | 153 |
151 remainingCandidates.appendVector(candidates); | 154 remainingCandidates.appendVector(candidates); |
152 } | 155 } |
153 | 156 |
154 void HTMLFormattingElementList::ensureNoahsArkCondition( | 157 void HTMLFormattingElementList::ensureNoahsArkCondition( |
155 HTMLStackItem* newItem) { | 158 HTMLStackItem* newItem) { |
156 HeapVector<Member<HTMLStackItem>> candidates; | 159 HeapVector<Member<HTMLStackItem>> candidates; |
157 tryToEnsureNoahsArkConditionQuickly(newItem, candidates); | 160 tryToEnsureNoahsArkConditionQuickly(newItem, candidates); |
158 if (candidates.isEmpty()) | 161 if (candidates.isEmpty()) |
159 return; | 162 return; |
160 | 163 |
161 // We pre-allocate and re-use this second vector to save one malloc per | 164 // We pre-allocate and re-use this second vector to save one malloc per |
162 // attribute that we verify. | 165 // attribute that we verify. |
163 HeapVector<Member<HTMLStackItem>> remainingCandidates; | 166 HeapVector<Member<HTMLStackItem>> remainingCandidates; |
164 remainingCandidates.reserveInitialCapacity(candidates.size()); | 167 remainingCandidates.reserveInitialCapacity(candidates.size()); |
165 | 168 |
166 const Vector<Attribute>& attributes = newItem->attributes(); | 169 const Vector<Attribute>& attributes = newItem->attributes(); |
167 for (size_t i = 0; i < attributes.size(); ++i) { | 170 for (size_t i = 0; i < attributes.size(); ++i) { |
168 const Attribute& attribute = attributes[i]; | 171 const Attribute& attribute = attributes[i]; |
169 | 172 |
170 for (size_t j = 0; j < candidates.size(); ++j) { | 173 for (size_t j = 0; j < candidates.size(); ++j) { |
171 HTMLStackItem* candidate = candidates[j]; | 174 HTMLStackItem* candidate = candidates[j]; |
172 | 175 |
173 // These properties should already have been checked by tryToEnsureNoahsAr
kConditionQuickly. | 176 // These properties should already have been checked by |
| 177 // tryToEnsureNoahsArkConditionQuickly. |
174 ASSERT(newItem->attributes().size() == candidate->attributes().size()); | 178 ASSERT(newItem->attributes().size() == candidate->attributes().size()); |
175 ASSERT(newItem->localName() == candidate->localName() && | 179 ASSERT(newItem->localName() == candidate->localName() && |
176 newItem->namespaceURI() == candidate->namespaceURI()); | 180 newItem->namespaceURI() == candidate->namespaceURI()); |
177 | 181 |
178 Attribute* candidateAttribute = | 182 Attribute* candidateAttribute = |
179 candidate->getAttributeItem(attribute.name()); | 183 candidate->getAttributeItem(attribute.name()); |
180 if (candidateAttribute && | 184 if (candidateAttribute && |
181 candidateAttribute->value() == attribute.value()) | 185 candidateAttribute->value() == attribute.value()) |
182 remainingCandidates.append(candidate); | 186 remainingCandidates.append(candidate); |
183 } | 187 } |
(...skipping 20 matching lines...) Expand all Loading... |
204 if (entry.isMarker()) | 208 if (entry.isMarker()) |
205 LOG(INFO) << "marker"; | 209 LOG(INFO) << "marker"; |
206 else | 210 else |
207 LOG(INFO) << *entry.element(); | 211 LOG(INFO) << *entry.element(); |
208 } | 212 } |
209 } | 213 } |
210 | 214 |
211 #endif | 215 #endif |
212 | 216 |
213 } // namespace blink | 217 } // namespace blink |
OLD | NEW |