00001 # if ! defined(TS_INTRUSIVE_DOUBLE_LIST_HEADER) 00002 # define TS_INTRUSIVE_DOUBLE_LIST_HEADER 00003 00004 /** @file 00005 00006 Intrusive double linked list container. 00007 00008 This provide support for a doubly linked list container for an 00009 arbitrary class that uses the class directly and not wrapped. It 00010 requires the class to provide the list pointers. 00011 00012 @note This is a header only library. 00013 00014 @note Due to bugs in either the C++ standard or gcc (or both), the 00015 link members @b must be declared in the class used for the 00016 list. If they are declared in a super class you will get "could 00017 not convert template argument" errors, even though it should 00018 work. This is because @c &T::m is of type @c S::* if @c S is a 00019 super class of @c T and @c m is declared in @c S. My view is that 00020 if I write "&T::m" I want a "T::*" and the compiler shouldn't go 00021 rummaging through the class hierarchy for some other type. For 00022 MSVC you can @c static_cast the template arguments as a 00023 workaround, but not in gcc. 00024 00025 @section license License 00026 00027 Licensed to the Apache Software Foundation (ASF) under one 00028 or more contributor license agreements. See the NOTICE file 00029 distributed with this work for additional information 00030 regarding copyright ownership. The ASF licenses this file 00031 to you under the Apache License, Version 2.0 (the 00032 "License"); you may not use this file except in compliance 00033 with the License. You may obtain a copy of the License at 00034 00035 http://www.apache.org/licenses/LICENSE-2.0 00036 00037 Unless required by applicable law or agreed to in writing, software 00038 distributed under the License is distributed on an "AS IS" BASIS, 00039 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00040 See the License for the specific language governing permissions and 00041 limitations under the License. 00042 00043 */ 00044 00045 # if USE_STL 00046 # include <iterator> 00047 # else 00048 namespace std { 00049 struct bidirectional_iterator_tag; 00050 } 00051 # endif 00052 00053 /** Intrusive doubly linked list container. 00054 00055 This holds items in a doubly linked list using members of the 00056 items. Elements are copied in to the list. No memory management 00057 is done by the list implementation. 00058 00059 To use this class a client should create the structure for 00060 elements of the list and ensure that it has two self pointers to 00061 be used by the list. For example, 00062 00063 @code 00064 struct Elt { 00065 int _payload; 00066 Elt* _next; 00067 Elt* _prev; 00068 }; 00069 @endcode 00070 00071 The list is declared as 00072 @code 00073 typedef IntrusiveDList<Elt, &Elt::_next, &Elt::_prev> EltList; 00074 @endcode 00075 00076 An element can be in multiple types of lists simultaneously as 00077 long as each list type uses distinct members. It is not possible 00078 for an element to be in more than one list of the same type 00079 simultaneously. This is intrinsic to intrusive list support. 00080 00081 Element access is done by using either STL style iteration, or 00082 direct access to the member pointers. A client can have its own 00083 mechanism for getting an element to start, or use the @c getHead 00084 and/or @c getTail methods to get the first and last elements in 00085 the list respectively. 00086 00087 @note Due to bugs in various compilers or the C++ specification 00088 (or both) it is not possible in general to declare the element 00089 pointers in a super class. The template argument @c T must be 00090 exactly the same @c T as for the element pointers, even though a 00091 pointer to member of a superclass should be trivially coerced to a 00092 pointer to member of subclass. MSVC permits an explicit cast in 00093 this case, but gcc does not and therefore there is no way to do 00094 this. It is most vexing. 00095 00096 P.S. I think it's a compiler bug personally with regard to the 00097 type of an expression of the form @c &T::M is not @c T::* if @c M 00098 is declared in a superclass S. In that case the type is @c S::* 00099 which seems very wrong to me. 00100 00101 */ 00102 template < 00103 typename T, ///< Type of list element. 00104 T* (T::*N), ///< Member to use for pointer to next element. 00105 T* (T::*P) ///< Member to use for pointer to previous element. 00106 > class IntrusiveDList { 00107 friend class iterator; 00108 public: 00109 typedef IntrusiveDList self; ///< Self reference type. 00110 typedef T element_type; ///< Type of list element. 00111 /** STL style iterator for access to elements. 00112 */ 00113 class iterator { 00114 friend class IntrusiveDList; 00115 public: 00116 typedef iterator self; ///< Self reference type. 00117 typedef T value_type; ///< Referenced type for iterator. 00118 typedef int difference_type; ///< Distance type. 00119 typedef T* pointer; ///< Pointer to referent. 00120 typedef T& reference; ///< Reference to referent. 00121 typedef std::bidirectional_iterator_tag iterator_category; 00122 00123 /// Default constructor. 00124 iterator() : _list(0), _elt(0) {} 00125 /// Equality test. 00126 /// @return @c true if @c this and @a that refer to the same object. 00127 bool operator==(self const& that) const { 00128 return _list == that._list && _elt == that._elt; 00129 } 00130 /// Pre-increment. 00131 /// Move to the next element in the list. 00132 /// @return The iterator. 00133 self& operator++() { 00134 if (_elt) _elt = _elt->*N; 00135 return *this; 00136 } 00137 /// Pre-decrement. 00138 /// Move to the previous element in the list. 00139 /// @return The iterator. 00140 self& operator--() { 00141 if (_elt) _elt = _elt->*P; 00142 else if (_list) _elt = _list->_tail; 00143 return *this; 00144 } 00145 /// Post-increment. 00146 /// Move to the next element in the list. 00147 /// @return The iterator value before the increment. 00148 self operator++(int) { 00149 self tmp(*this); 00150 ++*this; 00151 return tmp; 00152 } 00153 /// Post-decrement. 00154 /// Move to the previous element in the list. 00155 /// @return The iterator value before the decrement. 00156 self operator--(int) { 00157 self tmp(*this); 00158 ++*this; 00159 return tmp; 00160 } 00161 /// Inequality test. 00162 /// @return @c true if @c this and @a do not refer to the same object. 00163 bool operator!=(self const& that) const { return !(*this == that); } 00164 /// Dereference. 00165 /// @return A reference to the referent. 00166 reference operator*() { return *_elt; } 00167 /// Dereference. 00168 /// @return A pointer to the referent. 00169 pointer operator->() { return _elt; } 00170 protected: 00171 IntrusiveDList* _list; ///< List for this iterator. 00172 T* _elt; ///< Referenced element. 00173 /// Internal constructor for containers. 00174 iterator( 00175 IntrusiveDList* container, ///< Container for iteration. 00176 T* elt ///< Initial referent 00177 ) : _list(container), _elt(elt) { 00178 } 00179 }; 00180 00181 /// Default constructor (empty list). 00182 IntrusiveDList() : _head(0), _tail(0), _count(0) { } 00183 /// Empty check. 00184 /// @return @c true if the list is empty. 00185 bool isEmpty() const { return 0 == _head; } 00186 /// Add @a elt as the first element in the list. 00187 /// @return This container. 00188 self& prepend( 00189 T* elt ///< Element to add. 00190 ) { 00191 elt->*N = _head; 00192 elt->*P = 0; 00193 if (_head) _head->*P = elt; 00194 _head = elt; 00195 if (! _tail) _tail = _head; // empty to non-empty transition 00196 ++_count; 00197 return *this; 00198 } 00199 /// Add @elt as the last element in the list. 00200 /// @return This container. 00201 self& append( 00202 T* elt ///< Element to add. 00203 ) { 00204 elt->*N = 0; 00205 elt->*P = _tail; 00206 if (_tail) _tail->*N = elt; 00207 _tail = elt; 00208 if (! _head) _head = _tail; // empty to non-empty transition 00209 ++_count; 00210 return *this; 00211 } 00212 /// Remove the first element of the list. 00213 /// @return A poiner to the removed item, or @c NULL if the list was empty. 00214 T* takeHead() { 00215 T* zret = 0; 00216 if (_head) { 00217 zret = _head; 00218 _head = _head->*N; 00219 if (_head) _head->*P = 0; 00220 else _tail = 0; // non-empty to empty transition. 00221 zret->*N = 0; // erase traces of list. 00222 zret->*P = 0; 00223 --_count; 00224 } 00225 return zret; 00226 } 00227 /// Remove the last element of the list. 00228 /// @return A poiner to the removed item, or @c NULL if the list was empty. 00229 T* takeTail() { 00230 T* zret = 0; 00231 if (_tail) { 00232 zret = _tail; 00233 _tail = _tail->*P = 0; 00234 if (_tail) _tail->*N = 0; 00235 else _head = 0; // non-empty to empty transition. 00236 zret->*N = 0; // erase traces of list. 00237 zret->*P = 0; 00238 --_count; 00239 } 00240 return zret; 00241 } 00242 /// Insert a new element @a elt after @a target. 00243 /// The caller is responsible for ensuring @a target is in this list 00244 /// and @a elt is not in a list. 00245 /// @return This list. 00246 self& insertAfter( 00247 T* target, ///< Target element in list. 00248 T* elt ///< Element to insert. 00249 ) { 00250 // Should assert that !(elt->*N || elt->*P) 00251 elt->*N = target->*N; 00252 elt->*P = target; 00253 target->*N = elt; 00254 if (elt->*N) elt->*N->*P = elt; 00255 if (target == _tail) _tail = elt; 00256 ++_count; 00257 return *this; 00258 } 00259 /// Insert a new element @a elt before @a target. 00260 /// The caller is responsible for ensuring @a target is in this list 00261 /// and @a elt is not in a list. 00262 /// @return This list. 00263 self& insertBefore( 00264 T* target, ///< Target element in list. 00265 T* elt ///< Element to insert. 00266 ) { 00267 // Should assert that !(elt->*N || elt->*P) 00268 elt->*P = target->*P; 00269 elt->*N = target; 00270 target->*P = elt; 00271 if (elt->*P) elt->*P->*N = elt; 00272 if (target == _head) _head = elt; 00273 ++_count; 00274 return *this; 00275 } 00276 /// Take @a elt out of this list. 00277 /// @return This list. 00278 self& take( 00279 T* elt ///< Element to remove. 00280 ) { 00281 if (elt->*P) elt->*P->*N = elt->*N; 00282 if (elt->*N) elt->*N->*P = elt->*P; 00283 if (elt == _head) _head = elt->*N; 00284 if (elt == _tail) _tail = elt->*P; 00285 elt->*P = elt->*N = 0; 00286 --_count; 00287 return *this; 00288 } 00289 /// Remove all elements. 00290 /// @note @b No memory management is done! 00291 /// @return This container. 00292 self& clear() { _head = _tail = 0; _count = 0; return *this; } 00293 /// @return Number of elements in the list. 00294 size_t getCount() const { return _count; } 00295 00296 /// Get an iterator to the first element. 00297 iterator begin() { return iterator(this, _head); } 00298 /// Get an iterator to past the last element. 00299 iterator end() { return iterator(this, 0); } 00300 /// Get the first element. 00301 T* getHead() { return _head; } 00302 /// Get the last element. 00303 T* getTail() { return _tail; } 00304 protected: 00305 T* _head; ///< First element in list. 00306 T* _tail; ///< Last element in list. 00307 size_t _count; ///< # of elements in list. 00308 }; 00309 00310 # endif // TS_INTRUSIVE_DOUBLE_LIST_HEADER 00311
1.7.1