ListImpl.hpp
/* This file is part of Raul.
* Copyright (C) 2007-2009 David Robillard <http://drobilla.net>
*
* Raul is free software; you can redistribute it and/or modify it under the
* terms of the GNU General Public License as published by the Free Software
* Foundation; either version 2 of the License, or (at your option) any later
* version.
*
* Raul is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE. See the GNU General Public License for details.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#ifndef RAUL_LIST_IMPL_HPP
#define RAUL_LIST_IMPL_HPP
namespace Raul {
template <typename T>
List<T>::~List<T>()
{
clear();
}
template <typename T>
void
List<T>::clear()
{
Node* node = _head.get();
Node* next = NULL;
while (node) {
next = node->next();
delete node;
node = next;
}
_head = 0;
_tail = 0;
_size = 0;
}
template <typename T>
void
List<T>::push_back(Node* const ln)
{
assert(ln);
ln->next(NULL);
if ( ! _head.get()) { // empty
ln->prev(NULL);
_tail = ln;
_head = ln;
} else {
ln->prev(_tail.get());
_tail.get()->next(ln);
_tail = ln;
}
++_size;
}
template <typename T>
void
List<T>::push_back(T& elem)
{
Node* const ln = new Node(elem);
assert(ln);
ln->next(NULL);
if ( ! _head.get()) { // empty
ln->prev(NULL);
_tail = ln;
_head = ln;
} else {
ln->prev(_tail.get());
_tail.get()->next(ln);
_tail = ln;
}
++_size;
}
template <typename T>
void
List<T>::append(List<T>& list)
{
Node* const my_head = _head.get();
Node* const my_tail = _tail.get();
Node* const other_head = list._head.get();
Node* const other_tail = list._tail.get();
assert((my_head && my_tail) || (!my_head && !my_tail));
assert((other_head && other_tail) || (!other_head && !other_tail));
// Appending to an empty list
if (my_head == NULL && my_tail == NULL) {
_tail = other_tail;
_head = other_head;
_size = list._size;
} else if (other_head != NULL && other_tail != NULL) {
other_head->prev(my_tail);
// FIXME: atomicity an issue? _size < true size is probably fine...
// no guarantee an iteration runs exactly size times though. verify/document this.
// assuming comment above that says tail is writer only, this is fine
my_tail->next(other_head);
_tail = other_tail;
_size += list.size();
}
list._head = NULL;
list._tail = NULL;
list._size = 0;
}
template <typename T>
typename List<T>::iterator
List<T>::find(const T& val)
{
for (iterator i = begin(); i != end(); ++i)
if (*i == val)
return i;
return end();
}
template <typename T>
typename List<T>::Node*
List<T>::erase(const iterator iter)
{
assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
Node* const n = iter._listnode;
if (n) {
Node* const prev = n->prev();
Node* const next = n->next();
// Removing the head (or the only element)
if (n == _head.get())
_head = next;
// Removing the tail (or the only element)
if (n == _tail.get())
_tail = _tail.get()->prev();
if (prev)
n->prev()->next(next);
if (next)
n->next()->prev(prev);
--_size;
}
assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
return n;
}
template <typename T>
void
List<T>::chop_front(List<T>& front, size_t front_size, Node* front_tail)
{
assert(front_tail);
assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get()));
assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
front._size = front_size;
front._head = _head;
front._tail = front_tail;
Node* new_head = front_tail->next();
if (new_head) {
new_head->prev(NULL);
_head = new_head;
} else {
// FIXME: race?
_head = NULL;
_tail = NULL;
}
_size -= front_size;
front_tail->next(NULL);
assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get()));
assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
}
template <typename T>
List<T>::iterator::iterator(List<T>* list)
: _list(list),
_listnode(NULL)
{
}
template <typename T>
T&
List<T>::iterator::operator*()
{
assert(_listnode);
return _listnode->elem();
}
template <typename T>
T*
List<T>::iterator::operator->()
{
assert(_listnode);
return &_listnode->elem();
}
template <typename T>
inline typename List<T>::iterator&
List<T>::iterator::operator++()
{
assert(_listnode);
_listnode = _listnode->next();
return *this;
}
template <typename T>
inline bool
List<T>::iterator::operator!=(const iterator& iter) const
{
return (_listnode != iter._listnode);
}
template <typename T>
inline bool
List<T>::iterator::operator!=(const const_iterator& iter) const
{
return (_listnode != iter._listnode);
}
template <typename T>
inline bool
List<T>::iterator::operator==(const iterator& iter) const
{
return (_listnode == iter._listnode);
}
template <typename T>
inline bool
List<T>::iterator::operator==(const const_iterator& iter) const
{
return (_listnode == iter._listnode);
}
template <typename T>
inline typename List<T>::iterator
List<T>::begin()
{
typename List<T>::iterator iter(this);
iter._listnode = _head.get();
return iter;
}
template <typename T>
inline const typename List<T>::iterator
List<T>::end() const
{
return _end_iter;
}
template <typename T>
List<T>::const_iterator::const_iterator(const List<T>* const list)
: _list(list),
_listnode(NULL)
{
}
template <typename T>
const T&
List<T>::const_iterator::operator*()
{
assert(_listnode);
return _listnode->elem();
}
template <typename T>
const T*
List<T>::const_iterator::operator->()
{
assert(_listnode);
return &_listnode->elem();
}
template <typename T>
inline typename List<T>::const_iterator&
List<T>::const_iterator::operator++()
{
assert(_listnode);
_listnode = _listnode->next();
return *this;
}
template <typename T>
inline bool
List<T>::const_iterator::operator!=(const const_iterator& iter) const
{
return (_listnode != iter._listnode);
}
template <typename T>
inline bool
List<T>::const_iterator::operator!=(const iterator& iter) const
{
return (_listnode != iter._listnode);
}
template <typename T>
inline bool
List<T>::const_iterator::operator==(const const_iterator& iter) const
{
return (_listnode == iter._listnode);
}
template <typename T>
inline bool
List<T>::const_iterator::operator==(const iterator& iter) const
{
return (_listnode == iter._listnode);
}
template <typename T>
inline typename List<T>::const_iterator
List<T>::begin() const
{
typename List<T>::const_iterator iter(this);
iter._listnode = _head.get();
return iter;
}
} // namespace Raul
#endif // RAUL_LIST_IMPL_HPP
Raul::List::clear
void clear()
Clear the list, deleting all Nodes contained (but NOT their contents!)
Definition: ListImpl.hpp:37
Raul::List::iterator
Realtime safe iterator for a List.
Definition: List.hpp:130
Raul::List::size
unsigned size() const
Valid only in the write thread.
Definition: List.hpp:96
Raul::List::Node
A node in a List.
Definition: List.hpp:51
Raul
Definition: Array.hpp:26
Raul::List
A realtime safe, (partially) thread safe doubly-linked list.
Definition: List.hpp:41
Raul::List::append
void append(List< T > &list)
Append a list to this list.
Definition: ListImpl.hpp:119
Raul::List::erase
Node * erase(const iterator iter)
Remove an element from the list using an iterator.
Definition: ListImpl.hpp:177
Raul::List::push_back
void push_back(Node *elem)
Realtime Safe.
Definition: ListImpl.hpp:61
Raul::List::find
iterator find(const T &val)
Find an element in the list.
Definition: ListImpl.hpp:158
Raul::List::const_iterator::const_iterator
const_iterator(const List< T > *const list)
const_iterator stuff ///
Definition: ListImpl.hpp:331