Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | 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 Thu Jun 16 16:18:12 2005 for s11n by  doxygen 1.4.3-20050530