/**
 * 实现PHP内核中的HashTable
 */
#include "core.h"

static void hash_destructor(void *data){
	if(data != NULL){
		free(data);
		data = NULL;
	}
}

API HashTable* hash_init(HashTable *ht, int size, dtor_func_t destructor){
	int i = 3;
	ht = (HashTable*)malloc(sizeof(HashTable));

	if(ht == NULL){
		assert("hashTable init error\n");
	}

	while( (1 << i) < size){
		i++;
	}

	size = 1 << i;

	ht->pDestructor = destructor;
	ht->numOfElements = 0;
	ht->tableSize   = size;
	ht->tableMask   = size-1;
	ht->buckets     = (Bucket**)malloc(sizeof(Bucket*) * size);

	return ht;
}

/* time33算放，将字符串的每个字符ASCII码乘上33的总数 */
static inline ulong time33(const char *arKey, uint nKeyLength)
{
	register ulong hash = 5381;

	/* variant with the hash unrolled eight times */
	for (; nKeyLength >= 8; nKeyLength -= 8) {
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
	}
	switch (nKeyLength) {
		case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 1: hash = ((hash << 5) + hash) + *arKey++; break;
		case 0: break;
	}

	return hash;
}

#define INIT_HASH_H(z, h) 	switch(Z_TYPE_P(z)){\
								case IS_STRING:\
									h = time33(Z_STRVAL_P(z), Z_STRLEN_P(z)) & ht->tableMask;\
									break;\
								case IS_LONG:\
									h = Z_LVAL_P(z) & ht->tableMask;\
									break;\
								default:\
									return FAILURE;\
							}

API int zend_hash_set(HashTable *ht, zval *z, void *pData){
	long h;
	Bucket *p;

	zend_rehash(ht);

	INIT_HASH_H(z, h)

	p = ht->buckets[h];

	//元素不存在，则新建元素
	if(p == NULL){
		p = (Bucket*)malloc(sizeof(Bucket));
		if( p == NULL ) assert("malloc bucket error\n");

		switch(Z_TYPE_P(z)){
			case IS_STRING:
				memcpy(p->arKey, Z_STRVAL_P(z), Z_STRLEN_P(z));
				p->keyLength = Z_STRLEN_P(z);
				p->h 		 = 0;
				break;
			case IS_LONG:
				p->h 		 = Z_LVAL_P(z);
				p->keyLength = 0;
		}
		p->pData = pData;
		ht->buckets[h] = p;
		ht->numOfElements++;

		return SUCCESS;
	}

	//找到元素，要对字符串类型进行原始key对比，整型需要对原始索引进行对比。更新元素
	while(p != NULL){
		switch(Z_TYPE_P(z)){
			case IS_STRING:
				if(memcmp(Z_STRVAL_P(z), p->arKey, Z_STRLEN_P(z)) == 0 && Z_STRLEN_P(z) == p->keyLength){
					p->pData = pData;
					return SUCCESS;
				}
				break;
			case IS_LONG:
				if(Z_LVAL_P(z) == p->h){
					p->pData = pData;
					return SUCCESS;
				}
		}

		p = p->pNext;
	}

	//执行到此处，说明有碰撞发生
	p = (Bucket*)malloc(sizeof(Bucket));
	if( p == NULL ) assert("malloc bucket error\n");

	switch(Z_TYPE_P(z)){
		case IS_STRING:
			memcpy(p->arKey, Z_STRVAL_P(z), Z_STRLEN_P(z));
			p->keyLength = Z_STRLEN_P(z);
			p->h 		 = 0;
			break;
		case IS_LONG:
			p->h 		 = Z_LVAL_P(z);
			p->keyLength = 0;
	}
	p->pData = pData;
	ht->buckets[h]->pLast = p;
	ht->numOfElements++;

	return SUCCESS;
}

