[PATCH 3/6] bitset: use ffs where possible in the table implementation

[Akim Demaille]

* lib/bitset/table.c (tbitset_list): Use BITSET_FOR_EACH_BIT.
---
 ChangeLog          |   5 +++
 lib/bitset/table.c | 104 ++++++++++++---------------------------------
 2 files changed, 31 insertions(+), 78 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 5badf0c41..951b82b04 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
+
+       bitset: use ffs where possible in the table implementation
+       * lib/bitset/table.c (tbitset_list): Use BITSET_FOR_EACH_BIT.
+
 2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
 
        bitset: check empty and full bitsets
diff --git a/lib/bitset/table.c b/lib/bitset/table.c
index d111e0203..3643b6074 100644
--- a/lib/bitset/table.c
+++ b/lib/bitset/table.c
@@ -623,18 +623,14 @@ tbitset_list (bitset bset, bitset_bindex *list,
             {
               bitset_word word = srcp[windex - woffset] >> (bitno % 
BITSET_WORD_BITS);
 
-              for (; word; 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;
                 }
               bitno = (windex + 1) * BITSET_WORD_BITS;
             }
@@ -649,7 +645,6 @@ tbitset_list (bitset bset, bitset_bindex *list,
 
   for (; eindex < size; eindex++)
     {
-
       tbitset_elt *elt = elts[eindex];
       if (!elt)
         continue;
@@ -666,69 +661,25 @@ tbitset_list (bitset bset, bitset_bindex *list,
 #if TBITSET_ELT_WORDS == 2
           bitset_word word = srcp[0];
           if (word)
-            {
-              if (!(word & 0xffff))
-                {
-                  word >>= 16;
-                  bitno += 16;
-                }
-              if (!(word & 0xff))
-                {
-                  word >>= 8;
-                  bitno += 8;
-                }
-              for (; word; bitno++)
-                {
-                  if (word & 1)
-                    list[count++] = bitno;
-                  word >>= 1;
-                }
-            }
+            BITSET_FOR_EACH_BIT (pos, word)
+              list[count++] = bitno + pos;
           windex++;
           bitno = windex * BITSET_WORD_BITS;
 
           word = srcp[1];
           if (word)
-            {
-              if (!(word & 0xffff))
-                {
-                  word >>= 16;
-                  bitno += 16;
-                }
-              for (; word; bitno++)
-                {
-                  if (word & 1)
-                    list[count++] = bitno;
-                  word >>= 1;
-                }
-            }
+            BITSET_FOR_EACH_BIT (pos, word)
+              list[count++] = bitno + pos;
           windex++;
           bitno = windex * BITSET_WORD_BITS;
 #else
           for (int i = 0; i < TBITSET_ELT_WORDS; i++, windex++)
             {
-              bitno = windex * BITSET_WORD_BITS;
-
-              word = srcp[i];
+              bitset_word word = srcp[i];
               if (word)
-                {
-                  if (!(word & 0xffff))
-                    {
-                      word >>= 16;
-                      bitno += 16;
-                    }
-                  if (!(word & 0xff))
-                    {
-                      word >>= 8;
-                      bitno += 8;
-                    }
-                  for (; word; bitno++)
-                    {
-                      if (word & 1)
-                        list[count++] = bitno;
-                      word >>= 1;
-                    }
-                }
+                BITSET_FOR_EACH_BIT (pos, word)
+                  list[count++] = bitno + pos;
+              bitno = windex * BITSET_WORD_BITS;
             }
 #endif
         }
@@ -736,24 +687,21 @@ tbitset_list (bitset bset, bitset_bindex *list,
         {
           /* Tread more carefully since we need to check
              if array overflows.  */
-
-          for (int i = 0; i < TBITSET_ELT_WORDS; i++, windex++)
+          for (int i = 0; i < TBITSET_ELT_WORDS; i++)
             {
+              bitset_word word = srcp[i];
+              if (word)
+                BITSET_FOR_EACH_BIT (pos, word)
+                  {
+                    list[count++] = bitno + pos;
+                    if (count >= num)
+                      {
+                        *next = bitno + pos + 1;
+                        return count;
+                      }
+                  }
+              windex++;
               bitno = windex * BITSET_WORD_BITS;
-
-              for (bitset_word word = srcp[i]; word; bitno++)
-                {
-                  if (word & 1)
-                    {
-                      list[count++] = bitno;
-                      if (count >= num)
-                        {
-                          *next = bitno + 1;
-                          return count;
-                        }
-                    }
-                  word >>= 1;
-                }
             }
         }
     }
-- 
2.29.2