From d3b44beef6e899b65f15a1c27bb76e255d8651d3 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Sun, 5 Aug 2007 05:27:17 +0000 Subject: Ok, the set looks like it works. That's kinda' cool. It could use a few more operators, but that's a minor issue. --- src/set.h | 399 +++++--------------------------------------------------------- 1 file changed, 32 insertions(+), 367 deletions(-) (limited to 'src/set.h') diff --git a/src/set.h b/src/set.h index 36665a6..4788804 100644 --- a/src/set.h +++ b/src/set.h @@ -1,5 +1,5 @@ -#ifndef BU_HASH_H -#define BU_HASH_H +#ifndef BU_SET_H +#define BU_SET_H #include #include @@ -16,12 +16,7 @@ namespace Bu { - subExceptionDecl( HashException ) - - enum eHashException - { - excodeNotFilled - }; + subExceptionDecl( SetException ) template uint32_t __calcHashCode( const T &k ); @@ -29,156 +24,27 @@ namespace Bu template bool __cmpHashKeys( const T &a, const T &b ); - struct __calcNextTSize_fast - { - uint32_t operator()( uint32_t nCapacity, uint32_t nFill, uint32_t nDeleted ) const - { - if( nDeleted >= nCapacity/2 ) - return nCapacity; - return nCapacity*2+1; - } - }; - - template, typename valuealloc = std::allocator, typename challoc = std::allocator > - 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 - { - friend class Hash; - private: - HashProxy( Hash &h, key *k, uint32_t nPos, uint32_t hash ) : - hsh( h ), - pKey( k ), - nPos( nPos ), - hash( hash ), - bFilled( false ) - { - } - - HashProxy( Hash &h, uint32_t nPos, _value *pValue ) : - hsh( h ), - nPos( nPos ), - pValue( pValue ), - bFilled( true ) - { - } - - Hash &hsh; - 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 &() - { - 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 &value() - { - 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._erase( nPos ); - hsh.onDelete(); - } - } - - /** - * Assign data to this point in the hash table. - *@param nval (value_type) the data to assign. - */ - _value operator=( _value nval ) - { - if( bFilled ) - { - hsh.va.destroy( pValue ); - hsh.va.construct( pValue, nval ); - hsh.onUpdate(); - } - else - { - hsh.fill( nPos, *pKey, nval, hash ); - hsh.onInsert(); - } - - 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; - } - }; + template, typename challoc = std::allocator > + class Set; /** - * Libbu Template Hash Table + * Libbu Template Set *@param key (typename) The datatype of the hashtable keys - *@param value (typename) The datatype of the hashtable data *@param sizecalc (typename) Functor to compute new table size on rehash *@param keyalloc (typename) Memory allocator for hashtable keys - *@param valuealloc (typename) Memory allocator for hashtable values *@param challoc (typename) Byte allocator for bitflags */ - template - class Hash + template + class Set { - friend struct HashProxy; public: - Hash() : + Set() : nCapacity( 11 ), nFilled( 0 ), nDeleted( 0 ), bFilled( NULL ), bDeleted( NULL ), aKeys( NULL ), - aValues( NULL ), aHashCodes( NULL ) { nKeysSize = bitsToBytes( nCapacity ); @@ -188,17 +54,15 @@ namespace Bu aHashCodes = ca.allocate( nCapacity ); aKeys = ka.allocate( nCapacity ); - aValues = va.allocate( nCapacity ); } - Hash( const Hash &src ) : + Set( const Set &src ) : nCapacity( src.nCapacity ), nFilled( 0 ), nDeleted( 0 ), bFilled( NULL ), bDeleted( NULL ), aKeys( NULL ), - aValues( NULL ), aHashCodes( NULL ) { nKeysSize = bitsToBytes( nCapacity ); @@ -208,33 +72,30 @@ namespace Bu 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 ) ) { - insert( src.aKeys[j], src.aValues[j] ); + insert( src.aKeys[j] ); } } } /** - * Hashtable assignment operator. Clears this hashtable and + * Set assignment operator. Clears this hashtable and * copies RH into it. */ - Hash &operator=( const Hash &src ) + Set &operator=( const Set &src ) { 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 ); @@ -250,31 +111,28 @@ namespace Bu 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 ) ) { - insert( src.aKeys[j], src.aValues[j] ); + insert( src.aKeys[j] ); } } return *this; } - virtual ~Hash() + virtual ~Set() { 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 ); @@ -319,33 +177,12 @@ namespace Bu return 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[]( key k ) - { - uint32_t hash = __calcHashCode( k ); - bool bFill; - uint32_t nPos = probe( hash, k, bFill ); - - if( bFill ) - { - return HashProxy( *this, nPos, &aValues[nPos] ); - } - else - { - 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. */ - virtual void insert( key k, value v ) + virtual void insert( key k ) { uint32_t hash = __calcHashCode( k ); bool bFill; @@ -353,13 +190,11 @@ namespace Bu if( bFill ) { - va.destroy( &aValues[nPos] ); - va.construct( &aValues[nPos], v ); onUpdate(); } else { - fill( nPos, k, v, hash ); + fill( nPos, k, hash ); onInsert(); } } @@ -390,7 +225,7 @@ namespace Bu virtual void erase( struct iterator &i ) { if( this != &i.hsh ) - throw HashException("This iterator didn't come from this Hash."); + throw SetException("This iterator didn't come from this Hash."); if( isFilled( i.nPos ) && !isDeleted( i.nPos ) ) { _erase( i.nPos ); @@ -408,8 +243,6 @@ namespace Bu if( isFilled( j ) ) if( !isDeleted( j ) ) { - va.destroy( &aValues[j] ); - ka.destroy( &aKeys[j] ); onDelete(); } } @@ -417,55 +250,6 @@ namespace Bu clearBits(); } - /** - * Get an item of data from the hash table. - *@param k (key_type) Key pointing to the data to be retrieved. - *@returns (value_type &) The data pointed to by (k). - */ - virtual value &get( key k ) - { - uint32_t hash = __calcHashCode( k ); - bool bFill; - uint32_t nPos = probe( hash, k, bFill ); - - if( bFill ) - { - return aValues[nPos]; - } - else - { - throw HashException( - excodeNotFilled, - "No data assosiated with that key." - ); - } - } - - /** - * Get a const item of data from the hash table. - *@param k (key_type) Key pointing to the data to be retrieved. - *@returns (const value_type &) A const version of the data pointed - * to by (k). - */ - virtual const value &get( key k ) const - { - uint32_t hash = __calcHashCode( k ); - bool bFill; - uint32_t nPos = probe( hash, k, bFill ); - - if( bFill ) - { - return aValues[nPos]; - } - else - { - throw HashException( - excodeNotFilled, - "No data assosiated with that key." - ); - } - } - /** * Does the hash table contain an item under key (k). *@param k (key_type) The key to check. @@ -484,9 +268,9 @@ namespace Bu */ typedef struct iterator { - friend class Hash; + friend class Set; private: - iterator( Hash &hsh ) : + iterator( Set &hsh ) : hsh( hsh ), nPos( 0 ), bFinished( false ) @@ -494,14 +278,14 @@ namespace Bu nPos = hsh.getFirstPos( bFinished ); } - iterator( Hash &hsh, bool bDone ) : + iterator( Set &hsh, bool bDone ) : hsh( hsh ), nPos( 0 ), bFinished( bDone ) { } - Hash &hsh; + Set &hsh; uint32_t nPos; bool bFinished; @@ -561,7 +345,7 @@ namespace Bu iterator operator=( const iterator &oth ) { if( &hsh != &oth.hsh ) - throw HashException( + throw SetException( "Cannot mix iterators from different hash objects."); nPos = oth.nPos; bFinished = oth.bFinished; @@ -571,28 +355,10 @@ namespace Bu * Iterator dereference operator... err.. get the value *@returns (value_type &) The value behind this iterator. */ - value &operator *() - { - return hsh.getValueAtPos( nPos ); - } - - /** - * Get the key behind this iterator. - *@returns (key_type &) The key behind this iterator. - */ - key &getKey() + key &operator *() { return hsh.getKeyAtPos( nPos ); } - - /** - * Get the value behind this iterator. - *@returs (value_type &) The value behind this iterator. - */ - value &getValue() - { - return hsh.getValueAtPos( nPos ); - } }; /** @@ -600,9 +366,9 @@ namespace Bu */ typedef struct const_iterator { - friend class Hash; + friend class Set; private: - const_iterator( const Hash &hsh ) : + const_iterator( const Set &hsh ) : hsh( hsh ), nPos( 0 ), bFinished( false ) @@ -610,14 +376,14 @@ namespace Bu nPos = hsh.getFirstPos( bFinished ); } - const_iterator( const Hash &hsh, bool bDone ) : + const_iterator( const Set &hsh, bool bDone ) : hsh( hsh ), nPos( 0 ), bFinished( bDone ) { } - const Hash &hsh; + const Set &hsh; uint32_t nPos; bool bFinished; @@ -677,7 +443,7 @@ namespace Bu const_iterator operator=( const const_iterator &oth ) { if( &hsh != &oth.hsh ) - throw HashException( + throw SetException( "Cannot mix iterators from different hash objects."); nPos = oth.nPos; bFinished = oth.bFinished; @@ -687,28 +453,10 @@ namespace Bu * Iterator dereference operator... err.. get the value *@returns (value_type &) The value behind this iterator. */ - const value &operator *() const - { - return hsh.getValueAtPos( nPos ); - } - - /** - * Get the key behind this iterator. - *@returns (key_type &) The key behind this iterator. - */ - const key &getKey() const + const key &operator *() const { return hsh.getKeyAtPos( nPos ); } - - /** - * Get the value behind this iterator. - *@returs (value_type &) The value behind this iterator. - */ - const value &getValue() const - { - return hsh.getValueAtPos( nPos ); - } }; /** @@ -778,10 +526,9 @@ namespace Bu } } - virtual void fill( uint32_t loc, key &k, value &v, uint32_t hash ) + virtual void fill( uint32_t loc, key &k, uint32_t hash ) { bFilled[loc/32] |= (1<<(loc%32)); - va.construct( &aValues[loc], v ); ka.construct( &aKeys[loc], k ); aHashCodes[loc] = hash; nFilled++; @@ -792,18 +539,12 @@ namespace Bu 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 std::pair getAtPos( uint32_t nPos ) - { - return std::pair(aKeys[nPos],aValues[nPos]); - } - virtual key &getKeyAtPos( uint32_t nPos ) { return aKeys[nPos]; @@ -814,16 +555,6 @@ namespace Bu 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++ ) @@ -938,7 +669,6 @@ namespace Bu uint32_t *aOldHashCodes = aHashCodes; uint32_t nOldKeysSize = nKeysSize; uint32_t *bOldDeleted = bDeleted; - value *aOldValues = aValues; key *aOldKeys = aKeys; // Calculate new sizes @@ -952,7 +682,6 @@ namespace Bu aHashCodes = ca.allocate( nCapacity ); aKeys = ka.allocate( nCapacity ); - aValues = va.allocate( nCapacity ); nDeleted = nFilled = 0; @@ -962,7 +691,7 @@ namespace Bu if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && (bOldDeleted[j/32]&(1<<(j%32)))==0 ) { - insert( aOldKeys[j], aOldValues[j] ); + insert( aOldKeys[j] ); } } @@ -971,11 +700,9 @@ namespace Bu { if( (bOldFilled[j/32]&(1<<(j%32)))!=0 ) { - va.destroy( &aOldValues[j] ); ka.destroy( &aOldKeys[j] ); } } - va.deallocate( aOldValues, nOldCapacity ); ka.deallocate( aOldKeys, nOldCapacity ); ca.deallocate( bOldFilled, nOldKeysSize ); ca.deallocate( bOldDeleted, nOldKeysSize ); @@ -1000,73 +727,11 @@ namespace Bu 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 int &k ); - template<> bool __cmpHashKeys( const int &a, const int &b ); - - template<> uint32_t __calcHashCode( const unsigned int &k ); - template<> bool __cmpHashKeys( const unsigned int &a, const unsigned int &b ); - - template<> uint32_t __calcHashCode( const char * const &k ); - template<> bool __cmpHashKeys( const char * const &a, const char * const &b ); - - template<> uint32_t __calcHashCode( char * const &k ); - template<> bool __cmpHashKeys( char * const &a, char * const &b ); - - template<> uint32_t __calcHashCode( const std::string &k ); - template<> bool __cmpHashKeys( const std::string &a, const std::string &b ); - - /* - template - Archive &operator<<( Archive &ar, Hash &h ) - { - ar << h.size(); - for( typename Hash::iterator i = h.begin(); i != h.end(); i++ ) - { - std::pair p = *i; - ar << p.first << p.second; - } - - return ar; - } - - template - Archive &operator>>( Archive &ar, Hash &h ) - { - h.clear(); - uint32_t nSize; - ar >> nSize; - - for( uint32_t j = 0; j < nSize; j++ ) - { - key k; value v; - ar >> k >> v; - h.insert( k, v ); - } - - return ar; - }*/ - - /* - template - Serializer &operator&&( Serializer &ar, Hash &h ) - { - if( ar.isLoading() ) - { - return ar >> h; - } - else - { - return ar << h; - } - }*/ } #endif -- cgit v1.2.3