lib/bitset.c

   1 /* General bitsets.
   2    Copyright (C) 2002 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 2 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, write to the Free Software
  17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  18
  19 #ifdef HAVE_CONFIG_H
  20 #include "config.h"
  21 #endif
  22
  23 #include <stdlib.h>
  24 #include "bitset.h"
  25 #include "abitset.h"
  26 #include "lbitset.h"
  27 #include "ebitset.h"
  28 #include "bitset_stats.h"
  29 #include "obstack.h"
  30
  31 const char * const bitset_type_names[] = BITSET_TYPE_NAMES;
  32
  33 static void bitset_print PARAMS ((FILE *, bitset, int));
  34 static int bitset_op4_cmp PARAMS ((bitset, bitset, bitset, bitset, int));
  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 (type, n_bits)
  41      enum_bitset_type type;
  42      bitset_bindex n_bits;
  43 {
  44   size_t bytes;
  45
  46   if (bitset_stats_enabled)
  47     return bitset_stats_bytes ();
  48
  49   switch (type)
  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     default:
  64       abort ();
  65     }
  66
  67   return bytes;
  68 }
  69
  70
  71 /* Initialise bitset BSET of TYPE for N_BITS.  */
  72 bitset
  73 bitset_init (bset, n_bits, type)
  74      bitset bset;
  75      bitset_bindex n_bits;
  76      enum_bitset_type type;
  77 {
  78   if (bitset_stats_enabled)
  79     return bitset_stats_init (bset, n_bits, type);
  80
  81   switch (type)
  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     default:
  93       abort ();
  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 (n_bits, attr)
 103      bitset_bindex n_bits ATTRIBUTE_UNUSED;
 104      unsigned int attr;
 105 {
 106   enum bitset_type type;
 107
 108   /* Check attributes.  */
 109   if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
 110     abort ();
 111   if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
 112     abort ();
 113
 114   /* Choose the type of bitset. Note that sometimes we will be asked
 115   for a zero length fixed size bitset.  */
 116
 117   type = BITSET_ARRAY;
 118   /* Currently, the simple bitsets do not support a variable size.  */
 119   if (attr & BITSET_VARIABLE || attr & BITSET_SPARSE)
 120     {
 121       type = BITSET_LIST;
 122       if (attr & BITSET_DENSE || attr & BITSET_GREEDY)
 123         type = BITSET_TABLE;
 124     }
 125
 126   return type;
 127 }
 128
 129
 130 /* Create a bitset of N_BITS of type TYPE.  */
 131 bitset
 132 bitset_alloc (n_bits, type)
 133      bitset_bindex n_bits;
 134      enum_bitset_type type;
 135 {
 136   size_t bytes;
 137   bitset bset;
 138
 139   bytes = bitset_bytes (type, n_bits);
 140
 141   bset = (bitset) 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 (bobstack, n_bits, type)
 154      struct obstack *bobstack;
 155      bitset_bindex n_bits;
 156      enum_bitset_type type;
 157 {
 158   size_t bytes;
 159   bitset bset;
 160
 161   bytes = bitset_bytes (type, n_bits);
 162
 163   bset = obstack_alloc (bobstack, bytes);
 164   memset (bset, 0, bytes);
 165
 166   return bitset_init (bset, n_bits, type);
 167 }
 168
 169
 170 /* Create a bitset of N_BITS and with attribute hints specified by
 171    ATTR.  */
 172 bitset
 173 bitset_create (n_bits, attr)
 174      bitset_bindex n_bits;
 175      unsigned int attr;
 176 {
 177   enum bitset_type type;
 178
 179   type = bitset_type_choose (n_bits, attr);
 180
 181   return bitset_alloc (n_bits, type);
 182 }
 183
 184
 185 /* Free bitset BSET.  */
 186 void
 187 bitset_free (bset)
 188      bitset bset;
 189 {
 190   BITSET_FREE_ (bset);
 191   free (bset);
 192 }
 193
 194
 195 /* Free bitset BSET allocated on obstack.  */
 196 void
 197 bitset_obstack_free (bset)
 198      bitset bset;
 199 {
 200   BITSET_FREE_ (bset);
 201 }
 202
 203
 204 /* Return bitset type.  */
 205 enum bitset_type
 206 bitset_type_get (bset)
 207    bitset bset;
 208 {
 209    enum bitset_type type;
 210
 211    type = BITSET_TYPE_ (bset);
 212    if (type != BITSET_STATS)
 213       return type;
 214
 215    return bitset_stats_type_get (bset);
 216 }
 217
 218
 219 /* Return name of bitset type.  */
 220 const char *
 221 bitset_type_name_get (bset)
 222      bitset bset;
 223 {
 224   enum bitset_type type;
 225
 226   type = bitset_type_get (bset);
 227
 228   return bitset_type_names[type];
 229 }
 230
 231
 232 /* Find next bit set in SRC starting from and including BITNO.
 233    Return BITSET_BINDEX_MAX if SRC empty.  */
 234 bitset_bindex
 235 bitset_next (src, bitno)
 236      bitset src;
 237      bitset_bindex bitno;
 238 {
 239   bitset_bindex val;
 240   bitset_bindex next = bitno;
 241
 242   if (!bitset_list (src, &val, 1, &next))
 243     return BITSET_BINDEX_MAX;
 244   return val;
 245 }
 246
 247
 248 /* Find previous bit set in SRC starting from and including BITNO.
 249    Return BITSET_BINDEX_MAX if SRC empty.  */
 250 bitset_bindex
 251 bitset_prev (src, bitno)
 252      bitset src;
 253      bitset_bindex bitno;
 254 {
 255   bitset_bindex val;
 256   bitset_bindex next = bitno;
 257
 258   if (!bitset_list_reverse (src, &val, 1, &next))
 259     return BITSET_BINDEX_MAX;
 260   return val;
 261 }
 262
 263
 264 /* Find first set bit.   */
 265 bitset_bindex
 266 bitset_first (src)
 267      bitset src;
 268 {
 269   return bitset_next (src, 0);
 270 }
 271
 272
 273 /* Find last set bit.   */
 274 bitset_bindex
 275 bitset_last (src)
 276      bitset src;
 277 {
 278   return bitset_prev (src, 0);
 279 }
 280
 281
 282 /* Return non-zero if BITNO in SRC is the only set bit.  */
 283 int
 284 bitset_only_set_p (src, bitno)
 285      bitset src;
 286      bitset_bindex bitno;
 287 {
 288   bitset_bindex val[2];
 289   bitset_bindex next = 0;
 290
 291   if (bitset_list (src, val, 2, &next) != 1)
 292     return 0;
 293   return val[0] == bitno;
 294 }
 295
 296
 297 /* Print contents of bitset BSET to FILE.   */
 298 static void
 299 bitset_print (file, bset, verbose)
 300      FILE *file;
 301      bitset bset;
 302      int verbose;
 303 {
 304   unsigned int pos;
 305   bitset_bindex i;
 306   bitset_iterator iter;
 307
 308   if (verbose)
 309     fprintf (file, "n_bits = %lu, set = {",
 310              (unsigned long) bitset_size (bset));
 311
 312   pos = 30;
 313   BITSET_FOR_EACH (iter, bset, i, 0)
 314   {
 315     if (pos > 70)
 316       {
 317         fprintf (file, "\n");
 318         pos = 0;
 319       }
 320
 321     fprintf (file, "%d ", i);
 322     pos += 1 + (i >= 10) + (i >= 100);
 323   };
 324
 325   if (verbose)
 326     fprintf (file, "}\n");
 327 }
 328
 329
 330 /* Dump bitset BSET to FILE.  */
 331 void
 332 bitset_dump (file, bset)
 333      FILE *file;
 334      bitset bset;
 335 {
 336   bitset_print (file, bset, 0);
 337 }
 338
 339
 340
 341 /* Release memory associated with bitsets.  */
 342 void
 343 bitset_release_memory ()
 344 {
 345   lbitset_release_memory ();
 346   ebitset_release_memory ();
 347 }
 348
 349
 350
 351 /* Toggle bit BITNO in bitset BSET and return non-zero if not set.  */
 352 int
 353 bitset_toggle_ (bset, bitno)
 354     bitset bset;
 355     bitset_bindex bitno;
 356 {
 357   /* This routine is for completeness.  It could be optimized if
 358      required.  */
 359   if (bitset_test (bset, bitno))
 360     {
 361       bitset_reset (bset, bitno);
 362       return 0;
 363     }
 364   else
 365     {
 366       bitset_set (bset, bitno);
 367       return 1;
 368     }
 369 }
 370
 371
 372 /* Return number of bits set in bitset SRC.  */
 373 bitset_bindex
 374 bitset_count_ (src)
 375      bitset src;
 376 {
 377   bitset_bindex list[BITSET_LIST_SIZE];
 378   bitset_bindex next;
 379   bitset_bindex num;
 380   bitset_bindex count;
 381
 382   /* This could be greatly sped up by adding a count method for each
 383      bitset implementation that uses a direct technique (based on
 384      masks) for counting the number of bits set in a word.  */
 385
 386   next = 0;
 387   for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next));
 388        count += num)
 389     continue;
 390
 391   return count;
 392 }
 393
 394
 395 /* DST = SRC.  Return non-zero if DST != SRC.
 396    This is a fallback for the case where SRC and DST are different
 397    bitset types.  */
 398 int
 399 bitset_copy_ (dst, src)
 400      bitset dst;
 401      bitset src;
 402 {
 403   bitset_bindex i;
 404   bitset_iterator iter;
 405
 406   /* Convert bitset types.  We assume that the DST bitset
 407      is large enough to hold the SRC bitset.  */
 408   bitset_zero (dst);
 409   BITSET_FOR_EACH (iter, src, i, 0)
 410   {
 411      bitset_set (dst, i);
 412   };
 413
 414   return 1;
 415 }
 416
 417
 418 /* This is a fallback for implementations that do not support
 419    four operand operations.  */
 420 static inline int
 421 bitset_op4_cmp (dst, src1, src2, src3, op)
 422      bitset dst;
 423      bitset src1;
 424      bitset src2;
 425      bitset src3;
 426      enum_bitset_ops op;
 427 {
 428   int changed = 0;
 429   int stats_enabled_save;
 430   bitset tmp;
 431
 432   /* Create temporary bitset.  */
 433   stats_enabled_save = bitset_stats_enabled;
 434   bitset_stats_enabled = 0;
 435   tmp = bitset_alloc (0, bitset_type_get (dst));
 436   bitset_stats_enabled = stats_enabled_save;
 437
 438   switch (op)
 439     {
 440     case BITSET_OP_OR_AND:
 441       bitset_or (tmp, src1, src2);
 442       changed = bitset_and_cmp (dst, src3, tmp);
 443       break;
 444
 445     case BITSET_OP_AND_OR:
 446       bitset_and (tmp, src1, src2);
 447       changed = bitset_or_cmp (dst, src3, tmp);
 448       break;
 449
 450     case BITSET_OP_ANDN_OR:
 451       bitset_andn (tmp, src1, src2);
 452       changed = bitset_or_cmp (dst, src3, tmp);
 453       break;
 454
 455     default:
 456       abort ();
 457     }
 458
 459   bitset_free (tmp);
 460   return changed;
 461 }
 462
 463
 464 /* DST = (SRC1 & SRC2) | SRC3.  */
 465 void
 466 bitset_and_or_ (dst, src1, src2, src3)
 467      bitset dst;
 468      bitset src1;
 469      bitset src2;
 470      bitset src3;
 471 {
 472   bitset_and_or_cmp_ (dst, src1, src2, src3);
 473 }
 474
 475
 476 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 477    DST != (SRC1 & SRC2) | SRC3.  */
 478 int
 479 bitset_and_or_cmp_ (dst, src1, src2, src3)
 480      bitset dst;
 481      bitset src1;
 482      bitset src2;
 483      bitset src3;
 484 {
 485   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
 486 }
 487
 488
 489 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 490 void
 491 bitset_andn_or_ (dst, src1, src2, src3)
 492      bitset dst;
 493      bitset src1;
 494      bitset src2;
 495      bitset src3;
 496 {
 497   bitset_andn_or_cmp_ (dst, src1, src2, src3);
 498 }
 499
 500
 501 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 502    DST != (SRC1 & ~SRC2) | SRC3.  */
 503 int
 504 bitset_andn_or_cmp_ (dst, src1, src2, src3)
 505      bitset dst;
 506      bitset src1;
 507      bitset src2;
 508      bitset src3;
 509 {
 510   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
 511 }
 512
 513
 514 /* DST = (SRC1 | SRC2) & SRC3.  */
 515 void
 516 bitset_or_and_ (dst, src1, src2, src3)
 517      bitset dst;
 518      bitset src1;
 519      bitset src2;
 520      bitset src3;
 521 {
 522   bitset_or_and_cmp_ (dst, src1, src2, src3);
 523 }
 524
 525
 526 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 527    DST != (SRC1 | SRC2) & SRC3.  */
 528 int
 529 bitset_or_and_cmp_ (dst, src1, src2, src3)
 530      bitset dst;
 531      bitset src1;
 532      bitset src2;
 533      bitset src3;
 534 {
 535   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
 536 }
 537
 538
 539 /* Function to be called from debugger to print bitset.  */
 540 void
 541 debug_bitset (bset)
 542      bitset bset;
 543 {
 544   if (bset)
 545     bitset_print (stderr, bset, 1);
 546 }