]> git.saurik.com Git - bison.git/blame_incremental - lib/bitset.h
projects / bison.git / blame_incremental
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (non-incremental) | history | HEAD
(INCLUDES): Do not include from the intl directory, which has been removed.
[bison.git] / lib / bitset.h
... / ...
CommitLineData
1/* Generic bitsets.
2 Copyright (C) 2002 Free Software Foundation, Inc.
3 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
4
5This program is free software; you can redistribute it and/or modify
6it under the terms of the GNU General Public License as published by
7the Free Software Foundation; either version 2 of the License, or
8(at your option) any later version.
9
10This program is distributed in the hope that it will be useful,
11but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13GNU General Public License for more details.
14
15You should have received a copy of the GNU General Public License
16along with this program; if not, write to the Free Software
17Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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/* Attributes used to select a bitset implementation. */
30enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */
31 BITSET_VARIABLE = 2, /* Bitset size variable. */
32 BITSET_DENSE = 4, /* Bitset dense. */
33 BITSET_SPARSE = 8, /* Bitset sparse. */
34 BITSET_FRUGAL = 16, /* Prefer most compact. */
35 BITSET_GREEDY = 32}; /* Prefer fastest. */
36
37typedef unsigned int bitset_attrs;
38
39/* The contents of the structure should be considered to be private.
40 While I would like to make this structure opaque, it needs to be
41 visible for the inline bit set/test functions. */
42struct bitset_struct
43{
44 struct bbitset_struct b;
45};
46
47
48/* The contents of this structure should be considered private.
49 It is used for iterating over set bits. */
50typedef struct
51{
52 bitset_bindex list[BITSET_LIST_SIZE];
53 bitset_bindex next;
54 int num;
55 int i;
56} bitset_iterator;
57
58
59/* Return bytes required for bitset of desired type and size. */
60extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
61
62/* Initialise a bitset with desired type and size. */
63extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
64
65/* Select an implementation type based on the desired bitset size
66 and attributes. */
67extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
68 bitset_attrs));
69
70/* Create a bitset of desired type and size. The bitset is zeroed. */
71extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
72
73/* Free bitset. */
74extern void bitset_free PARAMS ((bitset));
75
76/* Create a bitset of desired type and size using an obstack. The
77 bitset is zeroed. */
78extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
79 bitset_bindex, enum bitset_type));
80
81/* Free bitset allocated on obstack. */
82extern void bitset_obstack_free PARAMS ((bitset));
83
84/* Create a bitset of desired size and attributes. The bitset is zeroed. */
85extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
86
87/* Return size in bits of bitset SRC. */
88extern int bitset_size PARAMS ((bitset));
89
90/* Return number of bits set in bitset SRC. */
91extern int bitset_count PARAMS ((bitset));
92
93/* Return bitset type. */
94extern enum bitset_type bitset_type_get PARAMS ((bitset));
95
96#if BITSET_INLINE
97static inline void bitset_set PARAMS ((bitset, bitset_bindex));
98static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
99static inline int bitset_test PARAMS ((bitset, bitset_bindex));
100
101/* Set bit BITNO in bitset BSET. */
102static inline void bitset_set (bset, bitno)
103 bitset bset;
104 bitset_bindex bitno;
105{
106 bitset_windex index = bitno / BITSET_WORD_BITS;
107 bitset_windex offset = index - bset->b.cindex;
108
109 if (offset < bset->b.csize)
110 bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
111 else
112 BITSET_SET_ (bset, bitno);
113}
114
115
116/* Reset bit BITNO in bitset BSET. */
117static inline void bitset_reset (bset, bitno)
118 bitset bset;
119 bitset_bindex bitno;
120{
121 bitset_windex index = bitno / BITSET_WORD_BITS;
122 bitset_windex offset = index - bset->b.cindex;
123
124 if (offset < bset->b.csize)
125 bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
126 else
127 BITSET_RESET_ (bset, bitno);
128}
129
130
131/* Test bit BITNO in bitset BSET. */
132static inline int bitset_test (bset, bitno)
133 bitset bset;
134 bitset_bindex bitno;
135{
136 bitset_windex index = bitno / BITSET_WORD_BITS;
137 bitset_windex offset = index - bset->b.cindex;
138
139 if (offset < bset->b.csize)
140 return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
141 else
142 return BITSET_TEST_ (bset, bitno);
143}
144#endif
145
146#if ! BITSET_INLINE
147
148/* Set bit BITNO in bitset BSET. */
149#define bitset_set(bset, bitno) \
150do \
151{ \
152 bitset_bindex _bitno = (bitno); \
153 bitset_windex _index = _bitno / BITSET_WORD_BITS; \
154 bitset_windex _offset = _index - (bset)->b.cindex; \
155 \
156 if (_offset < (bset)->b.csize) \
157 (bset)->b.cdata[_offset] |= \
158 ((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \
159 else \
160 BITSET_SET_ ((bset), _bitno); \
161} while (0)
162
163
164/* Reset bit BITNO in bitset BSET. */
165#define bitset_reset(bset, bitno) \
166do \
167{ \
168 bitset_bindex _bitno = (bitno); \
169 bitset_windex _index = _bitno / BITSET_WORD_BITS; \
170 bitset_windex _offset = _index - (bset)->b.cindex; \
171 \
172 if (_offset < (bset)->b.csize) \
173 (bset)->b.cdata[_offset] &= \
174 ~((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \
175 else \
176 BITSET_RESET_ ((bset), _bitno); \
177} while (0)
178
179
180/* Test bit BITNO in bitset BSET. */
181#define bitset_test(bset, bitno) \
182(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
183 ? (((int) \
184 ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
185 >> ((bitno) % BITSET_WORD_BITS))) \
186 & 1) \
187 : BITSET_TEST_ ((bset), (bitno)))
188#endif
189
190
191/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */
192extern int bitset_toggle PARAMS ((bitset, bitset_bindex));
193
194/* DST = 0. */
195extern int bitset_zero PARAMS ((bitset));
196
197/* DST = ~0. */
198extern int bitset_ones PARAMS ((bitset));
199
200/* Return non-zero if all bits in bitset SRC are reset. */
201extern int bitset_empty_p PARAMS ((bitset));
202
203/* Return DST == DST | SRC. */
204extern int bitset_subset_p PARAMS ((bitset, bitset));
205
206/* Return DST == SRC. */
207extern int bitset_equal_p PARAMS ((bitset, bitset));
208
209/* Return DST & SRC == 0. */
210extern int bitset_disjoint_p PARAMS ((bitset, bitset));
211
212/* DST == SRC. */
213extern int bitset_copy PARAMS ((bitset, bitset));
214
215/* DST = ~SRC. */
216extern int bitset_not PARAMS ((bitset, bitset));
217
218/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
219extern int bitset_or PARAMS ((bitset, bitset, bitset));
220
221/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
222extern int bitset_and PARAMS ((bitset, bitset, bitset));
223
224/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
225extern int bitset_xor PARAMS ((bitset, bitset, bitset));
226
227/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
228extern int bitset_andn PARAMS ((bitset, bitset, bitset));
229
230/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
231 DST != (SRC1 | SRC2) & SRC3. */
232extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
233
234/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
235 DST != (SRC1 & SRC2) | SRC3. */
236extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
237
238/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
239 DST != (SRC1 & ~SRC2) | SRC3. */
240extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));
241
242/* Find next bit set in BSET starting from and including BITNO. */
243extern int bitset_next PARAMS ((bitset, bitset_bindex));
244
245/* Find previous bit set in BSET starting from and including BITNO. */
246extern int bitset_prev PARAMS ((bitset, bitset_bindex));
247
248/* Return non-zero if BITNO in SRC is the only set bit. */
249extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
250
251/* Find list of up to NUM bits set in BSET starting from and including
252 *NEXT. Return with actual number of bits found and with *NEXT
253 indicating where search stopped. */
254#define bitset_list(BSET, LIST, NUM, NEXT) \
255BITSET_LIST_ (BSET, LIST, NUM, NEXT)
256
257/* Find reverse list of up to NUM bits set in BSET starting from and
258 including NEXT. Return with actual number of bits found and with
259 *NEXT indicating where search stopped. */
260#define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
261BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT)
262
263/* Find first set bit. */
264extern int bitset_first PARAMS ((bitset));
265
266/* Find last set bit. */
267extern int bitset_last PARAMS ((bitset));
268
269/* Dump bitset. */
270extern void bitset_dump PARAMS ((FILE *, bitset));
271
272/* Loop over all elements of BSET, starting with MIN, setting BIT
273 to the index of each set bit. */
274#define BITSET_FOR_EACH(ITER, BSET, BIT, MIN) \
275 for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
276 (ITER.num == BITSET_LIST_SIZE) \
277 && (ITER.num = bitset_list (BSET, ITER.list, \
278 BITSET_LIST_SIZE, &ITER.next));) \
279 for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
280
281
282/* Loop over all elements of BSET, in reverse order starting with
283 MIN, setting BIT to the index of each set bit. */
284#define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN) \
285 for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
286 (ITER.num == BITSET_LIST_SIZE) \
287 && (ITER.num = bitset_list_reverse (BSET, ITER.list, \
288 BITSET_LIST_SIZE, &ITER.next));) \
289 for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
290
291
292/* Define set operations in terms of logical operations. */
293
294#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
295
296#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
297
298#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
299
300#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
301 bitset_andn_or (DST, SRC1, SRC2, SRC3)
302
303
304/* Release any memory tied up with bitsets. */
305extern void bitset_release_memory PARAMS ((void));
306
307/* Enable bitset stats gathering. */
308extern void bitset_stats_enable PARAMS ((void));
309
310/* Disable bitset stats gathering. */
311extern void bitset_stats_disable PARAMS ((void));
312
313/* Read bitset stats file of accummulated stats. */
314void bitset_stats_read PARAMS ((const char *filename));
315
316/* Write bitset stats file of accummulated stats. */
317void bitset_stats_write PARAMS ((const char *filename));
318
319/* Dump bitset stats. */
320extern void bitset_stats_dump PARAMS ((FILE *));
321
322/* Function to debug bitset from debugger. */
323extern void debug_bitset PARAMS ((bitset));
324
325/* Function to debug bitset stats from debugger. */
326extern void debug_bitset_stats PARAMS ((void));
327
328#endif /* _BITSET_H */
329
bison