Re: A new module: bitset

[Akim Demaille]

> Le 28 nov. 2018 à 06:03, Paul Eggert  a écrit :
> 
> Akim Demaille wrote:
>> What do you propose?
> 
> A simple, general solution is to use only malloc/calloc/realloc, and to have 
> bitset functions fail when they exhaust memory.

Then I guess the current state does what you want.  If you
don't want the two occurrences of xmalloc in bitset, define
OBSTACK_CHUNK_ALLOC to what you want.

Re: A new module: bitset

[Paul Eggert]

Akim Demaille wrote:

What do you propose?


A simple, general solution is to use only malloc/calloc/realloc, and to have 
bitset functions fail when they exhaust memory.

Re: A new module: bitset

[Akim Demaille]

> Le 27 nov. 2018 à 21:31, Paul Eggert  a écrit :
> 
> On 11/26/18 8:15 PM, Akim Demaille wrote:
>> The current implementation uses xmalloc, but there are also calls to calloc 
>> and realloc.
> 
> How can it be right to combine xmalloc with calloc/realloc?

I agree.

> Shouldn't the implementation use xmalloc, xcalloc, and xrealloc for 
> consistency? Also, what about applications that don't want to use the x* 
> variants?

What do you propose?

Re: A new module: bitset

[Paul Eggert]

On 11/26/18 8:15 PM, Akim Demaille wrote:

The current implementation uses xmalloc, but there are also calls to calloc and 
realloc.


How can it be right to combine xmalloc with calloc/realloc? Shouldn't 
the implementation use xmalloc, xcalloc, and xrealloc for consistency? 
Also, what about applications that don't want to use the x* variants?

Re: A new module: bitset

[Akim Demaille]

Hi Paul!

> Le 25 nov. 2018 à 20:43, Paul Eggert  a écrit :
> 
> One top-level question is how does memory allocation work? Emacs has its own 
> memory allocator, and doesn't want to use plain malloc. It has its own 
> xmalloc implementation; will that suffice?

The current implementation uses xmalloc, but there are also calls to calloc and 
realloc.

Re: A new module: bitset

[Akim Demaille]

Hi Bruno!

> Le 25 nov. 2018 à 21:01, Bruno Haible  a écrit :
> 
> Hi Akim,
> 
>> Or completely change: all the bitsets of a bitsetv have the same dimension, 
>> so we could go to bitmatrix.
> 
> On the other hand, the module does not implement matrix operations
> (matrix multiplication, transposition, determinant),

But it could :)

> only transitive
> closure (which maybe is not so suitable for gnulib and should stay in
> Bison?).

It's not that big and would hardly code-bloat users.  I'd prefer it
to stay in gnulib, but it's your call.

> The definition 'typedef bitset * bitsetv;' is really an array of bitsets.
> 
> This also means that bitsetv.h should probably be renamed to
> bitset-array.h, not bitset-vector.h.

Ok.  But then what type name and prefix should we use?  Currently
it's bitsetv.  Would you want bitseta?  (I like bitmat :)

Re: A new module: bitset

[Bruno Haible]

Hi Akim,

> Or completely change: all the bitsets of a bitsetv have the same dimension, 
> so we could go to bitmatrix.

On the other hand, the module does not implement matrix operations
(matrix multiplication, transposition, determinant), only transitive
closure (which maybe is not so suitable for gnulib and should stay in
Bison?).

The definition 'typedef bitset * bitsetv;' is really an array of bitsets.

> I went for 'bitset/vector.h': same initial, and clear meaning (to me?).

Good idea. Yes, 'vector' commonly means an array of variable size
(as in C++, Common Lisp, Java, ...).

This also means that bitsetv.h should probably be renamed to
bitset-array.h, not bitset-vector.h.

> Currently bitset/ is only about implementation details, so I don't think 
> bitset vectors should be part of bitset/.

I agree.

The name conflict between bitset-vector.h and bitset/vector.h is superficial;
given that only the implementor knows about the second one, I find it
acceptable.

Bruno

Re: A new module: bitset

[Paul Eggert]

Akim Demaille wrote:

I think it should move to gnulib: it's way more powerful than what
we use in Bison only.  Paul already reported he would be interested
in using this module in Emacs.


