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
26namespace 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 */
37class List_item
38{
39public:
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
168protected:
169  List_item(List_item const &) throw() : _n(this), _p(this) {}
170
171public:
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
241private:
242  List_item *_n, *_p;
243};
244
245
246/* IMPLEMENTATION -----------------------------------------------------------*/
247template< typename C, typename N >
248C *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
258template< typename C, typename N >
259C *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
268template< typename C, typename N >
269C *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
287template< typename T, bool Poly >
288inline
289T *List_item::T_iter<T, Poly>::remove_me() throw()
290{ return cast_to_type(Iter::remove_me(), Int_to_type<P>()); }
291
292
293template< typename T >
294class T_list_item : public List_item
295{
296public:
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
302template< typename LI >
303class L_list
304{
305private:
306  LI *_h;
307
308public:
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 */
333template< typename D, template<typename A> class Alloc = New_allocator >
334class List
335{
336private:
337  class E : public List_item
338  {
339  public:
340    E(D const &d) throw() : data(d) {}
341    D data;
342  };
343
344public:
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
414private:
415  E *_h;
416  unsigned _l;
417  Alloc<Node> _a;
418};
419
420
421};
422
423