lib/bitset.h

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