From 095345fc4a8208364d4c1fdf645e0217d3921b8e Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 13 Jan 2012 15:43:09 -0800 Subject: Added new name manager and modified hierarchy manager to use it. --- abclib.dsp | 8 + src/base/abc/abcHieCec.c | 8 + src/base/abc/abcHieNew.c | 243 ++++++++++++++-------- src/misc/util/abc_global.h | 27 +++ src/misc/util/module.make | 1 + src/misc/util/utilNam.c | 492 +++++++++++++++++++++++++++++++++++++++++++++ src/misc/util/utilNam.h | 72 +++++++ 7 files changed, 769 insertions(+), 82 deletions(-) create mode 100644 src/misc/util/utilNam.c create mode 100644 src/misc/util/utilNam.h diff --git a/abclib.dsp b/abclib.dsp index cbb28eda..064206a3 100644 --- a/abclib.dsp +++ b/abclib.dsp @@ -2455,6 +2455,14 @@ SOURCE=.\src\misc\util\utilMem.h # End Source File # Begin Source File +SOURCE=.\src\misc\util\utilNam.c +# End Source File +# Begin Source File + +SOURCE=.\src\misc\util\utilNam.h +# End Source File +# Begin Source File + SOURCE=.\src\misc\util\utilSignal.c # End Source File # Begin Source File diff --git a/src/base/abc/abcHieCec.c b/src/base/abc/abcHieCec.c index ee2500ce..255c98e9 100644 --- a/src/base/abc/abcHieCec.c +++ b/src/base/abc/abcHieCec.c @@ -589,6 +589,14 @@ Gia_Man_t * Abc_NtkHieCecTest( char * pFileName, int fVerbose ) assert( Abc_NtkIsNetlist(pNtk) ); assert( !Abc_NtkLatchNum(pNtk) ); + // test the new data-structure + { + extern void Au_ManDeriveTest( Abc_Ntk_t * pRoot ); + Au_ManDeriveTest( pNtk ); + Abc_NtkDelete( pNtk ); + return NULL; + } + // print stats if ( fVerbose ) Abc_NtkPrintBoxInfo( pNtk ); diff --git a/src/base/abc/abcHieNew.c b/src/base/abc/abcHieNew.c index 91075e7a..75811825 100644 --- a/src/base/abc/abcHieNew.c +++ b/src/base/abc/abcHieNew.c @@ -25,6 +25,7 @@ #include #include "vec.h" +#include "utilNam.h" ABC_NAMESPACE_IMPL_START @@ -32,7 +33,7 @@ ABC_NAMESPACE_IMPL_START /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -#define AU_MAX_FANINS 0x0FFFFFFF +#define AU_MAX_FANINS 0x1FFFFFFF typedef enum { AU_OBJ_NONE, // 0: non-existent object @@ -54,8 +55,8 @@ typedef struct Au_Obj_t_ Au_Obj_t; struct Au_Obj_t_ // 16 bytes { unsigned Func; // functionality - unsigned Type : 4; // object type - unsigned nFanins : 28; // fanin count (related to AU_MAX_FANIN_NUM) + unsigned Type : 3; // object type + unsigned nFanins : 29; // fanin count (related to AU_MAX_FANIN_NUM) int Fanins[2]; // fanin literals }; @@ -70,6 +71,7 @@ struct Au_Ntk_t_ int nObjsUsed; // used objects int nObjs[AU_OBJ_VOID]; // counter of objects of each type // memory for objects + Vec_Ptr_t * vChunks; // memory pages Vec_Ptr_t vPages; // memory pages int iHandle; // currently available ID int nUseful; // the number of useful entries @@ -87,6 +89,7 @@ struct Au_Man_t_ { char * pName; // the name of the library Vec_Ptr_t vNtks; // the array of modules + Abc_Nam_t * pFuncs; // hashing functions into integers int nRefs; // reference counter }; @@ -116,9 +119,9 @@ static inline int Au_NtkFanNum( Au_Ntk_t * p ) { retur static inline int Au_NtkFlopNum( Au_Ntk_t * p ) { return p->nObjs[AU_OBJ_FLOP]; } static inline int Au_NtkBoxNum( Au_Ntk_t * p ) { return p->nObjs[AU_OBJ_BOX]; } static inline int Au_NtkNodeNum( Au_Ntk_t * p ) { return p->nObjs[AU_OBJ_NODE]; } -static inline int Au_NtkObjNumMax( Au_Ntk_t * p ) { return Vec_PtrSize(&p->vPages) * (1 << 12) + p->iHandle; } +static inline int Au_NtkObjNumMax( Au_Ntk_t * p ) { return (Vec_PtrSize(&p->vPages) - 1) * (1 << 12) + p->iHandle; } static inline int Au_NtkObjNum( Au_Ntk_t * p ) { return p->nObjsUsed; } -static inline Au_Obj_t * Au_NtkObj( Au_Ntk_t * p, int i ) { return (Au_Obj_t *)p->vPages.pArray[i >> 16] + (i & 0xFFFF); } +static inline Au_Obj_t * Au_NtkObj( Au_Ntk_t * p, int i ) { return (Au_Obj_t *)p->vPages.pArray[i >> 12] + (i & 0xFFF); } static inline int Au_ObjIsNone( Au_Obj_t * p ) { return p->Type == AU_OBJ_NONE; } static inline int Au_ObjIsConst0( Au_Obj_t * p ) { return p->Type == AU_OBJ_CONST0; } @@ -132,7 +135,7 @@ static inline int Au_ObjIsTerm( Au_Obj_t * p ) { retur static inline char * Au_ObjBase( Au_Obj_t * p ) { return (char *)p - ((ABC_PTRINT_T)p & 0x3FF); } static inline Au_Ntk_t * Au_ObjNtk( Au_Obj_t * p ) { return ((Au_Ntk_t **)Au_ObjBase(p))[0]; } -static inline int Au_ObjId( Au_Obj_t * p ) { return ((int *)Au_ObjBase(p))[3] + (((ABC_PTRINT_T)p & 0x3FF) >> 4); } +static inline int Au_ObjId( Au_Obj_t * p ) { return ((int *)Au_ObjBase(p))[2] | (((ABC_PTRINT_T)p & 0x3FF) >> 4); } static inline int Au_ObjPioNum( Au_Obj_t * p ) { assert(Au_ObjIsTerm(p)); return p->Fanins[p->nFanins]; } static inline int Au_ObjFunc( Au_Obj_t * p ) { return p->Func; } static inline Au_Ntk_t * Au_ObjModel( Au_Obj_t * p ) { assert(Au_ObjIsFan(p)||Au_ObjIsBox(p)); return Au_ManNtk(Au_NtkMan(Au_ObjNtk(p)), p->Func); } @@ -146,12 +149,70 @@ static inline void Au_ObjSetFaninLit( Au_Obj_t * p, int i, int f){ asser static inline int Au_ObjFanout( Au_Obj_t * p, int i ) { assert(p->Type == AU_OBJ_BOX && i >= 0 && i < p->Fanins[p->nFanins] && p->Fanins[i]); return p->Fanins[p->nFanins + 1 + i]; } static inline int Au_ObjSetFanout( Au_Obj_t * p, int i, int f ) { assert(p->Type == AU_OBJ_BOX && i >= 0 && i < p->Fanins[p->nFanins] && p->Fanins[i] == 0 && f > 0); p->Fanins[p->nFanins + 1 + i] = f; } -extern void Au_NtkPrintStats( Au_Ntk_t * p ); +extern void Au_ManAddNtk( Au_Man_t * pMan, Au_Ntk_t * p ); +extern void Au_ManFree( Au_Man_t * p ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// +/**Function************************************************************* + + Synopsis [Working with models.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Au_Ntk_t * Au_NtkAlloc( Au_Man_t * pMan, char * pName ) +{ + Au_Ntk_t * p; + p = ABC_CALLOC( Au_Ntk_t, 1 ); + p->pName = Au_UtilStrsav( pName ); + p->vChunks = Vec_PtrAlloc( 111 ); + Vec_IntGrow( &p->vPis, 111 ); + Vec_IntGrow( &p->vPos, 111 ); + Vec_PtrGrow( &p->vPages, 11 ); + Au_ManAddNtk( pMan, p ); + return p; +} +void Au_NtkFree( Au_Ntk_t * p ) +{ + Au_ManFree( p->pMan ); + Vec_PtrFreeFree( p->vChunks ); + ABC_FREE( p->vPages.pArray ); + ABC_FREE( p->vPis.pArray ); + ABC_FREE( p->vPos.pArray ); + ABC_FREE( p->pHTable ); + ABC_FREE( p->pName ); + ABC_FREE( p ); +} +int Au_NtkMemUsage( Au_Ntk_t * p ) +{ + int Mem = sizeof(Au_Ntk_t); + Mem += 4 * Vec_IntSize(&p->vPis); + Mem += 4 * Vec_IntSize(&p->vPos); + Mem += 16 * Vec_PtrSize(p->vChunks) * ((1<<12) + 64); + return Mem; +} +void Au_NtkPrintStats( Au_Ntk_t * p ) +{ + printf( "%-13s:", Au_NtkName(p) ); + printf( " i/o =%5d/%5d", Au_NtkPiNum(p), Au_NtkPoNum(p) ); +// printf( " lat =%5d", Au_NtkFlopNum(p) ); + printf( " nd =%6d", Au_NtkNodeNum(p) ); + printf( " box =%5d", Au_NtkBoxNum(p) ); + printf( " obj =%6d", Au_NtkObjNum(p) ); + printf( " max =%6d", Au_NtkObjNumMax(p) ); + printf( " use =%6d", p->nUseful ); + printf( " (%.2f %%)", 100.0 * (Au_NtkObjNumMax(p) - p->nUseful) / Au_NtkObjNumMax(p) ); + printf( " %.2f Mb", 1.0 * Au_NtkMemUsage(p) / (1 << 20) ); + printf( "\n" ); +} + /**Function************************************************************* Synopsis [Working with manager.] @@ -170,6 +231,7 @@ Au_Man_t * Au_ManAlloc( char * pName ) p->pName = Au_UtilStrsav( pName ); Vec_PtrGrow( &p->vNtks, 111 ); Vec_PtrPush( &p->vNtks, NULL ); + p->pFuncs = Abc_NamStart( 100, 16 ); return p; } void Au_ManFree( Au_Man_t * p ) @@ -177,15 +239,23 @@ void Au_ManFree( Au_Man_t * p ) assert( p->nRefs > 0 ); if ( --p->nRefs > 0 ) return; + Abc_NamStop( p->pFuncs ); ABC_FREE( p->vNtks.pArray ); ABC_FREE( p->pName ); ABC_FREE( p ); } +void Au_ManDelete( Au_Man_t * p ) +{ + Au_Ntk_t * pNtk; + int i; + Vec_PtrForEachEntryStart( Au_Ntk_t *, &p->vNtks, pNtk, i, 1 ) + Au_NtkFree( pNtk ); +} int Au_ManFindNtk( Au_Man_t * p, char * pName ) { Au_Ntk_t * pNtk; int i; - Vec_PtrForEachEntry( Au_Ntk_t *, &p->vNtks, pNtk, i ) + Vec_PtrForEachEntryStart( Au_Ntk_t *, &p->vNtks, pNtk, i, 1 ) if ( !strcmp(Au_NtkName(pNtk), pName) ) return i; return -1; @@ -197,60 +267,27 @@ void Au_ManAddNtk( Au_Man_t * pMan, Au_Ntk_t * p ) p->Id = Vec_PtrSize( &pMan->vNtks ); Vec_PtrPush( &pMan->vNtks, p ); } +int Au_ManMemUsage( Au_Man_t * p ) +{ + Au_Ntk_t * pNtk; + int i, Mem = 0; + Vec_PtrForEachEntryStart( Au_Ntk_t *, &p->vNtks, pNtk, i, 1 ) + Mem += Au_NtkMemUsage( pNtk ); + return Mem; +} void Au_ManPrintStats( Au_Man_t * p ) { Au_Ntk_t * pNtk; int i; printf( "Design %-13s\n", Au_ManName(p) ); - Vec_PtrForEachEntry( Au_Ntk_t *, &p->vNtks, pNtk, i ) + Vec_PtrForEachEntryStart( Au_Ntk_t *, &p->vNtks, pNtk, i, 1 ) Au_NtkPrintStats( pNtk ); -} - -/**Function************************************************************* - - Synopsis [Working with models.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Au_Ntk_t * Au_NtkAlloc( Au_Man_t * pMan, char * pName ) -{ - Au_Ntk_t * p; - p = ABC_CALLOC( Au_Ntk_t, 1 ); - p->pName = Au_UtilStrsav( pName ); - Vec_IntGrow( &p->vPis, 111 ); - Vec_IntGrow( &p->vPos, 111 ); - Vec_PtrGrow( &p->vPages, 11 ); - Au_ManAddNtk( pMan, p ); - return p; -} -void Au_NtkFree( Au_Ntk_t * p ) -{ - Au_ManFree( p->pMan ); - ABC_FREE( p->vPages.pArray ); - ABC_FREE( p->vPis.pArray ); - ABC_FREE( p->vPos.pArray ); - ABC_FREE( p->pHTable ); - ABC_FREE( p->pName ); - ABC_FREE( p ); -} -void Au_NtkPrintStats( Au_Ntk_t * p ) -{ - printf( "%-13s:", Au_NtkName(p) ); - printf( " i/o =%5d/%5d", Au_NtkPiNum(p), Au_NtkPoNum(p) ); - printf( " lat =%5d", Au_NtkFlopNum(p) ); - printf( " nd =%6d", Au_NtkNodeNum(p) ); - printf( " box =%5d", Au_NtkBoxNum(p) ); - printf( " obj =%6d", Au_NtkObjNum(p) ); - printf( " max =%6d", Au_NtkObjNumMax(p) ); - printf( " use =%6d", p->nUseful ); + printf( "Different functions = %d. ", Abc_NamObjNumMax(p->pFuncs) ); + printf( "Memory = %.2f Mb", 1.0 * Au_ManMemUsage(p) / (1 << 20) ); printf( "\n" ); } + /**Function************************************************************* Synopsis [Returns memory for the next object.] @@ -265,50 +302,77 @@ void Au_NtkPrintStats( Au_Ntk_t * p ) static inline void Au_NtkInsertHeader( Au_Ntk_t * p ) { Au_Obj_t * pMem = (Au_Obj_t *)Vec_PtrEntryLast( &p->vPages ); - if ( p->iHandle > 0 ) - p->iHandle += 64 - (p->iHandle & 63); assert( (((ABC_PTRINT_T)(pMem + p->iHandle) & 0x3FF) >> 4) == 0 ); ((Au_Ntk_t **)(pMem + p->iHandle))[0] = p; - ((int *)(pMem + p->iHandle))[3] = Vec_PtrSize(&p->vPages) - 1; + ((int *)(pMem + p->iHandle))[2] = ((Vec_PtrSize(&p->vPages) - 1) << 12) | (p->iHandle & 0xFC0); p->iHandle++; } int Au_NtkAllocObj( Au_Ntk_t * p, int nFanins, int Type ) { - Au_Obj_t * pMem; - int nObjInt = ((1+nFanins) >> 4) + (((1+nFanins) & 15) > 0); + Au_Obj_t * pMem, * pObj, * pTemp; + int Id, nObjInt = ((2+nFanins) >> 2) + (((2+nFanins) & 3) > 0); + if ( nObjInt > 63 ) + { + int nObjInt2 = 63 + 64 * (((nObjInt-63) >> 6) + (((nObjInt-63) & 63) > 0)); + assert( nObjInt2 >= nObjInt ); + p->nUseful += nObjInt - nObjInt2; + nObjInt = nObjInt2; + } + if ( Vec_PtrSize(&p->vPages) == 0 || p->iHandle + nObjInt > (1 << 12) ) { - if ( nObjInt + (1 << 6) > (1 << 12) ) - pMem = ABC_CALLOC( Au_Obj_t, nObjInt + (1 << 6) ); + if ( nObjInt + 64 > (1 << 12) ) + pMem = ABC_CALLOC( Au_Obj_t, nObjInt + 64 ); else - pMem = ABC_CALLOC( Au_Obj_t, (1 << 12) ); - Vec_PtrPush( &p->vPages, pMem ); + pMem = ABC_CALLOC( Au_Obj_t, (1 << 12) + 64 ); + Vec_PtrPush( p->vChunks, pMem ); + if ( ((ABC_PTRINT_T)pMem & 0xF) ) + pMem = (Au_Obj_t *)((char *)pMem + 16 - ((ABC_PTRINT_T)pMem & 0xF)); + assert( ((ABC_PTRINT_T)pMem & 0xF) == 0 ); p->iHandle = (((ABC_PTRINT_T)pMem & 0x3FF) >> 4); + if ( p->iHandle ) + { + pMem += 64 - (p->iHandle & 63); + // can introduce p->iHandleMax = (1 << 12) - (64 - (p->iHandle & 63)) + p->iHandle = 0; + } + Vec_PtrPush( &p->vPages, pMem ); Au_NtkInsertHeader( p ); } else + { pMem = (Au_Obj_t *)Vec_PtrEntryLast( &p->vPages ); - if ( nObjInt > 64 - (p->iHandle & 63) ) - Au_NtkInsertHeader( p ); - if ( p->iHandle + nObjInt > (1 << 12) ) - return Au_NtkAllocObj( p, nFanins, Type ); - assert( *((int *)pMem) == 0 ); - pMem->nFanins = nFanins; - p->nObjs[pMem->Type = Type]++; + if ( !(p->iHandle & 63) || nObjInt > (64 - (p->iHandle & 63)) ) + { + if ( p->iHandle & 63 ) + p->iHandle += 64 - (p->iHandle & 63); + Au_NtkInsertHeader( p ); + } + if ( p->iHandle + nObjInt > (1 << 12) ) + return Au_NtkAllocObj( p, nFanins, Type ); + } + pObj = pMem + p->iHandle; + assert( *((int *)pObj) == 0 ); + pObj->nFanins = nFanins; + p->nObjs[pObj->Type = Type]++; if ( Type == AU_OBJ_PI ) { - Au_ObjSetFaninLit( pMem, 0, Vec_IntSize(&p->vPis) ); - Vec_IntPush( &p->vPis, Au_ObjId(pMem) ); + Au_ObjSetFaninLit( pObj, 0, Vec_IntSize(&p->vPis) ); + Vec_IntPush( &p->vPis, Au_ObjId(pObj) ); } else if ( Type == AU_OBJ_PO ) { - Au_ObjSetFaninLit( pMem, 1, Vec_IntSize(&p->vPos) ); - Vec_IntPush( &p->vPos, Au_ObjId(pMem) ); + Au_ObjSetFaninLit( pObj, 1, Vec_IntSize(&p->vPos) ); + Vec_IntPush( &p->vPos, Au_ObjId(pObj) ); } p->iHandle += nObjInt; p->nUseful += nObjInt; p->nObjsUsed++; - return Au_ObjId(pMem); + + Id = Au_ObjId(pObj); + pTemp = Au_NtkObj( p, Id ); + assert( pTemp == pObj ); + return Id; } int Au_NtkCreateConst0( Au_Ntk_t * pNtk ) { @@ -357,6 +421,7 @@ int Au_NtkCreateBox( Au_Ntk_t * pNtk, Vec_Int_t * vFanins, int nFanouts, int iMo Au_ObjSetFaninLit( p, nFanins + 1 + i, Au_NtkCreateFan(pNtk, Id, i, iModel) ); p->nFanins = nFanins; p->Func = iModel; + assert( iModel > 0 ); return Id; } @@ -386,6 +451,7 @@ Au_Ntk_t * Au_NtkDerive( Au_Man_t * pMan, Abc_Ntk_t * pNtk ) Vec_Int_t * vFanins; int i, k, iFunc; assert( Abc_NtkIsNetlist(pNtk) ); + Abc_NtkCleanCopy( pNtk ); p = Au_NtkAlloc( pMan, Abc_NtkName(pNtk) ); // copy PIs Abc_NtkForEachPi( pNtk, pTerm, i ) @@ -396,15 +462,17 @@ Au_Ntk_t * Au_NtkDerive( Au_Man_t * pMan, Abc_Ntk_t * pNtk ) Vec_PtrForEachEntry( Abc_Obj_t *, vOrder, pObj, i ) { Vec_IntClear( vFanins ); - Abc_ObjForEachFanin( pObj, pTerm, k ) - Vec_IntPush( vFanins, pTerm->iTemp ); if ( Abc_ObjIsNode(pObj) ) { - iFunc = 3; // add type here + Abc_ObjForEachFanin( pObj, pTerm, k ) + Vec_IntPush( vFanins, pTerm->iTemp ); + iFunc = Abc_NamStrFindOrAdd( pMan->pFuncs, (char *)pObj->pData, NULL ); Abc_ObjFanout0(pObj)->iTemp = Au_NtkCreateNode(p, vFanins, iFunc); continue; } assert( Abc_ObjIsBox(pObj) ); + Abc_ObjForEachFanin( pObj, pTerm, k ) + Vec_IntPush( vFanins, Abc_ObjFanin0(pTerm)->iTemp ); pNtkModel = (Abc_Ntk_t *)pObj->pData; pObj->iTemp = Au_NtkCreateBox(p, vFanins, Abc_ObjFanoutNum(pObj), pNtkModel->iStep ); pAuObj = Au_NtkObj(p, pObj->iTemp); @@ -419,20 +487,31 @@ Au_Ntk_t * Au_NtkDerive( Au_Man_t * pMan, Abc_Ntk_t * pNtk ) return p; } -void Au_ManDeriveTest( Abc_Lib_t * pLib ) +void Au_ManDeriveTest( Abc_Ntk_t * pRoot ) { + extern Vec_Ptr_t * Abc_NtkCollectHie( Abc_Ntk_t * pNtk ); + + Vec_Ptr_t * vOrder; Abc_Ntk_t * pMod; Au_Man_t * pMan; Au_Ntk_t * pNtk; - int i; - pMan = Au_ManAlloc( pLib->pName ); - Vec_PtrForEachEntry( Abc_Ntk_t *, pLib->vModules, pMod, i ) + int i, clk = clock(); + + pMan = Au_ManAlloc( pRoot->pDesign->pName ); + + vOrder = Abc_NtkCollectHie( pRoot ); +// Vec_PtrForEachEntry( Abc_Ntk_t *, pLib->vModules, pMod, i ) + Vec_PtrForEachEntry( Abc_Ntk_t *, vOrder, pMod, i ) { pNtk = Au_NtkDerive( pMan, pMod ); pMod->iStep = pNtk->Id; } + Vec_PtrFree( vOrder ); + Au_ManPrintStats( pMan ); - Au_ManFree( pMan ); + Au_ManDelete( pMan ); + + Abc_PrintTime( 1, "Time", clock() - clk ); } //////////////////////////////////////////////////////////////////////// diff --git a/src/misc/util/abc_global.h b/src/misc/util/abc_global.h index 67b8abb0..61aa9327 100644 --- a/src/misc/util/abc_global.h +++ b/src/misc/util/abc_global.h @@ -298,6 +298,33 @@ static inline void Abc_PrintMemoryP( int level, const char * pStr, int time, int ABC_PRMP( pStr, time, Time ); } +// Returns the next prime >= p +static inline int Abc_PrimeCudd( unsigned int p ) +{ + int i,pn; + p--; + do { + p++; + if (p&1) + { + pn = 1; + i = 3; + while ((unsigned) (i * i) <= p) + { + if (p % i == 0) { + pn = 0; + break; + } + i += 2; + } + } + else + pn = 0; + } while (!pn); + return(p); + +} // end of Cudd_Prime + extern void Abc_Sort( int * pInput, int nSize ); extern int * Abc_SortCost( int * pCosts, int nSize ); diff --git a/src/misc/util/module.make b/src/misc/util/module.make index 287f22f7..bef32aea 100644 --- a/src/misc/util/module.make +++ b/src/misc/util/module.make @@ -1,4 +1,5 @@ SRC += src/misc/util/utilCex.c \ src/misc/util/utilFile.c \ + src/misc/util/utilNam.c \ src/misc/util/utilSignal.c \ src/misc/util/utilSort.c diff --git a/src/misc/util/utilNam.c b/src/misc/util/utilNam.c new file mode 100644 index 00000000..bfcb05f1 --- /dev/null +++ b/src/misc/util/utilNam.c @@ -0,0 +1,492 @@ +/**CFile**************************************************************** + + FileName [utilNam.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Manager for character strings.] + + Synopsis [Manager for character strings.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: utilNam.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + + +#include +#include +#include +#include + +#include "abc_global.h" +#include "vec.h" +#include "utilNam.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// this package maps non-empty character strings into natural numbers and back + +// name manager +struct Abc_Nam_t_ +{ + // info storage for names + int nStore; // the size of allocated storage + int iHandle; // the current free handle + char * pStore; // storage for name objects + // internal number mappings + Vec_Int_t * vInt2Handle; // mapping integers into handles + Vec_Int_t * vInt2Next; // mapping integers into nexts + // hash table for names + int * pBins; // the hash table bins + int nBins; // the number of bins + // manager recycling + int nRefs; // reference counter for the manager +}; + +static inline char * Abc_NamHandleToStr( Abc_Nam_t * p, int h ) { return (char *)(p->pStore + h); } +static inline int Abc_NamIntToHandle( Abc_Nam_t * p, int i ) { return Vec_IntEntry(p->vInt2Handle, i); } +static inline char * Abc_NamIntToStr( Abc_Nam_t * p, int i ) { return Abc_NamHandleToStr(p, Abc_NamIntToHandle(p,i)); } +static inline int Abc_NamIntToNext( Abc_Nam_t * p, int i ) { return Vec_IntEntry(p->vInt2Next, i); } +static inline int * Abc_NamIntToNextP( Abc_Nam_t * p, int i ) { return Vec_IntEntryP(p->vInt2Next, i); } + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Creates manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Nam_t * Abc_NamStart( int nObjs, int nAveSize ) +{ + Abc_Nam_t * p; + if ( nObjs == 0 ) + nObjs = 16; + p = ABC_CALLOC( Abc_Nam_t, 1 ); + p->nStore = ((nObjs * (nAveSize + 1) + 16) / 4) * 4; + p->pStore = ABC_ALLOC( char, p->nStore ); + p->nBins = Abc_PrimeCudd( nObjs ); + p->pBins = ABC_CALLOC( int, p->nBins ); + // 0th object is unused + p->vInt2Handle = Vec_IntAlloc( nObjs ); Vec_IntPush( p->vInt2Handle, -1 ); + p->vInt2Next = Vec_IntAlloc( nObjs ); Vec_IntPush( p->vInt2Next, -1 ); + p->iHandle = 4; + memset( p->pStore, 0, 4 ); +//Abc_Print( 1, "Starting nam with %d bins.\n", p->nBins ); + // start reference counting + p->nRefs = 1; + return p; +} + +/**Function************************************************************* + + Synopsis [Deletes manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NamStop( Abc_Nam_t * p ) +{ +//Abc_Print( 1, "Starting nam with %d bins.\n", p->nBins ); + Vec_IntFree( p->vInt2Handle ); + Vec_IntFree( p->vInt2Next ); + ABC_FREE( p->pStore ); + ABC_FREE( p->pBins ); + ABC_FREE( p ); +} + +/**Function************************************************************* + + Synopsis [Prints manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NamPrint( Abc_Nam_t * p ) +{ + int h, i; + Vec_IntForEachEntryStart( p->vInt2Handle, h, i, 1 ) + Abc_Print( 1, "%d=%s ", i, Abc_NamHandleToStr(p, h) ); + Abc_Print( 1, "\n" ); +} + +/**Function************************************************************* + + Synopsis [References the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Nam_t * Abc_NamRef( Abc_Nam_t * p ) +{ + p->nRefs++; + return p; +} + +/**Function************************************************************* + + Synopsis [Dereferences the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NamDeref( Abc_Nam_t * p ) +{ + if ( p == NULL ) + return; + if ( --p->nRefs == 0 ) + Abc_NamStop( p ); +} + +/**Function************************************************************* + + Synopsis [Returns the number of used entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NamObjNumMax( Abc_Nam_t * p ) +{ + return Vec_IntSize(p->vInt2Handle); +} + +/**Function************************************************************* + + Synopsis [Reports memory usage of the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NamMemUsed( Abc_Nam_t * p ) +{ + if ( p == NULL ) + return 0; + return sizeof(Abc_Nam_t) + p->iHandle + sizeof(int) * p->nBins + + sizeof(int) * (p->vInt2Handle->nSize + p->vInt2Next->nSize); +} + +/**Function************************************************************* + + Synopsis [Reports memory usage of the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NamMemAlloc( Abc_Nam_t * p ) +{ + if ( p == NULL ) + return 0; + return sizeof(Abc_Nam_t) + p->nStore + sizeof(int) * p->nBins + + sizeof(int) * (p->vInt2Handle->nCap + p->vInt2Next->nCap); +} + +/**Function************************************************************* + + Synopsis [Computes hash value of the C-string.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NamStrHash( const char * pStr, int nTableSize ) +{ + static int s_FPrimes[128] = { + 1009, 1049, 1093, 1151, 1201, 1249, 1297, 1361, 1427, 1459, + 1499, 1559, 1607, 1657, 1709, 1759, 1823, 1877, 1933, 1997, + 2039, 2089, 2141, 2213, 2269, 2311, 2371, 2411, 2467, 2543, + 2609, 2663, 2699, 2741, 2797, 2851, 2909, 2969, 3037, 3089, + 3169, 3221, 3299, 3331, 3389, 3461, 3517, 3557, 3613, 3671, + 3719, 3779, 3847, 3907, 3943, 4013, 4073, 4129, 4201, 4243, + 4289, 4363, 4441, 4493, 4549, 4621, 4663, 4729, 4793, 4871, + 4933, 4973, 5021, 5087, 5153, 5227, 5281, 5351, 5417, 5471, + 5519, 5573, 5651, 5693, 5749, 5821, 5861, 5923, 6011, 6073, + 6131, 6199, 6257, 6301, 6353, 6397, 6481, 6563, 6619, 6689, + 6737, 6803, 6863, 6917, 6977, 7027, 7109, 7187, 7237, 7309, + 7393, 7477, 7523, 7561, 7607, 7681, 7727, 7817, 7877, 7933, + 8011, 8039, 8059, 8081, 8093, 8111, 8123, 8147 + }; + unsigned i, uHash; + for ( uHash = 0, i = 0; pStr[i]; i++ ) + if ( i & 1 ) + uHash *= pStr[i] * s_FPrimes[i & 0x7F]; + else + uHash ^= pStr[i] * s_FPrimes[i & 0x7F]; + return uHash % nTableSize; +} + +/**Function************************************************************* + + Synopsis [Returns place where this string is, or should be.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int * Abc_NamStrHashFind( Abc_Nam_t * p, const char * pStr ) +{ + char * pThis; + int * pPlace = (int *)(p->pBins + Abc_NamStrHash( pStr, p->nBins )); + assert( *pStr ); + for ( pThis = (*pPlace)? Abc_NamIntToStr(p, *pPlace) : NULL; + pThis; pPlace = Abc_NamIntToNextP(p, *pPlace), + pThis = (*pPlace)? Abc_NamIntToStr(p, *pPlace) : NULL ) + if ( !strcmp( pStr, pThis ) ) + break; + return pPlace; +} + +/**Function************************************************************* + + Synopsis [Resizes the hash table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NamStrHashResize( Abc_Nam_t * p ) +{ + Vec_Int_t * vInt2HandleOld; + char * pThis; + int * piPlace, * pBinsOld, iHandleOld, i;//, clk = clock(); + assert( p->pBins != NULL ); +// Abc_Print( 1, "Resizing names manager hash table from %6d to %6d. ", p->nBins, Gia_PrimeCudd( 3 * p->nBins ) ); + // replace the table + pBinsOld = p->pBins; + p->nBins = Abc_PrimeCudd( 3 * p->nBins ); + p->pBins = ABC_CALLOC( int, p->nBins ); + // replace the handles array + vInt2HandleOld = p->vInt2Handle; + p->vInt2Handle = Vec_IntAlloc( 2 * Vec_IntSize(vInt2HandleOld) ); + Vec_IntPush( p->vInt2Handle, -1 ); + Vec_IntClear( p->vInt2Next ); Vec_IntPush( p->vInt2Next, -1 ); + // rehash the entries from the old table + Vec_IntForEachEntryStart( vInt2HandleOld, iHandleOld, i, 1 ) + { + pThis = Abc_NamHandleToStr( p, iHandleOld ); + piPlace = Abc_NamStrHashFind( p, pThis ); + assert( *piPlace == 0 ); + *piPlace = Vec_IntSize( p->vInt2Handle ); + assert( Vec_IntSize( p->vInt2Handle ) == i ); + Vec_IntPush( p->vInt2Handle, iHandleOld ); + Vec_IntPush( p->vInt2Next, 0 ); + } + Vec_IntFree( vInt2HandleOld ); + ABC_FREE( pBinsOld ); +// Abc_PrintTime( 1, "Time", clock() - clk ); +} + +/**Function************************************************************* + + Synopsis [Returns the index of the string in the table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NamStrFind( Abc_Nam_t * p, char * pStr ) +{ + return *Abc_NamStrHashFind( p, pStr ); +} + +/**Function************************************************************* + + Synopsis [Finds or adds the given name to storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NamStrFindOrAdd( Abc_Nam_t * p, char * pStr, int * pfFound ) +{ + int iHandleNew; + int *piPlace = Abc_NamStrHashFind( p, pStr ); + if ( *piPlace ) + { + if ( pfFound ) + *pfFound = 1; + return *piPlace; + } + if ( pfFound ) + *pfFound = 0; + iHandleNew = p->iHandle + strlen(pStr) + 1; + while ( p->nStore < iHandleNew ) + { + p->nStore *= 3; + p->nStore /= 2; + p->pStore = ABC_REALLOC( char, p->pStore, p->nStore ); + } + assert( p->nStore >= iHandleNew ); + // create new handle + *piPlace = Vec_IntSize( p->vInt2Handle ); + strcpy( Abc_NamHandleToStr( p, p->iHandle ), pStr ); + Vec_IntPush( p->vInt2Handle, p->iHandle ); + Vec_IntPush( p->vInt2Next, 0 ); + p->iHandle = iHandleNew; + // extend the hash table + if ( Vec_IntSize(p->vInt2Handle) > 2 * p->nBins ) + Abc_NamStrHashResize( p ); + return Vec_IntSize(p->vInt2Handle) - 1; +} + +/**Function************************************************************* + + Synopsis [Returns name from name ID.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Abc_NamStr( Abc_Nam_t * p, int NameId ) +{ + return NameId? Abc_NamIntToStr(p, NameId) : NULL; +} + +/**Function************************************************************* + + Synopsis [For each ID of the first manager, gives ID of the second one.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Abc_NamComputeIdMap( Abc_Nam_t * p1, Abc_Nam_t * p2 ) +{ + Vec_Int_t * vMap; + char * pThis; + int * piPlace, iHandle1, i; + if ( p1 == p2 ) + return Vec_IntStartNatural( Abc_NamObjNumMax(p1) ); + vMap = Vec_IntStart( Abc_NamObjNumMax(p1) ); + Vec_IntForEachEntryStart( p1->vInt2Handle, iHandle1, i, 1 ) + { + pThis = Abc_NamHandleToStr( p1, iHandle1 ); + piPlace = Abc_NamStrHashFind( p2, pThis ); + Vec_IntWriteEntry( vMap, i, *piPlace ); +// Abc_Print( 1, "%d->%d ", i, *piPlace ); + } + return vMap; +} + +/**Function************************************************************* + + Synopsis [Returns the number of common names in the array.] + + Description [The array contains name IDs in the first manager. + The procedure returns the number of entries that correspond to names + in the first manager that appear in the second manager.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NamReportCommon( Vec_Int_t * vNameIds1, Abc_Nam_t * p1, Abc_Nam_t * p2 ) +{ + int i, Entry, Counter = 0; + Vec_IntForEachEntry( vNameIds1, Entry, i ) + { + assert( Entry > 0 && Entry < Abc_NamObjNumMax(p1) ); + Counter += (Abc_NamStrFind(p2, Abc_NamStr(p1, Entry)) > 0); +// if ( Abc_NamStrFind(p2, Abc_NamStr(p1, Entry)) == 0 ) +// Abc_Print( 1, "unique name <%s>\n", Abc_NamStr(p1, Entry) ); + } + return Counter; +} + +/**Function************************************************************* + + Synopsis [Returns the name that appears in p1 does not appear in p2.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Abc_NamReportUnique( Vec_Int_t * vNameIds1, Abc_Nam_t * p1, Abc_Nam_t * p2 ) +{ + int i, Entry; + Vec_IntForEachEntry( vNameIds1, Entry, i ) + { + assert( Entry > 0 && Entry < Abc_NamObjNumMax(p1) ); + if ( Abc_NamStrFind(p2, Abc_NamStr(p1, Entry)) == 0 ) + return Abc_NamStr(p1, Entry); + } + return NULL; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/misc/util/utilNam.h b/src/misc/util/utilNam.h new file mode 100644 index 00000000..ae2c099c --- /dev/null +++ b/src/misc/util/utilNam.h @@ -0,0 +1,72 @@ +/**CFile**************************************************************** + + FileName [utilNam.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Memory recycling utilities.] + + Synopsis [Internal declarations.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: utilNam.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#ifndef __UTIL_NAM_H__ +#define __UTIL_NAM_H__ + + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +ABC_NAMESPACE_HEADER_START + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Abc_Nam_t_ Abc_Nam_t; + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== utilNam.c ===============================================================*/ +extern Abc_Nam_t * Abc_NamStart( int nObjs, int nAveSize ); +extern void Abc_NamStop( Abc_Nam_t * p ); +extern void Abc_NamPrint( Abc_Nam_t * p ); +extern Abc_Nam_t * Abc_NamRef( Abc_Nam_t * p ); +extern void Abc_NamDeref( Abc_Nam_t * p ); +extern int Abc_NamObjNumMax( Abc_Nam_t * p ); +extern int Abc_NamMemUsed( Abc_Nam_t * p ); +extern int Abc_NamMemAlloc( Abc_Nam_t * p ); +extern int Abc_NamStrFind( Abc_Nam_t * p, char * pStr ); +extern int Abc_NamStrFindOrAdd( Abc_Nam_t * p, char * pStr, int * pfFound ); +extern char * Abc_NamStr( Abc_Nam_t * p, int id ); +extern Vec_Int_t * Abc_NamComputeIdMap( Abc_Nam_t * p1, Abc_Nam_t * p2 ); +extern int Abc_NamReportCommon( Vec_Int_t * vNameIds1, Abc_Nam_t * p1, Abc_Nam_t * p2 ); + + +ABC_NAMESPACE_HEADER_END + +#endif + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + -- cgit v1.2.3