#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
typedef struct bucket{
	int h;  
	char* key;
	void* pData;
	struct bucket* pNext;
	struct bucket* pLast;
}Bucket;
typedef struct hashtable{
	int size;
	int elementsNum;
	int mask;
	Bucket** arBuckets; //这是一个存放buckets的array 
}HashTable;

/**
 **  这是一个计算HASH值的算法
 **/
int time33(char* arKey,int arlength){
	int h = 0;
	int i;
	for(i=0;i<arlength;i++){
		h = h*33 + (int)*arKey++;
	}
	return h;	
}

/**
 **  初始化一个大小是1的HASHTABLE 
 **/
int _init_hash_table(HashTable** ht){
	*ht = (HashTable*)malloc(sizeof(HashTable));
	(*ht)->size = 1;
	(*ht)->mask = (*ht)->size - 1;	
    (*ht)->elementsNum = 1;
	(*ht)->arBuckets = (Bucket**)malloc(sizeof(Bucket*)*(*ht)->size);
	memset((*ht)->arBuckets,0,sizeof(Bucket*)*(*ht)->size);
	return 1;		
} 

int _hash_link_bucket_to_bucket_head(Bucket** newBucket,Bucket** bucketHead){
	if(*bucketHead==NULL){
		*bucketHead = *newBucket;		
	}else{
		(*newBucket)->pNext = (*bucketHead)->pNext;
		(*newBucket)->pLast = (*bucketHead);
		if((*bucketHead)->pNext != NULL){
			(*bucketHead)->pNext->pLast = *newBucket;	
		}
		(*bucketHead)->pNext = *newBucket;	
	}
	return 1;
}

int _hash_new_bucket(Bucket** newBucket,int hash,char* arkey,void* pData){
	(*newBucket) = (Bucket*)malloc(sizeof(Bucket));
	(*newBucket)->h = hash;
	(*newBucket)->key = arkey;
	(*newBucket)->pData = pData;
	(*newBucket)->pNext = NULL;
	(*newBucket)->pLast = NULL;
	return 1;
}


int _hash_rehash(HashTable* ht){
	int i = 0;
	//由于我没定义pListNext指针，所以只能这样rehash了。 
	for( ; i<ht->size ; i++){
		if(ht->arBuckets[i] != NULL){
			int index = ht->arBuckets[i]->h & ht->mask ;
			if(i != index){
				_hash_link_bucket_to_bucket_head(&ht->arBuckets[i],&ht->arBuckets[index]);
				ht->arBuckets[i] = NULL;	
			}	
		}	
	}
	return 1;		
}

/**
 **  将HASHTABLE的大小扩容1倍 
 **/
int _hash_resize(HashTable* ht){
	if(ht != NULL){
		ht->size = ht->size << 1;
		ht->mask = ht->size - 1; 
		realloc(&ht->arBuckets,sizeof(Bucket*) * ht->size);
		int i;
		for(i=ht->size>>1;i<ht->size;i++){
			ht->arBuckets[i] = NULL;
		}
		//memset(ht->arBuckets[0],NULL,sizeof(Bucket*) * (ht->size >> 1));
		printf("resize:%i\r\n", ht->size);
		_hash_rehash(ht);
		return 1;		
	}
	return 0;
}


/**
 **  往HASHTABLE中添加元素 
 **/
int _hash_add_or_update(HashTable* ht,char* arKey,int arLength,void* pData){
	int h = time33(arKey,arLength);
	int index = h & ht->mask;
	Bucket* p = ht->arBuckets[index]; 
	while(p!=NULL){
		if(strcmp(arKey,p->key)==0){
			//这里应该执行更新操作
			free(p->pData);
			p->pData = pData; 
			return 1;
		}
		p = p->pNext;		
	}
	Bucket* newBucket;
	_hash_new_bucket(&newBucket,h,arKey,pData);
	_hash_link_bucket_to_bucket_head(&newBucket,&ht->arBuckets[index]);
	ht->elementsNum++;
	if(ht->elementsNum = ht->size){
		_hash_resize(ht);
	}
	return 0;
	
}

void* _hash_find(HashTable* ht,char* arKey,int arLength){
	int h = time33(arKey,arLength);
	int index = h & ht->mask;
	Bucket* p = ht->arBuckets[index]; 
	while(p!=NULL){
		if(strcmp(arKey,p->key)==0){
			return p->pData;
		}
		p = p->pNext;
	}
	return 0;
}

int PUT(HashTable* ht,void* key,void* value){
	char* arKey = (char*)key;
	int len = strlen(arKey);
	return _hash_add_or_update(ht,arKey,len,value);	
}

void* GET(HashTable* ht,void* key){
	char* arKey = (char*)key;
	int len = strlen(arKey);
	return _hash_find(ht,arKey,len);
}

int main(){
	printf("%s\r\n","这是一个hashtable的例子");
	HashTable* ht;
	_init_hash_table(&ht);
	PUT(ht,"1","mengjun");
	PUT(ht,"2","aaaaa");
	PUT(ht,"3","fff");
	PUT(ht,"24","eee");
	PUT(ht,"25","ddd");
	printf("%s\r\n",(char*)GET(ht,"1"));
	printf("%s\r\n",(char*)GET(ht,"2"));
	printf("%s\r\n",(char