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 | |
30 | namespace WebCore { |
31 | |
32 | WEBCORE_EXPORT void (size_t); |
33 | |
34 | template <class Collection, class Iterator> |
35 | class CollectionIndexCache { |
36 | public: |
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 | |
54 | private: |
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 | |
67 | template <class Collection, class Iterator> |
68 | inline 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 | |
77 | template <class Collection, class Iterator> |
78 | inline 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 | |
90 | template <class Collection, class Iterator> |
91 | unsigned 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 | |
113 | template <class Collection, class Iterator> |
114 | inline 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 | |
136 | template <class Collection, class Iterator> |
137 | inline 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 | |
172 | template <class Collection, class Iterator> |
173 | inline 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 | |
221 | template <class Collection, class Iterator> |
222 | void 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 | |