lib/bitset.h

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