/* small hash implementation */
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <stdbool.h>
#include "hash.h"

#define HASH_IBUCKETS 16

unsigned int hash(const char* key)
{
   unsigned h = 0;

   while (*key)  h += h + *key++ ;
   return h;
}

hash_t* hash_new ()
{
	hash_t* shash = (hash_t*) malloc(sizeof(hash_t));
	memset((void*)shash,0,sizeof(hash_t));
	shash->buckets =
		(hash_node_t**) malloc(HASH_IBUCKETS * sizeof(hash_node_t*));
	memset((void*) shash->buckets, 0, HASH_IBUCKETS * sizeof(hash_node_t*));
	shash->buckets_num=HASH_IBUCKETS;
	shash->elements_num=0;
	return shash;
}

void hash_destroy(hash_t* shash, void (*destroy_cb) (void*) ) {
	unsigned int i;
	
	for ( i=0; i < shash->buckets_num; i++ ) {
		hash_node_t* list = shash->buckets[i];
		
		while ( list != NULL ) {
			hash_node_t* item = list;
			(*destroy_cb) (item->value);
			free(item->key);
			list = item->next;
		}
	}
	free(shash->buckets);
	free(shash);
}

hash_node_t* hash_find_node(const hash_t* shash, const char* key) {
	unsigned int h = hash(key) % shash->buckets_num;
	hash_node_t* list = shash->buckets[h];

	while ( list!=NULL) {
		if (! strcmp(list->key,key) ) {
			return list;
		}
		list=list->next;
	}
	return NULL;
}

void* hash_find (const hash_t* shash, const char* key)
{
	hash_node_t* node;
	if ( ( node=hash_find_node(shash, key) ) == NULL ) {
		return NULL;
	}
	return node->value;
}

void hash_rebuild(hash_t* shash, unsigned int buckets_num)
{
	unsigned int i;
	hash_node_t** buckets = 
		(hash_node_t**) malloc( buckets_num * sizeof(hash_node_t*));
	memset(buckets,0,buckets_num * sizeof(hash_node_t*));
	
	for ( i=0; i < shash->buckets_num; i++ ) {
		hash_node_t* list = shash->buckets[i];
		
		while ( list != NULL ) {
			hash_node_t* item = list;
			unsigned int h = hash(list->key) % buckets_num;
			list = item->next;
			item->next = buckets[h];
			buckets[h] = item;
		}
	}
	free(shash->buckets);
	shash->buckets = buckets;
}

void hash_expand (hash_t* shash)
{
	unsigned int buckets_num = 2 * shash->buckets_num;
	hash_rebuild(shash, buckets_num);
}

void hash_constrain (hash_t* shash)
{
	unsigned int buckets_num = shash->buckets_num / 2 ;
	hash_rebuild(shash, buckets_num);
}

bool hash_insert (hash_t* shash, char* key, void* value)
{
	hash_node_t* new_node;
	unsigned int h;

	new_node = (hash_node_t*) malloc(sizeof(hash_node_t));
	if ( new_node == NULL ) {
		fprintf(stderr, "ERROR: Malloc failed, errno: %d, %s\n",
				errno, strerror(errno));
		return false;
	}
	memset((void*)new_node, 0, sizeof(hash_node_t));
	new_node->key = strdup(key);
	new_node->value = value;
	h = ( hash(key) % shash->buckets_num ) ;
	new_node->next = shash->buckets[h];
	shash->buckets[h] = new_node;
	shash->elements_num++;
	if ( 2 * shash->buckets_num < shash->elements_num ) {
		hash_expand(shash);
	}
	
	return true;
}

bool hash_delete(hash_t* shash, char* key)
{
	unsigned int h = ( hash(key) % shash->buckets_num );
	hash_node_t* prev = NULL;
	hash_node_t* list = shash->buckets[h];

	while ( list!=NULL ) {
		if (! strcmp(list->key,key) ) {
			if ( prev == NULL ) {
				shash->buckets[h] = list->next;
			} else {
				prev->next = list->next;
			}
			free(list->key);
			free(list);
			shash->elements_num--;
			if ( (shash->buckets_num > HASH_IBUCKETS) &&
				(shash->buckets_num > 2 * shash->elements_num)
				) {
				hash_constrain(shash);
			}
			return true;
		}
		prev=list;
		list=list->next;
	}
	/* Not found 
	 */
	return false;
}