lib/bitset.h

   1 /* Generic bitsets.
   2    Copyright (C) 2002, 2003, 2004 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;              /* Base bitset data.  */
  48
  49   struct abitset_struct
  50   {
  51     struct bbitset_struct b;
  52     bitset_word words[1];               /* The array of bits.  */
  53   } a;
  54
  55   struct ebitset_struct
  56   {
  57     struct bbitset_struct b;
  58     bitset_windex size;                 /* Number of elements.  */
  59     struct ebitset_elt_struct **elts;   /* Expanding array of ptrs to elts.  */
  60   } e;
  61
  62   struct lbitset_struct
  63   {
  64     struct bbitset_struct b;
  65     struct lbitset_elt_struct *head;    /* First element in linked list.  */
  66     struct lbitset_elt_struct *tail;    /* Last element in linked list.  */
  67   } l;
  68
  69   struct bitset_stats_struct
  70   {
  71     struct bbitset_struct b;
  72     bitset bset;
  73   } s;
  74
  75   struct vbitset_struct
  76   {
  77     struct bbitset_struct b;
  78     bitset_windex size;                 /* Allocated size of array.  */
  79   } v;
  80
  81 };
  82
  83
  84 /* The contents of this structure should be considered private.
  85    It is used for iterating over set bits.  */
  86 typedef struct
  87 {
  88   bitset_bindex list[BITSET_LIST_SIZE];
  89   bitset_bindex next;
  90   bitset_bindex num;
  91   bitset_bindex i;
  92 } bitset_iterator;
  93
  94
  95 /* Return bytes required for bitset of desired type and size.  */
  96 extern size_t bitset_bytes (enum bitset_type, bitset_bindex);
  97
  98 /* Initialise a bitset with desired type and size.  */
  99 extern bitset bitset_init (bitset, bitset_bindex, enum bitset_type);
 100
 101 /* Select an implementation type based on the desired bitset size
 102    and attributes.  */
 103 extern enum bitset_type bitset_type_choose (bitset_bindex, bitset_attrs);
 104
 105 /* Create a bitset of desired type and size.  The bitset is zeroed.  */
 106 extern bitset bitset_alloc (bitset_bindex, enum bitset_type);
 107
 108 /* Free bitset.  */
 109 extern void bitset_free (bitset);
 110
 111 /* Create a bitset of desired type and size using an obstack.  The
 112    bitset is zeroed.  */
 113 extern bitset bitset_obstack_alloc (struct obstack *bobstack,
 114                                     bitset_bindex, enum bitset_type);
 115
 116 /* Free bitset allocated on obstack.  */
 117 extern void bitset_obstack_free (bitset);
 118
 119 /* Create a bitset of desired size and attributes.  The bitset is zeroed.  */
 120 extern bitset bitset_create (bitset_bindex, bitset_attrs);
 121
 122 /* Return bitset type.  */
 123 extern enum bitset_type bitset_type_get (bitset);
 124
 125 /* Return bitset type name.  */
 126 extern const char *bitset_type_name_get (bitset);
 127
 128
 129 /* Set bit BITNO in bitset BSET.  */
 130 static inline void
 131 bitset_set (bitset bset, bitset_bindex bitno)
 132 {
 133   bitset_windex windex = bitno / BITSET_WORD_BITS;
 134   bitset_windex offset = windex - 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
 145 bitset_reset (bitset bset, bitset_bindex bitno)
 146 {
 147   bitset_windex windex = bitno / BITSET_WORD_BITS;
 148   bitset_windex offset = windex - bset->b.cindex;
 149
 150   if (offset < bset->b.csize)
 151     bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 152   else
 153     BITSET_RESET_ (bset, bitno);
 154 }
 155
 156
 157 /* Test bit BITNO in bitset BSET.  */
 158 static inline bool
 159 bitset_test (bitset bset, bitset_bindex bitno)
 160 {
 161   bitset_windex windex = bitno / BITSET_WORD_BITS;
 162   bitset_windex offset = windex - bset->b.cindex;
 163
 164   if (offset < bset->b.csize)
 165     return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
 166   else
 167     return BITSET_TEST_ (bset, bitno);
 168 }
 169
 170
 171 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 172 #define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
 173
 174 /* Return size in bits of bitset SRC.  */
 175 #define bitset_size(SRC) BITSET_SIZE_ (SRC)
 176
 177 /* Change size of bitset.  */
 178 extern void bitset_resize (bitset, bitset_bindex);
 179
 180 /* Return number of bits set in bitset SRC.  */
 181 #define bitset_count(SRC) BITSET_COUNT_ (SRC)
 182
 183
 184 /* Return SRC == 0.  */
 185 #define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
 186
 187 /* DST = ~0.  */
 188 #define bitset_ones(DST) BITSET_ONES_ (DST)
 189
 190 /* DST = 0.  */
 191 #define bitset_zero(DST) BITSET_ZERO_ (DST)
 192
 193
 194
 195 /* DST = SRC.  */
 196 #define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
 197
 198 /* Return DST & SRC == 0.  */
 199 #define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
 200
 201 /* Return DST == SRC.  */
 202 #define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
 203
 204 /* DST = ~SRC.  */
 205 #define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
 206
 207 /* Return DST == DST | SRC.  */
 208 #define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
 209
 210
 211
 212 /* DST = SRC1 & SRC2.  */
 213 #define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
 214
 215 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 216 #define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
 217
 218 /* DST = SRC1 & ~SRC2.  */
 219 #define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
 220
 221 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 222 #define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
 223
 224 /* DST = SRC1 | SRC2.  */
 225 #define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
 226
 227 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 228 #define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
 229
 230 /* DST = SRC1 ^ SRC2.  */
 231 #define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
 232
 233 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 234 #define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
 235
 236
 237
 238 /* DST = (SRC1 & SRC2) | SRC3.  */
 239 #define bitset_and_or(DST, SRC1, SRC2, SRC3) \
 240  BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
 241
 242 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 243    DST != (SRC1 & SRC2) | SRC3.  */
 244 #define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
 245  BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 246
 247 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 248 #define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
 249  BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
 250
 251 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 252    DST != (SRC1 & ~SRC2) | SRC3.  */
 253 #define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
 254  BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 255
 256 /* DST = (SRC1 | SRC2) & SRC3.  */
 257 #define bitset_or_and(DST, SRC1, SRC2, SRC3)\
 258  BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
 259
 260 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 261    DST != (SRC1 | SRC2) & SRC3.  */
 262 #define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
 263  BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
 264
 265 /* Find list of up to NUM bits set in BSET starting from and including
 266    *NEXT.  Return with actual number of bits found and with *NEXT
 267    indicating where search stopped.  */
 268 #define bitset_list(BSET, LIST, NUM, NEXT) \
 269  BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 270
 271 /* Find reverse list of up to NUM bits set in BSET starting from and
 272    including NEXT.  Return with actual number of bits found and with
 273    *NEXT indicating where search stopped.  */
 274 #define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
 275  BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
 276
 277 /* Return true if both bitsets are of the same type and size.  */
 278 extern bool bitset_compatible_p (bitset bset1, bitset bset2);
 279
 280 /* Find next set bit from the given bit index.  */
 281 extern bitset_bindex bitset_next (bitset, bitset_bindex);
 282
 283 /* Find previous set bit from the given bit index.  */
 284 extern bitset_bindex bitset_prev (bitset, bitset_bindex);
 285
 286 /* Find first set bit.  */
 287 extern bitset_bindex bitset_first (bitset);
 288
 289 /* Find last set bit.  */
 290 extern bitset_bindex bitset_last (bitset);
 291
 292 /* Return nonzero if this is the only set bit.  */
 293 extern bool bitset_only_set_p (bitset, bitset_bindex);
 294
 295 /* Dump bitset.  */
 296 extern void bitset_dump (FILE *, bitset);
 297
 298 /* Loop over all elements of BSET, starting with MIN, setting INDEX
 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 ("%lu ", (unsigned long int) i);
 308    };
 309 */
 310 #define BITSET_FOR_EACH(ITER, BSET, INDEX, 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 && ((INDEX) = 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 INDEX 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 ("%lu ", (unsigned long int) i);
 330    };
 331 */
 332 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, 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 && ((INDEX) = 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 /* Release any memory tied up with bitsets.  */
 365 extern void bitset_release_memory (void);
 366
 367 /* Enable bitset stats gathering.  */
 368 extern void bitset_stats_enable (void);
 369
 370 /* Disable bitset stats gathering.  */
 371 extern void bitset_stats_disable (void);
 372
 373 /* Read bitset stats file of accummulated stats.  */
 374 void bitset_stats_read (const char *filename);
 375
 376 /* Write bitset stats file of accummulated stats.  */
 377 void bitset_stats_write (const char *filename);
 378
 379 /* Dump bitset stats.  */
 380 extern void bitset_stats_dump (FILE *);
 381
 382 /* Function to debug bitset from debugger.  */
 383 extern void debug_bitset (bitset);
 384
 385 /* Function to debug bitset stats from debugger.  */
 386 extern void debug_bitset_stats (void);
 387
 388 #endif /* _BITSET_H  */
 389