RAUL 0.7.0
|
00001 /* This file is part of Raul. 00002 * Copyright (C) 2007-2009 David Robillard <http://drobilla.net> 00003 * 00004 * Raul is free software; you can redistribute it and/or modify it under the 00005 * terms of the GNU General Public License as published by the Free Software 00006 * Foundation; either version 2 of the License, or (at your option) any later 00007 * version. 00008 * 00009 * Raul is distributed in the hope that it will be useful, but WITHOUT ANY 00010 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 00011 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. 00012 * 00013 * You should have received a copy of the GNU General Public License along 00014 * with this program; if not, write to the Free Software Foundation, Inc., 00015 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00016 */ 00017 00018 #ifndef RAUL_LIST_HPP 00019 #define RAUL_LIST_HPP 00020 00021 #include <cstddef> 00022 #include <cassert> 00023 #include <boost/utility.hpp> 00024 #include "raul/Deletable.hpp" 00025 #include "raul/AtomicPtr.hpp" 00026 #include "raul/AtomicInt.hpp" 00027 00028 namespace Raul { 00029 00030 00037 template <typename T> 00038 class List : public Raul::Deletable, public boost::noncopyable 00039 { 00040 public: 00041 00048 class Node : public Raul::Deletable { 00049 public: 00050 Node(T elem) : _elem(elem) {} 00051 virtual ~Node() {} 00052 00053 template <typename Y> 00054 Node(const typename List<Y>::Node& copy) 00055 : _elem(copy._elem), _prev(copy._prev), _next(copy._next) 00056 {} 00057 00058 Node* prev() const { return _prev.get(); } 00059 void prev(Node* ln) { _prev = ln; } 00060 Node* next() const { return _next.get(); } 00061 void next(Node* ln) { _next = ln; } 00062 T& elem() { return _elem;} 00063 const T& elem() const { return _elem; } 00064 00065 private: 00066 T _elem; 00067 AtomicPtr<Node> _prev; 00068 AtomicPtr<Node> _next; 00069 }; 00070 00071 00072 List(size_t size=0, Node* head=NULL, Node* tail=NULL) 00073 : _size(size) 00074 , _end_iter(this) 00075 , _const_end_iter(this) 00076 { 00077 _head = head; 00078 _tail = tail; 00079 _end_iter._listnode = NULL; 00080 _const_end_iter._listnode = NULL; 00081 } 00082 00083 ~List(); 00084 00085 void push_back(Node* elem); 00086 void push_back(T& elem); 00087 00088 void append(List<T>& list); 00089 00090 void clear(); 00091 00093 unsigned size() const { return static_cast<unsigned>(_size.get()); } 00094 00096 bool empty() { return (_head.get() == NULL); } 00097 00098 class iterator; 00099 00101 class const_iterator { 00102 public: 00103 const_iterator(const List<T>* const list); 00104 const_iterator(const iterator& i) 00105 : _list(i._list), _listnode(i._listnode) {} 00106 00107 inline const T& operator*(); 00108 inline const T* operator->(); 00109 inline const_iterator& operator++(); 00110 inline bool operator!=(const const_iterator& iter) const; 00111 inline bool operator!=(const iterator& iter) const; 00112 inline bool operator==(const const_iterator& iter) const; 00113 inline bool operator==(const iterator& iter) const; 00114 00115 inline typename List<T>::Node* node() { return _listnode; } 00116 inline const typename List<T>::Node* node() const { return _listnode; } 00117 00118 friend class List<T>; 00119 00120 private: 00121 const List<T>* _list; 00122 const typename List<T>::Node* _listnode; 00123 }; 00124 00125 00127 class iterator { 00128 public: 00129 iterator(List<T>* const list); 00130 00131 inline T& operator*(); 00132 inline T* operator->(); 00133 inline iterator& operator++(); 00134 inline bool operator!=(const iterator& iter) const; 00135 inline bool operator!=(const const_iterator& iter) const; 00136 inline bool operator==(const iterator& iter) const; 00137 inline bool operator==(const const_iterator& iter) const; 00138 00139 friend class List<T>; 00140 friend class List<T>::const_iterator; 00141 00142 private: 00143 const List<T>* _list; 00144 typename List<T>::Node* _listnode; 00145 }; 00146 00147 void chop_front(List<T>& front, size_t front_size, Node* new_head); 00148 00149 Node* erase(const iterator iter); 00150 00151 iterator find(const T& val); 00152 00153 iterator begin(); 00154 const_iterator begin() const; 00155 const iterator end() const; 00156 00157 T& front() { return *begin(); } 00158 const T& front() const { return *begin(); } 00159 00160 Node* head() { return _head.get(); } 00161 const Node* head() const { return _head.get(); } 00162 00163 private: 00164 AtomicPtr<Node> _head; 00165 AtomicPtr<Node> _tail; 00166 AtomicInt _size; 00167 iterator _end_iter; 00168 const_iterator _const_end_iter; 00169 }; 00170 00171 00172 } // namespace Raul 00173 00174 #endif // RAUL_LIST_HPP 00175 00176 #include "ListImpl.hpp" 00177