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
25namespace 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 */
32template<typename ELEM_TYPE>
33class H_list_item_t
34{
35public:
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
50private:
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. */
72typedef 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 */
79template< typename T, typename POLICY = Bits::Basic_list_policy< T, H_list_item> >
80class H_list : public Bits::Basic_list<POLICY>
81{
82private:
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
88public:
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 */
258template< typename T >
259struct 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
267template< typename T >
268class H_list_bss : public H_list<T>
269{
270public:
271  H_list_bss() : H_list<T>(true) {}
272};
273
274template< typename T >
275class H_list_t_bss : public H_list_t<T>
276{
277public:
278  H_list_t_bss() : H_list_t<T>(true) {}
279};
280
281
282}
283