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