From 6f6bb9f9309a6d5e471579ec565d56e4d083dafb Mon Sep 17 00:00:00 2001
From: Mike Buland <eichlan@xagasoft.com>
Date: Tue, 21 Nov 2006 16:01:57 +0000
Subject: 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.

---
 src/hash.cpp       |  20 +++++
 src/hash.h         | 247 +++++++++++++++++++++++++++++++----------------------
 src/tests/hash.cpp |  26 ++++--
 3 files changed, 184 insertions(+), 109 deletions(-)

diff --git a/src/hash.cpp b/src/hash.cpp
index 14be208..0241753 100644
--- a/src/hash.cpp
+++ b/src/hash.cpp
@@ -1,5 +1,25 @@
 #include "hash.h"
 
+template<> uint32_t __calcHashCode<const int>( const int k )
+{
+	return k;
+}
+
+template<> bool __cmpHashKeys<const int>( const int a, const int b )
+{
+	return a == b;
+}
+
+template<> uint32_t __calcHashCode<int>( int k )
+{
+	return k;
+}
+
+template<> bool __cmpHashKeys<int>( int a, int b )
+{
+	return a == b;
+}
+
 template<>
 uint32_t __calcHashCode<const char *>( const char * k )
 {
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 );
 
diff --git a/src/tests/hash.cpp b/src/tests/hash.cpp
index 8406439..f9a8f12 100644
--- a/src/tests/hash.cpp
+++ b/src/tests/hash.cpp
@@ -67,11 +67,9 @@ int main()
 	}
 
 	printf("Getting\n-------------------\n\n");
-	printf("%d\n", sTest.get( names[10] ) );
-	printf("%d\n", (int)sTest[names[10]] );
-	sTest[names[10]] = 22;
-	sTest["That one guy"] = 135;
-	printf("%d\n", (int)sTest[names[10]] );
+
+	sTest.erase("Homer the Great");
+	sTest["Bart's Comet"].erase();
 
 	for( Hash<std::string, int>::iterator i = sTest.begin();
 		 i != sTest.end(); i++ )
@@ -79,5 +77,23 @@ int main()
 		Hash<std::string, int>::iterator j = i;
 		printf("%d: %s\n", (*j).second, (*j).first.c_str() );
 	}
+
+	for( int j = 0; j < 33; j++ )
+	{
+		if( sTest[names[j]].isFilled() )
+		{
+			if( sTest[names[j]] != j )
+			{
+				printf("'%s' should be %d, is %d\n",
+					names[j], j,
+					sTest[names[j]].value()
+					);
+			}
+		}
+		else
+		{
+			printf("Missing element %d, '%s'\n", j, names[j] );
+		}
+	}
 }
 
-- 
cgit v1.2.3