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