From fae5ded33194f9a45ff2ea044954e45eea47da92 Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Thu, 4 Mar 2021 09:48:58 +0100
Subject: [PATCH] binary search

---
 sem.c           |  3 ++-
 sem/hm/gamma.c  | 19 +++++++++++++++++++
 sem/hm/gamma.h  | 16 +++++-----------
 sem/hm/scheme.c |  6 +-----
 sem/hm/scheme.h |  3 +++
 sem/hm/subst.c  | 10 ++++++++--
 6 files changed, 38 insertions(+), 19 deletions(-)

diff --git a/sem.c b/sem.c
index 5c14642..b5c48e5 100644
--- a/sem.c
+++ b/sem.c
@@ -3,7 +3,8 @@
 
 #include "list.h"
 #include "sem/scc.h"
-#include "sem/hm.h"
+#include "sem/hm/scheme.h"
+#include "sem/hm/gamma.h"
 #include "ast.h"
 
 void type_error(YYLTYPE l, bool d, const char *msg, ...)
diff --git a/sem/hm/gamma.c b/sem/hm/gamma.c
index f6e66ad..1dcad70 100644
--- a/sem/hm/gamma.c
+++ b/sem/hm/gamma.c
@@ -5,6 +5,19 @@
 
 #define IN_CAP 50
 
+struct gamma {
+	int capacity;
+	int fresh;
+	int scope;
+	int nentries;
+	struct gamma_entry *entries;
+};
+struct gamma_entry {
+	int scope;
+	struct ident var;
+	struct scheme *scheme;
+};
+
 struct gamma *gamma_init()
 {
 	struct gamma *gamma = xalloc(1, struct gamma);
@@ -62,6 +75,12 @@ void gamma_decrement_scope(struct gamma *gamma)
 	gamma->scope--;
 }
 
+void gamma_iter(struct gamma *gamma, void *st, void (*iter)(struct ident, struct scheme *, void *))
+{
+	for (int i = 0; i<gamma->nentries; i++)
+		iter(gamma->entries[i].var, gamma->entries[i].scheme, st);
+}
+
 struct scheme *gamma_lookup(struct gamma *gamma, struct ident ident)
 {
 	struct scheme *res = NULL;
diff --git a/sem/hm/gamma.h b/sem/hm/gamma.h
index b5f52a1..d84b7eb 100644
--- a/sem/hm/gamma.h
+++ b/sem/hm/gamma.h
@@ -3,26 +3,20 @@
 
 #include <stdlib.h>
 
+#include "scheme.h"
 #include "../hm.h"
 #include "../../ident.h"
 
-struct gamma {
-	int capacity;
-	int fresh;
-	int scope;
-	int nentries;
-	struct gamma_entry {
-		int scope;
-		struct ident var;
-		struct scheme *scheme;
-	} *entries;
-};
+struct gamma;
+struct gamma_entry;
 
 struct gamma *gamma_init();
 void gamma_insert(struct gamma *gamma, struct ident ident, struct scheme *scheme);
 void gamma_increment_scope(struct gamma *gamma);
 void gamma_decrement_scope(struct gamma *gamma);
 
+void gamma_iter(struct gamma *gamma, void *st, void (*iter)(struct ident, struct scheme *, void *));
+
 struct scheme *gamma_lookup(struct gamma *gamma, struct ident ident);
 struct type *gamma_fresh(struct gamma *gamma);
 
diff --git a/sem/hm/scheme.c b/sem/hm/scheme.c
index 7769649..ee10c7d 100644
--- a/sem/hm/scheme.c
+++ b/sem/hm/scheme.c
@@ -38,11 +38,7 @@ struct scheme *scheme_generalise(struct gamma *gamma, struct type *t)
 	s->nvar = 0;
 	s->var = xalloc(nftv, struct ident);
 	for (int i = 0; i<nftv; i++) {
-		bool skip = false;
-		for (int j = 0; j<gamma->nentries; j++)
-			if (ident_cmp(gamma->entries[j].var, ftv[i]) == 0)
-				skip = true;
-		if (skip)
+		if (gamma_lookup(gamma, ftv[i]) != NULL)
 			continue;
 		s->nvar++;
 		s->var[i] = ident_dup(ftv[i]);
diff --git a/sem/hm/scheme.h b/sem/hm/scheme.h
index 2228328..8fe3d6f 100644
--- a/sem/hm/scheme.h
+++ b/sem/hm/scheme.h
@@ -1,6 +1,9 @@
 #ifndef SEM_HM_SCHEME_H
 #define SEM_HM_SCHEME_H
 
+#include "gamma.h"
+struct gamma;
+
 #include "../hm.h"
 #include "../../ident.h"
 
diff --git a/sem/hm/subst.c b/sem/hm/subst.c
index df1007c..42a8f92 100644
--- a/sem/hm/subst.c
+++ b/sem/hm/subst.c
@@ -158,10 +158,16 @@ struct scheme *subst_apply_s(struct subst *subst, struct scheme *scheme)
 	return scheme;
 }
 
+
+static void giter(struct ident ident, struct scheme *s, void *st)
+{
+	subst_apply_s((struct subst *)st, s);
+	(void)ident;
+}
+
 struct gamma *subst_apply_g(struct subst *subst, struct gamma *gamma)
 {
-	for (int i = 0; i<gamma->nentries; i++)
-		subst_apply_s(subst, gamma->entries[i].scheme);
+	gamma_iter(gamma, (void *)subst, giter);
 	return gamma;
 }
 
-- 
2.20.1