1 //
2 // Copyright 2018 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6 // FixedVector.h:
7 // A vector class with a maximum size and fixed storage.
8 //
9
10 #ifndef COMMON_FIXEDVECTOR_H_
11 #define COMMON_FIXEDVECTOR_H_
12
13 #include "common/debug.h"
14
15 #include <algorithm>
16 #include <array>
17 #include <initializer_list>
18
19 namespace angle
20 {
21 template <class T, size_t N, class Storage = std::array<T, N>>
22 class FixedVector final
23 {
24 public:
25 using value_type = typename Storage::value_type;
26 using size_type = typename Storage::size_type;
27 using reference = typename Storage::reference;
28 using const_reference = typename Storage::const_reference;
29 using pointer = typename Storage::pointer;
30 using const_pointer = typename Storage::const_pointer;
31 using iterator = typename Storage::iterator;
32 using const_iterator = typename Storage::const_iterator;
33 using reverse_iterator = typename Storage::reverse_iterator;
34 using const_reverse_iterator = typename Storage::const_reverse_iterator;
35
36 FixedVector();
37 FixedVector(size_type count, const value_type &value);
38 FixedVector(size_type count);
39
40 FixedVector(const FixedVector<T, N, Storage> &other);
41 FixedVector(FixedVector<T, N, Storage> &&other);
42 FixedVector(std::initializer_list<value_type> init);
43
44 FixedVector<T, N, Storage> &operator=(const FixedVector<T, N, Storage> &other);
45 FixedVector<T, N, Storage> &operator=(FixedVector<T, N, Storage> &&other);
46 FixedVector<T, N, Storage> &operator=(std::initializer_list<value_type> init);
47
48 // Makes class trivially destructible.
49 ~FixedVector() = default;
50
51 reference at(size_type pos);
52 const_reference at(size_type pos) const;
53
54 reference operator[](size_type pos);
55 const_reference operator[](size_type pos) const;
56
57 pointer data();
58 const_pointer data() const;
59
60 iterator begin();
61 const_iterator begin() const;
62
63 iterator end();
64 const_iterator end() const;
65
66 bool empty() const;
67 size_type size() const;
68 static constexpr size_type max_size();
69
70 void clear();
71
72 void push_back(const value_type &value);
73 void push_back(value_type &&value);
74
75 template <class... Args>
76 void emplace_back(Args &&...args);
77
78 void pop_back();
79 reference back();
80 const_reference back() const;
81
82 void swap(FixedVector<T, N, Storage> &other);
83
84 void resize(size_type count);
85 void resize(size_type count, const value_type &value);
86
87 bool full() const;
88
89 private:
90 void assign_from_initializer_list(std::initializer_list<value_type> init);
91
92 Storage mStorage;
93 size_type mSize = 0;
94 };
95
96 template <class T, size_t N, class Storage>
97 bool operator==(const FixedVector<T, N, Storage> &a, const FixedVector<T, N, Storage> &b)
98 {
99 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
100 }
101
102 template <class T, size_t N, class Storage>
103 bool operator!=(const FixedVector<T, N, Storage> &a, const FixedVector<T, N, Storage> &b)
104 {
105 return !(a == b);
106 }
107
108 template <class T, size_t N, class Storage>
109 FixedVector<T, N, Storage>::FixedVector() = default;
110
111 template <class T, size_t N, class Storage>
FixedVector(size_type count,const value_type & value)112 FixedVector<T, N, Storage>::FixedVector(size_type count, const value_type &value) : mSize(count)
113 {
114 ASSERT(count <= N);
115 std::fill(mStorage.begin(), mStorage.begin() + count, value);
116 }
117
118 template <class T, size_t N, class Storage>
FixedVector(size_type count)119 FixedVector<T, N, Storage>::FixedVector(size_type count) : mSize(count)
120 {
121 ASSERT(count <= N);
122 }
123
124 template <class T, size_t N, class Storage>
125 FixedVector<T, N, Storage>::FixedVector(const FixedVector<T, N, Storage> &other) = default;
126
127 template <class T, size_t N, class Storage>
128 FixedVector<T, N, Storage>::FixedVector(FixedVector<T, N, Storage> &&other) = default;
129
130 template <class T, size_t N, class Storage>
FixedVector(std::initializer_list<value_type> init)131 FixedVector<T, N, Storage>::FixedVector(std::initializer_list<value_type> init)
132 {
133 ASSERT(init.size() <= N);
134 assign_from_initializer_list(init);
135 }
136
137 template <class T, size_t N, class Storage>
138 FixedVector<T, N, Storage> &FixedVector<T, N, Storage>::operator=(
139 const FixedVector<T, N, Storage> &other) = default;
140
141 template <class T, size_t N, class Storage>
142 FixedVector<T, N, Storage> &FixedVector<T, N, Storage>::operator=(
143 FixedVector<T, N, Storage> &&other) = default;
144
145 template <class T, size_t N, class Storage>
146 FixedVector<T, N, Storage> &FixedVector<T, N, Storage>::operator=(
147 std::initializer_list<value_type> init)
148 {
149 clear();
150 ASSERT(init.size() <= N);
151 assign_from_initializer_list(init);
152 return this;
153 }
154
155 template <class T, size_t N, class Storage>
at(size_type pos)156 typename FixedVector<T, N, Storage>::reference FixedVector<T, N, Storage>::at(size_type pos)
157 {
158 ASSERT(pos < N);
159 return mStorage.at(pos);
160 }
161
162 template <class T, size_t N, class Storage>
at(size_type pos)163 typename FixedVector<T, N, Storage>::const_reference FixedVector<T, N, Storage>::at(
164 size_type pos) const
165 {
166 ASSERT(pos < N);
167 return mStorage.at(pos);
168 }
169
170 template <class T, size_t N, class Storage>
171 typename FixedVector<T, N, Storage>::reference FixedVector<T, N, Storage>::operator[](size_type pos)
172 {
173 ASSERT(pos < N);
174 return mStorage[pos];
175 }
176
177 template <class T, size_t N, class Storage>
178 typename FixedVector<T, N, Storage>::const_reference FixedVector<T, N, Storage>::operator[](
179 size_type pos) const
180 {
181 ASSERT(pos < N);
182 return mStorage[pos];
183 }
184
185 template <class T, size_t N, class Storage>
data()186 typename FixedVector<T, N, Storage>::const_pointer angle::FixedVector<T, N, Storage>::data() const
187 {
188 return mStorage.data();
189 }
190
191 template <class T, size_t N, class Storage>
data()192 typename FixedVector<T, N, Storage>::pointer angle::FixedVector<T, N, Storage>::data()
193 {
194 return mStorage.data();
195 }
196
197 template <class T, size_t N, class Storage>
begin()198 typename FixedVector<T, N, Storage>::iterator FixedVector<T, N, Storage>::begin()
199 {
200 return mStorage.begin();
201 }
202
203 template <class T, size_t N, class Storage>
begin()204 typename FixedVector<T, N, Storage>::const_iterator FixedVector<T, N, Storage>::begin() const
205 {
206 return mStorage.begin();
207 }
208
209 template <class T, size_t N, class Storage>
end()210 typename FixedVector<T, N, Storage>::iterator FixedVector<T, N, Storage>::end()
211 {
212 return mStorage.begin() + mSize;
213 }
214
215 template <class T, size_t N, class Storage>
end()216 typename FixedVector<T, N, Storage>::const_iterator FixedVector<T, N, Storage>::end() const
217 {
218 return mStorage.begin() + mSize;
219 }
220
221 template <class T, size_t N, class Storage>
empty()222 bool FixedVector<T, N, Storage>::empty() const
223 {
224 return mSize == 0;
225 }
226
227 template <class T, size_t N, class Storage>
size()228 typename FixedVector<T, N, Storage>::size_type FixedVector<T, N, Storage>::size() const
229 {
230 return mSize;
231 }
232
233 template <class T, size_t N, class Storage>
max_size()234 constexpr typename FixedVector<T, N, Storage>::size_type FixedVector<T, N, Storage>::max_size()
235 {
236 return N;
237 }
238
239 template <class T, size_t N, class Storage>
clear()240 void FixedVector<T, N, Storage>::clear()
241 {
242 resize(0);
243 }
244
245 template <class T, size_t N, class Storage>
push_back(const value_type & value)246 void FixedVector<T, N, Storage>::push_back(const value_type &value)
247 {
248 ASSERT(mSize < N);
249 mStorage[mSize] = value;
250 mSize++;
251 }
252
253 template <class T, size_t N, class Storage>
push_back(value_type && value)254 void FixedVector<T, N, Storage>::push_back(value_type &&value)
255 {
256 ASSERT(mSize < N);
257 mStorage[mSize] = std::move(value);
258 mSize++;
259 }
260
261 template <class T, size_t N, class Storage>
262 template <class... Args>
emplace_back(Args &&...args)263 void FixedVector<T, N, Storage>::emplace_back(Args &&...args)
264 {
265 ASSERT(mSize < N);
266 new (&mStorage[mSize]) T{std::forward<Args>(args)...};
267 mSize++;
268 }
269
270 template <class T, size_t N, class Storage>
pop_back()271 void FixedVector<T, N, Storage>::pop_back()
272 {
273 ASSERT(mSize > 0);
274 mSize--;
275 }
276
277 template <class T, size_t N, class Storage>
back()278 typename FixedVector<T, N, Storage>::reference FixedVector<T, N, Storage>::back()
279 {
280 ASSERT(mSize > 0);
281 return mStorage[mSize - 1];
282 }
283
284 template <class T, size_t N, class Storage>
back()285 typename FixedVector<T, N, Storage>::const_reference FixedVector<T, N, Storage>::back() const
286 {
287 ASSERT(mSize > 0);
288 return mStorage[mSize - 1];
289 }
290
291 template <class T, size_t N, class Storage>
swap(FixedVector<T,N,Storage> & other)292 void FixedVector<T, N, Storage>::swap(FixedVector<T, N, Storage> &other)
293 {
294 std::swap(mSize, other.mSize);
295 std::swap(mStorage, other.mStorage);
296 }
297
298 template <class T, size_t N, class Storage>
resize(size_type count)299 void FixedVector<T, N, Storage>::resize(size_type count)
300 {
301 ASSERT(count <= N);
302 while (mSize > count)
303 {
304 mSize--;
305 mStorage[mSize] = value_type();
306 }
307 while (mSize < count)
308 {
309 mStorage[mSize] = value_type();
310 mSize++;
311 }
312 }
313
314 template <class T, size_t N, class Storage>
resize(size_type count,const value_type & value)315 void FixedVector<T, N, Storage>::resize(size_type count, const value_type &value)
316 {
317 ASSERT(count <= N);
318 while (mSize > count)
319 {
320 mSize--;
321 mStorage[mSize] = value_type();
322 }
323 while (mSize < count)
324 {
325 mStorage[mSize] = value;
326 mSize++;
327 }
328 }
329
330 template <class T, size_t N, class Storage>
assign_from_initializer_list(std::initializer_list<value_type> init)331 void FixedVector<T, N, Storage>::assign_from_initializer_list(
332 std::initializer_list<value_type> init)
333 {
334 for (auto element : init)
335 {
336 mStorage[mSize] = std::move(element);
337 mSize++;
338 }
339 }
340
341 template <class T, size_t N, class Storage>
full()342 bool FixedVector<T, N, Storage>::full() const
343 {
344 return (mSize == N);
345 }
346 } // namespace angle
347
348 #endif // COMMON_FIXEDVECTOR_H_
349