diff options
Diffstat (limited to 'hash_tables.c')
| -rw-r--r-- | hash_tables.c | 181 |
1 files changed, 181 insertions, 0 deletions
diff --git a/hash_tables.c b/hash_tables.c new file mode 100644 index 0000000..15121b0 --- /dev/null +++ b/hash_tables.c @@ -0,0 +1,181 @@ +/* +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 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; +} + +/* 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_eq(Value *u, Value *v, Type *t) { + /* TODO */ + return false; +} + +/* +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 +*/ +static bool val_hash_table_adda(Allocator *a, HashTable *h, Value *v, Type *t) { + 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++) { + /* 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; + } + h->data = new_data; + h->cap = new_cap; + } + Value *vals = h->data; + U64 index = val_hash(v, t) % h->cap; + while (1) { + if (h->occupied[index]) { + if (val_eq(v, &vals[index], t)) + return true; + } else break; + index++; + } + vals[index] = *v; + h->occupied[index] = true; + return false; +} + +static void val_hash_table_add(HashTable *h, Value *v, Type *t) { + val_hash_table_adda(NULL, h, v, t); +} |