X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/7086e7071e8bfa2012e9134530a158c88a832ba6..cb3f7f335aa69ba3e6478fea8d4591f4f6d43bc5:/lib/bitset.c diff --git a/lib/bitset.c b/lib/bitset.c index c68ed788..f4692dde 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -1,155 +1,56 @@ /* General bitsets. - Copyright (C) 2002 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 -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or -(at your option) any later version. - -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -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. */ - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#include -#include "bitset.h" -#include "obstack.h" - -static void bitset_print PARAMS ((FILE *, bitset, int)); - -#if BITSET_CHECK -#define BITSET__CHECK2(DST, SRC) \ -if ((DST)->OPS != (SRC)->OPS) abort (); - -#define BITSET__CHECK3(DST, SRC1, SRC2) \ -if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS) abort (); - -#define BITSET__CHECK4(DST, SRC1, SRC2) \ -if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS \ - || (DST)->OPS != (SRC3)->OPS) abort (); -#else -#define BITSET__CHECK2(DST, SRC) - -#define BITSET__CHECK3(DST, SRC1, SRC2) - -#define BITSET__CHECK4(DST, SRC1, SRC2, SRC3) -#endif - -#if BITSET_STATS -#define BITSET_STATS_FILE "bitset.dat" - -#define BITSET_LOG_COUNT_BINS 10 -#define BITSET_LOG_SIZE_BINS 16 -#define BITSET_DENSITY_BINS 20 - -struct bitset_type_stats_struct -{ - unsigned int xmallocs; - unsigned int xfrees; - unsigned int oballocs; - unsigned int obfrees; - unsigned int lists; - unsigned int list_counts[BITSET_LOG_COUNT_BINS]; - unsigned int list_sizes[BITSET_LOG_SIZE_BINS]; - unsigned int list_density[BITSET_DENSITY_BINS]; -}; - -struct bitset_stats_struct -{ - unsigned int runs; - struct bitset_type_stats_struct types[BITSET_TYPE_NUM]; -}; - -struct bitset_stats_struct bitset_stats_data; -struct bitset_stats_struct *bitset_stats; - -static void bitset_percent_histogram_print PARAMS ((FILE *, const char *, - const char *, - unsigned int, - unsigned int *)); -static void bitset_log_histogram_print PARAMS ((FILE *, const char *, - const char *, - unsigned int, unsigned int *)); -static void bitset_stats_print_1 PARAMS ((FILE *, const char *, - struct bitset_type_stats_struct *)); -static void bitset_stats_print PARAMS ((FILE *, int)); -static void bitset_stats_read PARAMS ((void)); -static void bitset_stats_write PARAMS ((void)); - -#define BITSET_STATS_XMALLOCS_INC(TYPE) \ - if (bitset_stats) \ - bitset_stats->types[(TYPE)].xmallocs++ - -#define BITSET_STATS_XFREES_INC(BSET) \ - if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].xfrees++ -#define BITSET_STATS_OBALLOCS_INC(TYPE) \ - if (bitset_stats) \ - bitset_stats->types[(TYPE)].oballocs++ + Copyright (C) 2002, 2003, 2004, 2005, 2006, 2009, 2010 Free + Software Foundation, Inc. -#define BITSET_STATS_OBFREES_INC(BSET) \ - if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].obfrees++ - -#define BITSET_STATS_LISTS_INC(BSET) \ - if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].lists++ - -#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \ - if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].list_counts[(I)]++ - -#define BITSET_STATS_LIST_SIZES_INC(BSET, I) \ - if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].list_sizes[(I)]++ - -#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \ - if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].list_density[(I)]++ - -#else -#define BITSET_STATS_XMALLOCS_INC(TYPE) - -#define BITSET_STATS_XFREES_INC(BSET) + Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). -#define BITSET_STATS_OBALLOCS_INC(TYPE) + 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 3 of the License, or + (at your option) any later version. -#define BITSET_STATS_OBFREES_INC(BSET) + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -#define BITSET_STATS_LISTS_INC(BSET) + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ -#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) +#include -#define BITSET_STATS_LIST_SIZES_INC(BSET, I) +#include "bitset.h" -#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) -#endif /* BITSET_STATS */ +#include +#include +#include "abitset.h" +#include "lbitset.h" +#include "ebitset.h" +#include "vbitset.h" +#include "bitset_stats.h" +#include "obstack.h" +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 = sbitset_bytes (n_bits); + bytes = abitset_bytes (n_bits); break; case BITSET_LIST: @@ -160,8 +61,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; @@ -170,15 +72,18 @@ 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 sbitset_init (bset, n_bits); + return abitset_init (bset, n_bits); case BITSET_LIST: return lbitset_init (bset, n_bits); @@ -186,8 +91,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); } } @@ -196,52 +101,49 @@ 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; - -#ifdef ENABLE_CHECKING /* 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. */ -#endif + /* 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; - BITSET_STATS_XMALLOCS_INC (type); - bytes = bitset_bytes (type, n_bits); - bset = (bitset) xmalloc (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 + element. */ return bitset_init (bset, n_bits, type); } @@ -249,27 +151,25 @@ 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; - - BITSET_STATS_OBALLOCS_INC (type); + size_t bytes; + bitset bset; bytes = bitset_bytes (type, n_bits); - return bitset_init (obstack_alloc (bobstack, bytes), n_bits, type); + bset = obstack_alloc (bobstack, bytes); + memset (bset, 0, bytes); + + return bitset_init (bset, 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; @@ -281,95 +181,126 @@ bitset_create (n_bits, attr) /* Free bitset BSET. */ void -bitset_free (bset) - bitset bset; +bitset_free (bitset bset) { - BITSET_STATS_XFREES_INC (bset); - - if (bset->ops->free) - BITSET__FREE (bset); - - bset->ops = NULL; + BITSET_FREE_ (bset); free (bset); } /* Free bitset BSET allocated on obstack. */ void -bitset_obstack_free (bset) - bitset bset; +bitset_obstack_free (bitset bset) +{ + BITSET_FREE_ (bset); +} + + +/* Return bitset type. */ +enum bitset_type +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) { - BITSET_STATS_OBFREES_INC (bset); + enum bitset_type type; + + type = bitset_type_get (bset); - if (bset->ops->free) - BITSET__FREE (bset); - bset->ops = NULL; + 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); } +/* 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 false; + return val[0] == bitno; +} + + +/* 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_EXECUTE (bset, 0, i, + BITSET_FOR_EACH (iter, bset, i, 0) { if (pos > 70) { @@ -377,459 +308,199 @@ bitset_print (file, bset, verbose) pos = 0; } - fprintf (file, "%d ", i); + fprintf (file, "%lu ", (unsigned long int) i); pos += 1 + (i >= 10) + (i >= 100); - }); + }; if (verbose) fprintf (file, "}\n"); } -int -bitset_copy (dst, src) - bitset dst; - bitset src; +/* Dump bitset BSET to FILE. */ +void +bitset_dump (FILE *file, bitset bset) { - unsigned int i; - - if (dst->ops == src->ops) - 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_EXECUTE (src, 0, i, - { - bitset_set (dst, i); - }); - - return 1; + bitset_print (file, bset, false); } -/* Return size in bits of bitset SRC. */ -int -bitset_size (src) - bitset src; +/* Release memory associated with bitsets. */ +void +bitset_release_memory (void) { - return BITSET__SIZE (src); + lbitset_release_memory (); + ebitset_release_memory (); } -/* DST = 0. */ -int -bitset_zero (dst) - bitset dst; +/* Toggle bit BITNO in bitset BSET and the new value of the bit. */ +bool +bitset_toggle_ (bitset bset, bitset_bindex bitno) { - return BITSET__OP1 (dst, BITSET_ZERO); + /* 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; + } } -/* DST = ~0. */ -int -bitset_ones (dst) - bitset dst; +/* Return number of bits in bitset SRC. */ +bitset_bindex +bitset_size_ (bitset src) { - return BITSET__OP1 (dst, BITSET_ONES); + return BITSET_NBITS_ (src); } -/* Return non-zero if all bits in bitset SRC are reset. */ -int -bitset_empty_p (src) - bitset src; +/* Return number of bits set in bitset SRC. */ +bitset_bindex +bitset_count_ (bitset src) { - return BITSET__OP1 (src, BITSET_EMPTY_P); -} - + bitset_bindex list[BITSET_LIST_SIZE]; + bitset_bindex next; + bitset_bindex num; + bitset_bindex count; -/* Return DST == DST | SRC. */ -int -bitset_subset_p (dst, src) - bitset dst; - bitset src; -{ - return BITSET__OP2 (dst, src, BITSET_SUBSET_P); -} + /* 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. */ + next = 0; + for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next)); + count += num) + continue; -/* Return DST == SRC. */ -int -bitset_equal_p (dst, src) - bitset dst; - bitset src; -{ - BITSET__CHECK2 (dst, src); - return BITSET__OP2 (dst, src, BITSET_EQUAL_P); + return count; } -/* DST = ~SRC. */ -int -bitset_not (dst, src) - bitset dst; - bitset src; +/* 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) { - BITSET__CHECK2 (dst, src); - return BITSET__OP2 (dst, src, BITSET_NOT); -} + 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_or (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_OR); + return true; } -/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */ -int -bitset_and (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +/* This is a fallback for implementations that do not support + four operand operations. */ +static inline bool +bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3, + enum bitset_ops op) { - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_AND); -} + 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; -/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */ -int -bitset_xor (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_XOR); -} + switch (op) + { + default: + abort (); + case BITSET_OP_OR_AND: + bitset_or (tmp, src1, src2); + changed = bitset_and_cmp (dst, src3, tmp); + break; -/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */ -int -bitset_andn (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_ANDN); -} + case BITSET_OP_AND_OR: + 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_cmp (dst, src3, tmp); + break; + } -/* DST = SRC1 | ~SRC2. Return non-zero if DST != SRC1 | ~SRC2. */ -int -bitset_orn (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_ORN); + bitset_free (tmp); + return changed; } -/* 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) { - BITSET__CHECK4 (dst, src1, src2, src3); - return BITSET__OP4 (dst, src1, src2, src3, BITSET_OR_AND); + 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) { - BITSET__CHECK4 (dst, src1, src2, src3); - return BITSET__OP4 (dst, src1, src2, src3, BITSET_AND_OR); + return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR); } -/* Dump bitset BSET to FILE. */ +/* DST = (SRC1 & ~SRC2) | SRC3. */ void -bitset_dump (file, bset) - FILE *file; - bitset bset; +bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3) { - bitset_print (file, bset, 0); + bitset_andn_or_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_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3) { - bitset_print (stderr, bset, 1); + return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR); } -/* Release memory associated with bitsets. */ +/* DST = (SRC1 | SRC2) & SRC3. */ void -bitset_release_memory () -{ - lbitset_release_memory (); - ebitset_release_memory (); -} - - -#if BITSET_STATS -int -bitset_list (bset, list, num, next) - bitset bset; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; -{ - bitset_bindex count; - - count = BITSET__LIST (bset, list, num, next); - - if (bitset_stats) - { - bitset_bindex tmp; - bitset_bindex size; - bitset_bindex i; - enum bitset_type type; - - type = bset->ops->type; - BITSET_STATS_LISTS_INC (bset); - - /* Log histogram of number of set bits. */ - for (i = 0, tmp = count; tmp; tmp >>= 1, i++) - continue; - if (i >= BITSET_LOG_COUNT_BINS) - i = BITSET_LOG_COUNT_BINS - 1; - BITSET_STATS_LIST_COUNTS_INC (bset, i); - - /* Log histogram of number of bits in set. */ - size = bitset_size (bset); - for (i = 0, tmp = size; tmp; tmp >>= 1, i++) - continue; - if (i >= BITSET_LOG_SIZE_BINS) - i = BITSET_LOG_SIZE_BINS - 1; - BITSET_STATS_LIST_SIZES_INC (bset, i); - - /* Histogram of fraction of bits set. */ - i = size ? (count * BITSET_DENSITY_BINS) / size : 0; - if (i >= BITSET_DENSITY_BINS) - i = BITSET_DENSITY_BINS - 1; - BITSET_STATS_LIST_DENSITY_INC (bset, i); - } - return count; -} - - -/* Print a percentage histogram with message MSG to FILE. */ -static void -bitset_percent_histogram_print (file, name, msg, n_bins, bins) - FILE *file; - const char *name; - const char *msg; - unsigned int n_bins; - unsigned int *bins; +bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3) { - unsigned int i; - unsigned int total; - - total = 0; - for (i = 0; i < n_bins; i++) - total += bins[i]; - - if (!total) - return; - - fprintf (file, "%s %s", name, msg); - for (i = 0; i < n_bins; i++) - fprintf (file, "%.0f-%.0f%%\t%8d (%5.1f%%)\n", - i * 100.0 / n_bins, - (i + 1) * 100.0 / n_bins, - bins[i], (100.0 * bins[i]) / total); + bitset_or_and_cmp_ (dst, src1, src2, src3); } -/* Print a log histogram with message MSG to FILE. */ -static void -bitset_log_histogram_print (file, name, msg, n_bins, bins) - FILE *file; - const char *name; - const char *msg; - unsigned int n_bins; - unsigned int *bins; -{ - unsigned int i; - unsigned int total; - unsigned int max_width; - - total = 0; - for (i = 0; i < n_bins; i++) - total += bins[i]; - - if (!total) - return; - - /* 2 * ceil (log10(2) * (N - 1)) + 1 */ - max_width = 2 * (unsigned int)(0.30103 * (n_bins - 1) + 0.9999) + 1; - - fprintf (file, "%s %s", name, msg); - for (i = 0; i < 2; i++) - fprintf (file, "%*d\t%8d (%5.1f%%)\n", - max_width, i, bins[i], 100.0 * bins[i] / total); - - /* Perhaps we should bail out once the histogram goes to zero. */ - for (; i < n_bins; i++) - fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n", - max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1), - 1 << (i - 1), (1 << i) - 1, bins[i], (100.0 * bins[i]) / total); -} - - -/* Print bitset statistics to FILE. */ -static void -bitset_stats_print_1 (file, name, stats) - FILE *file; - const char *name; - struct bitset_type_stats_struct *stats; -{ - if (!stats) - return; - - fprintf (file, "%d %ss xmalloced, %d freed.\n", - stats->xmallocs, name, stats->xfrees); - fprintf (file, "%d %ss oballoced, %d freed.\n", - stats->oballocs, name, stats->obfrees); - - fprintf (file, "%d bitset_lists\n", stats->lists); - - bitset_log_histogram_print (file, name, "count log histogram\n", - BITSET_LOG_COUNT_BINS, stats->list_counts); - - bitset_log_histogram_print (file, name, "size log histogram\n", - BITSET_LOG_SIZE_BINS, stats->list_sizes); - - bitset_percent_histogram_print (file, name, "density histogram\n", - BITSET_DENSITY_BINS, stats->list_density); -} - - -/* Print all bitset statistics to FILE. */ -static void -bitset_stats_print (file, verbose) - FILE *file; - int verbose ATTRIBUTE_UNUSED; -{ - int i; - static const char *names[] = BITSET__TYPE_NAMES; - - if (!bitset_stats) - return; - - fprintf (file, "Bitset statistics:\n\n"); - - if (bitset_stats->runs > 1) - fprintf (file, "Accumulated runs = %d\n", bitset_stats->runs); - - for (i = 0; i < BITSET_TYPE_NUM; i++) - bitset_stats_print_1 (file, names[i], &bitset_stats->types[i]); -} -#endif /* BITSET_STATS */ - - -/* Initialise bitset statistics logging. */ -void -bitset_stats_init () -{ -#if BITSET_STATS - bitset_stats = &bitset_stats_data; - bitset_stats_read (); -#endif /* BITSET_STATS */ -} - - -/* Read bitset statistics file. */ -static void -bitset_stats_read () -{ - FILE *file; - - if (!bitset_stats) - return; - - file = fopen (BITSET_STATS_FILE, "r"); - if (file) - { - if (fread (&bitset_stats_data, sizeof (bitset_stats_data), - 1, file) != 1) - { - if (ferror (file)) - perror ("Could not read stats file"); - else - fprintf (stderr, "Bad stats file size\n"); - } - fclose (file); - } - bitset_stats_data.runs++; -} - - -/* Write bitset statistics file. */ -static void -bitset_stats_write () -{ - FILE *file; - - if (!bitset_stats) - return; - - file = fopen (BITSET_STATS_FILE, "w"); - if (file) - { - if (fwrite (&bitset_stats_data, sizeof (bitset_stats_data), - 1, file) != 1) - perror ("Could not write stats file"); - fclose (file); - } - else - perror ("Could not open stats file for writing"); -} - - -/* Dump bitset statistics to FILE. */ -void -bitset_stats_dump (file) - FILE *file; +/* 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 BITSET_STATS - bitset_stats_print (file, 0); - bitset_stats_write (); -#endif /* BITSET_STATS */ + return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND); } -/* Function to be called from debugger to print bitset stats. */ +/* Function to be called from debugger to print bitset. */ void -debug_bitset_stats (void) +debug_bitset (bitset bset) { -#if BITSET_STATS - bitset_stats_print (stderr, 1); -#endif /* BITSET_STATS */ + if (bset) + bitset_print (stderr, bset, true); }