lib/bitset.c

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