Yes, Emacs already has a bitset implementation for its boolean vectors. My vague 
recollection is that the Emacs code could benefit from using a Gnulib 
implementation, and that the new Gnulib bitset implementation would benefit from 
some of the ideas in the Emacs code.


One top-level question is how does memory allocation work? Emacs has its own 
memory allocator, and doesn't want to use plain malloc. It has its own xmalloc 
implementation; will that suffice?

Re: A new module: bitset

[Akim Demaille]

> Le 25 nov. 2018 à 19:55, Akim Demaille  a écrit :
> 
>>> Sure. You can push it into gnulib, without having extensive tests.
>> 
>> Great!  I read this as an ok to push the current state, which takes
>> into account your comments, but will most probably require more changes
>> later.
>> 
>> First, the bitset module (without bitset vectors).
> 
> Then its test/doc.

Finally, the bitsetv module.

commit b9ca447bb912cad2fd7aeeda3784aff42f13a336
Author: Akim Demaille 
Date:   Sun Nov 25 18:55:32 2018 +0100

bitsetv: new module

* lib/bitsetv.c, lib/bitsetv.h, modules/bitsetv: New.

diff --git a/ChangeLog b/ChangeLog
index 24bcccb44..681603031 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2018-11-25  Akim Demaille  
+
+   bitsetv: new module
+   * lib/bitsetv.c, lib/bitsetv.h, modules/bitsetv: New.
+
 2018-11-25  Akim Demaille  
 
