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 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 nullptr;
 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 nullptr;
 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 nullptr;
 200     }
 201     setCachedNode(currentNode, currentIndex);
 202     return currentNode;
 203 }
 204
 205 } // namespace blink
 206
 207 #endif // CollectionIndexCache_h