Added erase functionality, and specializations for using ints as hash keys, so

really it does everything the old one did, does it better, easier, and possibly
faster.

1 files changed, 143 insertions, 104 deletions

diff --git a/src/hash.h b/src/hash.h
index c4f4b43..ff3bafd 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -40,8 +40,9 @@ private:
         {
         }
 
-        HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, _value *pValue ) :
+        HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, uint32_t nPos, _value *pValue ) :
                 hsh( h ),
+                nPos( nPos ),
                 pValue( pValue ),
                 bFilled( true )
         {
@@ -74,6 +75,12 @@ public:
                 return bFilled;
         }
 
+        void erase()
+        {
+                if( bFilled )
+                        hsh._erase( nPos );
+        }
+
         _value operator=( _value nval )
         {
                 if( bFilled )
@@ -119,10 +126,11 @@ public:
                 for( uint32_t j = 0; j < nCapacity; j++ )
                 {
                         if( isFilled( j ) )
-                        {
-                                va.destroy( &aValues[j] );
-                                ka.destroy( &aKeys[j] );
-                        }
+                                if( !isDeleted( j ) )
+                                {
+                                        va.destroy( &aValues[j] );
+                                        ka.destroy( &aKeys[j] );
+                                }
                 }
                 va.deallocate( aValues, nCapacity );
                 ka.deallocate( aKeys, nCapacity );
@@ -167,7 +175,7 @@ public:
 
                 if( bFill )
                 {
-                        return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, &aValues[nPos] );
+                        return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, nPos, &aValues[nPos] );
                 }
                 else
                 {
@@ -192,7 +200,7 @@ public:
                 }
         }
 
-        value get( key k )
+        void erase( key k )
         {
                 uint32_t hash = __calcHashCode( k );
                 bool bFill;
@@ -200,110 +208,24 @@ public:
 
                 if( bFill )
                 {
-                        return aValues[nPos];
-                }
-                else
-                {
-                        throw "Hey, no such thing...";
-                }
-        }
-
-        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
-                for( int8_t j = 0;
-                        isFilled( nCur ) && j < 32;
-                        nCur = (nCur + (1<<j))%nCapacity, j++
-                        )
-                {
-                        // Is this the same hash code we were looking for?
-                        if( hash == aHashCodes[nCur] )
-                        {
-                                // Is it really the same key? (for safety)
-                                if( __cmpHashKeys( aKeys[nCur], k ) == true &&
-                                        isDeleted( nCur ) == false )
-                                {
-                                        bFill = true;
-                                        return nCur;
-                                }
-                        }
+                        _erase( nPos );
                 }
-
-                // This is our insurance, if the table is full, then go ahead and
-                // rehash, then try again.
-                if( isFilled( nCur ) && rehash == true )
-                {
-                        reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
-
-                        // This is potentially dangerous, and could cause an infinite loop.
-                        // Be careful writing probe, eh?
-                        return probe( hash, k, bFill );
-                }
-
-                bFill = false;
-                return nCur;
         }
 
-        void reHash( uint32_t nNewSize )
+        value get( key k )
         {
-                // Save all the old data
-                uint32_t nOldCapacity = nCapacity;
-                uint32_t *bOldFilled = bFilled;
-                uint32_t *aOldHashCodes = aHashCodes;
-                uint32_t nOldKeysSize = nKeysSize;
-                uint32_t *bOldDeleted = bDeleted;
-                value *aOldValues = aValues;
-                key *aOldKeys = aKeys;
-                
-                // Calculate new sizes
-                nCapacity = nNewSize;
-                nKeysSize = bitsToBytes( nCapacity );
-        
-                // Allocate new memory + prep
-                bFilled = ca.allocate( nKeysSize );
-                bDeleted = ca.allocate( nKeysSize );
-                clearBits();
-
-                aHashCodes = ca.allocate( nCapacity );
-                aKeys = ka.allocate( nCapacity );
-                aValues = va.allocate( nCapacity );
+                uint32_t hash = __calcHashCode( k );
+                bool bFill;
+                uint32_t nPos = probe( hash, k, bFill );
 
-                // Re-insert all of the old data (except deleted items)
-                for( uint32_t j = 0; j < nOldCapacity; j++ )
+                if( bFill )
                 {
-                        if( (bOldFilled[j/32]&(1<<(j%32)))!=0 )
-                        {
-                                insert( aOldKeys[j], aOldValues[j] );
-                        }
+                        return aValues[nPos];
                 }
-
-                // Delete all of the old data
-                for( uint32_t j = 0; j < nOldCapacity; j++ )
+                else
                 {
-                        if( (bOldFilled[j/32]&(1<<(j%32)))!=0 )
-                        {
-                                va.destroy( &aOldValues[j] );
-                                ka.destroy( &aOldKeys[j] );
-                        }
+                        throw "Hey, no such thing...";
                 }
-                va.deallocate( aOldValues, nOldCapacity );
-                ka.deallocate( aOldKeys, nOldCapacity );
-                ca.deallocate( bOldFilled, nOldKeysSize );
-                ca.deallocate( bOldDeleted, nOldKeysSize );
-                ca.deallocate( aOldHashCodes, nOldCapacity );
-        }
-
-        bool isFilled( uint32_t loc )
-        {
-                return (bFilled[loc/32]&(1<<(loc%32)))!=0;
-        }
-
-        bool isDeleted( uint32_t loc )
-        {
-                return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
         }
 
         typedef struct iterator
