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
isEmpty(const Collection & collection)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 }
hasExactlyOneNode(const Collection & collection)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
trace(Visitor * visitor)65 void trace(Visitor* visitor)
66 {
67 visitor->trace(m_currentNode);
68 }
69
70 protected:
cachedNode()71 ALWAYS_INLINE NodeType* cachedNode() const { return m_currentNode; }
cachedNodeIndex()72 ALWAYS_INLINE unsigned cachedNodeIndex() const { ASSERT(cachedNode()); return m_cachedNodeIndex; }
setCachedNode(NodeType * node,unsigned index)73 ALWAYS_INLINE void setCachedNode(NodeType* node, unsigned index)
74 {
75 ASSERT(node);
76 m_currentNode = node;
77 m_cachedNodeIndex = index;
78 }
79
isCachedNodeCountValid()80 ALWAYS_INLINE bool isCachedNodeCountValid() const { return m_isLengthCacheValid; }
cachedNodeCount()81 ALWAYS_INLINE unsigned cachedNodeCount() const { return m_cachedNodeCount; }
setCachedNodeCount(unsigned length)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>
CollectionIndexCache()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>
invalidate()108 void CollectionIndexCache<Collection, NodeType>::invalidate()
109 {
110 m_currentNode = nullptr;
111 m_isLengthCacheValid = false;
112 }
113
114 template <typename Collection, typename NodeType>
nodeCount(const Collection & collection)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>
nodeAt(const Collection & collection,unsigned index)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>
nodeBeforeCachedNode(const Collection & collection,unsigned index)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>
nodeAfterCachedNode(const Collection & collection,unsigned index)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