// hashtable.h

/*
 Written by
 Huang,Jessica C : jessica9@MIT.EDU
 Huang,Kai : kaih@MIT.EDU
 Huang, Edward : eych@MIT.EDU
 Shi,Melissa F : mshi@MIT.EDU
 
 September 25, 2001

 May be freely reproduced for educational or personal use
*/

#ifndef __HASHTABLE_H__
#define __HASHTABLE_H__

#include "types.h"


typedef struct Pair_s {               // node of linked list
    Vect vect;                        // that each non-NULL
    Key key;                          // element of the
    struct Pair_s *next;              // hashtable points to
} Pair;

#define HASHSIZE 500000               // size of hashtable
typedef Pair *Hashtable[ HASHSIZE ];  // Hashtable type!


// clears the hashtable of any initial garbage
void initHash( Hashtable ht )
{
    unsigned long i;

    for ( i = 0; i < HASHSIZE; ++i )
        ht[ i ] = NULL;
}


// puts a pair (vect, key) into the hashtable
void hashPut( Hashtable ht, Vect vect, Key key )
{
    unsigned long lvect = convertVect( vect );
    unsigned long index = lvect % HASHSIZE;
    Pair *ppair;

    if ( ht[ index ] == NULL ) {
        ppair = malloc( sizeof( Pair ) );
        copyVect( ppair->vect, vect );
        copyKey( ppair->key, key );
        ppair->next = NULL;
        ht[ index ] = ppair;
    } else {
        ppair = ht[ index ];
        while ( ppair->next != NULL )
            ppair = ppair->next;
        ppair->next = malloc( sizeof( Pair ) );
        copyVect( ppair->next->vect, vect );
        copyKey( ppair->next->key, key );
        ppair->next->next = NULL;
    }
}


// searches for vect in the hashtable; if found, returns the
// corresponding key; if not found, returns NULL
Byte *hashGet( Hashtable ht, Vect vect )
{
    unsigned long lvect = convertVect( vect );
    unsigned long index = lvect % HASHSIZE;
    Pair *ppair;

    for ( ppair = ht[ index ]; ppair != NULL; ppair = ppair->next ) {
        if ( convertVect( ppair->vect ) == lvect )
            return ppair->key;
    }

    return NULL;
}


#endif //__HASHTABLE_H__