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 ~FixedVector();
49
50 reference at(size_type pos);
51 const_reference at(size_type pos) const;
52
53 reference operator[](size_type pos);
54 const_reference operator[](size_type pos) const;
55
56 pointer data();
57 const_pointer data() const;
58
59 iterator begin();
60 const_iterator begin() const;
61
62 iterator end();
63 const_iterator end() const;
64
65 bool empty() const;
66 size_type size() const;
67 static constexpr size_type max_size();
68
69 void clear();
70
71 void push_back(const value_type &value);
72 void push_back(value_type &&value);
73
74 template <class... Args>
75 void emplace_back(Args &&... args);
76
77 void pop_back();
78 reference back();
79 const_reference back() const;
80
81 void swap(FixedVector<T, N, Storage> &other);
82
83 void resize(size_type count);
84 void resize(size_type count, const value_type &value);
85
86 bool full() const;
87
88 private:
89 void assign_from_initializer_list(std::initializer_list<value_type> init);
90
91 Storage mStorage;
92 size_type mSize = 0;
93 };
94
95 template <class T, size_t N, class Storage>
96 bool operator==(const FixedVector<T, N, Storage> &a, const FixedVector<T, N, Storage> &b)
97 {
98 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
99 }
100
101 template <class T, size_t N, class Storage>
102 bool operator!=(const FixedVector<T, N, Storage> &a, const FixedVector<T, N, Storage> &b)
103 {
104 return !(a == b);
105 }
106
107 template <class T, size_t N, class Storage>
108 FixedVector<T, N, Storage>::FixedVector() = default;
109
110 template <class T, size_t N, class Storage>
FixedVector(size_type count,const value_type & value)111 FixedVector<T, N, Storage>::FixedVector(size_type count, const value_type &value) : mSize(count)
112 {
113 ASSERT(count <= N);
114 std::fill(mStorage.begin(), mStorage.begin() + count, value);
115 }
116
117 template <class T, size_t N, class Storage>
FixedVector(size_type count)118 FixedVector<T, N, Storage>::FixedVector(size_type count) : mSize(count)
119 {
120 ASSERT(count <= N);
121 }
122
123 template <class T, size_t N, class Storage>
124 FixedVector<T, N, Storage>::FixedVector(const FixedVector<T, N, Storage> &other) = default;
125
126 template <class T, size_t N, class Storage>
127 FixedVector<T, N, Storage>::FixedVector(FixedVector<T, N, Storage> &&other) = default;
128
129 template <class T, size_t N, class Storage>
FixedVector(std::initializer_list<value_type> init)130 FixedVector<T, N, Storage>::FixedVector(std::initializer_list<value_type> init)
131 {
132 ASSERT(init.size() <= N);
133 assign_from_initializer_list(init);
134 }
135
136 template <class T, size_t N, class Storage>
137 FixedVector<T, N, Storage> &FixedVector<T, N, Storage>::operator=(
138 const FixedVector<T, N, Storage> &other) = default;
139
140 template <class T, size_t N, class Storage>
141 FixedVector<T, N, Storage> &FixedVector<T, N, Storage>::operator=(
142 FixedVector<T, N, Storage> &&other) = default;
143
144 template <class T, size_t N, class Storage>
145 FixedVector<T, N, Storage> &FixedVector<T, N, Storage>::operator=(
146 std::initializer_list<value_type> init)
147 {
148 clear();
149 ASSERT(init.size() <= N);
150 assign_from_initializer_list(init);
151 return this;
152 }
153
154 template <class T, size_t N, class Storage>
~FixedVector()155 FixedVector<T, N, Storage>::~FixedVector()
156 {
157 clear();
158 }
159
160 template <class T, size_t N, class Storage>
at(size_type pos)161 typename FixedVector<T, N, Storage>::reference FixedVector<T, N, Storage>::at(size_type pos)
162 {
163 ASSERT(pos < N);
164 return mStorage.at(pos);
165 }
166
167 template <class T, size_t N, class Storage>
at(size_type pos)168 typename FixedVector<T, N, Storage>::const_reference FixedVector<T, N, Storage>::at(
169 size_type pos) const
170 {
171 ASSERT(pos < N);
172 return mStorage.at(pos);
173 }
174
175 template <class T, size_t N, class Storage>
176 typename FixedVector<T, N, Storage>::reference FixedVector<T, N, Storage>::operator[](size_type pos)
177 {
178 ASSERT(pos < N);
179 return mStorage[pos];
180 }
181
182 template <class T, size_t N, class Storage>
183 typename FixedVector<T, N, Storage>::const_reference FixedVector<T, N, Storage>::operator[](
184 size_type pos) const
185 {
186 ASSERT(pos < N);
187 return mStorage[pos];
188 }
189
190 template <class T, size_t N, class Storage>
data()191 typename FixedVector<T, N, Storage>::const_pointer angle::FixedVector<T, N, Storage>::data() const
192 {
193 return mStorage.data();
194 }
195
196 template <class T, size_t N, class Storage>
data()197 typename FixedVector<T, N, Storage>::pointer angle::FixedVector<T, N, Storage>::data()
198 {
199 return mStorage.data();
200 }
201
202 template <class T, size_t N, class Storage>
begin()203 typename FixedVector<T, N, Storage>::iterator FixedVector<T, N, Storage>::begin()
204 {
205 return mStorage.begin();
206 }
207
208 template <class T, size_t N, class Storage>
begin()209 typename FixedVector<T, N, Storage>::const_iterator FixedVector<T, N, Storage>::begin() const
210 {
211 return mStorage.begin();
212 }
213
214 template <class T, size_t N, class Storage>
end()215 typename FixedVector<T, N, Storage>::iterator FixedVector<T, N, Storage>::end()
216 {
217 return mStorage.begin() + mSize;
218 }
219
220 template <class T, size_t N, class Storage>
end()221 typename FixedVector<T, N, Storage>::const_iterator FixedVector<T, N, Storage>::end() const
222 {
223 return mStorage.begin() + mSize;
224 }
225
226 template <class T, size_t N, class Storage>
empty()227 bool FixedVector<T, N, Storage>::empty() const
228 {
229 return mSize == 0;
230 }
231
232 template <class T, size_t N, class Storage>
size()233 typename FixedVector<T, N, Storage>::size_type FixedVector<T, N, Storage>::size() const
234 {
235 return mSize;
236 }
237
238 template <class T, size_t N, class Storage>
max_size()239 constexpr typename FixedVector<T, N, Storage>::size_type FixedVector<T, N, Storage>::max_size()
240 {
241 return N;
242 }
243
244 template <class T, size_t N, class Storage>
clear()245 void FixedVector<T, N, Storage>::clear()
246 {
247 resize(0);
248 }
249
250 template <class T, size_t N, class Storage>
push_back(const value_type & value)251 void FixedVector<T, N, Storage>::push_back(const value_type &value)
252 {
253 ASSERT(mSize < N);
254 mStorage[mSize] = value;
255 mSize++;
256 }
257
258 template <class T, size_t N, class Storage>
push_back(value_type && value)259 void FixedVector<T, N, Storage>::push_back(value_type &&value)
260 {
261 ASSERT(mSize < N);
262 mStorage[mSize] = std::move(value);
263 mSize++;
264 }
265
266 template <class T, size_t N, class Storage>
267 template <class... Args>
emplace_back(Args &&...args)268 void FixedVector<T, N, Storage>::emplace_back(Args &&... args)
269 {
270 ASSERT(mSize < N);
271 new (&mStorage[mSize]) T{std::forward<Args>(args)...};
272 mSize++;
273 }
274
275 template <class T, size_t N, class Storage>
pop_back()276 void FixedVector<T, N, Storage>::pop_back()
277 {
278 ASSERT(mSize > 0);
279 mSize--;
280 }
281
282 template <class T, size_t N, class Storage>
back()283 typename FixedVector<T, N, Storage>::reference FixedVector<T, N, Storage>::back()
284 {
285 ASSERT(mSize > 0);
286 return mStorage[mSize - 1];
287 }
288
289 template <class T, size_t N, class Storage>
back()290 typename FixedVector<T, N, Storage>::const_reference FixedVector<T, N, Storage>::back() const
291 {
292 ASSERT(mSize > 0);
293 return mStorage[mSize - 1];
294 }
295
296 template <class T, size_t N, class Storage>
swap(FixedVector<T,N,Storage> & other)297 void FixedVector<T, N, Storage>::swap(FixedVector<T, N, Storage> &other)
298 {
299 std::swap(mSize, other.mSize);
300 std::swap(mStorage, other.mStorage);
301 }
302
303 template <class T, size_t N, class Storage>
resize(size_type count)304 void FixedVector<T, N, Storage>::resize(size_type count)
305 {
306 ASSERT(count <= N);
307 while (mSize > count)
308 {
309 mSize--;
310 mStorage[mSize] = value_type();
311 }
312 while (mSize < count)
313 {
314 mStorage[mSize] = value_type();
315 mSize++;
316 }
317 }
318
319 template <class T, size_t N, class Storage>
resize(size_type count,const value_type & value)320 void FixedVector<T, N, Storage>::resize(size_type count, const value_type &value)
321 {
322 ASSERT(count <= N);
323 while (mSize > count)
324 {
325 mSize--;
326 mStorage[mSize] = value_type();
327 }
328 while (mSize < count)
329 {
330 mStorage[mSize] = value;
331 mSize++;
332 }
333 }
334
335 template <class T, size_t N, class Storage>
assign_from_initializer_list(std::initializer_list<value_type> init)336 void FixedVector<T, N, Storage>::assign_from_initializer_list(
337 std::initializer_list<value_type> init)
338 {
339 for (auto element : init)
340 {
341 mStorage[mSize] = std::move(element);
342 mSize++;
343 }
344 }
345
346 template <class T, size_t N, class Storage>
full()347 bool FixedVector<T, N, Storage>::full() const
348 {
349 return (mSize == N);
350 }
351 } // namespace angle
352
353 #endif // COMMON_FIXEDVECTOR_H_
354