lib/bitset.c

   1 /* General bitsets.
   2
   3    Copyright (C) 2002-2006, 2009-2015, 2018-2020 Free Software Foundation, Inc.
   4
   5    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
   6
   7    This program is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  19
  20 #include <config.h>
  21
  22 #include "bitset.h"
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #include "obstack.h"
  28
  29 #include "bitset/array.h"
  30 #include "bitset/list.h"
  31 #include "bitset/stats.h"
  32 #include "bitset/table.h"
  33 #include "bitset/vector.h"
  34
  35 const char * const bitset_type_names[] = BITSET_TYPE_NAMES;
  36
  37
  38 /* Return number of bytes required to create a N_BIT bitset
  39    of TYPE.  The bitset may grow to require more bytes than this.  */
  40 size_t
  41 bitset_bytes (enum bitset_type type, bitset_bindex n_bits)
  42 {
  43   if (bitset_stats_enabled)
  44     return bitset_stats_bytes ();
  45
  46   switch (type)
  47     {
  48     default:
  49       abort ();
  50
  51     case BITSET_ARRAY:
  52       return abitset_bytes (n_bits);
  53
  54     case BITSET_LIST:
  55       return lbitset_bytes (n_bits);
  56
  57     case BITSET_TABLE:
  58       return tbitset_bytes (n_bits);
  59
  60     case BITSET_VECTOR:
  61       return vbitset_bytes (n_bits);
  62     }
  63 }
  64
  65
  66 /* Initialise bitset BSET of TYPE for N_BITS.  */
  67 bitset
  68 bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
  69 {
  70   if (bitset_stats_enabled)
  71     return bitset_stats_init (bset, n_bits, type);
  72
  73   switch (type)
  74     {
  75     default:
  76       abort ();
  77
  78     case BITSET_ARRAY:
  79       return abitset_init (bset, n_bits);
  80
  81     case BITSET_LIST:
  82       return lbitset_init (bset, n_bits);
  83
  84     case BITSET_TABLE:
  85       return tbitset_init (bset, n_bits);
  86
  87     case BITSET_VECTOR:
  88       return vbitset_init (bset, n_bits);
  89     }
  90 }
  91
  92
  93 /* Select a bitset type for a set of N_BITS and with attribute hints
  94    specified by ATTR.  For variable size bitsets, N_BITS is only a
  95    hint and may be zero.  */
  96 enum bitset_type
  97 bitset_type_choose (bitset_bindex n_bits MAYBE_UNUSED, unsigned attr)
  98 {
  99   /* Check attributes.  */
 100   if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
 101     abort ();
 102   if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
 103     abort ();
 104
 105   /* Choose the type of bitset.  Note that sometimes we will be asked
 106   for a zero length fixed size bitset.  */
 107
 108
 109   /* If no attributes selected, choose a good compromise.  */
 110   if (!attr)
 111     return BITSET_VECTOR;
 112
 113   if (attr & BITSET_SPARSE)
 114     return BITSET_LIST;
 115
 116   if (attr & BITSET_FIXED)
 117     return BITSET_ARRAY;
 118
 119   if (attr & BITSET_GREEDY)
 120     return BITSET_TABLE;
 121
 122   return BITSET_VECTOR;
 123 }
 124
 125
 126 /* Create a bitset of N_BITS of type TYPE.  */
 127 bitset
 128 bitset_alloc (bitset_bindex n_bits, enum bitset_type type)
 129 {
 130   size_t bytes = bitset_bytes (type, n_bits);
 131
 132   bitset bset = xzalloc (bytes);
 133
 134   /* The cache is disabled until some elements are allocated.  If we
 135      have variable length arrays, then we may need to allocate a dummy
 136      element.  */
 137
 138   return bitset_init (bset, n_bits, type);
 139 }
 140
 141
 142 /* Create a bitset of N_BITS of type TYPE.  */
 143 bitset
 144 bitset_obstack_alloc (struct obstack *bobstack,
 145                       bitset_bindex n_bits, enum bitset_type type)
 146 {
 147   size_t bytes = bitset_bytes (type, n_bits);
 148
 149   bitset bset = obstack_alloc (bobstack, bytes);
 150   memset (bset, 0, bytes);
 151
 152   return bitset_init (bset, n_bits, type);
 153 }
 154
 155
 156 /* Create a bitset of N_BITS and with attribute hints specified by
 157    ATTR.  */
 158 bitset
 159 bitset_create (bitset_bindex n_bits, unsigned attr)
 160 {
 161   enum bitset_type type = bitset_type_choose (n_bits, attr);
 162
 163   return bitset_alloc (n_bits, type);
 164 }
 165
 166
 167 /* Free bitset BSET.  */
 168 void
 169 bitset_free (bitset bset)
 170 {
 171   if (bset)
 172     {
 173       BITSET_FREE_ (bset);
 174       free (bset);
 175     }
 176 }
 177
 178
 179 /* Free bitset BSET allocated on obstack.  */
 180 void
 181 bitset_obstack_free (bitset bset)
 182 {
 183   if (bset)
 184     BITSET_FREE_ (bset);
 185 }
 186
 187
 188 /* Return bitset type.  */
 189 enum bitset_type
 190 bitset_type_get (bitset bset)
 191 {
 192    enum bitset_type type = BITSET_TYPE_ (bset);
 193    if (type != BITSET_STATS)
 194      return type;
 195
 196    return bitset_stats_type_get (bset);
 197 }
 198
 199
 200 /* Return name of bitset type.  */
 201 const char *
 202 bitset_type_name_get (bitset bset)
 203 {
 204   enum bitset_type type = bitset_type_get (bset);
 205
 206   return bitset_type_names[type];
 207 }
 208
 209
 210 /* Find next bit set in SRC starting from and including BITNO.
 211    Return BITSET_BINDEX_MAX if SRC empty.  */
 212 bitset_bindex
 213 bitset_next (bitset src, bitset_bindex bitno)
 214 {
 215   bitset_bindex next = bitno;
 216   bitset_bindex val;
 217   if (!bitset_list (src, &val, 1, &next))
 218     return BITSET_BINDEX_MAX;
 219   return val;
 220 }
 221
 222
 223 /* Return true if both bitsets are of the same type and size.  */
 224 extern bool
 225 bitset_compatible_p (bitset bset1, bitset bset2)
 226 {
 227   return BITSET_COMPATIBLE_ (bset1, bset2);
 228 }
 229
 230
 231 /* Find previous bit set in SRC starting from and including BITNO.
 232    Return BITSET_BINDEX_MAX if SRC empty.  */
 233 bitset_bindex
 234 bitset_prev (bitset src, bitset_bindex bitno)
 235 {
 236   bitset_bindex next = bitno;
 237   bitset_bindex val;
 238   if (!bitset_list_reverse (src, &val, 1, &next))
 239     return BITSET_BINDEX_MAX;
 240   return val;
 241 }
 242
 243
 244 /* Find first set bit.   */
 245 bitset_bindex
 246 bitset_first (bitset src)
 247 {
 248   return bitset_next (src, 0);
 249 }
 250
 251
 252 /* Find last set bit.   */
 253 bitset_bindex
 254 bitset_last (bitset src)
 255 {
 256   return bitset_prev (src, 0);
 257 }
 258
 259
 260 /* Is BITNO in SRC the only set bit?  */
 261 bool
 262 bitset_only_set_p (bitset src, bitset_bindex bitno)
 263 {
 264   bitset_bindex val[2];
 265   bitset_bindex next = 0;
 266
 267   if (bitset_list (src, val, 2, &next) != 1)
 268     return false;
 269   return val[0] == bitno;
 270 }
 271
 272
 273 /* Print contents of bitset BSET to FILE.   */
 274 static void
 275 bitset_print (FILE *file, bitset bset, bool verbose)
 276 {
 277   if (verbose)
 278     fprintf (file, "n_bits = %lu, set = {",
 279              (unsigned long) bitset_size (bset));
 280
 281   unsigned pos = 30;
 282   bitset_bindex i;
 283   bitset_iterator iter;
 284   BITSET_FOR_EACH (iter, bset, i, 0)
 285   {
 286     if (pos > 70)
 287       {
 288         fprintf (file, "\n");
 289         pos = 0;
 290       }
 291
 292     fprintf (file, "%lu ", (unsigned long) i);
 293     pos += 1 + (i >= 10) + (i >= 100);
 294   }
 295
 296   if (verbose)
 297     fprintf (file, "}\n");
 298 }
 299
 300
 301 /* Dump bitset BSET to FILE.  */
 302 void
 303 bitset_dump (FILE *file, bitset bset)
 304 {
 305   bitset_print (file, bset, false);
 306 }
 307
 308
 309 /* Release memory associated with bitsets.  */
 310 void
 311 bitset_release_memory (void)
 312 {
 313   lbitset_release_memory ();
 314   tbitset_release_memory ();
 315 }
 316
 317
 318 /* Toggle bit BITNO in bitset BSET and the new value of the bit.  */
 319 bool
 320 bitset_toggle_ (bitset bset, bitset_bindex bitno)
 321 {
 322   /* This routine is for completeness.  It could be optimized if
 323      required.  */
 324   if (bitset_test (bset, bitno))
 325     {
 326       bitset_reset (bset, bitno);
 327       return false;
 328     }
 329   else
 330     {
 331       bitset_set (bset, bitno);
 332       return true;
 333     }
 334 }
 335
 336
 337 /* Return number of bits in bitset SRC.  */
 338 bitset_bindex
 339 bitset_size_ (bitset src)
 340 {
 341   return BITSET_NBITS_ (src);
 342 }
 343
 344
 345 /* Return number of bits set in bitset SRC.  */
 346 bitset_bindex
 347 bitset_count_ (bitset src)
 348 {
 349   bitset_bindex list[BITSET_LIST_SIZE];
 350   bitset_bindex count = 0;
 351
 352   /* This could be greatly sped up by adding a count method for each
 353      bitset implementation that uses a direct technique (based on
 354      masks) for counting the number of bits set in a word.  */
 355
 356   {
 357     bitset_bindex next = 0;
 358     bitset_bindex num;
 359     while ((num = bitset_list (src, list, BITSET_LIST_SIZE, &next)))
 360       count += num;
 361   }
 362
 363   return count;
 364 }
 365
 366
 367 /* DST = SRC.  Return true if DST != SRC.
 368    This is a fallback for the case where SRC and DST are different
 369    bitset types.  */
 370 bool
 371 bitset_copy_ (bitset dst, bitset src)
 372 {
 373   bitset_bindex i;
 374   bitset_iterator iter;
 375
 376   /* Convert bitset types.  We assume that the DST bitset
 377      is large enough to hold the SRC bitset.  */
 378   bitset_zero (dst);
 379   BITSET_FOR_EACH (iter, src, i, 0)
 380     bitset_set (dst, i);
 381
 382   return true;
 383 }
 384
 385
 386 /* This is a fallback for implementations that do not support
 387    four operand operations.  */
 388 static inline bool
 389 bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3,
 390                 enum bitset_ops op)
 391 {
 392   bool changed = false;
 393
 394   /* Create temporary bitset.  */
 395   bool stats_enabled_save = bitset_stats_enabled;
 396   bitset_stats_enabled = false;
 397   bitset tmp = bitset_alloc (0, bitset_type_get (dst));
 398   bitset_stats_enabled = stats_enabled_save;
 399
 400   switch (op)
 401     {
 402     default:
 403       abort ();
 404
 405     case BITSET_OP_OR_AND:
 406       bitset_or (tmp, src1, src2);
 407       changed = bitset_and_cmp (dst, src3, tmp);
 408       break;
 409
 410     case BITSET_OP_AND_OR:
 411       bitset_and (tmp, src1, src2);
 412       changed = bitset_or_cmp (dst, src3, tmp);
 413       break;
 414
 415     case BITSET_OP_ANDN_OR:
 416       bitset_andn (tmp, src1, src2);
 417       changed = bitset_or_cmp (dst, src3, tmp);
 418       break;
 419     }
 420
 421   bitset_free (tmp);
 422   return changed;
 423 }
 424
 425
 426 /* DST = (SRC1 & SRC2) | SRC3.  */
 427 void
 428 bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
 429 {
 430   bitset_and_or_cmp_ (dst, src1, src2, src3);
 431 }
 432
 433
 434 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 435    DST != (SRC1 & SRC2) | SRC3.  */
 436 bool
 437 bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
 438 {
 439   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
 440 }
 441
 442
 443 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 444 void
 445 bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
 446 {
 447   bitset_andn_or_cmp_ (dst, src1, src2, src3);
 448 }
 449
 450
 451 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 452    DST != (SRC1 & ~SRC2) | SRC3.  */
 453 bool
 454 bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
 455 {
 456   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
 457 }
 458
 459
 460 /* DST = (SRC1 | SRC2) & SRC3.  */
 461 void
 462 bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3)
 463 {
 464   bitset_or_and_cmp_ (dst, src1, src2, src3);
 465 }
 466
 467
 468 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 469    DST != (SRC1 | SRC2) & SRC3.  */
 470 bool
 471 bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
 472 {
 473   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
 474 }
 475
 476
 477 /* Function to be called from debugger to print bitset.  */
 478 void
 479 debug_bitset (bitset bset)
 480 {
 481   if (bset)
 482     bitset_print (stderr, bset, true);
 483 }