ir_graph_util.h File Reference

This graph shows which files directly or indirectly include this file:

Classes
struct	vertex
struct	edge
struct	graph
struct	dfn
struct	v_iter
Defines
#define	INVALID_EINDEX -1
#define	INVALID_VINDEX -1
#define	VERTEX_user(vertex) ((vertex)->user)
#define	VERTEX_from(vertex) ((vertex)->from)
#define	VERTEX_to(vertex) ((vertex)->to)
#define	VERTEX_fcnt(vertex) ((vertex)->fcnt)
#define	VERTEX_tcnt(vertex) ((vertex)->tcnt)
#define	VERTEX_level(vertex) ((vertex)->level)
#define	EDGE_user(edge) ((edge)->user)
#define	EDGE_from(edge) ((edge)->from)
#define	EDGE_to(edge) ((edge)->to)
#define	EDGE_nfrom(edge) ((edge)->nfrom)
#define	EDGE_nto(edge) ((edge)->nto)
#define	EDGE_etype(edge) ((edge)->etype)
#define	EDGE_RECURSIVE 1
#define	Set_EDGE_recursive(edge) (EDGE_etype(edge) \|= EDGE_RECURSIVE)
#define	EDGE_recursive(edge) (EDGE_etype(edge) & EDGE_RECURSIVE)
#define	DEF_VERTEX_SIZE 8
#define	DEF_EDGE_SIZE 8
#define	GRAPH_vcnt(g) ((g)->vcnt)
#define	GRAPH_vmax(g) ((g)->vmax)
#define	GRAPH_vfree(g) ((g)->vfree)
#define	GRAPH_ecnt(g) ((g)->ecnt)
#define	GRAPH_emax(g) ((g)->emax)
#define	GRAPH_efree(g) ((g)->efree)
#define	GRAPH_root(g) ((g)->root)
#define	GRAPH_m(g) ((g)->m)
#define	GRAPH_v(g) ((g)->v)
#define	GRAPH_v_i(g, index) ((g)->v[index])
#define	GRAPH_e(g) ((g)->e)
#define	GRAPH_e_i(g, index) ((g)->e[index])
#define	FOR_EACH_VERTEX(g, v)
#define	DFN_v_list(d) ((d)->v_list)
#define	DFN_v_list_i(d, i) ((d)->v_list[i])
#define	DFN_first(d) ((d)->first)
#define	DFN_end(d) ((d)->end)
#define	DFN_user(d) ((d)->user)
#define	DFN_user_i(d, i) ((d)->user[i])
#define	V_ITER_g(vi) ((vi)->g)
#define	V_ITER_c_v(vi) ((vi)->c_v)
#define	V_ITER_from_e(vi) ((vi)->from_e)
#define	V_ITER_to_e(vi) ((vi)->to_e)
#define	V_ITER_fcnt(vi) ((vi)->fcnt)
#define	V_ITER_nfrom(vi) ((vi)->nfrom)
#define	V_ITER_tcnt(vi) ((vi)->tcnt)
#define	V_ITER_nto(vi) ((vi)->nto)
#define	V_ITER_c_e(vi) ((vi)->c_e)
#define	V_ITER_m(vi) ((vi)->m)
#define	GR_ASSERT(EX, p) if (!(EX)) { printf("Graph assertion: "); printf(p); exit(1);}
#define	MEM_POOL_Alloc(m, s) malloc(s)
#define	MEM_POOL_Realloc(m, ob, os, ns) realloc(ob, ns)
#define	MEM_POOL_FREE(m, s) free(s)
Typedefs
typedef int	EINDEX
typedef int	VINDEX
typedef struct vertex	VERTEX
typedef int	ETYPEX
typedef int	BOOL
typedef char	MEM_POOL
typedef struct edge	EDGE
typedef struct graph	GRAPH
typedef struct dfn	DFN
typedef struct v_iter	V_ITER
Functions
void	Print_DFN (DFN , GRAPH g, void()(), void()())
DFN *	Depth_First_Ordering (GRAPH , MEM_POOL )
void	Free_DFN (DFN , MEM_POOL )
GRAPH *	build_graph_u (VINDEX, EINDEX, MEM_POOL *)
GRAPH *	build_graph (MEM_POOL *)
VINDEX	add_vertex (GRAPH , void )
EINDEX	add_edge (GRAPH , VINDEX, VINDEX, void )
BOOL	is_vertex (GRAPH *, VINDEX)
BOOL	is_edge (GRAPH *, EINDEX)
void	delete_edge (GRAPH *, EINDEX)
void *	delete_vertex (GRAPH *, VINDEX)
void *	get_vertex (GRAPH *, VINDEX)
void *	get_edge (GRAPH *, VINDEX, VINDEX)
void *	get_edge_u (GRAPH *, EINDEX)
void	set_edge_u (GRAPH , EINDEX, void )
int	num_preds (GRAPH *, VINDEX)
int	num_succs (GRAPH *, VINDEX)
int	edge_count (GRAPH *, VINDEX from, VINDEX to)
VINDEX	next_vertex (GRAPH *g, VINDEX vertex)
V_ITER *	create_vertex_iter (GRAPH , VINDEX, MEM_POOL )
VINDEX	first_v_preds (V_ITER *)
VINDEX	next_v_preds (V_ITER *)
VINDEX	first_v_succs (V_ITER *)
VINDEX	next_v_succs (V_ITER *)
void	set_vertex_level (GRAPH *, VINDEX r, int level)
int	get_vertex_level (GRAPH *, VINDEX r)

