/**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 "misc/vec/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=\n%s\n", 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 = Abc_Clock(); assert( p->pBins != NULL ); // Abc_Print( 1, "Resizing names manager hash table from %6d to %6d. ", p->nBins, Abc_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", Abc_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 i, iHandleNew; int *piPlace; if ( !(pStr[0] != '\\' || pStr[strlen(pStr)-1] == ' ') ) { for ( i = strlen(pStr) - 1; i >= 0; i-- ) if ( *pStr == ' ' ) break; assert( i < (int)strlen(pStr) ); } 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