]>
Commit | Line | Data |
---|---|---|
53e1b683 | 1 | /* SPDX-License-Identifier: LGPL-2.1+ */ |
5ffa42cb | 2 | |
11c3a366 TA |
3 | #include <errno.h> |
4 | #include <stddef.h> | |
5 | #include <stdint.h> | |
6 | #include <stdlib.h> | |
7 | #include <string.h> | |
8 | ||
b5efdb8a | 9 | #include "alloc-util.h" |
5ffa42cb | 10 | #include "bitmap.h" |
11c3a366 TA |
11 | #include "hashmap.h" |
12 | #include "macro.h" | |
5ffa42cb TG |
13 | |
14 | struct Bitmap { | |
848d08b7 | 15 | uint64_t *bitmaps; |
5ffa42cb TG |
16 | size_t n_bitmaps; |
17 | size_t bitmaps_allocated; | |
5ffa42cb TG |
18 | }; |
19 | ||
20 | /* Bitmaps are only meant to store relatively small numbers | |
21 | * (corresponding to, say, an enum), so it is ok to limit | |
22 | * the max entry. 64k should be plenty. */ | |
23 | #define BITMAPS_MAX_ENTRY 0xffff | |
24 | ||
25 | /* This indicates that we reached the end of the bitmap */ | |
26 | #define BITMAP_END ((unsigned) -1) | |
27 | ||
848d08b7 DM |
28 | #define BITMAP_NUM_TO_OFFSET(n) ((n) / (sizeof(uint64_t) * 8)) |
29 | #define BITMAP_NUM_TO_REM(n) ((n) % (sizeof(uint64_t) * 8)) | |
30 | #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem)) | |
5ffa42cb TG |
31 | |
32 | Bitmap *bitmap_new(void) { | |
33 | return new0(Bitmap, 1); | |
34 | } | |
35 | ||
17c8de63 LP |
36 | Bitmap *bitmap_copy(Bitmap *b) { |
37 | Bitmap *ret; | |
38 | ||
39 | ret = bitmap_new(); | |
40 | if (!ret) | |
41 | return NULL; | |
42 | ||
43 | ret->bitmaps = newdup(uint64_t, b->bitmaps, b->n_bitmaps); | |
6b430fdb ZJS |
44 | if (!ret->bitmaps) |
45 | return mfree(ret); | |
17c8de63 LP |
46 | |
47 | ret->n_bitmaps = ret->bitmaps_allocated = b->n_bitmaps; | |
48 | return ret; | |
49 | } | |
50 | ||
5ffa42cb TG |
51 | void bitmap_free(Bitmap *b) { |
52 | if (!b) | |
53 | return; | |
54 | ||
55 | free(b->bitmaps); | |
56 | free(b); | |
57 | } | |
58 | ||
59 | int bitmap_ensure_allocated(Bitmap **b) { | |
60 | Bitmap *a; | |
61 | ||
370a2172 LP |
62 | assert(b); |
63 | ||
5ffa42cb TG |
64 | if (*b) |
65 | return 0; | |
66 | ||
67 | a = bitmap_new(); | |
68 | if (!a) | |
69 | return -ENOMEM; | |
70 | ||
71 | *b = a; | |
72 | ||
73 | return 0; | |
74 | } | |
75 | ||
76 | int bitmap_set(Bitmap *b, unsigned n) { | |
848d08b7 | 77 | uint64_t bitmask; |
5ffa42cb TG |
78 | unsigned offset; |
79 | ||
80 | assert(b); | |
81 | ||
82 | /* we refuse to allocate huge bitmaps */ | |
83 | if (n > BITMAPS_MAX_ENTRY) | |
84 | return -ERANGE; | |
85 | ||
86 | offset = BITMAP_NUM_TO_OFFSET(n); | |
87 | ||
88 | if (offset >= b->n_bitmaps) { | |
89 | if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1)) | |
90 | return -ENOMEM; | |
91 | ||
92 | b->n_bitmaps = offset + 1; | |
93 | } | |
94 | ||
370a2172 | 95 | bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n); |
5ffa42cb TG |
96 | |
97 | b->bitmaps[offset] |= bitmask; | |
98 | ||
99 | return 0; | |
100 | } | |
101 | ||
102 | void bitmap_unset(Bitmap *b, unsigned n) { | |
848d08b7 | 103 | uint64_t bitmask; |
5ffa42cb TG |
104 | unsigned offset; |
105 | ||
370a2172 LP |
106 | if (!b) |
107 | return; | |
5ffa42cb TG |
108 | |
109 | offset = BITMAP_NUM_TO_OFFSET(n); | |
110 | ||
111 | if (offset >= b->n_bitmaps) | |
112 | return; | |
113 | ||
370a2172 | 114 | bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n); |
5ffa42cb TG |
115 | |
116 | b->bitmaps[offset] &= ~bitmask; | |
117 | } | |
118 | ||
119 | bool bitmap_isset(Bitmap *b, unsigned n) { | |
848d08b7 | 120 | uint64_t bitmask; |
5ffa42cb TG |
121 | unsigned offset; |
122 | ||
370a2172 | 123 | if (!b) |
5ffa42cb TG |
124 | return false; |
125 | ||
126 | offset = BITMAP_NUM_TO_OFFSET(n); | |
127 | ||
128 | if (offset >= b->n_bitmaps) | |
129 | return false; | |
130 | ||
370a2172 | 131 | bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n); |
5ffa42cb TG |
132 | |
133 | return !!(b->bitmaps[offset] & bitmask); | |
134 | } | |
135 | ||
136 | bool bitmap_isclear(Bitmap *b) { | |
137 | unsigned i; | |
138 | ||
0b808637 LP |
139 | if (!b) |
140 | return true; | |
5ffa42cb TG |
141 | |
142 | for (i = 0; i < b->n_bitmaps; i++) | |
370a2172 | 143 | if (b->bitmaps[i] != 0) |
5ffa42cb TG |
144 | return false; |
145 | ||
146 | return true; | |
147 | } | |
148 | ||
149 | void bitmap_clear(Bitmap *b) { | |
0b808637 LP |
150 | |
151 | if (!b) | |
152 | return; | |
5ffa42cb | 153 | |
a1e58e8e | 154 | b->bitmaps = mfree(b->bitmaps); |
05fb03be | 155 | b->n_bitmaps = 0; |
951c3eef | 156 | b->bitmaps_allocated = 0; |
5ffa42cb TG |
157 | } |
158 | ||
cb57dd41 | 159 | bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) { |
848d08b7 | 160 | uint64_t bitmask; |
5ffa42cb TG |
161 | unsigned offset, rem; |
162 | ||
370a2172 LP |
163 | assert(i); |
164 | assert(n); | |
165 | ||
22cedfe1 | 166 | if (!b || i->idx == BITMAP_END) |
5ffa42cb TG |
167 | return false; |
168 | ||
cb57dd41 TG |
169 | offset = BITMAP_NUM_TO_OFFSET(i->idx); |
170 | rem = BITMAP_NUM_TO_REM(i->idx); | |
370a2172 | 171 | bitmask = UINT64_C(1) << rem; |
5ffa42cb TG |
172 | |
173 | for (; offset < b->n_bitmaps; offset ++) { | |
174 | if (b->bitmaps[offset]) { | |
175 | for (; bitmask; bitmask <<= 1, rem ++) { | |
176 | if (b->bitmaps[offset] & bitmask) { | |
177 | *n = BITMAP_OFFSET_TO_NUM(offset, rem); | |
cb57dd41 | 178 | i->idx = *n + 1; |
5ffa42cb TG |
179 | |
180 | return true; | |
181 | } | |
182 | } | |
183 | } | |
184 | ||
185 | rem = 0; | |
186 | bitmask = 1; | |
187 | } | |
188 | ||
cb57dd41 | 189 | i->idx = BITMAP_END; |
5ffa42cb TG |
190 | |
191 | return false; | |
192 | } | |
193 | ||
194 | bool bitmap_equal(Bitmap *a, Bitmap *b) { | |
d5fa8199 MM |
195 | size_t common_n_bitmaps; |
196 | Bitmap *c; | |
197 | unsigned i; | |
5ffa42cb | 198 | |
7d7fa31c LP |
199 | if (a == b) |
200 | return true; | |
201 | ||
202 | if (!a != !b) | |
5ffa42cb TG |
203 | return false; |
204 | ||
205 | if (!a) | |
206 | return true; | |
207 | ||
d5fa8199 | 208 | common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps); |
65f95765 | 209 | if (memcmp_safe(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0) |
5ffa42cb TG |
210 | return false; |
211 | ||
d5fa8199 MM |
212 | c = a->n_bitmaps > b->n_bitmaps ? a : b; |
213 | for (i = common_n_bitmaps; i < c->n_bitmaps; i++) | |
214 | if (c->bitmaps[i] != 0) | |
215 | return false; | |
216 | ||
217 | return true; | |
5ffa42cb | 218 | } |