bitmap: Rework to assume always multiple of words storage length
[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 #include <ccan/endian/endian.h>
11
12 typedef unsigned long bitmap_word;
13
14 #define BITMAP_WORD_BITS        (sizeof(bitmap_word) * CHAR_BIT)
15 #define BITMAP_NWORDS(_n)       \
16         (((_n) + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
17
18 /*
19  * We wrap each word in a structure for type checking.
20  */
21 typedef struct {
22         bitmap_word w;
23 } bitmap;
24
25 static inline size_t bitmap_sizeof(int nbits)
26 {
27         return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
28 }
29
30 static inline bitmap *bitmap_alloc(int nbits)
31 {
32         return malloc(bitmap_sizeof(nbits));
33 }
34
35 static inline bitmap_word bitmap_bswap(bitmap_word w)
36 {
37         if (BITMAP_WORD_BITS == 32)
38                 return cpu_to_be32(w);
39         else if (BITMAP_WORD_BITS == 64)
40                 return cpu_to_be64(w);
41 }
42
43 #define BITMAP_WORD(_bm, _n)    ((_bm)[(_n) / BITMAP_WORD_BITS].w)
44 #define BITMAP_WORDBIT(_n)      \
45         (bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1)))
46
47 #define BITMAP_HEADWORDS(_nbits) \
48         ((_nbits) / BITMAP_WORD_BITS)
49 #define BITMAP_HEADBYTES(_nbits) \
50         (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word))
51
52 #define BITMAP_TAILWORD(_bm, _nbits) \
53         ((_bm)[BITMAP_HEADWORDS(_nbits)].w)
54 #define BITMAP_HASTAIL(_nbits)  (((_nbits) % BITMAP_WORD_BITS) != 0)
55 #define BITMAP_TAILBITS(_nbits) \
56         (bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS))))
57 #define BITMAP_TAIL(_bm, _nbits) \
58         (BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits))
59
60 static inline void bitmap_set_bit(bitmap *bitmap, int n)
61 {
62         BITMAP_WORD(bitmap, n) |= BITMAP_WORDBIT(n);
63 }
64
65 static inline void bitmap_clear_bit(bitmap *bitmap, int n)
66 {
67         BITMAP_WORD(bitmap, n) &= ~BITMAP_WORDBIT(n);
68 }
69
70 static inline void bitmap_change_bit(bitmap *bitmap, int n)
71 {
72         BITMAP_WORD(bitmap, n) ^= BITMAP_WORDBIT(n);
73 }
74
75 static inline bool bitmap_test_bit(bitmap *bitmap, int n)
76 {
77         return !!(BITMAP_WORD(bitmap, n) & BITMAP_WORDBIT(n));
78 }
79
80
81 static inline void bitmap_zero(bitmap *bitmap, int nbits)
82 {
83         memset(bitmap, 0, bitmap_sizeof(nbits));
84 }
85
86 static inline void bitmap_fill(bitmap *bitmap, int nbits)
87 {
88         memset(bitmap, 0xff, bitmap_sizeof(nbits));
89 }
90
91 static inline void bitmap_copy(bitmap *dst, bitmap *src, int nbits)
92 {
93         memcpy(dst, src, bitmap_sizeof(nbits));
94 }
95
96 #define BITMAP_DEF_BINOP(_name, _op) \
97         static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
98                                          int nbits) \
99         { \
100                 int i = 0; \
101                 for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \
102                         dst[i].w = src1[i].w _op src2[i].w; \
103                 } \
104         }
105
106 BITMAP_DEF_BINOP(and, &)
107 BITMAP_DEF_BINOP(or, |)
108 BITMAP_DEF_BINOP(xor, ^)
109 BITMAP_DEF_BINOP(andnot, & ~)
110
111 #undef BITMAP_DEF_BINOP
112
113 static inline void bitmap_complement(bitmap *dst, bitmap *src, int nbits)
114 {
115         int i;
116
117         for (i = 0; i < BITMAP_NWORDS(nbits); i++)
118                 dst[i].w = ~src[i].w;
119 }
120
121 static inline bool bitmap_equal(bitmap *src1, bitmap *src2, int nbits)
122 {
123         return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0)
124                 && (!BITMAP_HASTAIL(nbits)
125                     || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits)));
126 }
127
128 static inline bool bitmap_intersects(bitmap *src1, bitmap *src2, int nbits)
129 {
130         int i;
131
132         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
133                 if (src1[i].w & src2[i].w)
134                         return true;
135         }
136         if (BITMAP_HASTAIL(nbits) &&
137             (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits)))
138                 return true;
139         return false;
140 }
141
142 static inline bool bitmap_subset(bitmap *src1, bitmap *src2, int nbits)
143 {
144         int i;
145
146         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
147                 if (src1[i].w  & ~src2[i].w)
148                         return false;
149         }
150         if (BITMAP_HASTAIL(nbits) &&
151             (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
152                 return false;
153         return true;
154 }
155
156 static inline bool bitmap_full(bitmap *bitmap, int nbits)
157 {
158         int i;
159
160         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
161                 if (bitmap[i].w != -1UL)
162                         return false;
163         }
164         if (BITMAP_HASTAIL(nbits) &&
165             (BITMAP_TAIL(bitmap, nbits) != BITMAP_TAILBITS(nbits)))
166                 return false;
167
168         return true;
169 }
170
171 static inline bool bitmap_empty(bitmap *bitmap, int nbits)
172 {
173         int i;
174
175         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
176                 if (bitmap[i].w != 0)
177                         return false;
178         }
179         if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bitmap, nbits) != 0))
180                 return false;
181
182         return true;
183 }
184
185 #endif /* CCAN_BITMAP_H_ */