1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
|
/*
Copyright (C) 2019, 2020 Leo Tenenbaum.
This file is part of toc. toc is distributed under version 3 of the GNU General Public License, without any warranty whatsoever.
You should have received a copy of the GNU General Public License along with toc. If not, see <https://www.gnu.org/licenses/>.
*/
/*
TODO: better hash functions, especially for integers
(right now, nearby integers are close together in hash
space, which is bad with the way these hash tables
are designed)
*/
/* NOTE: any time you see 0x then 16 hexadecimal digits, that's probably a random number for hashing */
/*
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 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.0f) {
++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.0) {
++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 U64 type_hash(Type *t) {
static const U64 starters[TYPE_COUNT] = {
0x40d8675d0f148df7,
0xee4db91f31fdf2e1,
0x94963ca71f7f0df4,
0x95b9d36f45f27cf2,
0x68d393d7cade0570,
0x8191b5178d728e8c,
0x50da97f1211b2423,
0xc3977306abd0ae6c,
0x87ea684427e1c521,
0xcee5fd6d6cbdfe23
};
U64 hash = starters[t->kind];
assert(t->flags & TYPE_IS_RESOLVED);
switch (t->kind) {
case TYPE_BUILTIN:
return hash + (U64)t->builtin * 0x1307787dfff73417;
case TYPE_VOID:
case TYPE_UNKNOWN:
return hash;
case TYPE_TUPLE:
arr_foreach(t->tuple, Type, sub)
hash = hash * type_hash(sub) + 0x16225b0aa9993299;
return hash;
case TYPE_FN:
arr_foreach(t->fn.types, Type, sub)
hash = hash * type_hash(sub) + 0x2092d851ab2008de;
return hash;
case TYPE_PTR:
hash += type_hash(t->ptr) * 0x277caae472151119 + 0xf5c6ae7b4dae3bcf;
return hash;
case TYPE_SLICE:
hash += type_hash(t->slice) * 0x67a571620f9a5d6a + 0xc3f91e92c844ab1f;
return hash;
case TYPE_STRUCT:
hash += (U64)t->struc;
return hash;
case TYPE_ARR:
hash += type_hash(t->arr.of) * 0x3b6256104800a414 + 0xa901e68bbd8968a1
+ 0xbf79c81a3e68e504 * t->arr.n;
return hash;
case TYPE_EXPR: break;
}
assert(0); return 0;
}
/* Note that for these value hashing functions, values of different types may collide */
static U64 val_ptr_hash(void *v, Type *t) {
assert(t->flags & TYPE_IS_RESOLVED);
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;
case BUILTIN_TYPE:
return type_hash(*(Type **)v);
case BUILTIN_PKG: {
Package *pkg = *(Package **)v;
return (U64)pkg;
} break;
}
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_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;
}
case TYPE_EXPR: break;
}
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) {
assert(t->flags & TYPE_IS_RESOLVED);
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;
case BUILTIN_TYPE: {
bool ret = type_eq(*(Type **)u, *(Type **)v);
return ret;
}
case BUILTIN_PKG:
return *(Package **)u == *(Package **)v;
}
break;
case TYPE_VOID:
return true;
case TYPE_UNKNOWN:
return false;
case TYPE_FN:
return *(FnExpr **)u == *(FnExpr **)v;
case TYPE_PTR:
return *(void **)u == *(void **)v;
case TYPE_TUPLE: {
Value *us = *(Value **)u;
Value *vs = *(Value **)v;
for (size_t i = 0, len = arr_len(t->tuple); i < len; ++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;
case TYPE_EXPR: break;
}
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);
}
/*
if already_exists is not NULL, this will create the instance if it does not exist,
and set already_exists accordingly
*/
/* OPTIM: store instances in a block array (remember that the pointers need to stay valid!) */
static Instance *instance_table_adda(Allocator *a, HashTable *h, Value v, Type *t,
bool *already_exists) {
if (h->n * 2 >= h->cap) {
U64 new_cap = h->cap * 2 + 3;
Instance **new_data = allocr_malloc(a, (size_t)new_cap * sizeof *new_data);
bool *new_occupied = allocr_calloc(a, (size_t)new_cap, sizeof *new_occupied);
Instance **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;
allocr_free(a, old_occupied, h->cap * sizeof *old_occupied);
allocr_free(a, old_data, h->cap * sizeof *old_data);
h->cap = new_cap;
}
Instance **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)) {
*already_exists = true;
return data[index];
}
} else break;
++index;
if (index >= h->cap)
index -= h->cap;
}
if (already_exists) {
/* create, because it doesn't exist */
*already_exists = false;
data[index] = allocr_malloc(a, sizeof *data[index]);
data[index]->val = v;
h->occupied[index] = true;
++h->n;
return data[index];
}
return NULL;
}
#if 0
/* only call if you're not using an allocator */
static void hash_table_free(HashTable *h) {
free(h->data);
free(h->occupied);
}
#endif
|