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