tests/test-bitset.c

   1 /* Test of bitset.
   2    Copyright (C) 2018-2024 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 void
  26 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 void
  36 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 void
  47 compare (enum bitset_attr a, enum bitset_attr b)
  48 {
  49   /* bitset_list (used in many operations) uses a cache whose size is
  50      BITSET_LIST_SIZE */
  51   const int nbits = RANDOM (2 * BITSET_LIST_SIZE);
  52
  53   /* Four read only random initial values of type A.  */
  54   const bitset asrc0 = bitset_create (nbits, a);
  55   bitset_random (asrc0);
  56   const bitset asrc1 = bitset_create (nbits, a);
  57   bitset_random (asrc1);
  58   const bitset asrc2 = bitset_create (nbits, a);
  59   bitset_random (asrc2);
  60   const bitset asrc3 = bitset_create (nbits, a);
  61   bitset_random (asrc3);
  62
  63   /* Four read only values of type B, equal to the values of type A. */
  64   const bitset bsrc0 = bitset_create (nbits, b);
  65   bitset_copy (bsrc0, asrc0);
  66   const bitset bsrc1 = bitset_create (nbits, b);
  67   bitset_copy (bsrc1, asrc1);
  68   const bitset bsrc2 = bitset_create (nbits, b);
  69   bitset_copy (bsrc2, asrc2);
  70   const bitset bsrc3 = bitset_create (nbits, b);
  71   bitset_copy (bsrc3, asrc3);
  72
  73   /* Destinations for each operation.  */
  74   bitset adst = bitset_create (nbits, a);
  75   bitset bdst = bitset_create (nbits, b);
  76
  77   /* count */
  78   ASSERT (bitset_count (asrc0) == bitset_count (bsrc0));
  79
  80   /* not */
  81   bitset_not (adst, asrc0);
  82   bitset_not (bdst, bsrc0);
  83   assert_bitset_equal (adst, bdst);
  84
  85   /* and */
  86   bitset_and (adst, asrc0, asrc1);
  87   bitset_and (bdst, bsrc0, bsrc1);
  88   assert_bitset_equal (adst, bdst);
  89   ASSERT (bitset_and_cmp (adst, asrc0, asrc1)
  90           == bitset_and_cmp (bdst, bsrc0, bsrc1));
  91   assert_bitset_equal (adst, bdst);
  92
  93   /* andn */
  94   bitset_andn (adst, asrc0, asrc1);
  95   bitset_andn (bdst, bsrc0, bsrc1);
  96   assert_bitset_equal (adst, bdst);
  97   ASSERT (bitset_andn_cmp (adst, asrc0, asrc1)
  98           == bitset_andn_cmp (bdst, bsrc0, bsrc1));
  99   assert_bitset_equal (adst, bdst);
 100
 101   /* or */
 102   bitset_or (adst, asrc0, asrc1);
 103   bitset_or (bdst, bsrc0, bsrc1);
 104   assert_bitset_equal (adst, bdst);
 105   ASSERT (bitset_or_cmp (adst, asrc0, asrc1)
 106           == bitset_or_cmp (bdst, bsrc0, bsrc1));
 107   assert_bitset_equal (adst, bdst);
 108
 109   /* xor */
 110   bitset_xor (adst, asrc0, asrc1);
 111   bitset_xor (bdst, bsrc0, bsrc1);
 112   assert_bitset_equal (adst, bdst);
 113   ASSERT (bitset_xor_cmp (adst, asrc0, asrc1)
 114           == bitset_xor_cmp (bdst, bsrc0, bsrc1));
 115   assert_bitset_equal (adst, bdst);
 116
 117   /* and_or */
 118   bitset_and_or (adst, asrc0, asrc1, asrc2);
 119   bitset_and_or (bdst, bsrc0, bsrc1, bsrc2);
 120   assert_bitset_equal (adst, bdst);
 121   ASSERT (bitset_and_or_cmp (adst, asrc0, asrc1, asrc2)
 122           == bitset_and_or_cmp (bdst, bsrc0, bsrc1, bsrc2));
 123   assert_bitset_equal (adst, bdst);
 124
 125   /* andn_or */
 126   bitset_andn_or (adst, asrc0, asrc1, asrc2);
 127   bitset_andn_or (bdst, bsrc0, bsrc1, bsrc2);
 128   assert_bitset_equal (adst, bdst);
 129   ASSERT (bitset_andn_or_cmp (adst, asrc0, asrc1, asrc2)
 130           == bitset_andn_or_cmp (bdst, bsrc0, bsrc1, bsrc2));
 131   assert_bitset_equal (adst, bdst);
 132
 133   /* or_and */
 134   bitset_or_and (adst, asrc0, asrc1, asrc2);
 135   bitset_or_and (bdst, bsrc0, bsrc1, bsrc2);
 136   assert_bitset_equal (adst, bdst);
 137   ASSERT (bitset_or_and_cmp (adst, asrc0, asrc1, asrc2)
 138           == bitset_or_and_cmp (bdst, bsrc0, bsrc1, bsrc2));
 139   assert_bitset_equal (adst, bdst);
 140
 141   /* ones */
 142   bitset_ones (adst);
 143   bitset_ones (bdst);
 144   assert_bitset_equal (adst, bdst);
 145
 146   /* zero */
 147   bitset_zero (adst);
 148   bitset_zero (bdst);
 149   assert_bitset_equal (adst, bdst);
 150
 151   /* first and last and FOR_EACH.  */
 152   /* Work on bdst to exercise all the bitset types (adst is
 153      BITSET_VARIABLE).  */
 154   bitset_copy (bdst, bsrc0);
 155   debug_bitset (bdst);
 156   debug_bitset (bsrc0);
 157   bitset_copy (adst, bdst);
 158
 159   /* count. */
 160   ASSERT (bitset_count (adst) == bitset_count (bdst));
 161
 162   /* first and last */
 163   {
 164     bitset_bindex first = bitset_first (adst);
 165     ASSERT (first == bitset_first (bdst));
 166
 167     bitset_bindex last  = bitset_last (adst);
 168     ASSERT (last == bitset_last (bdst));
 169
 170     ASSERT (first <= last);
 171   }
 172
 173
 174   /* FOR_EACH.  */
 175   {
 176     bitset_iterator iter;
 177     bitset_bindex j;
 178     bitset_bindex first = bitset_first (bdst);
 179     bitset_bindex last  = bitset_last (bdst);
 180     bool seen_first = false;
 181     bool seen_last = false;
 182     BITSET_FOR_EACH (iter, bdst, j, 0)
 183       {
 184         ASSERT (first <= j && j <= last);
 185         ASSERT (bitset_test (bdst, j));
 186         if (j == first)
 187           seen_first = true;
 188         if (j == last)
 189           seen_last = true;
 190       }
 191     if (first == BITSET_BINDEX_MAX)
 192       {
 193         ASSERT (!seen_first);
 194         ASSERT (!seen_last);
 195       }
 196     else
 197       {
 198         ASSERT (seen_first);
 199         ASSERT (seen_last);
 200       }
 201   }
 202
 203   /* FOR_EACH_REVERSE.  */
 204   {
 205     bitset_iterator iter;
 206     bitset_bindex j;
 207     bitset_bindex first = bitset_first (bdst);
 208     bitset_bindex last  = bitset_last (bdst);
 209     bool seen_first = false;
 210     bool seen_last = false;
 211     BITSET_FOR_EACH_REVERSE (iter, bdst, j, 0)
 212       {
 213         ASSERT (first <= j && j <= last);
 214         ASSERT (bitset_test (bdst, j));
 215         if (j == first)
 216           seen_first = true;
 217         if (j == last)
 218           seen_last = true;
 219       }
 220     if (first == BITSET_BINDEX_MAX)
 221       {
 222         ASSERT (!seen_first);
 223         ASSERT (!seen_last);
 224       }
 225     else
 226       {
 227         ASSERT (seen_first);
 228         ASSERT (seen_last);
 229       }
 230   }
 231
 232
 233   /* resize.
 234
 235      ARRAY bitsets cannot be resized.  */
 236   if (bitset_type_get (bsrc0) != BITSET_ARRAY)
 237     {
 238       const int nbits_new = RANDOM (256);
 239       bitset_copy (adst, asrc0);
 240       bitset_copy (bdst, bsrc0);
 241       ASSERT (nbits_new == bitset_resize (adst, nbits_new));
 242       ASSERT (nbits_new == bitset_resize (bdst, nbits_new));
 243       assert_bitset_equal (adst, bdst);
 244     }
 245
 246   bitset_free (bdst);
 247   bitset_free (bsrc3);
 248   bitset_free (bsrc2);
 249   bitset_free (bsrc1);
 250   bitset_free (bsrc0);
 251   bitset_free (adst);
 252   bitset_free (asrc3);
 253   bitset_free (asrc2);
 254   bitset_free (asrc1);
 255   bitset_free (asrc0);
 256 }
 257
 258
 259 /* Check empty bitsets.  */
 260
 261 static void
 262 check_zero (bitset bs)
 263 {
 264   fprintf (stderr, "check_zero\n");
 265   bitset_zero (bs);
 266
 267   /* count. */
 268   ASSERT (bitset_count (bs) == 0);
 269
 270   /* first and last */
 271   ASSERT (bitset_first (bs) == BITSET_BINDEX_MAX);
 272   ASSERT (bitset_last (bs)  == BITSET_BINDEX_MAX);
 273
 274   /* FOR_EACH.  */
 275   {
 276     bitset_iterator iter;
 277     _GL_UNUSED bitset_bindex i;
 278     BITSET_FOR_EACH (iter, bs, i, 0)
 279       ASSERT (0);
 280     BITSET_FOR_EACH_REVERSE (iter, bs, i, 0)
 281       ASSERT (0);
 282   }
 283 }
 284
 285 /* Exercise on a single-bit values: it's easy to get the handling of
 286    the most significant bit wrong.  */
 287
 288 static void
 289 check_one_bit (bitset bs, int bitno)
 290 {
 291   fprintf (stderr, "check_one_bit(%d)\n", bitno);
 292   bitset_zero (bs);
 293   bitset_set (bs, bitno);
 294
 295   /* count. */
 296   ASSERT (bitset_count (bs) == 1);
 297
 298   /* test. */
 299   ASSERT (bitset_test (bs, bitno));
 300
 301   /* first and last */
 302   ASSERT (bitset_first (bs) == bitno);
 303   ASSERT (bitset_last (bs) == bitno);
 304
 305   /* FOR_EACH.  */
 306   {
 307     bitset_iterator iter;
 308     bitset_bindex i;
 309     BITSET_FOR_EACH (iter, bs, i, 0)
 310       ASSERT (i == bitno);
 311
 312     BITSET_FOR_EACH_REVERSE (iter, bs, i, 0)
 313       ASSERT (i == bitno);
 314   }
 315 }
 316
 317 /* Check full bitsets.  */
 318
 319 static void
 320 check_ones (bitset bs)
 321 {
 322   fprintf (stderr, "check_ones\n");
 323   const bitset_bindex size = bitset_size (bs);
 324
 325   bitset_ones (bs);
 326   debug_bitset (bs);
 327
 328   /* count. */
 329   ASSERT (bitset_count (bs) == size);
 330
 331   /* first and last */
 332   ASSERT (bitset_first (bs) == 0);
 333   ASSERT (bitset_last (bs)  == size - 1);
 334
 335   /* FOR_EACH.  */
 336   {
 337     bitset_iterator iter;
 338     bitset_bindex i;
 339     bitset_bindex count = 0;
 340     BITSET_FOR_EACH (iter, bs, i, 0)
 341       ASSERT (i == count++);
 342     ASSERT (count == size);
 343     BITSET_FOR_EACH_REVERSE (iter, bs, i, 0)
 344       ASSERT (i == --count);
 345     ASSERT (count == 0);
 346   }
 347 }
 348
 349 /* Check various operations against expected values for a bitset
 350    having attributes ATTR.  */
 351
 352 static void
 353 check_attributes (enum bitset_attr attr, int nbits)
 354 {
 355   bitset bs0 = bitset_create (nbits, attr);
 356   ASSERT (bitset_size (bs0) == nbits);
 357   ASSERT (bitset_count (bs0) == 0);
 358   ASSERT (bitset_empty_p (bs0));
 359
 360   bitset bs1 = bitset_create (nbits, attr);
 361   bitset_set (bs1, 1);
 362   bitset_set (bs1, 3);
 363   bitset_set (bs1, 5);
 364   ASSERT (bitset_count (bs1) == 3);
 365   ASSERT (!bitset_empty_p (bs1));
 366
 367   bitset bs2 = bitset_create (nbits, attr);
 368   bitset_set (bs2, 0);
 369   bitset_set (bs2, 2);
 370   bitset_set (bs2, 4);
 371
 372   /* disjoint_p */
 373   ASSERT (bitset_disjoint_p (bs1, bs2));
 374
 375   /* and */
 376   bitset bs = bitset_create (nbits, attr);
 377   bitset_and (bs, bs1, bs2);
 378   ASSERT (bitset_count (bs) == 0);
 379
 380   /* or */
 381   bitset_or (bs, bs1, bs2);
 382   ASSERT (bitset_count (bs) == 6);
 383
 384   check_zero (bs);
 385   check_ones (bs);
 386
 387   /* Exercise on all the single-bit values: it's easy to get the
 388      handling of the most significant bit wrong.  */
 389   for (int bitno = 0; bitno < nbits; ++bitno)
 390     check_one_bit (bs, bitno);
 391
 392   bitset_free (bs);
 393   bitset_free (bs2);
 394   bitset_free (bs1);
 395   bitset_free (bs0);
 396 }
 397
 398 int main (void)
 399 {
 400   bitset_stats_enable ();
 401
 402   for (int i = 0; i < 4; ++i)
 403     {
 404       /* table bitsets have elements that store 256 bits.  bitset_list
 405          (used in many operations) uses a cache whose size is
 406          BITSET_LIST_SIZE.  */
 407       int nbits =
 408         i == 0   ? 1
 409         : i == 1 ? 32
 410         : i == 2 ? 257
 411         :          (BITSET_LIST_SIZE + 1);
 412       check_attributes (BITSET_FIXED,    nbits);
 413       check_attributes (BITSET_VARIABLE, nbits);
 414       check_attributes (BITSET_DENSE,    nbits);
 415       check_attributes (BITSET_SPARSE,   nbits);
 416       check_attributes (BITSET_FRUGAL,   nbits);
 417       check_attributes (BITSET_GREEDY,   nbits);
 418     }
 419
 420   compare (BITSET_VARIABLE, BITSET_FIXED);
 421   compare (BITSET_VARIABLE, BITSET_VARIABLE);
 422   compare (BITSET_VARIABLE, BITSET_DENSE);
 423   compare (BITSET_VARIABLE, BITSET_SPARSE);
 424   compare (BITSET_VARIABLE, BITSET_FRUGAL);
 425   compare (BITSET_VARIABLE, BITSET_GREEDY);
 426
 427   bitset_stats_dump (stderr);
 428   return test_exit_status;
 429 }