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)
 *
 * This file is part of TUD:OS and distributed under the terms of the
 * GNU General Public License 2.
 * Please see the COPYING-GPL-2 file for details.
 *
 * As a special exception, you may use this file as part of a free software
 * library without restriction.  Specifically, if other files instantiate
 * templates or use macros or inline functions from this file, or you compile
 * this file and link it with other files to produce an executable, this
 * file does not by itself cause the resulting executable to be covered by
 * the GNU General Public License.  This exception does not however
 * invalidate any other reasons why the executable file might be covered by
 * the GNU General Public License.
 */
 
#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;
};
 
 
};