OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2013 Apple Inc. All rights reserved. | 2 * Copyright (C) 2013 Apple Inc. All rights reserved. |
3 * Copyright (C) 2014 Samsung Electronics. All rights reserved. | 3 * Copyright (C) 2014 Samsung Electronics. All rights reserved. |
4 * | 4 * |
5 * Redistribution and use in source and binary forms, with or without | 5 * Redistribution and use in source and binary forms, with or without |
6 * modification, are permitted provided that the following conditions are | 6 * modification, are permitted provided that the following conditions are |
7 * met: | 7 * met: |
8 * | 8 * |
9 * * Redistributions of source code must retain the above copyright | 9 * * Redistributions of source code must retain the above copyright |
10 * notice, this list of conditions and the following disclaimer. | 10 * notice, this list of conditions and the following disclaimer. |
(...skipping 18 matching lines...) Expand all Loading... |
29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
30 */ | 30 */ |
31 | 31 |
32 #ifndef CollectionIndexCache_h | 32 #ifndef CollectionIndexCache_h |
33 #define CollectionIndexCache_h | 33 #define CollectionIndexCache_h |
34 | 34 |
35 #include "core/dom/Element.h" | 35 #include "core/dom/Element.h" |
36 | 36 |
37 namespace WebCore { | 37 namespace WebCore { |
38 | 38 |
39 template <typename Collection> | 39 template <typename Collection, typename NodeType> |
40 class CollectionIndexCache { | 40 class CollectionIndexCache { |
41 public: | 41 public: |
42 CollectionIndexCache(); | 42 CollectionIndexCache(); |
43 | 43 |
44 bool isEmpty(const Collection& collection) | 44 bool isEmpty(const Collection& collection) |
45 { | 45 { |
46 if (isCachedNodeCountValid()) | 46 if (isCachedNodeCountValid()) |
47 return !cachedNodeCount(); | 47 return !cachedNodeCount(); |
48 if (cachedNode()) | 48 if (cachedNode()) |
49 return false; | 49 return false; |
50 return !nodeAt(collection, 0); | 50 return !nodeAt(collection, 0); |
51 } | 51 } |
52 bool hasExactlyOneNode(const Collection& collection) | 52 bool hasExactlyOneNode(const Collection& collection) |
53 { | 53 { |
54 if (isCachedNodeCountValid()) | 54 if (isCachedNodeCountValid()) |
55 return cachedNodeCount() == 1; | 55 return cachedNodeCount() == 1; |
56 if (cachedNode()) | 56 if (cachedNode()) |
57 return !cachedNodeIndex() && !nodeAt(collection, 1); | 57 return !cachedNodeIndex() && !nodeAt(collection, 1); |
58 return nodeAt(collection, 0) && !nodeAt(collection, 1); | 58 return nodeAt(collection, 0) && !nodeAt(collection, 1); |
59 } | 59 } |
60 | 60 |
61 unsigned nodeCount(const Collection&); | 61 unsigned nodeCount(const Collection&); |
62 Node* nodeAt(const Collection&, unsigned index); | 62 NodeType* nodeAt(const Collection&, unsigned index); |
63 | 63 |
64 void invalidate(); | 64 void invalidate(); |
65 | 65 |
66 ALWAYS_INLINE void setCachedNode(Node* node, unsigned index) | 66 ALWAYS_INLINE void setCachedNode(NodeType* node, unsigned index) |
67 { | 67 { |
68 ASSERT(node); | 68 ASSERT(node); |
69 m_currentNode = node; | 69 m_currentNode = node; |
70 m_cachedNodeIndex = index; | 70 m_cachedNodeIndex = index; |
71 } | 71 } |
72 | 72 |
73 private: | 73 private: |
74 Node* nodeBeforeOrAfterCachedNode(const Collection&, unsigned index, const C
ontainerNode& root); | 74 NodeType* nodeBeforeOrAfterCachedNode(const Collection&, unsigned index, con
st ContainerNode& root); |
75 bool isLastNodeCloserThanLastOrCachedNode(unsigned index) const; | 75 bool isLastNodeCloserThanLastOrCachedNode(unsigned index) const; |
76 bool isFirstNodeCloserThanCachedNode(unsigned index) const; | 76 bool isFirstNodeCloserThanCachedNode(unsigned index) const; |
77 | 77 |
78 ALWAYS_INLINE Node* cachedNode() const { return m_currentNode; } | 78 ALWAYS_INLINE NodeType* cachedNode() const { return m_currentNode; } |
79 ALWAYS_INLINE unsigned cachedNodeIndex() const { ASSERT(cachedNode()); retur
n m_cachedNodeIndex; } | 79 ALWAYS_INLINE unsigned cachedNodeIndex() const { ASSERT(cachedNode()); retur
n m_cachedNodeIndex; } |
80 | 80 |
81 ALWAYS_INLINE bool isCachedNodeCountValid() const { return m_isLengthCacheVa
lid; } | 81 ALWAYS_INLINE bool isCachedNodeCountValid() const { return m_isLengthCacheVa
lid; } |
82 ALWAYS_INLINE unsigned cachedNodeCount() const { return m_cachedNodeCount; } | 82 ALWAYS_INLINE unsigned cachedNodeCount() const { return m_cachedNodeCount; } |
83 ALWAYS_INLINE void setCachedNodeCount(unsigned length) | 83 ALWAYS_INLINE void setCachedNodeCount(unsigned length) |
84 { | 84 { |
85 m_cachedNodeCount = length; | 85 m_cachedNodeCount = length; |
86 m_isLengthCacheValid = true; | 86 m_isLengthCacheValid = true; |
87 } | 87 } |
88 | 88 |
89 Node* m_currentNode; | 89 NodeType* m_currentNode; |
90 unsigned m_cachedNodeCount; | 90 unsigned m_cachedNodeCount; |
91 unsigned m_cachedNodeIndex; | 91 unsigned m_cachedNodeIndex; |
92 unsigned m_isLengthCacheValid : 1; | 92 unsigned m_isLengthCacheValid : 1; |
93 }; | 93 }; |
94 | 94 |
95 template <typename Collection> | 95 template <typename Collection, typename NodeType> |
96 CollectionIndexCache<Collection>::CollectionIndexCache() | 96 CollectionIndexCache<Collection, NodeType>::CollectionIndexCache() |
97 : m_currentNode(0) | 97 : m_currentNode(0) |
98 , m_cachedNodeCount(0) | 98 , m_cachedNodeCount(0) |
99 , m_cachedNodeIndex(0) | 99 , m_cachedNodeIndex(0) |
100 , m_isLengthCacheValid(false) | 100 , m_isLengthCacheValid(false) |
101 { | 101 { |
102 } | 102 } |
103 | 103 |
104 template <typename Collection> | 104 template <typename Collection, typename NodeType> |
105 void CollectionIndexCache<Collection>::invalidate() | 105 void CollectionIndexCache<Collection, NodeType>::invalidate() |
106 { | 106 { |
107 m_currentNode = 0; | 107 m_currentNode = 0; |
108 m_isLengthCacheValid = false; | 108 m_isLengthCacheValid = false; |
109 } | 109 } |
110 | 110 |
111 template <typename Collection> | 111 template <typename Collection, typename NodeType> |
112 inline unsigned CollectionIndexCache<Collection>::nodeCount(const Collection& co
llection) | 112 inline unsigned CollectionIndexCache<Collection, NodeType>::nodeCount(const Coll
ection& collection) |
113 { | 113 { |
114 if (isCachedNodeCountValid()) | 114 if (isCachedNodeCountValid()) |
115 return cachedNodeCount(); | 115 return cachedNodeCount(); |
116 | 116 |
117 nodeAt(collection, UINT_MAX); | 117 nodeAt(collection, UINT_MAX); |
118 ASSERT(isCachedNodeCountValid()); | 118 ASSERT(isCachedNodeCountValid()); |
119 | 119 |
120 return cachedNodeCount(); | 120 return cachedNodeCount(); |
121 } | 121 } |
122 | 122 |
123 template <typename Collection> | 123 template <typename Collection, typename NodeType> |
124 inline Node* CollectionIndexCache<Collection>::nodeAt(const Collection& collecti
on, unsigned index) | 124 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAt(const Collec
tion& collection, unsigned index) |
125 { | 125 { |
126 if (cachedNode() && cachedNodeIndex() == index) | 126 if (cachedNode() && cachedNodeIndex() == index) |
127 return cachedNode(); | 127 return cachedNode(); |
128 | 128 |
129 if (isCachedNodeCountValid() && cachedNodeCount() <= index) | 129 if (isCachedNodeCountValid() && cachedNodeCount() <= index) |
130 return 0; | 130 return 0; |
131 | 131 |
132 ContainerNode& root = collection.rootNode(); | 132 ContainerNode& root = collection.rootNode(); |
133 if (isCachedNodeCountValid() && collection.canTraverseBackward() && isLastNo
deCloserThanLastOrCachedNode(index)) { | 133 if (isCachedNodeCountValid() && collection.canTraverseBackward() && isLastNo
deCloserThanLastOrCachedNode(index)) { |
134 Node* lastNode = collection.itemBefore(0); | 134 NodeType* lastNode = collection.itemBefore(0); |
135 ASSERT(lastNode); | 135 ASSERT(lastNode); |
136 setCachedNode(lastNode, cachedNodeCount() - 1); | 136 setCachedNode(lastNode, cachedNodeCount() - 1); |
137 } else if (!cachedNode() || isFirstNodeCloserThanCachedNode(index) || (!coll
ection.canTraverseBackward() && index < cachedNodeIndex())) { | 137 } else if (!cachedNode() || isFirstNodeCloserThanCachedNode(index) || (!coll
ection.canTraverseBackward() && index < cachedNodeIndex())) { |
138 Node* firstNode = collection.traverseToFirstElement(root); | 138 NodeType* firstNode = collection.traverseToFirstElement(root); |
139 if (!firstNode) { | 139 if (!firstNode) { |
140 setCachedNodeCount(0); | 140 setCachedNodeCount(0); |
141 return 0; | 141 return 0; |
142 } | 142 } |
143 setCachedNode(firstNode, 0); | 143 setCachedNode(firstNode, 0); |
144 ASSERT(!cachedNodeIndex()); | 144 ASSERT(!cachedNodeIndex()); |
145 } | 145 } |
146 | 146 |
147 if (cachedNodeIndex() == index) | 147 if (cachedNodeIndex() == index) |
148 return cachedNode(); | 148 return cachedNode(); |
149 | 149 |
150 return nodeBeforeOrAfterCachedNode(collection, index, root); | 150 return nodeBeforeOrAfterCachedNode(collection, index, root); |
151 } | 151 } |
152 | 152 |
153 template <typename Collection> | 153 template <typename Collection, typename NodeType> |
154 inline Node* CollectionIndexCache<Collection>::nodeBeforeOrAfterCachedNode(const
Collection& collection, unsigned index, const ContainerNode &root) | 154 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeOrAfterCa
chedNode(const Collection& collection, unsigned index, const ContainerNode &root
) |
155 { | 155 { |
156 unsigned currentIndex = cachedNodeIndex(); | 156 unsigned currentIndex = cachedNodeIndex(); |
157 Node* currentNode = cachedNode(); | 157 NodeType* currentNode = cachedNode(); |
158 ASSERT(currentNode); | 158 ASSERT(currentNode); |
159 ASSERT(currentIndex != index); | 159 ASSERT(currentIndex != index); |
160 | 160 |
161 if (index < cachedNodeIndex()) { | 161 if (index < cachedNodeIndex()) { |
162 ASSERT(collection.canTraverseBackward()); | 162 ASSERT(collection.canTraverseBackward()); |
163 while ((currentNode = collection.itemBefore(currentNode))) { | 163 while ((currentNode = collection.itemBefore(currentNode))) { |
164 ASSERT(currentIndex); | 164 ASSERT(currentIndex); |
165 currentIndex--; | 165 currentIndex--; |
166 if (currentIndex == index) { | 166 if (currentIndex == index) { |
167 setCachedNode(currentNode, currentIndex); | 167 setCachedNode(currentNode, currentIndex); |
168 return currentNode; | 168 return currentNode; |
169 } | 169 } |
170 } | 170 } |
171 ASSERT_NOT_REACHED(); | 171 ASSERT_NOT_REACHED(); |
172 return 0; | 172 return 0; |
173 } | 173 } |
174 | 174 |
175 currentNode = collection.traverseForwardToOffset(index, *currentNode, curren
tIndex, root); | 175 currentNode = collection.traverseForwardToOffset(index, *currentNode, curren
tIndex, root); |
176 if (!currentNode) { | 176 if (!currentNode) { |
177 // Did not find the node. On plus side, we now know the length. | 177 // Did not find the node. On plus side, we now know the length. |
178 setCachedNodeCount(currentIndex + 1); | 178 setCachedNodeCount(currentIndex + 1); |
179 return 0; | 179 return 0; |
180 } | 180 } |
181 setCachedNode(currentNode, currentIndex); | 181 setCachedNode(currentNode, currentIndex); |
182 return currentNode; | 182 return currentNode; |
183 } | 183 } |
184 | 184 |
185 template <typename Collection> | 185 template <typename Collection, typename NodeType> |
186 ALWAYS_INLINE bool CollectionIndexCache<Collection>::isLastNodeCloserThanLastOrC
achedNode(unsigned index) const | 186 ALWAYS_INLINE bool CollectionIndexCache<Collection, NodeType>::isLastNodeCloserT
hanLastOrCachedNode(unsigned index) const |
187 { | 187 { |
188 ASSERT(isCachedNodeCountValid()); | 188 ASSERT(isCachedNodeCountValid()); |
189 unsigned distanceFromLastNode = cachedNodeCount() - index; | 189 unsigned distanceFromLastNode = cachedNodeCount() - index; |
190 if (!cachedNode()) | 190 if (!cachedNode()) |
191 return distanceFromLastNode < index; | 191 return distanceFromLastNode < index; |
192 | 192 |
193 return cachedNodeIndex() < index && distanceFromLastNode < index - cachedNod
eIndex(); | 193 return cachedNodeIndex() < index && distanceFromLastNode < index - cachedNod
eIndex(); |
194 } | 194 } |
195 | 195 |
196 template <typename Collection> | 196 template <typename Collection, typename NodeType> |
197 ALWAYS_INLINE bool CollectionIndexCache<Collection>::isFirstNodeCloserThanCached
Node(unsigned index) const | 197 ALWAYS_INLINE bool CollectionIndexCache<Collection, NodeType>::isFirstNodeCloser
ThanCachedNode(unsigned index) const |
198 { | 198 { |
199 if (cachedNodeIndex() < index) | 199 if (cachedNodeIndex() < index) |
200 return false; | 200 return false; |
201 | 201 |
202 unsigned distanceFromCachedNode = cachedNodeIndex() - index; | 202 unsigned distanceFromCachedNode = cachedNodeIndex() - index; |
203 return index < distanceFromCachedNode; | 203 return index < distanceFromCachedNode; |
204 } | 204 } |
205 | 205 |
206 } // namespace WebCore | 206 } // namespace WebCore |
207 | 207 |
208 #endif // CollectionIndexCache_h | 208 #endif // CollectionIndexCache_h |
OLD | NEW |