From c5babf57de94a9a5e35c4bbb1237f3bffd15456c Mon Sep 17 00:00:00 2001
From: Kimplul <kimi.h.kuparinen@gmail.com>
Date: Sat, 19 Oct 2024 22:45:40 +0300
Subject: play around with lookup tables for commands
---
src/lookup.c | 123 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
src/lyn.c | 41 ++++++--------------
2 files changed, 135 insertions(+), 29 deletions(-)
create mode 100644 src/lookup.c
(limited to 'src')
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;
}
--
cgit v1.2.3