[PATCH 0/6] bitset: more conversions to ffs

[PATCH 0/6] bitset: more conversions to ffs

[Akim Demaille]

With this, I believe I have used ffs everywhere possible.  When gnulib
have fls* support, we will be able do the same for
bitset_list_reverse, but I'm not sure it's a frequent need.

FWIW, I have run successfully the test suite of Bison on every single
bitset implementation.

Cheers!

Akim Demaille (6):
  bitset: be sure to always return a value
  bitset: check empty and full bitsets
  bitset: use ffs where possible in the table implementation
  bitset: use ffs where possible in the vector implementation
  bitset: tests: try harder to break it
  bitset: tests: exercise the stats too

 ChangeLog           |  39 +++++++++++++++++
 lib/bitset/array.c  |  10 ++---
 lib/bitset/stats.c  |   8 +++-
 lib/bitset/table.c  | 104 +++++++++++---------------------------------
 lib/bitset/vector.c |  57 ++++++++++--------------
 tests/test-bitset.c |  88 ++++++++++++++++++++++++++++++++-----
 6 files changed, 176 insertions(+), 130 deletions(-)

-- 
2.29.2

[PATCH 1/6] bitset: be sure to always return a value

[Akim Demaille]

* lib/bitset/array.c (abitset_small_list): Always update *next and
return a value.
---
 ChangeLog          |  6 ++++++
 lib/bitset/array.c | 10 ++++------
 2 files changed, 10 insertions(+), 6 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index d50f4d1a2..88ae15003 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
+
+	bitset: be sure to always return a value
+	* lib/bitset/array.c (abitset_small_list): Always update *next and
+	return a value.
+
 2020-11-17  Akim Demaille  <akim@lrde.epita.fr>
 
 	bitset: strengthen tests
diff --git a/lib/bitset/array.c b/lib/bitset/array.c
index 3f8bcca87..0e90b6b1f 100644
--- a/lib/bitset/array.c
+++ b/lib/bitset/array.c
@@ -65,12 +65,8 @@ abitset_small_list (bitset src, bitset_bindex *list,
   bitset_bindex count = 0;
   /* Is there enough room to avoid checking in each iteration? */
   if (num >= BITSET_WORD_BITS)
-    {
-      BITSET_FOR_EACH_BIT (pos, word)
-        list[count++] = bitno + pos;
-      *next = bitno + BITSET_WORD_BITS;
-      return count;
-    }
+    BITSET_FOR_EACH_BIT (pos, word)
+      list[count++] = bitno + pos;
   else
     BITSET_FOR_EACH_BIT (pos, word)
       {
@@ -81,6 +77,8 @@ abitset_small_list (bitset src, bitset_bindex *list,
             return count;
           }
       }
+  *next = bitno + BITSET_WORD_BITS;
+  return count;
 }
 
 
-- 
2.29.2

[PATCH 2/6] bitset: check empty and full bitsets

[Akim Demaille]

* tests/test-bitset.c (check_zero, check_ones): New.
(check_attributes): Use them.
---
 ChangeLog           |  6 +++++
 tests/test-bitset.c | 56 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 62 insertions(+)

diff --git a/ChangeLog b/ChangeLog
index 88ae15003..5badf0c41 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
+
+	bitset: check empty and full bitsets
+	* tests/test-bitset.c (check_zero, check_ones): New.
+	(check_attributes): Use them.
+
 2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
 
 	bitset: be sure to always return a value
diff --git a/tests/test-bitset.c b/tests/test-bitset.c
index 5068ae782..fc0c6fbe9 100644
--- a/tests/test-bitset.c
+++ b/tests/test-bitset.c
@@ -224,12 +224,37 @@ void compare (enum bitset_attr a, enum bitset_attr b)
 }
 
 
