From 6959a83b7d7e6a272cfd626fa3799a875460f5ea Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 15:08:18 +0200 Subject: kstd: add ring_buffer include --- libs/kstd/kstd/ring_buffer.hpp | 20 ++++++++++++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 17 +++++++++++++++++ 2 files changed, 37 insertions(+) create mode 100644 libs/kstd/kstd/ring_buffer.hpp create mode 100644 libs/kstd/kstd/ring_buffer.tests.cpp diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp new file mode 100644 index 00000000..0ceb634d --- /dev/null +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -0,0 +1,20 @@ +#ifndef KSTD_RING_BUFFER_HPP +#define KSTD_RING_BUFFER_HPP + +#include + +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 + struct ring_buffer + { + }; + +} // 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..3608d5ce --- /dev/null +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -0,0 +1,17 @@ +#include + +#include + +#include + +SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") +{ + GIVEN("An empty context") + { + WHEN("constructing by default") + { + auto buffer = kstd::ring_buffer{}; + std::ignore = buffer; + } + } +} \ No newline at end of file -- cgit v1.2.3 From b2a39c22a86196128a8b67472b67b320c3e01c04 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 15:23:15 +0200 Subject: kstd: ring_buffer: implement capacity() --- libs/kstd/kstd/ring_buffer.hpp | 10 ++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 10 ++++++---- 2 files changed, 16 insertions(+), 4 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 0ceb634d..63ca94a1 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -13,6 +13,16 @@ namespace kstd template struct ring_buffer { + using size_type = std::size_t; + + //! 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 Capacity; + } + }; } // namespace kstd diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 3608d5ce..f661b50e 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -2,16 +2,18 @@ #include -#include - SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") { GIVEN("An empty context") { - WHEN("constructing by default") + WHEN("constructing by default using a capacity of 5") { auto buffer = kstd::ring_buffer{}; - std::ignore = buffer; + + THEN("the capacity is 5") + { + REQUIRE(buffer.capacity() == 5); + } } } } \ No newline at end of file -- cgit v1.2.3 From 712ac5310b6f3d064219bf4db2a4af3a98362c12 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 15:27:43 +0200 Subject: kstd: ring_buffer: implement max_size() --- libs/kstd/kstd/ring_buffer.hpp | 11 +++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 5 +++++ 2 files changed, 16 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 63ca94a1..427b31df 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -23,6 +23,17 @@ namespace kstd return Capacity; } + //! 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(); + } + }; } // namespace kstd diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index f661b50e..f693b0a8 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -14,6 +14,11 @@ SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") { REQUIRE(buffer.capacity() == 5); } + + THEN("the maximum size is equal to the capacity") + { + REQUIRE(buffer.max_size() == buffer.capacity()); + } } } } \ No newline at end of file -- cgit v1.2.3 From 1c9f678aa0496721317698c2c6aef559af0495c9 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 15:31:36 +0200 Subject: kstd: ring_buffer: add do sections --- libs/kstd/kstd/ring_buffer.hpp | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 427b31df..2949988e 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -15,6 +15,9 @@ namespace kstd { using size_type = std::size_t; + //! @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. @@ -34,6 +37,8 @@ namespace kstd return capacity(); } + //! @} + }; } // namespace kstd -- cgit v1.2.3 From d8b4ae2ddffa7ff9613d7a6416f3a405d81dad43 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 15:35:29 +0200 Subject: kstd: ring_buffer: implement empty() --- libs/kstd/kstd/ring_buffer.hpp | 13 +++++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 5 +++++ 2 files changed, 18 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 2949988e..a25e37b7 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -26,6 +26,14 @@ namespace kstd return 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_head == m_tail; + } + //! 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 @@ -39,6 +47,11 @@ namespace kstd //! @} + private: + //! The index of the element that was most recently added to this ring buffer. + size_type m_head{}; + //! The index of the element that was least recently added to this ring buffer. + size_type m_tail{}; }; } // namespace kstd diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index f693b0a8..37243014 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -15,6 +15,11 @@ SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") REQUIRE(buffer.capacity() == 5); } + THEN("the buffer is empty") + { + REQUIRE(buffer.empty()); + } + THEN("the maximum size is equal to the capacity") { REQUIRE(buffer.max_size() == buffer.capacity()); -- cgit v1.2.3 From 3d2b027d86ca65975c19a26968851dc50e142849 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 15:42:50 +0200 Subject: kstd: ring_buffer: implement size() --- libs/kstd/kstd/ring_buffer.hpp | 13 +++++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 5 +++++ 2 files changed, 18 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index a25e37b7..0e54c070 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -34,6 +34,19 @@ namespace kstd return m_head == m_tail; } + //! 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 + { + if (m_head >= m_tail) + { + return m_head - m_tail; + } + + return capacity() - m_tail + m_head; + } + //! 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 diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 37243014..6e936248 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -20,6 +20,11 @@ SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") 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()); -- cgit v1.2.3 From ad7a0764d381ad1a5272ad6a949f4929c85fb179 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 16:39:57 +0200 Subject: kstd: ring_buffer: implement at() --- libs/kstd/kstd/ring_buffer.hpp | 55 ++++++++++++++++++++++++++++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 29 +++++++++++++++++++ 2 files changed, 84 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 0e54c070..151ab994 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -1,6 +1,9 @@ #ifndef KSTD_RING_BUFFER_HPP #define KSTD_RING_BUFFER_HPP +#include + +#include #include namespace kstd @@ -13,8 +16,38 @@ namespace kstd template struct ring_buffer { + 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; + //! @name Element Access + //! @{ + + //! Get the element at the specified index. + //! + //! @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_index(position); + } + + //! Get the element at the specified index. + //! + //! @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_index(position); + } + + //! @} + //! @name Capacity //! @{ @@ -61,6 +94,28 @@ namespace kstd //! @} private: + constexpr auto element_at_index(size_type index) noexcept -> pointer + { + auto base_pointer = reinterpret_cast(m_storage.data()); + auto storage_index = (m_tail + index) % capacity(); + return base_pointer + storage_index; + } + + constexpr auto element_at_index(size_type index) const noexcept -> const_pointer + { + return const_cast(this)->element_at_index(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. + alignas(ValueType) std::array m_storage{}; //! The index of the element that was most recently added to this ring buffer. size_type m_head{}; //! The index of the element that was least recently added to this ring buffer. diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 6e936248..86ff4b30 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -1,6 +1,10 @@ #include +#include + #include +#include +#include SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") { @@ -31,4 +35,29 @@ SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") } } } +} + +SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") +{ + GIVEN("An empty ring buffer") + { + auto buffer = kstd::ring_buffer{}; + + 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!")); + } + } + } } \ No newline at end of file -- cgit v1.2.3 From ee803577187b05d54026b48a2ae83f4ba6f8202a Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 16:52:58 +0200 Subject: kstd: ring_buffer: rename head and tail --- libs/kstd/kstd/ring_buffer.hpp | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 151ab994..6bdfce92 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -64,7 +64,7 @@ namespace kstd //! @return @p true iff. this ring buffer is empty, @p false otherwise. [[nodiscard]] constexpr auto empty() const noexcept -> bool { - return m_head == m_tail; + return m_write_index == m_read_index; } //! Get the size of this ring buffer. @@ -72,12 +72,12 @@ namespace kstd //! @return The number of elements currently stored in this ring buffer. [[nodiscard]] constexpr auto size() const noexcept -> size_type { - if (m_head >= m_tail) + if (m_write_index >= m_read_index) { - return m_head - m_tail; + return m_write_index - m_read_index; } - return capacity() - m_tail + m_head; + return capacity() - (m_read_index - m_write_index); } //! Get the maximum number of elements this ring buffer can hold. @@ -97,7 +97,7 @@ namespace kstd constexpr auto element_at_index(size_type index) noexcept -> pointer { auto base_pointer = reinterpret_cast(m_storage.data()); - auto storage_index = (m_tail + index) % capacity(); + auto storage_index = (m_read_index + index) % capacity(); return base_pointer + storage_index; } @@ -116,10 +116,10 @@ namespace kstd //! The underlying storage for the elements of this ring buffer. alignas(ValueType) std::array m_storage{}; - //! The index of the element that was most recently added to this ring buffer. - size_type m_head{}; - //! The index of the element that was least recently added to this ring buffer. - size_type m_tail{}; + //! The index of the next element to be written. + size_type m_write_index{}; + //! The index of the first element to be read. + size_type m_read_index{}; }; } // namespace kstd -- cgit v1.2.3 From 7b2945dd452257ffae1c122828a4734c9075a756 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 16:56:09 +0200 Subject: kstd: ring_buffer: add missing documentation --- libs/kstd/kstd/ring_buffer.hpp | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 6bdfce92..6a152731 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -94,18 +94,27 @@ namespace kstd //! @} private: - constexpr auto element_at_index(size_type index) noexcept -> pointer + //! 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_index(size_type position) noexcept -> pointer { auto base_pointer = reinterpret_cast(m_storage.data()); - auto storage_index = (m_read_index + index) % capacity(); + auto storage_index = (m_read_index + position) % capacity(); return base_pointer + storage_index; } - constexpr auto element_at_index(size_type index) const noexcept -> const_pointer + //! 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_index(size_type position) const noexcept -> const_pointer { - return const_cast(this)->element_at_index(index); + return const_cast(this)->element_at_index(position); } + //! 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()) -- cgit v1.2.3 From 9daf5549287b9e3addcac00e688f5ebc2decf0d0 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 17:29:59 +0200 Subject: kstd: ring_buffer: implement n-values ctor. --- libs/kstd/kstd/ring_buffer.hpp | 39 ++++++++++++++++++++++- libs/kstd/kstd/ring_buffer.tests.cpp | 61 ++++++++++++++++++++++++++++++++++++ 2 files changed, 99 insertions(+), 1 deletion(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 6a152731..61fbf360 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -3,8 +3,12 @@ #include +#include #include #include +#include +#include +#include namespace kstd { @@ -23,6 +27,27 @@ namespace kstd using const_reference = value_type const &; using size_type = std::size_t; + //! @name Special Member Functions + //! @{ + + //! Construct an empty ring buffer. + constexpr ring_buffer() noexcept = default; + + //! Construct a ring buffer with a given number of copies of a given value. + 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."); + } + + std::ranges::for_each(std::views::iota(0uz, count), + [&](auto i) { std::construct_at(&m_storage[i].value, value); }); + m_write_index = count % capacity(); + } + + //! @} + //! @name Element Access //! @{ @@ -94,6 +119,18 @@ namespace kstd //! @} private: + //! A helper type for value storage to enable constexpr construction in C++26. + union value_storage + { + std::monostate empty; + value_type value; + + constexpr value_storage() noexcept + : empty{} + {} + constexpr ~value_storage() noexcept {} + }; + //! Get a pointer to the element at the given read-index relative position. //! //! @param position The logical (read-index relative) index of the element. @@ -124,7 +161,7 @@ namespace kstd } //! The underlying storage for the elements of this ring buffer. - alignas(ValueType) std::array m_storage{}; + alignas(ValueType) std::array m_storage{}; //! The index of the next element to be written. size_type m_write_index{}; //! The index of the first element to be read. diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 86ff4b30..d2515289 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -34,6 +34,31 @@ SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") REQUIRE(buffer.max_size() == buffer.capacity()); } } + + WHEN("constructing by n-copies-of-value constructor using a capacity of 5") + { + auto buffer = kstd::ring_buffer{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()); + } + } } } @@ -60,4 +85,40 @@ SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") } } } + + GIVEN("A ring buffer with a capacity of 5 containing 3 copies of the letter 'a'") + { + auto buffer = kstd::ring_buffer{3, 'a'}; + + THEN("accessing the first 3 element return 'a'") + { + REQUIRE(buffer.at(0) == 'a'); + REQUIRE(buffer.at(1) == 'a'); + REQUIRE(buffer.at(2) == 'a'); + } + + THEN("accessing the fourth element 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("working through a const reference") + { + auto const & ref = buffer; + + THEN("accessing the first 3 element return 'a'") + { + REQUIRE(ref.at(0) == 'a'); + REQUIRE(ref.at(1) == 'a'); + REQUIRE(ref.at(2) == 'a'); + } + + THEN("accessing the fourth element panics") + { + REQUIRE_THROWS_MATCHES(ref.at(3), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Index out-of-bounds in ring_buffer element access!")); + } + } + } } \ No newline at end of file -- cgit v1.2.3 From 685a9b6403180957e2ef4e200088ecca0de40017 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 17:51:34 +0200 Subject: kstd: ring_buffer: rename element_at_index --- libs/kstd/kstd/ring_buffer.hpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 61fbf360..075701ee 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -58,7 +58,7 @@ namespace kstd [[nodiscard]] constexpr auto at(size_type position) -> reference { panic_on_invalid_index(position); - return *element_at_index(position); + return *element_at(position); } //! Get the element at the specified index. @@ -68,7 +68,7 @@ namespace kstd [[nodiscard]] constexpr auto at(size_type position) const -> const_reference { panic_on_invalid_index(position); - return *element_at_index(position); + return *element_at(position); } //! @} @@ -135,7 +135,7 @@ namespace kstd //! //! @param position The logical (read-index relative) index of the element. //! @return A pointer to the object at given position. - constexpr auto element_at_index(size_type position) noexcept -> pointer + constexpr auto element_at(size_type position) noexcept -> pointer { auto base_pointer = reinterpret_cast(m_storage.data()); auto storage_index = (m_read_index + position) % capacity(); @@ -146,7 +146,7 @@ namespace kstd //! //! @param position The logical (read-index relative) index of the element. //! @return A pointer to the object at given position. - constexpr auto element_at_index(size_type position) const noexcept -> const_pointer + constexpr auto element_at(size_type position) const noexcept -> const_pointer { return const_cast(this)->element_at_index(position); } -- cgit v1.2.3 From bf92802e0252315e9753a2817d22fd885b40111f Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 17:55:16 +0200 Subject: kstd: ring_buffer: simplify element_at --- libs/kstd/kstd/ring_buffer.hpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 075701ee..d8873b2c 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -137,9 +137,8 @@ namespace kstd //! @return A pointer to the object at given position. constexpr auto element_at(size_type position) noexcept -> pointer { - auto base_pointer = reinterpret_cast(m_storage.data()); auto storage_index = (m_read_index + position) % capacity(); - return base_pointer + storage_index; + return &m_storage[storage_index].value; } //! Get a pointer to the element at the given read-index relative position. @@ -148,7 +147,8 @@ namespace kstd //! @return A pointer to the object at given position. constexpr auto element_at(size_type position) const noexcept -> const_pointer { - return const_cast(this)->element_at_index(position); + auto storage_index = (m_read_index + position) % capacity(); + return &m_storage[storage_index].value; } //! Trigger a kernel panic if an attempt is made to use an invalid index. -- cgit v1.2.3 From fe342f77c1183ee7ef14f909005351dcdef3f162 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 17:58:21 +0200 Subject: kstd: ring_buffer: implement operator[] --- libs/kstd/kstd/ring_buffer.hpp | 28 +++++++++++++++++++++++++++- libs/kstd/kstd/ring_buffer.tests.cpp | 22 ++++++++++++++++++---- 2 files changed, 45 insertions(+), 5 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index d8873b2c..b40e167b 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -51,7 +51,9 @@ namespace kstd //! @name Element Access //! @{ - //! Get the element at the specified index. + //! 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. @@ -63,6 +65,8 @@ namespace kstd //! 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 @@ -71,6 +75,28 @@ namespace kstd 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); + } + //! @} //! @name Capacity diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index d2515289..bf1ae2a0 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -90,35 +90,49 @@ SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") { auto buffer = kstd::ring_buffer{3, 'a'}; - THEN("accessing the first 3 element return '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 panics") + 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!")); } + THEN("accessing the first 3 elements using operator[] returns 'a'") + { + REQUIRE(buffer[0] == 'a'); + REQUIRE(buffer[1] == 'a'); + REQUIRE(buffer[2] == 'a'); + } + WHEN("working through a const reference") { auto const & ref = buffer; - THEN("accessing the first 3 element return 'a'") + 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 panics") + 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(buffer[0] == 'a'); + REQUIRE(buffer[1] == 'a'); + REQUIRE(buffer[2] == 'a'); + } } } } \ No newline at end of file -- cgit v1.2.3 From 3a0f05541cc619128ee35a75921d7a53e01755ca Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 18:03:17 +0200 Subject: kstd: ring_buffer: add interface type tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 82 ++++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index bf1ae2a0..f0be78a1 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -6,6 +6,88 @@ #include #include +#include +#include +#include + +SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") +{ + GIVEN("A ring buffer of float") + { + using buffer = kstd::ring_buffer; + + THEN("value_type is 'float'") + { + STATIC_REQUIRE(std::is_same_v); + } + + THEN("reference is 'float &'") + { + STATIC_REQUIRE(std::is_same_v); + } + + THEN("const_reference is 'float const &'") + { + STATIC_REQUIRE(std::is_same_v); + } + + THEN("pointer is 'float *'") + { + STATIC_REQUIRE(std::is_same_v); + } + + THEN("size_type is 'std::size_t'") + { + STATIC_REQUIRE(std::is_same_v); + } + + THEN("const_pointer is 'float const *'") + { + STATIC_REQUIRE(std::is_same_v); + } + + THEN("the return type of at() is 'reference' on a non-const buffer") + { + STATIC_REQUIRE(std::is_same_v().at(0))>); + } + + THEN("the return type of at() is 'const_reference' on a non-const buffer") + { + STATIC_REQUIRE(std::is_same_v().at(0))>); + } + + THEN("the return type of operator[] is 'reference' on a non-const buffer") + { + STATIC_REQUIRE(std::is_same_v()[0])>); + } + + THEN("the return type of operator[] is 'const_reference' on a non-const buffer") + { + STATIC_REQUIRE(std::is_same_v()[0])>); + } + + THEN("the return type of capacity() is `size_type`") + { + STATIC_REQUIRE(std::is_same_v().capacity())>); + } + + THEN("the return type of empty() is `bool`") + { + STATIC_REQUIRE(std::is_same_v().empty())>); + } + + THEN("the return type of size() is `size_type`") + { + STATIC_REQUIRE(std::is_same_v().size())>); + } + + THEN("the return type of max_size() is `size_type`") + { + STATIC_REQUIRE(std::is_same_v().max_size())>); + } + } +} + SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") { GIVEN("An empty context") -- cgit v1.2.3 From d03255d508bc1c42b0e0509c7472723ad9adea92 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Wed, 30 Sep 2026 18:03:41 +0200 Subject: kstd: ring_buffer: add missing test tag --- libs/kstd/kstd/ring_buffer.tests.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index f0be78a1..ae7119ad 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -88,7 +88,7 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") } } -SCENARIO("Ring Buffer initialization and construction", "[ring_buffer]") +SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") { GIVEN("An empty context") { -- cgit v1.2.3 From 4b370847c5cb1f81d8bf82644898b71970124828 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 10:03:55 +0200 Subject: kstd: ring_buffer: extract basic storage --- libs/kstd/kstd/bits/basic_storage.hpp | 119 ++++++++++++++++++++++++++++++++++ libs/kstd/kstd/ring_buffer.hpp | 31 +++------ 2 files changed, 127 insertions(+), 23 deletions(-) create mode 100644 libs/kstd/kstd/bits/basic_storage.hpp 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 +#include +#include + +namespace kstd::bits +{ + + //! A fixed-size storage buffer for elements of a given type. + template + 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 + requires(std::is_constructible_v) + constexpr auto construct(size_type index, ConstructorArguments &&... constructor_arguments) noexcept( + std::is_nothrow_constructible_v) -> void + { + std::construct_at(entry(index), std::forward(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 m_elements{}; + }; + +} // 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 index b40e167b..44510e3e 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -1,14 +1,12 @@ #ifndef KSTD_RING_BUFFER_HPP #define KSTD_RING_BUFFER_HPP +#include #include #include -#include #include -#include #include -#include namespace kstd { @@ -41,8 +39,7 @@ namespace kstd os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); } - std::ranges::for_each(std::views::iota(0uz, count), - [&](auto i) { std::construct_at(&m_storage[i].value, value); }); + std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { m_storage.construct(i, value); }); m_write_index = count % capacity(); } @@ -107,7 +104,7 @@ namespace kstd //! @return The number of elements that can fit in this ring buffer. [[nodiscard]] constexpr auto capacity() const noexcept -> size_type { - return Capacity; + return m_storage.capacity(); } //! Check if this ring buffer is empty. @@ -145,26 +142,14 @@ namespace kstd //! @} private: - //! A helper type for value storage to enable constexpr construction in C++26. - union value_storage - { - std::monostate empty; - value_type value; - - constexpr value_storage() noexcept - : empty{} - {} - constexpr ~value_storage() noexcept {} - }; - //! 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 storage_index = (m_read_index + position) % capacity(); - return &m_storage[storage_index].value; + 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. @@ -173,8 +158,8 @@ namespace kstd //! @return A pointer to the object at given position. constexpr auto element_at(size_type position) const noexcept -> const_pointer { - auto storage_index = (m_read_index + position) % capacity(); - return &m_storage[storage_index].value; + 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. @@ -187,7 +172,7 @@ namespace kstd } //! The underlying storage for the elements of this ring buffer. - alignas(ValueType) std::array m_storage{}; + bits::basic_storage m_storage{}; //! The index of the next element to be written. size_type m_write_index{}; //! The index of the first element to be read. -- cgit v1.2.3 From bf4ac04c73439395220bb0e6e1b648cb85bb8551 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 10:22:43 +0200 Subject: kstd: ring_buffer: add ctor panic test --- libs/kstd/kstd/ring_buffer.tests.cpp | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index ae7119ad..d2e4a84d 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -141,6 +141,16 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") 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{6, 'a'}), kstd::tests::os_panic, + Catch::Matchers::Message( + "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } } } -- cgit v1.2.3 From 483a0e34401226b4f95104419186504f7dcfee56 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 14:12:45 +0200 Subject: kstd: ring_buffer: fix const-overload tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index d2e4a84d..7f459734 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -221,9 +221,9 @@ SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") THEN("accessing the first 3 elements using operator[] returns 'a'") { - REQUIRE(buffer[0] == 'a'); - REQUIRE(buffer[1] == 'a'); - REQUIRE(buffer[2] == 'a'); + REQUIRE(ref[0] == 'a'); + REQUIRE(ref[1] == 'a'); + REQUIRE(ref[2] == 'a'); } } } -- cgit v1.2.3 From a23125b5c15685e962ee4d2f63ca108ead2aa2eb Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 14:14:41 +0200 Subject: kstd: ring_buffer: add write-through tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 7f459734..2157b6c3 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -195,6 +195,22 @@ SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") 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'); @@ -202,6 +218,22 @@ SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") 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'); + } + } + WHEN("working through a const reference") { auto const & ref = buffer; -- cgit v1.2.3 From ec7b93a75335372e75ea9d49cd943fa6aae4b33c Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 15:01:08 +0200 Subject: kstd: ring_buffer: add n-value-initialized ctor --- libs/kstd/kstd/ring_buffer.hpp | 17 +++++++++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 35 +++++++++++++++++++++++++++++++++++ 2 files changed, 52 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 44510e3e..3e85baae 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -31,7 +31,24 @@ namespace kstd //! Construct an empty ring buffer. constexpr ring_buffer() noexcept = default; + //! 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."); + } + + std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { m_storage.construct(i); }); + m_write_index = count % capacity(); + } + //! 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()) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 2157b6c3..43ddafae 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -152,6 +152,41 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") } } } + + WHEN("constructing by n-value-initialized constructor using a capacity of 5") + { + auto buffer = kstd::ring_buffer{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{6}), kstd::tests::os_panic, + Catch::Matchers::Message("[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + } + } } SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") -- cgit v1.2.3 From 6eec2dbb59294bbfd5daa3acc250bc243b12b1a1 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 18:19:39 +0200 Subject: kstd: ring_buffer: implement iterator type --- libs/kstd/kstd/ring_buffer.hpp | 144 +++++++++++++++++++++++++++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 21 +++++ 2 files changed, 165 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 3e85baae..8328655d 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -5,8 +5,11 @@ #include #include +#include #include +#include #include +#include namespace kstd { @@ -18,12 +21,153 @@ namespace kstd template struct ring_buffer { + template + 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; + using const_iterator = ring_buffer_iterator; + using reverse_iterator = std::reverse_iterator; + using const_reverse_iterator = std::reverse_iterator; + + template + 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; + using reference = std::conditional_t; + + constexpr ring_buffer_iterator() = default; + + constexpr ring_buffer_iterator(ring_buffer_iterator const &) = default; + + constexpr ring_buffer_iterator(ring_buffer_iterator it) + requires Const + : m_buffer{it.m_buffer} + , m_index{it.m_index} + {} + + template + [[nodiscard]] constexpr auto friend operator<=>(ring_buffer_iterator const & lhs, + ring_buffer_iterator const & rhs) noexcept + -> std::strong_ordering + { + return lhs.m_index <=> rhs.m_index; + } + + template + [[nodiscard]] constexpr auto friend operator==(ring_buffer_iterator const & lhs, + ring_buffer_iterator const & rhs) noexcept -> bool + { + return lhs.m_buffer == rhs.m_buffer && lhs.m_index == rhs.m_index; + } + + [[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(); + } + + template + [[nodiscard]] constexpr auto operator-(ring_buffer_iterator const & other) const noexcept + -> difference_type + { + return static_cast(m_index) - static_cast(other.m_index); + } + + constexpr auto operator+=(difference_type offset) noexcept -> ring_buffer_iterator & + { + m_index += offset; + return *this; + } + + [[nodiscard]] constexpr auto friend operator+(ring_buffer_iterator it, difference_type offset) noexcept + -> ring_buffer_iterator + { + return it += offset; + } + + [[nodiscard]] constexpr auto friend operator+(difference_type offset, ring_buffer_iterator it) noexcept + -> ring_buffer_iterator + { + return it += offset; + } + + constexpr auto operator-=(difference_type offset) noexcept -> ring_buffer_iterator & + { + m_index -= offset; + return *this; + } + + [[nodiscard]] constexpr auto friend operator-(ring_buffer_iterator it, difference_type offset) noexcept + -> ring_buffer_iterator + { + return it -= offset; + } + + constexpr auto operator++() noexcept -> ring_buffer_iterator & + { + ++m_index; + return *this; + } + + constexpr auto operator++(int) noexcept -> ring_buffer_iterator + { + auto copy = *this; + ++(*this); + return copy; + } + + constexpr auto operator--() noexcept -> ring_buffer_iterator & + { + --m_index; + return *this; + } + + constexpr auto operator--(int) noexcept -> ring_buffer_iterator + { + auto copy = *this; + --(*this); + return copy; + } + + [[nodiscard]] constexpr auto operator[](difference_type offset) const noexcept -> reference + { + return (*m_buffer)[m_index + static_cast(offset)]; + } + + [[nodiscard]] constexpr auto operator*() const noexcept -> reference + { + return *m_buffer->element_at(m_index); + } + + [[nodiscard]] constexpr auto operator->() const noexcept -> pointer + { + return m_buffer->element_at(m_index); + } + + private: + friend struct ring_buffer; + friend struct ring_buffer_iterator; + + using buffer_type = std::conditional_t; + + constexpr ring_buffer_iterator(buffer_type * buffer, size_type index) + : m_buffer{buffer} + , m_index{index} + {} + + buffer_type * m_buffer{}; + size_type m_index{}; + }; //! @name Special Member Functions //! @{ diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 43ddafae..91535e04 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -7,6 +7,7 @@ #include #include +#include #include #include @@ -46,6 +47,26 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") STATIC_REQUIRE(std::is_same_v); } + THEN("iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator); + } + + THEN("const_iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator); + } + + THEN("reverse_iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator); + } + + THEN("const_reverse_iterator models std::random_access_iterator") + { + STATIC_REQUIRE(std::random_access_iterator); + } + THEN("the return type of at() is 'reference' on a non-const buffer") { STATIC_REQUIRE(std::is_same_v().at(0))>); -- cgit v1.2.3 From cf26fc5750ec2161317b1ad3375fd9c971590cf4 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 18:30:07 +0200 Subject: kstd: ring_buffer: implement [c]begin() --- libs/kstd/kstd/ring_buffer.hpp | 23 +++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 118 ++++++++++++++++++++++++++++++++++- 2 files changed, 140 insertions(+), 1 deletion(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 8328655d..a848f3ce 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -257,6 +257,29 @@ namespace kstd //! @} + //! @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}; + } + + //! @} + //! @name Capacity //! @{ diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 91535e04..a3881aa6 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -106,6 +106,21 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { STATIC_REQUIRE(std::is_same_v().max_size())>); } + + THEN("the return type of begin() is `iterator`") + { + STATIC_REQUIRE(std::is_same_v().begin())>); + } + + THEN("the return type of begin() is `const_iterator` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v().begin())>); + } + + THEN("the return type of cbegin() is `const_iterator`") + { + STATIC_REQUIRE(std::is_same_v().cbegin())>); + } } } @@ -315,4 +330,105 @@ SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") } } } -} \ No newline at end of file +} + +SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") +{ + GIVEN("An empty ring buffer") + { + auto buffer = kstd::ring_buffer{}; + + 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); + } + + 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); + } + } + } + + GIVEN("A ring buffer with a capacity of 5 containing 3 copies of the letter 'a'") + { + auto buffer = kstd::ring_buffer{3, 'a'}; + + THEN("begin() return an iterator that does not equal std::default_sentinel") + { + REQUIRE(buffer.begin() != std::default_sentinel); + } + + 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 to the first element") + { + REQUIRE(*buffer.cbegin() == '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 cbegin() past the end, yields an iterator equal to " + "std::default_sentinel") + { + auto it = buffer.cbegin(); + ++it; + ++it; + ++it; + + REQUIRE(it == std::default_sentinel); + } + + 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() 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); + } + } + } +} -- cgit v1.2.3 From 6ba358c98c855b685077a21160b357663be99b32 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 18:44:14 +0200 Subject: kstd: ring_buffer: implement [c]end() --- libs/kstd/kstd/ring_buffer.hpp | 18 ++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 117 ++++++++++++++++++++++++++++++++++- 2 files changed, 134 insertions(+), 1 deletion(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index a848f3ce..92605fc2 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -278,6 +278,24 @@ namespace kstd 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; + } + //! @} //! @name Capacity diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index a3881aa6..7a9c56be 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -121,6 +121,21 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { STATIC_REQUIRE(std::is_same_v().cbegin())>); } + + THEN("the return type of end() is `std::default_sentinel_t`") + { + STATIC_REQUIRE(std::is_same_v().end())>); + } + + THEN("the return type of end() is `std::default_sentinel_t` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v().end())>); + } + + THEN("the return type of cend() is `std::default_sentinel_t`") + { + STATIC_REQUIRE(std::is_same_v().cend())>); + } } } @@ -348,6 +363,26 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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()); + } + WHEN("working through a const reference") { auto const & ref = buffer; @@ -356,6 +391,11 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") { REQUIRE(ref.begin() == std::default_sentinel); } + + THEN("begin() returns an iterator equal to end()") + { + REQUIRE(buffer.begin() == buffer.end()); + } } } @@ -363,11 +403,21 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") { auto buffer = kstd::ring_buffer{3, 'a'}; - THEN("begin() return an iterator that does not equal std::default_sentinel") + 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("begin() returns an iterator to the first element") { REQUIRE(*buffer.begin() == 'a'); @@ -378,6 +428,16 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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'); @@ -394,6 +454,26 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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") { @@ -405,6 +485,26 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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()); + } + WHEN("working through a const reference") { auto const & ref = buffer; @@ -414,6 +514,11 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") REQUIRE(ref.begin() != std::default_sentinel); } + THEN("begin() return an iterator that does not equal end()") + { + REQUIRE(ref.begin() != ref.end()); + } + THEN("begin() returns an iterator to the first element") { REQUIRE(*ref.begin() == 'a'); @@ -429,6 +534,16 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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()); + } } } } -- cgit v1.2.3 From 390e34ce7fc09daddd8180c4e687ab585e102c47 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 18:50:26 +0200 Subject: kstd: ring_buffer: add more range-based tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 50 ++++++++++++++++++++++++++++++++++++ 1 file changed, 50 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 7a9c56be..a118c2c3 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -383,6 +383,21 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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); + } + WHEN("working through a const reference") { auto const & ref = buffer; @@ -396,6 +411,16 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") { 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); + } } } @@ -418,6 +443,21 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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'); @@ -519,6 +559,16 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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'); -- cgit v1.2.3 From 966f2a709f6aa4a022c7c13900f97c083ee8a92a Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 19:30:27 +0200 Subject: kstd: ring_buffer: fix empty() and size() --- libs/kstd/kstd/ring_buffer.hpp | 17 ++++++----------- libs/kstd/kstd/ring_buffer.tests.cpp | 20 ++++++++++++++++++++ 2 files changed, 26 insertions(+), 11 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 92605fc2..48f4da0d 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -186,7 +186,7 @@ namespace kstd } std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { m_storage.construct(i); }); - m_write_index = count % capacity(); + m_size = count; } //! Construct a ring buffer with a given number of copies of a given value. @@ -201,7 +201,7 @@ namespace kstd } std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { m_storage.construct(i, value); }); - m_write_index = count % capacity(); + m_size = count; } //! @} @@ -314,7 +314,7 @@ namespace kstd //! @return @p true iff. this ring buffer is empty, @p false otherwise. [[nodiscard]] constexpr auto empty() const noexcept -> bool { - return m_write_index == m_read_index; + return m_size == 0; } //! Get the size of this ring buffer. @@ -322,12 +322,7 @@ namespace kstd //! @return The number of elements currently stored in this ring buffer. [[nodiscard]] constexpr auto size() const noexcept -> size_type { - if (m_write_index >= m_read_index) - { - return m_write_index - m_read_index; - } - - return capacity() - (m_read_index - m_write_index); + return m_size; } //! Get the maximum number of elements this ring buffer can hold. @@ -375,8 +370,8 @@ namespace kstd //! The underlying storage for the elements of this ring buffer. bits::basic_storage m_storage{}; - //! The index of the next element to be written. - size_type m_write_index{}; + //! 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{}; }; diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index a118c2c3..bff8f804 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -204,6 +204,26 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") } } + GIVEN("A full buffer") + { + auto buffer = kstd::ring_buffer{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()); + } + } + WHEN("constructing by n-value-initialized constructor using a capacity of 5") { auto buffer = kstd::ring_buffer{3}; -- cgit v1.2.3 From 22c50a96dfb66d1503bccb9a4fc480507dc237c0 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 21:48:21 +0200 Subject: kstd: ring_buffer: implement [cr][begin|end]() --- libs/kstd/kstd/ring_buffer.hpp | 36 +++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 144 +++++++++++++++++++++++++++++++++++ 2 files changed, 180 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 48f4da0d..b015755d 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -296,6 +296,42 @@ namespace kstd 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 diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index bff8f804..84adba91 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -136,6 +136,21 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { STATIC_REQUIRE(std::is_same_v().cend())>); } + + THEN("the return type of rbegin() is `reverse_iterator`") + { + STATIC_REQUIRE(std::is_same_v().rbegin())>); + } + + THEN("the return type of rbegin() is `const_reverse_iterator` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v().rbegin())>); + } + + THEN("the return type of crbegin() is `const_reverse_iterator`") + { + STATIC_REQUIRE(std::is_same_v().crbegin())>); + } } } @@ -418,6 +433,36 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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; @@ -441,6 +486,16 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") { 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); + } } } @@ -503,6 +558,46 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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") { @@ -565,6 +660,45 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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()); + } WHEN("working through a const reference") { auto const & ref = buffer; @@ -614,6 +748,16 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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()); + } } } } -- cgit v1.2.3 From 3385a54840c7985dde6a5b47d263920db4d6ed06 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 21:52:14 +0200 Subject: kstd: ring_buffer: add missing [c]rend() tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 15 +++++++++++++++ 1 file changed, 15 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 84adba91..f6613f33 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -151,6 +151,21 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { STATIC_REQUIRE(std::is_same_v().crbegin())>); } + + THEN("the return type of rend() is `reverse_iterator`") + { + STATIC_REQUIRE(std::is_same_v().rend())>); + } + + THEN("the return type of rend() is `const_reverse_iterator` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v().rend())>); + } + + THEN("the return type of crend() is `const_reverse_iterator`") + { + STATIC_REQUIRE(std::is_same_v().crend())>); + } } } -- cgit v1.2.3 From 3c6253cbd2ef9342ff572c9a09cc612f54f1fab6 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 21:54:59 +0200 Subject: kstd: ring_buffer: move construction tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 64 ++++++++++++++++++------------------ 1 file changed, 32 insertions(+), 32 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index f6613f33..32002d79 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -232,31 +232,46 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") "[KSTD] Tried to construct a ring buffer with more elements than it can support.")); } } - } - GIVEN("A full buffer") - { - auto buffer = kstd::ring_buffer{5}; - - THEN("the capacity is 5") + WHEN("constructing by n-value-initialized constructor using a capacity of 5") { - REQUIRE(buffer.capacity() == 5); - } + auto buffer = kstd::ring_buffer{3}; - THEN("the buffer is not empty") - { - REQUIRE_FALSE(buffer.empty()); + 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()); + } } - THEN("the size is equal to the capacity") + WHEN("constructing by n-value-initialized constructor using a capacity of 5 and 6 copies") { - REQUIRE(buffer.size() == buffer.capacity()); + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer{6}), 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") + GIVEN("A full buffer") { - auto buffer = kstd::ring_buffer{3}; + auto buffer = kstd::ring_buffer{5}; THEN("the capacity is 5") { @@ -268,24 +283,9 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") 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") + THEN("the size is equal to the capacity") { - REQUIRE_THROWS_MATCHES( - (kstd::ring_buffer{6}), kstd::tests::os_panic, - Catch::Matchers::Message("[KSTD] Tried to construct a ring buffer with more elements than it can support.")); + REQUIRE(buffer.size() == buffer.capacity()); } } } -- cgit v1.2.3 From 1b22cd5cced7ccdd829472b087f04c421cac2ff8 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 22:02:15 +0200 Subject: kstd: ring_buffer: implement dtor --- libs/kstd/kstd/ring_buffer.hpp | 6 +++++ libs/kstd/kstd/ring_buffer.tests.cpp | 50 ++++++++++++++++++++++++++++++++++++ 2 files changed, 56 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index b015755d..aa0b3a5c 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -175,6 +175,12 @@ namespace kstd //! Construct an empty ring buffer. constexpr ring_buffer() noexcept = default; + //! Destroy this ring buffer. + constexpr ~ring_buffer() noexcept + { + std::ranges::for_each(std::views::reverse(*this), [](auto & element) { std::destroy_at(&element); }); + } + //! Construct a ring buffer with a given number of value initialized elements. //! //! @param count The number of value initialized elements to construct. diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 32002d79..2a2d23b0 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -8,9 +8,24 @@ #include #include +#include #include #include +namespace +{ + struct static_dtor_tracker + { + auto static inline dtor_call_count = 0uz; + + ~static_dtor_tracker() + { + ++dtor_call_count; + } + }; + +} // namespace + SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { GIVEN("A ring buffer of float") @@ -290,6 +305,41 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") } } +SCENARIO("Ring Buffer destruction", "[kstd][ring_buffer]") +{ + GIVEN("An empty buffer") + { + static_dtor_tracker::dtor_call_count = 0; + auto buffer = std::make_shared>(); + + WHEN("the buffer is destroyed") + { + buffer.reset(); + + THEN("no dtors are invoked") + { + REQUIRE(static_dtor_tracker::dtor_call_count == 0); + } + } + } + + GIVEN("A buffer containing 3 elements") + { + static_dtor_tracker::dtor_call_count = 0; + auto buffer = std::make_shared>(3); + + WHEN("the buffer is destroyed") + { + buffer.reset(); + + THEN("3 dtors are invoked") + { + REQUIRE(static_dtor_tracker::dtor_call_count == 3); + } + } + } +} + SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") { GIVEN("An empty ring buffer") -- cgit v1.2.3 From bf7cfad29d6af61a3171136566990cb288e3f695 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 22:14:48 +0200 Subject: kstd: ring_buffer: implement copy ctor --- libs/kstd/kstd/ring_buffer.hpp | 9 +++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 27 +++++++++++++++++++++++++++ 2 files changed, 36 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index aa0b3a5c..2b97e0a9 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -175,6 +175,15 @@ namespace kstd //! 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) + : m_size{other.m_size} + , m_read_index{} + { + std::ranges::for_each(std::views::iota(0uz, other.size()), + [&](auto const i) { m_storage.construct(i, other[i]); }); + } + //! Destroy this ring buffer. constexpr ~ring_buffer() noexcept { diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 2a2d23b0..4e34249b 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -6,9 +6,12 @@ #include #include +#include #include +#include #include #include +#include #include #include @@ -303,6 +306,30 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") REQUIRE(buffer.size() == buffer.capacity()); } } + + GIVEN("A buffer with a capacity of 5 containing 3 elements") + { + auto buffer = kstd::ring_buffer{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)); + } + } + } } SCENARIO("Ring Buffer destruction", "[kstd][ring_buffer]") -- cgit v1.2.3 From fd732cf67681cffb717eff769ee0c2cd6de67d2b Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 22:33:14 +0200 Subject: kstd: ring_buffer: implement move ctor --- libs/kstd/kstd/ring_buffer.hpp | 9 +++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 16 ++++++++++++++++ 2 files changed, 25 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 2b97e0a9..d2f0f958 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -184,6 +184,15 @@ namespace kstd [&](auto const i) { m_storage.construct(i, other[i]); }); } + //! Construct a ring buffer by moving from an existing one. + constexpr ring_buffer(ring_buffer && other) + : m_size{other.m_size} + , m_read_index{} + { + std::ranges::for_each(std::views::iota(0uz, other.size()), + [&](auto const i) { m_storage.construct(i, std::move(other[i])); }); + } + //! Destroy this ring buffer. constexpr ~ring_buffer() noexcept { diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 4e34249b..537ed27e 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -329,6 +329,22 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") 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)); + } + } } } -- cgit v1.2.3 From e7af4fdb86a14e026d7c31dccc901210623a3efc Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 22:50:49 +0200 Subject: kstd: ring_buffer: implement copy and move assignment --- libs/kstd/kstd/ring_buffer.hpp | 57 +++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 182 +++++++++++++++++++++++++++++++++++ 2 files changed, 239 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index d2f0f958..c332d2e2 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -8,6 +8,7 @@ #include #include #include +#include #include #include @@ -228,6 +229,62 @@ namespace kstd m_size = count; } + //! 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) -> 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]); }); + } + else if (to_copy_assign < m_size) + { + std::ranges::for_each(std::views::drop(*this, to_copy_assign), + [](auto & element) { std::destroy_at(&element); }); + } + + m_size = other.m_size; + 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) -> ring_buffer & + { + if (this == &other) + { + return *this; + } + + auto const to_move_assign = std::min(m_size, other.m_size); + std::ranges::move(std::views::take(other, to_move_assign), std::ranges::begin(*this)); + + if (to_move_assign < other.m_size) + { + std::ranges::for_each(std::views::iota(to_move_assign, other.m_size), + [&](auto const i) { std::construct_at(element_at(i), std::move(other[i])); }); + } + else if (to_move_assign < m_size) + { + std::ranges::for_each(std::views::drop(*this, to_move_assign), + [](auto & element) { std::destroy_at(&element); }); + } + + m_size = other.m_size; + return *this; + } + //! @} //! @name Element Access diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 537ed27e..95a235e6 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -27,6 +27,47 @@ namespace } }; + 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; + + constexpr 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; + + constexpr static_copy_move_tracker(static_copy_move_tracker const &) + { + ++copy_ctor_call_count; + } + + constexpr static_copy_move_tracker(static_copy_move_tracker &&) + { + ++move_ctor_call_count; + } + + constexpr auto operator=(static_copy_move_tracker const &) -> static_copy_move_tracker & + { + ++copy_assignment_call_count; + return *this; + } + + constexpr auto operator=(static_copy_move_tracker &&) -> static_copy_move_tracker & + { + ++move_assignment_call_count; + return *this; + } + }; + } // namespace SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") @@ -348,6 +389,147 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") } } +SCENARIO("Ring Buffer assignment", "[kstd][ring_buffer]") +{ + GIVEN("3 partially populated buffers") + { + auto small = kstd::ring_buffer{2}; + auto same = kstd::ring_buffer{2}; + auto large = kstd::ring_buffer{3}; + + WHEN("copy assigning the small to the large one") + { + static_copy_move_tracker::reset(); + large = small; + + THEN("2 copy assignments and 1 destruction occurs") + { + REQUIRE(static_copy_move_tracker::dtor_call_count == 1); + REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 2); + REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("copy assigning the large to the small one") + { + static_copy_move_tracker::reset(); + small = large; + + THEN("2 copy assignments and 1 copy construction occurs") + { + REQUIRE(static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 1); + REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 2); + REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("copy assigning the small to the same size one") + { + static_copy_move_tracker::reset(); + same = small; + + THEN("2 copy assignments occur") + { + REQUIRE(static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 2); + REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("copy assigning a buffer to itself") + { + 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(static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + } + } + + WHEN("move assigning the small to the large one") + { + static_copy_move_tracker::reset(); + large = std::move(small); + + THEN("2 move assignments and 1 destruction occurs") + { + REQUIRE(static_copy_move_tracker::dtor_call_count == 1); + REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::move_assignment_call_count == 2); + } + } + + WHEN("move assigning the large to the small one") + { + static_copy_move_tracker::reset(); + small = std::move(large); + + THEN("2 move assignments and 1 move construction occurs") + { + REQUIRE(static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(static_copy_move_tracker::move_ctor_call_count == 1); + REQUIRE(static_copy_move_tracker::move_assignment_call_count == 2); + } + } + + WHEN("move assigning the small to the same size one") + { + static_copy_move_tracker::reset(); + same = std::move(small); + + THEN("2 move assignments occur") + { + REQUIRE(static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::move_assignment_call_count == 2); + } + } + + WHEN("move assigning a buffer to itself") + { + 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(static_copy_move_tracker::dtor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); + REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); + REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + } + } + } +} + SCENARIO("Ring Buffer destruction", "[kstd][ring_buffer]") { GIVEN("An empty buffer") -- cgit v1.2.3 From 25e893e3651889aa74fa1aafb5c1ed0899890692 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 1 Oct 2026 23:28:28 +0200 Subject: kstd: tests: extract static tracker types --- libs/kstd/kstd/ring_buffer.tests.cpp | 170 ++++++++++------------------- libs/kstd/kstd/test_support/test_types.hpp | 51 +++++++++ 2 files changed, 109 insertions(+), 112 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 95a235e6..8cd50e2f 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -1,6 +1,7 @@ #include #include +#include #include #include @@ -15,61 +16,6 @@ #include #include -namespace -{ - 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; - - constexpr 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; - - constexpr static_copy_move_tracker(static_copy_move_tracker const &) - { - ++copy_ctor_call_count; - } - - constexpr static_copy_move_tracker(static_copy_move_tracker &&) - { - ++move_ctor_call_count; - } - - constexpr auto operator=(static_copy_move_tracker const &) -> static_copy_move_tracker & - { - ++copy_assignment_call_count; - return *this; - } - - constexpr auto operator=(static_copy_move_tracker &&) -> static_copy_move_tracker & - { - ++move_assignment_call_count; - return *this; - } - }; - -} // namespace - SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { GIVEN("A ring buffer of float") @@ -393,58 +339,58 @@ SCENARIO("Ring Buffer assignment", "[kstd][ring_buffer]") { GIVEN("3 partially populated buffers") { - auto small = kstd::ring_buffer{2}; - auto same = kstd::ring_buffer{2}; - auto large = kstd::ring_buffer{3}; + auto small = kstd::ring_buffer{2}; + auto same = kstd::ring_buffer{2}; + auto large = kstd::ring_buffer{3}; WHEN("copy assigning the small to the large one") { - static_copy_move_tracker::reset(); + kstd::tests::static_copy_move_tracker::reset(); large = small; THEN("2 copy assignments and 1 destruction occurs") { - REQUIRE(static_copy_move_tracker::dtor_call_count == 1); - REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 2); - REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + 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") { - static_copy_move_tracker::reset(); + kstd::tests::static_copy_move_tracker::reset(); small = large; THEN("2 copy assignments and 1 copy construction occurs") { - REQUIRE(static_copy_move_tracker::dtor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 1); - REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 2); - REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + 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") { - static_copy_move_tracker::reset(); + kstd::tests::static_copy_move_tracker::reset(); same = small; THEN("2 copy assignments occur") { - REQUIRE(static_copy_move_tracker::dtor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 2); - REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + 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") { - static_copy_move_tracker::reset(); + kstd::tests::static_copy_move_tracker::reset(); #if defined(__clang__) #pragma clang diagnostic push @@ -457,62 +403,62 @@ SCENARIO("Ring Buffer assignment", "[kstd][ring_buffer]") THEN("no operations occur") { - REQUIRE(static_copy_move_tracker::dtor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); - REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + 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") { - static_copy_move_tracker::reset(); + kstd::tests::static_copy_move_tracker::reset(); large = std::move(small); THEN("2 move assignments and 1 destruction occurs") { - REQUIRE(static_copy_move_tracker::dtor_call_count == 1); - REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); - REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::move_assignment_call_count == 2); + 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 == 2); } } WHEN("move assigning the large to the small one") { - static_copy_move_tracker::reset(); + kstd::tests::static_copy_move_tracker::reset(); small = std::move(large); THEN("2 move assignments and 1 move construction occurs") { - REQUIRE(static_copy_move_tracker::dtor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); - REQUIRE(static_copy_move_tracker::move_ctor_call_count == 1); - REQUIRE(static_copy_move_tracker::move_assignment_call_count == 2); + 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 == 2); } } WHEN("move assigning the small to the same size one") { - static_copy_move_tracker::reset(); + kstd::tests::static_copy_move_tracker::reset(); same = std::move(small); THEN("2 move assignments occur") { - REQUIRE(static_copy_move_tracker::dtor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); - REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::move_assignment_call_count == 2); + 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 == 2); } } WHEN("move assigning a buffer to itself") { - static_copy_move_tracker::reset(); + kstd::tests::static_copy_move_tracker::reset(); #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wself-move" same = std::move(same); @@ -520,11 +466,11 @@ SCENARIO("Ring Buffer assignment", "[kstd][ring_buffer]") THEN("no operations occur") { - REQUIRE(static_copy_move_tracker::dtor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::copy_assignment_call_count == 0); - REQUIRE(static_copy_move_tracker::move_ctor_call_count == 0); - REQUIRE(static_copy_move_tracker::move_assignment_call_count == 0); + 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); } } } @@ -534,8 +480,8 @@ SCENARIO("Ring Buffer destruction", "[kstd][ring_buffer]") { GIVEN("An empty buffer") { - static_dtor_tracker::dtor_call_count = 0; - auto buffer = std::make_shared>(); + kstd::tests::static_dtor_tracker::dtor_call_count = 0; + auto buffer = std::make_shared>(); WHEN("the buffer is destroyed") { @@ -543,15 +489,15 @@ SCENARIO("Ring Buffer destruction", "[kstd][ring_buffer]") THEN("no dtors are invoked") { - REQUIRE(static_dtor_tracker::dtor_call_count == 0); + REQUIRE(kstd::tests::static_dtor_tracker::dtor_call_count == 0); } } } GIVEN("A buffer containing 3 elements") { - static_dtor_tracker::dtor_call_count = 0; - auto buffer = std::make_shared>(3); + kstd::tests::static_dtor_tracker::dtor_call_count = 0; + auto buffer = std::make_shared>(3); WHEN("the buffer is destroyed") { @@ -559,7 +505,7 @@ SCENARIO("Ring Buffer destruction", "[kstd][ring_buffer]") THEN("3 dtors are invoked") { - REQUIRE(static_dtor_tracker::dtor_call_count == 3); + REQUIRE(kstd::tests::static_dtor_tracker::dtor_call_count == 3); } } } diff --git a/libs/kstd/kstd/test_support/test_types.hpp b/libs/kstd/kstd/test_support/test_types.hpp index baf5e853..2ee8e0fc 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; + + constexpr 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; + + constexpr static_copy_move_tracker(static_copy_move_tracker const &) + { + ++copy_ctor_call_count; + } + + constexpr static_copy_move_tracker(static_copy_move_tracker &&) + { + ++move_ctor_call_count; + } + + constexpr auto operator=(static_copy_move_tracker const &) -> static_copy_move_tracker & + { + ++copy_assignment_call_count; + return *this; + } + + constexpr 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. -- cgit v1.2.3 From 9a01bef5542b26f13467d2fc6fde935d6301a98b Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 06:40:35 +0200 Subject: kstd: ring_buffer: implement clear() --- libs/kstd/kstd/ring_buffer.hpp | 14 ++++++++++- libs/kstd/kstd/ring_buffer.tests.cpp | 49 ++++++++++++++++++++++++++++++++++++ 2 files changed, 62 insertions(+), 1 deletion(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index c332d2e2..8741c6db 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -197,7 +197,7 @@ namespace kstd //! Destroy this ring buffer. constexpr ~ring_buffer() noexcept { - std::ranges::for_each(std::views::reverse(*this), [](auto & element) { std::destroy_at(&element); }); + clear(); } //! Construct a ring buffer with a given number of value initialized elements. @@ -455,6 +455,18 @@ namespace kstd //! @} + //! @name Modifiers + //! @{ + + constexpr auto clear() noexcept -> void + { + std::ranges::for_each(std::views::reverse(*this), [](auto & element) { std::destroy_at(&element); }); + m_size = 0; + m_read_index = 0; + } + + //! @} + private: //! Get a pointer to the element at the given read-index relative position. //! diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 8cd50e2f..163d537c 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -997,3 +997,52 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") } } } + +SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") +{ + GIVEN("An empty ring buffer") + { + auto buffer = kstd::ring_buffer{}; + + 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); + } + } + } + + GIVEN("A ring buffer containing static operation trackers") + { + auto buffer = kstd::ring_buffer{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); + } + } + } +} \ No newline at end of file -- cgit v1.2.3 From b95beb4597dec47fee3a3d3134eea138e72d27a8 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 06:52:44 +0200 Subject: kstd: ring_buffer: clear moved-from buffer While the standard says that a move-from object is in a valid but unspecified state, thus making it legal to leave the moved-from buffer in a non-empty state, we can do better here. For one, standard containers generally leave the moved-from object in an empty state. Secondly, destroying the contents of a ring_buffer object has linear complexity, as does moving the contents of a ring_buffer object. We can therefore clear the moved-from object while we are moving from it, without increasing the complexity of the move operation. At the same time, we can thereby reduce the amount of work that needs to be done when the moved-from object is finally destroyed. Note that during the move assignment operation, the moved-from buffer is in a somewhat peculiar state. Some of its elements have been destroyed, but its size has not changed. This is okay, because we are essentially still executing a transition from one valid state into another once. At the end of the move operation, we ensure that the size of the moved-from buffer is set to zero, thus reestablishing its invariant. --- libs/kstd/kstd/ring_buffer.hpp | 22 ++++++++++++++++------ libs/kstd/kstd/ring_buffer.tests.cpp | 32 ++++++++++++++++++++++++++------ 2 files changed, 42 insertions(+), 12 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 8741c6db..66d870dd 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -11,6 +11,7 @@ #include #include #include +#include namespace kstd { @@ -190,8 +191,11 @@ namespace kstd : m_size{other.m_size} , m_read_index{} { - std::ranges::for_each(std::views::iota(0uz, other.size()), - [&](auto const i) { m_storage.construct(i, std::move(other[i])); }); + std::ranges::for_each(std::views::iota(0uz, other.size()), [&](auto const i) { + m_storage.construct(i, std::move(other[i])); + std::destroy_at(other.element_at(i)); + }); + other.m_size = 0; } //! Destroy this ring buffer. @@ -268,12 +272,18 @@ namespace kstd } auto const to_move_assign = std::min(m_size, other.m_size); - std::ranges::move(std::views::take(other, to_move_assign), std::ranges::begin(*this)); + std::ranges::for_each(std::views::enumerate(std::views::take(other, to_move_assign)), [&](auto const & entry) { + auto & [i, element] = entry; + (*this)[i] = std::move(element); + std::destroy_at(other.element_at(i)); + }); if (to_move_assign < other.m_size) { - std::ranges::for_each(std::views::iota(to_move_assign, other.m_size), - [&](auto const i) { std::construct_at(element_at(i), std::move(other[i])); }); + std::ranges::for_each(std::views::iota(to_move_assign, other.m_size), [&](auto const i) { + std::construct_at(element_at(i), std::move(other[i])); + std::destroy_at(other.element_at(i)); + }); } else if (to_move_assign < m_size) { @@ -281,7 +291,7 @@ namespace kstd [](auto & element) { std::destroy_at(&element); }); } - m_size = other.m_size; + m_size = std::exchange(other.m_size, 0); return *this; } diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 163d537c..d22633d6 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -331,6 +331,11 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") { REQUIRE(std::ranges::equal(moved, copy)); } + + THEN("the moved-from buffer is empty") + { + REQUIRE(buffer.empty()); + } } } } @@ -416,14 +421,19 @@ SCENARIO("Ring Buffer assignment", "[kstd][ring_buffer]") kstd::tests::static_copy_move_tracker::reset(); large = std::move(small); - THEN("2 move assignments and 1 destruction occurs") + THEN("2 move assignments and 3 destructions occur") { - REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 1); + 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") @@ -431,14 +441,19 @@ SCENARIO("Ring Buffer assignment", "[kstd][ring_buffer]") kstd::tests::static_copy_move_tracker::reset(); small = std::move(large); - THEN("2 move assignments and 1 move construction occurs") + THEN("2 move assignments, 1 move construction, and 3 destructions occur") { - REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + 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") @@ -446,14 +461,19 @@ SCENARIO("Ring Buffer assignment", "[kstd][ring_buffer]") kstd::tests::static_copy_move_tracker::reset(); same = std::move(small); - THEN("2 move assignments occur") + THEN("2 move assignments and 2 destructions occur") { - REQUIRE(kstd::tests::static_copy_move_tracker::dtor_call_count == 0); + 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") -- cgit v1.2.3 From 555c181c042be054fb9574d8fc77d2663bd39d4f Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 11:36:01 +0200 Subject: kstd: ring_buffer: implement push_back() --- libs/kstd/kstd/ring_buffer.hpp | 41 +++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 232 ++++++++++++++++++++++++++++++++++- 2 files changed, 271 insertions(+), 2 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 66d870dd..755ebbf6 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -475,6 +475,47 @@ namespace kstd m_read_index = 0; } + //! 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) -> void + { + 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) -> void + { + 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(); + } + //! @} private: diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index d22633d6..3da3f7ea 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -6,6 +6,7 @@ #include #include #include +#include #include #include @@ -1020,7 +1021,7 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") { - GIVEN("An empty ring buffer") + GIVEN("An empty ring buffer with capcity 5") { auto buffer = kstd::ring_buffer{}; @@ -1038,9 +1039,95 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") 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})); + } + } } - GIVEN("A ring buffer containing static operation trackers") + GIVEN("A ring buffer with a capacity of 5 containing 3 elements") + { + auto buffer = kstd::ring_buffer{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{3}; @@ -1064,5 +1151,146 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") 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); + } + } + } + } + + GIVEN("A full ring buffer of static operation trackers") + { + auto buffer = kstd::ring_buffer{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); + } + } } } \ No newline at end of file -- cgit v1.2.3 From 058136e4e99b99dfa932941fc632b776ff1b590b Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 12:59:43 +0200 Subject: kstd: ring_buffer: implement try_push_back() --- libs/kstd/kstd/ring_buffer.hpp | 18 ++++++++++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 10 ++++++++++ 2 files changed, 28 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 755ebbf6..af70e991 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -6,6 +6,7 @@ #include #include +#include #include #include #include @@ -516,6 +517,23 @@ namespace kstd 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 ad dto the end of this ring buffer. + //! @return @p true iff. the buffer had space for the value, @p false otherwise. + template + requires(std::same_as>) + constexpr auto try_push_back(PushedType && value) -> bool + { + if (m_size >= capacity()) + { + return false; + } + + push_back(std::forward(value)); + return true; + } + //! @} private: diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 3da3f7ea..0b332494 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -1100,6 +1100,11 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") 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)); + } } GIVEN("A ring buffer with a capacity of 5 containing 3 elements") @@ -1292,5 +1297,10 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") 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{})); + } } } \ No newline at end of file -- cgit v1.2.3 From fb9b0f01f023973a9544ab758dfaf13ddc0a9de1 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 13:34:49 +0200 Subject: kstd: ring_buffer: implement pop_front() --- libs/kstd/kstd/ring_buffer.hpp | 15 ++++++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 38 ++++++++++++++++++++++++++++++++++++ 2 files changed, 53 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index af70e991..5039c7b4 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -534,6 +534,21 @@ namespace kstd return true; } + //! Remove the first element in the buffer. + //! + //! @warning This function will panic if the buffer is empty. + constexpr auto pop_front() -> void + { + if (empty()) + { + os::panic("[KSTD] Tried to pop an element from an empty ring_buffer!"); + } + + std::destroy_at(element_at(0)); + m_read_index = (m_read_index + 1) % capacity(); + --m_size; + } + //! @} private: diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 0b332494..479283ed 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -1105,6 +1105,12 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") { 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!")); + } } GIVEN("A ring buffer with a capacity of 5 containing 3 elements") @@ -1242,6 +1248,38 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") } } } + + WHEN("popping an element") + { + buffer.pop_front(); + + THEN("the size is 2") + { + REQUIRE(buffer.size() == 2); + } + + THEN("the buffer is not empty") + { + REQUIRE_FALSE(buffer.empty()); + } + } + + 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()); + } + } } GIVEN("A full ring buffer of static operation trackers") -- cgit v1.2.3 From 0dcc94e36a83dd9828798cc416c7bf07cb01562a Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 14:35:07 +0200 Subject: kstd: ring_buffer: fix documentation typo --- libs/kstd/kstd/ring_buffer.hpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 5039c7b4..591ff445 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -519,7 +519,7 @@ namespace kstd //! Try to add an element to the end of this ring buffer. //! - //! @param value The value to ad dto 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 requires(std::same_as>) -- cgit v1.2.3 From 88c9a78261fe1d54e297c7ac8bd4c052c19985fc Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 14:35:22 +0200 Subject: kstd: ring_buffer: add missing nodiscard --- libs/kstd/kstd/ring_buffer.hpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 591ff445..10ee334d 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -523,7 +523,7 @@ namespace kstd //! @return @p true iff. the buffer had space for the value, @p false otherwise. template requires(std::same_as>) - constexpr auto try_push_back(PushedType && value) -> bool + [[nodiscard]] constexpr auto try_push_back(PushedType && value) -> bool { if (m_size >= capacity()) { -- cgit v1.2.3 From 9b789956ff8013d21d6b4074de488f1eb5eb4625 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 14:41:59 +0200 Subject: kstd: ring_buffer: add more pop_front() tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 43 ++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 479283ed..767e7422 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -1341,4 +1341,47 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") REQUIRE_FALSE(buffer.try_push_back(kstd::tests::static_copy_move_tracker{})); } } + + GIVEN("A ring buffer with a capacity of 3 that has wrapped around") + { + auto buffer = kstd::ring_buffer{}; + 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); + } + } + } } \ No newline at end of file -- cgit v1.2.3 From 80a1bc7959576cc120332ed25b2c050d8397df28 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 14:58:16 +0200 Subject: kstd: ring_buffer: implement try_pop_front() --- libs/kstd/kstd/ring_buffer.hpp | 14 +++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 57 ++++++++++++++++++++++++++++++++++++ 2 files changed, 71 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 10ee334d..34f8a2d8 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -549,6 +549,20 @@ namespace kstd --m_size; } + //! 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) -> bool + { + if (empty()) + { + return false; + } + + pop_front(); + return true; + } + //! @} private: diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 767e7422..889a0c36 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -1111,6 +1111,11 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") 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") @@ -1280,6 +1285,58 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") 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()); + } + } } GIVEN("A full ring buffer of static operation trackers") -- cgit v1.2.3 From 5c7c3f83f2d78cbab383cd7e0d4a9a542696cd6d Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 14:59:22 +0200 Subject: kstd: ring_buffer: add try_pop_front dtor test --- libs/kstd/kstd/ring_buffer.tests.cpp | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 889a0c36..58037e1c 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -1256,6 +1256,7 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") WHEN("popping an element") { + kstd::tests::static_copy_move_tracker::reset(); buffer.pop_front(); THEN("the size is 2") @@ -1267,6 +1268,15 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") { 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") -- cgit v1.2.3 From d7d4e918e7a2ef893dff836554893dab6c833cc5 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 15:21:05 +0200 Subject: kstd: ring_buffer: add missing push/pop API tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 58037e1c..bd14223f 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -172,6 +172,26 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { STATIC_REQUIRE(std::is_same_v().crend())>); } + + THEN("the return type of push_back() is void") + { + STATIC_REQUIRE(std::is_same_v().push_back(std::declval()))>); + } + + THEN("the return type of try_push_back() is bool") + { + STATIC_REQUIRE(std::is_same_v().try_push_back(buffer::value_type{}))>); + } + + THEN("the return type of pop_front() is void") + { + STATIC_REQUIRE(std::is_same_v().pop_front())>); + } + + THEN("the return type of try_pop_front() is bool") + { + STATIC_REQUIRE(std::is_same_v().try_pop_front())>); + } } } -- cgit v1.2.3 From a564a638466f52eba8f4bff04259d77be695217a Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 15:21:54 +0200 Subject: kstd: ring_buffer: implement front() and back() --- libs/kstd/kstd/ring_buffer.hpp | 60 ++++++++++++++++++++++++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 71 ++++++++++++++++++++++++++++++++++++ 2 files changed, 131 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 34f8a2d8..eec998e6 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -347,6 +347,66 @@ namespace kstd 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 diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index bd14223f..12a88e8f 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -192,6 +192,26 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { STATIC_REQUIRE(std::is_same_v().try_pop_front())>); } + + THEN("the return type of front() is `reference`") + { + STATIC_REQUIRE(std::is_same_v().front())>); + } + + THEN("the return type of front() is `const_reference` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v().front())>); + } + + THEN("the return type of back() is `reference`") + { + STATIC_REQUIRE(std::is_same_v().back())>); + } + + THEN("the return type of back() is `const_reference` on a const buffer") + { + STATIC_REQUIRE(std::is_same_v().back())>); + } } } @@ -574,6 +594,37 @@ SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") 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'") @@ -632,6 +683,16 @@ SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") } } + 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; @@ -655,6 +716,16 @@ SCENARIO("Ring Buffer element access", "[kstd][ring_buffer]") 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))); + } } } } -- cgit v1.2.3 From da509fa854178842433739dc03f862ab9d5a4682 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 15:33:21 +0200 Subject: kstd: ring_buffer: add iterator documentation --- libs/kstd/kstd/ring_buffer.hpp | 84 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 84 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index eec998e6..ce737a81 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -38,6 +38,9 @@ namespace kstd using reverse_iterator = std::reverse_iterator; using const_reverse_iterator = std::reverse_iterator; + //! An iterator type for ring buffers. + //! + //! @tparam Const Whether this iterator is a const iterator. template struct ring_buffer_iterator { @@ -48,16 +51,29 @@ namespace kstd using pointer = std::conditional_t; using reference = std::conditional_t; + //! 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 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 [[nodiscard]] constexpr auto friend operator<=>(ring_buffer_iterator const & lhs, ring_buffer_iterator const & rhs) noexcept @@ -66,6 +82,12 @@ namespace kstd 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 [[nodiscard]] constexpr auto friend operator==(ring_buffer_iterator const & lhs, ring_buffer_iterator const & rhs) noexcept -> bool @@ -73,12 +95,22 @@ namespace kstd 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 [[nodiscard]] constexpr auto operator-(ring_buffer_iterator const & other) const noexcept -> difference_type @@ -86,42 +118,71 @@ namespace kstd return static_cast(m_index) - static_cast(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; @@ -129,12 +190,18 @@ namespace kstd 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; @@ -142,16 +209,26 @@ namespace kstd 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(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); @@ -161,14 +238,21 @@ namespace kstd friend struct ring_buffer; friend struct ring_buffer_iterator; + //! The type of the referenced buffer. using buffer_type = std::conditional_t; + //! 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{}; }; -- cgit v1.2.3 From bf59e881f3d4069d01e1dfad7c2cd8db54975763 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 15:47:50 +0200 Subject: kstd: ring_buffer: add more iterator tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 64 ++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 12a88e8f..99dbe3eb 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -1047,6 +1047,70 @@ SCENARIO("Ring Buffer iterators", "[kstd][ring_buffer]") 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; -- cgit v1.2.3 From 7087754a7360424518774cbb0fdf4b577edc167b Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 16:50:47 +0200 Subject: kstd: ring_buffer: handle zero-capacity instantiations --- libs/kstd/kstd/ring_buffer.hpp | 33 ++++-- libs/kstd/kstd/ring_buffer.tests.cpp | 224 +++++++++++++++++++++++++++++++++++ 2 files changed, 249 insertions(+), 8 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index ce737a81..10f45d72 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -626,6 +626,7 @@ namespace kstd //! //! @param value The value to add to the end of this ring buffer. constexpr auto push_back(value_type const & value) -> void + requires(Capacity > 0) { if (m_size < capacity()) { @@ -645,6 +646,7 @@ namespace kstd //! //! @param value The value to add to the end of this ring buffer. constexpr auto push_back(value_type && value) -> void + requires(Capacity > 0) { if (m_size < capacity()) { @@ -669,19 +671,27 @@ namespace kstd requires(std::same_as>) [[nodiscard]] constexpr auto try_push_back(PushedType && value) -> bool { - if (m_size >= capacity()) + if constexpr (Capacity > 0) + { + if (m_size >= capacity()) + { + return false; + } + + push_back(std::forward(value)); + return true; + } + else { return false; } - - push_back(std::forward(value)); - return true; } //! 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()) { @@ -698,13 +708,20 @@ namespace kstd //! @return @p true iff. an element was removed, @p false otherwise [[nodiscard]] constexpr auto try_pop_front() noexcept(std::is_nothrow_destructible_v) -> bool { - if (empty()) + if constexpr (Capacity > 0) + { + if (empty()) + { + return false; + } + + pop_front(); + return true; + } + else { return false; } - - pop_front(); - return true; } //! @} diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 99dbe3eb..453713ee 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -17,6 +17,16 @@ #include #include +namespace +{ + template + concept has_push_back = requires(BufferType buffer) { buffer.push_back(typename BufferType::value_type{}); }; + + template + concept has_pop_front = requires(BufferType buffer) { buffer.pop_front(); }; + +} // namespace + SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { GIVEN("A ring buffer of float") @@ -1606,4 +1616,218 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") } } } +} + +SCENARIO("Ring Buffer zero capacity", "[kstd][rin_buffer]") +{ + GIVEN("A ring buffer with a capacity of 0") + { + auto buffer = kstd::ring_buffer{}; + + 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); + } + + THEN("pop_front cannot be called") + { + STATIC_REQUIRE_FALSE(has_pop_front); + } + + 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{}; + other = buffer; + + THEN("the target is still empty") + { + REQUIRE(other.empty()); + } + } + + WHEN("move assigning to another zero-capacity buffer") + { + auto other = kstd::ring_buffer{}; + other = std::move(buffer); + + THEN("the target is still empty") + { + REQUIRE(other.empty()); + } + } + } + + WHEN("constructing by n-value-initialized constructor with a count of 0") + { + auto buffer = kstd::ring_buffer{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{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{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{1, 42}), 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{}; + + 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); + } + } + } } \ No newline at end of file -- cgit v1.2.3 From caf47befa014c9f2d6a5503527198ac736db2456 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 16:58:15 +0200 Subject: ci: merge test build and test execution --- .gitlab-ci.yml | 92 +++++++++++++++++++++++----------------------------------- 1 file changed, 37 insertions(+), 55 deletions(-) diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index ca18bd90..e77794b9 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -1,20 +1,52 @@ -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" 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: + paths: + - coverage/ + 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 +72,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: -- cgit v1.2.3 From f652d85c8e5f635b67bcb57d4143568d1216cf6d Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 17:17:33 +0200 Subject: kstd: ring_buffer: implement comparison --- libs/kstd/kstd/ring_buffer.hpp | 28 ++++++++ libs/kstd/kstd/ring_buffer.tests.cpp | 127 ++++++++++++++++++++++++++++++++++- 2 files changed, 154 insertions(+), 1 deletion(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 10f45d72..9cd533c4 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -382,6 +382,34 @@ namespace kstd //! @} + //! @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 //! @{ diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 453713ee..3476179e 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -222,6 +222,17 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { STATIC_REQUIRE(std::is_same_v().back())>); } + + THEN("the return type of operator== is `bool`") + { + STATIC_REQUIRE(std::is_same_v() == std::declval())>); + } + + THEN("the return type of operator<=> is the same as for the value_type") + { + STATIC_REQUIRE(std::is_same_v() <=> std::declval()), + decltype(std::declval() <=> std::declval())>); + } } } @@ -1618,7 +1629,7 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") } } -SCENARIO("Ring Buffer zero capacity", "[kstd][rin_buffer]") +SCENARIO("Ring Buffer zero capacity", "[kstd][ring_buffer]") { GIVEN("A ring buffer with a capacity of 0") { @@ -1830,4 +1841,118 @@ SCENARIO("Ring Buffer zero capacity", "[kstd][rin_buffer]") } } } +} + +SCENARIO("Ring Buffer comparison", "[kstd][ring_buffer]") +{ + GIVEN("Two ring buffers with the same content, constructed the same way") + { + auto lhs = kstd::ring_buffer{3, 1}; + auto rhs = kstd::ring_buffer{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{3, 1}; + + THEN("it compares equal to itself") + { + REQUIRE(buffer == buffer); + } + } + + GIVEN("Two empty ring buffers") + { + auto lhs = kstd::ring_buffer{}; + auto rhs = kstd::ring_buffer{}; + + THEN("they compare equal") + { + REQUIRE(lhs == rhs); + } + } + + GIVEN("Two ring buffers with different content") + { + auto smaller = kstd::ring_buffer{3, 1}; + auto larger = kstd::ring_buffer{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{2, 1}; + auto longer = kstd::ring_buffer{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{}; + wrapped.push_back(1); + wrapped.push_back(2); + wrapped.push_back(3); + wrapped.push_back(4); + + auto fresh = kstd::ring_buffer{}; + 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{}; + auto rhs = kstd::ring_buffer{}; + + THEN("they compare equal") + { + REQUIRE(lhs == rhs); + } + } } \ No newline at end of file -- cgit v1.2.3 From 01f013c2cfb8f5e4dae53a17a2f035edba8a9388 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 18:53:02 +0200 Subject: kstd: ring_buffer: implement emplace_back() --- libs/kstd/kstd/ring_buffer.hpp | 20 +++++ libs/kstd/kstd/ring_buffer.tests.cpp | 139 +++++++++++++++++++++++++++++++++++ 2 files changed, 159 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 9cd533c4..7b9012aa 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -648,6 +648,26 @@ namespace kstd m_read_index = 0; } + //! 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 + requires(Capacity > 0) + constexpr auto emplace_back(Args &&... args) -> reference + { + if (m_size < capacity()) + { + auto constructed = std::construct_at(element_at(m_size), std::forward(args)...); + ++m_size; + return *constructed; + } + + (*this)[0] = value_type{std::forward(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. diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 3476179e..b08ee222 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -25,6 +25,21 @@ namespace template concept has_pop_front = requires(BufferType buffer) { buffer.pop_front(); }; + template + 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]") @@ -233,6 +248,11 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") STATIC_REQUIRE(std::is_same_v() <=> std::declval()), decltype(std::declval() <=> std::declval())>); } + + THEN("the return type of emplace_back() is `reference`") + { + STATIC_REQUIRE(std::is_same_v().emplace_back(0.0f))>); + } } } @@ -1523,6 +1543,22 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") 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") @@ -1583,6 +1619,32 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") { 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") @@ -1627,6 +1689,78 @@ SCENARIO("Ring Buffer modifiers", "[kstd][ring_buffer]") } } } + + GIVEN("An empty ring buffer of points with a capacity of 3") + { + auto buffer = kstd::ring_buffer{}; + + 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{}; + + 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{ + 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]") @@ -1759,6 +1893,11 @@ SCENARIO("Ring Buffer zero capacity", "[kstd][ring_buffer]") REQUIRE(other.empty()); } } + + THEN("emplace_back cannot be called") + { + STATIC_REQUIRE_FALSE(has_emplace_back); + } } WHEN("constructing by n-value-initialized constructor with a count of 0") -- cgit v1.2.3 From 19c6f9e83cc453336804a3192ffd759847405d68 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 18:55:39 +0200 Subject: ci: add missing coverage regex --- .gitlab-ci.yml | 1 + 1 file changed, 1 insertion(+) diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index e77794b9..f0387238 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -13,6 +13,7 @@ bht: - 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/ -- cgit v1.2.3 From c4a1429a53b43ef8e6e7176f54bd1902426b5b3d Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 18:56:06 +0200 Subject: ci: remove non-existent coverage folder --- .gitlab-ci.yml | 2 -- 1 file changed, 2 deletions(-) diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index f0387238..9d38f6ee 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -39,8 +39,6 @@ bht-stress: - 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: - paths: - - coverage/ reports: codequality: code-quality-$PRESET-$TYPE.json junit: build/bht-stress/**/bht_results/*.xml -- cgit v1.2.3 From f19b8d50bf6653214a0a68e62af12f1de6f65de3 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 2 Oct 2026 19:33:32 +0200 Subject: kstd: ring_buffer: implement swap --- libs/kstd/kstd/ring_buffer.hpp | 35 +++++ libs/kstd/kstd/ring_buffer.tests.cpp | 250 +++++++++++++++++++++++++++++++++++ 2 files changed, 285 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 7b9012aa..152bf697 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -774,6 +774,41 @@ namespace kstd //! @} + //! @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 && + std::is_nothrow_move_constructible_v) -> 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. //! diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index b08ee222..d870c2f8 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -253,6 +253,11 @@ SCENARIO("Ring Buffer interface types", "[kstd][ring_buffer]") { STATIC_REQUIRE(std::is_same_v().emplace_back(0.0f))>); } + + THEN("the return type of swap() is void") + { + STATIC_REQUIRE(std::is_same_v(), std::declval()))>); + } } } @@ -2094,4 +2099,249 @@ SCENARIO("Ring Buffer comparison", "[kstd][ring_buffer]") 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{3, 1}; + auto b = kstd::ring_buffer{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{}; + fresh.push_back(10); + fresh.push_back(20); + fresh.push_back(30); + + auto wrapped = kstd::ring_buffer{}; + 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{2, 7}; + auto large = kstd::ring_buffer{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{}; + for (int v : {1, 2, 3, 4, 5, 6}) + { + a.push_back(v); + } + a.pop_front(); + + auto b = kstd::ring_buffer{}; + 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{}; + auto full = kstd::ring_buffer{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{}; + auto b = kstd::ring_buffer{}; + + 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{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{3}; + auto b = kstd::ring_buffer{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{5}; + auto small = kstd::ring_buffer{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 &>(), std::declval &>()))); + } + } + + GIVEN("A value type whose move operations are not noexcept") + { + THEN("swap() is not noexcept") + { + STATIC_REQUIRE_FALSE( + noexcept(swap(std::declval &>(), + std::declval &>()))); + } + } } \ No newline at end of file -- cgit v1.2.3 From a4fe8ea88e8ce6f1a211598894e6157bab86a369 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 5 Oct 2026 12:51:19 +0200 Subject: kstd: ring_buffer: implement iterator ctors --- libs/kstd/kstd/ring_buffer.hpp | 41 ++++ libs/kstd/kstd/ring_buffer.tests.cpp | 296 +++++++++++++++++++++++++++++ libs/kstd/kstd/test_support/test_types.hpp | 192 +++++++++++++++++++ 3 files changed, 529 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 152bf697..2f6a6b9f 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -318,6 +318,47 @@ namespace kstd m_size = count; } + //! 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 + constexpr ring_buffer(InputIterator first, InputIterator last) + { + for (; first != last && m_size < capacity(); ++first) + { + push_back(std::ranges::iter_move(first)); + } + + if (first != last) + { + clear(); + os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); + } + } + + //! 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 + constexpr ring_buffer(ForwardIterator first, ForwardIterator last) + { + auto const number_of_source_elements = static_cast(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."); + } + + std::ranges::for_each(first, last, [this](auto const & element) { this->push_back(element); }); + } + //! Replace the content of this ring buffer with a copy of the content of another one. //! //! @param other The ring buffer to copy from. diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index d870c2f8..ef3452d3 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -9,7 +9,9 @@ #include #include +#include #include +#include #include #include #include @@ -425,6 +427,300 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") } } } + + GIVEN("A single-pass input range with fewer elements than the capacity") + { + std::array 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{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 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{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 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{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{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 source{}; + auto first = + kstd::tests::mutable_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::mutable_input_iterator{}; + + 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{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 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{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 source{}; + auto first = + kstd::tests::mutable_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::mutable_input_iterator{}; + + WHEN("constructing from the range") + { + kstd::tests::static_copy_move_tracker::reset(); + auto buffer = kstd::ring_buffer{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 source{}; + auto first = kstd::tests::const_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::const_input_iterator{}; + + WHEN("constructing from the range") + { + kstd::tests::static_copy_move_tracker::reset(); + auto buffer = kstd::ring_buffer{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 source{kstd::tests::move_only_value{1}, + kstd::tests::move_only_value{2}}; + auto first = kstd::tests::mutable_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::mutable_input_iterator{}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer{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{1, 2, 3}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer{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{1, 2, 3}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer{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{1, 2, 3, 4, 5}; + + WHEN("constructing from the range") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer{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{}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer{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{}; + 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{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{}; + source.emplace_front(); + source.emplace_front(); + + WHEN("constructing from the range") + { + kstd::tests::static_copy_move_tracker::reset(); + auto buffer = kstd::ring_buffer{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{7, 8, 10}; + + WHEN("constructing both buffers from the same range") + { + auto first_buffer = kstd::ring_buffer{source.begin(), source.end()}; + auto second_buffer = kstd::ring_buffer{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})); + } + } + } } SCENARIO("Ring Buffer assignment", "[kstd][ring_buffer]") diff --git a/libs/kstd/kstd/test_support/test_types.hpp b/libs/kstd/kstd/test_support/test_types.hpp index 2ee8e0fc..0d830077 100644 --- a/libs/kstd/kstd/test_support/test_types.hpp +++ b/libs/kstd/kstd/test_support/test_types.hpp @@ -234,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. @@ -415,6 +433,180 @@ namespace kstd::tests } }; + //! A test input iterator that yields mutable references to its elements. + template + 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 + 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 -- cgit v1.2.3 From 3bc20030f591acb0e23311964bcd576614caf268 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 5 Oct 2026 13:04:37 +0200 Subject: kstd: ring_buffer: add missing noexcept specifications --- libs/kstd/kstd/ring_buffer.hpp | 27 ++++++++++++++++++--------- 1 file changed, 18 insertions(+), 9 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 2f6a6b9f..8176b68b 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -263,7 +263,7 @@ namespace kstd constexpr ring_buffer() noexcept = default; //! Construct a ring buffer by copying from an existing one. - constexpr ring_buffer(ring_buffer const & other) + constexpr ring_buffer(ring_buffer const & other) noexcept(std::is_nothrow_copy_constructible_v) : m_size{other.m_size} , m_read_index{} { @@ -272,7 +272,8 @@ namespace kstd } //! Construct a ring buffer by moving from an existing one. - constexpr ring_buffer(ring_buffer && other) + constexpr ring_buffer(ring_buffer && other) noexcept(std::is_nothrow_move_constructible_v && + std::is_nothrow_destructible_v) : m_size{other.m_size} , m_read_index{} { @@ -284,7 +285,7 @@ namespace kstd } //! Destroy this ring buffer. - constexpr ~ring_buffer() noexcept + constexpr ~ring_buffer() noexcept(std::is_nothrow_destructible_v) { clear(); } @@ -362,7 +363,10 @@ namespace kstd //! 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) -> ring_buffer & + constexpr auto operator=(ring_buffer const & other) noexcept(std::is_nothrow_copy_constructible_v && + std::is_nothrow_copy_assignable_v && + std::is_nothrow_destructible_v) + -> ring_buffer & { if (this == &other) { @@ -390,7 +394,9 @@ namespace kstd //! 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) -> ring_buffer & + constexpr auto operator=(ring_buffer && other) noexcept(std::is_nothrow_move_constructible_v && + std::is_nothrow_move_assignable_v && + std::is_nothrow_destructible_v) -> ring_buffer & { if (this == &other) { @@ -682,7 +688,7 @@ namespace kstd //! @name Modifiers //! @{ - constexpr auto clear() noexcept -> void + constexpr auto clear() noexcept(std::is_nothrow_destructible_v) -> void { std::ranges::for_each(std::views::reverse(*this), [](auto & element) { std::destroy_at(&element); }); m_size = 0; @@ -695,7 +701,8 @@ namespace kstd //! @param args The arguments to forward to the constructor of the element. template requires(Capacity > 0) - constexpr auto emplace_back(Args &&... args) -> reference + constexpr auto emplace_back(Args &&... args) noexcept(std::is_nothrow_constructible_v) + -> reference { if (m_size < capacity()) { @@ -714,7 +721,8 @@ namespace kstd //! 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) -> void + constexpr auto push_back(value_type const & value) noexcept(std::is_nothrow_copy_constructible_v && + std::is_nothrow_copy_assignable_v) -> void requires(Capacity > 0) { if (m_size < capacity()) @@ -734,7 +742,8 @@ namespace kstd //! assignment will be performed. //! //! @param value The value to add to the end of this ring buffer. - constexpr auto push_back(value_type && value) -> void + constexpr auto push_back(value_type && value) noexcept(std::is_nothrow_move_constructible_v && + std::is_nothrow_move_assignable_v) -> void requires(Capacity > 0) { if (m_size < capacity()) -- cgit v1.2.3 From 01438d77a5cfd21ab9e11afba9be9386731e61f9 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 5 Oct 2026 14:19:45 +0200 Subject: kstd: tests: remove nonsensical constexpr qualification --- libs/kstd/kstd/test_support/test_types.hpp | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/libs/kstd/kstd/test_support/test_types.hpp b/libs/kstd/kstd/test_support/test_types.hpp index 0d830077..ed3a8f7a 100644 --- a/libs/kstd/kstd/test_support/test_types.hpp +++ b/libs/kstd/kstd/test_support/test_types.hpp @@ -25,7 +25,7 @@ namespace kstd::tests auto static inline move_ctor_call_count = 0uz; auto static inline move_assignment_call_count = 0uz; - constexpr auto static reset() -> void + auto static reset() -> void { dtor_call_count = 0; copy_ctor_call_count = 0; @@ -36,23 +36,23 @@ namespace kstd::tests constexpr static_copy_move_tracker() = default; - constexpr static_copy_move_tracker(static_copy_move_tracker const &) + static_copy_move_tracker(static_copy_move_tracker const &) { ++copy_ctor_call_count; } - constexpr static_copy_move_tracker(static_copy_move_tracker &&) + static_copy_move_tracker(static_copy_move_tracker &&) { ++move_ctor_call_count; } - constexpr auto operator=(static_copy_move_tracker const &) -> static_copy_move_tracker & + auto operator=(static_copy_move_tracker const &) -> static_copy_move_tracker & { ++copy_assignment_call_count; return *this; } - constexpr auto operator=(static_copy_move_tracker &&) -> static_copy_move_tracker & + auto operator=(static_copy_move_tracker &&) -> static_copy_move_tracker & { ++move_assignment_call_count; return *this; -- cgit v1.2.3 From 6e467ace41a9c5b21b3013340127b341faa8754f Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 5 Oct 2026 14:20:04 +0200 Subject: kstd: ring_buffer: provide basic exception safety --- libs/kstd/kstd/ring_buffer.hpp | 59 ++++++++++++++++++++++++++++-------------- 1 file changed, 39 insertions(+), 20 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 8176b68b..48711cd3 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -3,6 +3,7 @@ #include #include +#include #include #include @@ -378,16 +379,20 @@ namespace kstd 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]); }); + 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::drop(*this, to_copy_assign), - [](auto & element) { std::destroy_at(&element); }); + 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); + }); } - m_size = other.m_size; return *this; } @@ -404,26 +409,34 @@ namespace kstd } auto const to_move_assign = std::min(m_size, other.m_size); - std::ranges::for_each(std::views::enumerate(std::views::take(other, to_move_assign)), [&](auto const & entry) { - auto & [i, element] = entry; - (*this)[i] = std::move(element); - std::destroy_at(other.element_at(i)); + 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 (to_move_assign < other.m_size) + if (other.m_size > 0) { - std::ranges::for_each(std::views::iota(to_move_assign, other.m_size), [&](auto const i) { - std::construct_at(element_at(i), std::move(other[i])); - std::destroy_at(other.element_at(i)); + 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::drop(*this, to_move_assign), - [](auto & element) { std::destroy_at(&element); }); + 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); + }); } - m_size = std::exchange(other.m_size, 0); return *this; } @@ -688,11 +701,16 @@ namespace kstd //! @name Modifiers //! @{ + //! Clear all elements from this ring buffer. constexpr auto clear() noexcept(std::is_nothrow_destructible_v) -> void { - std::ranges::for_each(std::views::reverse(*this), [](auto & element) { std::destroy_at(&element); }); - m_size = 0; - m_read_index = 0; + if constexpr (Capacity > 0) + { + while (!empty()) + { + pop_front(); + } + } } //! Construct an element at the end of this ring buffer. @@ -796,9 +814,10 @@ namespace kstd os::panic("[KSTD] Tried to pop an element from an empty ring_buffer!"); } - std::destroy_at(element_at(0)); + 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. -- cgit v1.2.3 From dbdfee9637042a765ab0a9d6882e8b665b6b0e51 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 5 Oct 2026 15:21:30 +0200 Subject: kstd: ring_buffer: fix ctor exception safety --- libs/kstd/kstd/ring_buffer.hpp | 92 +++++++++++++++++++++++++++++++++--------- 1 file changed, 74 insertions(+), 18 deletions(-) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 48711cd3..99584a90 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -265,24 +265,29 @@ namespace kstd //! Construct a ring buffer by copying from an existing one. constexpr ring_buffer(ring_buffer const & other) noexcept(std::is_nothrow_copy_constructible_v) - : m_size{other.m_size} - , m_read_index{} { - std::ranges::for_each(std::views::iota(0uz, other.size()), - [&](auto const i) { m_storage.construct(i, other[i]); }); + auto guard = 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 && std::is_nothrow_destructible_v) - : m_size{other.m_size} - , m_read_index{} { - std::ranges::for_each(std::views::iota(0uz, other.size()), [&](auto const i) { - m_storage.construct(i, std::move(other[i])); - std::destroy_at(other.element_at(i)); + auto guard = 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); }); - other.m_size = 0; + guard.disarm(); } //! Destroy this ring buffer. @@ -301,8 +306,12 @@ namespace kstd os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); } - std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { m_storage.construct(i); }); - m_size = count; + auto guard = 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. @@ -316,8 +325,12 @@ namespace kstd os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); } - std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { m_storage.construct(i, value); }); - m_size = count; + auto guard = 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. @@ -330,16 +343,21 @@ namespace kstd template constexpr ring_buffer(InputIterator first, InputIterator last) { - for (; first != last && m_size < capacity(); ++first) + auto guard = construction_guard{*this}; + if constexpr (Capacity > 0) { - push_back(std::ranges::iter_move(first)); + for (; first != last && m_size < capacity(); ++first) + { + push_back(std::ranges::iter_move(first)); + } } if (first != last) { - clear(); 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. @@ -358,7 +376,12 @@ namespace kstd os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); } - std::ranges::for_each(first, last, [this](auto const & element) { this->push_back(element); }); + if constexpr (Capacity > 0) + { + auto guard = construction_guard{*this}; + std::ranges::for_each(first, last, [this](auto const & element) { this->push_back(element); }); + guard.disarm(); + } } //! Replace the content of this ring buffer with a copy of the content of another one. @@ -879,6 +902,39 @@ namespace kstd //! @} private: + //! An RAII guard to ensure partially constructed buffers are properly cleaned up. + struct construction_guard + { + //! Construct a new construction guard for the given ring buffer. + constexpr explicit construction_guard(ring_buffer & buf) + : m_buffer{&buf} + {} + + constexpr construction_guard(construction_guard const &) = delete; + constexpr construction_guard(construction_guard &&) = delete; + + //! Destroy the construction guard, clearing the buffer if it is still engaged. + constexpr ~construction_guard() + { + if (m_buffer) + { + m_buffer->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 buffer. + constexpr auto disarm() noexcept -> void + { + m_buffer = nullptr; + } + + private: + ring_buffer * m_buffer; + }; + //! Get a pointer to the element at the given read-index relative position. //! //! @param position The logical (read-index relative) index of the element. -- cgit v1.2.3 From b636d6a31a9bfb0bbe0e4e4a3c10963cc1e29de7 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 5 Oct 2026 15:53:47 +0200 Subject: kstd: ring_buffer: implement from_range ctor --- libs/kstd/kstd/ring_buffer.hpp | 26 +++++ libs/kstd/kstd/ring_buffer.tests.cpp | 193 +++++++++++++++++++++++++++++++++++ 2 files changed, 219 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.hpp b/libs/kstd/kstd/ring_buffer.hpp index 99584a90..a87ee381 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -2,6 +2,7 @@ #define KSTD_RING_BUFFER_HPP #include +#include #include #include @@ -384,6 +385,31 @@ namespace kstd } } + //! 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 + requires((std::ranges::forward_range || std::ranges::sized_range) && + kstd::bits::container_compatible_range) + constexpr ring_buffer(kstd::from_range_t, Range && range) + { + if (static_cast(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 = construction_guard{*this}; + std::ranges::for_each(std::forward(range), + [this](auto && element) { this->push_back(std::forward(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. diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index ef3452d3..2517ff7b 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -1,5 +1,6 @@ #include +#include #include #include @@ -18,6 +19,7 @@ #include #include #include +#include namespace { @@ -721,6 +723,175 @@ SCENARIO("Ring Buffer initialization and construction", "[kstd][ring_buffer]") } } } + + GIVEN("A forward range with fewer elements than the capacity, constructed via kstd::from_range") + { + auto source = std::forward_list{1, 2, 3}; + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer{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{1, 2, 3}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer{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{1, 2, 3, 4, 5}; + + WHEN("constructing from the range") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer{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{}; + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer{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{}; + 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::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 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{first, last, source.size()}; + + STATIC_REQUIRE(std::ranges::sized_range); + STATIC_REQUIRE_FALSE(std::ranges::forward_range); + + WHEN("constructing from the range") + { + auto buffer = kstd::ring_buffer{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 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{first, last, source.size()}; + + WHEN("constructing from the range") + { + THEN("the constructor panics") + { + REQUIRE_THROWS_MATCHES((kstd::ring_buffer{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 source{}; + auto first = + kstd::tests::mutable_input_iterator{source.data(), source.size()}; + auto last = kstd::tests::mutable_input_iterator{}; + auto range = std::ranges::subrange, + kstd::tests::mutable_input_iterator, + 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::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(3); + + WHEN("constructing from the range") + { + kstd::tests::static_copy_move_tracker::reset(); + auto buffer = + kstd::ring_buffer{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]") @@ -2241,6 +2412,28 @@ SCENARIO("Ring Buffer zero capacity", "[kstd][ring_buffer]") } } + WHEN("constructing by from-range constructor with an empty range") + { + auto source = std::forward_list{}; + auto buffer = kstd::ring_buffer{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{1}; + REQUIRE_THROWS_MATCHES( + (kstd::ring_buffer{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("A zero-capacity buffer of static operation trackers") { auto buffer = kstd::ring_buffer{}; -- cgit v1.2.3 From d466390c43965fafd1474d3a263afc688ca4ac6a Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 5 Oct 2026 16:14:38 +0200 Subject: kstd: extract construction_guard --- libs/kstd/kstd/bits/construction_guard.hpp | 46 ++++++++++++++++++++++++++++ libs/kstd/kstd/ring_buffer.hpp | 48 +++++------------------------- 2 files changed, 54 insertions(+), 40 deletions(-) create mode 100644 libs/kstd/kstd/bits/construction_guard.hpp 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 + 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 index a87ee381..e9a733a3 100644 --- a/libs/kstd/kstd/ring_buffer.hpp +++ b/libs/kstd/kstd/ring_buffer.hpp @@ -3,6 +3,7 @@ #include #include +#include #include #include @@ -267,7 +268,7 @@ namespace kstd //! Construct a ring buffer by copying from an existing one. constexpr ring_buffer(ring_buffer const & other) noexcept(std::is_nothrow_copy_constructible_v) { - auto guard = construction_guard{*this}; + 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; @@ -279,7 +280,7 @@ namespace kstd constexpr ring_buffer(ring_buffer && other) noexcept(std::is_nothrow_move_constructible_v && std::is_nothrow_destructible_v) { - auto guard = construction_guard{*this}; + 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; @@ -307,7 +308,7 @@ namespace kstd os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); } - auto guard = construction_guard{*this}; + auto guard = bits::construction_guard{this}; std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { m_storage.construct(i); ++m_size; @@ -326,7 +327,7 @@ namespace kstd os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support."); } - auto guard = construction_guard{*this}; + auto guard = bits::construction_guard{this}; std::ranges::for_each(std::views::iota(0uz, count), [&](auto i) { m_storage.construct(i, value); ++m_size; @@ -344,7 +345,7 @@ namespace kstd template constexpr ring_buffer(InputIterator first, InputIterator last) { - auto guard = construction_guard{*this}; + auto guard = bits::construction_guard{this}; if constexpr (Capacity > 0) { for (; first != last && m_size < capacity(); ++first) @@ -379,7 +380,7 @@ namespace kstd if constexpr (Capacity > 0) { - auto guard = construction_guard{*this}; + auto guard = bits::construction_guard{this}; std::ranges::for_each(first, last, [this](auto const & element) { this->push_back(element); }); guard.disarm(); } @@ -403,7 +404,7 @@ namespace kstd if constexpr (Capacity > 0) { - auto guard = construction_guard{*this}; + auto guard = bits::construction_guard{this}; std::ranges::for_each(std::forward(range), [this](auto && element) { this->push_back(std::forward(element)); }); guard.disarm(); @@ -928,39 +929,6 @@ namespace kstd //! @} private: - //! An RAII guard to ensure partially constructed buffers are properly cleaned up. - struct construction_guard - { - //! Construct a new construction guard for the given ring buffer. - constexpr explicit construction_guard(ring_buffer & buf) - : m_buffer{&buf} - {} - - constexpr construction_guard(construction_guard const &) = delete; - constexpr construction_guard(construction_guard &&) = delete; - - //! Destroy the construction guard, clearing the buffer if it is still engaged. - constexpr ~construction_guard() - { - if (m_buffer) - { - m_buffer->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 buffer. - constexpr auto disarm() noexcept -> void - { - m_buffer = nullptr; - } - - private: - ring_buffer * m_buffer; - }; - //! Get a pointer to the element at the given read-index relative position. //! //! @param position The logical (read-index relative) index of the element. -- cgit v1.2.3 From 6c864832f111c085d28cd30ae96039670ef44c59 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 5 Oct 2026 16:25:07 +0200 Subject: kstd: ring_buffer: add more zero-capacity tests --- libs/kstd/kstd/ring_buffer.tests.cpp | 47 ++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) diff --git a/libs/kstd/kstd/ring_buffer.tests.cpp b/libs/kstd/kstd/ring_buffer.tests.cpp index 2517ff7b..54120b99 100644 --- a/libs/kstd/kstd/ring_buffer.tests.cpp +++ b/libs/kstd/kstd/ring_buffer.tests.cpp @@ -2434,6 +2434,53 @@ SCENARIO("Ring Buffer zero capacity", "[kstd][ring_buffer]") } } + 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{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 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{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{}; + auto buffer = kstd::ring_buffer{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{1}; + REQUIRE_THROWS_MATCHES( + (kstd::ring_buffer{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{}; -- cgit v1.2.3