Version abc60824

4 files changed, 128 insertions, 183 deletions

diff --git a/src/misc/nm/nm.h b/src/misc/nm/nm.h
index 9c96c8ba..89a9efac 100644
--- a/src/misc/nm/nm.h
+++ b/src/misc/nm/nm.h
@@ -25,6 +25,27 @@
 extern "C" {
 #endif
 
+/*
+    This manager is designed to store ID-to-name and name-to-ID mapping
+    for Boolean networks and And-Inverter Graphs.
+    
+    In a netlist, net names are unique. In this case, there is a one-to-one
+    mapping between IDs and names.
+
+    In a logic network, which do not have nets, several objects may have
+    the same name. For example, a latch output and a primary output.
+    Another example, a primary input and an input to a black box.
+    In this case, for each ID on an object there is only one name, 
+    but for each name may be several IDs of objects having this name.
+
+    The name manager maps ID-to-name uniquely but it allows one name to 
+    be mapped into several IDs. When a query to find an ID of the object
+    by its name is submitted, it is possible to specify the object type, 
+    which will help select one of several IDs. If the type is -1, and 
+    there is more than one object with the given name, any object with 
+    the given name is returned.
+*/
+
 ////////////////////////////////////////////////////////////////////////
 ///                          INCLUDES                                ///
 ////////////////////////////////////////////////////////////////////////
@@ -51,12 +72,11 @@ typedef struct Nm_Man_t_ Nm_Man_t;
 extern Nm_Man_t *   Nm_ManCreate( int nSize );
 extern void         Nm_ManFree( Nm_Man_t * p );
 extern int          Nm_ManNumEntries( Nm_Man_t * p );
-extern char *       Nm_ManStoreIdName( Nm_Man_t * p, int ObjId, char * pName, char * pSuffix );
+extern char *       Nm_ManStoreIdName( Nm_Man_t * p, int ObjId, int Type, char * pName, char * pSuffix );
 extern void         Nm_ManDeleteIdName( Nm_Man_t * p, int ObjId );
 extern char *       Nm_ManCreateUniqueName( Nm_Man_t * p, int ObjId );
 extern char *       Nm_ManFindNameById( Nm_Man_t * p, int ObjId );
-extern int          Nm_ManFindIdByName( Nm_Man_t * p, char * pName, int * pSecond );
-extern void         Nm_ManPrintTables( Nm_Man_t * p );
+extern int          Nm_ManFindIdByName( Nm_Man_t * p, char * pName, int Type );
 extern Vec_Int_t *  Nm_ManReturnNameIds( Nm_Man_t * p );
 
 #ifdef __cplusplus
diff --git a/src/misc/nm/nmApi.c b/src/misc/nm/nmApi.c
index 120dbe91..f7bb0fe7 100644
--- a/src/misc/nm/nmApi.c
+++ b/src/misc/nm/nmApi.c
@@ -46,7 +46,7 @@ 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   = 2; // determined how much larger the table should be compared to data in it
+    p->nSizeFactor   = 2; // determined the limit on the grow of data before the table resizes
     p->nGrowthFactor = 3; // determined how much the table grows after resizing
     // allocate and clean the bins
     p->nBins = Cudd_PrimeNm(nSize);
@@ -106,29 +106,23 @@ int Nm_ManNumEntries( Nm_Man_t * p )
   SeeAlso     []
 
 ***********************************************************************/
-char * Nm_ManStoreIdName( Nm_Man_t * p, int ObjId, char * pName, char * pSuffix )
+char * Nm_ManStoreIdName( Nm_Man_t * p, int ObjId, int Type, char * pName, char * pSuffix )
 {
-    Nm_Entry_t * pEntry, * pEntry2;
+    Nm_Entry_t * pEntry;
     int RetValue, nEntrySize;
+    // check if the object with this ID is already stored
     if ( pEntry = Nm_ManTableLookupId(p, ObjId) )
     {
-        if ( strcmp(pEntry->Name, pName) == 0 )
-            printf( "Nm_ManStoreIdName(): Entry with the same ID and name already exists.\n" );
-        else
-            printf( "Nm_ManStoreIdName(): Entry with the same ID and different name already exists.\n" );
-        return NULL;
-    }
-    if ( pSuffix == NULL && (pEntry = Nm_ManTableLookupName(p, pName, &pEntry2)) && pEntry2 )
-    {
-        printf( "Nm_ManStoreIdName(): Two entries with the same name already exist.\n" );
+        printf( "Nm_ManStoreIdName(): Entry with the same ID already exists.\n" );
         return NULL;
     }
-    // create the entry
+    // create a new entry
     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;
+    pEntry->Type = Type;
     sprintf( pEntry->Name, "%s%s", pName, pSuffix? pSuffix : "" );
     // add the entry to the hash table
     RetValue = Nm_ManTableAdd( p, pEntry );
@@ -158,7 +152,7 @@ void Nm_ManDeleteIdName( Nm_Man_t * p, int ObjId )
         return;
     }
     // remove entry from the table
-    Nm_ManTableDelete( p, pEntry );
+    Nm_ManTableDelete( p, ObjId );
 }
 
 
