src/calBdd/calBlk.c File Reference

#include "calInt.h"
Include dependency graph for calBlk.c:

Go to the source code of this file.

Functions

static void AddBlock (Cal_Block b1, Cal_Block b2)
Cal_Block Cal_BddNewVarBlock (Cal_BddManager bddManager, Cal_Bdd variable, long length)
void Cal_BddVarBlockReorderable (Cal_BddManager bddManager, Cal_Block block, int reorderable)
long CalBddFindBlock (Cal_Block block, long index)
void CalBddBlockDelta (Cal_Block b, long delta)
Cal_Block CalBddShiftBlock (Cal_BddManager_t *bddManager, Cal_Block b, long index)
unsigned long CalBlockMemoryConsumption (Cal_Block block)
void CalFreeBlockRecursively (Cal_Block block)

Function Documentation

static void AddBlock ( Cal_Block  b1,
Cal_Block  b2 
) [static]

CFile***********************************************************************

FileName [calBlk.c]

PackageName [cal]

Synopsis [Routines for manipulating blocks of variables.]

Description [Routines for manipulating blocks of variables.]

Author [Rajeev K. Ranjan (rajeev@eecs.berkeley.edu). Modelled on the BDD package developed by David Long.] Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. All rights reserved.

Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

Revision [

Id
calBlk.c,v 1.1.1.2 1998/05/04 00:59:05 hsv Exp

]AutomaticStart

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 305 of file calBlk.c.

00306 {
00307   long i, j, k;
00308   Cal_Block start, end;
00309 
00310   if (b1->numChildren){
00311     i = CalBddFindBlock(b1, b2->firstIndex);
00312     start = b1->children[i];
00313     j = CalBddFindBlock(b1, b2->lastIndex);
00314     end = b1->children[j];
00315     if (i == j) {
00316       AddBlock(start, b2);
00317     }
00318     else {
00319       if (start->firstIndex != b2->firstIndex ||
00320           end->lastIndex != b2->lastIndex){
00321         CalBddFatalMessage("AddBlock: illegal block overlap");
00322       }
00323       b2->numChildren = j-i+1;
00324           b2->children = Cal_MemAlloc(Cal_Block, b2->numChildren); 
00325           for (k=0; k < b2->numChildren; ++k){
00326             b2->children[k] = b1->children[i+k];
00327       }
00328           b1->children[i] = b2;
00329           ++i;
00330           for (k=j+1; k < b1->numChildren; ++k, ++i){
00331             b1->children[i] = b1->children[k];
00332       }
00333           b1->numChildren -= (b2->numChildren-1);
00334           b1->children = (Cal_Block *)
00335           Cal_MemRealloc(Cal_Block, b1->children, b1->numChildren);
00336         }
00337   }
00338   else {
00339       /* b1 and b2 are blocks representing just single variables. */
00340       b1->numChildren = 1;
00341       b1->children = Cal_MemAlloc(Cal_Block, b1->numChildren); 
00342       b1->children[0] = b2;
00343       b2->numChildren = 0;
00344       b2->children = 0;
00345   }
00346 }

Cal_Block Cal_BddNewVarBlock ( Cal_BddManager  bddManager,
Cal_Bdd  variable,
long  length 
)

AutomaticEnd Function********************************************************************

Synopsis [Creates and returns a variable block used for controlling dynamic reordering.]

Description [The block is specified by passing the first variable and the length of the block. The "length" number of consecutive variables starting from "variable" are put in the block.]

SideEffects [A new block is created.]

SeeAlso []

Definition at line 89 of file calBlk.c.

00090 {
00091   Cal_Block b;
00092   Cal_Bdd_t calBdd = CalBddGetInternalBdd(bddManager, variable);
00093   
00094   if (CalBddTypeAux(bddManager, calBdd) != CAL_BDD_TYPE_POSVAR) {
00095     CalBddWarningMessage("Cal_BddNewVarBlock: second argument is not a positive variable\n"); 
00096     if (CalBddIsBddConst(calBdd)){
00097       return (Cal_Block) 0;
00098         }
00099   }
00100 
00101   /*b = CAL_BDD_NEW_REC(bddManager, Cal_Block_t);*/
00102   b = Cal_MemAlloc(Cal_Block_t, 1);
00103   b->reorderable = 0;
00104   b->firstIndex = bddManager->idToIndex[calBdd.bddId];
00105   if (length <= 0) {
00106     CalBddWarningMessage("Cal_BddNewVarBlock: invalid final argument");
00107     length = 1;
00108   }
00109   b->lastIndex = b->firstIndex + length - 1;
00110   if (b->lastIndex >= bddManager->numVars) {
00111     CalBddWarningMessage("Cal_BddNewVarBlock: range covers non-existent variables"); 
00112     b->lastIndex = bddManager->numVars - 1;
00113   }
00114   AddBlock(bddManager->superBlock, b);
00115   return (b);
00116 }

