src/third_party/WebKit/Source/core/html/CollectionIndexCache.h

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