abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Data Structures | Macros | Typedefs | Functions
vecBit.h File Reference
#include <stdio.h>

Go to the source code of this file.

Data Structures

struct  Vec_Bit_t_
 

Macros

#define Vec_BitForEachEntry(vVec, Entry, i)   for ( i = 0; (i < Vec_BitSize(vVec)) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )
 MACRO DEFINITIONS ///. More...
 
#define Vec_BitForEachEntryStart(vVec, Entry, i, Start)   for ( i = Start; (i < Vec_BitSize(vVec)) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )
 
#define Vec_BitForEachEntryStop(vVec, Entry, i, Stop)   for ( i = 0; (i < Stop) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )
 
#define Vec_BitForEachEntryStartStop(vVec, Entry, i, Start, Stop)   for ( i = Start; (i < Stop) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )
 
#define Vec_BitForEachEntryReverse(vVec, pEntry, i)   for ( i = Vec_BitSize(vVec) - 1; (i >= 0) && (((pEntry) = Vec_BitEntry(vVec, i)), 1); i-- )
 

Typedefs

typedef
typedefABC_NAMESPACE_HEADER_START
struct Vec_Bit_t_ 		Vec_Bit_t
 INCLUDES ///. More...
 

Functions

static Vec_Bit_t * Vec_BitAlloc (int nCap)
 FUNCTION DEFINITIONS ///. More...
 
static Vec_Bit_t * Vec_BitStart (int nSize)
 
static Vec_Bit_t * Vec_BitStartFull (int nSize)
 
static Vec_Bit_t * Vec_BitDup (Vec_Bit_t *pVec)
 
static void Vec_BitFree (Vec_Bit_t *p)
 
static void Vec_BitFreeP (Vec_Bit_t **p)
 
static int * Vec_BitReleaseArray (Vec_Bit_t *p)
 
static int * Vec_BitArray (Vec_Bit_t *p)
 
static int Vec_BitSize (Vec_Bit_t *p)
 
static int Vec_BitCap (Vec_Bit_t *p)
 
static double Vec_BitMemory (Vec_Bit_t *p)
 
static int Vec_BitEntry (Vec_Bit_t *p, int i)
 
static void Vec_BitWriteEntry (Vec_Bit_t *p, int i, int Entry)
 
static int Vec_BitEntryLast (Vec_Bit_t *p)
 
static void Vec_BitGrow (Vec_Bit_t *p, int nCapMin)
 
static void Vec_BitFill (Vec_Bit_t *p, int nSize, int Fill)
 
static void Vec_BitFillExtra (Vec_Bit_t *p, int nSize, int Fill)
 
static int Vec_BitGetEntry (Vec_Bit_t *p, int i)
 
static void Vec_BitSetEntry (Vec_Bit_t *p, int i, int Entry)
 
static void Vec_BitShrink (Vec_Bit_t *p, int nSizeNew)
 
static void Vec_BitClear (Vec_Bit_t *p)
 
static void Vec_BitPush (Vec_Bit_t *p, int Entry)
 
static int Vec_BitPop (Vec_Bit_t *p)
 
static int Vec_BitCountWord (unsigned uWord)
 
static int Vec_BitCount (Vec_Bit_t *p)
 

Macro Definition Documentation

#define Vec_BitForEachEntry (   vVec,
  Entry,
  i 
)    for ( i = 0; (i < Vec_BitSize(vVec)) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )

MACRO DEFINITIONS ///.

Definition at line 54 of file vecBit.h.

#define Vec_BitForEachEntryReverse (   vVec,
  pEntry,
  i 
)    for ( i = Vec_BitSize(vVec) - 1; (i >= 0) && (((pEntry) = Vec_BitEntry(vVec, i)), 1); i-- )

Definition at line 62 of file vecBit.h.

#define Vec_BitForEachEntryStart (   vVec,
  Entry,
  i,
  Start 
)    for ( i = Start; (i < Vec_BitSize(vVec)) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )

Definition at line 56 of file vecBit.h.

#define Vec_BitForEachEntryStartStop (   vVec,
  Entry,
  i,
  Start,
  Stop 
)    for ( i = Start; (i < Stop) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )

Definition at line 60 of file vecBit.h.

#define Vec_BitForEachEntryStop (   vVec,
  Entry,
  i,
  Stop 
)    for ( i = 0; (i < Stop) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )

Definition at line 58 of file vecBit.h.

Typedef Documentation

typedef typedefABC_NAMESPACE_HEADER_START struct Vec_Bit_t_ Vec_Bit_t

INCLUDES ///.

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

FileName [vecBit.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Resizable arrays.]

Synopsis [Resizable arrays of bits.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:
vecBit.h,v 1.00 2005/06/20 00:00:00 alanmi Exp

]PARAMETERS ///BASIC TYPES ///

