source: sources/src/graph.cc @ 4

Last change on this file since 4 was 1, checked in by buchmann, 17 years ago

Initial import from CVS repository

File size: 8.8 KB
Line 
1/*------------------------------------------------------------\
2|                                                             |
3| Tool    :                  systemcass                       |
4|                                                             |
5| File    :                 graph.cc                          |
6|                                                             |
7| Author  :                 Petrot Frédéric                   |
8|                           Taktak Sami                       |
9|                           Buchmann Richard                  |
10|                                                             |
11| Date    :                   09_07_2004                      |
12|                                                             |
13\------------------------------------------------------------*/
14
15/*
16 * This file is part of the Disydent Project
17 * Copyright (C) Laboratoire LIP6 - Département ASIM
18 * Universite Pierre et Marie Curie
19 *
20 * Home page          : http://www-asim.lip6.fr/disydent
21 * E-mail             : mailto:richard.buchmann@lip6.fr
22 *
23 * This library is free software; you  can redistribute it and/or modify it
24 * under the terms  of the GNU Library General Public  License as published
25 * by the Free Software Foundation; either version 2 of the License, or (at
26 * your option) any later version.
27 *
28 * Disydent is distributed  in the hope  that it  will be
29 * useful, but WITHOUT  ANY WARRANTY; without even the  implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
31 * Public License for more details.
32 *
33 * You should have received a copy  of the GNU General Public License along
34 * with the GNU C Library; see the  file COPYING. If not, write to the Free
35 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
36 */
37
38/*
39 * $Log: graph.cc,v $
40 * Revision 1.10  2006/06/12 14:02:04  buchmann
41 * - Now sort transition and generation functions by fonction pointer
42 *   (Thank to Nicolas Pouillon)
43 * - Add Nicolas Pouillon as contributor into splash screen
44 * - Rename files and classes from "dependancy" to "dependency".
45 * - Add some references to bibliography file
46 * - Add licence note to every files
47 * - Rename "module graph" to "process graph"
48 * - Now dump module graph when using --t option and CASS scheduling at the same
49 *   time
50 *
51 * Bug fixes :
52 * - check user time ( != 0) before computing simulation performance
53 * - Remove reinterpret_cast (for pending write) because of unexpected results
54 * - Add ASSERT in trace functions
55 *
56 * Revision 1.9  2005/10/12 10:00:59  buchmann
57 * Bug fix :
58 * - test to avoid malloc(0)
59 *
60 * Remove :
61 * - unused variable
62 *
63 * Revision 1.8  2005/09/14 14:08:24  buchmann
64 * Add Werror flag to compile the debug library.
65 * Split sc_clock implementation from sc_port to sc_clock.
66 * Add a helper message to write mealy functions avoiding combinational cycle.
67 *
68 * Bug fix :
69 * - cvs rules is no longer circular
70 * - bit2string
71 * - port binding (sc_in to sc_out)
72 * - error message from FSM rules checker
73 * - sc_time copy operator
74 *
75 * Code cleaning :
76 * - remove duplicated code (entity.cc and sc_port.cc)
77 * - remove duplicated declarations (internal_ext.h and internal.h)
78 *
79 * Revision 1.7  2005/03/29 14:04:30  buchmann
80 * Bug fix :
81 * -  Evaluation order of Mealy functions
82 *
83 * Print more informations when DUMP_STAGE is defined.
84 *
85 * Revision 1.6  2005/01/20 09:15:12  buchmann
86 * add following functions to sc_uint classes :
87 * - operator []
88 * - range (left,right)
89 *
90 * support to port dependancy declarations.
91 * print used precompiled options in verbose mode.
92 * use pedantic flag.
93 * add some rules to generate documentations.
94 *
95 * Revision 1.5  2004/09/27 14:40:13  buchmann
96 * bug fix :
97 * - allow the use of user-defined structs in sc_signal/sc_in/sc_out/sc_inout
98 * - use sc_dt namespace like official SystemC engine
99 *
100 * add :
101 * - dump the signal/port/module dependancy graph in dot format
102 *
103 * Graph library is now splitted from the SystemCASS specific code.
104 *
105 */
106
107#include <stdio.h>
108#include <map>
109#include <string>
110
111#include "graph.h"
112#include "sc_sensitive.h"
113#include "sc_module.h"
114#include "sc_port.h"
115
116using namespace std;
117
118/* Sorry for that, Mr Knuth :-) */
119
120Graph *gb_new_graph(int n)
121{
122Graph *g;
123
124   g = (Graph *) malloc(sizeof(Graph));
125   g->n = n;
126   if (n)
127   {
128     g->vertices = (Vertex *) malloc(n * sizeof(Vertex));
129     (void)memset(g->vertices, 0, n * sizeof(Vertex));
130   } else {
131     g->vertices = NULL;
132   }
133   return g;
134}
135
136static void gb_new_arc(Vertex *u, Vertex *v, long l)
137{
138Arc *a;
139
140   a       = (Arc *) malloc(sizeof(Arc));
141   a->next = u->arcs;
142   u->arcs = a;
143   a->tip  = v;
144   a->len  = l;
145}
146
147/* end Sorry */
148
149#define VERTEX 220898
150
151#define type     u.I
152
153void new_arc(Vertex *u, Vertex *v)
154{
155Arc *a;
156#ifdef DEBUG
157        if ((u == NULL) || (v == NULL))
158                exit(29042004);
159#endif
160   for (a = u->arcs; a; a = a->next)
161      if (a->tip == v)
162         return;
163   gb_new_arc(u, v, 0L);
164}
165
166#define rank z.I
167#define parent y.V
168#define untagged x.A
169#define link w.V
170#define min v.V
171
172#define infinity g->n
173
174/* strong_component: extracts and topologically sorts the strong components of
175 * a graph.
176 * The returned data structure is a chain_list of chain_lists.
177 * The first list implicitely lists the components in order, and the pointed
178 * to ones list the components contents (one or more vertices) */
179
180extern strong_component_list_t *strong_component(Graph *g)
181{
182  long nn;
183  Vertex *active_stack;
184  Vertex *settled_stack;
185  Vertex *vv;
186 
187  register Vertex *v;
188 
189  strong_component_list_t *strongcomponents = new strong_component_list_t;
190        typedef std::vector<void*> void_list_t;
191  void_list_t *component;
192
193  if (g->vertices == NULL)
194    return strongcomponents;
195
196 /* Make all vertices unseen and all arcs untagged */
197 for (v = g->vertices + g->n - 1; v >= g->vertices; v--) {
198   v->rank = 0;
199   v->untagged = v->arcs;
200 }
201 nn = 0;
202 active_stack = settled_stack = NULL;
203
204 for (vv = g->vertices; vv < g->vertices + g->n; vv++)
205   if (vv->rank == 0) { /* vv is still unseen */
206     v = vv;
207     v->parent = NULL;
208     
209     v->rank = ++nn;
210     v->link = active_stack;
211     active_stack = v;
212     v->min = v;
213     
214     do { /* Eplore one step from the current vertex v, possibly moving to another vertex
215             and calling it v */
216       register Vertex *u;               /* a vertex adjacent to v */
217       register Arc *a = v->untagged;    /* v's first remaining untagged arc, if any */
218       if (a) {
219         u = a->tip;
220         v->untagged = a->next;    /* tag the arc from v to u */
221         if (u->rank) {    /* we've seen u already */
222           if (u->rank < v->min->rank) /* non-tree arc, jutt update v->min */
223             v->min = u;
224         } else {   /* u is presently unseen */
225           u->parent = v; /* the arcfrom v to u is a new tree arc */
226           v = u;         /* u will now be the currnt vertex */
227           v->rank = ++nn;  /* make vertex v active */
228           v->link = active_stack;
229           active_stack = v;
230           v->min = v;
231         }
232       } else { /* all arcs from v are tagged, so v matures */
233         u = v->parent; /* prepare to backtrack in the tree */
234         if (v->min == v) {
235           /* Remove v and all its successors on the activestack from the tree,
236              and mark them as a strong component of the graph */
237           register Vertex *t; /* runs though the vertices of the new strong component */
238           
239           t = active_stack;
240           active_stack = v->link;
241           v->link = settled_stack;
242           settled_stack = t; /* we've moved the top of one stack to the other */
243           component = new void_list_t;
244           /* singe vetex */
245           if (t != v) { /* NOT singe vetex */
246             while (t != v) {
247               component->push_back(t->data);
248               t->rank = infinity; /* now t is settled */
249               t->parent = v;  /* and v represents the new strong component */
250               t = t->link;
251             }
252           }
253           component->push_back(v->data);
254           strongcomponents->push_back(component);
255           v->rank = infinity; /* v too is settled */
256           v->parent = v; /* and represents its own strong component */
257         } else /* the arc from u to v has just matured, making v->min visible from u */
258           if (v->min->rank < u->min->rank) u->min = v->min;
259         v = u; /* the former parent of v is the new current vertex v */
260       }
261     } while (v != NULL);
262   }
263
264 return strongcomponents;
265}
266
267bool 
268has_cycle (const strong_component_list_t &l)
269{       
270        strong_component_list_t::const_iterator it;
271        for (it = l.begin (); it != l.end (); ++it)
272        {
273                if ((*it)->size() > 1)
274                        return true;
275        }
276        return false;
277}
278
279#if 0
280const component_list_t*
281get_cycle (const strong_component_list_t &l)
282{       
283        strong_component_list_t::const_iterator it;
284        for (it = l.begin (); it != l.end (); ++it)
285        {
286    const component_list_t *c = *it;
287                if (c->size() > 1)
288                        return c;
289        }
290        return NULL;
291}
292
293void
294print_cycle (std::ostream &o,
295             const component_list_t *c)
296{
297  if (c == NULL)
298    return;
299  component_list_t::const_iterator it;
300  for (it = c->begin (); it != c->end (); ++it)
301  {
302    void *v = *it;
303    o << hex << (int) v << " ";
304  }
305  o << "\n";
306}
307#endif
308
Note: See TracBrowser for help on using the repository browser.