l4/pkg/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 class 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 template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item > >
  44 class S_list : public Bits::Basic_list<POLICY>
  45 {
  46 private:
  47   S_list(S_list const &);
  48   void operator = (S_list const &);
  49
  50   typedef typename Bits::Basic_list<POLICY> Base;
  51
  52 public:
  53   typedef typename Base::Iterator Iterator;
  54
  55   // BSS allocation
  56   explicit S_list(bool x) : Base(x) {}
  57
  58   S_list() : Base() {}
  59
  60   void add(T *e)
  61   {
  62     e->_n = this->_f;
  63     this->_f = e;
  64   }
  65
  66   template< typename CAS >
  67   void add(T *e, CAS const &c)
  68   {
  69     do
  70       {
  71         e->_n = this->_f;
  72       }
  73     while (!c(&this->_f, e->_n, e));
  74   }
  75
  76   void push_front(T *e) { add(e); }
  77   T *pop_front()
  78   {
  79     T *r = this->front();
  80     if (this->_f)
  81       this->_f = this->_f->_n;
  82     return r;
  83   }
  84
  85   void insert(T *e, Iterator const &pred)
  86   {
  87     S_list_item *p = *pred;
  88     e->_n = p->_n;
  89     p->_n = e;
  90   }
  91
  92   static void insert_before(T *e, Iterator const &succ)
  93   {
  94     S_list_item **x = Base::__get_internal(succ);
  95
  96     e->_n = *x;
  97     *x = e;
  98   }
  99
 100   static void replace(Iterator const &p, T*e)
 101   {
 102     S_list_item **x = Base::__get_internal(p);
 103     e->_n = (*x)->_n;
 104     *x = e;
 105   }
 106
 107   static Iterator erase(Iterator const &e)
 108   {
 109     S_list_item **x = Base::__get_internal(e);
 110     *x = (*x)->_n;
 111     return e;
 112   }
 113
 114 };
 115
 116
 117 template< typename T >
 118 class S_list_bss : public S_list<T>
 119 {
 120 public:
 121   S_list_bss() : S_list<T>(true) {}
 122 };
 123
 124 template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item >  >
 125 class S_list_tail : public S_list<T, POLICY>
 126 {
 127 private:
 128   typedef S_list<T, POLICY> Base;
 129
 130 public:
 131   S_list_tail() : Base(), _tail(&this->_f) {}
 132
 133   void push_back(T *e)
 134   {
 135     e->_n = 0;
 136     *_tail = e;
 137     _tail = &e->_n;
 138   }
 139
 140   void clear()
 141   {
 142     Base::clear();
 143     _tail = &this->_f;
 144   }
 145
 146   void append(S_list_tail &o)
 147   {
 148     T *x = o.front();
 149     *_tail = x;
 150     if (x)
 151       _tail = o._tail;
 152     o.clear();
 153   }
 154
 155   void move_to(S_list_tail &t)
 156   { t._f = this->_f; t._tail = _tail; clear(); }
 157
 158 private:
 159   S_list_item **_tail;
 160 };
 161
 162 }