#include "config.h"
#include "hash.h"
#include "main.h"
#include "main_opt.h"
#include "random.h"
#include "xmalloc.h"

#include <errno.h>
#include <stddef.h>
#include <stdio.h>
#include <assert.h>

struct h_entry {
	size_t hash;
	void *key;
	void *value;
};

struct h_node {
	struct h_entry entry;
	struct h_node *next;
};

enum {MAGIC = 112};

void h_init(
		Hash *h,
		size_t (*hash)(const void *, size_t),
		int (*cmp)(const void *, const void *),
		void (*delk)(void *),
		void (*delv)(void *)
		) {
	size_t i;

	h->entries = 0;
	h->brk = -1;
	h->iter = -1;
	h->iterptr = NULL;
	h->seed = randval() * (size_t)-1;
	h->delk = delk;
	h->delv = delv;
	assert(hash != NULL);
	h->hash = hash;
	assert(cmp != NULL);
	h->cmp = cmp;
	h->table = xmalloc(h->newsize = h->size = MAGIC, sizeof *h->table);
	for (i = 0; i < h->size; ++i) {
		h->table[i] = NULL;
	}
}

#define DELKV(p)                   \
do {                               \
	if (h->delk) {                 \
		h->delk((p)->entry.key);   \
	}                              \
	if (h->delv) {                 \
		h->delv((p)->entry.value); \
	}                              \
} while (0)

void h_end(Hash *h) {
	size_t size, b;

	if (!h->table)
		return;

	for (b = 0, size = h->newsize; h->newsize; h->newsize--) {
		struct h_node *p;

		if ((p = h->table[h->newsize - 1])) {
			++b;
			for (; p; p = h->table[h->newsize - 1]) {
				h->table[h->newsize - 1] = p->next;
				DELKV(p);
				xfree(p);
			}
		}
	}
	xfree(h->table);
	h->table = NULL;

	if (Opt.debug & DBG_HASH) {
		fprintf(stderr, "%s: hash[%lu/%lu/%lu]\n", Prog, (unsigned long)h->entries, (unsigned long)b, (unsigned long)size);
	}
}

ATTR_PURE
static size_t xclip(const Hash *h, const size_t hash_unc) {
	size_t hash;

	hash = hash_unc % h->size;
	if (hash > h->brk) {
		hash = hash_unc % h->newsize;
	}

	return hash;
}

#if 0
ATTR_PURE
static size_t xhash(const Hash *h, const void *key) {
	return xclip(h, h->hash(key, h->seed));
}
#endif

#define XRESIZN(h) ((h)->brk + 1u)
#define XSTEP(h)   do { if (XRESIZN(h)) xstep(h); } while (0)

static void xstep(Hash *h) {
	struct h_node *rev = NULL;
	struct h_node *p;
	struct h_node *tmp;

	assert(h->table != NULL);

	for (p = h->table[h->brk]; p; p = tmp) {
		tmp = p->next;
		p->next = rev;
		rev = p;
	}
	h->table[h->brk--] = NULL;

	if (!XRESIZN(h)) {
		h->size = h->newsize;
	}

	for (p = rev; p; p = tmp) {
		const size_t i = xclip(h, p->entry.hash);
		tmp = p->next;
		p->next = h->table[i];
		h->table[i] = p;
	}
}

static void xincentries(Hash *h) {
	h->entries++;
	if (!(XRESIZN(h)) && h->entries / h->size > 3u) {
		size_t i;
		h->table = xrealloc(h->table, h->newsize = h->size * 2u + 1u);
		for (i = h->size; i < h->newsize; ++i) {
			h->table[i] = NULL;
		}
		h->brk = h->size - 1u;
		xstep(h);
	}
}

int h_get(Hash *h, const void *key, void **res) {
	XSTEP(h);
	{
		const size_t hash_unc = h->hash(key, h->seed);
		const size_t hash = xclip(h, hash_unc);
		struct h_node *p;

		for (p = h->table[hash]; p; p = p->next) {
			if (hash_unc == p->entry.hash && h->cmp(p->entry.key, key) == 0) {
				if (res) {
					*res = p->entry.value;
				}
				return H_OK;
			}
		}
	}
	return H_NOENT;
}

int h_del(Hash *h, const void *key) {
	XSTEP(h);
	{
		const size_t hash_unc = h->hash(key, h->seed);
		const size_t hash = xclip(h, hash_unc);
		struct h_node **p;

		for (p = &h->table[hash]; *p; p = &(*p)->next) {
			if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) {
				struct h_node *tmp = *p;
				*p = (*p)->next;
				DELKV(tmp);
				xfree(tmp);
				h->entries--;
				return H_OK;
			}
		}
	}

	return H_NOENT;
}

#if 0
void h_push(Hash *h, void *key, void *val) {
	XSTEP(h);
	{
		const size_t hash_unc = h->hash(key, h->seed);
		const size_t hash = xclip(h, hash_unc);
		struct h_node *p;

		p = xmalloc(1, sizeof *p);
		p->entry.hash = hash_unc;
		p->entry.key = key;
		p->entry.value = val;
		p->next = h->table[hash];
		h->table[hash] = p;

		xincentries(h);
	}
}
#endif

int h_put(Hash *h, void *key, void *val, int replace) {
	XSTEP(h);
	{
		const size_t hash_unc = h->hash(key, h->seed);
		const size_t hash = xclip(h, hash_unc);
		struct h_node **p;

		for (p = &h->table[hash]; *p; p = &(*p)->next) {
			if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) {
				if (replace) {
					DELKV(*p);
					(*p)->entry.key = key;
					(*p)->entry.value = val;
					return H_OK;
				} else {
					return H_EXIST;
				}
			}
		}

		*p = xmalloc(1, sizeof **p);

		(*p)->entry.hash = hash_unc;
		(*p)->entry.key = key;
		(*p)->entry.value = val;
		(*p)->next = NULL;

		xincentries(h);
	}

	return H_OK;
}

void h_reset(Hash *h) {
	h->iter = -1;
	h->iterptr = NULL;
}

int h_nextkv(Hash *h, void **k, void **v) {
	if (h->iterptr) {
		*k = h->iterptr->entry.key;
		*v = h->iterptr->entry.value;
		h->iterptr = h->iterptr->next;
		return H_OK;
	}

	for (h->iter++; h->iter < h->newsize; h->iter++) {
		if ((h->iterptr = h->table[h->iter])) {
			*k = h->iterptr->entry.key;
			*v = h->iterptr->entry.value;
			h->iterptr = h->iterptr->next;
			return H_OK;
		}
	}

	h->iter = -1;
	return H_NOENT;
}

#if 0
size_t (h_entries)(const Hash *h) {
	return h_entries(h);
}
#endif