Index: ps/trunk/source/ps/containers/StaticVector.h
===================================================================
--- ps/trunk/source/ps/containers/StaticVector.h (nonexistent)
+++ ps/trunk/source/ps/containers/StaticVector.h (revision 27329)
@@ -0,0 +1,568 @@
+/* Copyright (C) 2022 Wildfire Games.
+ * This file is part of 0 A.D.
+ *
+ * 0 A.D. is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * 0 A.D. is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with 0 A.D. If not, see .
+ */
+
+#ifndef INCLUDED_PS_STATICVECTOR
+#define INCLUDED_PS_STATICVECTOR
+
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+
+namespace PS
+{
+
+struct CapacityExceededException : public std::length_error
+{
+ using std::length_error::length_error;
+};
+
+template
+constexpr auto MakeSmallestCapableUnsigned()
+{
+ if constexpr (N <= std::numeric_limits::max())
+ return static_cast(0);
+ else if constexpr (N <= std::numeric_limits::max())
+ return static_cast(0);
+ else if constexpr (N <= std::numeric_limits::max())
+ return static_cast(0);
+ else if constexpr (N <= std::numeric_limits::max())
+ return static_cast(0);
+ else
+ {
+ static_assert(N <= std::numeric_limits::max());
+ return static_cast(0);
+ }
+}
+
+template
+constexpr auto MakeSmallestCapableSigned()
+{
+ // TODO C++20: Use std::cmp_*
+ if constexpr (N <= static_cast(std::numeric_limits::max()) &&
+ -static_cast(N) >= std::numeric_limits::min())
+ return static_cast(0);
+ else if constexpr (N <= static_cast(std::numeric_limits::max()) &&
+ -static_cast(N) >= std::numeric_limits::min())
+ return static_cast(0);
+ else if constexpr (N <= static_cast(std::numeric_limits::max()) &&
+ -static_cast(N) >= std::numeric_limits::min())
+ return static_cast(0);
+ else if constexpr (N <= static_cast(std::numeric_limits::max()) &&
+ -static_cast(N) >= std::numeric_limits::min())
+ return static_cast(0);
+ else
+ {
+ static_assert(N <= static_cast(std::numeric_limits::max()) &&
+ -static_cast(N) >= std::numeric_limits::min());
+ return static_cast(0);
+ }
+}
+
+/**
+ * A conntainer close to std::vector but the elements are stored in place:
+ * There is a fixed capacity and there is no dynamic memory allocation.
+ * Note: moving a StaticVector will be slower than moving a std::vector in
+ * case of sizeof(StaticVector) > sizeof(std::vector).
+ */
+template
+class StaticVector
+{
+public:
+ static_assert(std::is_nothrow_destructible_v);
+
+ using value_type = T;
+ using size_type = decltype(MakeSmallestCapableUnsigned());
+ using difference_type = decltype(MakeSmallestCapableSigned());
+ using reference = value_type&;
+ using const_reference = const value_type&;
+ using pointer = value_type*;
+ using const_pointer = const value_type*;
+ using iterator = pointer;
+ using const_iterator = const_pointer;
+ using reverse_iterator = std::reverse_iterator;
+ using const_reverse_iterator = std::reverse_iterator;
+
+
+ StaticVector() = default;
+ StaticVector(const StaticVector& other) noexcept(std::is_nothrow_copy_constructible_v)
+ : m_Size{other.size()}
+ {
+ std::uninitialized_copy(other.begin(), other.end(), begin());
+ }
+
+ template
+ explicit StaticVector(const StaticVector& other) noexcept(
+ std::is_nothrow_copy_constructible_v)
+ : m_Size{other.size()}
+ {
+ static_assert(OtherN < N);
+
+ std::uninitialized_copy(other.begin(), other.end(), begin());
+ }
+
+ StaticVector& operator=(const StaticVector& other) noexcept(std::is_nothrow_copy_constructible_v
+ && std::is_nothrow_copy_assignable_v)
+ {
+ const size_type initializedCopies{std::min(other.size(), size())};
+ std::copy_n(other.begin(), initializedCopies, begin());
+ std::uninitialized_copy(other.begin() + initializedCopies, other.end(),
+ begin() + initializedCopies);
+ std::destroy(begin() + initializedCopies, end());
+
+ m_Size = other.size();
+ return *this;
+ }
+
+ template
+ StaticVector& operator=(const StaticVector& other) noexcept(
+ std::is_nothrow_copy_constructible_v && std::is_nothrow_copy_assignable_v)
+ {
+ static_assert(OtherN < N);
+
+ const size_type initializedCopies{std::min(other.size(), size())};
+ std::copy_n(other.begin(), initializedCopies, begin());
+ std::uninitialized_copy(other.begin() + initializedCopies, other.end(),
+ begin() + initializedCopies);
+ std::destroy(begin() + initializedCopies, end());
+
+ m_Size = other.size();
+ return *this;
+ }
+
+ StaticVector(StaticVector&& other) noexcept(std::is_nothrow_move_constructible_v)
+ : m_Size{other.size()}
+ {
+ std::uninitialized_move(other.begin(), other.end(), begin());
+ }
+
+ template
+ explicit StaticVector(StaticVector&& other)
+ noexcept(std::is_nothrow_move_constructible_v)
+ : m_Size{other.size()}
+ {
+ static_assert(OtherN < N);
+
+ std::uninitialized_move(other.begin(), other.end(), begin());
+ }
+
+ StaticVector& operator=(StaticVector&& other) noexcept(std::is_nothrow_move_constructible_v &&
+ std::is_nothrow_move_assignable_v)
+ {
+ const size_type initializedMoves{std::min(other.size(), size())};
+ std::move(other.begin(), other.begin() + initializedMoves, begin());
+ std::uninitialized_move(other.begin() + initializedMoves, other.end(),
+ begin() + initializedMoves);
+ std::destroy(begin() + initializedMoves, end());
+
+ m_Size = other.size();
+ return *this;
+ }
+
+ template
+ StaticVector& operator=(StaticVector&& other) noexcept(
+ std::is_nothrow_move_constructible_v && std::is_nothrow_move_assignable_v)
+ {
+ static_assert(OtherN < N);
+
+ const size_type initializedMoves{std::min(other.size(), size())};
+ std::move(other.begin(), other.begin() + initializedMoves, begin());
+ std::uninitialized_move(other.begin() + initializedMoves, other.end(),
+ begin() + initializedMoves);
+ std::destroy(begin() + initializedMoves, end());
+
+ m_Size = other.size();
+ return *this;
+ }
+
+ ~StaticVector()
+ {
+ clear();
+ }
+
+ StaticVector(const size_type count, const T& value)
+ : m_Size{count}
+ {
+ if (count > N)
+ throw CapacityExceededException{fmt::format(
+ "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
+ count, N)};
+
+ std::uninitialized_fill(begin(), end(), value);
+ }
+
+ StaticVector(const size_type count)
+ : m_Size{count}
+ {
+ if (count > N)
+ throw CapacityExceededException{fmt::format(
+ "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
+ count, N)};
+
+ std::uninitialized_default_construct(begin(), end());
+ }
+
+ StaticVector(const std::initializer_list init)
+ : m_Size{static_cast(init.size())} // Will be tested below.
+ {
+ if (init.size() > N)
+ throw CapacityExceededException{fmt::format(
+ "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
+ init.size(), N)};
+
+ std::uninitialized_copy(init.begin(), init.end(), begin());
+ }
+
+ StaticVector& operator=(const std::initializer_list init)
+ {
+ if (init.size() > N)
+ throw CapacityExceededException{fmt::format(
+ "Tried to construct a StaticVector with a size of {} but the capacity is only {}",
+ init.size(), N)};
+
+ clear();
+ std::uninitialized_copy(init.begin(), init.end(), begin());
+ m_Size = init.size();
+ }
+
+
+
+ reference at(const size_type index)
+ {
+ if (index >= m_Size)
+ throw std::out_of_range{fmt::format("Called at({}) but there are only {} elements.",
+ index, size())};
+
+ return (*this)[index];
+ }
+
+ const_reference at(const size_type index) const
+ {
+ if (index >= size())
+ throw std::out_of_range{fmt::format("Called at({}) but there are only {} elements.",
+ index, size())};
+
+ return (*this)[index];
+ }
+
+ reference operator[](const size_type index) noexcept
+ {
+ ASSERT(index < size());
+ return *(begin() + index);
+ }
+
+ const_reference operator[](const size_type index) const noexcept
+ {
+ ASSERT(index < size());
+ return *(begin() + index);
+ }
+
+ reference front() noexcept
+ {
+ ASSERT(!empty());
+ return *begin();
+ }
+
+ const_reference front() const noexcept
+ {
+ ASSERT(!empty());
+ return *begin();
+ }
+
+ reference back() noexcept
+ {
+ ASSERT(!empty());
+ return *std::prev(end());
+ }
+
+ const_reference back() const noexcept
+ {
+ ASSERT(!empty());
+ return *std::prev(end());
+ }
+
+ pointer data() noexcept
+ {
+ return std::launder(reinterpret_cast(m_Data.data()));
+ }
+
+ const_pointer data() const noexcept
+ {
+ return std::launder(reinterpret_cast(m_Data.data()));
+ }
+
+
+ iterator begin() noexcept
+ {
+ return data();
+ }
+
+ const_iterator begin() const noexcept
+ {
+ return cbegin();
+ }
+
+ const_iterator cbegin() const noexcept
+ {
+ return data();
+ }
+
+ iterator end() noexcept
+ {
+ return begin() + size();
+ }
+
+ const_iterator end() const noexcept
+ {
+ return cend();
+ }
+
+ const_iterator cend() const noexcept
+ {
+ return cbegin() + size();
+ }
+
+ reverse_iterator rbegin() noexcept
+ {
+ return std::make_reverse_iterator(end());
+ }
+
+ const_reverse_iterator rbegin() const noexcept
+ {
+ return crbegin();
+ }
+
+ const_reverse_iterator crbegin() const noexcept
+ {
+ return std::make_reverse_iterator(end());
+ }
+
+ reverse_iterator rend() noexcept
+ {
+ return std::make_reverse_iterator(begin());
+ }
+
+ const_reverse_iterator rend() const noexcept
+ {
+ return crend();
+ }
+
+ const_reverse_iterator crend() const noexcept
+ {
+ return std::make_reverse_iterator(cbegin());
+ }
+
+ bool empty() const noexcept
+ {
+ return size() == 0;
+ }
+
+ bool full() const noexcept
+ {
+ return size() == N;
+ }
+
+ size_type size() const noexcept
+ {
+ return m_Size;
+ }
+
+ constexpr size_type capacity() const noexcept
+ {
+ return N;
+ }
+
+
+ void clear() noexcept
+ {
+ std::destroy(begin(), end());
+ m_Size = 0;
+ }
+
+ /**
+ * Inserts an element at location. The elements which were in the range
+ * [ location, end() ) get moved no the next position.
+ *
+ * Exceptions:
+ * If an exception is thrown when inserting an element at the end this
+ * function has no effect (strong exception guarantee).
+ * Otherwise the program is in a valid state (Basic exception guarantee).
+ */
+ iterator insert(const const_iterator location, const T& value)
+ {
+ if (full())
+ throw CapacityExceededException{"Called insert but the StaticVector is already full"};
+
+ if (location == end())
+ return std::addressof(emplace_back(value));
+
+ new(end()) T{std::move(back())};
+ ++m_Size;
+
+ const iterator mutableLocation{MutableIter(location)};
+ std::move_backward(mutableLocation, std::prev(end(), 2), std::prev(end(), 1));
+
+ *mutableLocation = value;
+ return mutableLocation;
+ }
+
+ /**
+ * Same as above but the new element is move-constructed.
+ *
+ * If an exception is thrown when inserting an element at the end this
+ * function has no effect (strong exception guarantee).
+ * If an exception is thrown the program is in a valid state
+ * (Basic exception guarantee).
+ */
+ iterator insert(const const_iterator location, T&& value)
+ {
+ if (full())
+ throw CapacityExceededException{"Called insert but the StaticVector is already full"};
+
+ if (location == end())
+ return std::addressof(emplace_back(std::move(value)));
+
+ const iterator mutableLocation{MakeMutableIterator(location)};
+ new(end()) T{std::move(back())};
+ ++m_Size;
+
+ std::move_backward(mutableLocation, end() - 2, end() -1);
+
+ *mutableLocation = std::move(value);
+ return mutableLocation;
+ }
+
+ /**
+ * If an exception is thrown this function has no effect
+ * (strong exception guarantee).
+ */
+ void push_back(const T& value)
+ {
+ emplace_back(value);
+ }
+
+ /**
+ * If an exception is thrown this function has no effect
+ * (strong exception guarantee).
+ */
+ void push_back(T&& value)
+ {
+ emplace_back(std::move(value));
+ }
+
+ /**
+ * If an exception is thrown this function has no effect
+ * (strong exception guarantee).
+ */
+ template
+ reference emplace_back(Args&&... args)
+ {
+ if (full())
+ throw CapacityExceededException{
+ "Called emplace_back but the StaticVector is already full"};
+
+ const iterator location{begin() + size()};
+ new(location) T{std::forward(args)...};
+ ++m_Size;
+ return *location;
+ }
+
+ void pop_back() noexcept
+ {
+ ASSERT(!empty());
+ std::destroy_at(std::addressof(back()));
+ --m_Size;
+ }
+
+ /**
+ * Constructs or destructs elements to adjust to newSize. After this call
+ * the StaticVector contains newSize elements. Unlike std::vector the
+ * capacity does not get changed. If newSize is bigger then the capacity
+ * a CapacityExceededException is thrown.
+ *
+ * If newSize is smaller than size() (shrinking) no exception is thrown
+ * (Nothrow exception guarantee).
+ * If an exception is thrown this function has no effect.
+ * (strong exception guarantee)
+ */
+ void resize(const size_type newSize)
+ {
+ if (newSize > N)
+ throw CapacityExceededException{fmt::format(
+ "Can not resize StaticVector to {} the capacity is {}", newSize, N)};
+
+ if (newSize > size())
+ std::uninitialized_default_construct(end(), begin() + newSize);
+ else
+ std::destroy(begin() + newSize, end());
+
+ m_Size = newSize;
+ }
+
+ /**
+ * Same as above but uses value to copy-construct the new elements.
+ *
+ * If newSize is smaller than size() (shrinking) no exception is thrown
+ * (Nothrow exception guarantee).
+ * If an exception is thrown this function has no effect.
+ * (strong exception guarantee)
+ */
+ void resize(const size_type newSize, const T& value)
+ {
+ if (newSize > N)
+ throw CapacityExceededException{fmt::format(
+ "Can't resize the StaticVector to {} the capacity is {}", newSize, N)};
+
+ if (newSize > size())
+ std::uninitialized_fill(end(), begin() + newSize, value);
+ else
+ std::destroy(begin() + newSize, end());
+
+ m_Size = newSize;
+ }
+
+ template
+ friend bool operator==(const StaticVector& lhs, const StaticVector& rhs)
+ {
+ return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+ }
+
+ template
+ friend bool operator!=(const StaticVector& lhs, const StaticVector& rhs)
+ {
+ return !(lhs == rhs);
+ }
+
+private:
+ iterator MakeMutableIterator(const const_iterator iter) noexcept
+ {
+ return begin() + (iter - begin());
+ }
+
+ using EagerInitialized = std::array;
+ alignas(EagerInitialized) std::array m_Data;
+ size_type m_Size{0};
+};
+
+} // namespace PS
+
+#endif // INCLUDED_PS_STATICVECTOR
Property changes on: ps/trunk/source/ps/containers/StaticVector.h
___________________________________________________________________
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
Index: ps/trunk/source/ps/containers/tests/test_StaticVector.h
===================================================================
--- ps/trunk/source/ps/containers/tests/test_StaticVector.h (nonexistent)
+++ ps/trunk/source/ps/containers/tests/test_StaticVector.h (revision 27329)
@@ -0,0 +1,216 @@
+/* Copyright (C) 2022 Wildfire Games.
+ * This file is part of 0 A.D.
+ *
+ * 0 A.D. is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * 0 A.D. is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with 0 A.D. If not, see .
+ */
+
+#include "lib/self_test.h"
+
+#include "ps/containers/StaticVector.h"
+
+#include
+#include
+#include
+#include
+
+class TestStaticVector : public CxxTest::TestSuite
+{
+public:
+ class ConstructionCounter
+ {
+ public:
+ ConstructionCounter(size_t& count) :
+ m_Count{count}
+ {
+ ++m_Count;
+ }
+
+ ConstructionCounter(const ConstructionCounter& other) :
+ m_Count{other.m_Count}
+ {
+ ++m_Count;
+ }
+
+ ConstructionCounter& operator=(const ConstructionCounter&)
+ {
+ return *this;
+ }
+
+ ConstructionCounter(ConstructionCounter&& other) :
+ m_Count{other.m_Count}
+ {
+ ++m_Count;
+ }
+
+ ConstructionCounter& operator=(ConstructionCounter&&)
+ {
+ return *this;
+ }
+
+ ~ConstructionCounter()
+ {
+ --m_Count;
+ }
+
+ friend bool operator==(const ConstructionCounter&, const ConstructionCounter&)
+ {
+ return true;
+ }
+
+ private:
+ size_t& m_Count;
+ };
+
+ void test_construction()
+ {
+ size_t count{0};
+ {
+ PS::StaticVector vec{ConstructionCounter{count}};
+ TS_ASSERT_EQUALS(count, 1);
+ TS_ASSERT_EQUALS(vec.size(), 1);
+
+ vec.pop_back();
+ TS_ASSERT_EQUALS(count, 0);
+ TS_ASSERT_EQUALS(vec.size(), 0);
+
+ vec.push_back(count);
+ TS_ASSERT_EQUALS(count, 1);
+ {
+ ConstructionCounter lval{count};
+ vec.push_back(lval);
+ vec.push_back(lval);
+ }
+ TS_ASSERT_EQUALS(count, 3);
+ TS_ASSERT_EQUALS(vec.end() - vec.begin(), 3);
+
+ vec.pop_back();
+ TS_ASSERT_EQUALS(count, 2);
+
+ vec.clear();
+ TS_ASSERT_EQUALS(count, 0);
+ TS_ASSERT(vec.empty());
+
+ vec.emplace_back(count);
+ vec.insert(vec.begin(), ConstructionCounter{count});
+ TS_ASSERT_EQUALS(count, 2);
+ }
+ TS_ASSERT_EQUALS(count, 0);
+
+ PS::StaticVector vec0(6, count);
+ TS_ASSERT_EQUALS(count, 6);
+
+ PS::StaticVector vec1(vec0);
+ TS_ASSERT_EQUALS(count, 12);
+
+ PS::StaticVector vec2(vec1);
+ TS_ASSERT_EQUALS(count, 18);
+ vec2.clear();
+
+ PS::StaticVector vec3(vec2);
+ TS_ASSERT_EQUALS(count, 12);
+ }
+
+ void test_assigne()
+ {
+ size_t count{0};
+
+ PS::StaticVector vec0(3, count);
+ TS_ASSERT_EQUALS(count, 3);
+ PS::StaticVector vec1(vec0);
+ TS_ASSERT_EQUALS(count, 6);
+ vec0 = vec1;
+ TS_ASSERT_EQUALS(count, 6);
+ vec0.emplace_back(count);
+ vec1 = vec0;
+ TS_ASSERT_EQUALS(vec0, vec1);
+ TS_ASSERT_EQUALS(count, 8);
+
+ vec1.pop_back();
+ vec1.pop_back();
+ vec0 = vec1;
+ TS_ASSERT_EQUALS(count, 4);
+ }
+
+ void test_exception()
+ {
+ TS_ASSERT_THROWS((PS::StaticVector(4)), PS::CapacityExceededException&);
+ PS::StaticVector vec0(3);
+ TS_ASSERT_THROWS(vec0.emplace_back(), PS::CapacityExceededException&);
+
+ PS::StaticVector vec1;
+ TS_ASSERT_THROWS(vec1.at(0), std::out_of_range&);
+ }
+
+ void test_ordering()
+ {
+ PS::StaticVector vec(36);
+ std::iota(vec.begin(), vec.end(), 0);
+ TS_ASSERT_EQUALS(vec[2], 2);
+ TS_ASSERT_EQUALS(vec[24], 24);
+
+ std::rotate(vec.begin(), vec.begin() + 12, vec.end());
+ TS_ASSERT_EQUALS(vec.front(), 12);
+ TS_ASSERT_EQUALS(vec[23], 35);
+ TS_ASSERT_EQUALS(vec[24], 0);
+
+ const auto pred
+ {
+ [](const int elem)
+ {
+ return elem < 10;
+ }
+ };
+
+ std::partition(vec.begin(), vec.end(), pred);
+ TS_ASSERT_LESS_THAN(vec[2], vec[10]);
+ TS_ASSERT_LESS_THAN(vec[5], vec[20]);
+ TS_ASSERT_EQUALS(std::partition_point(vec.begin(), vec.end(), pred), vec.begin() + 10);
+
+ std::sort(vec.begin(), vec.end());
+ TS_ASSERT(std::is_sorted(vec.begin(), vec.end()));
+ }
+
+ void test_compare()
+ {
+ TS_ASSERT((PS::StaticVector{0, 1, 2, 3} == PS::StaticVector{0, 1, 2, 3}));
+ TS_ASSERT((PS::StaticVector{0, 1, 2, 3} == PS::StaticVector{0, 1, 2, 3}));
+ TS_ASSERT((PS::StaticVector{0, 1, 2, 3} != PS::StaticVector{0, 1, 2, 4}));
+ TS_ASSERT((PS::StaticVector{0, 1, 2, 3} != PS::StaticVector{0, 1, 2, 4}));
+ TS_ASSERT((PS::StaticVector{0, 1, 2, 3} != PS::StaticVector{0, 1, 2}));
+ TS_ASSERT((PS::StaticVector{0, 1, 2, 3} != PS::StaticVector{0}));
+ TS_ASSERT((PS::StaticVector{0, 1, 2, 3} != PS::StaticVector{3, 2, 1, 0}));
+ }
+
+ // Types
+ static_assert(std::is_same_v>().begin()), int*>);
+ static_assert(std::is_same_v>().begin()),
+ const int*>);
+ static_assert(std::is_same_v>().end()), int*>);
+ static_assert(std::is_same_v>().end()),
+ const int*>);
+ static_assert(std::is_same_v>().data()), int*>);
+ static_assert(std::is_same_v>().data()),
+ const int*>);
+ static_assert(std::is_same_v>().front()), int&>);
+ static_assert(std::is_same_v>().front()),
+ const int&>);
+
+ // Size-types
+ static_assert(std::is_same_v::size_type, uint_fast8_t>);
+ static_assert(std::numeric_limits::size_type>::max() > 255);
+ static_assert(std::numeric_limits::difference_type>::min() < -128);
+
+ static_assert(std::is_same_v::size_type, uint_fast8_t>);
+ static_assert(std::is_same_v::difference_type, int_fast16_t>);
+};
Property changes on: ps/trunk/source/ps/containers/tests/test_StaticVector.h
___________________________________________________________________
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property