Loading...
Searching...
No Matches
slist
// 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"
namespace cxx {
class S_list_item
{
public:
S_list_item() : _n(0) {}
// BSS allocation
explicit S_list_item(bool) {}
private:
template<typename T, typename P> friend class S_list;
template<typename T, typename P> friend class S_list_tail;
template<typename T, typename X> friend struct Bits::Basic_list_policy;
S_list_item(S_list_item const &);
void operator = (S_list_item const &);
S_list_item *_n;
};
template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item > >
class S_list : public Bits::Basic_list<POLICY>
{
S_list(S_list const &) = delete;
void operator = (S_list const &) = delete;
private:
typedef typename Bits::Basic_list<POLICY> Base;
public:
typedef typename Base::Iterator Iterator;
S_list(S_list &&o) : Base(static_cast<Base&&>(o)) {}
S_list &operator = (S_list &&o)
{
Base::operator = (static_cast<Base&&>(o));
return *this;
}
// BSS allocation
explicit S_list(bool x) : Base(x) {}
S_list() : Base() {}
void add(T *e)
{
e->_n = this->_f;
this->_f = e;
}
template< typename CAS >
void add(T *e, CAS const &c)
{
do
{
e->_n = this->_f;
}
while (!c(&this->_f, e->_n, e));
}
void push_front(T *e) { add(e); }
T *pop_front()
{
T *r = this->front();
if (this->_f)
this->_f = this->_f->_n;
return r;
}
void insert(T *e, Iterator const &pred)
{
S_list_item *p = *pred;
e->_n = p->_n;
p->_n = e;
}
static void insert_before(T *e, Iterator const &succ)
{
S_list_item **x = Base::__get_internal(succ);
e->_n = *x;
*x = e;
}
static void replace(Iterator const &p, T*e)
{
S_list_item **x = Base::__get_internal(p);
e->_n = (*x)->_n;
*x = e;
}
static Iterator erase(Iterator const &e)
{
S_list_item **x = Base::__get_internal(e);
*x = (*x)->_n;
return e;
}
};
template< typename T >
class S_list_bss : public S_list<T>
{
public:
S_list_bss() : S_list<T>(true) {}
};
template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item > >
class S_list_tail : public S_list<T, POLICY>
{
private:
typedef S_list<T, POLICY> Base;
void add(T *e) = delete;
public:
using Iterator = typename Base::Iterator;
S_list_tail() : Base(), _tail(&this->_f) {}
S_list_tail(S_list_tail &&t)
: Base(static_cast<Base&&>(t)), _tail(t.empty() ? &this->_f : t._tail)
{
t._tail = &t._f;
}
S_list_tail &operator = (S_list_tail &&t)
{
if (&t == this)
return *this;
Base::operator = (static_cast<Base &&>(t));
_tail = t.empty() ? &this->_f : t._tail;
t._tail = &t._f;
return *this;
}
void push_front(T *e)
{
if (Base::empty())
_tail = &e->_n;
Base::push_front(e);
}
void push_back(T *e)
{
e->_n = 0;
*_tail = e;
_tail = &e->_n;
}
void clear()
{
Base::clear();
_tail = &this->_f;
}
void append(S_list_tail &o)
{
T *x = o.front();
*_tail = x;
if (x)
_tail = o._tail;
o.clear();
}
T *pop_front()
{
T *t = Base::pop_front();
if (t && Base::empty())
_tail = &this->_f;
return t;
}
private:
static void insert(T *e, Iterator const &pred);
static void insert_before(T *e, Iterator const &succ);
static void replace(Iterator const &p, T*e);
static Iterator erase(Iterator const &e);
private:
S_list_item **_tail;
};
}
cxx::Bits::Basic_list
Internal: Common functions for all head-based list implementations.
Definition list_basics.h:40
cxx::Bits::Basic_list< Bits::Basic_list_policy< T, S_list_item > >::empty
bool empty() const
Definition list_basics.h:126
cxx::Bits::Basic_list< Bits::Basic_list_policy< T, S_list_item > >::clear
void clear()
Definition list_basics.h:135
cxx::Bits::Basic_list::_f
POLICY::Head_type _f
Pointer to front of the list.
Definition list_basics.h:159
cxx::Bits::Basic_list< Bits::Basic_list_policy< T, S_list_item > >::front
Value_type front() const
Definition list_basics.h:128
cxx::S_list
Simple single-linked list.
Definition slist:41
cxx::S_list::add
void add(T *e)
Add an element to the front of the list.
Definition slist:65
cxx::S_list::push_front
void push_front(T *e)
Add an element to the front of the list.
Definition slist:82
cxx::S_list::pop_front
T * pop_front()
Remove and return the head element of the list.
Definition slist:89
cxx
Our C++ library.
Definition arith:11