bitset: use ffsl to accelerate iterations over set bits

Currently we iterate over words bit by bit.  Instead, we should jump
from set bit to set bit.
Suggested by Bruno Haible.

* modules/bitset: Depend upon ffsl.
* lib/bitset/base.h (bitset_ffs, BITSET_FOR_EACH_BIT): New.
* lib/bitset/array.c (abitset_list): Use BITSET_FOR_EACH_BIT.

1 files changed, 18 insertions, 32 deletions

diff --git a/lib/bitset/array.c b/lib/bitset/array.c
index 1db5838914..6c5f7ed34f 100644
--- a/lib/bitset/array.c
+++ b/lib/bitset/array.c
@@ -227,18 +227,15 @@ abitset_list (bitset src, bitset_bindex *list,
 
           bitoff = windex * BITSET_WORD_BITS;
           bitset_word word = srcp[windex] >> bitno;
-          for (bitno = bitoff + bitno; word; bitno++)
+          bitno = bitoff + bitno;
+          BITSET_FOR_EACH_BIT (pos, word)
             {
-              if (word & 1)
+              list[count++] = bitno + pos;
+              if (count >= num)
                 {
-                  list[count++] = bitno;
-                  if (count >= num)
-                    {
-                      *next = bitno + 1;
-                      return count;
-                    }
+                  *next = bitno + pos + 1;
+                  return count;
                 }
-              word >>= 1;
             }
           windex++;
         }
@@ -251,31 +248,20 @@ abitset_list (bitset src, bitset_bindex *list,
       if (!word)
         continue;
 
+      /* Is there enough room to avoid checking in each iteration? */
       if ((count + BITSET_WORD_BITS) < num)
-        {
-          for (bitno = bitoff; word; bitno++)
-            {
-              if (word & 1)
-                list[count++] = bitno;
-              word >>= 1;
-            }
-        }
+        BITSET_FOR_EACH_BIT (pos, word)
+          list[count++] = bitoff + pos;
       else
-        {
-          for (bitno = bitoff; word; bitno++)
-            {
-              if (word & 1)
-                {
-                  list[count++] = bitno;
-                  if (count >= num)
-                    {
-                      *next = bitno + 1;
-                      return count;
-                    }
-                }
-              word >>= 1;
-            }
-        }
+        BITSET_FOR_EACH_BIT (pos, word)
+          {
+            list[count++] = bitoff + pos;
+            if (count >= num)
+              {
+                *next = bitoff + pos + 1;
+                return count;
+              }
+          }
     }
 
   *next = bitoff;