lib/bitset.h

   1 /* Generic bitsets.
   2    Copyright (C) 2002-2004, 2009-2010 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 3 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, see <http://www.gnu.org/licenses/>.  */
  17
  18 #ifndef _BITSET_H
  19 #define _BITSET_H
  20
  21 /* This file is the public interface to the bitset abstract data type.
  22    Only use the functions and macros defined in this file.  */
  23
  24 #include "bbitset.h"
  25 #include "obstack.h"
  26 #include <stdio.h>
  27
  28 #if USE_UNLOCKED_IO
  29 # include "unlocked-io.h"
  30 #endif
  31
  32 /* Attributes used to select a bitset implementation.  */
  33 enum bitset_attr {BITSET_FIXED = 1,    /* Bitset size fixed.  */
  34                   BITSET_VARIABLE = 2, /* Bitset size variable.  */
  35                   BITSET_DENSE = 4,    /* Bitset dense.  */
  36                   BITSET_SPARSE = 8,   /* Bitset sparse.  */
  37                   BITSET_FRUGAL = 16,  /* Prefer most compact.  */
  38                   BITSET_GREEDY = 32}; /* Prefer fastest at memory expense.  */
  39
  40 typedef unsigned int bitset_attrs;
  41
  42 /* The contents of the union should be considered to be private.
  43    While I would like to make this union opaque, it needs to be
  44    visible for the inline bit set/test functions, and for delegation
  45    to the proper implementation.  */
  46 union bitset_union
  47 {
  48   /* This must be the first member of every other structure that is a
  49      member of this union.  */
  50   struct bbitset_struct b;              /* Base bitset data.  */
  51
  52   struct abitset_struct
  53   {
  54     struct bbitset_struct b;
  55     bitset_word words[1];               /* The array of bits.  */
  56   } a;
  57
  58   struct ebitset_struct
  59   {
  60     struct bbitset_struct b;
  61     bitset_windex size;                 /* Number of elements.  */
  62     struct ebitset_elt_struct **elts;   /* Expanding array of ptrs to elts.  */
  63   } e;
  64
  65   struct lbitset_struct
  66   {
  67     struct bbitset_struct b;
  68     struct lbitset_elt_struct *head;    /* First element in linked list.  */
  69     struct lbitset_elt_struct *tail;    /* Last element in linked list.  */
  70   } l;
  71
  72   struct bitset_stats_struct
  73   {
  74     struct bbitset_struct b;
  75     bitset bset;
  76   } s;
  77
  78   struct vbitset_struct
  79   {
  80     struct bbitset_struct b;
  81     bitset_windex size;                 /* Allocated size of array.  */
  82   } v;
  83
  84 };
  85
  86
  87 /* The contents of this structure should be considered private.
  88    It is used for iterating over set bits.  */
  89 typedef struct
  90 {
  91   bitset_bindex list[BITSET_LIST_SIZE];
  92   bitset_bindex next;
  93   bitset_bindex num;
  94   bitset_bindex i;
  95 } bitset_iterator;
  96
  97
  98 /* Return bytes required for bitset of desired type and size.  */
  99 extern size_t bitset_bytes (enum bitset_type, bitset_bindex);
 100
 101 /* Initialise a bitset with desired type and size.  */
 102 extern bitset bitset_init (bitset, bitset_bindex, enum bitset_type);
 103
 104 /* Select an implementation type based on the desired bitset size
 105    and attributes.  */
 106 extern enum bitset_type bitset_type_choose (bitset_bindex, bitset_attrs);
 107
 108 /* Create a bitset of desired type and size.  The bitset is zeroed.  */
 109 extern bitset bitset_alloc (bitset_bindex, enum bitset_type);
 110
 111 /* Free bitset.  */
 112 extern void bitset_free (bitset);
 113
 114 /* Create a bitset of desired type and size using an obstack.  The
 115    bitset is zeroed.  */
 116 extern bitset bitset_obstack_alloc (struct obstack *bobstack,
 117                                     bitset_bindex, enum bitset_type);
 118
 119 /* Free bitset allocated on obstack.  */
 120 extern void bitset_obstack_free (bitset);
 121
 122 /* Create a bitset of desired size and attributes.  The bitset is zeroed.  */
 123 extern bitset bitset_create (bitset_bindex, bitset_attrs);
 124
 125 /* Return bitset type.  */
 126 extern enum bitset_type bitset_type_get (bitset);
 127
 128 /* Return bitset type name.  */
 129 extern const char *bitset_type_name_get (bitset);
 130
 131
 132 /* Set bit BITNO in bitset BSET.  */
 133 static inline void
 134 bitset_set (bitset bset, bitset_bindex bitno)
 135 {
 136   bitset_windex windex = bitno / BITSET_WORD_BITS;
 137   bitset_windex offset = windex - bset->b.cindex;
 138
 139   if (offset < bset->b.csize)
 140     bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 141   else
 142     BITSET_SET_ (bset, bitno);
 143 }
 144
 145
 146 /* Reset bit BITNO in bitset BSET.  */
 147 static inline void
 148 bitset_reset (bitset bset, bitset_bindex bitno)
 149 {
 150   bitset_windex windex = bitno / BITSET_WORD_BITS;
 151   bitset_windex offset = windex - bset->b.cindex;
 152
 153   if (offset < bset->b.csize)
 154     bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 155   else
 156     BITSET_RESET_ (bset, bitno);
 157 }
 158
 159
 160 /* Test bit BITNO in bitset BSET.  */
 161 static inline bool
 162 bitset_test (bitset bset, bitset_bindex bitno)
 163 {
 164   bitset_windex windex = bitno / BITSET_WORD_BITS;
 165   bitset_windex offset = windex - bset->b.cindex;
 166
 167   if (offset < bset->b.csize)
 168     return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
 169   else
 170     return BITSET_TEST_ (bset, bitno);
 171 }
 172
 173
 174 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 175 #define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
 176
 177 /* Return size in bits of bitset SRC.  */
 178 #define bitset_size(SRC) BITSET_SIZE_ (SRC)
 179
 180 /* Change size of bitset.  */
 181 extern void bitset_resize (bitset, bitset_bindex);
 182
 183 /* Return number of bits set in bitset SRC.  */
 184 #define bitset_count(SRC) BITSET_COUNT_ (SRC)
 185
 186
 187 /* Return SRC == 0.  */
 188 #define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
 189
 190 /* DST = ~0.  */
 191 #define bitset_ones(DST) BITSET_ONES_ (DST)
 192
 193 /* DST = 0.  */
 194 #define bitset_zero(DST) BITSET_ZERO_ (DST)
 195
 196
 197
 198 /* DST = SRC.  */
 199 #define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
 200
 201 /* Return DST & SRC == 0.  */
 202 #define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
 203
 204 /* Return DST == SRC.  */
 205 #define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
 206
 207 /* DST = ~SRC.  */
 208 #define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
 209
 210 /* Return DST == DST | SRC.  */
 211 #define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
 212
 213
 214
 215 /* DST = SRC1 & SRC2.  */
 216 #define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
 217
 218 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 219 #define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
 220
 221 /* DST = SRC1 & ~SRC2.  */
 222 #define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
 223
 224 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 225 #define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
 226
 227 /* DST = SRC1 | SRC2.  */
 228 #define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
 229
 230 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 231 #define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
 232
 233 /* DST = SRC1 ^ SRC2.  */
 234 #define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
 235
 236 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 237 #define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
 238
 239
 240
 241 /* DST = (SRC1 & SRC2) | SRC3.  */
 242 #define bitset_and_or(DST, SRC1, SRC2, SRC3) \
 243  BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
 244
 245 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 246    DST != (SRC1 & SRC2) | SRC3.  */
 247 #define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
 248  BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 249
 250 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 251 #define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
 252  BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
 253
 254 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 255    DST != (SRC1 & ~SRC2) | SRC3.  */
 256 #define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
 257  BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 258
 259 /* DST = (SRC1 | SRC2) & SRC3.  */
 260 #define bitset_or_and(DST, SRC1, SRC2, SRC3)\
 261  BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
 262
 263 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 264    DST != (SRC1 | SRC2) & SRC3.  */
 265 #define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
 266  BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
 267
 268 /* Find list of up to NUM bits set in BSET starting from and including
 269    *NEXT.  Return with actual number of bits found and with *NEXT
 270    indicating where search stopped.  */
 271 #define bitset_list(BSET, LIST, NUM, NEXT) \
 272  BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 273
 274 /* Find reverse list of up to NUM bits set in BSET starting from and
 275    including NEXT.  Return with actual number of bits found and with
 276    *NEXT indicating where search stopped.  */
 277 #define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
 278  BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
 279
 280 /* Return true if both bitsets are of the same type and size.  */
 281 extern bool bitset_compatible_p (bitset bset1, bitset bset2);
 282
 283 /* Find next set bit from the given bit index.  */
 284 extern bitset_bindex bitset_next (bitset, bitset_bindex);
 285
 286 /* Find previous set bit from the given bit index.  */
 287 extern bitset_bindex bitset_prev (bitset, bitset_bindex);
 288
 289 /* Find first set bit.  */
 290 extern bitset_bindex bitset_first (bitset);
 291
 292 /* Find last set bit.  */
 293 extern bitset_bindex bitset_last (bitset);
 294
 295 /* Return nonzero if this is the only set bit.  */
 296 extern bool bitset_only_set_p (bitset, bitset_bindex);
 297
 298 /* Dump bitset.  */
 299 extern void bitset_dump (FILE *, bitset);
 300
 301 /* Loop over all elements of BSET, starting with MIN, setting INDEX
 302    to the index of each set bit.  For example, the following will print
 303    the bits set in a bitset:
 304
 305    bitset_bindex i;
 306    bitset_iterator iter;
 307
 308    BITSET_FOR_EACH (iter, src, i, 0)
 309    {
 310       printf ("%lu ", (unsigned long int) i);
 311    };
 312 */
 313 #define BITSET_FOR_EACH(ITER, BSET, INDEX, MIN)                               \
 314   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 315        (ITER.num == BITSET_LIST_SIZE)                                         \
 316        && (ITER.num = bitset_list (BSET, ITER.list,                           \
 317                                    BITSET_LIST_SIZE, &ITER.next));)           \
 318     for (ITER.i = 0;                                                          \
 319          ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1);               \
 320          ITER.i++)
 321
 322
 323 /* Loop over all elements of BSET, in reverse order starting with
 324    MIN, setting INDEX to the index of each set bit.  For example, the
 325    following will print the bits set in a bitset in reverse order:
 326
 327    bitset_bindex i;
 328    bitset_iterator iter;
 329
 330    BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
 331    {
 332       printf ("%lu ", (unsigned long int) i);
 333    };
 334 */
 335 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, MIN)                       \
 336   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 337        (ITER.num == BITSET_LIST_SIZE)                                         \
 338        && (ITER.num = bitset_list_reverse (BSET, ITER.list,                   \
 339                                            BITSET_LIST_SIZE, &ITER.next));)   \
 340     for (ITER.i = 0;                                                          \
 341          ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1);               \
 342          ITER.i++)
 343
 344
 345 /* Define set operations in terms of logical operations.  */
 346
 347 #define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
 348 #define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
 349
 350 #define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
 351 #define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
 352
 353 #define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
 354 #define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
 355
 356 /* Symmetrical difference.  */
 357 #define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
 358 #define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
 359
 360 /* Union of difference.  */
 361 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 362   bitset_andn_or (DST, SRC1, SRC2, SRC3)
 363 #define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
 364   bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
 365
 366
 367 /* Release any memory tied up with bitsets.  */
 368 extern void bitset_release_memory (void);
 369
 370 /* Enable bitset stats gathering.  */
 371 extern void bitset_stats_enable (void);
 372
 373 /* Disable bitset stats gathering.  */
 374 extern void bitset_stats_disable (void);
 375
 376 /* Read bitset stats file of accummulated stats.  */
 377 void bitset_stats_read (const char *file_name);
 378
 379 /* Write bitset stats file of accummulated stats.  */
 380 void bitset_stats_write (const char *file_name);
 381
 382 /* Dump bitset stats.  */
 383 extern void bitset_stats_dump (FILE *);
 384
 385 /* Function to debug bitset from debugger.  */
 386 extern void debug_bitset (bitset);
 387
 388 /* Function to debug bitset stats from debugger.  */
 389 extern void debug_bitset_stats (void);
 390
 391 #endif /* _BITSET_H  */