aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--libs/kstd/kstd/ring_buffer.hpp41
-rw-r--r--libs/kstd/kstd/ring_buffer.tests.cpp296
-rw-r--r--libs/kstd/kstd/test_support/test_types.hpp192
3 files changed, 529 insertions, 0 deletions
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<std::input_iterator InputIterator>
+ 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<std::forward_iterator ForwardIterator>
+ constexpr ring_buffer(ForwardIterator first, ForwardIterator last)
+ {
+ auto const number_of_source_elements = static_cast<size_type>(std::ranges::distance(first, last));
+ if (number_of_source_elements > capacity())
+ {
+ os::panic("[KSTD] Tried to construct a ring buffer with more elements than it can support.");
+ }
+
+ 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 <catch2/matchers/catch_matchers_range_equals.hpp>
#include <algorithm>
+#include <array>
#include <cstddef>
+#include <forward_list>
#include <functional>
#include <iterator>
#include <memory>
@@ -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<int, 3> source{1, 2, 3};
+ auto first = kstd::tests::test_input_iterator{source.data(), source.size()};
+ auto last = kstd::tests::test_input_iterator{};
+
+ WHEN("constructing from the range")
+ {
+ auto buffer = kstd::ring_buffer<int, 5>{first, last};
+
+ THEN("the buffer contains the elements of the range in order")
+ {
+ REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3}));
+ }
+ }
+ }
+
+ GIVEN("A single-pass input range with exactly as many elements as the capacity")
+ {
+ std::array<int, 3> source{1, 2, 3};
+ auto first = kstd::tests::test_input_iterator{source.data(), source.size()};
+ auto last = kstd::tests::test_input_iterator{};
+
+ WHEN("constructing from the range")
+ {
+ auto buffer = kstd::ring_buffer<int, 3>{first, last};
+
+ THEN("the buffer is full and contains the elements of the range in order")
+ {
+ REQUIRE(buffer.size() == buffer.capacity());
+ REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3}));
+ }
+ }
+ }
+
+ GIVEN("A single-pass input range with more elements than the capacity")
+ {
+ std::array<int, 5> source{1, 2, 3, 4, 5};
+ auto first = kstd::tests::test_input_iterator{source.data(), source.size()};
+ auto last = kstd::tests::test_input_iterator{};
+
+ WHEN("constructing from the range")
+ {
+ THEN("the constructor panics")
+ {
+ REQUIRE_THROWS_MATCHES((kstd::ring_buffer<int, 3>{first, last}), kstd::tests::os_panic,
+ Catch::Matchers::Message(
+ "[KSTD] Tried to construct a ring buffer with more elements than it can support."));
+ }
+ }
+ }
+
+ GIVEN("An empty input range")
+ {
+ auto first = kstd::tests::test_input_iterator{};
+ auto last = kstd::tests::test_input_iterator{};
+
+ WHEN("constructing from the range")
+ {
+ auto buffer = kstd::ring_buffer<int, 5>{first, last};
+
+ THEN("the buffer is empty")
+ {
+ REQUIRE(buffer.empty());
+ }
+ }
+ }
+
+ GIVEN("An input range of static operation trackers with more elements than the capacity")
+ {
+ std::array<kstd::tests::static_copy_move_tracker, 5> source{};
+ auto first =
+ kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{source.data(), source.size()};
+ auto last = kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{};
+
+ WHEN("constructing from the range")
+ {
+ THEN("the constructor panics without leaking the elements already moved into the buffer")
+ {
+ kstd::tests::static_copy_move_tracker::reset();
+ REQUIRE_THROWS_MATCHES((kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 3>{first, last}),
+ kstd::tests::os_panic,
+ Catch::Matchers::Message(
+ "[KSTD] Tried to construct a ring buffer with more elements than it can support."));
+ REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count ==
+ kstd::tests::static_copy_move_tracker::dtor_call_count);
+ }
+ }
+ }
+
+ GIVEN("An input range with more elements than the capacity, where dereferences are counted")
+ {
+ std::array<int, 10> source{};
+ std::size_t elements_touched = 0;
+ auto first = kstd::tests::counting_input_iterator{source.data(), source.size(), elements_touched};
+ auto last = kstd::tests::counting_input_iterator{};
+
+ WHEN("constructing from the range")
+ {
+ THEN("the constructor panics without dereferencing more elements than needed to detect the overflow")
+ {
+ REQUIRE_THROWS_MATCHES((kstd::ring_buffer<int, 3>{first, last}), kstd::tests::os_panic,
+ Catch::Matchers::Message(
+ "[KSTD] Tried to construct a ring buffer with more elements than it can support."));
+ REQUIRE(elements_touched == 3);
+ }
+ }
+ }
+
+ GIVEN("An input range of static operation trackers accessed through non-const references")
+ {
+ std::array<kstd::tests::static_copy_move_tracker, 3> source{};
+ auto first =
+ kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{source.data(), source.size()};
+ auto last = kstd::tests::mutable_input_iterator<kstd::tests::static_copy_move_tracker>{};
+
+ WHEN("constructing from the range")
+ {
+ kstd::tests::static_copy_move_tracker::reset();
+ auto buffer = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{first, last};
+
+ THEN("each element is moved into the buffer, not copied")
+ {
+ REQUIRE(buffer.size() == 3);
+ REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 3);
+ REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0);
+ }
+ }
+ }
+
+ GIVEN("An input range of static operation trackers accessed through const references")
+ {
+ std::array<kstd::tests::static_copy_move_tracker, 2> source{};
+ auto first = kstd::tests::const_input_iterator<kstd::tests::static_copy_move_tracker>{source.data(), source.size()};
+ auto last = kstd::tests::const_input_iterator<kstd::tests::static_copy_move_tracker>{};
+
+ WHEN("constructing from the range")
+ {
+ kstd::tests::static_copy_move_tracker::reset();
+ auto buffer = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{first, last};
+
+ THEN("each element is copied into the buffer, since it cannot be moved from a const source")
+ {
+ REQUIRE(buffer.size() == 2);
+ REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 2);
+ REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0);
+ }
+ }
+ }
+
+ GIVEN("An input range of a move-only value type")
+ {
+ std::array<kstd::tests::move_only_value, 2> source{kstd::tests::move_only_value{1},
+ kstd::tests::move_only_value{2}};
+ auto first = kstd::tests::mutable_input_iterator<kstd::tests::move_only_value>{source.data(), source.size()};
+ auto last = kstd::tests::mutable_input_iterator<kstd::tests::move_only_value>{};
+
+ WHEN("constructing from the range")
+ {
+ auto buffer = kstd::ring_buffer<kstd::tests::move_only_value, 5>{first, last};
+
+ THEN("the buffer contains the moved-from elements")
+ {
+ REQUIRE(buffer.size() == 2);
+ REQUIRE(buffer[0] == kstd::tests::move_only_value{1});
+ REQUIRE(buffer[1] == kstd::tests::move_only_value{2});
+ }
+ }
+ }
+
+ GIVEN("A forward range with fewer elements than the capacity")
+ {
+ auto source = std::forward_list<int>{1, 2, 3};
+
+ WHEN("constructing from the range")
+ {
+ auto buffer = kstd::ring_buffer<int, 5>{source.begin(), source.end()};
+
+ THEN("the buffer contains the elements of the range in order")
+ {
+ REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3}));
+ }
+ }
+ }
+
+ GIVEN("A forward range with exactly as many elements as the capacity")
+ {
+ auto source = std::forward_list<int>{1, 2, 3};
+
+ WHEN("constructing from the range")
+ {
+ auto buffer = kstd::ring_buffer<int, 3>{source.begin(), source.end()};
+
+ THEN("the buffer is full and contains the elements of the range in order")
+ {
+ REQUIRE(buffer.size() == buffer.capacity());
+ REQUIRE_THAT(buffer, Catch::Matchers::RangeEquals({1, 2, 3}));
+ }
+ }
+ }
+
+ GIVEN("A forward range with more elements than the capacity")
+ {
+ auto source = std::forward_list<int>{1, 2, 3, 4, 5};
+
+ WHEN("constructing from the range")
+ {
+ THEN("the constructor panics")
+ {
+ REQUIRE_THROWS_MATCHES((kstd::ring_buffer<int, 3>{source.begin(), source.end()}), kstd::tests::os_panic,
+ Catch::Matchers::Message(
+ "[KSTD] Tried to construct a ring buffer with more elements than it can support."));
+ }
+ }
+ }
+
+ GIVEN("An empty forward range")
+ {
+ auto source = std::forward_list<int>{};
+
+ WHEN("constructing from the range")
+ {
+ auto buffer = kstd::ring_buffer<int, 5>{source.begin(), source.end()};
+
+ THEN("the buffer is empty")
+ {
+ REQUIRE(buffer.empty());
+ }
+ }
+ }
+
+ GIVEN("A forward range of static operation trackers with more elements than the capacity")
+ {
+ auto source = std::forward_list<kstd::tests::static_copy_move_tracker>{};
+ source.emplace_front();
+ source.emplace_front();
+ source.emplace_front();
+ source.emplace_front();
+ source.emplace_front();
+
+ WHEN("constructing from the range")
+ {
+ THEN("the constructor panics without touching storage")
+ {
+ kstd::tests::static_copy_move_tracker::reset();
+ REQUIRE_THROWS_MATCHES(
+ (kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 3>{source.begin(), source.end()}),
+ kstd::tests::os_panic,
+ Catch::Matchers::Message(
+ "[KSTD] Tried to construct a ring buffer with more elements than it can support."));
+ REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 0);
+ REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0);
+ }
+ }
+ }
+
+ GIVEN("A forward range of static operation trackers that fits within the capacity")
+ {
+ auto source = std::forward_list<kstd::tests::static_copy_move_tracker>{};
+ source.emplace_front();
+ source.emplace_front();
+
+ WHEN("constructing from the range")
+ {
+ kstd::tests::static_copy_move_tracker::reset();
+ auto buffer = kstd::ring_buffer<kstd::tests::static_copy_move_tracker, 5>{source.begin(), source.end()};
+
+ THEN("each element is copied, not moved")
+ {
+ REQUIRE(buffer.size() == 2);
+ REQUIRE(kstd::tests::static_copy_move_tracker::copy_ctor_call_count == 2);
+ REQUIRE(kstd::tests::static_copy_move_tracker::move_ctor_call_count == 0);
+ }
+ }
+ }
+
+ GIVEN("A forward range used to construct two ring buffers in succession")
+ {
+ auto source = std::forward_list<int>{7, 8, 10};
+
+ WHEN("constructing both buffers from the same range")
+ {
+ auto first_buffer = kstd::ring_buffer<int, 5>{source.begin(), source.end()};
+ auto second_buffer = kstd::ring_buffer<int, 5>{source.begin(), source.end()};
+
+ THEN("both buffers contain the same elements and the source range is left untouched")
+ {
+ REQUIRE_THAT(first_buffer, Catch::Matchers::RangeEquals({7, 8, 10}));
+ REQUIRE_THAT(second_buffer, Catch::Matchers::RangeEquals({7, 8, 10}));
+ REQUIRE_THAT(source, Catch::Matchers::RangeEquals({7, 8, 10}));
+ }
+ }
+ }
}
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<typename ValueType>
+ struct mutable_input_iterator
+ {
+ using iterator_concept = std::input_iterator_tag;
+ using iterator_category = std::input_iterator_tag;
+ using difference_type = std::ptrdiff_t;
+ using value_type = ValueType;
+ using reference = ValueType &;
+ using pointer = ValueType *;
+
+ ValueType * current;
+ std::size_t count;
+
+ explicit mutable_input_iterator()
+ : current{nullptr}
+ , count{0}
+ {}
+
+ explicit mutable_input_iterator(ValueType * current, std::size_t count)
+ : current{current}
+ , count{count}
+ {}
+
+ [[nodiscard]] auto operator*() const -> ValueType &
+ {
+ return *current;
+ }
+
+ auto operator++() -> mutable_input_iterator &
+ {
+ ++current;
+ --count;
+ return *this;
+ }
+
+ auto operator++(int) -> void
+ {
+ ++*this;
+ }
+
+ [[nodiscard]] auto operator==(mutable_input_iterator const & other) const -> bool
+ {
+ if (current == nullptr && other.current == nullptr)
+ {
+ return true;
+ }
+
+ if (current == nullptr || other.current == nullptr)
+ {
+ return count == other.count;
+ }
+
+ return current == other.current && count == other.count;
+ }
+ };
+
+ //! A test input iterator that yields const references to its elements.
+ template<typename ValueType>
+ struct const_input_iterator
+ {
+ using iterator_concept = std::input_iterator_tag;
+ using iterator_category = std::input_iterator_tag;
+ using difference_type = std::ptrdiff_t;
+ using value_type = ValueType;
+ using reference = ValueType const &;
+ using pointer = ValueType const *;
+
+ ValueType const * current;
+ std::size_t count;
+
+ explicit const_input_iterator()
+ : current{nullptr}
+ , count{0}
+ {}
+
+ explicit const_input_iterator(ValueType const * current, std::size_t count)
+ : current{current}
+ , count{count}
+ {}
+
+ [[nodiscard]] auto operator*() const -> ValueType const &
+ {
+ return *current;
+ }
+
+ auto operator++() -> const_input_iterator &
+ {
+ ++current;
+ --count;
+ return *this;
+ }
+
+ auto operator++(int) -> void
+ {
+ ++*this;
+ }
+
+ [[nodiscard]] auto operator==(const_input_iterator const & other) const -> bool
+ {
+ if (current == nullptr && other.current == nullptr)
+ {
+ return true;
+ }
+
+ if (current == nullptr || other.current == nullptr)
+ {
+ return count == other.count;
+ }
+
+ return current == other.current && count == other.count;
+ }
+ };
+
+ //! A single-pass input iterator that counts how many of its elements have actually been dereferenced.
+ struct counting_input_iterator
+ {
+ using iterator_concept = std::input_iterator_tag;
+ using iterator_category = std::input_iterator_tag;
+ using difference_type = std::ptrdiff_t;
+ using value_type = int;
+ using reference = int const &;
+ using pointer = int const *;
+
+ int const * current;
+ std::size_t count;
+ std::size_t * elements_touched;
+
+ explicit counting_input_iterator()
+ : current{nullptr}
+ , count{0}
+ , elements_touched{nullptr}
+ {}
+
+ explicit counting_input_iterator(int const * current, std::size_t count, std::size_t & elements_touched)
+ : current{current}
+ , count{count}
+ , elements_touched{&elements_touched}
+ {}
+
+ [[nodiscard]] auto operator*() const -> int
+ {
+ ++(*elements_touched);
+ return *current;
+ }
+
+ auto operator++() -> counting_input_iterator &
+ {
+ ++current;
+ --count;
+ return *this;
+ }
+
+ auto operator++(int) -> void
+ {
+ ++*this;
+ }
+
+ [[nodiscard]] auto operator==(counting_input_iterator const & other) const -> bool
+ {
+ if (current == nullptr && other.current == nullptr)
+ {
+ return true;
+ }
+
+ if (current == nullptr || other.current == nullptr)
+ {
+ return count == other.count;
+ }
+
+ return current == other.current && count == other.count;
+ }
+ };
+
} // namespace kstd::tests
#endif
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-10 23:56:57 +0000