@@ -167,7 +161,7 @@ void Nm_ManDeleteIdName( Nm_Man_t * p, int ObjId )
   Synopsis    [Finds a unique name for the node.]
 
   Description [If the name exists, tries appending numbers to it until 
-  it becomes unique.]
+  it becomes unique. The name is not added to the table.]
                
   SideEffects []
 
@@ -182,9 +176,9 @@ char * Nm_ManCreateUniqueName( Nm_Man_t * p, int ObjId )
     if ( pEntry = Nm_ManTableLookupId(p, ObjId) )
         return pEntry->Name;
     sprintf( NameStr, "[%d]", ObjId );
-    for ( i = 1; Nm_ManTableLookupName(p, NameStr, NULL); i++ )
+    for ( i = 1; Nm_ManTableLookupName(p, NameStr, -1); i++ )
         sprintf( NameStr, "[%d]_%d", ObjId, i );
-    return Nm_ManStoreIdName( p, ObjId, NameStr, NULL );
+    return NameStr;
 }
 
 /**Function*************************************************************
@@ -218,69 +212,14 @@ char * Nm_ManFindNameById( Nm_Man_t * p, int ObjId )
   SeeAlso     []
 
 ***********************************************************************/
-int Nm_ManFindIdByName( Nm_Man_t * p, char * pName, int * pSecond )
+int Nm_ManFindIdByName( Nm_Man_t * p, char * pName, int Type )
 {
-    Nm_Entry_t * pEntry, * pEntry2;
-    if ( pEntry = Nm_ManTableLookupName(p, pName, &pEntry2) )
-    {
-        if ( pSecond )
-            *pSecond = pEntry2? pEntry2->ObjId : -1;
+    Nm_Entry_t * pEntry;
+    if ( pEntry = Nm_ManTableLookupName(p, pName, Type) )
         return pEntry->ObjId;
-    }
     return -1;
 }
 
-
-/**Function*************************************************************
-
-  Synopsis    [Prints distribution of entries in the bins.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-void Nm_ManPrintTables( Nm_Man_t * p )
-{
-    int i, Counter;
-
-    // rehash the entries from the old table
-    Counter = 0;
-    printf( "Int2Name: " );
-    for ( i = 0; i < p->nBins; i++ )
-    {
-        if ( Counter == 0 && p->pBinsI2N[i] == NULL )
-            continue;
-        if ( p->pBinsI2N[i] )
-            Counter++;
-        else
-        {
-            printf( "%d ", Counter );
-            Counter = 0;
-        }
-    }
-    printf( "\n" );
-
-    // rehash the entries from the old table
-    Counter = 0;
-    printf( "Name2Int: " );
-    for ( i = 0; i < p->nBins; i++ )
-    {
-        if ( Counter == 0 && p->pBinsN2I[i] == NULL )
-            continue;
-        if ( p->pBinsN2I[i] )
-            Counter++;
-        else
-        {
-            printf( "%d ", Counter );
-            Counter = 0;
-        }
-    }
-    printf( "\n" );
-}
-
 /**Function*************************************************************
 
   Synopsis    [Return the IDs of objects with names.]
diff --git a/src/misc/nm/nmInt.h b/src/misc/nm/nmInt.h
index 8356a4cb..028316e1 100644
--- a/src/misc/nm/nmInt.h
+++ b/src/misc/nm/nmInt.h
@@ -44,9 +44,11 @@ extern "C" {
 typedef struct Nm_Entry_t_ Nm_Entry_t;
 struct Nm_Entry_t_
 {
-    int              ObjId;         // object ID
+    unsigned         Type   :  4;   // object type
+    unsigned         ObjId  : 28;   // 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
+    Nm_Entry_t *     pNameSake;     // the next entry with the same name
     char             Name[0];       // name of the object
 };
 
@@ -71,9 +73,9 @@ struct Nm_Man_t_
 
 /*=== nmTable.c ==========================================================*/
 extern int              Nm_ManTableAdd( Nm_Man_t * p, Nm_Entry_t * pEntry );
