lib/bitset.h

   1 /* Generic bitsets.
   2
   3    Copyright (C) 2002-2004, 2009-2015, 2018 Free Software Foundation,
   4    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 <stdio.h>
  28 #if USE_UNLOCKED_IO
  29 # include "unlocked-io.h"
  30 #endif
  31
  32 #include "bitset/base.h"
  33 #include "obstack.h"
  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 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 /* The contents of this structure should be considered private.
  90    It is used for iterating over set bits.  */
  91 typedef struct
  92 {
  93   bitset_bindex list[BITSET_LIST_SIZE];
  94   bitset_bindex next;
  95   bitset_bindex num;
  96   bitset_bindex i;
  97 } bitset_iterator;
  98
  99
 100 /* Return bytes required for bitset of desired type and size.  */
 101 size_t bitset_bytes (enum bitset_type, bitset_bindex);
 102
 103 /* Initialise a bitset with desired type and size.  */
 104 bitset bitset_init (bitset, bitset_bindex, enum bitset_type);
 105
 106 /* Select an implementation type based on the desired bitset size
 107    and attributes.  */
 108 enum bitset_type bitset_type_choose (bitset_bindex, bitset_attrs);
 109
 110 /* Create a bitset of desired type and size.  The bitset is zeroed.  */
 111 bitset bitset_alloc (bitset_bindex, enum bitset_type);
 112
 113 /* Free bitset.  */
 114 void bitset_free (bitset);
 115
 116 /* Create a bitset of desired type and size using an obstack.  The
 117    bitset is zeroed.  */
 118 bitset bitset_obstack_alloc (struct obstack *bobstack,
 119                              bitset_bindex, enum bitset_type);
 120
 121 /* Free bitset allocated on obstack.  */
 122 void bitset_obstack_free (bitset);
 123
 124 /* Create a bitset of desired size and attributes.  The bitset is zeroed.  */
 125 bitset bitset_create (bitset_bindex, bitset_attrs);
 126
 127 /* Return bitset type.  */
 128 enum bitset_type bitset_type_get (bitset);
 129
 130 /* Return bitset type name.  */
 131 const char *bitset_type_name_get (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 /* Change size of bitset.  */
 183 void bitset_resize (bitset, bitset_bindex);
 184
 185 /* Return number of bits set in bitset SRC.  */
 186 #define bitset_count(SRC) BITSET_COUNT_ (SRC)
 187
 188
 189 /* Return SRC == 0.  */
 190 #define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
 191
 192 /* DST = ~0.  */
 193 #define bitset_ones(DST) BITSET_ONES_ (DST)
 194
 195 /* DST = 0.  */
 196 #define bitset_zero(DST) BITSET_ZERO_ (DST)
 197
 198
 199
 200 /* DST = SRC.  */
 201 #define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
 202
 203 /* Return DST & SRC == 0.  */
 204 #define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
 205
 206 /* Return DST == SRC.  */
 207 #define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
 208
 209 /* DST = ~SRC.  */
 210 #define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
 211
 212 /* Return DST == DST | SRC.  */
 213 #define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
 214
 215
 216
 217 /* DST = SRC1 & SRC2.  */
 218 #define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
 219
 220 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 221 #define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
 222
 223 /* DST = SRC1 & ~SRC2.  */
 224 #define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
 225
 226 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 227 #define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
 228
 229 /* DST = SRC1 | SRC2.  */
 230 #define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
 231
 232 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 233 #define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
 234
 235 /* DST = SRC1 ^ SRC2.  */
 236 #define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
 237
 238 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 239 #define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
 240
 241
 242
 243 /* DST = (SRC1 & SRC2) | SRC3.  */
 244 #define bitset_and_or(DST, SRC1, SRC2, SRC3) \
 245  BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
 246
 247 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 248    DST != (SRC1 & SRC2) | SRC3.  */
 249 #define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
 250  BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 251
 252 /* DST = (SRC1 & ~SRC2) | SRC3.  */
 253 #define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
 254  BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
 255
 256 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 257    DST != (SRC1 & ~SRC2) | SRC3.  */
 258 #define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
 259  BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
 260
 261 /* DST = (SRC1 | SRC2) & SRC3.  */
 262 #define bitset_or_and(DST, SRC1, SRC2, SRC3)\
 263  BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
 264
 265 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 266    DST != (SRC1 | SRC2) & SRC3.  */
 267 #define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
 268  BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
 269
 270 /* Find list of up to NUM bits set in BSET starting from and including
 271    *NEXT.  Return with actual number of bits found and with *NEXT
 272    indicating where search stopped.  */
 273 #define bitset_list(BSET, LIST, NUM, NEXT) \
 274  BITSET_LIST_ (BSET, LIST, NUM, NEXT)
 275
 276 /* Find reverse list of up to NUM bits set in BSET starting from and
 277    including NEXT.  Return with actual number of bits found and with
 278    *NEXT indicating where search stopped.  */
 279 #define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
 280  BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
 281
 282 /* Return true if both bitsets are of the same type and size.  */
 283 bool bitset_compatible_p (bitset bset1, bitset bset2);
 284
 285 /* Find next set bit from the given bit index.  */
 286 bitset_bindex bitset_next (bitset, bitset_bindex);
 287
 288 /* Find previous set bit from the given bit index.  */
 289 bitset_bindex bitset_prev (bitset, bitset_bindex);
 290
 291 /* Find first set bit.  */
 292 bitset_bindex bitset_first (bitset);
 293
 294 /* Find last set bit.  */
 295 bitset_bindex bitset_last (bitset);
 296
 297 /* Return nonzero if this is the only set bit.  */
 298 bool bitset_only_set_p (bitset, bitset_bindex);
 299
 300 /* Dump bitset.  */
 301 void bitset_dump (FILE *, bitset);
 302
 303 /* Loop over all elements of BSET, starting with MIN, setting INDEX
 304    to the index of each set bit.  For example, the following will print
 305    the bits set in a bitset:
 306
 307    bitset_bindex i;
 308    bitset_iterator iter;
 309
 310    BITSET_FOR_EACH (iter, src, i, 0)
 311      printf ("%lu ", (unsigned long) i);
 312 */
 313 #define BITSET_FOR_EACH(ITER, BSET, INDEX, MIN)                               \
 314   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 315        (ITER.num == BITSET_LIST_SIZE)                                         \
 316        && (ITER.num = bitset_list (BSET, ITER.list,                           \
 317                                    BITSET_LIST_SIZE, &ITER.next));)           \
 318     for (ITER.i = 0;                                                          \
 319          ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1);               \
 320          ITER.i++)
 321
 322
 323 /* Loop over all elements of BSET, in reverse order starting with
 324    MIN, setting INDEX to the index of each set bit.  For example, the
 325    following will print the bits set in a bitset in reverse order:
 326
 327    bitset_bindex i;
 328    bitset_iterator iter;
 329
 330    BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
 331     printf ("%lu ", (unsigned long) i);
 332 */
 333 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, MIN)                       \
 334   for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;                        \
 335        (ITER.num == BITSET_LIST_SIZE)                                         \
 336        && (ITER.num = bitset_list_reverse (BSET, ITER.list,                   \
 337                                            BITSET_LIST_SIZE, &ITER.next));)   \
 338     for (ITER.i = 0;                                                          \
 339          ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1);               \
 340          ITER.i++)
 341
 342
 343 /* Define set operations in terms of logical operations.  */
 344
 345 #define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
 346 #define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
 347
 348 #define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
 349 #define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
 350
 351 #define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
 352 #define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
 353
 354 /* Symmetrical difference.  */
 355 #define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
 356 #define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
 357
 358 /* Union of difference.  */
 359 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
 360   bitset_andn_or (DST, SRC1, SRC2, SRC3)
 361 #define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
 362   bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
 363
 364
 365 /* Release any memory tied up with bitsets.  */
 366 void bitset_release_memory (void);
 367
 368 /* Enable bitset stats gathering.  */
 369 void bitset_stats_enable (void);
 370
 371 /* Disable bitset stats gathering.  */
 372 void bitset_stats_disable (void);
 373
 374 /* Read bitset stats file of accummulated stats.  */
 375 void bitset_stats_read (const char *file_name);
 376
 377 /* Write bitset stats file of accummulated stats.  */
 378 void bitset_stats_write (const char *file_name);
 379
 380 /* Dump bitset stats.  */
 381 void bitset_stats_dump (FILE *);
 382
 383 /* Function to debug bitset from debugger.  */
 384 void debug_bitset (bitset);
 385
 386 /* Function to debug bitset stats from debugger.  */
 387 void debug_bitset_stats (void);
 388
 389 #endif /* _BITSET_H  */