source: vis_dev/glu-2.3/src/calBdd/calApplyReduce.c @ 26

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

library glu 2.3
File size: 9.0 KB
RevLine 
[13]1/**CFile***********************************************************************
2
3  FileName    [calApplyReduce.c]
4
5  PackageName [cal]
6
7  Synopsis    [Generic routines for processing temporary nodes during
8  "apply" and "reduce" phases.]
9
10  Description []
11
12  SeeAlso     [optional]
13
14  Author      [Jagesh Sanghavi (sanghavi@eecs.berkeley.edu)
15               Rajeev Ranjan   (rajeev@eecs.berkeley.edu)
16               ]
17  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
18  All rights reserved.
19
20  Permission is hereby granted, without written agreement and without license
21  or royalty fees, to use, copy, modify, and distribute this software and its
22  documentation for any purpose, provided that the above copyright notice and
23  the following two paragraphs appear in all copies of this software.
24
25  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
26  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
27  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
28  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
31  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
32  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
33  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
34  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
35
36  Revision    [$Id: calApplyReduce.c,v 1.1.1.3 1998/05/04 00:58:49 hsv Exp $]
37
38******************************************************************************/
39
40#include "calInt.h"
41
42/*---------------------------------------------------------------------------*/
43/* Constant declarations                                                     */
44/*---------------------------------------------------------------------------*/
45
46/*---------------------------------------------------------------------------*/
47/* Type declarations                                                         */
48/*---------------------------------------------------------------------------*/
49
50/*---------------------------------------------------------------------------*/
51/* Stucture declarations                                                     */
52/*---------------------------------------------------------------------------*/
53
54
55/*---------------------------------------------------------------------------*/
56/* Variable declarations                                                     */
57/*---------------------------------------------------------------------------*/
58
59/*---------------------------------------------------------------------------*/
60/* Macro declarations                                                        */
61/*---------------------------------------------------------------------------*/
62
63/**AutomaticStart*************************************************************/
64
65/*---------------------------------------------------------------------------*/
66/* Static function prototypes                                                */
67/*---------------------------------------------------------------------------*/
68
69
70/**AutomaticEnd***************************************************************/
71
72/*---------------------------------------------------------------------------*/
73/* Definition of exported functions                                          */
74/*---------------------------------------------------------------------------*/
75
76/*---------------------------------------------------------------------------*/
77/* Definition of internal functions                                          */
78/*---------------------------------------------------------------------------*/
79/**Function********************************************************************
80
81  Synopsis    [required]
82
83  Description [optional]
84
85  SideEffects [required]
86
87  SeeAlso     [optional]
88
89******************************************************************************/
90void
91CalHashTableApply(Cal_BddManager_t * bddManager, CalHashTable_t *
92                  hashTable, CalHashTable_t ** reqQueAtPipeDepth, CalOpProc_t
93                  calOpProc) 
94{
95  int i, numBins;
96  CalBddNode_t **bins = 0;
97  CalRequestNode_t *requestNode;
98  Cal_Bdd_t fx, gx, fxbar, gxbar, result;
99  Cal_BddId_t bddId;
100
101  numBins = hashTable->numBins;
102  bins = hashTable->bins;
103  for(i = 0; i < numBins; i++){
104    for(requestNode = bins[i];
105        requestNode != Cal_Nil(CalRequestNode_t);
106        requestNode = CalRequestNodeGetNextRequestNode(requestNode)){
107      /* Process the requestNode */
108      CalRequestNodeGetCofactors(bddManager, requestNode, fx, fxbar, gx, gxbar);
109      Cal_Assert(((CalAddress_t)(fx.bddNode)) & ~0xf);
110      Cal_Assert(((CalAddress_t)(gx.bddNode)) & ~0xf);
111      Cal_Assert(((CalAddress_t)(fxbar.bddNode)) & ~0xf);
112      Cal_Assert(((CalAddress_t)(gxbar.bddNode)) & ~0xf);
113      if((*calOpProc)(bddManager, fx, gx, &result) == 0){
114        CalBddNormalize(fx, gx);
115        CalBddGetMinId2(bddManager, fx, gx, bddId);
116        CalHashTableFindOrAdd(reqQueAtPipeDepth[bddId], fx, gx, &result);
117      }
118      CalBddIcrRefCount(result);
119      CalRequestNodePutThenRequest(requestNode, result);
120      if((*calOpProc)(bddManager, fxbar, gxbar, &result) == 0){
121        CalBddNormalize(fxbar, gxbar);
122        CalBddGetMinId2(bddManager, fxbar, gxbar, bddId);
123        CalHashTableFindOrAdd(reqQueAtPipeDepth[bddId], fxbar, gxbar, &result);
124      }
125      CalBddIcrRefCount(result);
126      CalRequestNodePutElseRequest(requestNode, result);
127    }
128  }
129}
130
131/**Function********************************************************************
132
133  Synopsis    [required]
134
135  Description [optional]
136
137  SideEffects [required]
138
139  SeeAlso     [optional]
140
141******************************************************************************/
142void
143CalHashTableReduce(Cal_BddManager_t * bddManager,
144                   CalHashTable_t * hashTable,
145                   CalHashTable_t * uniqueTableForId)
146{
147  int i, numBins = hashTable->numBins;
148  CalBddNode_t **bins = hashTable->bins;
149  Cal_BddId_t currentBddId = uniqueTableForId->bddId;
150  CalNodeManager_t *nodeManager = uniqueTableForId->nodeManager;
151  CalRequestNode_t *requestNode, *next;
152  CalBddNode_t *bddNode, *endNode;
153  Cal_Bdd_t thenBdd, elseBdd, result;
154  Cal_BddRefCount_t refCount;
155
156  endNode = hashTable->endNode;
157  for(i = 0; i < numBins; i++){
158    for(requestNode = bins[i];
159        requestNode != Cal_Nil(CalRequestNode_t);
160        requestNode = next){
161      next = CalRequestNodeGetNextRequestNode(requestNode);
162      /* Process the requestNode */
163      CalRequestNodeGetThenRequest(requestNode, thenBdd);
164      CalRequestNodeGetElseRequest(requestNode, elseBdd);
165      CalRequestIsForwardedTo(thenBdd);
166      CalRequestIsForwardedTo(elseBdd);
167      if(CalBddIsEqual(thenBdd, elseBdd)){
168        CalRequestNodeGetRefCount(requestNode, refCount);
169        CalRequestAddRefCount(thenBdd, refCount - 2);
170        CalRequestNodePutThenRequest(requestNode, thenBdd);
171        CalRequestNodePutElseRequestNode(requestNode, FORWARD_FLAG);
172        endNode->nextBddNode = requestNode;
173        endNode = requestNode;
174      }
175      else
176        if(CalUniqueTableForIdLookup(bddManager, uniqueTableForId,
177          thenBdd, elseBdd, &result) == 1){
178        CalBddDcrRefCount(thenBdd);
179        CalBddDcrRefCount(elseBdd);
180        CalRequestNodeGetRefCount(requestNode, refCount);
181        CalBddAddRefCount(result, refCount);
182        CalRequestNodePutThenRequest(requestNode, result);
183        CalRequestNodePutElseRequestNode(requestNode, FORWARD_FLAG);
184        endNode->nextBddNode = requestNode;
185        endNode = requestNode;
186      }
187      else if(CalBddIsOutPos(thenBdd)){
188        CalRequestNodePutThenRequest(requestNode, thenBdd);
189        CalRequestNodePutElseRequest(requestNode, elseBdd);
190        CalHashTableAddDirect(uniqueTableForId, requestNode);
191        bddManager->numNodes++;
192        bddManager->gcCheck--;
193      }
194      else{
195        CalNodeManagerAllocNode(nodeManager, bddNode);
196        CalBddNodePutThenBddId(bddNode, CalBddGetBddId(thenBdd));
197        CalBddNodePutThenBddNode(bddNode, CalBddGetBddNodeNot(thenBdd));
198        CalBddNodePutElseBddId(bddNode, CalBddGetBddId(elseBdd));
199        CalBddNodePutElseBddNode(bddNode, CalBddGetBddNodeNot(elseBdd));
200        CalRequestNodeGetRefCount(requestNode, refCount);
201        CalBddNodePutRefCount(bddNode, refCount);
202        CalHashTableAddDirect(uniqueTableForId, bddNode);
203        bddManager->numNodes++;
204        bddManager->gcCheck--;
205        CalRequestNodePutThenRequestId(requestNode, currentBddId);
206        CalRequestNodePutThenRequestNode(requestNode, CalBddNodeNot(bddNode));
207        CalRequestNodePutElseRequestNode(requestNode, FORWARD_FLAG);
208        endNode->nextBddNode = requestNode;
209        endNode = requestNode;
210      }
211    }
212  }
213  memset((char *)bins, 0, hashTable->numBins * sizeof(CalBddNode_t *));
214  hashTable->endNode = endNode;
215}
216/*---------------------------------------------------------------------------*/
217/* Definition of static functions                                            */
218/*---------------------------------------------------------------------------*/
219
220
221 
222
223
224
Note: See TracBrowser for help on using the repository browser.