From f01674e99a467e9eb99323130a1e1add4c57eda2 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Fri, 14 Aug 2009 21:22:03 +0000 Subject: Massive freaking changes!!! Bu:;SharedCore actually is in and works, it's well tested and there are no known memory leaks or violations as of now. It's been applied to Bu::List and Bu::FBasicString so far. This means that everything using Bu::List and Bu::FBasicString will be much, much faster and use considerably less memory. I still have plans to apply this to Hash and maybe a couple of other core classes. --- src/list.h | 373 ++++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 209 insertions(+), 164 deletions(-) (limited to 'src/list.h') diff --git a/src/list.h b/src/list.h index 934766b..d711a2e 100644 --- a/src/list.h +++ b/src/list.h @@ -10,7 +10,8 @@ #include #include "bu/exceptionbase.h" -#include "bu/util.h" +#include "bu/sharedcore.h" +//#include "bu/util.h" namespace Bu { @@ -22,6 +23,153 @@ namespace Bu ListLink *pPrev; }; + template + struct ListCore + { + typedef struct ListLink Link; + ListCore() : + pFirst( NULL ), + pLast( NULL ), + nSize( 0 ) + { } + Link *pFirst; + Link *pLast; + long nSize; + cmpfunc cmp; + linkalloc la; + valuealloc va; + + /** + * Append a value to the list. + *@param v (const value_type &) The value to append. + */ + void append( const value &v ) + { + Link *pNew = la.allocate( 1 ); + pNew->pValue = va.allocate( 1 ); + va.construct( pNew->pValue, v ); + nSize++; + if( pFirst == NULL ) + { + // Empty list + pFirst = pLast = pNew; + pNew->pNext = pNew->pPrev = NULL; + } + else + { + pNew->pNext = NULL; + pNew->pPrev = pLast; + pLast->pNext = pNew; + pLast = pNew; + } + } + + /** + * Prepend a value to the list. + *@param v (const value_type &) The value to prepend. + */ + void prepend( const value &v ) + { + Link *pNew = la.allocate( 1 ); + pNew->pValue = va.allocate( 1 ); + va.construct( pNew->pValue, v ); + nSize++; + if( pFirst == NULL ) + { + // Empty list + pFirst = pLast = pNew; + pNew->pNext = pNew->pPrev = NULL; + } + else + { + pNew->pNext = pFirst; + pNew->pPrev = NULL; + pFirst->pPrev = pNew; + pFirst = pNew; + } + } + + void clear() + { + Link *pCur = pFirst; + for(;;) + { + if( pCur == NULL ) break; + va.destroy( pCur->pValue ); + va.deallocate( pCur->pValue, 1 ); + Link *pTmp = pCur->pNext; + la.destroy( pCur ); + la.deallocate( pCur, 1 ); + pCur = pTmp; + } + pFirst = pLast = NULL; + nSize = 0; + } + + void insert( Link *pLink, const value &v ) + { + Link *pAfter = pLink; + if( pAfter == NULL ) + { + append( v ); + return; + } + Link *pPrev = pAfter->pPrev; + if( pPrev == NULL ) + { + prepend( v ); + return; + } + + Link *pNew = la.allocate( 1 ); + pNew->pValue = va.allocate( 1 ); + va.construct( pNew->pValue, v ); + nSize++; + + pNew->pNext = pAfter; + pNew->pPrev = pPrev; + pAfter->pPrev = pNew; + pPrev->pNext = pNew; + } + + /** + * Erase an item from the list. + *@param i (iterator) The item to erase. + */ + void erase( Link *pLink ) + { + Link *pCur = pLink; + if( pCur == NULL ) return; + Link *pPrev = pCur->pPrev; + if( pPrev == NULL ) + { + va.destroy( pCur->pValue ); + va.deallocate( pCur->pValue, 1 ); + pFirst = pCur->pNext; + la.destroy( pCur ); + la.deallocate( pCur, 1 ); + if( pFirst == NULL ) + pLast = NULL; + else + pFirst->pPrev = NULL; + nSize--; + } + else + { + va.destroy( pCur->pValue ); + va.deallocate( pCur->pValue, 1 ); + Link *pTmp = pCur->pNext; + la.destroy( pCur ); + la.deallocate( pCur, 1 ); + pPrev->pNext = pTmp; + if( pTmp != NULL ) + pTmp->pPrev = pPrev; + nSize--; + } + } + }; + /** * Linked list template container. This class is similar to the stl list * class except for a few minor changes. First, it doesn't mimic a stack or @@ -38,61 +186,46 @@ namespace Bu template, typename valuealloc=std::allocator, typename linkalloc=std::allocator > > - class List + class List : public SharedCore< struct ListCore > { private: typedef struct ListLink Link; typedef class List MyType; + typedef struct ListCore Core; + + protected: + using SharedCore< Core >::core; + using SharedCore< Core >::_hardCopy; + using SharedCore< Core >::_allocateCore; public: struct const_iterator; struct iterator; - List() : - pFirst( NULL ), - pLast( NULL ), - nSize( 0 ) + List() { } List( const MyType &src ) : - pFirst( NULL ), - pLast( NULL ), - nSize( 0 ) + SharedCore< Core >( src ) { - for( Link *pCur = src.pFirst; pCur; pCur = pCur->pNext ) - { - append( *pCur->pValue ); - } } ~List() { - clear(); - } - - /** - * Assignment operator. - *@param src (const MyType &) The list to assign to your list. - */ - MyType &operator=( const MyType &src ) - { - clear(); - for( Link *pCur = src.pFirst; pCur; pCur = pCur->pNext ) - { - append( *pCur->pValue ); - } - return *this; } MyType &operator+=( const value &v ) { + _hardCopy(); append( v ); return *this; } MyType &operator+=( const MyType &src ) { + _hardCopy(); append( src ); return *this; } @@ -102,67 +235,43 @@ namespace Bu */ void clear() { - Link *pCur = pFirst; - for(;;) - { - if( pCur == NULL ) break; - va.destroy( pCur->pValue ); - va.deallocate( pCur->pValue, 1 ); - Link *pTmp = pCur->pNext; - la.destroy( pCur ); - la.deallocate( pCur, 1 ); - pCur = pTmp; - } - pFirst = pLast = NULL; - nSize = 0; + _hardCopy(); + core->clear(); } void enqueue( const value &v ) { + _hardCopy(); append( v ); } value dequeue() { - value v = *pFirst->pValue; + // _hardCopy(); erase will call this for me + value v = *core->pFirst->pValue; erase( begin() ); return v; } - /** * Append a value to the list. *@param v (const value_type &) The value to append. */ void append( const value &v ) { - Link *pNew = la.allocate( 1 ); - pNew->pValue = va.allocate( 1 ); - va.construct( pNew->pValue, v ); - nSize++; - if( pFirst == NULL ) - { - // Empty list - pFirst = pLast = pNew; - pNew->pNext = pNew->pPrev = NULL; - } - else - { - pNew->pNext = NULL; - pNew->pPrev = pLast; - pLast->pNext = pNew; - pLast = pNew; - } + _hardCopy(); + core->append( v ); } void append( const MyType &rSrc ) { + _hardCopy(); for( typename MyType::const_iterator i = rSrc.begin(); i != rSrc.end(); i++ ) { - append( *i ); + core->append( *i ); } } @@ -172,23 +281,8 @@ namespace Bu */ void prepend( const value &v ) { - Link *pNew = la.allocate( 1 ); - pNew->pValue = va.allocate( 1 ); - va.construct( pNew->pValue, v ); - nSize++; - if( pFirst == NULL ) - { - // Empty list - pFirst = pLast = pNew; - pNew->pNext = pNew->pPrev = NULL; - } - else - { - pNew->pNext = pFirst; - pNew->pPrev = NULL; - pFirst->pPrev = pNew; - pFirst = pNew; - } + _hardCopy(); + core->prepend( v ); } /** @@ -197,37 +291,19 @@ namespace Bu */ void prepend( const MyType &rSrc ) { + _hardCopy(); for( typename MyType::const_iterator i = rSrc.begin(); i != rSrc.end(); i++ ) { - prepend( *i ); + core->prepend( *i ); } } void insert( MyType::iterator &i, const value &v ) { - Link *pAfter = i.pLink; - if( pAfter == NULL ) - { - append( v ); - return; - } - Link *pPrev = pAfter->pPrev; - if( pPrev == NULL ) - { - prepend( v ); - return; - } + _hardCopy(); - Link *pNew = la.allocate( 1 ); - pNew->pValue = va.allocate( 1 ); - va.construct( pNew->pValue, v ); - nSize++; - - pNew->pNext = pAfter; - pNew->pPrev = pPrev; - pAfter->pPrev = pNew; - pPrev->pNext = pNew; + core->insert( i.pLink, v ); } /** @@ -239,40 +315,27 @@ namespace Bu */ void insertSorted( const value &v ) { - Link *pNew = la.allocate( 1 ); - pNew->pValue = va.allocate( 1 ); - va.construct( pNew->pValue, v ); - nSize++; - if( pFirst == NULL ) + _hardCopy(); + if( core->pFirst == NULL ) { // Empty list - pFirst = pLast = pNew; - pNew->pNext = pNew->pPrev = NULL; + core->append( v ); return; } else { - Link *pCur = pFirst; + Link *pCur = core->pFirst; for(;;) { - if( !cmp( v, *(pCur->pValue)) ) + if( !core->cmp( v, *(pCur->pValue)) ) { - pNew->pNext = pCur; - pNew->pPrev = pCur->pPrev; - pCur->pPrev = pNew; - if( pNew->pPrev == NULL ) - pFirst = pNew; - else - pNew->pPrev->pNext = pNew; + core->insert( pCur, v ); return; } pCur = pCur->pNext; if( pCur == NULL ) { - pNew->pNext = NULL; - pNew->pPrev = pLast; - pLast->pNext = pNew; - pLast = pNew; + core->append( v ); return; } } @@ -541,7 +604,8 @@ namespace Bu */ iterator begin() { - return iterator( pFirst ); + _hardCopy(); + return iterator( core->pFirst ); } /** @@ -550,7 +614,7 @@ namespace Bu */ const_iterator begin() const { - return const_iterator( pFirst ); + return const_iterator( core->pFirst ); } /** @@ -579,34 +643,8 @@ namespace Bu */ void erase( iterator i ) { - Link *pCur = i.pLink; - if( pCur == NULL ) return; - Link *pPrev = pCur->pPrev; - if( pPrev == NULL ) - { - va.destroy( pCur->pValue ); - va.deallocate( pCur->pValue, 1 ); - pFirst = pCur->pNext; - la.destroy( pCur ); - la.deallocate( pCur, 1 ); - if( pFirst == NULL ) - pLast = NULL; - else - pFirst->pPrev = NULL; - nSize--; - } - else - { - va.destroy( pCur->pValue ); - va.deallocate( pCur->pValue, 1 ); - Link *pTmp = pCur->pNext; - la.destroy( pCur ); - la.deallocate( pCur, 1 ); - pPrev->pNext = pTmp; - if( pTmp != NULL ) - pTmp->pPrev = pPrev; - nSize--; - } + _hardCopy(); + core->erase( i.pLink ); } /** @@ -615,7 +653,7 @@ namespace Bu */ void erase( const value &v ) { - for( iterator i = begin(); i != end(); i++ ) + for( const_iterator i = begin(); i != end(); i++ ) { if( (*i) == v ) { @@ -631,7 +669,7 @@ namespace Bu */ long getSize() const { - return nSize; + return core->nSize; } /** @@ -640,7 +678,8 @@ namespace Bu */ value &first() { - return *pFirst->pValue; + _hardCopy(); + return *core->pFirst->pValue; } /** @@ -649,7 +688,7 @@ namespace Bu */ const value &first() const { - return *pFirst->pValue; + return *core->pFirst->pValue; } /** @@ -658,7 +697,8 @@ namespace Bu */ value &last() { - return *pLast->pValue; + _hardCopy(); + return *core->pLast->pValue; } /** @@ -667,21 +707,26 @@ namespace Bu */ const value &last() const { - return *pLast->pValue; + return *core->pLast->pValue; } bool isEmpty() const { - return (nSize == 0); + return (core->nSize == 0); } - + + protected: + virtual Core *_copyCore( Core *src ) + { + Core *pRet = _allocateCore(); + for( Link *pCur = src->pFirst; pCur; pCur = pCur->pNext ) + { + pRet->append( *pCur->pValue ); + } + return pRet; + } + private: - Link *pFirst; - Link *pLast; - linkalloc la; - valuealloc va; - long nSize; - cmpfunc cmp; }; class Formatter; -- cgit v1.2.3