polish tarjan

diff --git a/scc.c b/scc.c
index bf8a8b4..64e9ad0 100644 (file)
--- 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 (file)
--- 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 (file)
--- 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