//--------------------------------------------------------------------
// File: sighash.cpp
// Nov. 16 2001
// K.Becker
//
// simulation of signature hashing 

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

#define NKEYS 11
#define MAXSIZE 11
#define MAXSIG 15
#define EMPTY -1

int    KeyList[NKEYS] = { 17,35,14,16,25,29,24,27,36,13,28 };
int    SigTable[MAXSIZE];
int    HTable[MAXSIZE];
int    OffSet[MAXSIZE];
int    AddrSpace = MAXSIZE;

int    debug = 2;     // debug OFF

int 
	   key,      // key to hash
	   step,     // step size
	   sig;      // signature at home addr


int Hash( int key )
{
	return key % AddrSpace;
}

int GetStep( int key)
{
	return key / AddrSpace;
}

int Signature( int key, int pos )
{		 
	// given key and a position in the primary probe chain
	// calculate the appropriate signature value
	if (pos == 0) 
		return key % 15;
	else
		return (Signature(key, pos-1)+1) * key % 15;
}

//-------------------------------------------------------//
int next ( int loc, int stepsize )
{
	// calculate the next location in the table
	// with wrap-around 
	// wraps as often as necessary 
	int v;
	
	v = loc + stepsize;
	while ( v >= AddrSpace )
		v -= AddrSpace;
	return v;
	
} // next

//-------------------------------------------------------//
int prev ( int loc, int stepsize )
{
	// calculate the next location in the table
	// going backwards (with wrap-around)
	int v;
	
	v = loc - stepsize;
	while ( v < 0 )
		v += AddrSpace;
	return v;
	
} // prev

void PrintTable()
{
	int i;

	printf("\nLoc  Sep  Off  Rec\n");
	for( i=0; i < MAXSIZE; i++)
		printf(" %2i   %2i   %2i   %2i\n",
			i, SigTable[i], OffSet[i], HTable[i]);
	printf("\n");
}

void PlaceKey(int key, int home, int step)
{
	int loc = home;
	int pos = 0;
	int done = 0;
	int resKeySig;
	int tkey, tpos, tsig;	
	char c;
	
	// find place in sig table
	while( sig > SigTable[loc])
	{ // go to next place in probe chain
		pos++;
		loc = next(loc,step);
		sig = Signature(key,pos);
		printf("SigTable[%i] = %i\n",
			loc, SigTable[loc]);
	}
	// now sig <= SigTable[loc]
	while( !done )
	{
		// look in file
		if (HTable[loc] == EMPTY)
		{ // place key
			printf("Placing key %i at %i\n",key,loc);
			HTable[loc] = key;
			OffSet[loc] = pos;
			PrintTable();
			return;
		}
		else // collision; find out who gets to stay
		{
			resKeySig = Signature(HTable[loc], OffSet[loc]);
			printf("ResKey = %i Pos %i Sig = %i ",
				HTable[loc],OffSet[loc],resKeySig);
			
			if (resKeySig <= sig)// resKey stays
			{
				printf("Res Sig Less. ResKey stays.\n");
				// let it stay, set sig
				sig = (sig > 0)?sig - 1: sig;
				if (sig < SigTable[loc])
					SigTable[loc] = sig;
			}
			else if (resKeySig == sig)
			{
				printf("Sigs Equal. ResKey still stays.\n");
				// resKey still stays, set sig
				if (sig < SigTable[loc])
				    SigTable[loc] = sig;
			}
			else // resKeySig > sig :: new key stays
			{
				// place new key here, AND
				// retrieve resident key to re-place
				printf("ResKey moves.\n");
				tkey = HTable[loc];
				HTable[loc] = key;
				tpos = OffSet[loc];
				OffSet[loc] = pos;
				sig = Signature(tkey,tpos);
				
				// signature here gets set to resKeySig
				if (resKeySig < SigTable[pos])
				    SigTable[loc] = 
						(resKeySig > 0)?resKeySig - 1: resKeySig;
				
				key = tkey;
				pos = tpos;
				step = GetStep(tkey);
			} // else place new key
			
			// get next place in probe chain to check
			loc = next(loc,step);
			pos++;
			sig = Signature(key,pos);
			printf("looking to place %i, at: %i sig is: %i\n",
				key, loc, sig);
			printf("next?");
			scanf("%c",&c);
		} // else collision
		printf("trying again..\n");
		
	} // while not done
	
	
} // PlaceKey

int FindKey ( int key )
{
	int H,S,sep;
	int loc = Hash(key);
	int found = 0;
	int pos = 0;

	while ( !found )
	{
		S = Signature(key,pos);
		sep = SigTable[loc];
		printf("loc = %i pos = %i sep =	%i SIG = %i   ",
			loc, pos, sep, S);
		if ( S < sep )
		{
			printf("LESS, Look... ");
			if (key == HTable[loc])
			{
				printf("FOUND.\n");
				found++;
			}
			else
			{
				printf("NOT THERE.\n");
				found++;
			}
		}
		else if ( S == sep )
		{
			printf("EQUAL, Look... ");
			if (key == HTable[loc])
			{
				printf("FOUND.\n");
				found++;
			}
			else
			{
				printf("NOT THERE.Keep looking...\n");
				loc = next(loc,GetStep(key));
				pos++;
			}
		}
		else
		{
			printf("GREATER. Keep looking...\n");
			loc = next(loc,GetStep(key));
			pos++;\
		}
	}	 // while not found	

	return loc;
} // FindKey

int main( int argc, char* argv[]) {
	
	char c;	
	int more = 1;
	
	int 
		i,j;      // for indexing
	
	int    home;
	int    naddr;
	
	// initialize
	for(i = 0; i < MAXSIZE; i++)
	{
		SigTable[i] = MAXSIG;
		HTable[i] = -1;
		OffSet[i] = 0;
	}
	
	printf("Signature Hashing Simulation:\n\n");
	PrintTable();
	
	/*	// deal with debug switch
	if ((argc > 1) && (strcmp(argv[1],"-d")==0))
	debug = 1; // debug ON
	if (argc >2) // we have -d #
	debug = argv[2][0] - 48;
	
	 printf("DEBUG SWITCH IS %i.\n\n",debug);
	 if (!debug)
	 {
	 printf("To run a trace, run program with '-d' or '-d 2'\n");
	 exit(0);
	 }
	*/
	
	for (i=0; i < NKEYS; i++)
	{
		home = Hash(KeyList[i]);
		key = KeyList[i];
		sig = Signature(key, 0);
		naddr = home;
		printf("Key %i   Home %i   Sig %i\n", key,home,sig);
		PlaceKey(key,home,GetStep(key));
		printf("next?");
		scanf("%c",&c);
	} // done placing
 
	printf("Done placing keys. Hunting now...\n\n");
	while ( more )
	{
		PrintTable();
		printf("Looking for ..");
		scanf("%i%*c",&key);
		j = FindKey( key );
		printf("next?");
		scanf("%c",&c);
		if (c == 'n')
			more = 0;
	} // done hunting

	printf("Done.\n");
	
	return(0);
	
} // main

