abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fxuHeapD.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [fxuHeapD.c]
4 
5  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]
6 
7  Synopsis [The priority queue for double cube divisors.]
8 
9  Author [MVSIS Group]
10 
11  Affiliation [UC Berkeley]
12 
13  Date [Ver. 1.0. Started - February 1, 2003.]
14 
15  Revision [$Id: fxuHeapD.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $]
16 
17 ***********************************************************************/
18 
19 #include "fxuInt.h"
20 
21 ABC_NAMESPACE_IMPL_START
22 
23 
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27 
28 #define FXU_HEAP_DOUBLE_WEIGHT(pDiv) ((pDiv)->Weight)
29 #define FXU_HEAP_DOUBLE_CURRENT(p, pDiv) ((p)->pTree[(pDiv)->HNum])
30 #define FXU_HEAP_DOUBLE_PARENT_EXISTS(p, pDiv) ((pDiv)->HNum > 1)
31 #define FXU_HEAP_DOUBLE_CHILD1_EXISTS(p, pDiv) (((pDiv)->HNum << 1) <= p->nItems)
32 #define FXU_HEAP_DOUBLE_CHILD2_EXISTS(p, pDiv) ((((pDiv)->HNum << 1)+1) <= p->nItems)
33 #define FXU_HEAP_DOUBLE_PARENT(p, pDiv) ((p)->pTree[(pDiv)->HNum >> 1])
34 #define FXU_HEAP_DOUBLE_CHILD1(p, pDiv) ((p)->pTree[(pDiv)->HNum << 1])
35 #define FXU_HEAP_DOUBLE_CHILD2(p, pDiv) ((p)->pTree[((pDiv)->HNum << 1)+1])
36 #define FXU_HEAP_DOUBLE_ASSERT(p, pDiv) assert( (pDiv)->HNum >= 1 && (pDiv)->HNum <= p->nItemsAlloc )
37 
38 static void Fxu_HeapDoubleResize( Fxu_HeapDouble * p );
39 static void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 );
40 static void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv );
41 static void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv );
42 
43 ////////////////////////////////////////////////////////////////////////
44 /// FUNCTION DEFINITIONS ///
45 ////////////////////////////////////////////////////////////////////////
46 
47 /**Function*************************************************************
48 
49  Synopsis []
50 
51  Description []
52 
53  SideEffects []
54 
55  SeeAlso []
56 
57 ***********************************************************************/
58 Fxu_HeapDouble * Fxu_HeapDoubleStart()
59 {
60  Fxu_HeapDouble * p;
61  p = ABC_ALLOC( Fxu_HeapDouble, 1 );
62  memset( p, 0, sizeof(Fxu_HeapDouble) );
63  p->nItems = 0;
64  p->nItemsAlloc = 10000;
65  p->pTree = ABC_ALLOC( Fxu_Double *, p->nItemsAlloc + 1 );
66  p->pTree[0] = NULL;
67  return p;
68 }
69 
70 
71 /**Function*************************************************************
72 
73  Synopsis []
74 
75  Description []
76 
77  SideEffects []
78 
79  SeeAlso []
80 
81 ***********************************************************************/
82 void Fxu_HeapDoubleResize( Fxu_HeapDouble * p )
83 {
84  p->nItemsAlloc *= 2;
85  p->pTree = ABC_REALLOC( Fxu_Double *, p->pTree, p->nItemsAlloc + 1 );
86 }
87 
88 /**Function*************************************************************
89 
90  Synopsis []
91 
92  Description []
93 
94  SideEffects []
95 
96  SeeAlso []
97 
98 ***********************************************************************/
99 void Fxu_HeapDoubleStop( Fxu_HeapDouble * p )
100 {
101  ABC_FREE( p->pTree );
102  ABC_FREE( p );
103 }
104 
105 
106 /**Function*************************************************************
107 
108  Synopsis []
109 
110  Description []
111 
112  SideEffects []
113 
114  SeeAlso []
115 
116 ***********************************************************************/
117 void Fxu_HeapDoublePrint( FILE * pFile, Fxu_HeapDouble * p )
118 {
119  Fxu_Double * pDiv;
120  int Counter = 1;
121  int Degree = 1;
122 
123  Fxu_HeapDoubleCheck( p );
124  fprintf( pFile, "The contents of the heap:\n" );
125  fprintf( pFile, "Level %d: ", Degree );
126  Fxu_HeapDoubleForEachItem( p, pDiv )
127  {
128  assert( Counter == p->pTree[Counter]->HNum );
129  fprintf( pFile, "%2d=%3d ", Counter, FXU_HEAP_DOUBLE_WEIGHT(p->pTree[Counter]) );
130  if ( ++Counter == (1 << Degree) )
131  {
132  fprintf( pFile, "\n" );
133  Degree++;
134  fprintf( pFile, "Level %d: ", Degree );
135  }
136  }
137  fprintf( pFile, "\n" );
138  fprintf( pFile, "End of the heap printout.\n" );
139 }
140 
141 /**Function*************************************************************
142 
143  Synopsis []
144 
145  Description []
146 
147  SideEffects []
148 
149  SeeAlso []
150 
151 ***********************************************************************/
152 void Fxu_HeapDoubleCheck( Fxu_HeapDouble * p )
153 {
154  Fxu_Double * pDiv;
155  Fxu_HeapDoubleForEachItem( p, pDiv )
156  {
157  assert( pDiv->HNum == p->i );
158  Fxu_HeapDoubleCheckOne( p, pDiv );
159  }
160 }
161 
162 /**Function*************************************************************
163 
164  Synopsis []
165 
166  Description []
167 
168  SideEffects []
169 
170  SeeAlso []
171 
172 ***********************************************************************/
173 void Fxu_HeapDoubleCheckOne( Fxu_HeapDouble * p, Fxu_Double * pDiv )
174 {
175  int Weight1, Weight2;
176  if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) )
177  {
178  Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv);
179  Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) );
180  assert( Weight1 >= Weight2 );
181  }
182  if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) )
183  {
184  Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv);
185  Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) );
186  assert( Weight1 >= Weight2 );
187  }
188 }
189 
190 /**Function*************************************************************
191 
192  Synopsis []
193 
194  Description []
195 
196  SideEffects []
197 
198  SeeAlso []
199 
200 ***********************************************************************/
201 void Fxu_HeapDoubleInsert( Fxu_HeapDouble * p, Fxu_Double * pDiv )
202 {
203  if ( p->nItems == p->nItemsAlloc )
204  Fxu_HeapDoubleResize( p );
205  // put the last entry to the last place and move up
206  p->pTree[++p->nItems] = pDiv;
207  pDiv->HNum = p->nItems;
208  // move the last entry up if necessary
209  Fxu_HeapDoubleMoveUp( p, pDiv );
210 }
211 
212 /**Function*************************************************************
213 
214  Synopsis []
215 
216  Description []
217 
218  SideEffects []
219 
220  SeeAlso []
221 
222 ***********************************************************************/
223 void Fxu_HeapDoubleUpdate( Fxu_HeapDouble * p, Fxu_Double * pDiv )
224 {
225 //printf( "Updating divisor %d.\n", pDiv->Num );
226 
227  FXU_HEAP_DOUBLE_ASSERT(p,pDiv);
228  if ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,pDiv) &&
229  FXU_HEAP_DOUBLE_WEIGHT(pDiv) > FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_PARENT(p,pDiv) ) )
230  Fxu_HeapDoubleMoveUp( p, pDiv );
231  else if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) &&
232  FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) ) )
233  Fxu_HeapDoubleMoveDn( p, pDiv );
234  else if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) &&
235  FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) ) )
236  Fxu_HeapDoubleMoveDn( p, pDiv );
237 }
238 
239 /**Function*************************************************************
240 
241  Synopsis []
242 
243  Description []
244 
245  SideEffects []
246 
247  SeeAlso []
248 
249 ***********************************************************************/
250 void Fxu_HeapDoubleDelete( Fxu_HeapDouble * p, Fxu_Double * pDiv )
251 {
252  FXU_HEAP_DOUBLE_ASSERT(p,pDiv);
253  // put the last entry to the deleted place
254  // decrement the number of entries
255  p->pTree[pDiv->HNum] = p->pTree[p->nItems--];
256  p->pTree[pDiv->HNum]->HNum = pDiv->HNum;
257  // move the top entry down if necessary
258  Fxu_HeapDoubleUpdate( p, p->pTree[pDiv->HNum] );
259  pDiv->HNum = 0;
260 }
261 
262 /**Function*************************************************************
263 
264  Synopsis []
265 
266  Description []
267 
268  SideEffects []
269 
270  SeeAlso []
271 
272 ***********************************************************************/
273 Fxu_Double * Fxu_HeapDoubleReadMax( Fxu_HeapDouble * p )
274 {
275  if ( p->nItems == 0 )
276  return NULL;
277  return p->pTree[1];
278 }
279 
280 /**Function*************************************************************
281 
282  Synopsis []
283 
284  Description []
285 
286  SideEffects []
287 
288  SeeAlso []
289 
290 ***********************************************************************/
291 Fxu_Double * Fxu_HeapDoubleGetMax( Fxu_HeapDouble * p )
292 {
293  Fxu_Double * pDiv;
294  if ( p->nItems == 0 )
295  return NULL;
296  // prepare the return value
297  pDiv = p->pTree[1];
298  pDiv->HNum = 0;
299  // put the last entry on top
300  // decrement the number of entries
301  p->pTree[1] = p->pTree[p->nItems--];
302  p->pTree[1]->HNum = 1;
303  // move the top entry down if necessary
304  Fxu_HeapDoubleMoveDn( p, p->pTree[1] );
305  return pDiv;
306 }
307 
308 /**Function*************************************************************
309 
310  Synopsis []
311 
312  Description []
313 
314  SideEffects []
315 
316  SeeAlso []
317 
318 ***********************************************************************/
319 int Fxu_HeapDoubleReadMaxWeight( Fxu_HeapDouble * p )
320 {
321  if ( p->nItems == 0 )
322  return -1;
323  else
324  return FXU_HEAP_DOUBLE_WEIGHT(p->pTree[1]);
325 }
326 
327 
328 
329 /**Function*************************************************************
330 
331  Synopsis []
332 
333  Description []
334 
335  SideEffects []
336 
337  SeeAlso []
338 
339 ***********************************************************************/
340 void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 )
341 {
342  Fxu_Double * pDiv;
343  int Temp;
344  pDiv = *pDiv1;
345  *pDiv1 = *pDiv2;
346  *pDiv2 = pDiv;
347  Temp = (*pDiv1)->HNum;
348  (*pDiv1)->HNum = (*pDiv2)->HNum;
349  (*pDiv2)->HNum = Temp;
350 }
351 
352 /**Function*************************************************************
353 
354  Synopsis []
355 
356  Description []
357 
358  SideEffects []
359 
360  SeeAlso []
361 
362 ***********************************************************************/
363 void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv )
364 {
365  Fxu_Double ** ppDiv, ** ppPar;
366  ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv);
367  while ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,*ppDiv) )
368  {
369  ppPar = &FXU_HEAP_DOUBLE_PARENT(p,*ppDiv);
370  if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) > FXU_HEAP_DOUBLE_WEIGHT(*ppPar) )
371  {
372  Fxu_HeapDoubleSwap( ppDiv, ppPar );
373  ppDiv = ppPar;
374  }
375  else
376  break;
377  }
378 }
379 
380 /**Function*************************************************************
381 
382  Synopsis []
383 
384  Description []
385 
386  SideEffects []
387 
388  SeeAlso []
389 
390 ***********************************************************************/
391 void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv )
392 {
393  Fxu_Double ** ppChild1, ** ppChild2, ** ppDiv;
394  ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv);
395  while ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,*ppDiv) )
396  { // if Child1 does not exist, Child2 also does not exists
397 
398  // get the children
399  ppChild1 = &FXU_HEAP_DOUBLE_CHILD1(p,*ppDiv);
400  if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,*ppDiv) )
401  {
402  ppChild2 = &FXU_HEAP_DOUBLE_CHILD2(p,*ppDiv);
403 
404  // consider two cases
405  if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) &&
406  FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) )
407  { // Div is larger than both, skip
408  break;
409  }
410  else
411  { // Div is smaller than one of them, then swap it with larger
412  if ( FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) )
413  {
414  Fxu_HeapDoubleSwap( ppDiv, ppChild1 );
415  // update the pointer
416  ppDiv = ppChild1;
417  }
418  else
419  {
420  Fxu_HeapDoubleSwap( ppDiv, ppChild2 );
421  // update the pointer
422  ppDiv = ppChild2;
423  }
424  }
425  }
426  else // Child2 does not exist
427  {
428  // consider two cases
429  if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) )
430  { // Div is larger than Child1, skip
431  break;
432  }
433  else
434  { // Div is smaller than Child1, then swap them
435  Fxu_HeapDoubleSwap( ppDiv, ppChild1 );
436  // update the pointer
437  ppDiv = ppChild1;
438  }
439  }
440  }
441 }
442 
443 
444 ////////////////////////////////////////////////////////////////////////
445 /// END OF FILE ///
446 ////////////////////////////////////////////////////////////////////////
447 
448 
449 ABC_NAMESPACE_IMPL_END
450 
memset
char * memset()
Fxu_HeapDoubleStart
Fxu_HeapDouble * Fxu_HeapDoubleStart()
FUNCTION DEFINITIONS ///.
Definition: fxuHeapD.c:58
Fxu_HeapDoubleReadMax
Fxu_Double * Fxu_HeapDoubleReadMax(Fxu_HeapDouble *p)
Definition: fxuHeapD.c:273
FXU_HEAP_DOUBLE_CHILD2
#define FXU_HEAP_DOUBLE_CHILD2(p, pDiv)
Definition: fxuHeapD.c:35
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
FXU_HEAP_DOUBLE_WEIGHT
#define FXU_HEAP_DOUBLE_WEIGHT(pDiv)
DECLARATIONS ///.
Definition: fxuHeapD.c:28
Fxu_HeapDoubleDelete
void Fxu_HeapDoubleDelete(Fxu_HeapDouble *p, Fxu_Double *pDiv)
Definition: fxuHeapD.c:250
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
Fxu_HeapDoubleMoveUp
static void Fxu_HeapDoubleMoveUp(Fxu_HeapDouble *p, Fxu_Double *pDiv)
Definition: fxuHeapD.c:363
Fxu_HeapDoubleCheck
void Fxu_HeapDoubleCheck(Fxu_HeapDouble *p)
Definition: fxuHeapD.c:152
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
FXU_HEAP_DOUBLE_CHILD2_EXISTS
#define FXU_HEAP_DOUBLE_CHILD2_EXISTS(p, pDiv)
Definition: fxuHeapD.c:32
Fxu_HeapDoubleGetMax
Fxu_Double * Fxu_HeapDoubleGetMax(Fxu_HeapDouble *p)
Definition: fxuHeapD.c:291
FXU_HEAP_DOUBLE_CURRENT
#define FXU_HEAP_DOUBLE_CURRENT(p, pDiv)
Definition: fxuHeapD.c:29
Fxu_HeapDoubleReadMaxWeight
int Fxu_HeapDoubleReadMaxWeight(Fxu_HeapDouble *p)
Definition: fxuHeapD.c:319
Fxu_HeapDoubleForEachItem
#define Fxu_HeapDoubleForEachItem(Heap, Div)
Definition: fxuInt.h:375
Fxu_HeapDoubleUpdate
void Fxu_HeapDoubleUpdate(Fxu_HeapDouble *p, Fxu_Double *pDiv)
Definition: fxuHeapD.c:223
Fxu_HeapDoublePrint
void Fxu_HeapDoublePrint(FILE *pFile, Fxu_HeapDouble *p)
Definition: fxuHeapD.c:117
FXU_HEAP_DOUBLE_CHILD1
#define FXU_HEAP_DOUBLE_CHILD1(p, pDiv)
Definition: fxuHeapD.c:34
FXU_HEAP_DOUBLE_PARENT
#define FXU_HEAP_DOUBLE_PARENT(p, pDiv)
Definition: fxuHeapD.c:33
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
FxuHeapDouble::nItems
int nItems
Definition: fxuInt.h:145
Fxu_HeapDoubleMoveDn
static void Fxu_HeapDoubleMoveDn(Fxu_HeapDouble *p, Fxu_Double *pDiv)
Definition: fxuHeapD.c:391
Fxu_HeapDoubleStop
void Fxu_HeapDoubleStop(Fxu_HeapDouble *p)
Definition: fxuHeapD.c:99
Counter
static int Counter
Definition: extraBddMisc.c:1877
FxuDouble::HNum
int HNum
Definition: fxuInt.h:257
Fxu_HeapDoubleCheckOne
void Fxu_HeapDoubleCheckOne(Fxu_HeapDouble *p, Fxu_Double *pDiv)
Definition: fxuHeapD.c:173
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
FXU_HEAP_DOUBLE_PARENT_EXISTS
#define FXU_HEAP_DOUBLE_PARENT_EXISTS(p, pDiv)
Definition: fxuHeapD.c:30
FXU_HEAP_DOUBLE_CHILD1_EXISTS
#define FXU_HEAP_DOUBLE_CHILD1_EXISTS(p, pDiv)
Definition: fxuHeapD.c:31
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
FxuHeapDouble::nItemsAlloc
int nItemsAlloc
Definition: fxuInt.h:146
Fxu_HeapDoubleInsert
void Fxu_HeapDoubleInsert(Fxu_HeapDouble *p, Fxu_Double *pDiv)
Definition: fxuHeapD.c:201
Fxu_HeapDoubleResize
static void Fxu_HeapDoubleResize(Fxu_HeapDouble *p)
Definition: fxuHeapD.c:82
FxuHeapDouble::pTree
Fxu_Double ** pTree
Definition: fxuInt.h:144
assert
#define assert(ex)
Definition: util_old.h:213
Fxu_HeapDoubleSwap
static void Fxu_HeapDoubleSwap(Fxu_Double **pDiv1, Fxu_Double **pDiv2)
Definition: fxuHeapD.c:340
FXU_HEAP_DOUBLE_ASSERT
#define FXU_HEAP_DOUBLE_ASSERT(p, pDiv)
Definition: fxuHeapD.c:36