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

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

library glu 2.3
File size: 9.0 KB
Line 
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.