| OLD | NEW |
| 1 // Copyright 2015 The Chromium Authors. All rights reserved. | 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "core/dom/NthIndexCache.h" | 5 #include "core/dom/NthIndexCache.h" |
| 6 | 6 |
| 7 #include "core/dom/Document.h" | 7 #include "core/dom/Document.h" |
| 8 #include "core/dom/ElementTraversal.h" | 8 #include "core/dom/ElementTraversal.h" |
| 9 | 9 |
| 10 namespace blink { | 10 namespace blink { |
| (...skipping 137 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 148 nthIndexCache->cacheNthOfTypeIndexDataForParent(element); | 148 nthIndexCache->cacheNthOfTypeIndexDataForParent(element); |
| 149 return index; | 149 return index; |
| 150 } | 150 } |
| 151 | 151 |
| 152 void NthIndexCache::cacheNthIndexDataForParent(Element& element) { | 152 void NthIndexCache::cacheNthIndexDataForParent(Element& element) { |
| 153 DCHECK(element.parentNode()); | 153 DCHECK(element.parentNode()); |
| 154 if (!m_parentMap) | 154 if (!m_parentMap) |
| 155 m_parentMap = new ParentMap(); | 155 m_parentMap = new ParentMap(); |
| 156 | 156 |
| 157 ParentMap::AddResult addResult = | 157 ParentMap::AddResult addResult = |
| 158 m_parentMap->add(element.parentNode(), nullptr); | 158 m_parentMap->insert(element.parentNode(), nullptr); |
| 159 DCHECK(addResult.isNewEntry); | 159 DCHECK(addResult.isNewEntry); |
| 160 addResult.storedValue->value = new NthIndexData(*element.parentNode()); | 160 addResult.storedValue->value = new NthIndexData(*element.parentNode()); |
| 161 } | 161 } |
| 162 | 162 |
| 163 NthIndexCache::IndexByType& NthIndexCache::ensureTypeIndexMap( | 163 NthIndexCache::IndexByType& NthIndexCache::ensureTypeIndexMap( |
| 164 ContainerNode& parent) { | 164 ContainerNode& parent) { |
| 165 if (!m_parentMapForType) | 165 if (!m_parentMapForType) |
| 166 m_parentMapForType = new ParentMapForType(); | 166 m_parentMapForType = new ParentMapForType(); |
| 167 | 167 |
| 168 ParentMapForType::AddResult addResult = | 168 ParentMapForType::AddResult addResult = |
| 169 m_parentMapForType->add(&parent, nullptr); | 169 m_parentMapForType->insert(&parent, nullptr); |
| 170 if (addResult.isNewEntry) | 170 if (addResult.isNewEntry) |
| 171 addResult.storedValue->value = new IndexByType(); | 171 addResult.storedValue->value = new IndexByType(); |
| 172 | 172 |
| 173 DCHECK(addResult.storedValue->value); | 173 DCHECK(addResult.storedValue->value); |
| 174 return *addResult.storedValue->value; | 174 return *addResult.storedValue->value; |
| 175 } | 175 } |
| 176 | 176 |
| 177 void NthIndexCache::cacheNthOfTypeIndexDataForParent(Element& element) { | 177 void NthIndexCache::cacheNthOfTypeIndexDataForParent(Element& element) { |
| 178 DCHECK(element.parentNode()); | 178 DCHECK(element.parentNode()); |
| 179 IndexByType::AddResult addResult = | 179 IndexByType::AddResult addResult = ensureTypeIndexMap(*element.parentNode()) |
| 180 ensureTypeIndexMap(*element.parentNode()).add(element.tagName(), nullptr); | 180 .insert(element.tagName(), nullptr); |
| 181 DCHECK(addResult.isNewEntry); | 181 DCHECK(addResult.isNewEntry); |
| 182 addResult.storedValue->value = | 182 addResult.storedValue->value = |
| 183 new NthIndexData(*element.parentNode(), element.tagQName()); | 183 new NthIndexData(*element.parentNode(), element.tagQName()); |
| 184 } | 184 } |
| 185 | 185 |
| 186 unsigned NthIndexData::nthIndex(Element& element) const { | 186 unsigned NthIndexData::nthIndex(Element& element) const { |
| 187 DCHECK(!element.isPseudoElement()); | 187 DCHECK(!element.isPseudoElement()); |
| 188 | 188 |
| 189 unsigned index = 0; | 189 unsigned index = 0; |
| 190 for (Element *sibling = &element; sibling; | 190 for (Element *sibling = &element; sibling; |
| (...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 223 // The frequency at which we cache the nth-index for a set of siblings. A | 223 // The frequency at which we cache the nth-index for a set of siblings. A |
| 224 // spread value of 3 means every third Element will have its nth-index cached. | 224 // spread value of 3 means every third Element will have its nth-index cached. |
| 225 // Using a spread value > 1 is done to save memory. Looking up the nth-index | 225 // Using a spread value > 1 is done to save memory. Looking up the nth-index |
| 226 // will still be done in constant time in terms of sibling count, at most | 226 // will still be done in constant time in terms of sibling count, at most |
| 227 // 'spread' elements will be traversed. | 227 // 'spread' elements will be traversed. |
| 228 const unsigned spread = 3; | 228 const unsigned spread = 3; |
| 229 unsigned count = 0; | 229 unsigned count = 0; |
| 230 for (Element* sibling = ElementTraversal::firstChild(parent); sibling; | 230 for (Element* sibling = ElementTraversal::firstChild(parent); sibling; |
| 231 sibling = ElementTraversal::nextSibling(*sibling)) { | 231 sibling = ElementTraversal::nextSibling(*sibling)) { |
| 232 if (!(++count % spread)) | 232 if (!(++count % spread)) |
| 233 m_elementIndexMap.add(sibling, count); | 233 m_elementIndexMap.insert(sibling, count); |
| 234 } | 234 } |
| 235 DCHECK(count); | 235 DCHECK(count); |
| 236 m_count = count; | 236 m_count = count; |
| 237 } | 237 } |
| 238 | 238 |
| 239 NthIndexData::NthIndexData(ContainerNode& parent, const QualifiedName& type) { | 239 NthIndexData::NthIndexData(ContainerNode& parent, const QualifiedName& type) { |
| 240 // The frequency at which we cache the nth-index of type for a set of | 240 // The frequency at which we cache the nth-index of type for a set of |
| 241 // siblings. A spread value of 3 means every third Element of its type will | 241 // siblings. A spread value of 3 means every third Element of its type will |
| 242 // have its nth-index cached. Using a spread value > 1 is done to save | 242 // have its nth-index cached. Using a spread value > 1 is done to save |
| 243 // memory. Looking up the nth-index of its type will still be done in less | 243 // memory. Looking up the nth-index of its type will still be done in less |
| 244 // time, as most number of elements traversed will be equal to find 'spread' | 244 // time, as most number of elements traversed will be equal to find 'spread' |
| 245 // elements in the sibling set. | 245 // elements in the sibling set. |
| 246 const unsigned spread = 3; | 246 const unsigned spread = 3; |
| 247 unsigned count = 0; | 247 unsigned count = 0; |
| 248 for (Element* sibling = | 248 for (Element* sibling = |
| 249 ElementTraversal::firstChild(parent, HasTagName(type)); | 249 ElementTraversal::firstChild(parent, HasTagName(type)); |
| 250 sibling; | 250 sibling; |
| 251 sibling = ElementTraversal::nextSibling(*sibling, HasTagName(type))) { | 251 sibling = ElementTraversal::nextSibling(*sibling, HasTagName(type))) { |
| 252 if (!(++count % spread)) | 252 if (!(++count % spread)) |
| 253 m_elementIndexMap.add(sibling, count); | 253 m_elementIndexMap.insert(sibling, count); |
| 254 } | 254 } |
| 255 DCHECK(count); | 255 DCHECK(count); |
| 256 m_count = count; | 256 m_count = count; |
| 257 } | 257 } |
| 258 | 258 |
| 259 DEFINE_TRACE(NthIndexData) { | 259 DEFINE_TRACE(NthIndexData) { |
| 260 visitor->trace(m_elementIndexMap); | 260 visitor->trace(m_elementIndexMap); |
| 261 } | 261 } |
| 262 | 262 |
| 263 } // namespace blink | 263 } // namespace blink |
| OLD | NEW |