bitset: add tests and doc
diff --git a/lib/bitsetv.c b/lib/bitsetv.c
new file mode 100644
index 0..2a7ad3a01
--- /dev/null
+++ b/lib/bitsetv.c
@@ -0,0 +1,196 @@
+/* Bitset vectors.
+
+   Copyright (C) 2001-2002, 2004-2006, 2009-2015, 2018 Free Software
+   Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see .  */
+
+#include 
+
+#include "bitsetv.h"
+
+#include 
+
+
+/* Create a vector of N_VECS bitsets, each of N_BITS, and of
+   type TYPE.  */
+bitset *
+bitsetv_alloc (bitset_bindex n_vecs, bitset_bindex n_bits,
+   enum bitset_type type)
+{
+  /* Determine number of bytes for each set.  */
+  size_t bytes = bitset_bytes (type, n_bits);
+
+  /* If size calculation overflows, memory is exhausted.  */
+  if (BITSET_SIZE_MAX / (sizeof (bitset) + bytes) <= n_vecs)
+xalloc_die ();
+
+  /* Allocate vector table at head of bitset array.  */
+  size_t vector_bytes = (n_vecs + 1) * sizeof (bitset) + bytes - 1;
+  vector_bytes -= vector_bytes % bytes;
+  bitset *bsetv = xcalloc (1, vector_bytes + bytes * n_vecs);
+
+  bitset_bindex i = 0;
+  for (i = 0; i < n_vecs; i++)
+{
+  bsetv[i] = (bitset) (void *) ((char *) bsetv + vector_bytes + i * bytes);
+
+  bitset_init (bsetv[i], n_bits, type);
+}
+
+  /* Null terminate table.  */
+  bsetv[i] = 0;
+  return bsetv;
+}
+
+
+/* Create a vector of N_VECS bitsets, each of N_BITS, and with
+   attribute hints specified by ATTR.  */
+bitset *
+bitsetv_create (bitset_bindex n_vecs, bitset_bindex n_bits, unsigned attr)
+{
+  enum bitset_type type = bitset_type_choose (n_bits, attr);
+  return bitsetv_alloc (n_vecs, n_bits, type);
+}
+
+
+/* Free bitset vector BSETV.  */
+void
+bitsetv_free (bitsetv bsetv)
+{
+  for (bitset_bindex i = 0; bsetv[i]; i++)
+BITSET_FREE_ (bsetv[i]);
+  free (bsetv);
+}
+
+
+/* Zero a vector of bitsets.  */
+void
+bitsetv_zero (bitsetv bsetv)
+{
+  for (bitset_bindex i = 0; bsetv[i]; i++)
+bitset_zero (bsetv[i]);
+}
+
+
+/* Set a vector of bitsets to ones.  */
+void
+bitsetv_ones (bitsetv bsetv)
+{
+  for (bitset_bindex i = 0; bsetv[i]; i++)
+bitset_ones (bsetv[i]);
+}
+
+
+/* Given a vector BSETV of N bitsets of size N, modify its contents to
+   be the transitive closure of what was given.  */
+void
+bitsetv_transitive_closure (bitsetv bsetv)
+{
+  for (bitset_bindex i = 0; bsetv[i]; i++)
+for (bitset_bindex j = 0; bsetv[j]; j++)
+  if (bitset_test (bsetv[j], i))
+bitset_or (bsetv[j], bsetv[j], bsetv[i]);
+}
+
+
+/* Given a vector BSETV of N bitsets of size N, modify its contents to
+   be the reflexive transitive closure of what was given.  This is
+   the same as transitive closure but with all bits on the diagonal
+   of the bit matrix set.  */
+void
+bitsetv_reflexive_transitive_closure (bitsetv bsetv)
+{
+  bitsetv_transitive_closure (bsetv);
+  for (bitset_bindex i = 0; bsetv[i]; i++)
+bitset_set (bsetv[i], i);
+}
+
+
+/* Dump the contents of a bitset vector BSETV with N_VECS elements to
+   FILE.  */
+void
+bitsetv_dump (FILE *file, char const *title, char const *subtitle,
+  bitsetv bsetv)
+{
+  fprintf (file, "%s\n", title);
+  for (bitset_windex i = 0; bsetv[i]; i++)
+{
+  fprintf (file, "%s %lu\n", subtitle, (unsigned long) i);
+  bitset_dump (file, bsetv[i]);
+}
+
+  fprintf (file, "\n");
+}
+
+
+void
+debug_bitsetv (bitsetv bsetv)
+{
+  for (bitset_windex i = 0; bsetv[i]; i++)
+{
+  fprintf (stderr, "%lu: ", (unsigned long) i);
+  debug_bitset (bsetv[i]);

Re: A new module: bitset

[Akim Demaille]

> Le 25 nov. 2018 à 19:52, Akim Demaille  a écrit :
> 
>> Le 25 nov. 2018 à 18:54, Bruno Haible  a écrit :
>> 
>> Hi Akim,
>> 
 * Regarding tests: There is a large amount of algorithmic code. While
 the parts that Bison uses are surely correct, there is a possibility
 of bugs in the more rarely used parts. I would find it very useful
 to have unit tests of all 32 operations.
>>> 
>>> I definitely agree.  But I'd like to be incremental on this
>>> regard.
>> 
>> Sure. You can push it into gnulib, without having extensive tests.
> 
> Great!  I read this as an ok to push the current state, which takes
> into account your comments, but will most probably require more changes
> later.
> 
> First, the bitset module (without bitset vectors).

Then its test/doc.

commit 7c0d555aa341d7d5b8ab2fa8a94ee580636cc1c2
Author: Akim Demaille 
Date:   Sun Nov 25 09:49:09 2018 +0100

bitset: add tests and doc

First stabs at providing a documentation and test for the bitset
module.

* doc/bitset.texi, modules/test-bitset, tests/bitset-tests.c: New.

diff --git a/ChangeLog b/ChangeLog
index 9fae7910f..24bcccb44 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2018-11-25  Akim Demaille  
+
+   bitset: add tests and doc
+   First stabs at providing a documentation and test for the bitset
+   module.
+   * doc/bitset.texi, modules/test-bitset, tests/bitset-tests.c: New.
+
 2018-11-25  Akim Demaille  
 
bitset: new module
diff --git a/doc/bitset.texi b/doc/bitset.texi
new file mode 100644
index 0..614961b95
--- /dev/null
+++ b/doc/bitset.texi
@@ -0,0 +1,63 @@
+@node Bitsets
+@section Bitsets
+
+The module @samp{bitset} provides a common interface to several
+implementations of bitsets.  It also provides routines for vectors of bitsets.
+
+To look at an existing use, see GNU Bison.
+
+Currently it supports five flavours of bitsets:
+@description @code
+@item BITSET_ARRAY
+Array of bits (fixed size, fast for dense bitsets). Memory for bit array
+and bitset structure allocated contiguously.
+@item BITSET_LIST
+Linked list of arrays of bits (variable size, least storage for large
+very sparse sets).
+@item BITSET_TABLE
+Expandable table of pointers to arrays of bits (variable size, less
+storage for large sparse sets).  Faster than @code{BITSET_LIST} for
+random access.
+@item BITSET_VARRAY
+Variable array of bits (variable size, fast for dense bitsets).
+@item BITSET_STATS
+Wrapper bitset for internal use only.  Used for gathering statistics
+and/or better run-time checking.
+@end description
+
+However, the choice of the actual implementation is performed by the
+library, based on the user provided attributes:
+
+@description @code
+@code BITSET_FIXED
+Bitset size fixed.
+@code BITSET_VARIABLE
+Bitset size variable.
+@code BITSET_DENSE
+Bitset dense.
+@code BITSET_SPARSE
+Bitset sparse.
+@code BITSET_FRUGAL
+Prefer most compact.
+@code BITSET_GREEDY
+Prefer fastest at memory expense.
+@end description
+
+
+@smallexample
+enum { nbits = 32 };
+
+bitset bs0 = bitset_create (nbits, BITSET_FIXED);
+bitset_set (bs1, 1);
+bitset_set (bs1, 3);
+bitset_set (bs1, 5);
+
+bitset bs1 = bitset_create (nbits, BITSET_FIXED);
+bitset_set (bs1, 0);
+bitset_set (bs1, 2);
+bitset_set (bs1, 4);
+
+bitset bs = bitset_create (nbits, BITSET_FIXED);
+bitset_or (bs, b1, b2);
+ASSERT (bitset_count (bs) == 6);
+@end smallexample
diff --git a/modules/bitset-tests b/modules/bitset-tests
new file mode 100644
index 0..4a7b8b32b
--- /dev/null
+++ b/modules/bitset-tests
@@ -0,0 +1,11 @@
+Files:
+tests/test-bitset.c
+tests/macros.h
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-bitset
+check_PROGRAMS += test-bitset
diff --git a/tests/test-bitset.c b/tests/test-bitset.c
new file mode 100644
index 0..b673d188c
--- /dev/null
+++ b/tests/test-bitset.c
@@ -0,0 +1,66 @@
+/* Test of bitset.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see .  */
+
+#include 
+
+#include "bitset.h"
+
+#include "macros.h"
+
+void check_attributes (enum bitset_attr attr)
+{
+  enum { nbits = 32 };
+
+  bitset bs0 = bitset_create (nbits, attr);
+  ASSERT (bitset_size (bs0) == 32);
+  ASSERT (bitset_count (bs0) == 0);
+  ASSERT (bitset_empty_p (bs0));
+
+  bitset bs1 = bitset_create (nbits, attr);
+  bitset_set (bs1, 1);
+  bitset_set 

Re: A new module: bitset

[Akim Demaille]

> Le 25 nov. 2018 à 18:02, Akim Demaille  a écrit :
> 
> Hi Bruno!
> 
>> * File names are nowadays not limited to 8+3 characters, and names
>> like 'abitset.h', 'bbitset.h', 'ebitset.h', 'lbitset.h', 'vbitset.h'
>> are not really telling. How about using more descriptive names?
>> Note: You can use subdirectories to keep files grouped together,
>> especially since the only file the user sees is bitset.h.
>> How about renaming e.g.
>>   abitset.[hc] -> bitset/array.[hc]
>>   lbitset.[hc] -> bitset/list.[hc]
>> and keeping only bitset.h at the top level?
> 
> Fine with me!

There was the problem of vbitset.[ch], labeled as "variable array bitsets".  I 
disliked 'bitset/variable.h' because it's misleading, and does not look 
balanced in front of 'bitset/array.h' which is not named 'bitset/fixed.h'.  So, 
as a C++ developer, I went for 'bitset/vector.h': same initial, and clear 
meaning (to me?).

But now we also have the bitset vectors.  Currently bitset/ is only about 
implementation details, so I don't think bitset vectors should be part of 
bitset/.  I would be fine with bitsetv.[ch], as is currently the case, but 
maybe you have a different opinion.  Of course it could be bitset-vector.[ch].

Or completely change: all the bitsets of a bitsetv have the same dimension, so 
we could go to bitmatrix.  Which has the unfortunate consequence of making the 
link between both modules looser.

Re: A new module: bitset

[Bruno Haible]

Hi Akim,

> > * Regarding tests: There is a large amount of algorithmic code. While
> >  the parts that Bison uses are surely correct, there is a possibility
> >  of bugs in the more rarely used parts. I would find it very useful
> >  to have unit tests of all 32 operations.
> 
> I definitely agree.  But I'd like to be incremental on this
> regard.

Sure. You can push it into gnulib, without having extensive tests.

> >  An approach that minimizes the code to be written would be to
> >  do the same operations on, say, list-bitsets and array-bitsets, and
> >  compare the results. This way, you can infer the correctness of the
> >  list-bitsets implementation, assuming the correctness of the array-bitsets.
> >  (This approach is already used in the test-*list.c tests.)
> 
> Sure, but that won't catch errors on dispatch that would
> accidentally map two operations to the same one.  So, eventually
> it would be better to set the real expected results.

Randomized tests provide the best code coverage (i.e. exercise all branches
of the algorithmic code), but for randomized tests you don't have expected
results. So, how about a combination of the two approaches?
  - Tests with given inputs and expected results, as a basis and
to catch dispatch code errors,
  - Tests with randomized input that compare the different implementations
against each other, for code coverage.

Bruno

Re: A new module: bitset

[Akim Demaille]

Hi Michael,

I meant to put you in CC, but forgot to do it.  This message
is to inform you that we are moving your bitset library, as it
is currently in Bison, to gnulib.

See https://lists.gnu.org/archive/html/bug-gnulib/2018-11/msg00045.html
and following.

Cheers!

> Le 25 nov. 2018 à 09:57, Akim Demaille  a écrit :
> 
> Dead gnulibers,
> 
> In Bison, the core algorithms of the computation of the parsing tables
> heavily use bitsets and arrays of bitsets.  Initially Bison used its
> own routines for bitset manipulation (actually, a lot was done by
> hand, without any abstraction), but at some point I saw a very nice
> submission from Michael Hayes on the GCC lists for a fully featured
> lib on bitsets.  (https://gcc.gnu.org/ml/gcc/2002-01/msg00825.html).
> 
> I don't know whether it finally made it in GCC
> (https://gcc.gnu.org/ml/gcc/2002-05/msg01564.html), but it was
> included in Bison, and we maintained it over the years (mostly
> modernizing).
> 
> I think it should move to gnulib: it's way more powerful than what
> we use in Bison only.  Paul already reported he would be interested
> in using this module in Emacs.
> 
> This library is very flexible and implements several backends,
> depending on the expected use (whether dense/sparse, fixed/dynamic,
> etc.).  The headers are largely commented; but I have written a short
> doc so that the reader can get at least a sense of how to use this
> library.
> 
> Cheers!
> 
> 

Re: A new module: bitset

[Akim Demaille]

Hi Bruno!

> Le 25 nov. 2018 à 16:44, Bruno Haible  a écrit :
> 
> Some remarks:
> 
> * I can imagine programs that want bitsets but no bitset-vectors.
>  Suggestion: Move the bitsetv* code to a second module, named
>  'bitset-vector'.

That sounds good, indeed.

> * File names are nowadays not limited to 8+3 characters, and names
>  like 'abitset.h', 'bbitset.h', 'ebitset.h', 'lbitset.h', 'vbitset.h'
>  are not really telling. How about using more descriptive names?
>  Note: You can use subdirectories to keep files grouped together,
>  especially since the only file the user sees is bitset.h.
>  How about renaming e.g.
>abitset.[hc] -> bitset/array.[hc]
>lbitset.[hc] -> bitset/list.[hc]
>  and keeping only bitset.h at the top level?

Fine with me!

> * In the tests, the function
>void check_attributes (enum bitset_attr attr)
>  ignores its attr argument. Probably you meant to use attr instead of
>  BITSET_FIXED?

Good catch, thanks.  I wonder why the compiler did not complain.

> * Regarding tests: There is a large amount of algorithmic code. While
>  the parts that Bison uses are surely correct, there is a possibility
>  of bugs in the more rarely used parts. I would find it very useful
>  to have unit tests of all 32 operations.

I definitely agree.  But I'd like to be incremental on this
regard.

>  An approach that minimizes the code to be written would be to
>  do the same operations on, say, list-bitsets and array-bitsets, and
>  compare the results. This way, you can infer the correctness of the
>  list-bitsets implementation, assuming the correctness of the array-bitsets.
>  (This approach is already used in the test-*list.c tests.)

Sure, but that won't catch errors on dispatch that would
accidentally map two operations to the same one.  So, eventually
it would be better to set the real expected results.

> * The hint BITSET_FRUGAL is unused. How about eliminating it?

My reading of the code was rather that it is there, but needs
not be dealt with by the code, since that's the final default
case that implements it.  So it makes sense from the interface
point of view, but needs not be explicitly handled by the code.

Re: A new module: bitset

[Bruno Haible]

Hi Akim,

This code looks like well-designed, high-quality and very suitable for
gnulib.

I love especially about it that it's adaptable as programs change:
Initially the program might require fixed-size bitsets, and later
move to variable-size bitsets.

> I think it should move to gnulib

Yes, definitely.

> I have written a short
> doc so that the reader can get at least a sense of how to use this
> library.

This doc is good and essential (to get an overview).

Some remarks:

* I can imagine programs that want bitsets but no bitset-vectors.
  Suggestion: Move the bitsetv* code to a second module, named
  'bitset-vector'.

* File names are nowadays not limited to 8+3 characters, and names
  like 'abitset.h', 'bbitset.h', 'ebitset.h', 'lbitset.h', 'vbitset.h'
  are not really telling. How about using more descriptive names?
  Note: You can use subdirectories to keep files grouped together,
  especially since the only file the user sees is bitset.h.
  How about renaming e.g.
abitset.[hc] -> bitset/array.[hc]
lbitset.[hc] -> bitset/list.[hc]
  and keeping only bitset.h at the top level?

* In the tests, the function
void check_attributes (enum bitset_attr attr)
  ignores its attr argument. Probably you meant to use attr instead of
  BITSET_FIXED?

* Regarding tests: There is a large amount of algorithmic code. While
  the parts that Bison uses are surely correct, there is a possibility
  of bugs in the more rarely used parts. I would find it very useful
  to have unit tests of all 32 operations.

  An approach that minimizes the code to be written would be to
  do the same operations on, say, list-bitsets and array-bitsets, and
  compare the results. This way, you can infer the correctness of the
  list-bitsets implementation, assuming the correctness of the array-bitsets.
  (This approach is already used in the test-*list.c tests.)

* The hint BITSET_FRUGAL is unused. How about eliminating it?

Bruno

Re: A new module: bitset

[Akim Demaille]

Second part: doc and tests.

commit 52342213a42a77b639174e3fc7f2c586f6fc2422
Author: Akim Demaille 
Date:   Sun Nov 25 09:49:09 2018 +0100

   bitset: add tests and doc

   First stabs at providing a documentation and test for the bitset
   module.

   * doc/bitset.texi, modules/test-bitset, tests/bitset-tests.c: New.

diff --git a/ChangeLog b/ChangeLog
index 420e9941e..44db76e07 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2018-11-25  Akim Demaille  
+
+   bitset: add tests and doc
+   First stabs at providing a documentation and test for the bitset
+   module.
+   * doc/bitset.texi, modules/test-bitset, tests/bitset-tests.c: New.
+
2018-11-25  Akim Demaille  

bitset: new module
diff --git a/doc/bitset.texi b/doc/bitset.texi
new file mode 100644
index 0..614961b95
--- /dev/null
+++ b/doc/bitset.texi
@@ -0,0 +1,63 @@
+@node Bitsets
+@section Bitsets
+
+The module @samp{bitset} provides a common interface to several
+implementations of bitsets.  It also provides routines for vectors of bitsets.
+
+To look at an existing use, see GNU Bison.
+
+Currently it supports five flavours of bitsets:
+@description @code
+@item BITSET_ARRAY
+Array of bits (fixed size, fast for dense bitsets). Memory for bit array
+and bitset structure allocated contiguously.
+@item BITSET_LIST
+Linked list of arrays of bits (variable size, least storage for large
+very sparse sets).
+@item BITSET_TABLE
+Expandable table of pointers to arrays of bits (variable size, less
+storage for large sparse sets).  Faster than @code{BITSET_LIST} for
+random access.
+@item BITSET_VARRAY
+Variable array of bits (variable size, fast for dense bitsets).
+@item BITSET_STATS
+Wrapper bitset for internal use only.  Used for gathering statistics
+and/or better run-time checking.
+@end description
+
+However, the choice of the actual implementation is performed by the
+library, based on the user provided attributes:
+
+@description @code
+@code BITSET_FIXED
+Bitset size fixed.
+@code BITSET_VARIABLE
+Bitset size variable.
+@code BITSET_DENSE
+Bitset dense.
+@code BITSET_SPARSE
+Bitset sparse.
+@code BITSET_FRUGAL
+Prefer most compact.
+@code BITSET_GREEDY
+Prefer fastest at memory expense.
+@end description
+
+
+@smallexample
+enum { nbits = 32 };
+
+bitset bs0 = bitset_create (nbits, BITSET_FIXED);
+bitset_set (bs1, 1);
+bitset_set (bs1, 3);
+bitset_set (bs1, 5);
+
+bitset bs1 = bitset_create (nbits, BITSET_FIXED);
+bitset_set (bs1, 0);
+bitset_set (bs1, 2);
+bitset_set (bs1, 4);
+
+bitset bs = bitset_create (nbits, BITSET_FIXED);
+bitset_or (bs, b1, b2);
+ASSERT (bitset_count (bs) == 6);
+@end smallexample
diff --git a/modules/bitset-tests b/modules/bitset-tests
new file mode 100644
index 0..4a7b8b32b
--- /dev/null
+++ b/modules/bitset-tests
@@ -0,0 +1,11 @@
+Files:
+tests/test-bitset.c
+tests/macros.h
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-bitset
+check_PROGRAMS += test-bitset
diff --git a/tests/test-bitset.c b/tests/test-bitset.c
new file mode 100644
index 0..1e1e92af6
--- /dev/null
+++ b/tests/test-bitset.c
@@ -0,0 +1,63 @@
+/* Test of bitset.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see .  */
+
+#include 
+
+#include "bitset.h"
+
+#include "macros.h"
+
+void check_attributes (enum bitset_attr attr)
+{
+  enum { nbits = 32 };
+
+  bitset bs0 = bitset_create (nbits, BITSET_FIXED);
+  ASSERT (bitset_size (bs0) == 32);
+  ASSERT (bitset_count (bs0) == 0);
+  ASSERT (bitset_empty_p (bs0));
+
+  bitset bs1 = bitset_create (nbits, BITSET_FIXED);
+  bitset_set (bs1, 1);
+  bitset_set (bs1, 3);
+  bitset_set (bs1, 5);
+  ASSERT (bitset_count (bs1) == 3);
+  ASSERT (!bitset_empty_p (bs1));
+
+  bitset bs2 = bitset_create (nbits, BITSET_FIXED);
+  bitset_set (bs2, 0);
+  bitset_set (bs2, 2);
+  bitset_set (bs2, 4);
+
+  ASSERT (bitset_disjoint_p (bs1, bs2));
+
+  bitset bs = bitset_create (nbits, BITSET_FIXED);
+  bitset_and (bs, bs1, bs2);
+  ASSERT (bitset_count (bs) == 0);
+
+  bitset_or (bs, bs1, bs2);
+  ASSERT (bitset_count (bs) == 6);
+}
+
+int main (void)
+{
+  check_attributes (BITSET_FIXED);
+  check_attributes (BITSET_VARIABLE);
+  check_attributes (BITSET_DENSE);
+  check_attributes (BITSET_SPARSE);
+  check_attributes (BITSET_FRUGAL);
+  check_attributes (BITSET_GREEDY);
+  return 0;
+}