diff options
author | Bryn M. Reeves <bmr@redhat.com> | 2016-12-11 12:44:45 +0000 |
---|---|---|
committer | Bryn M. Reeves <bmr@redhat.com> | 2016-12-13 21:01:58 +0000 |
commit | 5d1d65e735b6dcc5f02d0e536e3b63617f40ce83 (patch) | |
tree | 8a0a2ec070271cc732ad36d376a32f8225d32dc4 /libdm/datastruct | |
parent | 107bc13db3b0117e32bacede53fbd382feaf4a17 (diff) | |
download | lvm2-5d1d65e735b6dcc5f02d0e536e3b63617f40ce83.tar.gz |
libdm: add dm_bit_get_last()/dm_bit_get_prev()
It is sometimes convenient to iterate over the set bits in a dm
bitset in reverse order (from the highest set bit toward zero), or
to quickly find the last set bit.
Add dm_bit_get_last() and dm_bit_get_prev(), mirroring the existing
dm_bit_get_first() and dm_bit_get_next().
dm_bit_get_prev() uses __builtin_clz when available to efficiently
test the bitset in reverse.
Diffstat (limited to 'libdm/datastruct')
-rw-r--r-- | libdm/datastruct/bitset.c | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/libdm/datastruct/bitset.c b/libdm/datastruct/bitset.c index 3fd6a9ca5..90efec6d0 100644 --- a/libdm/datastruct/bitset.c +++ b/libdm/datastruct/bitset.c @@ -76,6 +76,13 @@ static int _test_word(uint32_t test, int bit) return (tb ? ffs(tb) + bit - 1 : -1); } +static int _test_word_rev(uint32_t test, int bit) +{ + uint32_t tb = test << (DM_BITS_PER_INT - 1 - bit); + + return (tb ? bit - clz(tb) : -1); +} + int dm_bit_get_next(dm_bitset_t bs, int last_bit) { int bit, word; @@ -101,11 +108,40 @@ int dm_bit_get_next(dm_bitset_t bs, int last_bit) return -1; } +int dm_bit_get_prev(dm_bitset_t bs, int last_bit) +{ + int bit, word; + uint32_t test; + + last_bit--; /* otherwise we'll return the same bit again */ + + /* + * bs[0] holds number of bits + */ + while (last_bit >= 0) { + word = last_bit >> INT_SHIFT; + test = bs[word + 1]; + bit = last_bit & (DM_BITS_PER_INT - 1); + + if ((bit = _test_word_rev(test, bit)) >= 0) + return (word * DM_BITS_PER_INT) + bit; + + last_bit = (last_bit & ~(DM_BITS_PER_INT - 1)) - 1; + } + + return -1; +} + int dm_bit_get_first(dm_bitset_t bs) { return dm_bit_get_next(bs, -1); } +int dm_bit_get_last(dm_bitset_t bs) +{ + return dm_bit_get_prev(bs, bs[0] + 1); +} + /* * Based on the Linux kernel __bitmap_parselist from lib/bitmap.c */ |