based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING |
commitee7b197b5a4abba63b6711bdb6d5babe33adfe35
parentfc616cd767a03229610ed8cff873e07a0cd828ac
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateFri, 21 Mar 2025 15:11:26 +0100

Add list_pool

Diffstat:
Mexample/CMakeLists.txt|+
Aexample/list.cpp|+++++++++++++++++++++
Ainclude/based/list.hpp|+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 105 insertions(+), 0 deletions(-)

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

@@ -22,5 +22,6 @@ endfunction()

add_example(instrumentation)
add_example(algorithm)
add_example(list)
add_folders(Example)

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

@@ -0,0 +1,21 @@

#include <cstdint>
#include "based/list.hpp"
#include "based/instrumentation.hpp"
int main()
{
using instrumented = based::instrumented<double>;
based::list_pool<instrumented, std::uint8_t> pool;
auto head = pool.empty();
for (std::size_t i = 0; i < 0xFF; i++) {
head = pool.allocate(static_cast<double>(i), head);
}
based::free_list(pool, head);
return 0;
}

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

@@ -0,0 +1,83 @@

#pragma once
#include <vector>
namespace based
{
template<typename T, typename N>
// T semiregular
// N integral
class list_pool
{
public:
using value_type = T;
using list_type = N;
private:
struct node_t
{
value_type value;
list_type next = list_type(0);
};
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]; }
list_type new_node()
{
m_pool.push_back(node_t());
return list_type(m_pool.size());
}
public:
list_pool()
: m_free_list(empty())
{
}
const value_type& value(list_type x) const { return node(x).value; }
value_type& value(list_type x) { return node(x).value; }
const list_type& next(list_type x) const { return node(x).next; }
list_type& next(list_type x) { return node(x).next; }
list_type free(list_type x)
{
const list_type ret = next(x);
next(x) = m_free_list;
m_free_list = x;
return ret;
}
list_type allocate(const value_type& val, list_type tail)
{
list_type new_list = m_free_list;
if (is_empty(new_list)) {
new_list = new_node();
} else {
m_free_list = next(m_free_list);
}
value(new_list) = val;
next(new_list) = tail;
return new_list;
}
bool is_empty(list_type x) const { return x == empty(); }
list_type empty() const { return list_type(0); }
};
template<typename T, typename N>
void free_list(list_pool<T, N>& pool, typename list_pool<T, N>::list_type x)
{
while (!pool.is_empty(x)) {
x = pool.free(x);
}
}
} // namespace based