summaryrefslogtreecommitdiff
path: root/hash_tables.c
diff options
context:
space:
mode:
Diffstat (limited to 'hash_tables.c')
-rw-r--r--hash_tables.c321
1 files changed, 0 insertions, 321 deletions
diff --git a/hash_tables.c b/hash_tables.c
deleted file mode 100644
index 58ccbfd..0000000
--- a/hash_tables.c
+++ /dev/null
@@ -1,321 +0,0 @@
-/*
- hash tables are initialized by setting them to {0}, e.g.
- HashTable x = {0};
-*/
-static void *val_get_ptr(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 type_eq(Type *t1, Type *t2);
-
-static U64 f32_hash(F32 f) {
- /* OPTIM */
- U64 hash = 0;
- if (f < 0) {
- hash = 0x9a6db29edcba8af4;
- f = -f;
- }
- F32 last = f;
- int exponent = 0;
- while (f > 1) {
- exponent++;
- f /= 10;
- if (f == last) {
- /* +/- infinity probably */
- hash ^= 0x78bf61a81e80b9f2;
- return hash;
- }
- last = f;
- }
- for (int i = 0; i < F32_MANT_DIG; i++) {
- f *= 10;
- }
- hash ^= (U64)exponent + (U64)F32_DIG * (U64)f;
- return hash;
-}
-
-static U64 f64_hash(F64 f) {
- /* OPTIM */
- U64 hash = 0;
- if (f < 0) {
- hash = 0x9a6db29edcba8af4;
- f = -f;
- }
- F64 last = f;
- int exponent = 0;
- while (f > 1) {
- exponent++;
- f /= 10;
- if (f == last) {
- /* +/- infinity probably */
- hash ^= 0x78bf61a81e80b9f2;
- return hash;
- }
- last = f;
- }
- for (int i = 0; i < F64_MANT_DIG; i++) {
- f *= 10;
- }
- hash ^= (U64)exponent + (U64)F64_DIG * (U64)f;
- return hash;
-}
-
-static void fprint_val(FILE *f, Value v, Type *t); /* DELME */
-static void fprint_type(FILE *out, Type *t); /* !! */
-/* Note that for these value hashing functions, values of different types may collide */
-static U64 val_ptr_hash(void *v, Type *t) {
- switch (t->kind) {
- case TYPE_VOID: return 0;
- case TYPE_UNKNOWN: return 0;
- case TYPE_BUILTIN:
- switch (t->builtin) {
- case BUILTIN_I8: return (U64)*(I8 *)v;
- case BUILTIN_U8: return (U64)*(U8 *)v;
- case BUILTIN_I16: return (U64)*(I16 *)v;
- case BUILTIN_U16: return (U64)*(U16 *)v;
- case BUILTIN_I32: return (U64)*(I32 *)v;
- case BUILTIN_U32: return (U64)*(U32 *)v;
- case BUILTIN_I64: return (U64)*(I64 *)v;
- case BUILTIN_U64: return (U64)*(U64 *)v;
- case BUILTIN_F32: return f32_hash(*(F32 *)v);
- case BUILTIN_F64: return f64_hash(*(F64 *)v);
- case BUILTIN_CHAR: return (U64)*(char *)v;
- case BUILTIN_BOOL: return (U64)*(bool *)v;
- }
- assert(0);
- return 0;
- case TYPE_FN: return (U64)*(FnExpr **)v;
- case TYPE_TUPLE: {
- U64 hash = 0;
- 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]);
- x = rand_u32(x);
- }
- return hash;
- }
- case TYPE_PTR: return (U64)*(void **)v;
- case TYPE_TYPE: return (U64)*(Type **)v;
- case TYPE_USER: return val_ptr_hash(v, type_inner(t));
- case TYPE_ARR: {
- U32 x = 1;
- U64 hash = 0;
- U64 size = (U64)compiler_sizeof(t->arr.of);
- for (U64 i = 0; i < (U64)t->arr.n; i++) {
- hash += (U64)x * val_ptr_hash((char *)v + i * size, t->arr.of);
- x = rand_u32(x);
- }
- return hash;
- }
- case TYPE_SLICE: {
- U32 x = 1;
- U64 hash = 0;
- Slice *s = v;
- U64 size = (U64)compiler_sizeof(t->slice);
- for (U64 i = 0; i < (U64)s->n; i++) {
- hash += (U64)x * val_ptr_hash((char *)s->data + i * size, t->slice);
- x = rand_u32(x);
- }
- return hash;
- }
- case TYPE_STRUCT: {
- U32 x = 1;
- U64 hash = 0;
- arr_foreach(t->struc.fields, Field, f) {
- hash += (U64)x * val_ptr_hash((char *)v + f->offset, f->type);
- x = rand_u32(x);
- }
- return hash;
- }
- }
- assert(0);
- return 0;
-}
-
-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) {
- switch (t->kind) {
- case TYPE_BUILTIN:
- switch (t->builtin) {
- case BUILTIN_I8: return *(I8 *)u == *(I8 *)v;
- case BUILTIN_U8: return *(U8 *)u == *(U8 *)v;
- case BUILTIN_I16: return *(I16 *)u == *(I16 *)v;
- case BUILTIN_U16: return *(U16 *)u == *(U16 *)v;
- case BUILTIN_I32: return *(I32 *)u == *(I32 *)v;
- case BUILTIN_U32: return *(U32 *)u == *(U32 *)v;
- case BUILTIN_I64: return *(I64 *)u == *(I64 *)v;
- case BUILTIN_U64: return *(U64 *)u == *(U64 *)v;
- case BUILTIN_F32: return *(F32 *)u == *(F32 *)v;
- case BUILTIN_F64: return *(F64 *)u == *(F64 *)v;
- case BUILTIN_BOOL: return *(bool *)u == *(bool *)v;
- case BUILTIN_CHAR: return *(char *)u == *(char *)v;
- }
- break;
- case TYPE_VOID:
- return true;
- case TYPE_UNKNOWN:
- return false;
- case TYPE_FN:
- return *(FnExpr **)u == *(FnExpr **)v;
- case TYPE_USER:
- return val_ptr_eq(u, v, type_inner(t));
- case TYPE_PTR:
- return *(void **)u == *(void **)v;
- case TYPE_TYPE:
- return type_eq(*(Type **)u, *(Type **)v);
- case TYPE_TUPLE: {
- 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]))
- return false;
- }
- return true;
- }
- case TYPE_ARR: {
- U64 size = (U64)compiler_sizeof(t->arr.of);
- char *uptr = u, *vptr = v;
- for (U64 i = 0; i < t->arr.n; i++) {
- if (!val_ptr_eq(uptr, vptr, t->arr.of))
- return false;
- uptr += size;
- vptr += size;
- }
- return true;
- }
- case TYPE_SLICE: {
- U64 size = (U64)compiler_sizeof(t->arr.of);
- Slice *r = u;
- Slice *s = v;
- if (r->n != s->n) return false;
- char *sptr = r->data, *tptr = s->data;
- for (U64 i = 0; i < (U64)s->n; i++) {
- if (!val_ptr_eq(sptr, tptr, t->slice))
- return false;
- sptr += size;
- tptr += size;
- }
- return true;
- }
- case TYPE_STRUCT:
- arr_foreach(t->struc.fields, Field, f) {
- if (!val_ptr_eq((char *)u + f->offset, (char *)v + f->offset, f->type))
- return false;
- }
- return true;
- }
- assert(0);
- 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);
-}
-
-/*
- 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, 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, I64 *associated_number) {
- if (h->n * 2 >= h->cap) {
- U64 new_cap = h->cap * 2 + 2;
- ValNumPair *new_data = a ? allocr_malloc(a, (size_t)new_cap * sizeof *new_data)
- : malloc((size_t)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 */
- 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;
- }
- ValNumPair *data = h->data;
- U64 index = val_hash(v, t) % h->cap;
- while (1) {
- if (h->occupied[index]) {
- 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;
- }
- data[index].val = v;
- data[index].num = *associated_number;
- h->occupied[index] = true;
- h->n++;
- return false;
-}
-
-/* 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);
- free(h->occupied);
-}
-
-static void val_hash_table_test(void) {
- HashTable h = {0};
- Type type;
- type.kind = TYPE_BUILTIN;
- type.builtin = BUILTIN_I64;
- type.flags = TYPE_IS_RESOLVED;
- 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();
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-25 06:28:03 +0000