General Purpose library for Freestanding C++ and POSIX systems
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

157 lines
3.0 KiB

#pragma once
#include "gp_config.hpp"
#include "gp/functional/bind_front.hpp"
#include "gp/algorithms/tmp_manip.hpp"
#include "gp/utils/allocators/allocator.hpp"
#include "gp/utils/allocators/dummy.hpp"
#include <stddef.h>
namespace gp {
template<typename T, bool may_contain_self = false>
class ring_list{
public:
class explorer;
class node {
T* value;
node* prev;
node* next;
public:
node(T* p)
: value{p}
, prev{this}
, next{this}
{}
friend class gp::ring_list<T, may_contain_self>::explorer;
friend class gp::ring_list<T, may_contain_self>;
};
class explorer {
node* pos;
public:
explorer(node* v)
: pos{v}
{}
bool operator==(const explorer& oth) const {
return pos == oth.pos;
}
bool operator!=(const explorer& oth) const {
return pos != oth.pos;
}
explorer operator++() {
pos = pos->next;
return pos;
}
explorer operator++(int) {
auto tmp = pos;
pos = pos->next;
return tmp;
}
explorer operator--() {
pos = pos->prev;
return pos;
}
explorer operator--(int) {
auto tmp = pos;
pos = pos->prev;
return tmp;
}
T& operator*() {
return *(pos->value);
}
friend class ring_list;
};
private:
node* any_node;
size_t sz;
gp::reference_wrapper<allocator> alloc;
void stitch_around(node* n) {
n->prev->next = n->next;
n->next->prev = n->prev;
}
public:
ring_list(node* initial, allocator& _alloc)
: any_node{initial}
, sz{1}
, alloc{_alloc}
{}
ring_list(allocator& _alloc)
: any_node{nullptr}
, sz{0}
, alloc{_alloc}
{}
template<typename V = T, typename ...Args>
bool insert(Args&&... elem) {
allocator& used_allocator = alloc;
void* mem;
[[unlikely]] if(
nullptr == (mem = used_allocator.allocate(sizeof(V)))
) return false;
T* p = new(mem) V(elem...);
node* to_insert = nullptr;
[[unlikely]] if(
nullptr == (to_insert = reinterpret_cast<node*>(used_allocator.allocate(sizeof(node))))
) return false;
to_insert = new(to_insert) node(p);
[[unlikely]] if (any_node == nullptr)
{
any_node = to_insert;
} else {
to_insert->prev = any_node->prev;
to_insert->next = any_node;
to_insert->prev->next = to_insert;
any_node->prev = to_insert;
}
return true;
}
explorer explore() {
return any_node;
}
void remove(explorer value) {
allocator& used_allocator = alloc;
auto v = value.pos;
if(v == any_node) {
if(v->next == v) {
any_node = nullptr;
} else {
any_node = any_node->next;
stitch_around(v);
}
} else {
stitch_around(v);
}
v->value->~T();
gp_config::assertion(used_allocator.deallocate(v->value), "Bad free of value");
v->~node();
gp_config::assertion(used_allocator.deallocate(v), "Bad free of node");
}
~ring_list()
{
// TODO: Find a less hackish way to resove this issue
if constexpr (!may_contain_self) {
while(any_node) {
remove(explore());
}
}
}
};
}