Hi Bruno,
> Le 3 janv. 2021 à 03:19, Bruno Haible <br...@clisp.org> a écrit :
>
> Hi Akim,
>
> You might have noticed that we are currently publishing a news item per week
> about Gnulib in https://savannah.gnu.org/news/?group=gnulib ; they get
> propagated to http://planet.gnu.org/ .
>
> Would you want to write a short text about the 'bitset' module, for
> publication on 2021-01-06 or 2021-01-20?
>
> The audience is someone who may have heard about Gnulib, but is not yet
> using it.
Here's my proposal. Feel free to edit it at will.
Cheers!
# A set of bitset implementations
Gnulib features bitset, a module to support operations of lists of bits.
Its API is rich, and includes:
- all the expected operations on single bit (set, toggle, test, etc.);
- all the traditional binary bitwise operators (and, or, xor), often in two
flavors (return new values, or perform in place);
- some useful ternary operations, such as ((a ∧ b) ∨ c), ((a ∧ ¬b) ∨ c), etc.
Also in two flavors;
- many predicates (empty, equal, intersects, disjoint, subset and so forth);
- and of course, object creation, destruction, printing, iteration, reverse
iteration, etc.
The following example, taken from Bison, shows the bitset module in action.
It's a fix-point computation of `N`, a bitset of the "useful" symbols (a symbol
is useful if it can actually correspond to a piece of text. Think for instance
to `a: a b; b: a;`, `a` and `b` are useless).
```
static void
useless_nonterminals (bitset N, bitset P)
{
/* N is the bitset as built. Np is set being built this iteration.
P is bitset of all productions which have a RHS all in N. */
bitset Np = bitset_create (nnterms, BITSET_FIXED);
while (true)
{
bitset_copy (Np, N);
for (rule_number r = 0; r < nrules; ++r)
if (!bitset_test (P, r)
&& useful_production (r, N))
{
bitset_set (Np, rules[r].lhs->number);
bitset_set (P, r);
}
if (bitset_equal_p (N, Np))
break;
bitset_swap (N, Np);
}
bitset_free (N);
N = Np;
}
```
Like several other gnulib modules, bitset's API actually sits on top of several
implementations, with different performance profiles. Indeed bitsets can have
a fixed size, or being resizable; they can be tailored for dense sets (think of
an array of bits), or sparse (think of list of bits, or alternatively an table
of segments of dense bits). The module also includes a dedicated
implementation for small bitsets, fitting in machine words, which is
automatically selects when appropriate. It even features another
implementation, stats, which wraps a "genuine" implementation to gather
statistical data about the use of the bitsets, to help you tune your use of
bitset.
All this in a very transparent manner: an argument provided to the constructor
(see `BITSET_FIXED` in the example above).
Gnulib hosts another module, bitsetv, which uses the bitset module to provide
support for matrices of bits.
Both modules were crafted in 2002 by Michael Hayes for GCC
(https://gcc.gnu.org/ml/gcc/2002-01/msg00825.html), but, to the best of our
knowledge, it was never adopted there. However, the Bison team imported into
Bison and maintained it over the years, and later contributed it to gnulib.
