l4/pkg/l4re-core/cxx/lib/tl/include/slist

   1 // vi:ft=cpp
   2 /*
   3  * (c) 2011 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 "bits/list_basics.h"
  23
  24 namespace cxx {
  25
  26 class S_list_item
  27 {
  28 public:
  29   S_list_item() : _n(0) {}
  30   explicit S_list_item(bool) {}
  31
  32 private:
  33   template<typename T, typename P> friend class S_list;
  34   template<typename T, typename P> friend class S_list_tail;
  35   template<typename T, typename X> friend struct Bits::Basic_list_policy;
  36
  37   S_list_item(S_list_item const &);
  38   void operator = (S_list_item const &);
  39
  40   S_list_item *_n;
  41 };
  42
  43 /**
  44  * Simple single-linked list.
  45  *
  46  * \tparam T  Type of elements saved in the list. Must inherit from
  47  *            cxx::S_list_item
  48  */
  49 template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item > >
  50 class S_list : public Bits::Basic_list<POLICY>
  51 {
  52 private:
  53   S_list(S_list const &);
  54   void operator = (S_list const &);
  55
  56   typedef typename Bits::Basic_list<POLICY> Base;
  57
  58 public:
  59   typedef typename Base::Iterator Iterator;
  60
  61   // BSS allocation
  62   explicit S_list(bool x) : Base(x) {}
  63
  64   S_list() : Base() {}
  65
  66   /// Add an element to the front of the list.
  67   void add(T *e)
  68   {
  69     e->_n = this->_f;
  70     this->_f = e;
  71   }
  72
  73   template< typename CAS >
  74   void add(T *e, CAS const &c)
  75   {
  76     do
  77       {
  78         e->_n = this->_f;
  79       }
  80     while (!c(&this->_f, e->_n, e));
  81   }
  82
  83   /// Add an element to the front of the list.
  84   void push_front(T *e) { add(e); }
  85
  86   /**
  87    *  Remove and return the head element of the list.
  88    *
  89    *  \pre The list must not be empty or the behaviour will be undefined.
  90    */
  91   T *pop_front()
  92   {
  93     T *r = this->front();
  94     if (this->_f)
  95       this->_f = this->_f->_n;
  96     return r;
  97   }
  98
  99   void insert(T *e, Iterator const &pred)
 100   {
 101     S_list_item *p = *pred;
 102     e->_n = p->_n;
 103     p->_n = e;
 104   }
 105
 106   static void insert_before(T *e, Iterator const &succ)
 107   {
 108     S_list_item **x = Base::__get_internal(succ);
 109
 110     e->_n = *x;
 111     *x = e;
 112   }
 113
 114   static void replace(Iterator const &p, T*e)
 115   {
 116     S_list_item **x = Base::__get_internal(p);
 117     e->_n = (*x)->_n;
 118     *x = e;
 119   }
 120
 121   static Iterator erase(Iterator const &e)
 122   {
 123     S_list_item **x = Base::__get_internal(e);
 124     *x = (*x)->_n;
 125     return e;
 126   }
 127
 128 };
 129
 130
 131 template< typename T >
 132 class S_list_bss : public S_list<T>
 133 {
 134 public:
 135   S_list_bss() : S_list<T>(true) {}
 136 };
 137
 138 template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item >  >
 139 class S_list_tail : public S_list<T, POLICY>
 140 {
 141 private:
 142   typedef S_list<T, POLICY> Base;
 143
 144 public:
 145   S_list_tail() : Base(), _tail(&this->_f) {}
 146
 147   void push_back(T *e)
 148   {
 149     e->_n = 0;
 150     *_tail = e;
 151     _tail = &e->_n;
 152   }
 153
 154   void clear()
 155   {
 156     Base::clear();
 157     _tail = &this->_f;
 158   }
 159
 160   void append(S_list_tail &o)
 161   {
 162     T *x = o.front();
 163     *_tail = x;
 164     if (x)
 165       _tail = o._tail;
 166     o.clear();
 167   }
 168
 169   void move_to(S_list_tail &t)
 170   { t._f = this->_f; t._tail = _tail; clear(); }
 171
 172 private:
 173   S_list_item **_tail;
 174 };
 175
 176 }