lib/bitset.h

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