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
bitset_set(bitset bset,bitset_bindex bitno)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
bitset_reset(bitset bset,bitset_bindex bitno)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
bitset_test(bitset bset,bitset_bindex bitno)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 */
397