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 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 123 insertions(+)
create mode 100644 src/lookup.c
(limited to 'src/lookup.c')
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;
+}
--
cgit v1.2.3