#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/time.h>

#define	INPUT_SIZE	1000000


struct hashentry
{
	int  value;
	struct hashentry *previous;
	struct hashentry *next;
};

struct hashentry *hashtable[INPUT_SIZE];
void makehash(int []);
int hashthis(int);
void print_column(int);
int find_element(int);

int main()
{
	struct hashentry test1, test2;
	struct hashentry *test;
	int inputs[INPUT_SIZE];
	int i, result;
	double en, st;
	double sum=0.0;
	double microseconds = 1000000.0;
	struct timeval start_time, stop_time;   

	srand(getpid());
	for (i=0; i<INPUT_SIZE; i++)
		inputs[i]=rand();	
	
	makehash(inputs);
	
	for (i=0; i<INPUT_SIZE; i++)
	{
	
		gettimeofday(&start_time, (struct timezone *) 0);
		if(i%2 == 0)
			result=find_element(inputs[i]);
		else 
			result=find_element(i);	
		
		gettimeofday(&stop_time, (struct timezone *)0);
	
		st = start_time.tv_sec + (start_time.tv_usec/microseconds);
		en = stop_time.tv_sec + (stop_time.tv_usec/microseconds);
		sum=sum+en-st;
	}

	printf("%f\n", sum);
	printf("%f\n", sum/INPUT_SIZE);
	exit(0);
}

int hashthis(int this)
{
	return this%1000000;;
	
}

void makehash(int array[])
{
	int i, slot;
	struct hashentry *hash_pointer;
	
	for (i=0; i<INPUT_SIZE; i++)
	{
		hashtable[i]=(struct hashentry *) malloc(sizeof(struct hashentry));
		hashtable[i]->next=NULL;
		hashtable[i]->previous=NULL;
		hashtable[i]->value=-1;
	}

	for (i=0; i<INPUT_SIZE; i++)
	{
		slot=hashthis(array[i]);
		hash_pointer=hashtable[slot];
		while (hash_pointer->value != -1)
			hash_pointer=hash_pointer->next;
		hash_pointer->value=array[i];
		hash_pointer->next=(struct hashentry *) malloc(sizeof(struct hashentry));
		hash_pointer->next->next=NULL;
		hash_pointer->next->previous=hash_pointer;
		hash_pointer->next->value=-1;
	}
}

void print_column(int c)
{
	struct hashentry* headp;
	
	for (headp=hashtable[c]; headp->value!=-1; headp=headp->next)
		printf("%d, ", headp->value);
	printf("\n");
}

int find_element(int element)
{
	struct hashentry* headp;
	int column;
	int found=0;

	column=hashthis(element);
	for (headp=hashtable[column]; headp->value!=-1; headp=headp->next)
	{
		if(headp->value == element)
			found=1;
	}

	return found;
}