@@ -394,6 +316,13 @@ private:
                 nFilled++;
         }
 
+        void _erase( uint32_t loc )
+        {
+                bDeleted[loc/32] |= (1<<(loc%32));
+                va.destroy( &aValues[loc] );
+                ka.destroy( &aKeys[loc] );
+        }
+
         std::pair<key,value> getAtPos( uint32_t nPos )
         {
                 return std::pair<key,value>(aKeys[nPos],aValues[nPos]);
@@ -404,7 +333,8 @@ private:
                 for( uint32_t j = 0; j < nCapacity; j++ )
                 {
                         if( isFilled( j ) )
-                                return j;
+                                if( !isDeleted( j ) )
+                                        return j;
                 }
 
                 bFinished = true;
@@ -415,12 +345,115 @@ private:
                 for( uint32_t j = nPos+1; j < nCapacity; j++ )
                 {
                         if( isFilled( j ) )
-                                return j;
+                                if( !isDeleted( j ) )
+                                        return j;
                 }
 
                 bFinished = true;
         }
 
+        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
+                for( int8_t j = 0;
+                        isFilled( nCur ) && j < 32;
+                        nCur = (nCur + (1<<j))%nCapacity, j++
+                        )
+                {
+                        // Is this the same hash code we were looking for?
+                        if( hash == aHashCodes[nCur] )
+                        {
+                                // Skip over deleted entries.  Deleted entries are also filled,
+                                // so we only have to do this check here.
+                                if( isDeleted( nCur ) )
+                                        continue;
+
+                                // Is it really the same key? (for safety)
+                                if( __cmpHashKeys( aKeys[nCur], k ) == true )
+                                {
+                                        bFill = true;
+                                        return nCur;
+                                }
+                        }
+                }
+
+                // This is our insurance, if the table is full, then go ahead and
+                // rehash, then try again.
+                if( isFilled( nCur ) && rehash == true )
+                {
+                        reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
+
+                        // This is potentially dangerous, and could cause an infinite loop.
+                        // Be careful writing probe, eh?
+                        return probe( hash, k, bFill );
+                }
+
+                bFill = false;
+                return nCur;
+        }
+
+        void reHash( uint32_t nNewSize )
+        {
+                // Save all the old data
+                uint32_t nOldCapacity = nCapacity;
+                uint32_t *bOldFilled = bFilled;
+                uint32_t *aOldHashCodes = aHashCodes;
+                uint32_t nOldKeysSize = nKeysSize;
+                uint32_t *bOldDeleted = bDeleted;
+                value *aOldValues = aValues;
+                key *aOldKeys = aKeys;
+                
+                // Calculate new sizes
+                nCapacity = nNewSize;
+                nKeysSize = bitsToBytes( nCapacity );
+        
+                // Allocate new memory + prep
+                bFilled = ca.allocate( nKeysSize );
+                bDeleted = ca.allocate( nKeysSize );
+                clearBits();
+
+                aHashCodes = ca.allocate( nCapacity );
+                aKeys = ka.allocate( nCapacity );
+                aValues = va.allocate( nCapacity );
+
+                // 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 )
+                        {
+                                insert( aOldKeys[j], aOldValues[j] );
+                        }
+                }
+
+                // Delete all of the old data
+                for( uint32_t j = 0; j < nOldCapacity; j++ )
+                {
+                        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 );
+                ca.deallocate( aOldHashCodes, nOldCapacity );
+        }
+
+        bool isFilled( uint32_t loc )
+        {
+                return (bFilled[loc/32]&(1<<(loc%32)))!=0;
+        }
+
+        bool isDeleted( uint32_t loc )
+        {
+                return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
+        }
+
 private:
         uint32_t nCapacity;
         uint32_t nFilled;
@@ -437,6 +470,12 @@ private:
         sizecalc szCalc;
 };
 
+template<> uint32_t __calcHashCode<const int>( const int k );
+template<> bool __cmpHashKeys<const int>( const int a, const int b );
+
+template<> uint32_t __calcHashCode<int>( int k );
+template<> bool __cmpHashKeys<int>( int a, int b );
+
 template<> uint32_t __calcHashCode<const char *>( const char *k );
 template<> bool __cmpHashKeys<const char *>( const char *a, const char *b );