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