bitmap: Use a typesafe(ish) parameters instead of void *
[ccan] / ccan / bitmap / bitmap.h
1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #ifndef CCAN_BITMAP_H_
3 #define CCAN_BITMAP_H_
4
5 #include <stdbool.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 #define BITS_PER_LONG   (sizeof(unsigned long) * 8)
10
11 /*
12  * We use an unsigned long to get alignment, but wrap it in a
13  * structure for type checking
14  */
15 typedef struct {
16         unsigned long l;
17 } bitmap;
18
19 #define BYTE(_bm, _n)   (((unsigned char *)(_bm))[(_n) / 8])
20 #define LONG(_bm, _n)   (((unsigned long *)(_bm))[(_n) / BITS_PER_LONG])
21 #define BIT(_n)         (0x80 >> ((_n) % 8))
22
23 #define BYTES(_nbits)   ((_nbits) / 8)
24 #define BITS(_nbits)    ((~(0xff >> ((_nbits) % 8))) & 0xff)
25
26 static inline void bitmap_set_bit(bitmap *bitmap, int n)
27 {
28         BYTE(bitmap, n) |= BIT(n);
29 }
30
31 static inline void bitmap_clear_bit(bitmap *bitmap, int n)
32 {
33         BYTE(bitmap, n) &= ~BIT(n);
34 }
35
36 static inline void bitmap_change_bit(bitmap *bitmap, int n)
37 {
38         BYTE(bitmap, n) ^= BIT(n);
39 }
40
41 static inline bool bitmap_test_bit(bitmap *bitmap, int n)
42 {
43         return !!(BYTE(bitmap, n) & BIT(n));
44 }
45
46
47 static inline void bitmap_zero(bitmap *bitmap, int nbits)
48 {
49         memset(bitmap, 0, BYTES(nbits));
50         if (BITS(nbits))
51                 BYTE(bitmap, nbits) &= ~BITS(nbits);
52 }
53
54 static inline void bitmap_fill(bitmap *bitmap, int nbits)
55 {
56         memset(bitmap, 0xff, BYTES(nbits));
57         if (BITS(nbits))
58                 BYTE(bitmap, nbits) |= BITS(nbits);
59 }
60
61 static inline void bitmap_copy(bitmap *dst, bitmap *src, int nbits)
62 {
63         memcpy(dst, src, BYTES(nbits));
64         if (BITS(nbits)) {
65                 BYTE(dst, nbits) &= ~BITS(nbits);
66                 BYTE(dst, nbits) |= BYTE(src, nbits) & BITS(nbits);
67         }
68 }
69
70 #define DEF_BINOP(_name, _op) \
71         static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
72                                          int nbits) \
73         { \
74                 int n = 0; \
75                 while ((nbits - n) >= BITS_PER_LONG) { \
76                         LONG(dst, n) = LONG(src1, n) _op LONG(src2, n); \
77                         n += BITS_PER_LONG; \
78                 } \
79                 while ((nbits - n) >= 8) { \
80                         BYTE(dst, n) = BYTE(src1, n) _op BYTE(src2, n); \
81                         n += 8; \
82                 } \
83                 if (BITS(nbits)) { \
84                         BYTE(dst, nbits) &= ~BITS(nbits); \
85                         BYTE(dst, nbits) |= (BYTE(src1, nbits) _op BYTE(src2, nbits)) \
86                                 & BITS(nbits); \
87                 } \
88         }
89
90 DEF_BINOP(and, &)
91 DEF_BINOP(or, |)
92 DEF_BINOP(xor, ^)
93 DEF_BINOP(andnot, & ~)
94
95 #undef DEF_BINOP
96
97 static inline void bitmap_complement(bitmap *dst, bitmap *src, int nbits)
98 {
99         int n = 0;
100
101         while ((nbits - n) >= BITS_PER_LONG) {
102                 LONG(dst, n) = ~LONG(src, n);
103                 n += BITS_PER_LONG;
104         }
105         while ((nbits - n) >= 8) {
106                 BYTE(dst, n) = ~BYTE(src, n);
107                 n += 8;
108         }
109         if (BITS(nbits)) {
110                 BYTE(dst, nbits) &= ~BITS(nbits);
111                 BYTE(dst, nbits) |= ~BYTE(src, nbits) & BITS(nbits);
112         }
113 }
114
115 static inline bool bitmap_equal(bitmap *src1, bitmap *src2, int nbits)
116 {
117         if (memcmp(src1, src2, BYTES(nbits)) != 0)
118                 return false;
119         if ((BYTE(src1, nbits) & BITS(nbits))
120             != (BYTE(src2, nbits) & BITS(nbits)))
121                 return false;
122         return true;
123 }
124
125 static inline bool bitmap_intersects(bitmap *src1, bitmap *src2, int nbits)
126 {
127         int n = 0;
128
129         while ((nbits - n) >= BITS_PER_LONG) {
130                 if (LONG(src1, n) & LONG(src2, n))
131                         return true;
132                 n += BITS_PER_LONG;
133         }
134         while ((nbits - n) >= 8) {
135                 if (BYTE(src1, n) & BYTE(src2, n))
136                         return true;
137                 n += 8;
138         }
139         if (BITS(nbits) & BYTE(src1, nbits) & BYTE(src2, nbits)) {
140                 return true;
141         }
142         return false;
143 }
144
145 static inline bool bitmap_subset(bitmap *src1, bitmap *src2, int nbits)
146 {
147         int n = 0;
148
149         while ((nbits - n) >= BITS_PER_LONG) {
150                 if (LONG(src1, n) & ~LONG(src2, n))
151                         return false;
152                 n += BITS_PER_LONG;
153         }
154         while ((nbits - n) >= 8) {
155                 if (BYTE(src1, n) & ~BYTE(src2, n))
156                         return false;
157                 n += 8;
158         }
159         if (BITS(nbits) & (BYTE(src1, nbits) & ~BYTE(src2, nbits))) {
160                 return false;
161         }
162         return true;
163 }
164
165 static inline bool bitmap_full(bitmap *bitmap, int nbits)
166 {
167         int n = 0;
168
169         while ((nbits - n) >= BITS_PER_LONG) {
170                 if (LONG(bitmap, n) != -1UL)
171                         return false;
172                 n += BITS_PER_LONG;
173         }
174         while ((nbits - n) >= 8) {
175                 if (BYTE(bitmap, n) != 0xff)
176                         return false;
177                 n += 8;
178         }
179         if (BITS(nbits)
180             && ((BITS(nbits) & BYTE(bitmap, nbits)) != BITS(nbits))) {
181                 return false;
182         }
183         return true;
184 }
185
186 static inline bool bitmap_empty(bitmap *bitmap, int nbits)
187 {
188         int n = 0;
189
190         while ((nbits - n) >= BITS_PER_LONG) {
191                 if (LONG(bitmap, n))
192                         return false;
193                 n += BITS_PER_LONG;
194         }
195         while ((nbits - n) >= 8) {
196                 if (BYTE(bitmap, n))
197                         return false;
198                 n += 8;
199         }
200         if (BITS(nbits) && ((BITS(nbits) & BYTE(bitmap, nbits)))) {
201                 return false;
202         }
203         return true;
204 }
205
206
207 static inline bitmap *bitmap_alloc(int nbits)
208 {
209         return malloc((nbits + 7) / 8);
210 }
211
212 #undef BYTE
213 #undef LONG
214 #undef BIT
215 #undef BYTES
216 #undef BITS
217
218 #endif /* CCAN_BITMAP_H_ */