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