#include "stringmap.h"
#include "sys_log.h"
#include <stdlib.h>
#include <string.h>

#define LOADFACTOR (0.8f)
#define empty_hash (0xfffffffful)

struct _yrtag_stringmap
{
	uint32_t* hash;
	char** key;
	void** val;
	uint32_t* depth;
	size_t size;
	size_t maxprobe;
};

//djb2 hash (Dan Bernstein, http://www.cse.yorku.ca/~oz/hash.html)
uint32_t hashfunc(const char *str) {
	uint32_t hash = 5381;
	int c;
	while (c = *(const unsigned char*)(str++))
		hash = ((hash << 5) + hash) ^ c; /* hash * 33 ^ c */
	if(hash == empty_hash) hash = 0;
	return hash;
}

yrStringmap* yrStringmap_create(size_t size)
{
	yrStringmap* out = malloc(sizeof(yrStringmap));
	if(!out) {yrLog(0, "Out of memory"); return NULL;}

	out->size = (size_t) (size / LOADFACTOR);
	out->maxprobe = 0;

	out->hash = malloc(out->size * sizeof(uint32_t));
	out->key = malloc(out->size * sizeof(char*));
	out->val = malloc(out->size * sizeof(void*));
	out->depth = malloc(out->size * sizeof(uint32_t));
	if(!out->hash || !out->key || !out->val || !out->depth) {
		yrLog(0, "Out of memory");
		yrStringmap_destroy(out, 0);
		return NULL;
	}
	
	memset(out->hash, -1, out->size * sizeof(uint32_t));
	
	return out;
}

void yrStringmap_destroy(yrStringmap* sm, int free_values)
{
	if(!sm) return;

	if(free_values)
		for(size_t i = 0; i < sm->size; ++i)
			if(sm->hash[i] != empty_hash)
				free(sm->val[i]);
	if(sm->hash && sm->key && sm->val && sm->depth)
		for(size_t i = 0; i < sm->size; ++i)
			if(sm->hash[i] != empty_hash)
				free(sm->key[i]);

	free(sm->hash);
	free(sm->key);
	free(sm->val);
	free(sm->depth);
	free(sm);
}

void* yrStringmap_lookup(yrStringmap* sm, const char* key)
{
	uint32_t hash = hashfunc(key);
	size_t idx = hashfunc(key) % sm->size;

	for(size_t probe = 0; probe <= sm->maxprobe; ++probe)
	{
		if(!~(sm->hash[idx])) break; //fast way to check for empty hash, may want to turn this into a macro for readability
		if(sm->hash[idx] == hash)
			if(strcmp(sm->key[idx], key) == 0)
				return sm->val[idx];
		idx = (idx + 1) % sm->size;
	}
	return NULL;
}

int yrStringmap_insert(yrStringmap* sm, const char* key, void* val)
{
	key = _strdup(key);
	if(!key) { yrLog(0, "Out of memory"); return -1; }

	uint32_t hash = hashfunc(key);
	size_t baseidx = hashfunc(key) % sm->size;
	uint32_t probe = 0;
	for(size_t i = baseidx; i < baseidx + sm->size; ++i) {
		size_t idx = i % sm->size;
		if(sm->hash[idx] == empty_hash) {
			//free slot, insert here
			if(probe > sm->maxprobe) sm->maxprobe = probe;
			sm->hash[idx] = hash;
			sm->key[idx] = (char*) key;
			sm->val[idx] = val;
			sm->depth[idx] = probe;
			return 0;
		}
		if(sm->depth[idx] < probe) {
			//steal from the rich, swap
			if(probe > sm->maxprobe) sm->maxprobe = probe;
			uint32_t	swaph = sm->hash[idx];
			char*		swapk = sm->key[idx];
			void*		swapv = sm->val[idx];
			uint32_t	swapd = sm->depth[idx];
			sm->hash[idx] = hash;
			sm->key[idx] = (char*) key;
			sm->val[idx] = val;
			sm->depth[idx] = probe;
			hash = swaph;
			key = swapk;
			val = swapv;
			probe = swapd;
		}
		probe += 1;
		idx = (idx + 1) % sm->size;
	}
	free((char*)key);
	yrLog(0, "Stringmap is full");
	return -1;
}
