• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * bitmask user library implementation.
3  *
4  * Copyright (c) 2004-2006 Silicon Graphics, Inc. All rights reserved.
5  *
6  * Paul Jackson <pj@sgi.com>
7  */
8 
9 /*
10  *  This program is free software; you can redistribute it and/or modify
11  *  it under the terms of the GNU Lesser General Public License as published by
12  *  the Free Software Foundation; either version 2.1 of the License, or
13  *  (at your option) any later version.
14  *
15  *  This program is distributed in the hope that it will be useful,
16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  *  GNU Lesser General Public License for more details.
19  *
20  *  You should have received a copy of the GNU Lesser General Public License
21  *  along with this program; if not, write to the Free Software
22  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
23  */
24 
25 #include <stdio.h>
26 #include <string.h>
27 #include <stdlib.h>
28 #include <stdint.h>
29 
30 #include "bitmask.h"
31 
32 struct bitmask {
33 	unsigned int size;
34 	unsigned long *maskp;
35 };
36 
37 /* How many bits in an unsigned long */
38 #define bitsperlong (8 * sizeof(unsigned long))
39 
40 /* howmany(a,b) : how many elements of size b needed to hold all of a */
41 #define howmany(x,y) (((x)+((y)-1))/(y))
42 
43 /* How many longs in mask of n bits */
44 #define longsperbits(n) howmany(n, bitsperlong)
45 
46 /*
47  * The routines _getbit() and _setbit() are the only
48  * routines that actually understand the layout of bmp->maskp[].
49  *
50  * On little endian architectures, this could simply be an array of
51  * bytes.  But the kernel layout of bitmasks _is_ visible to userspace
52  * via the sched_(set/get)affinity calls in Linux 2.6, and on big
53  * endian architectures, it is painfully obvious that this is an
54  * array of unsigned longs.
55  */
56 
57 /* Return the value (0 or 1) of bit n in bitmask bmp */
_getbit(const struct bitmask * bmp,unsigned int n)58 static unsigned int _getbit(const struct bitmask *bmp, unsigned int n)
59 {
60 	if (n < bmp->size)
61 		return (bmp->maskp[n / bitsperlong] >> (n % bitsperlong)) & 1;
62 	else
63 		return 0;
64 }
65 
66 /* Set bit n in bitmask bmp to value v (0 or 1) */
_setbit(struct bitmask * bmp,unsigned int n,unsigned int v)67 static void _setbit(struct bitmask *bmp, unsigned int n, unsigned int v)
68 {
69 	if (n < bmp->size) {
70 		if (v)
71 			bmp->maskp[n / bitsperlong] |= 1UL << (n % bitsperlong);
72 		else
73 			bmp->maskp[n / bitsperlong] &=
74 			    ~(1UL << (n % bitsperlong));
75 	}
76 }
77 
78 /*
79  * Allocate and free `struct bitmask *`
80  */
81 
82 /* Allocate a new `struct bitmask` with a size of n bits */
bitmask_alloc(unsigned int n)83 struct bitmask *bitmask_alloc(unsigned int n)
84 {
85 	struct bitmask *bmp;
86 
87 	bmp = malloc(sizeof(*bmp));
88 	if (bmp == 0)
89 		return 0;
90 	bmp->size = n;
91 	bmp->maskp = calloc(longsperbits(n), sizeof(unsigned long));
92 	if (bmp->maskp == 0) {
93 		free(bmp);
94 		return 0;
95 	}
96 	return bmp;
97 }
98 
99 /* Free `struct bitmask` */
bitmask_free(struct bitmask * bmp)100 void bitmask_free(struct bitmask *bmp)
101 {
102 	if (bmp == 0)
103 		return;
104 	free(bmp->maskp);
105 	bmp->maskp = (unsigned long *)0xdeadcdef;	/* double free tripwire */
106 	free(bmp);
107 }
108 
109 /*
110  * Display and parse ascii string representations.
111  */
112 
113 #define HEXCHUNKSZ 32		/* hex binary format shows 32 bits per chunk */
114 #define HEXCHARSZ 8		/* hex ascii format has up to 8 chars per chunk */
115 #define max(a,b) ((a) > (b) ? (a) : (b))
116 
117 /*
118  * Write hex word representation of bmp to buf, 32 bits per
119  * comma-separated, zero-filled hex word.  Do not write more
120  * than buflen chars to buf.
121  *
122  * Return number of chars that would have been written
123  * if buf were large enough.
124  */
125 
bitmask_displayhex(char * buf,int buflen,const struct bitmask * bmp)126 int bitmask_displayhex(char *buf, int buflen, const struct bitmask *bmp)
127 {
128 	int chunk;
129 	int cnt = 0;
130 	const char *sep = "";
131 
132 	if (buflen < 1)
133 		return 0;
134 	buf[0] = 0;
135 
136 	for (chunk = howmany(bmp->size, HEXCHUNKSZ) - 1; chunk >= 0; chunk--) {
137 		uint32_t val = 0;
138 		int bit;
139 
140 		for (bit = HEXCHUNKSZ - 1; bit >= 0; bit--)
141 			val = val << 1 | _getbit(bmp, chunk * HEXCHUNKSZ + bit);
142 		cnt += snprintf(buf + cnt, max(buflen - cnt, 0), "%s%0*x",
143 				sep, HEXCHARSZ, val);
144 		sep = ",";
145 	}
146 	return cnt;
147 }
148 
149 /*
150  * emit(buf, buflen, rbot, rtop, len)
151  *
152  * Helper routine for bitmask_displaylist().  Write decimal number
153  * or range to buf+len, suppressing output past buf+buflen, with optional
154  * comma-prefix.  Return len of what would be written to buf, if it
155  * all fit.
156  */
157 
emit(char * buf,int buflen,int rbot,int rtop,int len)158 static inline int emit(char *buf, int buflen, int rbot, int rtop, int len)
159 {
160 	if (len > 0)
161 		len += snprintf(buf + len, max(buflen - len, 0), ",");
162 	if (rbot == rtop)
163 		len += snprintf(buf + len, max(buflen - len, 0), "%d", rbot);
164 	else
165 		len +=
166 		    snprintf(buf + len, max(buflen - len, 0), "%d-%d", rbot,
167 			     rtop);
168 	return len;
169 }
170 
171 /*
172  * Write decimal list representation of bmp to buf.
173  *
174  * Output format is a comma-separated list of decimal numbers and
175  * ranges.  Consecutively set bits are shown as two hyphen-separated
176  * decimal numbers, the smallest and largest bit numbers set in
177  * the range.  Output format is compatible with the format
178  * accepted as input by bitmap_parselist().
179  *
180  * The return value is the number of characters which would be
181  * generated for the given input, excluding the trailing '\0', as
182  * per ISO C99.
183  */
184 
bitmask_displaylist(char * buf,int buflen,const struct bitmask * bmp)185 int bitmask_displaylist(char *buf, int buflen, const struct bitmask *bmp)
186 {
187 	int len = 0;
188 	/* current bit is 'cur', most recently seen range is [rbot, rtop] */
189 	unsigned int cur, rbot, rtop;
190 
191 	if (buflen > 0)
192 		*buf = 0;
193 	rbot = cur = bitmask_first(bmp);
194 	while (cur < bmp->size) {
195 		rtop = cur;
196 		cur = bitmask_next(bmp, cur + 1);
197 		if (cur >= bmp->size || cur > rtop + 1) {
198 			len = emit(buf, buflen, rbot, rtop, len);
199 			rbot = cur;
200 		}
201 	}
202 	return len;
203 }
204 
nexttoken(const char * q,int sep)205 static const char *nexttoken(const char *q, int sep)
206 {
207 	if (q)
208 		q = strchr(q, sep);
209 	if (q)
210 		q++;
211 	return q;
212 }
213 
214 /*
215  * Parse hex word representation in buf to bmp.
216  *
217  * Returns -1 on error, leaving unspecified results in bmp.
218  */
219 
bitmask_parsehex(const char * buf,struct bitmask * bmp)220 int bitmask_parsehex(const char *buf, struct bitmask *bmp)
221 {
222 	const char *p, *q;
223 	int nchunks = 0, chunk;
224 	unsigned int size = 0;
225 
226 	bitmask_clearall(bmp);
227 	size = longsperbits(bmp->size) * 8 * sizeof(unsigned long);
228 
229 	q = buf;
230 	while (p = q, q = nexttoken(q, ','), p)
231 		nchunks++;
232 
233 	chunk = nchunks - 1;
234 	q = buf;
235 	while (p = q, q = nexttoken(q, ','), p) {
236 		uint32_t val;
237 		int bit;
238 		char *endptr;
239 		int nchars_read, nchars_unread;
240 
241 		val = strtoul(p, &endptr, 16);
242 
243 		/* We should have consumed 1 to 8 (HEXCHARSZ) chars */
244 		nchars_read = endptr - p;
245 		if (nchars_read < 1 || nchars_read > HEXCHARSZ)
246 			goto err;
247 
248 		/* We should have consumed up to next comma */
249 		nchars_unread = q - endptr;
250 		if (q != NULL && nchars_unread != 1)
251 			goto err;
252 
253 		for (bit = HEXCHUNKSZ - 1; bit >= 0; bit--) {
254 			unsigned int n = chunk * HEXCHUNKSZ + bit;
255 			if (n >= size)
256 				goto err;
257 			_setbit(bmp, n, (val >> bit) & 1);
258 		}
259 		chunk--;
260 	}
261 	return 0;
262 err:
263 	bitmask_clearall(bmp);
264 	return -1;
265 }
266 
267 /*
268  * When parsing bitmask lists, only allow numbers, separated by one
269  * of the allowed next characters.
270  *
271  * The parameter 'sret' is the return from a sscanf "%u%c".  It is
272  * -1 if the sscanf input string was empty.  It is 0 if the first
273  * character in the sscanf input string was not a decimal number.
274  * It is 1 if the unsigned number matching the "%u" was the end of the
275  * input string.  It is 2 if one or more additional characters followed
276  * the matched unsigned number.  If it is 2, then 'nextc' is the first
277  * character following the number.  The parameter 'ok_next_chars'
278  * is the nul-terminated list of allowed next characters.
279  *
280  * The mask term just scanned was ok if and only if either the numbers
281  * matching the %u were all of the input or if the next character in
282  * the input past the numbers was one of the allowed next characters.
283  */
scan_was_ok(int sret,char nextc,const char * ok_next_chars)284 static int scan_was_ok(int sret, char nextc, const char *ok_next_chars)
285 {
286 	return sret == 1 || (sret == 2 && strchr(ok_next_chars, nextc) != NULL);
287 }
288 
289 /*
290  * Parses a comma-separated list of numbers and ranges of numbers,
291  * with optional ':%u' strides modifying ranges, into provided bitmask.
292  * Some examples of input lists and their equivalent simple list:
293  *	Input		Equivalent to
294  *	0-3		0,1,2,3
295  *	0-7:2		0,2,4,6
296  *	1,3,5-7		1,3,5,6,7
297  *	0-3:2,8-15:4	0,2,8,12
298  */
bitmask_parselist(const char * buf,struct bitmask * bmp)299 int bitmask_parselist(const char *buf, struct bitmask *bmp)
300 {
301 	const char *p, *q;
302 
303 	bitmask_clearall(bmp);
304 
305 	q = buf;
306 	while (p = q, q = nexttoken(q, ','), p) {
307 		unsigned int a;	/* begin of range */
308 		unsigned int b;	/* end of range */
309 		unsigned int s;	/* stride */
310 		const char *c1, *c2;	/* next tokens after '-' or ',' */
311 		char nextc;	/* char after sscanf %u match */
312 		int sret;	/* sscanf return (number of matches) */
313 
314 		sret = sscanf(p, "%u%c", &a, &nextc);
315 		if (!scan_was_ok(sret, nextc, ",-"))
316 			goto err;
317 		b = a;
318 		s = 1;
319 		c1 = nexttoken(p, '-');
320 		c2 = nexttoken(p, ',');
321 		if (c1 != NULL && (c2 == NULL || c1 < c2)) {
322 			sret = sscanf(c1, "%u%c", &b, &nextc);
323 			if (!scan_was_ok(sret, nextc, ",:"))
324 				goto err;
325 			c1 = nexttoken(c1, ':');
326 			if (c1 != NULL && (c2 == NULL || c1 < c2)) {
327 				sret = sscanf(c1, "%u%c", &s, &nextc);
328 				if (!scan_was_ok(sret, nextc, ","))
329 					goto err;
330 			}
331 		}
332 		if (!(a <= b))
333 			goto err;
334 		if (b >= bmp->size)
335 			goto err;
336 		while (a <= b) {
337 			_setbit(bmp, a, 1);
338 			a += s;
339 		}
340 	}
341 	return 0;
342 err:
343 	bitmask_clearall(bmp);
344 	return -1;
345 }
346 
347 /*
348  * Basic assignment operations
349  */
350 
351 /* Copy bmp2 to bmp1 */
bitmask_copy(struct bitmask * bmp1,const struct bitmask * bmp2)352 struct bitmask *bitmask_copy(struct bitmask *bmp1, const struct bitmask *bmp2)
353 {
354 	unsigned int i;
355 	for (i = 0; i < bmp1->size; i++)
356 		_setbit(bmp1, i, _getbit(bmp2, i));
357 	return bmp1;
358 }
359 
360 /* Set all bits in bitmask: bmp = ~0 */
bitmask_setall(struct bitmask * bmp)361 struct bitmask *bitmask_setall(struct bitmask *bmp)
362 {
363 	unsigned int i;
364 	for (i = 0; i < bmp->size; i++)
365 		_setbit(bmp, i, 1);
366 	return bmp;
367 }
368 
369 /* Clear all bits in bitmask: bmp = 0 */
bitmask_clearall(struct bitmask * bmp)370 struct bitmask *bitmask_clearall(struct bitmask *bmp)
371 {
372 	unsigned int i;
373 	for (i = 0; i < bmp->size; i++)
374 		_setbit(bmp, i, 0);
375 	return bmp;
376 }
377 
378 /*
379  * Interface to kernel sched_setaffinity system call
380  */
381 
382 /* Length in bytes of mask - use as second argument to sched_setaffinity */
bitmask_nbytes(struct bitmask * bmp)383 unsigned int bitmask_nbytes(struct bitmask *bmp)
384 {
385 	return longsperbits(bmp->size) * sizeof(unsigned long);
386 }
387 
388 /* Direct pointer to bit mask - use as third argument to sched_setaffinty */
bitmask_mask(struct bitmask * bmp)389 unsigned long *bitmask_mask(struct bitmask *bmp)
390 {
391 	return bmp->maskp;
392 }
393 
394 /*
395  * Unary numeric queries
396  */
397 
398 /* Size in bits of entire bitmask */
bitmask_nbits(const struct bitmask * bmp)399 unsigned int bitmask_nbits(const struct bitmask *bmp)
400 {
401 	return bmp->size;
402 }
403 
404 /* Hamming Weight: number of set bits */
bitmask_weight(const struct bitmask * bmp)405 unsigned int bitmask_weight(const struct bitmask *bmp)
406 {
407 	unsigned int i;
408 	unsigned int w = 0;
409 	for (i = 0; i < bmp->size; i++)
410 		if (_getbit(bmp, i))
411 			w++;
412 	return w;
413 }
414 
415 /*
416  * Unary Boolean queries
417  */
418 
419 /* True if specified bit i is set */
bitmask_isbitset(const struct bitmask * bmp,unsigned int i)420 int bitmask_isbitset(const struct bitmask *bmp, unsigned int i)
421 {
422 	return _getbit(bmp, i);
423 }
424 
425 /* True if specified bit i is clear */
bitmask_isbitclear(const struct bitmask * bmp,unsigned int i)426 int bitmask_isbitclear(const struct bitmask *bmp, unsigned int i)
427 {
428 	return !_getbit(bmp, i);
429 }
430 
431 /* True if all bits are set */
bitmask_isallset(const struct bitmask * bmp)432 int bitmask_isallset(const struct bitmask *bmp)
433 {
434 	unsigned int i;
435 	for (i = 0; i < bmp->size; i++)
436 		if (!_getbit(bmp, i))
437 			return 0;
438 	return 1;
439 }
440 
441 /* True if all bits are clear */
bitmask_isallclear(const struct bitmask * bmp)442 int bitmask_isallclear(const struct bitmask *bmp)
443 {
444 	unsigned int i;
445 	for (i = 0; i < bmp->size; i++)
446 		if (_getbit(bmp, i))
447 			return 0;
448 	return 1;
449 }
450 
451 /*
452  * Single bit operations
453  */
454 
455 /* Set a single bit i in bitmask */
bitmask_setbit(struct bitmask * bmp,unsigned int i)456 struct bitmask *bitmask_setbit(struct bitmask *bmp, unsigned int i)
457 {
458 	_setbit(bmp, i, 1);
459 	return bmp;
460 }
461 
462 /* Clear a single bit i in bitmask */
bitmask_clearbit(struct bitmask * bmp,unsigned int i)463 struct bitmask *bitmask_clearbit(struct bitmask *bmp, unsigned int i)
464 {
465 	_setbit(bmp, i, 0);
466 	return bmp;
467 }
468 
469 /*
470  * Binary Boolean operations: bmp1 op? bmp2
471  */
472 
473 /* True if two bitmasks are equal */
bitmask_equal(const struct bitmask * bmp1,const struct bitmask * bmp2)474 int bitmask_equal(const struct bitmask *bmp1, const struct bitmask *bmp2)
475 {
476 	unsigned int i;
477 	for (i = 0; i < bmp1->size || i < bmp2->size; i++)
478 		if (_getbit(bmp1, i) != _getbit(bmp2, i))
479 			return 0;
480 	return 1;
481 }
482 
483 /* True if first bitmask is subset of second */
bitmask_subset(const struct bitmask * bmp1,const struct bitmask * bmp2)484 int bitmask_subset(const struct bitmask *bmp1, const struct bitmask *bmp2)
485 {
486 	unsigned int i;
487 	for (i = 0; i < bmp1->size; i++)
488 		if (_getbit(bmp1, i) > _getbit(bmp2, i))
489 			return 0;
490 	return 1;
491 }
492 
493 /* True if two bitmasks don't overlap */
bitmask_disjoint(const struct bitmask * bmp1,const struct bitmask * bmp2)494 int bitmask_disjoint(const struct bitmask *bmp1, const struct bitmask *bmp2)
495 {
496 	unsigned int i;
497 	for (i = 0; i < bmp1->size; i++)
498 		if (_getbit(bmp1, i) & _getbit(bmp2, i))
499 			return 0;
500 	return 1;
501 }
502 
503 /* True if two bitmasks do overlap */
bitmask_intersects(const struct bitmask * bmp1,const struct bitmask * bmp2)504 int bitmask_intersects(const struct bitmask *bmp1, const struct bitmask *bmp2)
505 {
506 	unsigned int i;
507 	for (i = 0; i < bmp1->size; i++)
508 		if (_getbit(bmp1, i) & _getbit(bmp2, i))
509 			return 1;
510 	return 0;
511 }
512 
513 /*
514  * Range operations
515  */
516 
517 /* Set bits of bitmask in specified range [i, j) */
bitmask_setrange(struct bitmask * bmp,unsigned int i,unsigned int j)518 struct bitmask *bitmask_setrange(struct bitmask *bmp,
519 				 unsigned int i, unsigned int j)
520 {
521 	unsigned int n;
522 	for (n = i; n < j; n++)
523 		_setbit(bmp, n, 1);
524 	return bmp;
525 }
526 
527 /* Clear bits of bitmask in specified range */
bitmask_clearrange(struct bitmask * bmp,unsigned int i,unsigned int j)528 struct bitmask *bitmask_clearrange(struct bitmask *bmp,
529 				   unsigned int i, unsigned int j)
530 {
531 	unsigned int n;
532 	for (n = i; n < j; n++)
533 		_setbit(bmp, n, 0);
534 	return bmp;
535 }
536 
537 /* Clear all but specified range */
bitmask_keeprange(struct bitmask * bmp,unsigned int i,unsigned int j)538 struct bitmask *bitmask_keeprange(struct bitmask *bmp,
539 				  unsigned int i, unsigned int j)
540 {
541 	bitmask_clearrange(bmp, 0, i);
542 	bitmask_clearrange(bmp, j, bmp->size);
543 	return bmp;
544 }
545 
546 /*
547  * Unary operations: bmp1 = op(struct bitmask *bmp2)
548  */
549 
550 /* Complement: bmp1 = ~bmp2 */
bitmask_complement(struct bitmask * bmp1,const struct bitmask * bmp2)551 struct bitmask *bitmask_complement(struct bitmask *bmp1,
552 				   const struct bitmask *bmp2)
553 {
554 	unsigned int i;
555 	for (i = 0; i < bmp1->size; i++)
556 		_setbit(bmp1, i, !_getbit(bmp2, i));
557 	return bmp1;
558 }
559 
560 /* Right shift: bmp1 = bmp2 >> n */
bitmask_shiftright(struct bitmask * bmp1,const struct bitmask * bmp2,unsigned int n)561 struct bitmask *bitmask_shiftright(struct bitmask *bmp1,
562 				   const struct bitmask *bmp2, unsigned int n)
563 {
564 	unsigned int i;
565 	for (i = 0; i < bmp1->size; i++)
566 		_setbit(bmp1, i, _getbit(bmp2, i + n));
567 	return bmp1;
568 }
569 
570 /* Left shift: bmp1 = bmp2 << n */
bitmask_shiftleft(struct bitmask * bmp1,const struct bitmask * bmp2,unsigned int n)571 struct bitmask *bitmask_shiftleft(struct bitmask *bmp1,
572 				  const struct bitmask *bmp2, unsigned int n)
573 {
574 	int i;
575 	for (i = bmp1->size - 1; i >= 0; i--)
576 		_setbit(bmp1, i, _getbit(bmp2, i - n));
577 	return bmp1;
578 }
579 
580 /*
581  * Binary operations: bmp1 = bmp2 op bmp3
582  */
583 
584 /* Logical `and` of two bitmasks: bmp1 = bmp2 & bmp3 */
bitmask_and(struct bitmask * bmp1,const struct bitmask * bmp2,const struct bitmask * bmp3)585 struct bitmask *bitmask_and(struct bitmask *bmp1, const struct bitmask *bmp2,
586 			    const struct bitmask *bmp3)
587 {
588 	unsigned int i;
589 	for (i = 0; i < bmp1->size; i++)
590 		_setbit(bmp1, i, _getbit(bmp2, i) & _getbit(bmp3, i));
591 	return bmp1;
592 }
593 
594 /* Logical `andnot` of two bitmasks: bmp1 = bmp2 & ~bmp3 */
bitmask_andnot(struct bitmask * bmp1,const struct bitmask * bmp2,const struct bitmask * bmp3)595 struct bitmask *bitmask_andnot(struct bitmask *bmp1, const struct bitmask *bmp2,
596 			       const struct bitmask *bmp3)
597 {
598 	unsigned int i;
599 	for (i = 0; i < bmp1->size; i++)
600 		_setbit(bmp1, i, _getbit(bmp2, i) & ~_getbit(bmp3, i));
601 	return bmp1;
602 }
603 
604 /* Logical `or` of two bitmasks: bmp1 = bmp2 | bmp3 */
bitmask_or(struct bitmask * bmp1,const struct bitmask * bmp2,const struct bitmask * bmp3)605 struct bitmask *bitmask_or(struct bitmask *bmp1, const struct bitmask *bmp2,
606 			   const struct bitmask *bmp3)
607 {
608 	unsigned int i;
609 	for (i = 0; i < bmp1->size; i++)
610 		_setbit(bmp1, i, _getbit(bmp2, i) | _getbit(bmp3, i));
611 	return bmp1;
612 }
613 
614 /* Logical `eor` of two bitmasks: bmp1 = bmp2 ^ bmp3 */
bitmask_eor(struct bitmask * bmp1,const struct bitmask * bmp2,const struct bitmask * bmp3)615 struct bitmask *bitmask_eor(struct bitmask *bmp1, const struct bitmask *bmp2,
616 			    const struct bitmask *bmp3)
617 {
618 	unsigned int i;
619 	for (i = 0; i < bmp1->size; i++)
620 		_setbit(bmp1, i, _getbit(bmp2, i) ^ _getbit(bmp3, i));
621 	return bmp1;
622 }
623 
624 /*
625  * Iteration operators
626  */
627 
628 /* Number of lowest set bit (min) */
bitmask_first(const struct bitmask * bmp)629 unsigned int bitmask_first(const struct bitmask *bmp)
630 {
631 	return bitmask_next(bmp, 0);
632 }
633 
634 /* Number of next set bit at or above given bit i */
bitmask_next(const struct bitmask * bmp,unsigned int i)635 unsigned int bitmask_next(const struct bitmask *bmp, unsigned int i)
636 {
637 	unsigned int n;
638 	for (n = i; n < bmp->size; n++)
639 		if (_getbit(bmp, n))
640 			break;
641 	return n;
642 }
643 
644 /* Absolute position of nth set bit */
bitmask_rel_to_abs_pos(const struct bitmask * bmp,unsigned int n)645 unsigned int bitmask_rel_to_abs_pos(const struct bitmask *bmp, unsigned int n)
646 {
647 	unsigned int i;
648 	for (i = 0; i < bmp->size; i++)
649 		if (_getbit(bmp, i))
650 			if (n-- == 0)
651 				break;
652 	return i;
653 }
654 
655 /* Relative position amongst set bits of bit n */
bitmask_abs_to_rel_pos(const struct bitmask * bmp,unsigned int n)656 unsigned int bitmask_abs_to_rel_pos(const struct bitmask *bmp, unsigned int n)
657 {
658 	unsigned int i;
659 	unsigned int w = 0;
660 
661 	if (!_getbit(bmp, n))
662 		return bmp->size;
663 	/* Add in number bits set before bit n */
664 	for (i = 0; i < n; i++)
665 		if (_getbit(bmp, i))
666 			w++;
667 	return w;
668 }
669 
670 /* Number of highest set bit (max) */
bitmask_last(const struct bitmask * bmp)671 unsigned int bitmask_last(const struct bitmask *bmp)
672 {
673 	unsigned int i;
674 	unsigned int m = bmp->size;
675 	for (i = 0; i < bmp->size; i++)
676 		if (_getbit(bmp, i))
677 			m = i;
678 	return m;
679 }
680