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#pragma once
30
31#include <wtf/ConcurrentBuffer.h>
32#include <wtf/Noncopyable.h>
33
34namespace WTF {
35
36// An iterator for ConcurrentVector. It supports only the pre ++ operator
37template <typename T, size_t SegmentSize = 8> class ConcurrentVector;
38template <typename T, size_t SegmentSize = 8> class ConcurrentVectorIterator {
39private:
40 friend class ConcurrentVector<T, SegmentSize>;
41public:
42 typedef ConcurrentVectorIterator<T, SegmentSize> Iterator;
43
44 ~ConcurrentVectorIterator() { }
45
46 T& operator*() const { return m_vector.at(m_index); }
47 T* operator->() const { return &m_vector.at(m_index); }
48
49 // Only prefix ++ operator supported
50 Iterator& operator++()
51 {
52 m_index++;
53 return *this;
54 }
55
56 bool operator==(const Iterator& other) const
57 {
58 return m_index == other.m_index && &m_vector == &other.m_vector;
59 }
60
61 bool operator!=(const Iterator& other) const
62 {
63 return m_index != other.m_index || &m_vector != &other.m_vector;
64 }
65
66 ConcurrentVectorIterator& operator=(const ConcurrentVectorIterator<T, SegmentSize>& other)
67 {
68 m_vector = other.m_vector;
69 m_index = other.m_index;
70 return *this;
71 }
72
73private:
74 ConcurrentVectorIterator(ConcurrentVector<T, SegmentSize>& vector, size_t index)
75 : m_vector(vector)
76 , m_index(index)
77 {
78 }
79
80 ConcurrentVector<T, SegmentSize>& m_vector;
81 size_t m_index;
82};
83
84// ConcurrentVector is like SegmentedVector, but suitable for scenarios where one thread appends
85// elements and another thread continues to access elements at lower indices. Only one thread can
86// append at a time, so that activity still needs locking. size() and last() are racy with append(),
87// in the sense that last() may crash if an append() is running concurrently because size()-1 does yet
88// have a segment.
89//
90// Typical users of ConcurrentVector already have some way of ensuring that by the time someone is
91// trying to use an index, some synchronization has happened to ensure that this index contains fully
92// initialized data. Thereafter, the keeper of that index is allowed to use it on this vector without
93// any locking other than what is needed to protect the integrity of the element at that index. This
94// works because we guarantee shrinking the vector is impossible and that growing the vector doesn't
95// delete old vector spines.
96template <typename T, size_t SegmentSize>
97class ConcurrentVector {
98 friend class ConcurrentVectorIterator<T, SegmentSize>;
99 WTF_MAKE_NONCOPYABLE(ConcurrentVector);
100 WTF_MAKE_FAST_ALLOCATED;
101
102public:
103 typedef ConcurrentVectorIterator<T, SegmentSize> Iterator;
104
105 ConcurrentVector() = default;
106
107 ~ConcurrentVector()
108 {
109 }
110
111 // This may return a size that is bigger than the underlying storage, since this does not fence
112 // manipulations of size. So if you access at size()-1, you may crash because this hasn't
113 // allocated storage for that index yet.
114 size_t size() const { return m_size; }
115
116 bool isEmpty() const { return !size(); }
117
118 T& at(size_t index)
119 {
120 ASSERT_WITH_SECURITY_IMPLICATION(index < m_size);
121 return segmentFor(index)->entries[subscriptFor(index)];
122 }
123
124 const T& at(size_t index) const
125 {
126 return const_cast<ConcurrentVector<T, SegmentSize>*>(this)->at(index);
127 }
128
129 T& operator[](size_t index)
130 {
131 return at(index);
132 }
133
134 const T& operator[](size_t index) const
135 {
136 return at(index);
137 }
138
139 T& first()
140 {
141 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
142 return at(0);
143 }
144 const T& first() const
145 {
146 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
147 return at(0);
148 }
149
150 // This may crash if run concurrently to append(). If you want to accurately track the size of
151 // this vector, you'll have to do it yourself, with your own fencing.
152 T& last()
153 {
154 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
155 return at(size() - 1);
156 }
157 const T& last() const
158 {
159 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
160 return at(size() - 1);
161 }
162
163 T takeLast()
164 {
165 ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
166 T result = WTFMove(last());
167 --m_size;
168 return result;
169 }
170
171 template<typename... Args>
172 void append(Args&&... args)
173 {
174 ++m_size;
175 if (!segmentExistsFor(m_size - 1))
176 allocateSegment();
177 new (NotNull, &last()) T(std::forward<Args>(args)...);
178 }
179
180 template<typename... Args>
181 T& alloc(Args&&... args)
182 {
183 append(std::forward<Args>(args)...);
184 return last();
185 }
186
187 void removeLast()
188 {
189 last().~T();
190 --m_size;
191 }
192
193 void grow(size_t size)
194 {
195 if (size == m_size)
196 return;
197 ASSERT(size > m_size);
198 ensureSegmentsFor(size);
199 size_t oldSize = m_size;
200 m_size = size;
201 for (size_t i = oldSize; i < m_size; ++i)
202 new (NotNull, &at(i)) T();
203 }
204
205 Iterator begin()
206 {
207 return Iterator(*this, 0);
208 }
209
210 Iterator end()
211 {
212 return Iterator(*this, m_size);
213 }
214
215private:
216 struct Segment {
217 WTF_MAKE_STRUCT_FAST_ALLOCATED;
218
219 T entries[SegmentSize];
220 };
221
222 bool segmentExistsFor(size_t index)
223 {
224 return index / SegmentSize < m_numSegments;
225 }
226
227 Segment* segmentFor(size_t index)
228 {
229 return m_segments[index / SegmentSize].get();
230 }
231
232 size_t subscriptFor(size_t index)
233 {
234 return index % SegmentSize;
235 }
236
237 void ensureSegmentsFor(size_t size)
238 {
239 size_t segmentCount = (m_size + SegmentSize - 1) / SegmentSize;
240 size_t neededSegmentCount = (size + SegmentSize - 1) / SegmentSize;
241
242 for (size_t i = segmentCount ? segmentCount - 1 : 0; i < neededSegmentCount; ++i)
243 ensureSegment(i);
244 }
245
246 void ensureSegment(size_t segmentIndex)
247 {
248 ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_numSegments);
249 if (segmentIndex == m_numSegments)
250 allocateSegment();
251 }
252
253 void allocateSegment()
254 {
255 m_segments.grow(m_numSegments + 1);
256 m_segments[m_numSegments++] = std::make_unique<Segment>();
257 }
258
259 size_t m_size { 0 };
260 ConcurrentBuffer<std::unique_ptr<Segment>> m_segments;
261 size_t m_numSegments { 0 };
262};
263
264} // namespace WTF
265
266using WTF::ConcurrentVector;
267