]>
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 | ||
53 | void bitmap_free(Bitmap *b) { | |
54 | if (!b) | |
55 | return; | |
56 | ||
57 | free(b->bitmaps); | |
58 | free(b); | |
59 | } | |
60 | ||
61 | int bitmap_ensure_allocated(Bitmap **b) { | |
62 | Bitmap *a; | |
63 | ||
370a2172 LP |
64 | assert(b); |
65 | ||
5ffa42cb TG |
66 | if (*b) |
67 | return 0; | |
68 | ||
69 | a = bitmap_new(); | |
70 | if (!a) | |
71 | return -ENOMEM; | |
72 | ||
73 | *b = a; | |
74 | ||
75 | return 0; | |
76 | } | |
77 | ||
78 | int bitmap_set(Bitmap *b, unsigned n) { | |
848d08b7 | 79 | uint64_t bitmask; |
5ffa42cb TG |
80 | unsigned offset; |
81 | ||
82 | assert(b); | |
83 | ||
84 | /* we refuse to allocate huge bitmaps */ | |
85 | if (n > BITMAPS_MAX_ENTRY) | |
86 | return -ERANGE; | |
87 | ||
88 | offset = BITMAP_NUM_TO_OFFSET(n); | |
89 | ||
90 | if (offset >= b->n_bitmaps) { | |
91 | if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1)) | |
92 | return -ENOMEM; | |
93 | ||
94 | b->n_bitmaps = offset + 1; | |
95 | } | |
96 | ||
370a2172 | 97 | bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n); |
5ffa42cb TG |
98 | |
99 | b->bitmaps[offset] |= bitmask; | |
100 | ||
101 | return 0; | |
102 | } | |
103 | ||
104 | void bitmap_unset(Bitmap *b, unsigned n) { | |
848d08b7 | 105 | uint64_t bitmask; |
5ffa42cb TG |
106 | unsigned offset; |
107 | ||
370a2172 LP |
108 | if (!b) |
109 | return; | |
5ffa42cb TG |
110 | |
111 | offset = BITMAP_NUM_TO_OFFSET(n); | |
112 | ||
113 | if (offset >= b->n_bitmaps) | |
114 | return; | |
115 | ||
370a2172 | 116 | bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n); |
5ffa42cb TG |
117 | |
118 | b->bitmaps[offset] &= ~bitmask; | |
119 | } | |
120 | ||
121 | bool bitmap_isset(Bitmap *b, unsigned n) { | |
848d08b7 | 122 | uint64_t bitmask; |
5ffa42cb TG |
123 | unsigned offset; |
124 | ||
370a2172 | 125 | if (!b) |
5ffa42cb TG |
126 | return false; |
127 | ||
128 | offset = BITMAP_NUM_TO_OFFSET(n); | |
129 | ||
130 | if (offset >= b->n_bitmaps) | |
131 | return false; | |
132 | ||
370a2172 | 133 | bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n); |
5ffa42cb TG |
134 | |
135 | return !!(b->bitmaps[offset] & bitmask); | |
136 | } | |
137 | ||
138 | bool bitmap_isclear(Bitmap *b) { | |
139 | unsigned i; | |
140 | ||
0b808637 LP |
141 | if (!b) |
142 | return true; | |
5ffa42cb TG |
143 | |
144 | for (i = 0; i < b->n_bitmaps; i++) | |
370a2172 | 145 | if (b->bitmaps[i] != 0) |
5ffa42cb TG |
146 | return false; |
147 | ||
148 | return true; | |
149 | } | |
150 | ||
151 | void bitmap_clear(Bitmap *b) { | |
0b808637 LP |
152 | |
153 | if (!b) | |
154 | return; | |
5ffa42cb | 155 | |
a1e58e8e | 156 | b->bitmaps = mfree(b->bitmaps); |
05fb03be | 157 | b->n_bitmaps = 0; |
951c3eef | 158 | b->bitmaps_allocated = 0; |
5ffa42cb TG |
159 | } |
160 | ||
cb57dd41 | 161 | bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) { |
848d08b7 | 162 | uint64_t bitmask; |
5ffa42cb TG |
163 | unsigned offset, rem; |
164 | ||
370a2172 LP |
165 | assert(i); |
166 | assert(n); | |
167 | ||
22cedfe1 | 168 | if (!b || i->idx == BITMAP_END) |
5ffa42cb TG |
169 | return false; |
170 | ||
cb57dd41 TG |
171 | offset = BITMAP_NUM_TO_OFFSET(i->idx); |
172 | rem = BITMAP_NUM_TO_REM(i->idx); | |
370a2172 | 173 | bitmask = UINT64_C(1) << rem; |
5ffa42cb TG |
174 | |
175 | for (; offset < b->n_bitmaps; offset ++) { | |
176 | if (b->bitmaps[offset]) { | |
177 | for (; bitmask; bitmask <<= 1, rem ++) { | |
178 | if (b->bitmaps[offset] & bitmask) { | |
179 | *n = BITMAP_OFFSET_TO_NUM(offset, rem); | |
cb57dd41 | 180 | i->idx = *n + 1; |
5ffa42cb TG |
181 | |
182 | return true; | |
183 | } | |
184 | } | |
185 | } | |
186 | ||
187 | rem = 0; | |
188 | bitmask = 1; | |
189 | } | |
190 | ||
cb57dd41 | 191 | i->idx = BITMAP_END; |
5ffa42cb TG |
192 | |
193 | return false; | |
194 | } | |
195 | ||
196 | bool bitmap_equal(Bitmap *a, Bitmap *b) { | |
d5fa8199 MM |
197 | size_t common_n_bitmaps; |
198 | Bitmap *c; | |
199 | unsigned i; | |
5ffa42cb | 200 | |
7d7fa31c LP |
201 | if (a == b) |
202 | return true; | |
203 | ||
204 | if (!a != !b) | |
5ffa42cb TG |
205 | return false; |
206 | ||
207 | if (!a) | |
208 | return true; | |
209 | ||
d5fa8199 MM |
210 | common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps); |
211 | if (memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0) | |
5ffa42cb TG |
212 | return false; |
213 | ||
d5fa8199 MM |
214 | c = a->n_bitmaps > b->n_bitmaps ? a : b; |
215 | for (i = common_n_bitmaps; i < c->n_bitmaps; i++) | |
216 | if (c->bitmaps[i] != 0) | |
217 | return false; | |
218 | ||
219 | return true; | |
5ffa42cb | 220 | } |