based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | LICENSE | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit a13de84d744796b68b61650b2a84d647993fc2dc
parent ee7b197b5a4abba63b6711bdb6d5babe33adfe35
author Dimitrije Dobrota < mail@dimitrijedobrota.com >
date Sat, 22 Mar 2025 17:07:12 +0100

Queue interface inside list_pool

Diffstat:
M example/list.cpp | ++++++++++++++++ -
M include/based/list.hpp | ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ---

2 files changed, 70 insertions(+), 4 deletions(-)

diff --git a/ example/list.cpp b/ example/list.cpp

@@ -9,7 +9,7 @@ int main()

using instrumented = based::instrumented<double>;

based::list_pool<instrumented, std::uint8_t> pool;
auto head = pool.empty();
auto head = pool.node_empty();

for (std::size_t i = 0; i < 0xFF; i++) {
head = pool.allocate(static_cast<double>(i), head);

@@ -17,5 +17,20 @@ int main()


based::free_list(pool, head);

auto queue = pool.queue_empty();
for (std::size_t i = 0; i < 0xFF; i++) {
if (i % 2 == 0) {
queue = pool.push_front(queue, static_cast<double>(i));
} else {
queue = pool.push_back(queue, static_cast<double>(i));
}

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

pool.free(queue);

return 0;
}

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

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

#pragma once

#include <utility>
#include <vector>

namespace based

@@ -35,10 +36,13 @@ private:


public:
list_pool()
: m_free_list(empty())
: m_free_list(node_empty())
{
}

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

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

@@ -53,6 +57,20 @@ public:

return ret;
}

list_type free(
list_type front, // NOLINT bugprone-easily-swappable-parameters
list_type back)
{
if (is_empty(front)) {
return node_empty();
}

const list_type ret = next(back);
next(back) = m_free_list;
m_free_list = front;
return ret;
}

list_type allocate(const value_type& val, list_type tail)
{
list_type new_list = m_free_list;

@@ -68,8 +86,41 @@ public:

return new_list;
}

bool is_empty(list_type x) const { return x == empty(); }
list_type empty() const { return list_type(0); }
using queue_t = std::pair<list_type, list_type>;

bool is_empty(const queue_t& que) const { return is_empty(que.first); }
queue_t queue_empty() { return {node_empty(), node_empty()}; }

queue_t push_front(const queue_t& que, const value_type& val)
{
auto new_node = allocate(val, que.first);
if (is_empty(que)) {
return {new_node, new_node};
}
return {new_node, que.second};
}

queue_t push_back(const queue_t& que, const value_type& val)
{
auto new_node = allocate(val, node_empty());
if (is_empty(que)) {
return {new_node, new_node};
}
next(que.second) = new_node;
return {new_node, new_node};
}

queue_t pop_front(const queue_t& que)
{
if (is_empty(que)) {
return que;
}
queue_t ret = {next(que.first), que.second};
free(que.first);
return ret;
}

void free(const queue_t& que) { free(que.first, que.second); }
};

template<typename T, typename N>