maint/gnulib/lib/bitset.h

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

INCLUDED FROM

DEFINITIONS
