src/calBdd/calCacheTableTwo.c File Reference

#include "calInt.h"
Include dependency graph for calCacheTableTwo.c:

Go to the source code of this file.

Data Structures

struct  CalCacheTableStruct
struct  CacheEntryStruct

Defines

#define CACHE_TABLE_DEFAULT_SIZE_INDEX   16
#define CACHE_TABLE_DEFAULT_CACHE_RATIO   4
#define CacheTableTwoDoHash(table, operand1, operand2, opCode)   ((((((CalAddress_t)(operand1)) + ((CalAddress_t)(operand2))) / NODE_SIZE) + opCode + ((CalAddress_t)operand1 & 0x1)+ ((CalAddress_t)operand2 & 0x1)) %((table)->numBins))
#define CacheTableTwoCompareCacheEntry(entry, _operand1, _operand2, _opCode)
#define CacheResultNodeIsForwardedTo(resultBddNode, resultBddId)

Typedefs

typedef struct CacheEntryStruct CacheEntry_t

Functions

static void CacheTableTwoRehash (CalCacheTable_t *cacheTable, int grow)
static void CacheTablePrint (CalCacheTable_t *cacheTable)
CalCacheTable_t * CalCacheTableTwoInit (Cal_BddManager_t *bddManager)
int CalCacheTableTwoQuit (CalCacheTable_t *cacheTable)
void CalCacheTableTwoInsert (Cal_BddManager_t *bddManager, Cal_Bdd_t f, Cal_Bdd_t g, Cal_Bdd_t result, unsigned long opCode, int cacheLevel)
int CalCacheTableTwoLookup (Cal_BddManager_t *bddManager, Cal_Bdd_t f, Cal_Bdd_t g, unsigned long opCode, Cal_Bdd_t *resultBddPtr)
void CalCacheTableTwoFlush (CalCacheTable_t *cacheTable)
int CalCacheTableTwoFlushAll (CalCacheTable_t *cacheTable)
void CalCacheTableTwoGCFlush (CalCacheTable_t *cacheTable)
void CalCacheTableTwoRepackUpdate (CalCacheTable_t *cacheTable)
void CalCheckCacheTableValidity (Cal_BddManager bddManager)
void CalCacheTableTwoFixResultPointers (Cal_BddManager_t *bddManager)
void CalCacheTablePrint (Cal_BddManager_t *bddManager)
void CalBddManagerGetCacheTableData (Cal_BddManager_t *bddManager, unsigned long *cacheSize, unsigned long *cacheEntries, unsigned long *cacheInsertions, unsigned long *cacheLookups, unsigned long *cacheHits, unsigned long *cacheCollisions)
void CalCacheTableRehash (Cal_BddManager_t *bddManager)
void CalCacheTableTwoFlushAssociationId (Cal_BddManager_t *bddManager, int associationId)
unsigned long CalCacheTableMemoryConsumption (CalCacheTable_t *cacheTable)

Define Documentation

#define CACHE_TABLE_DEFAULT_CACHE_RATIO   4

Definition at line 46 of file calCacheTableTwo.c.

#define CACHE_TABLE_DEFAULT_SIZE_INDEX   16

CFile***********************************************************************

FileName [calCacheTableTwo.c]

PackageName [cal]

Synopsis [Functions to manage the Cache tables.] Description [ ]

SeeAlso [optional]

Author [ Rajeev K. Ranjan (rajeev@eecs.berkeley.edu) Jagesh Sanghavi (sanghavi@eecs.berkeley.edu) ] Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. All rights reserved.

Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

Revision [

Id
calCacheTableTwo.c,v 1.4 1998/09/15 19:02:52 ravi Exp

]

Definition at line 45 of file calCacheTableTwo.c.

#define CacheResultNodeIsForwardedTo ( resultBddNode,
resultBddId   ) 
Value:
{ \
  CalBddNode_t *__resultBddNode;\
  __resultBddNode = CAL_BDD_POINTER(resultBddNode); \
  if(CalRequestNodeGetElseRequestNode(__resultBddNode) == FORWARD_FLAG){ \
    resultBddId = __resultBddNode->thenBddId; \
    resultBddNode = (CalBddNode_t*) \
                    (((CalAddress_t)(__resultBddNode->thenBddNode) & ~0xe)        \
                         ^(CAL_TAG0(resultBddNode))); \
  } \
}

Definition at line 104 of file calCacheTableTwo.c.

