1 files changed, 65 insertions, 0 deletions
diff --git a/hashmap.c b/hashmap.c
new file mode 100644
index 0000000..2dc30e1
--- /dev/null
+++ b/hashmap.c
@@ -0,0 +1,65 @@
+#include "hashmap.h"
+#include <stdlib.h>
+#include <stdio.h>
+#define DEFAULT_CAP 16
+
+void hm_init (
+    struct hash_map* map,
+    hm_hash_fn hash_fn,
+    hm_eq_fn eq_fn,
+    hm_destroy_fn destroy_fn
+) {
+    map->cap = DEFAULT_CAP;
+    map->entries = ccc_alloc(map->cap * sizeof(void*));
+    map->hash_fn = hash_fn;
+    map->eq_fn = eq_fn;
+    map->destroy_fn = destroy_fn;
+}
+
+void hm_destroy(struct hash_map* map) {
+    for (integral_t i = 0; i < map->cap; i++) {
+        if (map->entries[i] == NULL) continue;
+        if (map->destroy_fn != NULL) map->destroy_fn(map->entries[i]);
+        free(map->entries[i]);
+    }
+    free(map->entries);
+}
+
+void** hm_cell_r(const struct hash_map* map, const void* entry) {
+    integral_t idx0 = map->hash_fn(entry, map->cap), idx = idx0;
+    
+    do {
+        if (map->entries[idx] == NULL || map->eq_fn(map->entries[idx], entry))
+            return &map->entries[idx];
+    } while ((idx = (idx + 1) % map->cap) != idx0);
+    return NULL;
+}
+
+static void rehash(struct hash_map* map) {
+    void** old_entries = map->entries;
+    integral_t old_cap = map->cap;
+
+    map->cap = (map->cap + 1) << 1;
+    map->entries = ccc_alloc(map->cap * sizeof(void*));
+
+    for (integral_t i = 0; i < old_cap; i++) {
+        if (old_entries[i] == NULL) continue;
+        void** cell = hm_cell_r(map, old_entries[i]);
+        if (cell == NULL) {
+            fprintf(stderr, "ccc: rehash failed, likely a bug\n");
+            exit(1);
+        }
+        *cell = old_entries[i];
+    }
+
+    free(old_entries);
+}
+
+void** hm_cell_w(struct hash_map* map, const void* entry) {
+    void** cell = hm_cell_r(map, entry);
+    while (cell == NULL) {
+        rehash(map);
+        cell = hm_cell_r(map, entry);
+    }
+    return cell;
+}