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