1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
2
3 #include <errno.h>
4 #include <stddef.h>
5 #include <stdint.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 #include "alloc-util.h"
10 #include "bitmap.h"
11 #include "hashmap.h"
12 #include "macro.h"
13 #include "memory-util.h"
14
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 (UINT_MAX)
22
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))
26
bitmap_new(void)27 Bitmap* bitmap_new(void) {
28 return new0(Bitmap, 1);
29 }
30
bitmap_copy(Bitmap * b)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);
39 if (!ret->bitmaps)
40 return mfree(ret);
41
42 ret->n_bitmaps = b->n_bitmaps;
43 return ret;
44 }
45
bitmap_free(Bitmap * b)46 Bitmap* bitmap_free(Bitmap *b) {
47 if (!b)
48 return NULL;
49
50 free(b->bitmaps);
51 return mfree(b);
52 }
53
bitmap_ensure_allocated(Bitmap ** b)54 int bitmap_ensure_allocated(Bitmap **b) {
55 Bitmap *a;
56
57 assert(b);
58
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
bitmap_set(Bitmap * b,unsigned n)71 int bitmap_set(Bitmap *b, unsigned n) {
72 uint64_t bitmask;
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, offset + 1))
85 return -ENOMEM;
86
87 b->n_bitmaps = offset + 1;
88 }
89
90 bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
91
92 b->bitmaps[offset] |= bitmask;
93
94 return 0;
95 }
96
bitmap_unset(Bitmap * b,unsigned n)97 void bitmap_unset(Bitmap *b, unsigned n) {
98 uint64_t bitmask;
99 unsigned offset;
100
101 if (!b)
102 return;
103
104 offset = BITMAP_NUM_TO_OFFSET(n);
105
106 if (offset >= b->n_bitmaps)
107 return;
108
109 bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
110
111 b->bitmaps[offset] &= ~bitmask;
112 }
113
bitmap_isset(const Bitmap * b,unsigned n)114 bool bitmap_isset(const Bitmap *b, unsigned n) {
115 uint64_t bitmask;
116 unsigned offset;
117
118 if (!b)
119 return false;
120
121 offset = BITMAP_NUM_TO_OFFSET(n);
122
123 if (offset >= b->n_bitmaps)
124 return false;
125
126 bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
127
128 return !!(b->bitmaps[offset] & bitmask);
129 }
130
bitmap_isclear(const Bitmap * b)131 bool bitmap_isclear(const Bitmap *b) {
132 unsigned i;
133
134 if (!b)
135 return true;
136
137 for (i = 0; i < b->n_bitmaps; i++)
138 if (b->bitmaps[i] != 0)
139 return false;
140
141 return true;
142 }
143
bitmap_clear(Bitmap * b)144 void bitmap_clear(Bitmap *b) {
145 if (!b)
146 return;
147
148 b->bitmaps = mfree(b->bitmaps);
149 b->n_bitmaps = 0;
150 }
151
bitmap_iterate(const Bitmap * b,Iterator * i,unsigned * n)152 bool bitmap_iterate(const Bitmap *b, Iterator *i, unsigned *n) {
153 uint64_t bitmask;
154 unsigned offset, rem;
155
156 assert(i);
157 assert(n);
158
159 if (!b || i->idx == BITMAP_END)
160 return false;
161
162 offset = BITMAP_NUM_TO_OFFSET(i->idx);
163 rem = BITMAP_NUM_TO_REM(i->idx);
164 bitmask = UINT64_C(1) << rem;
165
166 for (; offset < b->n_bitmaps; offset ++) {
167 if (b->bitmaps[offset]) {
168 for (; bitmask; bitmask <<= 1, rem ++) {
169 if (b->bitmaps[offset] & bitmask) {
170 *n = BITMAP_OFFSET_TO_NUM(offset, rem);
171 i->idx = *n + 1;
172
173 return true;
174 }
175 }
176 }
177
178 rem = 0;
179 bitmask = 1;
180 }
181
182 i->idx = BITMAP_END;
183
184 return false;
185 }
186
bitmap_equal(const Bitmap * a,const Bitmap * b)187 bool bitmap_equal(const Bitmap *a, const Bitmap *b) {
188 size_t common_n_bitmaps;
189 const Bitmap *c;
190 unsigned i;
191
192 if (a == b)
193 return true;
194
195 if (!a != !b)
196 return false;
197
198 if (!a)
199 return true;
200
201 common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
202 if (memcmp_safe(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
203 return false;
204
205 c = a->n_bitmaps > b->n_bitmaps ? a : b;
206 for (i = common_n_bitmaps; i < c->n_bitmaps; i++)
207 if (c->bitmaps[i] != 0)
208 return false;
209
210 return true;
211 }
212