| 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 { |
| 11 | 11 |
| 12 NthIndexCache::NthIndexCache(Document& document) | 12 NthIndexCache::NthIndexCache(Document& document) |
| 13 : m_document(&document) | 13 : m_document(&document) |
| 14 #if ENABLE(ASSERT) | 14 #if DCHECK_IS_ON() |
| 15 , m_domTreeVersion(document.domTreeVersion()) | 15 , m_domTreeVersion(document.domTreeVersion()) |
| 16 #endif | 16 #endif |
| 17 { | 17 { |
| 18 document.setNthIndexCache(this); | 18 document.setNthIndexCache(this); |
| 19 } | 19 } |
| 20 | 20 |
| 21 NthIndexCache::~NthIndexCache() | 21 NthIndexCache::~NthIndexCache() |
| 22 { | 22 { |
| 23 ASSERT(m_domTreeVersion == m_document->domTreeVersion()); | 23 #if DCHECK_IS_ON() |
| 24 DCHECK_EQ(m_domTreeVersion, m_document->domTreeVersion()); |
| 25 #endif |
| 24 m_document->setNthIndexCache(nullptr); | 26 m_document->setNthIndexCache(nullptr); |
| 25 } | 27 } |
| 26 | 28 |
| 27 namespace { | 29 namespace { |
| 28 | 30 |
| 29 // Generating the cached nth-index counts when the number of children | 31 // Generating the cached nth-index counts when the number of children |
| 30 // exceeds this count. This number is picked based on testing | 32 // exceeds this count. This number is picked based on testing |
| 31 // querySelectorAll for :nth-child(3n+2) and :nth-of-type(3n+2) on an | 33 // querySelectorAll for :nth-child(3n+2) and :nth-of-type(3n+2) on an |
| 32 // increasing number of children. | 34 // increasing number of children. |
| 33 | 35 |
| (...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 73 } | 75 } |
| 74 return index; | 76 return index; |
| 75 } | 77 } |
| 76 | 78 |
| 77 } // namespace | 79 } // namespace |
| 78 | 80 |
| 79 unsigned NthIndexCache::nthChildIndex(Element& element) | 81 unsigned NthIndexCache::nthChildIndex(Element& element) |
| 80 { | 82 { |
| 81 if (element.isPseudoElement()) | 83 if (element.isPseudoElement()) |
| 82 return 1; | 84 return 1; |
| 83 ASSERT(element.parentNode()); | 85 DCHECK(element.parentNode()); |
| 84 NthIndexCache* nthIndexCache = element.document().nthIndexCache(); | 86 NthIndexCache* nthIndexCache = element.document().nthIndexCache(); |
| 85 NthIndexData* nthIndexData = nullptr; | 87 NthIndexData* nthIndexData = nullptr; |
| 86 if (nthIndexCache && nthIndexCache->m_parentMap) | 88 if (nthIndexCache && nthIndexCache->m_parentMap) |
| 87 nthIndexData = nthIndexCache->m_parentMap->get(element.parentNode()); | 89 nthIndexData = nthIndexCache->m_parentMap->get(element.parentNode()); |
| 88 if (nthIndexData) | 90 if (nthIndexData) |
| 89 return nthIndexData->nthIndex(element); | 91 return nthIndexData->nthIndex(element); |
| 90 unsigned index = uncachedNthChildIndex(element); | 92 unsigned index = uncachedNthChildIndex(element); |
| 91 if (nthIndexCache && index > kCachedSiblingCountLimit) | 93 if (nthIndexCache && index > kCachedSiblingCountLimit) |
| 92 nthIndexCache->cacheNthIndexDataForParent(element); | 94 nthIndexCache->cacheNthIndexDataForParent(element); |
| 93 return index; | 95 return index; |
| 94 } | 96 } |
| 95 | 97 |
| 96 unsigned NthIndexCache::nthLastChildIndex(Element& element) | 98 unsigned NthIndexCache::nthLastChildIndex(Element& element) |
| 97 { | 99 { |
| 98 if (element.isPseudoElement()) | 100 if (element.isPseudoElement()) |
| 99 return 1; | 101 return 1; |
| 100 ASSERT(element.parentNode()); | 102 DCHECK(element.parentNode()); |
| 101 NthIndexCache* nthIndexCache = element.document().nthIndexCache(); | 103 NthIndexCache* nthIndexCache = element.document().nthIndexCache(); |
| 102 NthIndexData* nthIndexData = nullptr; | 104 NthIndexData* nthIndexData = nullptr; |
| 103 if (nthIndexCache && nthIndexCache->m_parentMap) | 105 if (nthIndexCache && nthIndexCache->m_parentMap) |
| 104 nthIndexData = nthIndexCache->m_parentMap->get(element.parentNode()); | 106 nthIndexData = nthIndexCache->m_parentMap->get(element.parentNode()); |
| 105 if (nthIndexData) | 107 if (nthIndexData) |
| 106 return nthIndexData->nthLastIndex(element); | 108 return nthIndexData->nthLastIndex(element); |
| 107 unsigned index = uncachedNthLastChildIndex(element); | 109 unsigned index = uncachedNthLastChildIndex(element); |
| 108 if (nthIndexCache && index > kCachedSiblingCountLimit) | 110 if (nthIndexCache && index > kCachedSiblingCountLimit) |
| 109 nthIndexCache->cacheNthIndexDataForParent(element); | 111 nthIndexCache->cacheNthIndexDataForParent(element); |
| 110 return index; | 112 return index; |
| 111 } | 113 } |
| 112 | 114 |
| 113 NthIndexData* NthIndexCache::nthTypeIndexDataForParent(Element& element) const | 115 NthIndexData* NthIndexCache::nthTypeIndexDataForParent(Element& element) const |
| 114 { | 116 { |
| 115 ASSERT(element.parentNode()); | 117 DCHECK(element.parentNode()); |
| 116 if (!m_parentMapForType) | 118 if (!m_parentMapForType) |
| 117 return nullptr; | 119 return nullptr; |
| 118 if (const IndexByType* map = m_parentMapForType->get(element.parentNode())) | 120 if (const IndexByType* map = m_parentMapForType->get(element.parentNode())) |
| 119 return map->get(element.tagName()); | 121 return map->get(element.tagName()); |
| 120 return nullptr; | 122 return nullptr; |
| 121 } | 123 } |
| 122 | 124 |
| 123 unsigned NthIndexCache::nthOfTypeIndex(Element& element) | 125 unsigned NthIndexCache::nthOfTypeIndex(Element& element) |
| 124 { | 126 { |
| 125 if (element.isPseudoElement()) | 127 if (element.isPseudoElement()) |
| (...skipping 21 matching lines...) Expand all Loading... |
| 147 } | 149 } |
| 148 unsigned siblingCount = 0; | 150 unsigned siblingCount = 0; |
| 149 unsigned index = uncachedNthLastOfTypeIndex(element, siblingCount); | 151 unsigned index = uncachedNthLastOfTypeIndex(element, siblingCount); |
| 150 if (nthIndexCache && siblingCount > kCachedSiblingCountLimit) | 152 if (nthIndexCache && siblingCount > kCachedSiblingCountLimit) |
| 151 nthIndexCache->cacheNthOfTypeIndexDataForParent(element); | 153 nthIndexCache->cacheNthOfTypeIndexDataForParent(element); |
| 152 return index; | 154 return index; |
| 153 } | 155 } |
| 154 | 156 |
| 155 void NthIndexCache::cacheNthIndexDataForParent(Element& element) | 157 void NthIndexCache::cacheNthIndexDataForParent(Element& element) |
| 156 { | 158 { |
| 157 ASSERT(element.parentNode()); | 159 DCHECK(element.parentNode()); |
| 158 if (!m_parentMap) | 160 if (!m_parentMap) |
| 159 m_parentMap = new ParentMap(); | 161 m_parentMap = new ParentMap(); |
| 160 | 162 |
| 161 ParentMap::AddResult addResult = m_parentMap->add(element.parentNode(), null
ptr); | 163 ParentMap::AddResult addResult = m_parentMap->add(element.parentNode(), null
ptr); |
| 162 ASSERT(addResult.isNewEntry); | 164 DCHECK(addResult.isNewEntry); |
| 163 addResult.storedValue->value = new NthIndexData(*element.parentNode()); | 165 addResult.storedValue->value = new NthIndexData(*element.parentNode()); |
| 164 } | 166 } |
| 165 | 167 |
| 166 NthIndexCache::IndexByType& NthIndexCache::ensureTypeIndexMap(ContainerNode& par
ent) | 168 NthIndexCache::IndexByType& NthIndexCache::ensureTypeIndexMap(ContainerNode& par
ent) |
| 167 { | 169 { |
| 168 if (!m_parentMapForType) | 170 if (!m_parentMapForType) |
| 169 m_parentMapForType = new ParentMapForType(); | 171 m_parentMapForType = new ParentMapForType(); |
| 170 | 172 |
| 171 ParentMapForType::AddResult addResult = m_parentMapForType->add(&parent, nul
lptr); | 173 ParentMapForType::AddResult addResult = m_parentMapForType->add(&parent, nul
lptr); |
| 172 if (addResult.isNewEntry) | 174 if (addResult.isNewEntry) |
| 173 addResult.storedValue->value = new IndexByType(); | 175 addResult.storedValue->value = new IndexByType(); |
| 174 | 176 |
| 175 ASSERT(addResult.storedValue->value); | 177 DCHECK(addResult.storedValue->value); |
| 176 return *addResult.storedValue->value; | 178 return *addResult.storedValue->value; |
| 177 } | 179 } |
| 178 | 180 |
| 179 void NthIndexCache::cacheNthOfTypeIndexDataForParent(Element& element) | 181 void NthIndexCache::cacheNthOfTypeIndexDataForParent(Element& element) |
| 180 { | 182 { |
| 181 ASSERT(element.parentNode()); | 183 DCHECK(element.parentNode()); |
| 182 IndexByType::AddResult addResult = ensureTypeIndexMap(*element.parentNode())
.add(element.tagName(), nullptr); | 184 IndexByType::AddResult addResult = ensureTypeIndexMap(*element.parentNode())
.add(element.tagName(), nullptr); |
| 183 ASSERT(addResult.isNewEntry); | 185 DCHECK(addResult.isNewEntry); |
| 184 addResult.storedValue->value = new NthIndexData(*element.parentNode(), eleme
nt.tagQName()); | 186 addResult.storedValue->value = new NthIndexData(*element.parentNode(), eleme
nt.tagQName()); |
| 185 } | 187 } |
| 186 | 188 |
| 187 unsigned NthIndexData::nthIndex(Element& element) const | 189 unsigned NthIndexData::nthIndex(Element& element) const |
| 188 { | 190 { |
| 189 ASSERT(!element.isPseudoElement()); | 191 DCHECK(!element.isPseudoElement()); |
| 190 | 192 |
| 191 unsigned index = 0; | 193 unsigned index = 0; |
| 192 for (Element* sibling = &element; sibling; sibling = ElementTraversal::previ
ousSibling(*sibling), index++) { | 194 for (Element* sibling = &element; sibling; sibling = ElementTraversal::previ
ousSibling(*sibling), index++) { |
| 193 auto it = m_elementIndexMap.find(sibling); | 195 auto it = m_elementIndexMap.find(sibling); |
| 194 if (it != m_elementIndexMap.end()) | 196 if (it != m_elementIndexMap.end()) |
| 195 return it->value + index; | 197 return it->value + index; |
| 196 } | 198 } |
| 197 return index; | 199 return index; |
| 198 } | 200 } |
| 199 | 201 |
| 200 unsigned NthIndexData::nthOfTypeIndex(Element& element) const | 202 unsigned NthIndexData::nthOfTypeIndex(Element& element) const |
| 201 { | 203 { |
| 202 ASSERT(!element.isPseudoElement()); | 204 DCHECK(!element.isPseudoElement()); |
| 203 | 205 |
| 204 unsigned index = 0; | 206 unsigned index = 0; |
| 205 for (Element* sibling = &element; sibling; sibling = ElementTraversal::previ
ousSibling(*sibling, HasTagName(element.tagQName())), index++) { | 207 for (Element* sibling = &element; sibling; sibling = ElementTraversal::previ
ousSibling(*sibling, HasTagName(element.tagQName())), index++) { |
| 206 auto it = m_elementIndexMap.find(sibling); | 208 auto it = m_elementIndexMap.find(sibling); |
| 207 if (it != m_elementIndexMap.end()) | 209 if (it != m_elementIndexMap.end()) |
| 208 return it->value + index; | 210 return it->value + index; |
| 209 } | 211 } |
| 210 return index; | 212 return index; |
| 211 } | 213 } |
| 212 | 214 |
| (...skipping 13 matching lines...) Expand all Loading... |
| 226 // A spread value of 3 means every third Element will have its nth-index cac
hed. | 228 // A spread value of 3 means every third Element will have its nth-index cac
hed. |
| 227 // Using a spread value > 1 is done to save memory. Looking up the nth-index
will | 229 // Using a spread value > 1 is done to save memory. Looking up the nth-index
will |
| 228 // still be done in constant time in terms of sibling count, at most 'spread
' | 230 // still be done in constant time in terms of sibling count, at most 'spread
' |
| 229 // elements will be traversed. | 231 // elements will be traversed. |
| 230 const unsigned spread = 3; | 232 const unsigned spread = 3; |
| 231 unsigned count = 0; | 233 unsigned count = 0; |
| 232 for (Element* sibling = ElementTraversal::firstChild(parent); sibling; sibli
ng = ElementTraversal::nextSibling(*sibling)) { | 234 for (Element* sibling = ElementTraversal::firstChild(parent); sibling; sibli
ng = ElementTraversal::nextSibling(*sibling)) { |
| 233 if (!(++count % spread)) | 235 if (!(++count % spread)) |
| 234 m_elementIndexMap.add(sibling, count); | 236 m_elementIndexMap.add(sibling, count); |
| 235 } | 237 } |
| 236 ASSERT(count); | 238 DCHECK(count); |
| 237 m_count = count; | 239 m_count = count; |
| 238 } | 240 } |
| 239 | 241 |
| 240 NthIndexData::NthIndexData(ContainerNode& parent, const QualifiedName& type) | 242 NthIndexData::NthIndexData(ContainerNode& parent, const QualifiedName& type) |
| 241 { | 243 { |
| 242 // The frequency at which we cache the nth-index of type for a set of siblin
gs. | 244 // The frequency at which we cache the nth-index of type for a set of siblin
gs. |
| 243 // A spread value of 3 means every third Element of its type will have its n
th-index cached. | 245 // A spread value of 3 means every third Element of its type will have its n
th-index cached. |
| 244 // Using a spread value > 1 is done to save memory. Looking up the nth-index
of its type will | 246 // Using a spread value > 1 is done to save memory. Looking up the nth-index
of its type will |
| 245 // still be done in less time, as most number of elements traversed | 247 // still be done in less time, as most number of elements traversed |
| 246 // will be equal to find 'spread' elements in the sibling set. | 248 // will be equal to find 'spread' elements in the sibling set. |
| 247 const unsigned spread = 3; | 249 const unsigned spread = 3; |
| 248 unsigned count = 0; | 250 unsigned count = 0; |
| 249 for (Element* sibling = ElementTraversal::firstChild(parent, HasTagName(type
)); sibling; sibling = ElementTraversal::nextSibling(*sibling, HasTagName(type))
) { | 251 for (Element* sibling = ElementTraversal::firstChild(parent, HasTagName(type
)); sibling; sibling = ElementTraversal::nextSibling(*sibling, HasTagName(type))
) { |
| 250 if (!(++count % spread)) | 252 if (!(++count % spread)) |
| 251 m_elementIndexMap.add(sibling, count); | 253 m_elementIndexMap.add(sibling, count); |
| 252 } | 254 } |
| 253 ASSERT(count); | 255 DCHECK(count); |
| 254 m_count = count; | 256 m_count = count; |
| 255 } | 257 } |
| 256 | 258 |
| 257 DEFINE_TRACE(NthIndexData) | 259 DEFINE_TRACE(NthIndexData) |
| 258 { | 260 { |
| 259 visitor->trace(m_elementIndexMap); | 261 visitor->trace(m_elementIndexMap); |
| 260 } | 262 } |
| 261 | 263 |
| 262 #if !ENABLE(OILPAN) | 264 #if !ENABLE(OILPAN) |
| 263 NthIndexData::~NthIndexData() | 265 NthIndexData::~NthIndexData() |
| 264 { | 266 { |
| 265 } | 267 } |
| 266 #endif | 268 #endif |
| 267 | 269 |
| 268 } // namespace blink | 270 } // namespace blink |
| OLD | NEW |