Define Documentation

#define DEF_EDGE_SIZE 8

Definition at line 185 of file ir_graph_util.h.

Referenced by build_call_graph().

#define DEF_VERTEX_SIZE 8

Definition at line 184 of file ir_graph_util.h.

Referenced by build_call_graph().

#define DFN_end ( d ) ((d)->end)

Definition at line 230 of file ir_graph_util.h.

#define DFN_first ( d ) ((d)->first)

Definition at line 229 of file ir_graph_util.h.

#define DFN_user ( d ) ((d)->user)

Definition at line 231 of file ir_graph_util.h.

Referenced by Depth_First_Ordering().

#define DFN_user_i	(	d,
		i		)	((d)->user[i])

Definition at line 232 of file ir_graph_util.h.

Referenced by Print_DFN(), and Search().

#define DFN_v_list ( d ) ((d)->v_list)

Definition at line 227 of file ir_graph_util.h.

#define DFN_v_list_i	(	d,
		i		)	((d)->v_list[i])

Definition at line 228 of file ir_graph_util.h.

#define EDGE_etype ( edge ) ((edge)->etype)

Definition at line 147 of file ir_graph_util.h.

#define EDGE_from ( edge ) ((edge)->from)

Definition at line 143 of file ir_graph_util.h.

#define EDGE_nfrom ( edge ) ((edge)->nfrom)

Definition at line 145 of file ir_graph_util.h.

#define EDGE_nto ( edge ) ((edge)->nto)

Definition at line 146 of file ir_graph_util.h.

#define EDGE_recursive ( edge ) (EDGE_etype(edge) & EDGE_RECURSIVE)

Definition at line 152 of file ir_graph_util.h.

#define EDGE_RECURSIVE 1

Definition at line 150 of file ir_graph_util.h.

#define EDGE_to ( edge ) ((edge)->to)

Definition at line 144 of file ir_graph_util.h.

#define EDGE_user ( edge ) ((edge)->user)

Definition at line 142 of file ir_graph_util.h.

#define FOR_EACH_VERTEX	(	g,
		v		)

Value:

for ( v = 0; v < GRAPH_vmax(g); v++ )   \
          if ( VERTEX_fcnt (&GRAPH_v_i(g,v)) != INVALID_VINDEX )

Definition at line 202 of file ir_graph_util.h.

#define GR_ASSERT	(	EX,
		p		)	if (!(EX)) { printf("Graph assertion: "); printf(p); exit(1);}

Definition at line 277 of file ir_graph_util.h.

Referenced by add_edge(), build_graph(), build_graph_u(), delete_edge(), delete_vertex(), Depth_First_Ordering(), edge_count(), get_edge(), get_edge_u(), get_vertex(), grow_edge(), grow_vertex(), next_vertex(), num_preds(), num_succs(), and Print_Pred().

#define GRAPH_e ( g ) ((g)->e)

Definition at line 198 of file ir_graph_util.h.

#define GRAPH_e_i	(	g,
		index		)	((g)->e[index])

Definition at line 199 of file ir_graph_util.h.

#define GRAPH_ecnt ( g ) ((g)->ecnt)

Definition at line 191 of file ir_graph_util.h.

#define GRAPH_efree ( g ) ((g)->efree)

Definition at line 193 of file ir_graph_util.h.

#define GRAPH_emax ( g ) ((g)->emax)

Definition at line 192 of file ir_graph_util.h.

#define GRAPH_m ( g ) ((g)->m)

