From 7c8e53f1bee370c1a8a0c640313c12df220f4114 Mon Sep 17 00:00:00 2001 From: Jason Ekstrand Date: Sat, 15 Aug 2015 09:30:40 -0700 Subject: [PATCH] util/bitset: Add a BITSET_FOREACH_SET macro Reviewed-by: Eric Anholt --- src/util/bitset.h | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/src/util/bitset.h b/src/util/bitset.h index febcddefd97..c452819414f 100644 --- a/src/util/bitset.h +++ b/src/util/bitset.h @@ -96,4 +96,40 @@ __bitset_ffs(const BITSET_WORD *x, int n) #define BITSET_FFS(x) __bitset_ffs(x, ARRAY_SIZE(x)) +static inline unsigned +__bitset_next_set(unsigned i, BITSET_WORD *tmp, + BITSET_WORD *set, unsigned size) +{ + unsigned bit, word; + + /* NOTE: The initial conditions for this function are very specific. At + * the start of the loop, the tmp variable must be set to *set and the + * initial i value set to 0. This way, if there is a bit set in the first + * word, we ignore the i-value and just grab that bit (so 0 is ok, even + * though 0 may be returned). If the first word is 0, then the value of + * `word` will be 0 and we will go on to look at the second word. + */ + word = BITSET_BITWORD(i); + while (*tmp == 0) { + word++; + + if (word >= BITSET_WORDS(size)) + return size; + + *tmp = set[word]; + } + + /* Find the next set bit in the non-zero word */ + bit = ffs(*tmp) - 1; + + /* Unset the bit */ + *tmp &= ~(1ull << bit); + + return word * BITSET_WORDBITS + bit; +} + +#define BITSET_FOREACH_SET(__i, __tmp, __set, __size) \ + for (__tmp = *(__set), __i = 0; \ + (__i = __bitset_next_set(__i, &__tmp, __set, __size)) < __size;) + #endif -- 2.30.2