Definition at line 42 of file vecBit.h.

Function Documentation

static Vec_Bit_t* Vec_BitAlloc ( int  nCap)
inlinestatic

FUNCTION DEFINITIONS ///.

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

Synopsis [Allocates a vector with the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 80 of file vecBit.h.

81 {
82  Vec_Bit_t * p;
83  nCap = (nCap >> 5) + ((nCap & 31) > 0);
84  p = ABC_ALLOC( Vec_Bit_t, 1 );
85  p->nSize = 0;
86  p->nCap = nCap * 32;
87  p->pArray = nCap? ABC_ALLOC( int, nCap ) : NULL;
88  return p;
89 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Vec_Bit_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Bit_t_ Vec_Bit_t
INCLUDES ///.
Definition: vecBit.h:42
static int* Vec_BitArray ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 223 of file vecBit.h.

224 {
225  return p->pArray;
226 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
static int Vec_BitCap ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 255 of file vecBit.h.

256 {
257  return p->nCap;
258 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
static void Vec_BitClear ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 500 of file vecBit.h.

501 {
502  p->nSize = 0;
503 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
static int Vec_BitCount ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 584 of file vecBit.h.

585 {
586  unsigned * pArray = (unsigned *)p->pArray;
587  int nWords = (p->nSize >> 5) + ((p->nSize & 31) > 0);
588  int i, Counter = 0;
589  if ( p->nSize & 31 )
590  {
591  assert( nWords > 0 );
592  for ( i = 0; i < nWords-1; i++ )
593  Counter += Vec_BitCountWord( pArray[i] );
594  Counter += Vec_BitCountWord( pArray[i] & ~(~0 << (p->nSize & 31)) );
595  }
596  else
597  {
598  for ( i = 0; i < nWords; i++ )
599  Counter += Vec_BitCountWord( pArray[i] );
600  }
601  return Counter;
602 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
nWords
int nWords
Definition: abcNpn.c:127
Vec_BitCountWord
static int Vec_BitCountWord(unsigned uWord)
Definition: vecBit.h:564
Counter
static int Counter
Definition: extraBddMisc.c:1877
assert
#define assert(ex)
Definition: util_old.h:213
static int Vec_BitCountWord ( unsigned  uWord)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 564 of file vecBit.h.

565 {
566  uWord = (uWord & 0x55555555) + ((uWord>>1) & 0x55555555);
567  uWord = (uWord & 0x33333333) + ((uWord>>2) & 0x33333333);
568  uWord = (uWord & 0x0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F);
569  uWord = (uWord & 0x00FF00FF) + ((uWord>>8) & 0x00FF00FF);
570  return (uWord & 0x0000FFFF) + (uWord>>16);
571 }
static Vec_Bit_t* Vec_BitDup ( Vec_Bit_t *  pVec)
inlinestatic

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

Synopsis [Duplicates the integer array.]

Description []

SideEffects []

SeeAlso []

Definition at line 144 of file vecBit.h.

145 {
146  Vec_Bit_t * p;
147  assert( (pVec->nSize & 31) == 0 );
148  p = ABC_ALLOC( Vec_Bit_t, 1 );
149  p->nSize = pVec->nSize;
150  p->nCap = pVec->nSize;
151  p->pArray = p->nCap? ABC_ALLOC( int, p->nCap >> 5 ) : NULL;
152  memcpy( p->pArray, pVec->pArray, sizeof(int) * (p->nCap >> 5) );
153  return p;
154 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
memcpy
char * memcpy()
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Vec_Bit_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Bit_t_ Vec_Bit_t
INCLUDES ///.
Definition: vecBit.h:42
assert
#define assert(ex)
Definition: util_old.h:213
static int Vec_BitEntry ( Vec_Bit_t *  p,
int  i 
)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 287 of file vecBit.h.

288 {
289  assert( i >= 0 && i < p->nSize );
290  return (p->pArray[i >> 5] >> (i & 31)) & 1;
291 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
assert
#define assert(ex)
Definition: util_old.h:213
static int Vec_BitEntryLast ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 325 of file vecBit.h.

326 {
327  assert( p->nSize > 0 );
328  return Vec_BitEntry( p, p->nSize-1 );
329 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_BitEntry
static int Vec_BitEntry(Vec_Bit_t *p, int i)
Definition: vecBit.h:287
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_BitFill ( Vec_Bit_t *  p,
int  nSize,
int  Fill 
)
inlinestatic

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

Synopsis [Fills the vector with given number of entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 363 of file vecBit.h.

364 {
365  int i;
366  Vec_BitGrow( p, nSize );
367  nSize = (nSize >> 5) + ((nSize & 31) > 0);
368  if ( Fill == 0 )
369  {
370  for ( i = 0; i < nSize; i++ )
371  p->pArray[i] = 0;
372  }
373  else if ( Fill == 1 )
374  {
375  for ( i = 0; i < nSize; i++ )
376  p->pArray[i] = ~0;
377  }
378  else assert( 0 );
379  p->nSize = nSize * 32;
380 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_BitGrow
static void Vec_BitGrow(Vec_Bit_t *p, int nCapMin)
Definition: vecBit.h:342
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_BitFillExtra ( Vec_Bit_t *  p,
int  nSize,
int  Fill 
)
inlinestatic

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

Synopsis [Fills the vector with given number of entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 393 of file vecBit.h.

394 {
395  int i;
396  if ( nSize <= p->nSize )
397  return;
398  if ( nSize > 2 * p->nCap )
399  Vec_BitGrow( p, nSize );
400  else if ( nSize > p->nCap )
401  Vec_BitGrow( p, 2 * p->nCap );
402 
403  assert( p->nSize < nSize );
404  if ( (p->nSize >> 5) == (nSize >> 5) )
405  {
406  unsigned Mask = (~(~0 << (nSize-p->nSize)) << p->nSize);
407  if ( Fill == 1 )
408  p->pArray[nSize >> 5] |= Mask;
409  else if ( Fill == 0 )
410  p->pArray[nSize >> 5] &= ~Mask;
411  else assert( 0 );
412  }
413  else
414  {
415  unsigned Mask1 = (p->nSize & 31) ? ~0 << (p->nSize & 31) : 0;
416  unsigned Mask2 = (nSize & 31) ? ~(~0 << (nSize & 31)) : 0;
417  int w1 = (p->nSize >> 5);
418  int w2 = (nSize >> 5);
419  if ( Fill == 1 )
420  {
421  p->pArray[w1] |= Mask1;
422  p->pArray[w2] |= Mask2;
423  for ( i = w1 + 1; i < w2; i++ )
424  p->pArray[i] = ~0;
425  }
426  else if ( Fill == 0 )
427  {
428  p->pArray[w1] &= ~Mask1;
429  p->pArray[w2] &= ~Mask2;
430  for ( i = w1 + 1; i < w2; i++ )
431  p->pArray[i] = 0;
432  }
433  else assert( 0 );
434  }
435  p->nSize = nSize;
436 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_BitGrow
static void Vec_BitGrow(Vec_Bit_t *p, int nCapMin)
Definition: vecBit.h:342
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_BitFree ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 167 of file vecBit.h.

168 {
169  ABC_FREE( p->pArray );
170  ABC_FREE( p );
171 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
static void Vec_BitFreeP ( Vec_Bit_t **  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 184 of file vecBit.h.

185 {
186  if ( *p == NULL )
187  return;
188  ABC_FREE( (*p)->pArray );
189  ABC_FREE( (*p) );
190 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
static int Vec_BitGetEntry ( Vec_Bit_t *  p,
int  i 
)
inlinestatic

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

Synopsis [Returns the entry even if the place not exist.]

Description []

SideEffects []

SeeAlso []

Definition at line 449 of file vecBit.h.

450 {
451  Vec_BitFillExtra( p, i + 1, 0 );
452  return Vec_BitEntry( p, i );
453 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_BitFillExtra
static void Vec_BitFillExtra(Vec_Bit_t *p, int nSize, int Fill)
Definition: vecBit.h:393
Vec_BitEntry
static int Vec_BitEntry(Vec_Bit_t *p, int i)
Definition: vecBit.h:287
static void Vec_BitGrow ( Vec_Bit_t *  p,
int  nCapMin 
)
inlinestatic

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

Synopsis [Resizes the vector to the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 342 of file vecBit.h.

343 {
344  if ( p->nCap >= nCapMin )
345  return;
346  nCapMin = (nCapMin >> 5) + ((nCapMin & 31) > 0);
347  p->pArray = ABC_REALLOC( int, p->pArray, nCapMin );
348  assert( p->pArray );
349  p->nCap = nCapMin * 32;
350 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
assert
#define assert(ex)
Definition: util_old.h:213
static double Vec_BitMemory ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 271 of file vecBit.h.

272 {
273  return !p ? 0.0 : 1.0 * sizeof(int) * p->nCap + sizeof(Vec_Bit_t);
274 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Bit_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Bit_t_ Vec_Bit_t
INCLUDES ///.
Definition: vecBit.h:42
static int Vec_BitPop ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis [Returns the last entry and removes it from the list.]

Description []

SideEffects []

SeeAlso []

Definition at line 544 of file vecBit.h.

545 {
546  int Entry;
547  assert( p->nSize > 0 );
548  Entry = Vec_BitEntryLast( p );
549  p->nSize--;
550  return Entry;
551 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_BitEntryLast
static int Vec_BitEntryLast(Vec_Bit_t *p)
Definition: vecBit.h:325
assert
#define assert(ex)
Definition: util_old.h:213
static void Vec_BitPush ( Vec_Bit_t *  p,
int  Entry 
)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 516 of file vecBit.h.

517 {
518  if ( p->nSize == p->nCap )
519  {
520  if ( p->nCap < 16 )
521  Vec_BitGrow( p, 16 );
522  else
523  Vec_BitGrow( p, 2 * p->nCap );
524  }
525  if ( Entry == 1 )
526  p->pArray[p->nSize >> 5] |= (1 << (p->nSize & 31));
527  else if ( Entry == 0 )
528  p->pArray[p->nSize >> 5] &= ~(1 << (p->nSize & 31));
529  else assert( 0 );
530  p->nSize++;
531 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_BitGrow
static void Vec_BitGrow(Vec_Bit_t *p, int nCapMin)
Definition: vecBit.h:342
assert
#define assert(ex)
Definition: util_old.h:213
static int* Vec_BitReleaseArray ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 203 of file vecBit.h.

204 {
205  int * pArray = p->pArray;
206  p->nCap = 0;
207  p->nSize = 0;
208  p->pArray = NULL;
209  return pArray;
210 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
static void Vec_BitSetEntry ( Vec_Bit_t *  p,
int  i,
int  Entry 
)
inlinestatic

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

Synopsis [Inserts the entry even if the place does not exist.]

Description []

SideEffects []

SeeAlso []

Definition at line 466 of file vecBit.h.

467 {
468  Vec_BitFillExtra( p, i + 1, 0 );
469  Vec_BitWriteEntry( p, i, Entry );
470 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_BitWriteEntry
static void Vec_BitWriteEntry(Vec_Bit_t *p, int i, int Entry)
Definition: vecBit.h:304
Vec_BitFillExtra
static void Vec_BitFillExtra(Vec_Bit_t *p, int nSize, int Fill)
Definition: vecBit.h:393
static void Vec_BitShrink ( Vec_Bit_t *  p,
int  nSizeNew 
)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 483 of file vecBit.h.

484 {
485  assert( p->nSize >= nSizeNew );
486  p->nSize = nSizeNew;
487 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
assert
#define assert(ex)
Definition: util_old.h:213
static int Vec_BitSize ( Vec_Bit_t *  p)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 239 of file vecBit.h.

240 {
241  return p->nSize;
242 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
static Vec_Bit_t* Vec_BitStart ( int  nSize)
inlinestatic

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

Synopsis [Allocates a vector with the given size and cleans it.]

Description []

SideEffects []

SeeAlso []

Definition at line 102 of file vecBit.h.

103 {
104  Vec_Bit_t * p;
105  nSize = (nSize >> 5) + ((nSize & 31) > 0);
106  p = Vec_BitAlloc( nSize * 32 );
107  p->nSize = nSize * 32;
108  memset( p->pArray, 0, sizeof(int) * nSize );
109  return p;
110 }
memset
char * memset()
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Bit_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Bit_t_ Vec_Bit_t
INCLUDES ///.
Definition: vecBit.h:42
Vec_BitAlloc
static Vec_Bit_t * Vec_BitAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecBit.h:80
static Vec_Bit_t* Vec_BitStartFull ( int  nSize)
inlinestatic

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

Synopsis [Allocates a vector with the given size and cleans it.]

Description []

SideEffects []

SeeAlso []

Definition at line 123 of file vecBit.h.

124 {
125  Vec_Bit_t * p;
126  nSize = (nSize >> 5) + ((nSize & 31) > 0);
127  p = Vec_BitAlloc( nSize );
128  p->nSize = nSize * 32;
129  memset( p->pArray, 0xff, sizeof(int) * nSize );
130  return p;
131 }
memset
char * memset()
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Bit_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Bit_t_ Vec_Bit_t
INCLUDES ///.
Definition: vecBit.h:42
Vec_BitAlloc
static Vec_Bit_t * Vec_BitAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecBit.h:80
static void Vec_BitWriteEntry ( Vec_Bit_t *  p,
int  i,
int  Entry 
)
inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 304 of file vecBit.h.

305 {
306  assert( i >= 0 && i < p->nSize );
307  if ( Entry == 1 )
308  p->pArray[i >> 5] |= (1 << (i & 31));
309  else if ( Entry == 0 )
310  p->pArray[i >> 5] &= ~(1 << (i & 31));
311  else assert(0);
312 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
assert
#define assert(ex)
Definition: util_old.h:213