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 static void bitset_print PARAMS ((FILE *, bitset, int));
  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 int
  37 bitset_bytes (type, n_bits)
  38      enum bitset_type type;
  39      bitset_bindex n_bits;
  40 {
  41   unsigned int bytes;
  42
  43   if (bitset_stats_enabled)
  44     return bitset_stats_bytes ();
  45
  46   switch (type)
  47     {
  48     case BITSET_ARRAY:
  49       bytes = abitset_bytes (n_bits);
  50       break;
  51
  52     case BITSET_LIST:
  53       bytes = lbitset_bytes (n_bits);
  54       break;
  55
  56     case BITSET_TABLE:
  57       bytes = ebitset_bytes (n_bits);
  58       break;
  59
  60     default:
  61       abort ();
  62     }
  63
  64   return bytes;
  65 }
  66
  67
  68 /* Initialise bitset BSET of TYPE for N_BITS.  */
  69 bitset
  70 bitset_init (bset, n_bits, type)
  71      bitset bset;
  72      bitset_bindex n_bits;
  73      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     case BITSET_ARRAY:
  81       return abitset_init (bset, n_bits);
  82
  83     case BITSET_LIST:
  84       return lbitset_init (bset, n_bits);
  85
  86     case BITSET_TABLE:
  87       return ebitset_init (bset, n_bits);
  88
  89     default:
  90       abort ();
  91     }
  92 }
  93
  94
  95 /* Select a bitset type for a set of N_BITS and with attribute hints
  96    specified by ATTR.  For variable size bitsets, N_BITS is only a
  97    hint and may be zero.  */
  98 enum bitset_type
  99 bitset_type_choose (n_bits, attr)
 100      bitset_bindex n_bits ATTRIBUTE_UNUSED;
 101      unsigned int attr;
 102 {
 103   enum bitset_type type;
 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   /* Note that sometimes we will be asked for a zero length
 112      fixed size bitset.  */
 113
 114   /* Choose the type of bitset.  */
 115
 116   type = BITSET_ARRAY;
 117   /* Currently, the simple bitsets do not support a variable size.  */
 118   if (attr & BITSET_VARIABLE || attr & BITSET_SPARSE)
 119     {
 120       type = BITSET_LIST;
 121       if (attr & BITSET_DENSE || attr & BITSET_GREEDY)
 122         type = BITSET_TABLE;
 123     }
 124
 125   return type;
 126 }
 127
 128
 129 /* Create a bitset of N_BITS of type TYPE.  */
 130 bitset
 131 bitset_alloc (n_bits, type)
 132      bitset_bindex n_bits;
 133      enum bitset_type type;
 134 {
 135   unsigned int bytes;
 136   bitset bset;
 137
 138   bytes = bitset_bytes (type, n_bits);
 139
 140   bset = (bitset) 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 (bobstack, n_bits, type)
 153      struct obstack *bobstack;
 154      bitset_bindex n_bits;
 155      enum bitset_type type;
 156 {
 157   unsigned int 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 (n_bits, attr)
 173      bitset_bindex n_bits;
 174      unsigned int attr;
 175 {
 176   enum bitset_type type;
 177
 178   type = bitset_type_choose (n_bits, attr);
 179
 180   return bitset_alloc (n_bits, type);
 181 }
 182
 183
 184 /* Free bitset BSET.  */
 185 void
 186 bitset_free (bset)
 187      bitset bset;
 188 {
 189   BITSET_FREE_ (bset);
 190   free (bset);
 191 }
 192
 193
 194 /* Free bitset BSET allocated on obstack.  */
 195 void
 196 bitset_obstack_free (bset)
 197      bitset bset;
 198 {
 199   BITSET_FREE_ (bset);
 200 }
 201
 202
 203 /* Return bitset type.  */
 204 enum bitset_type
 205 bitset_type_get (bset)
 206    bitset bset;
 207 {
 208    enum bitset_type type;
 209
 210    type = BITSET_TYPE_ (bset);
 211    if (type != BITSET_STATS)
 212       return type;
 213
 214    return bitset_stats_type_get (bset);
 215 }
 216
 217
 218 /* Find next bit set in SRC starting from and including BITNO.
 219    Return -1 if SRC empty.  */
 220 int
 221 bitset_next (src, bitno)
 222      bitset src;
 223      bitset_bindex bitno;
 224 {
 225   bitset_bindex val;
 226   bitset_bindex next = bitno;
 227
 228   if (!bitset_list (src, &val, 1, &next))
 229     return -1;
 230   return val;
 231 }
 232
 233
 234 /* Find previous bit set in SRC starting from and including BITNO.
 235    Return -1 if SRC empty.  */
 236 int
 237 bitset_prev (src, bitno)
 238      bitset src;
 239      bitset_bindex bitno;
 240 {
 241   bitset_bindex val;
 242   bitset_bindex next = bitno;
 243
 244   if (!bitset_reverse_list (src, &val, 1, &next))
 245     return -1;
 246   return val;
 247 }
 248
 249
 250 /* Find first set bit.   */
 251 int
 252 bitset_first (src)
 253      bitset src;
 254 {
 255   return bitset_next (src, 0);
 256 }
 257
 258
 259 /* Find last set bit.   */
 260 int
 261 bitset_last (src)
 262      bitset src;
 263 {
 264   return bitset_prev (src, 0);
 265 }
 266
 267
 268 /* Return non-zero if BITNO in SRC is the only set bit.  */
 269 int
 270 bitset_only_set_p (src, bitno)
 271      bitset src;
 272      bitset_bindex bitno;
 273 {
 274   bitset_bindex val[2];
 275   bitset_bindex next = 0;
 276
 277   if (bitset_list (src, val, 2, &next) != 1)
 278     return 0;
 279   return val[0] == bitno;
 280 }
 281
 282
 283 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 284 int
 285 bitset_toggle (bset, bitno)
 286     bitset bset;
 287     bitset_bindex bitno;
 288 {
 289   /* This routine is for completeness.  It could be optimized if
 290      required.  */
 291   if (bitset_test (bset, bitno))
 292     {
 293       bitset_reset (bset, bitno);
 294       return 0;
 295     }
 296   else
 297     {
 298       bitset_set (bset, bitno);
 299       return 1;
 300     }
 301 }
 302
 303
 304 /* Print contents of bitset BSET to FILE.   */
 305 static void
 306 bitset_print (file, bset, verbose)
 307      FILE *file;
 308      bitset bset;
 309      int verbose;
 310 {
 311   unsigned int i, pos;
 312   bitset_iterator iter;
 313
 314   if (verbose)
 315     fprintf (file, "n_bits = %d, set = {", bitset_size (bset));
 316
 317   pos = 30;
 318   BITSET_FOR_EACH (iter, bset, i, 0)
 319   {
 320     if (pos > 70)
 321       {
 322         fprintf (file, "\n");
 323         pos = 0;
 324       }
 325
 326     fprintf (file, "%d ", i);
 327     pos += 1 + (i >= 10) + (i >= 100);
 328   };
 329
 330   if (verbose)
 331     fprintf (file, "}\n");
 332 }
 333
 334
 335 /* DST = SRC.  Return non-zero if DST != SRC.  */
 336 int
 337 bitset_copy (dst, src)
 338      bitset dst;
 339      bitset src;
 340 {
 341   unsigned int i;
 342   bitset_iterator iter;
 343
 344   if (BITSET_COMPATIBLE_ (dst, src))
 345     return BITSET_COPY_ (dst, src);
 346
 347   /* Convert bitset types.  We assume that the DST bitset
 348      is large enough to hold the SRC bitset.  */
 349   bitset_zero (dst);
 350   BITSET_FOR_EACH (iter, src, i, 0)
 351   {
 352      bitset_set (dst, i);
 353   };
 354
 355   return 1;
 356 }
 357
 358
 359 /* Return size in bits of bitset SRC.  */
 360 int
 361 bitset_size (src)
 362      bitset src;
 363 {
 364   return BITSET_SIZE_ (src);
 365 }
 366
 367
 368 /* Return number of bits set in bitset SRC.  */
 369 int
 370 bitset_count (src)
 371      bitset src;
 372 {
 373   bitset_bindex list[BITSET_LIST_SIZE];
 374   bitset_bindex next;
 375   int num;
 376   int count;
 377
 378   /* This could be greatly sped up by adding a count method for each
 379      bitset implementation that uses a direct technique (based on
 380      masks) for counting the number of bits set in a word.  */
 381
 382   next = 0;
 383   for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next));
 384        count += num)
 385     continue;
 386
 387   return count;
 388 }
 389
 390
 391 /* DST = 0.  */
 392 int
 393 bitset_zero (dst)
 394      bitset dst;
 395 {
 396   return BITSET_ZERO_ (dst);
 397 }
 398
 399
 400 /* DST = ~0.  */
 401 int
 402 bitset_ones (dst)
 403      bitset dst;
 404 {
 405   return BITSET_ONES_ (dst);
 406 }
 407
 408
 409 /* Return SRC == 0.  */
 410 int
 411 bitset_empty_p (src)
 412      bitset src;
 413 {
 414   return BITSET_EMPTY_P_ (src);
 415 }
 416
 417
 418 /* Return DST == DST | SRC.  */
 419 int
 420 bitset_subset_p (dst, src)
 421      bitset dst;
 422      bitset src;
 423 {
 424   return BITSET_SUBSET_P_ (dst, src);
 425 }
 426
 427
 428 /* Return DST == SRC.  */
 429 int
 430 bitset_equal_p (dst, src)
 431      bitset dst;
 432      bitset src;
 433 {
 434   return BITSET_EQUAL_P_ (dst, src);
 435 }
 436
 437
 438 /* Return DST & SRC == 0.  */
 439 int
 440 bitset_disjoint_p (dst, src)
 441      bitset dst;
 442      bitset src;
 443 {
 444   return BITSET_DISJOINT_P_ (dst, src);
 445 }
 446
 447
 448 /* DST = ~SRC.  */
 449 int
 450 bitset_not (dst, src)
 451      bitset dst;
 452      bitset src;
 453 {
 454   return BITSET_NOT_ (dst, src);
 455 }
 456
 457
 458 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 459 int
 460 bitset_or (dst, src1, src2)
 461      bitset dst;
 462      bitset src1;
 463      bitset src2;
 464 {
 465   return BITSET_OR_ (dst, src1, src2);
 466 }
 467
 468
 469 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 470 int
 471 bitset_and (dst, src1, src2)
 472      bitset dst;
 473      bitset src1;
 474      bitset src2;
 475 {
 476   return BITSET_AND_ (dst, src1, src2);
 477 }
 478
 479
 480 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 481 int
 482 bitset_xor (dst, src1, src2)
 483      bitset dst;
 484      bitset src1;
 485      bitset src2;
 486 {
 487   return BITSET_XOR_ (dst, src1, src2);
 488 }
 489
 490
 491 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 492 int
 493 bitset_andn (dst, src1, src2)
 494      bitset dst;
 495      bitset src1;
 496      bitset src2;
 497 {
 498   return BITSET_ANDN_ (dst, src1, src2);
 499 }
 500
 501
 502 /* This is a fallback for implementations that do not support
 503    four operand operations.  */
 504 int
 505 bitset_op4 (dst, src1, src2, src3, op)
 506      bitset dst;
 507      bitset src1;
 508      bitset src2;
 509      bitset src3;
 510      enum bitset_ops op;
 511 {
 512   int changed = 0;
 513   bitset tmp;
 514
 515   /* Create temporary bitset.  */
 516   tmp = bitset_alloc (0, bitset_type_get (dst));
 517
 518   switch (op)
 519     {
 520     case BITSET_OP_OR_AND:
 521       BITSET_OR_ (tmp, src1, src2);
 522       changed = BITSET_AND_ (dst, src3, tmp);
 523       break;
 524
 525     case BITSET_OP_AND_OR:
 526       BITSET_AND_ (tmp, src1, src2);
 527       changed = BITSET_OR_ (dst, src3, tmp);
 528       break;
 529
 530     case BITSET_OP_ANDN_OR:
 531       BITSET_ANDN_ (tmp, src1, src2);
 532       changed = BITSET_OR_ (dst, src3, tmp);
 533       break;
 534
 535     default:
 536       abort ();
 537     }
 538
 539   bitset_free (tmp);
 540   return changed;
 541 }
 542
 543
 544 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 545    DST != (SRC1 | SRC2) & SRC3.  */
 546 int
 547 bitset_or_and (dst, src1, src2, src3)
 548      bitset dst;
 549      bitset src1;
 550      bitset src2;
 551      bitset src3;
 552 {
 553   return BITSET_OR_AND_ (dst, src1, src2, src3);
 554 }
 555
 556
 557 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 558    DST != (SRC1 & SRC2) | SRC3.  */
 559 int
 560 bitset_and_or (dst, src1, src2, src3)
 561      bitset dst;
 562      bitset src1;
 563      bitset src2;
 564      bitset src3;
 565 {
 566   return BITSET_AND_OR_ (dst, src1, src2, src3);
 567 }
 568
 569
 570 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 571    DST != (SRC1 & ~SRC2) | SRC3.  */
 572 int
 573 bitset_andn_or (dst, src1, src2, src3)
 574      bitset dst;
 575      bitset src1;
 576      bitset src2;
 577      bitset src3;
 578 {
 579   return BITSET_ANDN_OR_ (dst, src1, src2, src3);
 580 }
 581
 582
 583 /* Dump bitset BSET to FILE.  */
 584 void
 585 bitset_dump (file, bset)
 586      FILE *file;
 587      bitset bset;
 588 {
 589   bitset_print (file, bset, 0);
 590 }
 591
 592
 593 /* Function to be called from debugger to print bitset.  */
 594 void
 595 debug_bitset (bset)
 596      bitset bset;
 597 {
 598   if (bset)
 599     bitset_print (stderr, bset, 1);
 600 }
 601
 602
 603 /* Release memory associated with bitsets.  */
 604 void
 605 bitset_release_memory ()
 606 {
 607   lbitset_release_memory ();
 608   ebitset_release_memory ();
 609 }