X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/613f5e1a895b0742c9b6c5e9461e4cf3f7389d7e..1168b32295f6acde7a777d9519723fe276155b6b:/lib/bitset.c diff --git a/lib/bitset.c b/lib/bitset.c index 0e8d26c9..d64d5f82 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -1,10 +1,12 @@ /* General bitsets. - Copyright (C) 2002 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,38 +15,39 @@ 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" -static void bitset_print PARAMS ((FILE *, bitset, int)); +const char * const bitset_type_names[] = BITSET_TYPE_NAMES; /* Return number of bytes required to create a N_BIT bitset of TYPE. The bitset may grow to require more bytes than this. */ -int -bitset_bytes (type, n_bits) - enum bitset_type type; - bitset_bindex n_bits; +size_t +bitset_bytes (enum bitset_type type, bitset_bindex n_bits) { - unsigned int bytes; + size_t bytes; if (bitset_stats_enabled) return bitset_stats_bytes (); switch (type) { + default: + abort (); + case BITSET_ARRAY: bytes = abitset_bytes (n_bits); break; @@ -57,8 +60,9 @@ bitset_bytes (type, n_bits) bytes = ebitset_bytes (n_bits); break; - default: - abort (); + case BITSET_VARRAY: + bytes = vbitset_bytes (n_bits); + break; } return bytes; @@ -67,16 +71,16 @@ bitset_bytes (type, n_bits) /* Initialise bitset BSET of TYPE for N_BITS. */ bitset -bitset_init (bset, n_bits, type) - bitset bset; - bitset_bindex n_bits; - enum bitset_type type; +bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) { if (bitset_stats_enabled) return bitset_stats_init (bset, n_bits, type); - + switch (type) { + default: + abort (); + case BITSET_ARRAY: return abitset_init (bset, n_bits); @@ -86,8 +90,8 @@ bitset_init (bset, n_bits, type) case BITSET_TABLE: return ebitset_init (bset, n_bits); - default: - abort (); + case BITSET_VARRAY: + return vbitset_init (bset, n_bits); } } @@ -96,48 +100,45 @@ bitset_init (bset, n_bits, type) specified by ATTR. For variable size bitsets, N_BITS is only a hint and may be zero. */ enum bitset_type -bitset_type_choose (n_bits, attr) - bitset_bindex n_bits ATTRIBUTE_UNUSED; - unsigned int attr; +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 (); - /* Note that sometimes we will be asked for a zero length - fixed size bitset. */ + /* Choose the type of bitset. Note that sometimes we will be asked + for a zero length fixed size bitset. */ - /* Choose the type of 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; - } + /* 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 type; + return BITSET_VARRAY; } /* Create a bitset of N_BITS of type TYPE. */ bitset -bitset_alloc (n_bits, type) - bitset_bindex n_bits; - enum bitset_type type; +bitset_alloc (bitset_bindex n_bits, enum bitset_type type) { - unsigned int bytes; + size_t bytes; bitset bset; 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 @@ -149,12 +150,10 @@ bitset_alloc (n_bits, type) /* Create a bitset of N_BITS of type TYPE. */ bitset -bitset_obstack_alloc (bobstack, n_bits, type) - struct obstack *bobstack; - bitset_bindex n_bits; - enum bitset_type type; +bitset_obstack_alloc (struct obstack *bobstack, + bitset_bindex n_bits, enum bitset_type type) { - unsigned int bytes; + size_t bytes; bitset bset; bytes = bitset_bytes (type, n_bits); @@ -169,9 +168,7 @@ bitset_obstack_alloc (bobstack, n_bits, type) /* Create a bitset of N_BITS and with attribute hints specified by ATTR. */ bitset -bitset_create (n_bits, attr) - bitset_bindex n_bits; - unsigned int attr; +bitset_create (bitset_bindex n_bits, unsigned int attr) { enum bitset_type type; @@ -183,8 +180,7 @@ bitset_create (n_bits, attr) /* Free bitset BSET. */ void -bitset_free (bset) - bitset bset; +bitset_free (bitset bset) { BITSET_FREE_ (bset); free (bset); @@ -193,8 +189,7 @@ bitset_free (bset) /* Free bitset BSET allocated on obstack. */ void -bitset_obstack_free (bset) - bitset bset; +bitset_obstack_free (bitset bset) { BITSET_FREE_ (bset); } @@ -202,117 +197,106 @@ bitset_obstack_free (bset) /* Return bitset type. */ enum bitset_type -bitset_type_get (bset) - bitset bset; +bitset_type_get (bitset bset) { enum bitset_type type; type = BITSET_TYPE_ (bset); if (type != BITSET_STATS) return type; - + return bitset_stats_type_get (bset); } +/* Return name of bitset type. */ +const char * +bitset_type_name_get (bitset bset) +{ + enum bitset_type type; + + type = bitset_type_get (bset); + + return bitset_type_names[type]; +} + + /* Find next bit set in SRC starting from and including BITNO. - Return -1 if SRC empty. */ -int -bitset_next (src, bitno) - bitset src; - bitset_bindex bitno; + Return BITSET_BINDEX_MAX if SRC empty. */ +bitset_bindex +bitset_next (bitset src, bitset_bindex bitno) { bitset_bindex val; bitset_bindex next = bitno; if (!bitset_list (src, &val, 1, &next)) - return -1; + return BITSET_BINDEX_MAX; return val; } +/* 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 -1 if SRC empty. */ -int -bitset_prev (src, bitno) - bitset src; - bitset_bindex bitno; + Return BITSET_BINDEX_MAX if SRC empty. */ +bitset_bindex +bitset_prev (bitset src, bitset_bindex bitno) { bitset_bindex val; bitset_bindex next = bitno; - if (!bitset_reverse_list (src, &val, 1, &next)) - return -1; + if (!bitset_list_reverse (src, &val, 1, &next)) + return BITSET_BINDEX_MAX; return val; } /* Find first set bit. */ -int -bitset_first (src) - bitset src; +bitset_bindex +bitset_first (bitset src) { return bitset_next (src, 0); } /* Find last set bit. */ -int -bitset_last (src) - bitset src; +bitset_bindex +bitset_last (bitset src) { return bitset_prev (src, 0); } -/* Return non-zero if BITNO in SRC is the only set bit. */ -int -bitset_only_set_p (src, bitno) - bitset src; - bitset_bindex bitno; +/* 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; } -/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */ -int -bitset_toggle (bset, bitno) - bitset bset; - bitset_bindex bitno; -{ - /* This routine is for completeness. It could be optimized if - required. */ - if (bitset_test (bset, bitno)) - { - bitset_reset (bset, bitno); - return 0; - } - else - { - bitset_set (bset, bitno); - return 1; - } -} - - /* Print contents of bitset BSET to FILE. */ static void -bitset_print (file, bset, verbose) - FILE *file; - bitset bset; - int verbose; +bitset_print (FILE *file, bitset bset, bool verbose) { - unsigned int i, pos; + unsigned int pos; + bitset_bindex i; bitset_iterator iter; if (verbose) - fprintf (file, "n_bits = %d, set = {", bitset_size (bset)); + fprintf (file, "n_bits = %lu, set = {", + (unsigned long int) bitset_size (bset)); pos = 30; BITSET_FOR_EACH (iter, bset, i, 0) @@ -323,7 +307,7 @@ bitset_print (file, bset, verbose) pos = 0; } - fprintf (file, "%d ", i); + fprintf (file, "%lu ", (unsigned long int) i); pos += 1 + (i >= 10) + (i >= 100); }; @@ -332,49 +316,59 @@ bitset_print (file, bset, verbose) } -/* DST = SRC. Return non-zero if DST != SRC. */ -int -bitset_copy (dst, src) - bitset dst; - bitset src; +/* Dump bitset BSET to FILE. */ +void +bitset_dump (FILE *file, bitset bset) { - unsigned int i; - bitset_iterator iter; + bitset_print (file, bset, false); +} - if (BITSET_COMPATIBLE_ (dst, src)) - return BITSET_COPY_ (dst, src); - /* Convert bitset types. We assume that the DST bitset - is large enough to hold the SRC bitset. */ - bitset_zero (dst); - BITSET_FOR_EACH (iter, src, i, 0) - { - bitset_set (dst, i); - }; +/* Release memory associated with bitsets. */ +void +bitset_release_memory (void) +{ + lbitset_release_memory (); + ebitset_release_memory (); +} - return 1; + +/* 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 + required. */ + if (bitset_test (bset, bitno)) + { + bitset_reset (bset, bitno); + return false; + } + else + { + bitset_set (bset, bitno); + return true; + } } -/* Return size in bits of bitset SRC. */ -int -bitset_size (src) - bitset src; +/* Return number of bits in bitset SRC. */ +bitset_bindex +bitset_size_ (bitset src) { - return BITSET_SIZE_ (src); + return BITSET_NBITS_ (src); } /* Return number of bits set in bitset SRC. */ -int -bitset_count (src) - bitset src; +bitset_bindex +bitset_count_ (bitset src) { bitset_bindex list[BITSET_LIST_SIZE]; bitset_bindex next; - int num; - int count; - + bitset_bindex num; + bitset_bindex count; + /* This could be greatly sped up by adding a count method for each bitset implementation that uses a direct technique (based on masks) for counting the number of bits set in a word. */ @@ -383,157 +377,67 @@ bitset_count (src) for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next)); count += num) continue; - - return count; -} - - -/* DST = 0. */ -int -bitset_zero (dst) - bitset dst; -{ - return BITSET_ZERO_ (dst); -} - - -/* DST = ~0. */ -int -bitset_ones (dst) - bitset dst; -{ - return BITSET_ONES_ (dst); -} - - -/* Return SRC == 0. */ -int -bitset_empty_p (src) - bitset src; -{ - return BITSET_EMPTY_P_ (src); -} - - -/* Return DST == DST | SRC. */ -int -bitset_subset_p (dst, src) - bitset dst; - bitset src; -{ - return BITSET_SUBSET_P_ (dst, src); -} - - -/* Return DST == SRC. */ -int -bitset_equal_p (dst, src) - bitset dst; - bitset src; -{ - return BITSET_EQUAL_P_ (dst, src); -} - - -/* Return DST & SRC == 0. */ -int -bitset_disjoint_p (dst, src) - bitset dst; - bitset src; -{ - return BITSET_DISJOINT_P_ (dst, src); -} - - -/* DST = ~SRC. */ -int -bitset_not (dst, src) - bitset dst; - bitset src; -{ - return BITSET_NOT_ (dst, src); -} - - -/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */ -int -bitset_or (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - return BITSET_OR_ (dst, src1, src2); -} - -/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */ -int -bitset_and (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - return BITSET_AND_ (dst, src1, src2); + return count; } -/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */ -int -bitset_xor (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +/* DST = SRC. Return true if DST != SRC. + This is a fallback for the case where SRC and DST are different + bitset types. */ +bool +bitset_copy_ (bitset dst, bitset src) { - return BITSET_XOR_ (dst, src1, src2); -} + bitset_bindex i; + bitset_iterator iter; + /* Convert bitset types. We assume that the DST bitset + is large enough to hold the SRC bitset. */ + bitset_zero (dst); + BITSET_FOR_EACH (iter, src, i, 0) + { + bitset_set (dst, i); + }; -/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */ -int -bitset_andn (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - return BITSET_ANDN_ (dst, src1, src2); + return true; } /* This is a fallback for implementations that do not support four operand operations. */ -int -bitset_op4 (dst, src1, src2, src3, op) - bitset dst; - bitset src1; - bitset src2; - bitset src3; - enum bitset_ops op; +static inline bool +bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3, + enum bitset_ops op) { - int changed = 0; + bool changed = false; + bool stats_enabled_save; bitset tmp; /* Create temporary bitset. */ + stats_enabled_save = bitset_stats_enabled; + 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_ (dst, src3, tmp); + bitset_or (tmp, src1, src2); + changed = bitset_and_cmp (dst, src3, tmp); break; case BITSET_OP_AND_OR: - BITSET_AND_ (tmp, src1, src2); - changed = BITSET_OR_ (dst, src3, tmp); + bitset_and (tmp, src1, src2); + changed = bitset_or_cmp (dst, src3, tmp); break; case BITSET_OP_ANDN_OR: - BITSET_ANDN_ (tmp, src1, src2); - changed = BITSET_OR_ (dst, src3, tmp); + bitset_andn (tmp, src1, src2); + changed = bitset_or_cmp (dst, src3, tmp); break; - - default: - abort (); } bitset_free (tmp); @@ -541,69 +445,61 @@ bitset_op4 (dst, src1, src2, src3, op) } -/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if - DST != (SRC1 | SRC2) & SRC3. */ -int -bitset_or_and (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; +/* DST = (SRC1 & SRC2) | SRC3. */ +void +bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3) { - return BITSET_OR_AND_ (dst, src1, src2, src3); + bitset_and_or_cmp_ (dst, src1, src2, src3); } /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if DST != (SRC1 & SRC2) | SRC3. */ -int -bitset_and_or (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; +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. */ +void +bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3) { - return BITSET_AND_OR_ (dst, src1, src2, src3); + bitset_andn_or_cmp_ (dst, src1, src2, src3); } /* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if DST != (SRC1 & ~SRC2) | SRC3. */ -int -bitset_andn_or (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; +bool +bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3) { - return BITSET_ANDN_OR_ (dst, src1, src2, src3); + return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR); } -/* Dump bitset BSET to FILE. */ +/* DST = (SRC1 | SRC2) & SRC3. */ void -bitset_dump (file, bset) - FILE *file; - bitset bset; +bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3) { - bitset_print (file, bset, 0); + bitset_or_and_cmp_ (dst, src1, src2, src3); } -/* Function to be called from debugger to print bitset. */ -void -debug_bitset (bset) - bitset bset; +/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if + DST != (SRC1 | SRC2) & SRC3. */ +bool +bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3) { - if (bset) - bitset_print (stderr, bset, 1); + return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND); } -/* Release memory associated with bitsets. */ +/* Function to be called from debugger to print bitset. */ void -bitset_release_memory () +debug_bitset (bitset bset) { - lbitset_release_memory (); - ebitset_release_memory (); + if (bset) + bitset_print (stderr, bset, true); }