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