2 * UCW Library -- Bit Array Operations
4 * (c) 2003--2006 Martin Mares <mj@ucw.cz>
5 * (c) 2012 Pavel Charvat <pchar@ucw.cz>
7 * This software may be freely distributed and used according to the terms
8 * of the GNU Lesser General Public License.
11 #ifndef _UCW_BITARRAY_H
12 #define _UCW_BITARRAY_H
16 typedef u32 *bitarray_t; // Must be initialized by bit_array_xmalloc(), bit_array_zero() or bit_array_set_all()
18 #define BIT_ARRAY_WORDS(n) (((n)+31)/32)
19 #define BIT_ARRAY_BYTES(n) (4*BIT_ARRAY_WORDS(n))
20 #define BIT_ARRAY(name,size) u32 name[BIT_ARRAY_WORDS(size)]
22 static inline bitarray_t bit_array_xmalloc(uns n)
24 return xmalloc(BIT_ARRAY_BYTES(n));
27 bitarray_t bit_array_xrealloc(bitarray_t a, uns old_n, uns new_n);
29 static inline bitarray_t bit_array_xmalloc_zero(uns n)
31 return xmalloc_zero(BIT_ARRAY_BYTES(n));
34 static inline void bit_array_zero(bitarray_t a, uns n)
36 bzero(a, BIT_ARRAY_BYTES(n));
39 static inline void bit_array_set_all(bitarray_t a, uns n)
42 memset(a, 255, w * 4);
48 static inline void bit_array_set(bitarray_t a, uns i)
50 a[i/32] |= (1 << (i%32));
53 static inline void bit_array_clear(bitarray_t a, uns i)
55 a[i/32] &= ~(1 << (i%32));
58 static inline void bit_array_assign(bitarray_t a, uns i, uns x)
63 bit_array_clear(a, i);
66 static inline uns bit_array_isset(bitarray_t a, uns i)
68 return a[i/32] & (1 << (i%32));
71 static inline uns bit_array_get(bitarray_t a, uns i)
73 return !! bit_array_isset(a, i);
76 static inline uns bit_array_test_and_set(bitarray_t a, uns i)
78 uns t = bit_array_isset(a, i);
83 static inline uns bit_array_test_and_clear(bitarray_t a, uns i)
85 uns t = bit_array_isset(a, i);
86 bit_array_clear(a, i);
90 uns bit_array_count_bits(bitarray_t a, uns n);
92 /* Iterate over all set bits */
93 #define BIT_ARRAY_FISH_BITS_BEGIN(var,ary,size) \
94 for (uns var##_hi=0; var##_hi < BIT_ARRAY_WORDS(size); var##_hi++) \
96 u32 var##_cur = ary[var##_hi]; \
97 for (uns var = 32 * var##_hi; var##_cur; var++, var##_cur >>= 1) \
101 #define BIT_ARRAY_FISH_BITS_END \