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)
19 * We wrap each word in a structure for type checking.
25 #define BITMAP_DECLARE(_name, _nbits) \
26 bitmap (_name)[BITMAP_NWORDS(_nbits)]
28 static inline size_t bitmap_sizeof(int nbits)
30 return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
33 static inline bitmap *bitmap_alloc(int nbits)
35 return malloc(bitmap_sizeof(nbits));
38 static inline bitmap_word bitmap_bswap(bitmap_word w)
40 if (BITMAP_WORD_BITS == 32)
41 return cpu_to_be32(w);
42 else if (BITMAP_WORD_BITS == 64)
43 return cpu_to_be64(w);
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)))
50 #define BITMAP_HEADWORDS(_nbits) \
51 ((_nbits) / BITMAP_WORD_BITS)
52 #define BITMAP_HEADBYTES(_nbits) \
53 (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word))
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))
63 static inline void bitmap_set_bit(bitmap *bitmap, int n)
65 BITMAP_WORD(bitmap, n) |= BITMAP_WORDBIT(n);
68 static inline void bitmap_clear_bit(bitmap *bitmap, int n)
70 BITMAP_WORD(bitmap, n) &= ~BITMAP_WORDBIT(n);
73 static inline void bitmap_change_bit(bitmap *bitmap, int n)
75 BITMAP_WORD(bitmap, n) ^= BITMAP_WORDBIT(n);
78 static inline bool bitmap_test_bit(bitmap *bitmap, int n)
80 return !!(BITMAP_WORD(bitmap, n) & BITMAP_WORDBIT(n));
84 static inline void bitmap_zero(bitmap *bitmap, int nbits)
86 memset(bitmap, 0, bitmap_sizeof(nbits));
89 static inline void bitmap_fill(bitmap *bitmap, int nbits)
91 memset(bitmap, 0xff, bitmap_sizeof(nbits));
94 static inline void bitmap_copy(bitmap *dst, bitmap *src, int nbits)
96 memcpy(dst, src, bitmap_sizeof(nbits));
99 #define BITMAP_DEF_BINOP(_name, _op) \
100 static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
104 for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \
105 dst[i].w = src1[i].w _op src2[i].w; \
109 BITMAP_DEF_BINOP(and, &)
110 BITMAP_DEF_BINOP(or, |)
111 BITMAP_DEF_BINOP(xor, ^)
112 BITMAP_DEF_BINOP(andnot, & ~)
114 #undef BITMAP_DEF_BINOP
116 static inline void bitmap_complement(bitmap *dst, bitmap *src, int nbits)
120 for (i = 0; i < BITMAP_NWORDS(nbits); i++)
121 dst[i].w = ~src[i].w;
124 static inline bool bitmap_equal(bitmap *src1, bitmap *src2, int nbits)
126 return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0)
127 && (!BITMAP_HASTAIL(nbits)
128 || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits)));
131 static inline bool bitmap_intersects(bitmap *src1, bitmap *src2, int nbits)
135 for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
136 if (src1[i].w & src2[i].w)
139 if (BITMAP_HASTAIL(nbits) &&
140 (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits)))
145 static inline bool bitmap_subset(bitmap *src1, bitmap *src2, int nbits)
149 for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
150 if (src1[i].w & ~src2[i].w)
153 if (BITMAP_HASTAIL(nbits) &&
154 (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
159 static inline bool bitmap_full(bitmap *bitmap, int nbits)
163 for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
164 if (bitmap[i].w != -1UL)
167 if (BITMAP_HASTAIL(nbits) &&
168 (BITMAP_TAIL(bitmap, nbits) != BITMAP_TAILBITS(nbits)))
174 static inline bool bitmap_empty(bitmap *bitmap, int nbits)
178 for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
179 if (bitmap[i].w != 0)
182 if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bitmap, nbits) != 0))
188 #endif /* CCAN_BITMAP_H_ */