109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)/* 209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * Copyright (C) 2013 Apple Inc. All rights reserved. 309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * Copyright (C) 2014 Samsung Electronics. All rights reserved. 409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * 509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * modification, are permitted provided that the following conditions are 709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * met: 809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * 909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * * Redistributions of source code must retain the above copyright 1009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 1109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * * Redistributions in binary form must reproduce the above 1209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * copyright notice, this list of conditions and the following disclaimer 1309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * in the documentation and/or other materials provided with the 1409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * distribution. 1509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * * Neither the name of Google Inc. nor the names of its 1609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * contributors may be used to endorse or promote products derived from 1709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * this software without specific prior written permission. 1809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * 1909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) */ 3109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 3209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#ifndef CollectionIndexCache_h 3309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#define CollectionIndexCache_h 3409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 35c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 3609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 3709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template <typename Collection, typename NodeType> 3809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)class CollectionIndexCache { 39d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) DISALLOW_ALLOCATION(); 4009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)public: 4109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) CollectionIndexCache(); 4209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 4309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool isEmpty(const Collection& collection) 4409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 4509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (isCachedNodeCountValid()) 4609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return !cachedNodeCount(); 4709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (cachedNode()) 4809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return false; 4909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return !nodeAt(collection, 0); 5009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 5109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool hasExactlyOneNode(const Collection& collection) 5209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 5309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (isCachedNodeCountValid()) 5409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return cachedNodeCount() == 1; 5509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (cachedNode()) 5609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return !cachedNodeIndex() && !nodeAt(collection, 1); 5709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return nodeAt(collection, 0) && !nodeAt(collection, 1); 5809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 5909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 6009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) unsigned nodeCount(const Collection&); 6109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) NodeType* nodeAt(const Collection&, unsigned index); 6209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 6309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void invalidate(); 6409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 65d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) void trace(Visitor* visitor) 66d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) { 67d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) visitor->trace(m_currentNode); 68d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) } 69d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) 707242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucciprotected: 7109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ALWAYS_INLINE NodeType* cachedNode() const { return m_currentNode; } 7209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ALWAYS_INLINE unsigned cachedNodeIndex() const { ASSERT(cachedNode()); return m_cachedNodeIndex; } 7309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ALWAYS_INLINE void setCachedNode(NodeType* node, unsigned index) 7409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 7509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(node); 7609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) m_currentNode = node; 7709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) m_cachedNodeIndex = index; 7809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 7909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 8009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ALWAYS_INLINE bool isCachedNodeCountValid() const { return m_isLengthCacheValid; } 8109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ALWAYS_INLINE unsigned cachedNodeCount() const { return m_cachedNodeCount; } 8209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ALWAYS_INLINE void setCachedNodeCount(unsigned length) 8309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 8409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) m_cachedNodeCount = length; 8509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) m_isLengthCacheValid = true; 8609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 8709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 887242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucciprivate: 897242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci NodeType* nodeBeforeCachedNode(const Collection&, unsigned index); 907242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci NodeType* nodeAfterCachedNode(const Collection&, unsigned index); 917242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci 92d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) RawPtrWillBeMember<NodeType> m_currentNode; 9309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) unsigned m_cachedNodeCount; 94197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch unsigned m_cachedNodeIndex : 31; 9509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) unsigned m_isLengthCacheValid : 1; 9609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}; 9709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 9809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template <typename Collection, typename NodeType> 9909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)CollectionIndexCache<Collection, NodeType>::CollectionIndexCache() 100d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) : m_currentNode(nullptr) 10109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) , m_cachedNodeCount(0) 10209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) , m_cachedNodeIndex(0) 10309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) , m_isLengthCacheValid(false) 10409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 10509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 10609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 10709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template <typename Collection, typename NodeType> 10809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void CollectionIndexCache<Collection, NodeType>::invalidate() 10909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 110d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) m_currentNode = nullptr; 11109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) m_isLengthCacheValid = false; 11209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 11309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 11409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template <typename Collection, typename NodeType> 11509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)inline unsigned CollectionIndexCache<Collection, NodeType>::nodeCount(const Collection& collection) 11609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 11709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (isCachedNodeCountValid()) 11809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return cachedNodeCount(); 11909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 12009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) nodeAt(collection, UINT_MAX); 12109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(isCachedNodeCountValid()); 12209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 12309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return cachedNodeCount(); 12409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 12509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 12609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template <typename Collection, typename NodeType> 12709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAt(const Collection& collection, unsigned index) 12809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 12909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (isCachedNodeCountValid() && index >= cachedNodeCount()) 13009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return 0; 13109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 13209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (cachedNode()) { 13309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (index > cachedNodeIndex()) 134a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch return nodeAfterCachedNode(collection, index); 13509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (index < cachedNodeIndex()) 136a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch return nodeBeforeCachedNode(collection, index); 13709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return cachedNode(); 13809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 13909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 14009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // No valid cache yet, let's find the first matching element. 14109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!isCachedNodeCountValid()); 1429e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles) NodeType* firstNode = collection.traverseToFirst(); 14309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (!firstNode) { 14409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // The collection is empty. 14509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) setCachedNodeCount(0); 14609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return 0; 14709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 14809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) setCachedNode(firstNode, 0); 149a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch return index ? nodeAfterCachedNode(collection, index) : firstNode; 15009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 15109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 15209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template <typename Collection, typename NodeType> 153a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdochinline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeCachedNode(const Collection& collection, unsigned index) 15409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 15509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(cachedNode()); // Cache should be valid. 15609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) unsigned currentIndex = cachedNodeIndex(); 15709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(currentIndex > index); 15809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 15909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Determine if we should traverse from the beginning of the collection instead of the cached node. 16009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool firstIsCloser = index < currentIndex - index; 16109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (firstIsCloser || !collection.canTraverseBackward()) { 1629e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles) NodeType* firstNode = collection.traverseToFirst(); 16309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(firstNode); 16409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) setCachedNode(firstNode, 0); 165a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch return index ? nodeAfterCachedNode(collection, index) : firstNode; 16609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 16709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 16809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Backward traversal from the cached node to the requested index. 16909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(collection.canTraverseBackward()); 1706f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch NodeType* currentNode = collection.traverseBackwardToOffset(index, *cachedNode(), currentIndex); 1716f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(currentNode); 1726f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch setCachedNode(currentNode, currentIndex); 1736f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return currentNode; 17409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 17509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 17609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template <typename Collection, typename NodeType> 177a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdochinline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAfterCachedNode(const Collection& collection, unsigned index) 17809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 17909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(cachedNode()); // Cache should be valid. 18009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) unsigned currentIndex = cachedNodeIndex(); 18109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(currentIndex < index); 18209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 18309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Determine if we should traverse from the end of the collection instead of the cached node. 18409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool lastIsCloser = isCachedNodeCountValid() && cachedNodeCount() - index < index - currentIndex; 18509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (lastIsCloser && collection.canTraverseBackward()) { 1869e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles) NodeType* lastItem = collection.traverseToLast(); 18709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(lastItem); 18809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) setCachedNode(lastItem, cachedNodeCount() - 1); 18909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (index < cachedNodeCount() - 1) 190a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch return nodeBeforeCachedNode(collection, index); 19109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return lastItem; 19209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 19309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 19409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Forward traversal from the cached node to the requested index. 195a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch NodeType* currentNode = collection.traverseForwardToOffset(index, *cachedNode(), currentIndex); 19609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (!currentNode) { 19709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Did not find the node. On plus side, we now know the length. 19809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) setCachedNodeCount(currentIndex + 1); 19909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return 0; 20009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 20109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) setCachedNode(currentNode, currentIndex); 20209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return currentNode; 20309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 20409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 205c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)} // namespace blink 20609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 20709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif // CollectionIndexCache_h 208