[PATCH 1/6] bitset: use ffs where possible in array implementation

[Akim Demaille]

* lib/bitset/array.c (abitset_small_list): Use BITSET_FOR_EACH_BIT.
---
 ChangeLog          |  5 +++++
 lib/bitset/array.c | 46 +++++++++++++++-------------------------------
 2 files changed, 20 insertions(+), 31 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index c8f4ffaac..ba738c8c5 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2020-11-17  Akim Demaille  <akim@lrde.epita.fr>
+
+       bitset: use ffs where possible in array implementation
+       * lib/bitset/array.c (abitset_small_list): Use BITSET_FOR_EACH_BIT.
+
 2020-11-16  Bruno Haible  <bruno@clisp.org>
 
        Fix link errors on platforms with libunistring.
diff --git a/lib/bitset/array.c b/lib/bitset/array.c
index 6c5f7ed34..3f8bcca87 100644
--- a/lib/bitset/array.c
+++ b/lib/bitset/array.c
@@ -62,38 +62,25 @@ abitset_small_list (bitset src, bitset_bindex *list,
 
   word >>= bitno;
 
-  /* If num is 1, we could speed things up with a binary search
-     of the word of interest.  */
-
-  bitset_bindex count;
+  bitset_bindex count = 0;
+  /* Is there enough room to avoid checking in each iteration? */
   if (num >= BITSET_WORD_BITS)
     {
-      for (count = 0; word; bitno++)
-        {
-          if (word & 1)
-            list[count++] = bitno;
-          word >>= 1;
-        }
+      BITSET_FOR_EACH_BIT (pos, word)
+        list[count++] = bitno + pos;
+      *next = bitno + BITSET_WORD_BITS;
+      return count;
     }
   else
-    {
-      for (count = 0; word; bitno++)
-        {
-          if (word & 1)
-            {
-              list[count++] = bitno;
-              if (count >= num)
-                {
-                  bitno++;
-                  break;
-                }
-            }
-          word >>= 1;
-        }
-    }
-
-  *next = bitno;
-  return count;
+    BITSET_FOR_EACH_BIT (pos, word)
+      {
+        list[count++] = bitno + pos;
+        if (count >= num)
+          {
+            *next = bitno + pos + 1;
+            return count;
+          }
+      }
 }
 
 
@@ -205,9 +192,6 @@ abitset_list (bitset src, bitset_bindex *list,
       if (windex >= size)
         return 0;
 
-      /* If num is 1, we could speed things up with a binary search
-         of the current word.  */
-
       bitoff = windex * BITSET_WORD_BITS;
     }
   else
-- 
2.29.2