unify hashmap type

7 files changed, 161 insertions, 203 deletions

diff --git a/codegen.c b/codegen.c
index d9b2962..bca0411 100644
--- a/codegen.c
+++ b/codegen.c
@@ -1,4 +1,5 @@
 #include "ccc.h"
+#include "hashmap.h"
 #include "codegen.h"
 #include "scope.h"
 #include "register.h"
@@ -28,7 +29,7 @@ static struct reg* MULDIV_OVERFLOW_REG = &RDX;
 #define FULL_REG_SZ 8
 #define WORD_SZ 2
 
-static struct dseg dseg;
+static struct hash_map dseg;
 static struct scope* scope;
 static const struct fn_decl_node* active_fn;
 static integral_t branch_counter = 0;
diff --git a/dseg.c b/dseg.c
index 09e18a3..7236b88 100644
--- a/dseg.c
+++ b/dseg.c
@@ -8,35 +8,9 @@
 
 static integral_t string_counter = 0;
 
-void dseg_init(struct dseg* dseg) {
-    dseg->entries = ccc_alloc(DEFAULT_SIZE * sizeof(struct dseg_entry*));
-    dseg->cap = DEFAULT_SIZE;
-}
-
-static void dseg_entry_destroy(struct dseg_entry* entry) {
-    free(entry->symbol);
-}
-
-void dseg_destroy(struct dseg* dseg) {
-    for (integral_t i = 0; i < dseg->cap; i++) {
-        if (dseg->entries[i] == NULL) continue;
-        dseg_entry_destroy(dseg->entries[i]);
-        free(dseg->entries[i]);
-    }
-    free(dseg->entries);
-}
-
-static inline integral_t advance_hash(
-    integral_t hash,
-    integral_t val,
-    integral_t cap
-) {
-    return ((hash << 5) - hash + val) % cap;;
-}
-
 static integral_t hash_string(const char* str, integral_t cap) {
     integral_t hash = 0, i = 0;
-    while (str[i] != 0) hash = advance_hash(hash, str[i++], cap);
+    while (str[i] != 0) ADVANCE_HASH(hash, str[i++], cap);
     return hash;
 }
 
@@ -57,6 +31,22 @@ static bool ent_eq(const struct dseg_entry* a, const struct dseg_entry* b) {
     DSEG_PANIC("equality function not defined for entry type");
 }
 
