gnulib - GNU portability library - News: Gnulib provides versatile bit-set implementations

Gnulib provides versatile bit-set implementations

Item posted by Akim Demaille <akim> on Wed 13 Jan 2021 12:17:37 PM UTC.

Gnulib features bitset, a module to support operations on 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 of `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, 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.