src/aig/ivy/ivyTable.c File Reference

#include "ivy.h"
Include dependency graph for ivyTable.c:

Go to the source code of this file.

Functions

static unsigned Ivy_Hash (Ivy_Obj_t *pObj, int TableSize)
static int * Ivy_TableFind (Ivy_Man_t *p, Ivy_Obj_t *pObj)
static void Ivy_TableResize (Ivy_Man_t *p)
static unsigned int Cudd_PrimeAig (unsigned int p)
Ivy_Obj_t * Ivy_TableLookup (Ivy_Man_t *p, Ivy_Obj_t *pObj)
void Ivy_TableInsert (Ivy_Man_t *p, Ivy_Obj_t *pObj)
void Ivy_TableDelete (Ivy_Man_t *p, Ivy_Obj_t *pObj)
void Ivy_TableUpdate (Ivy_Man_t *p, Ivy_Obj_t *pObj, int ObjIdNew)
int Ivy_TableCountEntries (Ivy_Man_t *p)
void Ivy_TableProfile (Ivy_Man_t *p)

Function Documentation

unsigned int Cudd_PrimeAig ( unsigned int  p  )  [static]

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

Synopsis [Returns the next prime >= p.]

Description [Copied from CUDD, for stand-aloneness.]

SideEffects [None]

SeeAlso []

Definition at line 272 of file ivyTable.c.

00273 {
00274     int i,pn;
00275 
00276     p--;
00277     do {
00278         p++;
00279         if (p&1) {
00280             pn = 1;
00281             i = 3;
00282             while ((unsigned) (i * i) <= p) {
00283                 if (p % i == 0) {
00284                     pn = 0;
00285                     break;
00286                 }
00287                 i += 2;
00288             }
00289         } else {
00290             pn = 0;
00291         }
00292     } while (!pn);
00293     return(p);
00294 
00295 } /* end of Cudd_Prime */

static unsigned Ivy_Hash ( Ivy_Obj_t *  pObj,
int  TableSize 
) [static]

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

