]>
git.ipfire.org Git - thirdparty/systemd.git/blob - src/basic/bitmap.c
1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2015 Tom Gundersen
8 systemd is free software; you can redistribute it and/or modify it
9 under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 2.1 of the License, or
11 (at your option) any later version.
13 systemd is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public License
19 along with systemd; If not, see <http://www.gnu.org/licenses/>.
28 #include "alloc-util.h"
36 size_t bitmaps_allocated
;
39 /* Bitmaps are only meant to store relatively small numbers
40 * (corresponding to, say, an enum), so it is ok to limit
41 * the max entry. 64k should be plenty. */
42 #define BITMAPS_MAX_ENTRY 0xffff
44 /* This indicates that we reached the end of the bitmap */
45 #define BITMAP_END ((unsigned) -1)
47 #define BITMAP_NUM_TO_OFFSET(n) ((n) / (sizeof(uint64_t) * 8))
48 #define BITMAP_NUM_TO_REM(n) ((n) % (sizeof(uint64_t) * 8))
49 #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem))
51 Bitmap
*bitmap_new(void) {
52 return new0(Bitmap
, 1);
55 void bitmap_free(Bitmap
*b
) {
63 int bitmap_ensure_allocated(Bitmap
**b
) {
80 int bitmap_set(Bitmap
*b
, unsigned n
) {
86 /* we refuse to allocate huge bitmaps */
87 if (n
> BITMAPS_MAX_ENTRY
)
90 offset
= BITMAP_NUM_TO_OFFSET(n
);
92 if (offset
>= b
->n_bitmaps
) {
93 if (!GREEDY_REALLOC0(b
->bitmaps
, b
->bitmaps_allocated
, offset
+ 1))
96 b
->n_bitmaps
= offset
+ 1;
99 bitmask
= UINT64_C(1) << BITMAP_NUM_TO_REM(n
);
101 b
->bitmaps
[offset
] |= bitmask
;
106 void bitmap_unset(Bitmap
*b
, unsigned n
) {
113 offset
= BITMAP_NUM_TO_OFFSET(n
);
115 if (offset
>= b
->n_bitmaps
)
118 bitmask
= UINT64_C(1) << BITMAP_NUM_TO_REM(n
);
120 b
->bitmaps
[offset
] &= ~bitmask
;
123 bool bitmap_isset(Bitmap
*b
, unsigned n
) {
130 offset
= BITMAP_NUM_TO_OFFSET(n
);
132 if (offset
>= b
->n_bitmaps
)
135 bitmask
= UINT64_C(1) << BITMAP_NUM_TO_REM(n
);
137 return !!(b
->bitmaps
[offset
] & bitmask
);
140 bool bitmap_isclear(Bitmap
*b
) {
146 for (i
= 0; i
< b
->n_bitmaps
; i
++)
147 if (b
->bitmaps
[i
] != 0)
153 void bitmap_clear(Bitmap
*b
) {
158 b
->bitmaps
= mfree(b
->bitmaps
);
160 b
->bitmaps_allocated
= 0;
163 bool bitmap_iterate(Bitmap
*b
, Iterator
*i
, unsigned *n
) {
165 unsigned offset
, rem
;
170 if (!b
|| i
->idx
== BITMAP_END
)
173 offset
= BITMAP_NUM_TO_OFFSET(i
->idx
);
174 rem
= BITMAP_NUM_TO_REM(i
->idx
);
175 bitmask
= UINT64_C(1) << rem
;
177 for (; offset
< b
->n_bitmaps
; offset
++) {
178 if (b
->bitmaps
[offset
]) {
179 for (; bitmask
; bitmask
<<= 1, rem
++) {
180 if (b
->bitmaps
[offset
] & bitmask
) {
181 *n
= BITMAP_OFFSET_TO_NUM(offset
, rem
);
198 bool bitmap_equal(Bitmap
*a
, Bitmap
*b
) {
199 size_t common_n_bitmaps
;
212 common_n_bitmaps
= MIN(a
->n_bitmaps
, b
->n_bitmaps
);
213 if (memcmp(a
->bitmaps
, b
->bitmaps
, sizeof(uint64_t) * common_n_bitmaps
) != 0)
216 c
= a
->n_bitmaps
> b
->n_bitmaps
? a
: b
;
217 for (i
= common_n_bitmaps
; i
< c
->n_bitmaps
; i
++)
218 if (c
->bitmaps
[i
] != 0)