Mercurial > gnulib

annotate doc/bitset.texi @ 40196:e63f5d3edab5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
relocatable-prog: Update documentation. * doc/relocatable-maint.texi (Supporting Relocation): Update to match the recent changes.
author Bruno Haible <bruno@clisp.org>
date Sun, 24 Feb 2019 01:49:15 +0100
parents 9d336a02bad8
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
39974
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
1 @node Bitsets
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
2 @section Bitsets
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
3
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
4 The module @samp{bitset} provides a common interface to several
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
5 implementations of bitsets. It also provides routines for vectors of bitsets.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
6
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
7 To look at an existing use, see GNU Bison.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
8
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
9 Currently it supports five flavours of bitsets:
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
10 @description @code
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
11 @item BITSET_ARRAY
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
12 Array of bits (fixed size, fast for dense bitsets). Memory for bit array
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
13 and bitset structure allocated contiguously.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
14 @item BITSET_LIST
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
15 Linked list of arrays of bits (variable size, least storage for large
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
16 very sparse sets).
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
17 @item BITSET_TABLE
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
18 Expandable table of pointers to arrays of bits (variable size, less
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
19 storage for large sparse sets). Faster than @code{BITSET_LIST} for
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
20 random access.
39978
9d336a02bad8 bitset: rename BITSET_VARRAY as BITSET_VECTOR
Akim Demaille <akim.demaille@gmail.com>
parents: 39974
diff changeset
21 @item BITSET_VECTOR
39974
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
22 Variable array of bits (variable size, fast for dense bitsets).
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
23 @item BITSET_STATS
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
24 Wrapper bitset for internal use only. Used for gathering statistics
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
25 and/or better run-time checking.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
26 @end description
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
27
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
28 However, the choice of the actual implementation is performed by the
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
29 library, based on the user provided attributes:
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
30
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
31 @description @code
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
32 @code BITSET_FIXED
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
33 Bitset size fixed.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
34 @code BITSET_VARIABLE
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
35 Bitset size variable.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
36 @code BITSET_DENSE
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
37 Bitset dense.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
38 @code BITSET_SPARSE
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
39 Bitset sparse.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
40 @code BITSET_FRUGAL
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
41 Prefer most compact.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
42 @code BITSET_GREEDY
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
43 Prefer fastest at memory expense.
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
44 @end description
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
45
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
46
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
47 @smallexample
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
48 enum { nbits = 32 };
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
49
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
50 bitset bs0 = bitset_create (nbits, BITSET_FIXED);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
51 bitset_set (bs1, 1);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
52 bitset_set (bs1, 3);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
53 bitset_set (bs1, 5);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
54
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
55 bitset bs1 = bitset_create (nbits, BITSET_FIXED);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
56 bitset_set (bs1, 0);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
57 bitset_set (bs1, 2);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
58 bitset_set (bs1, 4);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
59
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
60 bitset bs = bitset_create (nbits, BITSET_FIXED);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
61 bitset_or (bs, b1, b2);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
62 ASSERT (bitset_count (bs) == 6);
29a9f5317b0a bitset: add tests and doc
Akim Demaille <akim.demaille@gmail.com>
parents:
diff changeset
63 @end smallexample