Definition at line 195 of file ir_graph_util.h.

#define GRAPH_root ( g ) ((g)->root)

Definition at line 194 of file ir_graph_util.h.

#define GRAPH_v ( g ) ((g)->v)

Definition at line 196 of file ir_graph_util.h.

#define GRAPH_v_i	(	g,
		index		)	((g)->v[index])

Definition at line 197 of file ir_graph_util.h.

#define GRAPH_vcnt ( g ) ((g)->vcnt)

Definition at line 188 of file ir_graph_util.h.

#define GRAPH_vfree ( g ) ((g)->vfree)

Definition at line 190 of file ir_graph_util.h.

#define GRAPH_vmax ( g ) ((g)->vmax)

Definition at line 189 of file ir_graph_util.h.

#define INVALID_EINDEX -1

Definition at line 79 of file ir_graph_util.h.

#define INVALID_VINDEX -1

Definition at line 80 of file ir_graph_util.h.

#define MEM_POOL_Alloc	(	m,
		s		)	malloc(s)

Definition at line 278 of file ir_graph_util.h.

#define MEM_POOL_FREE	(	m,
		s		)	free(s)

Definition at line 280 of file ir_graph_util.h.

#define MEM_POOL_Realloc	(	m,
		ob,
		os,
		ns	)	realloc(ob, ns)

Definition at line 279 of file ir_graph_util.h.

#define Set_EDGE_recursive ( edge ) (EDGE_etype(edge) |= EDGE_RECURSIVE)

Definition at line 151 of file ir_graph_util.h.

#define V_ITER_c_e ( vi ) ((vi)->c_e)

Definition at line 274 of file ir_graph_util.h.

#define V_ITER_c_v ( vi ) ((vi)->c_v)

Definition at line 267 of file ir_graph_util.h.

#define V_ITER_fcnt ( vi ) ((vi)->fcnt)

Definition at line 270 of file ir_graph_util.h.

#define V_ITER_from_e ( vi ) ((vi)->from_e)

Definition at line 268 of file ir_graph_util.h.

#define V_ITER_g ( vi ) ((vi)->g)

Definition at line 266 of file ir_graph_util.h.

#define V_ITER_m ( vi ) ((vi)->m)

Definition at line 275 of file ir_graph_util.h.

#define V_ITER_nfrom ( vi ) ((vi)->nfrom)

Definition at line 271 of file ir_graph_util.h.

#define V_ITER_nto ( vi ) ((vi)->nto)

Definition at line 273 of file ir_graph_util.h.

#define V_ITER_tcnt ( vi ) ((vi)->tcnt)

Definition at line 272 of file ir_graph_util.h.

#define V_ITER_to_e ( vi ) ((vi)->to_e)

Definition at line 269 of file ir_graph_util.h.

#define VERTEX_fcnt ( vertex ) ((vertex)->fcnt)

Definition at line 107 of file ir_graph_util.h.

#define VERTEX_from ( vertex ) ((vertex)->from)

Definition at line 105 of file ir_graph_util.h.

#define VERTEX_level ( vertex ) ((vertex)->level)

Definition at line 109 of file ir_graph_util.h.

#define VERTEX_tcnt ( vertex ) ((vertex)->tcnt)

Definition at line 108 of file ir_graph_util.h.

#define VERTEX_to ( vertex ) ((vertex)->to)

Definition at line 106 of file ir_graph_util.h.

#define VERTEX_user ( vertex ) ((vertex)->user)

Definition at line 104 of file ir_graph_util.h.

Typedef Documentation

typedef int BOOL

Definition at line 125 of file ir_graph_util.h.

typedef struct dfn DFN

typedef struct edge EDGE

typedef int EINDEX

Definition at line 77 of file ir_graph_util.h.

typedef int ETYPEX

Definition at line 124 of file ir_graph_util.h.

typedef struct graph GRAPH

typedef char MEM_POOL

Definition at line 130 of file ir_graph_util.h.

typedef struct v_iter V_ITER

typedef struct vertex VERTEX

typedef int VINDEX

Definition at line 78 of file ir_graph_util.h.

Function Documentation

EINDEX add_edge	(	GRAPH *	,
		VINDEX	,
		VINDEX	,
		void *
	)

Definition at line 245 of file ir_graph_util.c.

References EDGE_etype, EDGE_from, EDGE_nfrom, EDGE_nto, EDGE_to, EDGE_user, GR_ASSERT, GRAPH_e_i, GRAPH_ecnt, GRAPH_efree, GRAPH_m, GRAPH_v_i, grow_edge(), is_vertex(), VERTEX_fcnt, VERTEX_from, VERTEX_tcnt, and VERTEX_to.