+/* Check empty bitsets.  */
+
+static void
+check_zero (bitset bs)
+{
+  fprintf (stderr, "check_zero\n");
+  bitset_zero (bs);
+
+  /* count. */
+  ASSERT (bitset_count (bs) == 0);
+
+  /* first and last */
+  ASSERT (bitset_first (bs) == BITSET_BINDEX_MAX);
+  ASSERT (bitset_last (bs)  == BITSET_BINDEX_MAX);
+
+  /* FOR_EACH.  */
+  {
+    bitset_iterator iter;
+    bitset_bindex i;
+    BITSET_FOR_EACH (iter, bs, i, 0)
+      ASSERT (0);
+  }
+}
+
 /* Exercise on a single-bit values: it's easy to get the handling of
    the most significant bit wrong.  */
 
 static void
 check_one_bit (bitset bs, int bitno)
 {
+  fprintf (stderr, "check_one_bit(%d)\n", bitno);
   bitset_zero (bs);
   bitset_set (bs, bitno);
 
@@ -252,6 +277,34 @@ check_one_bit (bitset bs, int bitno)
   }
 }
 
+/* Check full bitsets.  */
+
+static void
+check_ones (bitset bs)
+{
+  fprintf (stderr, "check_ones\n");
+  const bitset_bindex size = bitset_size (bs);
+
+  bitset_ones (bs);
+  debug_bitset (bs);
+
+  /* count. */
+  ASSERT (bitset_count (bs) == size);
+
+  /* first and last */
+  ASSERT (bitset_first (bs) == 0);
+  ASSERT (bitset_last (bs)  == size - 1);
+
+  /* FOR_EACH.  */
+  {
+    bitset_iterator iter;
+    bitset_bindex i;
+    bitset_bindex count = 0;
+    BITSET_FOR_EACH (iter, bs, i, 0)
+      ASSERT (i == count++);
+  }
+}
+
 /* Check various operations against expected values for a bitset
    having attributes ATTR.  */
 
@@ -287,6 +340,9 @@ check_attributes (enum bitset_attr attr, int nbits)
   bitset_or (bs, bs1, bs2);
   ASSERT (bitset_count (bs) == 6);
 
+  check_zero (bs);
+  check_ones (bs);
+
   /* Exercise on all the single-bit values: it's easy to get the
      handling of the most significant bit wrong.  */
   for (int bitno = 0; bitno < nbits; ++bitno)
-- 
2.29.2

