bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: A new module: bitset


From: Akim Demaille
Subject: Re: A new module: bitset
Date: Sun, 25 Nov 2018 19:55:36 +0100


> Le 25 nov. 2018 à 19:52, Akim Demaille <address@hidden> a écrit :
> 
>> Le 25 nov. 2018 à 18:54, Bruno Haible <address@hidden> a écrit :
>> 
>> Hi Akim,
>> 
>>>> * Regarding tests: There is a large amount of algorithmic code. While
>>>> the parts that Bison uses are surely correct, there is a possibility
>>>> of bugs in the more rarely used parts. I would find it very useful
>>>> to have unit tests of all 32 operations.
>>> 
>>> I definitely agree.  But I'd like to be incremental on this
>>> regard.
>> 
>> Sure. You can push it into gnulib, without having extensive tests.
> 
> Great!  I read this as an ok to push the current state, which takes
> into account your comments, but will most probably require more changes
> later.
> 
> First, the bitset module (without bitset vectors).

Then its test/doc.

commit 7c0d555aa341d7d5b8ab2fa8a94ee580636cc1c2
Author: Akim Demaille <address@hidden>
Date:   Sun Nov 25 09:49:09 2018 +0100

    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.

diff --git a/ChangeLog b/ChangeLog
index 9fae7910f..24bcccb44 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2018-11-25  Akim Demaille  <address@hidden>
+
+       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  <address@hidden>
 
        bitset: new module
diff --git a/doc/bitset.texi b/doc/bitset.texi
new file mode 100644
index 000000000..614961b95
--- /dev/null
+++ b/doc/bitset.texi
@@ -0,0 +1,63 @@
address@hidden Bitsets
address@hidden 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:
address@hidden @code
address@hidden BITSET_ARRAY
+Array of bits (fixed size, fast for dense bitsets). Memory for bit array
+and bitset structure allocated contiguously.
address@hidden BITSET_LIST
+Linked list of arrays of bits (variable size, least storage for large
+very sparse sets).
address@hidden 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.
address@hidden BITSET_VARRAY
+Variable array of bits (variable size, fast for dense bitsets).
address@hidden BITSET_STATS
+Wrapper bitset for internal use only.  Used for gathering statistics
+and/or better run-time checking.
address@hidden description
+
+However, the choice of the actual implementation is performed by the
+library, based on the user provided attributes:
+
address@hidden @code
address@hidden BITSET_FIXED
+Bitset size fixed.
address@hidden BITSET_VARIABLE
+Bitset size variable.
address@hidden BITSET_DENSE
+Bitset dense.
address@hidden BITSET_SPARSE
+Bitset sparse.
address@hidden BITSET_FRUGAL
+Prefer most compact.
address@hidden BITSET_GREEDY
+Prefer fastest at memory expense.
address@hidden description
+
+
address@hidden
+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);
address@hidden smallexample
diff --git a/modules/bitset-tests b/modules/bitset-tests
new file mode 100644
index 000000000..4a7b8b32b
--- /dev/null
+++ b/modules/bitset-tests
@@ -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
diff --git a/tests/test-bitset.c b/tests/test-bitset.c
new file mode 100644
index 000000000..b673d188c
--- /dev/null
+++ b/tests/test-bitset.c
@@ -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;
+}




reply via email to

[Prev in Thread] Current Thread [Next in Thread]