List.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_HPP
#define RAUL_LIST_HPP
#include <cstddef>
#include <cassert>
#include <boost/utility.hpp>
#include "raul/AtomicInt.hpp"
#include "raul/AtomicPtr.hpp"
#include "raul/Deletable.hpp"
namespace Raul {
template <typename T>
class List : public Raul::Deletable, public boost::noncopyable
{
public:
class Node : public Raul::Deletable {
public:
explicit Node(T elem) : _elem(elem) {}
virtual ~Node() {}
template <typename Y>
explicit Node(const typename List<Y>::Node& copy)
: _elem(copy._elem), _prev(copy._prev), _next(copy._next)
{}
Node* prev() const { return _prev.get(); }
void prev(Node* ln) { _prev = ln; }
Node* next() const { return _next.get(); }
void next(Node* ln) { _next = ln; }
T& elem() { return _elem;}
const T& elem() const { return _elem; }
private:
T _elem;
AtomicPtr<Node> _prev;
AtomicPtr<Node> _next;
};
List(size_t size=0, Node* head=NULL, Node* tail=NULL)
: _size(size)
, _end_iter(this)
, _const_end_iter(this)
{
_head = head;
_tail = tail;
_end_iter._listnode = NULL;
_const_end_iter._listnode = NULL;
}
~List();
void push_back(Node* elem);
void push_back(T& elem);
void append(List<T>& list);
void clear();
unsigned size() const { return static_cast<unsigned>(_size.get()); }
bool empty() { return (_head.get() == NULL); }
class iterator;
class const_iterator {
public:
explicit const_iterator(const List<T>* const list);
const_iterator(const iterator& i)
: _list(i._list), _listnode(i._listnode) {}
inline const T& operator*();
inline const T* operator->();
inline const_iterator& operator++();
inline bool operator!=(const const_iterator& iter) const;
inline bool operator!=(const iterator& iter) const;
inline bool operator==(const const_iterator& iter) const;
inline bool operator==(const iterator& iter) const;
inline typename List<T>::Node* node() { return _listnode; }
inline const typename List<T>::Node* node() const { return _listnode; }
friend class List<T>;
private:
const List<T>* _list;
const typename List<T>::Node* _listnode;
};
class iterator {
public:
explicit iterator(List<T>* const list);
inline T& operator*();
inline T* operator->();
inline iterator& operator++();
inline bool operator!=(const iterator& iter) const;
inline bool operator!=(const const_iterator& iter) const;
inline bool operator==(const iterator& iter) const;
inline bool operator==(const const_iterator& iter) const;
friend class List<T>;
friend class List<T>::const_iterator;
private:
const List<T>* _list;
typename List<T>::Node* _listnode;
};
void chop_front(List<T>& front, size_t front_size, Node* front_tail);
Node* erase(const iterator iter);
iterator find(const T& val);
iterator begin();
const_iterator begin() const;
const iterator end() const;
T& front() { return *begin(); }
const T& front() const { return *begin(); }
Node* head() { return _head.get(); }
const Node* head() const { return _head.get(); }
private:
AtomicPtr<Node> _head;
AtomicPtr<Node> _tail;
AtomicInt _size;
iterator _end_iter;
const_iterator _const_end_iter;
};
} // namespace Raul
#endif // RAUL_LIST_HPP
#include "ListImpl.hpp"
Raul::Deletable
Something with a virtual destructor.
Definition: Deletable.hpp:28
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::AtomicPtr
Atomic pointer.
Definition: AtomicPtr.hpp:30
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::AtomicInt
Atomic integer.
Definition: AtomicInt.hpp:29
Raul::List::erase
Node * erase(const iterator iter)
Remove an element from the list using an iterator.
Definition: ListImpl.hpp:177
Raul::List::const_iterator
Realtime safe const iterator for a List.
Definition: List.hpp:104
Raul::List::push_back
void push_back(Node *elem)
Realtime Safe.
Definition: ListImpl.hpp:61
Raul::List::empty
bool empty()
Valid for any thread.
Definition: List.hpp:99
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