lib/bitset.c

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