usefull commit message

1 files changed, 164 insertions, 0 deletions

diff --git a/src/hashtable.c b/src/hashtable.c
new file mode 100644
index 0000000..5ef1839
--- /dev/null
+++ b/src/hashtable.c
@@ -0,0 +1,164 @@
+#include <stdlib.h>
+#include <errno.h>
+
+#include "common.h"
+#include "hashtable.h"
+
+// TODO:
+// - automatic growing
+// - insertion options
+
+#define HASH(ht, key) (ht->hash_func(key) % ht->cap)
+
+static int hashtable_grow(hashtable_t ht, size_t cap);
+static int hashtable_find_item(hashtable_t ht, size_t idx, void *key, struct hashtable_item **item, struct hashtable_item **prev);
+static void hashtable_table_append_item(struct hashtable_item ** table, size_t idx, struct hashtable_item *item);
+
+hashtable_t hashtable_create(size_t cap, hashtable_hash_func hash_func, hashtable_equal_func equal_func)
+{
+    hashtable_t ht;
+    ERR_Z(ht = malloc(sizeof(*ht)), goto fail);
+
+    ht->hash_func = hash_func;
+    ht->equal_func = equal_func;
+    ht->cap = 0;
+    ht->size = 0;
+
+    ERR_ERRNO_SET(hashtable_grow(ht, cap), goto fail);
+    
+    return ht;
+fail:
+    hashtable_destroy(ht);
+    return NULL;
+}
+
+void hashtable_destroy(hashtable_t ht)
+{
+    if(!ht) return;
+    
+    if(ht->table) {
+        hashtable_for_each_item_safe(ht, item, i) {
+            free(item);
+        }
+        
+        free(ht->table);
+    }
+    
+    free(ht);
+}
+
+void hashtable_reset(hashtable_t ht)
+{
+    if(!ht) return;
+
+    if(ht->table) {
+        hashtable_for_each_item_safe(ht, item, i) {
+            free(item);
+        }
+    }
+
+    ht->size = 0;
+}
+
+int hashtable_insert(hashtable_t ht, void *key, void *data, void **prevkey, void **prevdata)
+{
+    size_t idx = HASH(ht, key);
+
+    struct hashtable_item *item, *prev;
+    hashtable_find_item(ht, idx, key, &item, &prev);
+    
+    if(item) {
+        if(prevkey)  *prevkey  = item->key;
+        if(prevdata) *prevdata = item->data;
+        item->key = key;
+        item->data = data;
+        return 0;
+    }
+    
+    ERR_Z(item = malloc(sizeof(*item)), return -ENOMEM);
+        
+    item->key = key;
+    item->data = data;
+    item->next = NULL;
+
+    hashtable_table_append_item(ht->table, idx, item);
+    ht->size++;
+    
+    if(ht->size > (ht->cap * 3/4)) {
+        return hashtable_grow(ht, 1 << ht->cap);
+    }
+    
+    return 0;
+}
+
+int hashtable_query(hashtable_t ht, void *key, void **data)
+{
+    size_t idx = HASH(ht, key);
+    
+    struct hashtable_item *item;
+    ERR_NZ_RET(hashtable_find_item(ht, idx, key, &item, NULL));
+
+    *data = item->data;
+    
+    return 0;
+}
+
+int hashtable_delete(hashtable_t ht, void *key)
+{
+    size_t idx = HASH(ht, key);
+    
+    struct hashtable_item *item, *prev;
+    ERR_NZ_RET(hashtable_find_item(ht, idx, key, &item, &prev));
+    
+    if(prev)
+        prev->next = item->next;
+    else
+        ht->table[idx] = item->next;
+
+    free(item);
+    
+    return 0;
+}
+
+static int hashtable_grow(hashtable_t ht, size_t cap)
+{
+    struct hashtable_item **new_table;
+    ERR_Z(new_table = calloc(cap, sizeof(*new_table)), return -ENOMEM);
+
+    if(ht->cap > 0) {
+        hashtable_for_each_item_safe(ht, item, i) {
+            // hash but with the new cap
+            size_t idx = ht->hash_func(item->key) % cap;
+            hashtable_table_append_item(new_table, idx, item);
+        }
+
+        free(ht->table);
+    }
+
+    ht->table = new_table;
+    ht->cap = cap;
+    
+    return 0;
+}
+
+static int hashtable_find_item(hashtable_t ht, size_t idx, void *key, struct hashtable_item **item, struct hashtable_item **prev)
+{
+    if(item) *item = NULL;
+    if(prev) *prev = NULL;
+
+    hashtable_for_each_item_on_index(ht, _item, idx) {
+        if(ht->equal_func(_item->key, key)) {
+            if(item) *item = _item;
+            return 0;
+        }
+        if(prev) *prev = _item;
+    }
+    
+    return -ENOENT;
+}
+
+static void hashtable_table_append_item(struct hashtable_item **table, size_t idx, struct hashtable_item *item)
+{
+    item->next = table[idx];
+    table[idx] = item;
+}