src/aig/hop/hopTable.c File Reference

#include "hop.h"
Include dependency graph for hopTable.c:

Go to the source code of this file.

Functions

static unsigned long Hop_Hash (Hop_Obj_t *pObj, int TableSize)
static Hop_Obj_t ** Hop_TableFind (Hop_Man_t *p, Hop_Obj_t *pObj)
static void Hop_TableResize (Hop_Man_t *p)
static unsigned int Cudd_PrimeAig (unsigned int p)
Hop_Obj_t * Hop_TableLookup (Hop_Man_t *p, Hop_Obj_t *pGhost)
void Hop_TableInsert (Hop_Man_t *p, Hop_Obj_t *pObj)
void Hop_TableDelete (Hop_Man_t *p, Hop_Obj_t *pObj)
int Hop_TableCountEntries (Hop_Man_t *p)
void Hop_TableProfile (Hop_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 234 of file hopTable.c.

00235 {
00236     int i,pn;
00237     p--;
00238     do {
00239         p++;
00240         if (p&1) {
00241             pn = 1;
00242             i = 3;
00243             while ((unsigned) (i * i) <= p) {
00244                 if (p % i == 0) {
00245                     pn = 0;
00246                     break;
00247                 }
00248                 i += 2;
00249             }
00250         } else {
00251             pn = 0;
00252         }
00253     } while (!pn);
00254     return(p);
00255 
00256 } /* end of Cudd_Prime */

static unsigned long Hop_Hash ( Hop_Obj_t *  pObj,
int  TableSize 
) [static]

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

FileName [hopTable.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Minimalistic And-Inverter Graph package.]

Synopsis [Structural hashing table.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

] DECLARATIONS ///

Definition at line 28 of file hopTable.c.

00029 {
00030     unsigned long Key = Hop_ObjIsExor(pObj) * 1699;
00031     Key ^= Hop_ObjFanin0(pObj)->Id * 7937;
00032     Key ^= Hop_ObjFanin1(pObj)->Id * 2971;
00033     Key ^= Hop_ObjFaninC0(pObj) * 911;
00034     Key ^= Hop_ObjFaninC1(pObj) * 353;
00035     return Key % TableSize;
00036 }

int Hop_TableCountEntries ( Hop_Man_t *  p  ) 

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 143 of file hopTable.c.

00144 {
00145     Hop_Obj_t * pEntry;
00146     int i, Counter = 0;
00147     for ( i = 0; i < p->nTableSize; i++ )
00148         for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext )
00149             Counter++;
00150     return Counter;
00151 }

void Hop_TableDelete ( Hop_Man_t *  p,
Hop_Obj_t *  pObj 
)

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

