abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fraigVec.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [fraigVec.c]
4 
5  PackageName [FRAIG: Functionally reduced AND-INV graphs.]
6 
7  Synopsis [Vector of FRAIG nodes.]
8 
9  Author [Alan Mishchenko <alanmi@eecs.berkeley.edu>]
10 
11  Affiliation [UC Berkeley]
12 
13  Date [Ver. 2.0. Started - October 1, 2004]
14 
15  Revision [$Id: fraigVec.c,v 1.7 2005/07/08 01:01:34 alanmi Exp $]
16 
17 ***********************************************************************/
18 
19 #include "fraigInt.h"
20 
21 ABC_NAMESPACE_IMPL_START
22 
23 
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27 
28 ////////////////////////////////////////////////////////////////////////
29 /// FUNCTION DEFINITIONS ///
30 ////////////////////////////////////////////////////////////////////////
31 
32 /**Function*************************************************************
33 
34  Synopsis [Allocates a vector with the given capacity.]
35 
36  Description []
37 
38  SideEffects []
39 
40  SeeAlso []
41 
42 ***********************************************************************/
43 Fraig_NodeVec_t * Fraig_NodeVecAlloc( int nCap )
44 {
45  Fraig_NodeVec_t * p;
46  p = ABC_ALLOC( Fraig_NodeVec_t, 1 );
47  if ( nCap > 0 && nCap < 8 )
48  nCap = 8;
49  p->nSize = 0;
50  p->nCap = nCap;
51  p->pArray = p->nCap? ABC_ALLOC( Fraig_Node_t *, p->nCap ) : NULL;
52  return p;
53 }
54 
55 /**Function*************************************************************
56 
57  Synopsis []
58 
59  Description []
60 
61  SideEffects []
62 
63  SeeAlso []
64 
65 ***********************************************************************/
66 void Fraig_NodeVecFree( Fraig_NodeVec_t * p )
67 {
68  ABC_FREE( p->pArray );
69  ABC_FREE( p );
70 }
71 
72 /**Function*************************************************************
73 
74  Synopsis [Duplicates the integer array.]
75 
76  Description []
77 
78  SideEffects []
79 
80  SeeAlso []
81 
82 ***********************************************************************/
83 Fraig_NodeVec_t * Fraig_NodeVecDup( Fraig_NodeVec_t * pVec )
84 {
85  Fraig_NodeVec_t * p;
86  p = ABC_ALLOC( Fraig_NodeVec_t, 1 );
87  p->nSize = pVec->nSize;
88  p->nCap = pVec->nCap;
89  p->pArray = p->nCap? ABC_ALLOC( Fraig_Node_t *, p->nCap ) : NULL;
90  memcpy( p->pArray, pVec->pArray, sizeof(Fraig_Node_t *) * pVec->nSize );
91  return p;
92 }
93 
94 /**Function*************************************************************
95 
96  Synopsis []
97 
98  Description []
99 
100  SideEffects []
101 
102  SeeAlso []
103 
104 ***********************************************************************/
105 Fraig_Node_t ** Fraig_NodeVecReadArray( Fraig_NodeVec_t * p )
106 {
107  return p->pArray;
108 }
109 
110 /**Function*************************************************************
111 
112  Synopsis []
113 
114  Description []
115 
116  SideEffects []
117 
118  SeeAlso []
119 
120 ***********************************************************************/
121 int Fraig_NodeVecReadSize( Fraig_NodeVec_t * p )
122 {
123  return p->nSize;
124 }
125 
126 /**Function*************************************************************
127 
128  Synopsis [Resizes the vector to the given capacity.]
129 
130  Description []
131 
132  SideEffects []
133 
134  SeeAlso []
135 
136 ***********************************************************************/
137 void Fraig_NodeVecGrow( Fraig_NodeVec_t * p, int nCapMin )
138 {
139  if ( p->nCap >= nCapMin )
140  return;
141  p->pArray = ABC_REALLOC( Fraig_Node_t *, p->pArray, nCapMin );
142  p->nCap = nCapMin;
143 }
144 
145 /**Function*************************************************************
146 
147  Synopsis []
148 
149  Description []
150 
151  SideEffects []
152 
153  SeeAlso []
154 
155 ***********************************************************************/
156 void Fraig_NodeVecShrink( Fraig_NodeVec_t * p, int nSizeNew )
157 {
158  assert( p->nSize >= nSizeNew );
159  p->nSize = nSizeNew;
160 }
161 
162 /**Function*************************************************************
163 
164  Synopsis []
165 
166  Description []
167 
168  SideEffects []
169 
170  SeeAlso []
171 
172 ***********************************************************************/
173 void Fraig_NodeVecClear( Fraig_NodeVec_t * p )
174 {
175  p->nSize = 0;
176 }
177 
178 /**Function*************************************************************
179 
180  Synopsis []
181 
182  Description []
183 
184  SideEffects []
185 
186  SeeAlso []
187 
188 ***********************************************************************/
189 void Fraig_NodeVecPush( Fraig_NodeVec_t * p, Fraig_Node_t * Entry )
190 {
191  if ( p->nSize == p->nCap )
192  {
193  if ( p->nCap < 16 )
194  Fraig_NodeVecGrow( p, 16 );
195  else
196  Fraig_NodeVecGrow( p, 2 * p->nCap );
197  }
198  p->pArray[p->nSize++] = Entry;
199 }
200 
201 /**Function*************************************************************
202 
203  Synopsis [Add the element while ensuring uniqueness.]
204 
205  Description [Returns 1 if the element was found, and 0 if it was new. ]
206 
207  SideEffects []
208 
209  SeeAlso []
210 
211 ***********************************************************************/
212 int Fraig_NodeVecPushUnique( Fraig_NodeVec_t * p, Fraig_Node_t * Entry )
213 {
214  int i;
215  for ( i = 0; i < p->nSize; i++ )
216  if ( p->pArray[i] == Entry )
217  return 1;
218  Fraig_NodeVecPush( p, Entry );
219  return 0;
220 }
221 
222 /**Function*************************************************************
223 
224  Synopsis [Inserts a new node in the order by arrival times.]
225 
226  Description []
227 
228  SideEffects []
229 
230  SeeAlso []
231 
232 ***********************************************************************/
233 void Fraig_NodeVecPushOrder( Fraig_NodeVec_t * p, Fraig_Node_t * pNode )
234 {
235  Fraig_Node_t * pNode1, * pNode2;
236  int i;
237  Fraig_NodeVecPush( p, pNode );
238  // find the p of the node
239  for ( i = p->nSize-1; i > 0; i-- )
240  {
241  pNode1 = p->pArray[i ];
242  pNode2 = p->pArray[i-1];
243  if ( pNode1 >= pNode2 )
244  break;
245  p->pArray[i ] = pNode2;
246  p->pArray[i-1] = pNode1;
247  }
248 }
249 
250 /**Function*************************************************************
251 
252  Synopsis [Add the element while ensuring uniqueness in the order.]
253 
254  Description [Returns 1 if the element was found, and 0 if it was new. ]
255 
256  SideEffects []
257 
258  SeeAlso []
259 
260 ***********************************************************************/
261 int Fraig_NodeVecPushUniqueOrder( Fraig_NodeVec_t * p, Fraig_Node_t * pNode )
262 {
263  int i;
264  for ( i = 0; i < p->nSize; i++ )
265  if ( p->pArray[i] == pNode )
266  return 1;
267  Fraig_NodeVecPushOrder( p, pNode );
268  return 0;
269 }
270 
271 /**Function*************************************************************
272 
273  Synopsis [Inserts a new node in the order by arrival times.]
274 
275  Description []
276 
277  SideEffects []
278 
279  SeeAlso []
280 
281 ***********************************************************************/
282 void Fraig_NodeVecPushOrderByLevel( Fraig_NodeVec_t * p, Fraig_Node_t * pNode )
283 {
284  Fraig_Node_t * pNode1, * pNode2;
285  int i;
286  Fraig_NodeVecPush( p, pNode );
287  // find the p of the node
288  for ( i = p->nSize-1; i > 0; i-- )
289  {
290  pNode1 = p->pArray[i ];
291  pNode2 = p->pArray[i-1];
292  if ( Fraig_Regular(pNode1)->Level <= Fraig_Regular(pNode2)->Level )
293  break;
294  p->pArray[i ] = pNode2;
295  p->pArray[i-1] = pNode1;
296  }
297 }
298 
299 /**Function*************************************************************
300 
301  Synopsis [Add the element while ensuring uniqueness in the order.]
302 
303  Description [Returns 1 if the element was found, and 0 if it was new. ]
304 
305  SideEffects []
306 
307  SeeAlso []
308 
309 ***********************************************************************/
310 int Fraig_NodeVecPushUniqueOrderByLevel( Fraig_NodeVec_t * p, Fraig_Node_t * pNode )
311 {
312  int i;
313  for ( i = 0; i < p->nSize; i++ )
314  if ( p->pArray[i] == pNode )
315  return 1;
316  Fraig_NodeVecPushOrderByLevel( p, pNode );
317  return 0;
318 }
319 
320 /**Function*************************************************************
321 
322  Synopsis []
323 
324  Description []
325 
326  SideEffects []
327 
328  SeeAlso []
329 
330 ***********************************************************************/
331 Fraig_Node_t * Fraig_NodeVecPop( Fraig_NodeVec_t * p )
332 {
333  return p->pArray[--p->nSize];
334 }
335 
336 /**Function*************************************************************
337 
338  Synopsis []
339 
340  Description []
341 
342  SideEffects []
343 
344  SeeAlso []
345 
346 ***********************************************************************/
347 void Fraig_NodeVecRemove( Fraig_NodeVec_t * p, Fraig_Node_t * Entry )
348 {
349  int i;
350  for ( i = 0; i < p->nSize; i++ )
351  if ( p->pArray[i] == Entry )
352  break;
353  assert( i < p->nSize );
354  for ( i++; i < p->nSize; i++ )
355  p->pArray[i-1] = p->pArray[i];
356  p->nSize--;
357 }
358 
359 /**Function*************************************************************
360 
361  Synopsis []
362 
363  Description []
364 
365  SideEffects []
366 
367  SeeAlso []
368 
369 ***********************************************************************/
370 void Fraig_NodeVecWriteEntry( Fraig_NodeVec_t * p, int i, Fraig_Node_t * Entry )
371 {
372  assert( i >= 0 && i < p->nSize );
373  p->pArray[i] = Entry;
374 }
375 
376 /**Function*************************************************************
377 
378  Synopsis []
379 
380  Description []
381 
382  SideEffects []
383 
384  SeeAlso []
385 
386 ***********************************************************************/
387 Fraig_Node_t * Fraig_NodeVecReadEntry( Fraig_NodeVec_t * p, int i )
388 {
389  assert( i >= 0 && i < p->nSize );
390  return p->pArray[i];
391 }
392 
393 /**Function*************************************************************
394 
395  Synopsis [Comparison procedure for two clauses.]
396 
397  Description []
398 
399  SideEffects []
400 
401  SeeAlso []
402 
403 ***********************************************************************/
404 int Fraig_NodeVecCompareLevelsIncreasing( Fraig_Node_t ** pp1, Fraig_Node_t ** pp2 )
405 {
406  int Level1 = Fraig_Regular(*pp1)->Level;
407  int Level2 = Fraig_Regular(*pp2)->Level;
408  if ( Level1 < Level2 )
409  return -1;
410  if ( Level1 > Level2 )
411  return 1;
412  return 0;
413 }
414 
415 /**Function*************************************************************
416 
417  Synopsis [Comparison procedure for two clauses.]
418 
419  Description []
420 
421  SideEffects []
422 
423  SeeAlso []
424 
425 ***********************************************************************/
426 int Fraig_NodeVecCompareLevelsDecreasing( Fraig_Node_t ** pp1, Fraig_Node_t ** pp2 )
427 {
428  int Level1 = Fraig_Regular(*pp1)->Level;
429  int Level2 = Fraig_Regular(*pp2)->Level;
430  if ( Level1 > Level2 )
431  return -1;
432  if ( Level1 < Level2 )
433  return 1;
434  return 0;
435 }
436 
437 /**Function*************************************************************
438 
439  Synopsis [Comparison procedure for two clauses.]
440 
441  Description []
442 
443  SideEffects []
444 
445  SeeAlso []
446 
447 ***********************************************************************/
448 int Fraig_NodeVecCompareNumbers( Fraig_Node_t ** pp1, Fraig_Node_t ** pp2 )
449 {
450  int Num1 = Fraig_Regular(*pp1)->Num;
451  int Num2 = Fraig_Regular(*pp2)->Num;
452  if ( Num1 < Num2 )
453  return -1;
454  if ( Num1 > Num2 )
455  return 1;
456  return 0;
457 }
458 
459 /**Function*************************************************************
460 
461  Synopsis [Comparison procedure for two clauses.]
462 
463  Description []
464 
465  SideEffects []
466 
467  SeeAlso []
468 
469 ***********************************************************************/
470 int Fraig_NodeVecCompareRefCounts( Fraig_Node_t ** pp1, Fraig_Node_t ** pp2 )
471 {
472  int nRefs1 = Fraig_Regular(*pp1)->nRefs;
473  int nRefs2 = Fraig_Regular(*pp2)->nRefs;
474 
475  if ( nRefs1 < nRefs2 )
476  return -1;
477  if ( nRefs1 > nRefs2 )
478  return 1;
479 
480  nRefs1 = Fraig_Regular(*pp1)->Level;
481  nRefs2 = Fraig_Regular(*pp2)->Level;
482 
483  if ( nRefs1 < nRefs2 )
484  return -1;
485  if ( nRefs1 > nRefs2 )
486  return 1;
487  return 0;
488 }
489 
490 /**Function*************************************************************
491 
492  Synopsis [Sorting the entries by their integer value.]
493 
494  Description []
495 
496  SideEffects []
497 
498  SeeAlso []
499 
500 ***********************************************************************/
501 void Fraig_NodeVecSortByLevel( Fraig_NodeVec_t * p, int fIncreasing )
502 {
503  if ( fIncreasing )
504  qsort( (void *)p->pArray, p->nSize, sizeof(Fraig_Node_t *),
505  (int (*)(const void *, const void *)) Fraig_NodeVecCompareLevelsIncreasing );
506  else
507  qsort( (void *)p->pArray, p->nSize, sizeof(Fraig_Node_t *),
508  (int (*)(const void *, const void *)) Fraig_NodeVecCompareLevelsDecreasing );
509 }
510 
511 /**Function*************************************************************
512 
513  Synopsis [Sorting the entries by their integer value.]
514 
515  Description []
516 
517  SideEffects []
518 
519  SeeAlso []
520 
521 ***********************************************************************/
522 void Fraig_NodeVecSortByNumber( Fraig_NodeVec_t * p )
523 {
524  qsort( (void *)p->pArray, p->nSize, sizeof(Fraig_Node_t *),
525  (int (*)(const void *, const void *)) Fraig_NodeVecCompareNumbers );
526 }
527 
528 /**Function*************************************************************
529 
530  Synopsis [Sorting the entries by their integer value.]
531 
532  Description []
533 
534  SideEffects []
535 
536  SeeAlso []
537 
538 ***********************************************************************/
539 void Fraig_NodeVecSortByRefCount( Fraig_NodeVec_t * p )
540 {
541  qsort( (void *)p->pArray, p->nSize, sizeof(Fraig_Node_t *),
542  (int (*)(const void *, const void *)) Fraig_NodeVecCompareRefCounts );
543 }
544 
545 ////////////////////////////////////////////////////////////////////////
546 /// END OF FILE ///
547 ////////////////////////////////////////////////////////////////////////
548 
549 ABC_NAMESPACE_IMPL_END
550 
Fraig_NodeVecReadSize
int Fraig_NodeVecReadSize(Fraig_NodeVec_t *p)
Definition: fraigVec.c:121
Fraig_NodeVecReadEntry
Fraig_Node_t * Fraig_NodeVecReadEntry(Fraig_NodeVec_t *p, int i)
Definition: fraigVec.c:387
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Fraig_NodeVecSortByLevel
void Fraig_NodeVecSortByLevel(Fraig_NodeVec_t *p, int fIncreasing)
Definition: fraigVec.c:501
Fraig_NodeVecFree
void Fraig_NodeVecFree(Fraig_NodeVec_t *p)
Definition: fraigVec.c:66
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
Fraig_NodeVecAlloc
ABC_NAMESPACE_IMPL_START Fraig_NodeVec_t * Fraig_NodeVecAlloc(int nCap)
DECLARATIONS ///.
Definition: fraigVec.c:43
memcpy
char * memcpy()
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Fraig_NodeVecReadArray
Fraig_Node_t ** Fraig_NodeVecReadArray(Fraig_NodeVec_t *p)
Definition: fraigVec.c:105
Fraig_NodeVecPushOrder
void Fraig_NodeVecPushOrder(Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
Definition: fraigVec.c:233
Fraig_NodeVecRemove
void Fraig_NodeVecRemove(Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
Definition: fraigVec.c:347
Fraig_NodeVecShrink
void Fraig_NodeVecShrink(Fraig_NodeVec_t *p, int nSizeNew)
Definition: fraigVec.c:156
Fraig_NodeVecCompareLevelsIncreasing
int Fraig_NodeVecCompareLevelsIncreasing(Fraig_Node_t **pp1, Fraig_Node_t **pp2)
Definition: fraigVec.c:404
Fraig_NodeVecDup
Fraig_NodeVec_t * Fraig_NodeVecDup(Fraig_NodeVec_t *pVec)
Definition: fraigVec.c:83
Fraig_NodeStruct_t_
Definition: fraigInt.h:207
Fraig_NodeVecPushUnique
int Fraig_NodeVecPushUnique(Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
Definition: fraigVec.c:212
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
if
if(last==0)
Definition: sparse_int.h:34
Fraig_NodeVecCompareNumbers
int Fraig_NodeVecCompareNumbers(Fraig_Node_t **pp1, Fraig_Node_t **pp2)
Definition: fraigVec.c:448
Fraig_NodeVecCompareLevelsDecreasing
int Fraig_NodeVecCompareLevelsDecreasing(Fraig_Node_t **pp1, Fraig_Node_t **pp2)
Definition: fraigVec.c:426
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Fraig_NodeVecStruct_t_::nCap
int nCap
Definition: fraigInt.h:265
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Fraig_NodeVecStruct_t_::pArray
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
Fraig_Regular
#define Fraig_Regular(p)
Definition: fraig.h:108
Fraig_NodeVecWriteEntry
void Fraig_NodeVecWriteEntry(Fraig_NodeVec_t *p, int i, Fraig_Node_t *Entry)
Definition: fraigVec.c:370
Fraig_NodeVecPop
Fraig_Node_t * Fraig_NodeVecPop(Fraig_NodeVec_t *p)
Definition: fraigVec.c:331
Fraig_NodeVecPushUniqueOrder
int Fraig_NodeVecPushUniqueOrder(Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
Definition: fraigVec.c:261
assert
#define assert(ex)
Definition: util_old.h:213
Fraig_NodeVecClear
void Fraig_NodeVecClear(Fraig_NodeVec_t *p)
Definition: fraigVec.c:173
Fraig_NodeVecStruct_t_::nSize
int nSize
Definition: fraigInt.h:266
Fraig_NodeVecSortByNumber
void Fraig_NodeVecSortByNumber(Fraig_NodeVec_t *p)
Definition: fraigVec.c:522
Fraig_NodeVecGrow
void Fraig_NodeVecGrow(Fraig_NodeVec_t *p, int nCapMin)
Definition: fraigVec.c:137
Fraig_NodeVecCompareRefCounts
int Fraig_NodeVecCompareRefCounts(Fraig_Node_t **pp1, Fraig_Node_t **pp2)
Definition: fraigVec.c:470
Fraig_NodeVecPushOrderByLevel
void Fraig_NodeVecPushOrderByLevel(Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
Definition: fraigVec.c:282
Fraig_NodeVecSortByRefCount
void Fraig_NodeVecSortByRefCount(Fraig_NodeVec_t *p)
Definition: fraigVec.c:539
Fraig_NodeVecStruct_t_
Definition: fraigInt.h:263
Fraig_NodeVecPushUniqueOrderByLevel
int Fraig_NodeVecPushUniqueOrderByLevel(Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
Definition: fraigVec.c:310
Fraig_NodeVecPush
void Fraig_NodeVecPush(Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
Definition: fraigVec.c:189