maint/gnulib/lib/bitset/base.h

/* */
This source file includes following definitions.
bitset_ffs_
bitset_fls_
   1 /* Base bitset stuff.
   2 
   3    Copyright (C) 2002-2004, 2006, 2009-2015, 2018-2021 Free Software
   4    Foundation, 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 <https://www.gnu.org/licenses/>.  */
  20 
  21 #ifndef _BITSET_BASE_H
  22 #define _BITSET_BASE_H
  23 
  24 #include <limits.h>
  25 #include <stdbool.h>
  26 #include <stddef.h>
  27 #include <stdlib.h>     /* because Gnulib's <stdlib.h> may '#define free ...' */
  28 #include <string.h> /* ffsl */
  29 
  30 #include "attribute.h"
  31 #include "integer_length.h"
  32 #include "xalloc.h"
  33 
  34 /* Currently we support five flavours of bitsets:
  35    BITSET_ARRAY:  Array of bits (fixed size, fast for dense bitsets).
  36                   Memory for bit array and bitset structure allocated
  37                   contiguously.
  38    BITSET_LIST:   Linked list of arrays of bits (variable size, least storage
  39                   for large very sparse sets).
  40    BITSET_TABLE:  Expandable table of pointers to arrays of bits
  41                   (variable size, less storage for large sparse sets).
  42                   Faster than BITSET_LIST for random access.
  43    BITSET_VECTOR: Variable array of bits (variable size, fast for
  44                   dense bitsets).
  45    BITSET_STATS:  Wrapper bitset for internal use only.  Used for gathering
  46                   statistics and/or better run-time checking.
  47 */
  48 enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_VECTOR,
  49                   BITSET_TYPE_NUM, BITSET_STATS};
  50 #define BITSET_TYPE_NAMES {"abitset", "lbitset", "tbitset", "vbitset"}
  51 
  52 extern const char * const bitset_type_names[];
  53 
  54 /* Data type used to store a word of bits.  */
  55 typedef unsigned long bitset_word;
  56 #define BITSET_WORD_BITS ((unsigned) (CHAR_BIT * sizeof (bitset_word)))
  57 
  58 /* Bit index.  In theory we might need a type wider than size_t, but
  59    in practice we lose at most a factor of CHAR_BIT by going with
  60    size_t, and that is good enough.  If this type is changed to be
  61    wider than size_t, the code needs to be modified to check for
  62    overflow when converting bit counts to byte or word counts.
  63    The bit and word index types must be unsigned.  */
  64 typedef size_t bitset_bindex;
  65 
  66 /* Word index.  */
  67 typedef size_t bitset_windex;
  68 
  69 /* Maximum values for commonly-used unsigned types.  BITSET_SIZE_MAX
  70    always equals SIZE_MAX, but some older systems lack SIZE_MAX.  */
  71 #define BITSET_BINDEX_MAX ((bitset_bindex) -1)
  72 
  73 /* Limit max word index to the maximum value of a signed integer
  74    to simplify cache disabling.  */
  75 #define BITSET_WINDEX_MAX (((bitset_windex) -1) >> 1)
  76 #define BITSET_SIZE_MAX ((size_t) -1)
  77 
  78 #define BITSET_MSB ((bitset_word) 1 << (BITSET_WORD_BITS - 1))
  79 
  80 #define BITSET_LIST_SIZE 1024
  81 
  82 enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES,
  83                  BITSET_OP_COPY, BITSET_OP_NOT,
  84                  BITSET_OP_EMPTY_P, BITSET_OP_EQUAL_P,
  85                  BITSET_OP_SUBSET_P, BITSET_OP_DISJOINT_P,
  86                  BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN,
  87                  BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR};
  88 
  89 struct bbitset_struct
  90 {
  91   const struct bitset_vtable *vtable;
  92   bitset_windex cindex;         /* Cache word index.  */
  93   bitset_windex csize;          /* Cache size in words.  */
  94   bitset_word *cdata;           /* Cache data pointer.  */
  95   bitset_bindex n_bits;         /* Number of bits.  */
  96   /* Perhaps we could sacrifice another word to indicate
  97      that the bitset is known to be zero, that a bit has been set
  98      in the cache, and that a bit has been cleared in the cache.
  99      This would speed up some of the searches but slightly slow down
 100      bit set/reset operations of cached bits.  */
 101 };
 102 
 103 
 104 typedef union bitset_union *bitset;
 105 
 106 
 107 /* Private accessor macros to bitset structure.  */
 108 #define BITSET_VTABLE_(SRC) (SRC)->b.vtable
 109 #define BITSET_CINDEX_(SRC) (SRC)->b.cindex
 110 #define BITSET_CDATA_(SRC) (SRC)->b.cdata
 111 #define BITSET_CSIZE_(SRC) (SRC)->b.csize
 112 #define BITSET_NBITS_(SRC) (SRC)->b.n_bits
 113 
 114 
 115 /* The contents of this structure should be considered private.  */
 116 struct bitset_vtable
 117 {
 118   void (*set) (bitset, bitset_bindex);
 119   void (*reset) (bitset, bitset_bindex);
 120   bool (*toggle) (bitset, bitset_bindex);
 121   bool (*test) (bitset, bitset_bindex);
 122   bitset_bindex (*resize) (bitset, bitset_bindex);
 123   bitset_bindex (*size) (bitset);
 124   bitset_bindex (*count) (bitset);
 125 
 126   bool (*empty_p) (bitset);
 127   void (*ones) (bitset);
 128   void (*zero) (bitset);
 129 
 130   void (*copy) (bitset, bitset);
 131   bool (*disjoint_p) (bitset, bitset);
 132   bool (*equal_p) (bitset, bitset);
 133   void (*not_) (bitset, bitset);
 134   bool (*subset_p) (bitset, bitset);
 135 
 136   void (*and_) (bitset, bitset, bitset);
 137   bool (*and_cmp) (bitset, bitset, bitset);
 138   void (*andn) (bitset, bitset, bitset);
 139   bool (*andn_cmp) (bitset, bitset, bitset);
 140   void (*or_) (bitset, bitset, bitset);
 141   bool (*or_cmp) (bitset, bitset, bitset);
 142   void (*xor_) (bitset, bitset, bitset);
 143   bool (*xor_cmp) (bitset, bitset, bitset);
 144 
 145   void (*and_or) (bitset, bitset, bitset, bitset);
 146   bool (*and_or_cmp) (bitset, bitset, bitset, bitset);
 147   void (*andn_or) (bitset, bitset, bitset, bitset);
 148   bool (*andn_or_cmp) (bitset, bitset, bitset, bitset);
 149   void (*or_and) (bitset, bitset, bitset, bitset);
 150   bool (*or_and_cmp) (bitset, bitset, bitset, bitset);
 151 
 152   bitset_bindex (*list) (bitset, bitset_bindex *, bitset_bindex,
 153                          bitset_bindex *);
 154   bitset_bindex (*list_reverse) (bitset, bitset_bindex *, bitset_bindex,
 155                                  bitset_bindex *);
 156   void (*free) (bitset);
 157   enum bitset_type type;
 158 };
 159 
 160 #define BITSET_COMPATIBLE_(BSET1, BSET2) \
 161 ((BSET1)->b.vtable == (BSET2)->b.vtable)
 162 
 163 #define BITSET_CHECK2_(DST, SRC) \
 164 if (!BITSET_COMPATIBLE_ (DST, SRC)) abort ();
 165 
 166 #define BITSET_CHECK3_(DST, SRC1, SRC2) \
 167 if (!BITSET_COMPATIBLE_ (DST, SRC1) \
 168     || !BITSET_COMPATIBLE_ (DST, SRC2)) abort ();
 169 
 170 #define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \
 171 if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \
 172     || !BITSET_COMPATIBLE_ (DST, SRC3)) abort ();
 173 
 174 
 175 /* Redefine number of bits in bitset DST.  */
 176 #define BITSET_RESIZE_(DST, SIZE) (DST)->b.vtable->resize (DST, SIZE)
 177 
 178 /* Return size in bits of bitset SRC.  */
 179 #define BITSET_SIZE_(SRC) (SRC)->b.vtable->size (SRC)
 180 
 181 /* Return number of bits set in bitset SRC.  */
 182 #define BITSET_COUNT_(SRC) (SRC)->b.vtable->count (SRC)
 183 
 184 /* Return type of bitset SRC.  */
 185 #define BITSET_TYPE_(DST) (DST)->b.vtable->type
 186 
 187 /* Set bit BITNO in bitset DST.  */
 188 #define BITSET_SET_(DST, BITNO) (DST)->b.vtable->set (DST, BITNO)
 189 
 190 /* Reset bit BITNO in bitset DST.  */
 191 #define BITSET_RESET_(DST, BITNO) (DST)->b.vtable->reset (DST, BITNO)
 192 
 193 /* Toggle bit BITNO in bitset DST.  */
 194 #define BITSET_TOGGLE_(DST, BITNO) (DST)->b.vtable->toggle (DST, BITNO)
 195 
 196 /* Return non-zero if bit BITNO in bitset SRC is set.  */
 197 #define BITSET_TEST_(SRC, BITNO) (SRC)->b.vtable->test (SRC, BITNO)
 198 
 199 /* Free bitset SRC.  */
 200 #define BITSET_FREE_(SRC)\
 201  ((SRC)->b.vtable->free ? (SRC)->b.vtable->free (SRC) :(void)0)
 202 
 203 
 204 /* Return SRC == 0.  */
 205 #define BITSET_EMPTY_P_(SRC) (SRC)->b.vtable->empty_p (SRC)
 206 
 207 /* DST = ~0.  */
 208 #define BITSET_ONES_(DST) (DST)->b.vtable->ones (DST)
 209 
 210 /* DST = 0.  */
 211 #define BITSET_ZERO_(DST) (DST)->b.vtable->zero (DST)
 212 
 213 
 214 
 215 /* DST = SRC.  */
 216 #define BITSET_COPY_(DST, SRC) (SRC)->b.vtable->copy (DST, SRC)
 217 
 218 /* Return DST & SRC == 0.  */
 219 #define BITSET_DISJOINT_P_(DST, SRC) (SRC)->b.vtable->disjoint_p (DST, SRC)
 220 
 221 /* Return DST == SRC.  */
 222 #define BITSET_EQUAL_P_(DST, SRC) (SRC)->b.vtable->equal_p (DST, SRC)
 223 
 224 /* DST = ~SRC.  */
 225 #define BITSET_NOT_(DST, SRC) (SRC)->b.vtable->not_ (DST, SRC)
 226 
 227 /* Return DST == DST | SRC.  */
 228 #define BITSET_SUBSET_P_(DST, SRC) (SRC)->b.vtable->subset_p (DST, SRC)
 229 
 230 
 231 /* DST = SRC1 & SRC2.  */
 232 #define BITSET_AND_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_ (DST, SRC1, SRC2)
 233 #define BITSET_AND_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_cmp (DST, SRC1, SRC2)
 234 
 235 /* DST = SRC1 & ~SRC2.  */
 236 #define BITSET_ANDN_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn (DST, SRC1, SRC2)
 237 #define BITSET_ANDN_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn_cmp (DST, SRC1, SRC2)
 238 
 239 /* DST = SRC1 | SRC2.  */
 240 #define BITSET_OR_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_ (DST, SRC1, SRC2)
 241 #define BITSET_OR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_cmp (DST, SRC1, SRC2)
 242 
 243 /* DST = SRC1 ^ SRC2.  */
 244 #define BITSET_XOR_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_ (DST, SRC1, SRC2)
 245 #define BITSET_XOR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_cmp (DST, SRC1, SRC2)
 246 
 247 
 248 
 249 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 250    DST != (SRC1 & SRC2) | SRC3.  */
 251 #define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3) \
 252  (SRC1)->b.vtable->and_or (DST, SRC1, SRC2, SRC3)
 253 #define BITSET_AND_OR_CMP_(DST, SRC1, SRC2, SRC3) \
 254  (SRC1)->b.vtable->and_or_cmp (DST, SRC1, SRC2, SRC3)
 255 
 256 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 257    DST != (SRC1 & ~SRC2) | SRC3.  */
 258 #define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3) \
 259  (SRC1)->b.vtable->andn_or (DST, SRC1, SRC2, SRC3)
 260 #define BITSET_ANDN_OR_CMP_(DST, SRC1, SRC2, SRC3) \
 261  (SRC1)->b.vtable->andn_or_cmp (DST, SRC1, SRC2, SRC3)
 262 
 263 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 264    DST != (SRC1 | SRC2) & SRC3.  */
 265 #define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3) \
 266  (SRC1)->b.vtable->or_and (DST, SRC1, SRC2, SRC3)
 267 #define BITSET_OR_AND_CMP_(DST, SRC1, SRC2, SRC3) \
 268  (SRC1)->b.vtable->or_and_cmp (DST, SRC1, SRC2, SRC3)
 269 
 270 
 271 /* Find list of up to NUM bits set in BSET starting from and including
 272    *NEXT.  Return with actual number of bits found and with *NEXT
 273    indicating where search stopped.  */
 274 #define BITSET_LIST_(BSET, LIST, NUM, NEXT) \
 275  (BSET)->b.vtable->list (BSET, LIST, NUM, NEXT)
 276 
 277 /* Find reverse list of up to NUM bits set in BSET starting from and
 278    including NEXT.  Return with actual number of bits found and with
 279    *NEXT indicating where search stopped.  */
 280 #define BITSET_LIST_REVERSE_(BSET, LIST, NUM, NEXT) \
 281  (BSET)->b.vtable->list_reverse (BSET, LIST, NUM, NEXT)
 282 
 283 /* Iterate left to right over each set bit of WORD.
 284    Each iteration sets POS to the 0-based index of the next set bit in WORD.
 285    Repeatedly resets bits in WORD in place until it's null.  */
 286 #define BITSET_FOR_EACH_BIT(Pos, Word)                  \
 287   for (int Pos = bitset_ffs_ (Word);                    \
 288        0 <= Pos;                                        \
 289        Word ^= 1UL << Pos, Pos = bitset_ffs_ (Word))
 290 
 291 /* Iterate right to left over each set bit of WORD.
 292    Each iteration sets POS to the 0-based index of the next set bit in WORD.
 293    Repeatedly resets bits in WORD in place until it's null.  */
 294 #define BITSET_FOR_EACH_BIT_REVERSE(Pos, Word)          \
 295   for (int Pos = bitset_fls_ (Word);                    \
 296        0 <= Pos;                                        \
 297        Word ^= 1UL << Pos, Pos = bitset_fls_ (Word))
 298 
 299 /* Private functions for bitset implementations.  */
 300 
 301 bool bitset_toggle_ (bitset, bitset_bindex);
 302 
 303 bitset_bindex bitset_count_ (bitset);
 304 
 305 bitset_bindex bitset_size_ (bitset);
 306 
 307 bool bitset_copy_ (bitset, bitset);
 308 
 309 void bitset_and_or_ (bitset, bitset, bitset, bitset);
 310 
 311 bool bitset_and_or_cmp_ (bitset, bitset, bitset, bitset);
 312 
 313 void bitset_andn_or_ (bitset, bitset, bitset, bitset);
 314 
 315 bool bitset_andn_or_cmp_ (bitset, bitset, bitset, bitset);
 316 
 317 void bitset_or_and_ (bitset, bitset, bitset, bitset);
 318 
 319 bool bitset_or_and_cmp_ (bitset, bitset, bitset, bitset);
 320 
 321 /* First set bit in WORD.
 322    Indexes start at 0, return -1 if WORD is null. */
 323 static inline
 324 int bitset_ffs_ (bitset_word word)
     /*  */
 325 {
 326   return ffsl ((long) word) - 1;
 327 }
 328 
 329 /* Last set bit in WORD.
 330    Indexes start at 0, return -1 if WORD is null. */
 331 static inline
 332 int bitset_fls_ (bitset_word word)
     /*  */
 333 {
 334   return integer_length_l (word) - 1;
 335 }
 336 
 337 #endif /* _BBITSET_H  */
/* */
root/maint/gnulib/lib/bitset/base.h

INCLUDED FROM

DEFINITIONS
