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