src/aig/aig/aigTable.c File Reference

#include "aig.h"
Include dependency graph for aigTable.c:

Go to the source code of this file.

Functions

static unsigned long Aig_Hash (Aig_Obj_t *pObj, int TableSize)
static Aig_Obj_t ** Aig_TableFind (Aig_Man_t *p, Aig_Obj_t *pObj)
void Aig_TableResize (Aig_Man_t *p)
Aig_Obj_t * Aig_TableLookup (Aig_Man_t *p, Aig_Obj_t *pGhost)
Aig_Obj_t * Aig_TableLookupTwo (Aig_Man_t *p, Aig_Obj_t *pFanin0, Aig_Obj_t *pFanin1)
void Aig_TableInsert (Aig_Man_t *p, Aig_Obj_t *pObj)
void Aig_TableDelete (Aig_Man_t *p, Aig_Obj_t *pObj)
int Aig_TableCountEntries (Aig_Man_t *p)
void Aig_TableProfile (Aig_Man_t *p)

Function Documentation

static unsigned long Aig_Hash ( Aig_Obj_t *  pObj,
int  TableSize 
) [static]

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

FileName [aigTable.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [Structural hashing table.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id
aigTable.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

] DECLARATIONS ///

Definition at line 28 of file aigTable.c.

00029 {
00030     unsigned long Key = Aig_ObjIsExor(pObj) * 1699;
00031     Key ^= Aig_ObjFanin0(pObj)->Id * 7937;
00032     Key ^= Aig_ObjFanin1(pObj)->Id * 2971;
00033     Key ^= Aig_ObjFaninC0(pObj) * 911;
00034     Key ^= Aig_ObjFaninC1(pObj) * 353;
00035     return Key % TableSize;
00036 }

int Aig_TableCountEntries ( Aig_Man_t *  p  ) 

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 229 of file aigTable.c.

00230 {
00231     Aig_Obj_t * pEntry;
00232     int i, Counter = 0;
00233     for ( i = 0; i < p->nTableSize; i++ )
00234         for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext )
00235             Counter++;
00236     return Counter;
00237 }

void Aig_TableDelete ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
)

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

Synopsis [Deletes the node from the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 207 of file aigTable.c.

00208 {
00209     Aig_Obj_t ** ppPlace;
00210     assert( !Aig_IsComplement(pObj) );
00211     ppPlace = Aig_TableFind( p, pObj );
00212     assert( *ppPlace == pObj ); // node should be in the table
00213     // remove the node
00214     *ppPlace = pObj->pNext;
00215     pObj->pNext = NULL;
00216 }

static Aig_Obj_t** Aig_TableFind ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
) [static]

Definition at line 39 of file aigTable.c.

00040 {
00041     Aig_Obj_t ** ppEntry;
00042     if ( Aig_ObjIsLatch(pObj) )
00043     {
00044         assert( Aig_ObjChild0(pObj) && Aig_ObjChild1(pObj) == NULL );
00045     }
00046     else
00047     {
00048         assert( Aig_ObjChild0(pObj) && Aig_ObjChild1(pObj) );
00049         assert( Aig_ObjFanin0(pObj)->Id < Aig_ObjFanin1(pObj)->Id );
00050     }
00051     for ( ppEntry = p->pTable + Aig_Hash(pObj, p->nTableSize); *ppEntry; ppEntry = &(*ppEntry)->pNext )
00052         if ( *ppEntry == pObj )
00053             return ppEntry;
00054     assert( *ppEntry == NULL );
00055     return ppEntry;
00056 }

