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