Added new name manager and modified hierarchy manager to use it.

7 files changed, 769 insertions, 82 deletions

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 <time.h>
 
 #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,7 +149,8 @@ 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                         ///
@@ -154,6 +158,63 @@ extern void Au_NtkPrintStats( Au_Ntk_t * p );
 
 /**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.]
 
   Description []
@@ -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 <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#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                                ///
+////////////////////////////////////////////////////////////////////////
+