1 // SPDX-License-Identifier: GPL-2.0
6 #include <helpers/bitmask.h>
8 /* How many bits in an unsigned long */
9 #define bitsperlong (8 * sizeof(unsigned long))
11 /* howmany(a,b) : how many elements of size b needed to hold all of a */
12 #define howmany(x, y) (((x)+((y)-1))/(y))
14 /* How many longs in mask of n bits */
15 #define longsperbits(n) howmany(n, bitsperlong)
17 #define max(a, b) ((a) > (b) ? (a) : (b))
20 * Allocate and free `struct bitmask *`
23 /* Allocate a new `struct bitmask` with a size of n bits */
24 struct bitmask
*bitmask_alloc(unsigned int n
)
28 bmp
= malloc(sizeof(*bmp
));
32 bmp
->maskp
= calloc(longsperbits(n
), sizeof(unsigned long));
40 /* Free `struct bitmask` */
41 void bitmask_free(struct bitmask
*bmp
)
46 bmp
->maskp
= (unsigned long *)0xdeadcdef; /* double free tripwire */
51 * The routines _getbit() and _setbit() are the only
52 * routines that actually understand the layout of bmp->maskp[].
54 * On little endian architectures, this could simply be an array of
55 * bytes. But the kernel layout of bitmasks _is_ visible to userspace
56 * via the sched_(set/get)affinity calls in Linux 2.6, and on big
57 * endian architectures, it is painfully obvious that this is an
58 * array of unsigned longs.
61 /* Return the value (0 or 1) of bit n in bitmask bmp */
62 static unsigned int _getbit(const struct bitmask
*bmp
, unsigned int n
)
65 return (bmp
->maskp
[n
/bitsperlong
] >> (n
% bitsperlong
)) & 1;
70 /* Set bit n in bitmask bmp to value v (0 or 1) */
71 static void _setbit(struct bitmask
*bmp
, unsigned int n
, unsigned int v
)
75 bmp
->maskp
[n
/bitsperlong
] |= 1UL << (n
% bitsperlong
);
77 bmp
->maskp
[n
/bitsperlong
] &=
78 ~(1UL << (n
% bitsperlong
));
83 * When parsing bitmask lists, only allow numbers, separated by one
84 * of the allowed next characters.
86 * The parameter 'sret' is the return from a sscanf "%u%c". It is
87 * -1 if the sscanf input string was empty. It is 0 if the first
88 * character in the sscanf input string was not a decimal number.
89 * It is 1 if the unsigned number matching the "%u" was the end of the
90 * input string. It is 2 if one or more additional characters followed
91 * the matched unsigned number. If it is 2, then 'nextc' is the first
92 * character following the number. The parameter 'ok_next_chars'
93 * is the nul-terminated list of allowed next characters.
95 * The mask term just scanned was ok if and only if either the numbers
96 * matching the %u were all of the input or if the next character in
97 * the input past the numbers was one of the allowed next characters.
99 static int scan_was_ok(int sret
, char nextc
, const char *ok_next_chars
)
102 (sret
== 2 && strchr(ok_next_chars
, nextc
) != NULL
);
105 static const char *nexttoken(const char *q
, int sep
)
114 /* Set a single bit i in bitmask */
115 struct bitmask
*bitmask_setbit(struct bitmask
*bmp
, unsigned int i
)
121 /* Set all bits in bitmask: bmp = ~0 */
122 struct bitmask
*bitmask_setall(struct bitmask
*bmp
)
125 for (i
= 0; i
< bmp
->size
; i
++)
130 /* Clear all bits in bitmask: bmp = 0 */
131 struct bitmask
*bitmask_clearall(struct bitmask
*bmp
)
134 for (i
= 0; i
< bmp
->size
; i
++)
139 /* True if all bits are clear */
140 int bitmask_isallclear(const struct bitmask
*bmp
)
143 for (i
= 0; i
< bmp
->size
; i
++)
149 /* True if specified bit i is set */
150 int bitmask_isbitset(const struct bitmask
*bmp
, unsigned int i
)
152 return _getbit(bmp
, i
);
155 /* Number of lowest set bit (min) */
156 unsigned int bitmask_first(const struct bitmask
*bmp
)
158 return bitmask_next(bmp
, 0);
161 /* Number of highest set bit (max) */
162 unsigned int bitmask_last(const struct bitmask
*bmp
)
165 unsigned int m
= bmp
->size
;
166 for (i
= 0; i
< bmp
->size
; i
++)
172 /* Number of next set bit at or above given bit i */
173 unsigned int bitmask_next(const struct bitmask
*bmp
, unsigned int i
)
176 for (n
= i
; n
< bmp
->size
; n
++)
183 * Parses a comma-separated list of numbers and ranges of numbers,
184 * with optional ':%u' strides modifying ranges, into provided bitmask.
185 * Some examples of input lists and their equivalent simple list:
186 * Input Equivalent to
190 * 0-3:2,8-15:4 0,2,8,12
192 int bitmask_parselist(const char *buf
, struct bitmask
*bmp
)
196 bitmask_clearall(bmp
);
199 while (p
= q
, q
= nexttoken(q
, ','), p
) {
200 unsigned int a
; /* begin of range */
201 unsigned int b
; /* end of range */
202 unsigned int s
; /* stride */
203 const char *c1
, *c2
; /* next tokens after '-' or ',' */
204 char nextc
; /* char after sscanf %u match */
205 int sret
; /* sscanf return (number of matches) */
207 sret
= sscanf(p
, "%u%c", &a
, &nextc
);
208 if (!scan_was_ok(sret
, nextc
, ",-"))
212 c1
= nexttoken(p
, '-');
213 c2
= nexttoken(p
, ',');
214 if (c1
!= NULL
&& (c2
== NULL
|| c1
< c2
)) {
215 sret
= sscanf(c1
, "%u%c", &b
, &nextc
);
216 if (!scan_was_ok(sret
, nextc
, ",:"))
218 c1
= nexttoken(c1
, ':');
219 if (c1
!= NULL
&& (c2
== NULL
|| c1
< c2
)) {
220 sret
= sscanf(c1
, "%u%c", &s
, &nextc
);
221 if (!scan_was_ok(sret
, nextc
, ","))
236 bitmask_clearall(bmp
);
241 * emit(buf, buflen, rbot, rtop, len)
243 * Helper routine for bitmask_displaylist(). Write decimal number
244 * or range to buf+len, suppressing output past buf+buflen, with optional
245 * comma-prefix. Return len of what would be written to buf, if it
249 static inline int emit(char *buf
, int buflen
, int rbot
, int rtop
, int len
)
252 len
+= snprintf(buf
+ len
, max(buflen
- len
, 0), ",");
254 len
+= snprintf(buf
+ len
, max(buflen
- len
, 0), "%d", rbot
);
256 len
+= snprintf(buf
+ len
, max(buflen
- len
, 0), "%d-%d",
262 * Write decimal list representation of bmp to buf.
264 * Output format is a comma-separated list of decimal numbers and
265 * ranges. Consecutively set bits are shown as two hyphen-separated
266 * decimal numbers, the smallest and largest bit numbers set in
267 * the range. Output format is compatible with the format
268 * accepted as input by bitmap_parselist().
270 * The return value is the number of characters which would be
271 * generated for the given input, excluding the trailing '\0', as
275 int bitmask_displaylist(char *buf
, int buflen
, const struct bitmask
*bmp
)
278 /* current bit is 'cur', most recently seen range is [rbot, rtop] */
279 unsigned int cur
, rbot
, rtop
;
283 rbot
= cur
= bitmask_first(bmp
);
284 while (cur
< bmp
->size
) {
286 cur
= bitmask_next(bmp
, cur
+1);
287 if (cur
>= bmp
->size
|| cur
> rtop
+ 1) {
288 len
= emit(buf
, buflen
, rbot
, rtop
, len
);