RAUL
0.8.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 00024 #include <boost/utility.hpp> 00025 00026 #include "raul/AtomicInt.hpp" 00027 #include "raul/AtomicPtr.hpp" 00028 #include "raul/Deletable.hpp" 00029 00030 namespace Raul { 00031 00032 00040 template <typename T> 00041 class List : public Raul::Deletable, public boost::noncopyable 00042 { 00043 public: 00044 00051 class Node : public Raul::Deletable { 00052 public: 00053 explicit Node(T elem) : _elem(elem) {} 00054 virtual ~Node() {} 00055 00056 template <typename Y> 00057 explicit Node(const typename List<Y>::Node& copy) 00058 : _elem(copy._elem), _prev(copy._prev), _next(copy._next) 00059 {} 00060 00061 Node* prev() const { return _prev.get(); } 00062 void prev(Node* ln) { _prev = ln; } 00063 Node* next() const { return _next.get(); } 00064 void next(Node* ln) { _next = ln; } 00065 T& elem() { return _elem;} 00066 const T& elem() const { return _elem; } 00067 00068 private: 00069 T _elem; 00070 AtomicPtr<Node> _prev; 00071 AtomicPtr<Node> _next; 00072 }; 00073 00074 00075 List(size_t size=0, Node* head=NULL, Node* tail=NULL) 00076 : _size(size) 00077 , _end_iter(this) 00078 , _const_end_iter(this) 00079 { 00080 _head = head; 00081 _tail = tail; 00082 _end_iter._listnode = NULL; 00083 _const_end_iter._listnode = NULL; 00084 } 00085 00086 ~List(); 00087 00088 void push_back(Node* elem); 00089 void push_back(T& elem); 00090 00091 void append(List<T>& list); 00092 00093 void clear(); 00094 00096 unsigned size() const { return static_cast<unsigned>(_size.get()); } 00097 00099 bool empty() { return (_head.get() == NULL); } 00100 00101 class iterator; 00102 00104 class const_iterator { 00105 public: 00106 explicit const_iterator(const List<T>* const list); 00107 const_iterator(const iterator& i) 00108 : _list(i._list), _listnode(i._listnode) {} 00109 00110 inline const T& operator*(); 00111 inline const T* operator->(); 00112 inline const_iterator& operator++(); 00113 inline bool operator!=(const const_iterator& iter) const; 00114 inline bool operator!=(const iterator& iter) const; 00115 inline bool operator==(const const_iterator& iter) const; 00116 inline bool operator==(const iterator& iter) const; 00117 00118 inline typename List<T>::Node* node() { return _listnode; } 00119 inline const typename List<T>::Node* node() const { return _listnode; } 00120 00121 friend class List<T>; 00122 00123 private: 00124 const List<T>* _list; 00125 const typename List<T>::Node* _listnode; 00126 }; 00127 00128 00130 class iterator { 00131 public: 00132 explicit iterator(List<T>* const list); 00133 00134 inline T& operator*(); 00135 inline T* operator->(); 00136 inline iterator& operator++(); 00137 inline bool operator!=(const iterator& iter) const; 00138 inline bool operator!=(const const_iterator& iter) const; 00139 inline bool operator==(const iterator& iter) const; 00140 inline bool operator==(const const_iterator& iter) const; 00141 00142 friend class List<T>; 00143 friend class List<T>::const_iterator; 00144 00145 private: 00146 const List<T>* _list; 00147 typename List<T>::Node* _listnode; 00148 }; 00149 00150 void chop_front(List<T>& front, size_t front_size, Node* front_tail); 00151 00152 Node* erase(const iterator iter); 00153 00154 iterator find(const T& val); 00155 00156 iterator begin(); 00157 const_iterator begin() const; 00158 const iterator end() const; 00159 00160 T& front() { return *begin(); } 00161 const T& front() const { return *begin(); } 00162 00163 Node* head() { return _head.get(); } 00164 const Node* head() const { return _head.get(); } 00165 00166 private: 00167 AtomicPtr<Node> _head; 00168 AtomicPtr<Node> _tail; 00169 AtomicInt _size; 00170 iterator _end_iter; 00171 const_iterator _const_end_iter; 00172 }; 00173 00174 00175 } // namespace Raul 00176 00177 #endif // RAUL_LIST_HPP 00178 00179 #include "ListImpl.hpp" 00180