-extern int              Nm_ManTableDelete( Nm_Man_t * p, Nm_Entry_t * pEntry );
+extern int              Nm_ManTableDelete( Nm_Man_t * p, int ObjId );
 extern Nm_Entry_t *     Nm_ManTableLookupId( Nm_Man_t * p, int ObjId );
-extern Nm_Entry_t *     Nm_ManTableLookupName( Nm_Man_t * p, char * pName, Nm_Entry_t ** ppSecond );
+extern Nm_Entry_t *     Nm_ManTableLookupName( Nm_Man_t * p, char * pName, int Type );
 extern unsigned int     Cudd_PrimeNm( unsigned int p );
 
 #ifdef __cplusplus
diff --git a/src/misc/nm/nmTable.c b/src/misc/nm/nmTable.c
index 4eeaf610..b209becd 100644
--- a/src/misc/nm/nmTable.c
+++ b/src/misc/nm/nmTable.c
@@ -67,37 +67,29 @@ static void Nm_ManResize( Nm_Man_t * p );
 ***********************************************************************/
 int Nm_ManTableAdd( Nm_Man_t * p, Nm_Entry_t * pEntry )
 {
-    Nm_Entry_t ** ppSpot;
-//    int i;
+    Nm_Entry_t ** ppSpot, * pOther;
     // resize the tables if needed
-//    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 )
-            return 0;
-    assert( p->pBinsI2N[i] == NULL );
-    p->pBinsI2N[i] = pEntry;
-    // hash it by Name
-    for ( i = Nm_HashString(pEntry->Name, p->nBins); p->pBinsN2I[i]; i = (i+1) % p->nBins )
-        if ( p->pBinsN2I[i] == pEntry )
-            return 0;
-    assert( p->pBinsN2I[i] == NULL );
-    p->pBinsN2I[i] = pEntry;
-*/
+    // add the entry to the table Id->Name
+    assert( Nm_ManTableLookupId(p, pEntry->ObjId) == NULL );
     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;
-
+    // check if an entry with the same name already exists
+    if ( pOther = Nm_ManTableLookupName(p, pEntry->Name, -1) )
+    {
+        // entry with the same name already exists - add it to the ring
+        pEntry->pNameSake = pOther->pNameSake? pOther->pNameSake : pOther;
+        pOther->pNameSake = pEntry;
+    }
+    else
+    {
+        // entry with the same name does not exist - add it to the table
+        ppSpot = p->pBinsN2I + Nm_HashString(pEntry->Name, p->nBins);
+        pEntry->pNextN2I = *ppSpot;
+        *ppSpot = pEntry;
+    }
     // report successfully added entry
     p->nEntries++;
     return 1;
@@ -114,10 +106,51 @@ int Nm_ManTableAdd( Nm_Man_t * p, Nm_Entry_t * pEntry )
   SeeAlso     []
 
 ***********************************************************************/
-int Nm_ManTableDelete( Nm_Man_t * p, Nm_Entry_t * pEntry )
+int Nm_ManTableDelete( Nm_Man_t * p, int ObjId )
 {
-    assert( 0 );
-    return 0;
+    Nm_Entry_t ** ppSpot, * pEntry, * pPrev;
+    int fRemoved;
+    // remove the entry from the table Id->Name
+    assert( Nm_ManTableLookupId(p, ObjId) != NULL );
+    ppSpot = p->pBinsI2N + Nm_HashNumber(ObjId, p->nBins);
+    while ( (*ppSpot)->ObjId != (unsigned)ObjId )
+        ppSpot = &(*ppSpot)->pNextI2N;
+    pEntry = *ppSpot; 
+    *ppSpot = (*ppSpot)->pNextI2N;
+    // remove the entry from the table Name->Id
+    ppSpot = p->pBinsN2I + Nm_HashString(pEntry->Name, p->nBins);
+    while ( *ppSpot && *ppSpot != pEntry )
+        ppSpot = &(*ppSpot)->pNextN2I;
+    // remember if we found this one in the list
+    fRemoved = (*ppSpot != NULL);
+    if ( *ppSpot )
+    {
+        assert( *ppSpot == pEntry );
+        *ppSpot = (*ppSpot)->pNextN2I;
+    }
+    // quit if this entry has no namesakes
+    if ( pEntry->pNameSake == NULL )
+    {
+        assert( fRemoved );
+        return 1;
+    }
+    // remove entry from the ring of namesakes
+    assert( pEntry->pNameSake != pEntry );
+    for ( pPrev = pEntry; pPrev->pNameSake != pEntry; pPrev = pPrev->pNameSake );
+    assert( !strcmp(pPrev->Name, pEntry->Name) );
+    assert( pPrev->pNameSake == pEntry );
+    if ( pEntry->pNameSake == pPrev ) // two entries in the ring
+        pPrev->pNameSake = NULL;
+    else
+        pPrev->pNameSake = pEntry->pNameSake;
+    // reinsert the ring back if we removed its connection with the list in the table
+    if ( fRemoved )
+    {
+        assert( pPrev->pNextN2I == NULL );
+        pPrev->pNextN2I = *ppSpot;
+        *ppSpot = pPrev;
+    }
+    return 1;
 }
 
 /**Function*************************************************************
@@ -134,21 +167,15 @@ int Nm_ManTableDelete( Nm_Man_t * p, Nm_Entry_t * pEntry )
 Nm_Entry_t * Nm_ManTableLookupId( Nm_Man_t * p, int ObjId )
 {
     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 )
+        if ( pEntry->ObjId == (unsigned)ObjId )
             return pEntry;
     return NULL;
 }
 
 /**Function*************************************************************
 
-  Synopsis    [Looks up the entry by name. May return two entries.]
+  Synopsis    [Looks up the entry by name and type.]
 
   Description []
                
@@ -157,42 +184,14 @@ Nm_Entry_t * Nm_ManTableLookupId( Nm_Man_t * p, int ObjId )
   SeeAlso     []
 
 ***********************************************************************/
-Nm_Entry_t * Nm_ManTableLookupName( Nm_Man_t * p, char * pName, Nm_Entry_t ** ppSecond )
+Nm_Entry_t * Nm_ManTableLookupName( Nm_Man_t * p, char * pName, int Type )
 {
-    Nm_Entry_t * pFirst, * pSecond, * pEntry;
+    Nm_Entry_t * 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 )
-        {
-            if ( pFirst == NULL )
-                pFirst = p->pBinsN2I[i];
-            else if ( pSecond == NULL )
-                pSecond = p->pBinsN2I[i];
-            else
-                assert( 0 ); // name appears more than 2 times
-        }
-        else
-            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;
+        if ( !strcmp(pEntry->Name, pName) && (Type == -1 || pEntry->Type == (unsigned)Type) )
+            return pEntry;
+    return pEntry;
 }
 
 /**Function*************************************************************
@@ -230,8 +229,6 @@ void Nm_ManProfile( Nm_Man_t * p )
     printf( "\n" );
 }
 
-
-
 /**Function*************************************************************
 
   Synopsis    [Resizes the table.]
@@ -256,39 +253,26 @@ clk = clock();
     pBinsNewN2I = ALLOC( Nm_Entry_t *, nBinsNew );
     memset( pBinsNewI2N, 0, sizeof(Nm_Entry_t *) * nBinsNew );
     memset( pBinsNewN2I, 0, sizeof(Nm_Entry_t *) * nBinsNew );
-    // rehash the entries from the old table
+    // rehash entries in Id->Name 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;
-/*
-        // hash it by ID
-        for ( i = Nm_HashNumber(pEntry->ObjId, nBinsNew); pBinsNewI2N[i]; i = (i+1) % nBinsNew )
-            if ( pBinsNewI2N[i] == pEntry )
-                assert( 0 );
-        assert( pBinsNewI2N[i] == NULL );
-        pBinsNewI2N[i] = pEntry;
-        // hash it by Name
-        for ( i = Nm_HashString(pEntry->Name, nBinsNew); pBinsNewN2I[i]; i = (i+1) % nBinsNew )
-            if ( pBinsNewN2I[i] == pEntry )
-                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++;
-    }
+        for ( pEntry = p->pBinsI2N[e], pEntry2 = pEntry? pEntry->pNextI2N : NULL; 
+              pEntry; pEntry = pEntry2, pEntry2 = pEntry? pEntry->pNextI2N : NULL )
+            {
+                ppSpot = pBinsNewI2N + Nm_HashNumber(pEntry->ObjId, nBinsNew);
+                pEntry->pNextI2N = *ppSpot;
+                *ppSpot = pEntry;
+                Counter++;
+            }
+    // rehash entries in Name->Id table
+    for ( e = 0; e < p->nBins; e++ )
+        for ( pEntry = p->pBinsN2I[e], pEntry2 = pEntry? pEntry->pNextN2I : NULL; 
+              pEntry; pEntry = pEntry2, pEntry2 = pEntry? pEntry->pNextN2I : NULL )
+            {
+                ppSpot = pBinsNewN2I + Nm_HashString(pEntry->Name, nBinsNew);
+                pEntry->pNextN2I = *ppSpot;
+                *ppSpot = pEntry;
+            }
     assert( Counter == p->nEntries );
 //    printf( "Increasing the structural table size from %6d to %6d. ", p->nBins, nBinsNew );
 //    PRT( "Time", clock() - clk );