lib/bitset.c

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