#define CacheTableTwoCompareCacheEntry ( entry,
_operand1,
_operand2,
_opCode   ) 
Value:
((((CalBddNode_t *)(((CalAddress_t)((entry)->operand1)) & ~0x2)) == (_operand1))\
 &&                                                             \
 ((entry)->operand2 == (_operand2))\
 &&                                                             \
 ((entry)->opCode == _opCode))

Definition at line 97 of file calCacheTableTwo.c.

#define CacheTableTwoDoHash ( table,
operand1,
operand2,
opCode   )     ((((((CalAddress_t)(operand1)) + ((CalAddress_t)(operand2))) / NODE_SIZE) + opCode + ((CalAddress_t)operand1 & 0x1)+ ((CalAddress_t)operand2 & 0x1)) %((table)->numBins))

Definition at line 88 of file calCacheTableTwo.c.

Typedef Documentation

typedef struct CacheEntryStruct CacheEntry_t

Definition at line 51 of file calCacheTableTwo.c.

Function Documentation

static void CacheTablePrint ( CalCacheTable_t *  cacheTable  )  [static]

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 663 of file calCacheTableTwo.c.

00664 {
00665   int i;
00666   unsigned long opCode;
00667   CacheEntry_t *bin;
00668   
00669   printf("cacheTable entries(%ld) bins(%ld)\n",
00670          cacheTable->numEntries, cacheTable->numBins);
00671   for(i = 0; i < cacheTable->numBins; i++){
00672     bin = cacheTable->bins+i;
00673     opCode = bin->opCode;
00674     if (opCode != CAL_OP_INVALID){
00675       fprintf(stdout,"Op = %s O1 = %lx, O2 = %lx RId = %d, RNode = %lx\n",
00676               ((opCode == CAL_OP_OR) ? "OR" : ((opCode == CAL_OP_AND) ? "AND" :
00677                                                ((opCode ==
00678                                                             CAL_OP_QUANT) ?
00679                                                            "QUANT" :
00680                                                            ((opCode ==
00681                                                              CAL_OP_REL_PROD)   
00682                                                             ?
00683                                                             "RELPROD"
00684                                                             :
00685                                                             "Nothing")))), 
00686               (CalAddress_t)bin->operand1,
00687               (CalAddress_t)bin->operand2, bin->resultBddId, 
00688               (CalAddress_t)bin->resultBddNode);
00689     }
00690   }
00691 }

static void CacheTableTwoRehash ( CalCacheTable_t *  cacheTable,
int  grow 
) [static]

AutomaticStart

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 604 of file calCacheTableTwo.c.

00605 {
00606   CacheEntry_t *oldBins = cacheTable->bins;
00607   int i, hashValue;
00608   int oldNumBins = cacheTable->numBins;
00609   CacheEntry_t *bin, *newBin;
00610   
00611   
00612   if(grow){
00613     cacheTable->sizeIndex++;
00614   }
00615   else{
00616     if (cacheTable->sizeIndex <= CACHE_TABLE_DEFAULT_SIZE_INDEX){/* No need to Rehash */
00617       return;
00618     }
00619     cacheTable->sizeIndex--;
00620   }
00621 
00622   cacheTable->numBins = TABLE_SIZE(cacheTable->sizeIndex);
00623   cacheTable->bins = Cal_MemAlloc(CacheEntry_t, cacheTable->numBins);
00624   if(cacheTable->bins == Cal_Nil(CacheEntry_t)){
00625     CalBddFatalMessage("out of memory");
00626   }
00627   
00628   memset((char *)cacheTable->bins, 0, 
00629          cacheTable->numBins*sizeof(CacheEntry_t));
00630 
00631   for(i = 0; i < oldNumBins; i++){
00632       bin  = oldBins+i;
00633       if (bin->opCode == CAL_OP_INVALID) continue;
00634       hashValue = CacheTableTwoDoHash(cacheTable,
00635                                       bin->operand1,
00636                                       bin->operand2,
00637                                       bin->opCode);
00638       newBin = cacheTable->bins+hashValue;
00639       if (newBin->opCode != CAL_OP_INVALID){
00640         cacheTable->numEntries--;
00641       }
00642       newBin->opCode = bin->opCode;
00643       newBin->operand1 = bin->operand1;
00644       newBin->operand2 = bin->operand2;
00645       newBin->resultBddId = bin->resultBddId;
00646       newBin->resultBddNode = bin->resultBddNode;
00647   }
00648   Cal_MemFree(oldBins);
00649 }

