Delete WebMetal implementation in favor of WebGPU
[WebKit-https.git] / Source / WebCore / dom / CollectionIndexCache.h
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 reportExtraMemoryAllocatedForCollectionIndexCache(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 }