#include<stdio.h>
#include<Windows.h>
#include<stdlib.h>
#include<iostream>

#define BUCKET_SIZE 1024

using namespace std;

#define TABLESIZE 16

#define compare(a,b)	strcmp((const char*)a,(const char *)b)
#define hash_func		SDBMHash

typedef struct _NodeList{

	void* key;
	void *date;
	_NodeList *next; 

}ListNode,NodeList;

typedef ListNode* List;
typedef NodeList* elem;

 

typedef struct _HashTable{
	int tableSize;
	List *thelist;

}HashTable;

unsigned int SDBMHash(void *key){
	
	unsigned int hash = 0;
	char *str = (char*)key;

	while(*str){
		
		hash = (*str++)+(hash<<6)+(hash<<16)-hash;
	
	
	}

	return (hash&0x7FFFFFFF);

}

//哈希函数
int Hash(int tablesize,void* key){

	//return (key%tablesize);
	return hash_func(key)%tablesize;
}

//初始化哈希链表
HashTable *initHash(HashTable *&Hash,int tablesize){
	
	//初始化哈希桶
	Hash = (HashTable*)malloc(sizeof(HashTable));

	if(!Hash){
	
	printf("error!\n");
	return NULL;
	}

	//给索引指针分配内存
	if(tablesize<0){
		tablesize = TABLESIZE;
	}

	Hash->tableSize = tablesize;

	Hash->thelist = (List*)malloc(sizeof(List)*tablesize);

	if(!Hash->thelist){
		
		printf("error malloc!\n");
		free(Hash);
		//return ;
	}

	for(int i=0;i<tablesize;i++){
		//给每个哈希数组指针分配头节点的堆内存
		
		Hash->thelist[i] = (ListNode*)malloc(sizeof(ListNode));
		
		if(!Hash->thelist[i]){
			
			//释放内存
			printf("error malloc!\n");
			free(Hash->thelist);
			free(Hash);

		}else{
			
			memset(Hash->thelist[i],0,sizeof(NodeList));
		}	
	}
	return Hash;
}

//通过key查找元素
elem find(HashTable *&H,void* key){

	if(!H) return NULL;

	//找到索引下标
	int i =0;
	i= Hash(H->tableSize,key);
	
	List e = H->thelist[i]->next;

	while(e!=NULL&&compare(e->key,key)){
		
		e = e->next; 

	}

	//要么成功找到key,要么key不存在
	return e;

}

//插入元素
bool insertHash(HashTable *H,void* key,void *value){
	//
	//if(!H) return false;
	

	//通过键值找到元素
	elem e = find(H,key);
	elem tmp = NULL;
	elem L = NULL;
	//tmp可能存在也可能不存在,当e不存在时
	//e不存在
	if(!e){
	
	//	tmp = (elem)malloc(sizeof(elem));

		tmp = (elem)malloc(sizeof(NodeList));

		if(tmp==NULL){
		
			printf("eroor malloc!\n");
			return false;
		}

			L = H->thelist[Hash(H->tableSize,key)];	//通过key的索引找出相应的位置

			tmp->date = value;
			tmp->key = key;
			tmp->next = L->next;
			L->next = tmp;

		

	}else{
		printf("the key has been exit!\n");
	}


}

//删除元素
bool deleteElem(HashTable *H,void* key){
	//

	//找元素
	elem last = NULL;
	elem e = NULL;

	//elem e = find(H,key);//找到相应的索引位?????我在干嘛
	List L = H->thelist[Hash(H->tableSize,key)];

	last = L;