void CalBddManagerGetCacheTableData ( Cal_BddManager_t *  bddManager,
unsigned long *  cacheSize,
unsigned long *  cacheEntries,
unsigned long *  cacheInsertions,
unsigned long *  cacheLookups,
unsigned long *  cacheHits,
unsigned long *  cacheCollisions 
)

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 500 of file calCacheTableTwo.c.

00507 {
00508   CalCacheTable_t *cacheTable = bddManager->cacheTable;
00509   *cacheSize += cacheTable->numBins;
00510   *cacheEntries += cacheTable->numEntries;
00511   *cacheInsertions += cacheTable->numInsertions;
00512   *cacheLookups += cacheTable->numLookups;
00513   *cacheHits += cacheTable->numHits;
00514   *cacheCollisions += cacheTable->numCollisions;
00515 }

unsigned long CalCacheTableMemoryConsumption ( CalCacheTable_t *  cacheTable  ) 

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 582 of file calCacheTableTwo.c.

00583 {
00584   return (unsigned long) (sizeof(cacheTable)+cacheTable->numBins*sizeof(CacheEntry_t));
00585 }

void CalCacheTablePrint ( Cal_BddManager_t *  bddManager  ) 

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 483 of file calCacheTableTwo.c.

00484 {
00485   CacheTablePrint(bddManager->cacheTable);
00486 }

void CalCacheTableRehash ( Cal_BddManager_t *  bddManager  ) 

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 529 of file calCacheTableTwo.c.

00530 {
00531   CalCacheTable_t *cacheTable = bddManager->cacheTable;
00532   if((3*cacheTable->numBins < cacheTable->cacheRatio*cacheTable->numEntries) &&
00533      (32*cacheTable->numBins <
00534       8*(bddManager->numNodes))){
00535     CacheTableTwoRehash(cacheTable, 1);
00536   }
00537 }

void CalCacheTableTwoFixResultPointers ( Cal_BddManager_t *  bddManager  ) 

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 452 of file calCacheTableTwo.c.

00453 {
00454   CalCacheTable_t *cacheTable = bddManager->cacheTable;
00455   int i;
00456   CacheEntry_t *bin = cacheTable->bins;
00457   int numBins = cacheTable->numBins;
00458   
00459   for (i=0; i<numBins; bin++,i++){
00460     if ((CalAddress_t)bin->operand1 & 0x2){ /* If the result node is temporary
00461                                    node */
00462       CacheResultNodeIsForwardedTo(bin->resultBddNode, bin->resultBddId);
00463       bin->operand1 = (CalBddNode_t *)((CalAddress_t)bin->operand1 &
00464                                        ~0x2); /* It is no longer temporary */
00465     }
00466   }
00467 }

void CalCacheTableTwoFlush ( CalCacheTable_t *  cacheTable  ) 

Function********************************************************************

