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