hashtable and symtable thingsHEADmaster

1 files changed, 135 insertions, 0 deletions

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);
+}