based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | LICENSE | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit 430b25f434f63656e1b5353e78c4648ab5335ed3
parent 534a0c41aed42c7a6167bf400fc1b39698b8ec0c
author Dimitrije Dobrota < mail@dimitrijedobrota.com >
date Mon, 28 Apr 2025 19:16:57 +0200

list_pool::const_iterator and more tests

Diffstat:
M include/based/list.hpp | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ----
M test/source/list_test.cpp | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ------

2 files changed, 126 insertions(+), 10 deletions(-)

diff --git a/ include/based/list.hpp b/ include/based/list.hpp

@@ -1,7 +1,6 @@

#pragma once

#include <cassert>
#include <functional>
#include <utility>
#include <vector>

@@ -104,13 +103,72 @@ public:

list_pool::list_type m_node;
};

struct const_iterator
{
using iterator_category = std::forward_iterator_tag;
using difference_type = list_pool::list_type;
using value_type = list_pool::value_type;
using reference = const value_type&;
using pointer = const value_type*;

const_iterator() = default;

explicit const_iterator(const list_pool& pool)
: const_iterator(pool, pool.node_empty())
{
}

const_iterator(const list_pool& pool, list_pool::list_type node)
: m_pool(&pool)
, m_node(node)
{
}

reference operator*() const { return m_pool->value(m_node); }
pointer operator->() const { return &**this; }

const_iterator& operator++()
{
m_node = m_pool->next(m_node);
return *this;
}

const_iterator operator++(int)
{
const_iterator tmp(*this);
++*this;
return tmp;
}

friend bool operator==(const const_iterator& x, const const_iterator& y)
{
assert(x.m_pool == y.m_pool);
return x.m_node == y.m_node;
}

friend bool operator!=(const const_iterator& x, const const_iterator& y)
{
return !(x == y);
}

private:
const list_pool* m_pool;
list_pool::list_type m_node;
};

[[nodiscard]] bool is_empty(list_type x) const { return x == node_empty(); }
[[nodiscard]] list_type node_empty() const { return list_type(0); }

[[nodiscard]] const value_type& value(list_type x) const { return node(x).value; }
[[nodiscard]] const value_type& value(list_type x) const
{
return node(x).value;
}
[[nodiscard]] value_type& value(list_type x) { return node(x).value; }

[[nodiscard]] const list_type& next(list_type x) const { return node(x).next; }
[[nodiscard]] const list_type& next(list_type x) const
{
return node(x).next;
}
[[nodiscard]] list_type& next(list_type x) { return node(x).next; }

list_type free(list_type x)

@@ -153,7 +211,10 @@ public:


using queue_t = std::pair<list_type, list_type>;

[[nodiscard]] bool is_empty(const queue_t& queue) const { return is_empty(queue.first); }
[[nodiscard]] bool is_empty(const queue_t& queue) const
{
return is_empty(queue.first);
}
[[nodiscard]] queue_t queue_empty() { return {node_empty(), node_empty()}; }

[[nodiscard]] queue_t push_front(const queue_t& queue, const value_type& val)

diff --git a/ test/source/list_test.cpp b/ test/source/list_test.cpp

@@ -4,6 +4,8 @@


#include <catch2/catch_test_macros.hpp>

template class based::list_pool<std::uint8_t, std::uint8_t>;

TEST_CASE("list_pool", "[list/list_pool]")
{
using list_pool = based::list_pool<std::uint8_t, std::uint8_t>;

@@ -58,10 +60,9 @@ TEST_CASE("list_pool", "[list/list_pool]")

REQUIRE(pool.node_empty() == head);
}

TEST_CASE("list_pool iterator", "[list/list_pool/iterator]")
TEST_CASE("list_pool iterator", "[list/list_pool]")
{
using list_pool = based::list_pool<std::uint8_t, std::uint8_t>;
using iter = list_pool::iterator;

auto pool = list_pool();
auto head = pool.node_empty();

@@ -73,20 +74,25 @@ TEST_CASE("list_pool iterator", "[list/list_pool/iterator]")


SECTION("for-loop")
{
std::uint64_t sum = 0;
for (auto it = iter(pool, head); it != iter(pool); ++it) {
using iter = list_pool::iterator;

std::uint32_t sum = 0;
for (auto it = iter(pool, head); it != iter(pool); it++) {
sum += *it.operator->();
sum += *it;
}

REQUIRE(sum == 0xFF * 0xFE / 2);
REQUIRE(sum == 0xFF * 0xFE);
}

SECTION("accumulate")
{
using iter = list_pool::iterator;

const auto sum = std::accumulate(
iter(pool, head),
iter(pool),
std::uint64_t {0},
std::uint32_t {0},
[](auto a, auto b)
{
return a + b;

@@ -99,6 +105,55 @@ TEST_CASE("list_pool iterator", "[list/list_pool/iterator]")

based::free_list(pool, head);
}

TEST_CASE("list_pool const iterator", "[list/list_pool]")
{
using list_pool = based::list_pool<std::uint8_t, std::uint8_t>;

auto pool = list_pool();
auto head = pool.node_empty();

static constexpr std::size_t iter_count = 0xFF;
for (std::uint8_t i = 0; i < iter_count; i++) {
head = pool.allocate(i, head);
}

SECTION("const for-loop")
{
using iter = list_pool::const_iterator;

std::uint32_t sum = 0;
for (auto it = iter(pool, head); it != iter(pool); it++) {
sum += *it.operator->();
sum += *it;
}

REQUIRE(sum == 0xFF * 0xFE);
}

SECTION("const accumulate")
{
using iter = list_pool::const_iterator;

static const auto sum =
[](const list_pool& lpool, const list_pool::list_type& lhead)
{
return std::accumulate(
iter(lpool, lhead),
iter(lpool),
std::uint32_t {0},
[](auto a, auto b)
{
return a + b;
}
);
};

REQUIRE(sum(pool, head) == 0xFF * 0xFE / 2);
}

based::free_list(pool, head);
}

TEST_CASE("list_pool queue", "[list/list_pool/queue]")
{
using list_pool = based::list_pool<std::uint8_t, std::uint8_t>;