]> mj.ucw.cz Git - libucw.git/blob - lib/bitarray.h
04ac582d04a3ecea43938c351081159383facf9c
[libucw.git] / lib / bitarray.h
1 /*
2  *      UCW Library -- Bit Array Operations
3  *
4  *      (c) 2003--2006 Martin Mares <mj@ucw.cz>
5  *
6  *      This software may be freely distributed and used according to the terms
7  *      of the GNU Lesser General Public License.
8  */
9
10 #include <string.h>
11
12 typedef u32 *bitarray_t;
13 #define BIT_ARRAY_WORDS(n) (((n)+31)/32)
14 #define BIT_ARRAY_BYTES(n) (4*BIT_ARRAY_WORDS(n))
15 #define BIT_ARRAY(name,size) u32 name[BIT_ARRAY_WORDS(size)]
16
17 static inline bitarray_t
18 bit_array_xmalloc(uns n)
19 {
20   return xmalloc(BIT_ARRAY_BYTES(n));
21 }
22
23 static inline bitarray_t
24 bit_array_xmalloc_zero(uns n)
25 {
26   return xmalloc_zero(BIT_ARRAY_BYTES(n));
27 }
28
29 static inline void
30 bit_array_zero(bitarray_t a, uns n)
31 {
32   bzero(a, BIT_ARRAY_BYTES(n));
33 }
34
35 static inline void
36 bit_array_set_all(bitarray_t a, uns n)
37 {
38   memset(a, 255, BIT_ARRAY_BYTES(n));
39 }
40
41 static inline void
42 bit_array_set(bitarray_t a, uns i)
43 {
44   a[i/32] |= (1 << (i%32));
45 }
46
47 static inline void
48 bit_array_clear(bitarray_t a, uns i)
49 {
50   a[i/32] &= ~(1 << (i%32));
51 }
52
53 static inline void
54 bit_array_assign(bitarray_t a, uns i, uns x)
55 {
56   if (x)
57     bit_array_set(a, i);
58   else
59     bit_array_clear(a, i);
60 }
61
62 static inline uns
63 bit_array_isset(bitarray_t a, uns i)
64 {
65   return a[i/32] & (1 << (i%32));
66 }
67
68 static inline uns
69 bit_array_get(bitarray_t a, uns i)
70 {
71   return !! bit_array_isset(a, i);
72 }
73
74 static inline uns
75 bit_array_test_and_set(bitarray_t a, uns i)
76 {
77   uns t = bit_array_isset(a, i);
78   bit_array_set(a, i);
79   return t;
80 }
81
82 static inline uns
83 bit_array_test_and_clear(bitarray_t a, uns i)
84 {
85   uns t = bit_array_isset(a, i);
86   bit_array_clear(a, i);
87   return t;
88 }
89
90 /* Iterate over all set bits, possibly destructively */
91 #define BIT_ARRAY_FISH_BITS_BEGIN(var,ary,size)                                 \
92   for (uns var##_hi=0; var##_hi < BIT_ARRAY_WORDS(size); var##_hi++)            \
93     for (uns var##_lo=0; ary[var##_hi]; var##_lo++)                             \
94       if (ary[var##_hi] & (1 << var##_lo))                                      \
95         {                                                                       \
96           uns var = 32*var##_hi + var##_lo;                                     \
97           ary[var##_hi] &= ~(1 << var##_lo);                                    \
98           do
99
100 #define BIT_ARRAY_FISH_BITS_END                                                 \
101           while (0);                                                            \
102         }