diff options
| -rw-r--r-- | codegen.c | 3 | ||||
| -rw-r--r-- | dseg.c | 95 | ||||
| -rw-r--r-- | dseg.h | 16 | ||||
| -rw-r--r-- | hashmap.c | 65 | ||||
| -rw-r--r-- | hashmap.h | 26 | ||||
| -rw-r--r-- | scope.c | 148 | ||||
| -rw-r--r-- | scope.h | 11 |
7 files changed, 161 insertions, 203 deletions
@@ -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; @@ -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"); @@ -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 @@ -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; @@ -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; }; |