From e800a25fd2c4945b465b4cd90b4d212272d1641c Mon Sep 17 00:00:00 2001 From: Leo Tenenbaum Date: Sun, 10 Nov 2019 14:57:13 -0500 Subject: added hash table test & fixed bugs there --- allocator.c | 13 +++++++ cgen.c | 6 ++-- hash_tables.c | 112 ++++++++++++++++++++++++++++++++++++++++++++-------------- tests.c | 1 + types.h | 9 ++++- 5 files changed, 111 insertions(+), 30 deletions(-) diff --git a/allocator.c b/allocator.c index 14b1a40..ce880a8 100644 --- a/allocator.c +++ b/allocator.c @@ -63,6 +63,19 @@ static void *allocr_realloc(Allocator *a, void *data, size_t old_size, size_t ne #endif } +static void allocr_free(Allocator *a, void *data, size_t size) { +#if NO_ALLOCATOR + (void)a; + (void)size; + free(data); +#else + /* OPTIM */ + (void)a; + (void)size; + (void)data; +#endif +} + static void allocr_free_all(Allocator *a) { for (Page *page = a->first; page;) { Page *next = page->next; diff --git a/cgen.c b/cgen.c index 575bdc7..a388b9b 100644 --- a/cgen.c +++ b/cgen.c @@ -734,9 +734,9 @@ static bool cgen_expr_pre(CGenerator *g, Expression *e) { } } else { - cgen_type_pre(g, &e->type, e->where); + if (!cgen_type_pre(g, &e->type, e->where)) return false; cgen_write(g, " %s", ret_name); - cgen_type_post(g, &e->type, e->where); + if (!cgen_type_post(g, &e->type, e->where)) return false; cgen_write(g, ";"); cgen_nl(g); } @@ -913,7 +913,7 @@ static bool cgen_expr_pre(CGenerator *g, Expression *e) { if (!cgen_type_pre(g, &ea->type, e->where)) return false; if (uses_ptr) - cgen_write(g, "p_"); + cgen_write(g, " p_"); else cgen_write(g, "(*p_)"); if (!cgen_type_post(g, &ea->type, e->where)) diff --git a/hash_tables.c b/hash_tables.c index 6c79e74..a8a5c82 100644 --- a/hash_tables.c +++ b/hash_tables.c @@ -3,9 +3,9 @@ HashTable x = {0}; */ static void *val_get_ptr(Value *v, Type *t); -static U64 val_hash(Value *v, Type *t); +static U64 val_hash(Value v, Type *t); static size_t compiler_sizeof(Type *t); -static bool val_eq(Value *u, Value *v, Type *t); +static bool val_eq(Value u, Value v, Type *t); static bool type_eq(Type *t1, Type *t2); static U64 f32_hash(F32 f) { @@ -88,7 +88,7 @@ static U64 val_ptr_hash(void *v, Type *t) { Value *elems = *(Value **)v; U32 x = 1; for (U64 i = 0; i < (U64)arr_len(t->tuple); i++) { - hash += (U64)x * val_hash(elems + i, &t->tuple[i]); + hash += (U64)x * val_hash(elems[i], &t->tuple[i]); x = rand_u32(x); } return hash; @@ -131,8 +131,8 @@ static U64 val_ptr_hash(void *v, Type *t) { return 0; } -static U64 val_hash(Value *v, Type *t) { - return val_ptr_hash(val_get_ptr(v, t), t); +static U64 val_hash(Value v, Type *t) { + return val_ptr_hash(val_get_ptr(&v, t), t); } static bool val_ptr_eq(void *u, void *v, Type *t) { @@ -169,7 +169,7 @@ static bool val_ptr_eq(void *u, void *v, Type *t) { Value *us = *(Value **)u; Value *vs = *(Value **)v; for (size_t i = 0; i < arr_len(t->tuple); i++) { - if (!val_eq(&us[i], &vs[i], &t->tuple[i])) + if (!val_eq(us[i], vs[i], &t->tuple[i])) return false; } return true; @@ -210,48 +210,108 @@ static bool val_ptr_eq(void *u, void *v, Type *t) { return false; } -static bool val_eq(Value *u, Value *v, Type *t) { - return val_ptr_eq(val_get_ptr(u, t), val_get_ptr(v, t), t); +static bool val_eq(Value u, Value v, Type *t) { + return val_ptr_eq(val_get_ptr(&u, t), val_get_ptr(&v, t), t); } /* for a value hash table, you must either ALWAYS or NEVER use an allocator all values in the hash table must have the same type. - returns true iff the value was already present + returns true iff the value was already present, and sets associated_number accordingly. + otherwise, associates the value with associated_number, and returns false. */ -static bool val_hash_table_adda(Allocator *a, HashTable *h, Value *v, Type *t) { +static bool val_hash_table_adda(Allocator *a, HashTable *h, Value v, Type *t, I64 *associated_number) { if (h->n * 2 >= h->cap) { U64 new_cap = h->cap * 2 + 2; - Value *new_data = a ? allocr_malloc(a, new_cap * (U64)sizeof(Value)) - : malloc(new_cap * sizeof(Value)); - h->occupied = a ? allocr_realloc(a, h->occupied, h->cap * (U64)sizeof(bool), - new_cap * (U64)sizeof(bool)) - : realloc(h->occupied, new_cap * sizeof(bool)); - Value *old_data = h->data; - for (size_t i = 0; i < h->n; i++) { + ValNumPair *new_data = a ? allocr_malloc(a, new_cap * (U64)sizeof *new_data) + : malloc(new_cap * sizeof *new_data); + bool *new_occupied = a ? allocr_calloc(a, (size_t)new_cap, sizeof *new_occupied) + : calloc((size_t)new_cap, sizeof *new_occupied); + ValNumPair *old_data = h->data; + bool *old_occupied = h->occupied; + for (U64 i = 0; i < h->cap; i++) { /* re-hash */ - U64 index = val_hash(&old_data[i], t) % new_cap; - while (h->occupied[index]) index++; - new_data[index] = old_data[i]; - h->occupied[index] = true; + if (old_occupied[i]) { + U64 index = val_hash(old_data[i].val, t) % new_cap; + while (new_occupied[index]) { + index++; + if (index >= new_cap) + index -= new_cap; + } + new_data[index] = old_data[i]; + new_occupied[index] = true; + } } h->data = new_data; + h->occupied = new_occupied; + if (a) { + allocr_free(a, old_occupied, h->cap * sizeof *old_occupied); + allocr_free(a, old_data, h->cap * sizeof *old_data); + } else { + free(old_occupied); + free(old_data); + } h->cap = new_cap; } - Value *vals = h->data; + ValNumPair *data = h->data; U64 index = val_hash(v, t) % h->cap; while (1) { if (h->occupied[index]) { - if (val_eq(v, &vals[index], t)) + if (val_eq(v, data[index].val, t)) { + *associated_number = data[index].num; return true; + } } else break; index++; + if (index >= h->cap) + index -= h->cap; } - vals[index] = *v; + data[index].val = v; + data[index].num = *associated_number; h->occupied[index] = true; + h->n++; return false; } -static void val_hash_table_add(HashTable *h, Value *v, Type *t) { - val_hash_table_adda(NULL, h, v, t); +/* see above */ +static bool val_hash_table_add(HashTable *h, Value v, Type *t, I64 *associated_number) { + return val_hash_table_adda(NULL, h, v, t, associated_number); +} + +/* only call if you're not using an allocator */ +static void hash_table_free(HashTable *h) { + free(h->data); +} + +static void val_hash_table_test(void) { + HashTable h = {0}; + Type type = {0}; + type.kind = TYPE_BUILTIN; + type.builtin = BUILTIN_I64; + for (I64 n = 0; n < 100; n++) { + Value v = {.i64 = n * n}; + if (val_hash_table_add(&h, v, &type, &n)) { + assert(!*"n*n already exists."); + } + } + for (I64 n = 0; n < 100; n++) { + Value v = {.i64 = n * n}; + I64 m = 0; + if (!val_hash_table_add(&h, v, &type, &m)) { + assert(!*"n*n does not exist."); + } + if (m != n) { + assert(!*"n*n exists, but has wrong associated value."); + } + } + I64 x = 100; + Value v = {.i64 = 8}; + if (val_hash_table_add(&h, v, &type, &x)) { + assert(!*"8 exists"); + } + hash_table_free(&h); +} + +static void hash_table_test(void) { + val_hash_table_test(); } diff --git a/tests.c b/tests.c index 3e08f4a..43d3e50 100644 --- a/tests.c +++ b/tests.c @@ -27,4 +27,5 @@ static void test_all(void) { arr_test(); block_arr_test(); idents_test(); + hash_table_test(); } diff --git a/types.h b/types.h index acf7bc0..9ba5bc0 100644 --- a/types.h +++ b/types.h @@ -466,6 +466,12 @@ typedef struct { U64 cap; } HashTable; +/* these are found in value hash tables */ +typedef struct { + Value val; + I64 num; +} ValNumPair; + typedef struct FnExpr { struct Declaration *params; /* declarations of the parameters to this function */ struct Declaration *ret_decls; /* array of decls, if this has named return values. otherwise, NULL */ @@ -475,7 +481,8 @@ typedef struct FnExpr { /* if name = NULL, this is an anonymous function, and id will be the ID of the fn. */ Identifier name; IdentID id; - HashTable *instances; /* for fns with co */ + HashTable *instances; /* for fns with constant parameters. the key is a tuple of the + constant parameters (note that this can be a 1-tuple) */ } c; } FnExpr; /* an expression such as fn(x: int) int { 2 * x } */ -- cgit v1.2.3