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 #if HAVE_CONFIG_H
  23 # include <config.h>
  24 #endif
  25
  26 #define BITSET_STATS 1
  27
  28 # ifndef PARAMS
  29 #  if defined PROTOTYPES || (defined __STDC__ && __STDC__)
  30 #   define PARAMS(Args) Args
  31 #  else
  32 #   define PARAMS(Args) ()
  33 #  endif
  34 # endif
  35
  36 # ifndef __attribute__
  37 #  if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
  38 #   define __attribute__(x)
  39 #  endif
  40 # endif
  41
  42 # ifndef ATTRIBUTE_NORETURN
  43 #  define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
  44 # endif
  45
  46 # ifndef ATTRIBUTE_UNUSED
  47 #  define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
  48 # endif
  49
  50 #include "bitset-int.h"
  51 #include "sbitset.h"
  52 #include "lbitset.h"
  53 #include "ebitset.h"
  54 #include "obstack.h"
  55 #include <stdio.h>
  56 #include "xalloc.h"
  57
  58 enum bitset_attr {BITSET_FIXED = 1,    /* Bitset size fixed.  */
  59                   BITSET_VARIABLE = 2, /* Bitset size variable.  */
  60                   BITSET_DENSE = 4,    /* Bitset dense.  */
  61                   BITSET_SPARSE = 8,   /* Bitset sparse.  */
  62                   BITSET_FRUGAL = 16,  /* Prefer most compact.  */
  63                   BITSET_GREEDY = 32}; /* Prefer fastest.  */
  64
  65 typedef unsigned int bitset_attrs;
  66
  67 /* The elements of these structures should be considered
  68    to be private.  */
  69 typedef struct bitset_struct
  70 {
  71   struct bitset_ops_struct *ops;
  72   bitset_windex cindex;         /* Cache word index.  */
  73   bitset_windex csize;          /* Cache size in words.  */
  74   bitset_word *cdata;           /* Cache data pointer.  */
  75   union bitset_data
  76   {
  77     struct sbitset_struct s;
  78     struct lbitset_struct l;
  79     struct ebitset_struct e;
  80   } u;
  81 } *bitset;
  82
  83
  84 /* The contents of this structure should be considered private.  */
  85 struct bitset_ops_struct
  86 {
  87   void (*set) PARAMS ((struct bitset_struct *, bitset_bindex));
  88   void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex));
  89   int (*test) PARAMS ((struct bitset_struct *, bitset_bindex));
  90   int (*size) PARAMS ((struct bitset_struct *));
  91   int (*op1) PARAMS ((struct bitset_struct *, enum bitset_ops));
  92   int (*op2) PARAMS ((struct bitset_struct *, struct bitset_struct *,
  93                       enum bitset_ops));
  94   int (*op3) PARAMS ((struct bitset_struct *, struct bitset_struct *,
  95                       struct bitset_struct *, enum bitset_ops));
  96   int (*op4) PARAMS ((struct bitset_struct *, struct bitset_struct *,
  97                       struct bitset_struct *, struct bitset_struct *,
  98                       enum bitset_ops));
  99   int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *,
 100                        bitset_bindex, bitset_bindex *));
 101   int (*reverse_list) PARAMS ((struct bitset_struct *, bitset_bindex *,
 102                                bitset_bindex, bitset_bindex *));
 103   void (*free) PARAMS ((struct bitset_struct *));
 104   enum bitset_type type;
 105 };
 106
 107
 108 /* Return bytes required for bitset of desired type and size.  */
 109 extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
 110
 111 /* Initialise a bitset with desired type and size.  */
 112 extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
 113
 114 extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
 115                                                     bitset_attrs));
 116
 117 /* Create a bitset of desired type and size.  */
 118 extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
 119
 120 /* Free bitset.  */
 121 extern void bitset_free PARAMS ((bitset));
 122
 123 /* Create a bitset of desired type and size using obstack.  */
 124 extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
 125                                             bitset_bindex, enum bitset_type));
 126
 127 /* Free bitset allocated on obstack.  */
 128 extern void bitset_obstack_free PARAMS ((bitset));
 129
 130 /* Create a bitset of desired size and attributes.  */
 131 extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
 132
 133 /* Return size in bits of bitset SRC.  */
 134 extern int bitset_size PARAMS ((bitset));
 135
 136 #if BITSET_CACHE && BITSET_INLINE
 137 static inline void bitset_set PARAMS ((bitset, bitset_bindex));
 138 static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
 139 static inline int bitset_test PARAMS ((bitset, bitset_bindex));
 140
 141 /* Set bit BITNO in bitset BSET.  */
 142 static inline void bitset_set (bset, bitno)
 143     bitset bset;
 144     bitset_bindex bitno;
 145 {
 146   bitset_windex index = bitno / BITSET_WORD_BITS;
 147   bitset_windex offset = index - bset->cindex;
 148
 149   if (offset < bset->csize)
 150     bset->cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
 151   else
 152     BITSET__SET (bset, bitno);
 153 }
 154
 155
 156 /* Reset bit BITNO in bitset BSET.  */
 157 static inline void bitset_reset (bset, bitno)
 158     bitset bset;
 159     bitset_bindex bitno;
 160 {
 161   bitset_windex index = bitno / BITSET_WORD_BITS;
 162   bitset_windex offset = index - bset->cindex;
 163
 164   if (offset < bset->csize)
 165     bset->cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
 166   else
 167     BITSET__RESET (bset, bitno);
 168 }
 169
 170
 171 /* Test bit BITNO in bitset BSET.  */
 172 static inline int bitset_test (bset, bitno)
 173     bitset bset;
 174     bitset_bindex bitno;
 175 {
 176   bitset_windex index = bitno / BITSET_WORD_BITS;
 177   bitset_windex offset = index - bset->cindex;
 178
 179   if (offset < bset->csize)
 180     return (bset->cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
 181   else
 182     return BITSET__TEST (bset, bitno);
 183 }
 184 #endif
 185
 186 #if BITSET_CACHE && ! BITSET_INLINE
 187
 188 /* Set bit BITNO in bitset BSET.  */
 189 #define bitset_set(bset, bitno)                                 \
 190 do                                                              \
 191 {                                                               \
 192   bitset_bindex _bitno = (bitno);                               \
 193   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 194   bitset_windex _offset = _index - (bset)->cindex;              \
 195                                                                 \
 196   if (_offset < (bset)->csize)                                  \
 197     (bset)->cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS));       \
 198   else                                                          \
 199     BITSET__SET ((bset), _bitno);                               \
 200 } while (0)
 201
 202
 203 /* Reset bit BITNO in bitset BSET.  */
 204 #define bitset_reset(bset, bitno)                               \
 205 do                                                              \
 206 {                                                               \
 207   bitset_bindex _bitno = (bitno);                               \
 208   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 209   bitset_windex _offset = _index - (bset)->cindex;              \
 210                                                                 \
 211   if (_offset < (bset)->csize)                                  \
 212     (bset)->cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS));      \
 213   else                                                          \
 214     BITSET__RESET ((bset), _bitno);                             \
 215 } while (0)
 216
 217
 218 /* Test bit BITNO in bitset BSET.  */
 219 #define bitset_test(bset, bitno) \
 220 (((((bitno) / BITSET_WORD_BITS) - (bset)->cindex) < (bset)->csize) \
 221   ? ((bset)->cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->cindex)] \
 222      >> ((bitno) % BITSET_WORD_BITS)) & 1 \
 223   : (unsigned int) BITSET__TEST ((bset), (bitno)))
 224 #endif
 225
 226 #if ! BITSET_CACHE
 227 /* Set bit BITNO in bitset SRC.  */
 228 #define bitset_set(SRC, BITNO) BITSET__SET (SRC, BITNO)
 229
 230 /* Reset bit BITNO in bitset SRC.  */
 231 #define bitset_reset(SRC, BITNO) BITSET__RESET (SRC, BITNO)
 232
 233 /* Return non-zero if bit BITNO in bitset SRC is set.  */
 234 #define bitset_test(SRC, BITNO) BITSET__TEST (SRC, BITNO)
 235 #endif
 236
 237 /* DST = 0.  */
 238 extern int bitset_zero PARAMS ((bitset));
 239
 240 /* DST = ~0.  */
 241 extern int bitset_ones PARAMS ((bitset));
 242
 243 /* Return non-zero if all bits in bitset SRC are reset.  */
 244 extern int bitset_empty_p PARAMS ((bitset));
 245
 246 /* Return DST == DST | SRC.  */
 247 extern int bitset_subset_p PARAMS ((bitset, bitset));
 248
 249 /* Return DST == SRC.  */
 250 extern int bitset_equal_p PARAMS ((bitset, bitset));
 251
 252 /* DST == SRC.  */
 253 extern int bitset_copy PARAMS ((bitset, bitset));
 254
 255 /* DST = ~SRC.  */
 256 extern int bitset_not PARAMS ((bitset, bitset));
 257
 258 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 259 extern int bitset_or PARAMS ((bitset, bitset, bitset));
 260
 261 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 262 extern int bitset_and PARAMS ((bitset, bitset, bitset));
 263
 264 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 265 extern int bitset_xor PARAMS ((bitset, bitset, bitset));
 266
 267 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 268 extern int bitset_andn PARAMS ((bitset, bitset, bitset));
 269
 270 /* DST = SRC1 | ~SRC2.  Return non-zero if DST != SRC1 | ~SRC2.  */
 271 extern int bitset_orn PARAMS ((bitset, bitset, bitset));
 272
 273 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 274    DST != (SRC1 | SRC2) & SRC3.  */
 275 extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
 276
 277 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 278    DST != (SRC1 & SRC2) | SRC3.  */
 279 extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
 280
 281 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 282    DST != (SRC1 & ~SRC2) | SRC3.  */
 283 #define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
 284
 285 /* Find next bit set in BSET starting from and including BITNO.  */
 286 extern int bitset_next PARAMS ((bitset, bitset_bindex));
 287
 288 /* Find previous bit set in BSET starting from and including BITNO.  */
 289 extern int bitset_prev PARAMS ((bitset, bitset_bindex));
 290
 291 /* Find list of up to NUM bits set in BSET starting from and including
 292    *NEXT.  Return with actual number of bits found and with *NEXT
 293    indicating where search stopped.  */
 294 #if BITSET_STATS
 295 extern int bitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
 296                                 bitset_bindex *));
 297 #else
 298 #define bitset_list(BSET, LIST, NUM, NEXT) \
 299 BITSET__LIST (BSET, LIST, NUM, NEXT)
 300 #endif
 301
 302 /* Find reverse list of up to NUM bits set in BSET starting from and
 303    including NEXT.  Return with actual number of bits found and with
 304    *NEXT indicating where search stopped.  */
 305 #define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
 306 BITSET__REVERSE_LIST (BSET, LIST, NUM, NEXT)
 307
 308 /* Find first set bit.  */
 309 extern int bitset_first PARAMS ((bitset));
 310
 311 /* Find last set bit.  */
 312 extern int bitset_last PARAMS ((bitset));
 313
 314 /* Dump bitset.  */
 315 extern void bitset_dump PARAMS ((FILE *, bitset));
 316
 317 /* Loop over all elements of BSET, starting with MIN, executing CODE.  */
 318 #define BITSET_EXECUTE(BSET, MIN, N, CODE)                              \
 319 do {                                                                    \
 320   bitset_bindex _list[BITSET_LIST_SIZE];                                \
 321   bitset_bindex _next = (MIN);                                          \
 322   int _num;                                                             \
 323                                                                         \
 324   while ((_num = bitset_list ((BSET), _list, BITSET_LIST_SIZE, &_next)))\
 325     {                                                                   \
 326        int _i;                                                          \
 327                                                                         \
 328        for (_i = 0; _i < _num; _i++)                                    \
 329          {                                                              \
 330             (N) = _list[_i];                                            \
 331             CODE;                                                       \
 332          }                                                              \
 333        if (_num < BITSET_LIST_SIZE)                                     \
 334          break;                                                         \
 335     }                                                                   \
 336 } while (0)
 337
 338
 339 /* Loop over all elements of BSET, in reverse order starting with
 340    MIN, executing CODE.  */
 341 #define BITSET_REVERSE_EXECUTE(BSET, MIN, N, CODE)                      \
 342 do {                                                                    \
 343   bitset_bindex _list[BITSET_LIST_SIZE];                                \
 344   bitset_bindex _next = (MIN);                                          \
 345   int _num;                                                             \
 346                                                                         \
 347   while ((_num = bitset_reverse_list ((BSET), _list,                    \
 348                                       BITSET_LIST_SIZE, &_next)))       \
 349     {                                                                   \
 350        int _i;                                                          \
 351                                                                         \
 352        for (_i = 0; _i < _num; _i++)                                    \
 353          {                                                              \
 354             (N) = _list[_i];                                            \
 355             CODE;                                                       \
 356          }                                                              \
 357        if (_num < BITSET_LIST_SIZE)                                     \
 358          break;                                                         \
 359     }                                                                   \
 360 } while (0)
 361
 362
 363 /* Define set operations in terms of bit operations.  */
 364
 365 #define bitset_diff(DST, SRC1, SRC2)  bitset_andn (DST, SRC1, SRC2)
 366
 367 #define bitset_intersection(DST, SRC1, SRC2)  bitset_and (DST, SRC1, SRC2)
 368
 369 #define bitset_union(DST, SRC1, SRC2)  bitset_or (DST, SRC1, SRC2)
 370
 371 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 372 bitset_andn_or (DST, SRC1, SRC2, SRC3)
 373
 374 /* Release any memory tied up with bitsets.  */
 375 extern void bitset_release_memory PARAMS ((void));
 376
 377 /* Initialise bitset stats.  */
 378 extern void bitset_stats_init PARAMS ((void));
 379
 380 /* Dump bitset stats.  */
 381 extern void bitset_stats_dump PARAMS ((FILE *));
 382
 383 /* Function to debug bitset from debugger.  */
 384 extern void debug_bitset PARAMS ((bitset));
 385
 386 /* Function to debug bitset stats from debugger.  */
 387 extern void debug_bitset_stats PARAMS ((void));
 388
 389 extern bitset sbitset_init PARAMS ((bitset, bitset_bindex));
 390
 391 extern bitset lbitset_init PARAMS ((bitset, bitset_bindex));
 392
 393 extern bitset ebitset_init PARAMS ((bitset, bitset_bindex));
 394
 395 #endif /* _BITSET_H  */