Synopsis [Deletes the node from the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 121 of file hopTable.c.

00122 {
00123     Hop_Obj_t ** ppPlace;
00124     assert( !Hop_IsComplement(pObj) );
00125     ppPlace = Hop_TableFind( p, pObj );
00126     assert( *ppPlace == pObj ); // node should be in the table
00127     // remove the node
00128     *ppPlace = pObj->pNext;
00129     pObj->pNext = NULL;
00130 }

static Hop_Obj_t** Hop_TableFind ( Hop_Man_t *  p,
Hop_Obj_t *  pObj 
) [static]

Definition at line 39 of file hopTable.c.

00040 {
00041     Hop_Obj_t ** ppEntry;
00042     assert( Hop_ObjChild0(pObj) && Hop_ObjChild1(pObj) );
00043     assert( Hop_ObjFanin0(pObj)->Id < Hop_ObjFanin1(pObj)->Id );
00044     for ( ppEntry = p->pTable + Hop_Hash(pObj, p->nTableSize); *ppEntry; ppEntry = &(*ppEntry)->pNext )
00045         if ( *ppEntry == pObj )
00046             return ppEntry;
00047     assert( *ppEntry == NULL );
00048     return ppEntry;
00049 }

void Hop_TableInsert ( Hop_Man_t *  p,
Hop_Obj_t *  pObj 
)

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

Synopsis [Adds the new node to the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 98 of file hopTable.c.

00099 {
00100     Hop_Obj_t ** ppPlace;
00101     assert( !Hop_IsComplement(pObj) );
00102     assert( Hop_TableLookup(p, pObj) == NULL );
00103     if ( (pObj->Id & 0xFF) == 0 && 2 * p->nTableSize < Hop_ManNodeNum(p) )
00104         Hop_TableResize( p );
00105     ppPlace = Hop_TableFind( p, pObj );
00106     assert( *ppPlace == NULL );
00107     *ppPlace = pObj;
00108 }

Hop_Obj_t* Hop_TableLookup ( Hop_Man_t *  p,
Hop_Obj_t *  pGhost 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 69 of file hopTable.c.

00070 {
00071     Hop_Obj_t * pEntry;
00072     assert( !Hop_IsComplement(pGhost) );
00073     assert( Hop_ObjChild0(pGhost) && Hop_ObjChild1(pGhost) );
00074     assert( Hop_ObjFanin0(pGhost)->Id < Hop_ObjFanin1(pGhost)->Id );
00075     if ( p->fRefCount && (!Hop_ObjRefs(Hop_ObjFanin0(pGhost)) || !Hop_ObjRefs(Hop_ObjFanin1(pGhost))) )
00076         return NULL;
00077     for ( pEntry = p->pTable[Hop_Hash(pGhost, p->nTableSize)]; pEntry; pEntry = pEntry->pNext )
00078     {
00079         if ( Hop_ObjChild0(pEntry) == Hop_ObjChild0(pGhost) && 
00080              Hop_ObjChild1(pEntry) == Hop_ObjChild1(pGhost) && 
00081              Hop_ObjType(pEntry) == Hop_ObjType(pGhost) )
00082             return pEntry;
00083     }
00084     return NULL;
00085 }

void Hop_TableProfile ( Hop_Man_t *  p  ) 

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

Synopsis [Profiles the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 209 of file hopTable.c.

00210 {
00211     Hop_Obj_t * pEntry;
00212     int i, Counter;
00213     for ( i = 0; i < p->nTableSize; i++ )
00214     {
00215         Counter = 0;
00216         for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext )
00217             Counter++;
00218         if ( Counter ) 
00219             printf( "%d ", Counter );
00220     }
00221 }

void Hop_TableResize ( Hop_Man_t *  p  )  [static]

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

Synopsis [Resizes the table.]

Description [Typically this procedure should not be called.]

SideEffects []

SeeAlso []

Definition at line 164 of file hopTable.c.

00165 {
00166     Hop_Obj_t * pEntry, * pNext;
00167     Hop_Obj_t ** pTableOld, ** ppPlace;
00168     int nTableSizeOld, Counter, nEntries, i, clk;
00169 clk = clock();
00170     // save the old table
00171     pTableOld = p->pTable;
00172     nTableSizeOld = p->nTableSize;
00173     // get the new table
00174     p->nTableSize = Cudd_PrimeAig( 2 * Hop_ManNodeNum(p) ); 
00175     p->pTable = ALLOC( Hop_Obj_t *, p->nTableSize );
00176     memset( p->pTable, 0, sizeof(Hop_Obj_t *) * p->nTableSize );
00177     // rehash the entries from the old table
00178     Counter = 0;
00179     for ( i = 0; i < nTableSizeOld; i++ )
00180     for ( pEntry = pTableOld[i], pNext = pEntry? pEntry->pNext : NULL; pEntry; pEntry = pNext, pNext = pEntry? pEntry->pNext : NULL )
00181     {
00182         // get the place where this entry goes in the table 
00183         ppPlace = Hop_TableFind( p, pEntry );
00184         assert( *ppPlace == NULL ); // should not be there
00185         // add the entry to the list
00186         *ppPlace = pEntry;
00187         pEntry->pNext = NULL;
00188         Counter++;
00189     }
00190     nEntries = Hop_ManNodeNum(p);
00191     assert( Counter == nEntries );
00192 //    printf( "Increasing the structural table size from %6d to %6d. ", nTableSizeOld, p->nTableSize );
00193 //    PRT( "Time", clock() - clk );
00194     // replace the table and the parameters
00195     free( pTableOld );
00196 }

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