lib/bitset.c

   1 /* General bitsets.
   2
   3    Copyright (C) 2002-2006, 2009-2015, 2018-2019 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 <http://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 ATTRIBUTE_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 = xcalloc (1, 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   BITSET_FREE_ (bset);
 172   free (bset);
 173 }
 174
 175
 176 /* Free bitset BSET allocated on obstack.  */
 177 void
 178 bitset_obstack_free (bitset bset)
 179 {
 180   BITSET_FREE_ (bset);
 181 }
 182
 183
 184 /* Return bitset type.  */
 185 enum bitset_type
 186 bitset_type_get (bitset bset)
 187 {
 188    enum bitset_type type = BITSET_TYPE_ (bset);
 189    if (type != BITSET_STATS)
 190      return type;
 191
 192    return bitset_stats_type_get (bset);
 193 }
 194
 195
 196 /* Return name of bitset type.  */
 197 const char *
 198 bitset_type_name_get (bitset bset)
 199 {
 200   enum bitset_type type = bitset_type_get (bset);
 201
 202   return bitset_type_names[type];
 203 }
 204
 205
 206 /* Find next bit set in SRC starting from and including BITNO.
 207    Return BITSET_BINDEX_MAX if SRC empty.  */
 208 bitset_bindex
 209 bitset_next (bitset src, bitset_bindex bitno)
 210 {
 211   bitset_bindex next = bitno;
 212   bitset_bindex val;
 213   if (!bitset_list (src, &val, 1, &next))
 214     return BITSET_BINDEX_MAX;
 215   return val;
 216 }
 217
 218
 219 /* Return true if both bitsets are of the same type and size.  */
 220 extern bool
 221 bitset_compatible_p (bitset bset1, bitset bset2)
 222 {
 223   return BITSET_COMPATIBLE_ (bset1, bset2);
 224 }
 225
 226
 227 /* Find previous bit set in SRC starting from and including BITNO.
 228    Return BITSET_BINDEX_MAX if SRC empty.  */
 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, "n_bits = %lu, set = {",
 275              (unsigned long) bitset_size (bset));
 276
 277   unsigned pos = 30;
 278   bitset_bindex i;
 279   bitset_iterator iter;
 280   BITSET_FOR_EACH (iter, bset, i, 0)
 281   {
 282     if (pos > 70)
 283       {
 284         fprintf (file, "\n");
 285         pos = 0;
 286       }
 287
 288     fprintf (file, "%lu ", (unsigned long) i);
 289     pos += 1 + (i >= 10) + (i >= 100);
 290   }
 291
 292   if (verbose)
 293     fprintf (file, "}\n");
 294 }
 295
 296
 297 /* Dump bitset BSET to FILE.  */
 298 void
 299 bitset_dump (FILE *file, bitset bset)
 300 {
 301   bitset_print (file, bset, false);
 302 }
 303
 304
 305 /* Release memory associated with bitsets.  */
 306 void
 307 bitset_release_memory (void)
 308 {
 309   lbitset_release_memory ();
 310   tbitset_release_memory ();
 311 }
 312
 313
 314 /* Toggle bit BITNO in bitset BSET and the new value of the bit.  */
 315 bool
 316 bitset_toggle_ (bitset bset, bitset_bindex bitno)
 317 {
 318   /* This routine is for completeness.  It could be optimized if
 319      required.  */
 320   if (bitset_test (bset, bitno))
 321     {
 322       bitset_reset (bset, bitno);
 323       return false;
 324     }
 325   else
 326     {
 327       bitset_set (bset, bitno);
 328       return true;
 329     }
 330 }
 331
 332
 333 /* Return number of bits in bitset SRC.  */
 334 bitset_bindex
 335 bitset_size_ (bitset src)
 336 {
 337   return BITSET_NBITS_ (src);
 338 }
 339
 340
 341 /* Return number of bits set in bitset SRC.  */
 342 bitset_bindex
 343 bitset_count_ (bitset src)
 344 {
 345   bitset_bindex list[BITSET_LIST_SIZE];
 346   bitset_bindex count = 0;
 347
 348   /* This could be greatly sped up by adding a count method for each
 349      bitset implementation that uses a direct technique (based on
 350      masks) for counting the number of bits set in a word.  */
 351
 352   {
 353     bitset_bindex next = 0;
 354     bitset_bindex num;
 355     while ((num = bitset_list (src, list, BITSET_LIST_SIZE, &next)))
 356       count += num;
 357   }
 358
 359   return count;
 360 }
 361
 362
 363 /* DST = SRC.  Return true if DST != SRC.
 364    This is a fallback for the case where SRC and DST are different
 365    bitset types.  */
 366 bool
 367 bitset_copy_ (bitset dst, bitset src)
 368 {
 369   bitset_bindex i;
 370   bitset_iterator iter;
 371
 372   /* Convert bitset types.  We assume that the DST bitset
 373      is large enough to hold the SRC bitset.  */
 374   bitset_zero (dst);
 375   BITSET_FOR_EACH (iter, src, i, 0)
 376     bitset_set (dst, i);
 377
 378   return true;
 379 }
 380
 381
 382 /* This is a fallback for implementations that do not support
 383    four operand operations.  */
 384 static inline bool
 385 bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3,
 386                 enum bitset_ops op)
 387 {
 388   bool changed = false;
 389
 390   /* Create temporary bitset.  */
 391   bool stats_enabled_save = bitset_stats_enabled;
 392   bitset_stats_enabled = false;
 393   bitset tmp = bitset_alloc (0, bitset_type_get (dst));
 394   bitset_stats_enabled = stats_enabled_save;
 395
 396   switch (op)
 397     {
 398     default:
 399       abort ();
 400
 401     case BITSET_OP_OR_AND:
 402       bitset_or (tmp, src1, src2);
 403       changed = bitset_and_cmp (dst, src3, tmp);
 404       break;
 405
 406     case BITSET_OP_AND_OR:
 407       bitset_and (tmp, src1, src2);
 408       changed = bitset_or_cmp (dst, src3, tmp);
 409       break;
 410
 411     case BITSET_OP_ANDN_OR:
 412       bitset_andn (tmp, src1, src2);
 413       changed = bitset_or_cmp (dst, src3, tmp);
 414       break;
 415     }
 416
 417   bitset_free (tmp);
 418   return changed;
 419 }
 420
 421
 422 /* DST = (SRC1 & SRC2) | SRC3.  */
 423 void
 424 bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
 425 {
 426   bitset_and_or_cmp_ (dst, src1, src2, src3);
 427 }
 428
 429
 430 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 431    DST != (SRC1 & SRC2) | SRC3.  */
 432 bool
 433 bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
 434 {
 435   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
 436 }
 437
 438
 439 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 440 void
 441 bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
 442 {
 443   bitset_andn_or_cmp_ (dst, src1, src2, src3);
 444 }
 445
 446
 447 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 448    DST != (SRC1 & ~SRC2) | SRC3.  */
 449 bool
 450 bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
 451 {
 452   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
 453 }
 454
 455
 456 /* DST = (SRC1 | SRC2) & SRC3.  */
 457 void
 458 bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3)
 459 {
 460   bitset_or_and_cmp_ (dst, src1, src2, src3);
 461 }
 462
 463
 464 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 465    DST != (SRC1 | SRC2) & SRC3.  */
 466 bool
 467 bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
 468 {
 469   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
 470 }
 471
 472
 473 /* Function to be called from debugger to print bitset.  */
 474 void
 475 debug_bitset (bitset bset)
 476 {
 477   if (bset)
 478     bitset_print (stderr, bset, true);
 479 }