| 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 137 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 148 | 148 |
| 149 template <typename Collection, typename NodeType> | 149 template <typename Collection, typename NodeType> |
| 150 inline NodeType* | 150 inline NodeType* |
| 151 CollectionIndexCache<Collection, NodeType>::nodeBeforeCachedNode( | 151 CollectionIndexCache<Collection, NodeType>::nodeBeforeCachedNode( |
| 152 const Collection& collection, | 152 const Collection& collection, |
| 153 unsigned index) { | 153 unsigned index) { |
| 154 DCHECK(cachedNode()); // Cache should be valid. | 154 DCHECK(cachedNode()); // Cache should be valid. |
| 155 unsigned currentIndex = cachedNodeIndex(); | 155 unsigned currentIndex = cachedNodeIndex(); |
| 156 DCHECK_GT(currentIndex, index); | 156 DCHECK_GT(currentIndex, index); |
| 157 | 157 |
| 158 // Determine if we should traverse from the beginning of the collection instea
d of the cached node. | 158 // Determine if we should traverse from the beginning of the collection |
| 159 // instead of the cached node. |
| 159 bool firstIsCloser = index < currentIndex - index; | 160 bool firstIsCloser = index < currentIndex - index; |
| 160 if (firstIsCloser || !collection.canTraverseBackward()) { | 161 if (firstIsCloser || !collection.canTraverseBackward()) { |
| 161 NodeType* firstNode = collection.traverseToFirst(); | 162 NodeType* firstNode = collection.traverseToFirst(); |
| 162 DCHECK(firstNode); | 163 DCHECK(firstNode); |
| 163 setCachedNode(firstNode, 0); | 164 setCachedNode(firstNode, 0); |
| 164 return index ? nodeAfterCachedNode(collection, index) : firstNode; | 165 return index ? nodeAfterCachedNode(collection, index) : firstNode; |
| 165 } | 166 } |
| 166 | 167 |
| 167 // Backward traversal from the cached node to the requested index. | 168 // Backward traversal from the cached node to the requested index. |
| 168 DCHECK(collection.canTraverseBackward()); | 169 DCHECK(collection.canTraverseBackward()); |
| 169 NodeType* currentNode = | 170 NodeType* currentNode = |
| 170 collection.traverseBackwardToOffset(index, *cachedNode(), currentIndex); | 171 collection.traverseBackwardToOffset(index, *cachedNode(), currentIndex); |
| 171 DCHECK(currentNode); | 172 DCHECK(currentNode); |
| 172 setCachedNode(currentNode, currentIndex); | 173 setCachedNode(currentNode, currentIndex); |
| 173 return currentNode; | 174 return currentNode; |
| 174 } | 175 } |
| 175 | 176 |
| 176 template <typename Collection, typename NodeType> | 177 template <typename Collection, typename NodeType> |
| 177 inline NodeType* | 178 inline NodeType* |
| 178 CollectionIndexCache<Collection, NodeType>::nodeAfterCachedNode( | 179 CollectionIndexCache<Collection, NodeType>::nodeAfterCachedNode( |
| 179 const Collection& collection, | 180 const Collection& collection, |
| 180 unsigned index) { | 181 unsigned index) { |
| 181 DCHECK(cachedNode()); // Cache should be valid. | 182 DCHECK(cachedNode()); // Cache should be valid. |
| 182 unsigned currentIndex = cachedNodeIndex(); | 183 unsigned currentIndex = cachedNodeIndex(); |
| 183 DCHECK_LT(currentIndex, index); | 184 DCHECK_LT(currentIndex, index); |
| 184 | 185 |
| 185 // Determine if we should traverse from the end of the collection instead of t
he cached node. | 186 // Determine if we should traverse from the end of the collection instead of |
| 187 // the cached node. |
| 186 bool lastIsCloser = isCachedNodeCountValid() && | 188 bool lastIsCloser = isCachedNodeCountValid() && |
| 187 cachedNodeCount() - index < index - currentIndex; | 189 cachedNodeCount() - index < index - currentIndex; |
| 188 if (lastIsCloser && collection.canTraverseBackward()) { | 190 if (lastIsCloser && collection.canTraverseBackward()) { |
| 189 NodeType* lastItem = collection.traverseToLast(); | 191 NodeType* lastItem = collection.traverseToLast(); |
| 190 DCHECK(lastItem); | 192 DCHECK(lastItem); |
| 191 setCachedNode(lastItem, cachedNodeCount() - 1); | 193 setCachedNode(lastItem, cachedNodeCount() - 1); |
| 192 if (index < cachedNodeCount() - 1) | 194 if (index < cachedNodeCount() - 1) |
| 193 return nodeBeforeCachedNode(collection, index); | 195 return nodeBeforeCachedNode(collection, index); |
| 194 return lastItem; | 196 return lastItem; |
| 195 } | 197 } |
| 196 | 198 |
| 197 // Forward traversal from the cached node to the requested index. | 199 // Forward traversal from the cached node to the requested index. |
| 198 NodeType* currentNode = | 200 NodeType* currentNode = |
| 199 collection.traverseForwardToOffset(index, *cachedNode(), currentIndex); | 201 collection.traverseForwardToOffset(index, *cachedNode(), currentIndex); |
| 200 if (!currentNode) { | 202 if (!currentNode) { |
| 201 // Did not find the node. On plus side, we now know the length. | 203 // Did not find the node. On plus side, we now know the length. |
| 202 setCachedNodeCount(currentIndex + 1); | 204 setCachedNodeCount(currentIndex + 1); |
| 203 return nullptr; | 205 return nullptr; |
| 204 } | 206 } |
| 205 setCachedNode(currentNode, currentIndex); | 207 setCachedNode(currentNode, currentIndex); |
| 206 return currentNode; | 208 return currentNode; |
| 207 } | 209 } |
| 208 | 210 |
| 209 } // namespace blink | 211 } // namespace blink |
| 210 | 212 |
| 211 #endif // CollectionIndexCache_h | 213 #endif // CollectionIndexCache_h |
| OLD | NEW |