doc/bitset.texi

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