L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
slist
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
24namespace cxx {
25
26class S_list_item
27{
28public:
29 S_list_item() : _n(0) {}
30 // BSS allocation
31 explicit S_list_item(bool) {}
32
33private:
34 template<typename T, typename P> friend class S_list;
35 template<typename T, typename P> friend class S_list_tail;
36 template<typename T, typename X> friend struct Bits::Basic_list_policy;
37
38 S_list_item(S_list_item const &);
39 void operator = (S_list_item const &);
40
41 S_list_item *_n;
42};
43
50template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item > >
51class S_list : public Bits::Basic_list<POLICY>
52{
53 S_list(S_list const &) = delete;
54 void operator = (S_list const &) = delete;
55
56private:
57 typedef typename Bits::Basic_list<POLICY> Base;
58
59public:
60 typedef typename Base::Iterator Iterator;
61
62 S_list(S_list &&o) : Base(static_cast<Base&&>(o)) {}
63
64 S_list &operator = (S_list &&o)
65 {
66 Base::operator = (static_cast<Base&&>(o));
67 return *this;
68 }
69
70 // BSS allocation
71 explicit S_list(bool x) : Base(x) {}
72
73 S_list() : Base() {}
74
76 void add(T *e)
77 {
78 e->_n = this->_f;
79 this->_f = e;
80 }
81
82 template< typename CAS >
83 void add(T *e, CAS const &c)
84 {
85 do
86 {
87 e->_n = this->_f;
88 }
89 while (!c(&this->_f, e->_n, e));
90 }
91
93 void push_front(T *e) { add(e); }
94
101 {
102 T *r = this->front();
103 if (this->_f)
104 this->_f = this->_f->_n;
105 return r;
106 }
107
108 void insert(T *e, Iterator const &pred)
109 {
110 S_list_item *p = *pred;
111 e->_n = p->_n;
112 p->_n = e;
113 }
114
115 static void insert_before(T *e, Iterator const &succ)
116 {
117 S_list_item **x = Base::__get_internal(succ);
118
119 e->_n = *x;
120 *x = e;
121 }
122
123 static void replace(Iterator const &p, T*e)
124 {
125 S_list_item **x = Base::__get_internal(p);
126 e->_n = (*x)->_n;
127 *x = e;
128 }
129
130 static Iterator erase(Iterator const &e)
131 {
132 S_list_item **x = Base::__get_internal(e);
133 *x = (*x)->_n;
134 return e;
135 }
136
137};
138
139
140template< typename T >
141class S_list_bss : public S_list<T>
142{
143public:
144 S_list_bss() : S_list<T>(true) {}
145};
146
147template< typename T, typename POLICY = Bits::Basic_list_policy< T, S_list_item > >
148class S_list_tail : public S_list<T, POLICY>
149{
150private:
151 typedef S_list<T, POLICY> Base;
152 void add(T *e) = delete;
153
154public:
155 using Iterator = typename Base::Iterator;
156 S_list_tail() : Base(), _tail(&this->_f) {}
157
158 S_list_tail(S_list_tail &&t)
159 : Base(static_cast<Base&&>(t)), _tail(t.empty() ? &this->_f : t._tail)
160 {
161 t._tail = &t._f;
162 }
163
164 S_list_tail &operator = (S_list_tail &&t)
165 {
166 if (&t == this)
167 return *this;
168
169 Base::operator = (static_cast<Base &&>(t));
170 _tail = t.empty() ? &this->_f : t._tail;
171 t._tail = &t._f;
172 return *this;
173 }
174
175 void push_front(T *e)
176 {
177 if (Base::empty())
178 _tail = &e->_n;
179
181 }
182
183 void push_back(T *e)
184 {
185 e->_n = 0;
186 *_tail = e;
187 _tail = &e->_n;
188 }
189
190 void clear()
191 {
192 Base::clear();
193 _tail = &this->_f;
194 }
195
196 void append(S_list_tail &o)
197 {
198 T *x = o.front();
199 *_tail = x;
200 if (x)
201 _tail = o._tail;
202 o.clear();
203 }
204
205 T *pop_front()
206 {
207 T *t = Base::pop_front();
208 if (t && Base::empty())
209 _tail = &this->_f;
210 return t;
211 }
212
213private:
214 static void insert(T *e, Iterator const &pred);
215 static void insert_before(T *e, Iterator const &succ);
216 static void replace(Iterator const &p, T*e);
217 static Iterator erase(Iterator const &e);
218
219private:
220 S_list_item **_tail;
221};
222
223}
Internal: Common functions for all head-based list implementations.
Definition list_basics.h:51
bool empty() const
Check if the list is empty.
void clear()
Remove all elements from the list.
POLICY::Head_type _f
Pointer to front of the list.
Value_type front() const
Return the first element in the list.
Simple single-linked list.
Definition slist:52
void add(T *e)
Add an element to the front of the list.
Definition slist:76
void push_front(T *e)
Add an element to the front of the list.
Definition slist:93
T * pop_front()
Remove and return the head element of the list.
Definition slist:100
Our C++ library.
Definition arith:22