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 /* Return bytes required for bitset of desired type and size.  */
  48 extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
  49
  50 /* Initialise a bitset with desired type and size.  */
  51 extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
  52
  53 /* Select an implementation type based on the desired bitset size
  54    and attributes.  */
  55 extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
  56                                                     bitset_attrs));
  57
  58 /* Create a bitset of desired type and size.  The bitset is zeroed.  */
  59 extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
  60
  61 /* Free bitset.  */
  62 extern void bitset_free PARAMS ((bitset));
  63
  64 /* Create a bitset of desired type and size using an obstack.  The
  65    bitset is zeroed.  */
  66 extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
  67                                             bitset_bindex, enum bitset_type));
  68
  69 /* Free bitset allocated on obstack.  */
  70 extern void bitset_obstack_free PARAMS ((bitset));
  71
  72 /* Create a bitset of desired size and attributes.  The bitset is zeroed.  */
  73 extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
  74
  75 /* Return size in bits of bitset SRC.  */
  76 extern int bitset_size PARAMS ((bitset));
  77
  78 /* Return number of bits set in bitset SRC.  */
  79 extern int bitset_count PARAMS ((bitset));
  80
  81 #if BITSET_CACHE && BITSET_INLINE
  82 static inline void bitset_set PARAMS ((bitset, bitset_bindex));
  83 static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
  84 static inline int bitset_test PARAMS ((bitset, bitset_bindex));
  85
  86 /* Set bit BITNO in bitset BSET.  */
  87 static inline void bitset_set (bset, bitno)
  88     bitset bset;
  89     bitset_bindex bitno;
  90 {
  91   bitset_windex index = bitno / BITSET_WORD_BITS;
  92   bitset_windex offset = index - bset->b.cindex;
  93
  94   if (offset < bset->b.csize)
  95     bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
  96   else
  97     BITSET_SET_ (bset, bitno);
  98 }
  99
 100
 101 /* Reset bit BITNO in bitset BSET.  */
 102 static inline void bitset_reset (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_RESET_ (bset, bitno);
 113 }
 114
 115
 116 /* Test bit BITNO in bitset BSET.  */
 117 static inline int bitset_test (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     return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
 126   else
 127     return BITSET_TEST_ (bset, bitno);
 128 }
 129 #endif
 130
 131 #if BITSET_CACHE && ! BITSET_INLINE
 132
 133 /* Set bit BITNO in bitset BSET.  */
 134 #define bitset_set(bset, bitno)                                 \
 135 do                                                              \
 136 {                                                               \
 137   bitset_bindex _bitno = (bitno);                               \
 138   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 139   bitset_windex _offset = _index - (bset)->b.cindex;            \
 140                                                                 \
 141   if (_offset < (bset)->b.csize)                                        \
 142     (bset)->b.cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS));     \
 143   else                                                          \
 144     BITSET_SET_ ((bset), _bitno);                               \
 145 } while (0)
 146
 147
 148 /* Reset bit BITNO in bitset BSET.  */
 149 #define bitset_reset(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_RESET_ ((bset), _bitno);                             \
 160 } while (0)
 161
 162
 163 /* Test bit BITNO in bitset BSET.  */
 164 #define bitset_test(bset, bitno) \
 165 (((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
 166   ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
 167      >> ((bitno) % BITSET_WORD_BITS)) & 1 \
 168   : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
 169 #endif
 170
 171 #if ! BITSET_CACHE
 172 /* Set bit BITNO in bitset SRC.  */
 173 #define bitset_set(SRC, BITNO) BITSET_SET_ (SRC, BITNO)
 174
 175 /* Reset bit BITNO in bitset SRC.  */
 176 #define bitset_reset(SRC, BITNO) BITSET_RESET_ (SRC, BITNO)
 177
 178 /* Return non-zero if bit BITNO in bitset SRC is set.  */
 179 #define bitset_test(SRC, BITNO) BITSET_TEST_ (SRC, BITNO)
 180 #endif
 181
 182 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 183 extern int bitset_toggle PARAMS ((bitset, bitset_bindex));
 184
 185 /* DST = 0.  */
 186 extern int bitset_zero PARAMS ((bitset));
 187
 188 /* DST = ~0.  */
 189 extern int bitset_ones PARAMS ((bitset));
 190
 191 /* Return non-zero if all bits in bitset SRC are reset.  */
 192 extern int bitset_empty_p PARAMS ((bitset));
 193
 194 /* Return DST == DST | SRC.  */
 195 extern int bitset_subset_p PARAMS ((bitset, bitset));
 196
 197 /* Return DST == SRC.  */
 198 extern int bitset_equal_p PARAMS ((bitset, bitset));
 199
 200 /* Return DST & SRC == 0.  */
 201 extern int bitset_disjoint_p PARAMS ((bitset, bitset));
 202
 203 /* DST == SRC.  */
 204 extern int bitset_copy PARAMS ((bitset, bitset));
 205
 206 /* DST = ~SRC.  */
 207 extern int bitset_not PARAMS ((bitset, bitset));
 208
 209 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 210 extern int bitset_or PARAMS ((bitset, bitset, bitset));
 211
 212 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 213 extern int bitset_and PARAMS ((bitset, bitset, bitset));
 214
 215 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 216 extern int bitset_xor PARAMS ((bitset, bitset, bitset));
 217
 218 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 219 extern int bitset_andn PARAMS ((bitset, bitset, bitset));
 220
 221 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 222    DST != (SRC1 | SRC2) & SRC3.  */
 223 extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
 224
 225 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 226    DST != (SRC1 & SRC2) | SRC3.  */
 227 extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
 228
 229 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 230    DST != (SRC1 & ~SRC2) | SRC3.  */
 231 extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));
 232
 233 /* Find next bit set in BSET starting from and including BITNO.  */
 234 extern int bitset_next PARAMS ((bitset, bitset_bindex));
 235
 236 /* Find previous bit set in BSET starting from and including BITNO.  */
 237 extern int bitset_prev PARAMS ((bitset, bitset_bindex));
 238
 239 /* Return non-zero if BITNO in SRC is the only set bit.  */
 240 extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
 241
 242 /* Find list of up to NUM bits set in BSET starting from and including
 243    *NEXT.  Return with actual number of bits found and with *NEXT
 244    indicating where search stopped.  */
 245 #if BITSET_STATS
 246 extern int bitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
 247                                 bitset_bindex *));
 248 #else
 249 #define bitset_list(BSET, LIST, NUM, NEXT) \
 250 BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 251 #endif
 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, executing CODE.  */
 269 #define BITSET_EXECUTE(BSET, MIN, N, CODE)                              \
 270 do {                                                                    \
 271   bitset_bindex _list[BITSET_LIST_SIZE];                                \
 272   bitset_bindex _next = (MIN);                                          \
 273   int _num;                                                             \
 274                                                                         \
 275   while ((_num = bitset_list ((BSET), _list, BITSET_LIST_SIZE, &_next)))\
 276     {                                                                   \
 277        int _i;                                                          \
 278                                                                         \
 279        for (_i = 0; _i < _num; _i++)                                    \
 280          {                                                              \
 281             (N) = _list[_i];                                            \
 282             CODE;                                                       \
 283          }                                                              \
 284        if (_num < BITSET_LIST_SIZE)                                     \
 285          break;                                                         \
 286     }                                                                   \
 287 } while (0)
 288
 289
 290 /* Loop over all elements of BSET, in reverse order starting with
 291    MIN, executing CODE.  */
 292 #define BITSET_REVERSE_EXECUTE(BSET, MIN, N, CODE)                      \
 293 do {                                                                    \
 294   bitset_bindex _list[BITSET_LIST_SIZE];                                \
 295   bitset_bindex _next = (MIN);                                          \
 296   int _num;                                                             \
 297                                                                         \
 298   while ((_num = bitset_reverse_list ((BSET), _list,                    \
 299                                       BITSET_LIST_SIZE, &_next)))       \
 300     {                                                                   \
 301        int _i;                                                          \
 302                                                                         \
 303        for (_i = 0; _i < _num; _i++)                                    \
 304          {                                                              \
 305             (N) = _list[_i];                                            \
 306             CODE;                                                       \
 307          }                                                              \
 308        if (_num < BITSET_LIST_SIZE)                                     \
 309          break;                                                         \
 310     }                                                                   \
 311 } while (0)
 312
 313
 314 /* Define set operations in terms of logical operations.  */
 315
 316 #define bitset_diff(DST, SRC1, SRC2)  bitset_andn (DST, SRC1, SRC2)
 317
 318 #define bitset_intersection(DST, SRC1, SRC2)  bitset_and (DST, SRC1, SRC2)
 319
 320 #define bitset_union(DST, SRC1, SRC2)  bitset_or (DST, SRC1, SRC2)
 321
 322 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 323   bitset_andn_or (DST, SRC1, SRC2, SRC3)
 324
 325
 326 /* Release any memory tied up with bitsets.  */
 327 extern void bitset_release_memory PARAMS ((void));
 328
 329 /* Initialise bitset stats.  */
 330 extern void bitset_stats_init PARAMS ((void));
 331
 332 /* Dump bitset stats.  */
 333 extern void bitset_stats_dump PARAMS ((FILE *));
 334
 335 /* Function to debug bitset from debugger.  */
 336 extern void debug_bitset PARAMS ((bitset));
 337
 338 /* Function to debug bitset stats from debugger.  */
 339 extern void debug_bitset_stats PARAMS ((void));
 340
 341 #endif /* _BITSET_H  */