17 struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g)  in isl_tarjan_graph_free()  argument
19 	if (!g)  in isl_tarjan_graph_free()
21 	free(g->node);  in isl_tarjan_graph_free()
22 	free(g->stack);  in isl_tarjan_graph_free()
23 	free(g->order);  in isl_tarjan_graph_free()
24 	free(g);  in isl_tarjan_graph_free()
30 	struct isl_tarjan_graph *g;  in isl_tarjan_graph_alloc()  local
33 	g = isl_calloc_type(ctx, struct isl_tarjan_graph);  in isl_tarjan_graph_alloc()
34 	if (!g)  in isl_tarjan_graph_alloc()
36 	g->len = len;  in isl_tarjan_graph_alloc()
37 	g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);  in isl_tarjan_graph_alloc()
38 	if (len && !g->node)  in isl_tarjan_graph_alloc()
41 		g->node[i].index = -1;  in isl_tarjan_graph_alloc()
42 	g->stack = isl_alloc_array(ctx, int, len);  in isl_tarjan_graph_alloc()
43 	if (len && !g->stack)  in isl_tarjan_graph_alloc()
45 	g->order = isl_alloc_array(ctx, int, 2 * len);  in isl_tarjan_graph_alloc()
46 	if (len && !g->order)  in isl_tarjan_graph_alloc()
49 	g->sp = 0;  in isl_tarjan_graph_alloc()
50 	g->index = 0;  in isl_tarjan_graph_alloc()
51 	g->op = 0;  in isl_tarjan_graph_alloc()
53 	return g;  in isl_tarjan_graph_alloc()
55 	isl_tarjan_graph_free(g);  in isl_tarjan_graph_alloc()
60  * in the graph with g->len nodes and with edges defined by "follows".
62 static isl_stat isl_tarjan_components(struct isl_tarjan_graph *g, int i,  in isl_tarjan_components()  argument
67 	g->node[i].index = g->index;  in isl_tarjan_components()
68 	g->node[i].min_index = g->index;  in isl_tarjan_components()
69 	g->node[i].on_stack = 1;  in isl_tarjan_components()
70 	g->index++;  in isl_tarjan_components()
71 	g->stack[g->sp++] = i;  in isl_tarjan_components()
73 	for (j = g->len - 1; j >= 0; --j) {  in isl_tarjan_components()
78 		if (g->node[j].index >= 0 &&  in isl_tarjan_components()
79 			(!g->node[j].on_stack ||  in isl_tarjan_components()
80 			 g->node[j].index > g->node[i].min_index))  in isl_tarjan_components()
89 		if (g->node[j].index < 0) {  in isl_tarjan_components()
90 			isl_tarjan_components(g, j, follows, user);  in isl_tarjan_components()
91 			if (g->node[j].min_index < g->node[i].min_index)  in isl_tarjan_components()
92 				g->node[i].min_index = g->node[j].min_index;  in isl_tarjan_components()
93 		} else if (g->node[j].index < g->node[i].min_index)  in isl_tarjan_components()
94 			g->node[i].min_index = g->node[j].index;  in isl_tarjan_components()
97 	if (g->node[i].index != g->node[i].min_index)  in isl_tarjan_components()
101 		j = g->stack[--g->sp];  in isl_tarjan_components()
102 		g->node[j].on_stack = 0;  in isl_tarjan_components()
103 		g->order[g->op++] = j;  in isl_tarjan_components()
105 	g->order[g->op++] = -1;  in isl_tarjan_components()
123 	struct isl_tarjan_graph *g = NULL;  in isl_tarjan_graph_init()  local
125 	g = isl_tarjan_graph_alloc(ctx, len);  in isl_tarjan_graph_init()
126 	if (!g)  in isl_tarjan_graph_init()
129 		if (g->node[i].index >= 0)  in isl_tarjan_graph_init()
131 		if (isl_tarjan_components(g, i, follows, user) < 0)  in isl_tarjan_graph_init()
132 			return isl_tarjan_graph_free(g);  in isl_tarjan_graph_init()
135 	return g;  in isl_tarjan_graph_init()
145  * in g->order.
150 	struct isl_tarjan_graph *g;  in isl_tarjan_graph_component()  local
152 	g = isl_tarjan_graph_alloc(ctx, len);  in isl_tarjan_graph_component()
153 	if (!g)  in isl_tarjan_graph_component()
155 	if (isl_tarjan_components(g, node, follows, user) < 0)  in isl_tarjan_graph_component()
156 		return isl_tarjan_graph_free(g);  in isl_tarjan_graph_component()
158 	return g;  in isl_tarjan_graph_component()