tests/test-bitset.c

   1 /* Test of bitset.
   2    Copyright (C) 2018-2020 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 #include <config.h>
  18
  19 #include "bitset.h"
  20
  21 #include "macros.h"
  22
  23 #define RANDOM(n) (rand () % (n))
  24
  25 static
  26 void assert_bitset_equal (bitset bs1, bitset bs2)
  27 {
  28   debug_bitset (bs1);
  29   debug_bitset (bs2);
  30   ASSERT (bitset_size (bs1) == bitset_size (bs2));
  31   for (bitset_bindex i = 0; i < bitset_size (bs1); ++i)
  32     ASSERT (bitset_test (bs1, i) == bitset_test (bs2, i));
  33 }
  34
  35 static
  36 void bitset_random (bitset bs)
  37 {
  38   for (bitset_bindex i = 0; i < bitset_size (bs); ++i)
  39     bitset_set (bs, RANDOM (2));
  40 }
  41
  42
  43 /* Check various operations on random bitsets with two different
  44    implementations.  */
  45
  46 static
  47 void compare (enum bitset_attr a, enum bitset_attr b)
  48 {
  49   const int nbits = RANDOM (256);
  50
  51   bitset asrc0 = bitset_create (nbits, a);
  52   bitset_random (asrc0);
  53   bitset asrc1 = bitset_create (nbits, a);
  54   bitset_random (asrc1);
  55   bitset asrc2 = bitset_create (nbits, a);
  56   bitset_random (asrc2);
  57   bitset asrc3 = bitset_create (nbits, a);
  58   bitset_random (asrc3);
  59   bitset adst = bitset_create (nbits, a);
  60
  61   bitset bsrc0 = bitset_create (nbits, b);
  62   bitset_copy (bsrc0, asrc0);
  63   bitset bsrc1 = bitset_create (nbits, b);
  64   bitset_copy (bsrc1, asrc1);
  65   bitset bsrc2 = bitset_create (nbits, b);
  66   bitset_copy (bsrc2, asrc2);
  67   bitset bsrc3 = bitset_create (nbits, b);
  68   bitset_copy (bsrc3, asrc3);
  69   bitset bdst = bitset_create (nbits, b);
  70
  71   /* not */
  72   bitset_not (adst, asrc0);
  73   bitset_not (bdst, bsrc0);
  74   assert_bitset_equal (adst, bdst);
  75
  76   /* and */
  77   bitset_and (adst, asrc0, asrc1);
  78   bitset_and (bdst, bsrc0, bsrc1);
  79   assert_bitset_equal (adst, bdst);
  80   ASSERT (bitset_and_cmp (adst, asrc0, asrc1)
  81           == bitset_and_cmp (bdst, bsrc0, bsrc1));
  82   assert_bitset_equal (adst, bdst);
  83
  84   /* andn */
  85   bitset_andn (adst, asrc0, asrc1);
  86   bitset_andn (bdst, bsrc0, bsrc1);
  87   assert_bitset_equal (adst, bdst);
  88   ASSERT (bitset_andn_cmp (adst, asrc0, asrc1)
  89           == bitset_andn_cmp (bdst, bsrc0, bsrc1));
  90   assert_bitset_equal (adst, bdst);
  91
  92   /* or */
  93   bitset_or (adst, asrc0, asrc1);
  94   bitset_or (bdst, bsrc0, bsrc1);
  95   assert_bitset_equal (adst, bdst);
  96   ASSERT (bitset_or_cmp (adst, asrc0, asrc1)
  97           == bitset_or_cmp (bdst, bsrc0, bsrc1));
  98   assert_bitset_equal (adst, bdst);
  99
 100   /* xor */
 101   bitset_xor (adst, asrc0, asrc1);
 102   bitset_xor (bdst, bsrc0, bsrc1);
 103   assert_bitset_equal (adst, bdst);
 104   ASSERT (bitset_xor_cmp (adst, asrc0, asrc1)
 105           == bitset_xor_cmp (bdst, bsrc0, bsrc1));
 106   assert_bitset_equal (adst, bdst);
 107
 108   /* and_or */
 109   bitset_and_or (adst, asrc0, asrc1, asrc2);
 110   bitset_and_or (bdst, bsrc0, bsrc1, bsrc2);
 111   assert_bitset_equal (adst, bdst);
 112   ASSERT (bitset_and_or_cmp (adst, asrc0, asrc1, asrc2)
 113           == bitset_and_or_cmp (bdst, bsrc0, bsrc1, bsrc2));
 114   assert_bitset_equal (adst, bdst);
 115
 116   /* andn_or */
 117   bitset_andn_or (adst, asrc0, asrc1, asrc2);
 118   bitset_andn_or (bdst, bsrc0, bsrc1, bsrc2);
 119   assert_bitset_equal (adst, bdst);
 120   ASSERT (bitset_andn_or_cmp (adst, asrc0, asrc1, asrc2)
 121           == bitset_andn_or_cmp (bdst, bsrc0, bsrc1, bsrc2));
 122   assert_bitset_equal (adst, bdst);
 123
 124   /* or_and */
 125   bitset_or_and (adst, asrc0, asrc1, asrc2);
 126   bitset_or_and (bdst, bsrc0, bsrc1, bsrc2);
 127   assert_bitset_equal (adst, bdst);
 128   ASSERT (bitset_or_and_cmp (adst, asrc0, asrc1, asrc2)
 129           == bitset_or_and_cmp (bdst, bsrc0, bsrc1, bsrc2));
 130   assert_bitset_equal (adst, bdst);
 131
 132   /* ones */
 133   bitset_ones (adst);
 134   bitset_ones (bdst);
 135   assert_bitset_equal (adst, bdst);
 136
 137   /* zero */
 138   bitset_zero (adst);
 139   bitset_zero (bdst);
 140   assert_bitset_equal (adst, bdst);
 141
 142   /* resize.
 143
 144      ARRAY bitsets cannot be resized.  */
 145   if (bitset_type_get (bsrc0) != BITSET_ARRAY)
 146     {
 147       const int nbits_new = RANDOM (256);
 148       bitset_copy (adst, asrc0);
 149       bitset_copy (bdst, bsrc0);
 150       ASSERT (nbits_new == bitset_resize (adst, nbits_new));
 151       ASSERT (nbits_new == bitset_resize (bdst, nbits_new));
 152       assert_bitset_equal (adst, bdst);
 153     }
 154
 155   bitset_free (bdst);
 156   bitset_free (bsrc3);
 157   bitset_free (bsrc2);
 158   bitset_free (bsrc1);
 159   bitset_free (bsrc0);
 160   bitset_free (adst);
 161   bitset_free (asrc3);
 162   bitset_free (asrc2);
 163   bitset_free (asrc1);
 164   bitset_free (asrc0);
 165 }
 166
 167
 168 /* Check various operations against expected values for a bitset
 169    having attributes ATTR.  */
 170
 171 static
 172 void check_attributes (enum bitset_attr attr)
 173 {
 174   enum { nbits = 32 };
 175
 176   bitset bs0 = bitset_create (nbits, attr);
 177   ASSERT (bitset_size (bs0) == 32);
 178   ASSERT (bitset_count (bs0) == 0);
 179   ASSERT (bitset_empty_p (bs0));
 180
 181   bitset bs1 = bitset_create (nbits, attr);
 182   bitset_set (bs1, 1);
 183   bitset_set (bs1, 3);
 184   bitset_set (bs1, 5);
 185   ASSERT (bitset_count (bs1) == 3);
 186   ASSERT (!bitset_empty_p (bs1));
 187
 188   bitset bs2 = bitset_create (nbits, attr);
 189   bitset_set (bs2, 0);
 190   bitset_set (bs2, 2);
 191   bitset_set (bs2, 4);
 192
 193   /* disjoint_p */
 194   ASSERT (bitset_disjoint_p (bs1, bs2));
 195
 196   /* and */
 197   bitset bs = bitset_create (nbits, attr);
 198   bitset_and (bs, bs1, bs2);
 199   ASSERT (bitset_count (bs) == 0);
 200
 201   /* or */
 202   bitset_or (bs, bs1, bs2);
 203   ASSERT (bitset_count (bs) == 6);
 204
 205   bitset_free (bs);
 206   bitset_free (bs2);
 207   bitset_free (bs1);
 208   bitset_free (bs0);
 209 }
 210
 211 int main (void)
 212 {
 213   check_attributes (BITSET_FIXED);
 214   check_attributes (BITSET_VARIABLE);
 215   check_attributes (BITSET_DENSE);
 216   check_attributes (BITSET_SPARSE);
 217   check_attributes (BITSET_FRUGAL);
 218   check_attributes (BITSET_GREEDY);
 219
 220   compare (BITSET_VARIABLE, BITSET_FIXED);
 221   compare (BITSET_VARIABLE, BITSET_VARIABLE);
 222   compare (BITSET_VARIABLE, BITSET_DENSE);
 223   compare (BITSET_VARIABLE, BITSET_SPARSE);
 224   compare (BITSET_VARIABLE, BITSET_FRUGAL);
 225   compare (BITSET_VARIABLE, BITSET_GREEDY);
 226   return 0;
 227 }