#include "idxmap.h"
#include <stdlib.h>
#include <string.h>

#define LOADFACTOR (0.8f)

struct item
{
	uint32_t key;
	uint32_t value;
};

struct _yrtag_idxmap
{
	struct item* map;
	uint32_t* stack;
	uint32_t* stackptr;
	uint32_t* depth;
	size_t storesize;
	size_t size;
	size_t maxprobe;
};

//Knuth:
/*static uint32_t hashfunc(uint32_t id) { return id * 2654435761ul; }*/
//Attempt at a 64-bit Knuth:
static size_t hashfunc(size_t id) { return id * 11400714819322457583ull; }

yrIdxmap* yrIdxmap_create(size_t size)
{
	yrIdxmap* out = malloc(sizeof(yrIdxmap));
	if(!out) return NULL;

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

	out->map = malloc(out->storesize * sizeof(struct item));
	out->depth = (uint32_t*) malloc(out->storesize * sizeof(uint32_t));
	out->stack = (uint32_t*) malloc(size * sizeof(uint32_t));
	if(!out->map || !out->depth || !out->stack) {
		yrIdxmap_destroy(out);
		return NULL;
	}
	
	memset(out->map, -1, out->storesize * sizeof(struct item));
	for(size_t i = 0; i < size; ++i)
		out->stack[i] = (uint32_t) i;
	out->stackptr = out->stack;
	
	return out;
}

void yrIdxmap_destroy(yrIdxmap* im)
{
	if(!im) return;

	free(im->map);
	free(im->stack);
	free(im->depth);
	free(im);
}

uint32_t yrIdxmap_lookup(yrIdxmap* im, uint32_t id)
{
	size_t idx = hashfunc(id) % im->storesize;

	for(size_t probe = 0; probe <= im->maxprobe; ++probe)
	{
		if(!~(im->map[idx].key)) break; //fast way to check for empty item
		if(im->map[idx].key == id) return im->map[idx].value;
		idx = (idx + 1) % im->storesize;
	}
	return invalid_item;
}

uint32_t yrIdxmap_insert(yrIdxmap* im, uint32_t id)
{
	if(yrIdxmap_isfull(im)) return invalid_item;
	uint32_t val = *im->stackptr;
	im->stackptr += 1;
	uint32_t retval = val;
	size_t idx = hashfunc(id) % im->storesize;
	uint32_t probe = 0;
	for(;;) {
		if(im->map[idx].key == invalid_item) {
			//free slot, insert here
			if(probe > im->maxprobe) im->maxprobe = probe;
			im->map[idx].key = id;
			im->map[idx].value = val;
			im->depth[idx] = probe;
			break; //this will always eventually happen as storesize>size
		}
		if(im->depth[idx] < probe) {
			//steal from the rich, swap
			if(probe > im->maxprobe) im->maxprobe = probe;
			uint32_t swapk = im->map[idx].key;
			uint32_t swapv = im->map[idx].value;
			uint32_t swapd = im->depth[idx];
			im->map[idx].key = id;
			im->map[idx].value = val;
			im->depth[idx] = probe;
			id = swapk;
			val = swapv;
			probe = swapd;
		}
		probe += 1;
		idx = (idx + 1) % im->storesize;
	}
	return retval;
}


uint32_t yrIdxmap_remove(yrIdxmap* im, uint32_t id)
{
	//find the used slot
	size_t idx = hashfunc(id) % im->storesize;
	size_t probe;
	for(probe = 0; probe <= im->maxprobe; ++probe) {
		if(im->map[idx].key == id) break;
		idx = (idx + 1) % im->storesize;
	}
	if(probe > im->maxprobe) return invalid_item;
	
	//put value back on stack
	im->stackptr -= 1;
	*(im->stackptr) = im->map[idx].value;
	uint32_t retval = im->map[idx].value;

	//shift values forward to make use of the free slot
	uint32_t dist = 1;
	size_t freeslot = idx;
	idx = (idx + 1) % im->storesize;
	while(dist <= im->maxprobe) {
		if(im->map[idx].key == invalid_item) break; //reached the end of a run
		if(dist <= im->depth[idx]) { //this item can be moved to the free slot
			im->map[freeslot].key = im->map[idx].key;
			im->map[freeslot].value = im->map[idx].value;
			im->depth[freeslot] = im->depth[idx] - dist;
			freeslot = idx;
			dist = 0;
		}
		dist += 1;
		idx = (idx + 1) % im->storesize;
	}
	
	//mark the last moved slot as free
	im->map[freeslot].key = invalid_item;
	return retval;
}

int yrIdxmap_isfull(yrIdxmap* im)
{
	return (im->stackptr == im->stack + im->size);
}