1 files changed, 123 insertions, 0 deletions
diff --git a/src/lookup.c b/src/lookup.c
new file mode 100644
index 0000000..377c505
--- /dev/null
+++ b/src/lookup.c
@@ -0,0 +1,123 @@
+#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;
+}