Here is the call graph for this function:

VINDEX add_vertex	(	GRAPH *	,
		void *
	)

Definition at line 207 of file ir_graph_util.c.

References GRAPH_m, GRAPH_v_i, GRAPH_vcnt, GRAPH_vfree, grow_vertex(), INVALID_EINDEX, VERTEX_fcnt, VERTEX_from, VERTEX_level, VERTEX_tcnt, VERTEX_to, and VERTEX_user.

Here is the call graph for this function:

GRAPH* build_graph ( MEM_POOL * )

Definition at line 123 of file ir_graph_util.c.

References bzero(), GR_ASSERT, GRAPH_ecnt, GRAPH_efree, GRAPH_m, GRAPH_root, GRAPH_vcnt, GRAPH_vfree, INVALID_VINDEX, and MEM_POOL_Alloc.

Here is the call graph for this function:

GRAPH* build_graph_u	(	VINDEX	,
		EINDEX	,
		MEM_POOL *
	)

Definition at line 57 of file ir_graph_util.c.

References bzero(), EDGE_from, EDGE_nfrom, GR_ASSERT, GRAPH_e, GRAPH_e_i, GRAPH_ecnt, GRAPH_efree, GRAPH_emax, GRAPH_m, GRAPH_root, GRAPH_v, GRAPH_v_i, GRAPH_vcnt, GRAPH_vfree, GRAPH_vmax, INVALID_VINDEX, MEM_POOL_Alloc, VERTEX_fcnt, and VERTEX_from.

Here is the call graph for this function:

V_ITER* create_vertex_iter	(	GRAPH *	,
		VINDEX	,
		MEM_POOL *
	)

Definition at line 542 of file ir_graph_util.c.

References GRAPH_v, MEM_POOL_Alloc, V_ITER_c_v, V_ITER_fcnt, V_ITER_from_e, V_ITER_g, V_ITER_m, V_ITER_nfrom, V_ITER_nto, V_ITER_tcnt, V_ITER_to_e, VERTEX_fcnt, VERTEX_from, VERTEX_tcnt, and VERTEX_to.

void delete_edge	(	GRAPH *	,
		EINDEX
	)

Definition at line 328 of file ir_graph_util.c.

References graph::e, EDGE_from, EDGE_nfrom, EDGE_nto, EDGE_to, GR_ASSERT, GRAPH_e_i, GRAPH_ecnt, GRAPH_efree, GRAPH_v_i, INVALID_VINDEX, is_edge(), edge::nto, VERTEX_fcnt, VERTEX_from, VERTEX_tcnt, and VERTEX_to.

Here is the call graph for this function:

void* delete_vertex	(	GRAPH *	,
		VINDEX
	)

Definition at line 402 of file ir_graph_util.c.

References delete_edge(), EDGE_nfrom, EDGE_nto, GR_ASSERT, GRAPH_e_i, GRAPH_v_i, GRAPH_vcnt, GRAPH_vfree, INVALID_EINDEX, is_vertex(), VERTEX_fcnt, VERTEX_from, VERTEX_to, and VERTEX_user.

Here is the call graph for this function:

DFN* Depth_First_Ordering	(	GRAPH *	,
		MEM_POOL *
	)

Definition at line 768 of file ir_graph_util.c.

References bzero(), d, DFN_end, DFN_first, DFN_user, DFN_v_list, edge_count(), GR_ASSERT, GRAPH_ecnt, GRAPH_root, GRAPH_vcnt, GRAPH_vmax, INVALID_EINDEX, INVALID_VINDEX, MEM_POOL_Alloc, MEM_POOL_FREE, NULL, and Search().

Here is the call graph for this function:

int edge_count	(	GRAPH *	,
		VINDEX	from,
		VINDEX	to
	)

Definition at line 502 of file ir_graph_util.c.

References EDGE_nfrom, EDGE_to, GR_ASSERT, GRAPH_e_i, GRAPH_v_i, INVALID_EINDEX, is_vertex(), and VERTEX_from.

Here is the call graph for this function:

VINDEX first_v_preds ( V_ITER * )

Definition at line 565 of file ir_graph_util.c.

References EDGE_from, EDGE_nto, GRAPH_e_i, INVALID_EINDEX, INVALID_VINDEX, MEM_POOL_FREE, V_ITER_c_e, V_ITER_g, V_ITER_m, V_ITER_nto, and V_ITER_to_e.

