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 size_t
  39 bitset_bytes (type, n_bits)
  40      enum bitset_type type;
  41      bitset_bindex n_bits;
  42 {
  43   size_t 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   size_t 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   size_t 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 BITSET_BINDEX_MAX if SRC empty.  */
 233 bitset_bindex
 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 BITSET_BINDEX_MAX;
 243   return val;
 244 }
 245
 246
 247 /* Find previous bit set in SRC starting from and including BITNO.
 248    Return BITSET_BINDEX_MAX if SRC empty.  */
 249 bitset_bindex
 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 BITSET_BINDEX_MAX;
 259   return val;
 260 }
 261
 262
 263 /* Find first set bit.   */
 264 bitset_bindex
 265 bitset_first (src)
 266      bitset src;
 267 {
 268   return bitset_next (src, 0);
 269 }
 270
 271
 272 /* Find last set bit.   */
 273 bitset_bindex
 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 = %lu, set = {",
 309              (unsigned long) bitset_size (bset));
 310
 311   pos = 30;
 312   BITSET_FOR_EACH (iter, bset, i, 0)
 313   {
 314     if (pos > 70)
 315       {
 316         fprintf (file, "\n");
 317         pos = 0;
 318       }
 319
 320     fprintf (file, "%d ", i);
 321     pos += 1 + (i >= 10) + (i >= 100);
 322   };
 323
 324   if (verbose)
 325     fprintf (file, "}\n");
 326 }
 327
 328
 329 /* Dump bitset BSET to FILE.  */
 330 void
 331 bitset_dump (file, bset)
 332      FILE *file;
 333      bitset bset;
 334 {
 335   bitset_print (file, bset, 0);
 336 }
 337
 338
 339
 340 /* Release memory associated with bitsets.  */
 341 void
 342 bitset_release_memory ()
 343 {
 344   lbitset_release_memory ();
 345   ebitset_release_memory ();
 346 }
 347
 348
 349
 350 /* Toggle bit BITNO in bitset BSET and return non-zero if not set.  */
 351 int
 352 bitset_toggle_ (bset, bitno)
 353     bitset bset;
 354     bitset_bindex bitno;
 355 {
 356   /* This routine is for completeness.  It could be optimized if
 357      required.  */
 358   if (bitset_test (bset, bitno))
 359     {
 360       bitset_reset (bset, bitno);
 361       return 0;
 362     }
 363   else
 364     {
 365       bitset_set (bset, bitno);
 366       return 1;
 367     }
 368 }
 369
 370
 371 /* Return number of bits set in bitset SRC.  */
 372 bitset_bindex
 373 bitset_count_ (src)
 374      bitset src;
 375 {
 376   bitset_bindex list[BITSET_LIST_SIZE];
 377   bitset_bindex next;
 378   bitset_bindex num;
 379   bitset_bindex count;
 380
 381   /* This could be greatly sped up by adding a count method for each
 382      bitset implementation that uses a direct technique (based on
 383      masks) for counting the number of bits set in a word.  */
 384
 385   next = 0;
 386   for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next));
 387        count += num)
 388     continue;
 389
 390   return count;
 391 }
 392
 393
 394 /* DST = SRC.  Return non-zero if DST != SRC.
 395    This is a fallback for the case where SRC and DST are different
 396    bitset types.  */
 397 int
 398 bitset_copy_ (dst, src)
 399      bitset dst;
 400      bitset src;
 401 {
 402   bitset_bindex i;
 403   bitset_iterator iter;
 404
 405   /* Convert bitset types.  We assume that the DST bitset
 406      is large enough to hold the SRC bitset.  */
 407   bitset_zero (dst);
 408   BITSET_FOR_EACH (iter, src, i, 0)
 409   {
 410      bitset_set (dst, i);
 411   };
 412
 413   return 1;
 414 }
 415
 416
 417 /* This is a fallback for implementations that do not support
 418    four operand operations.  */
 419 static inline int
 420 bitset_op4_cmp (dst, src1, src2, src3, op)
 421      bitset dst;
 422      bitset src1;
 423      bitset src2;
 424      bitset src3;
 425      enum bitset_ops op;
 426 {
 427   int changed = 0;
 428   int stats_enabled_save;
 429   bitset tmp;
 430
 431   /* Create temporary bitset.  */
 432   stats_enabled_save = bitset_stats_enabled;
 433   bitset_stats_enabled = 0;
 434   tmp = bitset_alloc (0, bitset_type_get (dst));
 435   bitset_stats_enabled = stats_enabled_save;
 436
 437   switch (op)
 438     {
 439     case BITSET_OP_OR_AND:
 440       bitset_or (tmp, src1, src2);
 441       changed = bitset_and_cmp (dst, src3, tmp);
 442       break;
 443
 444     case BITSET_OP_AND_OR:
 445       bitset_and (tmp, src1, src2);
 446       changed = bitset_or_cmp (dst, src3, tmp);
 447       break;
 448
 449     case BITSET_OP_ANDN_OR:
 450       bitset_andn (tmp, src1, src2);
 451       changed = bitset_or_cmp (dst, src3, tmp);
 452       break;
 453
 454     default:
 455       abort ();
 456     }
 457
 458   bitset_free (tmp);
 459   return changed;
 460 }
 461
 462
 463 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 464    DST != (SRC1 & SRC2) | SRC3.  */
 465 int
 466 bitset_and_or_cmp_ (dst, src1, src2, src3)
 467      bitset dst;
 468      bitset src1;
 469      bitset src2;
 470      bitset src3;
 471 {
 472   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
 473 }
 474
 475
 476 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 477    DST != (SRC1 & ~SRC2) | SRC3.  */
 478 int
 479 bitset_andn_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_ANDN_OR);
 486 }
 487
 488
 489 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 490    DST != (SRC1 | SRC2) & SRC3.  */
 491 int
 492 bitset_or_and_cmp_ (dst, src1, src2, src3)
 493      bitset dst;
 494      bitset src1;
 495      bitset src2;
 496      bitset src3;
 497 {
 498   return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
 499 }
 500
 501
 502 /* Function to be called from debugger to print bitset.  */
 503 void
 504 debug_bitset (bset)
 505      bitset bset;
 506 {
 507   if (bset)
 508     bitset_print (stderr, bset, 1);
 509 }