]> 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
* src/files.c (action_obstack): Remove, unused.
[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/* Return bytes required for bitset of desired type and size. */
48extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
49
50/* Initialise a bitset with desired type and size. */
51extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
52
53/* Select an implementation type based on the desired bitset size
54 and attributes. */
55extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
56 bitset_attrs));
57
58/* Create a bitset of desired type and size. The bitset is zeroed. */
59extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
60
61/* Free bitset. */
62extern void bitset_free PARAMS ((bitset));
63
64/* Create a bitset of desired type and size using an obstack. The
65 bitset is zeroed. */
66extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
67 bitset_bindex, enum bitset_type));
68
69/* Free bitset allocated on obstack. */
70extern void bitset_obstack_free PARAMS ((bitset));
71
72/* Create a bitset of desired size and attributes. The bitset is zeroed. */
73extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
74
75/* Return size in bits of bitset SRC. */
76extern int bitset_size PARAMS ((bitset));
77
78/* Return number of bits set in bitset SRC. */
79extern int bitset_count PARAMS ((bitset));
80
81#if BITSET_CACHE && BITSET_INLINE
82static inline void bitset_set PARAMS ((bitset, bitset_bindex));
83static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
84static inline int bitset_test PARAMS ((bitset, bitset_bindex));
85
86/* Set bit BITNO in bitset BSET. */
87static inline void bitset_set (bset, bitno)
88 bitset bset;
89 bitset_bindex bitno;
90{
91 bitset_windex index = bitno / BITSET_WORD_BITS;
92 bitset_windex offset = index - bset->b.cindex;
93
94 if (offset < bset->b.csize)
95 bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
96 else
97 BITSET_SET_ (bset, bitno);
98}
99
100
101/* Reset bit BITNO in bitset BSET. */
102static inline void bitset_reset (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] &= ~(1 << (bitno % BITSET_WORD_BITS));
111 else
112 BITSET_RESET_ (bset, bitno);
113}
114
115
116/* Test bit BITNO in bitset BSET. */
117static inline int bitset_test (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 return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
126 else
127 return BITSET_TEST_ (bset, bitno);
128}
129#endif
130
131#if BITSET_CACHE && ! BITSET_INLINE
132
133/* Set bit BITNO in bitset BSET. */
134#define bitset_set(bset, bitno) \
135do \
136{ \
137 bitset_bindex _bitno = (bitno); \
138 bitset_windex _index = _bitno / BITSET_WORD_BITS; \
139 bitset_windex _offset = _index - (bset)->b.cindex; \
140 \
141 if (_offset < (bset)->b.csize) \
142 (bset)->b.cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS)); \
143 else \
144 BITSET_SET_ ((bset), _bitno); \
145} while (0)
146
147
148/* Reset bit BITNO in bitset BSET. */
149#define bitset_reset(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] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \
158 else \
159 BITSET_RESET_ ((bset), _bitno); \
160} while (0)
161
162
163/* Test bit BITNO in bitset BSET. */
164#define bitset_test(bset, bitno) \
165(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
166 ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
167 >> ((bitno) % BITSET_WORD_BITS)) & 1 \
168 : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
169#endif
170
171#if ! BITSET_CACHE
172/* Set bit BITNO in bitset SRC. */
173#define bitset_set(SRC, BITNO) BITSET_SET_ (SRC, BITNO)
174
175/* Reset bit BITNO in bitset SRC. */
176#define bitset_reset(SRC, BITNO) BITSET_RESET_ (SRC, BITNO)
177
178/* Return non-zero if bit BITNO in bitset SRC is set. */
179#define bitset_test(SRC, BITNO) BITSET_TEST_ (SRC, BITNO)
180#endif
181
182/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */
183extern int bitset_toggle PARAMS ((bitset, bitset_bindex));
184
185/* DST = 0. */
186extern int bitset_zero PARAMS ((bitset));
187
188/* DST = ~0. */
189extern int bitset_ones PARAMS ((bitset));
190
191/* Return non-zero if all bits in bitset SRC are reset. */
192extern int bitset_empty_p PARAMS ((bitset));
193
194/* Return DST == DST | SRC. */
195extern int bitset_subset_p PARAMS ((bitset, bitset));
196
197/* Return DST == SRC. */
198extern int bitset_equal_p PARAMS ((bitset, bitset));
199
200/* Return DST & SRC == 0. */
201extern int bitset_disjoint_p PARAMS ((bitset, bitset));
202
203/* DST == SRC. */
204extern int bitset_copy PARAMS ((bitset, bitset));
205
206/* DST = ~SRC. */
207extern int bitset_not PARAMS ((bitset, bitset));
208
209/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
210extern int bitset_or PARAMS ((bitset, bitset, bitset));
211
212/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
213extern int bitset_and PARAMS ((bitset, bitset, bitset));
214
215/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
216extern int bitset_xor PARAMS ((bitset, bitset, bitset));
217
218/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
219extern int bitset_andn PARAMS ((bitset, bitset, bitset));
220
221/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
222 DST != (SRC1 | SRC2) & SRC3. */
223extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
224
225/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
226 DST != (SRC1 & SRC2) | SRC3. */
227extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
228
229/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
230 DST != (SRC1 & ~SRC2) | SRC3. */
231extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));
232
233/* Find next bit set in BSET starting from and including BITNO. */
234extern int bitset_next PARAMS ((bitset, bitset_bindex));
235
236/* Find previous bit set in BSET starting from and including BITNO. */
237extern int bitset_prev PARAMS ((bitset, bitset_bindex));
238
239/* Return non-zero if BITNO in SRC is the only set bit. */
240extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
241
242/* Find list of up to NUM bits set in BSET starting from and including
243 *NEXT. Return with actual number of bits found and with *NEXT
244 indicating where search stopped. */
245#if BITSET_STATS
246extern int bitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
247 bitset_bindex *));
248#else
249#define bitset_list(BSET, LIST, NUM, NEXT) \
250BITSET_LIST_ (BSET, LIST, NUM, NEXT)
251#endif
252
253/* Find reverse list of up to NUM bits set in BSET starting from and
254 including NEXT. Return with actual number of bits found and with
255 *NEXT indicating where search stopped. */
256#define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
257BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT)
258
259/* Find first set bit. */
260extern int bitset_first PARAMS ((bitset));
261
262/* Find last set bit. */
263extern int bitset_last PARAMS ((bitset));
264
265/* Dump bitset. */
266extern void bitset_dump PARAMS ((FILE *, bitset));
267
268/* Loop over all elements of BSET, starting with MIN, executing CODE. */
269#define BITSET_EXECUTE(BSET, MIN, N, CODE) \
270do { \
271 bitset_bindex _list[BITSET_LIST_SIZE]; \
272 bitset_bindex _next = (MIN); \
273 int _num; \
274 \
275 while ((_num = bitset_list ((BSET), _list, BITSET_LIST_SIZE, &_next)))\
276 { \
277 int _i; \
278 \
279 for (_i = 0; _i < _num; _i++) \
280 { \
281 (N) = _list[_i]; \
282 CODE; \
283 } \
284 if (_num < BITSET_LIST_SIZE) \
285 break; \
286 } \
287} while (0)
288
289
290/* Loop over all elements of BSET, in reverse order starting with
291 MIN, executing CODE. */
292#define BITSET_REVERSE_EXECUTE(BSET, MIN, N, CODE) \
293do { \
294 bitset_bindex _list[BITSET_LIST_SIZE]; \
295 bitset_bindex _next = (MIN); \
296 int _num; \
297 \
298 while ((_num = bitset_reverse_list ((BSET), _list, \
299 BITSET_LIST_SIZE, &_next))) \
300 { \
301 int _i; \
302 \
303 for (_i = 0; _i < _num; _i++) \
304 { \
305 (N) = _list[_i]; \
306 CODE; \
307 } \
308 if (_num < BITSET_LIST_SIZE) \
309 break; \
310 } \
311} while (0)
312
313
314/* Define set operations in terms of logical operations. */
315
316#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
317
318#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
319
320#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
321
322#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
323 bitset_andn_or (DST, SRC1, SRC2, SRC3)
324
325
326/* Release any memory tied up with bitsets. */
327extern void bitset_release_memory PARAMS ((void));
328
329/* Initialise bitset stats. */
330extern void bitset_stats_init PARAMS ((void));
331
332/* Dump bitset stats. */
333extern void bitset_stats_dump PARAMS ((FILE *));
334
335/* Function to debug bitset from debugger. */
336extern void debug_bitset PARAMS ((bitset));
337
338/* Function to debug bitset stats from debugger. */
339extern void debug_bitset_stats PARAMS ((void));
340
341#endif /* _BITSET_H */
bison