[6] | 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 | ******************************************************************************/ |
---|
| 90 | void |
---|
| 91 | CalHashTableApply(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 | ******************************************************************************/ |
---|
| 142 | void |
---|
| 143 | CalHashTableReduce(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 | |
---|