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 "config.h" | 5 #include "config.h" |
6 #include "core/dom/NthIndexCache.h" | 6 #include "core/dom/NthIndexCache.h" |
7 | 7 |
8 #include "core/dom/Document.h" | 8 #include "core/dom/Document.h" |
9 | 9 |
10 namespace blink { | 10 namespace blink { |
(...skipping 17 matching lines...) Expand all Loading... |
28 m_parentMap = adoptPtrWillBeNoop(new ParentMap()); | 28 m_parentMap = adoptPtrWillBeNoop(new ParentMap()); |
29 | 29 |
30 ParentMap::AddResult addResult = m_parentMap->add(&parent, nullptr); | 30 ParentMap::AddResult addResult = m_parentMap->add(&parent, nullptr); |
31 if (addResult.isNewEntry) | 31 if (addResult.isNewEntry) |
32 addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData()); | 32 addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData()); |
33 | 33 |
34 ASSERT(addResult.storedValue->value); | 34 ASSERT(addResult.storedValue->value); |
35 return *addResult.storedValue->value; | 35 return *addResult.storedValue->value; |
36 } | 36 } |
37 | 37 |
| 38 NthIndexCache::IndexByType& NthIndexCache::ensureTypeIndexMap(Node& parent) |
| 39 { |
| 40 if (!m_parentMapForType) |
| 41 m_parentMapForType = adoptPtrWillBeNoop(new ParentMapForType()); |
| 42 |
| 43 ParentMapForType::AddResult addResult = m_parentMapForType->add(&parent, nul
lptr); |
| 44 if (addResult.isNewEntry) |
| 45 addResult.storedValue->value = adoptPtrWillBeNoop(new IndexByType()); |
| 46 |
| 47 ASSERT(addResult.storedValue->value); |
| 48 return *addResult.storedValue->value; |
| 49 } |
| 50 |
38 unsigned NthIndexCache::NthIndexData::cacheNthIndices(Element& element) | 51 unsigned NthIndexCache::NthIndexData::cacheNthIndices(Element& element) |
39 { | 52 { |
40 ASSERT(!element.isPseudoElement()); | 53 ASSERT(!element.isPseudoElement()); |
| 54 ASSERT(m_elementIndexMap.isEmpty()); |
41 unsigned index = 0; | 55 unsigned index = 0; |
42 // The frequency at which we cache the nth-index for a set of siblings. | 56 // The frequency at which we cache the nth-index for a set of siblings. |
43 // A spread value of 3 means every third Element will have its nth-index cac
hed. | 57 // A spread value of 3 means every third Element will have its nth-index cac
hed. |
44 // Using a spread value > 1 is done to save memory. Looking up the nth-index
will | 58 // Using a spread value > 1 is done to save memory. Looking up the nth-index
will |
45 // still be done in constant time in terms of sibling count, at most 'spread
' | 59 // still be done in constant time in terms of sibling count, at most 'spread
' |
46 // elements will be traversed. | 60 // elements will be traversed. |
47 const unsigned spread = 3; | 61 const unsigned spread = 3; |
48 unsigned count = 0; | 62 unsigned count = 0; |
49 for (Element* sibling = ElementTraversal::firstChild(*element.parentNode());
sibling; sibling = ElementTraversal::nextSibling(*sibling)) { | 63 for (Element* sibling = ElementTraversal::firstChild(*element.parentNode());
sibling; sibling = ElementTraversal::nextSibling(*sibling)) { |
50 if (!(++count % spread)) | 64 if (!(++count % spread)) |
51 m_elementIndexMap.add(sibling, count); | 65 m_elementIndexMap.add(sibling, count); |
52 if (sibling == &element) | 66 if (sibling == &element) |
53 index = count; | 67 index = count; |
54 } | 68 } |
55 ASSERT(count && index); | 69 ASSERT(count && index); |
56 m_count = count; | 70 m_count = count; |
57 return index; | 71 return index; |
58 } | 72 } |
59 | 73 |
| 74 unsigned NthIndexCache::NthIndexData::cacheNthIndicesOfType(Element& element, co
nst QualifiedName& type) |
| 75 { |
| 76 ASSERT(!element.isPseudoElement()); |
| 77 ASSERT(m_elementIndexMap.isEmpty()); |
| 78 unsigned index = 0; |
| 79 // The frequency at which we cache the nth-index of type for a set of siblin
gs. |
| 80 // A spread value of 3 means every third Element of its type will have its n
th-index cached. |
| 81 // Using a spread value > 1 is done to save memory. Looking up the nth-index
of its type will |
| 82 // still be done in less time, as most number of elements traversed |
| 83 // will be equal to find 'spread' elements in the sibling set. |
| 84 const unsigned spread = 3; |
| 85 unsigned count = 0; |
| 86 for (Element* sibling = ElementTraversal::firstChild(*element.parentNode(),
HasTagName(type)); sibling; sibling = ElementTraversal::nextSibling(*sibling, Ha
sTagName(type))) { |
| 87 if (!(++count % spread)) |
| 88 m_elementIndexMap.add(sibling, count); |
| 89 if (sibling == &element) |
| 90 index = count; |
| 91 } |
| 92 ASSERT(count && index); |
| 93 m_count = count; |
| 94 return index; |
| 95 } |
| 96 |
| 97 NthIndexCache::NthIndexData& NthIndexCache::nthIndexDataWithTagName(Element& ele
ment) |
| 98 { |
| 99 IndexByType::AddResult addResult = ensureTypeIndexMap(*element.parentNode())
.add(element.tagName(), nullptr); |
| 100 if (addResult.isNewEntry) |
| 101 addResult.storedValue->value = adoptPtrWillBeNoop(new NthIndexData()); |
| 102 return *addResult.storedValue->value; |
| 103 } |
| 104 |
60 DEFINE_TRACE(NthIndexCache::NthIndexData) | 105 DEFINE_TRACE(NthIndexCache::NthIndexData) |
61 { | 106 { |
62 #if ENABLE(OILPAN) | 107 #if ENABLE(OILPAN) |
63 visitor->trace(m_elementIndexMap); | 108 visitor->trace(m_elementIndexMap); |
64 #endif | 109 #endif |
65 } | 110 } |
66 | 111 |
67 #if !ENABLE(OILPAN) | 112 #if !ENABLE(OILPAN) |
68 NthIndexCache::NthIndexData::~NthIndexData() | 113 NthIndexCache::NthIndexData::~NthIndexData() |
69 { | 114 { |
70 } | 115 } |
71 #endif | 116 #endif |
72 | 117 |
73 } // namespace blink | 118 } // namespace blink |
OLD | NEW |