VINDEX first_v_succs ( V_ITER * )

Definition at line 622 of file ir_graph_util.c.

References EDGE_nfrom, EDGE_to, GRAPH_e_i, INVALID_EINDEX, INVALID_VINDEX, MEM_POOL_FREE, V_ITER_c_e, V_ITER_from_e, V_ITER_g, V_ITER_m, and V_ITER_nfrom.

void Free_DFN	(	DFN *	,
		MEM_POOL *
	)

Definition at line 870 of file ir_graph_util.c.

References DFN_v_list, and MEM_POOL_FREE.

void* get_edge	(	GRAPH *	,
		VINDEX	,
		VINDEX
	)

Definition at line 480 of file ir_graph_util.c.

References EDGE_nfrom, EDGE_to, EDGE_user, GR_ASSERT, GRAPH_e_i, GRAPH_v_i, INVALID_EINDEX, is_vertex(), and VERTEX_from.

Here is the call graph for this function:

void* get_edge_u	(	GRAPH *	,
		EINDEX
	)

Definition at line 524 of file ir_graph_util.c.

References EDGE_user, GR_ASSERT, GRAPH_e_i, and is_edge().

Here is the call graph for this function:

void* get_vertex	(	GRAPH *	,
		VINDEX
	)

Definition at line 450 of file ir_graph_util.c.

References GR_ASSERT, GRAPH_v_i, is_vertex(), and VERTEX_user.

Here is the call graph for this function:

int get_vertex_level	(	GRAPH *	,
		VINDEX	r
	)

Definition at line 674 of file ir_graph_util.c.

References GRAPH_v_i, and VERTEX_level.

BOOL is_edge	(	GRAPH *	,
		EINDEX
	)

Definition at line 441 of file ir_graph_util.c.

References EDGE_from, GRAPH_e_i, GRAPH_emax, and INVALID_VINDEX.

BOOL is_vertex	(	GRAPH *	,
		VINDEX
	)

Definition at line 303 of file ir_graph_util.c.

References GRAPH_v_i, GRAPH_vmax, INVALID_VINDEX, and VERTEX_fcnt.

VINDEX next_v_preds ( V_ITER * )

Definition at line 593 of file ir_graph_util.c.

References EDGE_from, EDGE_nto, GRAPH_e_i, INVALID_VINDEX, MEM_POOL_FREE, V_ITER_c_e, V_ITER_g, V_ITER_m, and V_ITER_nto.

VINDEX next_v_succs ( V_ITER * )

Definition at line 647 of file ir_graph_util.c.

References EDGE_nfrom, EDGE_to, GRAPH_e_i, INVALID_VINDEX, MEM_POOL_FREE, V_ITER_c_e, V_ITER_g, V_ITER_m, and V_ITER_nfrom.

VINDEX next_vertex	(	GRAPH *	g,
		VINDEX	vertex
	)

Definition at line 312 of file ir_graph_util.c.

References GR_ASSERT, GRAPH_vmax, INVALID_VINDEX, and is_vertex().

Here is the call graph for this function:

int num_preds	(	GRAPH *	,
		VINDEX
	)

Definition at line 460 of file ir_graph_util.c.

References GR_ASSERT, GRAPH_v_i, is_vertex(), and VERTEX_tcnt.

Here is the call graph for this function:

int num_succs	(	GRAPH *	,
		VINDEX
	)

Definition at line 470 of file ir_graph_util.c.

References GR_ASSERT, GRAPH_v_i, is_vertex(), and VERTEX_fcnt.

Here is the call graph for this function:

void Print_DFN	(	DFN *	,
		GRAPH *	g,
		void(*)()	,
		void(*)()
	)

Definition at line 836 of file ir_graph_util.c.

References DFN_end, DFN_first, DFN_user_i, DFN_v_list_i, get_vertex_level(), and Print_Pred().

Here is the call graph for this function:

void set_edge_u	(	GRAPH *	,
		EINDEX	,
		void *
	)

Definition at line 534 of file ir_graph_util.c.

References EDGE_user, and GRAPH_e_i.

void set_vertex_level	(	GRAPH *	,
		VINDEX	r,
		int	level
	)

Definition at line 683 of file ir_graph_util.c.

References GRAPH_v_i, and VERTEX_level.

ir_graph_util.h File Reference

Classes

Defines

Typedefs

Functions

Define Documentation

Typedef Documentation

Function Documentation