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