llvm/polly/lib/External/isl/isl_tarjan.c

/*
 * Copyright 2010-2011 INRIA Saclay
 * Copyright 2012      Ecole Normale Superieure
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
 * 91893 Orsay, France
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
 */

#include <stdlib.h>
#include <isl/ctx.h>
#include <isl_tarjan.h>

struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g)
{ … }

static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)
{ … }

/* Perform Tarjan's algorithm for computing the strongly connected components
 * in the graph with g->len nodes and with edges defined by "follows".
 */
static isl_stat isl_tarjan_components(struct isl_tarjan_graph *g, int i,
	isl_bool (*follows)(int i, int j, void *user), void *user)
{ … }

/* Decompose the graph with "len" nodes and edges defined by "follows"
 * into strongly connected components (SCCs).
 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
 * It should return -1 on error.
 *
 * If SCC a contains a node i that follows a node j in another SCC b
 * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b
 * in the result.
 */
struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
	isl_bool (*follows)(int i, int j, void *user), void *user)
{ … }

/* Decompose the graph with "len" nodes and edges defined by "follows"
 * into the strongly connected component (SCC) that contains "node"
 * as well as all SCCs that are followed by this SCC.
 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
 * It should return -1 on error.
 *
 * The SCC containing "node" will appear as the last component
 * in g->order.
 */
struct isl_tarjan_graph *isl_tarjan_graph_component(isl_ctx *ctx, int len,
	int node, isl_bool (*follows)(int i, int j, void *user), void *user)
{ … }