#include <stdio.h>

#include <stdlib.h>



#define NULLKEY	-1

int hashsize[] = {10, 20, 40, 100, 1024};



typedef struct _HashTable{

	int *elem;

	int count;     // count of the elements of the table now;

	int sizeIndex; // hashsize[sizeIndex] is the size of the table now;

}HashTable;



int Hash(int key, int size)

{

	return key%size;

}



int Collision(int *p, int *c, int size)

{

	*p = (*p + *c)/size;

	return *p;

}



int RecreateHash(HashTable *H)

{

	int *p = NULL;

	int n = sizeof(hashsize)/sizeof(int);

	int i;

	if(H->sizeIndex < n){

		H->sizeIndex++;

		p = (int *)malloc(sizeof(int)*sizeof(hashsize[H->sizeIndex]));	

		for(i=0; i< hashsize[H->sizeIndex]; i++){

			p[i] = NULLKEY;

		}

		free(H->elem);

		H->elem = p;

		return 1;

	}else{

		return 0;

	}

}



int SearchHash(HashTable *H, int key, int *p, int *c)

{

	*p = Hash(key, hashsize[H->sizeIndex]);

	while(H->elem[*p] != NULLKEY && H->elem[*p] != key){

		++(*c);

		Collision(p, c, hashsize[H->sizeIndex]);

		if(*c > 10){

			break;

		}

	}

	if(H->elem[*p] == key){

		return 1;

	}else{

		return 0;

	}

		

}



int InsertHash(HashTable *H, int key)

{

	int c = 0;

	int p = 0;

	if( SearchHash(H, key, &p, &c) ){

		return 0;

	}else if( c < hashsize[H->sizeIndex]/2 ){

		H->elem[p] = key, 

		++H->count;

		return 1;	

	}else{

		RecreateHash(H);

		return -1;

	}

}



void main()

{

	int data[] = {1,3,4,5,8,10,11,22,44,55,66,22,99,32,41};

	//int data[] = {3,4,5,8,10,11};

	int n = sizeof(data)/sizeof(int);

	int i;

	int p;

	int c=0;

	

	HashTable H;

	H.count = 0;

	H.sizeIndex = 0;

	H.elem = (int *)malloc(sizeof(int) * hashsize[H.sizeIndex]);

	for(i=0;i<hashsize[H.sizeIndex];i++){

		H.elem[i] = NULLKEY;

	}





	printf("log.anycle.com\n\n");

	printf("Original data:\n");

	for(i=0;i<n; i++){

		printf(" %d", data[i]);

	}

	printf("\n");





	printf("Insert hash table:\n");

	i=0;

	while(i<n){

		for(i=0;i<n;i++){

			if(InsertHash(&H, data[i]) < 0){

				break;

			}

		}

	}



	printf("Print the hash table:\n");

	for(i=0;i<hashsize[H.sizeIndex];i++){

		printf(" %2d", H.elem[i]);

	}

	printf("\n");

}