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 ENABLE(ASSERT) |
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 ASSERT(m_domTreeVersion == m_document->domTreeVersion()); |
24 m_document->setNthIndexCache(nullptr); | 24 m_document->setNthIndexCache(nullptr); |
25 } | 25 } |
26 | 26 |
27 NthIndexData& NthIndexCache::ensureNthIndexDataFor(Node& parent) | 27 namespace { |
| 28 |
| 29 // Generating the cached nth-index counts when the number of children |
| 30 // 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 |
| 32 // increasing number of children. |
| 33 |
| 34 const unsigned kCachedSiblingCountLimit = 32; |
| 35 |
| 36 unsigned uncachedNthChildIndex(Element& element) |
28 { | 37 { |
| 38 int index = 1; |
| 39 for (const Element* sibling = ElementTraversal::previousSibling(element); si
bling; sibling = ElementTraversal::previousSibling(*sibling)) |
| 40 index++; |
| 41 |
| 42 return index; |
| 43 } |
| 44 |
| 45 unsigned uncachedNthLastChildIndex(Element& element) |
| 46 { |
| 47 int index = 1; |
| 48 for (const Element* sibling = ElementTraversal::nextSibling(element); siblin
g; sibling = ElementTraversal::nextSibling(*sibling)) |
| 49 ++index; |
| 50 return index; |
| 51 } |
| 52 |
| 53 unsigned uncachedNthOfTypeIndex(Element& element, unsigned& siblingCount) |
| 54 { |
| 55 int index = 1; |
| 56 const QualifiedName& tag = element.tagQName(); |
| 57 for (const Element* sibling = ElementTraversal::previousSibling(element); si
bling; sibling = ElementTraversal::previousSibling(*sibling)) { |
| 58 if (sibling->tagQName() == tag) |
| 59 ++index; |
| 60 ++siblingCount; |
| 61 } |
| 62 return index; |
| 63 } |
| 64 |
| 65 unsigned uncachedNthLastOfTypeIndex(Element& element, unsigned& siblingCount) |
| 66 { |
| 67 int index = 1; |
| 68 const QualifiedName& tag = element.tagQName(); |
| 69 for (const Element* sibling = ElementTraversal::nextSibling(element); siblin
g; sibling = ElementTraversal::nextSibling(*sibling)) { |
| 70 if (sibling->tagQName() == tag) |
| 71 ++index; |
| 72 ++siblingCount; |
| 73 } |
| 74 return index; |
| 75 } |
| 76 |
| 77 } // namespace |
| 78 |
| 79 unsigned NthIndexCache::nthChildIndex(Element& element) |
| 80 { |
| 81 if (element.isPseudoElement()) |
| 82 return 1; |
| 83 ASSERT(element.parentNode()); |
| 84 NthIndexCache* nthIndexCache = element.document().nthIndexCache(); |
| 85 NthIndexData* nthIndexData = nullptr; |
| 86 if (nthIndexCache && nthIndexCache->m_parentMap) |
| 87 nthIndexData = nthIndexCache->m_parentMap->get(element.parentNode()); |
| 88 if (nthIndexData) |
| 89 return nthIndexData->nthIndex(element); |
| 90 unsigned index = uncachedNthChildIndex(element); |
| 91 if (nthIndexCache && index > kCachedSiblingCountLimit) |
| 92 nthIndexCache->cacheNthIndexDataForParent(element); |
| 93 return index; |
| 94 } |
| 95 |
| 96 unsigned NthIndexCache::nthLastChildIndex(Element& element) |
| 97 { |
| 98 if (element.isPseudoElement()) |
| 99 return 1; |
| 100 ASSERT(element.parentNode()); |
| 101 NthIndexCache* nthIndexCache = element.document().nthIndexCache(); |
| 102 NthIndexData* nthIndexData = nullptr; |
| 103 if (nthIndexCache && nthIndexCache->m_parentMap) |
| 104 nthIndexData = nthIndexCache->m_parentMap->get(element.parentNode()); |
| 105 if (nthIndexData) |
| 106 return nthIndexData->nthLastIndex(element); |
| 107 unsigned index = uncachedNthLastChildIndex(element); |
| 108 if (nthIndexCache && index > kCachedSiblingCountLimit) |
| 109 nthIndexCache->cacheNthIndexDataForParent(element); |
| 110 return index; |
| 111 } |
| 112 |
| 113 NthIndexData* NthIndexCache::nthTypeIndexDataForParent(Element& element) const |
| 114 { |
| 115 ASSERT(element.parentNode()); |
| 116 if (!m_parentMapForType) |
| 117 return nullptr; |
| 118 if (const IndexByType* map = m_parentMapForType->get(element.parentNode())) |
| 119 return map->get(element.tagName()); |
| 120 return nullptr; |
| 121 } |
| 122 |
| 123 unsigned NthIndexCache::nthOfTypeIndex(Element& element) |
| 124 { |
| 125 if (element.isPseudoElement()) |
| 126 return 1; |
| 127 NthIndexCache* nthIndexCache = element.document().nthIndexCache(); |
| 128 if (nthIndexCache) { |
| 129 if (NthIndexData* nthIndexData = nthIndexCache->nthTypeIndexDataForParen
t(element)) |
| 130 return nthIndexData->nthOfTypeIndex(element); |
| 131 } |
| 132 unsigned siblingCount = 0; |
| 133 unsigned index = uncachedNthOfTypeIndex(element, siblingCount); |
| 134 if (nthIndexCache && siblingCount > kCachedSiblingCountLimit) |
| 135 nthIndexCache->cacheNthOfTypeIndexDataForParent(element); |
| 136 return index; |
| 137 } |
| 138 |
| 139 unsigned NthIndexCache::nthLastOfTypeIndex(Element& element) |
| 140 { |
| 141 if (element.isPseudoElement()) |
| 142 return 1; |
| 143 NthIndexCache* nthIndexCache = element.document().nthIndexCache(); |
| 144 if (nthIndexCache) { |
| 145 if (NthIndexData* nthIndexData = nthIndexCache->nthTypeIndexDataForParen
t(element)) |
| 146 return nthIndexData->nthLastOfTypeIndex(element); |
| 147 } |
| 148 unsigned siblingCount = 0; |
| 149 unsigned index = uncachedNthLastOfTypeIndex(element, siblingCount); |
| 150 if (nthIndexCache && siblingCount > kCachedSiblingCountLimit) |
| 151 nthIndexCache->cacheNthOfTypeIndexDataForParent(element); |
| 152 return index; |
| 153 } |
| 154 |
| 155 void NthIndexCache::cacheNthIndexDataForParent(Element& element) |
| 156 { |
| 157 ASSERT(element.parentNode()); |
29 if (!m_parentMap) | 158 if (!m_parentMap) |
30 m_parentMap = adoptPtrWillBeNoop(new ParentMap()); | 159 m_parentMap = adoptPtrWillBeNoop(new ParentMap()); |
31 | 160 |
32 ParentMap::AddResult addResult = m_parentMap->add(&parent, nullptr); | 161 ParentMap::AddResult addResult = m_parentMap->add(element.parentNode(), null
ptr); |
33 if (addResult.isNewEntry) | 162 ASSERT(addResult.isNewEntry); |
34 addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData()); | 163 addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData(*element.
parentNode())); |
35 | |
36 ASSERT(addResult.storedValue->value); | |
37 return *addResult.storedValue->value; | |
38 } | 164 } |
39 | 165 |
40 NthIndexCache::IndexByType& NthIndexCache::ensureTypeIndexMap(Node& parent) | 166 NthIndexCache::IndexByType& NthIndexCache::ensureTypeIndexMap(ContainerNode& par
ent) |
41 { | 167 { |
42 if (!m_parentMapForType) | 168 if (!m_parentMapForType) |
43 m_parentMapForType = adoptPtrWillBeNoop(new ParentMapForType()); | 169 m_parentMapForType = adoptPtrWillBeNoop(new ParentMapForType()); |
44 | 170 |
45 ParentMapForType::AddResult addResult = m_parentMapForType->add(&parent, nul
lptr); | 171 ParentMapForType::AddResult addResult = m_parentMapForType->add(&parent, nul
lptr); |
46 if (addResult.isNewEntry) | 172 if (addResult.isNewEntry) |
47 addResult.storedValue->value = adoptPtrWillBeNoop(new IndexByType()); | 173 addResult.storedValue->value = adoptPtrWillBeNoop(new IndexByType()); |
48 | 174 |
49 ASSERT(addResult.storedValue->value); | 175 ASSERT(addResult.storedValue->value); |
50 return *addResult.storedValue->value; | 176 return *addResult.storedValue->value; |
51 } | 177 } |
52 | 178 |
53 NthIndexData& NthIndexCache::nthIndexDataWithTagName(Element& element) | 179 void NthIndexCache::cacheNthOfTypeIndexDataForParent(Element& element) |
54 { | 180 { |
| 181 ASSERT(element.parentNode()); |
55 IndexByType::AddResult addResult = ensureTypeIndexMap(*element.parentNode())
.add(element.tagName(), nullptr); | 182 IndexByType::AddResult addResult = ensureTypeIndexMap(*element.parentNode())
.add(element.tagName(), nullptr); |
56 if (addResult.isNewEntry) | 183 ASSERT(addResult.isNewEntry); |
57 addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData()); | 184 addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData(*element.
parentNode(), element.tagQName())); |
58 return *addResult.storedValue->value; | |
59 } | 185 } |
60 | 186 |
61 unsigned NthIndexData::nthIndex(Element& element) | 187 unsigned NthIndexData::nthIndex(Element& element) const |
62 { | 188 { |
63 if (element.isPseudoElement()) | 189 ASSERT(!element.isPseudoElement()); |
64 return 1; | |
65 if (!m_count) | |
66 return cacheNthIndices(element); | |
67 | 190 |
68 unsigned index = 0; | 191 unsigned index = 0; |
69 for (Element* sibling = &element; sibling; sibling = ElementTraversal::previ
ousSibling(*sibling), index++) { | 192 for (Element* sibling = &element; sibling; sibling = ElementTraversal::previ
ousSibling(*sibling), index++) { |
70 auto it = m_elementIndexMap.find(sibling); | 193 auto it = m_elementIndexMap.find(sibling); |
71 if (it != m_elementIndexMap.end()) | 194 if (it != m_elementIndexMap.end()) |
72 return it->value + index; | 195 return it->value + index; |
73 } | 196 } |
74 return index; | 197 return index; |
75 } | 198 } |
76 | 199 |
77 unsigned NthIndexData::nthIndexOfType(Element& element, const QualifiedName& typ
e) | 200 unsigned NthIndexData::nthOfTypeIndex(Element& element) const |
78 { | 201 { |
79 if (element.isPseudoElement()) | 202 ASSERT(!element.isPseudoElement()); |
80 return 1; | 203 |
81 if (!m_count) | |
82 return cacheNthIndicesOfType(element, type); | |
83 unsigned index = 0; | 204 unsigned index = 0; |
84 for (Element* sibling = &element; sibling; sibling = ElementTraversal::previ
ousSibling(*sibling, HasTagName(type)), index++) { | 205 for (Element* sibling = &element; sibling; sibling = ElementTraversal::previ
ousSibling(*sibling, HasTagName(element.tagQName())), index++) { |
85 auto it = m_elementIndexMap.find(sibling); | 206 auto it = m_elementIndexMap.find(sibling); |
86 if (it != m_elementIndexMap.end()) | 207 if (it != m_elementIndexMap.end()) |
87 return it->value + index; | 208 return it->value + index; |
88 } | 209 } |
89 return index; | 210 return index; |
90 } | 211 } |
91 | 212 |
92 unsigned NthIndexData::nthLastIndex(Element& element) | 213 unsigned NthIndexData::nthLastIndex(Element& element) const |
93 { | 214 { |
94 if (element.isPseudoElement()) | 215 return m_count - nthIndex(element) + 1; |
95 return 1; | |
96 unsigned index = nthIndex(element); | |
97 return m_count - index + 1; | |
98 } | 216 } |
99 | 217 |
100 unsigned NthIndexData::nthLastIndexOfType(Element& element, const QualifiedName&
type) | 218 unsigned NthIndexData::nthLastOfTypeIndex(Element& element) const |
101 { | 219 { |
102 if (element.isPseudoElement()) | 220 return m_count - nthOfTypeIndex(element) + 1; |
103 return 1; | |
104 unsigned index = nthIndexOfType(element, type); | |
105 return m_count - index + 1; | |
106 } | 221 } |
107 | 222 |
108 unsigned NthIndexData::cacheNthIndices(Element& element) | 223 NthIndexData::NthIndexData(ContainerNode& parent) |
109 { | 224 { |
110 ASSERT(!element.isPseudoElement()); | |
111 ASSERT(m_elementIndexMap.isEmpty()); | |
112 unsigned index = 0; | |
113 // The frequency at which we cache the nth-index for a set of siblings. | 225 // The frequency at which we cache the nth-index for a set of siblings. |
114 // A spread value of 3 means every third Element will have its nth-index cac
hed. | 226 // A spread value of 3 means every third Element will have its nth-index cac
hed. |
115 // Using a spread value > 1 is done to save memory. Looking up the nth-index
will | 227 // Using a spread value > 1 is done to save memory. Looking up the nth-index
will |
116 // still be done in constant time in terms of sibling count, at most 'spread
' | 228 // still be done in constant time in terms of sibling count, at most 'spread
' |
117 // elements will be traversed. | 229 // elements will be traversed. |
118 const unsigned spread = 3; | 230 const unsigned spread = 3; |
119 unsigned count = 0; | 231 unsigned count = 0; |
120 for (Element* sibling = ElementTraversal::firstChild(*element.parentNode());
sibling; sibling = ElementTraversal::nextSibling(*sibling)) { | 232 for (Element* sibling = ElementTraversal::firstChild(parent); sibling; sibli
ng = ElementTraversal::nextSibling(*sibling)) { |
121 if (!(++count % spread)) | 233 if (!(++count % spread)) |
122 m_elementIndexMap.add(sibling, count); | 234 m_elementIndexMap.add(sibling, count); |
123 if (sibling == &element) | |
124 index = count; | |
125 } | 235 } |
126 ASSERT(count && index); | 236 ASSERT(count); |
127 m_count = count; | 237 m_count = count; |
128 return index; | |
129 } | 238 } |
130 | 239 |
131 unsigned NthIndexData::cacheNthIndicesOfType(Element& element, const QualifiedNa
me& type) | 240 NthIndexData::NthIndexData(ContainerNode& parent, const QualifiedName& type) |
132 { | 241 { |
133 ASSERT(!element.isPseudoElement()); | |
134 ASSERT(m_elementIndexMap.isEmpty()); | |
135 unsigned index = 0; | |
136 // The frequency at which we cache the nth-index of type for a set of siblin
gs. | 242 // The frequency at which we cache the nth-index of type for a set of siblin
gs. |
137 // A spread value of 3 means every third Element of its type will have its n
th-index cached. | 243 // A spread value of 3 means every third Element of its type will have its n
th-index cached. |
138 // Using a spread value > 1 is done to save memory. Looking up the nth-index
of its type will | 244 // Using a spread value > 1 is done to save memory. Looking up the nth-index
of its type will |
139 // still be done in less time, as most number of elements traversed | 245 // still be done in less time, as most number of elements traversed |
140 // will be equal to find 'spread' elements in the sibling set. | 246 // will be equal to find 'spread' elements in the sibling set. |
141 const unsigned spread = 3; | 247 const unsigned spread = 3; |
142 unsigned count = 0; | 248 unsigned count = 0; |
143 for (Element* sibling = ElementTraversal::firstChild(*element.parentNode(),
HasTagName(type)); sibling; sibling = ElementTraversal::nextSibling(*sibling, Ha
sTagName(type))) { | 249 for (Element* sibling = ElementTraversal::firstChild(parent, HasTagName(type
)); sibling; sibling = ElementTraversal::nextSibling(*sibling, HasTagName(type))
) { |
144 if (!(++count % spread)) | 250 if (!(++count % spread)) |
145 m_elementIndexMap.add(sibling, count); | 251 m_elementIndexMap.add(sibling, count); |
146 if (sibling == &element) | |
147 index = count; | |
148 } | 252 } |
149 ASSERT(count && index); | 253 ASSERT(count); |
150 m_count = count; | 254 m_count = count; |
151 return index; | |
152 } | 255 } |
153 | 256 |
154 DEFINE_TRACE(NthIndexData) | 257 DEFINE_TRACE(NthIndexData) |
155 { | 258 { |
156 #if ENABLE(OILPAN) | 259 #if ENABLE(OILPAN) |
157 visitor->trace(m_elementIndexMap); | 260 visitor->trace(m_elementIndexMap); |
158 #endif | 261 #endif |
159 } | 262 } |
160 | 263 |
161 #if !ENABLE(OILPAN) | 264 #if !ENABLE(OILPAN) |
162 NthIndexData::~NthIndexData() | 265 NthIndexData::~NthIndexData() |
163 { | 266 { |
164 } | 267 } |
165 #endif | 268 #endif |
166 | 269 |
167 } // namespace blink | 270 } // namespace blink |
OLD | NEW |