Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members

pointer_list.h

00001 // Author: stephan beal <stephan@s11n.net> 00002 // License: Public Domain 00003 #ifndef s11n_POINTERLIST_H_INCLUDED 00004 #define s11n_POINTERLIST_H_INCLUDED 00005 #include <string> 00006 #include <list> 00007 #include <map> 00008 #define POINTERLIST_USES_VECTOR 0 // define to true if you want to use a vector instead of a list (should be a bit faster?) 00009 #if POINTERLIST_USES_VECTOR 00010 # include <vector> 00011 #else 00012 # include <list> 00013 #endif 00014 00015 namespace s11n 00016 { 00017 using namespace std; 00018 00019 /** 00020 pointer_list is a simple template class for a container of pointers 00021 to T, plus some memory management features. 00022 00023 It's usage is STL-like. 00024 00025 Parameterized on: 00026 00027 - ChildType: the type of object to hold pointers to. 00028 00029 pointer_lists with auto_delete(true) often make useful ad-hoc 00030 poor-man's garbage collectors. 00031 00032 Known caveats: 00033 00034 Inserting the same pointer into the same list multiple 00035 times is fatal if the list's auto_delete() is enabled. It 00036 will crash in the list's dtor when it deletes the pointer 00037 twice. Multiple pointers to the same object are allowed 00038 because the STL containers allow it, and i want to conform 00039 with that basic behaviour. 00040 */ 00041 template < class ChildType > class pointer_list 00042 { 00043 public: 00044 /** 00045 A typedef to make the rest of the implementation easier to write. 00046 */ 00047 typedef pointer_list < ChildType > ThisType; 00048 00049 /** 00050 value_type defines the child type of this list. Note 00051 that it is a pointer type (because this is a /pointer 00052 list/ ;), so don't be confused by constructs like: 00053 00054 value_type objptr = 0; 00055 00056 (note the distinct lack of a *). 00057 00058 This odd definition is required for compatibility 00059 with std::vector and std::list. i would prefer to 00060 define it without the *. :/ 00061 */ 00062 typedef ChildType *value_type; 00063 00064 /** 00065 list_type is the type of underlying pointer 00066 container. 00067 */ 00068 #if POINTERLIST_USES_VECTOR 00069 typedef std::vector < value_type > list_type; 00070 #else 00071 typedef std::list < value_type > list_type; 00072 #endif 00073 00074 /** 00075 iterator which can be dereferenced to a (value_type *). 00076 */ 00077 typedef typename list_type::iterator iterator; 00078 00079 /** 00080 const iterator which can be dereferenced to a (value_type *). 00081 */ 00082 typedef typename list_type::const_iterator const_iterator; 00083 00084 00085 /** 00086 Creates a pointer_list with the given auto_delete policy. 00087 */ 00088 pointer_list( bool autodel = false ):m_autodel( autodel ) 00089 { 00090 } 00091 00092 /** 00093 Deletes all child pointers if this->auto_delete(). 00094 */ 00095 virtual ~pointer_list() 00096 { 00097 if ( this->auto_delete() ) this->delete_all(); 00098 } 00099 00100 /** 00101 If auto_delete() is true then all objects in this 00102 list will be deleted when this object dies or when 00103 erase() is called. Autodelete is false by default. 00104 */ 00105 bool auto_delete() const 00106 { 00107 return this->m_autodel; 00108 } 00109 00110 /** 00111 Sets the autodelete policy. See auto_delete(). 00112 */ 00113 void auto_delete( bool autodel ) 00114 { 00115 this->m_autodel = autodel; 00116 } 00117 00118 00119 /** 00120 Return a const iterator for the first element in 00121 this container. 00122 */ 00123 typename ThisType::const_iterator begin() const 00124 { 00125 return this->list.begin(); 00126 } 00127 00128 /** 00129 Return an iterator pointing to the first element in 00130 this container. 00131 */ 00132 typename ThisType::iterator begin() 00133 { 00134 return this->list.begin(); 00135 } 00136 00137 /** 00138 Return the after-the-end iterator. 00139 */ 00140 typename ThisType::const_iterator end() const 00141 { 00142 return this->list.end(); 00143 } 00144 00145 /** 00146 Return the after-the-end iterator. 00147 */ 00148 typename ThisType::iterator end() 00149 { 00150 return this->list.end(); 00151 } 00152 00153 00154 /** 00155 Returns an iterator pointing to the given pointer, 00156 or end() if this object does not contain that 00157 pointer. 00158 */ 00159 typename ThisType::iterator find( typename ThisType::value_type a ) 00160 { 00161 typename ThisType::iterator iter = list.begin(); 00162 typename ThisType::iterator enditer = list.end(); 00163 for ( ; iter != enditer; ++iter ) 00164 { 00165 if ( ( *iter ) == a ) 00166 { 00167 //LIBE_CERR << "find( " << a << " ) found " << (*iter) << endl; 00168 return iter; 00169 } 00170 } 00171 return list.end(); 00172 } 00173 00174 00175 /** 00176 Returns the number of child pointers in this list. 00177 */ 00178 unsigned long count() const 00179 { 00180 return ( unsigned long ) this->list.size(); // i hope that's implemented constant-time. C++ Standard doesn't define performance on ::std::list::size(). 00181 } 00182 /** 00183 Same as count(). 00184 */ 00185 unsigned long size() const 00186 { 00187 return ( unsigned long ) this->list.size(); 00188 } 00189 00190 /** 00191 Adds the given pointer to the list. If front == true then the pointer 00192 is added to the front of the list, else the end of the list. 00193 00194 If the pointer is NULL then this function does nothing. 00195 00196 Returns the pointer passed to it. 00197 */ 00198 typename ThisType::value_type add( typename ThisType::value_type a, bool front = false ) 00199 { 00200 if ( !a ) 00201 return NULL; 00202 if ( !front ) 00203 list.push_back( a ); 00204 else 00205 { 00206 #if POINTERLIST_USES_VECTOR 00207 list.insert( list.begin(), a ); 00208 #else 00209 list.push_front( a ); 00210 #endif 00211 } 00212 return a; 00213 } 00214 00215 /** 00216 For STL compatibility. 00217 00218 Adds an entry to the back of this list. 00219 */ 00220 typename ThisType::value_type push_back( typename ThisType::value_type a ) 00221 { 00222 return this->add( a, false ); 00223 } 00224 00225 /** 00226 For STL compatibility. 00227 00228 Adds an entry to the front of this list. 00229 */ 00230 typename ThisType::value_type push_front( typename ThisType::value_type a ) 00231 { 00232 return this->add( a, true ); 00233 } 00234 00235 00236 /** 00237 Defines the deletion policies recognized by remove(). 00238 */ 00239 enum DeletionPolicy 00240 { 00241 /** 00242 Use the policy set in <code>auto_delete()</code>. 00243 */ 00244 CheckAutoDelete = -1, 00245 /** 00246 Do not delete object. 00247 */ 00248 DoNotDelete = 0, 00249 /** 00250 Delete object. 00251 */ 00252 Delete = 1 00253 }; 00254 00255 /** 00256 Removes the given pointer from this list, assuming 00257 it contains the pointer. If the pointer is NULL or 00258 the list does not contain the entry, it returns 00259 NULL, otherwise it returns the pointer passed to 00260 it. 00261 00262 The passed-in pointer may or may not be deleted, 00263 depending on the value of deletionPolicy: 00264 00265 - CheckAutoDelete (-1, default) == check auto_delete() and do whatever 00266 that says. 00267 00268 - DoNotDelete (0) == do not delete 00269 00270 - Delete (1) == delete, regardless of auto_delete() 00271 00272 Obviously, if this function deletes the pointer 00273 then it will return NULL. 00274 */ 00275 typename ThisType::value_type remove( typename ThisType::value_type a, DeletionPolicy deletionPolicy = CheckAutoDelete ) 00276 { 00277 // todo: try to replace this stuff with: 00278 // std::remove_if( begin(), end(), std::equal_to<value_type>() ); 00279 if ( !a ) 00280 return NULL; 00281 typename ThisType::iterator iter = list.begin(); 00282 while ( iter != list.end() ) 00283 { 00284 if ( ( *iter ) == a ) 00285 { 00286 list.erase( iter ); 00287 if ( deletionPolicy > 0 || ( ( deletionPolicy == -1 ) && this->auto_delete() ) ) 00288 { 00289 delete( a ); 00290 return NULL; 00291 } 00292 return a; 00293 } 00294 ++iter; 00295 } 00296 return NULL; 00297 } 00298 00299 /** 00300 For STL compatibility. 00301 00302 if ( this->auto_delete() ) then (*it) is deleted. 00303 00304 */ 00305 void erase( ThisType::iterator it ) 00306 { 00307 if ( this->m_autodel ) delete( *it ); 00308 this->list.erase( it ); 00309 } 00310 00311 /** 00312 For STL compatibility. 00313 00314 if ( this->auto_delete() ) then the pointers in (*it) are deleted. 00315 00316 TODO: validate that the iterators are guaranteed to 00317 be valid after list_type::erase() is called! 00318 */ 00319 void erase( ThisType::iterator begin, ThisType::iterator end ) 00320 { 00321 for( ; begin != end; ++begin ) 00322 { 00323 if( this->m_autodel ) delete( *begin ); 00324 this->list.erase( begin ); 00325 } 00326 } 00327 00328 /** 00329 For STL compatibility. Calls erase( begin(), end() ). 00330 */ 00331 void clear() 00332 { 00333 this->erase( this->begin(), this->end() ); 00334 } 00335 00336 /** 00337 Deletes all children, irrespective of auto_delete(). 00338 */ 00339 void delete_all() 00340 { 00341 typedef std::map < typename ThisType::value_type, int > Protector; 00342 typename ThisType::value_type ptr; 00343 #define POINTER_LIST_SAFE_DELETE 0 00344 #if POINTER_LIST_SAFE_DELETE // causes a hang sometimes. See below. 00345 Protector delmap; // to avoid multi-deletes. 00346 #endif 00347 typename ThisType::iterator iter = list.begin(); 00348 typename ThisType::iterator eter = list.end(); 00349 for( ; iter != eter; ++iter ) 00350 { 00351 ptr = ( *iter ); 00352 #if POINTER_LIST_SAFE_DELETE 00353 if ( delmap.end() != delmap.find(ptr) ) continue; // hangs on the comparison sometimes! 00354 delmap[ptr] = 0; 00355 #endif 00356 delete( ptr ); 00357 } 00358 list.clear(); 00359 #undef POINTER_LIST_SAFE_DELETE 00360 } 00361 00362 /** 00363 Returns true if this list contains a. 00364 */ 00365 virtual bool contains( typename ThisType::value_type a ) 00366 { 00367 return this->list.end() != this->find( a ); 00368 } 00369 00370 00371 private: 00372 pointer_list( const ThisType & ); // intentionally unimplemented. 00373 ThisType & operator=( const ThisType & ); // intentionally unimplemented. 00374 bool m_autodel; 00375 list_type list; 00376 00377 }; // class pointer_list 00378 } // namespace 00379 00380 /*** 00381 These ostream operators are only useful for debuggering. 00382 */ 00383 using s11n::pointer_list; 00384 template < class Type > std::ostream & operator<<( std::ostream & os, const pointer_list < Type > &obj ) 00385 { 00386 typename pointer_list < Type >::const_iterator citer = obj.begin(); 00387 os << "pointer_list@" << std::hex << &obj << ":"; 00388 for ( ; citer != obj.end(); ++citer ) 00389 { 00390 os << " ptr["; 00391 os << std::hex << ( *citer ); 00392 os << "]"; 00393 } 00394 return os; 00395 } 00396 00397 /** 00398 Adds the given T pointer to the given pointer_list<T>. 00399 */ 00400 template < class Type > 00401 s11n::pointer_list < Type > & operator +=( s11n::pointer_list < Type > &el, Type * ptr ) 00402 { 00403 el.add( ptr ); 00404 return el; 00405 } 00406 00407 00408 /** 00409 Removes the given T pointer using pointer_list<T>::remove(). 00410 */ 00411 template < class Type > 00412 s11n::pointer_list < Type > & operator -=( s11n::pointer_list < Type > &el, Type * ptr ) 00413 { 00414 el.remove( ptr ); 00415 return el; 00416 } 00417 00418 #endif // s11n_POINTERLIST_H_INCLUDED

Generated on Wed Jul 28 16:04:14 2004 for s11n by doxygen 1.3.7