source: vis_dev/vis-2.3/src/part/partTotal.c @ 86

Last change on this file since 86 was 14, checked in by cecile, 13 years ago

vis2.3
File size: 10.9 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [partTotal.c]
4
5  PackageName [part]
6
7  Synopsis [Implements the partition of the network replicating exactly the
8  network structure in the partition graph.]
9
10  Description [Implements the partition that replicates the structure of the
11  network.  Every node in the network will be represented in the partition by a
12  "single" vertex.]
13
14  SeeAlso     [part.h]
15
16  Author      [Abelardo Pardo]
17
18  Copyright [This file was created at the University of Colorado at Boulder.
19  The University of Colorado at Boulder makes no warranty about the suitability
20  of this software for any purpose.  It is presented on an AS IS basis.]
21
22******************************************************************************/
23
24#include "partInt.h"
25
26static char rcsid[] UNUSED = "$Id: partTotal.c,v 1.5 2005/04/16 06:14:54 fabio Exp $";
27
28/*---------------------------------------------------------------------------*/
29/* Constant declarations                                                     */
30/*---------------------------------------------------------------------------*/
31
32
33/*---------------------------------------------------------------------------*/
34/* Structure declarations                                                    */
35/*---------------------------------------------------------------------------*/
36
37
38/*---------------------------------------------------------------------------*/
39/* Type declarations                                                         */
40/*---------------------------------------------------------------------------*/
41
42
43/*---------------------------------------------------------------------------*/
44/* Variable declarations                                                     */
45/*---------------------------------------------------------------------------*/
46
47
48/*---------------------------------------------------------------------------*/
49/* Macro declarations                                                        */
50/*---------------------------------------------------------------------------*/
51
52
53/**AutomaticStart*************************************************************/
54
55/*---------------------------------------------------------------------------*/
56/* Static function prototypes                                                */
57/*---------------------------------------------------------------------------*/
58
59
60/**AutomaticEnd***************************************************************/
61
62
63/*---------------------------------------------------------------------------*/
64/* Definition of exported functions                                          */
65/*---------------------------------------------------------------------------*/
66
67
68/*---------------------------------------------------------------------------*/
69/* Definition of internal functions                                          */
70/*---------------------------------------------------------------------------*/
71
72/**Function********************************************************************
73
74  Synopsis [Implements the partition that replicates the structure of
75  the network.]
76
77  Description [The procedure receives a pointer to a network, a pointer to a
78  just created partition, and the lists of root and leave network nodes. <p>
79
80  The procedure proceeds as follows. It creates the necessary data to call the
81  function Ntm_NetworkBuildMdds.  The array of roots and table of leaves are
82  created in based to the parameters <tt>rootList<\tt> and <tt>leaveList<\tt>
83  respectively. For each root node, its mvf is computed as a function of its
84  inmediate fanin or the leaves, depending on the value of
85  <tt>inTermsOfLeaves<\tt>. Once this computation has finished, one vertex per
86  obtained function is added to the graph. Afterwards, for every vertex, the
87  support of its multi-valued function is computed and the pertinent vertices
88  created in the graph.]
89
90  SideEffects []
91
92  SeeAlso     [PartPartitionInputsOutputs]
93
94******************************************************************************/
95void
96PartPartitionTotal(
97  Ntk_Network_t *network,
98  graph_t       *partition,
99  lsList        rootList,
100  lsList        leaveList,
101  mdd_t         *careSet,
102  int           inTermsOfLeaves)
103{
104  Ntk_Node_t    *nodePtr;           /* Pointer to iterate over nodes */
105  lsList        nodeList;           /* list of network nodes */
106  lsGen         gen;                /* To iterate over lists */
107  array_t       *setOfFunctions;
108  array_t       *rootArray;
109  st_table      *tableOfLeaves;
110  vertex_t      *toVertex;
111  int           i;
112
113  /* Obtain the table of leaves of the partition */
114  tableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
115  if (leaveList == (lsList)0) {
116    Ntk_NetworkForEachCombInput(network, gen, nodePtr) {
117      st_insert(tableOfLeaves, (char *)nodePtr, (char *) (long) (-1));
118    }
119  } /* End of then */ 
120  else {
121    lsForEachItem(leaveList, gen, nodePtr) {
122      st_insert(tableOfLeaves, (char *) nodePtr, (char *) (long) (-1));
123    }
124  } /* End of if-then-else */
125 
126  /* Obtain the list of nodes to obtain the partition from */
127  if (rootList == (lsList)0) {
128    nodeList = Ntk_NetworkReadNodes(network);
129  } /* End of then */ 
130  else {
131    array_t *temporaryRootArray;
132    st_table *resultTable;
133    st_generator *stgen;
134
135    /* Translate the root list to an array */
136    temporaryRootArray = array_alloc(Ntk_Node_t *, lsLength(rootList));
137    i = 0;
138    lsForEachItem(rootList, gen, nodePtr) {
139      array_insert(Ntk_Node_t *, temporaryRootArray, i++, nodePtr);
140    }
141
142    /* Obtain the intermediate nodes */
143    resultTable = Ntk_RegionFindNodes(temporaryRootArray, tableOfLeaves);
144    nodeList = lsCreate();
145    st_foreach_item(resultTable, stgen, (&nodePtr), NULL) {
146      lsNewBegin(nodeList, (lsGeneric)nodePtr, NIL(lsHandle));
147    }
148
149    /* Clean up */
150    st_free_table(resultTable);
151    array_free(temporaryRootArray);
152  } /* End of if-then-else */
153
154  rootArray = array_alloc(Ntk_Node_t *, 0);
155
156  /* Make sure every network node has an mdd Id assigned to it */
157  lsForEachItem(nodeList, gen, nodePtr) {
158
159    /* No need to assign mddIds to the shadow nodes */
160    if (Ntk_NodeTestIsShadow(nodePtr)) {
161      continue;
162    } /* End of if */
163
164    if (!inTermsOfLeaves || st_is_member(tableOfLeaves, (char *) nodePtr)) {
165      if (Ntk_NodeReadMddId(nodePtr) == NTK_UNASSIGNED_MDD_ID) {
166        Ord_NetworkAssignMddIdForNode(network, nodePtr);
167      } /* End of if */
168    } /* End of if */
169  } /* End of lsForEachItem */
170
171  /*
172   * If the result has to be in terms of the combinational inputs, the
173   * mdd array for each vertex will be build all at once by
174   * specifying all the nodes are roots and the combinational inputs
175   * as leaves
176   */
177  if (inTermsOfLeaves) {
178    lsForEachItem(nodeList, gen, nodePtr) {
179
180      /* Skip the shadow nodes */
181      if (Ntk_NodeTestIsShadow(nodePtr)) {
182        continue;
183      }
184
185      /* Insert the node as root */
186      array_insert_last(Ntk_Node_t *, rootArray, nodePtr);
187    } /* End of lsForEachItem */
188   
189    setOfFunctions = Ntm_NetworkBuildMvfs(network, rootArray, 
190                                          tableOfLeaves, careSet);
191  } /* End of then */ 
192  else {
193    /* Compute every mdd array attached to the vertex in terms of its fanin */
194
195    array_t *parameterArray;
196    st_table *tmptableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
197
198    setOfFunctions = array_alloc(Mvf_Function_t *, 0);
199
200    /*
201     * This array will hold one node pointer as the parameter to build
202     * the mdd array for a node. The array rootArray will be used to
203     * create an array of node pointers. Therefore, at the end of this
204     * if-then-else, setOfFunctions will hold the array of mdd arrays
205     * and rootArray will hold the array with all the node pointers
206     * whose mdd array was computed.
207     */
208    parameterArray = array_alloc(Ntk_Node_t *, 1);
209
210    lsForEachItem(nodeList, gen, nodePtr) {
211
212      /* Skip the shadow nodes */
213      if (!Ntk_NodeTestIsShadow(nodePtr)) {
214        Ntk_Node_t *faninPtr;       /* Pointer to fanin node of current node */
215        array_t    *temporaryArray;
216
217        /* Create the array of nodes */
218        array_insert_last(Ntk_Node_t *, rootArray, nodePtr);
219       
220        /* This table is needed empty every beginning of iteration */
221        st_free_table(tmptableOfLeaves);
222        tmptableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
223     
224        /* Prepare parameters to build the mdd array for the node */
225        array_insert(Ntk_Node_t *, parameterArray, 0, nodePtr);
226        Ntk_NodeForEachFanin(nodePtr, i, faninPtr) {
227          st_insert(tmptableOfLeaves, (char *)faninPtr, (char *)(-1));
228        }
229
230        /*
231         * If the node is a combinational inputs, it has no fanins but the node
232         * must appear in the table of leaves, otherwise the function
233         * Ntm_NetworkBuildMdds aborts. 
234         */
235        if (st_is_member(tableOfLeaves, (char *) nodePtr)) {
236          st_insert(tmptableOfLeaves, (char *)nodePtr, (char *)(-1));
237        } /* End of if */
238       
239        temporaryArray = Ntm_NetworkBuildMvfs(network, parameterArray, 
240                                              tmptableOfLeaves, careSet);
241        array_insert_last(Mvf_Function_t *, setOfFunctions, 
242                          array_fetch(Mvf_Function_t *, temporaryArray, 0));
243       
244        array_free(temporaryArray);
245      } /* End of if */
246    } /* End of lsForEachItem */
247   
248    array_free(parameterArray);
249    st_free_table(tmptableOfLeaves);
250  } /* End of if-then-else */
251
252  /* Partial Clean up */
253  st_free_table(tableOfLeaves);
254
255  assert(array_n(rootArray) == array_n(setOfFunctions));
256 
257  /*
258   * The computation now uses two steps, the first one creates all the
259   * vertices of the partition and the second one all the edges of the
260   * partition.
261   */
262
263  /* Create vertices */
264  arrayForEachItem(Ntk_Node_t *, rootArray, i, nodePtr) {
265    Mvf_Function_t *mvf  = array_fetch(Mvf_Function_t *, setOfFunctions, i);
266    char           *name = Ntk_NodeReadName(nodePtr);
267    int            mddId = Ntk_NodeReadMddId(nodePtr);
268
269    toVertex = g_add_vertex(partition);
270
271    /* Update the look-up tables in the partition */
272    st_insert(PartPartitionReadNameToVertex(partition),
273              name, (char *)toVertex);
274    st_insert(PartPartitionReadMddIdToVertex(partition),
275              (char *)(long) mddId, (char *)toVertex);
276
277    /* Create the information attached to the vertex */
278    toVertex->user_data = (gGeneric)PartVertexInfoCreateSingle(name, 
279                                                               mvf,
280                                                               mddId);
281  } /* End of arrayForEachItem */
282
283  /* Create the edges */
284  foreach_vertex(partition, gen, toVertex) {
285    nodePtr = Ntk_NetworkFindNodeByActualName(network, PartVertexReadName(toVertex));
286    if(!Ntk_NodeTestIsCombInput(nodePtr)) {
287      PartPartitionCreateVertexFaninEdges(partition, toVertex);
288    }
289  } /* End of foreach_vertex */
290
291  /* Clean up */
292  array_free(rootArray);
293  array_free(setOfFunctions);
294  if (rootList != (lsList)0) {
295    lsDestroy(nodeList, (void (*)(lsGeneric))0);
296  }
297} /* End of PartPartitionTotal */
298
299/*---------------------------------------------------------------------------*/
300/* Definition of static functions                                            */
301/*---------------------------------------------------------------------------*/
302
Note: See TracBrowser for help on using the repository browser.