L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
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
26namespace cxx {
27/*
28 * Classes: List_item, List<D, Alloc>
29 */
30
38{
39public:
45 class Iter
46 {
47 public:
48 Iter(List_item *c, List_item *f) noexcept : _c(c), _f(f) {}
49 Iter(List_item *f = 0) noexcept : _c(f), _f(f) {}
50
51 List_item *operator * () const noexcept { return _c; }
52 List_item *operator -> () const noexcept { return _c; }
53 Iter &operator ++ () noexcept
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) noexcept
67 { Iter o = *this; operator ++ (); return o; }
68
69 Iter &operator -- () noexcept
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) noexcept
83 { Iter o = *this; operator -- (); return o; }
84
86 List_item *remove_me() noexcept
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
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>) noexcept
126 { return dynamic_cast<List_item*>(i); }
127
128 static List_item *cast_to_li(T *i, Int_to_type<false>) noexcept
129 { return i; }
130
131 static T *cast_to_type(List_item *i, Int_to_type<true>) noexcept
132 { return dynamic_cast<T*>(i); }
133
134 static T *cast_to_type(List_item *i, Int_to_type<false>) noexcept
135 { return static_cast<T*>(i); }
136
137 public:
138
139 template< typename O >
140 explicit T_iter(T_iter<O> const &o) noexcept
141 : Iter(o) { dynamic_cast<T*>(*o); }
142
143 //TIter(CListItem *f) : Iter(f) {}
144 T_iter(T *f = 0) noexcept : Iter(cast_to_li(f, Int_to_type<P>())) {}
145 T_iter(T *c, T *f) noexcept
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 noexcept
151 { return cast_to_type(Iter::operator * (),Int_to_type<P>()); }
152 inline T *operator -> () const noexcept
153 { return operator * (); }
154
155 T_iter<T, Poly> operator ++ (int) noexcept
156 { T_iter<T, Poly> o = *this; Iter::operator ++ (); return o; }
157 T_iter<T, Poly> operator -- (int) noexcept
158 { T_iter<T, Poly> o = *this; Iter::operator -- (); return o; }
159 T_iter<T, Poly> &operator ++ () noexcept
160 { Iter::operator ++ (); return *this; }
161 T_iter<T, Poly> &operator -- () noexcept
162 { Iter::operator -- (); return *this; }
163 inline T *remove_me() noexcept;
164 };
165
166 List_item() noexcept : _n(this), _p(this) {}
167
168protected:
169 List_item(List_item const &) noexcept : _n(this), _p(this) {}
170
171public:
173 List_item *get_prev_item() const noexcept { return _p; }
174
176 List_item *get_next_item() const noexcept { return _n; }
177
179 void insert_prev_item(List_item *p) noexcept
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
189 void insert_next_item(List_item *p) noexcept
190 {
191 p->_p->_n = _n;
192 p->_p = this;
193 _n->_p = p;
194 _n = p;
195 }
196
198 void remove_me() noexcept
199 {
200 if (_p != this)
201 {
202 _p->_n = _n;
203 _n->_p = _p;
204 }
205 _p = _n = this;
206 }
207
216 template< typename C, typename N >
217 static inline C *push_back(C *head, N *p) noexcept;
218
227 template< typename C, typename N >
228 static inline C *push_front(C *head, N *p) noexcept;
229
238 template< typename C, typename N >
239 static inline C *remove(C *head, N *p) noexcept;
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) noexcept
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) noexcept
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) noexcept
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
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
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) noexcept : data(d) {}
341 D data;
342 };
343
344public:
345 class Node : private E
346 {};
347
348 typedef Alloc<Node> Node_alloc;
349
354 class Iter
355 {
356 private:
358
359 public:
360 Iter(E *e) noexcept : _i(e) {}
361
362 D &operator * () const noexcept { return (*_i)->data; }
363 D &operator -> () const noexcept { return (*_i)->data; }
364
365 Iter operator ++ (int) noexcept
366 { Iter o = *this; operator ++ (); return o; }
367 Iter operator -- (int) noexcept
368 { Iter o = *this; operator -- (); return o; }
369 Iter &operator ++ () noexcept { ++_i; return *this; }
370 Iter &operator -- () noexcept { --_i; return *this; }
371
373 operator E* () const noexcept { return *_i; }
374 };
375
376 List(Alloc<Node> const &a = Alloc<Node>()) noexcept : _h(0), _l(0), _a(a) {}
377
379 void push_back(D const &d) noexcept
380 {
381 void *n = _a.alloc();
382 if (!n) return;
383 _h = E::push_back(_h, new (n) E(d));
384 ++_l;
385 }
386
388 void push_front(D const &d) noexcept
389 {
390 void *n = _a.alloc();
391 if (!n) return;
392 _h = E::push_front(_h, new (n) E(d));
393 ++_l;
394 }
395
397 void remove(Iter const &i) noexcept
398 { E *e = i; _h = E::remove(_h, e); --_l; _a.free(e); }
399
401 unsigned long size() const noexcept { return _l; }
402
404 D const &operator [] (unsigned long idx) const noexcept
405 { Iter i = _h; for (; idx && *i; ++i, --idx) { } return *i; }
406
408 D &operator [] (unsigned long idx) noexcept
409 { Iter i = _h; for (; idx && *i; ++i, --idx) { } return *i; }
410
412 Iter items() noexcept { return Iter(_h); }
413
414private:
415 E *_h;
416 unsigned _l;
417 Alloc<Node> _a;
418};
419
420
421};
422
Iterator.
Definition list:355
Iterator for a list of ListItem-s.
Definition list:46
List_item * remove_me() noexcept
Remove item pointed to by iterator, and return pointer to element.
Definition list:86
Iterator for derived classes from ListItem.
Definition list:120
Basic list item.
Definition list:38
void remove_me() noexcept
Remove this item from the list.
Definition list:198
static C * remove(C *head, N *p) noexcept
Remove item from a list.
Definition list:269
static C * push_front(C *head, N *p) noexcept
Prepend item to a list.
Definition list:259
void insert_next_item(List_item *p) noexcept
Insert item p after this item.
Definition list:189
void insert_prev_item(List_item *p) noexcept
Insert item p before this item.
Definition list:179
List_item * get_prev_item() const noexcept
Get previous item.
Definition list:173
List_item * get_next_item() const noexcept
Get next item.
Definition list:176
static C * push_back(C *head, N *p) noexcept
Append item to a list.
Definition list:248
Doubly linked list, with internal allocation.
Definition list:335
void remove(Iter const &i) noexcept
Remove element pointed to by the iterator.
Definition list:397
unsigned long size() const noexcept
Get the length of the list.
Definition list:401
void push_front(D const &d) noexcept
Add element at the beginning of the list.
Definition list:388
D const & operator[](unsigned long idx) const noexcept
Random access.
Definition list:404
Iter items() noexcept
Get iterator for the list elements.
Definition list:412
void push_back(D const &d) noexcept
Add element at the end of the list.
Definition list:379
Our C++ library.
Definition arith:22