source: vis_dev/glu-2.3/src/calBdd/calBlk.c @ 88

Last change on this file since 88 was 13, checked in by cecile, 13 years ago

library glu 2.3
File size: 10.8 KB
RevLine 
[13]1/**CFile***********************************************************************
2
3  FileName    [calBlk.c]
4
5  PackageName [cal]
6
7  Synopsis    [Routines for manipulating blocks of variables.]
8
9  Description [Routines for manipulating blocks of variables.]
10
11  Author      [Rajeev K. Ranjan (rajeev@eecs.berkeley.edu). Modelled on the BDD package
12  developed by David Long.]
13  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
14  All rights reserved.
15
16  Permission is hereby granted, without written agreement and without license
17  or royalty fees, to use, copy, modify, and distribute this software and its
18  documentation for any purpose, provided that the above copyright notice and
19  the following two paragraphs appear in all copies of this software.
20
21  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
22  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
23  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
24  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
26  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
27  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
28  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
29  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
30  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
31
32  Revision    [$Id: calBlk.c,v 1.1.1.2 1998/05/04 00:59:05 hsv Exp $]
33
34******************************************************************************/
35
36#include "calInt.h"
37
38/*---------------------------------------------------------------------------*/
39/* Constant declarations                                                     */
40/*---------------------------------------------------------------------------*/
41
42/*---------------------------------------------------------------------------*/
43/* Type declarations                                                         */
44/*---------------------------------------------------------------------------*/
45
46/*---------------------------------------------------------------------------*/
47/* Stucture declarations                                                     */
48/*---------------------------------------------------------------------------*/
49
50/*---------------------------------------------------------------------------*/
51/* Variable declarations                                                     */
52/*---------------------------------------------------------------------------*/
53
54
55/*---------------------------------------------------------------------------*/
56/* Macro declarations                                                        */
57/*---------------------------------------------------------------------------*/
58
59/**AutomaticStart*************************************************************/
60
61/*---------------------------------------------------------------------------*/
62/* Static function prototypes                                                */
63/*---------------------------------------------------------------------------*/
64
65static void AddBlock(Cal_Block b1, Cal_Block b2);
66
67/**AutomaticEnd***************************************************************/
68
69/* BDD variable block routines */
70/*---------------------------------------------------------------------------*/
71/* Definition of exported functions                                          */
72/*---------------------------------------------------------------------------*/
73/**Function********************************************************************
74
75  Synopsis           [Creates and returns a variable block used for
76  controlling dynamic reordering.]
77
78  Description        [The block is specified by passing the first
79  variable and the length of the block. The "length" number of
80  consecutive variables starting from "variable" are put in the
81  block.]   
82
83  SideEffects        [A new block is created.]
84
85  SeeAlso            []
86
87******************************************************************************/
88Cal_Block
89Cal_BddNewVarBlock(Cal_BddManager bddManager, Cal_Bdd variable, long length)
90{
91  Cal_Block b;
92  Cal_Bdd_t calBdd = CalBddGetInternalBdd(bddManager, variable);
93 
94  if (CalBddTypeAux(bddManager, calBdd) != CAL_BDD_TYPE_POSVAR) {
95    CalBddWarningMessage("Cal_BddNewVarBlock: second argument is not a positive variable\n"); 
96    if (CalBddIsBddConst(calBdd)){
97      return (Cal_Block) 0;
98        }
99  }
100
101  /*b = CAL_BDD_NEW_REC(bddManager, Cal_Block_t);*/
102  b = Cal_MemAlloc(Cal_Block_t, 1);
103  b->reorderable = 0;
104  b->firstIndex = bddManager->idToIndex[calBdd.bddId];
105  if (length <= 0) {
106    CalBddWarningMessage("Cal_BddNewVarBlock: invalid final argument");
107    length = 1;
108  }
109  b->lastIndex = b->firstIndex + length - 1;
110  if (b->lastIndex >= bddManager->numVars) {
111    CalBddWarningMessage("Cal_BddNewVarBlock: range covers non-existent variables"); 
112    b->lastIndex = bddManager->numVars - 1;
113  }
114  AddBlock(bddManager->superBlock, b);
115  return (b);
116}
117/**Function********************************************************************
118
119  Synopsis           [Sets the reoderability of a particular block.]
120
121  Description        [If a block is reorderable, the child blocks are
122  recursively involved in swapping.]
123
124  SideEffects        [None.]
125
126  SeeAlso            []
127
128******************************************************************************/
129void
130Cal_BddVarBlockReorderable(Cal_BddManager bddManager, Cal_Block block,
131                           int reorderable)
132{
133  block->reorderable = reorderable;
134}
135
136/*---------------------------------------------------------------------------*/
137/* Definition of internal functions                                          */
138/*---------------------------------------------------------------------------*/
139/**Function********************************************************************
140
141  Synopsis           [required]
142
143  Description        [optional]
144
145  SideEffects        [required]
146
147  SeeAlso            [optional]
148
149******************************************************************************/
150long
151CalBddFindBlock(Cal_Block block, long index)
152{
153  long i, j, k;
154
155  i = 0;
156  j = block->numChildren-1;
157  while (i <= j) {
158    k = (i+j)/2;
159    if (block->children[k]->firstIndex <= index &&
160        block->children[k]->lastIndex >= index){
161      return (k);
162    }
163    if (block->children[k]->firstIndex > index){
164      j = k-1;
165    }
166    else {
167      i = k+1;
168    }
169  }
170  return i;
171}
172
173/**Function********************************************************************
174
175  Synopsis           [required]
176
177  Description        [optional]
178
179  SideEffects        [required]
180
181  SeeAlso            [optional]
182
183******************************************************************************/
184void
185CalBddBlockDelta(Cal_Block b, long delta)
186{
187  long i;
188  b->firstIndex += delta;
189  b->lastIndex += delta;
190  for (i=0; i < b->numChildren; ++i)
191    CalBddBlockDelta(b->children[i], delta);
192}
193
194
195/**Function********************************************************************
196
197  Synopsis           [required]
198
199  Description        [optional]
200
201  SideEffects        [required]
202
203  SeeAlso            [optional]
204
205******************************************************************************/
206Cal_Block
207CalBddShiftBlock(Cal_BddManager_t *bddManager, Cal_Block b, long index)
208{
209  long i, j;
210  Cal_Block p;
211
212  if (b->firstIndex >= index) {
213    CalBddBlockDelta(b, 1l);
214    return (b);
215  }
216  if (b->lastIndex < index) return (b);
217  b->lastIndex++;
218  i = CalBddFindBlock(b, index);
219  if (i == b->numChildren || b->children[i]->firstIndex == index) {
220    b->children = (Cal_Block *)
221        Cal_MemRealloc(Cal_Block, b->children, b->numChildren+1);
222    for (j = b->numChildren-1; j >= i; --j){
223      b->children[j+1] = CalBddShiftBlock(bddManager, b->children[j], index);
224    }
225    b->numChildren++;
226    /*p = CAL_BDD_NEW_REC(bddManager, Cal_Block_t);*/
227    p = Cal_MemAlloc(Cal_Block_t, 1);
228    p->reorderable = 0;
229    p->firstIndex = index;
230    p->lastIndex = index;
231    p->numChildren = 0;
232    p->children = 0;
233    b->children[i] = p;
234  }
235  else{
236    while (i < b->numChildren) {
237      CalBddShiftBlock(bddManager, b->children[i], index);
238      ++i;
239    }
240  }
241  return (b);
242}
243/**Function********************************************************************
244
245  Synopsis           [required]
246
247  Description        [optional]
248
249  SideEffects        [required]
250
251  SeeAlso            [optional]
252
253******************************************************************************/
254unsigned long
255CalBlockMemoryConsumption(Cal_Block block)
256{
257  unsigned long totalBytes = 0;
258  int i;
259 
260  totalBytes += sizeof(Cal_Block);
261  for (i=0; i<block->numChildren; i++){
262    totalBytes += CalBlockMemoryConsumption(block->children[i]);
263  }
264  return totalBytes;
265}
266/**Function********************************************************************
267
268  Synopsis           [required]
269
270  Description        [optional]
271
272  SideEffects        [required]
273
274  SeeAlso            [optional]
275
276******************************************************************************/
277void
278CalFreeBlockRecursively(Cal_Block block)
279{
280  int i;
281 
282  for (i=0; i<block->numChildren; i++){
283    CalFreeBlockRecursively(block->children[i]);
284  }
285  Cal_MemFree(block->children);
286  Cal_MemFree(block);
287}
288
289/*---------------------------------------------------------------------------*/
290/* Definition of static functions                                          */
291/*---------------------------------------------------------------------------*/
292
293/**Function********************************************************************
294
295  Synopsis           [required]
296
297  Description        [optional]
298
299  SideEffects        [required]
300
301  SeeAlso            [optional]
302
303******************************************************************************/
304static void
305AddBlock(Cal_Block b1, Cal_Block b2)
306{
307  long i, j, k;
308  Cal_Block start, end;
309
310  if (b1->numChildren){
311    i = CalBddFindBlock(b1, b2->firstIndex);
312    start = b1->children[i];
313    j = CalBddFindBlock(b1, b2->lastIndex);
314    end = b1->children[j];
315    if (i == j) {
316      AddBlock(start, b2);
317    }
318    else {
319      if (start->firstIndex != b2->firstIndex ||
320          end->lastIndex != b2->lastIndex){
321        CalBddFatalMessage("AddBlock: illegal block overlap");
322      }
323      b2->numChildren = j-i+1;
324          b2->children = Cal_MemAlloc(Cal_Block, b2->numChildren); 
325          for (k=0; k < b2->numChildren; ++k){
326            b2->children[k] = b1->children[i+k];
327      }
328          b1->children[i] = b2;
329          ++i;
330          for (k=j+1; k < b1->numChildren; ++k, ++i){
331            b1->children[i] = b1->children[k];
332      }
333          b1->numChildren -= (b2->numChildren-1);
334          b1->children = (Cal_Block *)
335          Cal_MemRealloc(Cal_Block, b1->children, b1->numChildren);
336        }
337  }
338  else {
339      /* b1 and b2 are blocks representing just single variables. */
340      b1->numChildren = 1;
341      b1->children = Cal_MemAlloc(Cal_Block, b1->numChildren); 
342      b1->children[0] = b2;
343      b2->numChildren = 0;
344      b2->children = 0;
345  }
346}
347
348
Note: See TracBrowser for help on using the repository browser.