[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
04-fyi-bitsets.patch
|
From: |
Akim Demaille |
|
Subject: |
04-fyi-bitsets.patch |
|
Date: |
Mon, 28 Jan 2002 11:55:45 +0100 |
I am not going to apply this patch now: I'm waiting for the papers.
But it gives an idea of how to use the new bitset implementation.
Index: ChangeLog
from Akim Demaille <address@hidden>
* 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.
Index: lib/Makefile.am
--- lib/Makefile.am Mon, 07 Jan 2002 21:20:16 +0100 akim
+++ lib/Makefile.am Sun, 27 Jan 2002 18:22:44 +0100 akim
@@ -41,5 +41,10 @@
quote.h quote.c quotearg.h quotearg.c \
xalloc.h xmalloc.c xstrdup.c xstrndup.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)
Index: src/closure.c
--- src/closure.c Fri, 28 Dec 2001 16:41:48 +0100 akim
+++ src/closure.c Sun, 27 Jan 2002 20:34:46 +0100 akim
@@ -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 @@
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 @@
{
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 @@
{
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 @@
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 @@
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 @@
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 @@
void
free_closure (void)
{
+ int i;
XFREE (itemset);
XFREE (ruleset);
- XFREE (fderives);
+
+ for (i = 0 ; i < nvars; ++i)
+ bitset_free (fderives[i]);
+ free (fderives);
}
Index: lib/bitset-int.h
--- lib/bitset-int.h Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/bitset-int.h Sun, 27 Jan 2002 19:31:38 +0100 akim
@@ -0,0 +1,112 @@
+/* Internal bitset definitions.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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 <limits.h>
+#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 */
Index: lib/bitset.c
--- lib/bitset.c Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/bitset.c Sun, 27 Jan 2002 20:33:21 +0100 akim
@@ -0,0 +1,835 @@
+/* General bitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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 <stdlib.h>
+#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 */
+}
Index: lib/bitset.h
--- lib/bitset.h Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/bitset.h Sun, 27 Jan 2002 19:33:07 +0100 akim
@@ -0,0 +1,395 @@
+/* Generic bitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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 <config.h>
+#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 <stdio.h>
+#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 */
Index: lib/bitsetv.c
--- lib/bitsetv.c Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/bitsetv.c Sun, 27 Jan 2002 18:21:11 +0100 akim
@@ -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 <stdlib.h>
+#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");
+}
Index: lib/bitsetv.h
--- lib/bitsetv.h Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/bitsetv.h Sun, 27 Jan 2002 18:21:20 +0100 akim
@@ -0,0 +1,49 @@
+/* Bitset vectors.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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 */
Index: lib/ebitset.c
--- lib/ebitset.c Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/ebitset.c Sun, 27 Jan 2002 19:33:26 +0100 akim
@@ -0,0 +1,1245 @@
+/* Functions to support efficient bitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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 <stdlib.h>
+
+# if WITH_DMALLOC
+# define DMALLOC_FUNC_CHECK
+# include <dmalloc.h>
+# 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);
+ }
+}
Index: lib/ebitset.h
--- lib/ebitset.h Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/ebitset.h Sun, 27 Jan 2002 18:21:20 +0100 akim
@@ -0,0 +1,58 @@
+/* Functions to support ebitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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
Index: lib/lbitset.c
--- lib/lbitset.c Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/lbitset.c Sun, 27 Jan 2002 19:33:21 +0100 akim
@@ -0,0 +1,1321 @@
+/* Functions to support link list bitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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 <stdlib.h>
+
+# if WITH_DMALLOC
+# define DMALLOC_FUNC_CHECK
+# include <dmalloc.h>
+# 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);
+ }
+}
Index: lib/lbitset.h
--- lib/lbitset.h Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/lbitset.h Sun, 27 Jan 2002 18:21:20 +0100 akim
@@ -0,0 +1,62 @@
+/* Functions to support lbitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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
Index: lib/sbitset.c
--- lib/sbitset.c Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/sbitset.c Sun, 27 Jan 2002 20:08:41 +0100 akim
@@ -0,0 +1,672 @@
+/* Simple bitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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 <stdlib.h>
+
+# if WITH_DMALLOC
+# define DMALLOC_FUNC_CHECK
+# include <dmalloc.h>
+# 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;
+}
Index: lib/sbitset.h
--- lib/sbitset.h Sun, 27 Jan 2002 20:40:31 +0100 akim
+++ lib/sbitset.h Sun, 27 Jan 2002 18:21:20 +0100 akim
@@ -0,0 +1,33 @@
+/* Functions to support sbitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- 04-fyi-bitsets.patch,
Akim Demaille <=