/* General bitsets.
- Copyright (C) 2002 Free Software Foundation, Inc.
+
+ Copyright (C) 2002-2006, 2009-2013 Free Software Foundation, Inc.
+
Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
- This program is free software; you can redistribute it and/or modify
+ This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
+ the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
+#include <config.h>
-#include <stdlib.h>
#include "bitset.h"
+
+#include <stdlib.h>
+#include <string.h>
#include "abitset.h"
#include "lbitset.h"
#include "ebitset.h"
+#include "vbitset.h"
#include "bitset_stats.h"
#include "obstack.h"
switch (type)
{
+ default:
+ abort ();
+
case BITSET_ARRAY:
bytes = abitset_bytes (n_bits);
break;
bytes = ebitset_bytes (n_bits);
break;
- default:
- abort ();
+ case BITSET_VARRAY:
+ bytes = vbitset_bytes (n_bits);
+ break;
}
return bytes;
switch (type)
{
+ default:
+ abort ();
+
case BITSET_ARRAY:
return abitset_init (bset, n_bits);
case BITSET_TABLE:
return ebitset_init (bset, n_bits);
- default:
- abort ();
+ case BITSET_VARRAY:
+ return vbitset_init (bset, n_bits);
}
}
enum bitset_type
bitset_type_choose (bitset_bindex n_bits ATTRIBUTE_UNUSED, unsigned int attr)
{
- enum bitset_type type;
-
/* Check attributes. */
if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
abort ();
if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
abort ();
- /* Choose the type of bitset. Note that sometimes we will be asked
+ /* Choose the type of bitset. Note that sometimes we will be asked
for a zero length fixed size bitset. */
- type = BITSET_ARRAY;
- /* Currently, the simple bitsets do not support a variable size. */
- if (attr & BITSET_VARIABLE || attr & BITSET_SPARSE)
- {
- type = BITSET_LIST;
- if (attr & BITSET_DENSE || attr & BITSET_GREEDY)
- type = BITSET_TABLE;
- }
- return type;
+ /* If no attributes selected, choose a good compromise. */
+ if (!attr)
+ return BITSET_VARRAY;
+
+ if (attr & BITSET_SPARSE)
+ return BITSET_LIST;
+
+ if (attr & BITSET_FIXED)
+ return BITSET_ARRAY;
+
+ if (attr & BITSET_GREEDY)
+ return BITSET_TABLE;
+
+ return BITSET_VARRAY;
}
bytes = bitset_bytes (type, n_bits);
- bset = (bitset) xcalloc (1, bytes);
+ bset = xcalloc (1, bytes);
/* The cache is disabled until some elements are allocated. If we
have variable length arrays, then we may need to allocate a dummy
/* Create a bitset of N_BITS of type TYPE. */
bitset
bitset_obstack_alloc (struct obstack *bobstack,
- bitset_bindex n_bits, enum bitset_type type)
+ bitset_bindex n_bits, enum bitset_type type)
{
size_t bytes;
bitset bset;
}
+/* Return true if both bitsets are of the same type and size. */
+extern bool
+bitset_compatible_p (bitset bset1, bitset bset2)
+{
+ return BITSET_COMPATIBLE_ (bset1, bset2);
+}
+
+
/* Find previous bit set in SRC starting from and including BITNO.
Return BITSET_BINDEX_MAX if SRC empty. */
bitset_bindex
}
-/* Return non-zero if BITNO in SRC is the only set bit. */
-int
+/* Is BITNO in SRC the only set bit? */
+bool
bitset_only_set_p (bitset src, bitset_bindex bitno)
{
bitset_bindex val[2];
bitset_bindex next = 0;
if (bitset_list (src, val, 2, &next) != 1)
- return 0;
+ return false;
return val[0] == bitno;
}
/* Print contents of bitset BSET to FILE. */
static void
-bitset_print (FILE *file, bitset bset, int verbose)
+bitset_print (FILE *file, bitset bset, bool verbose)
{
unsigned int pos;
bitset_bindex i;
if (verbose)
fprintf (file, "n_bits = %lu, set = {",
- (unsigned long) bitset_size (bset));
+ (unsigned long int) bitset_size (bset));
pos = 30;
BITSET_FOR_EACH (iter, bset, i, 0)
{
if (pos > 70)
{
- fprintf (file, "\n");
- pos = 0;
+ fprintf (file, "\n");
+ pos = 0;
}
- fprintf (file, "%d ", i);
+ fprintf (file, "%lu ", (unsigned long int) i);
pos += 1 + (i >= 10) + (i >= 100);
};
void
bitset_dump (FILE *file, bitset bset)
{
- bitset_print (file, bset, 0);
+ bitset_print (file, bset, false);
}
-
/* Release memory associated with bitsets. */
void
bitset_release_memory (void)
}
-
-/* Toggle bit BITNO in bitset BSET and return non-zero if not set. */
-int
+/* Toggle bit BITNO in bitset BSET and the new value of the bit. */
+bool
bitset_toggle_ (bitset bset, bitset_bindex bitno)
{
/* This routine is for completeness. It could be optimized if
if (bitset_test (bset, bitno))
{
bitset_reset (bset, bitno);
- return 0;
+ return false;
}
else
{
bitset_set (bset, bitno);
- return 1;
+ return true;
}
}
+/* Return number of bits in bitset SRC. */
+bitset_bindex
+bitset_size_ (bitset src)
+{
+ return BITSET_NBITS_ (src);
+}
+
+
/* Return number of bits set in bitset SRC. */
bitset_bindex
bitset_count_ (bitset src)
}
-/* DST = SRC. Return non-zero if DST != SRC.
+/* DST = SRC. Return true if DST != SRC.
This is a fallback for the case where SRC and DST are different
bitset types. */
-int
+bool
bitset_copy_ (bitset dst, bitset src)
{
bitset_bindex i;
bitset_set (dst, i);
};
- return 1;
+ return true;
}
/* This is a fallback for implementations that do not support
four operand operations. */
-static inline int
+static inline bool
bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3,
- enum bitset_ops op)
+ enum bitset_ops op)
{
- int changed = 0;
- int stats_enabled_save;
+ bool changed = false;
+ bool stats_enabled_save;
bitset tmp;
/* Create temporary bitset. */
stats_enabled_save = bitset_stats_enabled;
- bitset_stats_enabled = 0;
+ bitset_stats_enabled = false;
tmp = bitset_alloc (0, bitset_type_get (dst));
bitset_stats_enabled = stats_enabled_save;
switch (op)
{
+ default:
+ abort ();
+
case BITSET_OP_OR_AND:
bitset_or (tmp, src1, src2);
changed = bitset_and_cmp (dst, src3, tmp);
bitset_andn (tmp, src1, src2);
changed = bitset_or_cmp (dst, src3, tmp);
break;
-
- default:
- abort ();
}
bitset_free (tmp);
/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
DST != (SRC1 & SRC2) | SRC3. */
-int
+bool
bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
{
return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
DST != (SRC1 & ~SRC2) | SRC3. */
-int
+bool
bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
{
return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
DST != (SRC1 | SRC2) & SRC3. */
-int
+bool
bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
{
return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
debug_bitset (bitset bset)
{
if (bset)
- bitset_print (stderr, bset, 1);
+ bitset_print (stderr, bset, true);
}
projects / bison.git / blobdiff