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

#define	LOAD_FACTOR	1.0
#define	GROW_FACTOR 2.0

#include	"hash.h"

struct hash	*hash_new(char	*name)
{
	struct hash	*ht = calloc(sizeof(struct hash), 1);
	ht->name = name;
	ht->size = 1024;
	ht->entries = 0;
	ht->buckets = calloc(sizeof(struct hash_bucket*), ht->size);
	return ht;
}

static inline unsigned hash_code(struct hash *ht, char	*key)
{
	unsigned code = 0, off = 0;

	for(;*key;key++, off=(off+3)%25)
		code ^= (*key)<<off;

	return code % (ht->size - 1);
}

static inline void		hash_add_bucket(struct hash	*ht, struct hash_bucket	*bucket)
{
	unsigned	hash = hash_code(ht, bucket->key);

	bucket->next = ht->buckets[hash];
	ht->buckets[hash] = bucket;
	ht->entries++;
}

void		grow_hash(struct hash	*ht)
{
	int					old_size = ht->size, i;
	struct hash_bucket	**old_buckets = ht->buckets, *walker;

	int	new_size = GROW_FACTOR * ht->size;
	ht->buckets = calloc(sizeof(struct hash_bucket*), new_size);
	ht->size = new_size;
	ht->entries = 0;
	for(i=0;i<old_size;i++)
	{
		struct hash_bucket *next;
		for(walker=old_buckets[i];walker;walker=next)
		{
			next = walker->next;
			hash_add_bucket(ht, walker);
		}
	}
	free(old_buckets);
}

void		hash_add(struct hash	*ht, char	*key, void	*value)
{
	float		load = (float)(ht->entries + 1) / (ht->size);
	struct hash_bucket	*bucket = calloc(sizeof(struct hash_bucket), 1);

	if(load > LOAD_FACTOR)grow_hash(ht);

	bucket->key = key;
	bucket->value = value;
	hash_add_bucket(ht, bucket);
}

void		hash_visit_key(struct hash	*ht, char	*key, void	(*visitor)(void *value))
{
	unsigned h = hash_code(ht, key);
	struct hash_bucket	*bucket;
	
	for(bucket=ht->buckets[h];bucket;bucket=bucket->next)
	{
		//printf(" visit `%s' found `%s'\n", key, bucket->key);
		if(!strcmp(bucket->key, key))visitor(bucket->value);
	}
}

void		*hash_find(struct hash	*ht, char	*key)
{
	unsigned h = hash_code(ht, key);
	struct hash_bucket	*bucket;
	
	for(bucket=ht->buckets[h];bucket;bucket=bucket->next)
		if(!strcmp(bucket->key, key))return bucket->value;
	return 0;
}

void	hash_free(struct hash	*ht)
{
	int	i;
	for(i=0;i<ht->size;i++)
	{
		while(ht->buckets[i])
		{
			struct hash_bucket	*b = ht->buckets[i];
			ht->buckets[i] = b->next;
			free(b->key);
			free(b);
		}
	}
	free(ht->buckets);
	free(ht);
}