1 /* Generic bitsets.
2 Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
18
19 #ifndef _BITSET_H
20 #define _BITSET_H
21
22 /* This file is the public interface to the bitset abstract data type.
23 Only use the functions and macros defined in this file. */
24
25 #include "bbitset.h"
26 #include "obstack.h"
27 #include <stdio.h>
28
29 #if USE_UNLOCKED_IO
30 # include "unlocked-io.h"
31 #endif
32
33 /* Attributes used to select a bitset implementation. */
34 enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */
35 BITSET_VARIABLE = 2, /* Bitset size variable. */
36 BITSET_DENSE = 4, /* Bitset dense. */
37 BITSET_SPARSE = 8, /* Bitset sparse. */
38 BITSET_FRUGAL = 16, /* Prefer most compact. */
39 BITSET_GREEDY = 32}; /* Prefer fastest at memory expense. */
40
41 typedef unsigned int bitset_attrs;
42
43 /* The contents of the union should be considered to be private.
44 While I would like to make this union opaque, it needs to be
45 visible for the inline bit set/test functions, and for delegation
46 to the proper implementation. */
47 union bitset_union
48 {
49 /* This must be the first member of every other structure that is a
50 member of this union. */
51 struct bbitset_struct b; /* Base bitset data. */
52
53 struct abitset_struct
54 {
55 struct bbitset_struct b;
56 bitset_word words[1]; /* The array of bits. */
57 } a;
58
59 struct ebitset_struct
60 {
61 struct bbitset_struct b;
62 bitset_windex size; /* Number of elements. */
63 struct ebitset_elt_struct **elts; /* Expanding array of ptrs to elts. */
64 } e;
65
66 struct lbitset_struct
67 {
68 struct bbitset_struct b;
69 struct lbitset_elt_struct *head; /* First element in linked list. */
70 struct lbitset_elt_struct *tail; /* Last element in linked list. */
71 } l;
72
73 struct bitset_stats_struct
74 {
75 struct bbitset_struct b;
76 bitset bset;
77 } s;
78
79 struct vbitset_struct
80 {
81 struct bbitset_struct b;
82 bitset_windex size; /* Allocated size of array. */
83 } v;
84
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 extern size_t bitset_bytes (enum bitset_type, bitset_bindex);
101
102 /* Initialise a bitset with desired type and size. */
103 extern 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 extern 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 extern bitset bitset_alloc (bitset_bindex, enum bitset_type);
111
112 /* Free bitset. */
113 extern void bitset_free (bitset);
114
115 /* Create a bitset of desired type and size using an obstack. The
116 bitset is zeroed. */
117 extern bitset bitset_obstack_alloc (struct obstack *bobstack,
118 bitset_bindex, enum bitset_type);
119
120 /* Free bitset allocated on obstack. */
121 extern void bitset_obstack_free (bitset);
122
123 /* Create a bitset of desired size and attributes. The bitset is zeroed. */
124 extern bitset bitset_create (bitset_bindex, bitset_attrs);
125
126 /* Return bitset type. */
127 extern enum bitset_type bitset_type_get (bitset);
128
129 /* Return bitset type name. */
130 extern const char *bitset_type_name_get (bitset);
131
132
133 /* Set bit BITNO in bitset BSET. */
134 static inline void
bitset_set(bitset bset,bitset_bindex bitno)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
bitset_reset(bitset bset,bitset_bindex bitno)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
bitset_test(bitset bset,bitset_bindex bitno)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 of bitset. */
182 extern void bitset_resize (bitset, bitset_bindex);
183
184 /* Return number of bits set in bitset SRC. */
185 #define bitset_count(SRC) BITSET_COUNT_ (SRC)
186
187
188 /* Return SRC == 0. */
189 #define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
190
191 /* DST = ~0. */
192 #define bitset_ones(DST) BITSET_ONES_ (DST)
193
194 /* DST = 0. */
195 #define bitset_zero(DST) BITSET_ZERO_ (DST)
196
197
198
199 /* DST = SRC. */
200 #define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
201
202 /* Return DST & SRC == 0. */
203 #define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
204
205 /* Return DST == SRC. */
206 #define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
207
208 /* DST = ~SRC. */
209 #define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
210
211 /* Return DST == DST | SRC. */
212 #define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
213
214
215
216 /* DST = SRC1 & SRC2. */
217 #define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
218
219 /* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
220 #define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
221
222 /* DST = SRC1 & ~SRC2. */
223 #define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
224
225 /* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
226 #define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
227
228 /* DST = SRC1 | SRC2. */
229 #define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
230
231 /* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
232 #define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
233
234 /* DST = SRC1 ^ SRC2. */
235 #define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
236
237 /* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
238 #define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
239
240
241
242 /* DST = (SRC1 & SRC2) | SRC3. */
243 #define bitset_and_or(DST, SRC1, SRC2, SRC3) \
244 BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
245
246 /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
247 DST != (SRC1 & SRC2) | SRC3. */
248 #define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
249 BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
250
251 /* DST = (SRC1 & ~SRC2) | SRC3. */
252 #define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
253 BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
254
255 /* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
256 DST != (SRC1 & ~SRC2) | SRC3. */
257 #define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
258 BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
259
260 /* DST = (SRC1 | SRC2) & SRC3. */
261 #define bitset_or_and(DST, SRC1, SRC2, SRC3)\
262 BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
263
264 /* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
265 DST != (SRC1 | SRC2) & SRC3. */
266 #define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
267 BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
268
269 /* Find list of up to NUM bits set in BSET starting from and including
270 *NEXT. Return with actual number of bits found and with *NEXT
271 indicating where search stopped. */
272 #define bitset_list(BSET, LIST, NUM, NEXT) \
273 BITSET_LIST_ (BSET, LIST, NUM, NEXT)
274
275 /* Find reverse list of up to NUM bits set in BSET starting from and
276 including NEXT. Return with actual number of bits found and with
277 *NEXT indicating where search stopped. */
278 #define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
279 BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
280
281 /* Return true if both bitsets are of the same type and size. */
282 extern bool bitset_compatible_p (bitset bset1, bitset bset2);
283
284 /* Find next set bit from the given bit index. */
285 extern bitset_bindex bitset_next (bitset, bitset_bindex);
286
287 /* Find previous set bit from the given bit index. */
288 extern bitset_bindex bitset_prev (bitset, bitset_bindex);
289
290 /* Find first set bit. */
291 extern bitset_bindex bitset_first (bitset);
292
293 /* Find last set bit. */
294 extern bitset_bindex bitset_last (bitset);
295
296 /* Return nonzero if this is the only set bit. */
297 extern bool bitset_only_set_p (bitset, bitset_bindex);
298
299 /* Dump bitset. */
300 extern void bitset_dump (FILE *, bitset);
301
302 /* Loop over all elements of BSET, starting with MIN, setting INDEX
303 to the index of each set bit. For example, the following will print
304 the bits set in a bitset:
305
306 bitset_bindex i;
307 bitset_iterator iter;
308
309 BITSET_FOR_EACH (iter, src, i, 0)
310 {
311 printf ("%lu ", (unsigned long int) i);
312 };
313 */
314 #define BITSET_FOR_EACH(ITER, BSET, INDEX, MIN) \
315 for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
316 (ITER.num == BITSET_LIST_SIZE) \
317 && (ITER.num = bitset_list (BSET, ITER.list, \
318 BITSET_LIST_SIZE, &ITER.next));) \
319 for (ITER.i = 0; \
320 ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
321 ITER.i++)
322
323
324 /* Loop over all elements of BSET, in reverse order starting with
325 MIN, setting INDEX to the index of each set bit. For example, the
326 following will print the bits set in a bitset in reverse order:
327
328 bitset_bindex i;
329 bitset_iterator iter;
330
331 BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
332 {
333 printf ("%lu ", (unsigned long int) i);
334 };
335 */
336 #define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, MIN) \
337 for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
338 (ITER.num == BITSET_LIST_SIZE) \
339 && (ITER.num = bitset_list_reverse (BSET, ITER.list, \
340 BITSET_LIST_SIZE, &ITER.next));) \
341 for (ITER.i = 0; \
342 ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
343 ITER.i++)
344
345
346 /* Define set operations in terms of logical operations. */
347
348 #define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
349 #define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
350
351 #define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
352 #define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
353
354 #define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
355 #define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
356
357 /* Symmetrical difference. */
358 #define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
359 #define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
360
361 /* Union of difference. */
362 #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
363 bitset_andn_or (DST, SRC1, SRC2, SRC3)
364 #define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
365 bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
366
367
368 /* Release any memory tied up with bitsets. */
369 extern void bitset_release_memory (void);
370
371 /* Enable bitset stats gathering. */
372 extern void bitset_stats_enable (void);
373
374 /* Disable bitset stats gathering. */
375 extern void bitset_stats_disable (void);
376
377 /* Read bitset stats file of accummulated stats. */
378 void bitset_stats_read (const char *file_name);
379
380 /* Write bitset stats file of accummulated stats. */
381 void bitset_stats_write (const char *file_name);
382
383 /* Dump bitset stats. */
384 extern void bitset_stats_dump (FILE *);
385
386 /* Function to debug bitset from debugger. */
387 extern void debug_bitset (bitset);
388
389 /* Function to debug bitset stats from debugger. */
390 extern void debug_bitset_stats (void);
391
392 #endif /* _BITSET_H */
393