l4/pkg/cxx/lib/tl/include/list

   1 // vi:ft=cpp
   2 /*
   3  * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>
   4  *     economic rights: Technische Universität Dresden (Germany)
   5  *
   6  * This file is part of TUD:OS and distributed under the terms of the
   7  * GNU General Public License 2.
   8  * Please see the COPYING-GPL-2 file for details.
   9  *
  10  * As a special exception, you may use this file as part of a free software
  11  * library without restriction.  Specifically, if other files instantiate
  12  * templates or use macros or inline functions from this file, or you compile
  13  * this file and link it with other files to produce an executable, this
  14  * file does not by itself cause the resulting executable to be covered by
  15  * the GNU General Public License.  This exception does not however
  16  * invalidate any other reasons why the executable file might be covered by
  17  * the GNU General Public License.
  18  */
  19
  20 #pragma once
  21
  22 #include <l4/cxx/type_traits>
  23 #include <l4/cxx/std_alloc>
  24 #include <l4/cxx/std_ops>
  25
  26 namespace cxx {
  27 /*
  28  * Classes: List_item, List<D, Alloc>
  29  */
  30
  31 /**
  32  * \ingroup cxx_api
  33  * \brief Basic list item.
  34  *
  35  * Basic item that can be member of a doubly linked, cyclic list.
  36  */
  37 class List_item
  38 {
  39 public:
  40   /**
  41    * \brief Iterator for a list of ListItem-s.
  42    *
  43    * The Iterator iterates till it finds the first element again.
  44    */
  45   class Iter
  46   {
  47   public:
  48     Iter(List_item *c, List_item *f) throw() : _c(c), _f(f) {}
  49     Iter(List_item *f = 0) throw() : _c(f), _f(f) {}
  50
  51     List_item *operator * () const throw() { return _c; }
  52     List_item *operator -> () const throw() { return _c; }
  53     Iter &operator ++ () throw()
  54     {
  55       if (!_f)
  56         _c = 0;
  57       else
  58         _c = _c->get_next_item();
  59
  60       if (_c == _f)
  61         _c = 0;
  62
  63       return *this;
  64     }
  65
  66     Iter operator ++ (int) throw()
  67     { Iter o = *this; operator ++ (); return o; }
  68
  69     Iter &operator -- () throw()
  70     {
  71       if (!_f)
  72         _c = 0;
  73       else
  74         _c = _c->get_prev_item();
  75
  76       if (_c == _f)
  77         _c = 0;
  78
  79       return *this;
  80     }
  81
  82     Iter operator -- (int) throw()
  83     { Iter o = *this; operator -- (); return o; }
  84
  85     /** Remove item pointed to by iterator, and return pointer to element. */
  86     List_item *remove_me() throw()
  87     {
  88       if (!_c)
  89         return 0;
  90
  91       List_item *l = _c;
  92       operator ++ ();
  93       l->remove_me();
  94
  95       if (_f == l)
  96         _f = _c;
  97
  98       return l;
  99     }
 100
 101   private:
 102     List_item *_c, *_f;
 103   };
 104
 105   /**
 106    * \brief Iterator for derived classes from ListItem.
 107    *
 108    * Allows direct access to derived classes by * operator.
 109    *
 110    * Example:
 111    * class Foo : public ListItem
 112    * {
 113    * public:
 114    *   typedef T_iter<Foo> Iter;
 115    *   ...
 116    * };
 117    */
 118   template< typename T, bool Poly = false>
 119   class T_iter : public Iter
 120   {
 121   private:
 122     static bool const P = !Conversion<const T*, const List_item *>::exists
 123       || Poly;
 124
 125     static List_item *cast_to_li(T *i, Int_to_type<true>) throw()
 126     { return dynamic_cast<List_item*>(i); }
 127
 128     static List_item *cast_to_li(T *i, Int_to_type<false>) throw()
 129     { return i; }
 130
 131     static T *cast_to_type(List_item *i, Int_to_type<true>) throw()
 132     { return dynamic_cast<T*>(i); }
 133
 134     static T *cast_to_type(List_item *i, Int_to_type<false>) throw()
 135     { return static_cast<T*>(i); }
 136
 137   public:
 138
 139     template< typename O >
 140     explicit T_iter(T_iter<O> const &o) throw()
 141     : Iter(o) { dynamic_cast<T*>(*o); }
 142
 143     //TIter(CListItem *f) : Iter(f) {}
 144     T_iter(T *f = 0) throw() : Iter(cast_to_li(f, Int_to_type<P>())) {}
 145     T_iter(T *c, T *f) throw()
 146     : Iter(cast_to_li(c, Int_to_type<P>()),
 147         cast_to_li(f, Int_to_type<P>()))
 148     {}
 149
 150     inline T *operator * () const throw()
 151     { return cast_to_type(Iter::operator * (),Int_to_type<P>()); }
 152     inline T *operator -> () const throw()
 153     { return operator * (); }
 154
 155     T_iter<T, Poly> operator ++ (int) throw()
 156     { T_iter<T, Poly> o = *this; Iter::operator ++ (); return o; }
 157     T_iter<T, Poly> operator -- (int) throw()
 158     { T_iter<T, Poly> o = *this; Iter::operator -- (); return o; }
 159     T_iter<T, Poly> &operator ++ () throw()
 160     { Iter::operator ++ (); return *this; }
 161     T_iter<T, Poly> &operator -- () throw()
 162     { Iter::operator -- (); return *this; }
 163     inline T *remove_me() throw();
 164   };
 165
 166   List_item() throw() : _n(this), _p(this) {}
 167
 168 protected:
 169   List_item(List_item const &) throw() : _n(this), _p(this) {}
 170
 171 public:
 172   /** Get previous item. */
 173   List_item *get_prev_item() const throw() { return _p; }
 174
 175   /** Get next item. */
 176   List_item *get_next_item() const throw() { return _n; }
 177
 178   /** Insert item p before this item. */
 179   void insert_prev_item(List_item *p) throw()
 180   {
 181     p->_p->_n = this;
 182     List_item *pr = p->_p;
 183     p->_p = _p;
 184     _p->_n = p;
 185     _p = pr;
 186   }
 187
 188   /** Insert item p after this item. */
 189   void insert_next_item(List_item *p) throw()
 190   {
 191     p->_p->_n = _n;
 192     p->_p = this;
 193     _n->_p = p;
 194     _n = p;
 195   }
 196
 197   /** Remove this item from the list. */
 198   void remove_me() throw()
 199   {
 200     if (_p != this)
 201       {
 202         _p->_n = _n;
 203         _n->_p = _p;
 204       }
 205     _p = _n = this;
 206   }
 207
 208   /**
 209    * \brief Append item to a list.
 210    *
 211    * Convenience function for empty-head corner case.
 212    * \param h pointer to the current list head.
 213    * \param p pointer to new item.
 214    * \return the pointer to the new head.
 215    */
 216   template< typename C, typename N >
 217   static inline C *push_back(C *head, N *p) throw();
 218
 219   /**
 220    * \brief Prepend item to a list.
 221    *
 222    * Convenience function for empty-head corner case.
 223    * \param head pointer to the current list head.
 224    * \param p pointer to new item.
 225    * \return the pointer to the new head.
 226    */
 227   template< typename C, typename N >
 228   static inline C *push_front(C *head, N *p) throw();
 229
 230   /**
 231    * \brief Remove item from a list.
 232    *
 233    * Convenience function for remove-head corner case.
 234    * \param head pointer to the current list head.
 235    * \param p pointer to the item to remove.
 236    * \return the pointer to the new head.
 237    */
 238   template< typename C, typename N >
 239   static inline C *remove(C *head, N *p) throw();
 240
 241 private:
 242   List_item *_n, *_p;
 243 };
 244
 245
 246 /* IMPLEMENTATION -----------------------------------------------------------*/
 247 template< typename C, typename N >
 248 C *List_item::push_back(C *h, N *p) throw()
 249 {
 250   if (!p)
 251     return h;
 252   if (!h)
 253     return p;
 254   h->insert_prev_item(p);
 255   return h;
 256 }
 257
 258 template< typename C, typename N >
 259 C *List_item::push_front(C *h, N *p) throw()
 260 {
 261   if (!p)
 262     return h;
 263   if (h)
 264     h->insert_prev_item(p);
 265   return p;
 266 }
 267
 268 template< typename C, typename N >
 269 C *List_item::remove(C *h, N *p) throw()
 270 {
 271   if (!p)
 272     return h;
 273   if (!h)
 274     return 0;
 275   if (h == p)
 276     {
 277       if (p == p->_n)
 278         h = 0;
 279       else
 280         h = static_cast<C*>(p->_n);
 281     }
 282   p->remove_me();
 283
 284   return h;
 285 }
 286
 287 template< typename T, bool Poly >
 288 inline
 289 T *List_item::T_iter<T, Poly>::remove_me() throw()
 290 { return cast_to_type(Iter::remove_me(), Int_to_type<P>()); }
 291
 292
 293 template< typename T >
 294 class T_list_item : public List_item
 295 {
 296 public:
 297   T *next() const { return static_cast<T*>(List_item::get_next_item()); }
 298   T *prev() const { return static_cast<T*>(List_item::get_prev_item()); }
 299 };
 300
 301
 302 template< typename LI >
 303 class L_list
 304 {
 305 private:
 306   LI *_h;
 307
 308 public:
 309
 310   L_list() : _h(0) {}
 311
 312   void push_front(LI *e) { _h = LI::push_front(_h, e); }
 313   void push_back(LI *e) { _h = LI::push_back(_h, e); }
 314   void insert_before(LI *e, LI *p)
 315   {
 316     p->insert_prev_item(e);
 317     if (_h == p)
 318       _h = e;
 319   }
 320   void insert_after(LI *e, LI *p) { p->insert_next_item(e); }
 321
 322   void remove(LI *e)
 323   { _h = LI::remove(_h, e); }
 324
 325   LI *head() const { return _h; }
 326 };
 327
 328 /**
 329  * Doubly linked list, with internal allocation.
 330  * Container for items of type D, implemented by a doubly linked list.
 331  * Alloc defines the allocator policy.
 332  */
 333 template< typename D, template<typename A> class Alloc = New_allocator >
 334 class List
 335 {
 336 private:
 337   class E : public List_item
 338   {
 339   public:
 340     E(D const &d) throw() : data(d) {}
 341     D data;
 342   };
 343
 344 public:
 345   class Node : private E
 346   {};
 347
 348   typedef Alloc<Node> Node_alloc;
 349
 350   /**
 351    * Iterator.
 352    * Forward and backward iteratable.
 353    */
 354   class Iter
 355   {
 356   private:
 357     List_item::T_iter<E> _i;
 358
 359   public:
 360     Iter(E *e) throw() : _i(e) {}
 361
 362     D &operator * () const throw() { return (*_i)->data; }
 363     D &operator -> () const throw() { return (*_i)->data; }
 364
 365     Iter operator ++ (int) throw()
 366     { Iter o = *this; operator ++ (); return o; }
 367     Iter operator -- (int) throw()
 368     { Iter o = *this; operator -- (); return o; }
 369     Iter &operator ++ () throw() { ++_i; return *this; }
 370     Iter &operator -- () throw() { --_i; return *this; }
 371
 372     /** operator for testing validity (syntactically equal to pointers) */
 373     operator E* () const throw() { return *_i; }
 374   };
 375
 376   List(Alloc<Node> const &a = Alloc<Node>()) throw() : _h(0), _l(0), _a(a) {}
 377
 378   /** Add element at the end of the list. */
 379   void push_back(D const &d) throw()
 380   {
 381     void *n = _a.alloc();
 382     if (!n) return;
 383     _h = E::push_back(_h, new (n) E(d));
 384     ++_l;
 385   }
 386
 387   /** Add element at the beginning of the list. */
 388   void push_front(D const &d) throw()
 389   {
 390     void *n = _a.alloc();
 391     if (!n) return;
 392     _h = E::push_front(_h, new (n) E(d));
 393     ++_l;
 394   }
 395
 396   /** Remove element pointed to by the iterator. */
 397   void remove(Iter const &i) throw()
 398   { E *e = i; _h = E::remove(_h, e); --_l; _a.free(e); }
 399
 400   /** Get the length of the list. */
 401   unsigned long size() const throw() { return _l; }
 402
 403   /** Random access. Complexity is O(n). */
 404   D const &operator [] (unsigned long idx) const throw()
 405   { Iter i = _h; for (; idx && *i; ++i, --idx) ; return *i; }
 406
 407   /** Random access. Complexity is O(n). */
 408   D &operator [] (unsigned long idx) throw()
 409   { Iter i = _h; for (; idx && *i; ++i, --idx) ; return *i; }
 410
 411   /** Get iterator for the list elements. */
 412   Iter items() throw() { return Iter(_h); }
 413
 414 private:
 415   E *_h;
 416   unsigned _l;
 417   Alloc<Node> _a;
 418 };
 419
 420
 421 };
 422