Loading...
Searching...
No Matches
list
// vi:set ft=cpp: -*- Mode: C++ -*-
/*
* (c) 2008-2009 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 <l4/cxx/type_traits>
#include <l4/cxx/std_alloc>
#include <l4/cxx/std_ops>
namespace cxx {
/*
* Classes: List_item, List<D, Alloc>
*/
class List_item
{
public:
class Iter
{
public:
Iter(List_item *c, List_item *f) noexcept : _c(c), _f(f) {}
Iter(List_item *f = 0) noexcept : _c(f), _f(f) {}
List_item *operator * () const noexcept { return _c; }
List_item *operator -> () const noexcept { return _c; }
Iter &operator ++ () noexcept
{
if (!_f)
_c = 0;
else
_c = _c->get_next_item();
if (_c == _f)
_c = 0;
return *this;
}
Iter operator ++ (int) noexcept
{ Iter o = *this; operator ++ (); return o; }
Iter &operator -- () noexcept
{
if (!_f)
_c = 0;
else
_c = _c->get_prev_item();
if (_c == _f)
_c = 0;
return *this;
}
Iter operator -- (int) noexcept
{ Iter o = *this; operator -- (); return o; }
List_item *remove_me() noexcept
{
if (!_c)
return 0;
List_item *l = _c;
operator ++ ();
l->remove_me();
if (_f == l)
_f = _c;
return l;
}
private:
List_item *_c, *_f;
};
template< typename T, bool Poly = false>
class T_iter : public Iter
{
private:
static bool const P = !Conversion<const T*, const List_item *>::exists
|| Poly;
static List_item *cast_to_li(T *i, Int_to_type<true>) noexcept
{ return dynamic_cast<List_item*>(i); }
static List_item *cast_to_li(T *i, Int_to_type<false>) noexcept
{ return i; }
static T *cast_to_type(List_item *i, Int_to_type<true>) noexcept
{ return dynamic_cast<T*>(i); }
static T *cast_to_type(List_item *i, Int_to_type<false>) noexcept
{ return static_cast<T*>(i); }
public:
template< typename O >
explicit T_iter(T_iter<O> const &o) noexcept
: Iter(o) { dynamic_cast<T*>(*o); }
//TIter(CListItem *f) : Iter(f) {}
T_iter(T *f = 0) noexcept : Iter(cast_to_li(f, Int_to_type<P>())) {}
T_iter(T *c, T *f) noexcept
: Iter(cast_to_li(c, Int_to_type<P>()),
cast_to_li(f, Int_to_type<P>()))
{}
inline T *operator * () const noexcept
{ return cast_to_type(Iter::operator * (),Int_to_type<P>()); }
inline T *operator -> () const noexcept
{ return operator * (); }
T_iter<T, Poly> operator ++ (int) noexcept
{ T_iter<T, Poly> o = *this; Iter::operator ++ (); return o; }
T_iter<T, Poly> operator -- (int) noexcept
{ T_iter<T, Poly> o = *this; Iter::operator -- (); return o; }
T_iter<T, Poly> &operator ++ () noexcept
{ Iter::operator ++ (); return *this; }
T_iter<T, Poly> &operator -- () noexcept
{ Iter::operator -- (); return *this; }
inline T *remove_me() noexcept;
};
List_item() noexcept : _n(this), _p(this) {}
protected:
List_item(List_item const &) noexcept : _n(this), _p(this) {}
public:
List_item *get_prev_item() const noexcept { return _p; }
List_item *get_next_item() const noexcept { return _n; }
void insert_prev_item(List_item *p) noexcept
{
p->_p->_n = this;
List_item *pr = p->_p;
p->_p = _p;
_p->_n = p;
_p = pr;
}
void insert_next_item(List_item *p) noexcept
{
p->_p->_n = _n;
p->_p = this;
_n->_p = p;
_n = p;
}
void remove_me() noexcept
{
if (_p != this)
{
_p->_n = _n;
_n->_p = _p;
}
_p = _n = this;
}
template< typename C, typename N >
static inline C *push_back(C *head, N *p) noexcept;
template< typename C, typename N >
static inline C *push_front(C *head, N *p) noexcept;
template< typename C, typename N >
static inline C *remove(C *head, N *p) noexcept;
private:
List_item *_n, *_p;
};
/* IMPLEMENTATION -----------------------------------------------------------*/
template< typename C, typename N >
C *List_item::push_back(C *h, N *p) noexcept
{
if (!p)
return h;
if (!h)
return p;
h->insert_prev_item(p);
return h;
}
template< typename C, typename N >
C *List_item::push_front(C *h, N *p) noexcept
{
if (!p)
return h;
if (h)
h->insert_prev_item(p);
return p;
}
template< typename C, typename N >
C *List_item::remove(C *h, N *p) noexcept
{
if (!p)
return h;
if (!h)
return 0;
if (h == p)
{
if (p == p->_n)
h = 0;
else
h = static_cast<C*>(p->_n);
}
p->remove_me();
return h;
}
template< typename T, bool Poly >
inline
T *List_item::T_iter<T, Poly>::remove_me() noexcept
{ return cast_to_type(Iter::remove_me(), Int_to_type<P>()); }
template< typename T >
class T_list_item : public List_item
{
public:
T *next() const { return static_cast<T*>(List_item::get_next_item()); }
T *prev() const { return static_cast<T*>(List_item::get_prev_item()); }
};
template< typename LI >
class L_list
{
private:
LI *_h;
public:
L_list() : _h(0) {}
void push_front(LI *e) { _h = LI::push_front(_h, e); }
void push_back(LI *e) { _h = LI::push_back(_h, e); }
void insert_before(LI *e, LI *p)
{
p->insert_prev_item(e);
if (_h == p)
_h = e;
}
void insert_after(LI *e, LI *p) { p->insert_next_item(e); }
void remove(LI *e)
{ _h = LI::remove(_h, e); }
LI *head() const { return _h; }
};
template< typename D, template<typename A> class Alloc = New_allocator >
class List
{
private:
class E : public List_item
{
public:
E(D const &d) noexcept : data(d) {}
D data;
};
public:
class Node : private E
{};
typedef Alloc<Node> Node_alloc;
class Iter
{
private:
List_item::T_iter<E> _i;
public:
Iter(E *e) noexcept : _i(e) {}
D &operator * () const noexcept { return (*_i)->data; }
D &operator -> () const noexcept { return (*_i)->data; }
Iter operator ++ (int) noexcept
{ Iter o = *this; operator ++ (); return o; }
Iter operator -- (int) noexcept
{ Iter o = *this; operator -- (); return o; }
Iter &operator ++ () noexcept { ++_i; return *this; }
Iter &operator -- () noexcept { --_i; return *this; }
operator E* () const noexcept { return *_i; }
};
List(Alloc<Node> const &a = Alloc<Node>()) noexcept : _h(0), _l(0), _a(a) {}
void push_back(D const &d) noexcept
{
void *n = _a.alloc();
if (!n) return;
_h = E::push_back(_h, new (n) E(d));
++_l;
}
void push_front(D const &d) noexcept
{
void *n = _a.alloc();
if (!n) return;
_h = E::push_front(_h, new (n) E(d));
++_l;
}
void remove(Iter const &i) noexcept
{ E *e = i; _h = E::remove(_h, e); --_l; _a.free(e); }
unsigned long size() const noexcept { return _l; }
D const &operator [] (unsigned long idx) const noexcept
{ Iter i = _h; for (; idx && *i; ++i, --idx) { } return *i; }
D &operator [] (unsigned long idx) noexcept
{ Iter i = _h; for (; idx && *i; ++i, --idx) { } return *i; }
Iter items() noexcept { return Iter(_h); }
private:
E *_h;
unsigned _l;
Alloc<Node> _a;
};
};
cxx::List::Iter
Iterator.
Definition list:344
cxx::List_item::Iter::remove_me
List_item * remove_me() noexcept
Remove item pointed to by iterator, and return pointer to element.
Definition list:75
cxx::List_item::T_iter
Iterator for derived classes from ListItem.
Definition list:109
cxx::List_item
Basic list item.
Definition list:27
cxx::List_item::remove_me
void remove_me() noexcept
Remove this item from the list.
Definition list:187
cxx::List_item::remove
static C * remove(C *head, N *p) noexcept
Remove item from a list.
Definition list:258
cxx::List_item::push_front
static C * push_front(C *head, N *p) noexcept
Prepend item to a list.
Definition list:248
cxx::List_item::insert_next_item
void insert_next_item(List_item *p) noexcept
Insert item p after this item.
Definition list:178
cxx::List_item::insert_prev_item
void insert_prev_item(List_item *p) noexcept
Insert item p before this item.
Definition list:168
cxx::List_item::get_prev_item
List_item * get_prev_item() const noexcept
Get previous item.
Definition list:162
cxx::List_item::get_next_item
List_item * get_next_item() const noexcept
Get next item.
Definition list:165
cxx::List_item::push_back
static C * push_back(C *head, N *p) noexcept
Append item to a list.
Definition list:237
cxx::List
Doubly linked list, with internal allocation.
Definition list:324
cxx::List::remove
void remove(Iter const &i) noexcept
Remove element pointed to by the iterator.
Definition list:386
cxx::List::size
unsigned long size() const noexcept
Get the length of the list.
Definition list:390
cxx::List::push_front
void push_front(D const &d) noexcept
Add element at the beginning of the list.
Definition list:377
cxx::List::operator[]
D const & operator[](unsigned long idx) const noexcept
Random access.
Definition list:393
cxx::List::items
Iter items() noexcept
Get iterator for the list elements.
Definition list:401
cxx::List::push_back
void push_back(D const &d) noexcept
Add element at the end of the list.
Definition list:368
cxx::New_allocator
Standard allocator based on operator new () .
Definition std_alloc:57
cxx
Our C++ library.
Definition arith:11