[PATCH 4/7] bitset: use integrer_length in array implementation

[Akim Demaille]

* modules/bitset (Depends-on): Add integrer_length_l.
* lib/bitset/base.h (bitset_fls_, BITSET_FOR_EACH_BIT_REVERSE): New.
* lib/bitset/array.c (abitset_list_reverse): Use it.
---
 ChangeLog          |  7 +++++++
 lib/bitset/array.c | 19 +++++++++----------
 lib/bitset/base.h  | 21 +++++++++++++++++++++
 modules/bitset     |  1 +
 4 files changed, 38 insertions(+), 10 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 48d6191dd..ecf0fc054 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2020-11-29  Akim Demaille  <akim@lrde.epita.fr>
+
+       bitset: use integrer_length in array implementation
+       * modules/bitset (Depends-on): Add integrer_length_l.
+       * lib/bitset/base.h (bitset_fls_, BITSET_FOR_EACH_BIT_REVERSE): New.
+       * lib/bitset/array.c (abitset_list_reverse): Use it.
+
 2020-11-29  Akim Demaille  <akim@lrde.epita.fr>
 
        bitset: style: use consistent names
diff --git a/lib/bitset/array.c b/lib/bitset/array.c
index 0e90b6b1f..34773c787 100644
--- a/lib/bitset/array.c
+++ b/lib/bitset/array.c
@@ -143,19 +143,18 @@ abitset_list_reverse (bitset src, bitset_bindex *list,
 
   do
     {
-      bitset_word word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
-      for (; word; bitcnt--)
+      bitset_word word = srcp[windex];
+      if (bitcnt + 1 < BITSET_WORD_BITS)
+        /* We're starting in the middle of a word: smash bits to ignore.  */
+        word &= ((bitset_word) 1 << (bitcnt + 1)) - 1;
+      BITSET_FOR_EACH_BIT_REVERSE(pos, word)
         {
-          if (word & BITSET_MSB)
+          list[count++] = bitoff + pos;
+          if (count >= num)
             {
-              list[count++] = bitoff + bitcnt;
-              if (count >= num)
-                {
-                  *next = n_bits - (bitoff + bitcnt);
-                  return count;
-                }
+              *next = n_bits - (bitoff + pos);
+              return count;
             }
-          word <<= 1;
         }
       bitoff -= BITSET_WORD_BITS;
       bitcnt = BITSET_WORD_BITS - 1;
diff --git a/lib/bitset/base.h b/lib/bitset/base.h
index a124b0df4..64188ddb5 100644
--- a/lib/bitset/base.h
+++ b/lib/bitset/base.h
@@ -27,6 +27,7 @@
 #include <string.h> /* ffsl */
 
 #include "attribute.h"
+#include "integer_length.h"
 #include "xalloc.h"
 
 /* Currently we support five flavours of bitsets:
@@ -286,6 +287,14 @@ if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ 
(DST, SRC2) \
        0 <= Pos;                                        \
        Word ^= 1UL << Pos, Pos = bitset_ffs_ (Word))
 
+/* Iterate right to left over each set bit of WORD.
+   Each iteration sets POS to the 0-based index of the next set bit in WORD.
+   Repeatedly resets bits in WORD in place until it's null.  */
+#define BITSET_FOR_EACH_BIT_REVERSE(Pos, Word)          \
+  for (int Pos = bitset_fls_ (Word);                    \
+       0 <= Pos;                                        \
+       Word ^= 1UL << Pos, Pos = bitset_fls_ (Word))
+
 /* Private functions for bitset implementations.  */
 
 bool bitset_toggle_ (bitset, bitset_bindex);
@@ -316,4 +325,16 @@ int bitset_ffs_ (bitset_word word)
   return ffsl ((long) word) - 1;
 }
 
+#include <stdio.h>
+#include <stdlib.h>
+
+/* Last set bit in WORD.
+   Indexes start at 0, return -1 if WORD is null. */
+static inline
+int bitset_fls_ (bitset_word word)
+{
+  int res = integer_length_l (word) - 1;
+  return res;
+}
+
 #endif /* _BBITSET_H  */
diff --git a/modules/bitset b/modules/bitset
index 2516c2861..8c9cb7cc8 100644
--- a/modules/bitset
+++ b/modules/bitset
@@ -22,6 +22,7 @@ c99
 ffsl
 fopen-gnu
 gettext-h
+integer_length_l
 obstack
 xalloc
 
-- 
2.29.2