void Cal_BddVarBlockReorderable ( Cal_BddManager  bddManager,
Cal_Block  block,
int  reorderable 
)

Function********************************************************************

Synopsis [Sets the reoderability of a particular block.]

Description [If a block is reorderable, the child blocks are recursively involved in swapping.]

SideEffects [None.]

SeeAlso []

Definition at line 130 of file calBlk.c.

00132 {
00133   block->reorderable = reorderable;
00134 }

void CalBddBlockDelta ( Cal_Block  b,
long  delta 
)

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 185 of file calBlk.c.

00186 {
00187   long i;
00188   b->firstIndex += delta;
00189   b->lastIndex += delta;
00190   for (i=0; i < b->numChildren; ++i)
00191     CalBddBlockDelta(b->children[i], delta);
00192 }

long CalBddFindBlock ( Cal_Block  block,
long  index 
)

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 151 of file calBlk.c.

00152 {
00153   long i, j, k;
00154 
00155   i = 0;
00156   j = block->numChildren-1;
00157   while (i <= j) {
00158     k = (i+j)/2;
00159     if (block->children[k]->firstIndex <= index &&
00160         block->children[k]->lastIndex >= index){
00161       return (k);
00162     }
00163     if (block->children[k]->firstIndex > index){
00164       j = k-1;
00165     }
00166     else {
00167       i = k+1;
00168     }
00169   }
00170   return i;
00171 }

Cal_Block CalBddShiftBlock ( Cal_BddManager_t *  bddManager,
Cal_Block  b,
long  index 
)

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 207 of file calBlk.c.

00208 {
00209   long i, j;
00210   Cal_Block p;
00211 
00212   if (b->firstIndex >= index) {
00213     CalBddBlockDelta(b, 1l);
00214     return (b);
00215   }
00216   if (b->lastIndex < index) return (b);
00217   b->lastIndex++;
00218   i = CalBddFindBlock(b, index);
00219   if (i == b->numChildren || b->children[i]->firstIndex == index) {
00220     b->children = (Cal_Block *)
00221         Cal_MemRealloc(Cal_Block, b->children, b->numChildren+1);
00222     for (j = b->numChildren-1; j >= i; --j){
00223       b->children[j+1] = CalBddShiftBlock(bddManager, b->children[j], index);
00224     }
00225     b->numChildren++;
00226     /*p = CAL_BDD_NEW_REC(bddManager, Cal_Block_t);*/
00227     p = Cal_MemAlloc(Cal_Block_t, 1);
00228     p->reorderable = 0;
00229     p->firstIndex = index;
00230     p->lastIndex = index;
00231     p->numChildren = 0;
00232     p->children = 0;
00233     b->children[i] = p;
00234   }
00235   else{
00236     while (i < b->numChildren) {
00237       CalBddShiftBlock(bddManager, b->children[i], index);
00238       ++i;
00239     }
00240   }
00241   return (b);
00242 }

unsigned long CalBlockMemoryConsumption ( Cal_Block  block  ) 

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 255 of file calBlk.c.

00256 {
00257   unsigned long totalBytes = 0;
00258   int i;
00259   
00260   totalBytes += sizeof(Cal_Block);
00261   for (i=0; i<block->numChildren; i++){
00262     totalBytes += CalBlockMemoryConsumption(block->children[i]);
00263   }
00264   return totalBytes;
00265 }

void CalFreeBlockRecursively ( Cal_Block  block  ) 

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 278 of file calBlk.c.

00279 {
00280   int i;
00281   
00282   for (i=0; i<block->numChildren; i++){
00283     CalFreeBlockRecursively(block->children[i]);
00284   }
00285   Cal_MemFree(block->children);
00286   Cal_MemFree(block);
00287 }

Generated on Tue Jan 12 13:57:11 2010 for glu-2.2 by  doxygen 1.6.1