FileName [ivyTable.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [And-Inverter Graph package.]

Synopsis [Structural hashing table.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - May 11, 2006. ]

Revision [

Id
ivyTable.c,v 1.00 2006/05/11 00:00:00 alanmi Exp

] DECLARATIONS ///

Definition at line 28 of file ivyTable.c.

00029 {
00030     unsigned Key = Ivy_ObjIsExor(pObj) * 1699;
00031     Key ^= Ivy_ObjFaninId0(pObj) * 7937;
00032     Key ^= Ivy_ObjFaninId1(pObj) * 2971;
00033     Key ^= Ivy_ObjFaninC0(pObj) * 911;
00034     Key ^= Ivy_ObjFaninC1(pObj) * 353;
00035     Key ^= Ivy_ObjInit(pObj) * 911;
00036     return Key % TableSize;
00037 }

int Ivy_TableCountEntries ( Ivy_Man_t *  p  ) 

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

Synopsis [Count the number of nodes in the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 184 of file ivyTable.c.

00185 {
00186     int i, Counter = 0;
00187     for ( i = 0; i < p->nTableSize; i++ )
00188         Counter += (p->pTable[i] != 0);
00189     return Counter;
00190 }

void Ivy_TableDelete ( Ivy_Man_t *  p,
Ivy_Obj_t *  pObj 
)

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

Synopsis [Deletes the node from the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 129 of file ivyTable.c.

00130 {
00131     Ivy_Obj_t * pEntry;
00132     int i, * pPlace;
00133     assert( !Ivy_IsComplement(pObj) );
00134     if ( !Ivy_ObjIsHash(pObj) )
00135         return;
00136     pPlace = Ivy_TableFind( p, pObj );
00137     assert( *pPlace == pObj->Id ); // node should be in the table
00138     *pPlace = 0;
00139     // rehash the adjacent entries
00140     i = pPlace - p->pTable;
00141     for ( i = (i+1) % p->nTableSize; p->pTable[i]; i = (i+1) % p->nTableSize )
00142     {
00143         pEntry = Ivy_ManObj( p, p->pTable[i] );
00144         p->pTable[i] = 0;
00145         Ivy_TableInsert( p, pEntry );
00146     }
00147 }

static int* Ivy_TableFind ( Ivy_Man_t *  p,
Ivy_Obj_t *  pObj 
) [static]

Definition at line 40 of file ivyTable.c.

00041 {
00042     int i;
00043     assert( Ivy_ObjIsHash(pObj) );
00044     for ( i = Ivy_Hash(pObj, p->nTableSize); p->pTable[i]; i = (i+1) % p->nTableSize )
00045         if ( p->pTable[i] == pObj->Id )
00046             break;
00047     return p->pTable + i;
00048 }

void Ivy_TableInsert ( Ivy_Man_t *  p,
Ivy_Obj_t *  pObj 
)

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

Synopsis [Adds the node to the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 102 of file ivyTable.c.

00103 {
00104     int * pPlace;
00105     assert( !Ivy_IsComplement(pObj) );
00106     if ( !Ivy_ObjIsHash(pObj) )
00107         return;
00108     if ( (pObj->Id & 63) == 0 )
00109     {
00110         if ( p->nTableSize < 2 * Ivy_ManHashObjNum(p) )
00111             Ivy_TableResize( p );
00112     }
00113     pPlace = Ivy_TableFind( p, pObj );
00114     assert( *pPlace == 0 );
00115     *pPlace = pObj->Id;
00116 }

Ivy_Obj_t* Ivy_TableLookup ( Ivy_Man_t *  p,
Ivy_Obj_t *  pObj 
)

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Checks if node with the given attributes is in the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 68 of file ivyTable.c.

00069 {
00070     Ivy_Obj_t * pEntry;
00071     int i;
00072     assert( !Ivy_IsComplement(pObj) );
00073     if ( !Ivy_ObjIsHash(pObj) )
00074         return NULL;
00075     assert( Ivy_ObjIsLatch(pObj) || Ivy_ObjFaninId0(pObj) > 0 );
00076     assert( Ivy_ObjFaninId1(pObj) == 0 || Ivy_ObjFaninId0(pObj) < Ivy_ObjFaninId1(pObj) );
00077     if ( Ivy_ObjFanin0(pObj)->nRefs == 0 || (Ivy_ObjChild1(pObj) && Ivy_ObjFanin1(pObj)->nRefs == 0) )
00078         return NULL;
00079     for ( i = Ivy_Hash(pObj, p->nTableSize); p->pTable[i]; i = (i+1) % p->nTableSize )
00080     {
00081         pEntry = Ivy_ManObj( p, p->pTable[i] );
00082         if ( Ivy_ObjChild0(pEntry) == Ivy_ObjChild0(pObj) && 
00083              Ivy_ObjChild1(pEntry) == Ivy_ObjChild1(pObj) && 
00084              Ivy_ObjInit(pEntry) == Ivy_ObjInit(pObj) && 
00085              Ivy_ObjType(pEntry) == Ivy_ObjType(pObj) )
00086             return pEntry;
00087     }
00088     return NULL;
00089 }

void Ivy_TableProfile ( Ivy_Man_t *  p  ) 

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

Synopsis [Profiles the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 246 of file ivyTable.c.

00247 {
00248     int i, Counter = 0;
00249     for ( i = 0; i < p->nTableSize; i++ )
00250     {
00251         if ( p->pTable[i] )
00252             Counter++;
00253         else if ( Counter )
00254         {
00255             printf( "%d ", Counter );
00256             Counter = 0;
00257         }
00258     }
00259 }

void Ivy_TableResize ( Ivy_Man_t *  p  )  [static]

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

Synopsis [Resizes the table.]

Description [Typically this procedure should not be called.]

SideEffects []

SeeAlso []

Definition at line 203 of file ivyTable.c.

00204 {
00205     int * pTableOld, * pPlace;
00206     int nTableSizeOld, Counter, nEntries, e, clk;
00207 clk = clock();
00208     // save the old table
00209     pTableOld = p->pTable;
00210     nTableSizeOld = p->nTableSize;
00211     // get the new table
00212     p->nTableSize = Cudd_PrimeAig( 5 * Ivy_ManHashObjNum(p) ); 
00213     p->pTable = ALLOC( int, p->nTableSize );
00214     memset( p->pTable, 0, sizeof(int) * p->nTableSize );
00215     // rehash the entries from the old table
00216     Counter = 0;
00217     for ( e = 0; e < nTableSizeOld; e++ )
00218     {
00219         if ( pTableOld[e] == 0 )
00220             continue;
00221         Counter++;
00222         // get the place where this entry goes in the table table
00223         pPlace = Ivy_TableFind( p, Ivy_ManObj(p, pTableOld[e]) );
00224         assert( *pPlace == 0 ); // should not be in the table
00225         *pPlace = pTableOld[e];
00226     }
00227     nEntries = Ivy_ManHashObjNum(p);
00228 //    assert( Counter == nEntries );
00229 //    printf( "Increasing the structural table size from %6d to %6d. ", nTableSizeOld, p->nTableSize );
00230 //    PRT( "Time", clock() - clk );
00231     // replace the table and the parameters
00232     free( pTableOld );
00233 }

void Ivy_TableUpdate ( Ivy_Man_t *  p,
Ivy_Obj_t *  pObj,
int  ObjIdNew 
)

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

Synopsis [Updates the table to point to the new node.]

Description [If the old node (pObj) is in the table, updates the table to point to an object with different ID (ObjIdNew). The table should not contain an object with ObjIdNew (this is currently not checked).]

SideEffects []

SeeAlso []

Definition at line 162 of file ivyTable.c.

00163 {
00164     int * pPlace;
00165     assert( !Ivy_IsComplement(pObj) );
00166     if ( !Ivy_ObjIsHash(pObj) )
00167         return;
00168     pPlace = Ivy_TableFind( p, pObj );
00169     assert( *pPlace == pObj->Id ); // node should be in the table
00170     *pPlace = ObjIdNew; 
00171 }

Generated on Tue Jan 5 12:18:26 2010 for abc70930 by  doxygen 1.6.1