From: Akim Demaille Date: Mon, 4 Mar 2002 11:58:52 +0000 (+0000) Subject: * lib/bitset-int.h, lib/bitset.c, lib/bitset.h, lib/bitsetv.c, X-Git-Tag: BISON-1_49a~135 X-Git-Url: https://git.saurik.com/bison.git/commitdiff_plain/7086e7071e8bfa2012e9134530a158c88a832ba6?ds=sidebyside * lib/bitset-int.h, lib/bitset.c, lib/bitset.h, lib/bitsetv.c, * lib/bitsetv.h, lib/ebitset.c, lib/ebitset.h, lib/lbitset.c, * lib/lbitset.h, lib/sbitset.c, lib/sbitset.h: New. * src/closure.c (fderives): Be an array of bitsets. --- diff --git a/ChangeLog b/ChangeLog index 16bef4f6..70a04ba0 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2002-03-04 Akim Demaille + + * lib/bitset-int.h, lib/bitset.c, lib/bitset.h, lib/bitsetv.c, + * lib/bitsetv.h, lib/ebitset.c, lib/ebitset.h, lib/lbitset.c, + * lib/lbitset.h, lib/sbitset.c, lib/sbitset.h: New. + * src/closure.c (fderives): Be an array of bitsets. + 2002-02-28 Robert Anisko * data/bison.c++: Merge the two generated headers. Insert a copyright diff --git a/lib/Makefile.am b/lib/Makefile.am index 99ec8c8e..5dfdb11c 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -42,5 +42,10 @@ libbison_a_SOURCES = \ xalloc.h xmalloc.c xstrdup.c xstrndup.c \ readpipe.c +# Implementation of bitsets +libbison_a_SOURCES += \ + bitset-int.h bitset.h bitsetv.h ebitset.h lbitset.h sbitset.h \ + bitset.c bitsetv.c ebitset.c lbitset.c sbitset.c + libbison_a_LIBADD = @LIBOBJS@ @ALLOCA@ libbison_a_DEPENDENCIES = $(libbison_a_LIBADD) diff --git a/lib/bitset-int.h b/lib/bitset-int.h new file mode 100644 index 00000000..6c51166f --- /dev/null +++ b/lib/bitset-int.h @@ -0,0 +1,112 @@ +/* Internal bitset definitions. + 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. */ + +#ifndef _BITSET_INT_H +#define _BITSET_INT_H + +#ifdef HAVE_LIMITS_H +#include +#endif + +/* Currently we support three flavours of bitsets: + BITSET_ARRAY: Array of bits (fixed size, faster). + BITSET_LIST: Linked list of array of bits (variable size, least storage + for large very sparse sets). + BITSET_TABLE: Expandable table of pointers to array of bits + (variable size, less storage for large sparse sets). +*/ +enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM}; +#define BITSET__TYPE_NAMES {"sbitset", "lbitset", "ebitset"} + +/* Non-zero to enable bitset caching. */ +#define BITSET_CACHE 1 + +/* Non-zero to use inline functions instead of macros. */ +#define BITSET_INLINE 0 + +/* Non-zero to enable bitset statistics gathering. */ +#define BITSET_STATS 1 + +/* Non-zero to enable bitset type checking. */ +#define BITSET_CHECK 0 + +typedef unsigned long bitset_word; +#define BITSET_WORD_BITS ((unsigned) CHAR_BIT * sizeof (bitset_word)) + +/* Bit index. */ +typedef unsigned long bitset_bindex; + +/* Word index. */ +typedef unsigned long bitset_windex; + +#define BITSET_INDEX_MAX ((1U << (BITSET_WORD_BITS - 1))) + +#define BITSET_MSB (1U << (BITSET_WORD_BITS - 1)) + +#define BITSET_LIST_SIZE 1024 + +enum bitset_ops {BITSET_ZERO, BITSET_ONES, BITSET_EMPTY_P, + BITSET_COPY, BITSET_EQUAL_P, BITSET_SUBSET_P, BITSET_NOT, + BITSET_AND, BITSET_OR, BITSET_XOR, BITSET_ANDN, BITSET_ORN, + BITSET_OR_AND, BITSET_AND_OR, BITSET_ANDN_OR}; + +/* Return size in bits of bitset SRC. */ +#define BITSET__SIZE(SRC) (SRC)->ops->size (SRC) + +/* Set bit BITNO in bitset DST. */ +#define BITSET__SET(DST, BITNO) (DST)->ops->set (DST, BITNO) + +/* Reset bit BITNO in bitset DST. */ +#define BITSET__RESET(DST, BITNO) (DST)->ops->reset (DST, BITNO) + +/* Return non-zero if bit BITNO in bitset SRC is set. */ +#define BITSET__TEST(SRC, BITNO) (SRC)->ops->test (SRC, BITNO) + +/* Free bitset SRC. */ +#define BITSET__FREE(SRC) ((SRC)->ops->free) (SRC) + +/* Perform operation OP on DST. */ +#define BITSET__OP1(DST, OP) (DST)->ops->op1 (DST, OP) + +/* Perform operation OP on SRC and store in DST. */ +#define BITSET__OP2(DST, SRC, OP) (DST)->ops->op2 (DST, SRC, OP) + +/* DST = SRC1 OP SRC2. */ +#define BITSET__OP3(DST, SRC1, SRC2, OP) \ +(DST)->ops->op3 (DST, SRC1, SRC2, OP) + +/* DST = (SRC1 OP1 SRC2) OP2 SRC3. */ +#define BITSET__OP4(DST, SRC1, SRC2, SRC3, OP) \ +(DST)->ops->op4 (DST, SRC1, SRC2, SRC3, OP) + +/* DST = SRC. */ +#define BITSET__COPY(DST, SRC) BITSET__OP2 (DST, SRC, BITSET_COPY) + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT. Return with actual number of bits found and with *NEXT + indicating where search stopped. */ +#define BITSET__LIST(BSET, LIST, NUM, NEXT) \ +(BSET)->ops->list (BSET, LIST, NUM, NEXT) + +/* Find reverse list of up to NUM bits set in BSET starting from and + including NEXT. Return with actual number of bits found and with + *NEXT indicating where search stopped. */ +#define BITSET__REVERSE_LIST(BSET, LIST, NUM, NEXT) \ +(BSET)->ops->reverse_list (BSET, LIST, NUM, NEXT) + +#endif /* _BITSET_INT_H */ diff --git a/lib/bitset.c b/lib/bitset.c new file mode 100644 index 00000000..c68ed788 --- /dev/null +++ b/lib/bitset.c @@ -0,0 +1,835 @@ +/* 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++ + +#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) + +#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 */ + + + +/* 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; +{ + unsigned int bytes; + + switch (type) + { + case BITSET_ARRAY: + bytes = sbitset_bytes (n_bits); + break; + + case BITSET_LIST: + bytes = lbitset_bytes (n_bits); + break; + + case BITSET_TABLE: + bytes = ebitset_bytes (n_bits); + break; + + default: + abort (); + } + + 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; +{ + switch (type) + { + case BITSET_ARRAY: + return sbitset_init (bset, n_bits); + + case BITSET_LIST: + return lbitset_init (bset, n_bits); + + case BITSET_TABLE: + return ebitset_init (bset, n_bits); + + default: + abort (); + } +} + + +/* Select a bitset type for a set of N_BITS and with attribute hints + 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; +{ + 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. */ + + 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; +} + + +/* Create a bitset of N_BITS of type TYPE. */ +bitset +bitset_alloc (n_bits, type) + bitset_bindex n_bits; + enum bitset_type type; +{ + unsigned int bytes; + bitset bset; + + BITSET_STATS_XMALLOCS_INC (type); + + bytes = bitset_bytes (type, n_bits); + + bset = (bitset) xmalloc (bytes); + + 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; +{ + unsigned int bytes; + + BITSET_STATS_OBALLOCS_INC (type); + + bytes = bitset_bytes (type, n_bits); + + return bitset_init (obstack_alloc (bobstack, bytes), 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; +{ + enum bitset_type type; + + type = bitset_type_choose (n_bits, attr); + + return bitset_alloc (n_bits, type); +} + + +/* Free bitset BSET. */ +void +bitset_free (bset) + bitset bset; +{ + BITSET_STATS_XFREES_INC (bset); + + if (bset->ops->free) + BITSET__FREE (bset); + + bset->ops = NULL; + free (bset); +} + + +/* Free bitset BSET allocated on obstack. */ +void +bitset_obstack_free (bset) + bitset bset; +{ + BITSET_STATS_OBFREES_INC (bset); + + if (bset->ops->free) + BITSET__FREE (bset); + bset->ops = NULL; +} + + +/* 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; +{ + bitset_bindex val; + bitset_bindex next = bitno; + + if (!bitset_list (src, &val, 1, &next)) + return -1; + return val; +} + + +/* 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; +{ + bitset_bindex val; + bitset_bindex next = bitno; + + if (!bitset_reverse_list (src, &val, 1, &next)) + return -1; + return val; +} + + +/* Find first set bit. */ +int +bitset_first (src) + bitset src; +{ + return bitset_next (src, 0); +} + + +/* Find last set bit. */ +int +bitset_last (src) + bitset src; +{ + return bitset_prev (src, 0); +} + + +static void +bitset_print (file, bset, verbose) + FILE *file; + bitset bset; + int verbose; +{ + unsigned int i, pos; + + if (verbose) + fprintf (file, "n_bits = %d, set = {", bitset_size (bset)); + + pos = 30; + BITSET_EXECUTE (bset, 0, i, + { + if (pos > 70) + { + fprintf (file, "\n"); + pos = 0; + } + + fprintf (file, "%d ", i); + pos += 1 + (i >= 10) + (i >= 100); + }); + + if (verbose) + fprintf (file, "}\n"); +} + + +int +bitset_copy (dst, src) + bitset dst; + bitset src; +{ + 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; +} + + +/* Return size in bits of bitset SRC. */ +int +bitset_size (src) + bitset src; +{ + return BITSET__SIZE (src); +} + + +/* DST = 0. */ +int +bitset_zero (dst) + bitset dst; +{ + return BITSET__OP1 (dst, BITSET_ZERO); +} + + +/* DST = ~0. */ +int +bitset_ones (dst) + bitset dst; +{ + return BITSET__OP1 (dst, BITSET_ONES); +} + + +/* Return non-zero if all bits in bitset SRC are reset. */ +int +bitset_empty_p (src) + bitset src; +{ + return BITSET__OP1 (src, BITSET_EMPTY_P); +} + + +/* Return DST == DST | SRC. */ +int +bitset_subset_p (dst, src) + bitset dst; + bitset src; +{ + return BITSET__OP2 (dst, src, BITSET_SUBSET_P); +} + + +/* 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); +} + + +/* DST = ~SRC. */ +int +bitset_not (dst, src) + bitset dst; + bitset src; +{ + BITSET__CHECK2 (dst, src); + return BITSET__OP2 (dst, src, BITSET_NOT); +} + + +/* 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); +} + + +/* 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__OP3 (dst, src1, src2, BITSET_AND); +} + + +/* 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); +} + + +/* 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); +} + + +/* 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); +} + + +/* 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; +{ + BITSET__CHECK4 (dst, src1, src2, src3); + return BITSET__OP4 (dst, src1, src2, src3, BITSET_OR_AND); +} + + +/* 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__OP4 (dst, src1, src2, src3, BITSET_AND_OR); +} + + +/* 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; +{ + bitset_print (stderr, bset, 1); +} + + +/* 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 = 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; +{ + 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; +{ + 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; +{ +#if BITSET_STATS + bitset_stats_print (file, 0); + bitset_stats_write (); +#endif /* BITSET_STATS */ +} + + +/* Function to be called from debugger to print bitset stats. */ +void +debug_bitset_stats (void) +{ +#if BITSET_STATS + bitset_stats_print (stderr, 1); +#endif /* BITSET_STATS */ +} diff --git a/lib/bitset.h b/lib/bitset.h new file mode 100644 index 00000000..4afbbf4f --- /dev/null +++ b/lib/bitset.h @@ -0,0 +1,395 @@ +/* Generic 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. */ + +#ifndef _BITSET_H +#define _BITSET_H + +#if HAVE_CONFIG_H +# include +#endif + +#define BITSET_STATS 1 + +# ifndef PARAMS +# if defined PROTOTYPES || (defined __STDC__ && __STDC__) +# define PARAMS(Args) Args +# else +# define PARAMS(Args) () +# endif +# endif + +# ifndef __attribute__ +# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__ +# define __attribute__(x) +# endif +# endif + +# ifndef ATTRIBUTE_NORETURN +# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__)) +# endif + +# ifndef ATTRIBUTE_UNUSED +# define ATTRIBUTE_UNUSED __attribute__ ((__unused__)) +# endif + +#include "bitset-int.h" +#include "sbitset.h" +#include "lbitset.h" +#include "ebitset.h" +#include "obstack.h" +#include +#include "xalloc.h" + +enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */ + BITSET_VARIABLE = 2, /* Bitset size variable. */ + BITSET_DENSE = 4, /* Bitset dense. */ + BITSET_SPARSE = 8, /* Bitset sparse. */ + BITSET_FRUGAL = 16, /* Prefer most compact. */ + BITSET_GREEDY = 32}; /* Prefer fastest. */ + +typedef unsigned int bitset_attrs; + +/* The elements of these structures should be considered + to be private. */ +typedef struct bitset_struct +{ + struct bitset_ops_struct *ops; + bitset_windex cindex; /* Cache word index. */ + bitset_windex csize; /* Cache size in words. */ + bitset_word *cdata; /* Cache data pointer. */ + union bitset_data + { + struct sbitset_struct s; + struct lbitset_struct l; + struct ebitset_struct e; + } u; +} *bitset; + + +/* The contents of this structure should be considered private. */ +struct bitset_ops_struct +{ + void (*set) PARAMS ((struct bitset_struct *, bitset_bindex)); + void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex)); + int (*test) PARAMS ((struct bitset_struct *, bitset_bindex)); + int (*size) PARAMS ((struct bitset_struct *)); + int (*op1) PARAMS ((struct bitset_struct *, enum bitset_ops)); + int (*op2) PARAMS ((struct bitset_struct *, struct bitset_struct *, + enum bitset_ops)); + int (*op3) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, enum bitset_ops)); + int (*op4) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, struct bitset_struct *, + enum bitset_ops)); + int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *, + bitset_bindex, bitset_bindex *)); + int (*reverse_list) PARAMS ((struct bitset_struct *, bitset_bindex *, + bitset_bindex, bitset_bindex *)); + void (*free) PARAMS ((struct bitset_struct *)); + enum bitset_type type; +}; + + +/* Return bytes required for bitset of desired type and size. */ +extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex)); + +/* Initialise a bitset with desired type and size. */ +extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type)); + +extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex, + bitset_attrs)); + +/* Create a bitset of desired type and size. */ +extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type)); + +/* Free bitset. */ +extern void bitset_free PARAMS ((bitset)); + +/* Create a bitset of desired type and size using obstack. */ +extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack, + bitset_bindex, enum bitset_type)); + +/* Free bitset allocated on obstack. */ +extern void bitset_obstack_free PARAMS ((bitset)); + +/* Create a bitset of desired size and attributes. */ +extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs)); + +/* Return size in bits of bitset SRC. */ +extern int bitset_size PARAMS ((bitset)); + +#if BITSET_CACHE && BITSET_INLINE +static inline void bitset_set PARAMS ((bitset, bitset_bindex)); +static inline void bitset_reset PARAMS ((bitset, bitset_bindex)); +static inline int bitset_test PARAMS ((bitset, bitset_bindex)); + +/* Set bit BITNO in bitset BSET. */ +static inline void bitset_set (bset, bitno) + bitset bset; + bitset_bindex bitno; +{ + bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex offset = index - bset->cindex; + + if (offset < bset->csize) + bset->cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS)); + else + BITSET__SET (bset, bitno); +} + + +/* Reset bit BITNO in bitset BSET. */ +static inline void bitset_reset (bset, bitno) + bitset bset; + bitset_bindex bitno; +{ + bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex offset = index - bset->cindex; + + if (offset < bset->csize) + bset->cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS)); + else + BITSET__RESET (bset, bitno); +} + + +/* Test bit BITNO in bitset BSET. */ +static inline int bitset_test (bset, bitno) + bitset bset; + bitset_bindex bitno; +{ + bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex offset = index - bset->cindex; + + if (offset < bset->csize) + return (bset->cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1; + else + return BITSET__TEST (bset, bitno); +} +#endif + +#if BITSET_CACHE && ! BITSET_INLINE + +/* Set bit BITNO in bitset BSET. */ +#define bitset_set(bset, bitno) \ +do \ +{ \ + bitset_bindex _bitno = (bitno); \ + bitset_windex _index = _bitno / BITSET_WORD_BITS; \ + bitset_windex _offset = _index - (bset)->cindex; \ + \ + if (_offset < (bset)->csize) \ + (bset)->cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS)); \ + else \ + BITSET__SET ((bset), _bitno); \ +} while (0) + + +/* Reset bit BITNO in bitset BSET. */ +#define bitset_reset(bset, bitno) \ +do \ +{ \ + bitset_bindex _bitno = (bitno); \ + bitset_windex _index = _bitno / BITSET_WORD_BITS; \ + bitset_windex _offset = _index - (bset)->cindex; \ + \ + if (_offset < (bset)->csize) \ + (bset)->cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \ + else \ + BITSET__RESET ((bset), _bitno); \ +} while (0) + + +/* Test bit BITNO in bitset BSET. */ +#define bitset_test(bset, bitno) \ +(((((bitno) / BITSET_WORD_BITS) - (bset)->cindex) < (bset)->csize) \ + ? ((bset)->cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->cindex)] \ + >> ((bitno) % BITSET_WORD_BITS)) & 1 \ + : (unsigned int) BITSET__TEST ((bset), (bitno))) +#endif + +#if ! BITSET_CACHE +/* Set bit BITNO in bitset SRC. */ +#define bitset_set(SRC, BITNO) BITSET__SET (SRC, BITNO) + +/* Reset bit BITNO in bitset SRC. */ +#define bitset_reset(SRC, BITNO) BITSET__RESET (SRC, BITNO) + +/* Return non-zero if bit BITNO in bitset SRC is set. */ +#define bitset_test(SRC, BITNO) BITSET__TEST (SRC, BITNO) +#endif + +/* DST = 0. */ +extern int bitset_zero PARAMS ((bitset)); + +/* DST = ~0. */ +extern int bitset_ones PARAMS ((bitset)); + +/* Return non-zero if all bits in bitset SRC are reset. */ +extern int bitset_empty_p PARAMS ((bitset)); + +/* Return DST == DST | SRC. */ +extern int bitset_subset_p PARAMS ((bitset, bitset)); + +/* Return DST == SRC. */ +extern int bitset_equal_p PARAMS ((bitset, bitset)); + +/* DST == SRC. */ +extern int bitset_copy PARAMS ((bitset, bitset)); + +/* DST = ~SRC. */ +extern int bitset_not PARAMS ((bitset, bitset)); + +/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */ +extern int bitset_or PARAMS ((bitset, bitset, bitset)); + +/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */ +extern int bitset_and PARAMS ((bitset, bitset, bitset)); + +/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */ +extern int bitset_xor PARAMS ((bitset, bitset, bitset)); + +/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */ +extern int bitset_andn PARAMS ((bitset, bitset, bitset)); + +/* DST = SRC1 | ~SRC2. Return non-zero if DST != SRC1 | ~SRC2. */ +extern int bitset_orn PARAMS ((bitset, bitset, bitset)); + +/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if + DST != (SRC1 | SRC2) & SRC3. */ +extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset)); + +/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if + DST != (SRC1 & SRC2) | SRC3. */ +extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset)); + +/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if + DST != (SRC1 & ~SRC2) | SRC3. */ +#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \ + +/* Find next bit set in BSET starting from and including BITNO. */ +extern int bitset_next PARAMS ((bitset, bitset_bindex)); + +/* Find previous bit set in BSET starting from and including BITNO. */ +extern int bitset_prev PARAMS ((bitset, bitset_bindex)); + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT. Return with actual number of bits found and with *NEXT + indicating where search stopped. */ +#if BITSET_STATS +extern int bitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +#else +#define bitset_list(BSET, LIST, NUM, NEXT) \ +BITSET__LIST (BSET, LIST, NUM, NEXT) +#endif + +/* Find reverse list of up to NUM bits set in BSET starting from and + including NEXT. Return with actual number of bits found and with + *NEXT indicating where search stopped. */ +#define bitset_reverse_list(BSET, LIST, NUM, NEXT) \ +BITSET__REVERSE_LIST (BSET, LIST, NUM, NEXT) + +/* Find first set bit. */ +extern int bitset_first PARAMS ((bitset)); + +/* Find last set bit. */ +extern int bitset_last PARAMS ((bitset)); + +/* Dump bitset. */ +extern void bitset_dump PARAMS ((FILE *, bitset)); + +/* Loop over all elements of BSET, starting with MIN, executing CODE. */ +#define BITSET_EXECUTE(BSET, MIN, N, CODE) \ +do { \ + bitset_bindex _list[BITSET_LIST_SIZE]; \ + bitset_bindex _next = (MIN); \ + int _num; \ + \ + while ((_num = bitset_list ((BSET), _list, BITSET_LIST_SIZE, &_next)))\ + { \ + int _i; \ + \ + for (_i = 0; _i < _num; _i++) \ + { \ + (N) = _list[_i]; \ + CODE; \ + } \ + if (_num < BITSET_LIST_SIZE) \ + break; \ + } \ +} while (0) + + +/* Loop over all elements of BSET, in reverse order starting with + MIN, executing CODE. */ +#define BITSET_REVERSE_EXECUTE(BSET, MIN, N, CODE) \ +do { \ + bitset_bindex _list[BITSET_LIST_SIZE]; \ + bitset_bindex _next = (MIN); \ + int _num; \ + \ + while ((_num = bitset_reverse_list ((BSET), _list, \ + BITSET_LIST_SIZE, &_next))) \ + { \ + int _i; \ + \ + for (_i = 0; _i < _num; _i++) \ + { \ + (N) = _list[_i]; \ + CODE; \ + } \ + if (_num < BITSET_LIST_SIZE) \ + break; \ + } \ +} while (0) + + +/* Define set operations in terms of bit operations. */ + +#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2) + +#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2) + +#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2) + +#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \ +bitset_andn_or (DST, SRC1, SRC2, SRC3) + +/* Release any memory tied up with bitsets. */ +extern void bitset_release_memory PARAMS ((void)); + +/* Initialise bitset stats. */ +extern void bitset_stats_init PARAMS ((void)); + +/* Dump bitset stats. */ +extern void bitset_stats_dump PARAMS ((FILE *)); + +/* Function to debug bitset from debugger. */ +extern void debug_bitset PARAMS ((bitset)); + +/* Function to debug bitset stats from debugger. */ +extern void debug_bitset_stats PARAMS ((void)); + +extern bitset sbitset_init PARAMS ((bitset, bitset_bindex)); + +extern bitset lbitset_init PARAMS ((bitset, bitset_bindex)); + +extern bitset ebitset_init PARAMS ((bitset, bitset_bindex)); + +#endif /* _BITSET_H */ diff --git a/lib/bitsetv.c b/lib/bitsetv.c new file mode 100644 index 00000000..7fd82268 --- /dev/null +++ b/lib/bitsetv.c @@ -0,0 +1,128 @@ +/* Bitset vectors. + Copyright (C) 2001 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC 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, or (at your option) any later +version. + +GCC 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 GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include "bitsetv.h" + + +/* Create a vector of N_VECS bitsets, each of N_BITS, and of + type TYPE. */ +bitset * +bitsetv_alloc (n_vecs, n_bits, type) + unsigned int n_vecs; + unsigned int n_bits; + enum bitset_type type; +{ + unsigned int vector_bytes; + unsigned int bytes; + bitset *bsetv; + unsigned int i; + + /* Determine number of bytes for each set. */ + bytes = bitset_bytes (type, n_bits); + + /* Allocate vector table at head of bitset array. */ + vector_bytes = n_vecs * sizeof (bitset); + bsetv = (bitset *) xmalloc (vector_bytes + bytes * n_vecs); + + for (i = 0; i < n_vecs; i++) + { + bsetv[i] = (bitset)((char *)bsetv + vector_bytes + i * bytes); + + bitset_init (bsetv[i], n_bits, type); + } + return bsetv; +} + + +/* Create a vector of N_VECS bitsets, each of N_BITS, and with + attribute hints specified by ATTR. */ +bitset * +bitsetv_create (n_vecs, n_bits, attr) + unsigned int n_vecs; + unsigned int n_bits; + unsigned int attr; +{ + enum bitset_type type; + + type = bitset_type_choose (n_bits, attr); + return bitsetv_alloc (n_vecs, n_bits, type); +} + + +/* Free bitset vector BSETV. */ +void +bitsetv_free (bsetv) + bitset *bsetv; +{ + free (bsetv); +} + + +/* Zero a vector of N_VECS bitsets. */ +void +bitsetv_zero (bsetv, n_vecs) + struct bitset_struct **bsetv; + unsigned int n_vecs; +{ + unsigned int i; + + for (i = 0; i < n_vecs; i++) + bitset_zero (bsetv[i]); +} + + +/* Set a vector of N_VECS bitsets to ones. */ +void +bitsetv_ones (bsetv, n_vecs) + bitset *bsetv; + unsigned int n_vecs; +{ + unsigned int i; + + for (i = 0; i < n_vecs; i++) + bitset_ones (bsetv[i]); +} + + +/* Dump the contents of a bitset vector BSETV with N_VECS elements to + FILE. */ +void +bitsetv_dump (file, title, subtitle, bsetv, n_vecs) + FILE *file; + const char *title, *subtitle; + bitset *bsetv; + unsigned int n_vecs; +{ + unsigned int i; + + fprintf (file, "%s\n", title); + for (i = 0; i < n_vecs; i++) + { + fprintf (file, "%s %d\n", subtitle, i); + bitset_dump (file, bsetv[i]); + } + + fprintf (file, "\n"); +} diff --git a/lib/bitsetv.h b/lib/bitsetv.h new file mode 100644 index 00000000..cac4eb07 --- /dev/null +++ b/lib/bitsetv.h @@ -0,0 +1,49 @@ +/* Bitset vectors. + 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. */ + +#ifndef _BITSETV_H +#define _BITSETV_H + +#include "bitset.h" + +typedef bitset * bitsetv; + +/* Create a vector of N_VECS bitsets, each of N_BITS, and of + type TYPE. */ +extern bitsetv bitsetv_alloc PARAMS ((unsigned int, unsigned int, + enum bitset_type)); + +/* Create a vector of N_VECS bitsets, each of N_BITS, and with + attribute hints specified by ATTR. */ +extern bitsetv bitsetv_create PARAMS ((unsigned int, unsigned int, + unsigned int)); + +/* Free vector of bitsets. */ +extern void bitsetv_free PARAMS ((bitsetv)); + +/* Zero vector of bitsets. */ +extern void bitsetv_zero PARAMS ((bitsetv, unsigned int)); + +/* Set vector of bitsets. */ +extern void bitsetv_ones PARAMS ((bitsetv, unsigned int)); + +/* Dump vector of bitsets. */ +extern void bitsetv_dump PARAMS ((FILE *, const char *, + const char *, bitsetv, + unsigned int)); +#endif /* _BITSETV_H */ diff --git a/lib/ebitset.c b/lib/ebitset.c new file mode 100644 index 00000000..0a6cbd41 --- /dev/null +++ b/lib/ebitset.c @@ -0,0 +1,1245 @@ +/* Functions to support efficient 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 "bitset.h" +#include "obstack.h" +#include + +# if WITH_DMALLOC +# define DMALLOC_FUNC_CHECK +# include +# endif /* WITH_DMALLOC */ + +/* This file implements linked-list bitsets. These bitsets can be of + arbitrary length and are more efficient than arrays of bits for + large sparse sets. + + Usually if all the bits in an element are zero we remove the element + from the list. However, a side effect of the bit caching is that we + do not always notice when an element becomes zero. Hence the + ebitset_weed function which removes zero elements. + + Empty elements are represented by a NULL pointer in the table of + element pointers. An alternative is to point to a special zero + element. Similarly, we could represent an all 1's element with + another special ones element pointer. + + Bitsets are commonly empty so we need to ensure that this special + case is fast. A zero bitset is indicated when cdata is 0. This is + conservative since cdata may be non zero and the bitset may still + be zero. + + The bitset cache can be disabled either by setting cindex to + some large number or by setting csize to 0. Here + we use the former approach since cindex needs to be updated whenever + cdata is changed. +*/ + +/* Number of elements to initially allocate. */ +#ifndef EBITSET_INITIAL_SIZE +#define EBITSET_INITIAL_SIZE 2 +#endif + +/* Minimum number of elements to grow table. */ +#ifndef EBITSET_GROW_SIZE +#define EBITSET_GROW_SIZE 4 +#endif + + +enum ebitset_find_mode {EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST}; + +static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits. */ + +/* Obstack to allocate bitset elements from. */ +static struct obstack ebitset_obstack; +static int ebitset_obstack_init = 0; +static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */ + +static void ebitset_elts_grow PARAMS ((bitset, unsigned int)); +static ebitset_elt *ebitset_elt_alloc PARAMS ((void)); +static ebitset_elt *ebitset_elt_calloc PARAMS ((void)); +static void ebitset_elt_add PARAMS ((bitset, ebitset_elt *, unsigned int)); +static void ebitset_elt_remove PARAMS ((bitset, unsigned int)); +static void ebitset_elt_free PARAMS ((ebitset_elt *)); +static ebitset_elt *ebitset_elt_find PARAMS ((bitset, bitset_windex, + enum ebitset_find_mode)); +static ebitset_elt *ebitset_elt_last PARAMS ((bitset)); +static int ebitset_elt_zero_p PARAMS ((ebitset_elt *)); + +static int ebitset_weed PARAMS ((bitset)); +static void ebitset_zero PARAMS((bitset)); +static int ebitset_equal_p PARAMS((bitset, bitset)); +static void ebitset_copy PARAMS((bitset, bitset)); +static int ebitset_copy_compare PARAMS((bitset, bitset)); +static void ebitset_set PARAMS((bitset, bitset_bindex)); +static void ebitset_reset PARAMS((bitset, bitset_bindex)); +static int ebitset_test PARAMS((bitset, bitset_bindex)); +static int ebitset_size PARAMS((bitset)); +static int ebitset_op1 PARAMS((bitset, enum bitset_ops)); +static int ebitset_op2 PARAMS((bitset, bitset, enum bitset_ops)); +static int ebitset_op3 PARAMS((bitset, bitset, bitset, enum bitset_ops)); +static int ebitset_op4 PARAMS((bitset, bitset, bitset, bitset, + enum bitset_ops)); +static int ebitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static int ebitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static void ebitset_free PARAMS((bitset)); + + +#define EBITSET_ELTS(BSET) ((BSET)->u.e.elts) +#define EBITSET_SIZE(BSET) ((BSET)->u.e.size) + +#define EBITSET_NEXT(ELT) ((ELT)->u.next) +#define EBITSET_WORDS(ELT) ((ELT)->u.words) + +/* Disable bitset cache and mark BSET as being zero. */ +#define EBITSET_ZERO_SET(BSET) ((BSET)->cindex = BITSET_INDEX_MAX, \ + (BSET)->cdata = 0) + +#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->cindex = BITSET_INDEX_MAX) + +/* Disable bitset cache and mark BSET as being possibly non-zero. */ +#define EBITSET_NONZERO_SET(BSET) \ + (EBITSET_CACHE_DISABLE (BSET), (BSET)->cdata = (bitset_word *)~0) + +/* A conservative estimate of whether the bitset is zero. + This is non-zero only if we know for sure that the bitset is zero. */ +#define EBITSET_ZERO_P(BSET) ((BSET)->cdata == 0) + +/* Enable cache to point to element with table index EINDEX. + The element must exist. */ +#define EBITSET_CACHE_SET(BSET, EINDEX) \ + ((BSET)->cindex = (EINDEX) * EBITSET_ELT_WORDS, \ + (BSET)->cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX])) + + +/* Grow the expandable table for BSET by SIZE elements. */ +static void +ebitset_elts_grow (bset, size) + bitset bset; + unsigned int size; +{ + unsigned int oldsize; + unsigned int newsize; + + oldsize = EBITSET_SIZE (bset); + newsize = oldsize + size; + + EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset), + newsize * sizeof (ebitset_elt *)); + EBITSET_SIZE (bset) = newsize; + + memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *)); +} + + +/* Allocate a ebitset element. The bits are not cleared. */ +static inline ebitset_elt * +ebitset_elt_alloc () +{ + ebitset_elt *elt; + + if (ebitset_free_list != 0) + { + elt = ebitset_free_list; + ebitset_free_list = EBITSET_NEXT (elt); + } + else + { + /* We can't use gcc_obstack_init to initialize the obstack since + print-rtl.c now calls bitset functions, and bitset is linked + into the gen* functions. */ + if (!ebitset_obstack_init) + { + ebitset_obstack_init = 1; + + /* Let particular systems override the size of a chunk. */ +#ifndef OBSTACK_CHUNK_SIZE +#define OBSTACK_CHUNK_SIZE 0 +#endif + /* Let them override the alloc and free routines too. */ +#ifndef OBSTACK_CHUNK_ALLOC +#define OBSTACK_CHUNK_ALLOC xmalloc +#endif +#ifndef OBSTACK_CHUNK_FREE +#define OBSTACK_CHUNK_FREE free +#endif + +#if !defined(__GNUC__) || (__GNUC__ < 2) +#define __alignof__(type) 0 +#endif + + obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE, + __alignof__ (ebitset_elt), + (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC, + (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE); + } + + /* Perhaps we should add a number of new elements to the free + list. */ + elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack, + sizeof (ebitset_elt)); + } + + return elt; +} + + +/* Allocate a ebitset element. The bits are not cleared. */ +static inline ebitset_elt * +ebitset_elt_calloc () +{ + ebitset_elt *elt; + + elt = ebitset_elt_alloc (); + memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt))); + return elt; +} + + +static inline void +ebitset_elt_free (elt) + ebitset_elt *elt; +{ + EBITSET_NEXT (elt) = ebitset_free_list; + ebitset_free_list = elt; +} + + +/* Remove element with index EINDEX from bitset BSET. */ +static inline void +ebitset_elt_remove (bset, eindex) + bitset bset; + unsigned int eindex; +{ + ebitset_elts *elts; + ebitset_elt *elt; + + elts = EBITSET_ELTS (bset); + + elt = elts[eindex]; + + elts[eindex] = 0; + ebitset_elt_free (elt); +} + + +/* Add ELT into elts at index EINDEX of bitset BSET. */ +static inline void +ebitset_elt_add (bset, elt, eindex) + bitset bset; + ebitset_elt *elt; + unsigned int eindex; +{ + ebitset_elts *elts; + + elts = EBITSET_ELTS (bset); + /* Assume that the elts entry not allocated. */ + elts[eindex] = elt; +} + + +/* Return nonzero if all bits in an element are zero. */ +static inline int +ebitset_elt_zero_p (elt) + ebitset_elt *elt; +{ + int i; + + for (i = 0; i < EBITSET_ELT_WORDS; i++) + if (EBITSET_WORDS (elt)[i]) + return 0; + + return 1; +} + + +static ebitset_elt * +ebitset_elt_find (bset, index, mode) + bitset bset; + bitset_windex index; + enum ebitset_find_mode mode; +{ + ebitset_elt *elt; + bitset_windex size; + unsigned int eindex; + ebitset_elts *elts; + + eindex = index / EBITSET_ELT_WORDS; + + elts = EBITSET_ELTS (bset); + size = EBITSET_SIZE (bset); + + if (eindex < size) + { + ebitset_elt *elt; + + if ((elt = elts[eindex])) + { + if (EBITSET_WORDS (elt) == bset->cdata) + return elt; + + EBITSET_CACHE_SET (bset, eindex); + return elt; + } + } + + /* The element could not be found. */ + + switch (mode) + { + case EBITSET_FIND: + return 0; + + case EBITSET_CREATE: + if (eindex >= size) + { + unsigned int extra; + + extra = eindex - size + 1; + + /* We need to expand the table by EXTRA elements. It may be + better with large bitsets to grow the number of + elements by some fraction of the current size otherwise + we can spend a lot of time slowly increasing the size of the + bitset. */ + if (extra < EBITSET_GROW_SIZE) + extra = EBITSET_GROW_SIZE; + + ebitset_elts_grow (bset, extra); + } + + /* Create a new element. */ + elt = ebitset_elt_calloc (); + ebitset_elt_add (bset, elt, eindex); + EBITSET_CACHE_SET (bset, eindex); + return elt; + + case EBITSET_SUBST: + return &ebitset_zero_elts[0]; + + default: + abort (); + } +} + + +static inline ebitset_elt * +ebitset_elt_last (bset) + bitset bset; +{ + ebitset_elts *elts; + + elts = EBITSET_ELTS (bset); + + /* Assume that have at least one element in elts. */ + return elts[EBITSET_SIZE (bset) - 1]; +} + + +/* Weed out the zero elements from the elts. */ +static inline int +ebitset_weed (bset) + bitset bset; +{ + ebitset_elts *elts; + bitset_windex j; + int count; + + if (EBITSET_ZERO_P (bset)) + return 0; + + elts = EBITSET_ELTS (bset); + count = 0; + for (j = 0; j < EBITSET_SIZE (bset); j++) + { + ebitset_elt *elt = elts[j]; + + if (elt) + { + if (elt && ebitset_elt_zero_p (elt)) + { + ebitset_elt_remove (bset, j); + count++; + } + } + else + count++; + } + + count = j - count; + if (!count) + { + /* All the bits are zero. We could shrink the elts. + For now just mark BSET as known to be zero. */ + EBITSET_ZERO_SET (bset); + } + else + EBITSET_NONZERO_SET (bset); + + return count; +} + + +/* Set all bits in the bitset to zero. */ +static inline void +ebitset_zero (bset) + bitset bset; +{ + ebitset_elts *elts; + bitset_windex j; + + if (EBITSET_ZERO_P (bset)) + return; + + elts = EBITSET_ELTS (bset); + for (j = 0; j < EBITSET_SIZE (bset); j++) + { + ebitset_elt *elt = elts[j]; + + if (elt) + ebitset_elt_remove (bset, j); + } + + /* All the bits are zero. We could shrink the elts. + For now just mark BSET as known to be zero. */ + EBITSET_ZERO_SET (bset); +} + + +static inline int +ebitset_equal_p (dst, src) + bitset dst; + bitset src; +{ + ebitset_elts *selts; + ebitset_elts *delts; + bitset_windex j; + + if (src == dst) + return 1; + + ebitset_weed (dst); + ebitset_weed (src); + + if (EBITSET_SIZE (src) != EBITSET_SIZE (dst)) + return 0; + + selts = EBITSET_ELTS (src); + delts = EBITSET_ELTS (dst); + + for (j = 0; j < EBITSET_SIZE (src); j++) + { + unsigned int i; + ebitset_elt *selt = selts[j]; + ebitset_elt *delt = delts[j]; + + if (! selt && ! delt) + continue; + if ((selt && ! delt) || (!selt && delt)) + return 0; + + for (i = 0; i < EBITSET_ELT_WORDS; i++) + if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i]) + return 0; + } + return 1; +} + + +/* Copy bits from bitset SRC to bitset DST. */ +static inline void +ebitset_copy (dst, src) + bitset dst; + bitset src; +{ + ebitset_elts *selts; + ebitset_elts *delts; + bitset_windex j; + + if (src == dst) + return; + + ebitset_zero (dst); + + if (EBITSET_SIZE (dst) < EBITSET_SIZE (src)) + ebitset_elts_grow (dst, EBITSET_SIZE (src) - EBITSET_SIZE (dst)); + + selts = EBITSET_ELTS (src); + delts = EBITSET_ELTS (dst); + for (j = 0; j < EBITSET_SIZE (src); j++) + { + ebitset_elt *selt = selts[j]; + + if (selt) + { + ebitset_elt *tmp; + + tmp = ebitset_elt_alloc (); + delts[j] = tmp; + memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt), + sizeof (EBITSET_WORDS (selt))); + } + } + EBITSET_NONZERO_SET (dst); +} + + +/* Copy bits from bitset SRC to bitset DST. Return non-zero if + bitsets different. */ +static inline int +ebitset_copy_compare (dst, src) + bitset dst; + bitset src; +{ + if (src == dst) + return 0; + + if (EBITSET_ZERO_P (dst)) + { + ebitset_copy (dst, src); + return ! EBITSET_ZERO_P (src); + } + + if (ebitset_equal_p (dst, src)) + return 0; + + ebitset_copy (dst, src); + return 1; +} + + +/* Return size in bits of bitset SRC. */ +static int +ebitset_size (src) + bitset src; +{ + /* Return current size of bitset in bits. */ + return EBITSET_SIZE (src) * EBITSET_ELT_BITS; +} + + +/* Set bit BITNO in bitset DST. */ +static void +ebitset_set (dst, bitno) + bitset dst; + bitset_bindex bitno; +{ + bitset_windex index = bitno / BITSET_WORD_BITS; + + ebitset_elt_find (dst, index, EBITSET_CREATE); + + dst->cdata[index - dst->cindex] |= (1 << (bitno % BITSET_WORD_BITS)); +} + + +/* Reset bit BITNO in bitset DST. */ +static void +ebitset_reset (dst, bitno) + bitset dst; + bitset_bindex bitno; +{ + bitset_windex index = bitno / BITSET_WORD_BITS; + + if (!ebitset_elt_find (dst, index, EBITSET_FIND)) + return; + + dst->cdata[index - dst->cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); + + /* If all the data is zero, perhaps we should remove it now... + However, there could be a good chance that the element will be needed + again soon. */ +} + + +/* Test bit BITNO in bitset SRC. */ +static int +ebitset_test (src, bitno) + bitset src; + bitset_bindex bitno; +{ + bitset_windex index = bitno / BITSET_WORD_BITS; + + if (!ebitset_elt_find (src, index, EBITSET_FIND)) + return 0; + + return (src->cdata[index - src->cindex] >> (bitno % BITSET_WORD_BITS)) & 1; +} + + +static void +ebitset_free (bset) + bitset bset; +{ + ebitset_zero (bset); + free (EBITSET_ELTS (bset)); +} + + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ +static int +ebitset_reverse_list (bset, list, num, next) + bitset bset; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex n_bits; + bitset_bindex bitno; + bitset_bindex rbitno; + unsigned int bitcnt; + bitset_bindex bitoff; + bitset_windex index; + unsigned int eindex; + bitset_windex windex; + bitset_bindex count; + bitset_windex size; + bitset_word word; + ebitset_elts *elts; + + if (EBITSET_ZERO_P (bset)) + return 0; + + size = EBITSET_SIZE (bset); + n_bits = size * EBITSET_ELT_BITS; + rbitno = *next; + + if (rbitno >= n_bits) + return 0; + + elts = EBITSET_ELTS (bset); + + bitno = n_bits - (rbitno + 1); + + index = bitno / BITSET_WORD_BITS; + eindex = bitno / EBITSET_ELT_BITS; + windex = index - eindex * EBITSET_ELT_WORDS; + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + count = 0; + bitcnt = bitno % BITSET_WORD_BITS; + bitoff = index * BITSET_WORD_BITS; + + for (; eindex != ~0U; eindex--) + { + ebitset_elt *elt; + bitset_word *srcp; + + elt = elts[eindex]; + if (!elt) + continue; + + srcp = EBITSET_WORDS (elt); + + for (; windex != ~0U; windex--, bitoff -= BITSET_WORD_BITS, + bitcnt = BITSET_WORD_BITS - 1) + { + word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); + + for (; word; bitcnt--) + { + if (word & BITSET_MSB) + { + list[count++] = bitoff + bitcnt; + if (count >= num) + { + *next = n_bits - (bitoff + bitcnt); + return count; + } + } + word <<= 1; + } + } + + windex = EBITSET_ELT_WORDS; + } + + *next = n_bits - (bitoff + 1); + return count; +} + + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ +static int +ebitset_list (bset, list, num, next) + bitset bset; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_windex index; + unsigned int eindex; + bitset_bindex count; + bitset_windex size; + ebitset_elt *elt; + bitset_word word; + ebitset_elts *elts; + + if (EBITSET_ZERO_P (bset)) + return 0; + + bitno = *next; + count = 0; + + elts = EBITSET_ELTS (bset); + size = EBITSET_SIZE (bset); + eindex = bitno / EBITSET_ELT_BITS; + + if (bitno % EBITSET_ELT_BITS) + { + /* We need to start within an element. This is not very common. */ + + elt = elts[eindex]; + if (elt) + { + bitset_windex windex; + bitset_word *srcp = EBITSET_WORDS (elt); + + index = bitno / BITSET_WORD_BITS; + windex = eindex / EBITSET_ELT_WORDS; + + for (; (index - windex) < EBITSET_ELT_WORDS; index++) + { + word = srcp[index - windex] >> (bitno % BITSET_WORD_BITS); + + for (; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + bitno = (index + 1) * BITSET_WORD_BITS; + } + } + + /* Skip to next element. */ + eindex++; + } + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + for (; eindex < size; eindex++) + { + int i; + ebitset_elt *elt; + bitset_word *srcp; + + elt = elts[eindex]; + if (!elt) + continue; + + srcp = EBITSET_WORDS (elt); + index = eindex * EBITSET_ELT_WORDS; + + if ((count + EBITSET_ELT_BITS) < num) + { + /* The coast is clear, plant boot! */ + + for (i = 0; i < EBITSET_ELT_WORDS; i++, index++) + { + bitno = index * BITSET_WORD_BITS; + + word = srcp[i]; + if (word) + { + if (! (word & 0xffff)) + { + word >>= 16; + bitno += 16; + } + if (! (word & 0xff)) + { + word >>= 8; + bitno += 8; + } + for (; word; bitno++) + { + if (word & 1) + list[count++] = bitno; + word >>= 1; + } + } + } + } + else + { + /* Tread more carefully since we need to check + if array overflows. */ + + for (i = 0; i < EBITSET_ELT_WORDS; i++, index++) + { + bitno = index * BITSET_WORD_BITS; + + for (word = srcp[i]; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + } + } + } + + *next = bitno; + return count; +} + + +static int +ebitset_op1 (dst, op) + bitset dst; + enum bitset_ops op; +{ + bitset_windex j; + ebitset_elt *elt; + + switch (op) + { + case BITSET_ZERO: + ebitset_zero (dst); + return 1; + + case BITSET_ONES: + for (j = 0; j < EBITSET_SIZE (dst); j++) + { + /* Create new elements if they cannot be found. Perhaps + we should just add pointers to a ones element. */ + elt = ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); + memset (EBITSET_WORDS (elt), ~0, sizeof (EBITSET_WORDS (elt))); + } + break; + + case BITSET_EMPTY_P: + return ! ebitset_weed (dst); + + default: + abort (); + } + + EBITSET_NONZERO_SET (dst); + return 1; +} + + +static int +ebitset_op2 (dst, src, op) + bitset dst; + bitset src; + enum bitset_ops op; +{ + ebitset_elt *selt; + ebitset_elt *delt; + unsigned int i; + bitset_windex j; + + switch (op) + { + case BITSET_COPY: + ebitset_copy (dst, src); + break; + + case BITSET_NOT: + for (j = 0; j < EBITSET_SIZE (src); j++) + { + /* Create new elements for dst if they cannot be found + or substitute zero elements if src elements not found. */ + selt = ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST); + delt = ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); + + for (i = 0; i < EBITSET_ELT_WORDS; i++) + EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i]; + } + break; + + case BITSET_EQUAL_P: + return ebitset_equal_p (dst, src); + + /* Return 1 if DST == DST | SRC. */ + case BITSET_SUBSET_P: + { + ebitset_elts *selts; + ebitset_elts *delts; + bitset_windex ssize; + bitset_windex dsize; + + selts = EBITSET_ELTS (src); + delts = EBITSET_ELTS (dst); + + ssize = EBITSET_SIZE (src); + dsize = EBITSET_SIZE (dst); + + for (j = 0; j < ssize; j++) + { + ebitset_elt *selt; + ebitset_elt *delt; + + selt = j < ssize ? selts[j] : 0; + delt = j < dsize ? delts[j] : 0; + + if (! selt && ! delt) + continue; + + if (!selt) + selt = &ebitset_zero_elts[0]; + if (!delt) + delt = &ebitset_zero_elts[0]; + + for (i = 0; i < EBITSET_ELT_WORDS; i++) + if (EBITSET_WORDS (delt)[i] + != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i])) + return 0; + } + return 1; + } + break; + + default: + abort (); + } + + EBITSET_NONZERO_SET (dst); + return 1; +} + + +static int +ebitset_op3 (dst, src1, src2, op) + bitset dst; + bitset src1; + bitset src2; + enum bitset_ops op; +{ + bitset_windex ssize1; + bitset_windex ssize2; + bitset_windex dsize; + bitset_windex size; + ebitset_elts *selts1; + ebitset_elts *selts2; + ebitset_elts *delts; + bitset_word *srcp1; + bitset_word *srcp2; + bitset_word *dstp; + int changed = 0; + unsigned int i; + bitset_windex j; + + /* Fast track common, simple cases. */ + if (EBITSET_ZERO_P (src2)) + { + if (op == BITSET_AND) + { + ebitset_weed (dst); + changed = EBITSET_ZERO_P (dst); + ebitset_zero (dst); + return changed; + } + else if (op == BITSET_ANDN || op == BITSET_OR || op == BITSET_XOR) + { + return ebitset_copy_compare (dst, src1); + } + } + else if (EBITSET_ZERO_P (src1)) + { + if (op == BITSET_AND || op == BITSET_ANDN) + { + ebitset_weed (dst); + changed = EBITSET_ZERO_P (dst); + ebitset_zero (dst); + return changed; + } + else if (op == BITSET_OR || op == BITSET_XOR) + { + return ebitset_copy_compare (dst, src2); + } + } + + ssize1 = EBITSET_SIZE (src1); + ssize2 = EBITSET_SIZE (src2); + dsize = EBITSET_SIZE (dst); + size = ssize1; + if (size < ssize2) + size = ssize2; + + if (size > dsize) + ebitset_elts_grow (dst, size - dsize); + + selts1 = EBITSET_ELTS (src1); + selts2 = EBITSET_ELTS (src2); + delts = EBITSET_ELTS (dst); + + for (j = 0; j < size; j++) + { + ebitset_elt *selt1; + ebitset_elt *selt2; + ebitset_elt *delt; + + selt1 = j < ssize1 ? selts1[j] : 0; + selt2 = j < ssize2 ? selts2[j] : 0; + delt = j < dsize ? delts[j] : 0; + + if (! selt1 && ! selt2) + { + if (delt) + { + changed = 1; + ebitset_elt_remove (dst, j); + } + continue; + } + + if (!selt1) + selt1 = &ebitset_zero_elts[0]; + if (!selt2) + selt2 = &ebitset_zero_elts[0]; + if (!delt) + delt = ebitset_elt_calloc (); + else + delts[j] = 0; + + srcp1 = EBITSET_WORDS (selt1); + srcp2 = EBITSET_WORDS (selt2); + dstp = EBITSET_WORDS (delt); + switch (op) + { + case BITSET_OR: + for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ | *srcp2++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_AND: + for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ & *srcp2++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_XOR: + for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ ^ *srcp2++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_ANDN: + for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ & ~(*srcp2++); + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_ORN: + for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ | ~(*srcp2++); + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + default: + abort (); + } + + if (! ebitset_elt_zero_p (delt)) + { + ebitset_elt_add (dst, delt, j); + } + else + { + ebitset_elt_free (delt); + } + } + + /* If we have elements of DST left over, free them all. */ + for (; j < dsize; j++) + { + ebitset_elt *delt; + + changed = 1; + + delt = delts[j]; + + if (delt) + ebitset_elt_remove (dst, j); + } + + EBITSET_NONZERO_SET (dst); + return changed; +} + + +static int +ebitset_op4 (dst, src1, src2, src3, op) + bitset dst; + bitset src1; + bitset src2; + bitset src3; + enum bitset_ops op; +{ + int changed = 0; + bitset tmp; + + tmp = bitset_create (BITSET_LIST, 0); + + switch (op) + { + case BITSET_OR_AND: + bitset_or (tmp, src1, src2); + changed = bitset_and (dst, src3, tmp); + break; + + case BITSET_AND_OR: + bitset_and (tmp, src1, src2); + changed = bitset_or (dst, src3, tmp); + break; + + case BITSET_ANDN_OR: + bitset_andn (tmp, src1, src2); + changed = bitset_or (dst, src3, tmp); + break; + + default: + abort (); + } + + bitset_free (tmp); + EBITSET_NONZERO_SET (dst); + return changed; +} + + +/* Vector of operations for linked-list bitsets. */ +struct bitset_ops_struct ebitset_ops = + { + ebitset_set, + ebitset_reset, + ebitset_test, + ebitset_size, + ebitset_op1, + ebitset_op2, + ebitset_op3, + ebitset_op4, + ebitset_list, + ebitset_reverse_list, + ebitset_free, + BITSET_TABLE + }; + + +/* Return size of initial structure. */ +int +ebitset_bytes (n_bits) + bitset_bindex n_bits ATTRIBUTE_UNUSED; +{ + return sizeof (struct bitset_struct); +} + + +/* Initialize a bitset. */ + +bitset +ebitset_init (bset, n_bits) + bitset bset; + bitset_bindex n_bits; +{ + unsigned int size; + + bset->ops = &ebitset_ops; + + bset->csize = EBITSET_ELT_WORDS; + + EBITSET_ZERO_SET (bset); + + size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS + : EBITSET_INITIAL_SIZE; + + EBITSET_SIZE (bset) = 0; + EBITSET_ELTS (bset) = 0; + ebitset_elts_grow (bset, size); + + return bset; +} + + +void +ebitset_release_memory () +{ + ebitset_free_list = 0; + if (ebitset_obstack_init) + { + ebitset_obstack_init = 0; + obstack_free (&ebitset_obstack, NULL); + } +} diff --git a/lib/ebitset.h b/lib/ebitset.h new file mode 100644 index 00000000..5b481dbf --- /dev/null +++ b/lib/ebitset.h @@ -0,0 +1,58 @@ +/* Functions to support ebitsets. + 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. */ + +#ifndef _EBITSET_H +#define _EBITSET_H + +#include "bitset-int.h" + +/* Number of words to use for each element. */ +#ifndef EBITSET_ELT_WORDS +#define EBITSET_ELT_WORDS 2 +#endif + +/* Number of bits stored in each element. */ +#define EBITSET_ELT_BITS \ + ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS)) + +/* Ebitset element. We use an array of bits. */ +typedef struct ebitset_elt_struct +{ + union + { + bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */ + struct ebitset_elt_struct *next; + } u; +} ebitset_elt; + + +typedef ebitset_elt *ebitset_elts; + +/* Head of ebitset linked list. */ +typedef struct ebitset_struct +{ + unsigned int size; /* Number of elements. */ + ebitset_elts *elts; /* Expanding array of pointers to elements. */ +} *ebitset; + + +extern int ebitset_bytes PARAMS ((bitset_bindex)); + +extern void ebitset_release_memory PARAMS ((void)); + +#endif diff --git a/lib/lbitset.c b/lib/lbitset.c new file mode 100644 index 00000000..e400df3d --- /dev/null +++ b/lib/lbitset.c @@ -0,0 +1,1321 @@ +/* Functions to support link list 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 "bitset.h" +#include "obstack.h" +#include + +# if WITH_DMALLOC +# define DMALLOC_FUNC_CHECK +# include +# endif /* WITH_DMALLOC */ + +/* This file implements linked-list bitsets. These bitsets can be of + arbitrary length and are more efficient than arrays of bits for + large sparse sets. + + Usually if all the bits in an element are zero we remove the element + from the list. However, a side effect of the bit caching is that we + do not always notice when an element becomes zero. Hence the + lbitset_weed function which removes zero elements. */ + +enum lbitset_find_mode {LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST}; + +static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */ + +/* Obstack to allocate bitset elements from. */ +static struct obstack lbitset_obstack; +static int lbitset_obstack_init = 0; +static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */ + +static lbitset_elt *lbitset_elt_alloc PARAMS ((void)); +static lbitset_elt *lbitset_elt_calloc PARAMS ((void)); +static void lbitset_elt_link PARAMS ((bitset, lbitset_elt *)); +static void lbitset_elt_unlink PARAMS ((bitset, lbitset_elt *)); +static void lbitset_elt_free PARAMS ((lbitset_elt *)); +static lbitset_elt *lbitset_elt_find PARAMS ((bitset, bitset_windex, + enum lbitset_find_mode)); +static int lbitset_elt_zero_p PARAMS ((lbitset_elt *)); + +static void lbitset_prune PARAMS ((bitset, lbitset_elt *)); +static void lbitset_weed PARAMS ((bitset)); +static void lbitset_zero PARAMS((bitset)); +static int lbitset_equal_p PARAMS((bitset, bitset)); +static void lbitset_copy PARAMS((bitset, bitset)); +static int lbitset_copy_compare PARAMS((bitset, bitset)); +static void lbitset_set PARAMS((bitset, bitset_bindex)); +static void lbitset_reset PARAMS((bitset, bitset_bindex)); +static int lbitset_test PARAMS((bitset, bitset_bindex)); +static int lbitset_size PARAMS((bitset)); +static int lbitset_op1 PARAMS((bitset, enum bitset_ops)); +static int lbitset_op2 PARAMS((bitset, bitset, enum bitset_ops)); +static int lbitset_op3 PARAMS((bitset, bitset, bitset, enum bitset_ops)); +static int lbitset_op4 PARAMS((bitset, bitset, bitset, bitset, + enum bitset_ops)); +static int lbitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static int lbitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static void lbitset_free PARAMS((bitset)); + + +#define LBITSET_CURRENT1(X) (lbitset_elt *)((char *)(X) + ((char *)&(((lbitset_elt *)(X))->next) - (char *)&(((lbitset_elt *)(X))->words))) + +#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->cdata) + +#define LBITSET_HEAD(X) ((X)->u.l.head) +#define LBITSET_TAIL(X) ((X)->u.l.tail) + +/* Allocate a lbitset element. The bits are not cleared. */ +static inline lbitset_elt * +lbitset_elt_alloc () +{ + lbitset_elt *elt; + + if (lbitset_free_list != 0) + { + elt = lbitset_free_list; + lbitset_free_list = elt->next; + } + else + { + /* We can't use gcc_obstack_init to initialize the obstack since + print-rtl.c now calls bitset functions, and bitset is linked + into the gen* functions. */ + if (!lbitset_obstack_init) + { + lbitset_obstack_init = 1; + + /* Let particular systems override the size of a chunk. */ +#ifndef OBSTACK_CHUNK_SIZE +#define OBSTACK_CHUNK_SIZE 0 +#endif + /* Let them override the alloc and free routines too. */ +#ifndef OBSTACK_CHUNK_ALLOC +#define OBSTACK_CHUNK_ALLOC xmalloc +#endif +#ifndef OBSTACK_CHUNK_FREE +#define OBSTACK_CHUNK_FREE free +#endif + +#if !defined(__GNUC__) || (__GNUC__ < 2) +#define __alignof__(type) 0 +#endif + + obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE, + __alignof__ (lbitset_elt), + (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC, + (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE); + } + + /* Perhaps we should add a number of new elements to the free + list. */ + elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack, + sizeof (lbitset_elt)); + } + + return elt; +} + + +/* Allocate a lbitset element. The bits are not cleared. */ +static inline lbitset_elt * +lbitset_elt_calloc () +{ + lbitset_elt *elt; + + elt = lbitset_elt_alloc (); + memset (elt->words, 0, sizeof (elt->words)); + return elt; +} + + +static inline void +lbitset_elt_free (elt) + lbitset_elt *elt; +{ + elt->next = lbitset_free_list; + lbitset_free_list = elt; +} + + +/* Unlink element ELT from bitset BSET. */ +static inline void +lbitset_elt_unlink (bset, elt) + bitset bset; + lbitset_elt *elt; +{ + lbitset_elt *next = elt->next; + lbitset_elt *prev = elt->prev; + + if (prev) + prev->next = next; + + if (next) + next->prev = prev; + + if (LBITSET_HEAD (bset) == elt) + LBITSET_HEAD (bset) = next; + if (LBITSET_TAIL (bset) == elt) + LBITSET_TAIL (bset) = prev; + + /* Update cache pointer. Since the first thing we try is to insert + before current, make current the next entry in preference to the + previous. */ + if (LBITSET_CURRENT (bset) == elt) + { + if (next) + { + bset->cdata = next->words; + bset->cindex = next->index; + } + else if (prev) + { + bset->cdata = prev->words; + bset->cindex = prev->index; + } + else + { + bset->csize = 0; + bset->cdata = 0; + } + } + + lbitset_elt_free (elt); +} + + +/* Cut the chain of bitset BSET before element ELT and free the + elements. */ +static inline void +lbitset_prune (bset, elt) + bitset bset; + lbitset_elt *elt; +{ + lbitset_elt *next; + + if (!elt) + return; + + if (elt->prev) + { + LBITSET_TAIL (bset) = elt->prev; + bset->cdata = elt->prev->words; + bset->cindex = elt->prev->index; + elt->prev->next = 0; + } + else + { + LBITSET_HEAD (bset) = 0; + LBITSET_TAIL (bset) = 0; + bset->cdata = 0; + bset->csize = 0; + } + + for (; elt; elt = next) + { + next = elt->next; + lbitset_elt_free (elt); + } +} + + +/* Return nonzero if all bits in an element are zero. */ +static inline int +lbitset_elt_zero_p (elt) + lbitset_elt *elt; +{ + int i; + + for (i = 0; i < LBITSET_ELT_WORDS; i++) + if (elt->words[i]) + return 0; + + return 1; +} + + +/* Link the bitset element into the current bitset linked list. */ +static inline void +lbitset_elt_link (bset, elt) + bitset bset; + lbitset_elt *elt; +{ + bitset_windex index = elt->index; + lbitset_elt *ptr; + lbitset_elt *current; + + if (bset->csize) + current = LBITSET_CURRENT (bset); + else + current = LBITSET_HEAD (bset); + + /* If this is the first and only element, add it in. */ + if (LBITSET_HEAD (bset) == 0) + { + elt->next = elt->prev = 0; + LBITSET_HEAD (bset) = elt; + LBITSET_TAIL (bset) = elt; + } + + /* If this index is less than that of the current element, it goes + somewhere before the current element. */ + else if (index < bset->cindex) + { + for (ptr = current; + ptr->prev && ptr->prev->index > index; + ptr = ptr->prev) + continue; + + if (ptr->prev) + ptr->prev->next = elt; + else + LBITSET_HEAD (bset) = elt; + + elt->prev = ptr->prev; + elt->next = ptr; + ptr->prev = elt; + } + + /* Otherwise, it must go somewhere after the current element. */ + else + { + for (ptr = current; + ptr->next && ptr->next->index < index; + ptr = ptr->next) + continue; + + if (ptr->next) + ptr->next->prev = elt; + else + LBITSET_TAIL (bset) = elt; + + elt->next = ptr->next; + elt->prev = ptr; + ptr->next = elt; + } + + /* Set up so this is the first element searched. */ + bset->cindex = index; + bset->csize = LBITSET_ELT_WORDS; + bset->cdata = elt->words; +} + + +static lbitset_elt * +lbitset_elt_find (bset, index, mode) + bitset bset; + bitset_windex index; + enum lbitset_find_mode mode; +{ + lbitset_elt *elt; + lbitset_elt *current; + + if (bset->csize) + { + current = LBITSET_CURRENT (bset); + /* Check if element is the cached element. */ + if ((index - bset->cindex) < bset->csize) + return current; + } + else + { + current = LBITSET_HEAD (bset); + } + + if (current) + { + if (index < bset->cindex) + { + for (elt = current; + elt->prev && elt->index > index; + elt = elt->prev) + continue; + } + else + { + for (elt = current; + elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < index; + elt = elt->next) + continue; + } + + /* `element' is the nearest to the one we want. If it's not the one + we want, the one we want does not exist. */ + if (elt && (index - elt->index) < LBITSET_ELT_WORDS) + { + bset->cindex = elt->index; + bset->csize = LBITSET_ELT_WORDS; + bset->cdata = elt->words; + return elt; + } + } + + switch (mode) + { + case LBITSET_FIND: + return 0; + + case LBITSET_CREATE: + index = (index / (unsigned) LBITSET_ELT_WORDS) * LBITSET_ELT_WORDS; + + elt = lbitset_elt_calloc (); + elt->index = index; + lbitset_elt_link (bset, elt); + return elt; + + case LBITSET_SUBST: + return &lbitset_zero_elts[0]; + + default: + abort (); + } +} + + +/* Weed out the zero elements from the list. */ +static inline void +lbitset_weed (bset) + bitset bset; +{ + lbitset_elt *elt; + lbitset_elt *next; + + for (elt = LBITSET_HEAD (bset); elt; elt = next) + { + next = elt->next; + if (lbitset_elt_zero_p (elt)) + lbitset_elt_unlink (bset, elt); + } +} + + +/* Set all bits in the bitset to zero. */ +static inline void +lbitset_zero (bset) + bitset bset; +{ + lbitset_elt *head; + + head = LBITSET_HEAD (bset); + if (!head) + return; + + /* Clear a bitset by freeing the linked list at the head element. */ + lbitset_prune (bset, head); +} + + +static inline int +lbitset_equal_p (dst, src) + bitset dst; + bitset src; +{ + lbitset_elt *selt; + lbitset_elt *delt; + int j; + + if (src == dst) + return 1; + + lbitset_weed (src); + lbitset_weed (dst); + for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); + selt && delt; selt = selt->next, delt = delt->next) + { + if (selt->index != delt->index) + return 0; + + for (j = 0; j < LBITSET_ELT_WORDS; j++) + if (delt->words[j] != selt->words[j]) + return 0; + } + return ! selt && ! delt; +} + + +/* Copy bits from bitset SRC to bitset DST. */ +static inline void +lbitset_copy (dst, src) + bitset dst; + bitset src; +{ + lbitset_elt *elt; + lbitset_elt *head; + lbitset_elt *prev; + lbitset_elt *tmp; + + if (src == dst) + return; + + lbitset_zero (dst); + + head = LBITSET_HEAD (src); + if (!head) + return; + + prev = 0; + for (elt = head; elt; elt = elt->next) + { + tmp = lbitset_elt_alloc (); + tmp->index = elt->index; + tmp->prev = prev; + tmp->next = 0; + if (prev) + prev->next = tmp; + else + LBITSET_HEAD (dst) = tmp; + prev = tmp; + + memcpy (tmp->words, elt->words, sizeof (elt->words)); + } + LBITSET_TAIL (dst) = tmp; + + dst->csize = LBITSET_ELT_WORDS; + dst->cdata = LBITSET_HEAD (dst)->words; + dst->cindex = LBITSET_HEAD (dst)->index; +} + + +/* Copy bits from bitset SRC to bitset DST. Return non-zero if + bitsets different. */ +static inline int +lbitset_copy_compare (dst, src) + bitset dst; + bitset src; +{ + if (src == dst) + return 0; + + if (! LBITSET_HEAD (dst)) + { + lbitset_copy (dst, src); + return LBITSET_HEAD (src) != 0; + } + + if (lbitset_equal_p (dst, src)) + return 0; + + lbitset_copy (dst, src); + return 1; +} + + +/* Return size in bits of bitset SRC. */ +static int +lbitset_size (src) + bitset src; +{ + lbitset_elt *elt; + + elt = LBITSET_TAIL (src); + if (!elt) + return 0; + + /* Return current size of bitset in bits. */ + return (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS; +} + + +/* Set bit BITNO in bitset DST. */ +static void +lbitset_set (dst, bitno) + bitset dst; + bitset_bindex bitno; +{ + bitset_windex index = bitno / BITSET_WORD_BITS; + + lbitset_elt_find (dst, index, LBITSET_CREATE); + + dst->cdata[index - dst->cindex] |= (1 << (bitno % BITSET_WORD_BITS)); +} + + +/* Reset bit BITNO in bitset DST. */ +static void +lbitset_reset (dst, bitno) + bitset dst; + bitset_bindex bitno; +{ + bitset_windex index = bitno / BITSET_WORD_BITS; + + if (!lbitset_elt_find (dst, index, LBITSET_FIND)) + return; + + dst->cdata[index - dst->cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); + + /* If all the data is zero, perhaps we should unlink it now... */ +} + + +/* Test bit BITNO in bitset SRC. */ +static int +lbitset_test (src, bitno) + bitset src; + bitset_bindex bitno; +{ + bitset_windex index = bitno / BITSET_WORD_BITS; + + if (!lbitset_elt_find (src, index, LBITSET_FIND)) + return 0; + + return (src->cdata[index - src->cindex] >> (bitno % BITSET_WORD_BITS)) & 1; +} + + +static void +lbitset_free (bset) + bitset bset; +{ + lbitset_zero (bset); +} + + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ +static int +lbitset_reverse_list (bset, list, num, next) + bitset bset; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex rbitno; + bitset_bindex bitno; + unsigned int bitcnt; + bitset_bindex bitoff; + bitset_windex index; + bitset_bindex count; + lbitset_elt *elt; + bitset_word word; + bitset_bindex n_bits; + + elt = LBITSET_TAIL (bset); + if (!elt) + return 0; + + n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS; + rbitno = *next; + + if (rbitno >= n_bits) + return 0; + + bitno = n_bits - (rbitno + 1); + + index = bitno / BITSET_WORD_BITS; + + /* Skip back to starting element. */ + for (; elt && elt->index > index; elt = elt->prev) + continue; + + if (!elt) + return 0; + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + count = 0; + bitcnt = bitno % BITSET_WORD_BITS; + bitoff = index * BITSET_WORD_BITS; + + while (elt) + { + bitset_word *srcp = elt->words; + + for (; (index - elt->index) < LBITSET_ELT_WORDS; + index--, bitoff -= BITSET_WORD_BITS, + bitcnt = BITSET_WORD_BITS - 1) + { + word = srcp[index - elt->index] << (BITSET_WORD_BITS - 1 - bitcnt); + + for (; word; bitcnt--) + { + if (word & BITSET_MSB) + { + list[count++] = bitoff + bitcnt; + if (count >= num) + { + *next = n_bits - (bitoff + bitcnt); + return count; + } + } + word <<= 1; + } + } + + elt = elt->prev; + if (elt) + { + index = elt->index + LBITSET_ELT_WORDS - 1; + bitoff = index * BITSET_WORD_BITS; + } + } + + *next = n_bits - (bitoff + 1); + return count; +} + + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ +static int +lbitset_list (bset, list, num, next) + bitset bset; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_windex index; + bitset_bindex count; + lbitset_elt *elt; + lbitset_elt *head; + bitset_word word; + + head = LBITSET_HEAD (bset); + if (!head) + return 0; + + bitno = *next; + count = 0; + + if (!bitno) + { + /* This is the most common case. */ + + /* Start with the first element. */ + elt = head; + index = elt->index; + bitno = index * BITSET_WORD_BITS; + } + else + { + index = bitno / BITSET_WORD_BITS; + + /* Skip to starting element. */ + for (elt = head; + elt && (elt->index + LBITSET_ELT_WORDS - 1) < index; + elt = elt->next) + continue; + + if (!elt) + return 0; + + if (index < elt->index) + { + index = elt->index; + bitno = index * BITSET_WORD_BITS; + } + else + { + bitset_word *srcp = elt->words; + + /* We are starting within an element. */ + + for (; (index - elt->index) < LBITSET_ELT_WORDS; index++) + { + word = srcp[index - elt->index] >> (bitno % BITSET_WORD_BITS); + + for (; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + bitno = (index + 1) * BITSET_WORD_BITS; + } + + elt = elt->next; + if (elt) + { + index = elt->index; + bitno = index * BITSET_WORD_BITS; + } + } + } + + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + while (elt) + { + int i; + bitset_word *srcp = elt->words; + + if ((count + LBITSET_ELT_BITS) < num) + { + /* The coast is clear, plant boot! */ + +#if LBITSET_ELT_WORDS == 2 + word = srcp[0]; + if (word) + { + if (! (word & 0xffff)) + { + word >>= 16; + bitno += 16; + } + if (! (word & 0xff)) + { + word >>= 8; + bitno += 8; + } + for (; word; bitno++) + { + if (word & 1) + list[count++] = bitno; + word >>= 1; + } + } + index++; + bitno = index * BITSET_WORD_BITS; + + word = srcp[1]; + if (word) + { + if (! (word & 0xffff)) + { + word >>= 16; + bitno += 16; + } + for (; word; bitno++) + { + if (word & 1) + list[count++] = bitno; + word >>= 1; + } + } + index++; + bitno = index * BITSET_WORD_BITS; +#else + for (i = 0; i < LBITSET_ELT_WORDS; i++) + { + word = srcp[i]; + if (word) + { + if (! (word & 0xffff)) + { + word >>= 16; + bitno += 16; + } + if (! (word & 0xff)) + { + word >>= 8; + bitno += 8; + } + for (; word; bitno++) + { + if (word & 1) + list[count++] = bitno; + word >>= 1; + } + } + index++; + bitno = index * BITSET_WORD_BITS; + } +#endif + } + else + { + /* Tread more carefully since we need to check + if array overflows. */ + + for (i = 0; i < LBITSET_ELT_WORDS; i++) + { + for (word = srcp[i]; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + index++; + bitno = index * BITSET_WORD_BITS; + } + } + + elt = elt->next; + if (elt) + { + index = elt->index; + bitno = index * BITSET_WORD_BITS; + } + } + + *next = bitno; + return count; +} + + +static int +lbitset_op1 (dst, op) + bitset dst; + enum bitset_ops op; +{ + unsigned int i; + bitset_windex index; + lbitset_elt *elt; + + switch (op) + { + case BITSET_ZERO: + lbitset_zero (dst); + break; + + case BITSET_ONES: + /* This is a decidedly unfriendly operation for a linked list + bitset! */ + elt = LBITSET_TAIL (dst); + /* Ignore empty set. */ + if (!elt) + return 0; + + index = elt->index; + for (i = 0; i < index; i += LBITSET_ELT_WORDS) + { + /* Create new elements if they cannot be found. */ + elt = lbitset_elt_find (dst, i, LBITSET_CREATE); + memset (elt->words, ~0, sizeof (elt->words)); + } + break; + + case BITSET_EMPTY_P: + lbitset_weed (dst); + if (LBITSET_HEAD (dst)) + return 0; + break; + + default: + abort (); + } + + return 1; +} + + +static int +lbitset_op2 (dst, src, op) + bitset dst; + bitset src; + enum bitset_ops op; +{ + lbitset_elt *elt; + lbitset_elt *selt; + lbitset_elt *delt; + unsigned int i; + unsigned int j; + bitset_windex index; + + switch (op) + { + case BITSET_COPY: + lbitset_copy (dst, src); + break; + + case BITSET_NOT: + /* This is another unfriendly operation for a linked list + bitset! */ + elt = LBITSET_TAIL (dst); + /* Ignore empty set. */ + if (!elt) + return 0; + + index = elt->index; + for (i = 0; i < index; i += LBITSET_ELT_WORDS) + { + /* Create new elements for dst if they cannot be found + or substitute zero elements if src elements not found. */ + selt = lbitset_elt_find (dst, i, LBITSET_SUBST); + delt = lbitset_elt_find (dst, i, LBITSET_CREATE); + + for (j = 0; j < LBITSET_ELT_WORDS; j++) + delt->words[j] = ~selt->words[j]; + } + lbitset_weed (dst); + break; + + case BITSET_EQUAL_P: + return lbitset_equal_p (dst, src); + break; + + case BITSET_SUBSET_P: + for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); + selt || delt; selt = selt->next, delt = delt->next) + { + if (!selt) + selt = &lbitset_zero_elts[0]; + else if (!delt) + delt = &lbitset_zero_elts[0]; + else if (selt->index != delt->index) + { + if (selt->index < delt->index) + { + lbitset_zero_elts[2].next = delt; + delt = &lbitset_zero_elts[2]; + } + else + { + lbitset_zero_elts[1].next = selt; + selt = &lbitset_zero_elts[1]; + } + } + + for (j = 0; j < LBITSET_ELT_WORDS; j++) + if (delt->words[j] != (selt->words[j] | delt->words[j])) + return 0; + } + break; + + default: + abort (); + } + + return 1; +} + + +static int +lbitset_op3 (dst, src1, src2, op) + bitset dst; + bitset src1; + bitset src2; + enum bitset_ops op; +{ + lbitset_elt *selt1 = LBITSET_HEAD (src1); + lbitset_elt *selt2 = LBITSET_HEAD (src2); + lbitset_elt *delt = LBITSET_HEAD (dst); + bitset_windex index1; + bitset_windex index2; + bitset_windex index; + lbitset_elt *stmp1; + lbitset_elt *stmp2; + lbitset_elt *dtmp; + bitset_word *srcp1; + bitset_word *srcp2; + bitset_word *dstp; + int changed = 0; + unsigned int i; + + /* Fast track common, simple cases. */ + if (!selt2) + { + if (op == BITSET_AND) + { + lbitset_weed (dst); + changed = ! LBITSET_HEAD (dst); + lbitset_zero (dst); + return changed; + } + else if (op == BITSET_ANDN || op == BITSET_OR || op == BITSET_XOR) + { + return lbitset_copy_compare (dst, src1); + } + } + else if (!selt1) + { + if (op == BITSET_AND || op == BITSET_ANDN) + { + lbitset_weed (dst); + changed = ! LBITSET_HEAD (dst); + lbitset_zero (dst); + return changed; + } + else if (op == BITSET_OR || op == BITSET_XOR) + { + return lbitset_copy_compare (dst, src2); + } + } + + + LBITSET_HEAD (dst) = 0; + dst->csize = 0; + + index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; + index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; + + while (selt1 || selt2) + { + /* Figure out whether we need to substitute zero elements for + missing links. */ + if (index1 == index2) + { + index = index1; + stmp1 = selt1; + stmp2 = selt2; + selt1 = selt1->next; + index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; + selt2 = selt2->next; + index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; + } + else if (index1 < index2) + { + index = index1; + stmp1 = selt1; + stmp2 = &lbitset_zero_elts[0]; + selt1 = selt1->next; + index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; + } + else + { + index = index2; + stmp1 = &lbitset_zero_elts[0]; + stmp2 = selt2; + selt2 = selt2->next; + index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; + } + + /* Find the appropriate element from DST. Begin by discarding + elements that we've skipped. */ + while (delt && delt->index < index) + { + changed = 1; + dtmp = delt; + delt = delt->next; + lbitset_elt_free (dtmp); + } + if (delt && delt->index == index) + { + dtmp = delt; + delt = delt->next; + } + else + dtmp = lbitset_elt_calloc (); + + /* Do the operation, and if any bits are set, link it into the + linked list. */ + srcp1 = stmp1->words; + srcp2 = stmp2->words; + dstp = dtmp->words; + switch (op) + { + case BITSET_OR: + for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ | *srcp2++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_AND: + for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ & *srcp2++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_XOR: + for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ ^ *srcp2++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_ANDN: + for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ & ~(*srcp2++); + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_ORN: + for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ | ~(*srcp2++); + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + default: + abort (); + } + + if (! lbitset_elt_zero_p (dtmp)) + { + dtmp->index = index; + /* Perhaps this could be optimised... */ + lbitset_elt_link (dst, dtmp); + } + else + { + lbitset_elt_free (dtmp); + } + } + + /* If we have elements of DST left over, free them all. */ + if (delt) + { + changed = 1; + lbitset_prune (dst, delt); + } + + return changed; +} + + +static int +lbitset_op4 (dst, src1, src2, src3, op) + bitset dst; + bitset src1; + bitset src2; + bitset src3; + enum bitset_ops op; +{ + int changed = 0; + bitset tmp; + +#ifdef ENABLE_CHECKING + /* Check for compatiblity. */ + if (src1->ops != dst->ops || src2->ops != dst->ops || src3->ops != dst->ops) + abort (); +#endif + + tmp = bitset_create (BITSET_LIST, 0); + + switch (op) + { + case BITSET_OR_AND: + bitset_or (tmp, src1, src2); + changed = bitset_and (dst, src3, tmp); + break; + + case BITSET_AND_OR: + bitset_and (tmp, src1, src2); + changed = bitset_or (dst, src3, tmp); + break; + + case BITSET_ANDN_OR: + bitset_andn (tmp, src1, src2); + changed = bitset_or (dst, src3, tmp); + break; + + default: + abort (); + } + + bitset_free (tmp); + return changed; +} + + +/* Vector of operations for linked-list bitsets. */ +struct bitset_ops_struct lbitset_ops = + { + lbitset_set, + lbitset_reset, + lbitset_test, + lbitset_size, + lbitset_op1, + lbitset_op2, + lbitset_op3, + lbitset_op4, + lbitset_list, + lbitset_reverse_list, + lbitset_free, + BITSET_LIST + }; + + +/* Return size of initial structure. */ +int +lbitset_bytes (n_bits) + bitset_bindex n_bits ATTRIBUTE_UNUSED; +{ + return sizeof (struct bitset_struct); +} + + +/* Initialize a bitset. */ + +bitset +lbitset_init (bset, n_bits) + bitset bset; + bitset_bindex n_bits ATTRIBUTE_UNUSED; +{ + LBITSET_HEAD (bset) = 0; + LBITSET_TAIL (bset) = 0; + + bset->ops = &lbitset_ops; + + bset->cindex = 0; + /* Disable cache until have some elements allocated. + If we have variable length arrays, then we may + need to allocate dummy element. */ + bset->csize = 0; + bset->cdata = 0; + return bset; +} + + +void +lbitset_release_memory () +{ + lbitset_free_list = 0; + if (lbitset_obstack_init) + { + lbitset_obstack_init = 0; + obstack_free (&lbitset_obstack, NULL); + } +} diff --git a/lib/lbitset.h b/lib/lbitset.h new file mode 100644 index 00000000..9af651f1 --- /dev/null +++ b/lib/lbitset.h @@ -0,0 +1,62 @@ +/* Functions to support lbitsets. + 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. */ + +#ifndef _LBITSET_H +#define _LBITSET_H + +#include "bitset-int.h" + +/* Number of words to use for each element. The larger the value the + greater the size of the cache and the shorter the time to find a given bit + but the more memory wasted for sparse bitsets and the longer the time + to search for set bits. */ +#ifndef LBITSET_ELT_WORDS +#define LBITSET_ELT_WORDS 2 +#endif + +typedef bitset_word lbitset_word; +#define LBITSET_WORD_BITS BITSET_WORD_BITS + +/* Number of bits stored in each element. */ +#define LBITSET_ELT_BITS \ + ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS)) + +/* Lbitset element. We use an array of bits for each element. + These are linked together in a doubly-linked list. */ +typedef struct lbitset_elt_struct +{ + struct lbitset_elt_struct *next; /* Next element. */ + struct lbitset_elt_struct *prev; /* Previous element. */ + bitset_windex index; /* bitno / BITSET_WORD_BITS. */ + bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set. */ +} lbitset_elt; + + +/* Head of lbitset linked list. */ +typedef struct lbitset_struct +{ + lbitset_elt *head; /* First element in linked list. */ + lbitset_elt *tail; /* Last element in linked list. */ +} *lbitset; + + +extern int lbitset_bytes PARAMS ((bitset_bindex)); + +extern void lbitset_release_memory PARAMS ((void)); + +#endif diff --git a/lib/sbitset.c b/lib/sbitset.c new file mode 100644 index 00000000..807b71dd --- /dev/null +++ b/lib/sbitset.c @@ -0,0 +1,672 @@ +/* Simple 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 "bitset.h" +#include + +# if WITH_DMALLOC +# define DMALLOC_FUNC_CHECK +# include +# endif /* WITH_DMALLOC */ + +/* This file implements fixed size bitsets stored as an array + of words. Any unused bits in the last word must be zero. */ + +static void sbitset_unused_clear PARAMS((bitset)); + +static int sbitset_small_list PARAMS((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); + +static void sbitset_set PARAMS((bitset, bitset_bindex)); +static void sbitset_reset PARAMS((bitset, bitset_bindex)); +static int sbitset_test PARAMS((bitset, bitset_bindex)); +static int sbitset_size PARAMS((bitset)); +static int sbitset_op1 PARAMS((bitset, enum bitset_ops)); +static int sbitset_op2 PARAMS((bitset, bitset, enum bitset_ops)); +static int sbitset_op3 PARAMS((bitset, bitset, bitset, enum bitset_ops)); +static int sbitset_op4 PARAMS((bitset, bitset, bitset, bitset, + enum bitset_ops)); +static int sbitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static int sbitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); + +#define SBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) +#define SBITSET_WORDS(X) ((X)->u.s.words) +#define SBITSET_N_BITS(X) ((X)->u.s.n_bits) + + +/* Return size in bits of bitset SRC. */ +static int +sbitset_size (src) + bitset src; +{ + return SBITSET_N_BITS (src); +} + + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ +static int +sbitset_small_list (src, list, num, next) + bitset src; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_bindex count; + bitset_windex size; + bitset_word word; + + word = SBITSET_WORDS (src)[0]; + + /* Short circuit common case. */ + if (!word) + return 0; + + size = SBITSET_N_BITS (src); + bitno = *next; + if (bitno >= size) + return 0; + + word >>= bitno; + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + if (num >= BITSET_WORD_BITS) + { + for (count = 0; word; bitno++) + { + if (word & 1) + list[count++] = bitno; + word >>= 1; + } + } + else + { + for (count = 0; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + bitno++; + break; + } + } + word >>= 1; + } + } + + *next = bitno; + return count; +} + + +/* Set bit BITNO in bitset DST. */ +static void +sbitset_set (dst, bitno) + bitset dst ATTRIBUTE_UNUSED; + bitset_bindex bitno ATTRIBUTE_UNUSED; +{ + /* This should never occur for sbitsets. */ + abort (); +} + + +/* Reset bit BITNO in bitset DST. */ +static void +sbitset_reset (dst, bitno) + bitset dst ATTRIBUTE_UNUSED; + bitset_bindex bitno ATTRIBUTE_UNUSED; +{ + /* This should never occur for sbitsets. */ + abort (); +} + + +/* Test bit BITNO in bitset SRC. */ +static int +sbitset_test (src, bitno) + bitset src ATTRIBUTE_UNUSED; + bitset_bindex bitno ATTRIBUTE_UNUSED; +{ + /* This should never occur for sbitsets. */ + abort (); + return 0; +} + + +/* Find list of up to NUM bits set in BSET in reverse order, starting + from and including NEXT and store in array LIST. Return with + actual number of bits found and with *NEXT indicating where search + stopped. */ +static int +sbitset_reverse_list (src, list, num, next) + bitset src; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_bindex rbitno; + bitset_bindex count; + bitset_windex index; + unsigned int bitcnt; + bitset_bindex bitoff; + bitset_word word; + bitset_word *srcp = SBITSET_WORDS (src); + bitset_bindex n_bits = SBITSET_N_BITS (src); + + rbitno = *next; + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + if (rbitno >= n_bits) + return 0; + + count = 0; + + bitno = n_bits - (rbitno + 1); + + index = bitno / BITSET_WORD_BITS; + bitcnt = bitno % BITSET_WORD_BITS; + bitoff = index * BITSET_WORD_BITS; + + for (; index != ~0U; index--, bitoff -= BITSET_WORD_BITS, + bitcnt = BITSET_WORD_BITS - 1) + { + word = srcp[index] << (BITSET_WORD_BITS - 1 - bitcnt); + for (; word; bitcnt--) + { + if (word & BITSET_MSB) + { + list[count++] = bitoff + bitcnt; + if (count >= num) + { + *next = n_bits - (bitoff + bitcnt); + return count; + } + } + word <<= 1; + } + } + + *next = n_bits - (bitoff + 1); + return count; +} + + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ +static int +sbitset_list (src, list, num, next) + bitset src; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_bindex count; + bitset_windex index; + bitset_bindex bitoff; + bitset_windex size = src->csize; + bitset_word *srcp = SBITSET_WORDS (src); + bitset_word word; + + bitno = *next; + + count = 0; + if (! bitno) + { + /* Many bitsets are zero, so make this common case fast. */ + for (index = 0; index < size && ! srcp[index]; index++) + continue; + if (index >= size) + return 0; + + /* If num is 1, we could speed things up with a binary search + of the current word. */ + + bitoff = index * BITSET_WORD_BITS; + } + else + { + if (bitno >= SBITSET_N_BITS (src)) + return 0; + + index = bitno / BITSET_WORD_BITS; + bitno = bitno % BITSET_WORD_BITS; + + if (bitno) + { + /* Handle the case where we start within a word. + Most often, this is executed with large bitsets + with many set bits where we filled the array + on the previous call to this function. */ + + bitoff = index * BITSET_WORD_BITS; + word = srcp[index] >> bitno; + for (bitno = bitoff + bitno; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + index++; + } + bitoff = index * BITSET_WORD_BITS; + } + + for (; index < size; index++, bitoff += BITSET_WORD_BITS) + { + if (! (word = srcp[index])) + continue; + + if ((count + BITSET_WORD_BITS) < num) + { + for (bitno = bitoff; word; bitno++) + { + if (word & 1) + list[count++] = bitno; + word >>= 1; + } + } + else + { + for (bitno = bitoff; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + } + } + + *next = bitoff; + return count; +} + + +/* Ensure that any unused bits within the last word are clear. */ +static inline void +sbitset_unused_clear (dst) + bitset dst; +{ + unsigned int last_bit; + + last_bit = SBITSET_N_BITS (dst) % BITSET_WORD_BITS; + if (last_bit) + SBITSET_WORDS (dst)[dst->csize - 1] &= (bitset_word)((1 << last_bit) - 1); +} + + +static int +sbitset_op1 (dst, op) + bitset dst; + enum bitset_ops op; +{ + unsigned int i; + bitset_word *dstp = SBITSET_WORDS (dst); + unsigned int bytes; + + bytes = sizeof (bitset_word) * dst->csize; + + switch (op) + { + case BITSET_ZERO: + memset (dstp, 0, bytes); + break; + + case BITSET_ONES: + memset (dstp, ~0, bytes); + sbitset_unused_clear (dst); + break; + + case BITSET_EMPTY_P: + for (i = 0; i < dst->csize; i++) + if (dstp[i]) + return 0; + break; + + default: + abort (); + } + + return 1; +} + + +static int +sbitset_op2 (dst, src, op) + bitset dst; + bitset src; + enum bitset_ops op; +{ + unsigned int i; + bitset_word *srcp = SBITSET_WORDS (src); + bitset_word *dstp = SBITSET_WORDS (dst); + bitset_windex size = dst->csize; + +#ifdef ENABLE_CHECKING + /* Check for compatiblity. */ + if (src->ops != dst->ops || SBITSET_N_BITS (src) != SBITSET_N_BITS (dst)) + abort (); +#endif + + switch (op) + { + case BITSET_COPY: + if (srcp == dstp) + break; + memcpy (dstp, srcp, sizeof (bitset_word) * size); + break; + + case BITSET_NOT: + for (i = 0; i < size; i++) + *dstp++ = ~(*srcp++); + sbitset_unused_clear (dst); + break; + + case BITSET_EQUAL_P: + for (i = 0; i < size; i++) + if (*dstp++ != *srcp++) + return 0; + break; + + case BITSET_SUBSET_P: + for (i = 0; i < size; i++, dstp++, srcp++) + { + if (*dstp != (*srcp | *dstp)) + return 0; + } + break; + + default: + abort (); + } + + return 1; +} + + +static int +sbitset_op3 (dst, src1, src2, op) + bitset dst; + bitset src1; + bitset src2; + enum bitset_ops op; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p = SBITSET_WORDS (src1); + bitset_word *src2p = SBITSET_WORDS (src2); + bitset_word *dstp = SBITSET_WORDS (dst); + bitset_windex size = dst->csize; + +#ifdef ENABLE_CHECKING + /* Check for compatiblity. */ + if (src1->ops != dst->ops || SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst) + || src2->ops != dst->ops || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst)) + abort (); +#endif + + switch (op) + { + case BITSET_OR: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ | *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_AND: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ & *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_XOR: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ ^ *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_ANDN: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ & ~(*src2p++); + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_ORN: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ | ~(*src2p++); + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + sbitset_unused_clear (dst); + break; + + default: + abort (); + } + + return changed; +} + + +static int +sbitset_op4 (dst, src1, src2, src3, op) + bitset dst; + bitset src1; + bitset src2; + bitset src3; + enum bitset_ops op; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p = SBITSET_WORDS (src1); + bitset_word *src2p = SBITSET_WORDS (src2); + bitset_word *src3p = SBITSET_WORDS (src3); + bitset_word *dstp = SBITSET_WORDS (dst); + bitset_windex size = dst->csize; + +#ifdef ENABLE_CHECKING + /* Check for compatiblity. */ + if (src1->ops != dst->ops || SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst) + || src2->ops != dst->ops || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst) + || src3->ops != dst->ops || SBITSET_N_BITS (src3) != SBITSET_N_BITS (dst)) + abort (); +#endif + + switch (op) + { + case BITSET_OR_AND: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_AND_OR: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_ANDN_OR: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + default: + abort (); + } + + return changed; +} + + +/* Vector of operations for single word bitsets. */ +struct bitset_ops_struct sbitset_small_ops = + { + sbitset_set, + sbitset_reset, + sbitset_test, + sbitset_size, + sbitset_op1, + sbitset_op2, + sbitset_op3, + sbitset_op4, + sbitset_small_list, + sbitset_reverse_list, + NULL, + BITSET_ARRAY + }; + + +/* Vector of operations for multiple word bitsets. */ +struct bitset_ops_struct sbitset_ops = + { + sbitset_set, + sbitset_reset, + sbitset_test, + sbitset_size, + sbitset_op1, + sbitset_op2, + sbitset_op3, + sbitset_op4, + sbitset_list, + sbitset_reverse_list, + NULL, + BITSET_ARRAY +}; + + +int +sbitset_bytes (n_bits) + bitset_bindex n_bits; +{ + unsigned int bytes, size; + + size = SBITSET_N_WORDS (n_bits); + bytes = size * sizeof (bitset_word); + return sizeof (struct bitset_struct) + bytes - sizeof (bitset_word); +} + + +bitset +sbitset_init (bset, n_bits) + bitset bset; + bitset_bindex n_bits; +{ + bitset_windex size; + + size = SBITSET_N_WORDS (n_bits); + SBITSET_N_BITS (bset) = n_bits; + + /* Use optimized routines if bitset fits within a single word. + There is probably little merit if using caching since + the small bitset will always fit in the cache. */ + if (size == 1) + bset->ops = &sbitset_small_ops; + else + bset->ops = &sbitset_ops; + + bset->cindex = 0; + bset->csize = size; + bset->cdata = SBITSET_WORDS (bset); + return bset; +} diff --git a/lib/sbitset.h b/lib/sbitset.h new file mode 100644 index 00000000..777feea1 --- /dev/null +++ b/lib/sbitset.h @@ -0,0 +1,33 @@ +/* Functions to support sbitsets. + 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. */ + +#ifndef _SBITSET_H +#define _SBITSET_H + +#include "bitset-int.h" + +typedef struct sbitset_struct +{ + unsigned int n_bits; /* Number of bits. */ + bitset_word words[1]; /* The array of bits. */ +} *sbitset; + + +extern int sbitset_bytes PARAMS ((bitset_bindex)); + +#endif diff --git a/src/closure.c b/src/closure.c index e2a59851..a90b8670 100644 --- a/src/closure.c +++ b/src/closure.c @@ -26,6 +26,7 @@ #include "closure.h" #include "derives.h" #include "warshall.h" +#include "bitset.h" /* NITEMSET is the size of the array ITEMSET. */ short *itemset; @@ -34,11 +35,11 @@ int nitemset; static unsigned *ruleset; /* internal data. See comments before set_fderives and set_firsts. */ -static unsigned *fderives; -static unsigned *firsts; +static bitset *fderives; +static unsigned int *firsts; /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var. */ -#define FDERIVES(Var) (fderives + ((Var) - ntokens) * rulesetsize) +#define FDERIVES(Var) fderives[(Var) - ntokens] #define FIRSTS(Var) (firsts + ((Var) - ntokens) * varsetsize) /* number of words required to hold a bit for each rule */ @@ -99,7 +100,7 @@ print_fderives (void) { fprintf (stderr, "\t%s derives\n", symbols[i]->tag); for (j = 0; j <= nrules; j++) - if (BITISSET (FDERIVES (i), j)) + if (bitset_test (FDERIVES (i), j)) { short *rhsp; fprintf (stderr, "\t\t%d:", j - 1); @@ -159,7 +160,13 @@ set_fderives (void) { int i, j, k; - fderives = XCALLOC (unsigned, nvars * rulesetsize); + fderives = XCALLOC (bitset, nvars); + bitset_stats_init (); + for (i = 0 ; i < nvars; ++i) + { + fderives[i] = bitset_create (nrules + 1, BITSET_FIXED); + bitset_zero (fderives[i]); + } set_firsts (); @@ -167,7 +174,7 @@ set_fderives (void) for (j = ntokens; j < nsyms; ++j) if (BITISSET (FIRSTS (i), j - ntokens)) for (k = 0; derives[j][k] > 0; ++k) - SETBIT (FDERIVES (i), derives[j][k]); + bitset_set (FDERIVES (i), derives[j][k]); if (trace_flag) print_fderives (); @@ -206,8 +213,11 @@ closure (short *core, int n) if (n == 0) { - for (r = 0; r < rulesetsize; ++r) - ruleset[r] = FDERIVES (start_symbol)[r]; + for (ruleno = 0; ruleno < nrules + 1; ++ruleno) + if (bitset_test (FDERIVES (start_symbol), ruleno)) + SETBIT (ruleset, ruleno); + else + RESETBIT (ruleset, ruleno); } else { @@ -216,8 +226,9 @@ closure (short *core, int n) for (c = 0; c < n; ++c) if (ISVAR (ritem[core[c]])) - for (r = 0; r < rulesetsize; ++r) - ruleset[r] |= FDERIVES (ritem[core[c]])[r]; + for (ruleno = 0; ruleno < nrules + 1; ++ruleno) + if (bitset_test (FDERIVES (ritem[core[c]]), ruleno)) + SETBIT (ruleset, ruleno); } nitemset = 0; @@ -251,7 +262,11 @@ closure (short *core, int n) void free_closure (void) { + int i; XFREE (itemset); XFREE (ruleset); - XFREE (fderives); + + for (i = 0 ; i < nvars; ++i) + bitset_free (fderives[i]); + free (fderives); }