]>
git.ipfire.org Git - thirdparty/systemd.git/blob - src/shared/bitmap.c
1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
9 #include "alloc-util.h"
13 #include "memory-util.h"
15 /* Bitmaps are only meant to store relatively small numbers
16 * (corresponding to, say, an enum), so it is ok to limit
17 * the max entry. 64k should be plenty. */
18 #define BITMAPS_MAX_ENTRY 0xffff
20 /* This indicates that we reached the end of the bitmap */
21 #define BITMAP_END (UINT_MAX)
23 #define BITMAP_NUM_TO_OFFSET(n) ((n) / (sizeof(uint64_t) * 8))
24 #define BITMAP_NUM_TO_REM(n) ((n) % (sizeof(uint64_t) * 8))
25 #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem))
27 Bitmap
* bitmap_new(void) {
28 return new0(Bitmap
, 1);
31 Bitmap
* bitmap_copy(Bitmap
*b
) {
38 ret
->bitmaps
= newdup(uint64_t, b
->bitmaps
, b
->n_bitmaps
);
42 ret
->n_bitmaps
= b
->n_bitmaps
;
46 Bitmap
* bitmap_free(Bitmap
*b
) {
54 int bitmap_ensure_allocated(Bitmap
**b
) {
71 int bitmap_set(Bitmap
*b
, unsigned n
) {
77 /* we refuse to allocate huge bitmaps */
78 if (n
> BITMAPS_MAX_ENTRY
)
81 offset
= BITMAP_NUM_TO_OFFSET(n
);
83 if (offset
>= b
->n_bitmaps
) {
84 if (!GREEDY_REALLOC0(b
->bitmaps
, offset
+ 1))
87 b
->n_bitmaps
= offset
+ 1;
90 bitmask
= UINT64_C(1) << BITMAP_NUM_TO_REM(n
);
92 b
->bitmaps
[offset
] |= bitmask
;
97 void bitmap_unset(Bitmap
*b
, unsigned n
) {
104 offset
= BITMAP_NUM_TO_OFFSET(n
);
106 if (offset
>= b
->n_bitmaps
)
109 bitmask
= UINT64_C(1) << BITMAP_NUM_TO_REM(n
);
111 b
->bitmaps
[offset
] &= ~bitmask
;
114 bool bitmap_isset(const Bitmap
*b
, unsigned n
) {
121 offset
= BITMAP_NUM_TO_OFFSET(n
);
123 if (offset
>= b
->n_bitmaps
)
126 bitmask
= UINT64_C(1) << BITMAP_NUM_TO_REM(n
);
128 return !!(b
->bitmaps
[offset
] & bitmask
);
131 bool bitmap_isclear(const Bitmap
*b
) {
137 for (i
= 0; i
< b
->n_bitmaps
; i
++)
138 if (b
->bitmaps
[i
] != 0)
144 void bitmap_clear(Bitmap
*b
) {
148 b
->bitmaps
= mfree(b
->bitmaps
);
152 bool bitmap_iterate(const Bitmap
*b
, Iterator
*i
, unsigned *n
) {
154 unsigned offset
, rem
;
159 if (!b
|| i
->idx
== BITMAP_END
)
162 offset
= BITMAP_NUM_TO_OFFSET(i
->idx
);
163 rem
= BITMAP_NUM_TO_REM(i
->idx
);
164 bitmask
= UINT64_C(1) << rem
;
166 for (; offset
< b
->n_bitmaps
; offset
++) {
167 if (b
->bitmaps
[offset
]) {
168 for (; bitmask
; bitmask
<<= 1, rem
++) {
169 if (b
->bitmaps
[offset
] & bitmask
) {
170 *n
= BITMAP_OFFSET_TO_NUM(offset
, rem
);
187 bool bitmap_equal(const Bitmap
*a
, const Bitmap
*b
) {
188 size_t common_n_bitmaps
;
201 common_n_bitmaps
= MIN(a
->n_bitmaps
, b
->n_bitmaps
);
202 if (memcmp_safe(a
->bitmaps
, b
->bitmaps
, sizeof(uint64_t) * common_n_bitmaps
) != 0)
205 c
= a
->n_bitmaps
> b
->n_bitmaps
? a
: b
;
206 for (i
= common_n_bitmaps
; i
< c
->n_bitmaps
; i
++)
207 if (c
->bitmaps
[i
] != 0)