play around with lookup tables for commands

4 files changed, 166 insertions, 30 deletions

diff --git a/include/lyn/lookup.h b/include/lyn/lookup.h
new file mode 100644
index 0000000..577d450
--- /dev/null
+++ b/include/lyn/lookup.h
@@ -0,0 +1,29 @@
+#ifndef LYN_LOOKUP_H
+#define LYN_LOOKUP_H
+
+#include <stddef.h>
+
+struct lookup_node {
+	unsigned long hash;
+	struct lookup_node *left, *right;
+	char data[]; /* should be max aligned */
+};
+
+struct lookup {
+	size_t ns;
+	struct lookup_node *root;
+};
+
+struct lookup lookup_create(size_t s);
+void lookup_destroy(struct lookup *l);
+
+void *lookup_insert(struct lookup *l, const char *key, const void *n);
+void *lookup_at(struct lookup *l, const char *key);
+
+#define lookupt_insert(type, l, key, n)\
+	(type *)lookup_insert(type, l, key, n)
+
+#define lookupt_at(type, l, key)\
+	*(type *)lookup_at(&l, key)
+
+#endif /* LYN_LOOKUP_H */
diff --git a/include/lyn/lyn.h b/include/lyn/lyn.h
index 27a2fe3..ff79979 100644
--- a/include/lyn/lyn.h
+++ b/include/lyn/lyn.h
@@ -2,6 +2,7 @@
 #define LYN_H
 
 #include <lyn/parser.h>
+#include <lyn/lookup.h>
 #include <lyn/vec.h>
 
 #define lyn_at(v, i)\
@@ -9,7 +10,7 @@
 
 struct lyn_scope {
 	struct lyn_scope *parent;
-	struct vec visible;
+	struct lookup visible;
 };
 
 struct lyn {
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;
+}
diff --git a/src/lyn.c b/src/lyn.c
index 2783ba6..bd5dbb4 100644
--- a/src/lyn.c
+++ b/src/lyn.c
@@ -141,18 +141,13 @@ struct lyn lyn_create()
 	return (struct lyn){};
 }
 
-struct visible {
-	const char *name;
-	struct lyn_symbol symb;
-};
-
 int lyn_create_scope(struct lyn *lyn)
 {
 	struct lyn_scope *scope = calloc(1, sizeof(struct lyn_scope));
 	if (!scope)
 		return -1;
 
-	scope->visible = vec_create(sizeof(struct visible));
+	scope->visible = lookup_create(sizeof(struct lyn_symbol));
 	scope->parent = lyn->cur;
 
 	if (!lyn->root)
@@ -162,23 +157,17 @@ int lyn_create_scope(struct lyn *lyn)
 	return 0;
 }
 
-static struct visible *scope_find(struct lyn_scope *scope, const char *name)
+static struct lyn_symbol *scope_find(struct lyn_scope *scope, const char *name)
 {
-	foreach_vec(vi, scope->visible) {
-		struct visible *v = vec_at(&scope->visible, vi);
-		if (strcmp(v->name, name) == 0)
-			return v;
-	}
-
-	return NULL;
+	return lookup_at(&scope->visible, name);
 }
 
-static struct visible *scopes_find(struct lyn_scope *scope, const char *name)
+static struct lyn_symbol *scopes_find(struct lyn_scope *scope, const char *name)
 {
 	while (scope) {
-		struct visible *v = scope_find(scope, name);
-		if (v)
-			return v;
+		struct lyn_symbol *s = scope_find(scope, name);
+		if (s)
+			return s;
 
 		scope = scope->parent;
 	}
@@ -188,13 +177,11 @@ static struct visible *scopes_find(struct lyn_scope *scope, const char *name)
 
 static int scope_add(struct lyn_scope *scope, const char *name, struct lyn_symbol symb)
 {
-	if (scope_find(scope, name)) {
+	if (!lookup_insert(&scope->visible, name, &symb)) {
 		error("%s exists in scope\n", name);
 		return -1;
 	}
 
-	struct visible v = {.name = name, .symb = symb};
-	vect_append(struct visible, scope->visible, &v);
 	return 0;
 }
 
@@ -205,20 +192,16 @@ int lyn_create_symbol(struct lyn *lyn, const char *name, struct lyn_symbol symb)
 
 struct lyn_symbol *lyn_lookup_symbol(struct lyn *lyn, const char *name)
 {
-	struct visible *v = scopes_find(lyn->cur, name);
-	if (!v)
-		return NULL;
-
-	return &v->symb;
+	return scopes_find(lyn->cur, name);
 }
 
 int lyn_replace_symbol(struct lyn *lyn, const char *name, struct lyn_symbol symb)
 {
-	struct visible *v = scopes_find(lyn->cur, name);
-	if (!v)
+	struct lyn_symbol *s = scopes_find(lyn->cur, name);
+	if (!s)
 		return -1;
 
-	v->symb = symb;
+	*s = symb;
 	return 0;
 }