1 files changed, 345 insertions, 0 deletions

diff --git a/src/hashtable.cpp b/src/hashtable.cpp
new file mode 100644
index 0000000..9dfe653
--- /dev/null
+++ b/src/hashtable.cpp
@@ -0,0 +1,345 @@
+#include <string.h>
+#include <stdio.h>
+#include <math.h>
+
+#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;
+}
+
+bool HashTable::isFilled( int j )
+{
+        return (aTable[j].id != NULL)||(aTable[j].bDeleted);
+}
+
+bool 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<<j))%nTableSize, j++
+                        );
+
+                /**
+                 * This is an ugly little hack.  If the hash table is too full in allow-
+                 * dups mode we have to fall back on a linear search, otherwise you can
+                 * only get up to 32 entries with the same name.
+                 */
+                if( isFilled( nStart ) )
+                {
+                        int nOldStart = nStart;
+                        for(
+                                nStart++;
+                                isFilled( nStart ) && nStart != nOldStart;
+                                nStart = (nStart+1)%nTableSize
+                           );
+                }
+        }
+        else
+        {
+                for(
+                        unsigned long int j=0;
+                        isFilled( nStart ) && j < 32;
+                        nStart = (nStart+(1<<j))%nTableSize, j++
+                        )
+                {
+                        if( isFilled( nStart ) )
+                        {
+                                if( hFunc->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<<j))%nTableSize, j++ )
+        {
+                if( !isFilled( nPos ) ) return NULL;
+                if( hFunc->cmpIDs( id, aTable[nPos].id ) &&
+                        aTable[nPos].bDeleted == false )
+                {
+                        if( nSkip == 0 )
+                        {
+                                return aTable[nPos].data;
+                        }
+                        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<int>(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<<j))%nTableSize, j++ )
+        {
+                if( !isFilled( nPos ) ) return false;
+                if( hFunc->cmpIDs( id, aTable[nPos].id ) &&
+                        aTable[nPos].bDeleted == false )
+                {
+                        if( nSkip == 0 )
+                        {
+                                aTable[nPos].bDeleted = true;
+//                              aTable[nPos].
+                                nSize--;
+#ifdef HASH_DEBUG_VIS
+                                printDebugLine( (const char *)id );
+#endif
+                                return true;
+                        }
+                        else
+                        {
+                                nSkip--;
+                        }
+                }
+        }
+
+        return false;
+}
+