aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFelix Morgner <felix.morgner@ost.ch>2026-10-05 16:43:41 +0200
committerFelix Morgner <felix.morgner@ost.ch>2026-10-05 16:43:41 +0200
commit91190d585d9e385b3ccce29b47d038d750a1c52c (patch)
tree4d22ce8830056d44fb98b361a1f67bf757264a1c
parent8bec65ba723c9c628d934ec02021d5ce09c01105 (diff)
parent6c864832f111c085d28cd30ae96039670ef44c59 (diff)
downloadkernel-91190d585d9e385b3ccce29b47d038d750a1c52c.tar.xz
kernel-91190d585d9e385b3ccce29b47d038d750a1c52c.zip
Merge branch 'fmorgner/implement-kstd-ring-buffer' into 'develop'HEADdevelop
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.yml91
-rw-r--r--libs/kstd/kstd/bits/basic_storage.hpp119
-rw-r--r--libs/kstd/kstd/bits/construction_guard.hpp46
-rw-r--r--libs/kstd/kstd/ring_buffer.hpp971
-rw-r--r--libs/kstd/kstd/ring_buffer.tests.cpp2883
-rw-r--r--libs/kstd/kstd/test_support/test_types.hpp243
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