Loading...
Searching...
No Matches
hlist
// vi:set ft=cpp: -*- Mode: C++ -*-
/*
* (c) 2011 Alexander Warg <warg@os.inf.tu-dresden.de>
* economic rights: Technische Universität Dresden (Germany)
*
* License: see LICENSE.spdx (in this directory or the directories above)
*/
#pragma once
#include "bits/list_basics.h"
#include "type_traits"
namespace cxx {
template<typename ELEM_TYPE>
class H_list_item_t
{
public:
H_list_item_t() : _n(0), _pn(0) {}
~H_list_item_t() noexcept { l_remove(); }
private:
H_list_item_t(H_list_item_t const &) = delete;
template<typename T, typename P> friend class H_list;
template<typename T, typename X> friend struct Bits::Basic_list_policy;
void l_remove() noexcept
{
if (!_pn)
return;
*_pn = _n;
if (_n)
_n->_pn = _pn;
_pn = 0;
}
H_list_item_t *_n, **_pn;
};
typedef H_list_item_t<void> H_list_item;
template< typename T, typename POLICY = Bits::Basic_list_policy< T, H_list_item> >
class H_list : public Bits::Basic_list<POLICY>
{
private:
typedef typename POLICY::Item_type Item;
typedef Bits::Basic_list<POLICY> Base;
H_list(H_list const &);
void operator = (H_list const &);
public:
typedef typename Base::Iterator Iterator;
// BSS allocation
explicit H_list(bool x) : Base(x) {}
H_list() : Base() {}
static Iterator iter(T *c) { return Base::__iter(c->Item::_pn); }
static bool in_list(T const *e) { return e->Item::_pn; }
void add(T *e)
{
if (this->_f)
this->_f->_pn = &e->Item::_n;
e->Item::_n = this->_f;
e->Item::_pn = &this->_f;
this->_f = static_cast<Item*>(e);
}
void push_front(T *e) { add(e); }
T *pop_front()
{
T *r = this->front();
remove(r);
return r;
}
Iterator insert(T *e, Iterator const &pred)
{
Item **x = &this->_f;
if (pred != Base::end())
x = &(*pred)->_n;
e->Item::_n = *x;
if (*x)
(*x)->_pn = &(e->Item::_n);
e->Item::_pn = x;
*x = static_cast<Item*>(e);
return iter(e);
}
static Iterator insert_after(T *e, Iterator const &pred)
{
Item **x = &(*pred)->_n;
e->Item::_n = *x;
if (*x)
(*x)->_pn = &(e->Item::_n);
e->Item::_pn = x;
*x = static_cast<Item*>(e);
return iter(e);
}
static void insert_before(T *e, Iterator const &succ)
{
Item **x = Base::__get_internal(succ);
e->Item::_n = *x;
e->Item::_pn = x;
if (*x)
(*x)->_pn = &e->Item::_n;
*x = static_cast<Item*>(e);
}
static void replace(T *p, T *e)
{
e->Item::_n = p->Item::_n;
e->Item::_pn = p->Item::_pn;
*(p->Item::_pn) = static_cast<Item*>(e);
if (e->Item::_n)
e->Item::_n->_pn = &(e->Item::_n);
p->Item::_pn = 0;
}
static void remove(T *e)
{ e->Item::l_remove(); }
static Iterator erase(Iterator const &e)
{ e->Item::l_remove(); return e; }
};
template< typename T >
struct H_list_t : H_list<T, Bits::Basic_list_policy< T, H_list_item_t<T> > >
{
H_list_t() = default;
H_list_t(bool b)
: H_list<T, Bits::Basic_list_policy< T, H_list_item_t<T> > >(b)
{};
};
template< typename T >
class H_list_bss : public H_list<T>
{
public:
H_list_bss() : H_list<T>(true) {}
};
template< typename T >
class H_list_t_bss : public H_list_t<T>
{
public:
H_list_t_bss() : H_list_t<T>(true) {}
};
}
cxx::Bits::Basic_list
Internal: Common functions for all head-based list implementations.
Definition list_basics.h:40
cxx::Bits::Basic_list::end
Const_iterator end() const
Return a const iterator to the end of the list.
Definition list_basics.h:150
cxx::Bits::Basic_list::_f
POLICY::Head_type _f
Pointer to front of the list.
Definition list_basics.h:159
cxx::Bits::Basic_list::front
Value_type front() const
Return the first element in the list.
Definition list_basics.h:128
cxx::H_list_item_t
Basic element type for a double-linked H_list.
Definition hlist:23
cxx::H_list_item_t::H_list_item_t
H_list_item_t()
Constructor.
Definition hlist:30
cxx::H_list_item_t::~H_list_item_t
~H_list_item_t() noexcept
Destructor.
Definition hlist:37
cxx::H_list
General double-linked list of unspecified cxx::H_list_item elements.
Definition hlist:70
cxx::H_list::insert_after
static Iterator insert_after(T *e, Iterator const &pred)
Insert an element after the iterator position.
Definition hlist:160
cxx::H_list::pop_front
T * pop_front()
Remove and return the head element of the list.
Definition hlist:116
cxx::H_list::replace
static void replace(T *p, T *e)
Replace an element in a list with a new element.
Definition hlist:204
cxx::H_list::erase
static Iterator erase(Iterator const &e)
Remove the element at the given iterator position.
Definition hlist:236
cxx::H_list::insert_before
static void insert_before(T *e, Iterator const &succ)
Insert an element before the iterator position.
Definition hlist:180
cxx::H_list::add
void add(T *e)
Add element to the front of the list.
Definition hlist:99
cxx::H_list::insert
Iterator insert(T *e, Iterator const &pred)
Insert an element at the iterator position.
Definition hlist:133
cxx::H_list::remove
static void remove(T *e)
Remove the given element from its list.
Definition hlist:220
cxx::H_list::iter
static Iterator iter(T *c)
Return an iterator for an arbitrary list element.
Definition hlist:93
cxx::H_list::in_list
static bool in_list(T const *e)
Check if the given element is currently part of a list.
Definition hlist:96
cxx::H_list::push_front
void push_front(T *e)
Add element to the front of the list.
Definition hlist:109
cxx
Our C++ library.
Definition arith:11
cxx::H_list_item
H_list_item_t< void > H_list_item
Untyped list item.
Definition hlist:61
cxx::H_list_t
Double-linked list of typed H_list_item_t elements.
Definition hlist:249