Line data Source code
1 : /* Copyright (C) 2023 Wildfire Games.
2 : * This file is part of 0 A.D.
3 : *
4 : * 0 A.D. is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 2 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * 0 A.D. is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : *
14 : * You should have received a copy of the GNU General Public License
15 : * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 : */
17 :
18 : #ifndef INCLUDED_PS_STATICVECTOR
19 : #define INCLUDED_PS_STATICVECTOR
20 :
21 : #include <algorithm>
22 : #include <array>
23 : #include <cstdint>
24 : #include <fmt/format.h>
25 : #include <initializer_list>
26 : #include <limits>
27 : #include <memory>
28 : #include <new>
29 : #include <stdexcept>
30 :
31 : namespace PS
32 : {
33 :
34 2 : struct CapacityExceededException : public std::length_error
35 : {
36 2 : using std::length_error::length_error;
37 : };
38 :
39 : template<size_t N>
40 : constexpr auto MakeSmallestCapableUnsigned()
41 : {
42 : if constexpr (N <= std::numeric_limits<uint_fast8_t>::max())
43 : return static_cast<uint_fast8_t>(0);
44 : else if constexpr (N <= std::numeric_limits<uint_fast16_t>::max())
45 : return static_cast<uint_fast16_t>(0);
46 : else if constexpr (N <= std::numeric_limits<uint_fast32_t>::max())
47 : return static_cast<uint_fast32_t>(0);
48 : else if constexpr (N <= std::numeric_limits<uint_fast64_t>::max())
49 : return static_cast<uint_fast64_t>(0);
50 : else
51 : {
52 : static_assert(N <= std::numeric_limits<uintmax_t>::max());
53 : return static_cast<uintmax_t>(0);
54 : }
55 : }
56 :
57 : template<size_t N>
58 : constexpr auto MakeSmallestCapableSigned()
59 : {
60 : // TODO C++20: Use std::cmp_*
61 : if constexpr (N <= static_cast<uintmax_t>(std::numeric_limits<int_fast8_t>::max()) &&
62 : -static_cast<intmax_t>(N) >= std::numeric_limits<int_fast8_t>::min())
63 : return static_cast<int_fast8_t>(0);
64 : else if constexpr (N <= static_cast<uintmax_t>(std::numeric_limits<int_fast16_t>::max()) &&
65 : -static_cast<intmax_t>(N) >= std::numeric_limits<int_fast16_t>::min())
66 : return static_cast<int_fast16_t>(0);
67 : else if constexpr (N <= static_cast<uintmax_t>(std::numeric_limits<int_fast32_t>::max()) &&
68 : -static_cast<intmax_t>(N) >= std::numeric_limits<int_fast32_t>::min())
69 : return static_cast<int_fast32_t>(0);
70 : else if constexpr (N <= static_cast<uintmax_t>(std::numeric_limits<int_fast64_t>::max()) &&
71 : -static_cast<intmax_t>(N) >= std::numeric_limits<int_fast64_t>::min())
72 : return static_cast<int_fast64_t>(0);
73 : else
74 : {
75 : static_assert(N <= static_cast<uintmax_t>(std::numeric_limits<intmax_t>::max()) &&
76 : -static_cast<intmax_t>(N) >= std::numeric_limits<intmax_t>::min());
77 : return static_cast<intmax_t>(0);
78 : }
79 : }
80 :
81 : /**
82 : * A conntainer close to std::vector but the elements are stored in place:
83 : * There is a fixed capacity and there is no dynamic memory allocation.
84 : * Note: moving a StaticVector will be slower than moving a std::vector in
85 : * case of sizeof(StaticVector) > sizeof(std::vector).
86 : */
87 : template<typename T, size_t N>
88 : class StaticVector
89 : {
90 : public:
91 : static_assert(std::is_nothrow_destructible_v<T>);
92 :
93 : using value_type = T;
94 : using size_type = decltype(MakeSmallestCapableUnsigned<N>());
95 : using difference_type = decltype(MakeSmallestCapableSigned<N>());
96 : using reference = value_type&;
97 : using const_reference = const value_type&;
98 : using pointer = value_type*;
99 : using const_pointer = const value_type*;
100 : using iterator = pointer;
101 : using const_iterator = const_pointer;
102 : using reverse_iterator = std::reverse_iterator<iterator>;
103 : using const_reverse_iterator = std::reverse_iterator<const_iterator>;
104 :
105 :
106 1 : StaticVector() = default;
107 7 : StaticVector(const StaticVector& other) noexcept(std::is_nothrow_copy_constructible_v<T>)
108 7 : : m_Size{other.size()}
109 : {
110 7 : std::uninitialized_copy(other.begin(), other.end(), begin());
111 7 : }
112 :
113 : template<size_t OtherN>
114 1 : explicit StaticVector(const StaticVector<T, OtherN>& other) noexcept(
115 : std::is_nothrow_copy_constructible_v<T>)
116 1 : : m_Size{other.size()}
117 : {
118 : static_assert(OtherN < N);
119 :
120 1 : std::uninitialized_copy(other.begin(), other.end(), begin());
121 1 : }
122 :
123 3 : StaticVector& operator=(const StaticVector& other) noexcept(std::is_nothrow_copy_constructible_v<T>
124 : && std::is_nothrow_copy_assignable_v<T>)
125 : {
126 3 : const size_type initializedCopies{std::min(other.size(), size())};
127 3 : std::copy_n(other.begin(), initializedCopies, begin());
128 3 : std::uninitialized_copy(other.begin() + initializedCopies, other.end(),
129 3 : begin() + initializedCopies);
130 3 : std::destroy(begin() + initializedCopies, end());
131 :
132 3 : m_Size = other.size();
133 3 : return *this;
134 : }
135 :
136 : template<size_t OtherN>
137 : StaticVector& operator=(const StaticVector<T, OtherN>& other) noexcept(
138 : std::is_nothrow_copy_constructible_v<T> && std::is_nothrow_copy_assignable_v<T>)
139 : {
140 : static_assert(OtherN < N);
141 :
142 : const size_type initializedCopies{std::min(other.size(), size())};
143 : std::copy_n(other.begin(), initializedCopies, begin());
144 : std::uninitialized_copy(other.begin() + initializedCopies, other.end(),
145 : begin() + initializedCopies);
146 : std::destroy(begin() + initializedCopies, end());
147 :
148 : m_Size = other.size();
149 : return *this;
150 : }
151 :
152 : StaticVector(StaticVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>)
153 : : m_Size{other.size()}
154 : {
155 : std::uninitialized_move(other.begin(), other.end(), begin());
156 : }
157 :
158 : template<size_t OtherN>
159 : explicit StaticVector(StaticVector<T, OtherN>&& other)
160 : noexcept(std::is_nothrow_move_constructible_v<T>)
161 : : m_Size{other.size()}
162 : {
163 : static_assert(OtherN < N);
164 :
165 : std::uninitialized_move(other.begin(), other.end(), begin());
166 : }
167 :
168 : StaticVector& operator=(StaticVector&& other) noexcept(std::is_nothrow_move_constructible_v<T> &&
169 : std::is_nothrow_move_assignable_v<T>)
170 : {
171 : const size_type initializedMoves{std::min(other.size(), size())};
172 : std::move(other.begin(), other.begin() + initializedMoves, begin());
173 : std::uninitialized_move(other.begin() + initializedMoves, other.end(),
174 : begin() + initializedMoves);
175 : std::destroy(begin() + initializedMoves, end());
176 :
177 : m_Size = other.size();
178 : return *this;
179 : }
180 :
181 : template<size_t OtherN>
182 : StaticVector& operator=(StaticVector<T, OtherN>&& other) noexcept(
183 : std::is_nothrow_move_constructible_v<T> && std::is_nothrow_move_assignable_v<T>)
184 : {
185 : static_assert(OtherN < N);
186 :
187 : const size_type initializedMoves{std::min(other.size(), size())};
188 : std::move(other.begin(), other.begin() + initializedMoves, begin());
189 : std::uninitialized_move(other.begin() + initializedMoves, other.end(),
190 : begin() + initializedMoves);
191 : std::destroy(begin() + initializedMoves, end());
192 :
193 : m_Size = other.size();
194 : return *this;
195 : }
196 :
197 28 : ~StaticVector()
198 : {
199 28 : clear();
200 28 : }
201 :
202 2 : StaticVector(const size_type count, const T& value)
203 2 : : m_Size{count}
204 : {
205 2 : if (count > N)
206 : throw CapacityExceededException{fmt::format(
207 : "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
208 0 : count, N)};
209 :
210 2 : std::uninitialized_fill(begin(), end(), value);
211 2 : }
212 :
213 3 : StaticVector(const size_type count)
214 3 : : m_Size{count}
215 : {
216 3 : if (count > N)
217 : throw CapacityExceededException{fmt::format(
218 : "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
219 1 : count, N)};
220 :
221 2 : std::uninitialized_default_construct(begin(), end());
222 2 : }
223 :
224 15 : StaticVector(const std::initializer_list<T> init)
225 15 : : m_Size{static_cast<size_type>(init.size())} // Will be tested below.
226 : {
227 15 : if (init.size() > N)
228 0 : throw CapacityExceededException{fmt::format(
229 : "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
230 0 : init.size(), N)};
231 :
232 15 : std::uninitialized_copy(init.begin(), init.end(), begin());
233 15 : }
234 :
235 : StaticVector& operator=(const std::initializer_list<T> init)
236 : {
237 : if (init.size() > N)
238 : throw CapacityExceededException{fmt::format(
239 : "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
240 : init.size(), N)};
241 :
242 : clear();
243 : std::uninitialized_copy(init.begin(), init.end(), begin());
244 : m_Size = init.size();
245 : }
246 :
247 :
248 :
249 1 : reference at(const size_type index)
250 : {
251 1 : if (index >= m_Size)
252 : throw std::out_of_range{fmt::format("Called at({}) but there are only {} elements.",
253 1 : index, size())};
254 :
255 0 : return (*this)[index];
256 : }
257 :
258 : const_reference at(const size_type index) const
259 : {
260 : if (index >= size())
261 : throw std::out_of_range{fmt::format("Called at({}) but there are only {} elements.",
262 : index, size())};
263 :
264 : return (*this)[index];
265 : }
266 :
267 8 : reference operator[](const size_type index) noexcept
268 : {
269 8 : ASSERT(index < size());
270 8 : return *(begin() + index);
271 : }
272 :
273 0 : const_reference operator[](const size_type index) const noexcept
274 : {
275 0 : ASSERT(index < size());
276 0 : return *(begin() + index);
277 : }
278 :
279 1 : reference front() noexcept
280 : {
281 1 : ASSERT(!empty());
282 1 : return *begin();
283 : }
284 :
285 : const_reference front() const noexcept
286 : {
287 : ASSERT(!empty());
288 : return *begin();
289 : }
290 :
291 5 : reference back() noexcept
292 : {
293 5 : ASSERT(!empty());
294 5 : return *std::prev(end());
295 : }
296 :
297 : const_reference back() const noexcept
298 : {
299 : ASSERT(!empty());
300 : return *std::prev(end());
301 : }
302 :
303 145 : pointer data() noexcept
304 : {
305 145 : return std::launder(reinterpret_cast<pointer>(m_Data.data()));
306 : }
307 :
308 57 : const_pointer data() const noexcept
309 : {
310 57 : return std::launder(reinterpret_cast<const_pointer>(m_Data.data()));
311 : }
312 :
313 :
314 145 : iterator begin() noexcept
315 : {
316 145 : return data();
317 : }
318 :
319 30 : const_iterator begin() const noexcept
320 : {
321 30 : return cbegin();
322 : }
323 :
324 57 : const_iterator cbegin() const noexcept
325 : {
326 57 : return data();
327 : }
328 :
329 53 : iterator end() noexcept
330 : {
331 53 : return begin() + size();
332 : }
333 :
334 27 : const_iterator end() const noexcept
335 : {
336 27 : return cend();
337 : }
338 :
339 27 : const_iterator cend() const noexcept
340 : {
341 27 : return cbegin() + size();
342 : }
343 :
344 : reverse_iterator rbegin() noexcept
345 : {
346 : return std::make_reverse_iterator(end());
347 : }
348 :
349 : const_reverse_iterator rbegin() const noexcept
350 : {
351 : return crbegin();
352 : }
353 :
354 : const_reverse_iterator crbegin() const noexcept
355 : {
356 : return std::make_reverse_iterator(end());
357 : }
358 :
359 : reverse_iterator rend() noexcept
360 : {
361 : return std::make_reverse_iterator(begin());
362 : }
363 :
364 : const_reverse_iterator rend() const noexcept
365 : {
366 : return crend();
367 : }
368 :
369 : const_reverse_iterator crend() const noexcept
370 : {
371 : return std::make_reverse_iterator(cbegin());
372 : }
373 :
374 11 : bool empty() const noexcept
375 : {
376 11 : return size() == 0;
377 : }
378 :
379 7 : bool full() const noexcept
380 : {
381 7 : return size() == N;
382 : }
383 :
384 131 : size_type size() const noexcept
385 : {
386 131 : return m_Size;
387 : }
388 :
389 : constexpr size_type capacity() const noexcept
390 : {
391 : return N;
392 : }
393 :
394 :
395 30 : void clear() noexcept
396 : {
397 30 : std::destroy(begin(), end());
398 30 : m_Size = 0;
399 30 : }
400 :
401 : /**
402 : * Inserts an element at location. The elements which were in the range
403 : * [ location, end() ) get moved no the next position.
404 : *
405 : * Exceptions:
406 : * If an exception is thrown when inserting an element at the end this
407 : * function has no effect (strong exception guarantee).
408 : * Otherwise the program is in a valid state (Basic exception guarantee).
409 : */
410 : iterator insert(const const_iterator location, const T& value)
411 : {
412 : if (full())
413 : throw CapacityExceededException{"Called insert but the StaticVector is already full"};
414 :
415 : if (location == end())
416 : return std::addressof(emplace_back(value));
417 :
418 : new(end()) T{std::move(back())};
419 : ++m_Size;
420 :
421 : const iterator mutableLocation{MutableIter(location)};
422 : std::move_backward(mutableLocation, std::prev(end(), 2), std::prev(end(), 1));
423 :
424 : *mutableLocation = value;
425 : return mutableLocation;
426 : }
427 :
428 : /**
429 : * Same as above but the new element is move-constructed.
430 : *
431 : * If an exception is thrown when inserting an element at the end this
432 : * function has no effect (strong exception guarantee).
433 : * If an exception is thrown the program is in a valid state
434 : * (Basic exception guarantee).
435 : */
436 1 : iterator insert(const const_iterator location, T&& value)
437 : {
438 1 : if (full())
439 0 : throw CapacityExceededException{"Called insert but the StaticVector is already full"};
440 :
441 1 : if (location == end())
442 0 : return std::addressof(emplace_back(std::move(value)));
443 :
444 1 : const iterator mutableLocation{MakeMutableIterator(location)};
445 1 : new(end()) T{std::move(back())};
446 1 : ++m_Size;
447 :
448 1 : std::move_backward(mutableLocation, end() - 2, end() -1);
449 :
450 1 : *mutableLocation = std::move(value);
451 1 : return mutableLocation;
452 : }
453 :
454 : /**
455 : * If an exception is thrown this function has no effect
456 : * (strong exception guarantee).
457 : */
458 2 : void push_back(const T& value)
459 : {
460 2 : emplace_back(value);
461 2 : }
462 :
463 : /**
464 : * If an exception is thrown this function has no effect
465 : * (strong exception guarantee).
466 : */
467 1 : void push_back(T&& value)
468 : {
469 1 : emplace_back(std::move(value));
470 1 : }
471 :
472 : /**
473 : * If an exception is thrown this function has no effect
474 : * (strong exception guarantee).
475 : */
476 : template<typename... Args>
477 6 : reference emplace_back(Args&&... args)
478 : {
479 6 : if (full())
480 : throw CapacityExceededException{
481 1 : "Called emplace_back but the StaticVector is already full"};
482 :
483 5 : const iterator location{begin() + size()};
484 5 : new(location) T{std::forward<Args>(args)...};
485 5 : ++m_Size;
486 5 : return *location;
487 : }
488 :
489 4 : void pop_back() noexcept
490 : {
491 4 : ASSERT(!empty());
492 4 : std::destroy_at(std::addressof(back()));
493 4 : --m_Size;
494 4 : }
495 :
496 : /**
497 : * Constructs or destructs elements to adjust to newSize. After this call
498 : * the StaticVector contains newSize elements. Unlike std::vector the
499 : * capacity does not get changed. If newSize is bigger then the capacity
500 : * a CapacityExceededException is thrown.
501 : *
502 : * If newSize is smaller than size() (shrinking) no exception is thrown
503 : * (Nothrow exception guarantee).
504 : * If an exception is thrown this function has no effect.
505 : * (strong exception guarantee)
506 : */
507 : void resize(const size_type newSize)
508 : {
509 : if (newSize > N)
510 : throw CapacityExceededException{fmt::format(
511 : "Can not resize StaticVector to {} the capacity is {}", newSize, N)};
512 :
513 : if (newSize > size())
514 : std::uninitialized_default_construct(end(), begin() + newSize);
515 : else
516 : std::destroy(begin() + newSize, end());
517 :
518 : m_Size = newSize;
519 : }
520 :
521 : /**
522 : * Same as above but uses value to copy-construct the new elements.
523 : *
524 : * If newSize is smaller than size() (shrinking) no exception is thrown
525 : * (Nothrow exception guarantee).
526 : * If an exception is thrown this function has no effect.
527 : * (strong exception guarantee)
528 : */
529 : void resize(const size_type newSize, const T& value)
530 : {
531 : if (newSize > N)
532 : throw CapacityExceededException{fmt::format(
533 : "Can't resize the StaticVector to {} the capacity is {}", newSize, N)};
534 :
535 : if (newSize > size())
536 : std::uninitialized_fill(end(), begin() + newSize, value);
537 : else
538 : std::destroy(begin() + newSize, end());
539 :
540 : m_Size = newSize;
541 : }
542 :
543 : template<size_t OtherN>
544 8 : friend bool operator==(const StaticVector<T, N>& lhs, const StaticVector<T, OtherN>& rhs)
545 : {
546 8 : return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
547 : }
548 :
549 : template<size_t OtherN>
550 5 : friend bool operator!=(const StaticVector<T, N>& lhs, const StaticVector<T, OtherN>& rhs)
551 : {
552 5 : return !(lhs == rhs);
553 : }
554 :
555 : private:
556 1 : iterator MakeMutableIterator(const const_iterator iter) noexcept
557 : {
558 1 : return begin() + (iter - begin());
559 : }
560 :
561 : using EagerInitialized = std::array<T, N>;
562 : alignas(EagerInitialized) std::array<std::byte, sizeof(T) * N> m_Data;
563 : size_type m_Size{0};
564 : };
565 :
566 : } // namespace PS
567 :
568 : #endif // INCLUDED_PS_STATICVECTOR
|
