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 // FastVector.h:
7 //   A vector class with a initial fixed size and variable growth.
8 //   Based on FixedVector.
9 //
10 
11 #ifndef COMMON_FASTVECTOR_H_
12 #define COMMON_FASTVECTOR_H_
13 
14 #include "common/debug.h"
15 
16 #include <algorithm>
17 #include <array>
18 #include <initializer_list>
19 
20 namespace angle
21 {
22 template <class T, size_t N, class Storage = std::array<T, N>>
23 class FastVector final
24 {
25   public:
26     using value_type      = typename Storage::value_type;
27     using size_type       = typename Storage::size_type;
28     using reference       = typename Storage::reference;
29     using const_reference = typename Storage::const_reference;
30     using pointer         = typename Storage::pointer;
31     using const_pointer   = typename Storage::const_pointer;
32     using iterator        = T *;
33     using const_iterator  = const T *;
34 
35     FastVector();
36     FastVector(size_type count, const value_type &value);
37     FastVector(size_type count);
38 
39     FastVector(const FastVector<T, N, Storage> &other);
40     FastVector(FastVector<T, N, Storage> &&other);
41     FastVector(std::initializer_list<value_type> init);
42 
43     FastVector<T, N, Storage> &operator=(const FastVector<T, N, Storage> &other);
44     FastVector<T, N, Storage> &operator=(FastVector<T, N, Storage> &&other);
45     FastVector<T, N, Storage> &operator=(std::initializer_list<value_type> init);
46 
47     ~FastVector();
48 
49     reference at(size_type pos);
50     const_reference at(size_type pos) const;
51 
52     reference operator[](size_type pos);
53     const_reference operator[](size_type pos) const;
54 
55     pointer data();
56     const_pointer data() const;
57 
58     iterator begin();
59     const_iterator begin() const;
60 
61     iterator end();
62     const_iterator end() const;
63 
64     bool empty() const;
65     size_type size() const;
66 
67     void clear();
68 
69     void push_back(const value_type &value);
70     void push_back(value_type &&value);
71 
72     void pop_back();
73 
74     reference front();
75     const_reference front() const;
76 
77     reference back();
78     const_reference back() const;
79 
80     void swap(FastVector<T, N, Storage> &other);
81 
82     void resize(size_type count);
83     void resize(size_type count, const value_type &value);
84 
85     // Specialty function that removes a known element and might shuffle the list.
86     void remove_and_permute(const value_type &element);
87 
88   private:
89     void assign_from_initializer_list(std::initializer_list<value_type> init);
90     void ensure_capacity(size_t capacity);
91     bool uses_fixed_storage() const;
92 
93     Storage mFixedStorage;
94     pointer mData           = mFixedStorage.data();
95     size_type mSize         = 0;
96     size_type mReservedSize = N;
97 };
98 
99 template <class T, size_t N, class StorageN, size_t M, class StorageM>
100 bool operator==(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
101 {
102     return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
103 }
104 
105 template <class T, size_t N, class StorageN, size_t M, class StorageM>
106 bool operator!=(const FastVector<T, N, StorageN> &a, const FastVector<T, M, StorageM> &b)
107 {
108     return !(a == b);
109 }
110 
111 template <class T, size_t N, class Storage>
uses_fixed_storage()112 ANGLE_INLINE bool FastVector<T, N, Storage>::uses_fixed_storage() const
113 {
114     return mData == mFixedStorage.data();
115 }
116 
117 template <class T, size_t N, class Storage>
FastVector()118 FastVector<T, N, Storage>::FastVector()
119 {}
120 
121 template <class T, size_t N, class Storage>
FastVector(size_type count,const value_type & value)122 FastVector<T, N, Storage>::FastVector(size_type count, const value_type &value)
123 {
124     ensure_capacity(count);
125     mSize = count;
126     std::fill(begin(), end(), value);
127 }
128 
129 template <class T, size_t N, class Storage>
FastVector(size_type count)130 FastVector<T, N, Storage>::FastVector(size_type count)
131 {
132     ensure_capacity(count);
133     mSize = count;
134 }
135 
136 template <class T, size_t N, class Storage>
FastVector(const FastVector<T,N,Storage> & other)137 FastVector<T, N, Storage>::FastVector(const FastVector<T, N, Storage> &other)
138 {
139     ensure_capacity(other.mSize);
140     mSize = other.mSize;
141     std::copy(other.begin(), other.end(), begin());
142 }
143 
144 template <class T, size_t N, class Storage>
FastVector(FastVector<T,N,Storage> && other)145 FastVector<T, N, Storage>::FastVector(FastVector<T, N, Storage> &&other) : FastVector()
146 {
147     swap(other);
148 }
149 
150 template <class T, size_t N, class Storage>
FastVector(std::initializer_list<value_type> init)151 FastVector<T, N, Storage>::FastVector(std::initializer_list<value_type> init)
152 {
153     assign_from_initializer_list(init);
154 }
155 
156 template <class T, size_t N, class Storage>
157 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
158     const FastVector<T, N, Storage> &other)
159 {
160     ensure_capacity(other.mSize);
161     mSize = other.mSize;
162     std::copy(other.begin(), other.end(), begin());
163     return *this;
164 }
165 
166 template <class T, size_t N, class Storage>
167 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(FastVector<T, N, Storage> &&other)
168 {
169     swap(*this, other);
170     return *this;
171 }
172 
173 template <class T, size_t N, class Storage>
174 FastVector<T, N, Storage> &FastVector<T, N, Storage>::operator=(
175     std::initializer_list<value_type> init)
176 {
177     assign_from_initializer_list(init);
178     return *this;
179 }
180 
181 template <class T, size_t N, class Storage>
~FastVector()182 FastVector<T, N, Storage>::~FastVector()
183 {
184     clear();
185     if (!uses_fixed_storage())
186     {
187         delete[] mData;
188     }
189 }
190 
191 template <class T, size_t N, class Storage>
at(size_type pos)192 typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::at(size_type pos)
193 {
194     ASSERT(pos < mSize);
195     return mData[pos];
196 }
197 
198 template <class T, size_t N, class Storage>
at(size_type pos)199 typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::at(
200     size_type pos) const
201 {
202     ASSERT(pos < mSize);
203     return mData[pos];
204 }
205 
206 template <class T, size_t N, class Storage>
207 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::operator[](
208     size_type pos)
209 {
210     ASSERT(pos < mSize);
211     return mData[pos];
212 }
213 
214 template <class T, size_t N, class Storage>
215 ANGLE_INLINE
216     typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::operator[](
217         size_type pos) const
218 {
219     ASSERT(pos < mSize);
220     return mData[pos];
221 }
222 
223 template <class T, size_t N, class Storage>
224 ANGLE_INLINE typename FastVector<T, N, Storage>::const_pointer
data()225 angle::FastVector<T, N, Storage>::data() const
226 {
227     return mData;
228 }
229 
230 template <class T, size_t N, class Storage>
data()231 ANGLE_INLINE typename FastVector<T, N, Storage>::pointer angle::FastVector<T, N, Storage>::data()
232 {
233     return mData;
234 }
235 
236 template <class T, size_t N, class Storage>
begin()237 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::begin()
238 {
239     return mData;
240 }
241 
242 template <class T, size_t N, class Storage>
begin()243 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::begin()
244     const
245 {
246     return mData;
247 }
248 
249 template <class T, size_t N, class Storage>
end()250 ANGLE_INLINE typename FastVector<T, N, Storage>::iterator FastVector<T, N, Storage>::end()
251 {
252     return mData + mSize;
253 }
254 
255 template <class T, size_t N, class Storage>
end()256 ANGLE_INLINE typename FastVector<T, N, Storage>::const_iterator FastVector<T, N, Storage>::end()
257     const
258 {
259     return mData + mSize;
260 }
261 
262 template <class T, size_t N, class Storage>
empty()263 ANGLE_INLINE bool FastVector<T, N, Storage>::empty() const
264 {
265     return mSize == 0;
266 }
267 
268 template <class T, size_t N, class Storage>
size()269 ANGLE_INLINE typename FastVector<T, N, Storage>::size_type FastVector<T, N, Storage>::size() const
270 {
271     return mSize;
272 }
273 
274 template <class T, size_t N, class Storage>
clear()275 void FastVector<T, N, Storage>::clear()
276 {
277     resize(0);
278 }
279 
280 template <class T, size_t N, class Storage>
push_back(const value_type & value)281 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(const value_type &value)
282 {
283     if (mSize == mReservedSize)
284         ensure_capacity(mSize + 1);
285     mData[mSize++] = value;
286 }
287 
288 template <class T, size_t N, class Storage>
push_back(value_type && value)289 ANGLE_INLINE void FastVector<T, N, Storage>::push_back(value_type &&value)
290 {
291     if (mSize == mReservedSize)
292         ensure_capacity(mSize + 1);
293     mData[mSize++] = std::move(value);
294 }
295 
296 template <class T, size_t N, class Storage>
pop_back()297 ANGLE_INLINE void FastVector<T, N, Storage>::pop_back()
298 {
299     ASSERT(mSize > 0);
300     mSize--;
301 }
302 
303 template <class T, size_t N, class Storage>
front()304 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::front()
305 {
306     ASSERT(mSize > 0);
307     return mData[0];
308 }
309 
310 template <class T, size_t N, class Storage>
front()311 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::front()
312     const
313 {
314     ASSERT(mSize > 0);
315     return mData[0];
316 }
317 
318 template <class T, size_t N, class Storage>
back()319 ANGLE_INLINE typename FastVector<T, N, Storage>::reference FastVector<T, N, Storage>::back()
320 {
321     ASSERT(mSize > 0);
322     return mData[mSize - 1];
323 }
324 
325 template <class T, size_t N, class Storage>
back()326 ANGLE_INLINE typename FastVector<T, N, Storage>::const_reference FastVector<T, N, Storage>::back()
327     const
328 {
329     ASSERT(mSize > 0);
330     return mData[mSize - 1];
331 }
332 
333 template <class T, size_t N, class Storage>
swap(FastVector<T,N,Storage> & other)334 void FastVector<T, N, Storage>::swap(FastVector<T, N, Storage> &other)
335 {
336     std::swap(mSize, other.mSize);
337 
338     pointer tempData = other.mData;
339     if (uses_fixed_storage())
340         other.mData = other.mFixedStorage.data();
341     else
342         other.mData = mData;
343     if (tempData == other.mFixedStorage.data())
344         mData = mFixedStorage.data();
345     else
346         mData = tempData;
347     std::swap(mReservedSize, other.mReservedSize);
348 
349     if (uses_fixed_storage() || other.uses_fixed_storage())
350         std::swap(mFixedStorage, other.mFixedStorage);
351 }
352 
353 template <class T, size_t N, class Storage>
resize(size_type count)354 void FastVector<T, N, Storage>::resize(size_type count)
355 {
356     if (count > mSize)
357     {
358         ensure_capacity(count);
359     }
360     mSize = count;
361 }
362 
363 template <class T, size_t N, class Storage>
resize(size_type count,const value_type & value)364 void FastVector<T, N, Storage>::resize(size_type count, const value_type &value)
365 {
366     if (count > mSize)
367     {
368         ensure_capacity(count);
369         std::fill(mData + mSize, mData + count, value);
370     }
371     mSize = count;
372 }
373 
374 template <class T, size_t N, class Storage>
assign_from_initializer_list(std::initializer_list<value_type> init)375 void FastVector<T, N, Storage>::assign_from_initializer_list(std::initializer_list<value_type> init)
376 {
377     ensure_capacity(init.size());
378     mSize        = init.size();
379     size_t index = 0;
380     for (auto &value : init)
381     {
382         mData[index++] = value;
383     }
384 }
385 
386 template <class T, size_t N, class Storage>
remove_and_permute(const value_type & element)387 ANGLE_INLINE void FastVector<T, N, Storage>::remove_and_permute(const value_type &element)
388 {
389     size_t len = mSize - 1;
390     for (size_t index = 0; index < len; ++index)
391     {
392         if (mData[index] == element)
393         {
394             mData[index] = std::move(mData[len]);
395             break;
396         }
397     }
398     pop_back();
399 }
400 
401 template <class T, size_t N, class Storage>
ensure_capacity(size_t capacity)402 void FastVector<T, N, Storage>::ensure_capacity(size_t capacity)
403 {
404     // We have a minimum capacity of N.
405     if (mReservedSize < capacity)
406     {
407         ASSERT(capacity > N);
408         size_type newSize = std::max(mReservedSize, N);
409         while (newSize < capacity)
410         {
411             newSize *= 2;
412         }
413 
414         pointer newData = new value_type[newSize];
415 
416         if (mSize > 0)
417         {
418             std::move(begin(), end(), newData);
419         }
420 
421         if (!uses_fixed_storage())
422         {
423             delete[] mData;
424         }
425 
426         mData         = newData;
427         mReservedSize = newSize;
428     }
429 }
430 }  // namespace angle
431 
432 #endif  // COMMON_FASTVECTOR_H_
433