1/* @title: Bitmap */
2#pragma once
3#include <math/div.h>
4#include <stdatomic.h>
5#include <stdbool.h>
6#include <stddef.h>
7#include <stdint.h>
8#include <string.h>
9
10typedef uint64_t bitmap_word_t;
11
12#define BITMAP_BITS_PER_WORD 64
13#define BITMAP_WORDS(nbits) DIV_ROUND_UP(nbits, BITMAP_BITS_PER_WORD)
14#define BITMAP_DECLARE(name, nbits) bitmap_word_t name[BITMAP_WORDS(nbits)]
15
16#define BITMAP_WORD_INDEX(bit) ((bit) / BITMAP_BITS_PER_WORD)
17#define BITMAP_BIT_OFFSET(bit) ((bit) % BITMAP_BITS_PER_WORD)
18#define BITMAP_BIT_MASK(bit) ((bitmap_word_t) 1 << BITMAP_BIT_OFFSET(bit))
19
20#define bitmap_for_each_bit_set(bit, map, nbits) \
21 for (size_t bit = 0; bit < (nbits); bit++) \
22 if (bitmap_test((map), (bit)))
23
24#define bitmap_for_each_bit_unset(bit, map, nbits) \
25 for (size_t bit = 0; bit < (nbits); bit++) \
26 if (!bitmap_test((map), (bit)))
27
28static inline void bitmap_set(bitmap_word_t *map, size_t bit) {
29 map[BITMAP_WORD_INDEX(bit)] |= BITMAP_BIT_MASK(bit);
30}
31
32static inline void bitmap_clear(bitmap_word_t *map, size_t bit) {
33 map[BITMAP_WORD_INDEX(bit)] &= ~BITMAP_BIT_MASK(bit);
34}
35
36static inline void bitmap_toggle(bitmap_word_t *map, size_t bit) {
37 map[BITMAP_WORD_INDEX(bit)] ^= BITMAP_BIT_MASK(bit);
38}
39
40static inline bool bitmap_test(const bitmap_word_t *map, size_t bit) {
41 return (map[BITMAP_WORD_INDEX(bit)] & BITMAP_BIT_MASK(bit)) != 0;
42}
43
44static inline bool bitmap_test_and_set(bitmap_word_t *map, size_t bit) {
45 bool old = bitmap_test(map, bit);
46 bitmap_set(map, bit);
47 return old;
48}
49
50static inline bool bitmap_test_and_clear(bitmap_word_t *map, size_t bit) {
51 bool old = bitmap_test(map, bit);
52 bitmap_clear(map, bit);
53 return old;
54}
55
56static inline void bitmap_atomic_set(bitmap_word_t *map, size_t bit) {
57 _Atomic bitmap_word_t *atom =
58 (_Atomic bitmap_word_t *) &map[BITMAP_WORD_INDEX(bit)];
59 atomic_fetch_or_explicit(atom, BITMAP_BIT_MASK(bit), memory_order_relaxed);
60}
61
62static inline void bitmap_atomic_clear(bitmap_word_t *map, size_t bit) {
63 _Atomic bitmap_word_t *atom =
64 (_Atomic bitmap_word_t *) &map[BITMAP_WORD_INDEX(bit)];
65 atomic_fetch_and_explicit(atom, ~BITMAP_BIT_MASK(bit),
66 memory_order_relaxed);
67}
68
69static inline void bitmap_atomic_toggle(bitmap_word_t *map, size_t bit) {
70 _Atomic bitmap_word_t *atom =
71 (_Atomic bitmap_word_t *) &map[BITMAP_WORD_INDEX(bit)];
72 atomic_fetch_xor_explicit(atom, BITMAP_BIT_MASK(bit), memory_order_relaxed);
73}
74
75static inline bool bitmap_atomic_test(const bitmap_word_t *map, size_t bit) {
76 const _Atomic bitmap_word_t *atom =
77 (const _Atomic bitmap_word_t *) &map[BITMAP_WORD_INDEX(bit)];
78 return (atomic_load_explicit(atom, memory_order_relaxed) &
79 BITMAP_BIT_MASK(bit)) != 0;
80}
81
82static inline bool bitmap_atomic_test_and_set(bitmap_word_t *map, size_t bit) {
83 _Atomic bitmap_word_t *atom =
84 (_Atomic bitmap_word_t *) &map[BITMAP_WORD_INDEX(bit)];
85 bitmap_word_t prev = atomic_fetch_or_explicit(atom, BITMAP_BIT_MASK(bit),
86 memory_order_acq_rel);
87 return (prev & BITMAP_BIT_MASK(bit)) != 0;
88}
89
90static inline bool bitmap_atomic_test_and_clear(bitmap_word_t *map,
91 size_t bit) {
92 _Atomic bitmap_word_t *atom =
93 (_Atomic bitmap_word_t *) &map[BITMAP_WORD_INDEX(bit)];
94 bitmap_word_t prev = atomic_fetch_and_explicit(atom, ~BITMAP_BIT_MASK(bit),
95 memory_order_acq_rel);
96 return (prev & BITMAP_BIT_MASK(bit)) != 0;
97}
98
99static inline void bitmap_zero(bitmap_word_t *map, size_t nbits) {
100 memset(map, 0, BITMAP_WORDS(nbits) * sizeof(bitmap_word_t));
101}
102
103static inline void bitmap_copy(bitmap_word_t *dst, const bitmap_word_t *src,
104 size_t nbits) {
105 memcpy(dst, src, BITMAP_WORDS(nbits) * sizeof(bitmap_word_t));
106}
107
108static inline void bitmap_fill(bitmap_word_t *map, size_t nbits) {
109 size_t words = BITMAP_WORDS(nbits);
110 if (words == 0) {
111 return;
112 }
113
114 for (size_t i = 0; i < words - 1; i++) {
115 map[i] = ~(bitmap_word_t) 0;
116 }
117
118 size_t rem = nbits % BITMAP_BITS_PER_WORD;
119 map[words - 1] =
120 rem ? (((bitmap_word_t) 1 << rem) - 1) : ~(bitmap_word_t) 0;
121}
122
123static inline void bitmap_set_range(bitmap_word_t *map, size_t start,
124 size_t len) {
125 for (size_t i = 0; i < len; i++) {
126 bitmap_set(map, bit: start + i);
127 }
128}
129
130static inline void bitmap_clear_range(bitmap_word_t *map, size_t start,
131 size_t len) {
132 for (size_t i = 0; i < len; i++) {
133 bitmap_clear(map, bit: start + i);
134 }
135}
136
137static inline void bitmap_and(bitmap_word_t *dst, const bitmap_word_t *src1,
138 const bitmap_word_t *src2, size_t nbits) {
139 size_t words = BITMAP_WORDS(nbits);
140 for (size_t i = 0; i < words; i++) {
141 dst[i] = src1[i] & src2[i];
142 }
143}
144
145static inline void bitmap_or(bitmap_word_t *dst, const bitmap_word_t *src1,
146 const bitmap_word_t *src2, size_t nbits) {
147 size_t words = BITMAP_WORDS(nbits);
148 for (size_t i = 0; i < words; i++) {
149 dst[i] = src1[i] | src2[i];
150 }
151}
152
153static inline void bitmap_xor(bitmap_word_t *dst, const bitmap_word_t *src1,
154 const bitmap_word_t *src2, size_t nbits) {
155 size_t words = BITMAP_WORDS(nbits);
156 for (size_t i = 0; i < words; i++) {
157 dst[i] = src1[i] ^ src2[i];
158 }
159}
160
161static inline void bitmap_andnot(bitmap_word_t *dst, const bitmap_word_t *src1,
162 const bitmap_word_t *src2, size_t nbits) {
163 size_t words = BITMAP_WORDS(nbits);
164 for (size_t i = 0; i < words; i++) {
165 dst[i] = src1[i] & ~src2[i];
166 }
167}
168
169static inline bool bitmap_equal(const bitmap_word_t *src1,
170 const bitmap_word_t *src2, size_t nbits) {
171 size_t words = BITMAP_WORDS(nbits);
172 for (size_t i = 0; i < words; i++) {
173 if (src1[i] != src2[i]) {
174 return false;
175 }
176 }
177 return true;
178}
179
180static inline bool bitmap_intersects(const bitmap_word_t *src1,
181 const bitmap_word_t *src2, size_t nbits) {
182 size_t words = BITMAP_WORDS(nbits);
183 for (size_t i = 0; i < words; i++) {
184 if ((src1[i] & src2[i]) != 0) {
185 return true;
186 }
187 }
188 return false;
189}
190
191static inline bool bitmap_subset(const bitmap_word_t *subset,
192 const bitmap_word_t *superset, size_t nbits) {
193 size_t words = BITMAP_WORDS(nbits);
194 for (size_t i = 0; i < words; i++) {
195 if ((subset[i] & ~superset[i]) != 0) {
196 return false;
197 }
198 }
199 return true;
200}
201
202static inline bool bitmap_empty(const bitmap_word_t *map, size_t nbits) {
203 size_t words = BITMAP_WORDS(nbits);
204 for (size_t i = 0; i < words; i++) {
205 if (map[i] != 0) {
206 return false;
207 }
208 }
209 return true;
210}
211
212static inline bool bitmap_full(const bitmap_word_t *map, size_t nbits) {
213 size_t words = BITMAP_WORDS(nbits);
214 if (words == 0)
215 return true;
216 for (size_t i = 0; i < words - 1; i++) {
217 if (map[i] != ~(bitmap_word_t) 0) {
218 return false;
219 }
220 }
221 size_t rem = nbits % BITMAP_BITS_PER_WORD;
222 bitmap_word_t mask =
223 rem ? (((bitmap_word_t) 1 << rem) - 1) : ~(bitmap_word_t) 0;
224 return (map[words - 1] & mask) == mask;
225}
226
227static inline size_t bitmap_weight(const bitmap_word_t *map, size_t nbits) {
228 size_t words = BITMAP_WORDS(nbits);
229 size_t count = 0;
230
231 if (words == 0) {
232 return 0;
233 }
234
235 for (size_t i = 0; i < words - 1; i++) {
236 count += (size_t) __builtin_popcountll(map[i]);
237 }
238
239 size_t rem = nbits % BITMAP_BITS_PER_WORD;
240 bitmap_word_t last = map[words - 1];
241 if (rem) {
242 last &= ((bitmap_word_t) 1 << rem) - 1;
243 }
244 count += (size_t) __builtin_popcountll(last);
245
246 return count;
247}
248
249static inline size_t bitmap_find_first_set(const bitmap_word_t *map,
250 size_t nbits) {
251 size_t words = BITMAP_WORDS(nbits);
252 for (size_t i = 0; i < words; i++) {
253 if (map[i]) {
254 size_t bit =
255 i * BITMAP_BITS_PER_WORD + (size_t) __builtin_ctzll(map[i]);
256 return bit < nbits ? bit : nbits;
257 }
258 }
259 return nbits;
260}
261
262static inline size_t bitmap_find_first_zero(const bitmap_word_t *map,
263 size_t nbits) {
264 size_t words = BITMAP_WORDS(nbits);
265 for (size_t i = 0; i < words; i++) {
266 bitmap_word_t inv = ~map[i];
267 if (inv) {
268 size_t bit =
269 i * BITMAP_BITS_PER_WORD + (size_t) __builtin_ctzll(inv);
270 return bit < nbits ? bit : nbits;
271 }
272 }
273 return nbits;
274}
275
276static inline size_t bitmap_find_next_bit(const bitmap_word_t *map,
277 size_t nbits, size_t start) {
278 if (start >= nbits) {
279 return nbits;
280 }
281
282 size_t word_index = BITMAP_WORD_INDEX(start);
283 size_t bit_offset = BITMAP_BIT_OFFSET(start);
284
285 bitmap_word_t word = map[word_index] & (~((bitmap_word_t) 0) << bit_offset);
286 if (word) {
287 size_t bit =
288 word_index * BITMAP_BITS_PER_WORD + (size_t) __builtin_ctzll(word);
289 return bit < nbits ? bit : nbits;
290 }
291
292 for (size_t i = word_index + 1; i < BITMAP_WORDS(nbits); i++) {
293 if (map[i]) {
294 size_t bit =
295 i * BITMAP_BITS_PER_WORD + (size_t) __builtin_ctzll(map[i]);
296 return bit < nbits ? bit : nbits;
297 }
298 }
299
300 return nbits;
301}
302
303static inline size_t bitmap_find_next_zero_bit(const bitmap_word_t *map,
304 size_t nbits, size_t start) {
305 if (start >= nbits) {
306 return nbits;
307 }
308
309 size_t word_index = BITMAP_WORD_INDEX(start);
310 size_t bit_offset = BITMAP_BIT_OFFSET(start);
311
312 bitmap_word_t inv = ~map[word_index] & (~((bitmap_word_t) 0) << bit_offset);
313 if (inv) {
314 size_t bit =
315 word_index * BITMAP_BITS_PER_WORD + (size_t) __builtin_ctzll(inv);
316 return bit < nbits ? bit : nbits;
317 }
318
319 for (size_t i = word_index + 1; i < BITMAP_WORDS(nbits); i++) {
320 inv = ~map[i];
321 if (inv) {
322 size_t bit =
323 i * BITMAP_BITS_PER_WORD + (size_t) __builtin_ctzll(inv);
324 return bit < nbits ? bit : nbits;
325 }
326 }
327
328 return nbits;
329}
330