1 | /* Generic bitsets. |
2 | |
3 | Copyright (C) 2002-2004, 2009-2015, 2018-2019 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 _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 | /* Return bytes required for bitset of desired type and size. */ |
100 | size_t bitset_bytes (enum bitset_type, bitset_bindex); |
101 | |
102 | /* Initialise a bitset with desired type and size. */ |
103 | bitset bitset_init (bitset, bitset_bindex, enum bitset_type); |
104 | |
105 | /* Select an implementation type based on the desired bitset size |
106 | and attributes. */ |
107 | enum bitset_type bitset_type_choose (bitset_bindex, bitset_attrs); |
108 | |
109 | /* Create a bitset of desired type and size. The bitset is zeroed. */ |
110 | bitset bitset_alloc (bitset_bindex, enum bitset_type); |
111 | |
112 | /* Free bitset. */ |
113 | void bitset_free (bitset); |
114 | |
115 | /* Create a bitset of desired type and size using an obstack. The |
116 | bitset is zeroed. */ |
117 | bitset bitset_obstack_alloc (struct obstack *bobstack, |
118 | bitset_bindex, enum bitset_type); |
119 | |
120 | /* Free bitset allocated on obstack. */ |
121 | void bitset_obstack_free (bitset); |
122 | |
123 | /* Create a bitset of desired size and attributes. The bitset is zeroed. */ |
124 | bitset bitset_create (bitset_bindex, bitset_attrs); |
125 | |
126 | /* Return bitset type. */ |
127 | enum bitset_type bitset_type_get (bitset); |
128 | |
129 | /* Return bitset type name. */ |
130 | const char *bitset_type_name_get (bitset); |
131 | |
132 | |
133 | /* Set bit BITNO in bitset BSET. */ |
134 | static inline void |
135 | bitset_set (bitset bset, bitset_bindex bitno) |
136 | { |
137 | bitset_windex windex = bitno / BITSET_WORD_BITS; |
138 | bitset_windex offset = windex - bset->b.cindex; |
139 | |
140 | if (offset < bset->b.csize) |
141 | bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS)); |
142 | else |
143 | BITSET_SET_ (bset, bitno); |
144 | } |
145 | |
146 | |
147 | /* Reset bit BITNO in bitset BSET. */ |
148 | static inline void |
149 | bitset_reset (bitset bset, bitset_bindex bitno) |
150 | { |
151 | bitset_windex windex = bitno / BITSET_WORD_BITS; |
152 | bitset_windex offset = windex - bset->b.cindex; |
153 | |
154 | if (offset < bset->b.csize) |
155 | bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS)); |
156 | else |
157 | BITSET_RESET_ (bset, bitno); |
158 | } |
159 | |
160 | |
161 | /* Test bit BITNO in bitset BSET. */ |
162 | static inline bool |
163 | bitset_test (bitset bset, bitset_bindex bitno) |
164 | { |
165 | bitset_windex windex = bitno / BITSET_WORD_BITS; |
166 | bitset_windex offset = windex - bset->b.cindex; |
167 | |
168 | if (offset < bset->b.csize) |
169 | return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1; |
170 | else |
171 | return BITSET_TEST_ (bset, bitno); |
172 | } |
173 | |
174 | |
175 | /* Toggle bit BITNO in bitset BSET and return non-zero if now set. */ |
176 | #define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno) |
177 | |
178 | /* Return size in bits of bitset SRC. */ |
179 | #define bitset_size(SRC) BITSET_SIZE_ (SRC) |
180 | |
181 | /* Change size in bits of bitset. New bits are zeroed. Return |
182 | SIZE. */ |
183 | #define bitset_resize(DST, SIZE) BITSET_RESIZE_ (DST, SIZE) |
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 | bool bitset_compatible_p (bitset bset1, bitset bset2); |
284 | |
285 | /* Find next set bit from the given bit index. */ |
286 | bitset_bindex bitset_next (bitset, bitset_bindex); |
287 | |
288 | /* Find previous set bit from the given bit index. */ |
289 | bitset_bindex bitset_prev (bitset, bitset_bindex); |
290 | |
291 | /* Find first set bit. */ |
292 | bitset_bindex bitset_first (bitset); |
293 | |
294 | /* Find last set bit. */ |
295 | bitset_bindex bitset_last (bitset); |
296 | |
297 | /* Return nonzero if this is the only set bit. */ |
298 | bool bitset_only_set_p (bitset, bitset_bindex); |
299 | |
300 | /* Dump bitset. */ |
301 | 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 | printf ("%lu ", (unsigned long) i); |
312 | */ |
313 | #define BITSET_FOR_EACH(ITER, BSET, INDEX, MIN) \ |
314 | for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \ |
315 | (ITER.num == BITSET_LIST_SIZE) \ |
316 | && (ITER.num = bitset_list (BSET, ITER.list, \ |
317 | BITSET_LIST_SIZE, &ITER.next));) \ |
318 | for (ITER.i = 0; \ |
319 | ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \ |
320 | ITER.i++) |
321 | |
322 | |
323 | /* Loop over all elements of BSET, in reverse order starting with |
324 | MIN, setting INDEX to the index of each set bit. For example, the |
325 | following will print the bits set in a bitset in reverse order: |
326 | |
327 | bitset_bindex i; |
328 | bitset_iterator iter; |
329 | |
330 | BITSET_FOR_EACH_REVERSE (iter, src, i, 0) |
331 | printf ("%lu ", (unsigned long) i); |
332 | */ |
333 | #define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, MIN) \ |
334 | for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \ |
335 | (ITER.num == BITSET_LIST_SIZE) \ |
336 | && (ITER.num = bitset_list_reverse (BSET, ITER.list, \ |
337 | BITSET_LIST_SIZE, &ITER.next));) \ |
338 | for (ITER.i = 0; \ |
339 | ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \ |
340 | ITER.i++) |
341 | |
342 | |
343 | /* Define set operations in terms of logical operations. */ |
344 | |
345 | #define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2) |
346 | #define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2) |
347 | |
348 | #define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2) |
349 | #define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2) |
350 | |
351 | #define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2) |
352 | #define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2) |
353 | |
354 | /* Symmetrical difference. */ |
355 | #define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2) |
356 | #define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2) |
357 | |
358 | /* Union of difference. */ |
359 | #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \ |
360 | bitset_andn_or (DST, SRC1, SRC2, SRC3) |
361 | #define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \ |
362 | bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3) |
363 | |
364 | |
365 | /* Release any memory tied up with bitsets. */ |
366 | void bitset_release_memory (void); |
367 | |
368 | /* Enable bitset stats gathering. */ |
369 | void bitset_stats_enable (void); |
370 | |
371 | /* Disable bitset stats gathering. */ |
372 | void bitset_stats_disable (void); |
373 | |
374 | /* Read bitset stats file of accummulated stats. */ |
375 | void bitset_stats_read (const char *file_name); |
376 | |
377 | /* Write bitset stats file of accummulated stats. */ |
378 | void bitset_stats_write (const char *file_name); |
379 | |
380 | /* Dump bitset stats. */ |
381 | void bitset_stats_dump (FILE *); |
382 | |
383 | /* Function to debug bitset from debugger. */ |
384 | void debug_bitset (bitset); |
385 | |
386 | /* Function to debug bitset stats from debugger. */ |
387 | void debug_bitset_stats (void); |
388 | |
389 | #endif /* _GL_BITSET_H */ |
390 | |