diff options
| author | Felix Morgner <felix.morgner@ost.ch> | 2026-10-05 16:43:41 +0200 |
|---|---|---|
| committer | Felix Morgner <felix.morgner@ost.ch> | 2026-10-05 16:43:41 +0200 |
| commit | 91190d585d9e385b3ccce29b47d038d750a1c52c (patch) | |
| tree | 4d22ce8830056d44fb98b361a1f67bf757264a1c | |
| parent | 8bec65ba723c9c628d934ec02021d5ce09c01105 (diff) | |
| parent | 6c864832f111c085d28cd30ae96039670ef44c59 (diff) | |
| download | kernel-develop.tar.xz kernel-develop.zip | |
kstd: implement fixed-size ring_buffer
This patchset introduces a (non-standard) container to the kernel standard
library. The new container, `kstd::ring_buffer<T, N>`, is a fixed-size ring
buffer, with an LRU overwrite policy. This means, that the size of the buffer
is defined at compile-time. When a buffer is full, pushing further elements
into it will replace existing ones in a Least Recently Used manner.
The first target application of this new container is an extension to the
existing logging system, providing a kernel log buffer.
See merge request teachos/kernel!62
| -rw-r--r-- | .gitlab-ci.yml | 91 | ||||
| -rw-r--r-- | libs/kstd/kstd/bits/basic_storage.hpp | 119 | ||||
| -rw-r--r-- | libs/kstd/kstd/bits/construction_guard.hpp | 46 | ||||
| -rw-r--r-- | libs/kstd/kstd/ring_buffer.hpp | 971 | ||||
| -rw-r--r-- | libs/kstd/kstd/ring_buffer.tests.cpp | 2883 | ||||
| -rw-r--r-- | libs/kstd/kstd/test_support/test_types.hpp | 243 |
6 files changed, 4298 insertions, 55 deletions
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index ca18bd90..9d38f6ee 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -1,20 +1,51 @@ -build:bht: - stage: build +bht: + stage: test image: registry.gitlab.ost.ch:45023/teachos/devcontainers/bht.ci:latest script: - cmake --preset $PRESET - cmake --build --preset $PRESET-$TYPE --target all all_verify_interface_header_sets --parallel $(nproc) 2>&1 | tee build_output.txt - set -o pipefail - python3 scripts/ci/parse_clang_tidy.py build_output.txt > code-quality-$PRESET-$TYPE.json + - ctest --preset $PRESET-$TYPE --parallel --output-on-failure + - lcov --quiet --config-file .lcovrc --capture --directory $(pwd) --output-file coverage.info + - lcov --quiet --config-file .lcovrc --list coverage.info + - genhtml --quiet --config-file .lcovrc --prefix $(pwd) --output-directory coverage coverage.info + - gcovr --root . --cobertura-pretty --output coverage/cobertura-coverage.xml + after_script: + - echo "CoverageReport public URL - https://teachos.pages.ost.ch/-/kernel/-/jobs/$CI_JOB_ID/artifacts/coverage/index.html" + coverage: '/Total:\|\s*(\d+(?:\.\d+)?)\%/' artifacts: paths: - - build/$PRESET/ + - coverage/ reports: codequality: code-quality-$PRESET-$TYPE.json - expire_in: 15 min + coverage_report: + coverage_format: cobertura + path: coverage/cobertura-coverage.xml + junit: build/bht/**/bht_results/*.xml + expire_in: 24 hours parallel: matrix: - - PRESET: ["bht", "bht-stress"] + - PRESET: ["bht"] + TYPE: ["dbg", "rel"] + +bht-stress: + stage: test + image: registry.gitlab.ost.ch:45023/teachos/devcontainers/bht.ci:latest + script: + - cmake --preset $PRESET + - cmake --build --preset $PRESET-$TYPE --target all all_verify_interface_header_sets --parallel $(nproc) 2>&1 | tee build_output.txt + - set -o pipefail + - python3 scripts/ci/parse_clang_tidy.py build_output.txt > code-quality-$PRESET-$TYPE.json + - TSAN_OPTIONS=halt_on_error=1 ctest --preset $PRESET-$TYPE --parallel --output-on-failure + artifacts: + reports: + codequality: code-quality-$PRESET-$TYPE.json + junit: build/bht-stress/**/bht_results/*.xml + expire_in: 24 hours + parallel: + matrix: + - PRESET: ["bht-stress"] TYPE: ["dbg", "rel"] build:bootable: @@ -40,56 +71,6 @@ build:bootable: - PLATFORM: ["x86_64"] TYPE: ["dbg", "rel"] -test:bht: - stage: test - image: registry.gitlab.ost.ch:45023/teachos/devcontainers/bht.ci:latest - script: - - ctest --preset bht-$TYPE --parallel --output-on-failure - - lcov --quiet --config-file .lcovrc --capture --directory $(pwd) --output-file coverage.info - - lcov --quiet --config-file .lcovrc --list coverage.info - - genhtml --quiet --config-file .lcovrc --prefix $(pwd) --output-directory coverage coverage.info - - gcovr --root . --cobertura-pretty --output coverage/cobertura-coverage.xml - after_script: - - echo "CoverageReport public URL - https://teachos.pages.ost.ch/-/kernel/-/jobs/$CI_JOB_ID/artifacts/coverage/index.html" - coverage: '/Total:\|\s*(\d+(?:\.\d+)?)\%/' - artifacts: - paths: - - coverage/ - expire_in: 24 hours - reports: - coverage_report: - coverage_format: cobertura - path: coverage/cobertura-coverage.xml - junit: build/bht/**/bht_results/*.xml - parallel: - matrix: - - TYPE: ["dbg", "rel"] - needs: - - job: build:bht - parallel: - matrix: - - PRESET: ["bht"] - TYPE: ["$[[ matrix.TYPE ]]"] - -test:bht-stress: - stage: test - image: registry.gitlab.ost.ch:45023/teachos/devcontainers/bht.ci:latest - script: - - TSAN_OPTIONS=halt_on_error=1 ctest --preset bht-stress-$TYPE --parallel --output-on-failure - artifacts: - expire_in: 24 hours - reports: - junit: build/bht-stress/**/bht_results/*.xml - parallel: - matrix: - - TYPE: ["dbg", "rel"] - needs: - - job: build:bht - parallel: - matrix: - - PRESET: ["bht-stress"] - TYPE: ["$[[ matrix.TYPE ]]"] - license_check: stage: .pre image: diff --git a/libs/kstd/kstd/bits/basic_storage.hpp b/libs/kstd/kstd/bits/basic_storage.hpp new file mode 100644 index 00000000..d3ffcae1 --- /dev/null +++ b/libs/kstd/kstd/bits/basic_storage.hpp @@ -0,0 +1,119 @@ +#ifndef KST_BITS_BASIC_STORAGE_HPP +#define KST_BITS_BASIC_STORAGE_HPP + +#include <array> +#include <cstddef> +#include <type_traits> + +namespace kstd::bits +{ + + //! A fixed-size storage buffer for elements of a given type. + template<typename ValueType, std::size_t Capacity> + struct alignas(ValueType) basic_storage + { + //! The type of the values contained in this storage object. + using value_type = ValueType; + //! The type used for sizes and indices in this storage object. + using size_type = std::size_t; + //! The type of a pointer to an element in this storage object. + using pointer = value_type *; + //! The type of a pointer to a const element in this storage object. + using const_pointer = value_type const *; + + //! @name Special Member Functions + //! @{ + + constexpr basic_storage() noexcept = default; + constexpr basic_storage(basic_storage const &) = delete; + constexpr basic_storage(basic_storage &&) = delete; + constexpr ~basic_storage() noexcept = default; + + constexpr auto operator=(basic_storage const &) -> basic_storage & = delete; + constexpr auto operator=(basic_storage &&) -> basic_storage & = delete; + + //! @} + + //! @name Modifiers + //! @{ + + //! Construct a new value, at the given index, in this storage object. + //! + //! @tparam ConstructorArguments The types of the arguments to forward to the constructor of the new value. + //! @param index The index at which to construct the new value. + //! @param constructor_arguments The arguments to forward to the constructor of the new value. + template<typename... ConstructorArguments> + requires(std::is_constructible_v<value_type, ConstructorArguments...>) + constexpr auto construct(size_type index, ConstructorArguments &&... constructor_arguments) noexcept( + std::is_nothrow_constructible_v<value_type, ConstructorArguments...>) -> void + { + std::construct_at(entry(index), std::forward<ConstructorArguments>(constructor_arguments)...); + } + + //! Destroy the value at the given index in this storage object. + //! + //! @param index The index of the value to destroy. + constexpr auto destroy(size_type index) noexcept -> void + { + std::destroy_at(entry(index)); + } + + //! @} + + //! @name Element Access + //! @{ + + //! Get a pointer to the value the given index in this storage object. + //! + //! @param index The index of the value to get. + //! @return A pointer to the value at the given index. + constexpr auto entry(size_type index) noexcept -> pointer + { + return &m_elements[index].value; + } + + //! Get a pointer to the value the given index in this storage object. + //! + //! @param index The index of the value to get. + //! @return A pointer to the value at the given index. + constexpr auto entry(size_type index) const noexcept -> const_pointer + { + return &m_elements[index].value; + } + + //! @} + + //! @name Capacity + //! @{ + + //! Get the maximum number of elements this storage object can hold. + //! + //! @return The maximum number of elements this storage object can hold. + [[nodiscard]] constexpr auto capacity() const noexcept -> size_type + { + return Capacity; + } + + //! @} + + private: + //! A wrapper for a value contained in this storage. + //! + //! This wrapper serves to ensure that the values in the storage of this storage object are not constructed or + //! destroyed when the storage object is constructed or destroyed. This is required in order to support the use of a + //! fixed sized storage buffer with non-trivial types. + union element + { + constexpr element() {} + constexpr ~element() {} + + value_type value; + }; + + //! The underlying storage buffer for the elements of this storage object. + std::array<element, Capacity> m_elements{}; + }; + +} // namespace kstd::bits + +#endif
\ No newline at end of file diff --git a/libs/kstd/kstd/bits/construction_guard.hpp b/libs/kstd/kstd/bits/construction_guard.hpp new file mode 100644 index 00000000..38e7bbb6 --- /dev/null +++ b/libs/kstd/kstd/bits/construction_guard.hpp @@ -0,0 +1,46 @@ +#ifndef KSTD_BITS_CONSTRUCTION_GUARD_HPP +#define KSTD_BITS_CONSTRUCTION_GUARD_HPP + +namespace kstd::bits +{ + + //! An RAII guard to ensure partially constructed container elements are properly cleaned up. + //! + //! @tparam Container The type of the container being guarded. + template<typename Container> + requires requires(Container * c) { c->clear(); } + struct construction_guard + { + //! Construct a new construction guard for the given container. + constexpr explicit construction_guard(Container * container) + : m_container{container} + {} + + constexpr construction_guard(construction_guard const &) = delete; + constexpr construction_guard(construction_guard &&) = delete; + + //! Destroy the construction guard, clearing the container if it is still engaged. + constexpr ~construction_guard() + { + if (m_container) + { + m_container->clear(); + } + } + + constexpr auto operator=(construction_guard const &) -> construction_guard & = delete; + constexpr auto operator=(construction_guard &&) -> construction_guard & = delete; + + //! Disarm the construction guard, preventing it from clearing the container. + constexpr auto disarm() noexcept -> void + { + m_container = nullptr; + } + + private: + Container * m_container; + }; + +} // namespace kstd::bits + +#endif
\ No newline at end of file diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp new file mode 100644 index 00000000..e9a733a3 --- /dev/null +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -0,0 +1,971 @@ +#ifndef KSTD_RING_BUFFER_HPP +#define KSTD_RING_BUFFER_HPP + +#include <kstd/bits/basic_storage.hpp> +#include <kstd/bits/concepts.hpp> +#include <kstd/bits/construction_guard.hpp> +#include <kstd/os/error.hpp> +#include <kstd/ranges.hpp> + +#include <algorithm> +#include <compare> +#include <concepts> +#include <cstddef> +#include <iterator> +#include <memory> +#include <ranges> +#include <type_traits> +#include <utility> + +namespace kstd +{ + + //! A fixed-size buffer that will overwrite elements in an LRU manner when full. + //! + //! @tparam ValueType The type of the values contained in this ring buffer. + //! @tparam Capacity The maximum number of elements this ring buffer can hold. + template<typename ValueType, std::size_t Capacity> + struct ring_buffer + { + template<bool Const> + struct ring_buffer_iterator; + + using value_type = ValueType; + using pointer = value_type *; + using const_pointer = value_type const *; + using reference = value_type &; + using const_reference = value_type const &; + using size_type = std::size_t; + using iterator = ring_buffer_iterator<false>; + using const_iterator = ring_buffer_iterator<true>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + + //! An iterator type for ring buffers. + //! + //! @tparam Const Whether this iterator is a const iterator. + template<bool Const> + struct ring_buffer_iterator + { + using iterator_category = std::random_access_iterator_tag; + using iterator_concept = std::random_access_iterator_tag; + using value_type = ring_buffer::value_type; + using difference_type = std::ptrdiff_t; + using pointer = std::conditional_t<Const, ring_buffer::const_pointer, ring_buffer::pointer>; + using reference = std::conditional_t<Const, ring_buffer::const_reference, ring_buffer::reference>; + + //! Create an empty iterator, pointing to nothing. + constexpr ring_buffer_iterator() = default; + + //! Create a new iterator by copying an existing one. + constexpr ring_buffer_iterator(ring_buffer_iterator const &) = default; + + //! Create a new const iterator from a non-const iterator. + //! + //! @note This constructor only participates in overload resolution if `Const` is `true`. + //! + //! @param it The non-const iterator to convert to a const iterator. + constexpr ring_buffer_iterator(ring_buffer_iterator<!Const> it) + requires Const + : m_buffer{it.m_buffer} + , m_index{it.m_index} + {} + + //! Lexicographically compare two iterators. + //! + //! @tparam OtherConst Whether the other iterator is a const iterator. + //! @param lhs The left-hand side iterator. + //! @param rhs The right-hand side iterator. + //! @return A `std::strong_ordering` indicating the relative order of the iterators. + template<bool OtherConst> + [[nodiscard]] constexpr auto friend operator<=>(ring_buffer_iterator const & lhs, + ring_buffer_iterator<OtherConst> const & rhs) noexcept + -> std::strong_ordering + { + return lhs.m_index <=> rhs.m_index; + } + + //! Check if two iterators are equal. + //! + //! @tparam OtherConst Whether the other iterator is a const iterator. + //! @param lhs The left-hand side iterator. + //! @param rhs The right-hand side iterator. + //! @return @p true iff. the iterators are equal, @p false otherwise. + template<bool OtherConst> + [[nodiscard]] constexpr auto friend operator==(ring_buffer_iterator const & lhs, + ring_buffer_iterator<OtherConst> const & rhs) noexcept -> bool + { + return lhs.m_buffer == rhs.m_buffer && lhs.m_index == rhs.m_index; + } + + //! Check if an iterator is equal to the end sentinel. + //! + //! @param lhs The iterator. + //! @param rhs The end sentinel. + //! @return @p true iff. the iterator is at the end, @p false otherwise. + [[nodiscard]] constexpr auto friend operator==(ring_buffer_iterator const & lhs, std::default_sentinel_t) noexcept + -> bool + { + return lhs.m_buffer == nullptr || lhs.m_index >= lhs.m_buffer->size(); + } + + //! Compute the distance between two iterators. + //! + //! @tparam OtherConst Whether the other iterator is a const iterator. + //! @param other The other iterator. + //! @return The number of elements between this iterator and the other iterator. + template<bool OtherConst> + [[nodiscard]] constexpr auto operator-(ring_buffer_iterator<OtherConst> const & other) const noexcept + -> difference_type + { + return static_cast<difference_type>(m_index) - static_cast<difference_type>(other.m_index); + } + + //! Advance the iterator by a given offset. + //! + //! @param offset The number of positions to advance the iterator. + //! @return A reference to the advanced iterator. + constexpr auto operator+=(difference_type offset) noexcept -> ring_buffer_iterator & + { + m_index += offset; + return *this; + } + + //! Create a new iterator by adding an offset to this iterator. + //! + //! @param it The iterator to advance. + //! @param offset The number of positions to advance the iterator. + //! @return A new iterator advanced by the given offset. + [[nodiscard]] constexpr auto friend operator+(ring_buffer_iterator it, difference_type offset) noexcept + -> ring_buffer_iterator + { + return it += offset; + } + + //! Create a new iterator by adding an offset to this iterator. + //! + //! @param offset The number of positions to advance the iterator. + //! @param it The iterator to advance. + //! @return A new iterator advanced by the given offset. + [[nodiscard]] constexpr auto friend operator+(difference_type offset, ring_buffer_iterator it) noexcept + -> ring_buffer_iterator + { + return it += offset; + } + + //! Move the iterator backward by a given offset. + //! + //! @param offset The number of positions to move the iterator backward. + //! @return A reference to the moved iterator. + constexpr auto operator-=(difference_type offset) noexcept -> ring_buffer_iterator & + { + m_index -= offset; + return *this; + } + + //! Create a new iterator by subtracting an offset from this iterator. + //! + //! @param it The iterator to move backward. + //! @param offset The number of positions to move the iterator backward. + //! @return A new iterator moved backward by the given offset. + [[nodiscard]] constexpr auto friend operator-(ring_buffer_iterator it, difference_type offset) noexcept + -> ring_buffer_iterator + { + return it -= offset; + } + + //! Move the iterator forward by one position. + //! + //! @return A reference to the advanced iterator. + constexpr auto operator++() noexcept -> ring_buffer_iterator & + { + ++m_index; + return *this; + } + + //! Move the iterator forward by one position. + //! + //! @return A copy of the iterator before it was advanced. + constexpr auto operator++(int) noexcept -> ring_buffer_iterator + { + auto copy = *this; + ++(*this); + return copy; + } + + //! Move the iterator backward by one position. + //! + //! @return A reference to the moved iterator. + constexpr auto operator--() noexcept -> ring_buffer_iterator & + { + --m_index; + return *this; + } + + //! Move the iterator backward by one position. + //! + //! @return A copy of the iterator before it was moved. + constexpr auto operator--(int) noexcept -> ring_buffer_iterator + { + auto copy = *this; + --(*this); + return copy; + } + + //! Access an element at a given offset from the current iterator position. + //! + //! @param offset The offset from the current iterator position. + //! @return A reference to the element at the given offset. + [[nodiscard]] constexpr auto operator[](difference_type offset) const noexcept -> reference + { + return (*m_buffer)[m_index + static_cast<size_type>(offset)]; + } + + //! Access the element at the current iterator position. + //! + //! @return A reference to the element at the current iterator position. + [[nodiscard]] constexpr auto operator*() const noexcept -> reference + { + return *m_buffer->element_at(m_index); + } + + //! Access the pointer to the element at the current iterator position. + //! + //! @return A pointer to the element at the current iterator position. + [[nodiscard]] constexpr auto operator->() const noexcept -> pointer + { + return m_buffer->element_at(m_index); + } + + private: + friend struct ring_buffer; + friend struct ring_buffer_iterator<!Const>; + + //! The type of the referenced buffer. + using buffer_type = std::conditional_t<Const, ring_buffer const, ring_buffer>; + + //! Construct an iterator for the given buffer and index. + //! + //! @param buffer The buffer to reference. + //! @param index The index within the buffer. + constexpr ring_buffer_iterator(buffer_type * buffer, size_type index) + : m_buffer{buffer} + , m_index{index} + {} + + //! The buffer being referenced by this iterator. + buffer_type * m_buffer{}; + //! The current index within the referenced buffer. + size_type m_index{}; + }; + + //! @name Special Member Functions + //! @{ + + //! Construct an empty ring buffer. + constexpr ring_buffer() noexcept = default; + + //! Construct a ring buffer by copying from an existing one. + constexpr ring_buffer(ring_buffer const & other) noexcept(std::is_nothrow_copy_constructible_v<ValueType>) + { + auto guard = bits::construction_guard{this}; + std::ranges::for_each(std::views::iota(0uz, other.size()), [&](auto const i) { + m_storage.construct(i, other[i]); + ++m_size; + }); + guard.disarm(); + } + + //! Construct a ring buffer by moving from an existing one. + constexpr ring_buffer(ring_buffer && other) noexcept(std::is_nothrow_move_constructible_v<ValueType> && + std::is_nothrow_destructible_v<ValueType>) + { + auto guard = bits::construction_guard{this}; + std::ranges::for_each(std::views::iota(0uz, other.size()), [&](auto) { + m_storage.construct(m_size, std::move(other[0])); + ++m_size; + auto * to_destroy = other.element_at(0); + other.m_read_index = (other.m_read_index + 1) % other.capacity(); + --other.m_size; + std::destroy_at(to_destroy); + }); + guard.disarm(); + } + + //! Destroy this ring buffer. + constexpr ~ring_buffer() noexcept(std::is_nothrow_destructible_v<ValueType>) + { + clear(); + } + + //! Construct a ring buffer with a given number of value initialized elements. + //! + //! @param count The number of value initialized elements to construct. + constexpr ring_buffer(size_type count) + { + if (count > capacity()) + { + os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); + } + + auto guard = bits::construction_guard{this}; + std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { + m_storage.construct(i); + ++m_size; + }); + guard.disarm(); + } + + //! Construct a ring buffer with a given number of copies of a given value. + //! + //! @param count The number of copies to construct. + //! @param value The value to copy. + constexpr ring_buffer(size_type count, ValueType const & value) + { + if (count > capacity()) + { + os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); + } + + auto guard = bits::construction_guard{this}; + std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { + m_storage.construct(i, value); + ++m_size; + }); + guard.disarm(); + } + + //! Construct a ring buffer with the elements of an input range. + //! + //! @warning This function will panic if the input range contains more elements than the ring buffer can support. + //! + //! @tparam InputIterator The type of the source iterators. + //! @param first The beginning of the input range. + //! @param last The end of the input range. + template<std::input_iterator InputIterator> + constexpr ring_buffer(InputIterator first, InputIterator last) + { + auto guard = bits::construction_guard{this}; + if constexpr (Capacity > 0) + { + for (; first != last && m_size < capacity(); ++first) + { + push_back(std::ranges::iter_move(first)); + } + } + + if (first != last) + { + os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); + } + + guard.disarm(); + } + + //! Construct a ring buffer with the elements of a forward range. + //! + //! @warning This function will panic if the input range contains more elements than the ring buffer can support. + //! + //! @tparam ForwardIterator The type of the source iterators. + //! @param first The beginning of the input range. + //! @param last The end of the input range. + template<std::forward_iterator ForwardIterator> + constexpr ring_buffer(ForwardIterator first, ForwardIterator last) + { + auto const number_of_source_elements = static_cast<size_type>(std::ranges::distance(first, last)); + if (number_of_source_elements > capacity()) + { + os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); + } + + if constexpr (Capacity > 0) + { + auto guard = bits::construction_guard{this}; + std::ranges::for_each(first, last, [this](auto const & element) { this->push_back(element); }); + guard.disarm(); + } + } + + //! Construct a ring buffer from a range. + //! + //! @warning This function will panic if the input range contains more elements than the ring buffer can support. + //! + //! @tparam Range The type of the source range. + //! @param range The input range to construct the ring buffer from. + template<std::ranges::input_range Range> + requires((std::ranges::forward_range<Range> || std::ranges::sized_range<Range>) && + kstd::bits::container_compatible_range<Range, ValueType>) + constexpr ring_buffer(kstd::from_range_t, Range && range) + { + if (static_cast<size_type>(std::ranges::distance(range)) > capacity()) + { + os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); + } + + if constexpr (Capacity > 0) + { + auto guard = bits::construction_guard{this}; + std::ranges::for_each(std::forward<Range>(range), + [this](auto && element) { this->push_back(std::forward<decltype(element)>(element)); }); + guard.disarm(); + } + } + + //! Replace the content of this ring buffer with a copy of the content of another one. + //! + //! @param other The ring buffer to copy from. + constexpr auto operator=(ring_buffer const & other) noexcept(std::is_nothrow_copy_constructible_v<ValueType> && + std::is_nothrow_copy_assignable_v<ValueType> && + std::is_nothrow_destructible_v<ValueType>) + -> ring_buffer & + { + if (this == &other) + { + return *this; + } + + auto const to_copy_assign = std::min(m_size, other.m_size); + std::ranges::copy(std::views::take(other, to_copy_assign), std::ranges::begin(*this)); + + if (to_copy_assign < other.m_size) + { + std::ranges::for_each(std::views::iota(to_copy_assign, other.m_size), [&](auto const i) { + std::construct_at(element_at(i), other[i]); + ++m_size; + }); + } + else if (to_copy_assign < m_size) + { + std::ranges::for_each(std::views::iota(to_copy_assign, m_size) | std::views::reverse, [&](auto const i) { + auto * element = element_at(i); + --m_size; + std::destroy_at(element); + }); + } + + return *this; + } + + //! Replace the content of this ring buffer by moving from another one. + //! + //! @param other The ring buffer to move from. + constexpr auto operator=(ring_buffer && other) noexcept(std::is_nothrow_move_constructible_v<ValueType> && + std::is_nothrow_move_assignable_v<ValueType> && + std::is_nothrow_destructible_v<ValueType>) -> ring_buffer & + { + if (this == &other) + { + return *this; + } + + auto const to_move_assign = std::min(m_size, other.m_size); + std::ranges::for_each(std::views::iota(0uz, to_move_assign), [&](auto const i) { + (*this)[i] = std::move(other[0]); + auto * to_destroy = other.element_at(0); + other.m_read_index = (other.m_read_index + 1) % other.capacity(); + --other.m_size; + std::destroy_at(to_destroy); + }); + + if (other.m_size > 0) + { + std::ranges::for_each(std::views::iota(0uz, other.m_size), [&](auto) { + std::construct_at(element_at(m_size), std::move(other[0])); + ++m_size; + auto * to_destroy = other.element_at(0); + other.m_read_index = (other.m_read_index + 1) % other.capacity(); + --other.m_size; + std::destroy_at(to_destroy); + }); + } + else if (to_move_assign < m_size) + { + std::ranges::for_each(std::views::iota(to_move_assign, m_size) | std::views::reverse, [&](auto const i) { + auto * to_destroy = element_at(i); + --m_size; + std::destroy_at(to_destroy); + }); + } + + return *this; + } + + //! @} + + //! @name Comparison + //! @{ + + //! Lexicographically compare two ring buffers. + //! + //! @param lhs The left-hand side ring buffer to compare. + //! @param rhs The right-hand side ring buffer to compare. + //! @return A value indicating the lexicographical comparison result. + constexpr auto friend operator<=>(ring_buffer const & lhs, ring_buffer const & rhs) noexcept + { + auto const lhs_common = lhs | std::views::common; + auto const rhs_common = rhs | std::views::common; + return std::lexicographical_compare_three_way(std::ranges::begin(lhs_common), std::ranges::end(lhs_common), + std::ranges::begin(rhs_common), std::ranges::end(rhs_common)); + } + + //! Check if two ring buffers are equal. + //! + //! @param lhs The left-hand side ring buffer to compare. + //! @param rhs The right-hand side ring buffer to compare. + //! @return `true` if the ring buffers are equal, `false` otherwise. + constexpr auto friend operator==(ring_buffer const & lhs, ring_buffer const & rhs) noexcept -> bool + { + return std::ranges::equal(lhs, rhs); + } + + //! @} + + //! @name Element Access + //! @{ + + //! Get the element at the specified position. + //! + //! @warning This function will panic if the position is not valid for this ring buffer. + //! + //! @param position The zero-based index of the element to get. + //! @return A reference to the element at the given position. + [[nodiscard]] constexpr auto at(size_type position) -> reference + { + panic_on_invalid_index(position); + return *element_at(position); + } + + //! Get the element at the specified index. + //! + //! @warning This function will panic if the position is not valid for this ring buffer. + //! + //! @param position The zero-based index of the element to get. + //! @return A reference to the element at the given position. + [[nodiscard]] constexpr auto at(size_type position) const -> const_reference + { + panic_on_invalid_index(position); + return *element_at(position); + } + + //! Get the element at the specified position. + //! + //! @warning This function will invoke undefined behavior if the position is not valid for this ring buffer. + //! + //! @param position The zero-based index of the element to get. + //! @return A reference to the element at the given position. + [[nodiscard]] constexpr auto operator[](size_type position) noexcept -> reference + { + return *element_at(position); + } + + //! Get the element at the specified position. + //! + //! @warning This function will invoke undefined behavior if the position is not valid for this ring buffer. + //! + //! @param position The zero-based index of the element to get. + //! @return A reference to the element at the given position. + [[nodiscard]] constexpr auto operator[](size_type position) const noexcept -> const_reference + { + return *element_at(position); + } + + //! Get the first element in the buffer. + //! + //! @warning This function will panic if the buffer is empty. + //! + //! @return A reference to the first element in the buffer. + [[nodiscard]] constexpr auto front() -> reference + { + if (empty()) + { + os::panic("[KSTD] Tried to access an element from an empty ring_buffer!"); + } + + return *element_at(0); + } + + //! Get the first element in the buffer. + //! + //! @warning This function will panic if the buffer is empty. + //! + //! @return A reference to the first element in the buffer. + [[nodiscard]] constexpr auto front() const -> const_reference + { + if (empty()) + { + os::panic("[KSTD] Tried to access an element from an empty ring_buffer!"); + } + + return *element_at(0); + } + + //! Get the last element in the buffer. + //! + //! @warning This function will panic if the buffer is empty. + //! + //! @return A reference to the last element in the buffer. + [[nodiscard]] constexpr auto back() -> reference + { + if (empty()) + { + os::panic("[KSTD] Tried to access an element from an empty ring_buffer!"); + } + + return *element_at(m_size - 1); + } + + //! Get the last element in the buffer. + //! + //! @warning This function will panic if the buffer is empty. + //! + //! @return A reference to the last element in the buffer. + [[nodiscard]] constexpr auto back() const -> const_reference + { + if (empty()) + { + os::panic("[KSTD] Tried to access an element from an empty ring_buffer!"); + } + + return *element_at(m_size - 1); + } + + //! @} + + //! @name Iterators + //! @{ + + //! Get an iterator to the first element. + [[nodiscard]] constexpr auto begin() noexcept -> iterator + { + return iterator{this, 0}; + } + + //! Get an iterator to the first element. + [[nodiscard]] constexpr auto begin() const noexcept -> const_iterator + { + return const_iterator{this, 0}; + } + + //! Get an iterator to the first element. + [[nodiscard]] constexpr auto cbegin() const noexcept -> const_iterator + { + return const_iterator{this, 0}; + } + + //! Get an iterator to one past the last element. + [[nodiscard]] constexpr auto end() noexcept -> std::default_sentinel_t + { + return std::default_sentinel; + } + + //! Get an iterator to one past the last element. + [[nodiscard]] constexpr auto end() const noexcept -> std::default_sentinel_t + { + return std::default_sentinel; + } + + //! Get an iterator to one past the last element. + [[nodiscard]] constexpr auto cend() const noexcept -> std::default_sentinel_t + { + return std::default_sentinel; + } + + //! Get a reverse iterator to the first element. + [[nodiscard]] constexpr auto rbegin() noexcept -> reverse_iterator + { + return std::make_reverse_iterator(iterator{this, m_size}); + } + + //! Get a reverse iterator to the first element. + [[nodiscard]] constexpr auto rbegin() const noexcept -> const_reverse_iterator + { + return std::make_reverse_iterator(const_iterator{this, m_size}); + } + + //! Get a reverse iterator to the first element. + [[nodiscard]] constexpr auto crbegin() const noexcept -> const_reverse_iterator + { + return std::make_reverse_iterator(const_iterator{this, m_size}); + } + + //! Get a reverse iterator to the first element. + [[nodiscard]] constexpr auto rend() noexcept -> reverse_iterator + { + return std::make_reverse_iterator(iterator{this, 0}); + } + + //! Get a reverse iterator to the first element. + [[nodiscard]] constexpr auto rend() const noexcept -> const_reverse_iterator + { + return std::make_reverse_iterator(const_iterator{this, 0}); + } + + //! Get a reverse iterator to the first element. + [[nodiscard]] constexpr auto crend() const noexcept -> const_reverse_iterator + { + return std::make_reverse_iterator(const_iterator{this, 0}); + } + + //! @} + + //! @name Capacity + //! @{ + + //! Get the maximum number of elements this ring buffer can hold. + //! + //! @return The number of elements that can fit in this ring buffer. + [[nodiscard]] constexpr auto capacity() const noexcept -> size_type + { + return m_storage.capacity(); + } + + //! Check if this ring buffer is empty. + //! + //! @return @p true iff. this ring buffer is empty, @p false otherwise. + [[nodiscard]] constexpr auto empty() const noexcept -> bool + { + return m_size == 0; + } + + //! Get the size of this ring buffer. + //! + //! @return The number of elements currently stored in this ring buffer. + [[nodiscard]] constexpr auto size() const noexcept -> size_type + { + return m_size; + } + + //! Get the maximum number of elements this ring buffer can hold. + //! + //! Due to ring_buffer being a fixed-size container, this function will return the same value as capacity. This + //! function is provided for API compatibility with standard library functions. + //! + //! @return The theoretical maximum number of elements that can fit in this ring buffer. + [[nodiscard]] constexpr auto max_size() const noexcept -> size_type + { + return capacity(); + } + + //! @} + + //! @name Modifiers + //! @{ + + //! Clear all elements from this ring buffer. + constexpr auto clear() noexcept(std::is_nothrow_destructible_v<ValueType>) -> void + { + if constexpr (Capacity > 0) + { + while (!empty()) + { + pop_front(); + } + } + } + + //! Construct an element at the end of this ring buffer. + //! + //! @tparam Args The types of the arguments to forward to the constructor of the element. + //! @param args The arguments to forward to the constructor of the element. + template<typename... Args> + requires(Capacity > 0) + constexpr auto emplace_back(Args &&... args) noexcept(std::is_nothrow_constructible_v<ValueType, Args &&...>) + -> reference + { + if (m_size < capacity()) + { + auto constructed = std::construct_at(element_at(m_size), std::forward<Args>(args)...); + ++m_size; + return *constructed; + } + + (*this)[0] = value_type{std::forward<Args>(args)...}; + m_read_index = (m_read_index + 1) % capacity(); + return *element_at(m_size - 1); + } + + //! Add an element to the end of this ring buffer. + //! + //! If the buffer is full, the oldest element will be overwritten. + //! + //! @param value The value to add to the end of this ring buffer. + constexpr auto push_back(value_type const & value) noexcept(std::is_nothrow_copy_constructible_v<ValueType> && + std::is_nothrow_copy_assignable_v<ValueType>) -> void + requires(Capacity > 0) + { + if (m_size < capacity()) + { + std::construct_at(element_at(m_size), value); + ++m_size; + return; + } + + (*this)[0] = value; + m_read_index = (m_read_index + 1) % capacity(); + } + + //! Add an element to the end of this ring buffer. + //! + //! If the buffer is full, the oldest element will be overwritten. If the element would overwrite itself, no + //! assignment will be performed. + //! + //! @param value The value to add to the end of this ring buffer. + constexpr auto push_back(value_type && value) noexcept(std::is_nothrow_move_constructible_v<ValueType> && + std::is_nothrow_move_assignable_v<ValueType>) -> void + requires(Capacity > 0) + { + if (m_size < capacity()) + { + std::construct_at(element_at(m_size), std::move(value)); + ++m_size; + return; + } + + auto target = element_at(0); + if (std::addressof(value) != target) + { + *target = std::move(value); + } + m_read_index = (m_read_index + 1) % capacity(); + } + + //! Try to add an element to the end of this ring buffer. + //! + //! @param value The value to add to the end of this ring buffer. + //! @return @p true iff. the buffer had space for the value, @p false otherwise. + template<typename PushedType> + requires(std::same_as<ValueType, std::remove_cvref_t<PushedType>>) + [[nodiscard]] constexpr auto try_push_back(PushedType && value) -> bool + { + if constexpr (Capacity > 0) + { + if (m_size >= capacity()) + { + return false; + } + + push_back(std::forward<PushedType>(value)); + return true; + } + else + { + return false; + } + } + + //! Remove the first element in the buffer. + //! + //! @warning This function will panic if the buffer is empty. + constexpr auto pop_front() -> void + requires(Capacity > 0) + { + if (empty()) + { + os::panic("[KSTD] Tried to pop an element from an empty ring_buffer!"); + } + + auto to_destroy = element_at(0); + m_read_index = (m_read_index + 1) % capacity(); + --m_size; + std::destroy_at(to_destroy); + } + + //! Try to remove the first element in the buffer. + //! + //! @return @p true iff. an element was removed, @p false otherwise + [[nodiscard]] constexpr auto try_pop_front() noexcept(std::is_nothrow_destructible_v<value_type>) -> bool + { + if constexpr (Capacity > 0) + { + if (empty()) + { + return false; + } + + pop_front(); + return true; + } + else + { + return false; + } + } + + //! @} + + //! @name Swap + //! @{ + + //! Swap the contents of this ring buffer with another. + //! + //! @param other The other ring buffer to swap with. + constexpr auto friend swap(ring_buffer & lhs, + ring_buffer & rhs) noexcept(std::is_nothrow_swappable_v<value_type> && + std::is_nothrow_move_constructible_v<value_type>) -> void + requires(Capacity > 0) + { + auto const to_swap = std::min(lhs.m_size, rhs.m_size); + std::ranges::for_each(std::views::iota(0uz, to_swap), + [&](auto i) { std::ranges::swap(*lhs.element_at(i), *rhs.element_at(i)); }); + + if (rhs.m_size > lhs.m_size) + { + std::ranges::for_each(std::views::iota(to_swap, rhs.m_size), [&](auto i) { + std::construct_at(lhs.element_at(i), std::move(*rhs.element_at(i))); + std::destroy_at(rhs.element_at(i)); + }); + } + else if (lhs.m_size > to_swap) + { + std::ranges::for_each(std::views::iota(to_swap, lhs.m_size), [&](auto i) { + std::construct_at(rhs.element_at(i), std::move(*lhs.element_at(i))); + std::destroy_at(lhs.element_at(i)); + }); + } + + std::ranges::swap(lhs.m_size, rhs.m_size); + } + + //! @} + + private: + //! Get a pointer to the element at the given read-index relative position. + //! + //! @param position The logical (read-index relative) index of the element. + //! @return A pointer to the object at given position. + constexpr auto element_at(size_type position) noexcept -> pointer + { + auto const storage_index = (m_read_index + position) % capacity(); + return m_storage.entry(storage_index); + } + + //! Get a pointer to the element at the given read-index relative position. + //! + //! @param position The logical (read-index relative) index of the element. + //! @return A pointer to the object at given position. + constexpr auto element_at(size_type position) const noexcept -> const_pointer + { + auto const storage_index = (m_read_index + position) % capacity(); + return m_storage.entry(storage_index); + } + + //! Trigger a kernel panic if an attempt is made to use an invalid index. + constexpr auto panic_on_invalid_index(size_type index) const -> void + { + if (index >= size()) + { + os::panic("[KSTD] Index out-of-bounds in ring_buffer element access!"); + } + } + + //! The underlying storage for the elements of this ring buffer. + bits::basic_storage<value_type, Capacity> m_storage{}; + //! The current number of elements in the buffer. + size_type m_size{}; + //! The index of the first element to be read. + size_type m_read_index{}; + }; + +} // namespace kstd + +#endif
\ No newline at end of file diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp new file mode 100644 index 00000000..54120b99 --- /dev/null +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -0,0 +1,2883 @@ +#include <kstd/ring_buffer.hpp> + +#include <kstd/ranges.hpp> +#include <kstd/test_support/os_panic.hpp> +#include <kstd/test_support/test_types.hpp> + +#include <catch2/catch_test_macros.hpp> +#include <catch2/matchers/catch_matchers.hpp> +#include <catch2/matchers/catch_matchers_exception.hpp> +#include <catch2/matchers/catch_matchers_range_equals.hpp> + +#include <algorithm> +#include <array> +#include <cstddef> +#include <forward_list> +#include <functional> +#include <iterator> +#include <memory> +#include <string> +#include <type_traits> +#include <utility> +#include <vector> + +namespace +{ + template<typename BufferType> + concept has_push_back = requires(BufferType buffer) { buffer.push_back(typename BufferType::value_type{}); }; + + template<typename BufferType> + concept has_pop_front = requires(BufferType buffer) { buffer.pop_front(); }; + + template<typename BufferType> + concept has_emplace_back = requires(BufferType buffer) { buffer.emplace_back(typename BufferType::value_type{}); }; + + struct point + { + int x; + int y; + + constexpr point(int x_, int y_) + : x{x_} + , y{y_} + {} + + friend constexpr auto operator==(point const &, point const &) -> bool = default; + }; +} // namespace + +SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") +{ + GIVEN("A ring buffer of float") + { + using buffer = kstd::ring_buffer<float, 100>; + + THEN("value_type is 'float'") + { + STATIC_REQUIRE(std::is_same_v<float, buffer::value_type>); + } + + THEN("reference is 'float &'") + { + STATIC_REQUIRE(std::is_same_v<float &, buffer::reference>); + } + + THEN("const_reference is 'float const &'") + { + STATIC_REQUIRE(std::is_same_v<float const &, buffer::const_reference>); + } + + THEN("pointer is 'float *'") + { + STATIC_REQUIRE(std::is_same_v<float *, buffer::pointer>); + } + + THEN("size_type is 'std::size_t'") + { + STATIC_REQUIRE(std::is_same_v<std::size_t, buffer::size_type>); + } + + THEN("const_pointer is 'float const *'") + { + STATIC_REQUIRE(std::is_same_v<float const *, buffer::const_pointer>); + } + + THEN("iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator<buffer::iterator>); + } + + THEN("const_iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator<buffer::const_iterator>); + } + + THEN("reverse_iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator<buffer::reverse_iterator>); + } + + THEN("const_reverse_iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator<buffer::const_reverse_iterator>); + } + + THEN("the return type of at() is 'reference' on a non-const buffer") + { + STATIC_REQUIRE(std::is_same_v<buffer::reference, decltype(std::declval<buffer &>().at(0))>); + } + + THEN("the return type of at() is 'const_reference' on a non-const buffer") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_reference, decltype(std::declval<buffer const &>().at(0))>); + } + + THEN("the return type of operator[] is 'reference' on a non-const buffer") + { + STATIC_REQUIRE(std::is_same_v<buffer::reference, decltype(std::declval<buffer &>()[0])>); + } + + THEN("the return type of operator[] is 'const_reference' on a non-const buffer") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_reference, decltype(std::declval<buffer const &>()[0])>); + } + + THEN("the return type of capacity() is `size_type`") + { + STATIC_REQUIRE(std::is_same_v<buffer::size_type, decltype(std::declval<buffer &>().capacity())>); + } + + THEN("the return type of empty() is `bool`") + { + STATIC_REQUIRE(std::is_same_v<bool, decltype(std::declval<buffer &>().empty())>); + } + + THEN("the return type of size() is `size_type`") + { + STATIC_REQUIRE(std::is_same_v<buffer::size_type, decltype(std::declval<buffer &>().size())>); + } + + THEN("the return type of max_size() is `size_type`") + { + STATIC_REQUIRE(std::is_same_v<buffer::size_type, decltype(std::declval<buffer &>().max_size())>); + } + + THEN("the return type of begin() is `iterator`") + { + STATIC_REQUIRE(std::is_same_v<buffer::iterator, decltype(std::declval<buffer &>().begin())>); + } + + THEN("the return type of begin() is `const_iterator` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_iterator, decltype(std::declval<buffer const &>().begin())>); + } + + THEN("the return type of cbegin() is `const_iterator`") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_iterator, decltype(std::declval<buffer &>().cbegin())>); + } + + THEN("the return type of end() is `std::default_sentinel_t`") + { + STATIC_REQUIRE(std::is_same_v<std::default_sentinel_t, decltype(std::declval<buffer &>().end())>); + } + + THEN("the return type of end() is `std::default_sentinel_t` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v<std::default_sentinel_t, decltype(std::declval<buffer const &>().end())>); + } + + THEN("the return type of cend() is `std::default_sentinel_t`") + { + STATIC_REQUIRE(std::is_same_v<std::default_sentinel_t, decltype(std::declval<buffer &>().cend())>); + } + + THEN("the return type of rbegin() is `reverse_iterator`") + { + STATIC_REQUIRE(std::is_same_v<buffer::reverse_iterator, decltype(std::declval<buffer &>().rbegin())>); + } + + THEN("the return type of rbegin() is `const_reverse_iterator` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_reverse_iterator, decltype(std::declval<buffer const &>().rbegin())>); + } + + THEN("the return type of crbegin() is `const_reverse_iterator`") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_reverse_iterator, decltype(std::declval<buffer &>().crbegin())>); + } + + THEN("the return type of rend() is `reverse_iterator`") + { + STATIC_REQUIRE(std::is_same_v<buffer::reverse_iterator, decltype(std::declval<buffer &>().rend())>); + } + + THEN("the return type of rend() is `const_reverse_iterator` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_reverse_iterator, decltype(std::declval<buffer const &>().rend())>); + } + + THEN("the return type of crend() is `const_reverse_iterator`") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_reverse_iterator, decltype(std::declval<buffer &>().crend())>); + } + + THEN("the return type of push_back() is void") + { + STATIC_REQUIRE(std::is_same_v<void, decltype(std::declval<buffer &>().push_back(std::declval<int>()))>); + } + + THEN("the return type of try_push_back() is bool") + { + STATIC_REQUIRE(std::is_same_v<bool, decltype(std::declval<buffer &>().try_push_back(buffer::value_type{}))>); + } + + THEN("the return type of pop_front() is void") + { + STATIC_REQUIRE(std::is_same_v<void, decltype(std::declval<buffer &>().pop_front())>); + } + + THEN("the return type of try_pop_front() is bool") + { + STATIC_REQUIRE(std::is_same_v<bool, decltype(std::declval<buffer &>().try_pop_front())>); + } + + THEN("the return type of front() is `reference`") + { + STATIC_REQUIRE(std::is_same_v<buffer::reference, decltype(std::declval<buffer &>().front())>); + } + + THEN("the return type of front() is `const_reference` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_reference, decltype(std::declval<buffer const &>().front())>); + } + + THEN("the return type of back() is `reference`") + { + STATIC_REQUIRE(std::is_same_v<buffer::reference, decltype(std::declval<buffer &>().back())>); + } + + THEN("the return type of back() is `const_reference` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v<buffer::const_reference, decltype(std::declval<buffer const &>().back())>); + } + + THEN("the return type of operator== is `bool`") + { + STATIC_REQUIRE(std::is_same_v<bool, decltype(std::declval<buffer const &>() == std::declval<buffer const &>())>); + } + + THEN("the return type of operator<=> is the same as for the value_type") + { + STATIC_REQUIRE(std::is_same_v<decltype(std::declval<buffer::value_type>() <=> std::declval<buffer::value_type>()), + decltype(std::declval<buffer const &>() <=> std::declval<buffer const &>())>); + } + + THEN("the return type of emplace_back() is `reference`") + { + STATIC_REQUIRE(std::is_same_v<buffer::reference, decltype(std::declval<buffer &>().emplace_back(0.0f))>); + } + + THEN("the return type of swap() is void") + { + STATIC_REQUIRE(std::is_same_v<void, decltype(swap(std::declval<buffer &>(), std::declval<buffer &>()))>); + } + } +} + +SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") +{ + GIVEN("An empty context") + { + WHEN("constructing by default using a capacity of 5") + { + auto buffer = kstd::ring_buffer<int, 5>{}; + + THEN("the capacity is 5") + { + REQUIRE(buffer.capacity() == 5); + } + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + + THEN("the size is 0") + { + REQUIRE(buffer.size() == 0); + } + + THEN("the maximum size is equal to the capacity") + { + REQUIRE(buffer.max_size() == buffer.capacity()); + } + } + + WHEN("constructing by n-copies-of-value constructor using a capacity of 5") + { + auto buffer = kstd::ring_buffer<char, 5>{3, 'a'}; + + THEN("the capacity is 5") + { + REQUIRE(buffer.capacity() == 5); + } + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is equal to the number of copies") + { + REQUIRE(buffer.size() == 3); + } + + THEN("the maximum size is equal to the capacity") + { + REQUIRE(buffer.max_size() == buffer.capacity()); + } + } + + WHEN("constructing by n-copies-of-value constructor using a capacity of 5 and 6 copies") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<char, 5>{6, 'a'}), kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + + WHEN("constructing by n-value-initialized constructor using a capacity of 5") + { + auto buffer = kstd::ring_buffer<int, 5>{3}; + + THEN("the capacity is 5") + { + REQUIRE(buffer.capacity() == 5); + } + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is equal to the number of copies") + { + REQUIRE(buffer.size() == 3); + } + + THEN("the maximum size is equal to the capacity") + { + REQUIRE(buffer.max_size() == buffer.capacity()); + } + } + + WHEN("constructing by n-value-initialized constructor using a capacity of 5 and 6 copies") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<int, 5>{6}), kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + } + + GIVEN("A full buffer") + { + auto buffer = kstd::ring_buffer<int, 5>{5}; + + THEN("the capacity is 5") + { + REQUIRE(buffer.capacity() == 5); + } + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is equal to the capacity") + { + REQUIRE(buffer.size() == buffer.capacity()); + } + } + + GIVEN("A buffer with a capacity of 5 containing 3 elements") + { + auto buffer = kstd::ring_buffer<std::string, 5>{3, "test"}; + + WHEN("constructing a copy") + { + auto copy = buffer; + + THEN("the contents of both are identical") + { + REQUIRE(std::ranges::equal(buffer, copy)); + } + + THEN("their element addresses differ") + { + auto address_of = [](auto const & obj) { + return std::addressof(obj); + }; + + REQUIRE_FALSE(std::ranges::equal(buffer, copy, std::equal_to{}, address_of, address_of)); + } + } + + WHEN("moving from it") + { + auto copy = buffer; + auto moved = std::move(buffer); + + THEN("the new vector has size 3") + { + REQUIRE(moved.size() == 3); + } + + THEN("the new buffer contains the moved values") + { + REQUIRE(std::ranges::equal(moved, copy)); + } + + THEN("the moved-from buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + } + + GIVEN("A single-pass input range with fewer elements than the capacity") + { + std::array<int, 3> source{1, 2, 3}; + auto first = kstd::tests::test_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::test_input_iterator{}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 5>{first, last}; + + THEN("the buffer contains the elements of the range in order") + { + REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3})); + } + } + } + + GIVEN("A single-pass input range with exactly as many elements as the capacity") + { + std::array<int, 3> source{1, 2, 3}; + auto first = kstd::tests::test_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::test_input_iterator{}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 3>{first, last}; + + THEN("the buffer is full and contains the elements of the range in order") + { + REQUIRE(buffer.size() == buffer.capacity()); + REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3})); + } + } + } + + GIVEN("A single-pass input range with more elements than the capacity") + { + std::array<int, 5> source{1, 2, 3, 4, 5}; + auto first = kstd::tests::test_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::test_input_iterator{}; + + WHEN("constructing from the range") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<int, 3>{first, last}), kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + } + + GIVEN("An empty input range") + { + auto first = kstd::tests::test_input_iterator{}; + auto last = kstd::tests::test_input_iterator{}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 5>{first, last}; + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + } + + GIVEN("An input range of static operation trackers with more elements than the capacity") + { + std::array<kstd::tests::static_copy_move_tracker, 5> source{}; + auto first = + kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{source.data(), source.size()}; + auto last = kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{}; + + WHEN("constructing from the range") + { + THEN("the constructor panics without leaking the elements already moved into the buffer") + { + kstd::tests::static_copy_move_tracker::reset(); + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 3>{first, last}), + kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == + kstd::tests::static_copy_move_tracker::dtor_call_count); + } + } + } + + GIVEN("An input range with more elements than the capacity, where dereferences are counted") + { + std::array<int, 10> source{}; + std::size_t elements_touched = 0; + auto first = kstd::tests::counting_input_iterator{source.data(), source.size(), elements_touched}; + auto last = kstd::tests::counting_input_iterator{}; + + WHEN("constructing from the range") + { + THEN("the constructor panics without dereferencing more elements than needed to detect the overflow") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<int, 3>{first, last}), kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + REQUIRE(elements_touched == 3); + } + } + } + + GIVEN("An input range of static operation trackers accessed through non-const references") + { + std::array<kstd::tests::static_copy_move_tracker, 3> source{}; + auto first = + kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{source.data(), source.size()}; + auto last = kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{}; + + WHEN("constructing from the range") + { + kstd::tests::static_copy_move_tracker::reset(); + auto buffer = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{first, last}; + + THEN("each element is moved into the buffer, not copied") + { + REQUIRE(buffer.size() == 3); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 3); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + } + } + } + + GIVEN("An input range of static operation trackers accessed through const references") + { + std::array<kstd::tests::static_copy_move_tracker, 2> source{}; + auto first = kstd::tests::const_input_iterator<kstd::tests::static_copy_move_tracker>{source.data(), source.size()}; + auto last = kstd::tests::const_input_iterator<kstd::tests::static_copy_move_tracker>{}; + + WHEN("constructing from the range") + { + kstd::tests::static_copy_move_tracker::reset(); + auto buffer = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{first, last}; + + THEN("each element is copied into the buffer, since it cannot be moved from a const source") + { + REQUIRE(buffer.size() == 2); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 2); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + } + } + } + + GIVEN("An input range of a move-only value type") + { + std::array<kstd::tests::move_only_value, 2> source{kstd::tests::move_only_value{1}, + kstd::tests::move_only_value{2}}; + auto first = kstd::tests::mutable_input_iterator<kstd::tests::move_only_value>{source.data(), source.size()}; + auto last = kstd::tests::mutable_input_iterator<kstd::tests::move_only_value>{}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<kstd::tests::move_only_value, 5>{first, last}; + + THEN("the buffer contains the moved-from elements") + { + REQUIRE(buffer.size() == 2); + REQUIRE(buffer[0] == kstd::tests::move_only_value{1}); + REQUIRE(buffer[1] == kstd::tests::move_only_value{2}); + } + } + } + + GIVEN("A forward range with fewer elements than the capacity") + { + auto source = std::forward_list<int>{1, 2, 3}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 5>{source.begin(), source.end()}; + + THEN("the buffer contains the elements of the range in order") + { + REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3})); + } + } + } + + GIVEN("A forward range with exactly as many elements as the capacity") + { + auto source = std::forward_list<int>{1, 2, 3}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 3>{source.begin(), source.end()}; + + THEN("the buffer is full and contains the elements of the range in order") + { + REQUIRE(buffer.size() == buffer.capacity()); + REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3})); + } + } + } + + GIVEN("A forward range with more elements than the capacity") + { + auto source = std::forward_list<int>{1, 2, 3, 4, 5}; + + WHEN("constructing from the range") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<int, 3>{source.begin(), source.end()}), kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + } + + GIVEN("An empty forward range") + { + auto source = std::forward_list<int>{}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 5>{source.begin(), source.end()}; + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + } + + GIVEN("A forward range of static operation trackers with more elements than the capacity") + { + auto source = std::forward_list<kstd::tests::static_copy_move_tracker>{}; + source.emplace_front(); + source.emplace_front(); + source.emplace_front(); + source.emplace_front(); + source.emplace_front(); + + WHEN("constructing from the range") + { + THEN("the constructor panics without touching storage") + { + kstd::tests::static_copy_move_tracker::reset(); + REQUIRE_THROWS_MATCHES( + (kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 3>{source.begin(), source.end()}), + kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + } + } + } + + GIVEN("A forward range of static operation trackers that fits within the capacity") + { + auto source = std::forward_list<kstd::tests::static_copy_move_tracker>{}; + source.emplace_front(); + source.emplace_front(); + + WHEN("constructing from the range") + { + kstd::tests::static_copy_move_tracker::reset(); + auto buffer = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{source.begin(), source.end()}; + + THEN("each element is copied, not moved") + { + REQUIRE(buffer.size() == 2); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 2); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + } + } + } + + GIVEN("A forward range used to construct two ring buffers in succession") + { + auto source = std::forward_list<int>{7, 8, 10}; + + WHEN("constructing both buffers from the same range") + { + auto first_buffer = kstd::ring_buffer<int, 5>{source.begin(), source.end()}; + auto second_buffer = kstd::ring_buffer<int, 5>{source.begin(), source.end()}; + + THEN("both buffers contain the same elements and the source range is left untouched") + { + REQUIRE_THAT(first_buffer, Catch::Matchers::RangeEquals({7, 8, 10})); + REQUIRE_THAT(second_buffer, Catch::Matchers::RangeEquals({7, 8, 10})); + REQUIRE_THAT(source, Catch::Matchers::RangeEquals({7, 8, 10})); + } + } + } + + GIVEN("A forward range with fewer elements than the capacity, constructed via kstd::from_range") + { + auto source = std::forward_list<int>{1, 2, 3}; + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 5>{kstd::from_range, source}; + THEN("the buffer contains the elements of the range in order") + { + REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3})); + } + } + } + + GIVEN("A forward range with exactly as many elements as the capacity, constructed via kstd::from_range") + { + auto source = std::forward_list<int>{1, 2, 3}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 3>{kstd::from_range, source}; + + THEN("the buffer is full and contains the elements of the range in order") + { + REQUIRE(buffer.size() == buffer.capacity()); + REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3})); + } + } + } + + GIVEN("A forward range with more elements than the capacity, constructed via kstd::from_range") + { + auto source = std::forward_list<int>{1, 2, 3, 4, 5}; + + WHEN("constructing from the range") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<int, 3>{kstd::from_range, source}), kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + } + + GIVEN("An empty forward range, constructed via kstd::from_range") + { + auto source = std::forward_list<int>{}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 5>{kstd::from_range, source}; + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + } + + GIVEN("A forward range of static operation trackers with more elements than the capacity, constructed via " + "kstd::from_range") + { + auto source = std::forward_list<kstd::tests::static_copy_move_tracker>{}; + source.emplace_front(); + source.emplace_front(); + source.emplace_front(); + source.emplace_front(); + source.emplace_front(); + + WHEN("constructing from the range") + { + THEN("the constructor panics without touching storage") + { + kstd::tests::static_copy_move_tracker::reset(); + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 3>{kstd::from_range, source}), + kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + } + } + } + + GIVEN("A sized input range that is not a forward range, with fewer elements than the capacity") + { + std::array<int, 3> source{10, 20, 30}; + auto first = kstd::tests::test_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::test_input_iterator{}; + auto range = std::ranges::subrange<kstd::tests::test_input_iterator, kstd::tests::test_input_iterator, + std::ranges::subrange_kind::sized>{first, last, source.size()}; + + STATIC_REQUIRE(std::ranges::sized_range<decltype(range)>); + STATIC_REQUIRE_FALSE(std::ranges::forward_range<decltype(range)>); + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer<int, 5>{kstd::from_range, range}; + + THEN("the buffer contains the elements of the range in order") + { + REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({10, 20, 30})); + } + } + } + + GIVEN("A sized input range that is not a forward range, with more elements than the capacity") + { + std::array<int, 5> source{1, 2, 3, 4, 5}; + auto first = kstd::tests::test_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::test_input_iterator{}; + auto range = std::ranges::subrange<kstd::tests::test_input_iterator, kstd::tests::test_input_iterator, + std::ranges::subrange_kind::sized>{first, last, source.size()}; + + WHEN("constructing from the range") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<int, 3>{kstd::from_range, range}), kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + } + + GIVEN("A sized, non-forward input range of static operation trackers with more elements than the capacity") + { + std::array<kstd::tests::static_copy_move_tracker, 5> source{}; + auto first = + kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{source.data(), source.size()}; + auto last = kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{}; + auto range = std::ranges::subrange<kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>, + kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>, + std::ranges::subrange_kind::sized>{first, last, source.size()}; + + WHEN("constructing from the range") + { + THEN("the constructor panics without touching storage") + { + kstd::tests::static_copy_move_tracker::reset(); + REQUIRE_THROWS_MATCHES((kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 3>{kstd::from_range, range}), + kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + } + } + } + + GIVEN("A range of static operation trackers whose elements are accessed as rvalues") + { + auto source = std::vector<kstd::tests::static_copy_move_tracker>(3); + + WHEN("constructing from the range") + { + kstd::tests::static_copy_move_tracker::reset(); + auto buffer = + kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{kstd::from_range, std::views::as_rvalue(source)}; + + THEN("each element is moved into the buffer, not copied") + { + REQUIRE(buffer.size() == 3); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 3); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + } + } + } +} + +SCENARIO("Ring Buffer assignment", "[kstd][ring_buffer]") +{ + GIVEN("3 partially populated buffers") + { + auto small = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{2}; + auto same = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{2}; + auto large = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{3}; + + WHEN("copy assigning the small to the large one") + { + kstd::tests::static_copy_move_tracker::reset(); + large = small; + + THEN("2 copy assignments and 1 destruction occurs") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 2); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("copy assigning the large to the small one") + { + kstd::tests::static_copy_move_tracker::reset(); + small = large; + + THEN("2 copy assignments and 1 copy construction occurs") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 2); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("copy assigning the small to the same size one") + { + kstd::tests::static_copy_move_tracker::reset(); + same = small; + + THEN("2 copy assignments occur") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 2); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("copy assigning a buffer to itself") + { + kstd::tests::static_copy_move_tracker::reset(); + +#if defined(__clang__) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wself-assign-overloaded" +#endif + same = same; +#if defined(__clang__) +#pragma clang diagnostic pop +#endif + + THEN("no operations occur") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("move assigning the small to the large one") + { + kstd::tests::static_copy_move_tracker::reset(); + large = std::move(small); + + THEN("2 move assignments and 3 destructions occur") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 3); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 2); + } + + THEN("the moved-from buffer is empty") + { + REQUIRE(small.empty()); + } + } + + WHEN("move assigning the large to the small one") + { + kstd::tests::static_copy_move_tracker::reset(); + small = std::move(large); + + THEN("2 move assignments, 1 move construction, and 3 destructions occur") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 3); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 2); + } + + THEN("the moved-from buffer is empty") + { + REQUIRE(large.empty()); + } + } + + WHEN("move assigning the small to the same size one") + { + kstd::tests::static_copy_move_tracker::reset(); + same = std::move(small); + + THEN("2 move assignments and 2 destructions occur") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 2); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 2); + } + + THEN("the moved-from buffer is empty") + { + REQUIRE(small.empty()); + } + } + + WHEN("move assigning a buffer to itself") + { + kstd::tests::static_copy_move_tracker::reset(); +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wself-move" + same = std::move(same); +#pragma GCC diagnostic pop + + THEN("no operations occur") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + } +} + +SCENARIO("Ring Buffer destruction", "[kstd][ring_buffer]") +{ + GIVEN("An empty buffer") + { + kstd::tests::static_dtor_tracker::dtor_call_count = 0; + auto buffer = std::make_shared<kstd::ring_buffer<kstd::tests::static_dtor_tracker, 5>>(); + + WHEN("the buffer is destroyed") + { + buffer.reset(); + + THEN("no dtors are invoked") + { + REQUIRE(kstd::tests::static_dtor_tracker::dtor_call_count == 0); + } + } + } + + GIVEN("A buffer containing 3 elements") + { + kstd::tests::static_dtor_tracker::dtor_call_count = 0; + auto buffer = std::make_shared<kstd::ring_buffer<kstd::tests::static_dtor_tracker, 5>>(3); + + WHEN("the buffer is destroyed") + { + buffer.reset(); + + THEN("3 dtors are invoked") + { + REQUIRE(kstd::tests::static_dtor_tracker::dtor_call_count == 3); + } + } + } +} + +SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") +{ + GIVEN("An empty ring buffer") + { + auto buffer = kstd::ring_buffer<int, 5>{}; + + THEN("accessing element 0 panics") + { + REQUIRE_THROWS_MATCHES(buffer.at(0), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Index out-of-bounds in ring_buffer element access!")); + } + + WHEN("working through a const reference") + { + auto const & ref = buffer; + + THEN("accessing element 0 panics") + { + REQUIRE_THROWS_MATCHES(ref.at(0), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Index out-of-bounds in ring_buffer element access!")); + } + } + + THEN("calling front() panics") + { + REQUIRE_THROWS_MATCHES(buffer.front(), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to access an element from an empty ring_buffer!")); + } + + THEN("calling back() panics") + { + REQUIRE_THROWS_MATCHES(buffer.back(), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to access an element from an empty ring_buffer!")); + } + + WHEN("working through a const reference") + { + auto const & ref = buffer; + + THEN("calling front() panics") + { + REQUIRE_THROWS_MATCHES( + ref.front(), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to access an element from an empty ring_buffer!")); + } + + THEN("calling back() panics") + { + REQUIRE_THROWS_MATCHES( + ref.back(), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to access an element from an empty ring_buffer!")); + } + } + } + + GIVEN("A ring buffer with a capacity of 5 containing 3 copies of the letter 'a'") + { + auto buffer = kstd::ring_buffer<char, 5>{3, 'a'}; + + THEN("accessing the first 3 elements using at() returns 'a'") + { + REQUIRE(buffer.at(0) == 'a'); + REQUIRE(buffer.at(1) == 'a'); + REQUIRE(buffer.at(2) == 'a'); + } + + THEN("accessing the fourth element using at() panics") + { + REQUIRE_THROWS_MATCHES(buffer.at(3), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Index out-of-bounds in ring_buffer element access!")); + } + + WHEN("writing through the return value of at()") + { + buffer.at(1) = 'b'; + + THEN("the written element is changed") + { + REQUIRE(buffer.at(1) == 'b'); + } + + THEN("the other elements are unchanged") + { + REQUIRE(buffer.at(0) == 'a'); + REQUIRE(buffer.at(2) == 'a'); + } + } + + THEN("accessing the first 3 elements using operator[] returns 'a'") + { + REQUIRE(buffer[0] == 'a'); + REQUIRE(buffer[1] == 'a'); + REQUIRE(buffer[2] == 'a'); + } + + WHEN("writing through the return value of operator[]") + { + buffer[1] = 'b'; + + THEN("the written element is changed") + { + REQUIRE(buffer.at(1) == 'b'); + } + + THEN("the other elements are unchanged") + { + REQUIRE(buffer.at(0) == 'a'); + REQUIRE(buffer.at(2) == 'a'); + } + } + + THEN("calling front() returns the same object as at(0)") + { + REQUIRE(std::addressof(buffer.front()) == std::addressof(buffer.at(0))); + } + + THEN("calling back() returns the same object as at(size() - 1)") + { + REQUIRE(std::addressof(buffer.back()) == std::addressof(buffer.at(buffer.size() - 1))); + } + + WHEN("working through a const reference") + { + auto const & ref = buffer; + + THEN("accessing the first 3 elements using at() returns 'a'") + { + REQUIRE(ref.at(0) == 'a'); + REQUIRE(ref.at(1) == 'a'); + REQUIRE(ref.at(2) == 'a'); + } + + THEN("accessing the fourth element using at() panics") + { + REQUIRE_THROWS_MATCHES(ref.at(3), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Index out-of-bounds in ring_buffer element access!")); + } + + THEN("accessing the first 3 elements using operator[] returns 'a'") + { + REQUIRE(ref[0] == 'a'); + REQUIRE(ref[1] == 'a'); + REQUIRE(ref[2] == 'a'); + } + + THEN("calling front() returns the same object as at(0)") + { + REQUIRE(std::addressof(ref.front()) == std::addressof(ref.at(0))); + } + + THEN("calling back() returns the same object as at(size() - 1)") + { + REQUIRE(std::addressof(ref.back()) == std::addressof(ref.at(ref.size() - 1))); + } + } + } +} + +SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") +{ + GIVEN("An empty ring buffer") + { + auto buffer = kstd::ring_buffer<int, 5>{}; + + THEN("begin() returns an iterator equal to std::default_sentinel") + { + REQUIRE(buffer.begin() == std::default_sentinel); + } + + THEN("cbegin() returns an iterator equal to std::default_sentinel") + { + REQUIRE(buffer.cbegin() == std::default_sentinel); + } + + THEN("begin() returns an iterator equal to end()") + { + REQUIRE(buffer.begin() == buffer.end()); + } + + THEN("begin() returns an iterator equal to cend()") + { + REQUIRE(buffer.begin() == buffer.cend()); + } + + THEN("cbegin() returns an iterator equal to end()") + { + REQUIRE(buffer.cbegin() == buffer.end()); + } + + THEN("cbegin() returns an iterator equal to cend()") + { + REQUIRE(buffer.cbegin() == buffer.cend()); + } + + THEN("the distance between begin() and end() is 0") + { + REQUIRE(std::ranges::distance(buffer.begin(), buffer.end()) == 0); + } + + THEN("the distance between cbegin() and cend() is 0") + { + REQUIRE(std::ranges::distance(buffer.cbegin(), buffer.cend()) == 0); + } + + THEN("the distance on the entire buffer is 0") + { + REQUIRE(std::ranges::distance(buffer) == 0); + } + + THEN("rbegin() returns an iterator equal to rend()") + { + REQUIRE(buffer.rbegin() == buffer.rend()); + } + + THEN("rbegin() returns an iterator equal to crend()") + { + REQUIRE(buffer.rbegin() == buffer.crend()); + } + + THEN("crbegin() returns an iterator equal to rend()") + { + REQUIRE(buffer.crbegin() == buffer.rend()); + } + + THEN("crbegin() returns an iterator equal to crend()") + { + REQUIRE(buffer.crbegin() == buffer.crend()); + } + + THEN("the distance between rbegin() and rend() is 0") + { + REQUIRE(std::ranges::distance(buffer.rbegin(), buffer.rend()) == 0); + } + + THEN("the distance between crbegin() and crend() is 0") + { + REQUIRE(std::ranges::distance(buffer.crbegin(), buffer.crend()) == 0); + } + + WHEN("working through a const reference") + { + auto const & ref = buffer; + + THEN("begin() returns an iterator equal to std::default_sentinel") + { + REQUIRE(ref.begin() == std::default_sentinel); + } + + THEN("begin() returns an iterator equal to end()") + { + REQUIRE(buffer.begin() == buffer.end()); + } + + THEN("the distance between begin() and end() is 0") + { + REQUIRE(std::ranges::distance(buffer.begin(), buffer.end()) == 0); + } + + THEN("the distance on the entire buffer is 0") + { + REQUIRE(std::ranges::distance(buffer) == 0); + } + + THEN("rbegin() returns an iterator equal to rend()") + { + REQUIRE(buffer.rbegin() == buffer.rend()); + } + + THEN("the distance between rbegin() and rend() is 0") + { + REQUIRE(std::ranges::distance(buffer.rbegin(), buffer.rend()) == 0); + } + } + } + + GIVEN("A ring buffer with a capacity of 5 containing 3 copies of the letter 'a'") + { + auto buffer = kstd::ring_buffer<char, 5>{3, 'a'}; + + THEN("begin() returns an iterator that does not equal std::default_sentinel") + { + REQUIRE(buffer.begin() != std::default_sentinel); + } + + THEN("begin() returns an iterator that does not equal end()") + { + REQUIRE(buffer.begin() != buffer.end()); + } + + THEN("begin() returns an iterator that does not equal cend()") + { + REQUIRE(buffer.begin() != buffer.cend()); + } + + THEN("the distance between begin() and end() is 3") + { + REQUIRE(std::ranges::distance(buffer.begin(), buffer.end()) == 3); + } + + THEN("the distance between cbegin() and cend() is 3") + { + REQUIRE(std::ranges::distance(buffer.cbegin(), buffer.cend()) == 3); + } + + THEN("the distance on the entire buffer is 3") + { + REQUIRE(std::ranges::distance(buffer) == 3); + } + + THEN("begin() returns an iterator to the first element") + { + REQUIRE(*buffer.begin() == 'a'); + } + + THEN("cbegin() return an iterator that does not equal std::default_sentinel") + { + REQUIRE(buffer.cbegin() != std::default_sentinel); + } + + THEN("cbegin() returns an iterator that does not equal end()") + { + REQUIRE(buffer.cbegin() != buffer.end()); + } + + THEN("cbegin() returns an iterator that does not equal cend()") + { + REQUIRE(buffer.cbegin() != buffer.cend()); + } + + THEN("cbegin() returns an iterator to the first element") + { + REQUIRE(*buffer.cbegin() == 'a'); + } + + THEN("rbegin() returns an iterator that does not equal rend()") + { + REQUIRE(buffer.rbegin() != buffer.rend()); + } + + THEN("rbegin() returns an iterator that does not equal crend()") + { + REQUIRE(buffer.rbegin() != buffer.crend()); + } + + THEN("the distance between rbegin() and rend() is 3") + { + REQUIRE(std::ranges::distance(buffer.rbegin(), buffer.rend()) == 3); + } + + THEN("the distance between crbegin() and crend() is 3") + { + REQUIRE(std::ranges::distance(buffer.crbegin(), buffer.crend()) == 3); + } + + THEN("rbegin() returns an iterator to the first element") + { + REQUIRE(*buffer.rbegin() == 'a'); + } + + THEN("crbegin() returns an iterator that does not equal rend()") + { + REQUIRE(buffer.crbegin() != buffer.rend()); + } + + THEN("crbegin() returns an iterator that does not equal crend()") + { + REQUIRE(buffer.crbegin() != buffer.crend()); + } + + THEN("crbegin() returns an iterator to the first element") + { + REQUIRE(*buffer.crbegin() == 'a'); + } + + THEN( + "incrementing the iterator returned by begin() past the end, yields an iterator equal to std::default_sentinel") + { + auto it = buffer.begin(); + ++it; + ++it; + ++it; + + REQUIRE(it == std::default_sentinel); + } + + THEN("incrementing the iterator returned by begin() past the end, yields an iterator equal to end()") + { + auto it = buffer.begin(); + ++it; + ++it; + ++it; + + REQUIRE(it == buffer.end()); + } + + THEN("incrementing the iterator returned by begin() past the end, yields an iterator equal to cend()") + { + auto it = buffer.begin(); + ++it; + ++it; + ++it; + + REQUIRE(it == buffer.cend()); + } + + THEN("incrementing the iterator returned by cbegin() past the end, yields an iterator equal to " + "std::default_sentinel") + { + auto it = buffer.cbegin(); + ++it; + ++it; + ++it; + + REQUIRE(it == std::default_sentinel); + } + + THEN("incrementing the iterator returned by cbegin() past the end, yields an iterator equal to end()") + { + auto it = buffer.cbegin(); + ++it; + ++it; + ++it; + + REQUIRE(it == buffer.end()); + } + + THEN("incrementing the iterator returned by cbegin() past the end, yields an iterator equal to cend()") + { + auto it = buffer.cbegin(); + ++it; + ++it; + ++it; + + REQUIRE(it == buffer.cend()); + } + + THEN("incrementing the iterator returned by rbegin() past the end, yields an iterator equal to rend()") + { + auto it = buffer.rbegin(); + ++it; + ++it; + ++it; + + REQUIRE(it == buffer.rend()); + } + + THEN("incrementing the iterator returned by rbegin() past the end, yields an iterator equal to crend()") + { + auto it = buffer.rbegin(); + ++it; + ++it; + ++it; + + REQUIRE(it == buffer.crend()); + } + + THEN("incrementing the iterator returned by crbegin() past the end, yields an iterator equal to rend()") + { + auto it = buffer.crbegin(); + ++it; + ++it; + ++it; + + REQUIRE(it == buffer.rend()); + } + + THEN("incrementing the iterator returned by crbegin() past the end, yields an iterator equal to crend()") + { + auto it = buffer.crbegin(); + ++it; + ++it; + ++it; + + REQUIRE(it == buffer.crend()); + } + + THEN("a const_iterator can be constructed from an iterator") + { + auto it = decltype(buffer)::const_iterator{buffer.begin()}; + + AND_THEN("the const_iterator points to the same element as the original iterator") + { + REQUIRE(*it == *buffer.begin()); + } + } + + THEN("two iterators constructed from begin() and cbegin() compare equal") + { + auto it = buffer.begin(); + auto cit = buffer.cbegin(); + + REQUIRE(it == cit); + } + + THEN("an iterator to the second element compares greater than begin()") + { + REQUIRE(++buffer.begin() > buffer.begin()); + } + + THEN("an iterator to the second element compares less than the iterator to the third element") + { + REQUIRE(++buffer.begin() < std::next(buffer.begin(), 2)); + } + + THEN("the adding 1 to the iterator returned by begin() yields an iterator to the second element") + { + REQUIRE((buffer.begin() + 1) == ++buffer.begin()); + REQUIRE((1 + buffer.begin()) == ++buffer.begin()); + } + + THEN("subtracting 1 from the iterator returned by the second element yields an iterator to the first element") + { + REQUIRE(((buffer.begin() + 1) - 1) == buffer.begin()); + } + + THEN("postfix incrementing the iterator returned by begin() yields an iterator to the first element") + { + REQUIRE(buffer.begin()++ == buffer.begin()); + } + + THEN("postfix decrementing the iterator one after begin() yields an iterator to the first element") + { + REQUIRE((buffer.begin() + 1)-- == (buffer.begin() + 1)); + } + + THEN("accessing an element by subscripting the iterator yields the correct element") + { + auto it = buffer.begin(); + REQUIRE(std::addressof(it[0]) == std::addressof(buffer.at(0))); + REQUIRE(std::addressof(it[1]) == std::addressof(buffer.at(1))); + REQUIRE(std::addressof(it[2]) == std::addressof(buffer.at(2))); + } + + THEN("access to an element via member-of-pointer yields the correct element") + { + auto it = buffer.begin(); + REQUIRE(it.operator->() == std::addressof(buffer.at(0))); + } + + WHEN("working through a const reference") + { + auto const & ref = buffer; + + THEN("begin() return an iterator that does not equal std::default_sentinel") + { + REQUIRE(ref.begin() != std::default_sentinel); + } + + THEN("begin() return an iterator that does not equal end()") + { + REQUIRE(ref.begin() != ref.end()); + } + + THEN("the distance between begin() and end() is 3") + { + REQUIRE(std::ranges::distance(buffer.begin(), buffer.end()) == 3); + } + + THEN("the distance on the entire buffer is 3") + { + REQUIRE(std::ranges::distance(buffer) == 3); + } + + THEN("begin() returns an iterator to the first element") + { + REQUIRE(*ref.begin() == 'a'); + } + + THEN("incrementing the iterator returned by begin() past the end, yields an iterator equal to " + "std::default_sentinel") + { + auto it = ref.begin(); + ++it; + ++it; + ++it; + + REQUIRE(it == std::default_sentinel); + } + + THEN("incrementing the iterator returned by begin() past the end, yields an iterator equal to end()") + { + auto it = ref.begin(); + ++it; + ++it; + ++it; + + REQUIRE(it == ref.end()); + } + + THEN("incrementing the iterator returned by rbegin() past the end, yields an iterator equal to rend()") + { + auto it = ref.rbegin(); + ++it; + ++it; + ++it; + + REQUIRE(it == ref.rend()); + } + } + } +} + +SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") +{ + GIVEN("An empty ring buffer with capcity 5") + { + auto buffer = kstd::ring_buffer<int, 5>{}; + + WHEN("clearing the buffer") + { + buffer.clear(); + + THEN("the buffer is still empty") + { + REQUIRE(buffer.empty()); + } + + THEN("the size is still 0") + { + REQUIRE(buffer.size() == 0); + } + } + + WHEN("pushing an element into the buffer") + { + buffer.push_back(10); + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is 1") + { + REQUIRE(buffer.size() == 1); + } + + THEN("the first element is equal to the pushed value") + { + REQUIRE(buffer.at(0) == 10); + } + } + + WHEN("pushing six elements into the buffer copy") + { + for (int i = 0; i < 6; ++i) + { + buffer.push_back(i); + } + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is equal to the capacity") + { + REQUIRE(buffer.size() == buffer.capacity()); + } + + THEN("the first element is equal to the second pushed value") + { + REQUIRE(buffer.at(0) == 1); + } + + THEN("the last element is equal to the last pushed value") + { + REQUIRE(buffer.at(4) == 5); + } + } + + WHEN("pushing ten element into the buffer by copy") + { + for (int i = 0; i < 10; ++i) + { + buffer.push_back(i); + } + + THEN("the content is equal to the last 5 pushed values") + { + REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({5, 6, 7, 8, 9})); + } + } + + THEN("trying to push an element is successful") + { + REQUIRE(buffer.try_push_back(1)); + } + + THEN("popping an element panics") + { + REQUIRE_THROWS_MATCHES(buffer.pop_front(), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to pop an element from an empty ring_buffer!")); + } + + THEN("trying to pop an element fails") + { + REQUIRE_FALSE(buffer.try_pop_front()); + } + } + + GIVEN("A ring buffer with a capacity of 5 containing 3 elements") + { + auto buffer = kstd::ring_buffer<int, 5>{3}; + + WHEN("pushing a single element into the buffer") + { + buffer.push_back(10); + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is 4") + { + REQUIRE(buffer.size() == 4); + } + + THEN("the last element is equal to the pushed value") + { + REQUIRE(buffer.at(3) == 10); + } + } + } + + GIVEN("A partially filled ring buffer of static operation trackers") + { + auto buffer = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{3}; + + WHEN("clearing the buffer") + { + kstd::tests::static_copy_move_tracker::reset(); + buffer.clear(); + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + + THEN("the size is 0") + { + REQUIRE(buffer.size() == 0); + } + + THEN("3 dtors are invoked") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 3); + } + } + + WHEN("pushing an element from the buffer into the buffer") + { + kstd::tests::static_copy_move_tracker::reset(); + buffer.push_back(buffer.at(0)); + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is 4") + { + REQUIRE(buffer.size() == 4); + } + + THEN("1 copy construction occurs") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("pushing an element from the buffer into the buffer using move semantics") + { + kstd::tests::static_copy_move_tracker::reset(); + buffer.push_back(std::move(buffer.at(0))); + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is 4") + { + REQUIRE(buffer.size() == 4); + } + + THEN("1 move construction occurs") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("the buffer is full") + { + buffer.push_back({}); + buffer.push_back({}); + + AND_WHEN("the first element is pushed into the buffer by copy") + { + kstd::tests::static_copy_move_tracker::reset(); + buffer.push_back(buffer.at(0)); + + THEN("1 copy assignment occurs") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + AND_WHEN("the first element is pushed into the buffer by move") + { + kstd::tests::static_copy_move_tracker::reset(); + buffer.push_back(std::move(buffer.at(0))); + + THEN("no special operation occurs") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + } + + WHEN("popping an element") + { + kstd::tests::static_copy_move_tracker::reset(); + buffer.pop_front(); + + THEN("the size is 2") + { + REQUIRE(buffer.size() == 2); + } + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("there was one destructor call") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("popping 3 elements") + { + buffer.pop_front(); + buffer.pop_front(); + buffer.pop_front(); + + THEN("the size is 0") + { + REQUIRE(buffer.size() == 0); + } + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + + THEN("trying to pop an element succeeds") + { + REQUIRE(buffer.try_pop_front()); + } + + WHEN("popping an element using try_pop_front") + { + kstd::tests::static_copy_move_tracker::reset(); + REQUIRE(buffer.try_pop_front()); + + THEN("the size is 2") + { + REQUIRE(buffer.size() == 2); + } + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("there was one destructor call") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("popping 3 elements using try_pop_front") + { + CHECK(buffer.try_pop_front()); + CHECK(buffer.try_pop_front()); + CHECK(buffer.try_pop_front()); + + THEN("the size is 0") + { + REQUIRE(buffer.size() == 0); + } + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + + THEN("another attempt to pop an element fails") + { + REQUIRE_FALSE(buffer.try_pop_front()); + } + } + + WHEN("emplacing from an rvalue argument") + { + auto argument = kstd::tests::static_copy_move_tracker{}; + kstd::tests::static_copy_move_tracker::reset(); + buffer.emplace_back(std::move(argument)); + + THEN("exactly one move construction occurs, nothing else") + { + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + } + } + } + + GIVEN("A full ring buffer of static operation trackers") + { + auto buffer = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{5}; + + WHEN("pushing an element from the buffer into the buffer") + { + kstd::tests::static_copy_move_tracker::reset(); + buffer.push_back({buffer.at(0)}); + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is 5") + { + REQUIRE(buffer.size() == 5); + } + + THEN("1 copy assignment occurs") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("pushing an element into the buffer from a temporary") + { + kstd::tests::static_copy_move_tracker::reset(); + buffer.push_back({}); + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + + THEN("the size is 5") + { + REQUIRE(buffer.size() == 5); + } + + THEN("1 move assignment and 1 dtor call occurs") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 1); + } + } + + THEN("trying to push an element fails") + { + REQUIRE_FALSE(buffer.try_push_back(kstd::tests::static_copy_move_tracker{})); + } + + WHEN("emplacing from a const lvalue argument") + { + auto const argument = kstd::tests::static_copy_move_tracker{}; + kstd::tests::static_copy_move_tracker::reset(); + buffer.emplace_back(argument); + + THEN("a temporary is constructed and move-assigned into the overwritten slot") + { + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 1); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + } + } + + WHEN("emplacing an element that aliases an element already in the buffer") + { + buffer.emplace_back(std::move(buffer.at(0))); + + THEN("the content is correct despite the aliasing") + { + REQUIRE(buffer.size() == 5); + } + } + } + + GIVEN("A ring buffer with a capacity of 3 that has wrapped around") + { + auto buffer = kstd::ring_buffer<int, 3>{}; + buffer.push_back(1); + buffer.push_back(2); + buffer.push_back(3); + buffer.push_back(4); + + WHEN("popping an element") + { + buffer.pop_front(); + + THEN("the size is 2") + { + REQUIRE(buffer.size() == 2); + } + + THEN("the remaining elements are the two newest, in order") + { + REQUIRE(buffer.at(0) == 3); + REQUIRE(buffer.at(1) == 4); + } + } + + WHEN("popping an element and then pushing a new one") + { + buffer.pop_front(); + buffer.push_back(5); + + THEN("the size is back to 3") + { + REQUIRE(buffer.size() == 3); + } + + THEN("the content reflects the pop and the push") + { + REQUIRE(buffer.at(0) == 3); + REQUIRE(buffer.at(1) == 4); + REQUIRE(buffer.at(2) == 5); + } + } + } + + GIVEN("An empty ring buffer of points with a capacity of 3") + { + auto buffer = kstd::ring_buffer<point, 3>{}; + + WHEN("emplacing an element from multiple constructor arguments") + { + auto & result = buffer.emplace_back(3, 4); + + THEN("the size is 1") + { + REQUIRE(buffer.size() == 1); + } + + THEN("the element was constructed from the given arguments") + { + REQUIRE((buffer.at(0) == point{3, 4})); + } + + THEN("the returned reference refers to the newly constructed element") + { + REQUIRE(std::addressof(result) == std::addressof(buffer.at(0))); + } + } + } + + GIVEN("An empty ring buffer with a capacity of 3") + { + auto buffer = kstd::ring_buffer<int, 3>{}; + + WHEN("emplacing with no arguments") + { + auto & result = buffer.emplace_back(); + + THEN("the element is value-initialized") + { + REQUIRE(buffer.at(0) == 0); + } + + THEN("the returned reference refers to the newly constructed element") + { + REQUIRE(std::addressof(result) == std::addressof(buffer.at(0))); + } + } + } + + GIVEN("A full ring buffer of points with a capacity of 2") + { + auto buffer = kstd::ring_buffer<point, 2>{ + 2, point{0, 0} + }; + + WHEN("emplacing an element from multiple constructor arguments") + { + auto & result = buffer.emplace_back(7, 8); + + THEN("the size is still 2") + { + REQUIRE(buffer.size() == 2); + } + + THEN("the oldest element was replaced by the newly constructed one") + { + REQUIRE((buffer.at(1) == point{7, 8})); + } + + THEN("the returned reference refers to the newly constructed element, not the stale one") + { + REQUIRE(std::addressof(result) == std::addressof(buffer.at(1))); + } + } + } +} + +SCENARIO("Ring Buffer zero capacity", "[kstd][ring_buffer]") +{ + GIVEN("A ring buffer with a capacity of 0") + { + auto buffer = kstd::ring_buffer<int, 0>{}; + + THEN("the buffer is always empty") + { + REQUIRE(buffer.empty()); + } + + THEN("the capacity is 0") + { + REQUIRE(buffer.capacity() == 0); + } + + THEN("the maximum size is 0") + { + REQUIRE(buffer.max_size() == 0); + } + + THEN("trying to push an element fails") + { + REQUIRE_FALSE(buffer.try_push_back(1)); + } + + THEN("trying to pop an element fails") + { + REQUIRE_FALSE(buffer.try_pop_front()); + } + + THEN("push_back cannot be called") + { + STATIC_REQUIRE_FALSE(has_push_back<decltype(buffer)>); + } + + THEN("pop_front cannot be called") + { + STATIC_REQUIRE_FALSE(has_pop_front<decltype(buffer)>); + } + + THEN("accessing element 0 using at() panics") + { + REQUIRE_THROWS_MATCHES(buffer.at(0), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Index out-of-bounds in ring_buffer element access!")); + } + + THEN("calling front() panics") + { + REQUIRE_THROWS_MATCHES(buffer.front(), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to access an element from an empty ring_buffer!")); + } + + THEN("calling back() panics") + { + REQUIRE_THROWS_MATCHES(buffer.back(), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to access an element from an empty ring_buffer!")); + } + + THEN("begin() equals end()") + { + REQUIRE(buffer.begin() == buffer.end()); + } + + THEN("cbegin() equals cend()") + { + REQUIRE(buffer.cbegin() == buffer.cend()); + } + + THEN("rbegin() equals rend()") + { + REQUIRE(buffer.rbegin() == buffer.rend()); + } + + THEN("the distance between begin() and end() is 0") + { + REQUIRE(std::ranges::distance(buffer) == 0); + } + + WHEN("clearing the buffer") + { + buffer.clear(); + + THEN("the buffer is still empty") + { + REQUIRE(buffer.empty()); + } + } + + WHEN("constructing a copy") + { + auto copy = buffer; + + THEN("the copy is empty") + { + REQUIRE(copy.empty()); + } + } + + WHEN("moving from it") + { + auto moved = std::move(buffer); + + THEN("the new buffer is empty") + { + REQUIRE(moved.empty()); + } + } + + WHEN("copy assigning to another zero-capacity buffer") + { + auto other = kstd::ring_buffer<int, 0>{}; + other = buffer; + + THEN("the target is still empty") + { + REQUIRE(other.empty()); + } + } + + WHEN("move assigning to another zero-capacity buffer") + { + auto other = kstd::ring_buffer<int, 0>{}; + other = std::move(buffer); + + THEN("the target is still empty") + { + REQUIRE(other.empty()); + } + } + + THEN("emplace_back cannot be called") + { + STATIC_REQUIRE_FALSE(has_emplace_back<decltype(buffer)>); + } + } + + WHEN("constructing by n-value-initialized constructor with a count of 0") + { + auto buffer = kstd::ring_buffer<int, 0>{0}; + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + + WHEN("constructing by n-value-initialized constructor with a count of 1") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES( + (kstd::ring_buffer<int, 0>{1}), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + + WHEN("constructing by n-copies-of-value constructor with a count of 0") + { + auto buffer = kstd::ring_buffer<int, 0>{0, 10}; + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + + WHEN("constructing by n-copies-of-value constructor with a count of 1") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES( + (kstd::ring_buffer<int, 0>{1, 42}), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + + WHEN("constructing by from-range constructor with an empty range") + { + auto source = std::forward_list<int>{}; + auto buffer = kstd::ring_buffer<int, 0>{kstd::from_range, source}; + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + + WHEN("constructing by from-range constructor with a range containing 1 element") + { + THEN("the constructor panics") + { + auto source = std::forward_list<int>{1}; + REQUIRE_THROWS_MATCHES( + (kstd::ring_buffer<int, 0>{kstd::from_range, source}), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + + WHEN("constructing by input-iterator-pair constructor with an empty range") + { + auto first = kstd::tests::test_input_iterator{}; + auto last = kstd::tests::test_input_iterator{}; + auto buffer = kstd::ring_buffer<int, 0>{first, last}; + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + + WHEN("constructing by input-iterator-pair constructor with a range containing 1 element") + { + THEN("the constructor panics") + { + std::array<int, 1> source{1}; + auto first = kstd::tests::test_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::test_input_iterator{}; + REQUIRE_THROWS_MATCHES( + (kstd::ring_buffer<int, 0>{first, last}), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + + WHEN("constructing by forward-iterator-pair constructor with an empty range") + { + auto source = std::forward_list<int>{}; + auto buffer = kstd::ring_buffer<int, 0>{source.begin(), source.end()}; + + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + } + + WHEN("constructing by forward-iterator-pair constructor with a range containing 1 element") + { + THEN("the constructor panics") + { + auto source = std::forward_list<int>{1}; + REQUIRE_THROWS_MATCHES( + (kstd::ring_buffer<int, 0>{source.begin(), source.end()}), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } + + GIVEN("A zero-capacity buffer of static operation trackers") + { + auto buffer = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 0>{}; + + WHEN("trying to push an element from a temporary") + { + kstd::tests::static_copy_move_tracker::reset(); + auto const pushed = buffer.try_push_back(kstd::tests::static_copy_move_tracker{}); + + THEN("the push fails") + { + REQUIRE_FALSE(pushed); + } + + THEN("no special operation occurs other than the temporary's own destruction") + { + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 1); + } + } + + WHEN("trying to pop an element") + { + kstd::tests::static_copy_move_tracker::reset(); + auto const popped = buffer.try_pop_front(); + + THEN("the pop fails") + { + REQUIRE_FALSE(popped); + } + + THEN("no destructor is invoked") + { + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + } + } + } +} + +SCENARIO("Ring Buffer comparison", "[kstd][ring_buffer]") +{ + GIVEN("Two ring buffers with the same content, constructed the same way") + { + auto lhs = kstd::ring_buffer<int, 5>{3, 1}; + auto rhs = kstd::ring_buffer<int, 5>{3, 1}; + + THEN("they compare equal") + { + REQUIRE(lhs == rhs); + } + + THEN("neither is less than the other") + { + REQUIRE_FALSE(lhs < rhs); + REQUIRE_FALSE(rhs < lhs); + } + + THEN("they are equivalent under <=>") + { + REQUIRE((lhs <=> rhs) == 0); + } + } + + GIVEN("A ring buffer compares equal to itself") + { + auto buffer = kstd::ring_buffer<int, 5>{3, 1}; + + THEN("it compares equal to itself") + { + REQUIRE(buffer == buffer); + } + } + + GIVEN("Two empty ring buffers") + { + auto lhs = kstd::ring_buffer<int, 5>{}; + auto rhs = kstd::ring_buffer<int, 5>{}; + + THEN("they compare equal") + { + REQUIRE(lhs == rhs); + } + } + + GIVEN("Two ring buffers with different content") + { + auto smaller = kstd::ring_buffer<int, 5>{3, 1}; + auto larger = kstd::ring_buffer<int, 5>{3, 2}; + + THEN("they do not compare equal") + { + REQUIRE_FALSE(smaller == larger); + } + + THEN("the one with the smaller elements orders first") + { + REQUIRE(smaller < larger); + REQUIRE_FALSE(larger < smaller); + } + } + + GIVEN("Two ring buffers holding the same elements with different sizes") + { + auto shorter = kstd::ring_buffer<int, 5>{2, 1}; + auto longer = kstd::ring_buffer<int, 5>{3, 1}; + + THEN("they do not compare equal") + { + REQUIRE_FALSE(shorter == longer); + } + + THEN("the shorter buffer, being a prefix of the longer one, orders first") + { + REQUIRE(shorter < longer); + } + } + + GIVEN("Two ring buffers with the same logical content but different physical layouts") + { + auto wrapped = kstd::ring_buffer<int, 3>{}; + wrapped.push_back(1); + wrapped.push_back(2); + wrapped.push_back(3); + wrapped.push_back(4); + + auto fresh = kstd::ring_buffer<int, 3>{}; + fresh.push_back(2); + fresh.push_back(3); + fresh.push_back(4); + + THEN("they compare equal despite differing internal layouts") + { + REQUIRE(wrapped == fresh); + } + + THEN("they are equivalent under <=>") + { + REQUIRE((wrapped <=> fresh) == 0); + } + } + + GIVEN("Two zero-capacity ring buffers") + { + auto lhs = kstd::ring_buffer<int, 0>{}; + auto rhs = kstd::ring_buffer<int, 0>{}; + + THEN("they compare equal") + { + REQUIRE(lhs == rhs); + } + } +} + +SCENARIO("Ring Buffer swap", "[kstd][ring_buffer]") +{ + GIVEN("Two ring buffers of equal size, both freshly constructed") + { + auto a = kstd::ring_buffer<int, 5>{3, 1}; + auto b = kstd::ring_buffer<int, 5>{3, 2}; + + WHEN("swapping them") + { + swap(a, b); + + THEN("their sizes are unchanged") + { + REQUIRE(a.size() == 3); + REQUIRE(b.size() == 3); + } + + THEN("their contents are exchanged") + { + REQUIRE_THAT(a, Catch::Matchers::RangeEquals({2, 2, 2})); + REQUIRE_THAT(b, Catch::Matchers::RangeEquals({1, 1, 1})); + } + } + } + + GIVEN("Two ring buffers with the same logical content but different physical layouts") + { + auto fresh = kstd::ring_buffer<int, 5>{}; + fresh.push_back(10); + fresh.push_back(20); + fresh.push_back(30); + + auto wrapped = kstd::ring_buffer<int, 5>{}; + for (int v : {1, 2, 3, 4, 5}) + { + wrapped.push_back(v); + } + wrapped.pop_front(); + wrapped.pop_front(); + + WHEN("swapping them") + { + swap(fresh, wrapped); + + THEN("each buffer ends up holding the other's logical content") + { + REQUIRE_THAT(fresh, Catch::Matchers::RangeEquals({3, 4, 5})); + REQUIRE_THAT(wrapped, Catch::Matchers::RangeEquals({10, 20, 30})); + } + } + } + + GIVEN("A smaller and a larger ring buffer") + { + auto small = kstd::ring_buffer<int, 5>{2, 7}; + auto large = kstd::ring_buffer<int, 5>{5, 100}; + + WHEN("swapping with the smaller buffer passed first") + { + swap(small, large); + + THEN("the sizes are exchanged") + { + REQUIRE(small.size() == 5); + REQUIRE(large.size() == 2); + } + + THEN("the contents are exchanged") + { + REQUIRE_THAT(small, Catch::Matchers::RangeEquals({100, 100, 100, 100, 100})); + REQUIRE_THAT(large, Catch::Matchers::RangeEquals({7, 7})); + } + } + + WHEN("swapping with the larger buffer passed first") + { + swap(large, small); + + THEN("the sizes are exchanged") + { + REQUIRE(large.size() == 2); + REQUIRE(small.size() == 5); + } + + THEN("the contents are exchanged") + { + REQUIRE_THAT(large, Catch::Matchers::RangeEquals({7, 7})); + REQUIRE_THAT(small, Catch::Matchers::RangeEquals({100, 100, 100, 100, 100})); + } + } + } + + GIVEN("Two ring buffers that differ in both size and physical layout") + { + auto a = kstd::ring_buffer<int, 5>{}; + for (int v : {1, 2, 3, 4, 5, 6}) + { + a.push_back(v); + } + a.pop_front(); + + auto b = kstd::ring_buffer<int, 5>{}; + for (int v : {10, 20, 30, 40, 50}) + { + b.push_back(v); + } + b.pop_front(); + b.pop_front(); + b.pop_front(); + + WHEN("swapping them") + { + swap(a, b); + + THEN("the sizes are exchanged") + { + REQUIRE(a.size() == 2); + REQUIRE(b.size() == 4); + } + + THEN("the contents are exchanged") + { + REQUIRE_THAT(a, Catch::Matchers::RangeEquals({40, 50})); + REQUIRE_THAT(b, Catch::Matchers::RangeEquals({3, 4, 5, 6})); + } + } + } + + GIVEN("One empty and one non-empty ring buffer") + { + auto empty = kstd::ring_buffer<int, 5>{}; + auto full = kstd::ring_buffer<int, 5>{3, 10}; + + WHEN("swapping them") + { + swap(empty, full); + + THEN("the previously empty buffer now holds the content") + { + REQUIRE_THAT(empty, Catch::Matchers::RangeEquals({10, 10, 10})); + } + + THEN("the previously full buffer is now empty") + { + REQUIRE(full.empty()); + } + } + } + + GIVEN("Two empty ring buffers") + { + auto a = kstd::ring_buffer<int, 5>{}; + auto b = kstd::ring_buffer<int, 5>{}; + + WHEN("swapping them") + { + swap(a, b); + + THEN("both remain empty") + { + REQUIRE(a.empty()); + REQUIRE(b.empty()); + } + } + } + + GIVEN("A ring buffer swapped with itself") + { + auto buffer = kstd::ring_buffer<int, 5>{3, 1}; + buffer.at(1) = 2; + buffer.at(2) = 3; + + WHEN("swapping it with itself") + { + swap(buffer, buffer); + + THEN("its content is unchanged") + { + REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3})); + } + } + } + + GIVEN("Two partially filled ring buffers of static operation trackers, equal size") + { + auto a = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{3}; + auto b = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{3}; + + WHEN("swapping them") + { + kstd::tests::static_copy_move_tracker::reset(); + swap(a, b); + + THEN("each element is exchanged via one move construction and two move assignments, nothing is leaked") + { + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 3); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 6); + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 3); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + } + } + } + + GIVEN("Two ring buffers of static operation trackers with different sizes") + { + auto large = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{5}; + auto small = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{2}; + + WHEN("swapping them") + { + kstd::tests::static_copy_move_tracker::reset(); + swap(large, small); + + THEN("the shared prefix is exchanged by swapping, the remainder by move-construction, nothing is leaked") + { + REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 5); + REQUIRE(kstd::tests::static_copy_move_tracker::move_assignment_call_count == 4); + REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 5); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(kstd::tests::static_copy_move_tracker::copy_assignment_call_count == 0); + } + } + } + + GIVEN("A value type whose move operations are noexcept") + { + THEN("swap() is noexcept") + { + STATIC_REQUIRE( + noexcept(swap(std::declval<kstd::ring_buffer<int, 5> &>(), std::declval<kstd::ring_buffer<int, 5> &>()))); + } + } + + GIVEN("A value type whose move operations are not noexcept") + { + THEN("swap() is not noexcept") + { + STATIC_REQUIRE_FALSE( + noexcept(swap(std::declval<kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5> &>(), + std::declval<kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5> &>()))); + } + } +}
\ No newline at end of file diff --git a/libs/kstd/kstd/test_support/test_types.hpp b/libs/kstd/kstd/test_support/test_types.hpp index baf5e853..ed3a8f7a 100644 --- a/libs/kstd/kstd/test_support/test_types.hpp +++ b/libs/kstd/kstd/test_support/test_types.hpp @@ -8,6 +8,57 @@ namespace kstd::tests { + struct static_dtor_tracker + { + auto static inline dtor_call_count = 0uz; + + ~static_dtor_tracker() + { + ++dtor_call_count; + } + }; + + struct static_copy_move_tracker : static_dtor_tracker + { + auto static inline copy_ctor_call_count = 0uz; + auto static inline copy_assignment_call_count = 0uz; + auto static inline move_ctor_call_count = 0uz; + auto static inline move_assignment_call_count = 0uz; + + auto static reset() -> void + { + dtor_call_count = 0; + copy_ctor_call_count = 0; + copy_assignment_call_count = 0; + move_ctor_call_count = 0; + move_assignment_call_count = 0; + } + + constexpr static_copy_move_tracker() = default; + + static_copy_move_tracker(static_copy_move_tracker const &) + { + ++copy_ctor_call_count; + } + + static_copy_move_tracker(static_copy_move_tracker &&) + { + ++move_ctor_call_count; + } + + auto operator=(static_copy_move_tracker const &) -> static_copy_move_tracker & + { + ++copy_assignment_call_count; + return *this; + } + + auto operator=(static_copy_move_tracker &&) -> static_copy_move_tracker & + { + ++move_assignment_call_count; + return *this; + } + }; + //! A type tracking copy and move operations //! //! This type is designed to test move and copy semantics of standard library containers implemented in kstd. @@ -183,6 +234,24 @@ namespace kstd::tests } }; + //! A type that can only be moved, not copied. + struct move_only_value + { + int value; + + explicit move_only_value(int v) + : value{v} + {} + + move_only_value(move_only_value const &) = delete; + move_only_value(move_only_value &&) = default; + + auto operator=(move_only_value const &) -> move_only_value & = delete; + auto operator=(move_only_value &&) -> move_only_value & = default; + + [[nodiscard]] friend auto operator==(move_only_value const &, move_only_value const &) -> bool = default; + }; + //! An allocator that tracks the number of allocations. //! //! This allocator is designed to test allocation semantics of standard library containers implemented in kstd. @@ -364,6 +433,180 @@ namespace kstd::tests } }; + //! A test input iterator that yields mutable references to its elements. + template<typename ValueType> + struct mutable_input_iterator + { + using iterator_concept = std::input_iterator_tag; + using iterator_category = std::input_iterator_tag; + using difference_type = std::ptrdiff_t; + using value_type = ValueType; + using reference = ValueType &; + using pointer = ValueType *; + + ValueType * current; + std::size_t count; + + explicit mutable_input_iterator() + : current{nullptr} + , count{0} + {} + + explicit mutable_input_iterator(ValueType * current, std::size_t count) + : current{current} + , count{count} + {} + + [[nodiscard]] auto operator*() const -> ValueType & + { + return *current; + } + + auto operator++() -> mutable_input_iterator & + { + ++current; + --count; + return *this; + } + + auto operator++(int) -> void + { + ++*this; + } + + [[nodiscard]] auto operator==(mutable_input_iterator const & other) const -> bool + { + if (current == nullptr && other.current == nullptr) + { + return true; + } + + if (current == nullptr || other.current == nullptr) + { + return count == other.count; + } + + return current == other.current && count == other.count; + } + }; + + //! A test input iterator that yields const references to its elements. + template<typename ValueType> + struct const_input_iterator + { + using iterator_concept = std::input_iterator_tag; + using iterator_category = std::input_iterator_tag; + using difference_type = std::ptrdiff_t; + using value_type = ValueType; + using reference = ValueType const &; + using pointer = ValueType const *; + + ValueType const * current; + std::size_t count; + + explicit const_input_iterator() + : current{nullptr} + , count{0} + {} + + explicit const_input_iterator(ValueType const * current, std::size_t count) + : current{current} + , count{count} + {} + + [[nodiscard]] auto operator*() const -> ValueType const & + { + return *current; + } + + auto operator++() -> const_input_iterator & + { + ++current; + --count; + return *this; + } + + auto operator++(int) -> void + { + ++*this; + } + + [[nodiscard]] auto operator==(const_input_iterator const & other) const -> bool + { + if (current == nullptr && other.current == nullptr) + { + return true; + } + + if (current == nullptr || other.current == nullptr) + { + return count == other.count; + } + + return current == other.current && count == other.count; + } + }; + + //! A single-pass input iterator that counts how many of its elements have actually been dereferenced. + struct counting_input_iterator + { + using iterator_concept = std::input_iterator_tag; + using iterator_category = std::input_iterator_tag; + using difference_type = std::ptrdiff_t; + using value_type = int; + using reference = int const &; + using pointer = int const *; + + int const * current; + std::size_t count; + std::size_t * elements_touched; + + explicit counting_input_iterator() + : current{nullptr} + , count{0} + , elements_touched{nullptr} + {} + + explicit counting_input_iterator(int const * current, std::size_t count, std::size_t & elements_touched) + : current{current} + , count{count} + , elements_touched{&elements_touched} + {} + + [[nodiscard]] auto operator*() const -> int + { + ++(*elements_touched); + return *current; + } + + auto operator++() -> counting_input_iterator & + { + ++current; + --count; + return *this; + } + + auto operator++(int) -> void + { + ++*this; + } + + [[nodiscard]] auto operator==(counting_input_iterator const & other) const -> bool + { + if (current == nullptr && other.current == nullptr) + { + return true; + } + + if (current == nullptr || other.current == nullptr) + { + return count == other.count; + } + + return current == other.current && count == other.count; + } + }; + } // namespace kstd::tests #endif |
