From 59aaeb98322da272bc9454c31d6be5b8a8efa3da Mon Sep 17 00:00:00 2001 From: Mart Lubbers 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 #include +#include -#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; inedges; 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; innodes; i++) - ng->nodes[i] = stack[*sp+i]->data; + ng->nodes = malloc(ng->nnodes*sizeof(void *)); + if (ng == NULL) { + return 2; + } + for (int i = 0; innodes; 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; ifrom); - 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; innodes; i++) + if (freefun != NULL) { + for (int i = 0; innodes; 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