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 static inline void bitset_set PARAMS ((bitset, bitset_bindex));
 125 static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
 126 static inline int bitset_test PARAMS ((bitset, bitset_bindex));
 127
 128 /* Set bit BITNO in bitset BSET.  */
 129 static inline void bitset_set (bset, bitno)
 130     bitset bset;
 131     bitset_bindex bitno;
 132 {
 133   bitset_windex index = bitno / BITSET_WORD_BITS;
 134   bitset_windex offset = index - bset->b.cindex;
 135
 136   if (offset < bset->b.csize)
 137     bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 138   else
 139     BITSET_SET_ (bset, bitno);
 140 }
 141
 142
 143 /* Reset bit BITNO in bitset BSET.  */
 144 static inline void bitset_reset (bset, bitno)
 145     bitset bset;
 146     bitset_bindex bitno;
 147 {
 148   bitset_windex index = bitno / BITSET_WORD_BITS;
 149   bitset_windex offset = index - bset->b.cindex;
 150
 151   if (offset < bset->b.csize)
 152     bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 153   else
 154     BITSET_RESET_ (bset, bitno);
 155 }
 156
 157
 158 /* Test bit BITNO in bitset BSET.  */
 159 static inline int bitset_test (bset, bitno)
 160     bitset bset;
 161     bitset_bindex bitno;
 162 {
 163   bitset_windex index = bitno / BITSET_WORD_BITS;
 164   bitset_windex offset = index - bset->b.cindex;
 165
 166   if (offset < bset->b.csize)
 167     return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
 168   else
 169     return BITSET_TEST_ (bset, bitno);
 170 }
 171 #endif
 172
 173 #if ! BITSET_INLINE
 174
 175 /* Set bit BITNO in bitset BSET.  */
 176 #define bitset_set(bset, bitno)                                 \
 177 do                                                              \
 178 {                                                               \
 179   bitset_bindex _bitno = (bitno);                               \
 180   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 181   bitset_windex _offset = _index - (bset)->b.cindex;            \
 182                                                                 \
 183   if (_offset < (bset)->b.csize)                                        \
 184     (bset)->b.cdata[_offset] |=                                 \
 185       ((bitset_word) 1 << (_bitno % BITSET_WORD_BITS));         \
 186   else                                                          \
 187     BITSET_SET_ ((bset), _bitno);                               \
 188 } while (0)
 189
 190
 191 /* Reset bit BITNO in bitset BSET.  */
 192 #define bitset_reset(bset, bitno)                               \
 193 do                                                              \
 194 {                                                               \
 195   bitset_bindex _bitno = (bitno);                               \
 196   bitset_windex _index = _bitno / BITSET_WORD_BITS;             \
 197   bitset_windex _offset = _index - (bset)->b.cindex;            \
 198                                                                 \
 199   if (_offset < (bset)->b.csize)                                \
 200     (bset)->b.cdata[_offset] &=                                 \
 201        ~((bitset_word) 1 << (_bitno % BITSET_WORD_BITS));       \
 202   else                                                          \
 203     BITSET_RESET_ ((bset), _bitno);                             \
 204 } while (0)
 205
 206
 207 /* Test bit BITNO in bitset BSET.  */
 208 #define bitset_test(bset, bitno) \
 209 (((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize)  \
 210   ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
 211      >> ((bitno) % BITSET_WORD_BITS)) & 1 \
 212   : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
 213 #endif
 214
 215
 216 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 217 #define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
 218
 219 /* Return size in bits of bitset SRC.  */
 220 #define bitset_size(SRC) BITSET_SIZE_ (SRC)
 221
 222 /* Return number of bits set in bitset SRC.  */
 223 #define bitset_count(SRC) BITSET_COUNT_ (SRC)
 224
 225
 226 /* Return SRC == 0.  */
 227 #define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
 228
 229 /* DST = ~0.  */
 230 #define bitset_ones(DST) BITSET_ONES_ (DST)
 231
 232 /* DST = 0.  */
 233 #define bitset_zero(DST) BITSET_ZERO_ (DST)
 234
 235
 236
 237 /* DST = SRC.  */
 238 #define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
 239
 240 /* Return DST & SRC == 0.  */
 241 #define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
 242
 243 /* Return DST == SRC.  */
 244 #define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
 245
 246 /* DST = ~SRC.  */
 247 #define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
 248
 249 /* Return DST == DST | SRC.  */
 250 #define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
 251
 252
 253
 254 /* DST = SRC1 & SRC2.  */
 255 #define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
 256
 257 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 258 #define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
 259
 260 /* DST = SRC1 & ~SRC2.  */
 261 #define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
 262
 263 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 264 #define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
 265
 266 /* DST = SRC1 | SRC2.  */
 267 #define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
 268
 269 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 270 #define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
 271
 272 /* DST = SRC1 ^ SRC2.  */
 273 #define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
 274
 275 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 276 #define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
 277
 278
 279
 280 /* DST = (SRC1 & SRC2) | SRC3.  */
 281 #define bitset_and_or(DST, SRC1, SRC2, SRC3) \
 282  BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
 283
 284 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 285    DST != (SRC1 & SRC2) | SRC3.  */
 286 #define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
 287  BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 288
 289 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 290 #define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
 291  BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
 292
 293 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 294    DST != (SRC1 & ~SRC2) | SRC3.  */
 295 #define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
 296  BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 297
 298 /* DST = (SRC1 | SRC2) & SRC3.  */
 299 #define bitset_or_and(DST, SRC1, SRC2, SRC3)\
 300  BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
 301
 302 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 303    DST != (SRC1 | SRC2) & SRC3.  */
 304 #define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
 305  BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
 306
 307 /* Find list of up to NUM bits set in BSET starting from and including
 308    *NEXT.  Return with actual number of bits found and with *NEXT
 309    indicating where search stopped.  */
 310 #define bitset_list(BSET, LIST, NUM, NEXT) \
 311  BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 312
 313 /* Find reverse list of up to NUM bits set in BSET starting from and
 314    including NEXT.  Return with actual number of bits found and with
 315    *NEXT indicating where search stopped.  */
 316 #define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
 317  BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
 318
 319
 320 /* Find next set bit.  */
 321 extern bitset_bindex bitset_next PARAMS ((bitset, bitset_bindex));
 322
 323 /* Find previous set bit.  */
 324 extern bitset_bindex bitset_prev PARAMS ((bitset, bitset_bindex));
 325
 326 /* Find first set bit.  */
 327 extern bitset_bindex bitset_first PARAMS ((bitset));
 328
 329 /* Find last set bit.  */
 330 extern bitset_bindex bitset_last PARAMS ((bitset));
 331
 332 /* Return nonzero if this is the only set bit.  */
 333 extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
 334
 335 /* Dump bitset.  */
 336 extern void bitset_dump PARAMS ((FILE *, bitset));
 337
 338 /* Loop over all elements of BSET, starting with MIN, setting BIT
 339    to the index of each set bit.  For example, the following will print
 340    the bits set in a bitset:
 341
 342    bitset_bindex i;
 343    bitset_iterator iter;
 344
 345    bitset_zero (dst);
 346    BITSET_FOR_EACH (iter, src, i, 0)
 347    {
 348       printf ("%ld ", i);
 349    };
 350 */
 351 #define BITSET_FOR_EACH(ITER, BSET, BIT, MIN)                                 \
 352   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 353        (ITER.num == BITSET_LIST_SIZE)                                         \
 354        && (ITER.num = bitset_list (BSET, ITER.list,                           \
 355                                    BITSET_LIST_SIZE, &ITER.next));)           \
 356     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 357
 358
 359 /* Loop over all elements of BSET, in reverse order starting with
 360    MIN,  setting BIT to the index of each set bit. For example, the
 361    following will print the bits set in a bitset in reverse order:
 362
 363    bitset_bindex i;
 364    bitset_iterator iter;
 365
 366    bitset_zero (dst);
 367    BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
 368    {
 369       printf ("%ld ", i);
 370    };
 371 */
 372 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN)                         \
 373   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 374        (ITER.num == BITSET_LIST_SIZE)                                         \
 375        && (ITER.num = bitset_list_reverse (BSET, ITER.list,                   \
 376                                           BITSET_LIST_SIZE, &ITER.next));)    \
 377     for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
 378
 379
 380 /* Define set operations in terms of logical operations.  */
 381
 382 #define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
 383 #define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
 384
 385 #define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
 386 #define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
 387
 388 #define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
 389 #define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
 390
 391 /* Symmetrical difference.  */
 392 #define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
 393 #define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
 394
 395 /* Union of difference.  */
 396 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 397   bitset_andn_or (DST, SRC1, SRC2, SRC3)
 398 #define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
 399   bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
 400
 401
 402
 403 /* Release any memory tied up with bitsets.  */
 404 extern void bitset_release_memory PARAMS ((void));
 405
 406 /* Enable bitset stats gathering.  */
 407 extern void bitset_stats_enable PARAMS ((void));
 408
 409 /* Disable bitset stats gathering.  */
 410 extern void bitset_stats_disable PARAMS ((void));
 411
 412 /* Read bitset stats file of accummulated stats.  */
 413 void bitset_stats_read PARAMS ((const char *filename));
 414
 415 /* Write bitset stats file of accummulated stats.  */
 416 void bitset_stats_write PARAMS ((const char *filename));
 417
 418 /* Dump bitset stats.  */
 419 extern void bitset_stats_dump PARAMS ((FILE *));
 420
 421 /* Function to debug bitset from debugger.  */
 422 extern void debug_bitset PARAMS ((bitset));
 423
 424 /* Function to debug bitset stats from debugger.  */
 425 extern void debug_bitset_stats PARAMS ((void));
 426
 427 #endif /* _BITSET_H  */
 428