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
35namespace blink {
36
37template <typename Collection, typename NodeType>
38class CollectionIndexCache {
39    DISALLOW_ALLOCATION();
40public:
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
70protected:
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
88private:
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
98template <typename Collection, typename NodeType>
99CollectionIndexCache<Collection, NodeType>::CollectionIndexCache()
100    : m_currentNode(nullptr)
101    , m_cachedNodeCount(0)
102    , m_cachedNodeIndex(0)
103    , m_isLengthCacheValid(false)
104{
105}
106
107template <typename Collection, typename NodeType>
108void CollectionIndexCache<Collection, NodeType>::invalidate()
109{
110    m_currentNode = nullptr;
111    m_isLengthCacheValid = false;
112}
113
114template <typename Collection, typename NodeType>
115inline 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
126template <typename Collection, typename NodeType>
127inline 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
152template <typename Collection, typename NodeType>
153inline 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
176template <typename Collection, typename NodeType>
177inline 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