1 /* Licensed under LGPLv2+ - see LICENSE file for details */
10 #include <ccan/endian/endian.h>
12 typedef unsigned long bitmap_word;
14 #define BITMAP_WORD_BITS (sizeof(bitmap_word) * CHAR_BIT)
15 #define BITMAP_NWORDS(_n) \
16 (((_n) + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
18 #define BITMAP_WORD_0 (0)
19 #define BITMAP_WORD_1 ((bitmap_word)-1UL)
22 * We wrap each word in a structure for type checking.
24 typedef struct bitmap {
28 #define BITMAP_DECLARE(_name, _nbits) \
29 bitmap (_name)[BITMAP_NWORDS(_nbits)]
31 static inline size_t bitmap_sizeof(unsigned long nbits)
33 return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
36 static inline bitmap_word bitmap_bswap(bitmap_word w)
38 if (BITMAP_WORD_BITS == 32)
39 return (ENDIAN_CAST bitmap_word)cpu_to_be32(w);
40 else if (BITMAP_WORD_BITS == 64)
41 return (ENDIAN_CAST bitmap_word)cpu_to_be64(w);
44 #define BITMAP_WORD(_bm, _n) ((_bm)[(_n) / BITMAP_WORD_BITS].w)
45 #define BITMAP_WORDBIT(_n) \
46 (bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1)))
48 #define BITMAP_HEADWORDS(_nbits) \
49 ((_nbits) / BITMAP_WORD_BITS)
50 #define BITMAP_HEADBYTES(_nbits) \
51 (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word))
53 #define BITMAP_TAILWORD(_bm, _nbits) \
54 ((_bm)[BITMAP_HEADWORDS(_nbits)].w)
55 #define BITMAP_HASTAIL(_nbits) (((_nbits) % BITMAP_WORD_BITS) != 0)
56 #define BITMAP_TAILBITS(_nbits) \
57 (bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS))))
58 #define BITMAP_TAIL(_bm, _nbits) \
59 (BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits))
61 static inline void bitmap_set_bit(bitmap *bitmap, unsigned long n)
63 BITMAP_WORD(bitmap, n) |= BITMAP_WORDBIT(n);
66 static inline void bitmap_clear_bit(bitmap *bitmap, unsigned long n)
68 BITMAP_WORD(bitmap, n) &= ~BITMAP_WORDBIT(n);
71 static inline void bitmap_change_bit(bitmap *bitmap, unsigned long n)
73 BITMAP_WORD(bitmap, n) ^= BITMAP_WORDBIT(n);
76 static inline bool bitmap_test_bit(const bitmap *bitmap, unsigned long n)
78 return !!(BITMAP_WORD(bitmap, n) & BITMAP_WORDBIT(n));
81 void bitmap_zero_range(bitmap *bitmap, unsigned long n, unsigned long m);
82 void bitmap_fill_range(bitmap *bitmap, unsigned long n, unsigned long m);
84 static inline void bitmap_zero(bitmap *bitmap, unsigned long nbits)
86 memset(bitmap, 0, bitmap_sizeof(nbits));
89 static inline void bitmap_fill(bitmap *bitmap, unsigned long nbits)
91 memset(bitmap, 0xff, bitmap_sizeof(nbits));
94 static inline void bitmap_copy(bitmap *dst, const bitmap *src,
97 memcpy(dst, src, bitmap_sizeof(nbits));
100 #define BITMAP_DEF_BINOP(_name, _op) \
101 static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
102 unsigned long nbits) \
104 unsigned long i = 0; \
105 for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \
106 dst[i].w = src1[i].w _op src2[i].w; \
110 BITMAP_DEF_BINOP(and, &)
111 BITMAP_DEF_BINOP(or, |)
112 BITMAP_DEF_BINOP(xor, ^)
113 BITMAP_DEF_BINOP(andnot, & ~)
115 #undef BITMAP_DEF_BINOP
117 static inline void bitmap_complement(bitmap *dst, const bitmap *src,
122 for (i = 0; i < BITMAP_NWORDS(nbits); i++)
123 dst[i].w = ~src[i].w;
126 static inline bool bitmap_equal(const bitmap *src1, const bitmap *src2,
129 return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0)
130 && (!BITMAP_HASTAIL(nbits)
131 || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits)));
134 static inline bool bitmap_intersects(const bitmap *src1, const bitmap *src2,
139 for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
140 if (src1[i].w & src2[i].w)
143 if (BITMAP_HASTAIL(nbits) &&
144 (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits)))
149 static inline bool bitmap_subset(const bitmap *src1, const bitmap *src2,
154 for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
155 if (src1[i].w & ~src2[i].w)
158 if (BITMAP_HASTAIL(nbits) &&
159 (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
164 static inline bool bitmap_full(const bitmap *bitmap, unsigned long nbits)
168 for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
169 if (bitmap[i].w != -1UL)
172 if (BITMAP_HASTAIL(nbits) &&
173 (BITMAP_TAIL(bitmap, nbits) != BITMAP_TAILBITS(nbits)))
179 static inline bool bitmap_empty(const bitmap *bitmap, unsigned long nbits)
183 for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
184 if (bitmap[i].w != 0)
187 if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bitmap, nbits) != 0))
193 unsigned long bitmap_ffs(const bitmap *bitmap,
194 unsigned long n, unsigned long m);
197 * Allocation functions
199 static inline bitmap *bitmap_alloc(unsigned long nbits)
201 return malloc(bitmap_sizeof(nbits));
204 static inline bitmap *bitmap_alloc0(unsigned long nbits)
208 bitmap = bitmap_alloc(nbits);
210 bitmap_zero(bitmap, nbits);
214 static inline bitmap *bitmap_alloc1(unsigned long nbits)
218 bitmap = bitmap_alloc(nbits);
220 bitmap_fill(bitmap, nbits);
224 static inline bitmap *bitmap_realloc0(bitmap *bitmap,
225 unsigned long obits, unsigned long nbits)
227 bitmap = realloc(bitmap, bitmap_sizeof(nbits));
229 if ((nbits > obits) && bitmap)
230 bitmap_zero_range(bitmap, obits, nbits);
235 static inline bitmap *bitmap_realloc1(bitmap *bitmap,
236 unsigned long obits, unsigned long nbits)
238 bitmap = realloc(bitmap, bitmap_sizeof(nbits));
240 if ((nbits > obits) && bitmap)
241 bitmap_fill_range(bitmap, obits, nbits);
246 #endif /* CCAN_BITMAP_H_ */