lib/bitset.h

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