1/*
2 * Copyright (C) 2013-2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/Vector.h>
29
30namespace WebCore {
31
32WEBCORE_EXPORT void reportExtraMemoryAllocatedForCollectionIndexCache(size_t);
33
34template <class Collection, class Iterator>
35class CollectionIndexCache {
36public:
37 explicit CollectionIndexCache(const Collection&);
38
39 typedef typename std::iterator_traits<Iterator>::value_type NodeType;
40
41 unsigned nodeCount(const Collection&);
42 NodeType* nodeAt(const Collection&, unsigned index);
43
44 bool hasValidCache(const Collection& collection) const { return m_current != collection.collectionEnd() || m_nodeCountValid || m_listValid; }
45 void invalidate(const Collection&);
46 size_t memoryCost()
47 {
48 // memoryCost() may be invoked concurrently from a GC thread, and we need to be careful
49 // about what data we access here and how. Accessing m_cachedList.capacity() is safe
50 // because it doesn't involve any pointer chasing.
51 return m_cachedList.capacity() * sizeof(NodeType*);
52 }
53
54private:
55 unsigned computeNodeCountUpdatingListCache(const Collection&);
56 NodeType* traverseBackwardTo(const Collection&, unsigned);
57 NodeType* traverseForwardTo(const Collection&, unsigned);
58
59 Iterator m_current;
60 unsigned m_currentIndex;
61 unsigned m_nodeCount;
62 Vector<NodeType*> m_cachedList;
63 bool m_nodeCountValid : 1;
64 bool m_listValid : 1;
65};
66
67template <class Collection, class Iterator>
68inline CollectionIndexCache<Collection, Iterator>::CollectionIndexCache(const Collection& collection)
69 : m_current(collection.collectionEnd())
70 , m_currentIndex(0)
71 , m_nodeCount(0)
72 , m_nodeCountValid(false)
73 , m_listValid(false)
74{
75}
76
77template <class Collection, class Iterator>
78inline unsigned CollectionIndexCache<Collection, Iterator>::nodeCount(const Collection& collection)
79{
80 if (!m_nodeCountValid) {
81 if (!hasValidCache(collection))
82 collection.willValidateIndexCache();
83 m_nodeCount = computeNodeCountUpdatingListCache(collection);
84 m_nodeCountValid = true;
85 }
86
87 return m_nodeCount;
88}
89
90template <class Collection, class Iterator>
91unsigned CollectionIndexCache<Collection, Iterator>::computeNodeCountUpdatingListCache(const Collection& collection)
92{
93 auto current = collection.collectionBegin();
94 auto end = collection.collectionEnd();
95 if (current == end)
96 return 0;
97
98 unsigned oldCapacity = m_cachedList.capacity();
99 while (current != end) {
100 m_cachedList.append(&*current);
101 unsigned traversed;
102 collection.collectionTraverseForward(current, 1, traversed);
103 ASSERT(traversed == (current != end ? 1 : 0));
104 }
105 m_listValid = true;
106
107 if (unsigned capacityDifference = m_cachedList.capacity() - oldCapacity)
108 reportExtraMemoryAllocatedForCollectionIndexCache(capacityDifference * sizeof(NodeType*));
109
110 return m_cachedList.size();
111}
112
113template <class Collection, class Iterator>
114inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::traverseBackwardTo(const Collection& collection, unsigned index)
115{
116 ASSERT(m_current != collection.collectionEnd());
117 ASSERT(index < m_currentIndex);
118
119 bool firstIsCloser = index < m_currentIndex - index;
120 if (firstIsCloser || !collection.collectionCanTraverseBackward()) {
121 m_current = collection.collectionBegin();
122 m_currentIndex = 0;
123 if (index)
124 collection.collectionTraverseForward(m_current, index, m_currentIndex);
125 ASSERT(m_current != collection.collectionEnd());
126 return &*m_current;
127 }
128
129 collection.collectionTraverseBackward(m_current, m_currentIndex - index);
130 m_currentIndex = index;
131
132 ASSERT(m_current != collection.collectionEnd());
133 return &*m_current;
134}
135
136template <class Collection, class Iterator>
137inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::traverseForwardTo(const Collection& collection, unsigned index)
138{
139 ASSERT(m_current != collection.collectionEnd());
140 ASSERT(index > m_currentIndex);
141 ASSERT(!m_nodeCountValid || index < m_nodeCount);
142
143 bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index - m_currentIndex;
144 if (lastIsCloser && collection.collectionCanTraverseBackward()) {
145 ASSERT(hasValidCache(collection));
146 m_current = collection.collectionLast();
147 if (index < m_nodeCount - 1)
148 collection.collectionTraverseBackward(m_current, m_nodeCount - index - 1);
149 m_currentIndex = index;
150 ASSERT(m_current != collection.collectionEnd());
151 return &*m_current;
152 }
153
154 if (!hasValidCache(collection))
155 collection.willValidateIndexCache();
156
157 unsigned traversedCount;
158 collection.collectionTraverseForward(m_current, index - m_currentIndex, traversedCount);
159 m_currentIndex = m_currentIndex + traversedCount;
160
161 if (m_current == collection.collectionEnd()) {
162 ASSERT(m_currentIndex < index);
163 // Failed to find the index but at least we now know the size.
164 m_nodeCount = m_currentIndex + 1;
165 m_nodeCountValid = true;
166 return nullptr;
167 }
168 ASSERT(hasValidCache(collection));
169 return &*m_current;
170}
171
172template <class Collection, class Iterator>
173inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::nodeAt(const Collection& collection, unsigned index)
174{
175 if (m_nodeCountValid && index >= m_nodeCount)
176 return nullptr;
177
178 if (m_listValid)
179 return m_cachedList[index];
180
181 auto end = collection.collectionEnd();
182 if (m_current != end) {
183 if (index > m_currentIndex)
184 return traverseForwardTo(collection, index);
185 if (index < m_currentIndex)
186 return traverseBackwardTo(collection, index);
187 return &*m_current;
188 }
189
190 bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index;
191 if (lastIsCloser && collection.collectionCanTraverseBackward()) {
192 ASSERT(hasValidCache(collection));
193 m_current = collection.collectionLast();
194 if (index < m_nodeCount - 1)
195 collection.collectionTraverseBackward(m_current, m_nodeCount - index - 1);
196 m_currentIndex = index;
197 ASSERT(m_current != end);
198 return &*m_current;
199 }
200
201 if (!hasValidCache(collection))
202 collection.willValidateIndexCache();
203
204 m_current = collection.collectionBegin();
205 m_currentIndex = 0;
206 bool startIsEnd = m_current == end;
207 if (index && !startIsEnd) {
208 collection.collectionTraverseForward(m_current, index, m_currentIndex);
209 ASSERT(m_current != end || m_currentIndex < index);
210 }
211 if (m_current == end) {
212 // Failed to find the index but at least we now know the size.
213 m_nodeCount = startIsEnd ? 0 : m_currentIndex + 1;
214 m_nodeCountValid = true;
215 return nullptr;
216 }
217 ASSERT(hasValidCache(collection));
218 return &*m_current;
219}
220
221template <class Collection, class Iterator>
222void CollectionIndexCache<Collection, Iterator>::invalidate(const Collection& collection)
223{
224 m_current = collection.collectionEnd();
225 m_nodeCountValid = false;
226 m_listValid = false;
227 m_cachedList.shrink(0);
228}
229
230
231}
232