Synopsis [Free a Cache table along with the associated storage.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 317 of file calCacheTableTwo.c.

00318 {
00319   memset((char *)cacheTable->bins, 0,
00320          cacheTable->numBins*sizeof(CacheEntry_t));
00321   cacheTable->numEntries = 0;
00322 }

int CalCacheTableTwoFlushAll ( CalCacheTable_t *  cacheTable  ) 

Function********************************************************************

Synopsis [Free a Cache table along with the associated storage.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 336 of file calCacheTableTwo.c.

00337 {
00338   CalCacheTableTwoFlush(cacheTable);
00339   cacheTable->numInsertions = 0;
00340   cacheTable->numCollisions = 0;
00341   cacheTable->numLookups = 0;
00342   cacheTable->numHits = 0;
00343   return 0;
00344 }

void CalCacheTableTwoFlushAssociationId ( Cal_BddManager_t *  bddManager,
int  associationId 
)

Function********************************************************************

Synopsis [Flushes the entries from the cache which correspond to the given associationId.]

Description []

SideEffects [Cache entries are affected.]

SeeAlso []

Definition at line 551 of file calCacheTableTwo.c.

00553 {
00554   CalCacheTable_t *cacheTable =   bddManager->cacheTable;
00555   int i;
00556   CacheEntry_t *bin;
00557   
00558   for (i=0; i < cacheTable->numBins; i++){
00559     bin = cacheTable->bins+i;
00560     if ((bin->opCode == (CAL_OP_QUANT+associationId)) ||
00561         (bin->opCode == (CAL_OP_REL_PROD+associationId)) ||
00562         (bin->opCode == (CAL_OP_VAR_SUBSTITUTE+associationId))){
00563       /* This entry needs to be freed */
00564       cacheTable->numEntries--;
00565       memset((char *)bin, 0, sizeof(CacheEntry_t));
00566     }
00567   }
00568 }

void CalCacheTableTwoGCFlush ( CalCacheTable_t *  cacheTable  ) 

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 357 of file calCacheTableTwo.c.

00358 {
00359   int i;
00360   CacheEntry_t *bin = cacheTable->bins;
00361   int numBins = cacheTable->numBins;
00362   if (cacheTable->numEntries == 0) return;
00363   for (i=0; i<numBins; bin++,i++){
00364     if (bin->opCode != CAL_OP_INVALID){
00365       if (CalBddNodeIsMarked((CAL_BDD_POINTER(bin->operand1))) ||
00366           CalBddNodeIsMarked((CAL_BDD_POINTER(bin->operand2))) ||
00367           CalBddNodeIsMarked((CAL_BDD_POINTER(bin->resultBddNode)))){
00368         /* This entry needs to be freed */
00369         cacheTable->numEntries--;
00370         memset((char *)bin, 0, sizeof(CacheEntry_t));
00371       }
00372     }
00373   }
00374 }

CalCacheTable_t* CalCacheTableTwoInit ( Cal_BddManager_t *  bddManager  ) 

AutomaticEnd Function********************************************************************

Synopsis [Initialize a Cache table using default parameters.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 148 of file calCacheTableTwo.c.

00149 {
00150   CalCacheTable_t  *cacheTable;
00151   cacheTable = Cal_MemAlloc(CalCacheTable_t, 1);
00152   if (cacheTable == Cal_Nil(CalCacheTable_t)){
00153     CalBddFatalMessage("out of memory");
00154   }
00155   cacheTable->sizeIndex = CACHE_TABLE_DEFAULT_SIZE_INDEX;
00156   cacheTable->numBins = TABLE_SIZE(cacheTable->sizeIndex);
00157   cacheTable->cacheRatio = CACHE_TABLE_DEFAULT_CACHE_RATIO;
00158   cacheTable->bins = Cal_MemAlloc(CacheEntry_t, cacheTable->numBins);
00159   if(cacheTable->bins == Cal_Nil(CacheEntry_t)){
00160     CalBddFatalMessage("out of memory");
00161   }             
00162   memset((char *)cacheTable->bins, 0,
00163          cacheTable->numBins*sizeof(CacheEntry_t));
00164   cacheTable->numInsertions = 0;
00165   cacheTable->numEntries = 0;
00166   cacheTable->numHits = 0;
00167   cacheTable->numLookups = 0;
00168   cacheTable->numCollisions = 0;
00169   return cacheTable;
00170 }

void CalCacheTableTwoInsert ( Cal_BddManager_t *  bddManager,
Cal_Bdd_t  f,
Cal_Bdd_t  g,
Cal_Bdd_t  result,
unsigned long  opCode,
int  cacheLevel 
)

Function********************************************************************

Synopsis [Directly insert a BDD node in the Cache table.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 206 of file calCacheTableTwo.c.

00209 {
00210   int hashValue;
00211   CalCacheTable_t *cacheTable;
00212   CacheEntry_t *bin;
00213   CalBddNode_t *operand1Node, *operand2Node;
00214 
00215   cacheTable = bddManager->cacheTable;
00216   cacheTable->numInsertions++;
00217   hashValue = CacheTableTwoDoHash(cacheTable, CalBddGetBddNode(f),
00218                                   CalBddGetBddNode(g), opCode); 
00219 
00220   bin = cacheTable->bins + hashValue;
00221   if (bin->opCode != CAL_OP_INVALID){
00222     cacheTable->numCollisions++;
00223   }
00224   else{
00225     cacheTable->numEntries++;
00226   }
00227   
00228   bin->opCode = opCode;
00229   if ((CalAddress_t)CalBddGetBddNode(f) >
00230       (CalAddress_t)CalBddGetBddNode(g)){ 
00231     operand1Node = CalBddGetBddNode(g);
00232     operand2Node = CalBddGetBddNode(f);
00233   }
00234   else{
00235     operand1Node = CalBddGetBddNode(f);
00236     operand2Node = CalBddGetBddNode(g);
00237   }
00238   
00239   if (cacheLevel){
00240   /*
00241    * Mark this result as temporary node to be forwarded at the end of
00242    * operation. The reason we can use this tagging is because the
00243    * size of the structure is 16 bytes and we are requiring 8 or 16 byte
00244    * alignment (at least last 3 bits should be zero).
00245    */
00246     bin->operand1 = (CalBddNode_t *) (((CalAddress_t)operand1Node) | 0x2);
00247   }
00248   else {
00249     bin->operand1 = operand1Node;
00250   }
00251   bin->operand2 = operand2Node;
00252   bin->resultBddNode = CalBddGetBddNode(result);
00253   bin->resultBddId = CalBddGetBddId(result);
00254   return;
00255 }

int CalCacheTableTwoLookup ( Cal_BddManager_t *  bddManager,
Cal_Bdd_t  f,
Cal_Bdd_t  g,
unsigned long  opCode,
Cal_Bdd_t *  resultBddPtr 
)

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 270 of file calCacheTableTwo.c.

00273 {
00274   int hashValue;
00275   CalCacheTable_t *cacheTable;
00276   CacheEntry_t *bin;
00277   CalBddNode_t *operand1Node, *operand2Node;
00278   
00279   cacheTable = bddManager->cacheTable;
00280   cacheTable->numLookups++;
00281   hashValue = CacheTableTwoDoHash(cacheTable, CalBddGetBddNode(f),
00282                                   CalBddGetBddNode(g), opCode); 
00283 
00284   bin = cacheTable->bins+hashValue;
00285   
00286   if ((CalAddress_t)CalBddGetBddNode(f) > (CalAddress_t)CalBddGetBddNode(g)){
00287     operand1Node = CalBddGetBddNode(g);
00288     operand2Node = CalBddGetBddNode(f);
00289   }
00290   else{
00291     operand1Node = CalBddGetBddNode(f);
00292     operand2Node = CalBddGetBddNode(g);
00293   }
00294   if (CacheTableTwoCompareCacheEntry(bin, operand1Node, operand2Node,
00295                                      opCode)){
00296     CalBddPutBddId((*resultBddPtr), bin->resultBddId);
00297     CalBddPutBddNode((*resultBddPtr), bin->resultBddNode);
00298     cacheTable->numHits++;
00299     return 1;
00300   }
00301   *resultBddPtr = bddManager->bddNull;
00302   return 0;
00303 }

int CalCacheTableTwoQuit ( CalCacheTable_t *  cacheTable  ) 

Function********************************************************************

Synopsis [Free a Cache table along with the associated storage.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 185 of file calCacheTableTwo.c.

00186 {
00187   if(cacheTable == Cal_Nil(CalCacheTable_t))return 1;
00188   Cal_MemFree(cacheTable->bins);
00189   Cal_MemFree(cacheTable);
00190   return 0;
00191 }

void CalCacheTableTwoRepackUpdate ( CalCacheTable_t *  cacheTable  ) 

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 388 of file calCacheTableTwo.c.

00389 {
00390   int i;
00391   CacheEntry_t *bin = cacheTable->bins;
00392   int numBins = cacheTable->numBins;
00393   
00394   for (i=0; i<numBins; bin++,i++){
00395     if (bin->opCode != CAL_OP_INVALID){
00396       if (CalBddNodeIsForwarded(CAL_BDD_POINTER(bin->operand1))){
00397         CalBddNodeForward(bin->operand1);
00398       }
00399       if (CalBddNodeIsForwarded(CAL_BDD_POINTER(bin->operand2))){
00400         CalBddNodeForward(bin->operand2);
00401       }
00402       if (CalBddNodeIsForwarded(CAL_BDD_POINTER(bin->resultBddNode))){
00403         CalBddNodeForward(bin->resultBddNode);
00404       }
00405     }
00406   }
00407 }

void CalCheckCacheTableValidity ( Cal_BddManager  bddManager  ) 

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 421 of file calCacheTableTwo.c.

00422 {
00423   CalCacheTable_t *cacheTable = bddManager->cacheTable;
00424   int i;
00425   CacheEntry_t *bin = cacheTable->bins;
00426   int numBins = cacheTable->numBins;
00427   
00428   for (i=0; i<numBins; bin++,i++){
00429     if (bin->opCode != CAL_OP_INVALID){
00430       Cal_Assert(CalBddNodeIsForwarded(CAL_BDD_POINTER(bin->operand1))
00431                  == 0);
00432       Cal_Assert(CalBddNodeIsForwarded(CAL_BDD_POINTER(bin->operand2))
00433                  == 0);
00434       Cal_Assert(CalBddNodeIsForwarded(CAL_BDD_POINTER(bin->resultBddNode))
00435                  == 0);
00436     }
00437   }
00438 }

Generated on Tue Jan 12 13:57:11 2010 for glu-2.2 by  doxygen 1.6.1