API int zend_hash_find(HashTable *ht, zval *z, void **dest){
	long h;
	Bucket *p;

	INIT_HASH_H(z, h)

	p = ht->buckets[h];

	while( p != NULL ){
		switch(Z_TYPE_P(z)){
			case IS_STRING:
				if( memcmp(Z_STRVAL_P(z), p->arKey, Z_STRLEN_P(z)) == 0 && p->keyLength == Z_STRLEN_P(z)){
					*dest = p->pData;
					return SUCCESS;
				}
				break;
			case IS_LONG:
				if( Z_LVAL_P(z) == p->h ){
					*dest = p->pData;
					return SUCCESS;
				}
		}

		p = p->pNext;
	}

	return FAILURE;
}

API int zend_hash_delete(HashTable *ht, zval *z, void **dest){
	long h;
	Bucket *p;

	INIT_HASH_H(z, h)
	p = ht->buckets[h];
	if(p == NULL) return FAILURE;

	while(p != NULL){
		switch(Z_TYPE_P(z)){
			case IS_STRING:
				if( memcmp(Z_STRVAL_P(z), p->arKey, Z_STRLEN_P(z)) == 0 && p->keyLength == Z_STRLEN_P(z)){
					goto delete;
				}
				break;
			case IS_LONG:
				if( Z_LVAL_P(z) == p->h ){
					goto delete;
				}
		}
		p = p->pNext;
	}

	return FAILURE;

delete:
	if(dest != NULL) *dest = p->pData;
	if(p->pLast == NULL && p->pNext == NULL){ //单节点的双向链表
		ht->buckets[h] = NULL;
	}else if(p->pLast == NULL && p->pNext != NULL){ //双向链表的开端
		ht->buckets[h] = p->pNext;
	}else{
		p->pLast = NULL;
	}
	ht->pDestructor(p);
	return SUCCESS;

}

API int zend_rehash(HashTable *ht){
	if( (ht->numOfElements / ht->tableSize) >= 1){//哈希表使用率大于1则rehash
		Bucket** buckets = (Bucket**)malloc(sizeof(Bucket*) * ht->tableSize * 2);
		Bucket* p;

		ht->tableMask = ht->tableSize * 2 - 1;

		while(1){
			if(ht->rehashidx > ht->tableSize) break;

			p = ht->buckets[ht->rehashidx];

			while(p != NULL){//对链表形式进行遍历,重新hash存储到新hashtable
				long h;

				if(p->keyLength > 0){
					h = time33(p->arKey, p->keyLength) & ht->tableMask;
				}else{
					h = p->h & ht->tableMask;
				}

				buckets[h] = p;
				free(ht->buckets);//释放原有buckets数组
				ht->buckets = buckets;

				p = p->pNext;
			}

			ht->rehashidx++;//记录当前rehash索引
		}

		ht->rehashidx = 0;
		ht->tableSize *= 2;
	} 

	return SUCCESS;
}

int main(int argc, char const *argv[])
{
	HashTable *ht;
	zval *tval;
	char *hash_elements_val;
	int i = 0;

	MAKE_STD_ZVAL(tval);

	ZVAL_STRINGL(tval, "test111~", strlen("test111~")+1, 1);

	//test create hashtable
	ht = hash_init(ht, 15, hash_destructor);

	//test add or set
	zend_hash_set(ht, tval, strdup("hello world\n"));
	printf("hashTable length:%d\n", ht->tableSize);

	//test find
	zend_hash_find(ht, tval, (void**)&hash_elements_val);
	printf("find elements value:%s\n", hash_elements_val);

	//test delete
	zend_hash_delete(ht, tval, (void**)&hash_elements_val);
	printf("delete elements value:%s\n", hash_elements_val);

	//test rehash
	for(i; i <= 22; i++){
		char *key[30];

		free(Z_STRVAL_P(tval));

		sprintf(key, "abc%d", i);

		ZVAL_STRINGL(tval, key, 5, 1);

		zend_hash_set(ht, tval, strdup("hello world1\n"));
	}

	//test rehash find
	zend_hash_find(ht, tval, (void**)&hash_elements_val);
	printf("find elements value:%s\n", hash_elements_val);
	return 0;
}