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