abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
vecBit.h
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [vecBit.h]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Resizable arrays.]
8 
9  Synopsis [Resizable arrays of bits.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: vecBit.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #ifndef ABC__misc__vec__vecBit_h
22 #define ABC__misc__vec__vecBit_h
23 
24 
25 ////////////////////////////////////////////////////////////////////////
26 /// INCLUDES ///
27 ////////////////////////////////////////////////////////////////////////
28 
29 #include <stdio.h>
30 
31 ABC_NAMESPACE_HEADER_START
32 
33 
34 ////////////////////////////////////////////////////////////////////////
35 /// PARAMETERS ///
36 ////////////////////////////////////////////////////////////////////////
37 
38 ////////////////////////////////////////////////////////////////////////
39 /// BASIC TYPES ///
40 ////////////////////////////////////////////////////////////////////////
41 
42 typedef struct Vec_Bit_t_ Vec_Bit_t;
43 struct Vec_Bit_t_
44 {
45  int nCap;
46  int nSize;
47  int * pArray;
48 };
49 
50 ////////////////////////////////////////////////////////////////////////
51 /// MACRO DEFINITIONS ///
52 ////////////////////////////////////////////////////////////////////////
53 
54 #define Vec_BitForEachEntry( vVec, Entry, i ) \
55  for ( i = 0; (i < Vec_BitSize(vVec)) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )
56 #define Vec_BitForEachEntryStart( vVec, Entry, i, Start ) \
57  for ( i = Start; (i < Vec_BitSize(vVec)) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )
58 #define Vec_BitForEachEntryStop( vVec, Entry, i, Stop ) \
59  for ( i = 0; (i < Stop) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )
60 #define Vec_BitForEachEntryStartStop( vVec, Entry, i, Start, Stop ) \
61  for ( i = Start; (i < Stop) && (((Entry) = Vec_BitEntry(vVec, i)), 1); i++ )
62 #define Vec_BitForEachEntryReverse( vVec, pEntry, i ) \
63  for ( i = Vec_BitSize(vVec) - 1; (i >= 0) && (((pEntry) = Vec_BitEntry(vVec, i)), 1); i-- )
64 
65 ////////////////////////////////////////////////////////////////////////
66 /// FUNCTION DEFINITIONS ///
67 ////////////////////////////////////////////////////////////////////////
68 
69 /**Function*************************************************************
70 
71  Synopsis [Allocates a vector with the given capacity.]
72 
73  Description []
74 
75  SideEffects []
76 
77  SeeAlso []
78 
79 ***********************************************************************/
80 static inline Vec_Bit_t * Vec_BitAlloc( int nCap )
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 }
90 
91 /**Function*************************************************************
92 
93  Synopsis [Allocates a vector with the given size and cleans it.]
94 
95  Description []
96 
97  SideEffects []
98 
99  SeeAlso []
100 
101 ***********************************************************************/
102 static inline Vec_Bit_t * Vec_BitStart( int nSize )
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 }
111 
112 /**Function*************************************************************
113 
114  Synopsis [Allocates a vector with the given size and cleans it.]
115 
116  Description []
117 
118  SideEffects []
119 
120  SeeAlso []
121 
122 ***********************************************************************/
123 static inline Vec_Bit_t * Vec_BitStartFull( int nSize )
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 }
132 
133 /**Function*************************************************************
134 
135  Synopsis [Duplicates the integer array.]
136 
137  Description []
138 
139  SideEffects []
140 
141  SeeAlso []
142 
143 ***********************************************************************/
144 static inline Vec_Bit_t * Vec_BitDup( Vec_Bit_t * pVec )
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 }
155 
156 /**Function*************************************************************
157 
158  Synopsis []
159 
160  Description []
161 
162  SideEffects []
163 
164  SeeAlso []
165 
166 ***********************************************************************/
167 static inline void Vec_BitFree( Vec_Bit_t * p )
168 {
169  ABC_FREE( p->pArray );
170  ABC_FREE( p );
171 }
172 
173 /**Function*************************************************************
174 
175  Synopsis []
176 
177  Description []
178 
179  SideEffects []
180 
181  SeeAlso []
182 
183 ***********************************************************************/
184 static inline void Vec_BitFreeP( Vec_Bit_t ** p )
185 {
186  if ( *p == NULL )
187  return;
188  ABC_FREE( (*p)->pArray );
189  ABC_FREE( (*p) );
190 }
191 
192 /**Function*************************************************************
193 
194  Synopsis []
195 
196  Description []
197 
198  SideEffects []
199 
200  SeeAlso []
201 
202 ***********************************************************************/
203 static inline int * Vec_BitReleaseArray( Vec_Bit_t * p )
204 {
205  int * pArray = p->pArray;
206  p->nCap = 0;
207  p->nSize = 0;
208  p->pArray = NULL;
209  return pArray;
210 }
211 
212 /**Function*************************************************************
213 
214  Synopsis []
215 
216  Description []
217 
218  SideEffects []
219 
220  SeeAlso []
221 
222 ***********************************************************************/
223 static inline int * Vec_BitArray( Vec_Bit_t * p )
224 {
225  return p->pArray;
226 }
227 
228 /**Function*************************************************************
229 
230  Synopsis []
231 
232  Description []
233 
234  SideEffects []
235 
236  SeeAlso []
237 
238 ***********************************************************************/
239 static inline int Vec_BitSize( Vec_Bit_t * p )
240 {
241  return p->nSize;
242 }
243 
244 /**Function*************************************************************
245 
246  Synopsis []
247 
248  Description []
249 
250  SideEffects []
251 
252  SeeAlso []
253 
254 ***********************************************************************/
255 static inline int Vec_BitCap( Vec_Bit_t * p )
256 {
257  return p->nCap;
258 }
259 
260 /**Function*************************************************************
261 
262  Synopsis []
263 
264  Description []
265 
266  SideEffects []
267 
268  SeeAlso []
269 
270 ***********************************************************************/
271 static inline double Vec_BitMemory( Vec_Bit_t * p )
272 {
273  return !p ? 0.0 : 1.0 * sizeof(int) * p->nCap + sizeof(Vec_Bit_t);
274 }
275 
276 /**Function*************************************************************
277 
278  Synopsis []
279 
280  Description []
281 
282  SideEffects []
283 
284  SeeAlso []
285 
286 ***********************************************************************/
287 static inline int Vec_BitEntry( Vec_Bit_t * p, int i )
288 {
289  assert( i >= 0 && i < p->nSize );
290  return (p->pArray[i >> 5] >> (i & 31)) & 1;
291 }
292 
293 /**Function*************************************************************
294 
295  Synopsis []
296 
297  Description []
298 
299  SideEffects []
300 
301  SeeAlso []
302 
303 ***********************************************************************/
304 static inline void Vec_BitWriteEntry( Vec_Bit_t * p, int i, int Entry )
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 }
313 
314 /**Function*************************************************************
315 
316  Synopsis []
317 
318  Description []
319 
320  SideEffects []
321 
322  SeeAlso []
323 
324 ***********************************************************************/
325 static inline int Vec_BitEntryLast( Vec_Bit_t * p )
326 {
327  assert( p->nSize > 0 );
328  return Vec_BitEntry( p, p->nSize-1 );
329 }
330 
331 /**Function*************************************************************
332 
333  Synopsis [Resizes the vector to the given capacity.]
334 
335  Description []
336 
337  SideEffects []
338 
339  SeeAlso []
340 
341 ***********************************************************************/
342 static inline void Vec_BitGrow( Vec_Bit_t * p, int nCapMin )
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 }
351 
352 /**Function*************************************************************
353 
354  Synopsis [Fills the vector with given number of entries.]
355 
356  Description []
357 
358  SideEffects []
359 
360  SeeAlso []
361 
362 ***********************************************************************/
363 static inline void Vec_BitFill( Vec_Bit_t * p, int nSize, int Fill )
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 }
381 
382 /**Function*************************************************************
383 
384  Synopsis [Fills the vector with given number of entries.]
385 
386  Description []
387 
388  SideEffects []
389 
390  SeeAlso []
391 
392 ***********************************************************************/
393 static inline void Vec_BitFillExtra( Vec_Bit_t * p, int nSize, int Fill )
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 }
437 
438 /**Function*************************************************************
439 
440  Synopsis [Returns the entry even if the place not exist.]
441 
442  Description []
443 
444  SideEffects []
445 
446  SeeAlso []
447 
448 ***********************************************************************/
449 static inline int Vec_BitGetEntry( Vec_Bit_t * p, int i )
450 {
451  Vec_BitFillExtra( p, i + 1, 0 );
452  return Vec_BitEntry( p, i );
453 }
454 
455 /**Function*************************************************************
456 
457  Synopsis [Inserts the entry even if the place does not exist.]
458 
459  Description []
460 
461  SideEffects []
462 
463  SeeAlso []
464 
465 ***********************************************************************/
466 static inline void Vec_BitSetEntry( Vec_Bit_t * p, int i, int Entry )
467 {
468  Vec_BitFillExtra( p, i + 1, 0 );
469  Vec_BitWriteEntry( p, i, Entry );
470 }
471 
472 /**Function*************************************************************
473 
474  Synopsis []
475 
476  Description []
477 
478  SideEffects []
479 
480  SeeAlso []
481 
482 ***********************************************************************/
483 static inline void Vec_BitShrink( Vec_Bit_t * p, int nSizeNew )
484 {
485  assert( p->nSize >= nSizeNew );
486  p->nSize = nSizeNew;
487 }
488 
489 /**Function*************************************************************
490 
491  Synopsis []
492 
493  Description []
494 
495  SideEffects []
496 
497  SeeAlso []
498 
499 ***********************************************************************/
500 static inline void Vec_BitClear( Vec_Bit_t * p )
501 {
502  p->nSize = 0;
503 }
504 
505 /**Function*************************************************************
506 
507  Synopsis []
508 
509  Description []
510 
511  SideEffects []
512 
513  SeeAlso []
514 
515 ***********************************************************************/
516 static inline void Vec_BitPush( Vec_Bit_t * p, int Entry )
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 }
532 
533 /**Function*************************************************************
534 
535  Synopsis [Returns the last entry and removes it from the list.]
536 
537  Description []
538 
539  SideEffects []
540 
541  SeeAlso []
542 
543 ***********************************************************************/
544 static inline int Vec_BitPop( Vec_Bit_t * p )
545 {
546  int Entry;
547  assert( p->nSize > 0 );
548  Entry = Vec_BitEntryLast( p );
549  p->nSize--;
550  return Entry;
551 }
552 
553 /**Function*************************************************************
554 
555  Synopsis []
556 
557  Description []
558 
559  SideEffects []
560 
561  SeeAlso []
562 
563 ***********************************************************************/
564 static inline int Vec_BitCountWord( unsigned uWord )
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 }
572 
573 /**Function*************************************************************
574 
575  Synopsis []
576 
577  Description []
578 
579  SideEffects []
580 
581  SeeAlso []
582 
583 ***********************************************************************/
584 static inline int Vec_BitCount( Vec_Bit_t * p )
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 }
603 
604 ABC_NAMESPACE_HEADER_END
605 
606 #endif
607 
608 ////////////////////////////////////////////////////////////////////////
609 /// END OF FILE ///
610 ////////////////////////////////////////////////////////////////////////
611 
memset
char * memset()
Vec_BitSetEntry
static void Vec_BitSetEntry(Vec_Bit_t *p, int i, int Entry)
Definition: vecBit.h:466
Vec_BitGetEntry
static int Vec_BitGetEntry(Vec_Bit_t *p, int i)
Definition: vecBit.h:449
Vec_BitShrink
static void Vec_BitShrink(Vec_Bit_t *p, int nSizeNew)
Definition: vecBit.h:483
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_BitPop
static int Vec_BitPop(Vec_Bit_t *p)
Definition: vecBit.h:544
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
Vec_BitDup
static Vec_Bit_t * Vec_BitDup(Vec_Bit_t *pVec)
Definition: vecBit.h:144
memcpy
char * memcpy()
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Vec_BitFill
static void Vec_BitFill(Vec_Bit_t *p, int nSize, int Fill)
Definition: vecBit.h:363
Vec_BitStartFull
static Vec_Bit_t * Vec_BitStartFull(int nSize)
Definition: vecBit.h:123
Vec_BitFreeP
static void Vec_BitFreeP(Vec_Bit_t **p)
Definition: vecBit.h:184
Vec_BitWriteEntry
static void Vec_BitWriteEntry(Vec_Bit_t *p, int i, int Entry)
Definition: vecBit.h:304
nWords
int nWords
Definition: abcNpn.c:127
Vec_Bit_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Bit_t_ Vec_Bit_t
INCLUDES ///.
Definition: vecBit.h:42
Vec_BitArray
static int * Vec_BitArray(Vec_Bit_t *p)
Definition: vecBit.h:223
Vec_BitCountWord
static int Vec_BitCountWord(unsigned uWord)
Definition: vecBit.h:564
Vec_BitStart
static Vec_Bit_t * Vec_BitStart(int nSize)
Definition: vecBit.h:102
Vec_Bit_t_::nCap
int nCap
Definition: vecBit.h:45
Vec_BitReleaseArray
static int * Vec_BitReleaseArray(Vec_Bit_t *p)
Definition: vecBit.h:203
Vec_Bit_t_::pArray
int * pArray
Definition: vecBit.h:47
Counter
static int Counter
Definition: extraBddMisc.c:1877
ABC_NAMESPACE_HEADER_START
#define ABC_NAMESPACE_HEADER_START
NAMESPACES ///.
Definition: abc_global.h:105
Vec_BitAlloc
static Vec_Bit_t * Vec_BitAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecBit.h:80
ABC_NAMESPACE_HEADER_END
#define ABC_NAMESPACE_HEADER_END
Definition: abc_global.h:106
Vec_BitCap
static int Vec_BitCap(Vec_Bit_t *p)
Definition: vecBit.h:255
Vec_BitSize
static int Vec_BitSize(Vec_Bit_t *p)
Definition: vecBit.h:239
Vec_BitFillExtra
static void Vec_BitFillExtra(Vec_Bit_t *p, int nSize, int Fill)
Definition: vecBit.h:393
Vec_BitEntryLast
static int Vec_BitEntryLast(Vec_Bit_t *p)
Definition: vecBit.h:325
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Vec_BitEntry
static int Vec_BitEntry(Vec_Bit_t *p, int i)
Definition: vecBit.h:287
Vec_BitFree
static void Vec_BitFree(Vec_Bit_t *p)
Definition: vecBit.h:167
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
Vec_BitCount
static int Vec_BitCount(Vec_Bit_t *p)
Definition: vecBit.h:584
Vec_BitPush
static void Vec_BitPush(Vec_Bit_t *p, int Entry)
Definition: vecBit.h:516
Vec_Bit_t_::nSize
int nSize
Definition: vecBit.h:46
Vec_BitClear
static void Vec_BitClear(Vec_Bit_t *p)
Definition: vecBit.h:500
Vec_Bit_t_
Definition: vecBit.h:43
Vec_BitMemory
static double Vec_BitMemory(Vec_Bit_t *p)
Definition: vecBit.h:271