| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (C) 2013 Apple Inc. All rights reserved. | |
| 3 * Copyright (C) 2014 Samsung Electronics. All rights reserved. | |
| 4 * | |
| 5 * Redistribution and use in source and binary forms, with or without | |
| 6 * modification, are permitted provided that the following conditions are | |
| 7 * met: | |
| 8 * | |
| 9 * * Redistributions of source code must retain the above copyright | |
| 10 * notice, this list of conditions and the following disclaimer. | |
| 11 * * Redistributions in binary form must reproduce the above | |
| 12 * copyright notice, this list of conditions and the following disclaimer | |
| 13 * in the documentation and/or other materials provided with the | |
| 14 * distribution. | |
| 15 * * Neither the name of Google Inc. nor the names of its | |
| 16 * contributors may be used to endorse or promote products derived from | |
| 17 * this software without specific prior written permission. | |
| 18 * | |
| 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
| 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
| 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
| 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
| 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
| 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
| 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
| 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
| 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
| 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
| 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| 30 */ | |
| 31 | |
| 32 #ifndef CollectionIndexCache_h | |
| 33 #define CollectionIndexCache_h | |
| 34 | |
| 35 namespace blink { | |
| 36 | |
| 37 template <typename Collection, typename NodeType> | |
| 38 class CollectionIndexCache { | |
| 39 DISALLOW_NEW(); | |
| 40 | |
| 41 public: | |
| 42 CollectionIndexCache(); | |
| 43 | |
| 44 bool isEmpty(const Collection& collection) { | |
| 45 if (isCachedNodeCountValid()) | |
| 46 return !cachedNodeCount(); | |
| 47 if (cachedNode()) | |
| 48 return false; | |
| 49 return !nodeAt(collection, 0); | |
| 50 } | |
| 51 bool hasExactlyOneNode(const Collection& collection) { | |
| 52 if (isCachedNodeCountValid()) | |
| 53 return cachedNodeCount() == 1; | |
| 54 if (cachedNode()) | |
| 55 return !cachedNodeIndex() && !nodeAt(collection, 1); | |
| 56 return nodeAt(collection, 0) && !nodeAt(collection, 1); | |
| 57 } | |
| 58 | |
| 59 unsigned nodeCount(const Collection&); | |
| 60 NodeType* nodeAt(const Collection&, unsigned index); | |
| 61 | |
| 62 void invalidate(); | |
| 63 | |
| 64 DEFINE_INLINE_VIRTUAL_TRACE() { visitor->trace(m_currentNode); } | |
| 65 | |
| 66 protected: | |
| 67 ALWAYS_INLINE NodeType* cachedNode() const { return m_currentNode; } | |
| 68 ALWAYS_INLINE unsigned cachedNodeIndex() const { | |
| 69 DCHECK(cachedNode()); | |
| 70 return m_cachedNodeIndex; | |
| 71 } | |
| 72 ALWAYS_INLINE void setCachedNode(NodeType* node, unsigned index) { | |
| 73 DCHECK(node); | |
| 74 m_currentNode = node; | |
| 75 m_cachedNodeIndex = index; | |
| 76 } | |
| 77 | |
| 78 ALWAYS_INLINE bool isCachedNodeCountValid() const { | |
| 79 return m_isLengthCacheValid; | |
| 80 } | |
| 81 ALWAYS_INLINE unsigned cachedNodeCount() const { return m_cachedNodeCount; } | |
| 82 ALWAYS_INLINE void setCachedNodeCount(unsigned length) { | |
| 83 m_cachedNodeCount = length; | |
| 84 m_isLengthCacheValid = true; | |
| 85 } | |
| 86 | |
| 87 private: | |
| 88 NodeType* nodeBeforeCachedNode(const Collection&, unsigned index); | |
| 89 NodeType* nodeAfterCachedNode(const Collection&, unsigned index); | |
| 90 | |
| 91 Member<NodeType> m_currentNode; | |
| 92 unsigned m_cachedNodeCount; | |
| 93 unsigned m_cachedNodeIndex : 31; | |
| 94 unsigned m_isLengthCacheValid : 1; | |
| 95 }; | |
| 96 | |
| 97 template <typename Collection, typename NodeType> | |
| 98 CollectionIndexCache<Collection, NodeType>::CollectionIndexCache() | |
| 99 : m_currentNode(nullptr), | |
| 100 m_cachedNodeCount(0), | |
| 101 m_cachedNodeIndex(0), | |
| 102 m_isLengthCacheValid(false) {} | |
| 103 | |
| 104 template <typename Collection, typename NodeType> | |
| 105 void CollectionIndexCache<Collection, NodeType>::invalidate() { | |
| 106 m_currentNode = nullptr; | |
| 107 m_isLengthCacheValid = false; | |
| 108 } | |
| 109 | |
| 110 template <typename Collection, typename NodeType> | |
| 111 inline unsigned CollectionIndexCache<Collection, NodeType>::nodeCount( | |
| 112 const Collection& collection) { | |
| 113 if (isCachedNodeCountValid()) | |
| 114 return cachedNodeCount(); | |
| 115 | |
| 116 nodeAt(collection, UINT_MAX); | |
| 117 DCHECK(isCachedNodeCountValid()); | |
| 118 | |
| 119 return cachedNodeCount(); | |
| 120 } | |
| 121 | |
| 122 template <typename Collection, typename NodeType> | |
| 123 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAt( | |
| 124 const Collection& collection, | |
| 125 unsigned index) { | |
| 126 if (isCachedNodeCountValid() && index >= cachedNodeCount()) | |
| 127 return nullptr; | |
| 128 | |
| 129 if (cachedNode()) { | |
| 130 if (index > cachedNodeIndex()) | |
| 131 return nodeAfterCachedNode(collection, index); | |
| 132 if (index < cachedNodeIndex()) | |
| 133 return nodeBeforeCachedNode(collection, index); | |
| 134 return cachedNode(); | |
| 135 } | |
| 136 | |
| 137 // No valid cache yet, let's find the first matching element. | |
| 138 DCHECK(!isCachedNodeCountValid()); | |
| 139 NodeType* firstNode = collection.traverseToFirst(); | |
| 140 if (!firstNode) { | |
| 141 // The collection is empty. | |
| 142 setCachedNodeCount(0); | |
| 143 return nullptr; | |
| 144 } | |
| 145 setCachedNode(firstNode, 0); | |
| 146 return index ? nodeAfterCachedNode(collection, index) : firstNode; | |
| 147 } | |
| 148 | |
| 149 template <typename Collection, typename NodeType> | |
| 150 inline NodeType* | |
| 151 CollectionIndexCache<Collection, NodeType>::nodeBeforeCachedNode( | |
| 152 const Collection& collection, | |
| 153 unsigned index) { | |
| 154 DCHECK(cachedNode()); // Cache should be valid. | |
| 155 unsigned currentIndex = cachedNodeIndex(); | |
| 156 DCHECK_GT(currentIndex, index); | |
| 157 | |
| 158 // Determine if we should traverse from the beginning of the collection | |
| 159 // instead of the cached node. | |
| 160 bool firstIsCloser = index < currentIndex - index; | |
| 161 if (firstIsCloser || !collection.canTraverseBackward()) { | |
| 162 NodeType* firstNode = collection.traverseToFirst(); | |
| 163 DCHECK(firstNode); | |
| 164 setCachedNode(firstNode, 0); | |
| 165 return index ? nodeAfterCachedNode(collection, index) : firstNode; | |
| 166 } | |
| 167 | |
| 168 // Backward traversal from the cached node to the requested index. | |
| 169 DCHECK(collection.canTraverseBackward()); | |
| 170 NodeType* currentNode = | |
| 171 collection.traverseBackwardToOffset(index, *cachedNode(), currentIndex); | |
| 172 DCHECK(currentNode); | |
| 173 setCachedNode(currentNode, currentIndex); | |
| 174 return currentNode; | |
| 175 } | |
| 176 | |
| 177 template <typename Collection, typename NodeType> | |
| 178 inline NodeType* | |
| 179 CollectionIndexCache<Collection, NodeType>::nodeAfterCachedNode( | |
| 180 const Collection& collection, | |
| 181 unsigned index) { | |
| 182 DCHECK(cachedNode()); // Cache should be valid. | |
| 183 unsigned currentIndex = cachedNodeIndex(); | |
| 184 DCHECK_LT(currentIndex, index); | |
| 185 | |
| 186 // Determine if we should traverse from the end of the collection instead of | |
| 187 // the cached node. | |
| 188 bool lastIsCloser = isCachedNodeCountValid() && | |
| 189 cachedNodeCount() - index < index - currentIndex; | |
| 190 if (lastIsCloser && collection.canTraverseBackward()) { | |
| 191 NodeType* lastItem = collection.traverseToLast(); | |
| 192 DCHECK(lastItem); | |
| 193 setCachedNode(lastItem, cachedNodeCount() - 1); | |
| 194 if (index < cachedNodeCount() - 1) | |
| 195 return nodeBeforeCachedNode(collection, index); | |
| 196 return lastItem; | |
| 197 } | |
| 198 | |
| 199 // Forward traversal from the cached node to the requested index. | |
| 200 NodeType* currentNode = | |
| 201 collection.traverseForwardToOffset(index, *cachedNode(), currentIndex); | |
| 202 if (!currentNode) { | |
| 203 // Did not find the node. On plus side, we now know the length. | |
| 204 if (isCachedNodeCountValid()) | |
| 205 DCHECK_EQ(currentIndex + 1, cachedNodeCount()); | |
| 206 setCachedNodeCount(currentIndex + 1); | |
| 207 return nullptr; | |
| 208 } | |
| 209 setCachedNode(currentNode, currentIndex); | |
| 210 return currentNode; | |
| 211 } | |
| 212 | |
| 213 } // namespace blink | |
| 214 | |
| 215 #endif // CollectionIndexCache_h | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2397233003:
Move CollectionIndexCache.h from core/html/ to core/dom/. (Closed)
