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

typedef struct xhn {
	char flag;
	struct xhn *next;
	char *key;
	void *val;
} xhn_t;

struct xht {
	int prime;
	xhn_t *zen;
};

/* Generates a hash code for a string.
 * This function uses the ELF hashing algorithm as reprinted in 
 * Andrew Binstock, "Hashing Rehashed," Dr. Dobb's Journal, April 1996.
 */
static int _xhter(const char *s)
{
	/* ELF hash uses unsigned chars and unsigned arithmetic for portability */
	const unsigned char *name = (const unsigned char *)s;
	unsigned long int h = 0;

	while (*name) {		/* do some fancy bitwanking on the string */
		unsigned long int g;
		h = (h << 4) + (unsigned long int)(*name++);
		if ((g = (h & 0xF0000000UL)) != 0)
			h ^= (g >> 24);
		h &= ~g;

	}

	return (int)h;
}


static xhn_t *_xht_node_find(xhn_t *n, const char *key)
{
	for (; n != 0; n = n->next)
		if (n->key != 0 && strcmp(key, n->key) == 0)
			return n;
	return 0;
}


xht_t *xht_new(int prime)
{
	xht_t *xnew;

	xnew = (xht_t *)MDNSD_malloc(sizeof(struct xht));
	xnew->prime = prime;
	xnew->zen = (xhn_t *)MDNSD_calloc(1, (sizeof(struct xhn) * (size_t)prime));	/* array of xhn_t size of prime */

	return xnew;
}

/* does the set work, used by xht_set and xht_store */
static xhn_t *_xht_set(xht_t *h, char *key, void *val, char flag)
{
	int i;
	xhn_t *n;

	/* get our index for this key */
	i = _xhter(key) % h->prime;

	/* check for existing key first, or find an empty one */
	if ((n = _xht_node_find(&h->zen[i], key)) == 0) {
		for (n = &h->zen[i]; n != 0; n = n->next) {
			if (n->val == 0)
				break;
		}
	}

	/* if none, make a new one, link into this index */
	if (n == NULL) {
		if (h->zen != NULL) {
			n = (xhn_t *)MDNSD_malloc(sizeof(struct xhn));
			n->next = NULL;
			n->next = h->zen[i].next;
			h->zen[i].next = n;
		}
	} else if (n->flag) {
		/* When flag is set, we manage their mem and free em first */
		MDNSD_free((void *)n->key);
		MDNSD_free(n->val);
	}

	if (n != NULL) {
		n->flag = flag;
		n->key = key;
		n->val = val;
	} else {
		MDNSD_free(key);
		MDNSD_free(val);
	}

	return n;
}

void xht_set(xht_t *h, char *key, void *val)
{
	if (h == 0 || key == 0)
		return;
	_xht_set(h, key, val, 0);
}

void xht_store(xht_t *h, const char *key, int klen, void *val, int vlen)
{
	char *ckey, *cval;

	if (h == 0 || key == 0 || klen == 0)
		return;

	ckey = (char *)MDNSD_malloc((size_t)klen + 1);
	memcpy(ckey, key, (size_t)klen);
	ckey[klen] = '\0';
	cval = (char *)MDNSD_malloc((size_t)vlen + 1);
	memcpy(cval, val, (size_t)vlen);
	cval[vlen] = '\0';	/* convenience, in case it was a string too */
	_xht_set(h, ckey, cval, 1);
}


void *xht_get(xht_t *h, const char *key)
{
	xhn_t *n;

	if (h == 0 || key == 0 || (n = _xht_node_find(&h->zen[_xhter(key) % h->prime], key)) == 0)
		return 0;

	return n->val;
}


void xht_free(xht_t *h)
{
	int i;
	xhn_t *n, *f;

	if (h == 0)
		return;

	for (i = 0; i < h->prime; i++) {
		if ((n = (&h->zen[i])) == NULL)
			continue;
		if (n->flag) {
			MDNSD_free((void *)n->key);
			MDNSD_free(n->val);
		}
		for (n = (&h->zen[i])->next; n != 0;) {
			f = n->next;
			if (n->flag) {
				MDNSD_free((void *)n->key);
				MDNSD_free(n->val);
			}
			MDNSD_free(n);
			n = f;
		}
	}

	MDNSD_free(h->zen);
	MDNSD_free(h);
}

void xht_walk(xht_t *h, xht_walker w, void *arg)
{
	int i;
	xhn_t *n;

	if (h == 0 || w == 0)
		return;

	for (i = 0; i < h->prime; i++) {
		for (n = &h->zen[i]; n != 0; n = n->next) {
			if (n->key != 0 && n->val != 0)
				(*w)(h, n->key, n->val, arg);
		}
	}
}