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