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