From 59aaeb98322da272bc9454c31d6be5b8a8efa3da Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Fri, 12 Feb 2021 16:32:33 +0100
Subject: [PATCH] polish tarjan

---
 scc.c    |  10 ++-
 tarjan.c | 184 +++++++++++++++++++++++++++++++++++--------------------
 tarjan.h |   3 +-
 3 files changed, 129 insertions(+), 68 deletions(-)

diff --git a/scc.c b/scc.c
index bf8a8b4..64e9ad0 100644
--- a/scc.c
+++ b/scc.c
@@ -131,7 +131,15 @@ struct ast *ast_scc(struct ast *ast)
 		list_to_array(edges, &nedges, false);
 
 	// Do tarjan's and convert back into the declaration list
-	struct components *cs = scc(nfun, (void **)fundecls, nedges, edgedata);
+	int err;
+	struct components *cs = tarjans(nfun, (void **)fundecls, nedges, edgedata, &err);
+	if (cs == NULL) {
+		if (err == 1)
+			die("malformed edges in tarjan's????");
+		else
+			pdie("malloc");
+	}
+
 	int i = ffun;
 	FOREACHCOMP(c, cs) {
 		struct decl *d = safe_malloc(sizeof(struct decl));
diff --git a/tarjan.c b/tarjan.c
index 5ac7e2d..f399b84 100644
--- a/tarjan.c
+++ b/tarjan.c
@@ -1,7 +1,10 @@
 #include <stddef.h>
 #include <stdlib.h>
+#include <stdbool.h>
 
-#include "util.h"
+#ifndef min
+#define min(x, y) ((x)<(y) ? (x) : (y))
+#endif
 
 struct edge {
 	void *from;
@@ -15,116 +18,165 @@ struct components {
 };
 
 struct node {
-	int lowlink;
 	int index;
+	int lowlink;
 	bool onStack;
 	void *data;
 };
 
-static int ptrcmp(const void *l, const void *r)
-{
-	return (ptrdiff_t)((struct node *)l)->data
-		- (ptrdiff_t)((struct node *)r)->data;
-}
+struct tjstate {
+	int index;
+	int sp;
+	int nedges;
+	struct edge *edges;
+	struct node **stack;
+	struct components *head;
+	struct components *tail;
+};
 
 static int nodecmp(const void *l, const void *r)
 {
 	return (ptrdiff_t)l -(ptrdiff_t)((struct node *)r)->data;
 }
 
-struct components *strongconnect(struct node *v, struct node **stack, int *sp,
-	int *index, int nedges, struct edge *edges,
-	struct components *res, struct components **tail)
+static int strongconnect(struct node *v, struct tjstate *tj)
 {
 	struct node *w;
-	v->index = *index;
-	v->lowlink = *index;
-	(*index)++;
-	stack[(*sp)++] = v;
+
+	/* Set the depth index for v to the smallest unused index */
+	v->index = tj->index;
+	v->lowlink = tj->index;
+	tj->index++;
+	tj->stack[tj->sp] = v;
+	tj->sp++;
 	v->onStack = true;
 
-	for (int i = 0; i<nedges; i++) {
-		//Only consider nodes reachable from v
-		if (edges[i].from != v)
+	for (int i = 0; i<tj->nedges; i++) {
+		/* Only consider nodes reachable from v */
+		if (tj->edges[i].from != v) {
 			continue;
-		w = edges[i].to;
-		if (w->index == -1)
-			res = strongconnect(w, stack, sp, index,
-				nedges, edges, res, tail);
-		else if (w->onStack)
+		}
+		w = tj->edges[i].to;
+		/* Successor w has not yet been visited; recurse on it */
+		if (w->index == -1) {
+			int r = strongconnect(w, tj);
+			if (r != 0)
+				return r;
+			v->lowlink = min(v->lowlink, w->lowlink);
+		/* Successor w is in stack S and hence in the current SCC */
+		} else if (w->onStack) {
 			v->lowlink = min(v->lowlink, w->index);
+		}
 	}
 
+	/* If v is a root node, pop the stack and generate an SCC */
 	if (v->lowlink == v->index) {
-		struct components *ng = safe_malloc(sizeof(struct components));
-		if (*tail == NULL)
-			res = ng;
-		else
-			(*tail)->next = ng;
-		*tail = ng;
+		struct components *ng = malloc(sizeof(struct components));
+		if (ng == NULL) {
+			return 2;
+		}
+		if (tj->tail == NULL) {
+			tj->head = ng;
+		} else {
+			tj->tail->next = ng;
+		}
+		tj->tail = ng;
 		ng->next = NULL;
-		ng->nnodes = *sp;
+		ng->nnodes = 0;
 		do {
-			w = stack[--(*sp)];
+			tj->sp--;
+			w = tj->stack[tj->sp];
 			w->onStack = false;
+			ng->nnodes++;
 		} while (w != v);
-		ng->nnodes -= *sp;
-		ng->nodes = safe_malloc(ng->nnodes*sizeof(void *));
-		for (int i = 0; i<ng->nnodes; i++)
-			ng->nodes[i] = stack[*sp+i]->data;
+		ng->nodes = malloc(ng->nnodes*sizeof(void *));
+		if (ng == NULL) {
+			return 2;
+		}
+		for (int i = 0; i<ng->nnodes; i++) {
+			ng->nodes[i] = tj->stack[tj->sp+i]->data;
+		}
 	}
-	return res;
+	return 0;
 }
 
-#define nsearch(key)\
-	bsearch(key, nodes, nnodes, sizeof(struct node), nodecmp);\
-	if (key == NULL) {\
-		fprintf(stderr, "edge references unknown node\n");\
-		goto end;\
-	}\
+static int ptrcmp(const void *l, const void *r)
+{
+	return (ptrdiff_t)((struct node *)l)->data
+		- (ptrdiff_t)((struct node *)r)->data;
+}
 
-struct components *scc(int nnodes, void **nodedata, int nedges, struct edge **edgedata)
+/**
+ * Calculate the strongly connected components using Tarjan's algorithm:
+ * en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
+ *
+ * Returns NULL when there are invalid edges and sets the error to:
+ * 1 if there was a malformed edge
+ * 2 if malloc failed
+ *
+ * @param number of nodes
+ * @param data of the nodes
+ * @param number of edges
+ * @param data of edges
+ * @param pointer to error code
+ */
+struct components *tarjans(
+		int nnodes, void *nodedata[],
+		int nedges, struct edge *edgedata[],
+		int *error)
 {
-	//Create nodes
-	struct node *nodes = safe_malloc(nnodes*sizeof(struct node));
-	for (int i = 0; i<nnodes; i++)
-		nodes[i] = (struct node){.lowlink=-1, .index=-1,
-			.onStack=false, .data=nodedata[i]};
+	struct node nodes[nnodes];
+	struct edge edges[nedges];
+	struct node *stack[nnodes];
+	struct node *from, *to;
+	struct tjstate tj = {0, 0, nedges, edges, stack, NULL, .tail=NULL};
+
+	// Populate the nodes
+	for (int i = 0; i<nnodes; i++) {
+		nodes[i] = (struct node){-1, -1, false, nodedata[i]};
+	}
 	qsort(nodes, nnodes, sizeof(struct node), ptrcmp);
 
-	//Create edges
-	struct edge *edges = safe_malloc(nedges*sizeof(struct edge));
+	// Populate the edges
 	for (int i = 0; i<nedges; i++) {
-		struct node *from = nsearch(edgedata[i]->from);
-		struct node *to = nsearch(edgedata[i]->to);
+		from = bsearch(edgedata[i]->from, nodes, nnodes,
+			sizeof(struct node), nodecmp);
+		if (from == NULL) {
+			*error = 1;
+			return NULL;
+		}
+		to = bsearch(edgedata[i]->to, nodes, nnodes,
+			sizeof(struct node), nodecmp);
+		if (to == NULL) {
+			*error = 1;
+			return NULL;
+		}
 		edges[i] = (struct edge){.from=from, .to=to};
 	}
 
 	//Tarjan's
-	struct components *res = NULL, *tail = NULL;
-	struct node **stack = safe_malloc(nnodes*sizeof(struct node *));
-	int sp = 0;
-	int index = 0;
 	for (int i = 0; i < nnodes; i++) {
-		if (nodes[i].index == -1)
-			res = strongconnect(&nodes[i], stack, &sp, &index,
-				nedges, edges, res, &tail);
+		if (nodes[i].index == -1) {
+			*error = strongconnect(&nodes[i], &tj);
+			if (*error != 0)
+				return NULL;
+		}
 	}
-	free(stack);
-end:
-	free(nodes);
-	free(edges);
-	return res;
+	return tj.head;
 }
 
 void components_free(struct components *cs, void (*freefun)(void *))
 {
+	struct components *t;
+
 	while (cs != NULL) {
-		if (freefun != NULL)
-			for (int i = 0; i<cs->nnodes; i++)
+		if (freefun != NULL) {
+			for (int i = 0; i<cs->nnodes; i++) {
 				freefun(cs->nodes[i]);
+			}
+		}
 		free(cs->nodes);
-		struct components *t = cs->next;
+		t = cs->next;
 		free(cs);
 		cs = t;
 	}
diff --git a/tarjan.h b/tarjan.h
index b2a8fbb..3bcf0b8 100644
--- a/tarjan.h
+++ b/tarjan.h
@@ -25,7 +25,8 @@ struct components {
  * @param number of edges
  * @param data of edges
  */
-struct components *scc(int nn, void **nodes, int ne, struct edge **edges);
+struct components *tarjans(int nnodes, void *nodedata[], int nedges,
+	struct edge *edgedata[], int *error);
 
 /**
  * Free a list of components
-- 
2.20.1