From f4c20290509d7ed3a8fd5304577e7a4cc0b9d974 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Tue, 3 Apr 2007 03:49:53 +0000 Subject: Ok, no code is left in src, it's all in src/old. We'll gradually move code back into src as it's fixed and re-org'd. This includes tests, which, I may write a unit test system into libbu++ just to make my life easier. --- src/hashtable.cpp | 424 ------------------------------------------------------ 1 file changed, 424 deletions(-) delete mode 100644 src/hashtable.cpp (limited to 'src/hashtable.cpp') diff --git a/src/hashtable.cpp b/src/hashtable.cpp deleted file mode 100644 index dbcd964..0000000 --- a/src/hashtable.cpp +++ /dev/null @@ -1,424 +0,0 @@ -#include -#include -#include - -#include "hashtable.h" - -HashTable::HashTable( HashFunction *hNewFunc, unsigned long int nInitSize, bool bAllowDupes ) -{ - hFunc = hNewFunc; - nTableSize = nextPrime( nInitSize ); - aTable = new HashNode[nTableSize]; - //for( int j = 0; j < nTableSize; j++ ) if( aTable[j].id || aTable[j].data || aTable[j].bDeleted ) printf("Unclean entry\n"); - nSize = 0; - nFilled = 0; - this->bAllowDupes = bAllowDupes; -} - -HashTable::~HashTable() -{ - delete[] aTable; - delete hFunc; -} - -void HashTable::set( int j, const void *newID, const void *newData ) -{ - if( newData == NULL ) - { - printf("Inserting NULL data is indestinguishable from uninserted data!\n"); - } - aTable[j].id = newID; - aTable[j].data = newData; -} - -void HashTable::clear() -{ - memset( aTable, 0, sizeof(HashNode) * nTableSize ); -} - -bool HashTable::isFilled( int j ) -{ - return (aTable[j].id != NULL)||(aTable[j].bDeleted); -} - -void HashTable::reHash( unsigned long int nNewSize ) -{ - HashNode *aOldTable = aTable; - unsigned long int oldSize = nTableSize; - - // If the table can still be used if we just get rid of deleted items, don't - // change the size of the table, otherwise, go ahead and use the number - // passed in. - if( nSize > nTableSize>>1 ) - { - nTableSize = nextPrime( nNewSize ); - } - - aTable = newTable( nTableSize ); - //for( int j = 0; j < nTableSize; j++ ) if( aTable[j].id || aTable[j].data || aTable[j].bDeleted ) printf("Unclean entry\n"); - - nSize = 0; - nFilled = 0; - - for( unsigned long int j = 0; j < oldSize; j++ ) - { - if( aOldTable[j].id != NULL && aOldTable[j].bDeleted == false ) - { - insert( aOldTable[j].id, aOldTable[j].data ); - } - } - - delete[] aOldTable; -} - -unsigned long int HashTable::probe( unsigned long int nStart, const void *id ) -{ - int nHash = nStart; - nStart = nStart%nTableSize; - if( bAllowDupes == true ) - { - for( - unsigned long int j=0; - isFilled( nStart ) && j < 32; - nStart = (nStart+(1<cmpIDs( aTable[nStart].id, id ) == true && - aTable[nStart].bDeleted == false ) - { - return nStart; - } - } - } - } - // This is our insurance, if the table is full, then go ahead and rehash, - // then try again. - if( isFilled( nStart ) ) - { - reHash( getCapacity()*2 ); - return probe( nHash, id ); - } - return nStart; -} - -HashTable::HashNode *HashTable::newTable( unsigned long int nNewSize ) -{ - return new HashNode[nNewSize]; -} - -#ifdef HASH_DEBUG_VIS -void HashTable::printDebugLine( const char *exData ) -{ - char *buf = new char[getCapacity()+3]; - int j; - buf[0] = '['; - for( j = 0; j < getCapacity(); j++ ) - { - buf[j+1] = (aTable[j].bDeleted)?('X'):((isFilled( j ))?('#'):('-')); - } - buf[j+1] = ']'; - buf[j+2] = '\0'; - printf("%s %s\n", buf, exData ); - delete[] buf; -} -#endif - -bool HashTable::insert( const void *id, const void *data ) -{ - unsigned long int nPos = probe( hFunc->hash( id ), id )%nTableSize; - - if( bAllowDupes == true ) - { - if( aTable[nPos].id == NULL && aTable[nPos].bDeleted == false ) - { - set( nPos, id, data ); -#ifdef HASH_DEBUG_VIS - printDebugLine( (const char *)id ); -#endif - nSize++; - nFilled++; - return true; - } - else - { - return false; - } - } - else - { - if( aTable[nPos].id == NULL && aTable[nPos].bDeleted == false ) - { - set( nPos, id, data ); -#ifdef HASH_DEBUG_VIS - printDebugLine( (const char *)id ); -#endif - nSize++; - nFilled++; - return true; - } - else if( hFunc->cmpIDs( aTable[nPos].id, id ) == true ) - { - set( nPos, id, data ); -#ifdef HASH_DEBUG_VIS - printDebugLine( (const char *)id ); -#endif - return true; - } - else - { - return false; - } - } -} - -const void *HashTable::get( const void *id, unsigned long int nSkip ) -{ - unsigned long int nPos = hFunc->hash( id )%nTableSize; - - for( unsigned long int j=0; j < 32; nPos = (nPos+(1<cmpIDs( id, aTable[nPos].id ) ) - { - if( nSkip == 0 ) - { - return aTable[nPos].data; - } - else - { - nSkip--; - } - } - } - } - - if( bAllowDupes ) - { - unsigned long int nOldPos = nPos; - for( nPos++; nPos != nOldPos; nPos=(nPos+1)%nTableSize ) - { - if( !isFilled( nPos ) ) return NULL; - if( aTable[nPos].bDeleted == false ) - { - if( hFunc->cmpIDs( id, aTable[nPos].id ) ) - { - if( nSkip == 0 ) - { - return aTable[nPos].data; - } - else - { - nSkip--; - } - } - } - } - } - - return NULL; -} - -const void *HashTable::getKey( const void *id, unsigned long int nSkip ) -{ - unsigned long int nPos = hFunc->hash( id )%nTableSize; - - for( unsigned long int j=0; j < 32; nPos = (nPos+(1<cmpIDs( id, aTable[nPos].id ) ) - { - if( nSkip == 0 ) - { - return aTable[nPos].id; - } - else - { - nSkip--; - } - } - } - } - - if( bAllowDupes ) - { - unsigned long int nOldPos = nPos; - for( nPos++; nPos != nOldPos; nPos=(nPos+1)%nTableSize ) - { - if( !isFilled( nPos ) ) return NULL; - if( aTable[nPos].bDeleted == false ) - { - if( hFunc->cmpIDs( id, aTable[nPos].id ) ) - { - if( nSkip == 0 ) - { - return aTable[nPos].id; - } - else - { - nSkip--; - } - } - } - } - } - - return NULL; -} - -void *HashTable::getFirstItemPos() -{ - HashPos *pos = new HashPos; - return pos; -} - -const void *HashTable::getItemData( void *xPos ) -{ - return aTable[((HashPos *)xPos)->nPos].data; -} - -const void *HashTable::getItemID( void *xPos ) -{ - return aTable[((HashPos *)xPos)->nPos].id; -} - -void *HashTable::getNextItemPos( void *xPos ) -{ - HashPos *pos = (HashPos *)xPos; - if( pos->bStarted == false ) - { - pos->bStarted = true; - pos->nPos = 0; - } - else - { - pos->nPos++; - } - if( pos->nPos < nTableSize ) - { - for( ; pos->nPos < nTableSize; pos->nPos++ ) - { - if( isFilled( pos->nPos ) && - aTable[pos->nPos].bDeleted == false ) - { - return xPos; - } - } - } - - delete pos; - - return NULL; -} - -// Big-O sqrt(n) -// Change this to be erethpothynies table with a storage -// lookup later on. -bool HashTable::isPrime (int num) -{ - if (num == 2) // the only even prime - return true; - else if (num % 2 == 0) // other even numbers are composite - return false; - else - { - //bool prime = true; - int divisor = 3; - int upperLimit = static_cast(sqrt(num) + 1); - while (divisor <= upperLimit) - { - if (num % divisor == 0) - return false; - // prime = false; - divisor +=2; - } - return true; - } -} - -// Big-O n^(3/2) -int HashTable::nextPrime( int base ) -{ - int nPrime; - for( nPrime = base; isPrime( nPrime ) == false; nPrime++ ); - return nPrime; -} - -unsigned long int HashTable::getCapacity() -{ - return nTableSize; -} - -unsigned long int HashTable::getSize() -{ - return nSize; -} - -double HashTable::getLoad() -{ - return (double)(nFilled)/(double)(nTableSize); -} - -const void *HashTable::operator[](const void *id) -{ - return get( id ); -} - -bool HashTable::del( const void *id, int nSkip ) -{ - unsigned long int nPos = hFunc->hash( id )%nTableSize; - - for( unsigned long int j=0; j < 32; nPos = (nPos+(1<cmpIDs( id, aTable[nPos].id ) && - aTable[nPos].bDeleted == false ) - { - if( nSkip == 0 ) - { - aTable[nPos].bDeleted = true; - nSize--; -#ifdef HASH_DEBUG_VIS - printDebugLine( (const char *)id ); -#endif - return true; - } - else - { - nSkip--; - } - } - } - - return false; -} - -- cgit v1.2.3