#include <string.h>
#include <stdlib.h>
#include <lyn/lookup.h>

struct lookup lookup_create(size_t s)
{
	return (struct lookup){.ns = s, .root = NULL};
}

unsigned long djb2(const unsigned char *str)
{
	unsigned long hash = 5381;
	int c;

	while ((c = *str++))
		hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

	return hash;
}

static size_t lookup_size(struct lookup *l, size_t key_len)
{
	return sizeof(struct lookup_node) + l->ns + key_len + 1;
}

static struct lookup_node *create_node(struct lookup *l, unsigned long hash, const char *key, const void *n)
{
	size_t key_len = strlen(key);
	struct lookup_node *new = malloc(lookup_size(l, key_len));
	if (!new)
		return NULL;

	memcpy(new->data, n, l->ns);
	strcpy(new->data + l->ns, key);
	new->hash = hash;
	new->left = NULL;
	new->right = NULL;
	return new;
}

void *lookup_insert(struct lookup *l, const char *key, const void *n)
{
	enum {INSERT_LEFT, INSERT_RIGHT} side = INSERT_LEFT;

	unsigned long hash = djb2((const unsigned char *)key);
	if (!l->root) {
		struct lookup_node *new = create_node(l, hash, key, n);
		if (!new)
			return NULL;

		l->root = new;
		return &new->data;
	}

	struct lookup_node *cmp = l->root;
	while (cmp) {
		if (cmp->hash == hash) {
			if (strcmp(cmp->data + l->ns, key) == 0)
				return NULL;

			if (cmp->left) {
				cmp = cmp->left;
				continue;
			}

			side = INSERT_LEFT;
			break;
		}
		else if (cmp->hash < hash) {
			if (cmp->left) {
				cmp = cmp->left;
				continue;
			}

			side = INSERT_LEFT;
			break;
		}
		else if (cmp->hash > hash) {
			if (cmp->right) {
				cmp = cmp->right;
				continue;
			}

			side = INSERT_RIGHT;
			break;
		}
	}

	struct lookup_node *new = create_node(l, hash, key, n);
	if (!new)
		return NULL;

	if (side == INSERT_LEFT)
		cmp->left = new;
	else if (side == INSERT_RIGHT)
		cmp->right = new;
	else
		abort();

	return &new->data;
}

void *lookup_at(struct lookup *l, const char *key)
{
	unsigned long hash = djb2((const unsigned char *)key);
	struct lookup_node *n = l->root;
	while (n) {
		if (n->hash == hash) {
			if (strcmp(n->data + l->ns, key) == 0)
				return &n->data;

			n = n->left;
		}
		else if (n->hash < hash) {
			n = n->left;
		}
		else if (n->hash > hash) {
			n = n->right;
		}
	}

	return NULL;
}