X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/d08290769c798befc27e9f8bbc3f1a3da12d1f08..f6df83b4e80b2a53c08b5dc654e247076a3b9b03:/lib/bitset.c diff --git a/lib/bitset.c b/lib/bitset.c index a500d471..d8b5f092 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -1,10 +1,12 @@ /* General bitsets. - Copyright (C) 2002, 2003 Free Software Foundation, Inc. + + Copyright (C) 2002-2006, 2009-2012 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, @@ -13,18 +15,18 @@ 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 . */ -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif +#include -#include #include "bitset.h" + +#include +#include #include "abitset.h" #include "lbitset.h" #include "ebitset.h" +#include "vbitset.h" #include "bitset_stats.h" #include "obstack.h" @@ -43,6 +45,9 @@ bitset_bytes (enum bitset_type type, bitset_bindex n_bits) switch (type) { + default: + abort (); + case BITSET_ARRAY: bytes = abitset_bytes (n_bits); break; @@ -55,8 +60,9 @@ bitset_bytes (enum bitset_type type, bitset_bindex n_bits) bytes = ebitset_bytes (n_bits); break; - default: - abort (); + case BITSET_VARRAY: + bytes = vbitset_bytes (n_bits); + break; } return bytes; @@ -72,6 +78,9 @@ bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) switch (type) { + default: + abort (); + case BITSET_ARRAY: return abitset_init (bset, n_bits); @@ -81,8 +90,8 @@ bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) case BITSET_TABLE: return ebitset_init (bset, n_bits); - default: - abort (); + case BITSET_VARRAY: + return vbitset_init (bset, n_bits); } } @@ -93,27 +102,30 @@ bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) 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; } @@ -126,7 +138,7 @@ bitset_alloc (bitset_bindex n_bits, enum bitset_type type) 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 @@ -139,7 +151,7 @@ bitset_alloc (bitset_bindex n_bits, enum bitset_type type) /* 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; @@ -223,6 +235,14 @@ bitset_next (bitset src, bitset_bindex bitno) } +/* 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 @@ -276,18 +296,18 @@ bitset_print (FILE *file, bitset bset, bool verbose) 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); }; @@ -304,7 +324,6 @@ bitset_dump (FILE *file, bitset bset) } - /* Release memory associated with bitsets. */ void bitset_release_memory (void) @@ -314,7 +333,6 @@ bitset_release_memory (void) } - /* Toggle bit BITNO in bitset BSET and the new value of the bit. */ bool bitset_toggle_ (bitset bset, bitset_bindex bitno) @@ -334,6 +352,14 @@ bitset_toggle_ (bitset bset, bitset_bindex bitno) } +/* 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) @@ -381,7 +407,7 @@ bitset_copy_ (bitset dst, bitset src) four operand operations. */ static inline bool bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3, - enum bitset_ops op) + enum bitset_ops op) { bool changed = false; bool stats_enabled_save; @@ -395,6 +421,9 @@ bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3, switch (op) { + default: + abort (); + case BITSET_OP_OR_AND: bitset_or (tmp, src1, src2); changed = bitset_and_cmp (dst, src3, tmp); @@ -409,9 +438,6 @@ bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3, bitset_andn (tmp, src1, src2); changed = bitset_or_cmp (dst, src3, tmp); break; - - default: - abort (); } bitset_free (tmp);