RAUL  0.8.0
List.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_HPP
19 #define RAUL_LIST_HPP
20 
21 #include <cstddef>
22 #include <cassert>
23 
24 #include <boost/utility.hpp>
25 
26 #include "raul/AtomicInt.hpp"
27 #include "raul/AtomicPtr.hpp"
28 #include "raul/Deletable.hpp"
29 
30 namespace Raul {
31 
32 
40 template <typename T>
41 class List : public Raul::Deletable, public boost::noncopyable
42 {
43 public:
44 
51  class Node : public Raul::Deletable {
52  public:
53  explicit Node(T elem) : _elem(elem) {}
54  virtual ~Node() {}
55 
56  template <typename Y>
57  explicit Node(const typename List<Y>::Node& copy)
58  : _elem(copy._elem), _prev(copy._prev), _next(copy._next)
59  {}
60 
61  Node* prev() const { return _prev.get(); }
62  void prev(Node* ln) { _prev = ln; }
63  Node* next() const { return _next.get(); }
64  void next(Node* ln) { _next = ln; }
65  T& elem() { return _elem;}
66  const T& elem() const { return _elem; }
67 
68  private:
69  T _elem;
70  AtomicPtr<Node> _prev;
71  AtomicPtr<Node> _next;
72  };
73 
74 
75  List(size_t size=0, Node* head=NULL, Node* tail=NULL)
76  : _size(size)
77  , _end_iter(this)
78  , _const_end_iter(this)
79  {
80  _head = head;
81  _tail = tail;
82  _end_iter._listnode = NULL;
83  _const_end_iter._listnode = NULL;
84  }
85 
86  ~List();
87 
88  void push_back(Node* elem);
89  void push_back(T& elem);
90 
91  void append(List<T>& list);
92 
93  void clear();
94 
96  unsigned size() const { return static_cast<unsigned>(_size.get()); }
97 
99  bool empty() { return (_head.get() == NULL); }
100 
101  class iterator;
102 
105  public:
106  explicit const_iterator(const List<T>* const list);
107  const_iterator(const iterator& i)
108  : _list(i._list), _listnode(i._listnode) {}
109 
110  inline const T& operator*();
111  inline const T* operator->();
112  inline const_iterator& operator++();
113  inline bool operator!=(const const_iterator& iter) const;
114  inline bool operator!=(const iterator& iter) const;
115  inline bool operator==(const const_iterator& iter) const;
116  inline bool operator==(const iterator& iter) const;
117 
118  inline typename List<T>::Node* node() { return _listnode; }
119  inline const typename List<T>::Node* node() const { return _listnode; }
120 
121  friend class List<T>;
122 
123  private:
124  const List<T>* _list;
125  const typename List<T>::Node* _listnode;
126  };
127 
128 
130  class iterator {
131  public:
132  explicit iterator(List<T>* const list);
133 
134  inline T& operator*();
135  inline T* operator->();
136  inline iterator& operator++();
137  inline bool operator!=(const iterator& iter) const;
138  inline bool operator!=(const const_iterator& iter) const;
139  inline bool operator==(const iterator& iter) const;
140  inline bool operator==(const const_iterator& iter) const;
141 
142  friend class List<T>;
143  friend class List<T>::const_iterator;
144 
145  private:
146  const List<T>* _list;
147  typename List<T>::Node* _listnode;
148  };
149 
150  void chop_front(List<T>& front, size_t front_size, Node* front_tail);
151 
152  Node* erase(const iterator iter);
153 
154  iterator find(const T& val);
155 
156  iterator begin();
157  const_iterator begin() const;
158  const iterator end() const;
159 
160  T& front() { return *begin(); }
161  const T& front() const { return *begin(); }
162 
163  Node* head() { return _head.get(); }
164  const Node* head() const { return _head.get(); }
165 
166 private:
167  AtomicPtr<Node> _head;
168  AtomicPtr<Node> _tail;
169  AtomicInt _size;
170  iterator _end_iter;
171  const_iterator _const_end_iter;
172 };
173 
174 
175 } // namespace Raul
176 
177 #endif // RAUL_LIST_HPP
178 
179 #include "ListImpl.hpp"
180 
Something with a virtual destructor.
Definition: Deletable.hpp:28
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:130
A node in a List.
Definition: List.hpp:51
Atomic pointer.
Definition: AtomicPtr.hpp:30
Definition: Array.hpp:26
A realtime safe, (partially) thread safe doubly-linked list.
Definition: List.hpp:41
void append(List< T > &list)
Append a list to this list.
Definition: ListImpl.hpp:119
Atomic integer.
Definition: AtomicInt.hpp:29
Node * erase(const iterator iter)
Remove an element from the list using an iterator.
Definition: ListImpl.hpp:177
Realtime safe const iterator for a List.
Definition: List.hpp:104
void push_back(Node *elem)
Realtime Safe.
Definition: ListImpl.hpp:61
bool empty()
Valid for any thread.
Definition: List.hpp:99
iterator find(const T &val)
Find an element in the list.
Definition: ListImpl.hpp:158
unsigned size() const
Valid only in the write thread.
Definition: List.hpp:96