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 union should be considered to be private.
  40    While I would like to make this union opaque, it needs to be
  41    visible for the inline bit set/test functions, and for delegation
  42    to the proper implementation.  */
  43 union bitset_union
  44 {
  45   /* This must be the first member of every other structure that is a
  46      member of this union.  */
  47   struct bbitset_struct b;
  48
  49   struct abitset_struct
  50   {
  51     struct bbitset_struct b;
  52     bitset_bindex n_bits;               /* Number of bits.  */
  53     bitset_word words[1];               /* The array of bits.  */
  54   } a;
  55
  56   struct ebitset_struct
  57   {
  58     struct bbitset_struct b;
  59     bitset_windex size;                 /* Number of elements.  */
  60     struct ebitset_elt_struct **elts;   /* Expanding array of ptrs to elts.  */
  61   } e;
  62
  63   struct lbitset_struct
  64   {
  65     struct bbitset_struct b;
  66     struct lbitset_elt_struct *head;    /* First element in linked list.  */
  67     struct lbitset_elt_struct *tail;    /* Last element in linked list.  */
  68   } l;
  69
  70   struct bitset_stats_struct
  71   {
  72     struct bbitset_struct b;
  73     bitset bset;
  74   } s;
  75 };
  76
  77
  78 /* The contents of this structure should be considered private.
  79    It is used for iterating over set bits.  */
  80 typedef struct
  81 {
  82   bitset_bindex list[BITSET_LIST_SIZE];
  83   bitset_bindex next;
  84   bitset_bindex num;
  85   bitset_bindex i;
  86 } bitset_iterator;
  87
  88
  89 /* Return bytes required for bitset of desired type and size.  */
  90 extern size_t bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
  91
  92 /* Initialise a bitset with desired type and size.  */
  93 extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
  94
  95 /* Select an implementation type based on the desired bitset size
  96    and attributes.  */
  97 extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
  98                                                     bitset_attrs));
  99
 100 /* Create a bitset of desired type and size.  The bitset is zeroed.  */
 101 extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
 102
 103 /* Free bitset.  */
 104 extern void bitset_free PARAMS ((bitset));
 105
 106 /* Create a bitset of desired type and size using an obstack.  The
 107    bitset is zeroed.  */
 108 extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
 109                                             bitset_bindex, enum bitset_type));
 110
 111 /* Free bitset allocated on obstack.  */
 112 extern void bitset_obstack_free PARAMS ((bitset));
 113
 114 /* Create a bitset of desired size and attributes.  The bitset is zeroed.  */
 115 extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
 116
 117 /* Return bitset type.  */
 118 extern enum bitset_type bitset_type_get PARAMS ((bitset));
 119
 120 /* Return bitset type name.  */
 121 extern const char *bitset_type_name_get PARAMS ((bitset));
 122
 123 #if BITSET_INLINE
 124
 125 /* Set bit BITNO in bitset BSET.  */
 126 static inline void
 127 bitset_set (bitset bset, bitset_bindex bitno)
 128 {
 129   bitset_windex index = bitno / BITSET_WORD_BITS;
 130   bitset_windex offset = index - bset->b.cindex;
 131
 132   if (offset < bset->b.csize)
 133     bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 134   else
 135     BITSET_SET_ (bset, bitno);
 136 }
 137
 138
 139 /* Reset bit BITNO in bitset BSET.  */
 140 static inline void
 141 bitset_reset (bitset bset, bitset_bindex bitno)
 142 {
 143   bitset_windex index = bitno / BITSET_WORD_BITS;
 144   bitset_windex offset = index - bset->b.cindex;
 145
 146   if (offset < bset->b.csize)
 147     bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 148   else
 149     BITSET_RESET_ (bset, bitno);
 150 }
 151
 152
 153 /* Test bit BITNO in bitset BSET.  */
 154 static inline int
 155 bitset_test (bitset bset, bitset_bindex bitno)
 156 {
 157   bitset_windex index = bitno / BITSET_WORD_BITS;
 158   bitset_windex offset = index - bset->b.cindex;
 159
 160   if (offset < bset->b.csize)
 161     return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
 162   else
 163     return BITSET_TEST_ (bset, bitno);
 164 }
 165 #endif
 166
 167 #if ! BITSET_INLINE
 168
 169 /* Set bit BITNO in bitset BSET.  */
 170 #define bitset_set(bset, bitno)                                 \
 171 do                                                              \
 172 {                                                               \
 173   bitset_bindex _bitno = (bitno);                               \
 174   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 175   bitset_windex _offset = _index - (bset)->b.cindex;            \
 176                                                                 \
 177   if (_offset < (bset)->b.csize)                                        \
 178     (bset)->b.cdata[_offset] |=                                 \
 179       ((bitset_word) 1 << (_bitno % BITSET_WORD_BITS));         \
 180   else                                                          \
 181     BITSET_SET_ ((bset), _bitno);                               \
 182 } while (0)
 183
 184
 185 /* Reset bit BITNO in bitset BSET.  */
 186 #define bitset_reset(bset, bitno)                               \
 187 do                                                              \
 188 {                                                               \
 189   bitset_bindex _bitno = (bitno);                               \
 190   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 191   bitset_windex _offset = _index - (bset)->b.cindex;            \
 192                                                                 \
 193   if (_offset < (bset)->b.csize)                                \
 194     (bset)->b.cdata[_offset] &=                                 \
 195        ~((bitset_word) 1 << (_bitno % BITSET_WORD_BITS));       \
 196   else                                                          \
 197     BITSET_RESET_ ((bset), _bitno);                             \
 198 } while (0)
 199
 200
 201 /* Test bit BITNO in bitset BSET.  */
 202 #define bitset_test(bset, bitno) \
 203 (((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize)  \
 204   ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
 205      >> ((bitno) % BITSET_WORD_BITS)) & 1 \
 206   : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
 207 #endif
 208
 209
 210 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 211 #define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
 212
 213 /* Return size in bits of bitset SRC.  */
 214 #define bitset_size(SRC) BITSET_SIZE_ (SRC)
 215
 216 /* Return number of bits set in bitset SRC.  */
 217 #define bitset_count(SRC) BITSET_COUNT_ (SRC)
 218
 219
 220 /* Return SRC == 0.  */
 221 #define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
 222
 223 /* DST = ~0.  */
 224 #define bitset_ones(DST) BITSET_ONES_ (DST)
 225
 226 /* DST = 0.  */
 227 #define bitset_zero(DST) BITSET_ZERO_ (DST)
 228
 229
 230
 231 /* DST = SRC.  */
 232 #define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
 233
 234 /* Return DST & SRC == 0.  */
 235 #define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
 236
 237 /* Return DST == SRC.  */
 238 #define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
 239
 240 /* DST = ~SRC.  */
 241 #define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
 242
 243 /* Return DST == DST | SRC.  */
 244 #define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
 245
 246
 247
 248 /* DST = SRC1 & SRC2.  */
 249 #define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
 250
 251 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 252 #define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
 253
 254 /* DST = SRC1 & ~SRC2.  */
 255 #define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
 256
 257 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 258 #define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
 259
 260 /* DST = SRC1 | SRC2.  */
 261 #define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
 262
 263 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 264 #define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
 265
 266 /* DST = SRC1 ^ SRC2.  */
 267 #define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
 268
 269 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 270 #define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
 271
 272
 273
 274 /* DST = (SRC1 & SRC2) | SRC3.  */
 275 #define bitset_and_or(DST, SRC1, SRC2, SRC3) \
 276  BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
 277
 278 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 279    DST != (SRC1 & SRC2) | SRC3.  */
 280 #define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
 281  BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 282
 283 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 284 #define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
 285  BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
 286
 287 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 288    DST != (SRC1 & ~SRC2) | SRC3.  */
 289 #define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
 290  BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 291
 292 /* DST = (SRC1 | SRC2) & SRC3.  */
 293 #define bitset_or_and(DST, SRC1, SRC2, SRC3)\
 294  BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
 295
 296 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 297    DST != (SRC1 | SRC2) & SRC3.  */
 298 #define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
 299  BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
 300
 301 /* Find list of up to NUM bits set in BSET starting from and including
 302    *NEXT.  Return with actual number of bits found and with *NEXT
 303    indicating where search stopped.  */
 304 #define bitset_list(BSET, LIST, NUM, NEXT) \
 305  BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 306
 307 /* Find reverse list of up to NUM bits set in BSET starting from and
 308    including NEXT.  Return with actual number of bits found and with
 309    *NEXT indicating where search stopped.  */
 310 #define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
 311  BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
 312
 313
 314 /* Find next set bit.  */
 315 extern bitset_bindex bitset_next PARAMS ((bitset, bitset_bindex));
 316
 317 /* Find previous set bit.  */
 318 extern bitset_bindex bitset_prev PARAMS ((bitset, bitset_bindex));
 319
 320 /* Find first set bit.  */
 321 extern bitset_bindex bitset_first PARAMS ((bitset));
 322
 323 /* Find last set bit.  */
 324 extern bitset_bindex bitset_last PARAMS ((bitset));
 325
 326 /* Return nonzero if this is the only set bit.  */
 327 extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
 328
 329 /* Dump bitset.  */
 330 extern void bitset_dump PARAMS ((FILE *, bitset));
 331
 332 /* Loop over all elements of BSET, starting with MIN, setting BIT
 333    to the index of each set bit.  For example, the following will print
 334    the bits set in a bitset:
 335
 336    bitset_bindex i;
 337    bitset_iterator iter;
 338
 339    bitset_zero (dst);
 340    BITSET_FOR_EACH (iter, src, i, 0)
 341    {
 342       printf ("%ld ", i);
 343    };
 344 */
 345 #define BITSET_FOR_EACH(ITER, BSET, BIT, MIN)                                 \
 346   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 347        (ITER.num == BITSET_LIST_SIZE)                                         \
 348        && (ITER.num = bitset_list (BSET, ITER.list,                           \
 349                                    BITSET_LIST_SIZE, &ITER.next));)           \
 350     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 351
 352
 353 /* Loop over all elements of BSET, in reverse order starting with
 354    MIN,  setting BIT to the index of each set bit. For example, the
 355    following will print the bits set in a bitset in reverse order:
 356
 357    bitset_bindex i;
 358    bitset_iterator iter;
 359
 360    bitset_zero (dst);
 361    BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
 362    {
 363       printf ("%ld ", i);
 364    };
 365 */
 366 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN)                         \
 367   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 368        (ITER.num == BITSET_LIST_SIZE)                                         \
 369        && (ITER.num = bitset_list_reverse (BSET, ITER.list,                   \
 370                                           BITSET_LIST_SIZE, &ITER.next));)    \
 371     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 372
 373
 374 /* Define set operations in terms of logical operations.  */
 375
 376 #define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
 377 #define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
 378
 379 #define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
 380 #define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
 381
 382 #define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
 383 #define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
 384
 385 /* Symmetrical difference.  */
 386 #define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
 387 #define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
 388
 389 /* Union of difference.  */
 390 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 391   bitset_andn_or (DST, SRC1, SRC2, SRC3)
 392 #define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
 393   bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
 394
 395
 396
 397 /* Release any memory tied up with bitsets.  */
 398 extern void bitset_release_memory PARAMS ((void));
 399
 400 /* Enable bitset stats gathering.  */
 401 extern void bitset_stats_enable PARAMS ((void));
 402
 403 /* Disable bitset stats gathering.  */
 404 extern void bitset_stats_disable PARAMS ((void));
 405
 406 /* Read bitset stats file of accummulated stats.  */
 407 void bitset_stats_read PARAMS ((const char *filename));
 408
 409 /* Write bitset stats file of accummulated stats.  */
 410 void bitset_stats_write PARAMS ((const char *filename));
 411
 412 /* Dump bitset stats.  */
 413 extern void bitset_stats_dump PARAMS ((FILE *));
 414
 415 /* Function to debug bitset from debugger.  */
 416 extern void debug_bitset PARAMS ((bitset));
 417
 418 /* Function to debug bitset stats from debugger.  */
 419 extern void debug_bitset_stats PARAMS ((void));
 420
 421 #endif /* _BITSET_H  */
 422