lib/bitset.h

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