RAUL  0.5.1
ListImpl.hpp
1 /* This file is part of Raul.
2  * Copyright (C) 2007 Dave Robillard <http://drobilla.net>
3  *
4  * Raul is free software; you can redistribute it and/or modify it under the
5  * terms of the GNU General Public License as published by the Free Software
6  * Foundation; either version 2 of the License, or (at your option) any later
7  * version.
8  *
9  * Raul is distributed in the hope that it will be useful, but WITHOUT ANY
10  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details.
12  *
13  * You should have received a copy of the GNU General Public License along
14  * with this program; if not, write to the Free Software Foundation, Inc.,
15  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
16  */
17 
18 #ifndef RAUL_LIST_IMPL_HPP
19 #define RAUL_LIST_IMPL_HPP
20 
21 namespace Raul {
22 
23 
24 template <typename T>
25 List<T>::~List<T>()
26 {
27  clear();
28 }
29 
30 
35 template <typename T>
36 void
38 {
39  Node* node = _head.get();
40  Node* next = NULL;
41 
42  while (node) {
43  next = node->next();
44  delete node;
45  node = next;
46  }
47 
48  _head = 0;
49  _tail = 0;
50  _size = 0;
51 }
52 
53 
59 template <typename T>
60 void
62 {
63  assert(ln);
64 
65  ln->next(NULL);
66 
67  if ( ! _head.get()) { // empty
68  ln->prev(NULL);
69  _tail = ln;
70  _head = ln;
71  } else {
72  ln->prev(_tail.get());
73  _tail.get()->next(ln);
74  _tail = ln;
75  }
76  ++_size;
77 }
78 
79 
85 template <typename T>
86 void
88 {
89  Node* const ln = new Node(elem);
90 
91  assert(ln);
92 
93  ln->next(NULL);
94 
95  if ( ! _head.get()) { // empty
96  ln->prev(NULL);
97  _tail = ln;
98  _head = ln;
99  } else {
100  ln->prev(_tail.get());
101  _tail.get()->next(ln);
102  _tail = ln;
103  }
104  ++_size;
105 }
106 
107 
118 template <typename T>
119 void
121 {
122  Node* const my_head = _head.get();
123  Node* const my_tail = _tail.get();
124  Node* const other_head = list._head.get();
125  Node* const other_tail = list._tail.get();
126 
127  // Appending to an empty list
128  if (my_head == NULL && my_tail == NULL) {
129  _head = other_head;
130  _tail = other_tail;
131  _size = list._size;
132  } else if (other_head != NULL && other_tail != NULL) {
133 
134  other_head->prev(my_tail);
135 
136  // FIXME: atomicity an issue? _size < true size is probably fine...
137  // no gurantee an iteration runs exactly size times though. verify/document this.
138  // assuming comment above that says tail is writer only, this is fine
139  my_tail->next(other_head);
140  _tail = other_tail;
141  _size += list.size();
142  }
143 
144  list._head = NULL;
145  list._tail = NULL;
146  list._size = 0;
147 }
148 
149 
155 template <typename T>
156 typename List<T>::iterator
157 List<T>::find(const T& val)
158 {
159  for (iterator i = begin(); i != end(); ++i)
160  if (*i == val)
161  return i;
162 
163  return end();
164 }
165 
166 
174 template <typename T>
175 typename List<T>::Node*
177 {
178  Node* const n = iter._listnode;
179 
180  if (n) {
181 
182  Node* const prev = n->prev();
183  Node* const next = n->next();
184 
185  // Removing the head (or the only element)
186  if (n == _head.get())
187  _head = next;
188 
189  // Removing the tail (or the only element)
190  if (n == _tail.get())
191  _tail = _tail.get()->prev();
192 
193  if (prev)
194  n->prev()->next(next);
195 
196  if (next)
197  n->next()->prev(prev);
198 
199  --_size;
200  }
201 
202  return n;
203 }
204 
205 
207 
208 template <typename T>
210 : _list(list),
211  _listnode(NULL)
212 {
213 }
214 
215 
216 template <typename T>
217 T&
218 List<T>::iterator::operator*()
219 {
220  assert(_listnode);
221  return _listnode->elem();
222 }
223 
224 
225 template <typename T>
226 T*
227 List<T>::iterator::operator->()
228 {
229  assert(_listnode);
230  return &_listnode->elem();
231 }
232 
233 
234 template <typename T>
235 inline typename List<T>::iterator&
236 List<T>::iterator::operator++()
237 {
238  assert(_listnode);
239  _listnode = _listnode->next();
240 
241  return *this;
242 }
243 
244 
245 template <typename T>
246 inline bool
247 List<T>::iterator::operator!=(const iterator& iter) const
248 {
249  return (_listnode != iter._listnode);
250 }
251 
252 
253 template <typename T>
254 inline bool
255 List<T>::iterator::operator!=(const const_iterator& iter) const
256 {
257  return (_listnode != iter._listnode);
258 }
259 
260 
261 template <typename T>
262 inline bool
263 List<T>::iterator::operator==(const iterator& iter) const
264 {
265  return (_listnode == iter._listnode);
266 }
267 
268 
269 template <typename T>
270 inline bool
271 List<T>::iterator::operator==(const const_iterator& iter) const
272 {
273  return (_listnode == iter._listnode);
274 }
275 
276 
277 template <typename T>
278 inline typename List<T>::iterator
279 List<T>::begin()
280 {
281  typename List<T>::iterator iter(this);
282 
283  iter._listnode = _head.get();
284 
285  return iter;
286 }
287 
288 
289 template <typename T>
290 inline const typename List<T>::iterator
291 List<T>::end() const
292 {
293  return _end_iter;
294 }
295 
296 
297 
299 
300 
301 template <typename T>
303 : _list(list),
304  _listnode(NULL)
305 {
306 }
307 
308 
309 template <typename T>
310 const T&
312 {
313  assert(_listnode);
314  return _listnode->elem();
315 }
316 
317 
318 template <typename T>
319 const T*
321 {
322  assert(_listnode);
323  return &_listnode->elem();
324 }
325 
326 
327 template <typename T>
328 inline typename List<T>::const_iterator&
329 List<T>::const_iterator::operator++()
330 {
331  assert(_listnode);
332  _listnode = _listnode->next();
333 
334  return *this;
335 }
336 
337 
338 template <typename T>
339 inline bool
340 List<T>::const_iterator::operator!=(const const_iterator& iter) const
341 {
342  return (_listnode != iter._listnode);
343 }
344 
345 
346 template <typename T>
347 inline bool
348 List<T>::const_iterator::operator!=(const iterator& iter) const
349 {
350  return (_listnode != iter._listnode);
351 }
352 
353 
354 template <typename T>
355 inline bool
356 List<T>::const_iterator::operator==(const const_iterator& iter) const
357 {
358  return (_listnode == iter._listnode);
359 }
360 
361 
362 template <typename T>
363 inline bool
364 List<T>::const_iterator::operator==(const iterator& iter) const
365 {
366  return (_listnode == iter._listnode);
367 }
368 
369 template <typename T>
370 inline typename List<T>::const_iterator
371 List<T>::begin() const
372 {
373  typename List<T>::const_iterator iter(this);
374  iter._listnode = _head.get();
375  return iter;
376 }
377 
378 
379 } // namespace Raul
380 
381 
382 #endif // RAUL_LIST_IMPL_HPP
void clear()
Clear the list, deleting all Nodes contained (but NOT their contents!)
Definition: ListImpl.hpp:37
Realtime safe iterator for a List.
Definition: List.hpp:118
unsigned size() const
Valid only in the write thread.
Definition: List.hpp:87
A node in a List.
Definition: List.hpp:48
A realtime safe, (partially) thread safe doubly-linked list.
Definition: List.hpp:38
void append(List< T > &list)
Append a list to this list.
Definition: ListImpl.hpp:120
Node * erase(const iterator iter)
Remove an element from the list using an iterator.
Definition: ListImpl.hpp:176
void push_back(Node *elem)
Realtime Safe.
Definition: ListImpl.hpp:61
iterator find(const T &val)
Find an element in the list.
Definition: ListImpl.hpp:157
const_iterator(const List< T > *const list)
const_iterator stuff ///
Definition: ListImpl.hpp:302