[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

[PATCH 4/6] bitset: use ffs where possible in the vector implementation

[Akim Demaille]

* lib/bitset/vector.c (vbitset_list): Use BITSET_FOR_EACH_BIT.
---
 ChangeLog           |  5 ++++
 lib/bitset/vector.c | 57 +++++++++++++++++----------------------------
 2 files changed, 27 insertions(+), 35 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 951b82b04..2bc68b9dc 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 vector implementation
+	* lib/bitset/vector.c (vbitset_list): Use BITSET_FOR_EACH_BIT.
+
 2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
 
 	bitset: use ffs where possible in the table implementation
diff --git a/lib/bitset/vector.c b/lib/bitset/vector.c
index fe14d6703..4c0c9dbfd 100644
--- a/lib/bitset/vector.c
+++ b/lib/bitset/vector.c
@@ -204,6 +204,7 @@ static bitset_bindex
 vbitset_list (bitset src, bitset_bindex *list,
               bitset_bindex num, bitset_bindex *next)
 {
+  /* FIXME: almost a duplicate of abitset_list.  Factor?  */
   bitset_windex size = VBITSET_SIZE (src);
   bitset_word *srcp = VBITSET_WORDS (src);
   bitset_bindex bitno = *next;
@@ -211,7 +212,6 @@ vbitset_list (bitset src, bitset_bindex *list,
 
   bitset_windex windex;
   bitset_bindex bitoff;
-  bitset_word word;
 
   if (!bitno)
     {
@@ -242,19 +242,16 @@ vbitset_list (bitset src, bitset_bindex *list,
              on the previous call to this function.  */
 
           bitoff = windex * BITSET_WORD_BITS;
-          word = srcp[windex] >> bitno;
-          for (bitno = bitoff + bitno; word; bitno++)
+          bitset_word word = srcp[windex] >> 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++;
         }
@@ -263,34 +260,24 @@ vbitset_list (bitset src, bitset_bindex *list,
 
   for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
     {
-      if (!(word = srcp[windex]))
+      bitset_word word = srcp[windex];
+      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;
-- 
2.29.2

[PATCH 5/6] bitset: tests: try harder to break it

[Akim Demaille]

bitset_list (used in bitset_first, bitset_next, bitset_count,
BITSET_FOR_EACH, etc.) uses a cache of size BITSET_LIST_SIZE (1024).
None of our tests current try bitsets bigger than this.

* tests/test-bitset.c (compare): Be ready to use bitsets larger than
BITSET_LIST_SIZE.
(main): Likewise.
While at it, also exercise super small bitsets.
---
 ChangeLog           |  8 ++++++++
 tests/test-bitset.c | 28 ++++++++++++++++++----------
 2 files changed, 26 insertions(+), 10 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 2bc68b9dc..cd595f41d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
+
+	bitset: tests: try harder to break it
+	* tests/test-bitset.c (compare): Be ready to use bitsets larger than
+	BITSET_LIST_SIZE.
+	(main): Likewise.
+	While at it, also exercise super small bitsets.
+
 2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
 
 	bitset: use ffs where possible in the vector implementation
diff --git a/tests/test-bitset.c b/tests/test-bitset.c
index fc0c6fbe9..9a2d7c521 100644
--- a/tests/test-bitset.c
+++ b/tests/test-bitset.c
@@ -22,8 +22,8 @@
 
 #define RANDOM(n) (rand () % (n))
 
-static
-void assert_bitset_equal (bitset bs1, bitset bs2)
+static void
+assert_bitset_equal (bitset bs1, bitset bs2)
 {
   debug_bitset (bs1);
   debug_bitset (bs2);
@@ -32,8 +32,8 @@ void assert_bitset_equal (bitset bs1, bitset bs2)
     ASSERT (bitset_test (bs1, i) == bitset_test (bs2, i));
 }
 
-static
-void bitset_random (bitset bs)
+static void
+bitset_random (bitset bs)
 {
   for (bitset_bindex i = 0; i < bitset_size (bs); ++i)
     bitset_set (bs, RANDOM (2));
@@ -43,10 +43,12 @@ void bitset_random (bitset bs)
 /* Check various operations on random bitsets with two different
    implementations.  */
 
-static
-void compare (enum bitset_attr a, enum bitset_attr b)
+static void
+compare (enum bitset_attr a, enum bitset_attr b)
 {
-  const int nbits = RANDOM (256);
+  /* bitset_list (used in many operations) uses a cache whose size is
+     BITSET_LIST_SIZE */
+  const int nbits = RANDOM (2 * BITSET_LIST_SIZE);
 
   /* Four read only random initial values of type A.  */
   const bitset asrc0 = bitset_create (nbits, a);
@@ -356,10 +358,16 @@ check_attributes (enum bitset_attr attr, int nbits)
 
 int main (void)
 {
-  for (int i = 0; i < 2; ++i)
+  for (int i = 0; i < 4; ++i)
     {
-      /* table bitsets have elements that store 256 bits.  */
-      int nbits = i == 0 ? 32 : 257;
+      /* table bitsets have elements that store 256 bits.  bitset_list
+         (used in many operations) uses a cache whose size is
+         BITSET_LIST_SIZE.  */
+      int nbits =
+        i == 0   ? 1
+        : i == 1 ? 32
+        : i == 2 ? 257
+        :          (BITSET_LIST_SIZE + 1);
       check_attributes (BITSET_FIXED,    nbits);
       check_attributes (BITSET_VARIABLE, nbits);
       check_attributes (BITSET_DENSE,    nbits);
-- 
2.29.2

[PATCH 6/6] bitset: exercise the stats too

[Akim Demaille]

* tests/test-bitset.c: Display the stats at the end of the test.
* lib/bitset/stats.c (bitset_log_histogram_print): When diplaying the
last bin, display "256-..." rather that "256-511", since the last bin
does count item greater than or equal to 256.
---
 lib/bitset/stats.c  | 8 +++++++-
 tests/test-bitset.c | 4 ++++
 2 files changed, 11 insertions(+), 1 deletion(-)

diff --git a/lib/bitset/stats.c b/lib/bitset/stats.c
index 5bd44c06a..df9264285 100644
--- a/lib/bitset/stats.c
+++ b/lib/bitset/stats.c
@@ -154,13 +154,19 @@ bitset_log_histogram_print (FILE *file, const char *name, const char *msg,
       fprintf (file, "%*d\t%8u (%5.1f%%)\n",
                max_width, i, bins[i], 100.0 * bins[i] / total);
 
-    for (; i < n_bins; i++)
+    for (; i < n_bins - 1; i++)
       fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n",
                max_width - ((unsigned) (0.30103 * (i) + 0.9999) + 1),
                1UL << (i - 1),
                (1UL << i) - 1,
                bins[i],
                (100.0 * bins[i]) / total);
+
+    fprintf (file, "%*lu-...\t%8u (%5.1f%%)\n",
+             max_width - ((unsigned) (0.30103 * (i) + 0.9999) + 1),
+             1UL << (i - 1),
+             bins[i],
+             (100.0 * bins[i]) / total);
   }
 }
 
diff --git a/tests/test-bitset.c b/tests/test-bitset.c
index 9a2d7c521..6fa656a22 100644
--- a/tests/test-bitset.c
+++ b/tests/test-bitset.c
@@ -358,6 +358,8 @@ check_attributes (enum bitset_attr attr, int nbits)
 
 int main (void)
 {
+  bitset_stats_enable ();
+
   for (int i = 0; i < 4; ++i)
     {
       /* table bitsets have elements that store 256 bits.  bitset_list
@@ -382,5 +384,7 @@ int main (void)
   compare (BITSET_VARIABLE, BITSET_SPARSE);
   compare (BITSET_VARIABLE, BITSET_FRUGAL);
   compare (BITSET_VARIABLE, BITSET_GREEDY);
+
+  bitset_stats_dump (stderr);
   return 0;
 }
-- 
2.29.2

[PATCH 6/6] bitset: tests: exercise the stats too

[Akim Demaille]

* tests/test-bitset.c: Display the stats at the end of the test.
* lib/bitset/stats.c (bitset_log_histogram_print): When diplaying the
last bin, display "256-..." rather that "256-511", since the last bin
does count item greater than or equal to 256.
---
 ChangeLog           | 9 +++++++++
 lib/bitset/stats.c  | 8 +++++++-
 tests/test-bitset.c | 4 ++++
 3 files changed, 20 insertions(+), 1 deletion(-)

diff --git a/ChangeLog b/ChangeLog
index cd595f41d..55c4e08e8 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
+
+	bitset: tests: exercise the stats too
+
+	* tests/test-bitset.c: Display the stats at the end of the test.
+	* lib/bitset/stats.c (bitset_log_histogram_print): When diplaying the
+	last bin, display "256-..." rather that "256-511", since the last bin
+	does count item greater than or equal to 256.
+
 2020-11-19  Akim Demaille  <akim@lrde.epita.fr>
 
 	bitset: tests: try harder to break it
diff --git a/lib/bitset/stats.c b/lib/bitset/stats.c
index 5bd44c06a..df9264285 100644
--- a/lib/bitset/stats.c
+++ b/lib/bitset/stats.c
@@ -154,13 +154,19 @@ bitset_log_histogram_print (FILE *file, const char *name, const char *msg,
       fprintf (file, "%*d\t%8u (%5.1f%%)\n",
                max_width, i, bins[i], 100.0 * bins[i] / total);
 
-    for (; i < n_bins; i++)
+    for (; i < n_bins - 1; i++)
       fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n",
                max_width - ((unsigned) (0.30103 * (i) + 0.9999) + 1),
                1UL << (i - 1),
                (1UL << i) - 1,
                bins[i],
                (100.0 * bins[i]) / total);
+
+    fprintf (file, "%*lu-...\t%8u (%5.1f%%)\n",
+             max_width - ((unsigned) (0.30103 * (i) + 0.9999) + 1),
+             1UL << (i - 1),
+             bins[i],
+             (100.0 * bins[i]) / total);
   }
 }
 
diff --git a/tests/test-bitset.c b/tests/test-bitset.c
index 9a2d7c521..6fa656a22 100644
--- a/tests/test-bitset.c
+++ b/tests/test-bitset.c
@@ -358,6 +358,8 @@ check_attributes (enum bitset_attr attr, int nbits)
 
 int main (void)
 {
+  bitset_stats_enable ();
+
   for (int i = 0; i < 4; ++i)
     {
       /* table bitsets have elements that store 256 bits.  bitset_list
@@ -382,5 +384,7 @@ int main (void)
   compare (BITSET_VARIABLE, BITSET_SPARSE);
   compare (BITSET_VARIABLE, BITSET_FRUGAL);
   compare (BITSET_VARIABLE, BITSET_GREEDY);
+
+  bitset_stats_dump (stderr);
   return 0;
 }
-- 
2.29.2

Re: [PATCH 0/6] bitset: more conversions to ffs

[Bruno Haible]

Hi Akim,

> When gnulib have fls* support, we will be able do the same for
> bitset_list_reverse

Gnulib has modules integer_length, integer_length_l, integer_length_ll.
That sounds like what you are asking for.

Bruno

Re: [PATCH 0/6] bitset: more conversions to ffs

[Akim Demaille]

Hi Bruno,

> Le 19 nov. 2020 à 16:04, Bruno Haible <bruno@clisp.org> a écrit :
> 
> Hi Akim,
> 
>> When gnulib have fls* support, we will be able do the same for
>> bitset_list_reverse
> 
> Gnulib has modules integer_length, integer_length_l, integer_length_ll.

Oh, yes.  Why these names?  "fls" feels more "natural" in front of fss.
But just as cryptic indeed.

I can see it is not POSIX, but

https://www.freebsd.org/cgi/man.cgi?query=fls&sektion=3&manpath=FreeBSD+7.1-RELEASE

> That sounds like what you are asking for.

Too bad :( I was happy being done with that :)

Thanks!

Re: [PATCH 0/6] bitset: more conversions to ffs

[Bruno Haible]

Akim Demaille wrote:
> > Gnulib has modules integer_length, integer_length_l, integer_length_ll.
> 
> Oh, yes.  Why these names?

The name 'integer-length' comes from ANSI Common Lisp [1]. The suffixes exist
because in C we need 3 different functions for 'unsigned int', 'unsigned long',
and 'unsigned long long' arguments.

> "fls" feels more "natural" in front of fss.
> But just as cryptic indeed.
> 
> I can see it is not POSIX, but
> 
> https://www.freebsd.org/cgi/man.cgi?query=fls&sektion=3&manpath=FreeBSD+7.1-RELEASE

ANSI Common Lisp predates FreeBSD 5.3 by 15 years :-)

Bruno

[1] http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/fun_integer-length.html

Re: [PATCH 0/6] bitset: more conversions to ffs

[Akim Demaille]

Hi Bruno,

So I installed these commits.

> Le 20 nov. 2020 à 00:05, Bruno Haible <bruno@clisp.org> a écrit :
> 
> Akim Demaille wrote:
>>> Gnulib has modules integer_length, integer_length_l, integer_length_ll.
>> 
>> Oh, yes.  Why these names?
> 
> The name 'integer-length' comes from ANSI Common Lisp [1].
> [...]
> ANSI Common Lisp predates FreeBSD 5.3 by 15 years :-)

Thanks for the reference!  Cheers!