00001 /* 00002 00003 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00004 00005 This program is free software; you can redistribute it and/or modify it 00006 under the terms of version 2 of the GNU General Public License as 00007 published by the Free Software Foundation. 00008 00009 This program is distributed in the hope that it would be useful, but 00010 WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00012 00013 Further, this software is distributed without any warranty that it is 00014 free of the rightful claim of any third person regarding infringement 00015 or the like. Any license provided herein, whether implied or 00016 otherwise, applies only to this software file. Patent licenses, if 00017 any, provided herein do not apply to combinations of this program with 00018 other software, or any other product whatsoever. 00019 00020 You should have received a copy of the GNU General Public License along 00021 with this program; if not, write the Free Software Foundation, Inc., 59 00022 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00023 00024 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00025 Mountain View, CA 94043, or: 00026 00027 http://www.sgi.com 00028 00029 For further information regarding this notice, see: 00030 00031 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00032 00033 */ 00034 00035 00036 /* ==================================================================== 00037 * ==================================================================== 00038 * 00039 * Module: ip_graph.h 00040 * Author: Seema Hiranandani 00041 * 00042 * $Revision: 1.1 $ 00043 * $Date: 2005/07/27 02:22:18 $ 00044 * $Author: kevinlo $ 00045 * $Source: /depot/CVSROOT/javi/src/sw/cmplr/ir_tools/ir_graph_util.h,v $ 00046 * 00047 * Revision history: 00048 * 19-Aug-95 - Original Version 00049 * 00050 * Description: 00051 * 00052 * This module contains data structures for a graph abstraction. 00053 * This graph is used to construct, for instance, a call graph. 00054 * 00055 * ==================================================================== 00056 * ==================================================================== 00057 */ 00058 00059 #ifndef ip_graph_INCLUDED 00060 #define ip_graph_INCLUDED 00061 #ifdef __cplusplus 00062 extern "C" { 00063 #endif 00064 00065 /* ==================================================================== 00066 * 00067 * VERTEX / EDGE / GRAPH : Directed graph implementation 00068 * 00069 * A GRAPH is a set of VERTEX objects, connected by a set of EDGE 00070 * objects. These sets are implemented as a vector of VERTEXes and a 00071 * vector of EDGEs, with all references being indices into these 00072 * vectors. The sets are allowed to grow (by adding VERTEXes or EDGEs) 00073 * or to shrink (by deleting them). Growth may cause reallocation of 00074 * the vector. To minimize reallocation cost, it is done in larger 00075 * chunks than necessary. To avoid rearrangement of the data upon 00076 * deletion, the deleted VERTEX/EDGE is simply marked invalid. 00077 * 00078 * ==================================================================== 00079 */ 00080 00081 /* EDGE/VERTEX index types, and reserved index values: */ 00082 typedef int EINDEX; 00083 typedef int VINDEX; 00084 #define INVALID_EINDEX -1 00085 #define INVALID_VINDEX -1 00086 00087 /* ==================================================================== 00088 * 00089 * A VERTEX contains two singly-linked lists of EDGEs, one of EDGEs 00090 * starting at that VERTEX, and one of EDGEs ending at that VERTEX. 00091 * Each list is represented in the VERTEX by the index of its first 00092 * element (VERTEX_from and VERTEX_to) and a count of its elements 00093 * (VERTEX_fcnt and VERTEX_tcnt). An invalid (i.e. unused) VERTEX is 00094 * indicated by VERTEX_fcnt == INVALID_EINDEX. The VERTEX also 00095 * contains a pointer VERTEX_user to additional data required by the 00096 * client derived graph. The level of a vertex is defined as the (max level 00097 * of the immediate successors of the vertex) + 1 00098 * ==================================================================== 00099 */ 00100 00101 typedef struct vertex { 00102 void* user; /* user information */ 00103 EINDEX from, to; /* first edge from and to this vertex */ 00104 EINDEX fcnt, tcnt; /* from/to counts */ 00105 int level; /* level of the vertex */ 00106 } VERTEX; 00107 00108 /* Field access macros: */ 00109 #define VERTEX_user(vertex) ((vertex)->user) 00110 #define VERTEX_from(vertex) ((vertex)->from) 00111 #define VERTEX_to(vertex) ((vertex)->to) 00112 #define VERTEX_fcnt(vertex) ((vertex)->fcnt) 00113 #define VERTEX_tcnt(vertex) ((vertex)->tcnt) 00114 #define VERTEX_level(vertex) ((vertex)->level) 00115 /* ==================================================================== 00116 * 00117 * A EDGE contains two VERTEXes, its from VERTEX (EDGE_from) and its 00118 * to vertex (EDGE_to). It contains links (indices) to the next edges 00119 * in the VERTEX_from list for its from VERTEX (EDGE_nfrom), and in the 00120 * VERTEX_to list for its to VERTEX (EDGE_nto). It contains a flag 00121 * word containing attributes, and a pointer EDGE_user to additional 00122 * data required by the client derived graph. 00123 * 00124 * ==================================================================== 00125 */ 00126 00127 /* EDGE data structure: */ 00128 00129 typedef int ETYPEX; 00130 typedef int BOOL; 00131 #ifndef FALSE 00132 #define FALSE 0 00133 #define TRUE 1 00134 #endif 00135 typedef char MEM_POOL; 00136 00137 typedef struct edge { 00138 void * user; /* user information */ 00139 VINDEX from, to; /* from and to vertices */ 00140 EINDEX nfrom; /* next edge from the from vertex */ 00141 EINDEX nto; /* next edge to the to vertex */ 00142 ETYPEX etype; /* edge type, i.e. is it a back edge resulting */ 00143 /* in a cycle: used to locate recursion */ 00144 } EDGE; 00145 00146 /* Field access macros: */ 00147 #define EDGE_user(edge) ((edge)->user) 00148 #define EDGE_from(edge) ((edge)->from) 00149 #define EDGE_to(edge) ((edge)->to) 00150 #define EDGE_nfrom(edge) ((edge)->nfrom) 00151 #define EDGE_nto(edge) ((edge)->nto) 00152 #define EDGE_etype(edge) ((edge)->etype) 00153 00154 /* Flag access: */ 00155 #define EDGE_RECURSIVE 1 00156 #define Set_EDGE_recursive(edge) (EDGE_etype(edge) |= EDGE_RECURSIVE) 00157 #define EDGE_recursive(edge) (EDGE_etype(edge) & EDGE_RECURSIVE) 00158 00159 /* ==================================================================== 00160 * 00161 * A GRAPH is the top-level directed graph data structure. For both 00162 * vertices and edges, it contains the number of VERTEX/EDGE structures 00163 * actually allocated (GRAPH_vmax, GRAPH_emax), the number of actual 00164 * VERTEX/EDGE components of the graph (GRAPH_vcnt, GRAPH_ecnt), the 00165 * number of free VERTEX/EDGE structures that are allocated and 00166 * available for use (GRAPH_vfree, GRAPH_efree), and the vector of 00167 * VERTEX_EDGE components (GRAPH_v, GRAPH_e). It also contains the 00168 * root of the graph (GRAPH_root) and the memory pool to use for 00169 * allocation (GRAPH_m). 00170 * 00171 * ==================================================================== 00172 */ 00173 00174 typedef struct graph { 00175 VINDEX vcnt; /* vertex count */ 00176 VINDEX vmax; /* max vertices */ 00177 VINDEX vfree; /* number of free vertices */ 00178 00179 EINDEX ecnt; /* edge count */ 00180 EINDEX emax; /* max edges */ 00181 EINDEX efree; /* number of free edges */ 00182 00183 VINDEX root; /* root of the graph */ 00184 VERTEX *v; /* list of vertices */ 00185 EDGE *e; /* list of edges */ 00186 MEM_POOL *m; /* mem pool */ 00187 } GRAPH; 00188 00189 #define DEF_VERTEX_SIZE 8 00190 #define DEF_EDGE_SIZE 8 00191 00192 /* Field access macros: */ 00193 #define GRAPH_vcnt(g) ((g)->vcnt) 00194 #define GRAPH_vmax(g) ((g)->vmax) 00195 #define GRAPH_vfree(g)((g)->vfree) 00196 #define GRAPH_ecnt(g) ((g)->ecnt) 00197 #define GRAPH_emax(g) ((g)->emax) 00198 #define GRAPH_efree(g) ((g)->efree) 00199 #define GRAPH_root(g) ((g)->root) 00200 #define GRAPH_m(g) ((g)->m) 00201 #define GRAPH_v(g) ((g)->v) 00202 #define GRAPH_v_i(g,index) ((g)->v[index]) 00203 #define GRAPH_e(g) ((g)->e) 00204 #define GRAPH_e_i(g,index) ((g)->e[index]) 00205 00206 /* Walk all the valid vertices in the graph g, using VINDEX v: */ 00207 #define FOR_EACH_VERTEX(g,v) \ 00208 for ( v = 0; v < GRAPH_vmax(g); v++ ) \ 00209 if ( VERTEX_fcnt (&GRAPH_v_i(g,v)) != INVALID_VINDEX ) 00210 00211 /* ==================================================================== 00212 * 00213 * DFN: Depth-first numbering graph traversal control struct 00214 * 00215 * This struct is used to store an ordering of the nodes in a graph, to 00216 * control traversal in a particular order. It contains a vector of 00217 * the graph vertices in the traversal order (DFN_v_list), and the 00218 * indices of the first useful index in the vector (GRAV_first) and of 00219 * the index after the last useful index in the vector (DFN_end). 00220 * 00221 * ==================================================================== 00222 */ 00223 00224 typedef struct dfn { 00225 int first; 00226 int end; 00227 VINDEX* v_list; 00228 void **user; 00229 } DFN; 00230 00231 /* Field access macros: */ 00232 #define DFN_v_list(d) ((d)->v_list) 00233 #define DFN_v_list_i(d,i) ((d)->v_list[i]) 00234 #define DFN_first(d) ((d)->first) 00235 #define DFN_end(d) ((d)->end) 00236 #define DFN_user(d) ((d)->user) 00237 #define DFN_user_i(d,i) ((d)->user[i]) 00238 00239 /* Trace a DFN ordering: */ 00240 extern void Print_DFN ( DFN *, GRAPH *g, void (*)(), void (*)()); 00241 00242 /* Construct a depth-first numbering of the given graph: */ 00243 extern DFN* Depth_First_Ordering ( GRAPH *, MEM_POOL * ); 00244 00245 /* De-allocate a DFN ordering: */ 00246 extern void Free_DFN ( DFN *, MEM_POOL * ); 00247 00248 /* ==================================================================== 00249 * 00250 * V_ITER: Vertex iterator control struct 00251 * 00252 * This struct is used to control an iterator over vertices. 00253 * 00254 * ==================================================================== 00255 */ 00256 00257 typedef struct v_iter { 00258 GRAPH *g; /* the graph */ 00259 VINDEX c_v; /* the current vertex */ 00260 EINDEX from_e; /* from edge */ 00261 EINDEX to_e; /* to edge */ 00262 EINDEX fcnt; /* from count */ 00263 EINDEX nfrom; /* next from edge */ 00264 EINDEX tcnt; /* to count */ 00265 EINDEX nto; /* next to edges */ 00266 EINDEX c_e; /* current edge */ 00267 MEM_POOL *m; /* mempool */ 00268 } V_ITER; 00269 00270 /* Field access macros: */ 00271 #define V_ITER_g(vi) ((vi)->g) 00272 #define V_ITER_c_v(vi) ((vi)->c_v) 00273 #define V_ITER_from_e(vi) ((vi)->from_e) 00274 #define V_ITER_to_e(vi) ((vi)->to_e) 00275 #define V_ITER_fcnt(vi) ((vi)->fcnt) 00276 #define V_ITER_nfrom(vi) ((vi)->nfrom) 00277 #define V_ITER_tcnt(vi) ((vi)->tcnt) 00278 #define V_ITER_nto(vi) ((vi)->nto) 00279 #define V_ITER_c_e(vi) ((vi)->c_e) 00280 #define V_ITER_m(vi) ((vi)->m) 00281 00282 #define GR_ASSERT(EX, p) if (!(EX)) { printf("Graph assertion: "); printf(p); exit(1);} 00283 #define MEM_POOL_Alloc(m, s) malloc(s) 00284 #define MEM_POOL_Realloc(m, ob, os, ns) realloc(ob, ns) 00285 #define MEM_POOL_FREE(m, s) free(s) 00286 00287 /* ==================================================================== 00288 * 00289 * External function declarations 00290 * 00291 * ==================================================================== 00292 */ 00293 00294 extern GRAPH* build_graph_u(VINDEX, EINDEX, MEM_POOL*); 00295 extern GRAPH* build_graph(MEM_POOL*); 00296 00297 extern VINDEX add_vertex(GRAPH*, void*); 00298 extern EINDEX add_edge(GRAPH*, VINDEX, VINDEX, void*); 00299 00300 extern BOOL is_vertex(GRAPH*, VINDEX); 00301 extern BOOL is_edge(GRAPH*, EINDEX); 00302 00303 extern void delete_edge(GRAPH*, EINDEX); 00304 extern void* delete_vertex(GRAPH*, VINDEX); 00305 00306 extern void* get_vertex(GRAPH*, VINDEX); 00307 extern void* get_edge(GRAPH*, VINDEX, VINDEX); 00308 extern void* get_edge_u(GRAPH*, EINDEX ); 00309 extern void set_edge_u (GRAPH *, EINDEX, void *); 00310 00311 extern int num_preds(GRAPH*, VINDEX); 00312 extern int num_succs(GRAPH*, VINDEX); 00313 extern int edge_count(GRAPH*, VINDEX from, VINDEX to); 00314 00315 extern VINDEX next_vertex(GRAPH *g, VINDEX vertex); 00316 00317 extern V_ITER* create_vertex_iter(GRAPH*, VINDEX, MEM_POOL*); 00318 extern VINDEX first_v_preds(V_ITER*); 00319 extern VINDEX next_v_preds(V_ITER*); 00320 extern VINDEX first_v_succs(V_ITER*); 00321 extern VINDEX next_v_succs(V_ITER*); 00322 00323 /* related to the level of a vertex in the graph */ 00324 extern void set_vertex_level(GRAPH*, VINDEX r, int level); 00325 extern int get_vertex_level(GRAPH*, VINDEX r); 00326 00327 #ifdef __cplusplus 00328 } 00329 #endif 00330 #endif /* ip_graph_INCLUDED */ 00331
1.5.6