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] |= ((bitset_word) 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] &= ~((bitset_word) 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] |=                                 \
 158       ((bitset_word) 1 << (_bitno % BITSET_WORD_BITS));         \
 159   else                                                          \
 160     BITSET_SET_ ((bset), _bitno);                               \
 161 } while (0)
 162
 163
 164 /* Reset bit BITNO in bitset BSET.  */
 165 #define bitset_reset(bset, bitno)                               \
 166 do                                                              \
 167 {                                                               \
 168   bitset_bindex _bitno = (bitno);                               \
 169   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 170   bitset_windex _offset = _index - (bset)->b.cindex;            \
 171                                                                 \
 172   if (_offset < (bset)->b.csize)                                        \
 173     (bset)->b.cdata[_offset] &=                                 \
 174       ~((bitset_word) 1 << (_bitno % BITSET_WORD_BITS));        \
 175   else                                                          \
 176     BITSET_RESET_ ((bset), _bitno);                             \
 177 } while (0)
 178
 179
 180 /* Test bit BITNO in bitset BSET.  */
 181 #define bitset_test(bset, bitno) \
 182 (((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
 183   ? (((int)                                                     \
 184       ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
 185        >> ((bitno) % BITSET_WORD_BITS)))                        \
 186      & 1)                                                       \
 187   : BITSET_TEST_ ((bset), (bitno)))
 188 #endif
 189
 190
 191 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 192 extern int bitset_toggle PARAMS ((bitset, bitset_bindex));
 193
 194 /* DST = 0.  */
 195 extern int bitset_zero PARAMS ((bitset));
 196
 197 /* DST = ~0.  */
 198 extern int bitset_ones PARAMS ((bitset));
 199
 200 /* Return non-zero if all bits in bitset SRC are reset.  */
 201 extern int bitset_empty_p PARAMS ((bitset));
 202
 203 /* Return DST == DST | SRC.  */
 204 extern int bitset_subset_p PARAMS ((bitset, bitset));
 205
 206 /* Return DST == SRC.  */
 207 extern int bitset_equal_p PARAMS ((bitset, bitset));
 208
 209 /* Return DST & SRC == 0.  */
 210 extern int bitset_disjoint_p PARAMS ((bitset, bitset));
 211
 212 /* DST == SRC.  */
 213 extern int bitset_copy PARAMS ((bitset, bitset));
 214
 215 /* DST = ~SRC.  */
 216 extern int bitset_not PARAMS ((bitset, bitset));
 217
 218 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 219 extern int bitset_or PARAMS ((bitset, bitset, bitset));
 220
 221 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 222 extern int bitset_and PARAMS ((bitset, bitset, bitset));
 223
 224 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 225 extern int bitset_xor PARAMS ((bitset, bitset, bitset));
 226
 227 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 228 extern int bitset_andn PARAMS ((bitset, bitset, bitset));
 229
 230 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 231    DST != (SRC1 | SRC2) & SRC3.  */
 232 extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
 233
 234 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 235    DST != (SRC1 & SRC2) | SRC3.  */
 236 extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
 237
 238 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 239    DST != (SRC1 & ~SRC2) | SRC3.  */
 240 extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));
 241
 242 /* Find next bit set in BSET starting from and including BITNO.  */
 243 extern int bitset_next PARAMS ((bitset, bitset_bindex));
 244
 245 /* Find previous bit set in BSET starting from and including BITNO.  */
 246 extern int bitset_prev PARAMS ((bitset, bitset_bindex));
 247
 248 /* Return non-zero if BITNO in SRC is the only set bit.  */
 249 extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
 250
 251 /* Find list of up to NUM bits set in BSET starting from and including
 252    *NEXT.  Return with actual number of bits found and with *NEXT
 253    indicating where search stopped.  */
 254 #define bitset_list(BSET, LIST, NUM, NEXT) \
 255 BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 256
 257 /* Find reverse list of up to NUM bits set in BSET starting from and
 258    including NEXT.  Return with actual number of bits found and with
 259    *NEXT indicating where search stopped.  */
 260 #define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
 261 BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT)
 262
 263 /* Find first set bit.  */
 264 extern int bitset_first PARAMS ((bitset));
 265
 266 /* Find last set bit.  */
 267 extern int bitset_last PARAMS ((bitset));
 268
 269 /* Dump bitset.  */
 270 extern void bitset_dump PARAMS ((FILE *, bitset));
 271
 272 /* Loop over all elements of BSET, starting with MIN, setting BIT
 273    to the index of each set bit.  */
 274 #define BITSET_FOR_EACH(ITER, BSET, BIT, MIN)                                 \
 275   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 276        (ITER.num == BITSET_LIST_SIZE)                                         \
 277        && (ITER.num = bitset_list (BSET, ITER.list,                           \
 278                                    BITSET_LIST_SIZE, &ITER.next));)           \
 279     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 280
 281
 282 /* Loop over all elements of BSET, in reverse order starting with
 283    MIN,  setting BIT to the index of each set bit.  */
 284 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN)                         \
 285   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 286        (ITER.num == BITSET_LIST_SIZE)                                         \
 287        && (ITER.num = bitset_list_reverse (BSET, ITER.list,                   \
 288                                           BITSET_LIST_SIZE, &ITER.next));)    \
 289     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 290
 291
 292 /* Define set operations in terms of logical operations.  */
 293
 294 #define bitset_diff(DST, SRC1, SRC2)  bitset_andn (DST, SRC1, SRC2)
 295
 296 #define bitset_intersection(DST, SRC1, SRC2)  bitset_and (DST, SRC1, SRC2)
 297
 298 #define bitset_union(DST, SRC1, SRC2)  bitset_or (DST, SRC1, SRC2)
 299
 300 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 301   bitset_andn_or (DST, SRC1, SRC2, SRC3)
 302
 303
 304 /* Release any memory tied up with bitsets.  */
 305 extern void bitset_release_memory PARAMS ((void));
 306
 307 /* Enable bitset stats gathering.  */
 308 extern void bitset_stats_enable PARAMS ((void));
 309
 310 /* Disable bitset stats gathering.  */
 311 extern void bitset_stats_disable PARAMS ((void));
 312
 313 /* Read bitset stats file of accummulated stats.  */
 314 void bitset_stats_read PARAMS ((const char *filename));
 315
 316 /* Write bitset stats file of accummulated stats.  */
 317 void bitset_stats_write PARAMS ((const char *filename));
 318
 319 /* Dump bitset stats.  */
 320 extern void bitset_stats_dump PARAMS ((FILE *));
 321
 322 /* Function to debug bitset from debugger.  */
 323 extern void debug_bitset PARAMS ((bitset));
 324
 325 /* Function to debug bitset stats from debugger.  */
 326 extern void debug_bitset_stats PARAMS ((void));
 327
 328 #endif /* _BITSET_H  */
 329