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] &= ~(1 << (_bitno % BITSET_WORD_BITS));    \
 171   else                                                          \
 172     BITSET_RESET_ ((bset), _bitno);                             \
 173 } while (0)
 174
 175
 176 /* Test bit BITNO in bitset BSET.  */
 177 #define bitset_test(bset, bitno) \
 178 (((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize)  \
 179   ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
 180      >> ((bitno) % BITSET_WORD_BITS)) & 1 \
 181   : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
 182 #endif
 183
 184
 185 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 186 #define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
 187
 188 /* Return size in bits of bitset SRC.  */
 189 #define bitset_size(SRC) BITSET_SIZE_ (SRC)
 190
 191 /* Return number of bits set in bitset SRC.  */
 192 #define bitset_count(SRC) BITSET_COUNT_ (SRC)
 193
 194
 195 /* Return SRC == 0.  */
 196 #define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
 197
 198 /* DST = ~0.  */
 199 #define bitset_ones(DST) BITSET_ONES_ (DST)
 200
 201 /* DST = 0.  */
 202 #define bitset_zero(DST) BITSET_ZERO_ (DST)
 203
 204
 205
 206 /* DST = SRC.  */
 207 #define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
 208
 209 /* Return DST & SRC == 0.  */
 210 #define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
 211
 212 /* Return DST == SRC.  */
 213 #define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
 214
 215 /* DST = ~SRC.  */
 216 #define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
 217
 218 /* Return DST == DST | SRC.  */
 219 #define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
 220
 221
 222
 223 /* DST = SRC1 & SRC2.  */
 224 #define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
 225
 226 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 227 #define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
 228
 229 /* DST = SRC1 & ~SRC2.  */
 230 #define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
 231
 232 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 233 #define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
 234
 235 /* DST = SRC1 | SRC2.  */
 236 #define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
 237
 238 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 239 #define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
 240
 241 /* DST = SRC1 ^ SRC2.  */
 242 #define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
 243
 244 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 245 #define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
 246
 247
 248
 249 /* DST = (SRC1 & SRC2) | SRC3.  */
 250 #define bitset_and_or(DST, SRC1, SRC2, SRC3) \
 251  BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
 252
 253 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 254    DST != (SRC1 & SRC2) | SRC3.  */
 255 #define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
 256  BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 257
 258 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 259 #define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
 260  BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
 261
 262 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 263    DST != (SRC1 & ~SRC2) | SRC3.  */
 264 #define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
 265  BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 266
 267 /* DST = (SRC1 | SRC2) & SRC3.  */
 268 #define bitset_or_and(DST, SRC1, SRC2, SRC3)\
 269  BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
 270
 271 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 272    DST != (SRC1 | SRC2) & SRC3.  */
 273 #define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
 274  BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
 275
 276 /* Find list of up to NUM bits set in BSET starting from and including
 277    *NEXT.  Return with actual number of bits found and with *NEXT
 278    indicating where search stopped.  */
 279 #define bitset_list(BSET, LIST, NUM, NEXT) \
 280  BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 281
 282 /* Find reverse list of up to NUM bits set in BSET starting from and
 283    including NEXT.  Return with actual number of bits found and with
 284    *NEXT indicating where search stopped.  */
 285 #define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
 286  BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
 287
 288
 289 /* Find first set bit.  */
 290 extern bitset_bindex bitset_first PARAMS ((bitset));
 291
 292 /* Find last set bit.  */
 293 extern bitset_bindex bitset_last PARAMS ((bitset));
 294
 295 /* Dump bitset.  */
 296 extern void bitset_dump PARAMS ((FILE *, bitset));
 297
 298 /* Loop over all elements of BSET, starting with MIN, setting BIT
 299    to the index of each set bit.  For example, the following will print
 300    the bits set in a bitset:
 301
 302    bitset_bindex i;
 303    bitset_iterator iter;
 304
 305    bitset_zero (dst);
 306    BITSET_FOR_EACH (iter, src, i, 0)
 307    {
 308       printf ("%ld ", i);
 309    };
 310 */
 311 #define BITSET_FOR_EACH(ITER, BSET, BIT, MIN)                                 \
 312   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 313        (ITER.num == BITSET_LIST_SIZE)                                         \
 314        && (ITER.num = bitset_list (BSET, ITER.list,                           \
 315                                    BITSET_LIST_SIZE, &ITER.next));)           \
 316     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 317
 318
 319 /* Loop over all elements of BSET, in reverse order starting with
 320    MIN,  setting BIT to the index of each set bit. For example, the
 321    following will print the bits set in a bitset in reverse order:
 322
 323    bitset_bindex i;
 324    bitset_iterator iter;
 325
 326    bitset_zero (dst);
 327    BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
 328    {
 329       printf ("%ld ", i);
 330    };
 331 */
 332 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN)                         \
 333   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 334        (ITER.num == BITSET_LIST_SIZE)                                         \
 335        && (ITER.num = bitset_list_reverse (BSET, ITER.list,                   \
 336                                           BITSET_LIST_SIZE, &ITER.next));)    \
 337     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 338
 339
 340 /* Define set operations in terms of logical operations.  */
 341
 342 #define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
 343 #define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
 344
 345 #define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
 346 #define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
 347
 348 #define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
 349 #define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
 350
 351 /* Symmetrical difference.  */
 352 #define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
 353 #define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
 354
 355 /* Union of difference.  */
 356 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 357   bitset_andn_or (DST, SRC1, SRC2, SRC3)
 358 #define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
 359   bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
 360
 361
 362
 363 /* Release any memory tied up with bitsets.  */
 364 extern void bitset_release_memory PARAMS ((void));
 365
 366 /* Enable bitset stats gathering.  */
 367 extern void bitset_stats_enable PARAMS ((void));
 368
 369 /* Disable bitset stats gathering.  */
 370 extern void bitset_stats_disable PARAMS ((void));
 371
 372 /* Read bitset stats file of accummulated stats.  */
 373 void bitset_stats_read PARAMS ((const char *filename));
 374
 375 /* Write bitset stats file of accummulated stats.  */
 376 void bitset_stats_write PARAMS ((const char *filename));
 377
 378 /* Dump bitset stats.  */
 379 extern void bitset_stats_dump PARAMS ((FILE *));
 380
 381 /* Function to debug bitset from debugger.  */
 382 extern void debug_bitset PARAMS ((bitset));
 383
 384 /* Function to debug bitset stats from debugger.  */
 385 extern void debug_bitset_stats PARAMS ((void));
 386
 387 #endif /* _BITSET_H  */
 388