src/misc/nm/nmTable.c File Reference

#include "nmInt.h"
Include dependency graph for nmTable.c:

Go to the source code of this file.

Functions

static unsigned Nm_HashNumber (int Num, int TableSize)
static unsigned Nm_HashString (char *pName, int TableSize)
static void Nm_ManResize (Nm_Man_t *p)
int Nm_ManTableAdd (Nm_Man_t *p, Nm_Entry_t *pEntry)
int Nm_ManTableDelete (Nm_Man_t *p, int ObjId)
Nm_Entry_t * Nm_ManTableLookupId (Nm_Man_t *p, int ObjId)
Nm_Entry_t * Nm_ManTableLookupName (Nm_Man_t *p, char *pName, int Type)
void Nm_ManProfile (Nm_Man_t *p)
unsigned int Cudd_PrimeNm (unsigned int p)

Function Documentation

unsigned int Cudd_PrimeNm ( unsigned int  p  ) 

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

Synopsis [Returns the smallest prime larger than the number.]

Description []

SideEffects []

SeeAlso []

Definition at line 311 of file nmTable.c.

00312 {
00313     int i,pn;
00314 
00315     p--;
00316     do {
00317         p++;
00318         if (p&1) {
00319             pn = 1;
00320             i = 3;
00321             while ((unsigned) (i * i) <= p) {
00322                 if (p % i == 0) {
00323                     pn = 0;
00324                     break;
00325                 }
00326                 i += 2;
00327             }
00328         } else {
00329             pn = 0;
00330         }
00331     } while (!pn);
00332     return(p);
00333 
00334 } /* end of Cudd_Prime */

static unsigned Nm_HashNumber ( int  Num,
int  TableSize 
) [static]

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

FileName [nmTable.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Name manager.]

Synopsis [Hash table for the name manager.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id
nmTable.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

] DECLARATIONS ///

Definition at line 28 of file nmTable.c.

00029 {
00030     unsigned Key = 0;
00031     Key ^= ( Num        & 0xFF) * 7937;
00032     Key ^= ((Num >>  8) & 0xFF) * 2971;
00033     Key ^= ((Num >> 16) & 0xFF) * 911;
00034     Key ^= ((Num >> 24) & 0xFF) * 353;
00035     return Key % TableSize;
00036 }

static unsigned Nm_HashString ( char *  pName,
int  TableSize 
) [static]

Definition at line 39 of file nmTable.c.

00040 {
00041     static int s_Primes[10] = { 
00042         1291, 1699, 2357, 4177, 5147, 
00043         5647, 6343, 7103, 7873, 8147
00044     };
00045     unsigned i, Key = 0;
00046     for ( i = 0; pName[i] != '\0'; i++ )
00047         Key ^= s_Primes[i%10]*pName[i]*pName[i];
00048     return Key % TableSize;
00049 }

void Nm_ManProfile ( Nm_Man_t *  p  ) 

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

