X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/ef0175024063536689906e706f83ee9a12af98e3..85ac3861e7c7de8877562ac0dbb1233d91c705c2:/lib/bitset.c diff --git a/lib/bitset.c b/lib/bitset.c index 23df1791..aaf1e87f 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -1,5 +1,5 @@ /* General bitsets. - Copyright (C) 2002 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004 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 @@ -14,127 +14,39 @@ 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. */ + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifdef HAVE_CONFIG_H #include "config.h" #endif #include +#include #include "bitset.h" -#include "sbitset.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)); - -#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[BITSET_TYPE_ (BSET)].xfrees++ - -#define BITSET_STATS_OBALLOCS_INC(TYPE) \ - if (bitset_stats) \ - bitset_stats->types[(TYPE)].oballocs++ - -#define BITSET_STATS_OBFREES_INC(BSET) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].obfrees++ - -#define BITSET_STATS_LISTS_INC(BSET) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].lists++ - -#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++ - -#define BITSET_STATS_LIST_SIZES_INC(BSET, I) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++ - -#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].list_density[(I)]++ - -#else -#define BITSET_STATS_XMALLOCS_INC(TYPE) - -#define BITSET_STATS_XFREES_INC(BSET) - -#define BITSET_STATS_OBALLOCS_INC(TYPE) - -#define BITSET_STATS_OBFREES_INC(BSET) - -#define BITSET_STATS_LISTS_INC(BSET) - -#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) - -#define BITSET_STATS_LIST_SIZES_INC(BSET, I) - -#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) -#endif /* BITSET_STATS */ +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) { case BITSET_ARRAY: - bytes = sbitset_bytes (n_bits); + bytes = abitset_bytes (n_bits); break; case BITSET_LIST: @@ -145,6 +57,10 @@ bitset_bytes (type, n_bits) bytes = ebitset_bytes (n_bits); break; + case BITSET_VARRAY: + bytes = vbitset_bytes (n_bits); + break; + default: abort (); } @@ -155,15 +71,15 @@ 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) { case BITSET_ARRAY: - return sbitset_init (bset, n_bits); + return abitset_init (bset, n_bits); case BITSET_LIST: return lbitset_init (bset, n_bits); @@ -171,6 +87,9 @@ bitset_init (bset, n_bits, type) case BITSET_TABLE: return ebitset_init (bset, n_bits); + case BITSET_VARRAY: + return vbitset_init (bset, n_bits); + default: abort (); } @@ -181,55 +100,48 @@ 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; - -#if BITSET_CHECK /* 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. */ + + /* If no attributes selected, choose a good compromise. */ + if (!attr) + return BITSET_VARRAY; - 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 (attr & BITSET_SPARSE) + return BITSET_LIST; + + if (attr & BITSET_FIXED) + return BITSET_ARRAY; - return type; + if (attr & BITSET_GREEDY) + return BITSET_TABLE; + + 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) xcalloc (1, bytes); /* The cache is disabled until some elements are allocated. If we - have variable length arrays, then we may need to allocate dummy + have variable length arrays, then we may need to allocate a dummy element. */ return bitset_init (bset, n_bits, type); @@ -238,16 +150,12 @@ 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; - BITSET_STATS_OBALLOCS_INC (type); - bytes = bitset_bytes (type, n_bits); bset = obstack_alloc (bobstack, bytes); @@ -260,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; @@ -274,11 +180,8 @@ bitset_create (n_bits, attr) /* Free bitset BSET. */ void -bitset_free (bset) - bitset bset; +bitset_free (bitset bset) { - BITSET_STATS_XFREES_INC (bset); - BITSET_FREE_ (bset); free (bset); } @@ -286,79 +189,117 @@ bitset_free (bset) /* Free bitset BSET allocated on obstack. */ void -bitset_obstack_free (bset) - bitset bset; +bitset_obstack_free (bitset bset) { - BITSET_STATS_OBFREES_INC (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) +{ + 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); } +/* 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) { @@ -368,224 +309,131 @@ bitset_print (file, bset, verbose) fprintf (file, "%d ", i); pos += 1 + (i >= 10) + (i >= 100); - }); + }; if (verbose) fprintf (file, "}\n"); } -/* DST = SRC. Return non-zero if DST != SRC. */ -int -bitset_copy (dst, src) - bitset dst; - bitset src; -{ - unsigned int i; - - 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_EXECUTE (src, 0, i, - { - bitset_set (dst, i); - }); - - return 1; -} - - -/* Return size in bits of bitset SRC. */ -int -bitset_size (src) - bitset src; -{ - return BITSET_SIZE_ (src); -} - - -/* Return number of bits set in bitset SRC. */ -int -bitset_count (src) - bitset src; -{ - bitset_bindex list[BITSET_LIST_SIZE]; - bitset_bindex next; - int num; - int count; - - next = 0; - 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; +/* Dump bitset BSET to FILE. */ +void +bitset_dump (FILE *file, bitset bset) { - BITSET_CHECK2_ (dst, src); - return BITSET_SUBSET_P_ (dst, src); + bitset_print (file, bset, false); } -/* Return DST == SRC. */ -int -bitset_equal_p (dst, src) - bitset dst; - bitset src; +/* Release memory associated with bitsets. */ +void +bitset_release_memory (void) { - BITSET_CHECK2_ (dst, src); - return BITSET_EQUAL_P_ (dst, src); + lbitset_release_memory (); + ebitset_release_memory (); } -/* Return DST & SRC == 0. */ -int -bitset_disjoint_p (dst, src) - bitset dst; - bitset src; +/* Toggle bit BITNO in bitset BSET and the new value of the bit. */ +bool +bitset_toggle_ (bitset bset, bitset_bindex bitno) { - BITSET_CHECK2_ (dst, src); - return BITSET_DISJOINT_P_ (dst, src); + /* 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 = ~SRC. */ -int -bitset_not (dst, src) - bitset dst; - bitset src; +/* Return number of bits in bitset SRC. */ +bitset_bindex +bitset_size_ (bitset src) { - BITSET_CHECK2_ (dst, src); - return BITSET_NOT_ (dst, src); + return BITSET_NBITS_ (src); } -/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */ -int -bitset_or (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +/* Return number of bits set in bitset SRC. */ +bitset_bindex +bitset_count_ (bitset src) { - BITSET_CHECK3_ (dst, src1, src2); - return BITSET_OR_ (dst, src1, src2); -} - + bitset_bindex list[BITSET_LIST_SIZE]; + bitset_bindex next; + bitset_bindex num; + bitset_bindex count; -/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */ -int -bitset_and (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - BITSET_CHECK3_ (dst, src1, src2); - return BITSET_AND_ (dst, src1, src2); -} + /* 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; -/* 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_XOR_ (dst, src1, src2); + return count; } -/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */ -int -bitset_andn (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) { - BITSET_CHECK3_ (dst, src1, src2); - return BITSET_ANDN_ (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_orn (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; -{ - BITSET_CHECK3_ (dst, src1, src2); - return BITSET_ORN_ (dst, src1, src2); + return true; } -int -bitset_op4 (dst, src1, src2, src3, op) - bitset dst; - bitset src1; - bitset src2; - bitset src3; - enum bitset_ops op; +/* 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) { - int changed = 0; + bool changed = false; + bool stats_enabled_save; bitset tmp; /* Create temporary bitset. */ - tmp = bitset_alloc (BITSET_TYPE_ (dst), 0); + 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) { 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: @@ -597,316 +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) { - BITSET_CHECK4_ (dst, src1, src2, 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) { - BITSET_CHECK4_ (dst, src1, src2, src3); - return BITSET_AND_OR_ (dst, src1, src2, 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 -bitset_andn_or (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; -{ - BITSET_CHECK4_ (dst, src1, src2, src3); - return BITSET_ANDN_OR_ (dst, src1, src2, src3); -} - - -/* Dump bitset BSET to FILE. */ -void -bitset_dump (file, bset) - FILE *file; - bitset bset; -{ - bitset_print (file, bset, 0); -} - - -/* Function to be called from debugger to print bitset. */ -void -debug_bitset (bset) - bitset bset; -{ - if (bset) - bitset_print (stderr, bset, 1); -} - - -/* Release memory associated with bitsets. */ +/* DST = (SRC1 & ~SRC2) | SRC3. */ void -bitset_release_memory () +bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3) { - lbitset_release_memory (); - ebitset_release_memory (); + bitset_andn_or_cmp_ (dst, src1, src2, src3); } -#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 = BITSET_TYPE_ (bset); - 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; -{ - 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); -} - - -/* 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; +/* 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) { - 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); + return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR); } -/* 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. */ +/* DST = (SRC1 | SRC2) & SRC3. */ 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 () +bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3) { - 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++; + bitset_or_and_cmp_ (dst, src1, src2, src3); } -/* 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); }