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

  Synopsis    [Implementation of Rudell's sifting algorithm.]

  Description [Implementation of Rudell's sifting algorithm.
  Assumes that no dead nodes are present.
    <ol>
    <li> Order all the variables according to the number of entries
    in each unique table.
    <li> Sift the variable up and down, remembering each time the
    total size of the DD heap.
    <li> Select the best permutation.
    <li> Repeat 3 and 4 for all variables.
    </ol>
  Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

******************************************************************************/
Function
Synopsis    [Implementation of Rudell's sifting algorithm.]

Description [Implementation of Rudell's sifting algorithm.
Assumes that no dead nodes are present.

 Order all the variables according to the number of entries
in each unique table.
 Sift the variable up and down, remembering each time the
total size of the DD heap.
 Select the best permutation.
 Repeat 3 and 4 for all variables.

Returns 1 if successful; 0 otherwise.]


Function Synopsis [ Implementation of Rudell ' s sifting algorithm . ] Description [ Implementation of Rudell ' s sifting algorithm . Assumes that no dead nodes are present . Order all the variables according to the number of entries in each unique table . Sift the variable up and down remembering each time the total size of the DD heap . Select the best permutation . Repeat 3 and 4 for all variables . Returns 1 if successful ; 0 otherwise . ]
int
cuddSifting(
  DdManager * table,
  int  lower,
  int  upper)
{
    int i;
    int *var;
    int size;
    int x;
    int result;
#ifdef DD_STATS
    int previousSize;
#endif
    size = table->size;
    var = NULL;
    entry = ABC_ALLOC(int,size);
    if (entry == NULL) {
        table->errorCode = CUDD_MEMORY_OUT;
        goto cuddSiftingOutOfMem;
    }
    var = ABC_ALLOC(int,size);
    if (var == NULL) {
        table->errorCode = CUDD_MEMORY_OUT;
        goto cuddSiftingOutOfMem;
    }
    for (i = 0; i < size; i++) {
        x = table->perm[i];
        entry[i] = table->subtables[x].keys;
        var[i] = i;
    }
    qsort((void *)var,size,sizeof(int),(DD_QSFP)ddUniqueCompare);
    for (i = 0; i < ddMin(table->siftMaxVar,size); i++) {
        if (ddTotalNumberSwapping >= table->siftMaxSwap)
            break;
        x = table->perm[var[i]];
        if (x < lower || x > upper || table->subtables[x].bindVar == 1)
            continue;
#ifdef DD_STATS
        previousSize = table->keys - table->isolated;
#endif
        result = ddSiftingAux(table, x, lower, upper);
        if (!result) goto cuddSiftingOutOfMem;
#ifdef DD_STATS
        if (table->keys < (unsigned) previousSize + table->isolated) {
            (void) fprintf(table->out,"-");
        } else if (table->keys > (unsigned) previousSize + table->isolated) {
            (void) fprintf(table->out,"+");     
            (void) fprintf(table->err,"\nSize increased from %d to %d while sifting variable %d\n", previousSize, table->keys - table->isolated, var[i]);
        } else {
            (void) fprintf(table->out,"=");
        }
        fflush(table->out);
#endif
    }
    ABC_FREE(var);
    ABC_FREE(entry);
    return(1);
cuddSiftingOutOfMem:
    if (entry != NULL) ABC_FREE(entry);
    if (var != NULL) ABC_FREE(var);
    return(0);
}
int cuddSifting ( DdManager * table , int lower , int upper ) { int i ; int * var ; int size ; int x ; int result ; #ifdef DD_STATS int previousSize ; #endif size = table -> size ; var = NULL ; entry = ABC_ALLOC ( int , size ) ; if ( entry == NULL ) { table -> errorCode = CUDD_MEMORY_OUT ; goto cuddSiftingOutOfMem ; } var = ABC_ALLOC ( int , size ) ; if ( var == NULL ) { table -> errorCode = CUDD_MEMORY_OUT ; goto cuddSiftingOutOfMem ; } for ( i = 0 ; i < size ; i ++ ) { x = table -> perm [ i ] ; entry [ i ] = table -> subtables [ x ] . keys ; var [ i ] = i ; } qsort ( ( void * ) var , size , sizeof ( int ) , ( DD_QSFP ) ddUniqueCompare ) ; for ( i = 0 ; i < ddMin ( table -> siftMaxVar , size ) ; i ++ ) { if ( ddTotalNumberSwapping >= table -> siftMaxSwap ) break ; x = table -> perm [ var [ i ] ] ; if ( x < lower || x > upper || table -> subtables [ x ] . bindVar == 1 ) continue ; #ifdef DD_STATS previousSize = table -> keys - table -> isolated ; #endif result = ddSiftingAux ( table , x , lower , upper ) ; if ( ! result ) goto cuddSiftingOutOfMem ; #ifdef DD_STATS if ( table -> keys < ( unsigned ) previousSize + table -> isolated ) { ( void ) fprintf ( table -> out , " " ) ; } else if ( table -> keys > ( unsigned ) previousSize + table -> isolated ) { ( void ) fprintf ( table -> out , " " ) ; ( void ) fprintf ( table -> err , " \n \n " , previousSize , table -> keys - table -> isolated , var [ i ] ) ; } else { ( void ) fprintf ( table -> out , " " ) ; } fflush ( table -> out ) ; #endif } ABC_FREE ( var ) ; ABC_FREE ( entry ) ; return ( 1 ) ; cuddSiftingOutOfMem : if ( entry != NULL ) ABC_FREE ( entry ) ; if ( var != NULL ) ABC_FREE ( var ) ; return ( 0 ) ; }
Function
Synopsis    [Implementation of Rudell's sifting algorithm.]
Function Synopsis [ Implementation of Rudell ' s sifting algorithm . ]
/* Find order in which to sift variables. */ /* Now sift. */ /* should never happen */