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

  Synopsis [Destroys the n most recently created subtables in a unique table.]

  Description [Destroys the n most recently created subtables in a unique
  table.  n should be positive. The subtables should not contain any live
  nodes, except the (isolated) projection function. The projection
  functions are freed.  Returns 1 if successful; 0 otherwise.]

  SideEffects [The variable map used for fast variable substitution is
  destroyed if it exists. In this case the cache is also cleared.]

  SeeAlso     [cuddInsertSubtables Cudd_SetVarMap]

******************************************************************************/
Function
Synopsis [Destroys the n most recently created subtables in a unique table.]

Description [Destroys the n most recently created subtables in a unique
table.  n should be positive. The subtables should not contain any live
nodes, except the (isolated) projection function. The projection
functions are freed.  Returns 1 if successful; 0 otherwise.]

SideEffects [The variable map used for fast variable substitution is
destroyed if it exists. In this case the cache is also cleared.]


Function Synopsis [ Destroys the n most recently created subtables in a unique table . ] Description [ Destroys the n most recently created subtables in a unique table . n should be positive . The subtables should not contain any live nodes except the ( isolated ) projection function . The projection functions are freed . Returns 1 if successful ; 0 otherwise . ] SideEffects [ The variable map used for fast variable substitution is destroyed if it exists . In this case the cache is also cleared . ]
int
cuddDestroySubtables(
  DdManager * unique,
  int  n)
{
    DdSubtable *subtables;
    DdNodePtr *nodelist;
    DdNodePtr *vars;
    int firstIndex, lastIndex;
    int index, level, newlevel;
    int lowestLevel;
    int shift;
    int found;
    if (n <= 0) return(0);
    if (n > unique->size) n = unique->size;
    subtables = unique->subtables;
    vars = unique->vars;
    firstIndex = unique->size - n;
    lastIndex  = unique->size;
    lowestLevel = unique->size;
    for (index = firstIndex; index < lastIndex; index++) {
        level = unique->perm[index];
        if (level < lowestLevel) lowestLevel = level;
        nodelist = subtables[level].nodelist;
        if (subtables[level].keys - subtables[level].dead != 1) return(0);
        if (vars[index]->ref != 1) {
            if (vars[index]->ref != DD_MAXREF) return(0);
            found = cuddFindParent(unique,vars[index]);
            if (found) {
                return(0);
            } else {
                vars[index]->ref = 1;
            }
        }
        Cudd_RecursiveDeref(unique,vars[index]);
    }
    (void) cuddGarbageCollect(unique,1);
    for (index = firstIndex; index < lastIndex; index++) {
        level = unique->perm[index];
        nodelist = subtables[level].nodelist;
#ifdef DD_DEBUG
        assert(subtables[level].keys == 0);
#endif
        ABC_FREE(nodelist);
        unique->memused -= sizeof(DdNodePtr) * subtables[level].slots;
        unique->slots -= subtables[level].slots;
        unique->dead -= subtables[level].dead;
    }
    shift = 1;
    for (level = lowestLevel + 1; level < unique->size; level++) {
        if (subtables[level].keys == 0) {
            shift++;
            continue;
        }
        newlevel = level - shift;
        subtables[newlevel].slots = subtables[level].slots;
        subtables[newlevel].shift = subtables[level].shift;
        subtables[newlevel].keys = subtables[level].keys;
        subtables[newlevel].maxKeys = subtables[level].maxKeys;
        subtables[newlevel].dead = subtables[level].dead;
        subtables[newlevel].nodelist = subtables[level].nodelist;
        index = unique->invperm[level];
        unique->perm[index] = newlevel;
        unique->invperm[newlevel]  = index;
        subtables[newlevel].bindVar = subtables[level].bindVar;
        subtables[newlevel].varType = subtables[level].varType;
        subtables[newlevel].pairIndex = subtables[level].pairIndex;
        subtables[newlevel].varHandled = subtables[level].varHandled;
        subtables[newlevel].varToBeGrouped = subtables[level].varToBeGrouped;
    }
    if (unique->map != NULL) {
        cuddCacheFlush(unique);
        ABC_FREE(unique->map);
        unique->map = NULL;
    }
    unique->minDead = (unsigned) (unique->gcFrac * (double) unique->slots);
    unique->size -= n;
    return(1);
}
int cuddDestroySubtables ( DdManager * unique , int n ) { DdSubtable * subtables ; DdNodePtr * nodelist ; DdNodePtr * vars ; int firstIndex , lastIndex ; int index , level , newlevel ; int lowestLevel ; int shift ; int found ; if ( n <= 0 ) return ( 0 ) ; if ( n > unique -> size ) n = unique -> size ; subtables = unique -> subtables ; vars = unique -> vars ; firstIndex = unique -> size - n ; lastIndex = unique -> size ; lowestLevel = unique -> size ; for ( index = firstIndex ; index < lastIndex ; index ++ ) { level = unique -> perm [ index ] ; if ( level < lowestLevel ) lowestLevel = level ; nodelist = subtables [ level ] . nodelist ; if ( subtables [ level ] . keys - subtables [ level ] . dead != 1 ) return ( 0 ) ; if ( vars [ index ] -> ref != 1 ) { if ( vars [ index ] -> ref != DD_MAXREF ) return ( 0 ) ; found = cuddFindParent ( unique , vars [ index ] ) ; if ( found ) { return ( 0 ) ; } else { vars [ index ] -> ref = 1 ; } } Cudd_RecursiveDeref ( unique , vars [ index ] ) ; } ( void ) cuddGarbageCollect ( unique , 1 ) ; for ( index = firstIndex ; index < lastIndex ; index ++ ) { level = unique -> perm [ index ] ; nodelist = subtables [ level ] . nodelist ; #ifdef DD_DEBUG assert ( subtables [ level ] . keys == 0 ) ; #endif ABC_FREE ( nodelist ) ; unique -> memused -= sizeof ( DdNodePtr ) * subtables [ level ] . slots ; unique -> slots -= subtables [ level ] . slots ; unique -> dead -= subtables [ level ] . dead ; } shift = 1 ; for ( level = lowestLevel + 1 ; level < unique -> size ; level ++ ) { if ( subtables [ level ] . keys == 0 ) { shift ++ ; continue ; } newlevel = level - shift ; subtables [ newlevel ] . slots = subtables [ level ] . slots ; subtables [ newlevel ] . shift = subtables [ level ] . shift ; subtables [ newlevel ] . keys = subtables [ level ] . keys ; subtables [ newlevel ] . maxKeys = subtables [ level ] . maxKeys ; subtables [ newlevel ] . dead = subtables [ level ] . dead ; subtables [ newlevel ] . nodelist = subtables [ level ] . nodelist ; index = unique -> invperm [ level ] ; unique -> perm [ index ] = newlevel ; unique -> invperm [ newlevel ] = index ; subtables [ newlevel ] . bindVar = subtables [ level ] . bindVar ; subtables [ newlevel ] . varType = subtables [ level ] . varType ; subtables [ newlevel ] . pairIndex = subtables [ level ] . pairIndex ; subtables [ newlevel ] . varHandled = subtables [ level ] . varHandled ; subtables [ newlevel ] . varToBeGrouped = subtables [ level ] . varToBeGrouped ; } if ( unique -> map != NULL ) { cuddCacheFlush ( unique ) ; ABC_FREE ( unique -> map ) ; unique -> map = NULL ; } unique -> minDead = ( unsigned ) ( unique -> gcFrac * ( double ) unique -> slots ) ; unique -> size -= n ; return ( 1 ) ; }
Function
Synopsis [Destroys the n most recently created subtables in a unique table.]
Function Synopsis [ Destroys the n most recently created subtables in a unique table . ]
/* Sanity check and set up. */ /* Check for nodes labeled by the variables being destroyed
    ** that may still be in use.  It is allowed to destroy a variable
    ** only if there are no such nodes. Also, find the lowest level
    ** among the variables being destroyed. This will make further
    ** processing more efficient.
    */ /* The projection function should be isolated. If the ref count
        ** is 1, everything is OK. If the ref count is saturated, then
        ** we need to make sure that there are no nodes pointing to it.
        ** As for the external references, we assume the application is
        ** responsible for them.
        */ /* Collect garbage, because we cannot afford having dead nodes pointing
    ** to the dead nodes in the subtables being destroyed.
    */ /* Here we know we can destroy our subtables. */ /* Here all subtables to be destroyed have their keys field == 0 and
    ** their hash tables have been freed.
    ** We now scan the subtables from level lowestLevel + 1 to level size - 1,
    ** shifting the subtables as required. We keep a running count of
    ** how many subtables have been moved, so that we know by how many
    ** positions each subtable should be shifted.
    */ /* Destroy the map. If a surviving variable is
    ** mapped to a dying variable, and the map were used again,
    ** an out-of-bounds access to unique->vars would result. */