#include <string.h>
#include <stdlib.h>
+#include <stddef.h>
-#include "ast.h"
-#include "list.h"
-#include "tarjan.h"
+#include "../ast.h"
+#include "../list.h"
+
+#ifndef min
+#define min(x, y) ((x)<(y) ? (x) : (y))
+#endif
+
+struct edge {
+ void *from;
+ void *to;
+};
+
+struct components {
+ int nnodes;
+ void **nodes;
+ struct components *next;
+};
+
+struct node {
+ int index;
+ int lowlink;
+ bool onStack;
+ void *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;
+}
+
+static int strongconnect(struct node *v, struct tjstate *tj)
+{
+ struct node *w;
+
+ /* 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<tj->nedges; i++) {
+ /* Only consider nodes reachable from v */
+ if (tj->edges[i].from != v)
+ continue;
+ 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 (tj->tail == NULL)
+ tj->head = ng;
+ else
+ tj->tail->next = ng;
+ tj->tail = ng;
+ ng->next = NULL;
+ ng->nnodes = 0;
+ do {
+ tj->sp--;
+ w = tj->stack[tj->sp];
+ w->onStack = false;
+ ng->nnodes++;
+ } while (w != v);
+ ng->nodes = safe_malloc(ng->nnodes*sizeof(void *));
+ for (int i = 0; i<ng->nnodes; i++)
+ ng->nodes[i] = tj->stack[tj->sp+i]->data;
+ }
+ return 0;
+}
+
+static int ptrcmp(const void *l, const void *r)
+{
+ return (ptrdiff_t)((struct node *)l)->data
+ - (ptrdiff_t)((struct node *)r)->data;
+}
+
+/**
+ * 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
+ *
+ * @param number of nodes
+ * @param data of the nodes
+ * @param number of edges
+ * @param data of edges
+ */
+struct components *tarjans(
+ int nnodes, void *nodedata[],
+ int nedges, struct edge *edgedata[])
+{
+ 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);
+
+ // Populate the edges
+ for (int i = 0; i<nedges; i++) {
+ from = bsearch(edgedata[i]->from, nodes, nnodes,
+ sizeof(struct node), nodecmp);
+ if (from == NULL)
+ die("malformed from component of edge\n");
+ to = bsearch(edgedata[i]->to, nodes, nnodes,
+ sizeof(struct node), nodecmp);
+ if (to == NULL)
+ die("malformed to component of edge\n");
+ edges[i] = (struct edge){.from=from, .to=to};
+ }
+
+ //Tarjan's
+ for (int i = 0; i < nnodes; i++)
+ if (nodes[i].index == -1)
+ strongconnect(&nodes[i], &tj);
+ return tj.head;
+}
int iddeclcmp(const void *l, const void *r)
{
struct decl **to = bsearch(expr->data.efuncall.ident, decls,
ndecls, sizeof(struct decl *), iddeclcmp);
if (to == NULL) {
- fprintf(stderr, "calling an unknown function\n");
+ die("calling an unknown function\n");
} else {
struct edge *edge = safe_malloc(sizeof(struct edge));
edge->from = parent;
edges = edges_stmt(nfun, fundecls, fundecls[i],
fundecls[i]->data.dfun->body[j], edges);
int nedges;
- struct edge **edgedata = (struct edge **)
+ struct edge **edata = (struct edge **)
list_to_array(edges, &nedges, false);
// Do tarjan's and convert back into the declaration list
- 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");
- }
+ struct components *cs = tarjans(nfun, (void **)fundecls, nedges, edata);
+ if (cs == NULL)
+ die("malformed edges in tarjan's????");
int i = ffun;
- FOREACHCOMP(c, cs) {
+ for (struct components *c = cs; c != NULL; c = c->next) {
struct decl *d = safe_malloc(sizeof(struct decl));
if (c->nnodes > 1) {
d->type = dcomp;
//Cleanup
for (int i = 0; i<nedges; i++)
- free(edgedata[i]);
- free(edgedata);
- components_free(cs, free);
+ free(edata[i]);
+ free(edata);
+
+ struct components *t;
+ while (cs != NULL) {
+ for (int i = 0; i<cs->nnodes; i++)
+ free(cs->nodes[i]);
+ free(cs->nodes);
+ t = cs->next;
+ free(cs);
+ cs = t;
+ }
return ast;
}
repositories / ccc.git / blobdiff