L4Re - L4 Runtime Environment
slist
1 // vi:set ft=cpp: -*- Mode: C++ -*-
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 }