diff options
Diffstat (limited to 'src/misc')
-rw-r--r-- | src/misc/nm/nmApi.c | 7 | ||||
-rw-r--r-- | src/misc/nm/nmInt.h | 2 | ||||
-rw-r--r-- | src/misc/nm/nmTable.c | 106 | ||||
-rw-r--r-- | src/misc/vec/vecInt.h | 22 |
4 files changed, 120 insertions, 17 deletions
diff --git a/src/misc/nm/nmApi.c b/src/misc/nm/nmApi.c index e44d1ef9..120dbe91 100644 --- a/src/misc/nm/nmApi.c +++ b/src/misc/nm/nmApi.c @@ -46,10 +46,10 @@ Nm_Man_t * Nm_ManCreate( int nSize ) p = ALLOC( Nm_Man_t, 1 ); memset( p, 0, sizeof(Nm_Man_t) ); // set the parameters - p->nSizeFactor = 4; // determined how much larger the table should be compared to data in it - p->nGrowthFactor = 4; // determined how much the table grows after resizing + p->nSizeFactor = 2; // determined how much larger the table should be compared to data in it + p->nGrowthFactor = 3; // determined how much the table grows after resizing // allocate and clean the bins - p->nBins = Cudd_PrimeNm(p->nSizeFactor*nSize); + p->nBins = Cudd_PrimeNm(nSize); p->pBinsI2N = ALLOC( Nm_Entry_t *, p->nBins ); p->pBinsN2I = ALLOC( Nm_Entry_t *, p->nBins ); memset( p->pBinsI2N, 0, sizeof(Nm_Entry_t *) * p->nBins ); @@ -127,6 +127,7 @@ char * Nm_ManStoreIdName( Nm_Man_t * p, int ObjId, char * pName, char * pSuffix nEntrySize = sizeof(Nm_Entry_t) + strlen(pName) + (pSuffix?strlen(pSuffix):0) + 1; nEntrySize = (nEntrySize / 4 + ((nEntrySize % 4) > 0)) * 4; pEntry = (Nm_Entry_t *)Extra_MmFlexEntryFetch( p->pMem, nEntrySize ); + pEntry->pNextI2N = pEntry->pNextN2I = NULL; pEntry->ObjId = ObjId; sprintf( pEntry->Name, "%s%s", pName, pSuffix? pSuffix : "" ); // add the entry to the hash table diff --git a/src/misc/nm/nmInt.h b/src/misc/nm/nmInt.h index 43901993..8356a4cb 100644 --- a/src/misc/nm/nmInt.h +++ b/src/misc/nm/nmInt.h @@ -45,6 +45,8 @@ typedef struct Nm_Entry_t_ Nm_Entry_t; struct Nm_Entry_t_ { int ObjId; // object ID + Nm_Entry_t * pNextI2N; // the next entry in the ID hash table + Nm_Entry_t * pNextN2I; // the next entry in the name hash table char Name[0]; // name of the object }; diff --git a/src/misc/nm/nmTable.c b/src/misc/nm/nmTable.c index 4243244d..4eeaf610 100644 --- a/src/misc/nm/nmTable.c +++ b/src/misc/nm/nmTable.c @@ -44,7 +44,7 @@ static unsigned Nm_HashString( char * pName, int TableSize ) }; unsigned i, Key = 0; for ( i = 0; pName[i] != '\0'; i++ ) - Key ^= s_Primes[i%10]*pName[i]*pName[i]*pName[i]; + Key ^= s_Primes[i%10]*pName[i]*pName[i]; return Key % TableSize; } @@ -67,13 +67,16 @@ static void Nm_ManResize( Nm_Man_t * p ); ***********************************************************************/ int Nm_ManTableAdd( Nm_Man_t * p, Nm_Entry_t * pEntry ) { - int i; + Nm_Entry_t ** ppSpot; +// int i; // resize the tables if needed - if ( p->nEntries * p->nSizeFactor > p->nBins ) +// if ( p->nEntries * p->nSizeFactor > p->nBins ) + if ( p->nEntries > p->nBins * p->nSizeFactor ) { // Nm_ManPrintTables( p ); Nm_ManResize( p ); } +/* // hash it by ID for ( i = Nm_HashNumber(pEntry->ObjId, p->nBins); p->pBinsI2N[i]; i = (i+1) % p->nBins ) if ( p->pBinsI2N[i] == pEntry ) @@ -86,6 +89,15 @@ int Nm_ManTableAdd( Nm_Man_t * p, Nm_Entry_t * pEntry ) return 0; assert( p->pBinsN2I[i] == NULL ); p->pBinsN2I[i] = pEntry; +*/ + ppSpot = p->pBinsI2N + Nm_HashNumber(pEntry->ObjId, p->nBins); + pEntry->pNextI2N = *ppSpot; + *ppSpot = pEntry; + + ppSpot = p->pBinsN2I + Nm_HashString(pEntry->Name, p->nBins); + pEntry->pNextN2I = *ppSpot; + *ppSpot = pEntry; + // report successfully added entry p->nEntries++; return 1; @@ -121,10 +133,16 @@ int Nm_ManTableDelete( Nm_Man_t * p, Nm_Entry_t * pEntry ) ***********************************************************************/ Nm_Entry_t * Nm_ManTableLookupId( Nm_Man_t * p, int ObjId ) { - int i; + Nm_Entry_t * pEntry; +// int i; +/* for ( i = Nm_HashNumber(ObjId, p->nBins); p->pBinsI2N[i]; i = (i+1) % p->nBins ) if ( p->pBinsI2N[i]->ObjId == ObjId ) return p->pBinsI2N[i]; +*/ + for ( pEntry = p->pBinsI2N[ Nm_HashNumber(ObjId, p->nBins) ]; pEntry; pEntry = pEntry->pNextI2N ) + if ( pEntry->ObjId == ObjId ) + return pEntry; return NULL; } @@ -141,9 +159,10 @@ Nm_Entry_t * Nm_ManTableLookupId( Nm_Man_t * p, int ObjId ) ***********************************************************************/ Nm_Entry_t * Nm_ManTableLookupName( Nm_Man_t * p, char * pName, Nm_Entry_t ** ppSecond ) { - Nm_Entry_t * pFirst, * pSecond; - int i, Counter = 0; + Nm_Entry_t * pFirst, * pSecond, * pEntry; + int Counter = 0; pFirst = pSecond = NULL; +/* for ( i = Nm_HashString(pName, p->nBins); p->pBinsN2I[i]; i = (i+1) % p->nBins ) if ( strcmp(p->pBinsN2I[i]->Name, pName) == 0 ) { @@ -158,12 +177,60 @@ Nm_Entry_t * Nm_ManTableLookupName( Nm_Man_t * p, char * pName, Nm_Entry_t ** pp Counter++; if ( Counter > 100 ) printf( "%d ", Counter ); +*/ + for ( pEntry = p->pBinsN2I[ Nm_HashString(pName, p->nBins) ]; pEntry; pEntry = pEntry->pNextN2I ) + if ( strcmp(pEntry->Name, pName) == 0 ) + { + if ( pFirst == NULL ) + pFirst = pEntry; + else if ( pSecond == NULL ) + pSecond = pEntry; + else + assert( 0 ); // name appears more than 2 times + } + // save the names if ( ppSecond ) *ppSecond = pSecond; return pFirst; } +/**Function************************************************************* + + Synopsis [Profiles hash tables.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nm_ManProfile( Nm_Man_t * p ) +{ + Nm_Entry_t * pEntry; + int Counter, e; + printf( "I2N table: " ); + for ( e = 0; e < p->nBins; e++ ) + { + Counter = 0; + for ( pEntry = p->pBinsI2N[e]; pEntry; pEntry = pEntry->pNextI2N ) + Counter++; + printf( "%d ", Counter ); + } + printf( "\n" ); + printf( "N2I table: " ); + for ( e = 0; e < p->nBins; e++ ) + { + Counter = 0; + for ( pEntry = p->pBinsN2I[e]; pEntry; pEntry = pEntry->pNextN2I ) + Counter++; + printf( "%d ", Counter ); + } + printf( "\n" ); +} + + /**Function************************************************************* @@ -178,8 +245,8 @@ Nm_Entry_t * Nm_ManTableLookupName( Nm_Man_t * p, char * pName, Nm_Entry_t ** pp ***********************************************************************/ void Nm_ManResize( Nm_Man_t * p ) { - Nm_Entry_t ** pBinsNewI2N, ** pBinsNewN2I, * pEntry; - int nBinsNew, Counter, e, i, clk; + Nm_Entry_t ** pBinsNewI2N, ** pBinsNewN2I, * pEntry, * pEntry2, ** ppSpot; + int nBinsNew, Counter, e, clk; clk = clock(); // get the new table size @@ -192,12 +259,13 @@ clk = clock(); // rehash the entries from the old table Counter = 0; for ( e = 0; e < p->nBins; e++ ) + for ( pEntry = p->pBinsI2N[e], pEntry2 = pEntry? pEntry->pNextI2N : NULL; + pEntry; pEntry = pEntry2, pEntry2 = pEntry? pEntry->pNextI2N : NULL ) { - pEntry = p->pBinsI2N[e]; - if ( pEntry == NULL ) - continue; - Counter++; - +// pEntry = p->pBinsI2N[e]; +// if ( pEntry == NULL ) +// continue; +/* // hash it by ID for ( i = Nm_HashNumber(pEntry->ObjId, nBinsNew); pBinsNewI2N[i]; i = (i+1) % nBinsNew ) if ( pBinsNewI2N[i] == pEntry ) @@ -210,6 +278,16 @@ clk = clock(); assert( 0 ); assert( pBinsNewN2I[i] == NULL ); pBinsNewN2I[i] = pEntry; +*/ + ppSpot = pBinsNewI2N + Nm_HashNumber(pEntry->ObjId, nBinsNew); + pEntry->pNextI2N = *ppSpot; + *ppSpot = pEntry; + + ppSpot = pBinsNewN2I + Nm_HashString(pEntry->Name, nBinsNew); + pEntry->pNextN2I = *ppSpot; + *ppSpot = pEntry; + + Counter++; } assert( Counter == p->nEntries ); // printf( "Increasing the structural table size from %6d to %6d. ", p->nBins, nBinsNew ); @@ -220,10 +298,10 @@ clk = clock(); p->pBinsI2N = pBinsNewI2N; p->pBinsN2I = pBinsNewN2I; p->nBins = nBinsNew; +// Nm_ManProfile( p ); } - /**Function************************************************************* Synopsis [Returns the smallest prime larger than the number.] diff --git a/src/misc/vec/vecInt.h b/src/misc/vec/vecInt.h index 4f193cf2..4a97fc91 100644 --- a/src/misc/vec/vecInt.h +++ b/src/misc/vec/vecInt.h @@ -583,6 +583,28 @@ static inline int Vec_IntPushUnique( Vec_Int_t * p, int Entry ) /**Function************************************************************* + Synopsis [Returns the pointer to the next nWords entries in the vector.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline unsigned * Vec_IntFetch( Vec_Int_t * p, int nWords ) +{ + p->nSize += nWords; + if ( p->nSize > p->nCap ) + { +// Vec_IntGrow( p, 2 * p->nSize ); + return NULL; + } + return ((unsigned *)p->pArray) + p->nSize - nWords; +} + +/**Function************************************************************* + Synopsis [Returns the last entry and removes it from the list.] Description [] |