[PATCH 0/5] bitset: use ffs

[Akim Demaille]

Some time ago, Bruno reported that it was surprising that there are no
occurrences of ffs in the bitset module.  This series introduces the
use of ffs in array-based bitsets.  There are more places where ffs
could be used, but before installing it everywhere, I want to first
make sure that the approach I took is ok.

Originally bitset right-shifting words looking for set
least-significant bits:

    for (bitno = bitoff; word; bitno++)
      {
        if (word & 1)
          list[count++] = bitno;
        word >>= 1;
      }
      
I first tried to reproduce something similar with ffs.  Unfortunately
that led to `word >>= pos + 1`, where pos could be 63, so noop...

Instead, I'm reseting each least-significant bit in word, and the loop
above becomes:

    BITSET_FOR_EACH_BIT (pos, word)
      list[count++] = bitoff + pos;

with

    #define BITSET_FOR_EACH_BIT(Pos, Word)                  \
      for (int Pos = bitset_ffs (Word);                     \
           0 <= Pos;                                        \
           Word ^= 1UL << Pos, Pos = bitset_ffs (Word))

Cheers!

Akim Demaille (5):
  bitset: comment changes
  bitset: making debug traces more useful
  bitset: fix the copy from lbitset to other types
  bitset: more tests
  bitset: use ffsl to accelerate iterations over set bits

 ChangeLog           |  28 ++++++++++++
 lib/bitset.c        |   9 ++--
 lib/bitset.h        |  28 ++++++++----
 lib/bitset/array.c  |  56 +++++++++--------------
 lib/bitset/base.h   |   9 ++++
 lib/bitset/list.c   |  11 ++++-
 modules/bitset      |   1 +
 tests/test-bitset.c | 107 ++++++++++++++++++++++++++++++++++++++++----
 8 files changed, 190 insertions(+), 59 deletions(-)

-- 
2.29.2