hashtable and symtable thingsHEADmaster

3 files changed, 182 insertions, 3 deletions

diff --git a/src/eval.h b/src/eval.h
index fc7b8ad..8b70a06 100644
--- a/src/eval.h
+++ b/src/eval.h
@@ -2,17 +2,38 @@
 #define EVAL_H
 
 #include "parser.h"
+#include "hashtbl.h"
 
 typedef struct eval *eval_t;
 
+// struct symdata {
+//     enum symbol_type {
+//         SYMBOL_VALUE,
+//         SYMBOL_FUNC,
+//         SYMBOL_FUNC_BUILTIN
+//     } type;
+//
+//     union {
+//         value_t value;
+//         ast_t   func;
+//         builtin_func_t builtin;
+//     };
+// };
+//
+// struct symtbl {
+//     hashtbl_t table;
+//     struct symtbl *parent;
+// };
+
 struct eval {
-    // symtbl_t root;
-    // symtbl_t *cur;
+    // struct symtbl root;
+    // struct symtbl *cur;
+    // ...
 };
 
 // TODO: add options for the evaluation
 eval_t eval_create();
 void eval_destroy(eval_t eval);
-int eval_ast(eval_t eval, parser_t ast);
+int eval_ast(eval_t eval, ast_t *ast);
 
 #endif
diff --git a/src/hashtbl.c b/src/hashtbl.c
new file mode 100644
index 0000000..02f2118
--- /dev/null
+++ b/src/hashtbl.c
@@ -0,0 +1,135 @@
+#include <stdio.h>
+#include <string.h>
+#include <errno.h>
+
+#include "common.h"
+#include "hashtbl.h"
+
+static struct hash_item *hash_item_alloc();
+static void hash_item_reset_rec(struct hash_item *item, bool should_free);
+
+static struct hash_item *hash_item_find(struct hash_item *item, char *key, bool create);
+
+static size_t hash(char *str)
+{
+    size_t hash = 5381;
+    char c;
+    while ((c = *str++) != 0)
+        hash = ((hash << 5) + hash) + (size_t)c;
+
+    // return hash;
+    return 0;
+}
+
+// ---------- Exported Functions ---------- //
+
+hashtbl_t hashtbl_create(size_t cap)
+{
+    hashtbl_t hashtbl = xmalloc(sizeof(*hashtbl));
+
+    hashtbl->cap = cap;
+    hashtbl->items = xcalloc(hashtbl->cap, sizeof(*hashtbl->items));
+
+    for(size_t i = 0; i < hashtbl->cap; i++) {
+        hashtbl->items[i] = hash_item_alloc();
+    }
+    
+    return hashtbl;
+}
+      
+void hashtbl_destroy(hashtbl_t hashtbl)
+{
+    if(hashtbl == NULL) return;
+    
+    for(int i = 0; i < hashtbl->cap; i++) {
+        hash_item_reset_rec(hashtbl->items[i], true);
+    }
+    
+    free(hashtbl->items);
+    free(hashtbl);
+}
+
+void hashtbl_reset(hashtbl_t hashtbl)
+{
+    for(int i = 0; i < hashtbl->cap; i++) {
+        hash_item_reset_rec(hashtbl->items[i]->next, true);
+        hash_item_reset_rec(hashtbl->items[i]->next, false);
+    }
+}
+
+#define HEAD_ITEM (hashtbl->items[hash(key) % hashtbl->cap])
+
+int hashtbl_insert(hashtbl_t hashtbl, char *key, void *data, size_t data_sz)
+{
+    struct hash_item *item = hash_item_find(HEAD_ITEM, key, true);
+
+    if(item->data) free(item->data);
+    
+    item->data = xmalloc(data_sz);
+    memcpy(item->data, data, data_sz);
+
+    return 0;
+}
+
+int hashtbl_query(hashtbl_t hashtbl, char *key, void **dest)
+{
+    struct hash_item *item = hash_item_find(HEAD_ITEM, key, false);
+    
+    if(item == NULL) return 1;
+    if(dest != NULL) *dest = item->data;
+    return 0;
+}
+
+// ---------- Helper Functions ---------- //
+
+static struct hash_item *hash_item_alloc()
+{
+    struct hash_item *item = xmalloc(sizeof(struct hash_item));
+    
+    item->next = NULL;
+    item->key = NULL;
+    item->data = NULL;
+    
+    return item;
+}
+
+static void hash_item_reset_rec(struct hash_item *item, bool should_free)
+{
+    if(item == NULL) return;
+    
+    if(item->key) free(item->key);
+    if(item->data) free(item->data);
+    
+    hash_item_reset_rec(item->next, should_free);
+    
+    if(should_free) free(item);
+}
+
+static struct hash_item *hash_item_find(struct hash_item *item, char *key, bool create)
+{
+    if(item-> key == NULL) {
+        if(!create) return NULL;
+        
+        item->key = xmalloc(strlen(key) + 1);
+        strcpy(item->key, key);
+        return item;
+    } 
+        
+    if(strcmp(key, item->key) == 0) {
+        return item;
+    }
+
+    if(item->next == NULL) {
+        if(!create) return NULL;
+        
+        struct hash_item *next = hash_item_alloc();
+        
+        next->key = xmalloc(strlen(key) + 1);
+        strcpy(next->key, key);
+        
+        item->next = next;
+        return item->next;
+    }
+    
+    return hash_item_find(item->next, key, create);
+}
diff --git a/src/hashtbl.h b/src/hashtbl.h
new file mode 100644
index 0000000..a6cfa10
--- /dev/null
+++ b/src/hashtbl.h
@@ -0,0 +1,23 @@
+#ifndef HASHTBL_H
+#define HASHTBL_H
+
+typedef struct hash_table *hashtbl_t;
+
+struct hash_table {    
+    struct hash_item {
+        struct hash_item *next;
+        char *key;
+        void *data;
+    } **items;
+    
+    size_t cap;
+};
+
+hashtbl_t hashtbl_create(size_t cap);
+void hashtbl_destroy(hashtbl_t hashtbl);
+void hashtbl_reset(hashtbl_t hashtbl);
+
+int hashtbl_insert(hashtbl_t hashtbl, char *key, void *data, size_t data_sz);
+int hashtbl_query(hashtbl_t hashtbl, char *key, void **dest);
+
+#endif