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>
FixedVector(FixedVector<T,N,Storage> && other)128 FixedVector<T, N, Storage>::FixedVector(FixedVector<T, N, Storage> &&other)
129 : mStorage(std::move(other.mStorage)), mSize(other.mSize)
130 {
131 other.mSize = 0;
132 }
133
134 template <class T, size_t N, class Storage>
FixedVector(std::initializer_list<value_type> init)135 FixedVector<T, N, Storage>::FixedVector(std::initializer_list<value_type> init)
136 {
137 ASSERT(init.size() <= N);
138 assign_from_initializer_list(init);
139 }
140
141 template <class T, size_t N, class Storage>
142 FixedVector<T, N, Storage> &FixedVector<T, N, Storage>::operator=(
143 const 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 FixedVector<T, N, Storage> &&other)
148 {
149 mStorage = std::move(other.mStorage);
150 mSize = other.mSize;
151 other.mSize = 0;
152 return *this;
153 }
154
155 template <class T, size_t N, class Storage>
156 FixedVector<T, N, Storage> &FixedVector<T, N, Storage>::operator=(
157 std::initializer_list<value_type> init)
158 {
159 clear();
160 ASSERT(init.size() <= N);
161 assign_from_initializer_list(init);
162 return *this;
163 }
164
165 template <class T, size_t N, class Storage>
at(size_type pos)166 typename FixedVector<T, N, Storage>::reference FixedVector<T, N, Storage>::at(size_type pos)
167 {
168 ASSERT(pos < mSize);
169 return mStorage.at(pos);
170 }
171
172 template <class T, size_t N, class Storage>
at(size_type pos)173 typename FixedVector<T, N, Storage>::const_reference FixedVector<T, N, Storage>::at(
174 size_type pos) const
175 {
176 ASSERT(pos < mSize);
177 return mStorage.at(pos);
178 }
179
180 template <class T, size_t N, class Storage>
181 typename FixedVector<T, N, Storage>::reference FixedVector<T, N, Storage>::operator[](size_type pos)
182 {
183 ASSERT(pos < mSize);
184 return mStorage[pos];
185 }
186
187 template <class T, size_t N, class Storage>
188 typename FixedVector<T, N, Storage>::const_reference FixedVector<T, N, Storage>::operator[](
189 size_type pos) const
190 {
191 ASSERT(pos < mSize);
192 return mStorage[pos];
193 }
194
195 template <class T, size_t N, class Storage>
data()196 typename FixedVector<T, N, Storage>::const_pointer angle::FixedVector<T, N, Storage>::data() const
197 {
198 return mStorage.data();
199 }
200
201 template <class T, size_t N, class Storage>
data()202 typename FixedVector<T, N, Storage>::pointer angle::FixedVector<T, N, Storage>::data()
203 {
204 return mStorage.data();
205 }
206
207 template <class T, size_t N, class Storage>
begin()208 typename FixedVector<T, N, Storage>::iterator FixedVector<T, N, Storage>::begin()
209 {
210 return mStorage.begin();
211 }
212
213 template <class T, size_t N, class Storage>
begin()214 typename FixedVector<T, N, Storage>::const_iterator FixedVector<T, N, Storage>::begin() const
215 {
216 return mStorage.begin();
217 }
218
219 template <class T, size_t N, class Storage>
end()220 typename FixedVector<T, N, Storage>::iterator FixedVector<T, N, Storage>::end()
221 {
222 return mStorage.begin() + mSize;
223 }
224
225 template <class T, size_t N, class Storage>
end()226 typename FixedVector<T, N, Storage>::const_iterator FixedVector<T, N, Storage>::end() const
227 {
228 return mStorage.begin() + mSize;
229 }
230
231 template <class T, size_t N, class Storage>
empty()232 bool FixedVector<T, N, Storage>::empty() const
233 {
234 return mSize == 0;
235 }
236
237 template <class T, size_t N, class Storage>
size()238 typename FixedVector<T, N, Storage>::size_type FixedVector<T, N, Storage>::size() const
239 {
240 return mSize;
241 }
242
243 template <class T, size_t N, class Storage>
max_size()244 constexpr typename FixedVector<T, N, Storage>::size_type FixedVector<T, N, Storage>::max_size()
245 {
246 return N;
247 }
248
249 template <class T, size_t N, class Storage>
clear()250 void FixedVector<T, N, Storage>::clear()
251 {
252 resize(0);
253 }
254
255 template <class T, size_t N, class Storage>
push_back(const value_type & value)256 void FixedVector<T, N, Storage>::push_back(const value_type &value)
257 {
258 ASSERT(mSize < N);
259 mStorage[mSize] = value;
260 mSize++;
261 }
262
263 template <class T, size_t N, class Storage>
push_back(value_type && value)264 void FixedVector<T, N, Storage>::push_back(value_type &&value)
265 {
266 ASSERT(mSize < N);
267 mStorage[mSize] = std::move(value);
268 mSize++;
269 }
270
271 template <class T, size_t N, class Storage>
272 template <class... Args>
emplace_back(Args &&...args)273 void FixedVector<T, N, Storage>::emplace_back(Args &&...args)
274 {
275 ASSERT(mSize < N);
276 new (&mStorage[mSize]) T{std::forward<Args>(args)...};
277 mSize++;
278 }
279
280 template <class T, size_t N, class Storage>
pop_back()281 void FixedVector<T, N, Storage>::pop_back()
282 {
283 ASSERT(mSize > 0);
284 mSize--;
285 }
286
287 template <class T, size_t N, class Storage>
back()288 typename FixedVector<T, N, Storage>::reference FixedVector<T, N, Storage>::back()
289 {
290 ASSERT(mSize > 0);
291 return mStorage[mSize - 1];
292 }
293
294 template <class T, size_t N, class Storage>
back()295 typename FixedVector<T, N, Storage>::const_reference FixedVector<T, N, Storage>::back() const
296 {
297 ASSERT(mSize > 0);
298 return mStorage[mSize - 1];
299 }
300
301 template <class T, size_t N, class Storage>
swap(FixedVector<T,N,Storage> & other)302 void FixedVector<T, N, Storage>::swap(FixedVector<T, N, Storage> &other)
303 {
304 std::swap(mSize, other.mSize);
305 std::swap(mStorage, other.mStorage);
306 }
307
308 template <class T, size_t N, class Storage>
resize(size_type count)309 void FixedVector<T, N, Storage>::resize(size_type count)
310 {
311 ASSERT(count <= N);
312 while (mSize > count)
313 {
314 mSize--;
315 mStorage[mSize] = value_type();
316 }
317 while (mSize < count)
318 {
319 mStorage[mSize] = value_type();
320 mSize++;
321 }
322 }
323
324 template <class T, size_t N, class Storage>
resize(size_type count,const value_type & value)325 void FixedVector<T, N, Storage>::resize(size_type count, const value_type &value)
326 {
327 ASSERT(count <= N);
328 while (mSize > count)
329 {
330 mSize--;
331 mStorage[mSize] = value_type();
332 }
333 while (mSize < count)
334 {
335 mStorage[mSize] = value;
336 mSize++;
337 }
338 }
339
340 template <class T, size_t N, class Storage>
assign_from_initializer_list(std::initializer_list<value_type> init)341 void FixedVector<T, N, Storage>::assign_from_initializer_list(
342 std::initializer_list<value_type> init)
343 {
344 for (auto element : init)
345 {
346 mStorage[mSize] = std::move(element);
347 mSize++;
348 }
349 }
350
351 template <class T, size_t N, class Storage>
full()352 bool FixedVector<T, N, Storage>::full() const
353 {
354 return (mSize == N);
355 }
356 } // namespace angle
357
358 #endif // COMMON_FIXEDVECTOR_H_
359