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
23 bit_array_xmalloc(uns n)
25 return xmalloc(BIT_ARRAY_BYTES(n));
28 bitarray_t bit_array_xrealloc(bitarray_t a, uns old_n, uns new_n);
30 static inline bitarray_t
31 bit_array_xmalloc_zero(uns n)
33 return xmalloc_zero(BIT_ARRAY_BYTES(n));
37 bit_array_zero(bitarray_t a, uns n)
39 bzero(a, BIT_ARRAY_BYTES(n));
43 bit_array_set_all(bitarray_t a, uns n)
46 memset(a, 255, w * 4);
53 bit_array_set(bitarray_t a, uns i)
55 a[i/32] |= (1 << (i%32));
59 bit_array_clear(bitarray_t a, uns i)
61 a[i/32] &= ~(1 << (i%32));
65 bit_array_assign(bitarray_t a, uns i, uns x)
70 bit_array_clear(a, i);
74 bit_array_isset(bitarray_t a, uns i)
76 return a[i/32] & (1 << (i%32));
80 bit_array_get(bitarray_t a, uns i)
82 return !! bit_array_isset(a, i);
86 bit_array_test_and_set(bitarray_t a, uns i)
88 uns t = bit_array_isset(a, i);
94 bit_array_test_and_clear(bitarray_t a, uns i)
96 uns t = bit_array_isset(a, i);
97 bit_array_clear(a, i);
101 uns bit_array_count_bits(bitarray_t a, uns n);
103 /* Iterate over all set bits */
104 #define BIT_ARRAY_FISH_BITS_BEGIN(var,ary,size) \
105 for (uns var##_hi=0; var##_hi < BIT_ARRAY_WORDS(size); var##_hi++) \
107 u32 var##_cur = ary[var##_hi]; \
108 for (uns var = 32 * var##_hi; var##_cur; var++, var##_cur >>= 1) \
112 #define BIT_ARRAY_FISH_BITS_END \