based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | LICENSE | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit 7387b8bdd6f937ba2d48bf3878ddca9feba39b31
parent fdf5dc326745b5c66b5d075ce4fd7be4ab0494b2
author Dimitrije Dobrota < mail@dimitrijedobrota.com >
date Thu, 3 Apr 2025 21:41:09 +0200

Test list

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

3 files changed, 149 insertions(+), 2 deletions(-)

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

@@ -1,5 +1,6 @@

#pragma once

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

@@ -26,8 +27,17 @@ private:

std::vector<node_t> m_pool;
list_type m_free_list;

const node_t& node(list_type x) const { return m_pool[x - 1]; }
node_t& node(list_type x) { return m_pool[x - 1]; }
const node_t& node(list_type x) const
{
assert(x != 0);
return m_pool[x - 1];
}

node_t& node(list_type x)
{
assert(x != 0);
return m_pool[x - 1];
}

list_type new_node()
{

diff --git a/ test/CMakeLists.txt b/ test/CMakeLists.txt

@@ -28,6 +28,9 @@ add_test(max_test)

add_test(max_element_test)
add_test(minmax_element_test)

# ---- List ----
add_test(list_test)

# ---- End-of-file commands ----

add_folders(Test)

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

@@ -0,0 +1,134 @@

#include <numeric>

#include "based/list.hpp"

#include <catch2/catch_test_macros.hpp>

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

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

SECTION("node_empty is empty")
{
REQUIRE(pool.is_empty(head) == true);
REQUIRE(pool.node_empty() == head);
}

SECTION("add one node")
{
head = pool.allocate(1, head);

REQUIRE(pool.is_empty(head) == false);
REQUIRE(pool.value(head) == 1);

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

SECTION("add two nodes")
{
head = pool.allocate(2, head);

REQUIRE(pool.is_empty(head) == false);
REQUIRE(pool.value(head) == 2);

REQUIRE(pool.value(pool.next(head)) == 1);
REQUIRE(pool.next(pool.next(head)) == pool.node_empty());

head = pool.free(head);
}

SECTION("alloc after free")
{
head = pool.allocate(2, head);
head = pool.free(head);
head = pool.allocate(3, head);

REQUIRE(pool.is_empty(head) == false);
REQUIRE(pool.value(head) == 3);

head = pool.free(head);
}

head = pool.free(head);
}

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

TEST_CASE("list_pool iterator", "[list/list_pool/iterator]")
{
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();

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

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

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

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

REQUIRE(sum == 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>;
using iter = list_pool::iterator;

auto pool = list_pool();
auto queue = pool.queue_empty();

SECTION("free(empty, empty)")
{
REQUIRE(pool.free(queue.first, queue.second) == pool.node_empty());
}

SECTION("pop_front(empty)")
{
REQUIRE(pool.pop_front(queue) == queue);
}

for (std::uint8_t i = 0; i < 0xFF; i++) {
if (i % 2 == 0) {
queue = pool.push_front(queue, i);
} else {
queue = pool.push_back(queue, i);
}

if (i % 3 == 0) {
queue = pool.pop_front(queue);
}
}

std::uint64_t sum = 0;
for (auto it = iter(pool, queue.first); it != iter(pool); ++it) {
sum += *it;
}

pool.free(queue);

REQUIRE(sum == 21717);
}