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