Welcome to Mike95.com
Home
WELCOME
ABOUT MIKE95.COM
CONTACT ME


Features
FUNNY JOKES
HUMAN FACTOR


C++
Library Source Code:
CGIPARSE
JSTRING
JVECTOR
JSTACK
JHASHTABLE


COM / ASP
MIKE95 COM SVR
- ASP STACK
- ASP QUEUE
- ASP VECTOR


Tutorials:
TEMPLATES
ALGORITHMS
DESIGN PATTERNS


Sample Work
Internet Based
TASK/BUG TRACKER


Visual C++ / MFC
FLIGHT PATH (C++)
MP3 PLAY LIST


Java
JAVA TALK
BAR GRAPH
WEB CAM


Personal
CONTACT ME
RESUME
PICTURES
TRIPS
JHashtable
#include "JHashtable.h"

template <class KeyType, class ObjType>
JHashtable<KeyType,ObjType>::JHashtable( UINT initialCapacity, float loadFactor )
{
    if ( loadFactor <= 0.0 )
    {
        cerr << "Bad Argument for loadFactor" << endl;
        exit(1);
    }

    m_count = 0;
    m_tableSize = initialCapacity;
    m_loadFactor = loadFactor;
    m_threshold = (UINT)(initialCapacity * loadFactor);

    //initialize and set to null
    //==========================
    m_table = new JHashtableEntry*[m_tableSize];
    memset( m_table, 0, sizeof(JHashtableEntry*) * m_tableSize );

    //nullify the user hash function pointer
    UserHash = NULL;
}

template <class KeyType, class ObjType>
JHashtable<KeyType,ObjType>::~JHashtable( )
{
    clear();
    delete [] m_table;
}

template <class KeyType, class ObjType>
bool
JHashtable<KeyType,ObjType>::contains( const ObjType& value ) const
{
    JHashtableEntry** tab = m_table;
    for( UINT i = 0; i < m_tableSize; i++ )
    {
        for( JHashtableEntry* e = tab[i]; e != NULL; e = e->next )
        {
            if ( e->value == value )
                return true;
        }
    }

    return false;
}

template <class KeyType, class ObjType>
bool
JHashtable<KeyType,ObjType>::containsKey( const KeyType& key ) const
{
    return FindEntryByKey( key ) == NULL;
}


template <class KeyType, class ObjType>
const ObjType&
JHashtable<KeyType,ObjType>::get( const KeyType& key )
{
    JHashtableEntry* entry = FindEntryByKey( key );
    
    if ( entry != NULL )
        return entry->value;
    
    return NULL_ITEM; //if not found
}

template <class KeyType, class ObjType>
void
JHashtable<KeyType,ObjType>::rehash()
{
    UINT oldTableSize = m_tableSize;
    JHashtableEntry** oldTable = m_table;

    UINT newTableSize = nextPrime( 2 * oldTableSize );
    JHashtableEntry** newTable = new JHashtableEntry*[newTableSize];
    
    memset( newTable, 0, sizeof(JHashtableEntry*) * newTableSize );
    

    m_threshold = (UINT)(newTableSize * m_loadFactor);
    m_table = newTable;

    //copy all the entries from the old to the new table
    for( i = 0; i < oldTableSize; i++ )
    {
        for( JHashtableEntry* old = oldTable[i]; old != NULL; )
        {
            JHashtableEntry* e = old;
            old = old->next;

            UINT index = e->hash % newTableSize;
            e->next = newTable[index];
            newTable[index] = e;
        }
    }

    m_tableSize = newTableSize;

    delete [] oldTable;
}

template <class KeyType, class ObjType>
ObjType
JHashtable<KeyType,ObjType>::put( const KeyType& key, const ObjType& value )
{
    //Makes sure the key is not already in the hashtable
    //replace item if found
    JHashtableEntry* e = FindEntryByKey( key );    
    if ( e != NULL )
    {
            ObjType old = e->value;
            e->value = value;
            return old;
    }
    

    //Rehash the table if the threshold is exceeded
    if ( m_count >= m_threshold )
    {
        rehash();
        return put( key, value );
    }

    //Creates the new entry here
    e = new JHashtableEntry();
    e->hash = hash;
    e->key = key;
    e->value = value;
    
    JHashtableEntry* row = GetHashRow( key );
    e->next = row;
    *row = e;
    m_count++;

    return NULL_ITEM;
}

template <class KeyType, class ObjType>
ObjType
JHashtable<KeyType,ObjType>::remove( const KeyType& key )
{
    JHashtableEntry* hashRow = GetHashRow( key );
    
    for( JHashtableEntry* e = hashRow, *prev = NULL; e != NULL; prev = e, e = e->next)
    {
        if ( e->hash == hash && e->key == key )
        {
            if ( prev != NULL )
                prev->next = e->next;
            else
                tab[index] = tab[index]->next;

            ObjType theReturn = e->value;
            delete e;
            m_count--;    //decrement counter
            return theReturn;
        }
    }

    return NULL_ITEM;
}

template <class KeyType, class ObjType>
void
JHashtable<KeyType,ObjType>::clear()
{
    JHashtableEntry** tab = m_table;
    
    for(UINT i = 0; i < m_tableSize; i++ )
    {
        JHashtableEntry* e = tab[i];
        while( e != NULL )
        {
            JHashtableEntry* tmp = e;
            e = e->next;
            delete tmp;
        }
        
        tab[i] = NULL;
    }

    //reset the counter
    m_count = 0;
}

template <class KeyType, class ObjType>
UINT
JHashtable<KeyType,ObjType>::nextPrime( UINT start )
{
    if( start % 2 == 0 )
        start++;

    UINT i;

    for( ; ; start += 2 )
    {
        for( i = 3; i * i <= start; i += 2 )
            if( start % i == 0 )
                break;

        if( i * i > start )
            return start;
    }
}


template <class KeyType, class ObjType>
typename JHashtable<KeyType,ObjType>::JHashtableEntry*
JHashtable<KeyType,ObjType>::FindEntryByKey( const KeyType& key )
{
    JHashtable<KeyType,ObjType>::JHashtableEntry* hashRow = GetHashRow( key );
    
    for( JHashtableEntry* e = hashRow; e != NULL; e = e->next )
    {
        if ( e->hash == hash && e->key == key )
            return e->value;
    }

    return NULL;
}

template <class KeyType, class ObjType>
typename JHashtable<KeyType,ObjType>::JHashtableEntry*
JHashtable<KeyType,ObjType>::GetHashRow( const KeyType& key )
{
    JHashtable<KeyType,ObjType>::JHashtableEntry** tab = m_table;
    UINT hash = (*UserHash)(key);
    UINT index = hash % m_tableSize;

    return tab[index];
}


(c)2017 Mike95.com / Site Disclaimer
Site Meter