Synopsis [Profiles hash tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 219 of file nmTable.c.

00220 {
00221     Nm_Entry_t * pEntry;
00222     int Counter, e;
00223     printf( "I2N table: " );
00224     for ( e = 0; e < p->nBins; e++ )
00225     {
00226         Counter = 0;
00227         for ( pEntry = p->pBinsI2N[e]; pEntry; pEntry = pEntry->pNextI2N )
00228             Counter++;
00229         printf( "%d ", Counter );
00230     }
00231     printf( "\n" );
00232     printf( "N2I table: " );
00233     for ( e = 0; e < p->nBins; e++ )
00234     {
00235         Counter = 0;
00236         for ( pEntry = p->pBinsN2I[e]; pEntry; pEntry = pEntry->pNextN2I )
00237             Counter++;
00238         printf( "%d ", Counter );
00239     }
00240     printf( "\n" );
00241 }

void Nm_ManResize ( Nm_Man_t *  p  )  [static]

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

Synopsis [Resizes the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 254 of file nmTable.c.

00255 {
00256     Nm_Entry_t ** pBinsNewI2N, ** pBinsNewN2I, * pEntry, * pEntry2, ** ppSpot;
00257     int nBinsNew, Counter, e, clk;
00258 
00259 clk = clock();
00260     // get the new table size
00261     nBinsNew = Cudd_PrimeCopy( p->nGrowthFactor * p->nBins ); 
00262     // allocate a new array
00263     pBinsNewI2N = ALLOC( Nm_Entry_t *, nBinsNew );
00264     pBinsNewN2I = ALLOC( Nm_Entry_t *, nBinsNew );
00265     memset( pBinsNewI2N, 0, sizeof(Nm_Entry_t *) * nBinsNew );
00266     memset( pBinsNewN2I, 0, sizeof(Nm_Entry_t *) * nBinsNew );
00267     // rehash entries in Id->Name table
00268     Counter = 0;
00269     for ( e = 0; e < p->nBins; e++ )
00270         for ( pEntry = p->pBinsI2N[e], pEntry2 = pEntry? pEntry->pNextI2N : NULL; 
00271               pEntry; pEntry = pEntry2, pEntry2 = pEntry? pEntry->pNextI2N : NULL )
00272             {
00273                 ppSpot = pBinsNewI2N + Nm_HashNumber(pEntry->ObjId, nBinsNew);
00274                 pEntry->pNextI2N = *ppSpot;
00275                 *ppSpot = pEntry;
00276                 Counter++;
00277             }
00278     // rehash entries in Name->Id table
00279     for ( e = 0; e < p->nBins; e++ )
00280         for ( pEntry = p->pBinsN2I[e], pEntry2 = pEntry? pEntry->pNextN2I : NULL; 
00281               pEntry; pEntry = pEntry2, pEntry2 = pEntry? pEntry->pNextN2I : NULL )
00282             {
00283                 ppSpot = pBinsNewN2I + Nm_HashString(pEntry->Name, nBinsNew);
00284                 pEntry->pNextN2I = *ppSpot;
00285                 *ppSpot = pEntry;
00286             }
00287     assert( Counter == p->nEntries );
00288 //    printf( "Increasing the structural table size from %6d to %6d. ", p->nBins, nBinsNew );
00289 //    PRT( "Time", clock() - clk );
00290     // replace the table and the parameters
00291     free( p->pBinsI2N );
00292     free( p->pBinsN2I );
00293     p->pBinsI2N = pBinsNewI2N;
00294     p->pBinsN2I = pBinsNewN2I;
00295     p->nBins = nBinsNew;
00296 //    Nm_ManProfile( p );
00297 }

int Nm_ManTableAdd ( Nm_Man_t *  p,
Nm_Entry_t *  pEntry 
)

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

Synopsis [Adds an entry to two hash tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 68 of file nmTable.c.

00069 {
00070     Nm_Entry_t ** ppSpot, * pOther;
00071     // resize the tables if needed
00072     if ( p->nEntries > p->nBins * p->nSizeFactor )
00073         Nm_ManResize( p );
00074     // add the entry to the table Id->Name
00075     assert( Nm_ManTableLookupId(p, pEntry->ObjId) == NULL );
00076     ppSpot = p->pBinsI2N + Nm_HashNumber(pEntry->ObjId, p->nBins);
00077     pEntry->pNextI2N = *ppSpot;
00078     *ppSpot = pEntry;
00079     // check if an entry with the same name already exists
00080     if ( pOther = Nm_ManTableLookupName(p, pEntry->Name, -1) )
00081     {
00082         // entry with the same name already exists - add it to the ring
00083         pEntry->pNameSake = pOther->pNameSake? pOther->pNameSake : pOther;
00084         pOther->pNameSake = pEntry;
00085     }
00086     else
00087     {
00088         // entry with the same name does not exist - add it to the table
00089         ppSpot = p->pBinsN2I + Nm_HashString(pEntry->Name, p->nBins);
00090         pEntry->pNextN2I = *ppSpot;
00091         *ppSpot = pEntry;
00092     }
00093     // report successfully added entry
00094     p->nEntries++;
00095     return 1;
00096 }

int Nm_ManTableDelete ( Nm_Man_t *  p,
int  ObjId 
)

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

Synopsis [Deletes the entry from two hash tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 109 of file nmTable.c.

00110 {
00111     Nm_Entry_t ** ppSpot, * pEntry, * pPrev;
00112     int fRemoved;
00113     p->nEntries--;
00114     // remove the entry from the table Id->Name
00115     assert( Nm_ManTableLookupId(p, ObjId) != NULL );
00116     ppSpot = p->pBinsI2N + Nm_HashNumber(ObjId, p->nBins);
00117     while ( (*ppSpot)->ObjId != (unsigned)ObjId )
00118         ppSpot = &(*ppSpot)->pNextI2N;
00119     pEntry = *ppSpot; 
00120     *ppSpot = (*ppSpot)->pNextI2N;
00121     // remove the entry from the table Name->Id
00122     ppSpot = p->pBinsN2I + Nm_HashString(pEntry->Name, p->nBins);
00123     while ( *ppSpot && *ppSpot != pEntry )
00124         ppSpot = &(*ppSpot)->pNextN2I;
00125     // remember if we found this one in the list
00126     fRemoved = (*ppSpot != NULL);
00127     if ( *ppSpot )
00128     {
00129         assert( *ppSpot == pEntry );
00130         *ppSpot = (*ppSpot)->pNextN2I;
00131     }
00132     // quit if this entry has no namesakes
00133     if ( pEntry->pNameSake == NULL )
00134     {
00135         assert( fRemoved );
00136         return 1;
00137     }
00138     // remove entry from the ring of namesakes
00139     assert( pEntry->pNameSake != pEntry );
00140     for ( pPrev = pEntry; pPrev->pNameSake != pEntry; pPrev = pPrev->pNameSake );
00141     assert( !strcmp(pPrev->Name, pEntry->Name) );
00142     assert( pPrev->pNameSake == pEntry );
00143     if ( pEntry->pNameSake == pPrev ) // two entries in the ring
00144         pPrev->pNameSake = NULL;
00145     else
00146         pPrev->pNameSake = pEntry->pNameSake;
00147     // reinsert the ring back if we removed its connection with the list in the table
00148     if ( fRemoved )
00149     {
00150         assert( pPrev->pNextN2I == NULL );
00151         pPrev->pNextN2I = *ppSpot;
00152         *ppSpot = pPrev;
00153     }
00154     return 1;
00155 }

Nm_Entry_t* Nm_ManTableLookupId ( Nm_Man_t *  p,
int  ObjId 
)

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

Synopsis [Looks up the entry by ID.]

Description []

SideEffects []

SeeAlso []

Definition at line 168 of file nmTable.c.

00169 {
00170     Nm_Entry_t * pEntry;
00171     for ( pEntry = p->pBinsI2N[ Nm_HashNumber(ObjId, p->nBins) ]; pEntry; pEntry = pEntry->pNextI2N )
00172         if ( pEntry->ObjId == (unsigned)ObjId )
00173             return pEntry;
00174     return NULL;
00175 }

Nm_Entry_t* Nm_ManTableLookupName ( Nm_Man_t *  p,
char *  pName,
int  Type 
)

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

Synopsis [Looks up the entry by name and type.]

Description []

SideEffects []

SeeAlso []

Definition at line 188 of file nmTable.c.

00189 {
00190     Nm_Entry_t * pEntry, * pTemp;
00191     int Counter = 0;
00192     for ( pEntry = p->pBinsN2I[ Nm_HashString(pName, p->nBins) ]; pEntry; pEntry = pEntry->pNextN2I )
00193     {
00194         // check the entry itself
00195         if ( !strcmp(pEntry->Name, pName) && (Type == -1 || pEntry->Type == (unsigned)Type) )
00196             return pEntry;
00197         // if there is no namesakes, continue
00198         if ( pEntry->pNameSake == NULL )
00199             continue;
00200         // check the list of namesakes
00201         for ( pTemp = pEntry->pNameSake; pTemp != pEntry; pTemp = pTemp->pNameSake )
00202             if ( !strcmp(pTemp->Name, pName) && (Type == -1 || pTemp->Type == (unsigned)Type) )
00203                 return pTemp;
00204     }
00205     return NULL;
00206 }

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