3 Copyright (C) 2002-2006, 2009-2015, 2018-2020 Free Software Foundation, Inc.
5 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
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.
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.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <https://www.gnu.org/licenses/>. */
29 #include "bitset/array.h"
30 #include "bitset/list.h"
31 #include "bitset/stats.h"
32 #include "bitset/table.h"
33 #include "bitset/vector.h"
35 const char * const bitset_type_names
[] = BITSET_TYPE_NAMES
;
38 /* Return number of bytes required to create a N_BIT bitset
39 of TYPE. The bitset may grow to require more bytes than this. */
41 bitset_bytes (enum bitset_type type
, bitset_bindex n_bits
)
43 if (bitset_stats_enabled
)
44 return bitset_stats_bytes ();
52 return abitset_bytes (n_bits
);
55 return lbitset_bytes (n_bits
);
58 return tbitset_bytes (n_bits
);
61 return vbitset_bytes (n_bits
);
66 /* Initialise bitset BSET of TYPE for N_BITS. */
68 bitset_init (bitset bset
, bitset_bindex n_bits
, enum bitset_type type
)
70 if (bitset_stats_enabled
)
71 return bitset_stats_init (bset
, n_bits
, type
);
79 return abitset_init (bset
, n_bits
);
82 return lbitset_init (bset
, n_bits
);
85 return tbitset_init (bset
, n_bits
);
88 return vbitset_init (bset
, n_bits
);
93 /* Select a bitset type for a set of N_BITS and with attribute hints
94 specified by ATTR. For variable size bitsets, N_BITS is only a
95 hint and may be zero. */
97 bitset_type_choose (bitset_bindex n_bits MAYBE_UNUSED
, unsigned attr
)
99 /* Check attributes. */
100 if (attr
& BITSET_FIXED
&& attr
& BITSET_VARIABLE
)
102 if (attr
& BITSET_SPARSE
&& attr
& BITSET_DENSE
)
105 /* Choose the type of bitset. Note that sometimes we will be asked
106 for a zero length fixed size bitset. */
109 /* If no attributes selected, choose a good compromise. */
111 return BITSET_VECTOR
;
113 if (attr
& BITSET_SPARSE
)
116 if (attr
& BITSET_FIXED
)
119 if (attr
& BITSET_GREEDY
)
122 return BITSET_VECTOR
;
126 /* Create a bitset of N_BITS of type TYPE. */
128 bitset_alloc (bitset_bindex n_bits
, enum bitset_type type
)
130 size_t bytes
= bitset_bytes (type
, n_bits
);
132 bitset bset
= xzalloc (bytes
);
134 /* The cache is disabled until some elements are allocated. If we
135 have variable length arrays, then we may need to allocate a dummy
138 return bitset_init (bset
, n_bits
, type
);
142 /* Create a bitset of N_BITS of type TYPE. */
144 bitset_obstack_alloc (struct obstack
*bobstack
,
145 bitset_bindex n_bits
, enum bitset_type type
)
147 size_t bytes
= bitset_bytes (type
, n_bits
);
149 bitset bset
= obstack_alloc (bobstack
, bytes
);
150 memset (bset
, 0, bytes
);
152 return bitset_init (bset
, n_bits
, type
);
156 /* Create a bitset of N_BITS and with attribute hints specified by
159 bitset_create (bitset_bindex n_bits
, unsigned attr
)
161 enum bitset_type type
= bitset_type_choose (n_bits
, attr
);
163 return bitset_alloc (n_bits
, type
);
167 /* Free bitset BSET. */
169 bitset_free (bitset bset
)
179 /* Free bitset BSET allocated on obstack. */
181 bitset_obstack_free (bitset bset
)
188 /* Return bitset type. */
190 bitset_type_get (bitset bset
)
192 enum bitset_type type
= BITSET_TYPE_ (bset
);
193 if (type
!= BITSET_STATS
)
196 return bitset_stats_type_get (bset
);
200 /* Return name of bitset type. */
202 bitset_type_name_get (bitset bset
)
204 enum bitset_type type
= bitset_type_get (bset
);
206 return bitset_type_names
[type
];
210 /* Find next bit set in SRC starting from and including BITNO.
211 Return BITSET_BINDEX_MAX if SRC empty. */
213 bitset_next (bitset src
, bitset_bindex bitno
)
215 bitset_bindex next
= bitno
;
217 if (!bitset_list (src
, &val
, 1, &next
))
218 return BITSET_BINDEX_MAX
;
223 /* Return true if both bitsets are of the same type and size. */
225 bitset_compatible_p (bitset bset1
, bitset bset2
)
227 return BITSET_COMPATIBLE_ (bset1
, bset2
);
231 /* Find previous bit set in SRC starting from and including BITNO.
232 Return BITSET_BINDEX_MAX if SRC empty. */
234 bitset_prev (bitset src
, bitset_bindex bitno
)
236 bitset_bindex next
= bitno
;
238 if (!bitset_list_reverse (src
, &val
, 1, &next
))
239 return BITSET_BINDEX_MAX
;
244 /* Find first set bit. */
246 bitset_first (bitset src
)
248 return bitset_next (src
, 0);
252 /* Find last set bit. */
254 bitset_last (bitset src
)
256 return bitset_prev (src
, 0);
260 /* Is BITNO in SRC the only set bit? */
262 bitset_only_set_p (bitset src
, bitset_bindex bitno
)
264 bitset_bindex val
[2];
265 bitset_bindex next
= 0;
267 if (bitset_list (src
, val
, 2, &next
) != 1)
269 return val
[0] == bitno
;
273 /* Print contents of bitset BSET to FILE. */
275 bitset_print (FILE *file
, bitset bset
, bool verbose
)
278 fprintf (file
, "n_bits = %lu, set = {",
279 (unsigned long) bitset_size (bset
));
283 bitset_iterator iter
;
284 BITSET_FOR_EACH (iter
, bset
, i
, 0)
288 fprintf (file
, "\n");
292 fprintf (file
, "%lu ", (unsigned long) i
);
293 pos
+= 1 + (i
>= 10) + (i
>= 100);
297 fprintf (file
, "}\n");
301 /* Dump bitset BSET to FILE. */
303 bitset_dump (FILE *file
, bitset bset
)
305 bitset_print (file
, bset
, false);
309 /* Release memory associated with bitsets. */
311 bitset_release_memory (void)
313 lbitset_release_memory ();
314 tbitset_release_memory ();
318 /* Toggle bit BITNO in bitset BSET and the new value of the bit. */
320 bitset_toggle_ (bitset bset
, bitset_bindex bitno
)
322 /* This routine is for completeness. It could be optimized if
324 if (bitset_test (bset
, bitno
))
326 bitset_reset (bset
, bitno
);
331 bitset_set (bset
, bitno
);
337 /* Return number of bits in bitset SRC. */
339 bitset_size_ (bitset src
)
341 return BITSET_NBITS_ (src
);
345 /* Return number of bits set in bitset SRC. */
347 bitset_count_ (bitset src
)
349 bitset_bindex list
[BITSET_LIST_SIZE
];
350 bitset_bindex count
= 0;
352 /* This could be greatly sped up by adding a count method for each
353 bitset implementation that uses a direct technique (based on
354 masks) for counting the number of bits set in a word. */
357 bitset_bindex next
= 0;
359 while ((num
= bitset_list (src
, list
, BITSET_LIST_SIZE
, &next
)))
367 /* DST = SRC. Return true if DST != SRC.
368 This is a fallback for the case where SRC and DST are different
371 bitset_copy_ (bitset dst
, bitset src
)
374 bitset_iterator iter
;
376 /* Convert bitset types. We assume that the DST bitset
377 is large enough to hold the SRC bitset. */
379 BITSET_FOR_EACH (iter
, src
, i
, 0)
386 /* This is a fallback for implementations that do not support
387 four operand operations. */
389 bitset_op4_cmp (bitset dst
, bitset src1
, bitset src2
, bitset src3
,
392 bool changed
= false;
394 /* Create temporary bitset. */
395 bool stats_enabled_save
= bitset_stats_enabled
;
396 bitset_stats_enabled
= false;
397 bitset tmp
= bitset_alloc (0, bitset_type_get (dst
));
398 bitset_stats_enabled
= stats_enabled_save
;
405 case BITSET_OP_OR_AND
:
406 bitset_or (tmp
, src1
, src2
);
407 changed
= bitset_and_cmp (dst
, src3
, tmp
);
410 case BITSET_OP_AND_OR
:
411 bitset_and (tmp
, src1
, src2
);
412 changed
= bitset_or_cmp (dst
, src3
, tmp
);
415 case BITSET_OP_ANDN_OR
:
416 bitset_andn (tmp
, src1
, src2
);
417 changed
= bitset_or_cmp (dst
, src3
, tmp
);
426 /* DST = (SRC1 & SRC2) | SRC3. */
428 bitset_and_or_ (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
430 bitset_and_or_cmp_ (dst
, src1
, src2
, src3
);
434 /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
435 DST != (SRC1 & SRC2) | SRC3. */
437 bitset_and_or_cmp_ (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
439 return bitset_op4_cmp (dst
, src1
, src2
, src3
, BITSET_OP_AND_OR
);
443 /* DST = (SRC1 & ~SRC2) | SRC3. */
445 bitset_andn_or_ (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
447 bitset_andn_or_cmp_ (dst
, src1
, src2
, src3
);
451 /* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
452 DST != (SRC1 & ~SRC2) | SRC3. */
454 bitset_andn_or_cmp_ (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
456 return bitset_op4_cmp (dst
, src1
, src2
, src3
, BITSET_OP_ANDN_OR
);
460 /* DST = (SRC1 | SRC2) & SRC3. */
462 bitset_or_and_ (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
464 bitset_or_and_cmp_ (dst
, src1
, src2
, src3
);
468 /* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
469 DST != (SRC1 | SRC2) & SRC3. */
471 bitset_or_and_cmp_ (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
473 return bitset_op4_cmp (dst
, src1
, src2
, src3
, BITSET_OP_OR_AND
);
477 /* Function to be called from debugger to print bitset. */
479 debug_bitset (bitset bset
)
482 bitset_print (stderr
, bset
, true);