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