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