/* 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 "sbitset.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));
-
-#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)
{
+ default:
+ abort ();
+
case BITSET_ARRAY:
- bytes = sbitset_bytes (n_bits);
+ bytes = abitset_bytes (n_bits);
break;
case BITSET_LIST:
bytes = ebitset_bytes (n_bits);
break;
- default:
- abort ();
+ case BITSET_VARRAY:
+ bytes = vbitset_bytes (n_bits);
+ break;
}
return bytes;
/* 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);
case BITSET_TABLE:
return ebitset_init (bset, n_bits);
- default:
- abort ();
+ case BITSET_VARRAY:
+ return vbitset_init (bset, n_bits);
}
}
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. */
- 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;
- return type;
+ if (attr & BITSET_SPARSE)
+ return BITSET_LIST;
+
+ if (attr & BITSET_FIXED)
+ return BITSET_ARRAY;
+
+ 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);
+ 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 dummy
+ have variable length arrays, then we may need to allocate a dummy
element. */
return bitset_init (bset, 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);
/* 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;
/* Free bitset BSET. */
void
-bitset_free (bset)
- bitset bset;
+bitset_free (bitset bset)
{
- BITSET_STATS_XFREES_INC (bset);
-
BITSET_FREE_ (bset);
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)
{
- 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);
- });
+ };
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;
+ /* 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. */
-/* 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);
-}
-
+ 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)
{
+ 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);
}
-/* 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;
-{
- BITSET_CHECK4_ (dst, src1, src2, src3);
- return BITSET_AND_OR_ (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;
-{
- 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;
+bool
+bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
{
- bitset_print (file, bset, 0);
+ return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
}
-/* Function to be called from debugger to print bitset. */
+/* DST = (SRC1 & ~SRC2) | SRC3. */
void
-debug_bitset (bset)
- bitset bset;
+bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
{
- if (bset)
- bitset_print (stderr, bset, 1);
+ bitset_andn_or_cmp_ (dst, src1, src2, src3);
}
-/* Release memory associated with bitsets. */
-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 = 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;
-{
- 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;
+/* 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)
{
- 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]);
+ return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
}
-#endif /* BITSET_STATS */
-/* Initialise bitset statistics logging. */
+/* DST = (SRC1 | SRC2) & SRC3. */
void
-bitset_stats_init ()
+bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3)
{
-#if BITSET_STATS
- bitset_stats = &bitset_stats_data;
- bitset_stats_read ();
-#endif /* BITSET_STATS */
+ bitset_or_and_cmp_ (dst, src1, src2, src3);
}
-/* 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);
}
projects / bison.git / blobdiff