| 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 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 62 | 62 |
| 63 void invalidate(); | 63 void invalidate(); |
| 64 | 64 |
| 65 DEFINE_INLINE_VIRTUAL_TRACE() | 65 DEFINE_INLINE_VIRTUAL_TRACE() |
| 66 { | 66 { |
| 67 visitor->trace(m_currentNode); | 67 visitor->trace(m_currentNode); |
| 68 } | 68 } |
| 69 | 69 |
| 70 protected: | 70 protected: |
| 71 ALWAYS_INLINE NodeType* cachedNode() const { return m_currentNode; } | 71 ALWAYS_INLINE NodeType* cachedNode() const { return m_currentNode; } |
| 72 ALWAYS_INLINE unsigned cachedNodeIndex() const { ASSERT(cachedNode()); retur
n m_cachedNodeIndex; } | 72 ALWAYS_INLINE unsigned cachedNodeIndex() const |
| 73 { |
| 74 DCHECK(cachedNode()); |
| 75 return m_cachedNodeIndex; |
| 76 } |
| 73 ALWAYS_INLINE void setCachedNode(NodeType* node, unsigned index) | 77 ALWAYS_INLINE void setCachedNode(NodeType* node, unsigned index) |
| 74 { | 78 { |
| 75 ASSERT(node); | 79 DCHECK(node); |
| 76 m_currentNode = node; | 80 m_currentNode = node; |
| 77 m_cachedNodeIndex = index; | 81 m_cachedNodeIndex = index; |
| 78 } | 82 } |
| 79 | 83 |
| 80 ALWAYS_INLINE bool isCachedNodeCountValid() const { return m_isLengthCacheVa
lid; } | 84 ALWAYS_INLINE bool isCachedNodeCountValid() const { return m_isLengthCacheVa
lid; } |
| 81 ALWAYS_INLINE unsigned cachedNodeCount() const { return m_cachedNodeCount; } | 85 ALWAYS_INLINE unsigned cachedNodeCount() const { return m_cachedNodeCount; } |
| 82 ALWAYS_INLINE void setCachedNodeCount(unsigned length) | 86 ALWAYS_INLINE void setCachedNodeCount(unsigned length) |
| 83 { | 87 { |
| 84 m_cachedNodeCount = length; | 88 m_cachedNodeCount = length; |
| 85 m_isLengthCacheValid = true; | 89 m_isLengthCacheValid = true; |
| (...skipping 25 matching lines...) Expand all Loading... |
| 111 m_isLengthCacheValid = false; | 115 m_isLengthCacheValid = false; |
| 112 } | 116 } |
| 113 | 117 |
| 114 template <typename Collection, typename NodeType> | 118 template <typename Collection, typename NodeType> |
| 115 inline unsigned CollectionIndexCache<Collection, NodeType>::nodeCount(const Coll
ection& collection) | 119 inline unsigned CollectionIndexCache<Collection, NodeType>::nodeCount(const Coll
ection& collection) |
| 116 { | 120 { |
| 117 if (isCachedNodeCountValid()) | 121 if (isCachedNodeCountValid()) |
| 118 return cachedNodeCount(); | 122 return cachedNodeCount(); |
| 119 | 123 |
| 120 nodeAt(collection, UINT_MAX); | 124 nodeAt(collection, UINT_MAX); |
| 121 ASSERT(isCachedNodeCountValid()); | 125 DCHECK(isCachedNodeCountValid()); |
| 122 | 126 |
| 123 return cachedNodeCount(); | 127 return cachedNodeCount(); |
| 124 } | 128 } |
| 125 | 129 |
| 126 template <typename Collection, typename NodeType> | 130 template <typename Collection, typename NodeType> |
| 127 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAt(const Collec
tion& collection, unsigned index) | 131 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAt(const Collec
tion& collection, unsigned index) |
| 128 { | 132 { |
| 129 if (isCachedNodeCountValid() && index >= cachedNodeCount()) | 133 if (isCachedNodeCountValid() && index >= cachedNodeCount()) |
| 130 return nullptr; | 134 return nullptr; |
| 131 | 135 |
| 132 if (cachedNode()) { | 136 if (cachedNode()) { |
| 133 if (index > cachedNodeIndex()) | 137 if (index > cachedNodeIndex()) |
| 134 return nodeAfterCachedNode(collection, index); | 138 return nodeAfterCachedNode(collection, index); |
| 135 if (index < cachedNodeIndex()) | 139 if (index < cachedNodeIndex()) |
| 136 return nodeBeforeCachedNode(collection, index); | 140 return nodeBeforeCachedNode(collection, index); |
| 137 return cachedNode(); | 141 return cachedNode(); |
| 138 } | 142 } |
| 139 | 143 |
| 140 // No valid cache yet, let's find the first matching element. | 144 // No valid cache yet, let's find the first matching element. |
| 141 ASSERT(!isCachedNodeCountValid()); | 145 DCHECK(!isCachedNodeCountValid()); |
| 142 NodeType* firstNode = collection.traverseToFirst(); | 146 NodeType* firstNode = collection.traverseToFirst(); |
| 143 if (!firstNode) { | 147 if (!firstNode) { |
| 144 // The collection is empty. | 148 // The collection is empty. |
| 145 setCachedNodeCount(0); | 149 setCachedNodeCount(0); |
| 146 return nullptr; | 150 return nullptr; |
| 147 } | 151 } |
| 148 setCachedNode(firstNode, 0); | 152 setCachedNode(firstNode, 0); |
| 149 return index ? nodeAfterCachedNode(collection, index) : firstNode; | 153 return index ? nodeAfterCachedNode(collection, index) : firstNode; |
| 150 } | 154 } |
| 151 | 155 |
| 152 template <typename Collection, typename NodeType> | 156 template <typename Collection, typename NodeType> |
| 153 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeCachedNod
e(const Collection& collection, unsigned index) | 157 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeCachedNod
e(const Collection& collection, unsigned index) |
| 154 { | 158 { |
| 155 ASSERT(cachedNode()); // Cache should be valid. | 159 DCHECK(cachedNode()); // Cache should be valid. |
| 156 unsigned currentIndex = cachedNodeIndex(); | 160 unsigned currentIndex = cachedNodeIndex(); |
| 157 ASSERT(currentIndex > index); | 161 DCHECK_GT(currentIndex, index); |
| 158 | 162 |
| 159 // Determine if we should traverse from the beginning of the collection inst
ead of the cached node. | 163 // Determine if we should traverse from the beginning of the collection inst
ead of the cached node. |
| 160 bool firstIsCloser = index < currentIndex - index; | 164 bool firstIsCloser = index < currentIndex - index; |
| 161 if (firstIsCloser || !collection.canTraverseBackward()) { | 165 if (firstIsCloser || !collection.canTraverseBackward()) { |
| 162 NodeType* firstNode = collection.traverseToFirst(); | 166 NodeType* firstNode = collection.traverseToFirst(); |
| 163 ASSERT(firstNode); | 167 DCHECK(firstNode); |
| 164 setCachedNode(firstNode, 0); | 168 setCachedNode(firstNode, 0); |
| 165 return index ? nodeAfterCachedNode(collection, index) : firstNode; | 169 return index ? nodeAfterCachedNode(collection, index) : firstNode; |
| 166 } | 170 } |
| 167 | 171 |
| 168 // Backward traversal from the cached node to the requested index. | 172 // Backward traversal from the cached node to the requested index. |
| 169 ASSERT(collection.canTraverseBackward()); | 173 DCHECK(collection.canTraverseBackward()); |
| 170 NodeType* currentNode = collection.traverseBackwardToOffset(index, *cachedNo
de(), currentIndex); | 174 NodeType* currentNode = collection.traverseBackwardToOffset(index, *cachedNo
de(), currentIndex); |
| 171 ASSERT(currentNode); | 175 DCHECK(currentNode); |
| 172 setCachedNode(currentNode, currentIndex); | 176 setCachedNode(currentNode, currentIndex); |
| 173 return currentNode; | 177 return currentNode; |
| 174 } | 178 } |
| 175 | 179 |
| 176 template <typename Collection, typename NodeType> | 180 template <typename Collection, typename NodeType> |
| 177 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAfterCachedNode
(const Collection& collection, unsigned index) | 181 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAfterCachedNode
(const Collection& collection, unsigned index) |
| 178 { | 182 { |
| 179 ASSERT(cachedNode()); // Cache should be valid. | 183 DCHECK(cachedNode()); // Cache should be valid. |
| 180 unsigned currentIndex = cachedNodeIndex(); | 184 unsigned currentIndex = cachedNodeIndex(); |
| 181 ASSERT(currentIndex < index); | 185 DCHECK_LT(currentIndex, index); |
| 182 | 186 |
| 183 // Determine if we should traverse from the end of the collection instead of
the cached node. | 187 // Determine if we should traverse from the end of the collection instead of
the cached node. |
| 184 bool lastIsCloser = isCachedNodeCountValid() && cachedNodeCount() - index <
index - currentIndex; | 188 bool lastIsCloser = isCachedNodeCountValid() && cachedNodeCount() - index <
index - currentIndex; |
| 185 if (lastIsCloser && collection.canTraverseBackward()) { | 189 if (lastIsCloser && collection.canTraverseBackward()) { |
| 186 NodeType* lastItem = collection.traverseToLast(); | 190 NodeType* lastItem = collection.traverseToLast(); |
| 187 ASSERT(lastItem); | 191 DCHECK(lastItem); |
| 188 setCachedNode(lastItem, cachedNodeCount() - 1); | 192 setCachedNode(lastItem, cachedNodeCount() - 1); |
| 189 if (index < cachedNodeCount() - 1) | 193 if (index < cachedNodeCount() - 1) |
| 190 return nodeBeforeCachedNode(collection, index); | 194 return nodeBeforeCachedNode(collection, index); |
| 191 return lastItem; | 195 return lastItem; |
| 192 } | 196 } |
| 193 | 197 |
| 194 // Forward traversal from the cached node to the requested index. | 198 // Forward traversal from the cached node to the requested index. |
| 195 NodeType* currentNode = collection.traverseForwardToOffset(index, *cachedNod
e(), currentIndex); | 199 NodeType* currentNode = collection.traverseForwardToOffset(index, *cachedNod
e(), currentIndex); |
| 196 if (!currentNode) { | 200 if (!currentNode) { |
| 197 // Did not find the node. On plus side, we now know the length. | 201 // Did not find the node. On plus side, we now know the length. |
| 198 setCachedNodeCount(currentIndex + 1); | 202 setCachedNodeCount(currentIndex + 1); |
| 199 return nullptr; | 203 return nullptr; |
| 200 } | 204 } |
| 201 setCachedNode(currentNode, currentIndex); | 205 setCachedNode(currentNode, currentIndex); |
| 202 return currentNode; | 206 return currentNode; |
| 203 } | 207 } |
| 204 | 208 |
| 205 } // namespace blink | 209 } // namespace blink |
| 206 | 210 |
| 207 #endif // CollectionIndexCache_h | 211 #endif // CollectionIndexCache_h |
| OLD | NEW |