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

  Synopsis    [Swaps two groups and records the move.]

  Description [Swaps two groups and records the move. Returns the
  number of keys in the DD table in case of success; 0 otherwise.]

  SideEffects [None]

******************************************************************************/
Function
Synopsis    [Swaps two groups and records the move.]

Description [Swaps two groups and records the move. Returns the
number of keys in the DD table in case of success; 0 otherwise.]


Function Synopsis [ Swaps two groups and records the move . ] Description [ Swaps two groups and records the move . Returns the number of keys in the DD table in case of success ; 0 otherwise . ]
static int
ddGroupMove(
  DdManager * table,
  int  x,
  int  y,
  Move ** moves)
{
    Move *move;
    int  size;
    int  i,j,xtop,xbot,xsize,ytop,ybot,ysize,newxtop;
    int  swapx = -1,swapy = -1;
#if defined(DD_DEBUG) && defined(DD_VERBOSE)
    int  initialSize,bestSize;
#endif
#ifdef DD_DEBUG
    assert(x < y);
#endif
    xbot = x;
    xtop = table->subtables[x].next;
    xsize = xbot - xtop + 1;
    ybot = y;
    while ((unsigned) ybot < table->subtables[ybot].next)
        ybot = table->subtables[ybot].next;
    ytop = y;
    ysize = ybot - ytop + 1;
#if defined(DD_DEBUG) && defined(DD_VERBOSE)
    initialSize = bestSize = table->keys - table->isolated;
#endif
    for (i = 1; i <= ysize; i++) {
        for (j = 1; j <= xsize; j++) {
            size = cuddSwapInPlace(table,x,y);
            if (size == 0) goto ddGroupMoveOutOfMem;
#if defined(DD_DEBUG) && defined(DD_VERBOSE)
            if (size < bestSize)
                bestSize = size;
#endif
            swapx = x; swapy = y;
            y = x;
            x = cuddNextLow(table,y);
        }
        y = ytop + i;
        x = cuddNextLow(table,y);
    }
#if defined(DD_DEBUG) && defined(DD_VERBOSE)
    if ((bestSize < initialSize) && (bestSize < size))
        (void) fprintf(table->out,"Missed local minimum: initialSize:%d  bestSize:%d  finalSize:%d\n",initialSize,bestSize,size);
#endif
    y = xtop; 
    for (i = 0; i < ysize - 1; i++) {
        table->subtables[y].next = cuddNextHigh(table,y);
        y = cuddNextHigh(table,y);
    }
    table->subtables[y].next = xtop; 
    x = cuddNextHigh(table,y);
    newxtop = x;
    for (i = 0; i < xsize - 1; i++) {
        table->subtables[x].next = cuddNextHigh(table,x);
        x = cuddNextHigh(table,x);
    }
    table->subtables[x].next = newxtop; 
#ifdef DD_DEBUG
    if (pr > 0) (void) fprintf(table->out,"ddGroupMove:\n");
#endif
    move = (Move *) cuddDynamicAllocNode(table);
    if (move == NULL) goto ddGroupMoveOutOfMem;
    move->x = swapx;
    move->y = swapy;
    move->flags = MTR_DEFAULT;
    move->size = table->keys - table->isolated;
    move->next = *moves;
    *moves = move;
    return(table->keys - table->isolated);
ddGroupMoveOutOfMem:
    while (*moves != NULL) {
        move = (*moves)->next;
        cuddDeallocMove(table, *moves);
        *moves = move;
    }
    return(0);
}
static int ddGroupMove ( DdManager * table , int x , int y , Move * * moves ) { Move * move ; int size ; int i , j , xtop , xbot , xsize , ytop , ybot , ysize , newxtop ; int swapx = -1 , swapy = -1 ; #if defined ( DD_DEBUG ) && defined ( DD_VERBOSE ) int initialSize , bestSize ; #endif #ifdef DD_DEBUG assert ( x < y ) ; #endif xbot = x ; xtop = table -> subtables [ x ] . next ; xsize = xbot - xtop + 1 ; ybot = y ; while ( ( unsigned ) ybot < table -> subtables [ ybot ] . next ) ybot = table -> subtables [ ybot ] . next ; ytop = y ; ysize = ybot - ytop + 1 ; #if defined ( DD_DEBUG ) && defined ( DD_VERBOSE ) initialSize = bestSize = table -> keys - table -> isolated ; #endif for ( i = 1 ; i <= ysize ; i ++ ) { for ( j = 1 ; j <= xsize ; j ++ ) { size = cuddSwapInPlace ( table , x , y ) ; if ( size == 0 ) goto ddGroupMoveOutOfMem ; #if defined ( DD_DEBUG ) && defined ( DD_VERBOSE ) if ( size < bestSize ) bestSize = size ; #endif swapx = x ; swapy = y ; y = x ; x = cuddNextLow ( table , y ) ; } y = ytop + i ; x = cuddNextLow ( table , y ) ; } #if defined ( DD_DEBUG ) && defined ( DD_VERBOSE ) if ( ( bestSize < initialSize ) && ( bestSize < size ) ) ( void ) fprintf ( table -> out , " \n " , initialSize , bestSize , size ) ; #endif y = xtop ; for ( i = 0 ; i < ysize - 1 ; i ++ ) { table -> subtables [ y ] . next = cuddNextHigh ( table , y ) ; y = cuddNextHigh ( table , y ) ; } table -> subtables [ y ] . next = xtop ; x = cuddNextHigh ( table , y ) ; newxtop = x ; for ( i = 0 ; i < xsize - 1 ; i ++ ) { table -> subtables [ x ] . next = cuddNextHigh ( table , x ) ; x = cuddNextHigh ( table , x ) ; } table -> subtables [ x ] . next = newxtop ; #ifdef DD_DEBUG if ( pr > 0 ) ( void ) fprintf ( table -> out , " \n " ) ; #endif move = ( Move * ) cuddDynamicAllocNode ( table ) ; if ( move == NULL ) goto ddGroupMoveOutOfMem ; move -> x = swapx ; move -> y = swapy ; move -> flags = MTR_DEFAULT ; move -> size = table -> keys - table -> isolated ; move -> next = * moves ; * moves = move ; return ( table -> keys - table -> isolated ) ; ddGroupMoveOutOfMem : while ( * moves != NULL ) { move = ( * moves ) -> next ; cuddDeallocMove ( table , * moves ) ; * moves = move ; } return ( 0 ) ; }
Function
Synopsis    [Swaps two groups and records the move.]
Function Synopsis [ Swaps two groups and records the move . ]
/* We assume that x < y */ /* Find top, bottom, and size for the two groups. */ /* Sift the variables of the second group up through the first group */ /* fix groups */ /* ytop is now where xtop used to be */ /* y is bottom of its group, join */ /* it to top of its group */ /* x is bottom of its group, join */ /* it to top of its group */ /* Store group move */