+static void ent_destroy(struct dseg_entry* entry) {
+    free(entry->symbol);
+}
+
+void dseg_init(struct hash_map* dseg) {
+    hm_init(
+        dseg,
+        (hm_hash_fn) hash_ent,
+        (hm_eq_fn) ent_eq,
+        (hm_destroy_fn) ent_destroy);
+}
+
+void dseg_destroy(struct hash_map* dseg) {
+    hm_destroy(dseg);
+}
+
 static void ent_assign_key(struct dseg_entry* ent) {
     switch (ent->type) {
         case ENT_STRING:
@@ -70,47 +60,8 @@ static void ent_assign_key(struct dseg_entry* ent) {
     }
 }
 
-static struct dseg_entry** dseg_cell(
-    const struct dseg* dseg,
-    const struct dseg_entry* ent
-) {
-    integral_t orig_idx = hash_ent(ent, dseg->cap);
-    integral_t idx = orig_idx;
-
-    do {
-        if (dseg->entries[idx] == NULL || ent_eq(dseg->entries[idx], ent))
-            return &dseg->entries[idx];
-    } while ((idx = (idx + 1) % dseg->cap) != orig_idx);
-    return NULL;
-}
-
-static void rehash_dseg(struct dseg* dseg) {
-    struct dseg_entry** old_ents = dseg->entries;
-    integral_t old_cap = dseg->cap;
-
-    dseg->cap = (dseg->cap + 1) << 1;
-    dseg->entries = ccc_alloc(dseg->cap * sizeof(struct dseg_entry*));
-
-    for (integral_t i = 0; i < old_cap; i++) {
-        if (old_ents[i] == NULL) continue;
-        struct dseg_entry** cell = dseg_cell(dseg, old_ents[i]);
-        if (cell == NULL) {
-            fprintf(stderr, "ccc: data segment rehash failed, likely a bug\n");
-            exit(1);
-        }
-        *cell = old_ents[i];
-    }
-
-    free(old_ents);
-}
-
-const char* dseg_put(struct dseg* dseg, struct dseg_entry entry) {
-    struct dseg_entry** cell = dseg_cell(dseg, &entry);
-    while (cell == NULL) {
-        rehash_dseg(dseg);
-        cell = dseg_cell(dseg, &entry);
-    }
-
+const char* dseg_put(struct hash_map* dseg, struct dseg_entry entry) {
+    struct dseg_entry** cell = (struct dseg_entry**) hm_cell_w(dseg, &entry);
     if (*cell != NULL) return (*cell)->symbol;
     struct dseg_entry* new_ent = ccc_alloc(sizeof(struct dseg_entry));
     *cell = new_ent;
@@ -123,7 +74,7 @@ static inline bool is_printable(char c) {
     return ' ' <= c && c <= '~';
 }
 
-void emit_string(FILE* outfile, const struct dseg_entry* ent) {
+void emit_string_data(FILE* outfile, const struct dseg_entry* ent) {
     const char* str = ent->key.string;
     fprintf(outfile, "db ");
     for (integral_t i = 0; str[i] != 0;) {
@@ -138,16 +89,16 @@ void emit_string(FILE* outfile, const struct dseg_entry* ent) {
     fprintf(outfile, "0x0");
 }
 
-void emit_dseg(FILE* outfile, const struct dseg* dseg) {
+void emit_dseg(FILE* outfile, const struct hash_map* dseg) {
     fprintf(outfile, "section .data\n");
     for (integral_t i = 0; i < dseg->cap; i++) {
         const struct dseg_entry* ent = dseg->entries[i];
-        if (dseg->entries[i] == NULL) continue;
+        if (ent == NULL) continue;
 
         fprintf(outfile, "\t%s ", ent->symbol);
         switch (ent->type) {
             case ENT_STRING:
-                emit_string(outfile, ent);
+                emit_string_data(outfile, ent);
                 break;
         }
         fprintf(outfile, "\n");
diff --git a/dseg.h b/dseg.h
index 4decf2f..bceaac4 100644
--- a/dseg.h
+++ b/dseg.h
@@ -1,7 +1,7 @@
 #ifndef DSEG_H
 #define DSEG_H
 
-#include "ccc.h"
+#include "hashmap.h"
 #include <stdio.h>
 
 struct dseg_entry {
@@ -14,15 +14,9 @@ struct dseg_entry {
     char* symbol;
 };
 
-struct dseg {
-    struct dseg_entry** entries;
-    integral_t sz;
-    integral_t cap;
-};
-
-void dseg_init(struct dseg* dseg);
-void dseg_destroy(struct dseg* dseg);
-const char* dseg_put(struct dseg* dseg, struct dseg_entry entry);
-void emit_dseg(FILE* outfile, const struct dseg* dseg);
+void dseg_init(struct hash_map* dseg);
+void dseg_destroy(struct hash_map* dseg);
+const char* dseg_put(struct hash_map* dseg, struct dseg_entry entry);
+void emit_dseg(FILE* outfile, const struct hash_map* dseg);
 
 #endif
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;
+}
diff --git a/hashmap.h b/hashmap.h
new file mode 100644
index 0000000..ff52eb2
--- /dev/null
+++ b/hashmap.h
@@ -0,0 +1,26 @@
+#ifndef HASHMAP_H
+#define HASHMAP_H
+
+#include "ccc.h"
+
+#define ADVANCE_HASH(hash, val, cap) (hash = ((hash << 5) - hash + val) % cap)
+
+typedef integral_t (*hm_hash_fn)(const void*, integral_t);
+typedef bool (*hm_eq_fn)(const void*, const void*);
+typedef void (*hm_destroy_fn)(void*);
+
+struct hash_map {
+    void** entries;
+    integral_t cap;
+
+    hm_hash_fn hash_fn;
+    hm_eq_fn eq_fn;
+    hm_destroy_fn destroy_fn;
+};
+
+void hm_init(struct hash_map*, hm_hash_fn, hm_eq_fn, hm_destroy_fn);
+void hm_destroy(struct hash_map*);
+void** hm_cell_r(const struct hash_map*, const void*);
+void** hm_cell_w(struct hash_map*, const void*);
+
+#endif
diff --git a/scope.c b/scope.c
index 7077748..f47545e 100644
--- a/scope.c
+++ b/scope.c
@@ -1,121 +1,50 @@
 #include "scope.h"
 #include <stdlib.h>
-#include <stdio.h>
 #include <string.h>
 #define DEFAULT_SIZE 16
 
-static void scope_init(struct scope* scope) {
-    scope->types = ccc_alloc(DEFAULT_SIZE * sizeof(struct type_def*));
-    scope->type_cap = DEFAULT_SIZE;
-    scope->vars = ccc_alloc(DEFAULT_SIZE * sizeof(struct var_def*));
-    scope->var_cap = DEFAULT_SIZE;
-}
-
-static void var_destroy(struct var_def* var) {
-    free(var->name);
-}
-
-void scope_destroy(struct scope* scope) {
-    for (integral_t i = 0; i < scope->type_cap; i++) {
-        if (scope->types[i] != NULL) {
-            free(scope->types[i]);
-        }
-    }
-    free(scope->types);
-
-    for (integral_t i = 0; i < scope->var_cap; i++) {
-        if (scope->vars[i] != NULL) {
-            var_destroy(scope->vars[i]);
-            free(scope->vars[i]);
-        }
-    }
-    free(scope->vars);
-}
-
-static inline integral_t advance_hash(
-    integral_t hash,
-    integral_t val,
-    integral_t cap
-) {
-    return ((hash << 5) - hash + val) % cap;;
-}
-
 static integral_t hash_name(const char* name, integral_t cap) {
     integral_t hash = 0, i = 0;
-    while (name[i] != 0) hash = advance_hash(hash, name[i++], cap);
+    while (name[i] != 0) ADVANCE_HASH(hash, name[i++], cap);
     return hash;
 }
 
-static struct type_alias** type_cell(
-    const struct scope* scope,
-    const char* name
-) {
-    integral_t orig_idx = hash_name(name, scope->type_cap);
-    integral_t idx = orig_idx;
-
-    do {
-        if (scope->types[idx] == NULL
-                || strcmp(name, scope->types[idx]->name) == 0)
-            return &scope->types[idx];
-    } while ((idx = (idx + 1) % scope->type_cap) != orig_idx);
-    return NULL;
+static integral_t hash_type(const struct type_alias* type, integral_t cap) {
+    return hash_name(type->name, cap);
 }
 
-static void rehash_types(struct scope* scope) {
-    struct type_alias** old_types = scope->types;
-    integral_t old_cap = scope->type_cap;
-
-    scope->type_cap = (scope->type_cap + 1) << 1;
-    scope->types = ccc_alloc(scope->type_cap * sizeof(struct type_def*));
-
-    for (integral_t i = 0; i < old_cap; i++) {
-        if (old_types[i] == NULL) continue;
-
-        struct type_alias** cell = type_cell(scope, old_types[i]->name);
-        if (cell == NULL) {
-            fprintf(stderr, "ccc: types rehash failed, likely a bug\n");
-            exit(1);
-        }
-        *cell = old_types[i];
-    }
-
-    free(old_types);
+static bool type_eq(const struct type_alias* a, const struct type_alias* b) {
+    return strcmp(a->name, b->name) == 0;
 }
 
-static struct var_def** var_cell(
-    const struct scope* scope,
-    const char* name
-) {
-    integral_t orig_idx = hash_name(name, scope->var_cap);
-    integral_t idx = orig_idx;
-
-    do {
-        if (scope->vars[idx] == NULL
-                || strcmp(name, scope->vars[idx]->name) == 0)
-            return &scope->vars[idx];
-    } while ((idx = (idx + 1) % scope->var_cap) != orig_idx);
-    return NULL;
+static integral_t hash_var(const struct var_def* var, integral_t cap) {
+    return hash_name(var->name, cap);
 }
 
-static void rehash_vars(struct scope* scope) {
-    struct var_def** old_vars = scope->vars;
-    integral_t old_cap = scope->var_cap;
-
-    scope->var_cap = (scope->var_cap + 1) << 1;
-    scope->vars = ccc_alloc(scope->var_cap * sizeof(struct var_def*));
+static bool var_eq(const struct var_def* a, const struct var_def* b) {
+    return strcmp(a->name, b->name) == 0;
+}
 
-    for (integral_t i = 0; i < old_cap; i++) {
-        if (old_vars[i] == NULL) continue;
+static void var_destroy(struct var_def* var) {
+    free(var->name);
+}
 
-        struct var_def** cell = var_cell(scope, old_vars[i]->name);
-        if (cell == NULL) {
-            fprintf(stderr, "ccc: vars rehash failed, likely a bug\n");
-            exit(1);
-        }
-        *cell = old_vars[i];
-    }
+static void scope_init(struct scope* scope) {
+    hm_init(
+        &scope->types,
+        (hm_hash_fn) hash_type,
+        (hm_eq_fn) type_eq,
+        NULL);
+    hm_init(
+        &scope->vars,
+        (hm_hash_fn) hash_var,
+        (hm_eq_fn) var_eq,
+        (hm_destroy_fn) var_destroy);
+}
 
-    free(old_vars);
+void scope_destroy(struct scope* scope) {
+    hm_destroy(&scope->types);
+    hm_destroy(&scope->vars);
 }
 
 void scope_push(struct scope** p_scope) {
@@ -135,7 +64,9 @@ bool scope_get_type(
     const char* name
 ) {
     for (; scope != NULL; scope = scope->next_out) {
-        struct type_alias** cell = type_cell(scope, name);
+        const struct type_alias** cell = (const struct type_alias**) hm_cell_r(
+            &scope->types,
+            &(struct type_alias) { .name = name });
         if (cell == NULL || *cell == NULL) continue;
         if (p_entry != NULL) *p_entry = *cell;
         return true;
@@ -147,11 +78,8 @@ const struct type_alias* scope_define_type(
     struct scope* scope,
     struct type_alias type
 ) {
-    struct type_alias** cell = type_cell(scope, type.name);
-    while (cell == NULL) {
-        rehash_types(scope);
-        cell = type_cell(scope, type.name);
-    }
+    struct type_alias** cell =
+        (struct type_alias**) hm_cell_w(&scope->types, &type);
 
     /* redefinition leaks memory, so refuse */
     if (*cell != NULL) return NULL;
@@ -167,7 +95,9 @@ bool scope_get_var(
     const char* name
 ) {
     for (; scope != NULL; scope = scope->next_out) {
-        struct var_def** cell = var_cell(scope, name);
+        struct var_def** cell = (struct var_def**) hm_cell_r(
+            &scope->vars,
+            &(struct var_def) {.name = (char*) name});
         if (cell == NULL || *cell == NULL) continue;
         if (p_entry != NULL) *p_entry = *cell;
         return true;
@@ -176,11 +106,7 @@ bool scope_get_var(
 }
 
 struct var_def* scope_define_var(struct scope* scope, struct var_def var) {
-    struct var_def** cell = var_cell(scope, var.name);
-    while (cell == NULL) {
-        rehash_vars(scope);
-        cell = var_cell(scope, var.name);
-    }
+    struct var_def** cell = (struct var_def**) hm_cell_w(&scope->vars, &var);
 
     /* redefinition leaks memory, so refuse */
     if (*cell != NULL) return NULL;
diff --git a/scope.h b/scope.h
index 72b342c..4f7ac3a 100644
--- a/scope.h
+++ b/scope.h
@@ -3,6 +3,7 @@
 
 #include "ccc.h"
 #include "type.h"
+#include "hashmap.h"
 
 struct storage_location {
     enum {
@@ -36,14 +37,8 @@ struct var_def {
 };
 
 struct scope {
-    struct type_alias** types;
-    integral_t type_sz;
-    integral_t type_cap;
-
-    struct var_def** vars;
-    integral_t var_sz;
-    integral_t var_cap;
-
+    struct hash_map types;
+    struct hash_map vars;
     struct scope* next_out;
     integral_t bp_offset;
 };