L4Re - L4 Runtime Environment
hlist
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 #include "type_traits"
24 
25 namespace cxx {
26 
27 /**
28  * Basic element type for a double-linked H_list.
29  *
30  * \tparam ELEM_TYPE Base class of the list element.
31  */
32 template<typename ELEM_TYPE>
33 class H_list_item_t
34 {
35 public:
36  /**
37  * Constructor.
38  *
39  * Creates an element that is not in any list.
40  */
41  H_list_item_t() : _pn(0) {}
42  /**
43  * Destructor.
44  *
45  * Automatically removes the element from any list it still might be
46  * enchained in.
47  */
48  ~H_list_item_t() noexcept { l_remove(); }
49 
50 private:
51  H_list_item_t(H_list_item_t const &) = delete;
52 
53  template<typename T, typename P> friend class H_list;
54  template<typename T, typename X> friend struct Bits::Basic_list_policy;
55 
56  void l_remove() noexcept
57  {
58  if (!_pn)
59  return;
60 
61  *_pn = _n;
62  if (_n)
63  _n->_pn = _pn;
64 
65  _pn = 0;
66  }
67 
68  H_list_item_t *_n, **_pn;
69 };
70 
71 /** Untyped list item. */
72 typedef H_list_item_t<void> H_list_item;
73 
74 /**
75  * General double-linked list of unspecified cxx::H_list_item elements.
76  *
77  * Most of the time, you want to use H_list_t.
78  */
79 template< typename T, typename POLICY = Bits::Basic_list_policy< T, H_list_item> >
80 class H_list : public Bits::Basic_list<POLICY>
81 {
82 private:
83  typedef typename POLICY::Item_type Item;
84  typedef Bits::Basic_list<POLICY> Base;
85  H_list(H_list const &);
86  void operator = (H_list const &);
87 
88 public:
89  typedef typename Base::Iterator Iterator;
90 
91  // BSS allocation
92  explicit H_list(bool x) : Base(x) {}
93  H_list() : Base() {}
94 
95  /**
96  * Return an iterator for an arbitrary list element
97  *
98  * \param c List element to start the iteration.
99  *
100  * \return A mutable forward iterator.
101  *
102  * \pre The element must be in a list.
103  */
104  static Iterator iter(T *c) { return Base::__iter(c->Item::_pn); }
105 
106  /// Check if the given element is currently part of a list.
107  static bool in_list(T const *e) { return e->Item::_pn; }
108 
109  /// Add element to the front of the list.
110  void add(T *e)
111  {
112  if (this->_f)
113  this->_f->_pn = &e->Item::_n;
114  e->Item::_n = this->_f;
115  e->Item::_pn = &this->_f;
116  this->_f = static_cast<Item*>(e);
117  }
118 
119  /// Add element to the front of the list.
120  void push_front(T *e) { add(e); }
121 
122  /**
123  * Remove and return the head element of the list.
124  *
125  * \pre The list must not be empty or the behaviour will be undefined.
126  */
127  T *pop_front()
128  {
129  T *r = this->front();
130  remove(r);
131  return r;
132  }
133 
134  /**
135  * Insert an element at the iterator position.
136  *
137  * \param e New Element to be inserted
138  * \param pred Iterator pointing to the element after which the
139  * element will be inserted. If end() is given, the
140  * element will be inserted at the beginning of the queue.
141  *
142  * \return Iterator pointing to the newly inserted element.
143  */
144  Iterator insert(T *e, Iterator const &pred)
145  {
146  Item **x = &this->_f;
147  if (pred != Base::end())
148  x = &(*pred)->_n;
149 
150  e->Item::_n = *x;
151 
152  if (*x)
153  (*x)->_pn = &(e->Item::_n);
154 
155  e->Item::_pn = x;
156  *x = static_cast<Item*>(e);
157  return iter(e);
158  }
159 
160  /**
161  * Insert an element after the iterator position.
162  *
163  * \param e New element to be inserted.
164  * \param pred Iterator pointing to the element after which the
165  * element will be inserted. Must not be end().
166  *
167  * \return Iterator pointing to the newly inserted element.
168  *
169  * \pre The list must not be empty.
170  */
171  static Iterator insert_after(T *e, Iterator const &pred)
172  {
173  Item **x = &(*pred)->_n;
174  e->Item::_n = *x;
175 
176  if (*x)
177  (*x)->_pn = &(e->Item::_n);
178 
179  e->Item::_pn = x;
180  *x = static_cast<Item*>(e);
181  return iter(e);
182  }
183 
184  /**
185  * Insert an element before the iterator position.
186  *
187  * \param e New element to be inserted.
188  * \param succ Iterator pointing to the element before which the
189  * element will be inserted. Must not be end().
190  */
191  static void insert_before(T *e, Iterator const &succ)
192  {
193  Item **x = Base::__get_internal(succ);
194 
195  e->Item::_n = *x;
196  e->Item::_pn = x;
197 
198  if (*x)
199  (*x)->_pn = &e->Item::_n;
200 
201  *x = static_cast<Item*>(e);
202  }
203 
204  /**
205  * Replace an element in a list with a new element.
206  *
207  * \param p Element in list to be replaced.
208  * \param e Replacement element, must not yet be in a list.
209  *
210  * \pre `p` and `e` must not be NULL.
211  *
212  * After the operation the p element is no longer in the
213  * list and may be reused.
214  */
215  static void replace(T *p, T *e)
216  {
217  e->Item::_n = p->Item::_n;
218  e->Item::_pn = p->Item::_pn;
219  *(p->Item::_pn) = static_cast<Item*>(e);
220  if (e->Item::_n)
221  e->Item::_n->_pn = &(e->Item::_n);
222 
223  p->Item::_pn = 0;
224  }
225 
226  /**
227  * Remove the given element from its list.
228  *
229  * \param e Element to be removed. Must be in a list.
230  */
231  static void remove(T *e)
232  { e->Item::l_remove(); }
233 
234  /**
235  * Remove the element at the given iterator position.
236  *
237  * \param e Iterator pointing to the element to be removed. Must not
238  * point to end().
239  *
240  * \return New iterator pointing to the element after the removed one.
241  *
242  * \note The hlist implementation guarantees that the original iterator
243  * is still valid after the element has been removed. In fact, the
244  * iterator returned is the same as the one supplied in the `e`
245  * parameter.
246  */
247  static Iterator erase(Iterator const &e)
248  { e->Item::l_remove(); return e; }
249 };
250 
251 /**
252  * Double-linked list of typed H_list_item_t elements.
253  *
254  * \note H_lists are not self-cleaning. Elements that are still chained
255  * during destruction are not removed and will therefore be in an
256  * undefined state after the destruction.
257  */
258 template< typename T >
259 struct H_list_t : H_list<T, Bits::Basic_list_policy< T, H_list_item_t<T> > >
260 {
261  H_list_t() = default;
262  H_list_t(bool b)
263  : H_list<T, Bits::Basic_list_policy< T, H_list_item_t<T> > >(b)
264  {};
265 };
266 
267 template< typename T >
268 class H_list_bss : public H_list<T>
269 {
270 public:
271  H_list_bss() : H_list<T>(true) {}
272 };
273 
274 template< typename T >
275 class H_list_t_bss : public H_list_t<T>
276 {
277 public:
278  H_list_t_bss() : H_list_t<T>(true) {}
279 };
280 
281 
282 }