1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#pragma once
4
5namespace bs
6{
7 /** @addtogroup General
8 * @{
9 */
10
11 /**
12 * Dynamically sized container that statically allocates enough room for @p N elements of type @p Type. If the element
13 * count exceeds the statically allocated buffer size the vector falls back to general purpose dynamic allocator.
14 */
15 template <class Type, UINT32 N>
16 class SmallVector final
17 {
18 public:
19 typedef Type ValueType;
20 typedef Type* Iterator;
21 typedef const Type* ConstIterator;
22 typedef std::reverse_iterator<Type*> ReverseIterator;
23 typedef std::reverse_iterator<const Type*> ConstReverseIterator;
24
25 SmallVector() = default;
26 SmallVector(const SmallVector<ValueType, N>& other)
27 {
28 if(!other.empty())
29 *this = other;
30 }
31
32 SmallVector(SmallVector<ValueType, N>&& other)
33 {
34 if(!other.empty())
35 *this = std::move(other);
36 }
37
38 SmallVector(UINT32 size, const Type& value = Type())
39 {
40 append(size, value);
41 }
42
43 SmallVector(std::initializer_list<Type> list)
44 {
45 append(list);
46 }
47
48 ~SmallVector()
49 {
50 for (auto& entry : *this)
51 entry.~Type();
52
53 if(!isSmall())
54 bs_free(mElements);
55 }
56
57 SmallVector<ValueType, N>& operator= (const SmallVector<ValueType, N>& other)
58 {
59 if(this == &other)
60 return *this;
61
62 UINT32 mySize = size();
63 const UINT32 otherSize = other.size();
64
65 // Use assignment copy if we have more elements than the other array, and destroy any excess elements
66 if(mySize > otherSize)
67 {
68 Iterator newEnd;
69 if(otherSize > 0)
70 newEnd = std::copy(other.begin(), other.end(), begin());
71 else
72 newEnd = begin();
73
74 for(;newEnd != end(); ++newEnd)
75 (*newEnd).~Type();
76
77 }
78 // Otherwise we need to partially copy (up to our size), and do uninitialized copy for rest. And an optional
79 // grow if our capacity isn't enough (in which case we do uninitialized copy for all).
80 else
81 {
82 if (otherSize > mCapacity)
83 {
84 clear();
85 mySize = 0;
86
87 grow(otherSize);
88 }
89 else if (mySize > 0)
90 std::copy(other.begin(), other.begin() + mySize, begin());
91
92 std::uninitialized_copy(other.begin() + mySize, other.end(), begin() + mySize);
93 }
94
95 mSize = otherSize;
96 return *this;
97 }
98
99 SmallVector<ValueType, N>& operator= (SmallVector<ValueType, N>&& other)
100 {
101 if(this == &other)
102 return *this;
103
104 // If the other buffer isn't small, we can just steal its buffer
105 if(!other.isSmall())
106 {
107 for(auto& entry : *this)
108 entry.~Type();
109
110 if(!isSmall())
111 bs_free(mElements);
112
113 mElements = other.mElements;
114 other.mElements = (Type*)other.mStorage;
115 mSize = std::exchange(other.mSize, 0);
116 mCapacity = std::exchange(other.mCapacity, N);
117 }
118 // Otherwise we do essentially the same thing as in non-move assigment, except for also clearing the other
119 // vector
120 else
121 {
122 UINT32 mySize = size();
123 const UINT32 otherSize = other.size();
124
125 // Use assignment copy if we have more elements than the other array, and destroy any excess elements
126 if(mySize > otherSize)
127 {
128 Iterator newEnd;
129 if(otherSize > 0)
130 newEnd = std::move(other.begin(), other.end(), begin());
131 else
132 newEnd = begin();
133
134 for(;newEnd != end(); ++newEnd)
135 (*newEnd).~Type();
136 }
137 else
138 {
139 if (otherSize > mCapacity)
140 {
141 clear();
142 mySize = 0;
143
144 grow(otherSize);
145 }
146 else if (mySize > 0)
147 std::move(other.begin(), other.begin() + mySize, begin());
148
149 std::uninitialized_copy(
150 std::make_move_iterator(other.begin() + mySize),
151 std::make_move_iterator(other.end()),
152 begin() + mySize);
153 }
154
155 mSize = otherSize;
156 other.clear();
157 }
158
159 return *this;
160 }
161
162 SmallVector<ValueType, N>& operator=(std::initializer_list<Type> list)
163 {
164 UINT32 mySize = size();
165 const UINT32 otherSize = (UINT32)list.size();
166
167 // Use assignment copy if we have more elements than the list, and destroy any excess elements
168 if(mySize > otherSize)
169 {
170 Iterator newEnd;
171 if(otherSize > 0)
172 newEnd = std::copy(list.begin(), list.end(), begin());
173 else
174 newEnd = begin();
175
176 for(;newEnd != end(); ++newEnd)
177 (*newEnd).~Type();
178
179 }
180 // Otherwise we need to partially copy (up to our size), and do uninitialized copy for rest. And an optional
181 // grow if our capacity isn't enough (in which case we do uninitialized copy for all).
182 else
183 {
184 if (otherSize > mCapacity)
185 {
186 clear();
187 mySize = 0;
188
189 grow(otherSize);
190 }
191 else if (mySize > 0)
192 std::copy(list.begin(), list.begin() + mySize, begin());
193
194 std::uninitialized_copy(list.begin() + mySize, list.end(), begin() + mySize);
195 }
196
197 mSize = otherSize;
198 return *this;;
199 }
200
201 bool operator== (const SmallVector<ValueType, N>& other)
202 {
203 if (this->size() != other.size()) return false;
204 return std::equal(this->begin(), this->end(), other.begin());
205 }
206
207 bool operator!= (const SmallVector<ValueType, N>& other)
208 {
209 return !(*this == other);
210 }
211
212 bool operator< (const SmallVector<ValueType, N>& other) const
213 {
214 return std::lexicographical_compare(begin(), end(), other.begin(), other.end());
215 }
216
217 bool operator> (const SmallVector<ValueType, N>& other) const
218 {
219 return other < *this;
220 }
221
222 bool operator<= (const SmallVector<ValueType, N>& other) const
223 {
224 return !(other < *this);
225 }
226
227 bool operator>= (const SmallVector<ValueType, N>& other) const
228 {
229 return !(*this < other);
230 }
231
232 Type& operator[] (UINT32 index)
233 {
234 assert(index < mSize && "Array index out-of-range.");
235
236 return mElements[index];
237 }
238
239 const Type& operator[] (UINT32 index) const
240 {
241 assert(index < mSize && "Array index out-of-range.");
242
243 return mElements[index];
244 }
245
246 bool empty() const { return mSize == 0; }
247
248 Iterator begin() { return mElements; }
249 Iterator end() { return mElements + mSize; }
250
251 ConstIterator begin() const { return mElements; }
252 ConstIterator end() const { return mElements + mSize; }
253
254 ConstIterator cbegin() const { return mElements; }
255 ConstIterator cend() const { return mElements + mSize; }
256
257 ReverseIterator rbegin() { return ReverseIterator(end()); }
258 ReverseIterator rend() { return ReverseIterator(begin()); }
259
260 ConstReverseIterator rbegin() const { return ConstReverseIterator(end()); }
261 ConstReverseIterator rend() const { return ConstReverseIterator(begin()); }
262
263 ConstReverseIterator crbegin() const { return ConstReverseIterator(end()); }
264 ConstReverseIterator crend() const { return ConstReverseIterator(begin()); }
265
266 UINT32 size() const { return mSize; }
267 UINT32 capacity() const { return mCapacity; }
268
269 Type* data() { return mElements; }
270 const Type* data() const { return mElements; }
271
272 Type& front()
273 {
274 assert(!empty());
275 return mElements[0];
276 }
277
278 Type& back()
279 {
280 assert(!empty());
281 return mElements[mSize - 1];
282 }
283
284 const Type& front() const
285 {
286 assert(!empty());
287 return mElements[0];
288 }
289
290 const Type& back() const
291 {
292 assert(!empty());
293 return mElements[mSize - 1];
294 }
295
296 void add(const Type& element)
297 {
298 if (mSize == mCapacity)
299 grow(mCapacity << 1);
300
301 new (&mElements[mSize++]) Type(element);
302 }
303
304 void add(Type&& element)
305 {
306 if (mSize == mCapacity)
307 grow(mCapacity << 1);
308
309 new (&mElements[mSize++]) Type(std::move(element));
310 }
311
312 void append(ConstIterator start, ConstIterator end)
313 {
314 const UINT32 count = (UINT32)std::distance(start, end);
315
316 if ((size() + count) > capacity())
317 this->grow(size() + count);
318
319 std::uninitialized_copy(start, end, this->end());
320 mSize += count;
321 }
322
323 void append(UINT32 count, const Type& element)
324 {
325 if ((size() + count) > capacity())
326 this->grow(size() + count);
327
328 std::uninitialized_fill_n(end(), count, element);
329 mSize += count;
330 }
331
332 void append(std::initializer_list<Type> list)
333 {
334 append(list.begin(), list.end());
335 }
336
337 void pop()
338 {
339 assert(mSize > 0 && "Popping an empty array.");
340 mSize--;
341 mElements[mSize].~Type();
342 }
343
344 Iterator erase(ConstIterator iter)
345 {
346 assert(iter >= begin() && "Iterator to erase is out of bounds.");
347 assert(iter < end() && "Erasing at past-the-end iterator.");
348
349 Iterator toErase = const_cast<Iterator>(iter);
350 std::move(toErase + 1, end(), toErase);
351 pop();
352
353 return toErase;
354 }
355
356 void remove(UINT32 index)
357 {
358 erase(begin() + index);
359 }
360
361 bool contains(const Type& element)
362 {
363 for (UINT32 i = 0; i < mSize; i++)
364 {
365 if (mElements[i] == element)
366 return true;
367 }
368
369 return false;
370 }
371
372 void removeValue(const Type& element)
373 {
374 for (UINT32 i = 0; i < mSize; i++)
375 {
376 if (mElements[i] == element)
377 {
378 remove(i);
379 break;
380 }
381 }
382 }
383
384 void clear()
385 {
386 for (UINT32 i = 0; i < mSize; ++i)
387 mElements[i].~Type();
388
389 mSize = 0;
390 }
391
392 void reserve(UINT32 capacity)
393 {
394 if (capacity > mCapacity)
395 grow(capacity);
396 }
397
398 void resize(UINT32 size, const Type& value = Type())
399 {
400 if(size > mCapacity)
401 grow(size);
402
403 if(size > mSize)
404 {
405 for(UINT32 i = mSize; i < size; i++)
406 new (&mElements[i]) Type(value);
407 }
408 else
409 {
410 for(UINT32 i = size; i < mSize; i++)
411 mElements[i].~Type();
412 }
413
414 mSize = size;
415 }
416
417 private:
418 /** Returns true if the vector is still using its static memory and hasn't made any dynamic allocations. */
419 bool isSmall() const { return mElements == (Type*)mStorage; }
420
421 void grow(UINT32 capacity)
422 {
423 assert(capacity > N);
424
425 // Allocate memory with the new capacity (caller guarantees never to call this with capacity <= N, so we don't
426 // need to worry about the static buffer)
427 Type* buffer = bs_allocN<Type>(capacity);
428
429 // Move any existing elements
430 std::uninitialized_copy(
431 std::make_move_iterator(begin()),
432 std::make_move_iterator(end()),
433 buffer);
434
435 // Destoy existing elements in old memory
436 for (auto& entry : *this)
437 entry.~Type();
438
439 // If the current buffer is dynamically allocated, free it
440 if(!isSmall())
441 bs_free(mElements);
442
443 mElements = buffer;
444 mCapacity = capacity;
445 }
446
447 std::aligned_storage_t<sizeof(Type), alignof(Type)> mStorage[N];
448 Type* mElements = (Type*)mStorage;
449
450 UINT32 mSize = 0;
451 UINT32 mCapacity = N;
452 };
453
454 /** @} */
455
456 /** @cond SPECIALIZATIONS */
457
458 /**
459 * RTTIPlainType for SmallVector.
460 *
461 * @see RTTIPlainType
462 */
463 template<class T, UINT32 N> struct RTTIPlainType<SmallVector<T, N>>
464 {
465 enum { id = TID_SmallVector }; enum { hasDynamicSize = 1 };
466
467 /** @copydoc RTTIPlainType::toMemory */
468 static void toMemory(const SmallVector<T, N>& data, char* memory)
469 {
470 UINT32 size = sizeof(UINT32);
471 char* memoryStart = memory;
472 memory += sizeof(UINT32);
473
474 UINT32 numElements = (UINT32)data.size();
475 memcpy(memory, &numElements, sizeof(UINT32));
476 memory += sizeof(UINT32);
477 size += sizeof(UINT32);
478
479 for(const auto& item : data)
480 {
481 UINT32 elementSize = rttiGetElemSize(item);
482 RTTIPlainType<T>::toMemory(item, memory);
483
484 memory += elementSize;
485 size += elementSize;
486 }
487
488 memcpy(memoryStart, &size, sizeof(UINT32));
489 }
490
491 /** @copydoc RTTIPlainType::fromMemory */
492 static UINT32 fromMemory(SmallVector<T, N>& data, char* memory)
493 {
494 UINT32 size = 0;
495 memcpy(&size, memory, sizeof(UINT32));
496 memory += sizeof(UINT32);
497
498 UINT32 numElements;
499 memcpy(&numElements, memory, sizeof(UINT32));
500 memory += sizeof(UINT32);
501
502 data.clear();
503 for(UINT32 i = 0; i < numElements; i++)
504 {
505 T element;
506 UINT32 elementSize = RTTIPlainType<T>::fromMemory(element, memory);
507 data.add(element);
508
509 memory += elementSize;
510 }
511
512 return size;
513 }
514
515 /** @copydoc RTTIPlainType::getDynamicSize */
516 static UINT32 getDynamicSize(const SmallVector<T, N>& data)
517 {
518 UINT64 dataSize = sizeof(UINT32) * 2;
519
520 for(const auto& item : data)
521 dataSize += rttiGetElemSize(item);
522
523 assert(dataSize <= std::numeric_limits<UINT32>::max());
524
525 return (UINT32)dataSize;
526 }
527 };
528
529 /** @endcond */
530}