Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / ConcurrentVector.h
1 /*
2  * Copyright (C) 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  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #ifndef ConcurrentVector_h
30 #define ConcurrentVector_h
31
32 #include <wtf/ConcurrentBuffer.h>
33 #include <wtf/Noncopyable.h>
34
35 namespace WTF {
36
37 // An iterator for ConcurrentVector. It supports only the pre ++ operator
38 template <typename T, size_t SegmentSize = 8> class ConcurrentVector;
39 template <typename T, size_t SegmentSize = 8> class ConcurrentVectorIterator {
40 private:
41     friend class ConcurrentVector<T, SegmentSize>;
42 public:
43     typedef ConcurrentVectorIterator<T, SegmentSize> Iterator;
44
45     ~ConcurrentVectorIterator() { }
46
47     T& operator*() const { return m_vector.at(m_index); }
48     T* operator->() const { return &m_vector.at(m_index); }
49
50     // Only prefix ++ operator supported
51     Iterator& operator++()
52     {
53         m_index++;
54         return *this;
55     }
56
57     bool operator==(const Iterator& other) const
58     {
59         return m_index == other.m_index && &m_vector == &other.m_vector;
60     }
61
62     bool operator!=(const Iterator& other) const
63     {
64         return m_index != other.m_index || &m_vector != &other.m_vector;
65     }
66
67     ConcurrentVectorIterator& operator=(const ConcurrentVectorIterator<T, SegmentSize>& other)
68     {
69         m_vector = other.m_vector;
70         m_index = other.m_index;
71         return *this;
72     }
73
74 private:
75     ConcurrentVectorIterator(ConcurrentVector<T, SegmentSize>& vector, size_t index)
76         : m_vector(vector)
77         , m_index(index)
78     {
79     }
80
81     ConcurrentVector<T, SegmentSize>& m_vector;
82     size_t m_index;
83 };
84
85 // ConcurrentVector is like SegmentedVector, but suitable for scenarios where one thread appends
86 // elements and another thread continues to access elements at lower indices. Only one thread can
87 // append at a time, so that activity still needs locking. size() and last() are racy with append(),
88 // in the sense that last() may crash if an append() is running concurrently because size()-1 does yet
89 // have a segment.
90 //
91 // Typical users of ConcurrentVector already have some way of ensuring that by the time someone is
92 // trying to use an index, some synchronization has happened to ensure that this index contains fully
93 // initialized data. Thereafter, the keeper of that index is allowed to use it on this vector without
94 // any locking other than what is needed to protect the integrity of the element at that index. This
95 // works because we guarantee shrinking the vector is impossible and that growing the vector doesn't
96 // delete old vector spines.
97 template <typename T, size_t SegmentSize>
98 class ConcurrentVector {
99     friend class ConcurrentVectorIterator<T, SegmentSize>;
100     WTF_MAKE_NONCOPYABLE(ConcurrentVector);
101     WTF_MAKE_FAST_ALLOCATED;
102
103 public:
104     typedef ConcurrentVectorIterator<T, SegmentSize> Iterator;
105
106     ConcurrentVector() = default;
107
108     ~ConcurrentVector()
109     {
110     }
111
112     // This may return a size that is bigger than the underlying storage, since this does not fence
113     // manipulations of size. So if you access at size()-1, you may crash because this hasn't
114     // allocated storage for that index yet.
115     size_t size() const { return m_size; }
116
117     bool isEmpty() const { return !size(); }
118
119     T& at(size_t index)
120     {
121         ASSERT_WITH_SECURITY_IMPLICATION(index < m_size);
122         return segmentFor(index)->entries[subscriptFor(index)];
123     }
124
125     const T& at(size_t index) const
126     {
127         return const_cast<ConcurrentVector<T, SegmentSize>*>(this)->at(index);
128     }
129
130     T& operator[](size_t index)
131     {
132         return at(index);
133     }
134
135     const T& operator[](size_t index) const
136     {
137         return at(index);
138     }
139
140     T& first()
141     {
142         ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
143         return at(0);
144     }
145     const T& first() const
146     {
147         ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
148         return at(0);
149     }
150     
151     // This may crash if run concurrently to append(). If you want to accurately track the size of
152     // this vector, you'll have to do it yourself, with your own fencing.
153     T& last()
154     {
155         ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
156         return at(size() - 1);
157     }
158     const T& last() const
159     {
160         ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
161         return at(size() - 1);
162     }
163
164     T takeLast()
165     {
166         ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
167         T result = WTFMove(last());
168         --m_size;
169         return result;
170     }
171
172     template<typename... Args>
173     void append(Args&&... args)
174     {
175         ++m_size;
176         if (!segmentExistsFor(m_size - 1))
177             allocateSegment();
178         new (NotNull, &last()) T(std::forward<Args>(args)...);
179     }
180
181     template<typename... Args>
182     T& alloc(Args&&... args)
183     {
184         append(std::forward<Args>(args)...);
185         return last();
186     }
187
188     void removeLast()
189     {
190         last().~T();
191         --m_size;
192     }
193
194     void grow(size_t size)
195     {
196         if (size == m_size)
197             return;
198         ASSERT(size > m_size);
199         ensureSegmentsFor(size);
200         size_t oldSize = m_size;
201         m_size = size;
202         for (size_t i = oldSize; i < m_size; ++i)
203             new (NotNull, &at(i)) T();
204     }
205
206     Iterator begin()
207     {
208         return Iterator(*this, 0);
209     }
210
211     Iterator end()
212     {
213         return Iterator(*this, m_size);
214     }
215
216 private:
217     struct Segment {
218         WTF_MAKE_STRUCT_FAST_ALLOCATED;
219             
220         T entries[SegmentSize];
221     };
222
223     bool segmentExistsFor(size_t index)
224     {
225         return index / SegmentSize < m_numSegments;
226     }
227
228     Segment* segmentFor(size_t index)
229     {
230         return m_segments[index / SegmentSize].get();
231     }
232
233     size_t subscriptFor(size_t index)
234     {
235         return index % SegmentSize;
236     }
237
238     void ensureSegmentsFor(size_t size)
239     {
240         size_t segmentCount = (m_size + SegmentSize - 1) / SegmentSize;
241         size_t neededSegmentCount = (size + SegmentSize - 1) / SegmentSize;
242
243         for (size_t i = segmentCount ? segmentCount - 1 : 0; i < neededSegmentCount; ++i)
244             ensureSegment(i);
245     }
246
247     void ensureSegment(size_t segmentIndex)
248     {
249         ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_numSegments);
250         if (segmentIndex == m_numSegments)
251             allocateSegment();
252     }
253
254     void allocateSegment()
255     {
256         m_segments.grow(m_numSegments + 1);
257         m_segments[m_numSegments++] = std::make_unique<Segment>();
258     }
259
260     size_t m_size { 0 };
261     ConcurrentBuffer<std::unique_ptr<Segment>> m_segments;
262     size_t m_numSegments { 0 };
263 };
264
265 } // namespace WTF
266
267 using WTF::ConcurrentVector;
268
269 #endif // ConcurrentVector_h