L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
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
25namespace cxx {
26
32template<typename ELEM_TYPE>
34{
35public:
41 H_list_item_t() : _n(0), _pn(0) {}
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
73
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;
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
104 static Iterator iter(T *c) { return Base::__iter(c->Item::_pn); }
105
107 static bool in_list(T const *e) { return e->Item::_pn; }
108
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
120 void push_front(T *e) { add(e); }
121
128 {
129 T *r = this->front();
130 remove(r);
131 return r;
132 }
133
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
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
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
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
231 static void remove(T *e)
232 { e->Item::l_remove(); }
233
247 static Iterator erase(Iterator const &e)
248 { e->Item::l_remove(); return e; }
249};
250
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)
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}
Internal: Common functions for all head-based list implementations.
Definition list_basics.h:51
Const_iterator end() const
Return a const iterator to the end of the list.
POLICY::Head_type _f
Pointer to front of the list.
Value_type front() const
Return the first element in the list.
Basic element type for a double-linked H_list.
Definition hlist:34
H_list_item_t()
Constructor.
Definition hlist:41
~H_list_item_t() noexcept
Destructor.
Definition hlist:48
General double-linked list of unspecified cxx::H_list_item elements.
Definition hlist:81
static Iterator insert_after(T *e, Iterator const &pred)
Insert an element after the iterator position.
Definition hlist:171
T * pop_front()
Remove and return the head element of the list.
Definition hlist:127
static void replace(T *p, T *e)
Replace an element in a list with a new element.
Definition hlist:215
static Iterator erase(Iterator const &e)
Remove the element at the given iterator position.
Definition hlist:247
static void insert_before(T *e, Iterator const &succ)
Insert an element before the iterator position.
Definition hlist:191
void add(T *e)
Add element to the front of the list.
Definition hlist:110
Iterator insert(T *e, Iterator const &pred)
Insert an element at the iterator position.
Definition hlist:144
static void remove(T *e)
Remove the given element from its list.
Definition hlist:231
static Iterator iter(T *c)
Return an iterator for an arbitrary list element.
Definition hlist:104
static bool in_list(T const *e)
Check if the given element is currently part of a list.
Definition hlist:107
void push_front(T *e)
Add element to the front of the list.
Definition hlist:120
Our C++ library.
Definition arith:22
H_list_item_t< void > H_list_item
Untyped list item.
Definition hlist:72
Double-linked list of typed H_list_item_t elements.
Definition hlist:260