]> git.saurik.com Git - bison.git/blame - lib/bitset.h
projects / bison.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
* lib/bitset-int.h, lib/bitset.c, lib/bitset.h, lib/bitsetv.c,
[bison.git] / lib / bitset.h
CommitLineData
7086e707
AD		 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#if HAVE_CONFIG_H
23# include <config.h>
24#endif
25
26#define BITSET_STATS 1
27
28# ifndef PARAMS
29# if defined PROTOTYPES || (defined __STDC__ && __STDC__)
30# define PARAMS(Args) Args
31# else
32# define PARAMS(Args) ()
33# endif
34# endif
35
36# ifndef __attribute__
37# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
38# define __attribute__(x)
39# endif
40# endif
41
42# ifndef ATTRIBUTE_NORETURN
43# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
44# endif
45
46# ifndef ATTRIBUTE_UNUSED
47# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
48# endif
49
50#include "bitset-int.h"
51#include "sbitset.h"
52#include "lbitset.h"
53#include "ebitset.h"
54#include "obstack.h"
55#include <stdio.h>
56#include "xalloc.h"
57
58enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */
59 BITSET_VARIABLE = 2, /* Bitset size variable. */
60 BITSET_DENSE = 4, /* Bitset dense. */
61 BITSET_SPARSE = 8, /* Bitset sparse. */
62 BITSET_FRUGAL = 16, /* Prefer most compact. */
63 BITSET_GREEDY = 32}; /* Prefer fastest. */
64
65typedef unsigned int bitset_attrs;
66
67/* The elements of these structures should be considered
68 to be private. */
69typedef struct bitset_struct
70{
71 struct bitset_ops_struct *ops;
72 bitset_windex cindex; /* Cache word index. */
73 bitset_windex csize; /* Cache size in words. */
74 bitset_word *cdata; /* Cache data pointer. */
75 union bitset_data
76 {
77 struct sbitset_struct s;
78 struct lbitset_struct l;
79 struct ebitset_struct e;
80 } u;
81} *bitset;
82
83
84/* The contents of this structure should be considered private. */
85struct bitset_ops_struct
86{
87 void (*set) PARAMS ((struct bitset_struct *, bitset_bindex));
88 void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex));
89 int (*test) PARAMS ((struct bitset_struct *, bitset_bindex));
90 int (*size) PARAMS ((struct bitset_struct *));
91 int (*op1) PARAMS ((struct bitset_struct *, enum bitset_ops));
92 int (*op2) PARAMS ((struct bitset_struct *, struct bitset_struct *,
93 enum bitset_ops));
94 int (*op3) PARAMS ((struct bitset_struct *, struct bitset_struct *,
95 struct bitset_struct *, enum bitset_ops));
96 int (*op4) PARAMS ((struct bitset_struct *, struct bitset_struct *,
97 struct bitset_struct *, struct bitset_struct *,
98 enum bitset_ops));
99 int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *,
100 bitset_bindex, bitset_bindex *));
101 int (*reverse_list) PARAMS ((struct bitset_struct *, bitset_bindex *,
102 bitset_bindex, bitset_bindex *));
103 void (*free) PARAMS ((struct bitset_struct *));
104 enum bitset_type type;
105};
106
107
108/* Return bytes required for bitset of desired type and size. */
109extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
110
111/* Initialise a bitset with desired type and size. */
112extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
113
114extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
115 bitset_attrs));
116
117/* Create a bitset of desired type and size. */
118extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
119
120/* Free bitset. */
121extern void bitset_free PARAMS ((bitset));
122
123/* Create a bitset of desired type and size using obstack. */
124extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
125 bitset_bindex, enum bitset_type));
126
127/* Free bitset allocated on obstack. */
128extern void bitset_obstack_free PARAMS ((bitset));
129
130/* Create a bitset of desired size and attributes. */
131extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
132
133/* Return size in bits of bitset SRC. */
134extern int bitset_size PARAMS ((bitset));
135
136#if BITSET_CACHE && BITSET_INLINE
137static inline void bitset_set PARAMS ((bitset, bitset_bindex));
138static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
139static inline int bitset_test PARAMS ((bitset, bitset_bindex));
140
141/* Set bit BITNO in bitset BSET. */
142static inline void bitset_set (bset, bitno)
143 bitset bset;
144 bitset_bindex bitno;
145{
146 bitset_windex index = bitno / BITSET_WORD_BITS;
147 bitset_windex offset = index - bset->cindex;
148
149 if (offset < bset->csize)
150 bset->cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
151 else
152 BITSET__SET (bset, bitno);
153}
154
155
156/* Reset bit BITNO in bitset BSET. */
157static inline void bitset_reset (bset, bitno)
158 bitset bset;
159 bitset_bindex bitno;
160{
161 bitset_windex index = bitno / BITSET_WORD_BITS;
162 bitset_windex offset = index - bset->cindex;
163
164 if (offset < bset->csize)
165 bset->cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
166 else
167 BITSET__RESET (bset, bitno);
168}
169
170
171/* Test bit BITNO in bitset BSET. */
172static inline int bitset_test (bset, bitno)
173 bitset bset;
174 bitset_bindex bitno;
175{
176 bitset_windex index = bitno / BITSET_WORD_BITS;
177 bitset_windex offset = index - bset->cindex;
178
179 if (offset < bset->csize)
180 return (bset->cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
181 else
182 return BITSET__TEST (bset, bitno);
183}
184#endif
185
186#if BITSET_CACHE && ! BITSET_INLINE
187
188/* Set bit BITNO in bitset BSET. */
189#define bitset_set(bset, bitno) \
190do \
191{ \
192 bitset_bindex _bitno = (bitno); \
193 bitset_windex _index = _bitno / BITSET_WORD_BITS; \
194 bitset_windex _offset = _index - (bset)->cindex; \
195 \
196 if (_offset < (bset)->csize) \
197 (bset)->cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS)); \
198 else \
199 BITSET__SET ((bset), _bitno); \
200} while (0)
201
202
203/* Reset bit BITNO in bitset BSET. */
204#define bitset_reset(bset, bitno) \
205do \
206{ \
207 bitset_bindex _bitno = (bitno); \
208 bitset_windex _index = _bitno / BITSET_WORD_BITS; \
209 bitset_windex _offset = _index - (bset)->cindex; \
210 \
211 if (_offset < (bset)->csize) \
212 (bset)->cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \
213 else \
214 BITSET__RESET ((bset), _bitno); \
215} while (0)
216
217
218/* Test bit BITNO in bitset BSET. */
219#define bitset_test(bset, bitno) \
220(((((bitno) / BITSET_WORD_BITS) - (bset)->cindex) < (bset)->csize) \
221 ? ((bset)->cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->cindex)] \
222 >> ((bitno) % BITSET_WORD_BITS)) & 1 \
223 : (unsigned int) BITSET__TEST ((bset), (bitno)))
224#endif
225
226#if ! BITSET_CACHE
227/* Set bit BITNO in bitset SRC. */
228#define bitset_set(SRC, BITNO) BITSET__SET (SRC, BITNO)
229
230/* Reset bit BITNO in bitset SRC. */
231#define bitset_reset(SRC, BITNO) BITSET__RESET (SRC, BITNO)
232
233/* Return non-zero if bit BITNO in bitset SRC is set. */
234#define bitset_test(SRC, BITNO) BITSET__TEST (SRC, BITNO)
235#endif
236
237/* DST = 0. */
238extern int bitset_zero PARAMS ((bitset));
239
240/* DST = ~0. */
241extern int bitset_ones PARAMS ((bitset));
242
243/* Return non-zero if all bits in bitset SRC are reset. */
244extern int bitset_empty_p PARAMS ((bitset));
245
246/* Return DST == DST | SRC. */
247extern int bitset_subset_p PARAMS ((bitset, bitset));
248
249/* Return DST == SRC. */
250extern int bitset_equal_p PARAMS ((bitset, bitset));
251
252/* DST == SRC. */
253extern int bitset_copy PARAMS ((bitset, bitset));
254
255/* DST = ~SRC. */
256extern int bitset_not PARAMS ((bitset, bitset));
257
258/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
259extern int bitset_or PARAMS ((bitset, bitset, bitset));
260
261/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
262extern int bitset_and PARAMS ((bitset, bitset, bitset));
263
264/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
265extern int bitset_xor PARAMS ((bitset, bitset, bitset));
266
267/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
268extern int bitset_andn PARAMS ((bitset, bitset, bitset));
269
270/* DST = SRC1 | ~SRC2. Return non-zero if DST != SRC1 | ~SRC2. */
271extern int bitset_orn PARAMS ((bitset, bitset, bitset));
272
273/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
274 DST != (SRC1 | SRC2) & SRC3. */
275extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
276
277/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
278 DST != (SRC1 & SRC2) | SRC3. */
279extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
280
281/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
282 DST != (SRC1 & ~SRC2) | SRC3. */
283#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
284
285/* Find next bit set in BSET starting from and including BITNO. */
286extern int bitset_next PARAMS ((bitset, bitset_bindex));
287
288/* Find previous bit set in BSET starting from and including BITNO. */
289extern int bitset_prev PARAMS ((bitset, bitset_bindex));
290
291/* Find list of up to NUM bits set in BSET starting from and including
292 *NEXT. Return with actual number of bits found and with *NEXT
293 indicating where search stopped. */
294#if BITSET_STATS
295extern int bitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
296 bitset_bindex *));
297#else
298#define bitset_list(BSET, LIST, NUM, NEXT) \
299BITSET__LIST (BSET, LIST, NUM, NEXT)
300#endif
301
302/* Find reverse list of up to NUM bits set in BSET starting from and
303 including NEXT. Return with actual number of bits found and with
304 *NEXT indicating where search stopped. */
305#define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
306BITSET__REVERSE_LIST (BSET, LIST, NUM, NEXT)
307
308/* Find first set bit. */
309extern int bitset_first PARAMS ((bitset));
310
311/* Find last set bit. */
312extern int bitset_last PARAMS ((bitset));
313
314/* Dump bitset. */
315extern void bitset_dump PARAMS ((FILE *, bitset));
316
317/* Loop over all elements of BSET, starting with MIN, executing CODE. */
318#define BITSET_EXECUTE(BSET, MIN, N, CODE) \
319do { \
320 bitset_bindex _list[BITSET_LIST_SIZE]; \
321 bitset_bindex _next = (MIN); \
322 int _num; \
323 \
324 while ((_num = bitset_list ((BSET), _list, BITSET_LIST_SIZE, &_next)))\
325 { \
326 int _i; \
327 \
328 for (_i = 0; _i < _num; _i++) \
329 { \
330 (N) = _list[_i]; \
331 CODE; \
332 } \
333 if (_num < BITSET_LIST_SIZE) \
334 break; \
335 } \
336} while (0)
337
338
339/* Loop over all elements of BSET, in reverse order starting with
340 MIN, executing CODE. */
341#define BITSET_REVERSE_EXECUTE(BSET, MIN, N, CODE) \
342do { \
343 bitset_bindex _list[BITSET_LIST_SIZE]; \
344 bitset_bindex _next = (MIN); \
345 int _num; \
346 \
347 while ((_num = bitset_reverse_list ((BSET), _list, \
348 BITSET_LIST_SIZE, &_next))) \
349 { \
350 int _i; \
351 \
352 for (_i = 0; _i < _num; _i++) \
353 { \
354 (N) = _list[_i]; \
355 CODE; \
356 } \
357 if (_num < BITSET_LIST_SIZE) \
358 break; \
359 } \
360} while (0)
361
362
363/* Define set operations in terms of bit operations. */
364
365#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
366
367#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
368
369#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
370
371#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
372bitset_andn_or (DST, SRC1, SRC2, SRC3)
373
374/* Release any memory tied up with bitsets. */
375extern void bitset_release_memory PARAMS ((void));
376
377/* Initialise bitset stats. */
378extern void bitset_stats_init PARAMS ((void));
379
380/* Dump bitset stats. */
381extern void bitset_stats_dump PARAMS ((FILE *));
382
383/* Function to debug bitset from debugger. */
384extern void debug_bitset PARAMS ((bitset));
385
386/* Function to debug bitset stats from debugger. */
387extern void debug_bitset_stats PARAMS ((void));
388
389extern bitset sbitset_init PARAMS ((bitset, bitset_bindex));
390
391extern bitset lbitset_init PARAMS ((bitset, bitset_bindex));
392
393extern bitset ebitset_init PARAMS ((bitset, bitset_bindex));
394
395#endif /* _BITSET_H */
bison