RAUL  0.8.0
ListImpl.hpp
1 /* This file is part of Raul.
2  * Copyright (C) 2007-2009 David 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
61 List<T>::push_back(Node* const ln)
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 
117 template <typename T>
118 void
120 {
121  Node* const my_head = _head.get();
122  Node* const my_tail = _tail.get();
123  Node* const other_head = list._head.get();
124  Node* const other_tail = list._tail.get();
125 
126  assert((my_head && my_tail) || (!my_head && !my_tail));
127  assert((other_head && other_tail) || (!other_head && !other_tail));
128 
129  // Appending to an empty list
130  if (my_head == NULL && my_tail == NULL) {
131  _tail = other_tail;
132  _head = other_head;
133  _size = list._size;
134  } else if (other_head != NULL && other_tail != NULL) {
135 
136  other_head->prev(my_tail);
137 
138  // FIXME: atomicity an issue? _size < true size is probably fine...
139  // no guarantee an iteration runs exactly size times though. verify/document this.
140  // assuming comment above that says tail is writer only, this is fine
141  my_tail->next(other_head);
142  _tail = other_tail;
143  _size += list.size();
144  }
145 
146  list._head = NULL;
147  list._tail = NULL;
148  list._size = 0;
149 }
150 
151 
156 template <typename T>
157 typename List<T>::iterator
158 List<T>::find(const T& val)
159 {
160  for (iterator i = begin(); i != end(); ++i)
161  if (*i == val)
162  return i;
163 
164  return end();
165 }
166 
167 
175 template <typename T>
176 typename List<T>::Node*
177 List<T>::erase(const iterator iter)
178 {
179  assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
180 
181  Node* const n = iter._listnode;
182 
183  if (n) {
184  Node* const prev = n->prev();
185  Node* const next = n->next();
186 
187  // Removing the head (or the only element)
188  if (n == _head.get())
189  _head = next;
190 
191  // Removing the tail (or the only element)
192  if (n == _tail.get())
193  _tail = _tail.get()->prev();
194 
195  if (prev)
196  n->prev()->next(next);
197 
198  if (next)
199  n->next()->prev(prev);
200 
201  --_size;
202  }
203 
204  assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
205  return n;
206 }
207 
208 
209 template <typename T>
210 void
211 List<T>::chop_front(List<T>& front, size_t front_size, Node* front_tail)
212 {
213  assert(front_tail);
214  assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get()));
215  assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
216  front._size = front_size;
217  front._head = _head;
218  front._tail = front_tail;
219  Node* new_head = front_tail->next();
220  if (new_head) {
221  new_head->prev(NULL);
222  _head = new_head;
223  } else {
224  // FIXME: race?
225  _head = NULL;
226  _tail = NULL;
227  }
228  _size -= front_size;
229  front_tail->next(NULL);
230  assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get()));
231  assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
232 }
233 
234 
236 
237 template <typename T>
238 List<T>::iterator::iterator(List<T>* list)
239 : _list(list),
240  _listnode(NULL)
241 {
242 }
243 
244 
245 template <typename T>
246 T&
247 List<T>::iterator::operator*()
248 {
249  assert(_listnode);
250  return _listnode->elem();
251 }
252 
253 
254 template <typename T>
255 T*
256 List<T>::iterator::operator->()
257 {
258  assert(_listnode);
259  return &_listnode->elem();
260 }
261 
262 
263 template <typename T>
264 inline typename List<T>::iterator&
265 List<T>::iterator::operator++()
266 {
267  assert(_listnode);
268  _listnode = _listnode->next();
269 
270  return *this;
271 }
272 
273 
274 template <typename T>
275 inline bool
276 List<T>::iterator::operator!=(const iterator& iter) const
277 {
278  return (_listnode != iter._listnode);
279 }
280 
281 
282 template <typename T>
283 inline bool
284 List<T>::iterator::operator!=(const const_iterator& iter) const
285 {
286  return (_listnode != iter._listnode);
287 }
288 
289 
290 template <typename T>
291 inline bool
292 List<T>::iterator::operator==(const iterator& iter) const
293 {
294  return (_listnode == iter._listnode);
295 }
296 
297 
298 template <typename T>
299 inline bool
300 List<T>::iterator::operator==(const const_iterator& iter) const
301 {
302  return (_listnode == iter._listnode);
303 }
304 
305 
306 template <typename T>
307 inline typename List<T>::iterator
308 List<T>::begin()
309 {
310  typename List<T>::iterator iter(this);
311 
312  iter._listnode = _head.get();
313 
314  return iter;
315 }
316 
317 
318 template <typename T>
319 inline const typename List<T>::iterator
320 List<T>::end() const
321 {
322  return _end_iter;
323 }
324 
325 
326 
328 
329 
330 template <typename T>
332 : _list(list),
333  _listnode(NULL)
334 {
335 }
336 
337 
338 template <typename T>
339 const T&
341 {
342  assert(_listnode);
343  return _listnode->elem();
344 }
345 
346 
347 template <typename T>
348 const T*
350 {
351  assert(_listnode);
352  return &_listnode->elem();
353 }
354 
355 
356 template <typename T>
357 inline typename List<T>::const_iterator&
358 List<T>::const_iterator::operator++()
359 {
360  assert(_listnode);
361  _listnode = _listnode->next();
362 
363  return *this;
364 }
365 
366 
367 template <typename T>
368 inline bool
369 List<T>::const_iterator::operator!=(const const_iterator& iter) const
370 {
371  return (_listnode != iter._listnode);
372 }
373 
374 
375 template <typename T>
376 inline bool
377 List<T>::const_iterator::operator!=(const iterator& iter) const
378 {
379  return (_listnode != iter._listnode);
380 }
381 
382 
383 template <typename T>
384 inline bool
385 List<T>::const_iterator::operator==(const const_iterator& iter) const
386 {
387  return (_listnode == iter._listnode);
388 }
389 
390 
391 template <typename T>
392 inline bool
393 List<T>::const_iterator::operator==(const iterator& iter) const
394 {
395  return (_listnode == iter._listnode);
396 }
397 
398 template <typename T>
399 inline typename List<T>::const_iterator
400 List<T>::begin() const
401 {
402  typename List<T>::const_iterator iter(this);
403  iter._listnode = _head.get();
404  return iter;
405 }
406 
407 
408 } // namespace Raul
409 
410 
411 #endif // RAUL_LIST_IMPL_HPP
Raul::List::erase
Node * erase(const iterator iter)
Remove an element from the list using an iterator.
Definition: ListImpl.hpp:177
Raul::List::iterator
Realtime safe iterator for a List.
Definition: List.hpp:130
Raul::List
A realtime safe, (partially) thread safe doubly-linked list.
Definition: List.hpp:41
Raul::List::find
iterator find(const T &val)
Find an element in the list.
Definition: ListImpl.hpp:158
Raul::List::size
unsigned size() const
Valid only in the write thread.
Definition: List.hpp:96
Raul::List::clear
void clear()
Clear the list, deleting all Nodes contained (but NOT their contents!)
Definition: ListImpl.hpp:37
Raul::List::append
void append(List< T > &list)
Append a list to this list.
Definition: ListImpl.hpp:119
Raul::List::Node
A node in a List.
Definition: List.hpp:51
Raul::List::push_back
void push_back(Node *elem)
Realtime Safe.
Definition: ListImpl.hpp:61