L4Re - L4 Runtime Environment
list
1 // vi:set ft=cpp: -*- Mode: C++ -*-
2 /*
3  * (c) 2008-2009 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 <l4/cxx/type_traits>
23 #include <l4/cxx/std_alloc>
24 #include <l4/cxx/std_ops>
25 
26 namespace cxx {
27 /*
28  * Classes: List_item, List<D, Alloc>
29  */
30 
31 /**
32  * \ingroup cxx_api
33  * \brief Basic list item.
34  *
35  * Basic item that can be member of a doubly linked, cyclic list.
36  */
37 class List_item
38 {
39 public:
40  /**
41  * \brief Iterator for a list of ListItem-s.
42  *
43  * The Iterator iterates till it finds the first element again.
44  */
45  class Iter
46  {
47  public:
48  Iter(List_item *c, List_item *f) throw() : _c(c), _f(f) {}
49  Iter(List_item *f = 0) throw() : _c(f), _f(f) {}
50 
51  List_item *operator * () const throw() { return _c; }
52  List_item *operator -> () const throw() { return _c; }
53  Iter &operator ++ () throw()
54  {
55  if (!_f)
56  _c = 0;
57  else
58  _c = _c->get_next_item();
59 
60  if (_c == _f)
61  _c = 0;
62 
63  return *this;
64  }
65 
66  Iter operator ++ (int) throw()
67  { Iter o = *this; operator ++ (); return o; }
68 
69  Iter &operator -- () throw()
70  {
71  if (!_f)
72  _c = 0;
73  else
74  _c = _c->get_prev_item();
75 
76  if (_c == _f)
77  _c = 0;
78 
79  return *this;
80  }
81 
82  Iter operator -- (int) throw()
83  { Iter o = *this; operator -- (); return o; }
84 
85  /** Remove item pointed to by iterator, and return pointer to element. */
86  List_item *remove_me() throw()
87  {
88  if (!_c)
89  return 0;
90 
91  List_item *l = _c;
92  operator ++ ();
93  l->remove_me();
94 
95  if (_f == l)
96  _f = _c;
97 
98  return l;
99  }
100 
101  private:
102  List_item *_c, *_f;
103  };
104 
105  /**
106  * \brief Iterator for derived classes from ListItem.
107  *
108  * Allows direct access to derived classes by * operator.
109  *
110  * Example:
111  * class Foo : public ListItem
112  * {
113  * public:
114  * typedef T_iter<Foo> Iter;
115  * ...
116  * };
117  */
118  template< typename T, bool Poly = false>
119  class T_iter : public Iter
120  {
121  private:
122  static bool const P = !Conversion<const T*, const List_item *>::exists
123  || Poly;
124 
125  static List_item *cast_to_li(T *i, Int_to_type<true>) throw()
126  { return dynamic_cast<List_item*>(i); }
127 
128  static List_item *cast_to_li(T *i, Int_to_type<false>) throw()
129  { return i; }
130 
131  static T *cast_to_type(List_item *i, Int_to_type<true>) throw()
132  { return dynamic_cast<T*>(i); }
133 
134  static T *cast_to_type(List_item *i, Int_to_type<false>) throw()
135  { return static_cast<T*>(i); }
136 
137  public:
138 
139  template< typename O >
140  explicit T_iter(T_iter<O> const &o) throw()
141  : Iter(o) { dynamic_cast<T*>(*o); }
142 
143  //TIter(CListItem *f) : Iter(f) {}
144  T_iter(T *f = 0) throw() : Iter(cast_to_li(f, Int_to_type<P>())) {}
145  T_iter(T *c, T *f) throw()
146  : Iter(cast_to_li(c, Int_to_type<P>()),
147  cast_to_li(f, Int_to_type<P>()))
148  {}
149 
150  inline T *operator * () const throw()
151  { return cast_to_type(Iter::operator * (),Int_to_type<P>()); }
152  inline T *operator -> () const throw()
153  { return operator * (); }
154 
155  T_iter<T, Poly> operator ++ (int) throw()
156  { T_iter<T, Poly> o = *this; Iter::operator ++ (); return o; }
157  T_iter<T, Poly> operator -- (int) throw()
158  { T_iter<T, Poly> o = *this; Iter::operator -- (); return o; }
159  T_iter<T, Poly> &operator ++ () throw()
160  { Iter::operator ++ (); return *this; }
161  T_iter<T, Poly> &operator -- () throw()
162  { Iter::operator -- (); return *this; }
163  inline T *remove_me() throw();
164  };
165 
166  List_item() throw() : _n(this), _p(this) {}
167 
168 protected:
169  List_item(List_item const &) throw() : _n(this), _p(this) {}
170 
171 public:
172  /** Get previous item. */
173  List_item *get_prev_item() const throw() { return _p; }
174 
175  /** Get next item. */
176  List_item *get_next_item() const throw() { return _n; }
177 
178  /** Insert item p before this item. */
179  void insert_prev_item(List_item *p) throw()
180  {
181  p->_p->_n = this;
182  List_item *pr = p->_p;
183  p->_p = _p;
184  _p->_n = p;
185  _p = pr;
186  }
187 
188  /** Insert item p after this item. */
189  void insert_next_item(List_item *p) throw()
190  {
191  p->_p->_n = _n;
192  p->_p = this;
193  _n->_p = p;
194  _n = p;
195  }
196 
197  /** Remove this item from the list. */
198  void remove_me() throw()
199  {
200  if (_p != this)
201  {
202  _p->_n = _n;
203  _n->_p = _p;
204  }
205  _p = _n = this;
206  }
207 
208  /**
209  * \brief Append item to a list.
210  *
211  * Convenience function for empty-head corner case.
212  * \param head Pointer to the current list head.
213  * \param p Pointer to new item.
214  * \return the pointer to the new head.
215  */
216  template< typename C, typename N >
217  static inline C *push_back(C *head, N *p) throw();
218 
219  /**
220  * \brief Prepend item to a list.
221  *
222  * Convenience function for empty-head corner case.
223  * \param head pointer to the current list head.
224  * \param p pointer to new item.
225  * \return the pointer to the new head.
226  */
227  template< typename C, typename N >
228  static inline C *push_front(C *head, N *p) throw();
229 
230  /**
231  * \brief Remove item from a list.
232  *
233  * Convenience function for remove-head corner case.
234  * \param head pointer to the current list head.
235  * \param p pointer to the item to remove.
236  * \return the pointer to the new head.
237  */
238  template< typename C, typename N >
239  static inline C *remove(C *head, N *p) throw();
240 
241 private:
242  List_item *_n, *_p;
243 };
244 
245 
246 /* IMPLEMENTATION -----------------------------------------------------------*/
247 template< typename C, typename N >
248 C *List_item::push_back(C *h, N *p) throw()
249 {
250  if (!p)
251  return h;
252  if (!h)
253  return p;
254  h->insert_prev_item(p);
255  return h;
256 }
257 
258 template< typename C, typename N >
259 C *List_item::push_front(C *h, N *p) throw()
260 {
261  if (!p)
262  return h;
263  if (h)
264  h->insert_prev_item(p);
265  return p;
266 }
267 
268 template< typename C, typename N >
269 C *List_item::remove(C *h, N *p) throw()
270 {
271  if (!p)
272  return h;
273  if (!h)
274  return 0;
275  if (h == p)
276  {
277  if (p == p->_n)
278  h = 0;
279  else
280  h = static_cast<C*>(p->_n);
281  }
282  p->remove_me();
283 
284  return h;
285 }
286 
287 template< typename T, bool Poly >
288 inline
289 T *List_item::T_iter<T, Poly>::remove_me() throw()
290 { return cast_to_type(Iter::remove_me(), Int_to_type<P>()); }
291 
292 
293 template< typename T >
294 class T_list_item : public List_item
295 {
296 public:
297  T *next() const { return static_cast<T*>(List_item::get_next_item()); }
298  T *prev() const { return static_cast<T*>(List_item::get_prev_item()); }
299 };
300 
301 
302 template< typename LI >
303 class L_list
304 {
305 private:
306  LI *_h;
307 
308 public:
309 
310  L_list() : _h(0) {}
311 
312  void push_front(LI *e) { _h = LI::push_front(_h, e); }
313  void push_back(LI *e) { _h = LI::push_back(_h, e); }
314  void insert_before(LI *e, LI *p)
315  {
316  p->insert_prev_item(e);
317  if (_h == p)
318  _h = e;
319  }
320  void insert_after(LI *e, LI *p) { p->insert_next_item(e); }
321 
322  void remove(LI *e)
323  { _h = LI::remove(_h, e); }
324 
325  LI *head() const { return _h; }
326 };
327 
328 /**
329  * Doubly linked list, with internal allocation.
330  * Container for items of type D, implemented by a doubly linked list.
331  * Alloc defines the allocator policy.
332  */
333 template< typename D, template<typename A> class Alloc = New_allocator >
334 class List
335 {
336 private:
337  class E : public List_item
338  {
339  public:
340  E(D const &d) throw() : data(d) {}
341  D data;
342  };
343 
344 public:
345  class Node : private E
346  {};
347 
348  typedef Alloc<Node> Node_alloc;
349 
350  /**
351  * Iterator.
352  * Forward and backward iteratable.
353  */
354  class Iter
355  {
356  private:
357  List_item::T_iter<E> _i;
358 
359  public:
360  Iter(E *e) throw() : _i(e) {}
361 
362  D &operator * () const throw() { return (*_i)->data; }
363  D &operator -> () const throw() { return (*_i)->data; }
364 
365  Iter operator ++ (int) throw()
366  { Iter o = *this; operator ++ (); return o; }
367  Iter operator -- (int) throw()
368  { Iter o = *this; operator -- (); return o; }
369  Iter &operator ++ () throw() { ++_i; return *this; }
370  Iter &operator -- () throw() { --_i; return *this; }
371 
372  /** operator for testing validity (syntactically equal to pointers) */
373  operator E* () const throw() { return *_i; }
374  };
375 
376  List(Alloc<Node> const &a = Alloc<Node>()) throw() : _h(0), _l(0), _a(a) {}
377 
378  /** Add element at the end of the list. */
379  void push_back(D const &d) throw()
380  {
381  void *n = _a.alloc();
382  if (!n) return;
383  _h = E::push_back(_h, new (n) E(d));
384  ++_l;
385  }
386 
387  /** Add element at the beginning of the list. */
388  void push_front(D const &d) throw()
389  {
390  void *n = _a.alloc();
391  if (!n) return;
392  _h = E::push_front(_h, new (n) E(d));
393  ++_l;
394  }
395 
396  /** Remove element pointed to by the iterator. */
397  void remove(Iter const &i) throw()
398  { E *e = i; _h = E::remove(_h, e); --_l; _a.free(e); }
399 
400  /** Get the length of the list. */
401  unsigned long size() const throw() { return _l; }
402 
403  /** Random access. Complexity is O(n). */
404  D const &operator [] (unsigned long idx) const throw()
405  { Iter i = _h; for (; idx && *i; ++i, --idx) { } return *i; }
406 
407  /** Random access. Complexity is O(n). */
408  D &operator [] (unsigned long idx) throw()
409  { Iter i = _h; for (; idx && *i; ++i, --idx) { } return *i; }
410 
411  /** Get iterator for the list elements. */
412  Iter items() throw() { return Iter(_h); }
413 
414 private:
415  E *_h;
416  unsigned _l;
417  Alloc<Node> _a;
418 };
419 
420 
421 };
422