From efba777fe43f8bf0fa3c269dee279ae60f002cf3 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Thu, 4 Mar 2021 09:17:24 +0100 Subject: [PATCH] make substitution a sorted set --- ident.c | 33 +++++++++++++------ ident.h | 6 ++-- sem/hm/subst.c | 89 ++++++++++++++++++++++++++++++++++---------------- sem/hm/subst.h | 4 +-- util.c | 1 + 5 files changed, 90 insertions(+), 43 deletions(-) diff --git a/ident.c b/ident.c index 966474a..43d026a 100644 --- a/ident.c +++ b/ident.c @@ -17,15 +17,29 @@ struct ident ident_int(int i) int ident_cmp(struct ident l, struct ident r) { - //int bigger than str - if (l.type == iint) - return r.type == iint ? l.data.iint - r.data.iint : 1; - else - return r.type == istr - ? strcmp(l.data.istr, r.data.istr) : -1; + //int > buf == str + switch (l.type) { + case iint: + switch (r.type) { + case iint: + return l.data.iint - r.data.iint; + default: + return 1; + } + break; + case istr: + switch (r.type) { + case iint: + return -1; + case istr: + return strcmp(l.data.istr, r.data.istr); + } + break; + } + return 0; } -int ident_cmpv(void *l, void *r) +int ident_cmpv(const void *l, const void *r) { return ident_cmp(*(struct ident *)l, *(struct ident *)r); } @@ -35,7 +49,7 @@ int ident_stricmp(char *l, struct ident r) return ident_cmp((struct ident){.type=istr, .data={.istr=l}}, r); } -int ident_stricmpv(void *l, void *r) +int ident_stricmpv(const void *l, const void *r) { return ident_stricmp((char *)l, *(struct ident *)r); } @@ -45,7 +59,7 @@ int ident_istrcmp(struct ident l, char *r) return ident_cmp(l, (struct ident){.type=istr, .data={.istr=r}}); } -int ident_istrcmpv(void *l, void *r) +int ident_istrcmpv(const void *l, const void *r) { return ident_istrcmp(*(struct ident *)l, (char *)r); } @@ -78,5 +92,4 @@ void ident_free(struct ident i) { if (i.type == istr) free(i.data.istr); - (void)i; } diff --git a/ident.h b/ident.h index 8c9f0bd..c059efe 100644 --- a/ident.h +++ b/ident.h @@ -15,11 +15,11 @@ struct ident ident_str(char *istr); struct ident ident_int(int iint); int ident_cmp(struct ident, struct ident); -int ident_cmpv(void *, void *); +int ident_cmpv(const void *, const void *); int ident_stricmp(char *, struct ident); -int ident_stricmpv(void *, void *); +int ident_stricmpv(const void *, const void *); int ident_istrcmp(struct ident, char *); -int ident_istrcmpv(void *, void *); +int ident_istrcmpv(const void *, const void *); struct ident ident_dup(struct ident); char *ident_tostr(struct ident); diff --git a/sem/hm/subst.c b/sem/hm/subst.c index 81c13c7..df1007c 100644 --- a/sem/hm/subst.c +++ b/sem/hm/subst.c @@ -1,5 +1,6 @@ #include #include +#include #include "../hm.h" #include "../../list.h" @@ -34,25 +35,59 @@ struct subst *subst_id() return res; } -struct subst *subst_insert(struct subst *s, struct ident ident, struct type *t) + +static inline void subst_increase_cap(struct subst *s) { - int i = 0; - while (i < s->nvar) { - if (ident_cmp(s->entries[i].var, ident) == 0) { - type_free(s->entries[i].type); - s->entries[i].type = type_dup(t); - return s; - } - i++; - } if (s->nvar >= s->capacity) { s->capacity += s->capacity; s->entries = xrealloc(s->entries, s->capacity, struct subst_entry); } +} + +static const void *bsearchfail; +int idententrycmp(const void *l, const void *r) +{ + bsearchfail = r; + return ident_cmp(*(struct ident *)l, ((struct subst_entry *)r)->var); +} + +struct subst *subst_insert(struct subst *s, struct ident ident, struct type *t) +{ + size_t idx; + //Shortcut, substitution is still empty + if (s->nvar == 0) { + idx = 0; + //Shortcut, ident is the biggest + } else if (ident_cmp(ident, s->entries[s->nvar-1].var) > 0) { + idx = s->nvar; + subst_increase_cap(s); + } else { + //See if it is already in here + bsearchfail = NULL; + struct subst_entry *e = bsearch(&ident, s->entries, s->nvar, + sizeof(struct subst_entry), idententrycmp); + if (e != NULL) { + type_free(e->type); + e->type = type_dup(t); + return s; + } + idx = ((intptr_t)s->entries-(intptr_t)bsearchfail) + /sizeof(struct subst_entry); + //check if it is smaller than the smallest + if (idx == 0) { + if (ident_cmp(ident, s->entries[0].var) > 0) + idx++; + } else if (idx >= s->nvar) + idx = s->nvar; + + subst_increase_cap(s); + for (size_t i = s->nvar; i>idx; i--) + s->entries[i] = s->entries[i-1]; + } + s->entries[idx].var = ident_dup(ident); + s->entries[idx].type = type_dup(t); s->nvar++; - s->entries[i].var = ident_dup(ident); - s->entries[i].type = type_dup(t); return s; } @@ -64,10 +99,10 @@ struct subst *subst_singleton(struct ident ident, struct type *t) struct subst *subst_union(struct subst *s1, struct subst *s2) { //Apply s1 on s2 - for (int i = 0; invar; i++) + for (size_t i = 0; invar; i++) s2->entries[i].type = subst_apply_t(s1, s2->entries[i].type); //Insert s1 into s2 - for (int i = 0; invar; i++) + for (size_t i = 0; invar; i++) subst_insert(s2, s1->entries[i].var, s1->entries[i].type); subst_free(s1); return s2; @@ -91,19 +126,17 @@ struct type *subst_apply_t(struct subst *subst, struct type *l) l->data.ttuple.l = subst_apply_t(subst, l->data.ttuple.l); l->data.ttuple.r = subst_apply_t(subst, l->data.ttuple.r); break; - case tvar: - for (int i = 0; invar; i++) { - if (ident_cmp(subst->entries[i].var, l->data.tvar) == 0) { - ident_free(l->data.tvar); - struct type *r = - type_dup(subst->entries[i].type); - *l = *r; - free(r); - break; - } + case tvar: { + struct subst_entry *e = bsearch(&l->data.tvar, subst->entries, + subst->nvar, sizeof(struct subst_entry), ident_cmpv); + if (e != NULL) { + ident_free(l->data.tvar); + struct type *r = type_dup(e->type); + *l = *r; + free(r); } break; - } + }} return l; } @@ -111,7 +144,7 @@ struct scheme *subst_apply_s(struct subst *subst, struct scheme *scheme) { //remove the quantified ones from the subst struct subst *s = subst_id(); - for (int j = 0; jnvar; j++) { + for (size_t j = 0; jnvar; j++) { bool found = false; for (int i = 0; invar; i++) if (ident_cmp(scheme->var[i], subst->entries[j].var) == 0) @@ -138,7 +171,7 @@ void subst_print(struct subst *s, FILE *out) fprintf(out, "(nil)"); } else { fprintf(out, "["); - for (int i = 0; invar; i++) { + for (size_t i = 0; invar; i++) { ident_print(s->entries[i].var, out); fprintf(out, "->"); type_print(s->entries[i].type, out); @@ -160,7 +193,7 @@ static void subst_really_free(void *sp) void subst_free(struct subst *s) { - for (int i = 0; invar; i++) { + for (size_t i = 0; invar; i++) { ident_free(s->entries[i].var); type_free(s->entries[i].type); } diff --git a/sem/hm/subst.h b/sem/hm/subst.h index 5df635a..579272e 100644 --- a/sem/hm/subst.h +++ b/sem/hm/subst.h @@ -6,8 +6,8 @@ #include "../../ident.h" struct subst { - int nvar; - int capacity; + size_t nvar; + size_t capacity; struct subst_entry *entries; }; struct subst_entry { diff --git a/util.c b/util.c index 7f26aa3..cdc0d28 100644 --- a/util.c +++ b/util.c @@ -2,6 +2,7 @@ #include #include #include +#include #include #include "util.h" -- 2.20.1