1 /* General bitsets.
2
3 Copyright (C) 2002-2006, 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 #include <config.h>
21
22 #include "bitset.h"
23
24 #include <stdlib.h>
25 #include <string.h>
26 #include "abitset.h"
27 #include "lbitset.h"
28 #include "ebitset.h"
29 #include "vbitset.h"
30 #include "bitset_stats.h"
31 #include "obstack.h"
32
33 const char * const bitset_type_names[] = BITSET_TYPE_NAMES;
34
35
36 /* Return number of bytes required to create a N_BIT bitset
37 of TYPE. The bitset may grow to require more bytes than this. */
38 size_t
bitset_bytes(enum bitset_type type,bitset_bindex n_bits)39 bitset_bytes (enum bitset_type type, bitset_bindex n_bits)
40 {
41 size_t bytes;
42
43 if (bitset_stats_enabled)
44 return bitset_stats_bytes ();
45
46 switch (type)
47 {
48 default:
49 abort ();
50
51 case BITSET_ARRAY:
52 bytes = abitset_bytes (n_bits);
53 break;
54
55 case BITSET_LIST:
56 bytes = lbitset_bytes (n_bits);
57 break;
58
59 case BITSET_TABLE:
60 bytes = ebitset_bytes (n_bits);
61 break;
62
63 case BITSET_VARRAY:
64 bytes = vbitset_bytes (n_bits);
65 break;
66 }
67
68 return bytes;
69 }
70
71
72 /* Initialise bitset BSET of TYPE for N_BITS. */
73 bitset
bitset_init(bitset bset,bitset_bindex n_bits,enum bitset_type type)74 bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
75 {
76 if (bitset_stats_enabled)
77 return bitset_stats_init (bset, n_bits, type);
78
79 switch (type)
80 {
81 default:
82 abort ();
83
84 case BITSET_ARRAY:
85 return abitset_init (bset, n_bits);
86
87 case BITSET_LIST:
88 return lbitset_init (bset, n_bits);
89
90 case BITSET_TABLE:
91 return ebitset_init (bset, n_bits);
92
93 case BITSET_VARRAY:
94 return vbitset_init (bset, n_bits);
95 }
96 }
97
98
99 /* Select a bitset type for a set of N_BITS and with attribute hints
100 specified by ATTR. For variable size bitsets, N_BITS is only a
101 hint and may be zero. */
102 enum bitset_type
bitset_type_choose(bitset_bindex n_bits ATTRIBUTE_UNUSED,unsigned int attr)103 bitset_type_choose (bitset_bindex n_bits ATTRIBUTE_UNUSED, unsigned int attr)
104 {
105 /* Check attributes. */
106 if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
107 abort ();
108 if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
109 abort ();
110
111 /* Choose the type of bitset. Note that sometimes we will be asked
112 for a zero length fixed size bitset. */
113
114
115 /* If no attributes selected, choose a good compromise. */
116 if (!attr)
117 return BITSET_VARRAY;
118
119 if (attr & BITSET_SPARSE)
120 return BITSET_LIST;
121
122 if (attr & BITSET_FIXED)
123 return BITSET_ARRAY;
124
125 if (attr & BITSET_GREEDY)
126 return BITSET_TABLE;
127
128 return BITSET_VARRAY;
129 }
130
131
132 /* Create a bitset of N_BITS of type TYPE. */
133 bitset
bitset_alloc(bitset_bindex n_bits,enum bitset_type type)134 bitset_alloc (bitset_bindex n_bits, enum bitset_type type)
135 {
136 size_t bytes;
137 bitset bset;
138
139 bytes = bitset_bytes (type, n_bits);
140
141 bset = xcalloc (1, bytes);
142
143 /* The cache is disabled until some elements are allocated. If we
144 have variable length arrays, then we may need to allocate a dummy
145 element. */
146
147 return bitset_init (bset, n_bits, type);
148 }
149
150
151 /* Create a bitset of N_BITS of type TYPE. */
152 bitset
bitset_obstack_alloc(struct obstack * bobstack,bitset_bindex n_bits,enum bitset_type type)153 bitset_obstack_alloc (struct obstack *bobstack,
154 bitset_bindex n_bits, enum bitset_type type)
155 {
156 size_t bytes;
157 bitset bset;
158
159 bytes = bitset_bytes (type, n_bits);
160
161 bset = obstack_alloc (bobstack, bytes);
162 memset (bset, 0, bytes);
163
164 return bitset_init (bset, n_bits, type);
165 }
166
167
168 /* Create a bitset of N_BITS and with attribute hints specified by
169 ATTR. */
170 bitset
bitset_create(bitset_bindex n_bits,unsigned int attr)171 bitset_create (bitset_bindex n_bits, unsigned int attr)
172 {
173 enum bitset_type type;
174
175 type = bitset_type_choose (n_bits, attr);
176
177 return bitset_alloc (n_bits, type);
178 }
179
180
181 /* Free bitset BSET. */
182 void
bitset_free(bitset bset)183 bitset_free (bitset bset)
184 {
185 BITSET_FREE_ (bset);
186 free (bset);
187 }
188
189
190 /* Free bitset BSET allocated on obstack. */
191 void
bitset_obstack_free(bitset bset)192 bitset_obstack_free (bitset bset)
193 {
194 BITSET_FREE_ (bset);
195 }
196
197
198 /* Return bitset type. */
199 enum bitset_type
bitset_type_get(bitset bset)200 bitset_type_get (bitset bset)
201 {
202 enum bitset_type type;
203
204 type = BITSET_TYPE_ (bset);
205 if (type != BITSET_STATS)
206 return type;
207
208 return bitset_stats_type_get (bset);
209 }
210
211
212 /* Return name of bitset type. */
213 const char *
bitset_type_name_get(bitset bset)214 bitset_type_name_get (bitset bset)
215 {
216 enum bitset_type type;
217
218 type = bitset_type_get (bset);
219
220 return bitset_type_names[type];
221 }
222
223
224 /* Find next bit set in SRC starting from and including BITNO.
225 Return BITSET_BINDEX_MAX if SRC empty. */
226 bitset_bindex
bitset_next(bitset src,bitset_bindex bitno)227 bitset_next (bitset src, bitset_bindex bitno)
228 {
229 bitset_bindex val;
230 bitset_bindex next = bitno;
231
232 if (!bitset_list (src, &val, 1, &next))
233 return BITSET_BINDEX_MAX;
234 return val;
235 }
236
237
238 /* Return true if both bitsets are of the same type and size. */
239 extern bool
bitset_compatible_p(bitset bset1,bitset bset2)240 bitset_compatible_p (bitset bset1, bitset bset2)
241 {
242 return BITSET_COMPATIBLE_ (bset1, bset2);
243 }
244
245
246 /* Find previous bit set in SRC starting from and including BITNO.
247 Return BITSET_BINDEX_MAX if SRC empty. */
248 bitset_bindex
bitset_prev(bitset src,bitset_bindex bitno)249 bitset_prev (bitset src, bitset_bindex bitno)
250 {
251 bitset_bindex val;
252 bitset_bindex next = bitno;
253
254 if (!bitset_list_reverse (src, &val, 1, &next))
255 return BITSET_BINDEX_MAX;
256 return val;
257 }
258
259
260 /* Find first set bit. */
261 bitset_bindex
bitset_first(bitset src)262 bitset_first (bitset src)
263 {
264 return bitset_next (src, 0);
265 }
266
267
268 /* Find last set bit. */
269 bitset_bindex
bitset_last(bitset src)270 bitset_last (bitset src)
271 {
272 return bitset_prev (src, 0);
273 }
274
275
276 /* Is BITNO in SRC the only set bit? */
277 bool
bitset_only_set_p(bitset src,bitset_bindex bitno)278 bitset_only_set_p (bitset src, bitset_bindex bitno)
279 {
280 bitset_bindex val[2];
281 bitset_bindex next = 0;
282
283 if (bitset_list (src, val, 2, &next) != 1)
284 return false;
285 return val[0] == bitno;
286 }
287
288
289 /* Print contents of bitset BSET to FILE. */
290 static void
bitset_print(FILE * file,bitset bset,bool verbose)291 bitset_print (FILE *file, bitset bset, bool verbose)
292 {
293 unsigned int pos;
294 bitset_bindex i;
295 bitset_iterator iter;
296
297 if (verbose)
298 fprintf (file, "n_bits = %lu, set = {",
299 (unsigned long int) bitset_size (bset));
300
301 pos = 30;
302 BITSET_FOR_EACH (iter, bset, i, 0)
303 {
304 if (pos > 70)
305 {
306 fprintf (file, "\n");
307 pos = 0;
308 }
309
310 fprintf (file, "%lu ", (unsigned long int) i);
311 pos += 1 + (i >= 10) + (i >= 100);
312 };
313
314 if (verbose)
315 fprintf (file, "}\n");
316 }
317
318
319 /* Dump bitset BSET to FILE. */
320 void
bitset_dump(FILE * file,bitset bset)321 bitset_dump (FILE *file, bitset bset)
322 {
323 bitset_print (file, bset, false);
324 }
325
326
327 /* Release memory associated with bitsets. */
328 void
bitset_release_memory(void)329 bitset_release_memory (void)
330 {
331 lbitset_release_memory ();
332 ebitset_release_memory ();
333 }
334
335
336 /* Toggle bit BITNO in bitset BSET and the new value of the bit. */
337 bool
bitset_toggle_(bitset bset,bitset_bindex bitno)338 bitset_toggle_ (bitset bset, bitset_bindex bitno)
339 {
340 /* This routine is for completeness. It could be optimized if
341 required. */
342 if (bitset_test (bset, bitno))
343 {
344 bitset_reset (bset, bitno);
345 return false;
346 }
347 else
348 {
349 bitset_set (bset, bitno);
350 return true;
351 }
352 }
353
354
355 /* Return number of bits in bitset SRC. */
356 bitset_bindex
bitset_size_(bitset src)357 bitset_size_ (bitset src)
358 {
359 return BITSET_NBITS_ (src);
360 }
361
362
363 /* Return number of bits set in bitset SRC. */
364 bitset_bindex
bitset_count_(bitset src)365 bitset_count_ (bitset src)
366 {
367 bitset_bindex list[BITSET_LIST_SIZE];
368 bitset_bindex next;
369 bitset_bindex num;
370 bitset_bindex count;
371
372 /* This could be greatly sped up by adding a count method for each
373 bitset implementation that uses a direct technique (based on
374 masks) for counting the number of bits set in a word. */
375
376 next = 0;
377 for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next));
378 count += num)
379 continue;
380
381 return count;
382 }
383
384
385 /* DST = SRC. Return true if DST != SRC.
386 This is a fallback for the case where SRC and DST are different
387 bitset types. */
388 bool
bitset_copy_(bitset dst,bitset src)389 bitset_copy_ (bitset dst, bitset src)
390 {
391 bitset_bindex i;
392 bitset_iterator iter;
393
394 /* Convert bitset types. We assume that the DST bitset
395 is large enough to hold the SRC bitset. */
396 bitset_zero (dst);
397 BITSET_FOR_EACH (iter, src, i, 0)
398 {
399 bitset_set (dst, i);
400 };
401
402 return true;
403 }
404
405
406 /* This is a fallback for implementations that do not support
407 four operand operations. */
408 static inline bool
bitset_op4_cmp(bitset dst,bitset src1,bitset src2,bitset src3,enum bitset_ops op)409 bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3,
410 enum bitset_ops op)
411 {
412 bool changed = false;
413 bool stats_enabled_save;
414 bitset tmp;
415
416 /* Create temporary bitset. */
417 stats_enabled_save = bitset_stats_enabled;
418 bitset_stats_enabled = false;
419 tmp = bitset_alloc (0, bitset_type_get (dst));
420 bitset_stats_enabled = stats_enabled_save;
421
422 switch (op)
423 {
424 default:
425 abort ();
426
427 case BITSET_OP_OR_AND:
428 bitset_or (tmp, src1, src2);
429 changed = bitset_and_cmp (dst, src3, tmp);
430 break;
431
432 case BITSET_OP_AND_OR:
433 bitset_and (tmp, src1, src2);
434 changed = bitset_or_cmp (dst, src3, tmp);
435 break;
436
437 case BITSET_OP_ANDN_OR:
438 bitset_andn (tmp, src1, src2);
439 changed = bitset_or_cmp (dst, src3, tmp);
440 break;
441 }
442
443 bitset_free (tmp);
444 return changed;
445 }
446
447
448 /* DST = (SRC1 & SRC2) | SRC3. */
449 void
bitset_and_or_(bitset dst,bitset src1,bitset src2,bitset src3)450 bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
451 {
452 bitset_and_or_cmp_ (dst, src1, src2, src3);
453 }
454
455
456 /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
457 DST != (SRC1 & SRC2) | SRC3. */
458 bool
bitset_and_or_cmp_(bitset dst,bitset src1,bitset src2,bitset src3)459 bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
460 {
461 return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
462 }
463
464
465 /* DST = (SRC1 & ~SRC2) | SRC3. */
466 void
bitset_andn_or_(bitset dst,bitset src1,bitset src2,bitset src3)467 bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
468 {
469 bitset_andn_or_cmp_ (dst, src1, src2, src3);
470 }
471
472
473 /* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
474 DST != (SRC1 & ~SRC2) | SRC3. */
475 bool
bitset_andn_or_cmp_(bitset dst,bitset src1,bitset src2,bitset src3)476 bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
477 {
478 return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
479 }
480
481
482 /* DST = (SRC1 | SRC2) & SRC3. */
483 void
bitset_or_and_(bitset dst,bitset src1,bitset src2,bitset src3)484 bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3)
485 {
486 bitset_or_and_cmp_ (dst, src1, src2, src3);
487 }
488
489
490 /* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
491 DST != (SRC1 | SRC2) & SRC3. */
492 bool
bitset_or_and_cmp_(bitset dst,bitset src1,bitset src2,bitset src3)493 bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
494 {
495 return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
496 }
497
498
499 /* Function to be called from debugger to print bitset. */
500 void
debug_bitset(bitset bset)501 debug_bitset (bitset bset)
502 {
503 if (bset)
504 bitset_print (stderr, bset, true);
505 }
506