abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fraigVec.c File Reference
#include "fraigInt.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START
Fraig_NodeVec_t
Fraig_NodeVecAlloc (int nCap)
 DECLARATIONS ///. More...
 
void Fraig_NodeVecFree (Fraig_NodeVec_t *p)
 
Fraig_NodeVec_tFraig_NodeVecDup (Fraig_NodeVec_t *pVec)
 
Fraig_Node_t ** Fraig_NodeVecReadArray (Fraig_NodeVec_t *p)
 
int Fraig_NodeVecReadSize (Fraig_NodeVec_t *p)
 
void Fraig_NodeVecGrow (Fraig_NodeVec_t *p, int nCapMin)
 
void Fraig_NodeVecShrink (Fraig_NodeVec_t *p, int nSizeNew)
 
void Fraig_NodeVecClear (Fraig_NodeVec_t *p)
 
void Fraig_NodeVecPush (Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
 
int Fraig_NodeVecPushUnique (Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
 
void Fraig_NodeVecPushOrder (Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
 
int Fraig_NodeVecPushUniqueOrder (Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
 
void Fraig_NodeVecPushOrderByLevel (Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
 
int Fraig_NodeVecPushUniqueOrderByLevel (Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
 
Fraig_Node_tFraig_NodeVecPop (Fraig_NodeVec_t *p)
 
void Fraig_NodeVecRemove (Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
 
void Fraig_NodeVecWriteEntry (Fraig_NodeVec_t *p, int i, Fraig_Node_t *Entry)
 
Fraig_Node_tFraig_NodeVecReadEntry (Fraig_NodeVec_t *p, int i)
 
int Fraig_NodeVecCompareLevelsIncreasing (Fraig_Node_t **pp1, Fraig_Node_t **pp2)
 
int Fraig_NodeVecCompareLevelsDecreasing (Fraig_Node_t **pp1, Fraig_Node_t **pp2)
 
int Fraig_NodeVecCompareNumbers (Fraig_Node_t **pp1, Fraig_Node_t **pp2)
 
int Fraig_NodeVecCompareRefCounts (Fraig_Node_t **pp1, Fraig_Node_t **pp2)
 
void Fraig_NodeVecSortByLevel (Fraig_NodeVec_t *p, int fIncreasing)
 
void Fraig_NodeVecSortByNumber (Fraig_NodeVec_t *p)
 
void Fraig_NodeVecSortByRefCount (Fraig_NodeVec_t *p)
 

Function Documentation

ABC_NAMESPACE_IMPL_START Fraig_NodeVec_t* Fraig_NodeVecAlloc ( int  nCap)

DECLARATIONS ///.

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

FileName [fraigVec.c]

PackageName [FRAIG: Functionally reduced AND-INV graphs.]

Synopsis [Vector of FRAIG nodes.]

Author [Alan Mishchenko alanm.nosp@m.i@ee.nosp@m.cs.be.nosp@m.rkel.nosp@m.ey.ed.nosp@m.u]

Affiliation [UC Berkeley]

Date [Ver. 2.0. Started - October 1, 2004]

Revision [

Id:
fraigVec.c,v 1.7 2005/07/08 01:01:34 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Allocates a vector with the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 43 of file fraigVec.c.

44 {
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 }
static Llb_Mgr_t * p
Definition: llb3Image.c:950
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecClear ( Fraig_NodeVec_t p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 173 of file fraigVec.c.

174 {
175  p->nSize = 0;
176 }
int Fraig_NodeVecCompareLevelsDecreasing ( Fraig_Node_t **  pp1,
Fraig_Node_t **  pp2 
)

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

Synopsis [Comparison procedure for two clauses.]

Description []

SideEffects []

SeeAlso []

Definition at line 426 of file fraigVec.c.

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 }
if(last==0)
Definition: sparse_int.h:34
#define Fraig_Regular(p)
Definition: fraig.h:108
int Fraig_NodeVecCompareLevelsIncreasing ( Fraig_Node_t **  pp1,
Fraig_Node_t **  pp2 
)

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

Synopsis [Comparison procedure for two clauses.]

Description []

SideEffects []

SeeAlso []

Definition at line 404 of file fraigVec.c.

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 }
if(last==0)
Definition: sparse_int.h:34
#define Fraig_Regular(p)
Definition: fraig.h:108
int Fraig_NodeVecCompareNumbers ( Fraig_Node_t **  pp1,
Fraig_Node_t **  pp2 
)

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

Synopsis [Comparison procedure for two clauses.]

Description []

SideEffects []

SeeAlso []

Definition at line 448 of file fraigVec.c.

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 }
if(last==0)
Definition: sparse_int.h:34
#define Fraig_Regular(p)
Definition: fraig.h:108
int Fraig_NodeVecCompareRefCounts ( Fraig_Node_t **  pp1,
Fraig_Node_t **  pp2 
)

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

Synopsis [Comparison procedure for two clauses.]

Description []

SideEffects []

SeeAlso []

Definition at line 470 of file fraigVec.c.

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 }
if(last==0)
Definition: sparse_int.h:34
#define Fraig_Regular(p)
Definition: fraig.h:108
Fraig_NodeVec_t* Fraig_NodeVecDup ( Fraig_NodeVec_t pVec)

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

Synopsis [Duplicates the integer array.]

Description []

SideEffects []

SeeAlso []

Definition at line 83 of file fraigVec.c.

84 {
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 }
static Llb_Mgr_t * p
Definition: llb3Image.c:950
char * memcpy()
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecFree ( Fraig_NodeVec_t p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 66 of file fraigVec.c.

67 {
68  ABC_FREE( p->pArray );
69  ABC_FREE( p );
70 }
#define ABC_FREE(obj)
Definition: abc_global.h:232
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecGrow ( Fraig_NodeVec_t p,
int  nCapMin 
)

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

Synopsis [Resizes the vector to the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 137 of file fraigVec.c.

138 {
139  if ( p->nCap >= nCapMin )
140  return;
141  p->pArray = ABC_REALLOC( Fraig_Node_t *, p->pArray, nCapMin );
142  p->nCap = nCapMin;
143 }
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
Fraig_Node_t* Fraig_NodeVecPop ( Fraig_NodeVec_t p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 331 of file fraigVec.c.

332 {
333  return p->pArray[--p->nSize];
334 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecPush ( Fraig_NodeVec_t p,
Fraig_Node_t Entry 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 189 of file fraigVec.c.

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 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecGrow(Fraig_NodeVec_t *p, int nCapMin)
Definition: fraigVec.c:137
void Fraig_NodeVecPushOrder ( Fraig_NodeVec_t p,
Fraig_Node_t pNode 
)

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

Synopsis [Inserts a new node in the order by arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 233 of file fraigVec.c.

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 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecPush(Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
Definition: fraigVec.c:189
void Fraig_NodeVecPushOrderByLevel ( Fraig_NodeVec_t p,
Fraig_Node_t pNode 
)

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

Synopsis [Inserts a new node in the order by arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 282 of file fraigVec.c.

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 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
#define Fraig_Regular(p)
Definition: fraig.h:108
void Fraig_NodeVecPush(Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
Definition: fraigVec.c:189
int Fraig_NodeVecPushUnique ( Fraig_NodeVec_t p,
Fraig_Node_t Entry 
)

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

Synopsis [Add the element while ensuring uniqueness.]

Description [Returns 1 if the element was found, and 0 if it was new. ]

SideEffects []

SeeAlso []

Definition at line 212 of file fraigVec.c.

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 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecPush(Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
Definition: fraigVec.c:189
int Fraig_NodeVecPushUniqueOrder ( Fraig_NodeVec_t p,
Fraig_Node_t pNode 
)

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

Synopsis [Add the element while ensuring uniqueness in the order.]

Description [Returns 1 if the element was found, and 0 if it was new. ]

SideEffects []

SeeAlso []

Definition at line 261 of file fraigVec.c.

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 }
void Fraig_NodeVecPushOrder(Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
Definition: fraigVec.c:233
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
int Fraig_NodeVecPushUniqueOrderByLevel ( Fraig_NodeVec_t p,
Fraig_Node_t pNode 
)

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

Synopsis [Add the element while ensuring uniqueness in the order.]

Description [Returns 1 if the element was found, and 0 if it was new. ]

SideEffects []

SeeAlso []

Definition at line 310 of file fraigVec.c.

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 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecPushOrderByLevel(Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
Definition: fraigVec.c:282
Fraig_Node_t** Fraig_NodeVecReadArray ( Fraig_NodeVec_t p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 105 of file fraigVec.c.

106 {
107  return p->pArray;
108 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
Fraig_Node_t* Fraig_NodeVecReadEntry ( Fraig_NodeVec_t p,
int  i 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 387 of file fraigVec.c.

388 {
389  assert( i >= 0 && i < p->nSize );
390  return p->pArray[i];
391 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
#define assert(ex)
Definition: util_old.h:213
int Fraig_NodeVecReadSize ( Fraig_NodeVec_t p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 121 of file fraigVec.c.

122 {
123  return p->nSize;
124 }
void Fraig_NodeVecRemove ( Fraig_NodeVec_t p,
Fraig_Node_t Entry 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 347 of file fraigVec.c.

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 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
#define assert(ex)
Definition: util_old.h:213
void Fraig_NodeVecShrink ( Fraig_NodeVec_t p,
int  nSizeNew 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 156 of file fraigVec.c.

157 {
158  assert( p->nSize >= nSizeNew );
159  p->nSize = nSizeNew;
160 }
#define assert(ex)
Definition: util_old.h:213
void Fraig_NodeVecSortByLevel ( Fraig_NodeVec_t p,
int  fIncreasing 
)

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

Synopsis [Sorting the entries by their integer value.]

Description []

SideEffects []

SeeAlso []

Definition at line 501 of file fraigVec.c.

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 }
int Fraig_NodeVecCompareLevelsIncreasing(Fraig_Node_t **pp1, Fraig_Node_t **pp2)
Definition: fraigVec.c:404
int Fraig_NodeVecCompareLevelsDecreasing(Fraig_Node_t **pp1, Fraig_Node_t **pp2)
Definition: fraigVec.c:426
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecSortByNumber ( Fraig_NodeVec_t p)

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

Synopsis [Sorting the entries by their integer value.]

Description []

SideEffects []

SeeAlso []

Definition at line 522 of file fraigVec.c.

523 {
524  qsort( (void *)p->pArray, p->nSize, sizeof(Fraig_Node_t *),
525  (int (*)(const void *, const void *)) Fraig_NodeVecCompareNumbers );
526 }
int Fraig_NodeVecCompareNumbers(Fraig_Node_t **pp1, Fraig_Node_t **pp2)
Definition: fraigVec.c:448
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
void Fraig_NodeVecSortByRefCount ( Fraig_NodeVec_t p)

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

Synopsis [Sorting the entries by their integer value.]

Description []

SideEffects []

SeeAlso []

Definition at line 539 of file fraigVec.c.

540 {
541  qsort( (void *)p->pArray, p->nSize, sizeof(Fraig_Node_t *),
542  (int (*)(const void *, const void *)) Fraig_NodeVecCompareRefCounts );
543 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
int Fraig_NodeVecCompareRefCounts(Fraig_Node_t **pp1, Fraig_Node_t **pp2)
Definition: fraigVec.c:470
void Fraig_NodeVecWriteEntry ( Fraig_NodeVec_t p,
int  i,
Fraig_Node_t Entry 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 370 of file fraigVec.c.

371 {
372  assert( i >= 0 && i < p->nSize );
373  p->pArray[i] = Entry;
374 }
Fraig_Node_t ** pArray
Definition: fraigInt.h:267
#define assert(ex)
Definition: util_old.h:213