Mercurial > gnulib
changeset 39974:29a9f5317b0a
bitset: add tests and doc
First stabs at providing a documentation and test for the bitset
module.
* doc/bitset.texi, modules/test-bitset, tests/bitset-tests.c: New.
author | Akim Demaille <akim.demaille@gmail.com> |
---|---|
date | Sun, 25 Nov 2018 09:49:09 +0100 |
parents | 12c0d1c1c28a |
children | 90954bfe8d66 |
files | ChangeLog doc/bitset.texi modules/bitset-tests tests/test-bitset.c |
diffstat | 4 files changed, 147 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog Sun Oct 28 17:32:15 2018 +0100 +++ b/ChangeLog Sun Nov 25 09:49:09 2018 +0100 @@ -1,3 +1,10 @@ +2018-11-25 Akim Demaille <akim@lrde.epita.fr> + + bitset: add tests and doc + First stabs at providing a documentation and test for the bitset + module. + * doc/bitset.texi, modules/test-bitset, tests/bitset-tests.c: New. + 2018-11-25 Akim Demaille <akim@lrde.epita.fr> bitset: new module
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/bitset.texi Sun Nov 25 09:49:09 2018 +0100 @@ -0,0 +1,63 @@ +@node Bitsets +@section Bitsets + +The module @samp{bitset} provides a common interface to several +implementations of bitsets. It also provides routines for vectors of bitsets. + +To look at an existing use, see GNU Bison. + +Currently it supports five flavours of bitsets: +@description @code +@item BITSET_ARRAY +Array of bits (fixed size, fast for dense bitsets). Memory for bit array +and bitset structure allocated contiguously. +@item BITSET_LIST +Linked list of arrays of bits (variable size, least storage for large +very sparse sets). +@item BITSET_TABLE +Expandable table of pointers to arrays of bits (variable size, less +storage for large sparse sets). Faster than @code{BITSET_LIST} for +random access. +@item BITSET_VARRAY +Variable array of bits (variable size, fast for dense bitsets). +@item BITSET_STATS +Wrapper bitset for internal use only. Used for gathering statistics +and/or better run-time checking. +@end description + +However, the choice of the actual implementation is performed by the +library, based on the user provided attributes: + +@description @code +@code BITSET_FIXED +Bitset size fixed. +@code BITSET_VARIABLE +Bitset size variable. +@code BITSET_DENSE +Bitset dense. +@code BITSET_SPARSE +Bitset sparse. +@code BITSET_FRUGAL +Prefer most compact. +@code BITSET_GREEDY +Prefer fastest at memory expense. +@end description + + +@smallexample +enum { nbits = 32 }; + +bitset bs0 = bitset_create (nbits, BITSET_FIXED); +bitset_set (bs1, 1); +bitset_set (bs1, 3); +bitset_set (bs1, 5); + +bitset bs1 = bitset_create (nbits, BITSET_FIXED); +bitset_set (bs1, 0); +bitset_set (bs1, 2); +bitset_set (bs1, 4); + +bitset bs = bitset_create (nbits, BITSET_FIXED); +bitset_or (bs, b1, b2); +ASSERT (bitset_count (bs) == 6); +@end smallexample
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/modules/bitset-tests Sun Nov 25 09:49:09 2018 +0100 @@ -0,0 +1,11 @@ +Files: +tests/test-bitset.c +tests/macros.h + +Depends-on: + +configure.ac: + +Makefile.am: +TESTS += test-bitset +check_PROGRAMS += test-bitset
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/test-bitset.c Sun Nov 25 09:49:09 2018 +0100 @@ -0,0 +1,66 @@ +/* Test of bitset. + Copyright (C) 2018 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +#include "bitset.h" + +#include "macros.h" + +void check_attributes (enum bitset_attr attr) +{ + enum { nbits = 32 }; + + bitset bs0 = bitset_create (nbits, attr); + ASSERT (bitset_size (bs0) == 32); + ASSERT (bitset_count (bs0) == 0); + ASSERT (bitset_empty_p (bs0)); + + bitset bs1 = bitset_create (nbits, attr); + bitset_set (bs1, 1); + bitset_set (bs1, 3); + bitset_set (bs1, 5); + ASSERT (bitset_count (bs1) == 3); + ASSERT (!bitset_empty_p (bs1)); + + bitset bs2 = bitset_create (nbits, attr); + bitset_set (bs2, 0); + bitset_set (bs2, 2); + bitset_set (bs2, 4); + + /* disjoint_p */ + ASSERT (bitset_disjoint_p (bs1, bs2)); + + /* and */ + bitset bs = bitset_create (nbits, attr); + bitset_and (bs, bs1, bs2); + ASSERT (bitset_count (bs) == 0); + + /* or */ + bitset_or (bs, bs1, bs2); + ASSERT (bitset_count (bs) == 6); +} + +int main (void) +{ + check_attributes (BITSET_FIXED); + check_attributes (BITSET_VARIABLE); + check_attributes (BITSET_DENSE); + check_attributes (BITSET_SPARSE); + check_attributes (BITSET_FRUGAL); + check_attributes (BITSET_GREEDY); + return 0; +}