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

 
 
Latest News
GNU gnulib: calling for beta-testers posted by haible, Sun 21 Apr 2024 10:47:35 AM UTC
Gnulib helps you porting to Android posted by haible, Sat 15 Apr 2023 10:31:06 PM UTC
Gnulib helps you get away from fork() + exec() posted by haible, Sun 20 Nov 2022 04:27:43 PM UTC
Gnulib provides versatile bit-set implementations posted by akim, Wed 13 Jan 2021 12:17:37 PM UTC
Gnulib supports portable multithreading posted by haible, Wed 30 Dec 2020 03:10:08 PM UTC

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.

 

Back to the top

Powered by Savane 3.13-02a9.
Corresponding source code