lib/bitset.c

   1 /* General bitsets.
   2
   3    Copyright (C) 2002-2006, 2009-2015, 2018-2024 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 (MAYBE_UNUSED bitset_bindex n_bits, 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 bitset_bindex
 211 bitset_next (bitset src, bitset_bindex bitno)
 212 {
 213   bitset_bindex next = bitno;
 214   bitset_bindex val;
 215   if (!bitset_list (src, &val, 1, &next))
 216     return BITSET_BINDEX_MAX;
 217   return val;
 218 }
 219
 220
 221 /* Return true if both bitsets are of the same type and size.  */
 222 extern bool
 223 bitset_compatible_p (bitset bset1, bitset bset2)
 224 {
 225   return BITSET_COMPATIBLE_ (bset1, bset2);
 226 }
 227
 228
 229 bitset_bindex
 230 bitset_prev (bitset src, bitset_bindex bitno)
 231 {
 232   bitset_bindex next = bitno;
 233   bitset_bindex val;
 234   if (!bitset_list_reverse (src, &val, 1, &next))
 235     return BITSET_BINDEX_MAX;
 236   return val;
 237 }
 238
 239
 240 /* Find first set bit.   */
 241 bitset_bindex
 242 bitset_first (bitset src)
 243 {
 244   return bitset_next (src, 0);
 245 }
 246
 247
 248 /* Find last set bit.   */
 249 bitset_bindex
 250 bitset_last (bitset src)
 251 {
 252   return bitset_prev (src, 0);
 253 }
 254
 255
 256 /* Is BITNO in SRC the only set bit?  */
 257 bool
 258 bitset_only_set_p (bitset src, bitset_bindex bitno)
 259 {
 260   bitset_bindex val[2];
 261   bitset_bindex next = 0;
 262
 263   if (bitset_list (src, val, 2, &next) != 1)
 264     return false;
 265   return val[0] == bitno;
 266 }
 267
 268
 269 /* Print contents of bitset BSET to FILE.   */
 270 static void
 271 bitset_print (FILE *file, bitset bset, bool verbose)
 272 {
 273   if (verbose)
 274     fprintf (file, "%s{n_bits = %lu, set = {",
 275              bitset_type_name_get (bset),
 276              (unsigned long) bitset_size (bset));
 277
 278   unsigned pos = 30;
 279   bitset_bindex i;
 280   bitset_iterator iter;
 281   BITSET_FOR_EACH (iter, bset, i, 0)
 282   {
 283     if (pos > 70)
 284       {
 285         fprintf (file, "\n");
 286         pos = 0;
 287       }
 288
 289     fprintf (file, "%lu ", (unsigned long) i);
 290     pos += 1 + (i >= 10) + (i >= 100);
 291   }
 292
 293   if (verbose)
 294     fprintf (file, "}}\n");
 295 }
 296
 297
 298 /* Dump bitset BSET to FILE.  */
 299 void
 300 bitset_dump (FILE *file, bitset bset)
 301 {
 302   bitset_print (file, bset, false);
 303 }
 304
 305
 306 /* Release memory associated with bitsets.  */
 307 void
 308 bitset_release_memory (void)
 309 {
 310   lbitset_release_memory ();
 311   tbitset_release_memory ();
 312 }
 313
 314
 315 /* Toggle bit BITNO in bitset BSET and the new value of the bit.  */
 316 bool
 317 bitset_toggle_ (bitset bset, bitset_bindex bitno)
 318 {
 319   /* This routine is for completeness.  It could be optimized if
 320      required.  */
 321   if (bitset_test (bset, bitno))
 322     {
 323       bitset_reset (bset, bitno);
 324       return false;
 325     }
 326   else
 327     {
 328       bitset_set (bset, bitno);
 329       return true;
 330     }
 331 }
 332
 333
 334 /* Return number of bits in bitset SRC.  */
 335 bitset_bindex
 336 bitset_size_ (bitset src)
 337 {
 338   return BITSET_NBITS_ (src);
 339 }
 340
 341
 342 /* Return number of bits set in bitset SRC.  */
 343 bitset_bindex
 344 bitset_count_ (bitset src)
 345 {
 346   bitset_bindex list[BITSET_LIST_SIZE];
 347   bitset_bindex count = 0;
 348
 349   /* This could be greatly sped up by adding a count method for each
 350      bitset implementation that uses a direct technique (based on
 351      masks) for counting the number of bits set in a word.  */
 352
 353   {
 354     bitset_bindex next = 0;
 355     bitset_bindex num;
 356     while ((num = bitset_list (src, list, BITSET_LIST_SIZE, &next)))
 357       count += num;
 358   }
 359
 360   return count;
 361 }
 362
 363
 364 /* DST = SRC.  Return true if DST != SRC.
 365    This is a fallback for the case where SRC and DST are different
 366    bitset types.  */
 367 bool
 368 bitset_copy_ (bitset dst, bitset src)
 369 {
 370   bitset_bindex i;
 371   bitset_iterator iter;
 372
 373   /* Convert bitset types.  We assume that the DST bitset
 374      is large enough to hold the SRC bitset.  */
 375   bitset_zero (dst);
 376   BITSET_FOR_EACH (iter, src, i, 0)
 377     bitset_set (dst, i);
 378
 379   return true;
 380 }
 381
 382
 383 /* This is a fallback for implementations that do not support
 384    four operand operations.  */
 385 static inline bool
 386 bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3,
 387                 enum bitset_ops op)
 388 {
 389   bool changed = false;
 390
 391   /* Create temporary bitset.  */
 392   bool stats_enabled_save = bitset_stats_enabled;
 393   bitset_stats_enabled = false;
 394   bitset tmp = bitset_alloc (0, bitset_type_get (dst));
 395   bitset_stats_enabled = stats_enabled_save;
 396
 397   switch (op)
 398     {
 399     default:
 400       abort ();
 401
 402     case BITSET_OP_OR_AND:
 403       bitset_or (tmp, src1, src2);
 404       changed = bitset_and_cmp (dst, src3, tmp);
 405       break;
 406
 407     case BITSET_OP_AND_OR:
 408       bitset_and (tmp, src1, src2);
 409       changed = bitset_or_cmp (dst, src3, tmp);
 410       break;
 411
 412     case BITSET_OP_ANDN_OR:
 413       bitset_andn (tmp, src1, src2);
 414       changed = bitset_or_cmp (dst, src3, tmp);
 415       break;
 416     }
 417
 418   bitset_free (tmp);
 419   return changed;
 420 }
 421
 422
 423 /* DST = (SRC1 & SRC2) | SRC3.  */
 424 void
 425 bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
 426 {
 427   bitset_and_or_cmp_ (dst, src1, src2, src3);
 428 }
 429
 430
 431 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 432    DST != (SRC1 & SRC2) | SRC3.  */
 433 bool
 434 bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
 435 {
 436   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
 437 }
 438
 439
 440 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 441 void
 442 bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
 443 {
 444   bitset_andn_or_cmp_ (dst, src1, src2, src3);
 445 }
 446
 447
 448 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 449    DST != (SRC1 & ~SRC2) | SRC3.  */
 450 bool
 451 bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
 452 {
 453   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
 454 }
 455
 456
 457 /* DST = (SRC1 | SRC2) & SRC3.  */
 458 void
 459 bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3)
 460 {
 461   bitset_or_and_cmp_ (dst, src1, src2, src3);
 462 }
 463
 464
 465 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 466    DST != (SRC1 | SRC2) & SRC3.  */
 467 bool
 468 bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
 469 {
 470   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
 471 }
 472
 473
 474 /* Function to be called from debugger to print bitset.  */
 475 void
 476 debug_bitset (bitset bset)
 477 {
 478   if (bset)
 479     bitset_print (stderr, bset, true);
 480 }