abc/src/bdd/cudd/cuddSubsetSP.c
/**Function********************************************************************

  Synopsis    [ Labels each node with its shortest distance from the root]

  Description [ Labels each node with its shortest distance from the root.
  This is done in a BFS search of the BDD. The nodes are processed
  in a queue implemented as pages(array) to reduce memory fragmentation.
  An entry is created for each node visited. The distance from the root
  to the node with the corresponding  parity is updated. The procedure
  is called recursively each recusion level handling nodes at a given
  level from the root.]


  SideEffects [Creates entries in the pathTable]

  SeeAlso     [CreatePathTable CreateBotDist]

******************************************************************************/
Function
Synopsis    [ Labels each node with its shortest distance from the root]

Description [ Labels each node with its shortest distance from the root.
This is done in a BFS search of the BDD. The nodes are processed
in a queue implemented as pages(array) to reduce memory fragmentation.
An entry is created for each node visited. The distance from the root
to the node with the corresponding  parity is updated. The procedure
is called recursively each recusion level handling nodes at a given
level from the root.]

SideEffects [Creates entries in the pathTable]


Function Synopsis [ Labels each node with its shortest distance from the root ] Description [ Labels each node with its shortest distance from the root . This is done in a BFS search of the BDD . The nodes are processed in a queue implemented as pages ( array ) to reduce memory fragmentation . An entry is created for each node visited . The distance from the root to the node with the corresponding parity is updated . The procedure is called recursively each recusion level handling nodes at a given level from the root . ] SideEffects [ Creates entries in the pathTable ]
static void
CreateTopDist(
  st__table * pathTable ,
  int  parentPage ,
  int  parentQueueIndex ,
  int  topLen ,
  DdNode ** childPage ,
  int  childQueueIndex ,
  int  numParents ,
  FILE *fp )
{
    NodeDist_t *nodeStat;
    DdNode *N, *Nv, *Nnv, *node, *child, *regChild;
    int  i;
    int processingDone, childrenCount;
#ifdef DD_DEBUG
    numCalls++;
    if ((queuePages[parentPage] == childPage) && (parentQueueIndex ==
                                                  childQueueIndex)) {
        fprintf(fp, "Should not happen that they are equal\n");
    }
    assert(queuePageIndex == childQueueIndex);
    assert(currentQueuePage == childPage);
#endif
    childrenCount = 0;
    while (numParents) {
        numParents--;
        if (parentQueueIndex == queuePageSize) {
            parentPage++;
            parentQueueIndex = 0;
        }
        node = *(queuePages[parentPage] + parentQueueIndex);
        parentQueueIndex++;
        N = Cudd_Regular(node);
        Nv = Cudd_T(N);
        Nnv = Cudd_E(N);
        Nv = Cudd_NotCond(Nv, Cudd_IsComplement(node));
        Nnv = Cudd_NotCond(Nnv, Cudd_IsComplement(node));
        processingDone = 2;
        while (processingDone) {
            if (processingDone == 2) {
                child = Nv;
            } else {
                child = Nnv;
            }
            regChild = Cudd_Regular(child);
            if (!Cudd_IsConstant(child)) {
                if (! st__lookup(pathTable, (const char *)regChild, (char **)&nodeStat)) {
                    if (nodeDistPageIndex == nodeDistPageSize)
                        ResizeNodeDistPages();
                    if (memOut) {
                        for (i = 0; i <= queuePage; i++) ABC_FREE(queuePages[i]);
                        ABC_FREE(queuePages);
                        st__free_table(pathTable);
                        return;
                    }
                    nodeStat = currentNodeDistPage + nodeDistPageIndex;
                    nodeDistPageIndex++;
                    nodeStat->oddTopDist = MAXSHORTINT;
                    nodeStat->evenTopDist = MAXSHORTINT;
                    nodeStat->evenBotDist = MAXSHORTINT;
                    nodeStat->oddBotDist = MAXSHORTINT;
                    nodeStat->regResult = NULL;
                    nodeStat->compResult = NULL;
                    if (Cudd_IsComplement(child)) {
                        nodeStat->oddTopDist = (DdHalfWord) topLen + 1;
                    } else {
                        nodeStat->evenTopDist = (DdHalfWord) topLen + 1;
                    }
                    if ( st__insert(pathTable, (char *)regChild,
                                  (char *)nodeStat) == st__OUT_OF_MEM) {
                        memOut = 1;
                        for (i = 0; i <= nodeDistPage; i++)
                            ABC_FREE(nodeDistPages[i]);
                        ABC_FREE(nodeDistPages);
                        for (i = 0; i <= queuePage; i++) ABC_FREE(queuePages[i]);
                        ABC_FREE(queuePages);
                        st__free_table(pathTable);
                        return;
                    }
                    if (queuePageIndex == queuePageSize) ResizeQueuePages();
                    if (memOut) {
                        for (i = 0; i <= nodeDistPage; i++)
                            ABC_FREE(nodeDistPages[i]);
                        ABC_FREE(nodeDistPages);
                        st__free_table(pathTable);
                        return;
                    }
                    *(currentQueuePage + queuePageIndex) = child;
                    queuePageIndex++;
                    childrenCount++;
                } else {
                    if (((Cudd_IsComplement(child)) && (nodeStat->oddTopDist ==
                          MAXSHORTINT)) || ((!Cudd_IsComplement(child)) &&
                                  (nodeStat->evenTopDist == MAXSHORTINT))) {
                        if (queuePageIndex == queuePageSize) ResizeQueuePages();
                        if (memOut) {
                            for (i = 0; i <= nodeDistPage; i++)
                                ABC_FREE(nodeDistPages[i]);
                            ABC_FREE(nodeDistPages);
                            st__free_table(pathTable);
                            return;
                        }
                        *(currentQueuePage + queuePageIndex) = child;
                        queuePageIndex++;
                        if (Cudd_IsComplement(child)) {
                            nodeStat->oddTopDist = (DdHalfWord) topLen + 1;
                        } else {
                            nodeStat->evenTopDist = (DdHalfWord) topLen + 1;
                        }
                        childrenCount++;
                    }
                } 
            } 
            processingDone--;
        } 
    }  
#ifdef DD_DEBUG
    assert(queuePages[parentPage] == childPage);
    assert(parentQueueIndex == childQueueIndex);
#endif
    if (childrenCount != 0) {
        topLen++;
        childPage = currentQueuePage;
        childQueueIndex = queuePageIndex;
        CreateTopDist(pathTable, parentPage, parentQueueIndex, topLen,
                      childPage, childQueueIndex, childrenCount, fp);
    }
    return;
}
static void CreateTopDist ( st__table * pathTable , int parentPage , int parentQueueIndex , int topLen , DdNode * * childPage , int childQueueIndex , int numParents , FILE * fp ) { NodeDist_t * nodeStat ; DdNode * N , * Nv , * Nnv , * node , * child , * regChild ; int i ; int processingDone , childrenCount ; #ifdef DD_DEBUG numCalls ++ ; if ( ( queuePages [ parentPage ] == childPage ) && ( parentQueueIndex == childQueueIndex ) ) { fprintf ( fp , " \n " ) ; } assert ( queuePageIndex == childQueueIndex ) ; assert ( currentQueuePage == childPage ) ; #endif childrenCount = 0 ; while ( numParents ) { numParents -- ; if ( parentQueueIndex == queuePageSize ) { parentPage ++ ; parentQueueIndex = 0 ; } node = * ( queuePages [ parentPage ] + parentQueueIndex ) ; parentQueueIndex ++ ; N = Cudd_Regular ( node ) ; Nv = Cudd_T ( N ) ; Nnv = Cudd_E ( N ) ; Nv = Cudd_NotCond ( Nv , Cudd_IsComplement ( node ) ) ; Nnv = Cudd_NotCond ( Nnv , Cudd_IsComplement ( node ) ) ; processingDone = 2 ; while ( processingDone ) { if ( processingDone == 2 ) { child = Nv ; } else { child = Nnv ; } regChild = Cudd_Regular ( child ) ; if ( ! Cudd_IsConstant ( child ) ) { if ( ! st__lookup ( pathTable , ( const char * ) regChild , ( char * * ) & nodeStat ) ) { if ( nodeDistPageIndex == nodeDistPageSize ) ResizeNodeDistPages ( ) ; if ( memOut ) { for ( i = 0 ; i <= queuePage ; i ++ ) ABC_FREE ( queuePages [ i ] ) ; ABC_FREE ( queuePages ) ; st__free_table ( pathTable ) ; return ; } nodeStat = currentNodeDistPage + nodeDistPageIndex ; nodeDistPageIndex ++ ; nodeStat -> oddTopDist = MAXSHORTINT ; nodeStat -> evenTopDist = MAXSHORTINT ; nodeStat -> evenBotDist = MAXSHORTINT ; nodeStat -> oddBotDist = MAXSHORTINT ; nodeStat -> regResult = NULL ; nodeStat -> compResult = NULL ; if ( Cudd_IsComplement ( child ) ) { nodeStat -> oddTopDist = ( DdHalfWord ) topLen + 1 ; } else { nodeStat -> evenTopDist = ( DdHalfWord ) topLen + 1 ; } if ( st__insert ( pathTable , ( char * ) regChild , ( char * ) nodeStat ) == st__OUT_OF_MEM ) { memOut = 1 ; for ( i = 0 ; i <= nodeDistPage ; i ++ ) ABC_FREE ( nodeDistPages [ i ] ) ; ABC_FREE ( nodeDistPages ) ; for ( i = 0 ; i <= queuePage ; i ++ ) ABC_FREE ( queuePages [ i ] ) ; ABC_FREE ( queuePages ) ; st__free_table ( pathTable ) ; return ; } if ( queuePageIndex == queuePageSize ) ResizeQueuePages ( ) ; if ( memOut ) { for ( i = 0 ; i <= nodeDistPage ; i ++ ) ABC_FREE ( nodeDistPages [ i ] ) ; ABC_FREE ( nodeDistPages ) ; st__free_table ( pathTable ) ; return ; } * ( currentQueuePage + queuePageIndex ) = child ; queuePageIndex ++ ; childrenCount ++ ; } else { if ( ( ( Cudd_IsComplement ( child ) ) && ( nodeStat -> oddTopDist == MAXSHORTINT ) ) || ( ( ! Cudd_IsComplement ( child ) ) && ( nodeStat -> evenTopDist == MAXSHORTINT ) ) ) { if ( queuePageIndex == queuePageSize ) ResizeQueuePages ( ) ; if ( memOut ) { for ( i = 0 ; i <= nodeDistPage ; i ++ ) ABC_FREE ( nodeDistPages [ i ] ) ; ABC_FREE ( nodeDistPages ) ; st__free_table ( pathTable ) ; return ; } * ( currentQueuePage + queuePageIndex ) = child ; queuePageIndex ++ ; if ( Cudd_IsComplement ( child ) ) { nodeStat -> oddTopDist = ( DdHalfWord ) topLen + 1 ; } else { nodeStat -> evenTopDist = ( DdHalfWord ) topLen + 1 ; } childrenCount ++ ; } } } processingDone -- ; } } #ifdef DD_DEBUG assert ( queuePages [ parentPage ] == childPage ) ; assert ( parentQueueIndex == childQueueIndex ) ; #endif if ( childrenCount != 0 ) { topLen ++ ; childPage = currentQueuePage ; childQueueIndex = queuePageIndex ; CreateTopDist ( pathTable , parentPage , parentQueueIndex , topLen , childPage , childQueueIndex , childrenCount , fp ) ; } return ; }
Function
Synopsis    [ Labels each node with its shortest distance from the root]
Function Synopsis [ Labels each node with its shortest distance from the root ]
/* hast table to store path lengths */ /* the pointer to the page on which the first parent in the queue is to be found. */ /* pointer to the first parent on the page */ /* current distance from the root */ /* pointer to the page on which the first child is to be added. */ /* pointer to the first child */ /* number of parents to process in this recursive call */ /* where to write messages */ /* assume this procedure comes in with only the root node*/ /* set queue index to the next available entry for addition */ /* set queue page to page of addition */ /* number children added to queue is initialized , needed for
     * numParents in the next call
     */ /* process all the nodes in this level */ /* a parent to process */ /* get its children */ /* processing the THEN and the ELSE children, the THEN
             * child first
             */ /* dont process if the child is a constant */ /* check is already visited, if not add a new entry in
                 * the path Table
                 */ /* if not in table, has never been visited */ /* create entry for table */ /* New entry for child in path Table is created here */ /* Initialize fields of the node data */ /* update the table entry element, the distance keeps
                     * track of the parity of the path from the root
                     */ /* insert entry element for  child in the table */ /* Create list element for this child to process its children.
                     * If this node has been processed already, then it appears
                     * in the path table and hence is never added to the list
                     * again.
                     */ /* if not been met in a path with this parity before */ /* put in list */ /* update the distance with the appropriate parity */ /* end of else (not found in st__table) */ /*end of if Not constant child */ /*end of while processing Nv, Nnv */ /*end of while numParents */