void Aig_TableInsert ( Aig_Man_t *  p,
Aig_Obj_t *  pObj 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 184 of file aigTable.c.

00185 {
00186     Aig_Obj_t ** ppPlace;
00187     assert( !Aig_IsComplement(pObj) );
00188     assert( Aig_TableLookup(p, pObj) == NULL );
00189     if ( (pObj->Id & 0xFF) == 0 && 2 * p->nTableSize < Aig_ManNodeNum(p) )
00190         Aig_TableResize( p );
00191     ppPlace = Aig_TableFind( p, pObj );
00192     assert( *ppPlace == NULL );
00193     *ppPlace = pObj;
00194 }

Aig_Obj_t* Aig_TableLookup ( Aig_Man_t *  p,
Aig_Obj_t *  pGhost 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 118 of file aigTable.c.

00119 {
00120     Aig_Obj_t * pEntry;
00121     assert( !Aig_IsComplement(pGhost) );
00122     if ( pGhost->Type == AIG_OBJ_LATCH )
00123     {
00124         assert( Aig_ObjChild0(pGhost) && Aig_ObjChild1(pGhost) == NULL );
00125         if ( !Aig_ObjRefs(Aig_ObjFanin0(pGhost)) )
00126             return NULL;
00127     }
00128     else
00129     {
00130         assert( pGhost->Type == AIG_OBJ_AND );
00131         assert( Aig_ObjChild0(pGhost) && Aig_ObjChild1(pGhost) );
00132         assert( Aig_ObjFanin0(pGhost)->Id < Aig_ObjFanin1(pGhost)->Id );
00133         if ( !Aig_ObjRefs(Aig_ObjFanin0(pGhost)) || !Aig_ObjRefs(Aig_ObjFanin1(pGhost)) )
00134             return NULL;
00135     }
00136     for ( pEntry = p->pTable[Aig_Hash(pGhost, p->nTableSize)]; pEntry; pEntry = pEntry->pNext )
00137     {
00138         if ( Aig_ObjChild0(pEntry) == Aig_ObjChild0(pGhost) && 
00139              Aig_ObjChild1(pEntry) == Aig_ObjChild1(pGhost) && 
00140              Aig_ObjType(pEntry) == Aig_ObjType(pGhost) )
00141             return pEntry;
00142     }
00143     return NULL;
00144 }

Aig_Obj_t* Aig_TableLookupTwo ( Aig_Man_t *  p,
Aig_Obj_t *  pFanin0,
Aig_Obj_t *  pFanin1 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 157 of file aigTable.c.

00158 {
00159     Aig_Obj_t * pGhost;
00160     // consider simple cases
00161     if ( pFanin0 == pFanin1 )
00162         return pFanin0;
00163     if ( pFanin0 == Aig_Not(pFanin1) )
00164         return Aig_ManConst0(p);
00165     if ( Aig_Regular(pFanin0) == Aig_ManConst1(p) )
00166         return pFanin0 == Aig_ManConst1(p) ? pFanin1 : Aig_ManConst0(p);
00167     if ( Aig_Regular(pFanin1) == Aig_ManConst1(p) )
00168         return pFanin1 == Aig_ManConst1(p) ? pFanin0 : Aig_ManConst0(p);
00169     pGhost = Aig_ObjCreateGhost( p, pFanin0, pFanin1, AIG_OBJ_AND );
00170     return Aig_TableLookup( p, pGhost );
00171 }

void Aig_TableProfile ( Aig_Man_t *  p  ) 

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

Synopsis [Profiles the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 250 of file aigTable.c.

00251 {
00252     Aig_Obj_t * pEntry;
00253     int i, Counter;
00254     for ( i = 0; i < p->nTableSize; i++ )
00255     {
00256         Counter = 0;
00257         for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext )
00258             Counter++;
00259         if ( Counter ) 
00260             printf( "%d ", Counter );
00261     }
00262 }

void Aig_TableResize ( Aig_Man_t *  p  ) 

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

Synopsis [Resizes the table.]

Description [Typically this procedure should not be called.]

SideEffects []

SeeAlso []

Definition at line 73 of file aigTable.c.

00074 {
00075     Aig_Obj_t * pEntry, * pNext;
00076     Aig_Obj_t ** pTableOld, ** ppPlace;
00077     int nTableSizeOld, Counter, i, clk;
00078 clk = clock();
00079     // save the old table
00080     pTableOld = p->pTable;
00081     nTableSizeOld = p->nTableSize;
00082     // get the new table
00083     p->nTableSize = Aig_PrimeCudd( 2 * Aig_ManNodeNum(p) ); 
00084     p->pTable = ALLOC( Aig_Obj_t *, p->nTableSize );
00085     memset( p->pTable, 0, sizeof(Aig_Obj_t *) * p->nTableSize );
00086     // rehash the entries from the old table
00087     Counter = 0;
00088     for ( i = 0; i < nTableSizeOld; i++ )
00089     for ( pEntry = pTableOld[i], pNext = pEntry? pEntry->pNext : NULL; 
00090           pEntry; pEntry = pNext, pNext = pEntry? pEntry->pNext : NULL )
00091     {
00092         // get the place where this entry goes in the table 
00093         ppPlace = Aig_TableFind( p, pEntry );
00094         assert( *ppPlace == NULL ); // should not be there
00095         // add the entry to the list
00096         *ppPlace = pEntry;
00097         pEntry->pNext = NULL;
00098         Counter++;
00099     }
00100     assert( Counter == Aig_ManNodeNum(p) );
00101 //    printf( "Increasing the structural table size from %6d to %6d. ", nTableSizeOld, p->nTableSize );
00102 //    PRT( "Time", clock() - clk );
00103     // replace the table and the parameters
00104     free( pTableOld );
00105 }

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