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