isl_basic_set_opt: accept NULL pointer on zero-size allocation
[isl.git] / isl_tarjan.c
blobea5bfa916e115c93d2bb0ec77c7e103dddf2b334
1 /*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2012 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13 #include <stdlib.h>
14 #include <isl/ctx.h>
15 #include <isl_tarjan.h>
17 void isl_tarjan_graph_free(struct isl_tarjan_graph *g)
19 if (!g)
20 return;
21 free(g->node);
22 free(g->stack);
23 free(g->order);
24 free(g);
27 static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)
29 struct isl_tarjan_graph *g;
30 int i;
32 g = isl_calloc_type(ctx, struct isl_tarjan_graph);
33 if (!g)
34 return NULL;
35 g->len = len;
36 g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);
37 if (!g->node)
38 goto error;
39 for (i = 0; i < len; ++i)
40 g->node[i].index = -1;
41 g->stack = isl_alloc_array(ctx, int, len);
42 if (!g->stack)
43 goto error;
44 g->order = isl_alloc_array(ctx, int, 2 * len);
45 if (!g->order)
46 goto error;
48 g->sp = 0;
49 g->index = 0;
50 g->op = 0;
52 return g;
53 error:
54 isl_tarjan_graph_free(g);
55 return NULL;
58 /* Perform Tarjan's algorithm for computing the strongly connected components
59 * in the graph with g->len nodes and with edges defined by "follows".
61 static int isl_tarjan_components(struct isl_tarjan_graph *g, int i,
62 int (*follows)(int i, int j, void *user), void *user)
64 int j;
66 g->node[i].index = g->index;
67 g->node[i].min_index = g->index;
68 g->node[i].on_stack = 1;
69 g->index++;
70 g->stack[g->sp++] = i;
72 for (j = g->len - 1; j >= 0; --j) {
73 int f;
75 if (j == i)
76 continue;
77 if (g->node[j].index >= 0 &&
78 (!g->node[j].on_stack ||
79 g->node[j].index > g->node[i].min_index))
80 continue;
82 f = follows(i, j, user);
83 if (f < 0)
84 return -1;
85 if (!f)
86 continue;
88 if (g->node[j].index < 0) {
89 isl_tarjan_components(g, j, follows, user);
90 if (g->node[j].min_index < g->node[i].min_index)
91 g->node[i].min_index = g->node[j].min_index;
92 } else if (g->node[j].index < g->node[i].min_index)
93 g->node[i].min_index = g->node[j].index;
96 if (g->node[i].index != g->node[i].min_index)
97 return 0;
99 do {
100 j = g->stack[--g->sp];
101 g->node[j].on_stack = 0;
102 g->order[g->op++] = j;
103 } while (j != i);
104 g->order[g->op++] = -1;
106 return 0;
109 /* Decompose the graph with "len" nodes and edges defined by "follows"
110 * into strongly connected components (SCCs).
111 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
112 * It should return -1 on error.
114 * If SCC a contains a node i that follows a node j in another SCC b
115 * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b
116 * in the result.
118 struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
119 int (*follows)(int i, int j, void *user), void *user)
121 int i;
122 struct isl_tarjan_graph *g = NULL;
124 g = isl_tarjan_graph_alloc(ctx, len);
125 if (!g)
126 return NULL;
127 for (i = len - 1; i >= 0; --i) {
128 if (g->node[i].index >= 0)
129 continue;
130 if (isl_tarjan_components(g, i, follows, user) < 0)
131 goto error;
134 return g;
135 error:
136 isl_tarjan_graph_free(g);
137 return NULL;