L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
dlist
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
22namespace cxx {
23
24class D_list_item
25{
26public:
27 D_list_item() : _dli_next(0) {}
28private:
29 friend class D_list_item_policy;
30
31 D_list_item(D_list_item const &);
32 void operator = (D_list_item const &);
33
34 D_list_item *_dli_next, *_dli_prev;
35};
36
37class D_list_item_policy
38{
39public:
40 typedef D_list_item Item;
41 static D_list_item *&prev(D_list_item *e) { return e->_dli_prev; }
42 static D_list_item *&next(D_list_item *e) { return e->_dli_next; }
43 static D_list_item *prev(D_list_item const *e) { return e->_dli_prev; }
44 static D_list_item *next(D_list_item const *e) { return e->_dli_next; }
45};
46
47template< typename T >
48struct Sd_list_head_policy
49{
50 typedef T *Head_type;
51 static T *head(Head_type h) { return h; }
52 static void set_head(Head_type &h, T *v) { h = v; }
53};
54
55template<
56 typename T,
57 typename C = D_list_item_policy
58>
59class D_list_cyclic
60{
61protected:
62 template< typename VALUE, typename ITEM >
63 class __Iterator
64 {
65 public:
66 typedef VALUE *Value_type;
67 typedef VALUE *value_type;
68
69 __Iterator() {}
70
71 bool operator == (__Iterator const &o) const
72 { return _c == o._c; }
73
74 bool operator != (__Iterator const &o) const
75 { return _c != o._c; }
76
77 __Iterator &operator ++ ()
78 {
79 _c = C::next(_c);
80 return *this;
81 }
82
83 __Iterator &operator -- ()
84 {
85 _c = C::prev(_c);
86 return *this;
87 }
88
89 Value_type operator * () const { return static_cast<Value_type>(_c); }
90 Value_type operator -> () const { return static_cast<Value_type>(_c); }
91
92 private:
93 friend class D_list_cyclic;
94
95 explicit __Iterator(ITEM *s) : _c(s) {}
96
97 ITEM *_c;
98 };
99
100public:
101 typedef T *Value_type;
102 typedef T *value_type;
103 typedef __Iterator<T, typename C::Item> Iterator;
104 typedef Iterator Const_iterator;
105
106 static void remove(T *e)
107 {
108 C::next(C::prev(e)) = C::next(e);
109 C::prev(C::next(e)) = C::prev(e);
110 C::next(e) = 0;
111 }
112
113 static Iterator erase(Iterator const &e)
114 {
115 typename C::Item *n = C::next(*e);
116 remove(*e);
117 return __iter(n);
118 }
119
120 static Iterator iter(T const *e) { return Iterator(const_cast<T*>(e)); }
121
122 static bool in_list(T const *e) { return C::next(const_cast<T*>(e)); }
123 static bool has_sibling(T const *e) { return C::next(const_cast<T*>(e)) != e; }
124
125 static Iterator insert_after(T *e, Iterator const &pos)
126 {
127 C::prev(e) = *pos;
128 C::next(e) = C::next(*pos);
129 C::prev(C::next(*pos)) = e;
130 C::next(*pos) = e;
131 return pos;
132 }
133
134 static Iterator insert_before(T *e, Iterator const &pos)
135 {
136 C::next(e) = *pos;
137 C::prev(e) = C::prev(*pos);
138 C::next(C::prev(*pos)) = e;
139 C::prev(*pos) = e;
140 return pos;
141 }
142
143 static T *self_insert(T *e)
144 { C::next(e) = C::prev(e) = e; return e; }
145
146 static void remove_last(T *e)
147 { C::next(e) = 0; }
148
149protected:
150 static Iterator __iter(typename C::Item *e) { return Iterator(e); }
151};
152
153template<
154 typename T,
155 typename C = D_list_item_policy,
156 typename H = Sd_list_head_policy<T>,
157 bool BSS = false
158>
159class Sd_list : public D_list_cyclic<T, C>
160{
161private:
162 typedef D_list_cyclic<T, C> Base;
163
164public:
165 typedef typename Base::Iterator Iterator;
166 enum Pos
167 { Back, Front };
168
169 Sd_list() { if (!BSS) H::set_head(_f, 0); }
170
171 bool empty() const { return !H::head(_f); }
172 T *front() const { return H::head(_f); }
173
174 void remove(T *e)
175 {
176 T *h = H::head(_f);
177 if (e == C::next(e)) // must be the last
178 {
179 Base::remove_last(e);
180 H::set_head(_f, 0);
181 return;
182 }
183
184 if (e == H::head(_f))
185 H::set_head(_f, static_cast<T*>(C::next(h)));
186
187 Base::remove(e);
188 }
189
190 Iterator erase(Iterator const &e)
191 {
192 typename C::Item *n = C::next(*e);
193 remove(*e);
194 return __iter(n);
195 }
196
197 void push(T *e, Pos pos)
198 {
199 T *h = H::head(_f);
200 if (!h)
201 H::set_head(_f, Base::self_insert(e));
202 else
203 {
204 Base::insert_before(e, this->iter(h));
205 if (pos == Front)
206 H::set_head(_f, e);
207 }
208 }
209
210 void push_back(T *e) { push(e, Back); }
211 void push_front(T *e) { push(e, Front); }
212 void rotate_to(T *h) { H::set_head(_f, h); }
213
214 typename H::Head_type const &head() const { return _f; }
215 typename H::Head_type &head() { return _f; }
216
217private:
218 Sd_list(Sd_list const &);
219 void operator = (Sd_list const &);
220
221 typename H::Head_type _f;
222};
223
224template<
225 typename T,
226 typename C = D_list_item_policy,
227 bool BSS = false
228>
229class D_list : public D_list_cyclic<T, C>
230{
231private:
232 typedef D_list_cyclic<T, C> Base;
233 typedef typename C::Item Internal_type;
234
235public:
236 enum Pos
237 { Back, Front };
238
239 typedef typename Base::Iterator Iterator;
240 typedef typename Base::Const_iterator Const_iterator;
241 typedef T* value_type;
242 typedef T* Value_type;
243
244 D_list() { this->self_insert(static_cast<T*>(&_h)); }
245
246 bool empty() const { return C::next(static_cast<T const *>(&_h)) == &_h; }
247
248 static void remove(T *e) { Base::remove(e); }
249 Iterator erase(Iterator const &e) { return Base::erase(e); }
250
251 void push(T *e, Pos pos)
252 {
253 if (pos == Front)
254 Base::insert_after(e, end());
255 else
256 Base::insert_before(e, end());
257 }
258
259 void push_back(T *e) { push(e, Back); }
260 void push_front(T *e) { push(e, Front); }
261
262 Iterator begin() const { return this->__iter(C::next(const_cast<Internal_type *>(&_h))); }
263 Iterator end() const { return this->__iter(const_cast<Internal_type *>(&_h)); }
264
265private:
266 D_list(D_list const &);
267 void operator = (D_list const &);
268
269 Internal_type _h;
270};
271
272}
273
Our C++ library.
Definition arith:22