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