summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--allocator.c13
-rw-r--r--cgen.c6
-rw-r--r--hash_tables.c112
-rw-r--r--tests.c1
-rw-r--r--types.h9
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 } */
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-25 06:28:11 +0000