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.  */
  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   int num;
  55   int i;
  56 } bitset_iterator;
  57
  58
  59 /* Return bytes required for bitset of desired type and size.  */
  60 extern int 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 size in bits of bitset SRC.  */
  88 extern int bitset_size PARAMS ((bitset));
  89
  90 /* Return number of bits set in bitset SRC.  */
  91 extern int bitset_count PARAMS ((bitset));
  92
  93 /* Return bitset type.  */
  94 extern enum bitset_type bitset_type_get PARAMS ((bitset));
  95
  96 #if BITSET_INLINE
  97 static inline void bitset_set PARAMS ((bitset, bitset_bindex));
  98 static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
  99 static inline int bitset_test PARAMS ((bitset, bitset_bindex));
 100
 101 /* Set bit BITNO in bitset BSET.  */
 102 static inline void bitset_set (bset, bitno)
 103     bitset bset;
 104     bitset_bindex bitno;
 105 {
 106   bitset_windex index = bitno / BITSET_WORD_BITS;
 107   bitset_windex offset = index - bset->b.cindex;
 108
 109   if (offset < bset->b.csize)
 110     bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
 111   else
 112     BITSET_SET_ (bset, bitno);
 113 }
 114
 115
 116 /* Reset bit BITNO in bitset BSET.  */
 117 static inline void bitset_reset (bset, bitno)
 118     bitset bset;
 119     bitset_bindex bitno;
 120 {
 121   bitset_windex index = bitno / BITSET_WORD_BITS;
 122   bitset_windex offset = index - bset->b.cindex;
 123
 124   if (offset < bset->b.csize)
 125     bset->b.cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
 126   else
 127     BITSET_RESET_ (bset, bitno);
 128 }
 129
 130
 131 /* Test bit BITNO in bitset BSET.  */
 132 static inline int bitset_test (bset, bitno)
 133     bitset bset;
 134     bitset_bindex bitno;
 135 {
 136   bitset_windex index = bitno / BITSET_WORD_BITS;
 137   bitset_windex offset = index - bset->b.cindex;
 138
 139   if (offset < bset->b.csize)
 140     return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
 141   else
 142     return BITSET_TEST_ (bset, bitno);
 143 }
 144 #endif
 145
 146 #if ! BITSET_INLINE
 147
 148 /* Set bit BITNO in bitset BSET.  */
 149 #define bitset_set(bset, bitno)                                 \
 150 do                                                              \
 151 {                                                               \
 152   bitset_bindex _bitno = (bitno);                               \
 153   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 154   bitset_windex _offset = _index - (bset)->b.cindex;            \
 155                                                                 \
 156   if (_offset < (bset)->b.csize)                                        \
 157     (bset)->b.cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS));     \
 158   else                                                          \
 159     BITSET_SET_ ((bset), _bitno);                               \
 160 } while (0)
 161
 162
 163 /* Reset bit BITNO in bitset BSET.  */
 164 #define bitset_reset(bset, bitno)                               \
 165 do                                                              \
 166 {                                                               \
 167   bitset_bindex _bitno = (bitno);                               \
 168   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 169   bitset_windex _offset = _index - (bset)->b.cindex;            \
 170                                                                 \
 171   if (_offset < (bset)->b.csize)                                        \
 172     (bset)->b.cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS));    \
 173   else                                                          \
 174     BITSET_RESET_ ((bset), _bitno);                             \
 175 } while (0)
 176
 177
 178 /* Test bit BITNO in bitset BSET.  */
 179 #define bitset_test(bset, bitno) \
 180 (((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
 181   ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
 182      >> ((bitno) % BITSET_WORD_BITS)) & 1 \
 183   : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
 184 #endif
 185
 186
 187 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 188 extern int bitset_toggle PARAMS ((bitset, bitset_bindex));
 189
 190 /* DST = 0.  */
 191 extern int bitset_zero PARAMS ((bitset));
 192
 193 /* DST = ~0.  */
 194 extern int bitset_ones PARAMS ((bitset));
 195
 196 /* Return non-zero if all bits in bitset SRC are reset.  */
 197 extern int bitset_empty_p PARAMS ((bitset));
 198
 199 /* Return DST == DST | SRC.  */
 200 extern int bitset_subset_p PARAMS ((bitset, bitset));
 201
 202 /* Return DST == SRC.  */
 203 extern int bitset_equal_p PARAMS ((bitset, bitset));
 204
 205 /* Return DST & SRC == 0.  */
 206 extern int bitset_disjoint_p PARAMS ((bitset, bitset));
 207
 208 /* DST == SRC.  */
 209 extern int bitset_copy PARAMS ((bitset, bitset));
 210
 211 /* DST = ~SRC.  */
 212 extern int bitset_not PARAMS ((bitset, bitset));
 213
 214 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 215 extern int bitset_or PARAMS ((bitset, bitset, bitset));
 216
 217 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 218 extern int bitset_and PARAMS ((bitset, bitset, bitset));
 219
 220 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 221 extern int bitset_xor PARAMS ((bitset, bitset, bitset));
 222
 223 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 224 extern int bitset_andn PARAMS ((bitset, bitset, bitset));
 225
 226 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 227    DST != (SRC1 | SRC2) & SRC3.  */
 228 extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
 229
 230 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 231    DST != (SRC1 & SRC2) | SRC3.  */
 232 extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
 233
 234 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 235    DST != (SRC1 & ~SRC2) | SRC3.  */
 236 extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));
 237
 238 /* Find next bit set in BSET starting from and including BITNO.  */
 239 extern int bitset_next PARAMS ((bitset, bitset_bindex));
 240
 241 /* Find previous bit set in BSET starting from and including BITNO.  */
 242 extern int bitset_prev PARAMS ((bitset, bitset_bindex));
 243
 244 /* Return non-zero if BITNO in SRC is the only set bit.  */
 245 extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
 246
 247 /* Find list of up to NUM bits set in BSET starting from and including
 248    *NEXT.  Return with actual number of bits found and with *NEXT
 249    indicating where search stopped.  */
 250 #define bitset_list(BSET, LIST, NUM, NEXT) \
 251 BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 252
 253 /* Find reverse list of up to NUM bits set in BSET starting from and
 254    including NEXT.  Return with actual number of bits found and with
 255    *NEXT indicating where search stopped.  */
 256 #define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
 257 BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT)
 258
 259 /* Find first set bit.  */
 260 extern int bitset_first PARAMS ((bitset));
 261
 262 /* Find last set bit.  */
 263 extern int bitset_last PARAMS ((bitset));
 264
 265 /* Dump bitset.  */
 266 extern void bitset_dump PARAMS ((FILE *, bitset));
 267
 268 /* Loop over all elements of BSET, starting with MIN, setting BIT
 269    to the index of each set bit.  */
 270 #define BITSET_FOR_EACH(ITER, BSET, BIT, MIN)                                 \
 271   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 272        (ITER.num == BITSET_LIST_SIZE)                                         \
 273        && (ITER.num = bitset_list (BSET, ITER.list,                           \
 274                                    BITSET_LIST_SIZE, &ITER.next));)           \
 275     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 276
 277
 278 /* Loop over all elements of BSET, in reverse order starting with
 279    MIN,  setting BIT to the index of each set bit.  */
 280 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN)                         \
 281   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 282        (ITER.num == BITSET_LIST_SIZE)                                         \
 283        && (ITER.num = bitset_list_reverse (BSET, ITER.list,                   \
 284                                           BITSET_LIST_SIZE, &ITER.next));)    \
 285     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 286
 287
 288 /* Define set operations in terms of logical operations.  */
 289
 290 #define bitset_diff(DST, SRC1, SRC2)  bitset_andn (DST, SRC1, SRC2)
 291
 292 #define bitset_intersection(DST, SRC1, SRC2)  bitset_and (DST, SRC1, SRC2)
 293
 294 #define bitset_union(DST, SRC1, SRC2)  bitset_or (DST, SRC1, SRC2)
 295
 296 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 297   bitset_andn_or (DST, SRC1, SRC2, SRC3)
 298
 299
 300 /* Release any memory tied up with bitsets.  */
 301 extern void bitset_release_memory PARAMS ((void));
 302
 303 /* Enable bitset stats gathering.  */
 304 extern void bitset_stats_enable PARAMS ((void));
 305
 306 /* Disable bitset stats gathering.  */
 307 extern void bitset_stats_disable PARAMS ((void));
 308
 309 /* Read bitset stats file of accummulated stats.  */
 310 void bitset_stats_read PARAMS ((const char *filename));
 311
 312 /* Write bitset stats file of accummulated stats.  */
 313 void bitset_stats_write PARAMS ((const char *filename));
 314
 315 /* Dump bitset stats.  */
 316 extern void bitset_stats_dump PARAMS ((FILE *));
 317
 318 /* Function to debug bitset from debugger.  */
 319 extern void debug_bitset PARAMS ((bitset));
 320
 321 /* Function to debug bitset stats from debugger.  */
 322 extern void debug_bitset_stats PARAMS ((void));
 323
 324 #endif /* _BITSET_H  */
 325