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 ***********************************************************************/
Vec_BitAlloc(int nCap)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 ***********************************************************************/
Vec_BitStart(int nSize)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) * (size_t)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 ***********************************************************************/
Vec_BitStartFull(int nSize)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 * 32 );
128 p->nSize = nSize * 32;
129 memset( p->pArray, 0xff, sizeof(int) * (size_t)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 ***********************************************************************/
Vec_BitDup(Vec_Bit_t * pVec)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) * (size_t)(p->nCap >> 5) );
153 return p;
154 }
155
156 /**Function*************************************************************
157
158 Synopsis []
159
160 Description []
161
162 SideEffects []
163
164 SeeAlso []
165
166 ***********************************************************************/
Vec_BitFree(Vec_Bit_t * p)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 ***********************************************************************/
Vec_BitFreeP(Vec_Bit_t ** p)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 ***********************************************************************/
Vec_BitReleaseArray(Vec_Bit_t * p)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 ***********************************************************************/
Vec_BitArray(Vec_Bit_t * p)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 ***********************************************************************/
Vec_BitSize(Vec_Bit_t * p)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 ***********************************************************************/
Vec_BitCap(Vec_Bit_t * p)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 ***********************************************************************/
Vec_BitMemory(Vec_Bit_t * p)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 ***********************************************************************/
Vec_BitEntry(Vec_Bit_t * p,int i)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 ***********************************************************************/
Vec_BitWriteEntry(Vec_Bit_t * p,int i,int Entry)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 }
Vec_BitAddEntry(Vec_Bit_t * p,int i)313 static inline int Vec_BitAddEntry( Vec_Bit_t * p, int i )
314 {
315 if ( Vec_BitEntry(p, i) )
316 return 1;
317 Vec_BitWriteEntry( p, i, 1 );
318 return 0;
319 }
320
321 /**Function*************************************************************
322
323 Synopsis []
324
325 Description []
326
327 SideEffects []
328
329 SeeAlso []
330
331 ***********************************************************************/
Vec_BitEntryLast(Vec_Bit_t * p)332 static inline int Vec_BitEntryLast( Vec_Bit_t * p )
333 {
334 assert( p->nSize > 0 );
335 return Vec_BitEntry( p, p->nSize-1 );
336 }
337
338 /**Function*************************************************************
339
340 Synopsis [Resizes the vector to the given capacity.]
341
342 Description []
343
344 SideEffects []
345
346 SeeAlso []
347
348 ***********************************************************************/
Vec_BitGrow(Vec_Bit_t * p,int nCapMin)349 static inline void Vec_BitGrow( Vec_Bit_t * p, int nCapMin )
350 {
351 if ( p->nCap >= nCapMin )
352 return;
353 nCapMin = (nCapMin >> 5) + ((nCapMin & 31) > 0);
354 p->pArray = ABC_REALLOC( int, p->pArray, nCapMin );
355 assert( p->pArray );
356 p->nCap = nCapMin * 32;
357 }
358
359 /**Function*************************************************************
360
361 Synopsis [Fills the vector with given number of entries.]
362
363 Description []
364
365 SideEffects []
366
367 SeeAlso []
368
369 ***********************************************************************/
Vec_BitFill(Vec_Bit_t * p,int nSize,int Fill)370 static inline void Vec_BitFill( Vec_Bit_t * p, int nSize, int Fill )
371 {
372 int i;
373 Vec_BitGrow( p, nSize );
374 nSize = (nSize >> 5) + ((nSize & 31) > 0);
375 if ( Fill == 0 )
376 {
377 for ( i = 0; i < nSize; i++ )
378 p->pArray[i] = 0;
379 }
380 else if ( Fill == 1 )
381 {
382 for ( i = 0; i < nSize; i++ )
383 p->pArray[i] = ~0;
384 }
385 else assert( 0 );
386 p->nSize = nSize * 32;
387 }
388
389 /**Function*************************************************************
390
391 Synopsis [Fills the vector with given number of entries.]
392
393 Description []
394
395 SideEffects []
396
397 SeeAlso []
398
399 ***********************************************************************/
Vec_BitFillExtra(Vec_Bit_t * p,int nSize,int Fill)400 static inline void Vec_BitFillExtra( Vec_Bit_t * p, int nSize, int Fill )
401 {
402 int i;
403 if ( nSize <= p->nSize )
404 return;
405 if ( nSize > 2 * p->nCap )
406 Vec_BitGrow( p, nSize );
407 else if ( nSize > p->nCap )
408 Vec_BitGrow( p, 2 * p->nCap );
409
410 assert( p->nSize < nSize );
411 if ( (p->nSize >> 5) == (nSize >> 5) )
412 {
413 unsigned Mask = (~(~0 << (nSize-p->nSize)) << p->nSize);
414 if ( Fill == 1 )
415 p->pArray[nSize >> 5] |= Mask;
416 else if ( Fill == 0 )
417 p->pArray[nSize >> 5] &= ~Mask;
418 else assert( 0 );
419 }
420 else
421 {
422 unsigned Mask1 = (p->nSize & 31) ? ~0 << (p->nSize & 31) : 0;
423 unsigned Mask2 = (nSize & 31) ? ~(~0 << (nSize & 31)) : 0;
424 int w1 = (p->nSize >> 5);
425 int w2 = (nSize >> 5);
426 if ( Fill == 1 )
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 if ( Fill == 0 )
434 {
435 p->pArray[w1] &= ~Mask1;
436 p->pArray[w2] &= ~Mask2;
437 for ( i = w1 + 1; i < w2; i++ )
438 p->pArray[i] = 0;
439 }
440 else assert( 0 );
441 }
442 p->nSize = nSize;
443 }
444
445 /**Function*************************************************************
446
447 Synopsis [Returns the entry even if the place not exist.]
448
449 Description []
450
451 SideEffects []
452
453 SeeAlso []
454
455 ***********************************************************************/
Vec_BitGetEntry(Vec_Bit_t * p,int i)456 static inline int Vec_BitGetEntry( Vec_Bit_t * p, int i )
457 {
458 Vec_BitFillExtra( p, i + 1, 0 );
459 return Vec_BitEntry( p, i );
460 }
461
462 /**Function*************************************************************
463
464 Synopsis [Inserts the entry even if the place does not exist.]
465
466 Description []
467
468 SideEffects []
469
470 SeeAlso []
471
472 ***********************************************************************/
Vec_BitSetEntry(Vec_Bit_t * p,int i,int Entry)473 static inline void Vec_BitSetEntry( Vec_Bit_t * p, int i, int Entry )
474 {
475 Vec_BitFillExtra( p, i + 1, 0 );
476 Vec_BitWriteEntry( p, i, Entry );
477 }
478
479 /**Function*************************************************************
480
481 Synopsis []
482
483 Description []
484
485 SideEffects []
486
487 SeeAlso []
488
489 ***********************************************************************/
Vec_BitShrink(Vec_Bit_t * p,int nSizeNew)490 static inline void Vec_BitShrink( Vec_Bit_t * p, int nSizeNew )
491 {
492 assert( p->nSize >= nSizeNew );
493 p->nSize = nSizeNew;
494 }
495
496 /**Function*************************************************************
497
498 Synopsis []
499
500 Description []
501
502 SideEffects []
503
504 SeeAlso []
505
506 ***********************************************************************/
Vec_BitClear(Vec_Bit_t * p)507 static inline void Vec_BitClear( Vec_Bit_t * p )
508 {
509 p->nSize = 0;
510 }
511
512 /**Function*************************************************************
513
514 Synopsis []
515
516 Description []
517
518 SideEffects []
519
520 SeeAlso []
521
522 ***********************************************************************/
Vec_BitPush(Vec_Bit_t * p,int Entry)523 static inline void Vec_BitPush( Vec_Bit_t * p, int Entry )
524 {
525 if ( p->nSize == p->nCap )
526 {
527 if ( p->nCap < 16 )
528 Vec_BitGrow( p, 16 );
529 else
530 Vec_BitGrow( p, 2 * p->nCap );
531 }
532 if ( Entry == 1 )
533 p->pArray[p->nSize >> 5] |= (1 << (p->nSize & 31));
534 else if ( Entry == 0 )
535 p->pArray[p->nSize >> 5] &= ~(1 << (p->nSize & 31));
536 else assert( 0 );
537 p->nSize++;
538 }
539
540 /**Function*************************************************************
541
542 Synopsis [Returns the last entry and removes it from the list.]
543
544 Description []
545
546 SideEffects []
547
548 SeeAlso []
549
550 ***********************************************************************/
Vec_BitPop(Vec_Bit_t * p)551 static inline int Vec_BitPop( Vec_Bit_t * p )
552 {
553 int Entry;
554 assert( p->nSize > 0 );
555 Entry = Vec_BitEntryLast( p );
556 p->nSize--;
557 return Entry;
558 }
559
560 /**Function*************************************************************
561
562 Synopsis []
563
564 Description []
565
566 SideEffects []
567
568 SeeAlso []
569
570 ***********************************************************************/
Vec_BitCountWord(unsigned uWord)571 static inline int Vec_BitCountWord( unsigned uWord )
572 {
573 uWord = (uWord & 0x55555555) + ((uWord>>1) & 0x55555555);
574 uWord = (uWord & 0x33333333) + ((uWord>>2) & 0x33333333);
575 uWord = (uWord & 0x0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F);
576 uWord = (uWord & 0x00FF00FF) + ((uWord>>8) & 0x00FF00FF);
577 return (uWord & 0x0000FFFF) + (uWord>>16);
578 }
579
580 /**Function*************************************************************
581
582 Synopsis []
583
584 Description []
585
586 SideEffects []
587
588 SeeAlso []
589
590 ***********************************************************************/
Vec_BitCount(Vec_Bit_t * p)591 static inline int Vec_BitCount( Vec_Bit_t * p )
592 {
593 unsigned * pArray = (unsigned *)p->pArray;
594 int nWords = (p->nSize >> 5) + ((p->nSize & 31) > 0);
595 int i, Counter = 0;
596 if ( p->nSize & 31 )
597 {
598 assert( nWords > 0 );
599 for ( i = 0; i < nWords-1; i++ )
600 Counter += Vec_BitCountWord( pArray[i] );
601 Counter += Vec_BitCountWord( pArray[i] & ~(~0 << (p->nSize & 31)) );
602 }
603 else
604 {
605 for ( i = 0; i < nWords; i++ )
606 Counter += Vec_BitCountWord( pArray[i] );
607 }
608 return Counter;
609 }
610
611 /**Function*************************************************************
612
613 Synopsis []
614
615 Description []
616
617 SideEffects []
618
619 SeeAlso []
620
621 ***********************************************************************/
Vec_BitReset(Vec_Bit_t * p)622 static inline void Vec_BitReset( Vec_Bit_t * p )
623 {
624 int i, nWords = (p->nSize >> 5) + ((p->nSize & 31) > 0);
625 for ( i = 0; i < nWords; i++ )
626 p->pArray[i] = 0;
627 }
628
629 ABC_NAMESPACE_HEADER_END
630
631 #endif
632
633 ////////////////////////////////////////////////////////////////////////
634 /// END OF FILE ///
635 ////////////////////////////////////////////////////////////////////////
636
637