lib/bitset.c

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