From 867dae89929a11a421ec21af71d494ad0ecc1963 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Thu, 14 Oct 2010 23:26:25 +0000 Subject: SharedCore has more features now, which is cool, including a test to see if another object of the parent type has the same core, and another to clone the parent object. That one is pretty cool, it means you can now get a real copy when you want to, great for multi-threaded stuff. Also, two more classes are now SharedCore: Hash and Heap! --- src/archive.cpp | 9 +- src/archive.h | 4 +- src/archivebase.h | 5 +- src/array.h | 27 +- src/fbasicstring.h | 23 +- src/hash.h | 1046 +++++++++++++++++++++++----------------------- src/heap.h | 298 ++++++++----- src/list.h | 26 +- src/set.h | 760 +-------------------------------- src/sharedcore.h | 30 +- src/tests/sharedcore.cpp | 2 +- src/unit/hash.unit | 13 + 12 files changed, 841 insertions(+), 1402 deletions(-) (limited to 'src') diff --git a/src/archive.cpp b/src/archive.cpp index 69d4a0c..7a10921 100644 --- a/src/archive.cpp +++ b/src/archive.cpp @@ -22,20 +22,15 @@ Bu::Archive::~Archive() { } -void Bu::Archive::write( const void *pData, int32_t nSize ) +void Bu::Archive::write( const void *pData, size_t nSize ) { if( nSize == 0 || pData == NULL ) return; -// Bu::sio << "Writing starting at pos: " << rStream.tell() << " - " -// << Bu::sio.flush; - rStream.write( (const char *)pData, nSize ); -// -// Bu::sio << rStream.tell() << " (" << nSize << "b)" << Bu::sio.nl; } -void Bu::Archive::read( void *pData, int32_t nSize ) +void Bu::Archive::read( void *pData, size_t nSize ) { if( nSize == 0 || pData == NULL ) return; diff --git a/src/archive.h b/src/archive.h index bd85113..9d2aee2 100644 --- a/src/archive.h +++ b/src/archive.h @@ -83,8 +83,8 @@ namespace Bu virtual ~Archive(); virtual void close(); - virtual void write(const void *, int32_t); - virtual void read(void *, int32_t); + virtual void write( const void *pData, size_t iSize ); + virtual void read( void *pData, size_t iSize ); /** * For storage, get an ID for the pointer to the object you're going to diff --git a/src/archivebase.h b/src/archivebase.h index c871bb5..18591f0 100644 --- a/src/archivebase.h +++ b/src/archivebase.h @@ -9,6 +9,7 @@ #define BU_ARCHIVE_BASE_H #include +#include namespace Bu { @@ -19,8 +20,8 @@ namespace Bu virtual ~ArchiveBase(); virtual void close()=0; - virtual void write( const void *pData, int32_t iLength )=0; - virtual void read( void *pData, int32_t iLength )=0; + virtual void write( const void *pData, size_t iLength )=0; + virtual void read( void *pData, size_t iLength )=0; virtual bool isLoading()=0; }; diff --git a/src/array.h b/src/array.h index eeee677..fc4fb12 100644 --- a/src/array.h +++ b/src/array.h @@ -17,10 +17,18 @@ namespace Bu { subExceptionDecl( ArrayException ) + template + class Array; + template class ArrayCore { - public: + friend class Array; + friend class SharedCore< + Array, + ArrayCore + >; + private: ArrayCore() : pData( NULL ), iSize( 0 ), @@ -110,16 +118,20 @@ namespace Bu *@ingroup Containers */ template > - class Array : public SharedCore > + class Array : public SharedCore< + Array, + ArrayCore + > { private: typedef class Array MyType; typedef class ArrayCore Core; protected: - using SharedCore< Core >::core; - using SharedCore< Core >::_hardCopy; - using SharedCore< Core >::_allocateCore; + using SharedCore::core; + using SharedCore::_hardCopy; + using SharedCore::_resetCore; + using SharedCore::_allocateCore; public: struct const_iterator; @@ -130,7 +142,7 @@ namespace Bu } Array( const MyType &src ) : - SharedCore< Core >( src ) + SharedCore( src ) { } @@ -168,8 +180,7 @@ namespace Bu */ void clear() { - _hardCopy(); - core->clear(); + _resetCore(); } MyType &append( const value &rVal ) diff --git a/src/fbasicstring.h b/src/fbasicstring.h index 19853f5..82c5137 100644 --- a/src/fbasicstring.h +++ b/src/fbasicstring.h @@ -34,10 +34,19 @@ namespace Bu }; #define cpy( dest, src, size ) Bu::memcpy( dest, src, size*sizeof(chr) ) + + template< typename chr, int nMinSize, typename chralloc, + typename chunkalloc> class FBasicString; template struct FStringCore { + friend class FBasicString; + friend class SharedCore< + FBasicString, + FStringCore + >; + private: typedef struct FStringCore MyType; typedef struct FStringChunk Chunk; FStringCore() : @@ -174,16 +183,20 @@ namespace Bu *@param chralloc (typename) Memory Allocator for chr *@param chunkalloc (typename) Memory Allocator for chr chunks */ - template< typename chr, int nMinSize=256, typename chralloc=std::allocator, typename chunkalloc=std::allocator > > - class FBasicString : public SharedCore< FStringCore > + template< typename chr, int nMinSize=256, + typename chralloc=std::allocator, + typename chunkalloc=std::allocator > > + class FBasicString : public SharedCore< + FBasicString, + FStringCore > { protected: typedef struct FStringChunk Chunk; typedef struct FBasicString MyType; typedef struct FStringCore Core; - using SharedCore< Core >::core; - using SharedCore< Core >::_hardCopy; + using SharedCore::core; + using SharedCore::_hardCopy; public: FBasicString() @@ -201,7 +214,7 @@ namespace Bu } FBasicString( const MyType &rSrc ) : - SharedCore( rSrc ) + SharedCore( rSrc ) { } diff --git a/src/hash.h b/src/hash.h index 1cb539b..714a7f7 100644 --- a/src/hash.h +++ b/src/hash.h @@ -12,7 +12,8 @@ #include "bu/exceptionbase.h" #include "bu/list.h" #include "bu/util.h" -#include "archivebase.h" +#include "bu/archivebase.h" +#include "bu/sharedcore.h" #define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0)) @@ -49,137 +50,354 @@ namespace Bu } }; - template, typename valuealloc = std::allocator, typename challoc = std::allocator > + template class Hash; - template< typename key, typename _value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator, typename valuealloc = std::allocator<_value>, typename challoc = std::allocator > - struct HashProxy + template + class HashCore { - friend class Hash; + friend class Hash; + friend class SharedCore< + Hash, + HashCore + >; private: - HashProxy( Hash &h, const key *k, uint32_t nPos, uint32_t hash ) : - hsh( h ), - pKey( k ), - nPos( nPos ), - hash( hash ), - bFilled( false ) + HashCore() : + nCapacity( 0 ), + nFilled( 0 ), + nDeleted( 0 ), + bFilled( NULL ), + bDeleted( NULL ), + aKeys( NULL ), + aValues( NULL ), + aHashCodes( NULL ) { } - HashProxy( Hash &h, uint32_t nPos, _value *pValue ) : - hsh( h ), - nPos( nPos ), - pValue( pValue ), - bFilled( true ) + virtual ~HashCore() { + clear(); } - Hash &hsh; - const key *pKey; - uint32_t nPos; - _value *pValue; - uint32_t hash; - bool bFilled; + void init() + { + if( nCapacity > 0 ) + return; - public: - /** - * Cast operator for HashProxy. - *@returns (value_type &) The value the HashProxy is pointing to. - */ - operator _value &() + nCapacity = 11; + nKeysSize = bitsToBytes( nCapacity ); + bFilled = ca.allocate( nKeysSize ); + bDeleted = ca.allocate( nKeysSize ); + clearBits(); + + aHashCodes = ca.allocate( nCapacity ); + aKeys = ka.allocate( nCapacity ); + aValues = va.allocate( nCapacity ); + } + + void clearBits() { - if( bFilled == false ) - throw HashException( - excodeNotFilled, - "No data assosiated with that key." - ); - return *pValue; + if( nCapacity == 0 ) + return; + + for( uint32_t j = 0; j < nKeysSize; j++ ) + { + bFilled[j] = bDeleted[j] = 0; + } } - /** - * Direct function for retrieving a value out of the HashProxy. - *@returns (value_type &) The value pointed to by this HashProxy. - */ - DEPRECATED - _value &value() + void fill( uint32_t loc, const key &k, const value &v, uint32_t hash ) { - if( bFilled == false ) - throw HashException( - excodeNotFilled, - "No data assosiated with that key." - ); - return *pValue; + init(); + + bFilled[loc/32] |= (1<<(loc%32)); + va.construct( &aValues[loc], v ); + ka.construct( &aKeys[loc], k ); + aHashCodes[loc] = hash; + nFilled++; + //printf("Filled: %d, Deleted: %d, Capacity: %d\n", + // nFilled, nDeleted, nCapacity ); + } + + void _erase( uint32_t loc ) + { + if( nCapacity == 0 ) + return; + + bDeleted[loc/32] |= (1<<(loc%32)); + va.destroy( &aValues[loc] ); + ka.destroy( &aKeys[loc] ); + nDeleted++; + //printf("Filled: %d, Deleted: %d, Capacity: %d\n", + // nFilled, nDeleted, nCapacity ); + } + + key &getKeyAtPos( uint32_t nPos ) + { + if( nPos >= nCapacity ) + throw HashException("Referenced position invalid."); + return aKeys[nPos]; } - /** - * Direct function for retrieving a value out of the HashProxy. - *@returns (value_type &) The value pointed to by this HashProxy. - */ - _value &getValue() + const key &getKeyAtPos( uint32_t nPos ) const { - if( bFilled == false ) - throw HashException( - excodeNotFilled, - "No data assosiated with that key." - ); - return *pValue; + if( nPos >= nCapacity ) + throw HashException("Referenced position invalid."); + return aKeys[nPos]; + } + + value &getValueAtPos( uint32_t nPos ) + { + if( nPos >= nCapacity ) + throw HashException("Referenced position invalid."); + return aValues[nPos]; + } + + const value &getValueAtPos( uint32_t nPos ) const + { + if( nPos >= nCapacity ) + throw HashException("Referenced position invalid."); + return aValues[nPos]; } - /** - * Whether this HashProxy points to something real or not. - */ - bool isFilled() + uint32_t getFirstPos( bool &bFinished ) const { - return bFilled; + for( uint32_t j = 0; j < nCapacity; j++ ) + { + if( isFilled( j ) ) + if( !isDeleted( j ) ) + return j; + } + + bFinished = true; + return 0; } - /** - * Erase the data pointed to by this HashProxy. - */ - void erase() + uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const { - if( bFilled ) + for( uint32_t j = nPos+1; j < nCapacity; j++ ) { - hsh._erase( nPos ); - hsh.onDelete(); + if( isFilled( j ) ) + if( !isDeleted( j ) ) + return j; } + + bFinished = true; + return 0; } - /** - * Assign data to this point in the hash table. - *@param nval (value_type) the data to assign. - */ - _value operator=( _value nval ) + uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true ) + { + init(); + + uint32_t nCur = hash%nCapacity; + + // First we scan to see if the key is already there, abort if we + // run out of probing room, or we find a non-filled entry + int8_t j; + for( j = 0; + isFilled( nCur ) && j < 32; + nCur = (nCur + (1<() + bool isFilled( uint32_t loc ) const { - if( bFilled == false ) - throw HashException( - excodeNotFilled, - "No data assosiated with that key." - ); - return pValue; + if( loc >= nCapacity ) + throw HashException("Referenced position invalid."); + return (bFilled[loc/32]&(1<<(loc%32)))!=0; } + + bool isDeleted( uint32_t loc ) const + { + if( loc >= nCapacity ) + throw HashException("Referenced position invalid."); + return (bDeleted[loc/32]&(1<<(loc%32)))!=0; + } + + void clear() + { + for( uint32_t j = 0; j < nCapacity; j++ ) + { + if( isFilled( j ) ) + if( !isDeleted( j ) ) + { + va.destroy( &aValues[j] ); + ka.destroy( &aKeys[j] ); + } + } + va.deallocate( aValues, nCapacity ); + ka.deallocate( aKeys, nCapacity ); + ca.deallocate( bFilled, nKeysSize ); + ca.deallocate( bDeleted, nKeysSize ); + ca.deallocate( aHashCodes, nCapacity ); + + bFilled = NULL; + bDeleted = NULL; + aKeys = NULL; + aValues = NULL; + aHashCodes = NULL; + + nCapacity = 0; + nFilled = 0; + nDeleted = 0; + } + + uint32_t nCapacity; + uint32_t nFilled; + uint32_t nDeleted; + uint32_t *bFilled; + uint32_t *bDeleted; + uint32_t nKeysSize; + key *aKeys; + value *aValues; + uint32_t *aHashCodes; + valuealloc va; + keyalloc ka; + challoc ca; + sizecalc szCalc; }; /** @@ -224,119 +442,38 @@ namespace Bu *@param challoc (typename) Byte allocator for bitflags *@ingroup Containers */ - template - class Hash + template, + typename valuealloc = std::allocator, + typename challoc = std::allocator + > + class Hash : public SharedCore< + Hash, + HashCore + > { - friend struct HashProxy; + private: + typedef class HashCore Core; typedef class Hash MyType; + protected: + using SharedCore::core; + using SharedCore::_hardCopy; + using SharedCore::_resetCore; + using SharedCore::_allocateCore; + public: - Hash() : - nCapacity( 11 ), - nFilled( 0 ), - nDeleted( 0 ), - bFilled( NULL ), - bDeleted( NULL ), - aKeys( NULL ), - aValues( NULL ), - aHashCodes( NULL ) + Hash() { - nKeysSize = bitsToBytes( nCapacity ); - bFilled = ca.allocate( nKeysSize ); - bDeleted = ca.allocate( nKeysSize ); - clearBits(); - - aHashCodes = ca.allocate( nCapacity ); - aKeys = ka.allocate( nCapacity ); - aValues = va.allocate( nCapacity ); } - Hash( const Hash &src ) : - nCapacity( src.nCapacity ), - nFilled( 0 ), - nDeleted( 0 ), - bFilled( NULL ), - bDeleted( NULL ), - aKeys( NULL ), - aValues( NULL ), - aHashCodes( NULL ) + Hash( const MyType &src ) : + SharedCore( src ) { - nKeysSize = bitsToBytes( nCapacity ); - bFilled = ca.allocate( nKeysSize ); - bDeleted = ca.allocate( nKeysSize ); - clearBits(); - - aHashCodes = ca.allocate( nCapacity ); - aKeys = ka.allocate( nCapacity ); - aValues = va.allocate( nCapacity ); - - for( uint32_t j = 0; j < src.nCapacity; j++ ) - { - if( src.isFilled( j ) && !src.isDeleted( j ) ) - { - insert( src.aKeys[j], src.aValues[j] ); - } - } - } - - /** - * Hashtable assignment operator. Clears this hashtable and - * copies RH into it. - */ - Hash &operator=( const Hash &src ) - { - for( uint32_t j = 0; j < nCapacity; j++ ) - { - if( isFilled( j ) && !isDeleted( j ) ) - { - va.destroy( &aValues[j] ); - ka.destroy( &aKeys[j] ); - } - } - va.deallocate( aValues, nCapacity ); - ka.deallocate( aKeys, nCapacity ); - ca.deallocate( bFilled, nKeysSize ); - ca.deallocate( bDeleted, nKeysSize ); - ca.deallocate( aHashCodes, nCapacity ); - - nFilled = 0; - nDeleted = 0; - nCapacity = src.nCapacity; - nKeysSize = bitsToBytes( nCapacity ); - bFilled = ca.allocate( nKeysSize ); - bDeleted = ca.allocate( nKeysSize ); - clearBits(); - - aHashCodes = ca.allocate( nCapacity ); - aKeys = ka.allocate( nCapacity ); - aValues = va.allocate( nCapacity ); - - for( uint32_t j = 0; j < src.nCapacity; j++ ) - { - if( src.isFilled( j ) && !src.isDeleted( j ) ) - { - insert( src.aKeys[j], src.aValues[j] ); - } - } - - return *this; } virtual ~Hash() { - for( uint32_t j = 0; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - if( !isDeleted( j ) ) - { - va.destroy( &aValues[j] ); - ka.destroy( &aKeys[j] ); - } - } - va.deallocate( aValues, nCapacity ); - ka.deallocate( aKeys, nCapacity ); - ca.deallocate( bFilled, nKeysSize ); - ca.deallocate( bDeleted, nKeysSize ); - ca.deallocate( aHashCodes, nCapacity ); } /** @@ -345,7 +482,7 @@ namespace Bu */ uint32_t getCapacity() const { - return nCapacity; + return core->nCapacity; } /** @@ -355,7 +492,7 @@ namespace Bu */ uint32_t getFill() const { - return nFilled; + return core->nFilled; } /** @@ -364,12 +501,12 @@ namespace Bu */ uint32_t getSize() const { - return nFilled-nDeleted; + return core->nFilled-core->nDeleted; } bool isEmpty() const { - return (nFilled-nDeleted) == 0; + return (core->nFilled-core->nDeleted) == 0; } /** @@ -379,68 +516,170 @@ namespace Bu */ uint32_t getDeleted() const { - return nDeleted; + return core->nDeleted; } - /** - * Hash table index operator - *@param k (key_type) Key of data to be retrieved. - *@returns (HashProxy) Proxy pointing to the data. - */ - virtual HashProxy operator[]( const key &k ) + struct HashProxy { - uint32_t hash = __calcHashCode( k ); - bool bFill; - uint32_t nPos = probe( hash, k, bFill ); + friend class Hash; + private: + HashProxy( MyType &h, const key *k, uint32_t nPos, uint32_t hash ) : + hsh( h ), + pKey( k ), + nPos( nPos ), + hash( hash ), + bFilled( false ) + { + } - if( bFill ) + HashProxy( MyType &h, uint32_t nPos, value *pValue ) : + hsh( h ), + nPos( nPos ), + pValue( pValue ), + bFilled( true ) { - return HashProxy( *this, nPos, &aValues[nPos] ); } - else + + MyType &hsh; + const key *pKey; + uint32_t nPos; + value *pValue; + uint32_t hash; + bool bFilled; + + public: + /** + * Cast operator for HashProxy. + *@returns (value_type &) The value the HashProxy is pointing to. + */ + operator value &() { - return HashProxy( *this, &k, nPos, hash ); + if( bFilled == false ) + throw HashException( + excodeNotFilled, + "No data assosiated with that key." + ); + return *pValue; + } + + /** + * Direct function for retrieving a value out of the HashProxy. + *@returns (value_type &) The value pointed to by this HashProxy. + */ + value &getValue() + { + if( bFilled == false ) + throw HashException( + excodeNotFilled, + "No data assosiated with that key." + ); + return *pValue; + } + + /** + * Whether this HashProxy points to something real or not. + */ + bool isFilled() + { + return bFilled; + } + + /** + * Erase the data pointed to by this HashProxy. + */ + void erase() + { + if( bFilled ) + { + hsh.core->_erase( nPos ); + } + } + + /** + * Assign data to this point in the hash table. + *@param nval (value_type) the data to assign. + */ + value operator=( value nval ) + { + if( bFilled ) + { + hsh.core->va.destroy( &hsh.core->aValues[nPos] ); + hsh.core->va.construct( &hsh.core->aValues[nPos], nval ); + } + else + { + hsh.core->fill( nPos, *pKey, nval, hash ); + } + + return nval; } - } + + /** + * Pointer extraction operator. Access to members of data pointed to + * by HashProxy. + *@returns (value_type *) + */ + value *operator->() + { + if( bFilled == false ) + throw HashException( + excodeNotFilled, + "No data assosiated with that key." + ); + return pValue; + } + }; /** - * Insert a value (v) under key (k) into the hash table - *@param k (key_type) Key to list the value under. - *@param v (value_type) Value to store in the hash table. + * Hash table index operator + *@param k (key_type) Key of data to be retrieved. + *@returns (HashProxy) Proxy pointing to the data. */ - virtual void insert( const key &k, const value &v ) + HashProxy operator[]( const key &k ) { + _hardCopy(); + uint32_t hash = __calcHashCode( k ); bool bFill; - uint32_t nPos = probe( hash, k, bFill ); + uint32_t nPos = core->probe( hash, k, bFill ); if( bFill ) { - va.destroy( &aValues[nPos] ); - va.construct( &aValues[nPos], v ); - onUpdate(); + return HashProxy( *this, nPos, &core->aValues[nPos] ); } else { - fill( nPos, k, v, hash ); - onInsert(); + return HashProxy( *this, &k, nPos, hash ); } } + /** + * Insert a value (v) under key (k) into the hash table + *@param k (key_type) Key to list the value under. + *@param v (value_type) Value to store in the hash table. + */ + void insert( const key &k, const value &v ) + { + _hardCopy(); + + core->insert( k, v ); + } + /** * Remove a value from the hash table. *@param k (key_type) The data under this key will be erased. */ - virtual void erase( const key &k ) + void erase( const key &k ) { + _hardCopy(); + uint32_t hash = __calcHashCode( k ); bool bFill; - uint32_t nPos = probe( hash, k, bFill ); + uint32_t nPos = core->probe( hash, k, bFill ); if( bFill ) { - _erase( nPos ); - onDelete(); + core->_erase( nPos ); } } @@ -450,14 +689,16 @@ namespace Bu * Remove a value from the hash pointed to from an iterator. *@param i (iterator &) The data to be erased. */ - virtual void erase( struct iterator &i ) + void erase( struct iterator &i ) { if( this != i.hsh ) throw HashException("This iterator didn't come from this Hash."); - if( isFilled( i.nPos ) && !isDeleted( i.nPos ) ) + + _hardCopy(); + + if( core->isFilled( i.nPos ) && !core->isDeleted( i.nPos ) ) { - _erase( i.nPos ); - onDelete(); + core->_erase( i.nPos ); } } @@ -466,17 +707,7 @@ namespace Bu */ virtual void clear() { - for( uint32_t j = 0; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - if( !isDeleted( j ) ) - { - _erase( j ); - onDelete(); - } - } - - clearBits(); + _resetCore(); } /** @@ -484,15 +715,17 @@ namespace Bu *@param k (key_type) Key pointing to the data to be retrieved. *@returns (value_type &) The data pointed to by (k). */ - virtual value &get( const key &k ) + value &get( const key &k ) { + _hardCopy(); + uint32_t hash = __calcHashCode( k ); bool bFill; - uint32_t nPos = probe( hash, k, bFill, false ); + uint32_t nPos = core->probe( hash, k, bFill, false ); if( bFill ) { - return aValues[nPos]; + return core->aValues[nPos]; } else { @@ -509,15 +742,15 @@ namespace Bu *@returns (const value_type &) A const version of the data pointed * to by (k). */ - virtual const value &get( const key &k ) const + const value &get( const key &k ) const { uint32_t hash = __calcHashCode( k ); bool bFill; - uint32_t nPos = probe( hash, k, bFill ); + uint32_t nPos = core->probe( hash, k, bFill ); if( bFill ) { - return aValues[nPos]; + return core->aValues[nPos]; } else { @@ -533,18 +766,10 @@ namespace Bu *@param k (key_type) The key to check. *@returns (bool) Whether there was an item in the hash under key (k). */ - virtual bool has( const key &k ) - { - bool bFill; - probe( __calcHashCode( k ), k, bFill, false ); - - return bFill; - } - - virtual bool has( const key &k ) const + bool has( const key &k ) const { bool bFill; - probe( __calcHashCode( k ), k, bFill ); + core->probe( __calcHashCode( k ), k, bFill ); return bFill; } @@ -561,7 +786,7 @@ namespace Bu nPos( 0 ), bFinished( false ) { - nPos = hsh->getFirstPos( bFinished ); + nPos = hsh->core->getFirstPos( bFinished ); } iterator( MyType *hsh, bool bDone ) : @@ -590,11 +815,6 @@ namespace Bu { } - DEPRECATED bool isActive() const - { - return !bFinished; - } - bool isValid() const { return !bFinished; @@ -611,7 +831,7 @@ namespace Bu iterator operator++( int ) { if( bFinished == false ) - nPos = hsh->getNextPos( nPos, bFinished ); + nPos = hsh->core->getNextPos( nPos, bFinished ); return *this; } @@ -622,7 +842,7 @@ namespace Bu iterator operator++() { if( bFinished == false ) - nPos = hsh->getNextPos( nPos, bFinished ); + nPos = hsh->core->getNextPos( nPos, bFinished ); return *this; } @@ -671,21 +891,22 @@ namespace Bu */ value &operator *() { - return hsh->getValueAtPos( nPos ); + hsh->_hardCopy(); + return hsh->core->getValueAtPos( nPos ); } const value &operator *() const { - return hsh->getValueAtPos( nPos ); + return hsh->core->getValueAtPos( nPos ); } /** * Get the key behind this iterator. *@returns (key_type &) The key behind this iterator. */ - key &getKey() + const key &getKey() const { - return hsh->getKeyAtPos( nPos ); + return hsh->core->getKeyAtPos( nPos ); } /** @@ -694,7 +915,17 @@ namespace Bu */ value &getValue() { - return hsh->getValueAtPos( nPos ); + hsh->_hardCopy(); + return hsh->core->getValueAtPos( nPos ); + } + + /** + * Get the value behind this iterator. + *@returns (value_type &) The value behind this iterator. + */ + const value &getValue() const + { + return hsh->core->getValueAtPos( nPos ); } } iterator; @@ -710,7 +941,7 @@ namespace Bu nPos( 0 ), bFinished( false ) { - nPos = hsh->getFirstPos( bFinished ); + nPos = hsh->core->getFirstPos( bFinished ); } const_iterator( const MyType *hsh, bool bDone ) : @@ -762,7 +993,7 @@ namespace Bu const_iterator operator++( int ) { if( bFinished == false ) - nPos = hsh->getNextPos( nPos, bFinished ); + nPos = hsh->core->getNextPos( nPos, bFinished ); return *this; } @@ -773,7 +1004,7 @@ namespace Bu const_iterator operator++() { if( bFinished == false ) - nPos = hsh->getNextPos( nPos, bFinished ); + nPos = hsh->core->getNextPos( nPos, bFinished ); return *this; } @@ -822,7 +1053,7 @@ namespace Bu */ const value &operator *() const { - return hsh->getValueAtPos( nPos ); + return hsh->core->getValueAtPos( nPos ); } /** @@ -831,7 +1062,7 @@ namespace Bu */ const key &getKey() const { - return hsh->getKeyAtPos( nPos ); + return hsh->core->getKeyAtPos( nPos ); } /** @@ -840,7 +1071,7 @@ namespace Bu */ const value &getValue() const { - return hsh->getValueAtPos( nPos ); + return hsh->core->getValueAtPos( nPos ); } } const_iterator; @@ -883,13 +1114,13 @@ namespace Bu { Bu::List lKeys; - for( uint32_t j = 0; j < nCapacity; j++ ) + for( uint32_t j = 0; j < core->nCapacity; j++ ) { - if( isFilled( j ) ) + if( core->isFilled( j ) ) { - if( !isDeleted( j ) ) + if( !core->isDeleted( j ) ) { - lKeys.append( aKeys[j] ); + lKeys.append( core->aKeys[j] ); } } } @@ -901,13 +1132,13 @@ namespace Bu { Bu::List lValues; - for( uint32_t j = 0; j < nCapacity; j++ ) + for( uint32_t j = 0; j < core->nCapacity; j++ ) { - if( isFilled( j ) ) + if( core->isFilled( j ) ) { - if( !isDeleted( j ) ) + if( !core->isDeleted( j ) ) { - lValues.append( aValues[j] ); + lValues.append( core->aValues[j] ); } } } @@ -916,243 +1147,32 @@ namespace Bu } protected: - virtual void onInsert() {} - virtual void onUpdate() {} - virtual void onDelete() {} - virtual void onReHash() {} - - virtual void clearBits() - { - for( uint32_t j = 0; j < nKeysSize; j++ ) - { - bFilled[j] = bDeleted[j] = 0; - } - } - - virtual void fill( uint32_t loc, const key &k, const value &v, uint32_t hash ) - { - bFilled[loc/32] |= (1<<(loc%32)); - va.construct( &aValues[loc], v ); - ka.construct( &aKeys[loc], k ); - aHashCodes[loc] = hash; - nFilled++; - //printf("Filled: %d, Deleted: %d, Capacity: %d\n", - // nFilled, nDeleted, nCapacity ); - } - - virtual void _erase( uint32_t loc ) - { - bDeleted[loc/32] |= (1<<(loc%32)); - va.destroy( &aValues[loc] ); - ka.destroy( &aKeys[loc] ); - nDeleted++; - //printf("Filled: %d, Deleted: %d, Capacity: %d\n", - // nFilled, nDeleted, nCapacity ); - } - - virtual key &getKeyAtPos( uint32_t nPos ) - { - return aKeys[nPos]; - } - - virtual const key &getKeyAtPos( uint32_t nPos ) const - { - return aKeys[nPos]; - } - - virtual value &getValueAtPos( uint32_t nPos ) - { - return aValues[nPos]; - } - - virtual const value &getValueAtPos( uint32_t nPos ) const - { - return aValues[nPos]; - } - - virtual uint32_t getFirstPos( bool &bFinished ) const - { - for( uint32_t j = 0; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - if( !isDeleted( j ) ) - return j; - } - - bFinished = true; - return 0; - } - - virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const - { - for( uint32_t j = nPos+1; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - if( !isDeleted( j ) ) - return j; - } - - bFinished = true; - return 0; - } - - uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true ) - { - uint32_t nCur = hash%nCapacity; - - // First we scan to see if the key is already there, abort if we - // run out of probing room, or we find a non-filled entry - int8_t j; - for( j = 0; - isFilled( nCur ) && j < 32; - nCur = (nCur + (1<nFilled = 0; + pRet->nDeleted = 0; + pRet->nCapacity = src->nCapacity; + pRet->nKeysSize = bitsToBytes( pRet->nCapacity ); + pRet->bFilled = pRet->ca.allocate( pRet->nKeysSize ); + pRet->bDeleted = pRet->ca.allocate( pRet->nKeysSize ); + pRet->clearBits(); - // Re-insert all of the old data (except deleted items) - for( uint32_t j = 0; j < nOldCapacity; j++ ) - { - if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && - (bOldDeleted[j/32]&(1<<(j%32)))==0 ) - { - insert( aOldKeys[j], aOldValues[j] ); - } - } + pRet->aHashCodes = pRet->ca.allocate( pRet->nCapacity ); + pRet->aKeys = pRet->ka.allocate( pRet->nCapacity ); + pRet->aValues = pRet->va.allocate( pRet->nCapacity ); - // Delete all of the old data - for( uint32_t j = 0; j < nOldCapacity; j++ ) + for( uint32_t j = 0; j < src->nCapacity; j++ ) { - if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && - (bOldDeleted[j/32]&(1<<(j%32)))==0 ) + if( src->isFilled( j ) && !src->isDeleted( j ) ) { - va.destroy( &aOldValues[j] ); - ka.destroy( &aOldKeys[j] ); + pRet->insert( src->aKeys[j], src->aValues[j] ); } } - va.deallocate( aOldValues, nOldCapacity ); - ka.deallocate( aOldKeys, nOldCapacity ); - ca.deallocate( bOldFilled, nOldKeysSize ); - ca.deallocate( bOldDeleted, nOldKeysSize ); - ca.deallocate( aOldHashCodes, nOldCapacity ); - } - - virtual bool isFilled( uint32_t loc ) const - { - return (bFilled[loc/32]&(1<<(loc%32)))!=0; - } - virtual bool isDeleted( uint32_t loc ) const - { - return (bDeleted[loc/32]&(1<<(loc%32)))!=0; + return pRet; } - - protected: - uint32_t nCapacity; - uint32_t nFilled; - uint32_t nDeleted; - uint32_t *bFilled; - uint32_t *bDeleted; - uint32_t nKeysSize; - key *aKeys; - value *aValues; - uint32_t *aHashCodes; - valuealloc va; - keyalloc ka; - challoc ca; - sizecalc szCalc; }; template uint32_t __calcHashCode( const T &k ) diff --git a/src/heap.h b/src/heap.h index 9df4121..1dac69b 100644 --- a/src/heap.h +++ b/src/heap.h @@ -13,76 +13,92 @@ #include "bu/exceptionbase.h" #include "bu/util.h" #include "bu/queue.h" +#include "bu/sharedcore.h" namespace Bu { subExceptionDecl( HeapException ); - /** - * A priority queue that allows for an unlimited number of priorities. All - * objects enqueued must support less-than-comparison. Then every time an - * item is dequeued it is always the least item in the heap. The heap - * operates using a binary tree for storage, which allows most operations - * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins - * whereas peeking is constant time. - * - * This heap implementation allows iterating, however please note that any - * enqueue or dequeue operation will invalidate the iterator and make it - * unusable (if it still works, you shouldn't trust the results). Also, - * the items are not stored in memory in order, they are optomized into a - * tree. This means that the items will be in effectively random order - * while iterating through them, and the order cannot be trusted. Also, - * modifying an item in the heap will not cause that item to be re-sorted. - * If you want to change the position of an item in the heap you will have - * to dequeue every item before it, dequeue that item, change it, and - * re-enqueue all of the items removed. - */ - template, typename itemalloc=std::allocator > - class Heap : public Queue + template + class Heap; + + template + class HeapCore { - public: - Heap() : - iSize( 7 ), + friend class Heap; + friend class SharedCore< + Heap, HeapCore + >; + private: + HeapCore() : + iSize( 0 ), iFill( 0 ), - aItem( ia.allocate( iSize ) ) + aItem( NULL ) { } - - Heap( cmpfunc cmpin ) : - iSize( 7 ), - iFill( 0 ), - aItem( ia.allocate( iSize ) ), - cmp( cmpin ) + + virtual ~HeapCore() { + clear(); } - Heap( int iInitialCapacity ) : - iSize( 0 ), - iFill( 0 ), - aItem( NULL ) + void init() { - for( iSize = 1; iSize < iInitialCapacity; iSize=iSize*2+1 ) { } + if( iSize > 0 ) + return; + + iSize = 7; + iFill = 0; aItem = ia.allocate( iSize ); } - - Heap( cmpfunc cmpin, int iInitialCapacity ) : - iSize( 0 ), - iFill( 0 ), - aItem( NULL ), - cmp( cmpin ) + + void init( int iCap ) { - for( iSize = 1; iSize < iInitialCapacity; iSize=iSize*2+1 ) { } + if( iSize > 0 ) + return; + + for( iSize = 1; iSize < iCap; iSize=iSize*2+1 ) { } + iFill = 0; aItem = ia.allocate( iSize ); } - virtual ~Heap() + void clear() { + if( iSize == 0 ) + return; + for( int j = 0; j < iFill; j++ ) ia.destroy( &aItem[j] ); ia.deallocate( aItem, iSize ); aItem = NULL; + iSize = 0; + iFill = 0; } + + void upSize() + { + if( iSize == 0 ) + { + init(); + return; + } + item *aNewItems = ia.allocate( iSize*2+1 ); + // + // We cannot use a memcopy here because we don't know what kind + // of datastructures are being used, we have to copy them one at + // a time. + // + for( int j = 0; j < iFill; j++ ) + { + ia.construct( &aNewItems[j], aItem[j] ); + ia.destroy( &aItem[j] ); + } + ia.deallocate( aItem, iSize ); + aItem = aNewItems; + iSize = iSize*2+1; + } + virtual void enqueue( const item &it ) { item i = it; // TODO: This is a silly workaround, put the i item @@ -126,20 +142,6 @@ namespace Bu iFill++; } - virtual item &peek() - { - if( iFill == 0 ) - throw HeapException("Heap empty."); - return aItem[0]; - } - - virtual const item &peek() const - { - if( iFill == 0 ) - throw HeapException("Heap empty."); - return aItem[0]; - } - virtual item dequeue() { if( iFill == 0 ) @@ -174,14 +176,117 @@ namespace Bu return iRet; } + private: + int iSize; + int iFill; + item *aItem; + cmpfunc cmp; + itemalloc ia; + }; + + /** + * A priority queue that allows for an unlimited number of priorities. All + * objects enqueued must support less-than-comparison. Then every time an + * item is dequeued it is always the least item in the heap. The heap + * operates using a binary tree for storage, which allows most operations + * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins + * whereas peeking is constant time. + * + * This heap implementation allows iterating, however please note that any + * enqueue or dequeue operation will invalidate the iterator and make it + * unusable (if it still works, you shouldn't trust the results). Also, + * the items are not stored in memory in order, they are optomized into a + * tree. This means that the items will be in effectively random order + * while iterating through them, and the order cannot be trusted. Also, + * modifying an item in the heap will not cause that item to be re-sorted. + * If you want to change the position of an item in the heap you will have + * to dequeue every item before it, dequeue that item, change it, and + * re-enqueue all of the items removed. + */ + template, typename itemalloc=std::allocator > + class Heap : public Queue, public SharedCore< + Heap, + HeapCore + > + { + private: + typedef class Heap MyType; + typedef class HeapCore Core; + + protected: + using SharedCore::core; + using SharedCore::_hardCopy; + using SharedCore::_resetCore; + using SharedCore::_allocateCore; + + public: + Heap() + { + } + + Heap( cmpfunc cmpin ) + { + core->cmp = cmpin; + } + + Heap( int iInitialCapacity ) + { + core->init( iInitialCapacity ); + } + + Heap( cmpfunc cmpin, int iInitialCapacity ) + { + core->cmp = cmpin; + core->init( iInitialCapacity ); + } + + Heap( const MyType &rSrc ) : + SharedCore( rSrc ) + { + } + + virtual ~Heap() + { + } + + virtual void enqueue( const item &it ) + { + _hardCopy(); + + core->enqueue( it ); + } + + virtual item &peek() + { + _hardCopy(); + + if( core->iFill == 0 ) + throw HeapException("Heap empty."); + return core->aItem[0]; + } + + virtual const item &peek() const + { + if( core->iFill == 0 ) + throw HeapException("Heap empty."); + return core->aItem[0]; + } + + virtual item dequeue() + { + _hardCopy(); + + return core->dequeue(); + } + virtual bool isEmpty() const { - return (iFill==0); + return (core->iFill==0); } virtual int getSize() const { - return iFill; + return core->iFill; } class iterator @@ -201,7 +306,7 @@ namespace Bu { if( pHeap == NULL ) throw Bu::ExceptionBase("Iterator not initialized."); - if( iIndex < 0 || iIndex >= pHeap->iFill ) + if( iIndex < 0 || iIndex >= pHeap->core->iFill ) throw Bu::ExceptionBase("Iterator out of bounds."); } @@ -230,12 +335,16 @@ namespace Bu item &operator*() { - return pHeap->aItem[iIndex]; + pHeap->_hardCopy(); + + return pHeap->core->aItem[iIndex]; } item *operator->() { - return &(pHeap->aItem[iIndex]); + pHeap->_hardCopy(); + + return &(pHeap->core->aItem[iIndex]); } iterator &operator++() @@ -260,7 +369,7 @@ namespace Bu { checkValid(); iIndex++; - if( iIndex >= pHeap->iFill ) + if( iIndex >= pHeap->core->iFill ) iIndex = -1; return *this; @@ -279,7 +388,7 @@ namespace Bu checkValid(); iterator ret( *this ); ret.iIndex += iDelta; - if( ret.iIndex >= pHeap->iFill ) + if( ret.iIndex >= pHeap->core->iFill ) ret.iIndex = -1; return ret; } @@ -294,12 +403,12 @@ namespace Bu return ret; } - operator bool() + operator bool() const { return iIndex != -1; } - bool isValid() + bool isValid() const { return iIndex != -1; } @@ -328,7 +437,7 @@ namespace Bu { if( pHeap == NULL ) throw Bu::ExceptionBase("Iterator not initialized."); - if( iIndex < 0 || iIndex >= pHeap->iFill ) + if( iIndex < 0 || iIndex >= pHeap->core->iFill ) throw Bu::ExceptionBase("Iterator out of bounds."); } @@ -363,19 +472,23 @@ namespace Bu const item &operator*() { - return pHeap->aItem[iIndex]; + pHeap->_hardCopy(); + + return pHeap->core->aItem[iIndex]; } const item *operator->() { - return &(pHeap->aItem[iIndex]); + pHeap->_hardCopy(); + + return &(pHeap->core->aItem[iIndex]); } const_iterator &operator++() { checkValid(); iIndex++; - if( iIndex >= pHeap->iFill ) + if( iIndex >= pHeap->core->iFill ) iIndex = -1; return *this; @@ -393,7 +506,7 @@ namespace Bu { checkValid(); iIndex++; - if( iIndex >= pHeap->iFill ) + if( iIndex >= pHeap->core->iFill ) iIndex = -1; return *this; @@ -427,12 +540,12 @@ namespace Bu return ret; } - operator bool() + operator bool() const { return iIndex != -1; } - bool isValid() + bool isValid() const { return iIndex != -1; } @@ -452,14 +565,14 @@ namespace Bu iterator begin() { - if( iFill == 0 ) + if( core->iFill == 0 ) return end(); return iterator( this, 0 ); } const_iterator begin() const { - if( iFill == 0 ) + if( core->iFill == 0 ) return end(); return const_iterator( this, 0 ); } @@ -475,31 +588,22 @@ namespace Bu } - private: - void upSize() + protected: + virtual Core *_copyCore( Core *src ) { - item *aNewItems = ia.allocate( iSize*2+1 ); - // - // We cannot use a memcopy here because we don't know what kind - // of datastructures are being used, we have to copy them one at - // a time. - // - for( int j = 0; j < iFill; j++ ) + Core *pRet = _allocateCore(); + + pRet->iSize = src->iSize; + pRet->iFill = src->iFill; + pRet->cmp = src->cmp; + pRet->aItem = pRet->ia.allocate( pRet->iSize ); + for( int j = 0; j < pRet->iFill; j++ ) { - ia.construct( &aNewItems[j], aItem[j] ); - ia.destroy( &aItem[j] ); + pRet->ia.construct( &pRet->aItem[j], src->aItem[j] ); } - ia.deallocate( aItem, iSize ); - aItem = aNewItems; - iSize = iSize*2+1; - } - private: - int iSize; - int iFill; - item *aItem; - cmpfunc cmp; - itemalloc ia; + return pRet; + } }; }; diff --git a/src/list.h b/src/list.h index 9b95983..ba1d2c4 100644 --- a/src/list.h +++ b/src/list.h @@ -24,10 +24,18 @@ namespace Bu ListLink *pPrev; }; - template + template + class List; + + template struct ListCore { + friend class List; + friend class SharedCore< + List, + ListCore + >; + private: typedef struct ListLink Link; ListCore() : pFirst( NULL ), @@ -193,8 +201,10 @@ namespace Bu */ template, typename linkalloc=std::allocator > > - class List : public SharedCore< struct ListCore > + class List : public SharedCore< + List, + ListCore + > { private: typedef struct ListLink Link; @@ -202,9 +212,9 @@ namespace Bu typedef struct ListCore Core; protected: - using SharedCore< Core >::core; - using SharedCore< Core >::_hardCopy; - using SharedCore< Core >::_allocateCore; + using SharedCore::core; + using SharedCore::_hardCopy; + using SharedCore::_allocateCore; public: struct const_iterator; @@ -215,7 +225,7 @@ namespace Bu } List( const MyType &src ) : - SharedCore< Core >( src ) + SharedCore( src ) { } diff --git a/src/set.h b/src/set.h index 6a2abce..047ff7f 100644 --- a/src/set.h +++ b/src/set.h @@ -24,17 +24,10 @@ namespace Bu { subExceptionDecl( SetException ) - template - uint32_t __calcHashCode( const T &k ); - - template - bool __cmpHashKeys( const T &a, const T &b ); - - template, typename challoc = std::allocator > - class Set; - /** - * Libbu Template Set + *@todo Set should be rewritten, possibly using a b-tree as ordered storage + * in the backend. It should use either a b-tree or array for storage and + * allow set intersections, unions, etc. *@param key (typename) The datatype of the hashtable keys *@param sizecalc (typename) Functor to compute new table size on rehash *@param keyalloc (typename) Memory allocator for hashtable keys @@ -45,754 +38,7 @@ namespace Bu class Set { public: - Set() : - nCapacity( 11 ), - nFilled( 0 ), - nDeleted( 0 ), - bFilled( NULL ), - bDeleted( NULL ), - aKeys( NULL ), - aHashCodes( NULL ) - { - nKeysSize = bitsToBytes( nCapacity ); - bFilled = ca.allocate( nKeysSize ); - bDeleted = ca.allocate( nKeysSize ); - clearBits(); - - aHashCodes = ca.allocate( nCapacity ); - aKeys = ka.allocate( nCapacity ); - } - - Set( const Set &src ) : - nCapacity( src.nCapacity ), - nFilled( 0 ), - nDeleted( 0 ), - bFilled( NULL ), - bDeleted( NULL ), - aKeys( NULL ), - aHashCodes( NULL ) - { - nKeysSize = bitsToBytes( nCapacity ); - bFilled = ca.allocate( nKeysSize ); - bDeleted = ca.allocate( nKeysSize ); - clearBits(); - - aHashCodes = ca.allocate( nCapacity ); - aKeys = ka.allocate( nCapacity ); - - for( uint32_t j = 0; j < src.nCapacity; j++ ) - { - if( src.isFilled( j ) ) - { - insert( src.aKeys[j] ); - } - } - } - - /** - * Set assignment operator. Clears this hashtable and - * copies RH into it. - */ - Set &operator=( const Set &src ) - { - for( uint32_t j = 0; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - if( !isDeleted( j ) ) - { - ka.destroy( &aKeys[j] ); - } - } - ka.deallocate( aKeys, nCapacity ); - ca.deallocate( bFilled, nKeysSize ); - ca.deallocate( bDeleted, nKeysSize ); - ca.deallocate( aHashCodes, nCapacity ); - - nFilled = 0; - nDeleted = 0; - nCapacity = src.nCapacity; - nKeysSize = bitsToBytes( nCapacity ); - bFilled = ca.allocate( nKeysSize ); - bDeleted = ca.allocate( nKeysSize ); - clearBits(); - - aHashCodes = ca.allocate( nCapacity ); - aKeys = ka.allocate( nCapacity ); - - for( uint32_t j = 0; j < src.nCapacity; j++ ) - { - if( src.isFilled( j ) ) - { - insert( src.aKeys[j] ); - } - } - - return *this; - } - - virtual ~Set() - { - for( uint32_t j = 0; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - if( !isDeleted( j ) ) - { - ka.destroy( &aKeys[j] ); - } - } - ka.deallocate( aKeys, nCapacity ); - ca.deallocate( bFilled, nKeysSize ); - ca.deallocate( bDeleted, nKeysSize ); - ca.deallocate( aHashCodes, nCapacity ); - } - - /** - * Get the current hash table capacity. (Changes at re-hash) - *@returns (uint32_t) The current capacity. - */ - uint32_t getCapacity() - { - return nCapacity; - } - - /** - * Get the number of hash locations spoken for. (Including - * not-yet-cleaned-up deleted items.) - *@returns (uint32_t) The current fill state. - */ - uint32_t getFill() - { - return nFilled; - } - - /** - * Get the number of items stored in the hash table. - *@returns (uint32_t) The number of items stored in the hash table. - */ - uint32_t getSize() - { - return nFilled-nDeleted; - } - - /** - * Get the number of items which have been deleted, but not yet - * cleaned up. - *@returns (uint32_t) The number of deleted items. - */ - uint32_t getDeleted() - { - return nDeleted; - } - - /** - * Insert key (k) into the set - *@param k (key_type) Key to list the value under. - */ - virtual void insert( key k ) - { - uint32_t hash = __calcHashCode( k ); - bool bFill; - uint32_t nPos = probe( hash, k, bFill ); - - if( bFill ) - { - onUpdate(); - } - else - { - fill( nPos, k, hash ); - onInsert(); - } - } - - /** - * Remove a value from the hash table. - *@param k (key_type) The data under this key will be erased. - */ - virtual void erase( key k ) - { - uint32_t hash = __calcHashCode( k ); - bool bFill; - uint32_t nPos = probe( hash, k, bFill ); - - if( bFill ) - { - _erase( nPos ); - onDelete(); - } - } - - struct iterator; - - /** - * Remove a value from the hash pointed to from an iterator. - *@param i (iterator &) The data to be erased. - */ - virtual void erase( struct iterator &i ) - { - if( this != &i.hsh ) - throw SetException("This iterator didn't come from this Hash."); - if( isFilled( i.nPos ) && !isDeleted( i.nPos ) ) - { - _erase( i.nPos ); - onDelete(); - } - } - - /** - * Remove all data from the hash table. - */ - virtual void clear() - { - for( uint32_t j = 0; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - if( !isDeleted( j ) ) - { - _erase( j ); - onDelete(); - } - } - - clearBits(); - } - - /** - * Does the hash table contain an item under key (k). - *@param k (key_type) The key to check. - *@returns (bool) Whether there was an item in the hash under key (k). - */ - virtual bool has( key k ) - { - bool bFill; - probe( __calcHashCode( k ), k, bFill, false ); - - return bFill; - } - - /** - * Iteration structure for iterating through the hash. - */ - typedef struct iterator - { - friend class Set; - private: - iterator( Set &hsh ) : - hsh( hsh ), - nPos( 0 ), - bFinished( false ) - { - nPos = hsh.getFirstPos( bFinished ); - } - - iterator( Set &hsh, bool bDone ) : - hsh( hsh ), - nPos( 0 ), - bFinished( bDone ) - { - } - - Set &hsh; - uint32_t nPos; - bool bFinished; - - public: - /** - * Iterator incrementation operator. Move the iterator forward. - */ - iterator operator++( int ) - { - if( bFinished == false ) - nPos = hsh.getNextPos( nPos, bFinished ); - - return *this; - } - - /** - * Iterator incrementation operator. Move the iterator forward. - */ - iterator operator++() - { - if( bFinished == false ) - nPos = hsh.getNextPos( nPos, bFinished ); - - return *this; - } - - /** - * Iterator equality comparison operator. Iterators the same? - */ - bool operator==( const iterator &oth ) const - { - if( bFinished != oth.bFinished ) - return false; - if( bFinished == true ) - { - return true; - } - else - { - if( oth.nPos == nPos ) - return true; - return false; - } - } - - /** - * Iterator not equality comparison operator. Not the same? - */ - bool operator!=( const iterator &oth ) const - { - return !(*this == oth ); - } - - /** - * Iterator assignment operator. - */ - iterator operator=( const iterator &oth ) - { - if( &hsh != &oth.hsh ) - throw SetException( - "Cannot mix iterators from different set objects."); - nPos = oth.nPos; - bFinished = oth.bFinished; - } - - /** - * Iterator dereference operator... err.. get the value - *@returns (value_type &) The value behind this iterator. - */ - key &operator *() - { - return hsh.getKeyAtPos( nPos ); - } - - const key &operator *() const - { - return hsh.getKeyAtPos( nPos ); - } - - bool isValid() const - { - return !bFinished; - } - - operator bool() const - { - return !bFinished; - } - } iterator; - - /** - * Iteration structure for iterating through the set (const). - */ - typedef struct const_iterator - { - friend class Set; - private: - const_iterator( const Set &hsh ) : - hsh( hsh ), - nPos( 0 ), - bFinished( false ) - { - nPos = hsh.getFirstPos( bFinished ); - } - - const_iterator( const Set &hsh, bool bDone ) : - hsh( hsh ), - nPos( 0 ), - bFinished( bDone ) - { - } - - const Set &hsh; - uint32_t nPos; - bool bFinished; - - public: - /** - * Iterator incrementation operator. Move the iterator forward. - */ - const_iterator operator++( int ) - { - if( bFinished == false ) - nPos = hsh.getNextPos( nPos, bFinished ); - - return *this; - } - - /** - * Iterator incrementation operator. Move the iterator forward. - */ - const_iterator operator++() - { - if( bFinished == false ) - nPos = hsh.getNextPos( nPos, bFinished ); - - return *this; - } - - /** - * Iterator equality comparison operator. Iterators the same? - */ - bool operator==( const const_iterator &oth ) const - { - if( bFinished != oth.bFinished ) - return false; - if( bFinished == true ) - { - return true; - } - else - { - if( oth.nPos == nPos ) - return true; - return false; - } - } - - /** - * Iterator not equality comparison operator. Not the same? - */ - bool operator!=( const const_iterator &oth ) const - { - return !(*this == oth ); - } - - /** - * Iterator assignment operator. - */ - const_iterator operator=( const const_iterator &oth ) - { - if( &hsh != &oth.hsh ) - throw SetException( - "Cannot mix iterators from different hash objects."); - nPos = oth.nPos; - bFinished = oth.bFinished; - } - - /** - * Iterator dereference operator... err.. get the value - *@returns (value_type &) The value behind this iterator. - */ - const key &operator *() const - { - return hsh.getKeyAtPos( nPos ); - } - - bool isValid() const - { - return !bFinished; - } - - operator bool() const - { - return !bFinished; - } - } const_iterator; - - /** - * Get an iterator pointing to the first item in the hash table. - *@returns (iterator) An iterator pointing to the first item in the - * hash table. - */ - iterator begin() - { - return iterator( *this ); - } - - const_iterator begin() const - { - return const_iterator( *this ); - } - - /** - * Get an iterator pointing to a point just past the last item in the - * hash table. - *@returns (iterator) An iterator pointing to a point just past the - * last item in the hash table. - */ - iterator end() - { - return iterator( *this, true ); - } - - const_iterator end() const - { - return const_iterator( *this, true ); - } - - /** - * Get a list of all the keys in the hash table. - *@returns (std::list) The list of keys in the hash table. - */ - Bu::List getKeys() const - { - Bu::List lKeys; - - for( uint32_t j = 0; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - { - if( !isDeleted( j ) ) - { - lKeys.append( aKeys[j] ); - } - } - } - - return lKeys; - } - - protected: - virtual void onInsert() {} - virtual void onUpdate() {} - virtual void onDelete() {} - virtual void onReHash() {} - - virtual void clearBits() - { - for( uint32_t j = 0; j < nKeysSize; j++ ) - { - bFilled[j] = bDeleted[j] = 0; - } - } - - virtual void fill( uint32_t loc, key &k, uint32_t hash ) - { - bFilled[loc/32] |= (1<<(loc%32)); - ka.construct( &aKeys[loc], k ); - aHashCodes[loc] = hash; - nFilled++; - //printf("Filled: %d, Deleted: %d, Capacity: %d\n", - // nFilled, nDeleted, nCapacity ); - } - - virtual void _erase( uint32_t loc ) - { - bDeleted[loc/32] |= (1<<(loc%32)); - ka.destroy( &aKeys[loc] ); - nDeleted++; - //printf("Filled: %d, Deleted: %d, Capacity: %d\n", - // nFilled, nDeleted, nCapacity ); - } - - virtual key &getKeyAtPos( uint32_t nPos ) - { - return aKeys[nPos]; - } - - virtual const key &getKeyAtPos( uint32_t nPos ) const - { - return aKeys[nPos]; - } - - virtual uint32_t getFirstPos( bool &bFinished ) const - { - for( uint32_t j = 0; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - if( !isDeleted( j ) ) - return j; - } - - bFinished = true; - return 0; - } - - virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const - { - for( uint32_t j = nPos+1; j < nCapacity; j++ ) - { - if( isFilled( j ) ) - if( !isDeleted( j ) ) - return j; - } - - bFinished = true; - return 0; - } - - uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true ) - { - uint32_t nCur = hash%nCapacity; - - // First we scan to see if the key is already there, abort if we - // run out of probing room, or we find a non-filled entry - int8_t j; - for( j = 0; - isFilled( nCur ) && j < 32; - nCur = (nCur + (1< - Archive &operator<<( Archive &ar, const Set &h ) - { - ar << h.getSize(); - for( typename Set::const_iterator i = h.begin(); i != h.end(); i++ ) - { - ar << (*i); - } - - return ar; - } - - template - Archive &operator>>( Archive &ar, Set &h ) - { - h.clear(); - long nSize; - ar >> nSize; - - for( long j = 0; j < nSize; j++ ) - { - key v; - ar >> v; - h.insert( v ); - } - - return ar; - } } #endif diff --git a/src/sharedcore.h b/src/sharedcore.h index 5a44df9..ac36606 100644 --- a/src/sharedcore.h +++ b/src/sharedcore.h @@ -15,10 +15,10 @@ namespace Bu { - template + template class SharedCore { - typedef class SharedCore _SharedType; + typedef class SharedCore _SharedType; public: SharedCore() : core( NULL ), @@ -54,6 +54,18 @@ namespace Bu return *iRefCount; } + Shell clone() const + { + Shell s( dynamic_cast(*this) ); + s._hardCopy(); + return s; + } + + bool isCoreShared( const Shell &rOther ) const + { + return rOther.core == core; + } + protected: Core *core; void _hardCopy() @@ -68,6 +80,20 @@ namespace Bu iRefCount = new int( 1 ); } + /** + * Reset core acts like a hard copy, except instead of providing a + * standalone copy of the shared core, it provides a brand new core. + * + * Very useful in functions used to reset the state of an object. + */ + void _resetCore() + { + if( core ) + _deref(); + core = _allocateCore(); + iRefCount = new int( 1 ); + } + virtual Core *_allocateCore() { return new Core(); diff --git a/src/tests/sharedcore.cpp b/src/tests/sharedcore.cpp index 1d0c16e..9b0a0ec 100644 --- a/src/tests/sharedcore.cpp +++ b/src/tests/sharedcore.cpp @@ -14,7 +14,7 @@ struct ShintCore { int val; }; -class Shint : public Bu::SharedCore +class Shint : public Bu::SharedCore { public: Shint() diff --git a/src/unit/hash.unit b/src/unit/hash.unit index e3d7e42..124b074 100644 --- a/src/unit/hash.unit +++ b/src/unit/hash.unit @@ -84,4 +84,17 @@ suite Hash printf(" - \"%s\" = %d\n", i.getKey().getStr(), i.getValue() ); } */ } + + test copy + { + StrIntHash h; + h.insert("hello", 55 ); + h.insert("goodbye", -1812 ); + + StrIntHash h2 = h; + unitTest( h2.isCoreShared( h ) ); + + StrIntHash h3 = h.clone(); + unitTest( !h3.isCoreShared( h ) ); + } } -- cgit v1.2.3