Home | History | Annotate | Download | only in html 
      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_ALLOCATION();
     40 public:
     41     CollectionIndexCache();
     42 
     43     bool isEmpty(const Collection& collection)
     44     {
     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     {
     53         if (isCachedNodeCountValid())
     54             return cachedNodeCount() == 1;
     55         if (cachedNode())
     56             return !cachedNodeIndex() && !nodeAt(collection, 1);
     57         return nodeAt(collection, 0) && !nodeAt(collection, 1);
     58     }
     59 
     60     unsigned nodeCount(const Collection&);
     61     NodeType* nodeAt(const Collection&, unsigned index);
     62 
     63     void invalidate();
     64 
     65     void trace(Visitor* visitor)
     66     {
     67         visitor->trace(m_currentNode);
     68     }
     69 
     70 protected:
     71     ALWAYS_INLINE NodeType* cachedNode() const { return m_currentNode; }
     72     ALWAYS_INLINE unsigned cachedNodeIndex() const { ASSERT(cachedNode()); return m_cachedNodeIndex; }
     73     ALWAYS_INLINE void setCachedNode(NodeType* node, unsigned index)
     74     {
     75         ASSERT(node);
     76         m_currentNode = node;
     77         m_cachedNodeIndex = index;
     78     }
     79 
     80     ALWAYS_INLINE bool isCachedNodeCountValid() const { return m_isLengthCacheValid; }
     81     ALWAYS_INLINE unsigned cachedNodeCount() const { return m_cachedNodeCount; }
     82     ALWAYS_INLINE void setCachedNodeCount(unsigned length)
     83     {
     84         m_cachedNodeCount = length;
     85         m_isLengthCacheValid = true;
     86     }
     87 
     88 private:
     89     NodeType* nodeBeforeCachedNode(const Collection&, unsigned index);
     90     NodeType* nodeAfterCachedNode(const Collection&, unsigned index);
     91 
     92     RawPtrWillBeMember<NodeType> m_currentNode;
     93     unsigned m_cachedNodeCount;
     94     unsigned m_cachedNodeIndex : 31;
     95     unsigned m_isLengthCacheValid : 1;
     96 };
     97 
     98 template <typename Collection, typename NodeType>
     99 CollectionIndexCache<Collection, NodeType>::CollectionIndexCache()
    100     : m_currentNode(nullptr)
    101     , m_cachedNodeCount(0)
    102     , m_cachedNodeIndex(0)
    103     , m_isLengthCacheValid(false)
    104 {
    105 }
    106 
    107 template <typename Collection, typename NodeType>
    108 void CollectionIndexCache<Collection, NodeType>::invalidate()
    109 {
    110     m_currentNode = nullptr;
    111     m_isLengthCacheValid = false;
    112 }
    113 
    114 template <typename Collection, typename NodeType>
    115 inline unsigned CollectionIndexCache<Collection, NodeType>::nodeCount(const Collection& collection)
    116 {
    117     if (isCachedNodeCountValid())
    118         return cachedNodeCount();
    119 
    120     nodeAt(collection, UINT_MAX);
    121     ASSERT(isCachedNodeCountValid());
    122 
    123     return cachedNodeCount();
    124 }
    125 
    126 template <typename Collection, typename NodeType>
    127 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAt(const Collection& collection, unsigned index)
    128 {
    129     if (isCachedNodeCountValid() && index >= cachedNodeCount())
    130         return 0;
    131 
    132     if (cachedNode()) {
    133         if (index > cachedNodeIndex())
    134             return nodeAfterCachedNode(collection, index);
    135         if (index < cachedNodeIndex())
    136             return nodeBeforeCachedNode(collection, index);
    137         return cachedNode();
    138     }
    139 
    140     // No valid cache yet, let's find the first matching element.
    141     ASSERT(!isCachedNodeCountValid());
    142     NodeType* firstNode = collection.traverseToFirst();
    143     if (!firstNode) {
    144         // The collection is empty.
    145         setCachedNodeCount(0);
    146         return 0;
    147     }
    148     setCachedNode(firstNode, 0);
    149     return index ? nodeAfterCachedNode(collection, index) : firstNode;
    150 }
    151 
    152 template <typename Collection, typename NodeType>
    153 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeCachedNode(const Collection& collection, unsigned index)
    154 {
    155     ASSERT(cachedNode()); // Cache should be valid.
    156     unsigned currentIndex = cachedNodeIndex();
    157     ASSERT(currentIndex > index);
    158 
    159     // Determine if we should traverse from the beginning of the collection instead of the cached node.
    160     bool firstIsCloser = index < currentIndex - index;
    161     if (firstIsCloser || !collection.canTraverseBackward()) {
    162         NodeType* firstNode = collection.traverseToFirst();
    163         ASSERT(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     ASSERT(collection.canTraverseBackward());
    170     NodeType* currentNode = collection.traverseBackwardToOffset(index, *cachedNode(), currentIndex);
    171     ASSERT(currentNode);
    172     setCachedNode(currentNode, currentIndex);
    173     return currentNode;
    174 }
    175 
    176 template <typename Collection, typename NodeType>
    177 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAfterCachedNode(const Collection& collection, unsigned index)
    178 {
    179     ASSERT(cachedNode()); // Cache should be valid.
    180     unsigned currentIndex = cachedNodeIndex();
    181     ASSERT(currentIndex < index);
    182 
    183     // Determine if we should traverse from the end of the collection instead of the cached node.
    184     bool lastIsCloser = isCachedNodeCountValid() && cachedNodeCount() - index < index - currentIndex;
    185     if (lastIsCloser && collection.canTraverseBackward()) {
    186         NodeType* lastItem = collection.traverseToLast();
    187         ASSERT(lastItem);
    188         setCachedNode(lastItem, cachedNodeCount() - 1);
    189         if (index < cachedNodeCount() - 1)
    190             return nodeBeforeCachedNode(collection, index);
    191         return lastItem;
    192     }
    193 
    194     // Forward traversal from the cached node to the requested index.
    195     NodeType* currentNode = collection.traverseForwardToOffset(index, *cachedNode(), currentIndex);
    196     if (!currentNode) {
    197         // Did not find the node. On plus side, we now know the length.
    198         setCachedNodeCount(currentIndex + 1);
    199         return 0;
    200     }
    201     setCachedNode(currentNode, currentIndex);
    202     return currentNode;
    203 }
    204 
    205 } // namespace blink
    206 
    207 #endif // CollectionIndexCache_h
    208