blob: cfa2241c1e6b1384791c8b570a287bd9bf12c337 (
plain)
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
|
#include <stddef.h>
#include "chibicc.h"
static unsigned long hash_type(Type *type) {
unsigned long hash = 6997;
if (!type) return hash;
if (type->hashing) return hash;
type->hashing = 1;
#define EXTEND_HASH(v) hash = (hash * 33) ^ (size_t)(v)
EXTEND_HASH(type->kind);
EXTEND_HASH(type->size);
EXTEND_HASH(type->align);
EXTEND_HASH(type->is_unsigned);
EXTEND_HASH(type->is_atomic);
// EXTEND_HASH(hash_type(type->origin));
EXTEND_HASH(hash_type(type->base));
EXTEND_HASH(type->array_len);
EXTEND_HASH(type->vla_len);
EXTEND_HASH(type->vla_size);
EXTEND_HASH(type->members);
// TODO: assume the members pointers are actually same?
// for (Member *m = type->members; m; m = m->next) {
// EXTEND_HASH(hash_type(m->ty));
// EXTEND_HASH(m->name); // token
// EXTEND_HASH(m->idx);
// EXTEND_HASH(m->align);
// EXTEND_HASH(m->offset);
// EXTEND_HASH(m->is_bitfield);
// EXTEND_HASH(m->bit_offset);
// EXTEND_HASH(m->bit_width);
// }
EXTEND_HASH(type->is_flexible);
EXTEND_HASH(type->is_packed);
EXTEND_HASH(hash_type(type->return_ty));
EXTEND_HASH(hash_type(type->params));
EXTEND_HASH(type->is_variadic);
// EXTEND_HASH(type->next);
type->hashing = 0;
return hash;
}
int definitely_same_type(Type *type1, Type *type2) {
if (!type1 || !type2) return type1 == type2;
if (type1->hashing != type2->hashing) return 0;
if (type1->hashing) return type1 == type2;
type1->hashing = 1;
type2->hashing = 1;
#define FIELD_CHECK(field) if (type1->field != type2->field) goto disequal
#define RECURSE_CHECK(field) if (!definitely_same_type(type1->field, type2->field)) goto disequal
FIELD_CHECK(kind);
FIELD_CHECK(size);
FIELD_CHECK(align);
FIELD_CHECK(is_unsigned);
FIELD_CHECK(is_atomic);
// RECURSE_CHECK(origin);
RECURSE_CHECK(base);
FIELD_CHECK(array_len);
FIELD_CHECK(vla_len);
FIELD_CHECK(vla_size);
FIELD_CHECK(members);
FIELD_CHECK(is_flexible);
FIELD_CHECK(is_packed);
RECURSE_CHECK(return_ty);
FIELD_CHECK(params);
FIELD_CHECK(is_variadic);
// RECURSE_CHECK(next);
type1->hashing = 0;
type2->hashing = 0;
return 1;
disequal:
type1->hashing = 0;
type2->hashing = 0;
return 0;
}
static Type **HASH_MAP = 0;
static int CAP_HASH_MAP = 0;
static int N_HASH_MAP = 0;
Type *hash_lookup(Type *type) {
if (!CAP_HASH_MAP) return 0;
size_t idx = hash_type(type) % CAP_HASH_MAP;
while (HASH_MAP[idx]) {
if (definitely_same_type(HASH_MAP[idx], type)) {
return HASH_MAP[idx];
}
if (++idx == CAP_HASH_MAP) idx = 0;
}
return 0;
}
void hash_insert(Type *type) {
if ((N_HASH_MAP + 1) >= (CAP_HASH_MAP / 2)) {
// RESIZE AND REHASH
int old_cap = CAP_HASH_MAP;
Type **old_hash_map = HASH_MAP;
CAP_HASH_MAP = (CAP_HASH_MAP + 1) * 4;
N_HASH_MAP = 0;
HASH_MAP = calloc(CAP_HASH_MAP, sizeof(HASH_MAP[0]));
for (int i = 0; i < old_cap; i++)
if (old_hash_map[i])
hash_insert(old_hash_map[i]);
if (old_hash_map) free(old_hash_map);
}
N_HASH_MAP++;
size_t idx = hash_type(type) % CAP_HASH_MAP;
while (HASH_MAP[idx])
if (++idx == CAP_HASH_MAP) idx = 0;
HASH_MAP[idx] = type;
}
|
