shhash.c

主要进行大规模的电路综合

/**CFile****************************************************************

  FileName    [shHash.c]

  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]

  Synopsis    [Hashing the two-input AND gates.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - February 1, 2003.]

  Revision    [$Id: shHash.c,v 1.2 2003/05/27 23:14:51 alanmi Exp $]

***********************************************************************/

#include "shInt.h"

////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

struct ShTableStruct
{
    Sh_Node_t ** pTable;         // the table of entries
    int          nTableSize;     // the size of the hash table
    int          nNodes;         // the total number of AND nodes in the table
    Sh_Node_t *  pListUnique;    // the list of unique nodes
    int          nListUnique;    // the number of unique nodes
};

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFITIONS                           ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Sh_Table_t * Sh_TableAlloc( int nTableSize )
{
    Sh_Table_t * p;
    p = ALLOC( Sh_Table_t, 1 );
    memset( p, 0, sizeof(Sh_Table_t) );
    p->pTable = ALLOC( Sh_Node_t *, nTableSize );
    memset( p->pTable, 0, sizeof(Sh_Node_t *) * nTableSize );
    p->nTableSize = nTableSize;
    return p;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sh_TableFree( Sh_Table_t * p )
{
#ifdef USE_SYSTEM_MEMORY_MANAGEMENT
    Sh_Node_t * pEnt, * pEnt2;
    int i;
    // delete var maps
    for ( i = 0; i < p->nTableSize; i++ )
        for ( pEnt = p->pTable[i], pEnt2 = pEnt? pEnt->pNext: NULL; 
            pEnt; pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL )
            {
                assert( pEnt->nRefs == 0 );
                FREE( pEnt );
            }
    // delete the unique nodes
    for ( pEnt = p->pListUnique, pEnt2 = pEnt? pEnt->pNext: NULL; 
        pEnt; pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL )
        {
            assert( pEnt->nRefs == 0 );
            FREE( pEnt );
        }
#endif
    FREE( p->pTable );
    FREE( p );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Sh_Node_t * Sh_TableLookup( Sh_Manager_t * pMan, Sh_Node_t * pNode1, Sh_Node_t * pNode2 )
{
    Sh_Table_t * p = pMan->pTable;
    Sh_Node_t *  pNode;
    unsigned Key;

    if ( pNode1 == pNode2 )
        return pNode1;

    if ( pNode1 > pNode2 )
        return Sh_TableLookup( pMan, pNode2, pNode1 );

    Key = hashKey2( pNode1, pNode2, p->nTableSize );
    for ( pNode = p->pTable[Key]; pNode; pNode = pNode->pNext )
        if ( pNode->pOne == pNode1 && pNode->pTwo == pNode2 )
        {
            assert( Sh_Regular(pNode->pOne)->Num != Sh_Regular(pNode->pTwo)->Num );
            return pNode;
        }

    // create the new node
#ifdef USE_SYSTEM_MEMORY_MANAGEMENT
    pNode = ALLOC( Sh_Node_t, 1 );
#else
    pNode = (Sh_Node_t *)memManFixedEntryFetch( pMan->pMem );
#endif
//    memset( pNode, 0, sizeof(Sh_Node_t) );
    pNode->pOne = pNode1;   shNodeRef( pNode1 );
    pNode->pTwo = pNode2;   shNodeRef( pNode2 );
    pNode->TravId = 0;
    pNode->nRefs  = 0;
    pNode->fVar   = 0;
    pNode->pData  = 0;
    pNode->pData2 = 0;
    pNode->Num    = p->nNodes;
    assert( Sh_Regular(pNode1)->Num != Sh_Regular(pNode2)->Num );

    // add the node to the corresponding linked list in the table
    pNode->pNext = p->pTable[Key];
    p->pTable[Key] = pNode;

    p->nNodes++;
    return pNode;
}

/**Function*************************************************************

  Synopsis    [Creates a unique node equivalent to the given node.]

  Description [A unique node is used to represent the funtionality of the
  given node without overlapping with functionalities that hash into the
  same node. The unique nodes are essentially duplicates of some nodes
  in the table. The unique nodes are not in the table but in a special 
  linked list.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Sh_Node_t * Sh_TableInsertUnique( Sh_Manager_t * pMan, Sh_Node_t * pNode )
{
    Sh_Node_t * pNodeR, * pNodeUnique;
    bool fCompl;

    pNodeR = Sh_Regular(pNode);
    fCompl = Sh_IsComplement(pNode);

    // create the new node
#ifdef USE_SYSTEM_MEMORY_MANAGEMENT
    pNodeUnique = ALLOC( Sh_Node_t, 1 );
#else
    pNodeUnique = (Sh_Node_t *)memManFixedEntryFetch( pMan->pMem );
#endif
//    memset( pNodeUnique, 0, sizeof(Sh_Node_t) );
    pNodeUnique->pOne = pNodeR->pOne;   shNodeRef( pNodeR->pOne );
    pNodeUnique->pTwo = pNodeR->pTwo;   shNodeRef( pNodeR->pTwo );
    pNodeUnique->TravId = 0;
    pNodeUnique->nRefs  = 0;
    pNodeUnique->fVar   = 1; // make this node non-hashable
    pNodeUnique->pData  = 0;
    pNodeUnique->pData2 = 0;
    pNodeUnique->Num    = - pMan->pTable->nListUnique - 1;

    // add the unique node to the list of unique nodes
    pNodeUnique->pNext = pMan->pTable->pListUnique;
    pMan->pTable->pListUnique = pNodeUnique;

    pMan->pTable->nListUnique++;
    return Sh_NotCond( pNodeUnique, fCompl );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sh_TableReadNodeNum( Sh_Manager_t * p )
{
    return p->pTable->nNodes;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sh_TableReadNodeUniqueNum( Sh_Manager_t * p )
{
    return p->pTable->nListUnique;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sh_TableIncrementNodes( Sh_Manager_t * p )
{
    return p->pTable->nNodes++;
}

/**Function*************************************************************

  Synopsis    [Cleans the data fields of all nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sh_TableCleanNodes( Sh_Manager_t * pMan )
{
    Sh_Node_t * pEnt, * pEnt2;
    int i;
    // delete var maps
    for ( i = 0; i < pMan->pTable->nTableSize; i++ )
        for ( pEnt = pMan->pTable->pTable[i], pEnt2 = pEnt? pEnt->pNext: NULL; 
            pEnt; pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL )
                pEnt->pData = 0;
    // delete the unique nodes
    for ( pEnt = pMan->pTable->pListUnique, pEnt2 = pEnt? pEnt->pNext: NULL; 
        pEnt; pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL )
            pEnt->pData = 0;
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////