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