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
  35
  36 /* Return number of bytes required to create a N_BIT bitset
  37    of TYPE.  The bitset may grow to require more bytes than this.  */
  38 int
  39 bitset_bytes (type, n_bits)
  40      enum bitset_type type;
  41      bitset_bindex n_bits;
  42 {
  43   unsigned int bytes;
  44
  45   if (bitset_stats_enabled)
  46     return bitset_stats_bytes ();
  47
  48   switch (type)
  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     default:
  63       abort ();
  64     }
  65
  66   return bytes;
  67 }
  68
  69
  70 /* Initialise bitset BSET of TYPE for N_BITS.  */
  71 bitset
  72 bitset_init (bset, n_bits, type)
  73      bitset bset;
  74      bitset_bindex n_bits;
  75      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     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     default:
  92       abort ();
  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 (n_bits, attr)
 102      bitset_bindex n_bits ATTRIBUTE_UNUSED;
 103      unsigned int attr;
 104 {
 105   enum bitset_type type;
 106
 107   /* Check attributes.  */
 108   if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
 109     abort ();
 110   if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
 111     abort ();
 112
 113   /* Choose the type of bitset. Note that sometimes we will be asked
 114   for a zero length fixed size 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 /* Return name of bitset type.  */
 219 const char *
 220 bitset_type_name_get (bset)
 221      bitset bset;
 222 {
 223   enum bitset_type type;
 224
 225   type = bitset_type_get (bset);
 226
 227   return bitset_type_names[type];
 228 }
 229
 230
 231 /* Find next bit set in SRC starting from and including BITNO.
 232    Return -1 if SRC empty.  */
 233 int
 234 bitset_next (src, bitno)
 235      bitset src;
 236      bitset_bindex bitno;
 237 {
 238   bitset_bindex val;
 239   bitset_bindex next = bitno;
 240
 241   if (!bitset_list (src, &val, 1, &next))
 242     return -1;
 243   return val;
 244 }
 245
 246
 247 /* Find previous bit set in SRC starting from and including BITNO.
 248    Return -1 if SRC empty.  */
 249 int
 250 bitset_prev (src, bitno)
 251      bitset src;
 252      bitset_bindex bitno;
 253 {
 254   bitset_bindex val;
 255   bitset_bindex next = bitno;
 256
 257   if (!bitset_list_reverse (src, &val, 1, &next))
 258     return -1;
 259   return val;
 260 }
 261
 262
 263 /* Find first set bit.   */
 264 int
 265 bitset_first (src)
 266      bitset src;
 267 {
 268   return bitset_next (src, 0);
 269 }
 270
 271
 272 /* Find last set bit.   */
 273 int
 274 bitset_last (src)
 275      bitset src;
 276 {
 277   return bitset_prev (src, 0);
 278 }
 279
 280
 281 /* Return non-zero if BITNO in SRC is the only set bit.  */
 282 int
 283 bitset_only_set_p (src, bitno)
 284      bitset src;
 285      bitset_bindex bitno;
 286 {
 287   bitset_bindex val[2];
 288   bitset_bindex next = 0;
 289
 290   if (bitset_list (src, val, 2, &next) != 1)
 291     return 0;
 292   return val[0] == bitno;
 293 }
 294
 295
 296 /* Print contents of bitset BSET to FILE.   */
 297 static void
 298 bitset_print (file, bset, verbose)
 299      FILE *file;
 300      bitset bset;
 301      int verbose;
 302 {
 303   unsigned int pos;
 304   bitset_bindex i;
 305   bitset_iterator iter;
 306
 307   if (verbose)
 308     fprintf (file, "n_bits = %d, set = {", bitset_size (bset));
 309
 310   pos = 30;
 311   BITSET_FOR_EACH (iter, bset, i, 0)
 312   {
 313     if (pos > 70)
 314       {
 315         fprintf (file, "\n");
 316         pos = 0;
 317       }
 318
 319     fprintf (file, "%d ", i);
 320     pos += 1 + (i >= 10) + (i >= 100);
 321   };
 322
 323   if (verbose)
 324     fprintf (file, "}\n");
 325 }
 326
 327
 328 /* Dump bitset BSET to FILE.  */
 329 void
 330 bitset_dump (file, bset)
 331      FILE *file;
 332      bitset bset;
 333 {
 334   bitset_print (file, bset, 0);
 335 }
 336
 337
 338
 339 /* Release memory associated with bitsets.  */
 340 void
 341 bitset_release_memory ()
 342 {
 343   lbitset_release_memory ();
 344   ebitset_release_memory ();
 345 }
 346
 347
 348
 349 /* Toggle bit BITNO in bitset BSET and return non-zero if not set.  */
 350 int
 351 bitset_toggle_ (bset, bitno)
 352     bitset bset;
 353     bitset_bindex bitno;
 354 {
 355   /* This routine is for completeness.  It could be optimized if
 356      required.  */
 357   if (bitset_test (bset, bitno))
 358     {
 359       bitset_reset (bset, bitno);
 360       return 0;
 361     }
 362   else
 363     {
 364       bitset_set (bset, bitno);
 365       return 1;
 366     }
 367 }
 368
 369
 370 /* Return number of bits set in bitset SRC.  */
 371 int
 372 bitset_count_ (src)
 373      bitset src;
 374 {
 375   bitset_bindex list[BITSET_LIST_SIZE];
 376   bitset_bindex next;
 377   int num;
 378   int count;
 379
 380   /* This could be greatly sped up by adding a count method for each
 381      bitset implementation that uses a direct technique (based on
 382      masks) for counting the number of bits set in a word.  */
 383
 384   next = 0;
 385   for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next));
 386        count += num)
 387     continue;
 388
 389   return count;
 390 }
 391
 392
 393 /* DST = SRC.  Return non-zero if DST != SRC.
 394    This is a fallback for the case where SRC and DST are different
 395    bitset types.  */
 396 int
 397 bitset_copy_ (dst, src)
 398      bitset dst;
 399      bitset src;
 400 {
 401   bitset_bindex i;
 402   bitset_iterator iter;
 403
 404   /* Convert bitset types.  We assume that the DST bitset
 405      is large enough to hold the SRC bitset.  */
 406   bitset_zero (dst);
 407   BITSET_FOR_EACH (iter, src, i, 0)
 408   {
 409      bitset_set (dst, i);
 410   };
 411
 412   return 1;
 413 }
 414
 415
 416 /* This is a fallback for implementations that do not support
 417    four operand operations.  */
 418 static inline int
 419 bitset_op4_cmp (dst, src1, src2, src3, op)
 420      bitset dst;
 421      bitset src1;
 422      bitset src2;
 423      bitset src3;
 424      enum bitset_ops op;
 425 {
 426   int changed = 0;
 427   int stats_enabled_save;
 428   bitset tmp;
 429
 430   /* Create temporary bitset.  */
 431   stats_enabled_save = bitset_stats_enabled;
 432   bitset_stats_enabled = 0;
 433   tmp = bitset_alloc (0, bitset_type_get (dst));
 434   bitset_stats_enabled = stats_enabled_save;
 435
 436   switch (op)
 437     {
 438     case BITSET_OP_OR_AND:
 439       bitset_or (tmp, src1, src2);
 440       changed = bitset_and_cmp (dst, src3, tmp);
 441       break;
 442
 443     case BITSET_OP_AND_OR:
 444       bitset_and (tmp, src1, src2);
 445       changed = bitset_or_cmp (dst, src3, tmp);
 446       break;
 447
 448     case BITSET_OP_ANDN_OR:
 449       bitset_andn (tmp, src1, src2);
 450       changed = bitset_or_cmp (dst, src3, tmp);
 451       break;
 452
 453     default:
 454       abort ();
 455     }
 456
 457   bitset_free (tmp);
 458   return changed;
 459 }
 460
 461
 462 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 463    DST != (SRC1 & SRC2) | SRC3.  */
 464 int
 465 bitset_and_or_cmp_ (dst, src1, src2, src3)
 466      bitset dst;
 467      bitset src1;
 468      bitset src2;
 469      bitset src3;
 470 {
 471   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
 472 }
 473
 474
 475 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 476    DST != (SRC1 & ~SRC2) | SRC3.  */
 477 int
 478 bitset_andn_or_cmp_ (dst, src1, src2, src3)
 479      bitset dst;
 480      bitset src1;
 481      bitset src2;
 482      bitset src3;
 483 {
 484   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
 485 }
 486
 487
 488 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 489    DST != (SRC1 | SRC2) & SRC3.  */
 490 int
 491 bitset_or_and_cmp_ (dst, src1, src2, src3)
 492      bitset dst;
 493      bitset src1;
 494      bitset src2;
 495      bitset src3;
 496 {
 497   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
 498 }
 499
 500
 501 /* Function to be called from debugger to print bitset.  */
 502 void
 503 debug_bitset (bset)
 504      bitset bset;
 505 {
 506   if (bset)
 507     bitset_print (stderr, bset, 1);
 508 }