doc/bitset.texi

   1 @node Bitsets
   2 @section Bitsets
   3
   4 The module @samp{bitset} provides a common interface to several
   5 implementations of bitsets.  It also provides routines for vectors of bitsets.
   6
   7 To look at an existing use, see GNU Bison.
   8
   9 Currently it supports five flavours of bitsets:
  10 @description @code
  11 @item BITSET_ARRAY
  12 Array of bits (fixed size, fast for dense bitsets). Memory for bit array
  13 and bitset structure allocated contiguously.
  14 @item BITSET_LIST
  15 Linked list of arrays of bits (variable size, least storage for large
  16 very sparse sets).
  17 @item BITSET_TABLE
  18 Expandable table of pointers to arrays of bits (variable size, less
  19 storage for large sparse sets).  Faster than @code{BITSET_LIST} for
  20 random access.
  21 @item BITSET_VECTOR
  22 Variable array of bits (variable size, fast for dense bitsets).
  23 @item BITSET_STATS
  24 Wrapper bitset for internal use only.  Used for gathering statistics
  25 and/or better run-time checking.
  26 @end description
  27
  28 However, the choice of the actual implementation is performed by the
  29 library, based on the user provided attributes:
  30
  31 @description @code
  32 @code BITSET_FIXED
  33 Bitset size fixed.
  34 @code BITSET_VARIABLE
  35 Bitset size variable.
  36 @code BITSET_DENSE
  37 Bitset dense.
  38 @code BITSET_SPARSE
  39 Bitset sparse.
  40 @code BITSET_FRUGAL
  41 Prefer most compact.
  42 @code BITSET_GREEDY
  43 Prefer fastest at memory expense.
  44 @end description
  45
  46
  47 @smallexample
  48 enum { nbits = 32 };
  49
  50 bitset bs0 = bitset_create (nbits, BITSET_FIXED);
  51 bitset_set (bs0, 1);
  52 bitset_set (bs0, 3);
  53 bitset_set (bs0, 5);
  54
  55 bitset bs1 = bitset_create (nbits, BITSET_FIXED);
  56 bitset_set (bs1, 0);
  57 bitset_set (bs1, 2);
  58 bitset_set (bs1, 4);
  59
  60 bitset bs = bitset_create (nbits, BITSET_FIXED);
  61 bitset_or (bs, bs0, bs1);
  62 ASSERT (bitset_count (bs) == 6);
  63
  64 bitset_free (bs);
  65 bitset_free (bs1);
  66 bitset_free (bs0);
  67 @end smallexample