[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: A new module: bitset
|
From: |
Akim Demaille |
|
Subject: |
Re: A new module: bitset |
|
Date: |
Sun, 25 Nov 2018 19:52:11 +0100 |
> Le 25 nov. 2018 à 18:54, Bruno Haible <address@hidden> a écrit :
>
> Hi Akim,
>
>>> * Regarding tests: There is a large amount of algorithmic code. While
>>> the parts that Bison uses are surely correct, there is a possibility
>>> of bugs in the more rarely used parts. I would find it very useful
>>> to have unit tests of all 32 operations.
>>
>> I definitely agree. But I'd like to be incremental on this
>> regard.
>
> Sure. You can push it into gnulib, without having extensive tests.
Great! I read this as an ok to push the current state, which takes
into account your comments, but will most probably require more changes
later.
First, the bitset module (without bitset vectors).
commit de7956e9d91c826855b664867fb6e1ce35988020
Author: Akim Demaille <address@hidden>
Date: Sun Oct 28 17:32:15 2018 +0100
bitset: new module
* lib/bitset.c, lib/bitset.h, lib/bitset/array.c,
* lib/bitset/array.h, lib/bitset/base.h, lib/bitset/expandable.c,
* lib/bitset/expandable.h, lib/bitset/list.c, lib/bitset/list.h,
* lib/bitset/stats.c, lib/bitset/stats.h, lib/bitset/vector.c,
* lib/bitset/vector.h, modules/bitset:
New.
diff --git a/ChangeLog b/ChangeLog
index cbc7260ef..9fae7910f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2018-11-25 Akim Demaille <address@hidden>
+
+ bitset: new module
+ * lib/bitset.c, lib/bitset.h, lib/bitset/array.c,
+ * lib/bitset/array.h, lib/bitset/base.h, lib/bitset/expandable.c,
+ * lib/bitset/expandable.h, lib/bitset/list.c, lib/bitset/list.h,
+ * lib/bitset/stats.c, lib/bitset/stats.h, lib/bitset/vector.c,
+ * lib/bitset/vector.h, modules/bitset:
+ New.
+
2018-11-23 Bruno Haible <address@hidden>
localename: Fix gettext test failures on mingw.
diff --git a/lib/bitset.c b/lib/bitset.c
new file mode 100644
index 000000000..8b8982091
--- /dev/null
+++ b/lib/bitset.c
@@ -0,0 +1,480 @@
+/* General bitsets.
+
+ Copyright (C) 2002-2006, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#include <config.h>
+
+#include "bitset.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "obstack.h"
+
+#include "bitset/array.h"
+#include "bitset/expandable.h"
+#include "bitset/list.h"
+#include "bitset/stats.h"
+#include "bitset/vector.h"
+
+const char * const bitset_type_names[] = BITSET_TYPE_NAMES;
+
+
+/* Return number of bytes required to create a N_BIT bitset
+ of TYPE. The bitset may grow to require more bytes than this. */
+size_t
+bitset_bytes (enum bitset_type type, bitset_bindex n_bits)
+{
+ if (bitset_stats_enabled)
+ return bitset_stats_bytes ();
+
+ switch (type)
+ {
+ default:
+ abort ();
+
+ case BITSET_ARRAY:
+ return abitset_bytes (n_bits);
+
+ case BITSET_LIST:
+ return lbitset_bytes (n_bits);
+
+ case BITSET_TABLE:
+ return ebitset_bytes (n_bits);
+
+ case BITSET_VARRAY:
+ return vbitset_bytes (n_bits);
+ }
+}
+
+
+/* Initialise bitset BSET of TYPE for N_BITS. */
+bitset
+bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
+{
+ if (bitset_stats_enabled)
+ return bitset_stats_init (bset, n_bits, type);
+
+ switch (type)
+ {
+ default:
+ abort ();
+
+ case BITSET_ARRAY:
+ return abitset_init (bset, n_bits);
+
+ case BITSET_LIST:
+ return lbitset_init (bset, n_bits);
+
+ case BITSET_TABLE:
+ return ebitset_init (bset, n_bits);
+
+ case BITSET_VARRAY:
+ return vbitset_init (bset, n_bits);
+ }
+}
+
+
+/* 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 (bitset_bindex n_bits ATTRIBUTE_UNUSED, unsigned attr)
+{
+ /* Check attributes. */
+ if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
+ abort ();
+ if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
+ abort ();
+
+ /* Choose the type of bitset. Note that sometimes we will be asked
+ for a zero length fixed size bitset. */
+
+
+ /* If no attributes selected, choose a good compromise. */
+ if (!attr)
+ return BITSET_VARRAY;
+
+ if (attr & BITSET_SPARSE)
+ return BITSET_LIST;
+
+ if (attr & BITSET_FIXED)
+ return BITSET_ARRAY;
+
+ if (attr & BITSET_GREEDY)
+ return BITSET_TABLE;
+
+ return BITSET_VARRAY;
+}
+
+
+/* Create a bitset of N_BITS of type TYPE. */
+bitset
+bitset_alloc (bitset_bindex n_bits, enum bitset_type type)
+{
+ size_t bytes = bitset_bytes (type, n_bits);
+
+ bitset bset = xcalloc (1, bytes);
+
+ /* The cache is disabled until some elements are allocated. If we
+ have variable length arrays, then we may need to allocate a dummy
+ element. */
+
+ return bitset_init (bset, n_bits, type);
+}
+
+
+/* Create a bitset of N_BITS of type TYPE. */
+bitset
+bitset_obstack_alloc (struct obstack *bobstack,
+ bitset_bindex n_bits, enum bitset_type type)
+{
+ size_t bytes = bitset_bytes (type, n_bits);
+
+ bitset bset = obstack_alloc (bobstack, bytes);
+ memset (bset, 0, bytes);
+
+ return bitset_init (bset, n_bits, type);
+}
+
+
+/* Create a bitset of N_BITS and with attribute hints specified by
+ ATTR. */
+bitset
+bitset_create (bitset_bindex n_bits, unsigned attr)
+{
+ enum bitset_type type = bitset_type_choose (n_bits, attr);
+
+ return bitset_alloc (n_bits, type);
+}
+
+
+/* Free bitset BSET. */
+void
+bitset_free (bitset bset)
+{
+ BITSET_FREE_ (bset);
+ free (bset);
+}
+
+
+/* Free bitset BSET allocated on obstack. */
+void
+bitset_obstack_free (bitset bset)
+{
+ BITSET_FREE_ (bset);
+}
+
+
+/* Return bitset type. */
+enum bitset_type
+bitset_type_get (bitset bset)
+{
+ enum bitset_type type = BITSET_TYPE_ (bset);
+ if (type != BITSET_STATS)
+ return type;
+
+ return bitset_stats_type_get (bset);
+}
+
+
+/* Return name of bitset type. */
+const char *
+bitset_type_name_get (bitset bset)
+{
+ enum bitset_type type = bitset_type_get (bset);
+
+ return bitset_type_names[type];
+}
+
+
+/* Find next bit set in SRC starting from and including BITNO.
+ Return BITSET_BINDEX_MAX if SRC empty. */
+bitset_bindex
+bitset_next (bitset src, bitset_bindex bitno)
+{
+ bitset_bindex next = bitno;
+ bitset_bindex val;
+ if (!bitset_list (src, &val, 1, &next))
+ return BITSET_BINDEX_MAX;
+ return val;
+}
+
+
+/* Return true if both bitsets are of the same type and size. */
+extern bool
+bitset_compatible_p (bitset bset1, bitset bset2)
+{
+ return BITSET_COMPATIBLE_ (bset1, bset2);
+}
+
+
+/* Find previous bit set in SRC starting from and including BITNO.
+ Return BITSET_BINDEX_MAX if SRC empty. */
+bitset_bindex
+bitset_prev (bitset src, bitset_bindex bitno)
+{
+ bitset_bindex next = bitno;
+ bitset_bindex val;
+ if (!bitset_list_reverse (src, &val, 1, &next))
+ return BITSET_BINDEX_MAX;
+ return val;
+}
+
+
+/* Find first set bit. */
+bitset_bindex
+bitset_first (bitset src)
+{
+ return bitset_next (src, 0);
+}
+
+
+/* Find last set bit. */
+bitset_bindex
+bitset_last (bitset src)
+{
+ return bitset_prev (src, 0);
+}
+
+
+/* Is BITNO in SRC the only set bit? */
+bool
+bitset_only_set_p (bitset src, bitset_bindex bitno)
+{
+ bitset_bindex val[2];
+ bitset_bindex next = 0;
+
+ if (bitset_list (src, val, 2, &next) != 1)
+ return false;
+ return val[0] == bitno;
+}
+
+
+/* Print contents of bitset BSET to FILE. */
+static void
+bitset_print (FILE *file, bitset bset, bool verbose)
+{
+ if (verbose)
+ fprintf (file, "n_bits = %lu, set = {",
+ (unsigned long) bitset_size (bset));
+
+ unsigned pos = 30;
+ bitset_bindex i;
+ bitset_iterator iter;
+ BITSET_FOR_EACH (iter, bset, i, 0)
+ {
+ if (pos > 70)
+ {
+ fprintf (file, "\n");
+ pos = 0;
+ }
+
+ fprintf (file, "%lu ", (unsigned long) i);
+ pos += 1 + (i >= 10) + (i >= 100);
+ }
+
+ if (verbose)
+ fprintf (file, "}\n");
+}
+
+
+/* Dump bitset BSET to FILE. */
+void
+bitset_dump (FILE *file, bitset bset)
+{
+ bitset_print (file, bset, false);
+}
+
+
+/* Release memory associated with bitsets. */
+void
+bitset_release_memory (void)
+{
+ lbitset_release_memory ();
+ ebitset_release_memory ();
+}
+
+
+/* Toggle bit BITNO in bitset BSET and the new value of the bit. */
+bool
+bitset_toggle_ (bitset bset, bitset_bindex bitno)
+{
+ /* This routine is for completeness. It could be optimized if
+ required. */
+ if (bitset_test (bset, bitno))
+ {
+ bitset_reset (bset, bitno);
+ return false;
+ }
+ else
+ {
+ bitset_set (bset, bitno);
+ return true;
+ }
+}
+
+
+/* Return number of bits in bitset SRC. */
+bitset_bindex
+bitset_size_ (bitset src)
+{
+ return BITSET_NBITS_ (src);
+}
+
+
+/* Return number of bits set in bitset SRC. */
+bitset_bindex
+bitset_count_ (bitset src)
+{
+ bitset_bindex list[BITSET_LIST_SIZE];
+ bitset_bindex count = 0;
+
+ /* This could be greatly sped up by adding a count method for each
+ bitset implementation that uses a direct technique (based on
+ masks) for counting the number of bits set in a word. */
+
+ {
+ bitset_bindex next = 0;
+ bitset_bindex num;
+ while ((num = bitset_list (src, list, BITSET_LIST_SIZE, &next)))
+ count += num;
+ }
+
+ return count;
+}
+
+
+/* DST = SRC. Return true if DST != SRC.
+ This is a fallback for the case where SRC and DST are different
+ bitset types. */
+bool
+bitset_copy_ (bitset dst, bitset src)
+{
+ bitset_bindex i;
+ bitset_iterator iter;
+
+ /* Convert bitset types. We assume that the DST bitset
+ is large enough to hold the SRC bitset. */
+ bitset_zero (dst);
+ BITSET_FOR_EACH (iter, src, i, 0)
+ bitset_set (dst, i);
+
+ return true;
+}
+
+
+/* This is a fallback for implementations that do not support
+ four operand operations. */
+static inline bool
+bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3,
+ enum bitset_ops op)
+{
+ bool changed = false;
+
+ /* Create temporary bitset. */
+ bool stats_enabled_save = bitset_stats_enabled;
+ bitset_stats_enabled = false;
+ bitset tmp = bitset_alloc (0, bitset_type_get (dst));
+ bitset_stats_enabled = stats_enabled_save;
+
+ switch (op)
+ {
+ default:
+ abort ();
+
+ case BITSET_OP_OR_AND:
+ bitset_or (tmp, src1, src2);
+ changed = bitset_and_cmp (dst, src3, tmp);
+ break;
+
+ case BITSET_OP_AND_OR:
+ bitset_and (tmp, src1, src2);
+ changed = bitset_or_cmp (dst, src3, tmp);
+ break;
+
+ case BITSET_OP_ANDN_OR:
+ bitset_andn (tmp, src1, src2);
+ changed = bitset_or_cmp (dst, src3, tmp);
+ break;
+ }
+
+ bitset_free (tmp);
+ return changed;
+}
+
+
+/* DST = (SRC1 & SRC2) | SRC3. */
+void
+bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ bitset_and_or_cmp_ (dst, src1, src2, src3);
+}
+
+
+/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & SRC2) | SRC3. */
+bool
+bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
+}
+
+
+/* DST = (SRC1 & ~SRC2) | SRC3. */
+void
+bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ bitset_andn_or_cmp_ (dst, src1, src2, src3);
+}
+
+
+/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & ~SRC2) | SRC3. */
+bool
+bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
+}
+
+
+/* DST = (SRC1 | SRC2) & SRC3. */
+void
+bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ bitset_or_and_cmp_ (dst, src1, src2, src3);
+}
+
+
+/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
+ DST != (SRC1 | SRC2) & SRC3. */
+bool
+bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
+}
+
+
+/* Function to be called from debugger to print bitset. */
+void
+debug_bitset (bitset bset)
+{
+ if (bset)
+ bitset_print (stderr, bset, true);
+}
diff --git a/lib/bitset.h b/lib/bitset.h
new file mode 100644
index 000000000..161ac58ee
--- /dev/null
+++ b/lib/bitset.h
@@ -0,0 +1,389 @@
+/* Generic bitsets.
+
+ Copyright (C) 2002-2004, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _BITSET_H
+#define _BITSET_H
+
+/* This file is the public interface to the bitset abstract data type.
+ Only use the functions and macros defined in this file. */
+
+#include <stdio.h>
+#if USE_UNLOCKED_IO
+# include "unlocked-io.h"
+#endif
+
+#include "bitset/base.h"
+#include "obstack.h"
+
+/* Attributes used to select a bitset implementation. */
+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 at memory expense. */
+
+typedef unsigned bitset_attrs;
+
+/* The contents of the union should be considered to be private.
+ While I would like to make this union opaque, it needs to be
+ visible for the inline bit set/test functions, and for delegation
+ to the proper implementation. */
+union bitset_union
+{
+ /* This must be the first member of every other structure that is a
+ member of this union. */
+ struct bbitset_struct b; /* Base bitset data. */
+
+ struct abitset_struct
+ {
+ struct bbitset_struct b;
+ bitset_word words[1]; /* The array of bits. */
+ } a;
+
+ struct ebitset_struct
+ {
+ struct bbitset_struct b;
+ bitset_windex size; /* Number of elements. */
+ struct ebitset_elt_struct **elts; /* Expanding array of ptrs to elts. */
+ } e;
+
+ struct lbitset_struct
+ {
+ struct bbitset_struct b;
+ struct lbitset_elt_struct *head; /* First element in linked list. */
+ struct lbitset_elt_struct *tail; /* Last element in linked list. */
+ } l;
+
+ struct bitset_stats_struct
+ {
+ struct bbitset_struct b;
+ bitset bset;
+ } s;
+
+ struct vbitset_struct
+ {
+ struct bbitset_struct b;
+ bitset_windex size; /* Allocated size of array. */
+ } v;
+};
+
+
+/* The contents of this structure should be considered private.
+ It is used for iterating over set bits. */
+typedef struct
+{
+ bitset_bindex list[BITSET_LIST_SIZE];
+ bitset_bindex next;
+ bitset_bindex num;
+ bitset_bindex i;
+} bitset_iterator;
+
+
+/* Return bytes required for bitset of desired type and size. */
+size_t bitset_bytes (enum bitset_type, bitset_bindex);
+
+/* Initialise a bitset with desired type and size. */
+bitset bitset_init (bitset, bitset_bindex, enum bitset_type);
+
+/* Select an implementation type based on the desired bitset size
+ and attributes. */
+enum bitset_type bitset_type_choose (bitset_bindex, bitset_attrs);
+
+/* Create a bitset of desired type and size. The bitset is zeroed. */
+bitset bitset_alloc (bitset_bindex, enum bitset_type);
+
+/* Free bitset. */
+void bitset_free (bitset);
+
+/* Create a bitset of desired type and size using an obstack. The
+ bitset is zeroed. */
+bitset bitset_obstack_alloc (struct obstack *bobstack,
+ bitset_bindex, enum bitset_type);
+
+/* Free bitset allocated on obstack. */
+void bitset_obstack_free (bitset);
+
+/* Create a bitset of desired size and attributes. The bitset is zeroed. */
+bitset bitset_create (bitset_bindex, bitset_attrs);
+
+/* Return bitset type. */
+enum bitset_type bitset_type_get (bitset);
+
+/* Return bitset type name. */
+const char *bitset_type_name_get (bitset);
+
+
+/* Set bit BITNO in bitset BSET. */
+static inline void
+bitset_set (bitset bset, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+ bitset_windex offset = windex - bset->b.cindex;
+
+ if (offset < bset->b.csize)
+ bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
+ else
+ BITSET_SET_ (bset, bitno);
+}
+
+
+/* Reset bit BITNO in bitset BSET. */
+static inline void
+bitset_reset (bitset bset, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+ bitset_windex offset = windex - bset->b.cindex;
+
+ if (offset < bset->b.csize)
+ bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
+ else
+ BITSET_RESET_ (bset, bitno);
+}
+
+
+/* Test bit BITNO in bitset BSET. */
+static inline bool
+bitset_test (bitset bset, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+ bitset_windex offset = windex - bset->b.cindex;
+
+ if (offset < bset->b.csize)
+ return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
+ else
+ return BITSET_TEST_ (bset, bitno);
+}
+
+
+/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */
+#define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
+
+/* Return size in bits of bitset SRC. */
+#define bitset_size(SRC) BITSET_SIZE_ (SRC)
+
+/* Change size of bitset. */
+void bitset_resize (bitset, bitset_bindex);
+
+/* Return number of bits set in bitset SRC. */
+#define bitset_count(SRC) BITSET_COUNT_ (SRC)
+
+
+/* Return SRC == 0. */
+#define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
+
+/* DST = ~0. */
+#define bitset_ones(DST) BITSET_ONES_ (DST)
+
+/* DST = 0. */
+#define bitset_zero(DST) BITSET_ZERO_ (DST)
+
+
+
+/* DST = SRC. */
+#define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
+
+/* Return DST & SRC == 0. */
+#define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
+
+/* Return DST == SRC. */
+#define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
+
+/* DST = ~SRC. */
+#define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
+
+/* Return DST == DST | SRC. */
+#define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
+
+
+
+/* DST = SRC1 & SRC2. */
+#define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
+#define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 & ~SRC2. */
+#define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
+#define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 | SRC2. */
+#define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
+#define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 ^ SRC2. */
+#define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
+
+/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
+#define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
+
+
+
+/* DST = (SRC1 & SRC2) | SRC3. */
+#define bitset_and_or(DST, SRC1, SRC2, SRC3) \
+ BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & SRC2) | SRC3. */
+#define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
+ BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 & ~SRC2) | SRC3. */
+#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
+ BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & ~SRC2) | SRC3. */
+#define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
+ BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 | SRC2) & SRC3. */
+#define bitset_or_and(DST, SRC1, SRC2, SRC3)\
+ BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
+ DST != (SRC1 | SRC2) & SRC3. */
+#define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
+ BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
+
+/* 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) \
+ BITSET_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_list_reverse(BSET, LIST, NUM, NEXT) \
+ BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
+
+/* Return true if both bitsets are of the same type and size. */
+bool bitset_compatible_p (bitset bset1, bitset bset2);
+
+/* Find next set bit from the given bit index. */
+bitset_bindex bitset_next (bitset, bitset_bindex);
+
+/* Find previous set bit from the given bit index. */
+bitset_bindex bitset_prev (bitset, bitset_bindex);
+
+/* Find first set bit. */
+bitset_bindex bitset_first (bitset);
+
+/* Find last set bit. */
+bitset_bindex bitset_last (bitset);
+
+/* Return nonzero if this is the only set bit. */
+bool bitset_only_set_p (bitset, bitset_bindex);
+
+/* Dump bitset. */
+void bitset_dump (FILE *, bitset);
+
+/* Loop over all elements of BSET, starting with MIN, setting INDEX
+ to the index of each set bit. For example, the following will print
+ the bits set in a bitset:
+
+ bitset_bindex i;
+ bitset_iterator iter;
+
+ BITSET_FOR_EACH (iter, src, i, 0)
+ printf ("%lu ", (unsigned long) i);
+*/
+#define BITSET_FOR_EACH(ITER, BSET, INDEX, MIN) \
+ for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
+ (ITER.num == BITSET_LIST_SIZE) \
+ && (ITER.num = bitset_list (BSET, ITER.list, \
+ BITSET_LIST_SIZE, &ITER.next));) \
+ for (ITER.i = 0; \
+ ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
+ ITER.i++)
+
+
+/* Loop over all elements of BSET, in reverse order starting with
+ MIN, setting INDEX to the index of each set bit. For example, the
+ following will print the bits set in a bitset in reverse order:
+
+ bitset_bindex i;
+ bitset_iterator iter;
+
+ BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
+ printf ("%lu ", (unsigned long) i);
+*/
+#define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, MIN) \
+ for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
+ (ITER.num == BITSET_LIST_SIZE) \
+ && (ITER.num = bitset_list_reverse (BSET, ITER.list, \
+ BITSET_LIST_SIZE, &ITER.next));) \
+ for (ITER.i = 0; \
+ ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
+ ITER.i++)
+
+
+/* Define set operations in terms of logical operations. */
+
+#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
+#define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
+
+#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
+#define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1,
SRC2)
+
+#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
+#define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
+
+/* Symmetrical difference. */
+#define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
+#define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
+
+/* Union of difference. */
+#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
+ bitset_andn_or (DST, SRC1, SRC2, SRC3)
+#define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
+ bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
+
+
+/* Release any memory tied up with bitsets. */
+void bitset_release_memory (void);
+
+/* Enable bitset stats gathering. */
+void bitset_stats_enable (void);
+
+/* Disable bitset stats gathering. */
+void bitset_stats_disable (void);
+
+/* Read bitset stats file of accummulated stats. */
+void bitset_stats_read (const char *file_name);
+
+/* Write bitset stats file of accummulated stats. */
+void bitset_stats_write (const char *file_name);
+
+/* Dump bitset stats. */
+void bitset_stats_dump (FILE *);
+
+/* Function to debug bitset from debugger. */
+void debug_bitset (bitset);
+
+/* Function to debug bitset stats from debugger. */
+void debug_bitset_stats (void);
+
+#endif /* _BITSET_H */
diff --git a/lib/bitset/array.c b/lib/bitset/array.c
new file mode 100644
index 000000000..affca177e
--- /dev/null
+++ b/lib/bitset/array.c
@@ -0,0 +1,772 @@
+/* Array bitsets.
+
+ Copyright (C) 2002-2003, 2006, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#include <config.h>
+
+#include "bitset/array.h"
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+/* This file implements fixed size bitsets stored as an array
+ of words. Any unused bits in the last word must be zero. */
+
+#define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
+#define ABITSET_WORDS(X) ((X)->a.words)
+
+
+static bitset_bindex
+abitset_resize (bitset src, bitset_bindex size)
+{
+ /* These bitsets have a fixed size. */
+ if (BITSET_SIZE_ (src) != size)
+ abort ();
+
+ return size;
+}
+
+/* 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 bitset_bindex
+abitset_small_list (bitset src, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ bitset_word word = ABITSET_WORDS (src)[0];
+
+ /* Short circuit common case. */
+ if (!word)
+ return 0;
+
+ bitset_windex size = BITSET_SIZE_ (src);
+ bitset_bindex 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. */
+
+ bitset_bindex count;
+ 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
+abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
+{
+ /* This should never occur for abitsets since we should always hit
+ the cache. It is likely someone is trying to access outside the
+ bounds of the bitset. */
+ abort ();
+}
+
+
+/* Reset bit BITNO in bitset DST. */
+static void
+abitset_reset (bitset dst ATTRIBUTE_UNUSED,
+ bitset_bindex bitno ATTRIBUTE_UNUSED)
+{
+ /* This should never occur for abitsets since we should always hit
+ the cache. It is likely someone is trying to access outside the
+ bounds of the bitset. Since the bit is zero anyway, let it pass. */
+}
+
+
+/* Test bit BITNO in bitset SRC. */
+static bool
+abitset_test (bitset src ATTRIBUTE_UNUSED,
+ bitset_bindex bitno ATTRIBUTE_UNUSED)
+{
+ /* This should never occur for abitsets since we should always
+ hit the cache. */
+ return false;
+}
+
+
+/* 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 bitset_bindex
+abitset_list_reverse (bitset src, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ bitset_bindex rbitno = *next;
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_bindex n_bits = BITSET_SIZE_ (src);
+
+ /* If num is 1, we could speed things up with a binary search
+ of the word of interest. */
+
+ if (rbitno >= n_bits)
+ return 0;
+
+ bitset_bindex count = 0;
+
+ bitset_bindex bitno = n_bits - (rbitno + 1);
+
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+ unsigned bitcnt = bitno % BITSET_WORD_BITS;
+ bitset_bindex bitoff = windex * BITSET_WORD_BITS;
+
+ do
+ {
+ bitset_word 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;
+ }
+ bitoff -= BITSET_WORD_BITS;
+ bitcnt = BITSET_WORD_BITS - 1;
+ }
+ while (windex--);
+
+ *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 bitset_bindex
+abitset_list (bitset src, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ bitset_windex windex;
+ bitset_bindex bitoff;
+ bitset_windex size = src->b.csize;
+ bitset_word *srcp = ABITSET_WORDS (src);
+
+ bitset_bindex bitno = *next;
+
+ bitset_bindex count = 0;
+ if (!bitno)
+ {
+ /* Many bitsets are zero, so make this common case fast. */
+ for (windex = 0; windex < size && !srcp[windex]; windex++)
+ continue;
+ if (windex >= size)
+ return 0;
+
+ /* If num is 1, we could speed things up with a binary search
+ of the current word. */
+
+ bitoff = windex * BITSET_WORD_BITS;
+ }
+ else
+ {
+ if (bitno >= BITSET_SIZE_ (src))
+ return 0;
+
+ windex = 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 = windex * BITSET_WORD_BITS;
+ bitset_word word = srcp[windex] >> bitno;
+ for (bitno = bitoff + bitno; word; bitno++)
+ {
+ if (word & 1)
+ {
+ list[count++] = bitno;
+ if (count >= num)
+ {
+ *next = bitno + 1;
+ return count;
+ }
+ }
+ word >>= 1;
+ }
+ windex++;
+ }
+ bitoff = windex * BITSET_WORD_BITS;
+ }
+
+ for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
+ {
+ bitset_word word = srcp[windex];
+ if (!word)
+ 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
+abitset_unused_clear (bitset dst)
+{
+ unsigned last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
+ if (last_bit)
+ ABITSET_WORDS (dst)[dst->b.csize - 1] &=
+ ((bitset_word) 1 << last_bit) - 1;
+}
+
+
+static void
+abitset_ones (bitset dst)
+{
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ size_t bytes = sizeof (bitset_word) * dst->b.csize;
+
+ memset (dstp, -1, bytes);
+ abitset_unused_clear (dst);
+}
+
+
+static void
+abitset_zero (bitset dst)
+{
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ size_t bytes = sizeof (bitset_word) * dst->b.csize;
+
+ memset (dstp, 0, bytes);
+}
+
+
+static bool
+abitset_empty_p (bitset dst)
+{
+ bitset_word *dstp = ABITSET_WORDS (dst);
+
+ for (bitset_windex i = 0; i < dst->b.csize; i++)
+ if (dstp[i])
+ return false;
+ return true;
+}
+
+
+static void
+abitset_copy1 (bitset dst, bitset src)
+{
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ if (srcp == dstp)
+ return;
+ bitset_windex size = dst->b.csize;
+ memcpy (dstp, srcp, sizeof (bitset_word) * size);
+}
+
+
+static void
+abitset_not (bitset dst, bitset src)
+{
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ *dstp++ = ~(*srcp++);
+ abitset_unused_clear (dst);
+}
+
+
+static bool
+abitset_equal_p (bitset dst, bitset src)
+{
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ if (*srcp++ != *dstp++)
+ return false;
+ return true;
+}
+
+
+static bool
+abitset_subset_p (bitset dst, bitset src)
+{
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++, dstp++, srcp++)
+ if (*dstp != (*srcp | *dstp))
+ return false;
+ return true;
+}
+
+
+static bool
+abitset_disjoint_p (bitset dst, bitset src)
+{
+ bitset_word *srcp = ABITSET_WORDS (src);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ if (*srcp++ & *dstp++)
+ return false;
+ return true;
+}
+
+
+static void
+abitset_and (bitset dst, bitset src1, bitset src2)
+{
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ *dstp++ = *src1p++ & *src2p++;
+}
+
+
+static bool
+abitset_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+ bool changed = false;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ & *src2p++;
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+abitset_andn (bitset dst, bitset src1, bitset src2)
+{
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ *dstp++ = *src1p++ & ~(*src2p++);
+}
+
+
+static bool
+abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+ bool changed = false;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ & ~(*src2p++);
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+abitset_or (bitset dst, bitset src1, bitset src2)
+{
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ *dstp++ = *src1p++ | *src2p++;
+}
+
+
+static bool
+abitset_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+ bool changed = false;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ | *src2p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+abitset_xor (bitset dst, bitset src1, bitset src2)
+{
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ *dstp++ = *src1p++ ^ *src2p++;
+}
+
+
+static bool
+abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+ bool changed = false;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ ^ *src2p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ *dstp++ = (*src1p++ & *src2p++) | *src3p++;
+}
+
+
+static bool
+abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ bool changed = false;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
+}
+
+
+static bool
+abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ bool changed = false;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++)
+ *dstp++ = (*src1p++ | *src2p++) & *src3p++;
+}
+
+
+static bool
+abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ bool changed = false;
+ bitset_word *src1p = ABITSET_WORDS (src1);
+ bitset_word *src2p = ABITSET_WORDS (src2);
+ bitset_word *src3p = ABITSET_WORDS (src3);
+ bitset_word *dstp = ABITSET_WORDS (dst);
+ bitset_windex size = dst->b.csize;
+
+ for (bitset_windex i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+abitset_copy (bitset dst, bitset src)
+{
+ if (BITSET_COMPATIBLE_ (dst, src))
+ abitset_copy1 (dst, src);
+ else
+ bitset_copy_ (dst, src);
+}
+
+
+/* Vector of operations for single word bitsets. */
+struct bitset_vtable abitset_small_vtable = {
+ abitset_set,
+ abitset_reset,
+ bitset_toggle_,
+ abitset_test,
+ abitset_resize,
+ bitset_size_,
+ bitset_count_,
+ abitset_empty_p,
+ abitset_ones,
+ abitset_zero,
+ abitset_copy,
+ abitset_disjoint_p,
+ abitset_equal_p,
+ abitset_not,
+ abitset_subset_p,
+ abitset_and,
+ abitset_and_cmp,
+ abitset_andn,
+ abitset_andn_cmp,
+ abitset_or,
+ abitset_or_cmp,
+ abitset_xor,
+ abitset_xor_cmp,
+ abitset_and_or,
+ abitset_and_or_cmp,
+ abitset_andn_or,
+ abitset_andn_or_cmp,
+ abitset_or_and,
+ abitset_or_and_cmp,
+ abitset_small_list,
+ abitset_list_reverse,
+ NULL,
+ BITSET_ARRAY
+};
+
+
+/* Vector of operations for multiple word bitsets. */
+struct bitset_vtable abitset_vtable = {
+ abitset_set,
+ abitset_reset,
+ bitset_toggle_,
+ abitset_test,
+ abitset_resize,
+ bitset_size_,
+ bitset_count_,
+ abitset_empty_p,
+ abitset_ones,
+ abitset_zero,
+ abitset_copy,
+ abitset_disjoint_p,
+ abitset_equal_p,
+ abitset_not,
+ abitset_subset_p,
+ abitset_and,
+ abitset_and_cmp,
+ abitset_andn,
+ abitset_andn_cmp,
+ abitset_or,
+ abitset_or_cmp,
+ abitset_xor,
+ abitset_xor_cmp,
+ abitset_and_or,
+ abitset_and_or_cmp,
+ abitset_andn_or,
+ abitset_andn_or_cmp,
+ abitset_or_and,
+ abitset_or_and_cmp,
+ abitset_list,
+ abitset_list_reverse,
+ NULL,
+ BITSET_ARRAY
+};
+
+
+size_t
+abitset_bytes (bitset_bindex n_bits)
+{
+ size_t header_size = offsetof (union bitset_union, a.words);
+ struct bitset_align_struct { char a; union bitset_union b; };
+ size_t bitset_alignment = offsetof (struct bitset_align_struct, b);
+
+ bitset_windex size = ABITSET_N_WORDS (n_bits);
+ size_t bytes = header_size + size * sizeof (bitset_word);
+
+ /* Align the size properly for a vector of abitset objects. */
+ if (header_size % bitset_alignment != 0
+ || sizeof (bitset_word) % bitset_alignment != 0)
+ {
+ bytes += bitset_alignment - 1;
+ bytes -= bytes % bitset_alignment;
+ }
+
+ return bytes;
+}
+
+
+bitset
+abitset_init (bitset bset, bitset_bindex n_bits)
+{
+ bitset_windex size = ABITSET_N_WORDS (n_bits);
+ BITSET_NBITS_ (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. */
+ bset->b.vtable = size == 1 ? &abitset_small_vtable : &abitset_vtable;
+ bset->b.cindex = 0;
+ bset->b.csize = size;
+ bset->b.cdata = ABITSET_WORDS (bset);
+ return bset;
+}
diff --git a/lib/bitset/array.h b/lib/bitset/array.h
new file mode 100644
index 000000000..e7f737291
--- /dev/null
+++ b/lib/bitset/array.h
@@ -0,0 +1,30 @@
+/* Functions to support abitsets.
+
+ Copyright (C) 2002, 2004, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _BITSET_ARRAY_H
+#define _BITSET_ARRAY_H
+
+#include "bitset.h"
+
+size_t abitset_bytes (bitset_bindex);
+
+bitset abitset_init (bitset, bitset_bindex);
+
+#endif
diff --git a/lib/bitset/base.h b/lib/bitset/base.h
new file mode 100644
index 000000000..b974078be
--- /dev/null
+++ b/lib/bitset/base.h
@@ -0,0 +1,312 @@
+/* Base bitset stuff.
+
+ Copyright (C) 2002-2004, 2006, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _BITSET_BASE_H
+#define _BITSET_BASE_H
+
+#include <limits.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "xalloc.h"
+
+#ifndef __attribute__
+# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
+# define __attribute__(x)
+# endif
+#endif
+
+#define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
+
+/* Currently we support five flavours of bitsets:
+ BITSET_ARRAY: Array of bits (fixed size, fast for dense bitsets).
+ Memory for bit array and bitset structure allocated
+ contiguously.
+ BITSET_LIST: Linked list of arrays of bits (variable size, least storage
+ for large very sparse sets).
+ BITSET_TABLE: Expandable table of pointers to arrays of bits
+ (variable size, less storage for large sparse sets).
+ Faster than BITSET_LIST for random access.
+ BITSET_VARRAY: Variable array of bits (variable size, fast for
+ dense bitsets).
+ BITSET_STATS: Wrapper bitset for internal use only. Used for gathering
+ statistics and/or better run-time checking.
+*/
+enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_VARRAY,
+ BITSET_TYPE_NUM, BITSET_STATS};
+#define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset", "vbitset"}
+
+extern const char * const bitset_type_names[];
+
+enum bitset_alloc_type {BITSET_MALLOC, BITSET_OBALLOC};
+
+/* Data type used to store a word of bits. */
+typedef unsigned long bitset_word;
+#define BITSET_WORD_BITS ((unsigned) (CHAR_BIT * sizeof (bitset_word)))
+
+/* Bit index. In theory we might need a type wider than size_t, but
+ in practice we lose at most a factor of CHAR_BIT by going with
+ size_t, and that is good enough. If this type is changed to be
+ wider than size_t, the code needs to be modified to check for
+ overflow when converting bit counts to byte or word counts.
+ The bit and word index types must be unsigned. */
+typedef size_t bitset_bindex;
+
+/* Word index. */
+typedef size_t bitset_windex;
+
+/* Maximum values for commonly-used unsigned types. BITSET_SIZE_MAX
+ always equals SIZE_MAX, but some older systems lack SIZE_MAX. */
+#define BITSET_BINDEX_MAX ((bitset_bindex) -1)
+
+/* Limit max word index to the maximum value of a signed integer
+ to simplify cache disabling. */
+#define BITSET_WINDEX_MAX (((bitset_windex) -1) >> 1)
+#define BITSET_SIZE_MAX ((size_t) -1)
+
+#define BITSET_MSB ((bitset_word) 1 << (BITSET_WORD_BITS - 1))
+
+#define BITSET_LIST_SIZE 1024
+
+enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES,
+ BITSET_OP_COPY, BITSET_OP_NOT,
+ BITSET_OP_EMPTY_P, BITSET_OP_EQUAL_P,
+ BITSET_OP_SUBSET_P, BITSET_OP_DISJOINT_P,
+ BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN,
+ BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR};
+
+struct bbitset_struct
+{
+ const struct bitset_vtable *vtable;
+ bitset_windex cindex; /* Cache word index. */
+ bitset_windex csize; /* Cache size in words. */
+ bitset_word *cdata; /* Cache data pointer. */
+ bitset_bindex n_bits; /* Number of bits. */
+ /* Perhaps we could sacrifice another word to indicate
+ that the bitset is known to be zero, that a bit has been set
+ in the cache, and that a bit has been cleared in the cache.
+ This would speed up some of the searches but slightly slow down
+ bit set/reset operations of cached bits. */
+};
+
+
+typedef union bitset_union *bitset;
+
+
+/* Private accessor macros to bitset structure. */
+#define BITSET_VTABLE_(SRC) (SRC)->b.vtable
+#define BITSET_CINDEX_(SRC) (SRC)->b.cindex
+#define BITSET_CDATA_(SRC) (SRC)->b.cdata
+#define BITSET_CSIZE_(SRC) (SRC)->b.csize
+#define BITSET_NBITS_(SRC) (SRC)->b.n_bits
+
+
+/* The contents of this structure should be considered private. */
+struct bitset_vtable
+{
+ void (*set) (bitset, bitset_bindex);
+ void (*reset) (bitset, bitset_bindex);
+ bool (*toggle) (bitset, bitset_bindex);
+ bool (*test) (bitset, bitset_bindex);
+ bitset_bindex (*resize) (bitset, bitset_bindex);
+ bitset_bindex (*size) (bitset);
+ bitset_bindex (*count) (bitset);
+
+ bool (*empty_p) (bitset);
+ void (*ones) (bitset);
+ void (*zero) (bitset);
+
+ void (*copy) (bitset, bitset);
+ bool (*disjoint_p) (bitset, bitset);
+ bool (*equal_p) (bitset, bitset);
+ void (*not_) (bitset, bitset);
+ bool (*subset_p) (bitset, bitset);
+
+ void (*and_) (bitset, bitset, bitset);
+ bool (*and_cmp) (bitset, bitset, bitset);
+ void (*andn) (bitset, bitset, bitset);
+ bool (*andn_cmp) (bitset, bitset, bitset);
+ void (*or_) (bitset, bitset, bitset);
+ bool (*or_cmp) (bitset, bitset, bitset);
+ void (*xor_) (bitset, bitset, bitset);
+ bool (*xor_cmp) (bitset, bitset, bitset);
+
+ void (*and_or) (bitset, bitset, bitset, bitset);
+ bool (*and_or_cmp) (bitset, bitset, bitset, bitset);
+ void (*andn_or) (bitset, bitset, bitset, bitset);
+ bool (*andn_or_cmp) (bitset, bitset, bitset, bitset);
+ void (*or_and) (bitset, bitset, bitset, bitset);
+ bool (*or_and_cmp) (bitset, bitset, bitset, bitset);
+
+ bitset_bindex (*list) (bitset, bitset_bindex *, bitset_bindex,
+ bitset_bindex *);
+ bitset_bindex (*list_reverse) (bitset, bitset_bindex *, bitset_bindex,
+ bitset_bindex *);
+ void (*free) (bitset);
+ enum bitset_type type;
+};
+
+#define BITSET_COMPATIBLE_(BSET1, BSET2) \
+((BSET1)->b.vtable == (BSET2)->b.vtable)
+
+#define BITSET_CHECK2_(DST, SRC) \
+if (!BITSET_COMPATIBLE_ (DST, SRC)) abort ();
+
+#define BITSET_CHECK3_(DST, SRC1, SRC2) \
+if (!BITSET_COMPATIBLE_ (DST, SRC1) \
+ || !BITSET_COMPATIBLE_ (DST, SRC2)) abort ();
+
+#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \
+if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \
+ || !BITSET_COMPATIBLE_ (DST, SRC3)) abort ();
+
+
+/* Redefine number of bits in bitset DST. */
+#define BITSET_RESIZE_(DST, SIZE) (DST)->b.vtable->resize (DST, SIZE)
+
+/* Return size in bits of bitset SRC. */
+#define BITSET_SIZE_(SRC) (SRC)->b.vtable->size (SRC)
+
+/* Return number of bits set in bitset SRC. */
+#define BITSET_COUNT_(SRC) (SRC)->b.vtable->count (SRC)
+
+/* Return type of bitset SRC. */
+#define BITSET_TYPE_(DST) (DST)->b.vtable->type
+
+/* Set bit BITNO in bitset DST. */
+#define BITSET_SET_(DST, BITNO) (DST)->b.vtable->set (DST, BITNO)
+
+/* Reset bit BITNO in bitset DST. */
+#define BITSET_RESET_(DST, BITNO) (DST)->b.vtable->reset (DST, BITNO)
+
+/* Toggle bit BITNO in bitset DST. */
+#define BITSET_TOGGLE_(DST, BITNO) (DST)->b.vtable->toggle (DST, BITNO)
+
+/* Return non-zero if bit BITNO in bitset SRC is set. */
+#define BITSET_TEST_(SRC, BITNO) (SRC)->b.vtable->test (SRC, BITNO)
+
+/* Free bitset SRC. */
+#define BITSET_FREE_(SRC)\
+ ((SRC)->b.vtable->free ? (SRC)->b.vtable->free (SRC) :(void)0)
+
+
+/* Return SRC == 0. */
+#define BITSET_EMPTY_P_(SRC) (SRC)->b.vtable->empty_p (SRC)
+
+/* DST = ~0. */
+#define BITSET_ONES_(DST) (DST)->b.vtable->ones (DST)
+
+/* DST = 0. */
+#define BITSET_ZERO_(DST) (DST)->b.vtable->zero (DST)
+
+
+
+/* DST = SRC. */
+#define BITSET_COPY_(DST, SRC) (SRC)->b.vtable->copy (DST, SRC)
+
+/* Return DST & SRC == 0. */
+#define BITSET_DISJOINT_P_(DST, SRC) (SRC)->b.vtable->disjoint_p (DST, SRC)
+
+/* Return DST == SRC. */
+#define BITSET_EQUAL_P_(DST, SRC) (SRC)->b.vtable->equal_p (DST, SRC)
+
+/* DST = ~SRC. */
+#define BITSET_NOT_(DST, SRC) (SRC)->b.vtable->not_ (DST, SRC)
+
+/* Return DST == DST | SRC. */
+#define BITSET_SUBSET_P_(DST, SRC) (SRC)->b.vtable->subset_p (DST, SRC)
+
+
+/* DST = SRC1 & SRC2. */
+#define BITSET_AND_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_ (DST, SRC1, SRC2)
+#define BITSET_AND_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_cmp (DST, SRC1,
SRC2)
+
+/* DST = SRC1 & ~SRC2. */
+#define BITSET_ANDN_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn (DST, SRC1, SRC2)
+#define BITSET_ANDN_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn_cmp (DST,
SRC1, SRC2)
+
+/* DST = SRC1 | SRC2. */
+#define BITSET_OR_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_ (DST, SRC1, SRC2)
+#define BITSET_OR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_cmp (DST, SRC1,
SRC2)
+
+/* DST = SRC1 ^ SRC2. */
+#define BITSET_XOR_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_ (DST, SRC1, SRC2)
+#define BITSET_XOR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_cmp (DST, SRC1,
SRC2)
+
+
+
+/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & SRC2) | SRC3. */
+#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->and_or (DST, SRC1, SRC2, SRC3)
+#define BITSET_AND_OR_CMP_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->and_or_cmp (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
+ DST != (SRC1 & ~SRC2) | SRC3. */
+#define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->andn_or (DST, SRC1, SRC2, SRC3)
+#define BITSET_ANDN_OR_CMP_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->andn_or_cmp (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
+ DST != (SRC1 | SRC2) & SRC3. */
+#define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->or_and (DST, SRC1, SRC2, SRC3)
+#define BITSET_OR_AND_CMP_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->or_and_cmp (DST, SRC1, SRC2, SRC3)
+
+
+/* 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)->b.vtable->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_LIST_REVERSE_(BSET, LIST, NUM, NEXT) \
+ (BSET)->b.vtable->list_reverse (BSET, LIST, NUM, NEXT)
+
+
+/* Private functions for bitset implementations. */
+
+bool bitset_toggle_ (bitset, bitset_bindex);
+
+bitset_bindex bitset_count_ (bitset);
+
+bitset_bindex bitset_size_ (bitset);
+
+bool bitset_copy_ (bitset, bitset);
+
+void bitset_and_or_ (bitset, bitset, bitset, bitset);
+
+bool bitset_and_or_cmp_ (bitset, bitset, bitset, bitset);
+
+void bitset_andn_or_ (bitset, bitset, bitset, bitset);
+
+bool bitset_andn_or_cmp_ (bitset, bitset, bitset, bitset);
+
+void bitset_or_and_ (bitset, bitset, bitset, bitset);
+
+bool bitset_or_and_cmp_ (bitset, bitset, bitset, bitset);
+
+#endif /* _BBITSET_H */
diff --git a/lib/bitset/expandable.c b/lib/bitset/expandable.c
new file mode 100644
index 000000000..e831fdc21
--- /dev/null
+++ b/lib/bitset/expandable.c
@@ -0,0 +1,1229 @@
+/* Functions to support expandable bitsets.
+
+ Copyright (C) 2002-2006, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#include <config.h>
+
+#include "bitset/expandable.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "obstack.h"
+
+/* This file implements expandable bitsets. These bitsets can be of
+ arbitrary length and are more efficient than arrays of bits for
+ large sparse sets.
+
+ 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
+ BITSET_WINDEX_MAX or by setting csize to 0. Here
+ we use the former approach since cindex needs to be updated whenever
+ cdata is changed.
+*/
+
+
+/* Number of words to use for each element. */
+#define EBITSET_ELT_WORDS 2
+
+/* 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;
+
+
+/* Number of elements to initially allocate. */
+
+#ifndef EBITSET_INITIAL_SIZE
+# define EBITSET_INITIAL_SIZE 2
+#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 bool ebitset_obstack_init = false;
+static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */
+
+#define EBITSET_N_ELTS(N) (((N) + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS)
+#define EBITSET_ELTS(BSET) ((BSET)->e.elts)
+#define EBITSET_SIZE(BSET) EBITSET_N_ELTS (BITSET_NBITS_ (BSET))
+#define EBITSET_ASIZE(BSET) ((BSET)->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)->b.cindex = BITSET_WINDEX_MAX, \
+ (BSET)->b.cdata = 0)
+
+#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX)
+
+/* Disable bitset cache and mark BSET as being possibly non-zero. */
+#define EBITSET_NONZERO_SET(BSET) \
+ (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.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)->b.cdata == 0)
+
+/* Enable cache to point to element with table index EINDEX.
+ The element must exist. */
+#define EBITSET_CACHE_SET(BSET, EINDEX) \
+ ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
+ (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
+
+#undef min
+#undef max
+#define min(a, b) ((a) > (b) ? (b) : (a))
+#define max(a, b) ((a) > (b) ? (a) : (b))
+
+static bitset_bindex
+ebitset_resize (bitset src, bitset_bindex n_bits)
+{
+ if (n_bits == BITSET_NBITS_ (src))
+ return n_bits;
+
+ bitset_windex oldsize = EBITSET_SIZE (src);
+ bitset_windex newsize = EBITSET_N_ELTS (n_bits);
+
+ if (oldsize < newsize)
+ {
+ /* The bitset needs to grow. If we already have enough memory
+ allocated, then just zero what we need. */
+ if (newsize > EBITSET_ASIZE (src))
+ {
+ /* We need to allocate more memory. When oldsize is
+ non-zero this means that we are changing the size, so
+ grow the bitset 25% larger than requested to reduce
+ number of reallocations. */
+
+ bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
+ EBITSET_ELTS (src)
+ = realloc (EBITSET_ELTS (src), size * sizeof (ebitset_elt *));
+ EBITSET_ASIZE (src) = size;
+ }
+
+ memset (EBITSET_ELTS (src) + oldsize, 0,
+ (newsize - oldsize) * sizeof (ebitset_elt *));
+ }
+ else
+ {
+ /* The bitset needs to shrink. There's no point deallocating
+ the memory unless it is shrinking by a reasonable amount. */
+ if ((oldsize - newsize) >= oldsize / 2)
+ {
+ EBITSET_ELTS (src)
+ = realloc (EBITSET_ELTS (src), newsize * sizeof (ebitset_elt *));
+ EBITSET_ASIZE (src) = newsize;
+ }
+
+ /* Need to prune any excess bits. FIXME. */
+ }
+
+ BITSET_NBITS_ (src) = n_bits;
+ return n_bits;
+}
+
+
+/* Allocate a ebitset element. The bits are not cleared. */
+static inline ebitset_elt *
+ebitset_elt_alloc (void)
+{
+ ebitset_elt *elt;
+
+ if (ebitset_free_list != 0)
+ {
+ elt = ebitset_free_list;
+ ebitset_free_list = EBITSET_NEXT (elt);
+ }
+ else
+ {
+ if (!ebitset_obstack_init)
+ {
+ ebitset_obstack_init = true;
+
+ /* 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),
+ OBSTACK_CHUNK_ALLOC,
+ 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 cleared. */
+static inline ebitset_elt *
+ebitset_elt_calloc (void)
+{
+ ebitset_elt *elt = ebitset_elt_alloc ();
+ memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt)));
+ return elt;
+}
+
+
+static inline void
+ebitset_elt_free (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 (bitset bset, bitset_windex eindex)
+{
+ ebitset_elts *elts = EBITSET_ELTS (bset);
+ ebitset_elt *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 (bitset bset, ebitset_elt *elt, bitset_windex eindex)
+{
+ ebitset_elts *elts = EBITSET_ELTS (bset);
+ /* Assume that the elts entry not allocated. */
+ elts[eindex] = elt;
+}
+
+
+/* Are all bits in an element zero? */
+static inline bool
+ebitset_elt_zero_p (ebitset_elt *elt)
+{
+ for (int i = 0; i < EBITSET_ELT_WORDS; i++)
+ if (EBITSET_WORDS (elt)[i])
+ return false;
+ return true;
+}
+
+
+static ebitset_elt *
+ebitset_elt_find (bitset bset, bitset_bindex bindex,
+ enum ebitset_find_mode mode)
+{
+ bitset_windex eindex = bindex / EBITSET_ELT_BITS;
+
+ ebitset_elts *elts = EBITSET_ELTS (bset);
+ bitset_windex size = EBITSET_SIZE (bset);
+
+ if (eindex < size)
+ {
+ ebitset_elt *elt = elts[eindex];
+ if (elt)
+ {
+ if (EBITSET_WORDS (elt) != bset->b.cdata)
+ EBITSET_CACHE_SET (bset, eindex);
+ return elt;
+ }
+ }
+
+ /* The element could not be found. */
+
+ switch (mode)
+ {
+ default:
+ abort ();
+
+ case EBITSET_FIND:
+ return 0;
+
+ case EBITSET_CREATE:
+ if (eindex >= size)
+ ebitset_resize (bset, bindex);
+
+ /* Create a new element. */
+ {
+ ebitset_elt *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];
+ }
+}
+
+
+/* Weed out the zero elements from the elts. */
+static inline bitset_windex
+ebitset_weed (bitset bset)
+{
+ if (EBITSET_ZERO_P (bset))
+ return 0;
+
+ ebitset_elts *elts = EBITSET_ELTS (bset);
+ bitset_windex count = 0;
+ bitset_windex j;
+ for (j = 0; j < EBITSET_SIZE (bset); j++)
+ {
+ ebitset_elt *elt = elts[j];
+
+ if (elt)
+ {
+ if (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 (bitset bset)
+{
+ if (EBITSET_ZERO_P (bset))
+ return;
+
+ ebitset_elts *elts = EBITSET_ELTS (bset);
+ for (bitset_windex 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 bool
+ebitset_equal_p (bitset dst, bitset src)
+{
+ if (src == dst)
+ return true;
+
+ ebitset_weed (dst);
+ ebitset_weed (src);
+
+ if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
+ return false;
+
+ ebitset_elts *selts = EBITSET_ELTS (src);
+ ebitset_elts *delts = EBITSET_ELTS (dst);
+
+ for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++)
+ {
+ ebitset_elt *selt = selts[j];
+ ebitset_elt *delt = delts[j];
+
+ if (!selt && !delt)
+ continue;
+ if ((selt && !delt) || (!selt && delt))
+ return false;
+
+ for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++)
+ if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
+ return false;
+ }
+ return true;
+}
+
+
+/* Copy bits from bitset SRC to bitset DST. */
+static inline void
+ebitset_copy_ (bitset dst, bitset src)
+{
+ if (src == dst)
+ return;
+
+ ebitset_zero (dst);
+
+ if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src))
+ ebitset_resize (dst, BITSET_NBITS_ (src));
+
+ ebitset_elts *selts = EBITSET_ELTS (src);
+ ebitset_elts *delts = EBITSET_ELTS (dst);
+ for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++)
+ {
+ ebitset_elt *selt = selts[j];
+ if (selt)
+ {
+ ebitset_elt *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 true if
+ bitsets different. */
+static inline bool
+ebitset_copy_cmp (bitset dst, bitset src)
+{
+ if (src == dst)
+ return false;
+
+ if (EBITSET_ZERO_P (dst))
+ {
+ ebitset_copy_ (dst, src);
+ return !EBITSET_ZERO_P (src);
+ }
+
+ if (ebitset_equal_p (dst, src))
+ return false;
+
+ ebitset_copy_ (dst, src);
+ return true;
+}
+
+
+/* Set bit BITNO in bitset DST. */
+static void
+ebitset_set (bitset dst, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+ ebitset_elt_find (dst, bitno, EBITSET_CREATE);
+
+ dst->b.cdata[windex - dst->b.cindex] |=
+ (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
+}
+
+
+/* Reset bit BITNO in bitset DST. */
+static void
+ebitset_reset (bitset dst, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+ if (!ebitset_elt_find (dst, bitno, EBITSET_FIND))
+ return;
+
+ dst->b.cdata[windex - dst->b.cindex] &=
+ ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
+
+ /* If all the data is zero, perhaps we should remove it now...
+ However, there is a good chance that the element will be needed
+ again soon. */
+}
+
+
+/* Test bit BITNO in bitset SRC. */
+static bool
+ebitset_test (bitset src, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+ return (ebitset_elt_find (src, bitno, EBITSET_FIND)
+ && ((src->b.cdata[windex - src->b.cindex]
+ >> (bitno % BITSET_WORD_BITS))
+ & 1));
+}
+
+
+static void
+ebitset_free (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 bitset_bindex
+ebitset_list_reverse (bitset bset, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ if (EBITSET_ZERO_P (bset))
+ return 0;
+
+ bitset_windex size = EBITSET_SIZE (bset);
+ bitset_bindex n_bits = size * EBITSET_ELT_BITS;
+ bitset_bindex rbitno = *next;
+
+ if (rbitno >= n_bits)
+ return 0;
+
+ ebitset_elts *elts = EBITSET_ELTS (bset);
+
+ bitset_bindex bitno = n_bits - (rbitno + 1);
+
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+ bitset_windex eindex = bitno / EBITSET_ELT_BITS;
+ bitset_windex woffset = windex - eindex * EBITSET_ELT_WORDS;
+
+ /* If num is 1, we could speed things up with a binary search
+ of the word of interest. */
+ bitset_bindex count = 0;
+ unsigned bcount = bitno % BITSET_WORD_BITS;
+ bitset_bindex boffset = windex * BITSET_WORD_BITS;
+
+ do
+ {
+ ebitset_elt *elt = elts[eindex];
+ if (elt)
+ {
+ bitset_word *srcp = EBITSET_WORDS (elt);
+
+ do
+ {
+ for (bitset_word word = srcp[woffset] << (BITSET_WORD_BITS - 1 -
bcount);
+ word; bcount--)
+ {
+ if (word & BITSET_MSB)
+ {
+ list[count++] = boffset + bcount;
+ if (count >= num)
+ {
+ *next = n_bits - (boffset + bcount);
+ return count;
+ }
+ }
+ word <<= 1;
+ }
+ boffset -= BITSET_WORD_BITS;
+ bcount = BITSET_WORD_BITS - 1;
+ }
+ while (woffset--);
+ }
+
+ woffset = EBITSET_ELT_WORDS - 1;
+ boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
+ }
+ while (eindex--);
+
+ *next = n_bits - (boffset + 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 bitset_bindex
+ebitset_list (bitset bset, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ if (EBITSET_ZERO_P (bset))
+ return 0;
+
+ bitset_bindex bitno = *next;
+ bitset_bindex count = 0;
+
+ ebitset_elts *elts = EBITSET_ELTS (bset);
+ bitset_windex size = EBITSET_SIZE (bset);
+ bitset_windex eindex = bitno / EBITSET_ELT_BITS;
+
+ if (bitno % EBITSET_ELT_BITS)
+ {
+ /* We need to start within an element. This is not very common. */
+
+ ebitset_elt *elt = elts[eindex];
+ if (elt)
+ {
+ bitset_windex woffset;
+ bitset_word *srcp = EBITSET_WORDS (elt);
+
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+ woffset = eindex * EBITSET_ELT_WORDS;
+
+ for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
+ {
+ bitset_word word = srcp[windex - woffset] >> (bitno %
BITSET_WORD_BITS);
+
+ for (; word; bitno++)
+ {
+ if (word & 1)
+ {
+ list[count++] = bitno;
+ if (count >= num)
+ {
+ *next = bitno + 1;
+ return count;
+ }
+ }
+ word >>= 1;
+ }
+ bitno = (windex + 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++)
+ {
+ bitset_word *srcp;
+
+ ebitset_elt *elt = elts[eindex];
+ if (!elt)
+ continue;
+
+ srcp = EBITSET_WORDS (elt);
+ bitset_windex windex = eindex * EBITSET_ELT_WORDS;
+
+ if ((count + EBITSET_ELT_BITS) < num)
+ {
+ /* The coast is clear, plant boot! */
+
+#if EBITSET_ELT_WORDS == 2
+ bitset_word 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;
+ }
+ }
+ windex++;
+ bitno = windex * 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;
+ }
+ }
+ windex++;
+ bitno = windex * BITSET_WORD_BITS;
+#else
+ for (int i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
+ {
+ bitno = windex * 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;
+ }
+ }
+ }
+#endif
+ }
+ else
+ {
+ /* Tread more carefully since we need to check
+ if array overflows. */
+
+ for (int i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
+ {
+ bitno = windex * BITSET_WORD_BITS;
+
+ for (bitset_word 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;
+}
+
+
+/* Ensure that any unused bits within the last element are clear. */
+static inline void
+ebitset_unused_clear (bitset dst)
+{
+ bitset_bindex n_bits = BITSET_NBITS_ (dst);
+ unsigned last_bit = n_bits % EBITSET_ELT_BITS;
+
+ if (last_bit)
+ {
+ ebitset_elts *elts = EBITSET_ELTS (dst);
+
+ bitset_windex eindex = n_bits / EBITSET_ELT_BITS;
+
+ ebitset_elt *elt = elts[eindex];
+ if (elt)
+ {
+ bitset_word *srcp = EBITSET_WORDS (elt);
+
+ bitset_windex windex = n_bits / BITSET_WORD_BITS;
+ bitset_windex woffset = eindex * EBITSET_ELT_WORDS;
+
+ srcp[windex - woffset] &= ((bitset_word) 1 << last_bit) - 1;
+ windex++;
+ for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
+ srcp[windex - woffset] = 0;
+ }
+ }
+}
+
+
+static void
+ebitset_ones (bitset dst)
+{
+ for (bitset_windex 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? */
+ ebitset_elt *elt =
+ ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
+ memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
+ }
+ EBITSET_NONZERO_SET (dst);
+ ebitset_unused_clear (dst);
+}
+
+
+static bool
+ebitset_empty_p (bitset dst)
+{
+ if (EBITSET_ZERO_P (dst))
+ return 1;
+
+ ebitset_elts *elts = EBITSET_ELTS (dst);
+ for (bitset_windex j = 0; j < EBITSET_SIZE (dst); j++)
+ {
+ ebitset_elt *elt = elts[j];
+
+ if (elt)
+ {
+ if (!ebitset_elt_zero_p (elt))
+ return 0;
+ /* Do some weeding as we go. */
+ ebitset_elt_remove (dst, j);
+ }
+ }
+
+ /* All the bits are zero. We could shrink the elts.
+ For now just mark DST as known to be zero. */
+ EBITSET_ZERO_SET (dst);
+ return 1;
+}
+
+
+static void
+ebitset_not (bitset dst, bitset src)
+{
+ ebitset_resize (dst, BITSET_NBITS_ (src));
+
+ for (bitset_windex 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. */
+ ebitset_elt *selt =
+ ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_SUBST);
+ ebitset_elt *delt =
+ ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
+
+ for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++)
+ EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
+ }
+ EBITSET_NONZERO_SET (dst);
+ ebitset_unused_clear (dst);
+}
+
+
+/* Is DST == DST | SRC? */
+static bool
+ebitset_subset_p (bitset dst, bitset src)
+{
+ ebitset_elts *selts = EBITSET_ELTS (src);
+ ebitset_elts *delts = EBITSET_ELTS (dst);
+
+ bitset_windex ssize = EBITSET_SIZE (src);
+ bitset_windex dsize = EBITSET_SIZE (dst);
+
+ for (bitset_windex j = 0; j < ssize; j++)
+ {
+ ebitset_elt *selt = j < ssize ? selts[j] : 0;
+ ebitset_elt *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 (unsigned i = 0; i < EBITSET_ELT_WORDS; i++)
+ if (EBITSET_WORDS (delt)[i]
+ != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
+ return false;
+ }
+ return true;
+}
+
+
+/* Is DST & SRC == 0? */
+static bool
+ebitset_disjoint_p (bitset dst, bitset src)
+{
+ ebitset_elts *selts = EBITSET_ELTS (src);
+ ebitset_elts *delts = EBITSET_ELTS (dst);
+
+ bitset_windex ssize = EBITSET_SIZE (src);
+ bitset_windex dsize = EBITSET_SIZE (dst);
+
+ for (bitset_windex j = 0; j < ssize; j++)
+ {
+ ebitset_elt *selt = j < ssize ? selts[j] : 0;
+ ebitset_elt *delt = j < dsize ? delts[j] : 0;
+
+ if (!selt || !delt)
+ continue;
+
+ for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++)
+ if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
+ return false;
+ }
+ return true;
+}
+
+
+
+static bool
+ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
+{
+ bool changed = false;
+
+ ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));
+
+ bitset_windex ssize1 = EBITSET_SIZE (src1);
+ bitset_windex ssize2 = EBITSET_SIZE (src2);
+ bitset_windex dsize = EBITSET_SIZE (dst);
+ bitset_windex size = ssize1;
+ if (size < ssize2)
+ size = ssize2;
+
+ ebitset_elts *selts1 = EBITSET_ELTS (src1);
+ ebitset_elts *selts2 = EBITSET_ELTS (src2);
+ ebitset_elts *delts = EBITSET_ELTS (dst);
+
+ bitset_windex j = 0;
+ for (j = 0; j < size; j++)
+ {
+ ebitset_elt *selt1 = j < ssize1 ? selts1[j] : 0;
+ ebitset_elt *selt2 = j < ssize2 ? selts2[j] : 0;
+ ebitset_elt *delt = j < dsize ? delts[j] : 0;
+
+ if (!selt1 && !selt2)
+ {
+ if (delt)
+ {
+ changed = true;
+ 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;
+
+ bitset_word *srcp1 = EBITSET_WORDS (selt1);
+ bitset_word *srcp2 = EBITSET_WORDS (selt2);
+ bitset_word *dstp = EBITSET_WORDS (delt);
+ switch (op)
+ {
+ default:
+ abort ();
+
+ case BITSET_OP_OR:
+ for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+ {
+ bitset_word tmp = *srcp1++ | *srcp2++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ break;
+
+ case BITSET_OP_AND:
+ for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+ {
+ bitset_word tmp = *srcp1++ & *srcp2++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ break;
+
+ case BITSET_OP_XOR:
+ for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+ {
+ bitset_word tmp = *srcp1++ ^ *srcp2++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ break;
+
+ case BITSET_OP_ANDN:
+ for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+ {
+ bitset_word tmp = *srcp1++ & ~(*srcp2++);
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ break;
+ }
+
+ 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++)
+ {
+ changed = true;
+
+ ebitset_elt *delt = delts[j];
+ if (delt)
+ ebitset_elt_remove (dst, j);
+ }
+
+ EBITSET_NONZERO_SET (dst);
+ return changed;
+}
+
+
+static bool
+ebitset_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+ if (EBITSET_ZERO_P (src2))
+ {
+ ebitset_weed (dst);
+ bool changed = EBITSET_ZERO_P (dst);
+ ebitset_zero (dst);
+ return changed;
+ }
+ else if (EBITSET_ZERO_P (src1))
+ {
+ ebitset_weed (dst);
+ bool changed = EBITSET_ZERO_P (dst);
+ ebitset_zero (dst);
+ return changed;
+ }
+ return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
+}
+
+
+static void
+ebitset_and (bitset dst, bitset src1, bitset src2)
+{
+ ebitset_and_cmp (dst, src1, src2);
+}
+
+
+static bool
+ebitset_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+ if (EBITSET_ZERO_P (src2))
+ {
+ return ebitset_copy_cmp (dst, src1);
+ }
+ else if (EBITSET_ZERO_P (src1))
+ {
+ ebitset_weed (dst);
+ bool changed = EBITSET_ZERO_P (dst);
+ ebitset_zero (dst);
+ return changed;
+ }
+ return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
+}
+
+
+static void
+ebitset_andn (bitset dst, bitset src1, bitset src2)
+{
+ ebitset_andn_cmp (dst, src1, src2);
+}
+
+
+static bool
+ebitset_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+ if (EBITSET_ZERO_P (src2))
+ {
+ return ebitset_copy_cmp (dst, src1);
+ }
+ else if (EBITSET_ZERO_P (src1))
+ {
+ return ebitset_copy_cmp (dst, src2);
+ }
+ return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
+}
+
+
+static void
+ebitset_or (bitset dst, bitset src1, bitset src2)
+{
+ ebitset_or_cmp (dst, src1, src2);
+}
+
+
+static bool
+ebitset_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+ if (EBITSET_ZERO_P (src2))
+ {
+ return ebitset_copy_cmp (dst, src1);
+ }
+ else if (EBITSET_ZERO_P (src1))
+ {
+ return ebitset_copy_cmp (dst, src2);
+ }
+ return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
+}
+
+
+static void
+ebitset_xor (bitset dst, bitset src1, bitset src2)
+{
+ ebitset_xor_cmp (dst, src1, src2);
+}
+
+
+static void
+ebitset_copy (bitset dst, bitset src)
+{
+ if (BITSET_COMPATIBLE_ (dst, src))
+ ebitset_copy_ (dst, src);
+ else
+ bitset_copy_ (dst, src);
+}
+
+
+/* Vector of operations for linked-list bitsets. */
+struct bitset_vtable ebitset_vtable = {
+ ebitset_set,
+ ebitset_reset,
+ bitset_toggle_,
+ ebitset_test,
+ ebitset_resize,
+ bitset_size_,
+ bitset_count_,
+ ebitset_empty_p,
+ ebitset_ones,
+ ebitset_zero,
+ ebitset_copy,
+ ebitset_disjoint_p,
+ ebitset_equal_p,
+ ebitset_not,
+ ebitset_subset_p,
+ ebitset_and,
+ ebitset_and_cmp,
+ ebitset_andn,
+ ebitset_andn_cmp,
+ ebitset_or,
+ ebitset_or_cmp,
+ ebitset_xor,
+ ebitset_xor_cmp,
+ bitset_and_or_,
+ bitset_and_or_cmp_,
+ bitset_andn_or_,
+ bitset_andn_or_cmp_,
+ bitset_or_and_,
+ bitset_or_and_cmp_,
+ ebitset_list,
+ ebitset_list_reverse,
+ ebitset_free,
+ BITSET_TABLE
+};
+
+
+/* Return size of initial structure. */
+size_t
+ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
+{
+ return sizeof (struct ebitset_struct);
+}
+
+
+/* Initialize a bitset. */
+
+bitset
+ebitset_init (bitset bset, bitset_bindex n_bits)
+{
+ bset->b.vtable = &ebitset_vtable;
+
+ bset->b.csize = EBITSET_ELT_WORDS;
+
+ EBITSET_ZERO_SET (bset);
+
+ EBITSET_ASIZE (bset) = 0;
+ EBITSET_ELTS (bset) = 0;
+ ebitset_resize (bset, n_bits);
+
+ return bset;
+}
+
+
+void
+ebitset_release_memory (void)
+{
+ ebitset_free_list = 0;
+ if (ebitset_obstack_init)
+ {
+ ebitset_obstack_init = false;
+ obstack_free (&ebitset_obstack, NULL);
+ }
+}
diff --git a/lib/bitset/expandable.h b/lib/bitset/expandable.h
new file mode 100644
index 000000000..781903e40
--- /dev/null
+++ b/lib/bitset/expandable.h
@@ -0,0 +1,32 @@
+/* Functions to support ebitsets.
+
+ Copyright (C) 2002, 2004, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _BITSET_EXPANDABLE_H
+#define _BITSET_EXPANDABLE_H
+
+#include "bitset.h"
+
+size_t ebitset_bytes (bitset_bindex);
+
+bitset ebitset_init (bitset, bitset_bindex);
+
+void ebitset_release_memory (void);
+
+#endif
diff --git a/lib/bitset/list.c b/lib/bitset/list.c
new file mode 100644
index 000000000..d784270f5
--- /dev/null
+++ b/lib/bitset/list.c
@@ -0,0 +1,1327 @@
+/* Functions to support link list bitsets.
+
+ Copyright (C) 2002-2004, 2006, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#include <config.h>
+
+#include "bitset/list.h"
+
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "obstack.h"
+
+/* 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. */
+
+
+/* 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.
+
+ The routines that dominate timing profiles are lbitset_elt_find
+ and lbitset_elt_link, especially when accessing the bits randomly. */
+
+#define LBITSET_ELT_WORDS 2
+
+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;
+
+
+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 bool lbitset_obstack_init = false;
+static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */
+
+extern void debug_lbitset (bitset);
+
+#define LBITSET_CURRENT1(X) \
+ ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))
+
+#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
+
+#define LBITSET_HEAD(X) ((X)->l.head)
+#define LBITSET_TAIL(X) ((X)->l.tail)
+
+/* Allocate a lbitset element. The bits are not cleared. */
+static inline lbitset_elt *
+lbitset_elt_alloc (void)
+{
+ lbitset_elt *elt;
+
+ if (lbitset_free_list != 0)
+ {
+ elt = lbitset_free_list;
+ lbitset_free_list = elt->next;
+ }
+ else
+ {
+ if (!lbitset_obstack_init)
+ {
+ lbitset_obstack_init = true;
+
+ /* 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),
+ OBSTACK_CHUNK_ALLOC,
+ 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 cleared. */
+static inline lbitset_elt *
+lbitset_elt_calloc (void)
+{
+ lbitset_elt *elt = lbitset_elt_alloc ();
+ memset (elt->words, 0, sizeof (elt->words));
+ return elt;
+}
+
+
+static inline void
+lbitset_elt_free (lbitset_elt *elt)
+{
+ elt->next = lbitset_free_list;
+ lbitset_free_list = elt;
+}
+
+
+/* Unlink element ELT from bitset BSET. */
+static inline void
+lbitset_elt_unlink (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->b.cdata = next->words;
+ bset->b.cindex = next->index;
+ }
+ else if (prev)
+ {
+ bset->b.cdata = prev->words;
+ bset->b.cindex = prev->index;
+ }
+ else
+ {
+ bset->b.csize = 0;
+ bset->b.cdata = 0;
+ }
+ }
+
+ lbitset_elt_free (elt);
+}
+
+
+/* Cut the chain of bitset BSET before element ELT and free the
+ elements. */
+static inline void
+lbitset_prune (bitset bset, lbitset_elt *elt)
+{
+ if (!elt)
+ return;
+
+ if (elt->prev)
+ {
+ LBITSET_TAIL (bset) = elt->prev;
+ bset->b.cdata = elt->prev->words;
+ bset->b.cindex = elt->prev->index;
+ elt->prev->next = 0;
+ }
+ else
+ {
+ LBITSET_HEAD (bset) = 0;
+ LBITSET_TAIL (bset) = 0;
+ bset->b.cdata = 0;
+ bset->b.csize = 0;
+ }
+
+ lbitset_elt *next;
+ for (; elt; elt = next)
+ {
+ next = elt->next;
+ lbitset_elt_free (elt);
+ }
+}
+
+
+/* Are all bits in an element zero? */
+static inline bool
+lbitset_elt_zero_p (lbitset_elt *elt)
+{
+ for (int i = 0; i < LBITSET_ELT_WORDS; i++)
+ if (elt->words[i])
+ return false;
+ return true;
+}
+
+
+/* Link the bitset element into the current bitset linked list. */
+static inline void
+lbitset_elt_link (bitset bset, lbitset_elt *elt)
+{
+ bitset_windex windex = elt->index;
+
+ lbitset_elt *current = bset->b.csize ? LBITSET_CURRENT (bset) : 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 (windex < bset->b.cindex)
+ {
+ lbitset_elt *ptr;
+ for (ptr = current;
+ ptr->prev && ptr->prev->index > windex; 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
+ {
+ lbitset_elt *ptr;
+ for (ptr = current;
+ ptr->next && ptr->next->index < windex; 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->b.cindex = windex;
+ bset->b.csize = LBITSET_ELT_WORDS;
+ bset->b.cdata = elt->words;
+}
+
+
+static lbitset_elt *
+lbitset_elt_find (bitset bset, bitset_windex windex,
+ enum lbitset_find_mode mode)
+{
+ lbitset_elt *current;
+
+ if (bset->b.csize)
+ {
+ current = LBITSET_CURRENT (bset);
+ /* Check if element is the cached element. */
+ if ((windex - bset->b.cindex) < bset->b.csize)
+ return current;
+ }
+ else
+ {
+ current = LBITSET_HEAD (bset);
+ }
+
+ if (current)
+ {
+ lbitset_elt *elt;
+ if (windex < bset->b.cindex)
+ {
+ for (elt = current;
+ elt->prev && elt->index > windex; elt = elt->prev)
+ continue;
+ }
+ else
+ {
+ for (elt = current;
+ elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
+ elt = elt->next)
+ continue;
+ }
+
+ /* ELT is the nearest to the one we want. If it's not the one
+ we want, the one we want does not exist. */
+ if (windex - elt->index < LBITSET_ELT_WORDS)
+ {
+ bset->b.cindex = elt->index;
+ bset->b.csize = LBITSET_ELT_WORDS;
+ bset->b.cdata = elt->words;
+ return elt;
+ }
+ }
+
+ switch (mode)
+ {
+ default:
+ abort ();
+
+ case LBITSET_FIND:
+ return 0;
+
+ case LBITSET_CREATE:
+ windex -= windex % LBITSET_ELT_WORDS;
+ lbitset_elt *elt = lbitset_elt_calloc ();
+ elt->index = windex;
+ lbitset_elt_link (bset, elt);
+ return elt;
+
+ case LBITSET_SUBST:
+ return &lbitset_zero_elts[0];
+ }
+}
+
+
+/* Weed out the zero elements from the list. */
+static inline void
+lbitset_weed (bitset bset)
+{
+ lbitset_elt *next;
+ for (lbitset_elt *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 void
+lbitset_zero (bitset bset)
+{
+ lbitset_elt *head = LBITSET_HEAD (bset);
+ if (!head)
+ return;
+
+ /* Clear a bitset by freeing the linked list at the head element. */
+ lbitset_prune (bset, head);
+}
+
+
+/* Is DST == SRC? */
+static inline bool
+lbitset_equal_p (bitset dst, bitset src)
+{
+ if (src == dst)
+ return true;
+
+ lbitset_weed (src);
+ lbitset_weed (dst);
+ lbitset_elt *selt;
+ lbitset_elt *delt;
+ for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
+ selt && delt; selt = selt->next, delt = delt->next)
+ {
+ if (selt->index != delt->index)
+ return false;
+
+ for (int j = 0; j < LBITSET_ELT_WORDS; j++)
+ if (delt->words[j] != selt->words[j])
+ return false;
+ }
+ return !selt && !delt;
+}
+
+
+/* Copy bits from bitset SRC to bitset DST. */
+static inline void
+lbitset_copy (bitset dst, bitset src)
+{
+ if (src == dst)
+ return;
+
+ lbitset_zero (dst);
+
+ lbitset_elt *head = LBITSET_HEAD (src);
+ if (!head)
+ return;
+
+ lbitset_elt *prev = 0;
+ lbitset_elt *tmp;
+ for (lbitset_elt *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->b.csize = LBITSET_ELT_WORDS;
+ dst->b.cdata = LBITSET_HEAD (dst)->words;
+ dst->b.cindex = LBITSET_HEAD (dst)->index;
+}
+
+
+/* Copy bits from bitset SRC to bitset DST. Return true if
+ bitsets different. */
+static inline bool
+lbitset_copy_cmp (bitset dst, bitset src)
+{
+ if (src == dst)
+ return false;
+
+ if (!LBITSET_HEAD (dst))
+ {
+ lbitset_copy (dst, src);
+ return LBITSET_HEAD (src) != 0;
+ }
+
+ if (lbitset_equal_p (dst, src))
+ return false;
+
+ lbitset_copy (dst, src);
+ return true;
+}
+
+
+static bitset_bindex
+lbitset_resize (bitset src, bitset_bindex size)
+{
+ BITSET_NBITS_ (src) = size;
+
+ /* Need to prune any excess bits. FIXME. */
+ return size;
+}
+
+/* Set bit BITNO in bitset DST. */
+static void
+lbitset_set (bitset dst, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+ lbitset_elt_find (dst, windex, LBITSET_CREATE);
+
+ dst->b.cdata[windex - dst->b.cindex] |=
+ (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
+}
+
+
+/* Reset bit BITNO in bitset DST. */
+static void
+lbitset_reset (bitset dst, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+ if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
+ return;
+
+ dst->b.cdata[windex - dst->b.cindex] &=
+ ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
+
+ /* If all the data is zero, perhaps we should unlink it now... */
+}
+
+
+/* Test bit BITNO in bitset SRC. */
+static bool
+lbitset_test (bitset src, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+ return (lbitset_elt_find (src, windex, LBITSET_FIND)
+ && ((src->b.cdata[windex - src->b.cindex]
+ >> (bitno % BITSET_WORD_BITS))
+ & 1));
+}
+
+
+static void
+lbitset_free (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 bitset_bindex
+lbitset_list_reverse (bitset bset, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ lbitset_elt *elt = LBITSET_TAIL (bset);
+ if (!elt)
+ return 0;
+
+ bitset_bindex n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
+ bitset_bindex rbitno = *next;
+
+ if (rbitno >= n_bits)
+ return 0;
+
+ bitset_bindex bitno = n_bits - (rbitno + 1);
+
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+ /* Skip back to starting element. */
+ for (; elt && elt->index > windex; elt = elt->prev)
+ continue;
+
+ if (!elt)
+ return 0;
+
+ unsigned bcount;
+ if (windex >= elt->index + LBITSET_ELT_WORDS)
+ {
+ /* We are trying to start in no-mans land so start
+ at end of current elt. */
+ bcount = BITSET_WORD_BITS - 1;
+ windex = elt->index + LBITSET_ELT_WORDS - 1;
+ }
+ else
+ {
+ bcount = bitno % BITSET_WORD_BITS;
+ }
+
+ bitset_bindex count = 0;
+ bitset_bindex boffset = windex * BITSET_WORD_BITS;
+
+ /* If num is 1, we could speed things up with a binary search
+ of the word of interest. */
+
+ while (elt)
+ {
+ bitset_word *srcp = elt->words;
+
+ for (; (windex - elt->index) < LBITSET_ELT_WORDS;
+ windex--, boffset -= BITSET_WORD_BITS,
+ bcount = BITSET_WORD_BITS - 1)
+ {
+ bitset_word word =
+ srcp[windex - elt->index] << (BITSET_WORD_BITS - 1 - bcount);
+
+ for (; word; bcount--)
+ {
+ if (word & BITSET_MSB)
+ {
+ list[count++] = boffset + bcount;
+ if (count >= num)
+ {
+ *next = n_bits - (boffset + bcount);
+ return count;
+ }
+ }
+ word <<= 1;
+ }
+ }
+
+ elt = elt->prev;
+ if (elt)
+ {
+ windex = elt->index + LBITSET_ELT_WORDS - 1;
+ boffset = windex * BITSET_WORD_BITS;
+ }
+ }
+
+ *next = n_bits - (boffset + 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 bitset_bindex
+lbitset_list (bitset bset, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ lbitset_elt *head = LBITSET_HEAD (bset);
+ if (!head)
+ return 0;
+
+ bitset_windex windex;
+ lbitset_elt *elt;
+
+ bitset_bindex bitno = *next;
+ bitset_bindex count = 0;
+
+ if (!bitno)
+ {
+ /* This is the most common case. */
+
+ /* Start with the first element. */
+ elt = head;
+ windex = elt->index;
+ bitno = windex * BITSET_WORD_BITS;
+ }
+ else
+ {
+ windex = bitno / BITSET_WORD_BITS;
+
+ /* Skip to starting element. */
+ for (elt = head;
+ elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
+ elt = elt->next)
+ continue;
+
+ if (!elt)
+ return 0;
+
+ if (windex < elt->index)
+ {
+ windex = elt->index;
+ bitno = windex * BITSET_WORD_BITS;
+ }
+ else
+ {
+ bitset_word *srcp = elt->words;
+
+ /* We are starting within an element. */
+
+ for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
+ {
+ bitset_word word = srcp[windex - 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 = (windex + 1) * BITSET_WORD_BITS;
+ }
+
+ elt = elt->next;
+ if (elt)
+ {
+ windex = elt->index;
+ bitno = windex * BITSET_WORD_BITS;
+ }
+ }
+ }
+
+
+ /* If num is 1, we could speed things up with a binary search
+ of the word of interest. */
+
+ while (elt)
+ {
+ bitset_word *srcp = elt->words;
+
+ if ((count + LBITSET_ELT_BITS) < num)
+ {
+ /* The coast is clear, plant boot! */
+
+#if LBITSET_ELT_WORDS == 2
+ bitset_word 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;
+ }
+ }
+ windex++;
+ bitno = windex * 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;
+ }
+ }
+ windex++;
+ bitno = windex * BITSET_WORD_BITS;
+#else
+ for (int i = 0; i < LBITSET_ELT_WORDS; i++)
+ {
+ bitset_word 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;
+ }
+ }
+ windex++;
+ bitno = windex * BITSET_WORD_BITS;
+ }
+#endif
+ }
+ else
+ {
+ /* Tread more carefully since we need to check
+ if array overflows. */
+
+ for (int i = 0; i < LBITSET_ELT_WORDS; i++)
+ {
+ for (bitset_word word = srcp[i]; word; bitno++)
+ {
+ if (word & 1)
+ {
+ list[count++] = bitno;
+ if (count >= num)
+ {
+ *next = bitno + 1;
+ return count;
+ }
+ }
+ word >>= 1;
+ }
+ windex++;
+ bitno = windex * BITSET_WORD_BITS;
+ }
+ }
+
+ elt = elt->next;
+ if (elt)
+ {
+ windex = elt->index;
+ bitno = windex * BITSET_WORD_BITS;
+ }
+ }
+
+ *next = bitno;
+ return count;
+}
+
+
+static bool
+lbitset_empty_p (bitset dst)
+{
+ lbitset_elt *elt;
+ lbitset_elt *next;
+
+ for (elt = LBITSET_HEAD (dst); elt; elt = next)
+ {
+ next = elt->next;
+ if (!lbitset_elt_zero_p (elt))
+ return false;
+ /* Weed as we go. */
+ lbitset_elt_unlink (dst, elt);
+ }
+
+ return true;
+}
+
+
+/* Ensure that any unused bits within the last element are clear. */
+static inline void
+lbitset_unused_clear (bitset dst)
+{
+ bitset_bindex n_bits = BITSET_SIZE_ (dst);
+ unsigned last_bit = n_bits % LBITSET_ELT_BITS;
+
+ if (last_bit)
+ {
+ lbitset_elt *elt = LBITSET_TAIL (dst);
+ bitset_word *srcp = elt->words;
+ bitset_windex windex = n_bits / BITSET_WORD_BITS;
+
+ srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1;
+ windex++;
+
+ for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
+ srcp[windex - elt->index] = 0;
+ }
+}
+
+
+static void
+lbitset_ones (bitset dst)
+{
+ /* This is a decidedly unfriendly operation for a linked list
+ bitset! It makes a sparse bitset become dense. An alternative
+ is to have a flag that indicates that the bitset stores the
+ complement of what it indicates. */
+
+ bitset_windex windex
+ = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
+
+ for (bitset_windex i = 0; i < windex; i += LBITSET_ELT_WORDS)
+ {
+ /* Create new elements if they cannot be found. */
+ lbitset_elt *elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+ memset (elt->words, -1, sizeof (elt->words));
+ }
+
+ lbitset_unused_clear (dst);
+}
+
+
+static void
+lbitset_not (bitset dst, bitset src)
+{
+ bitset_windex windex
+ = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
+
+ for (bitset_windex i = 0; i < windex; i += LBITSET_ELT_WORDS)
+ {
+ /* Create new elements for dst if they cannot be found
+ or substitute zero elements if src elements not found. */
+ lbitset_elt *selt = lbitset_elt_find (src, i, LBITSET_SUBST);
+ lbitset_elt *delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+
+ for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
+ delt->words[j] = ~selt->words[j];
+ }
+ lbitset_unused_clear (dst);
+ lbitset_weed (dst);
+}
+
+
+/* Is DST == DST | SRC? */
+static bool
+lbitset_subset_p (bitset dst, bitset src)
+{
+ for (lbitset_elt *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 (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
+ if (delt->words[j] != (selt->words[j] | delt->words[j]))
+ return false;
+ }
+ return true;
+}
+
+
+/* Is DST & SRC == 0? */
+static bool
+lbitset_disjoint_p (bitset dst, bitset src)
+{
+ for (lbitset_elt *selt = LBITSET_HEAD (src), *delt = LBITSET_HEAD (dst);
+ selt && delt; selt = selt->next, delt = delt->next)
+ {
+ 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];
+ }
+ /* Since the elements are different, there is no
+ intersection of these elements. */
+ continue;
+ }
+
+ for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
+ if (selt->words[j] & delt->words[j])
+ return false;
+ }
+ return true;
+}
+
+
+static bool
+lbitset_op3_cmp (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);
+ bool changed = false;
+
+ LBITSET_HEAD (dst) = 0;
+ dst->b.csize = 0;
+
+ bitset_windex windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
+ bitset_windex windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
+
+ while (selt1 || selt2)
+ {
+ bitset_windex windex;
+ lbitset_elt *stmp1;
+ lbitset_elt *stmp2;
+
+ /* Figure out whether we need to substitute zero elements for
+ missing links. */
+ if (windex1 == windex2)
+ {
+ windex = windex1;
+ stmp1 = selt1;
+ stmp2 = selt2;
+ selt1 = selt1->next;
+ windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
+ selt2 = selt2->next;
+ windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
+ }
+ else if (windex1 < windex2)
+ {
+ windex = windex1;
+ stmp1 = selt1;
+ stmp2 = &lbitset_zero_elts[0];
+ selt1 = selt1->next;
+ windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
+ }
+ else
+ {
+ windex = windex2;
+ stmp1 = &lbitset_zero_elts[0];
+ stmp2 = selt2;
+ selt2 = selt2->next;
+ windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
+ }
+
+ /* Find the appropriate element from DST. Begin by discarding
+ elements that we've skipped. */
+ lbitset_elt *dtmp;
+ while (delt && delt->index < windex)
+ {
+ changed = true;
+ dtmp = delt;
+ delt = delt->next;
+ lbitset_elt_free (dtmp);
+ }
+ if (delt && delt->index == windex)
+ {
+ 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. */
+ bitset_word *srcp1 = stmp1->words;
+ bitset_word *srcp2 = stmp2->words;
+ bitset_word *dstp = dtmp->words;
+ switch (op)
+ {
+ default:
+ abort ();
+
+ case BITSET_OP_OR:
+ for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+ {
+ bitset_word tmp = *srcp1++ | *srcp2++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ break;
+
+ case BITSET_OP_AND:
+ for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+ {
+ bitset_word tmp = *srcp1++ & *srcp2++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ break;
+
+ case BITSET_OP_XOR:
+ for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+ {
+ bitset_word tmp = *srcp1++ ^ *srcp2++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ break;
+
+ case BITSET_OP_ANDN:
+ for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+ {
+ bitset_word tmp = *srcp1++ & ~(*srcp2++);
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ break;
+ }
+
+ if (!lbitset_elt_zero_p (dtmp))
+ {
+ dtmp->index = windex;
+ /* 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 = true;
+ lbitset_prune (dst, delt);
+ }
+
+ return changed;
+}
+
+
+static bool
+lbitset_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+ lbitset_elt *selt1 = LBITSET_HEAD (src1);
+ lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+ if (!selt2)
+ {
+ lbitset_weed (dst);
+ bool changed = !LBITSET_HEAD (dst);
+ lbitset_zero (dst);
+ return changed;
+ }
+ else if (!selt1)
+ {
+ lbitset_weed (dst);
+ bool changed = !LBITSET_HEAD (dst);
+ lbitset_zero (dst);
+ return changed;
+ }
+ else
+ return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
+}
+
+
+static void
+lbitset_and (bitset dst, bitset src1, bitset src2)
+{
+ lbitset_and_cmp (dst, src1, src2);
+}
+
+
+static bool
+lbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+ lbitset_elt *selt1 = LBITSET_HEAD (src1);
+ lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+ if (!selt2)
+ {
+ return lbitset_copy_cmp (dst, src1);
+ }
+ else if (!selt1)
+ {
+ lbitset_weed (dst);
+ bool changed = !LBITSET_HEAD (dst);
+ lbitset_zero (dst);
+ return changed;
+ }
+ else
+ return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
+}
+
+
+static void
+lbitset_andn (bitset dst, bitset src1, bitset src2)
+{
+ lbitset_andn_cmp (dst, src1, src2);
+}
+
+
+static bool
+lbitset_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+ lbitset_elt *selt1 = LBITSET_HEAD (src1);
+ lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+ if (!selt2)
+ return lbitset_copy_cmp (dst, src1);
+ else if (!selt1)
+ return lbitset_copy_cmp (dst, src2);
+ else
+ return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
+}
+
+
+static void
+lbitset_or (bitset dst, bitset src1, bitset src2)
+{
+ lbitset_or_cmp (dst, src1, src2);
+}
+
+
+static bool
+lbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+ lbitset_elt *selt1 = LBITSET_HEAD (src1);
+ lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+ if (!selt2)
+ return lbitset_copy_cmp (dst, src1);
+ else if (!selt1)
+ return lbitset_copy_cmp (dst, src2);
+ else
+ return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
+}
+
+
+static void
+lbitset_xor (bitset dst, bitset src1, bitset src2)
+{
+ lbitset_xor_cmp (dst, src1, src2);
+}
+
+
+
+/* Vector of operations for linked-list bitsets. */
+struct bitset_vtable lbitset_vtable = {
+ lbitset_set,
+ lbitset_reset,
+ bitset_toggle_,
+ lbitset_test,
+ lbitset_resize,
+ bitset_size_,
+ bitset_count_,
+ lbitset_empty_p,
+ lbitset_ones,
+ lbitset_zero,
+ lbitset_copy,
+ lbitset_disjoint_p,
+ lbitset_equal_p,
+ lbitset_not,
+ lbitset_subset_p,
+ lbitset_and,
+ lbitset_and_cmp,
+ lbitset_andn,
+ lbitset_andn_cmp,
+ lbitset_or,
+ lbitset_or_cmp,
+ lbitset_xor,
+ lbitset_xor_cmp,
+ bitset_and_or_,
+ bitset_and_or_cmp_,
+ bitset_andn_or_,
+ bitset_andn_or_cmp_,
+ bitset_or_and_,
+ bitset_or_and_cmp_,
+ lbitset_list,
+ lbitset_list_reverse,
+ lbitset_free,
+ BITSET_LIST
+};
+
+
+/* Return size of initial structure. */
+size_t
+lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
+{
+ return sizeof (struct lbitset_struct);
+}
+
+
+/* Initialize a bitset. */
+bitset
+lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
+{
+ BITSET_NBITS_ (bset) = n_bits;
+ bset->b.vtable = &lbitset_vtable;
+ return bset;
+}
+
+
+void
+lbitset_release_memory (void)
+{
+ lbitset_free_list = 0;
+ if (lbitset_obstack_init)
+ {
+ lbitset_obstack_init = false;
+ obstack_free (&lbitset_obstack, NULL);
+ }
+}
+
+
+/* Function to be called from debugger to debug lbitset. */
+void
+debug_lbitset (bitset bset)
+{
+ if (!bset)
+ return;
+
+ for (lbitset_elt *elt = LBITSET_HEAD (bset); elt; elt = elt->next)
+ {
+ fprintf (stderr, "Elt %lu\n", (unsigned long) elt->index);
+ for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++)
+ {
+ bitset_word word = elt->words[i];
+
+ fprintf (stderr, " Word %u:", i);
+ for (unsigned j = 0; j < LBITSET_WORD_BITS; j++)
+ if ((word & ((bitset_word) 1 << j)))
+ fprintf (stderr, " %u", j);
+ fprintf (stderr, "\n");
+ }
+ }
+}
diff --git a/lib/bitset/list.h b/lib/bitset/list.h
new file mode 100644
index 000000000..839b3ec84
--- /dev/null
+++ b/lib/bitset/list.h
@@ -0,0 +1,32 @@
+/* Functions to support lbitsets.
+
+ Copyright (C) 2002, 2004, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _BITSET_LIST_H
+#define _BITSET_LIST_H
+
+#include "bitset.h"
+
+size_t lbitset_bytes (bitset_bindex);
+
+bitset lbitset_init (bitset, bitset_bindex);
+
+void lbitset_release_memory (void);
+
+#endif
diff --git a/lib/bitset/stats.c b/lib/bitset/stats.c
new file mode 100644
index 000000000..4947ffbb5
--- /dev/null
+++ b/lib/bitset/stats.c
@@ -0,0 +1,731 @@
+/* Bitset statistics.
+
+ Copyright (C) 2002-2006, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+/* This file is a wrapper bitset implementation for the other bitset
+ implementations. It provides bitset compatibility checking and
+ statistics gathering without having to instrument the bitset
+ implementations. When statistics gathering is enabled, the bitset
+ operations get vectored through here and we then call the appropriate
+ routines. */
+
+#include <config.h>
+
+#include "bitset/stats.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "gettext.h"
+#define _(Msgid) gettext (Msgid)
+
+#include "bitset/array.h"
+#include "bitset/base.h"
+#include "bitset/expandable.h"
+#include "bitset/list.h"
+#include "bitset/vector.h"
+
+/* Configuration macros. */
+#define BITSET_STATS_FILE "bitset.dat"
+#define BITSET_LOG_COUNT_BINS 10
+#define BITSET_LOG_SIZE_BINS 16
+#define BITSET_DENSITY_BINS 20
+
+
+/* Accessor macros. */
+#define BITSET_STATS_ALLOCS_INC(TYPE) \
+ bitset_stats_info->types[(TYPE)].allocs++
+#define BITSET_STATS_FREES_INC(BSET) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++
+#define BITSET_STATS_SETS_INC(BSET) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++
+#define BITSET_STATS_CACHE_SETS_INC(BSET) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++
+#define BITSET_STATS_RESETS_INC(BSET) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++
+#define BITSET_STATS_CACHE_RESETS_INC(BSET) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++
+#define BITSET_STATS_TESTS_INC(BSET) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++
+#define BITSET_STATS_CACHE_TESTS_INC(BSET) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++
+#define BITSET_STATS_LISTS_INC(BSET) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++
+#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++
+#define BITSET_STATS_LIST_SIZES_INC(BSET, I) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++
+#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \
+ bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++
+
+
+struct bitset_type_info_struct
+{
+ unsigned allocs;
+ unsigned frees;
+ unsigned lists;
+ unsigned sets;
+ unsigned cache_sets;
+ unsigned resets;
+ unsigned cache_resets;
+ unsigned tests;
+ unsigned cache_tests;
+ unsigned list_counts[BITSET_LOG_COUNT_BINS];
+ unsigned list_sizes[BITSET_LOG_SIZE_BINS];
+ unsigned list_density[BITSET_DENSITY_BINS];
+};
+
+struct bitset_stats_info_struct
+{
+ unsigned runs;
+ struct bitset_type_info_struct types[BITSET_TYPE_NUM];
+};
+
+
+struct bitset_stats_info_struct bitset_stats_info_data;
+struct bitset_stats_info_struct *bitset_stats_info;
+bool bitset_stats_enabled = false;
+
+
+/* Print a percentage histogram with message MSG to FILE. */
+static void
+bitset_percent_histogram_print (FILE *file, const char *name, const char *msg,
+ unsigned n_bins, unsigned *bins)
+{
+ unsigned total = 0;
+ for (unsigned i = 0; i < n_bins; i++)
+ total += bins[i];
+
+ if (!total)
+ return;
+
+ fprintf (file, "%s %s", name, msg);
+ for (unsigned i = 0; i < n_bins; i++)
+ fprintf (file, "%.0f-%.0f%%\t%8u (%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 *file, const char *name, const char *msg,
+ unsigned n_bins, unsigned *bins)
+{
+ unsigned total = 0;
+ for (unsigned i = 0; i < n_bins; i++)
+ total += bins[i];
+
+ if (!total)
+ return;
+
+ /* Determine number of useful bins. */
+ {
+ unsigned i;
+ for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
+ continue;
+ n_bins = i;
+ }
+
+ /* 2 * ceil (log10 (2) * (N - 1)) + 1. */
+ unsigned max_width = 2 * (unsigned) (0.30103 * (n_bins - 1) + 0.9999) + 1;
+
+ fprintf (file, "%s %s", name, msg);
+ {
+ unsigned i;
+ for (i = 0; i < 2; i++)
+ fprintf (file, "%*d\t%8u (%5.1f%%)\n",
+ max_width, i, bins[i], 100.0 * bins[i] / total);
+
+ for (; i < n_bins; i++)
+ fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n",
+ max_width - ((unsigned) (0.30103 * (i) + 0.9999) + 1),
+ 1UL << (i - 1),
+ (1UL << i) - 1,
+ bins[i],
+ (100.0 * bins[i]) / total);
+ }
+}
+
+
+/* Print bitset statistics to FILE. */
+static void
+bitset_stats_print_1 (FILE *file, const char *name,
+ struct bitset_type_info_struct *stats)
+{
+ if (!stats)
+ return;
+
+ fprintf (file, "%s:\n", name);
+ fprintf (file, _("%u bitset_allocs, %u freed (%.2f%%).\n"),
+ stats->allocs, stats->frees,
+ stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
+ fprintf (file, _("%u bitset_sets, %u cached (%.2f%%)\n"),
+ stats->sets, stats->cache_sets,
+ stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
+ fprintf (file, _("%u bitset_resets, %u cached (%.2f%%)\n"),
+ stats->resets, stats->cache_resets,
+ stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
+ fprintf (file, _("%u bitset_tests, %u cached (%.2f%%)\n"),
+ stats->tests, stats->cache_tests,
+ stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);
+
+ fprintf (file, _("%u 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 *file, bool verbose ATTRIBUTE_UNUSED)
+{
+ if (!bitset_stats_info)
+ return;
+
+ fprintf (file, _("Bitset statistics:\n\n"));
+
+ if (bitset_stats_info->runs > 1)
+ fprintf (file, _("Accumulated runs = %u\n"), bitset_stats_info->runs);
+
+ for (int i = 0; i < BITSET_TYPE_NUM; i++)
+ bitset_stats_print_1 (file, bitset_type_names[i],
+ &bitset_stats_info->types[i]);
+}
+
+
+/* Initialise bitset statistics logging. */
+void
+bitset_stats_enable (void)
+{
+ if (!bitset_stats_info)
+ bitset_stats_info = &bitset_stats_info_data;
+ bitset_stats_enabled = true;
+}
+
+
+void
+bitset_stats_disable (void)
+{
+ bitset_stats_enabled = false;
+}
+
+
+/* Read bitset statistics file. */
+void
+bitset_stats_read (const char *file_name)
+{
+ if (!bitset_stats_info)
+ return;
+
+ if (!file_name)
+ file_name = BITSET_STATS_FILE;
+
+ FILE *file = fopen (file_name, "r");
+ if (file)
+ {
+ if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
+ 1, file) != 1)
+ {
+ if (ferror (file))
+ perror (_("cannot read stats file"));
+ else
+ fprintf (stderr, _("bad stats file size\n"));
+ }
+ if (fclose (file) != 0)
+ perror (_("cannot read stats file"));
+ }
+ bitset_stats_info_data.runs++;
+}
+
+
+/* Write bitset statistics file. */
+void
+bitset_stats_write (const char *file_name)
+{
+ if (!bitset_stats_info)
+ return;
+
+ if (!file_name)
+ file_name = BITSET_STATS_FILE;
+
+ FILE *file = fopen (file_name, "w");
+ if (file)
+ {
+ if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
+ 1, file) != 1)
+ perror (_("cannot write stats file"));
+ if (fclose (file) != 0)
+ perror (_("cannot write stats file"));
+ }
+ else
+ perror (_("cannot open stats file for writing"));
+}
+
+
+/* Dump bitset statistics to FILE. */
+void
+bitset_stats_dump (FILE *file)
+{
+ bitset_stats_print (file, false);
+}
+
+
+/* Function to be called from debugger to print bitset stats. */
+void
+debug_bitset_stats (void)
+{
+ bitset_stats_print (stderr, true);
+}
+
+
+static void
+bitset_stats_set (bitset dst, bitset_bindex bitno)
+{
+ bitset bset = dst->s.bset;
+ bitset_windex wordno = bitno / BITSET_WORD_BITS;
+ bitset_windex offset = wordno - bset->b.cindex;
+
+ BITSET_STATS_SETS_INC (bset);
+
+ if (offset < bset->b.csize)
+ {
+ bset->b.cdata[offset] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
+ BITSET_STATS_CACHE_SETS_INC (bset);
+ }
+ else
+ BITSET_SET_ (bset, bitno);
+}
+
+
+static void
+bitset_stats_reset (bitset dst, bitset_bindex bitno)
+{
+ bitset bset = dst->s.bset;
+ bitset_windex wordno = bitno / BITSET_WORD_BITS;
+ bitset_windex offset = wordno - bset->b.cindex;
+
+ BITSET_STATS_RESETS_INC (bset);
+
+ if (offset < bset->b.csize)
+ {
+ bset->b.cdata[offset] &=
+ ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
+ BITSET_STATS_CACHE_RESETS_INC (bset);
+ }
+ else
+ BITSET_RESET_ (bset, bitno);
+}
+
+
+static bool
+bitset_stats_toggle (bitset src, bitset_bindex bitno)
+{
+ return BITSET_TOGGLE_ (src->s.bset, bitno);
+}
+
+
+static bool
+bitset_stats_test (bitset src, bitset_bindex bitno)
+{
+ bitset bset = src->s.bset;
+ bitset_windex wordno = bitno / BITSET_WORD_BITS;
+ bitset_windex offset = wordno - bset->b.cindex;
+
+ BITSET_STATS_TESTS_INC (bset);
+
+ if (offset < bset->b.csize)
+ {
+ BITSET_STATS_CACHE_TESTS_INC (bset);
+ return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
+ }
+ else
+ return BITSET_TEST_ (bset, bitno);
+}
+
+
+static bitset_bindex
+bitset_stats_resize (bitset src, bitset_bindex size)
+{
+ return BITSET_RESIZE_ (src->s.bset, size);
+}
+
+
+static bitset_bindex
+bitset_stats_size (bitset src)
+{
+ return BITSET_SIZE_ (src->s.bset);
+}
+
+
+static bitset_bindex
+bitset_stats_count (bitset src)
+{
+ return BITSET_COUNT_ (src->s.bset);
+}
+
+
+static bool
+bitset_stats_empty_p (bitset dst)
+{
+ return BITSET_EMPTY_P_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_ones (bitset dst)
+{
+ BITSET_ONES_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_zero (bitset dst)
+{
+ BITSET_ZERO_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_copy (bitset dst, bitset src)
+{
+ BITSET_CHECK2_ (dst, src);
+ BITSET_COPY_ (dst->s.bset, src->s.bset);
+}
+
+
+static bool
+bitset_stats_disjoint_p (bitset dst, bitset src)
+{
+ BITSET_CHECK2_ (dst, src);
+ return BITSET_DISJOINT_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static bool
+bitset_stats_equal_p (bitset dst, bitset src)
+{
+ BITSET_CHECK2_ (dst, src);
+ return BITSET_EQUAL_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static void
+bitset_stats_not (bitset dst, bitset src)
+{
+ BITSET_CHECK2_ (dst, src);
+ BITSET_NOT_ (dst->s.bset, src->s.bset);
+}
+
+
+static bool
+bitset_stats_subset_p (bitset dst, bitset src)
+{
+ BITSET_CHECK2_ (dst, src);
+ return BITSET_SUBSET_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static void
+bitset_stats_and (bitset dst, bitset src1, bitset src2)
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ BITSET_AND_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_andn (bitset dst, bitset src1, bitset src2)
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ BITSET_ANDN_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_ANDN_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_or (bitset dst, bitset src1, bitset src2)
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ BITSET_OR_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_xor (bitset dst, bitset src1, bitset src2)
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ BITSET_XOR_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+ BITSET_CHECK3_ (dst, src1, src2);
+ return BITSET_XOR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+ BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bool
+bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+ return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset,
src3->s.bset);
+}
+
+
+static void
+bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+ BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bool
+bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+ return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset,
src3->s.bset);
+}
+
+
+static void
+bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+ BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bool
+bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ BITSET_CHECK4_ (dst, src1, src2, src3);
+ return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset,
src3->s.bset);
+}
+
+
+static bitset_bindex
+bitset_stats_list (bitset bset, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ bitset_bindex count = BITSET_LIST_ (bset->s.bset, list, num, next);
+
+ BITSET_STATS_LISTS_INC (bset->s.bset);
+
+ /* Log histogram of number of set bits. */
+ {
+ bitset_bindex i;
+ bitset_bindex tmp;
+ 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->s.bset, i);
+ }
+
+ /* Log histogram of number of bits in set. */
+ bitset_bindex size = BITSET_SIZE_ (bset->s.bset);
+ {
+ bitset_bindex i;
+ bitset_bindex tmp;
+ 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->s.bset, i);
+ }
+
+ /* Histogram of fraction of bits set. */
+ {
+ bitset_bindex i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
+ if (i >= BITSET_DENSITY_BINS)
+ i = BITSET_DENSITY_BINS - 1;
+ BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i);
+ }
+ return count;
+}
+
+
+static bitset_bindex
+bitset_stats_list_reverse (bitset bset, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next);
+}
+
+
+static void
+bitset_stats_free (bitset bset)
+{
+ BITSET_STATS_FREES_INC (bset->s.bset);
+ BITSET_FREE_ (bset->s.bset);
+}
+
+
+struct bitset_vtable bitset_stats_vtable = {
+ bitset_stats_set,
+ bitset_stats_reset,
+ bitset_stats_toggle,
+ bitset_stats_test,
+ bitset_stats_resize,
+ bitset_stats_size,
+ bitset_stats_count,
+ bitset_stats_empty_p,
+ bitset_stats_ones,
+ bitset_stats_zero,
+ bitset_stats_copy,
+ bitset_stats_disjoint_p,
+ bitset_stats_equal_p,
+ bitset_stats_not,
+ bitset_stats_subset_p,
+ bitset_stats_and,
+ bitset_stats_and_cmp,
+ bitset_stats_andn,
+ bitset_stats_andn_cmp,
+ bitset_stats_or,
+ bitset_stats_or_cmp,
+ bitset_stats_xor,
+ bitset_stats_xor_cmp,
+ bitset_stats_and_or,
+ bitset_stats_and_or_cmp,
+ bitset_stats_andn_or,
+ bitset_stats_andn_or_cmp,
+ bitset_stats_or_and,
+ bitset_stats_or_and_cmp,
+ bitset_stats_list,
+ bitset_stats_list_reverse,
+ bitset_stats_free,
+ BITSET_STATS
+};
+
+
+/* Return enclosed bitset type. */
+enum bitset_type
+bitset_stats_type_get (bitset bset)
+{
+ return BITSET_TYPE_ (bset->s.bset);
+}
+
+
+size_t
+bitset_stats_bytes (void)
+{
+ return sizeof (struct bitset_stats_struct);
+}
+
+
+bitset
+bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
+{
+ bset->b.vtable = &bitset_stats_vtable;
+
+ /* Disable cache. */
+ bset->b.cindex = 0;
+ bset->b.csize = 0;
+ bset->b.cdata = 0;
+
+ BITSET_NBITS_ (bset) = n_bits;
+
+ /* Set up the actual bitset implementation that
+ we are a wrapper over. */
+ switch (type)
+ {
+ default:
+ abort ();
+
+ case BITSET_ARRAY:
+ {
+ size_t bytes = abitset_bytes (n_bits);
+ bset->s.bset = xcalloc (1, bytes);
+ abitset_init (bset->s.bset, n_bits);
+ }
+ break;
+
+ case BITSET_LIST:
+ {
+ size_t bytes = lbitset_bytes (n_bits);
+ bset->s.bset = xcalloc (1, bytes);
+ lbitset_init (bset->s.bset, n_bits);
+ }
+ break;
+
+ case BITSET_TABLE:
+ {
+ size_t bytes = ebitset_bytes (n_bits);
+ bset->s.bset = xcalloc (1, bytes);
+ ebitset_init (bset->s.bset, n_bits);
+ }
+ break;
+
+ case BITSET_VARRAY:
+ {
+ size_t bytes = vbitset_bytes (n_bits);
+ bset->s.bset = xcalloc (1, bytes);
+ vbitset_init (bset->s.bset, n_bits);
+ }
+ break;
+ }
+
+ BITSET_STATS_ALLOCS_INC (type);
+
+ return bset;
+}
diff --git a/lib/bitset/stats.h b/lib/bitset/stats.h
new file mode 100644
index 000000000..cd0da1c4e
--- /dev/null
+++ b/lib/bitset/stats.h
@@ -0,0 +1,34 @@
+/* Functions to support bitset statistics.
+
+ Copyright (C) 2002-2004, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _BITSET_STATS_H
+#define _BITSET_STATS_H
+
+#include "bitset/base.h"
+
+extern bool bitset_stats_enabled;
+
+enum bitset_type bitset_stats_type_get (bitset);
+
+size_t bitset_stats_bytes (void);
+
+bitset bitset_stats_init (bitset, bitset_bindex, enum bitset_type);
+
+#endif
diff --git a/lib/bitset/vector.c b/lib/bitset/vector.c
new file mode 100644
index 000000000..75e734505
--- /dev/null
+++ b/lib/bitset/vector.c
@@ -0,0 +1,988 @@
+/* Variable array bitsets.
+
+ Copyright (C) 2002-2006, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#include <config.h>
+
+#include "bitset/vector.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+/* This file implements variable size bitsets stored as a variable
+ length array of words. Any unused bits in the last word must be
+ zero.
+
+ Note that binary or ternary operations assume that each bitset operand
+ has the same size.
+*/
+
+static void vbitset_unused_clear (bitset);
+
+static void vbitset_set (bitset, bitset_bindex);
+static void vbitset_reset (bitset, bitset_bindex);
+static bool vbitset_test (bitset, bitset_bindex);
+static bitset_bindex vbitset_list (bitset, bitset_bindex *,
+ bitset_bindex, bitset_bindex *);
+static bitset_bindex vbitset_list_reverse (bitset, bitset_bindex *,
+ bitset_bindex, bitset_bindex *);
+
+#define VBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
+#define VBITSET_WORDS(X) ((X)->b.cdata)
+#define VBITSET_SIZE(X) ((X)->b.csize)
+#define VBITSET_ASIZE(X) ((X)->v.size)
+
+#undef min
+#undef max
+#define min(a, b) ((a) > (b) ? (b) : (a))
+#define max(a, b) ((a) > (b) ? (a) : (b))
+
+static bitset_bindex
+vbitset_resize (bitset src, bitset_bindex n_bits)
+{
+ if (n_bits == BITSET_NBITS_ (src))
+ return n_bits;
+
+ bitset_windex oldsize = VBITSET_SIZE (src);
+ bitset_windex newsize = VBITSET_N_WORDS (n_bits);
+
+ if (oldsize < newsize)
+ {
+ /* The bitset needs to grow. If we already have enough memory
+ allocated, then just zero what we need. */
+ if (newsize > VBITSET_ASIZE (src))
+ {
+ /* We need to allocate more memory. When oldsize is
+ non-zero this means that we are changing the size, so
+ grow the bitset 25% larger than requested to reduce
+ number of reallocations. */
+
+ bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
+ VBITSET_WORDS (src)
+ = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
+ VBITSET_ASIZE (src) = size;
+ }
+
+ memset (VBITSET_WORDS (src) + oldsize, 0,
+ (newsize - oldsize) * sizeof (bitset_word));
+ VBITSET_SIZE (src) = newsize;
+ }
+ else
+ {
+ /* The bitset needs to shrink. There's no point deallocating
+ the memory unless it is shrinking by a reasonable amount. */
+ if ((oldsize - newsize) >= oldsize / 2)
+ {
+ VBITSET_WORDS (src)
+ = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
+ VBITSET_ASIZE (src) = newsize;
+ }
+
+ /* Need to prune any excess bits. FIXME. */
+
+ VBITSET_SIZE (src) = newsize;
+ }
+
+ BITSET_NBITS_ (src) = n_bits;
+ return n_bits;
+}
+
+
+/* Set bit BITNO in bitset DST. */
+static void
+vbitset_set (bitset dst, bitset_bindex bitno)
+{
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+ /* Perhaps we should abort. The user should explicitly call
+ bitset_resize since this will not catch the case when we set a
+ bit larger than the current size but smaller than the allocated
+ size. */
+ vbitset_resize (dst, bitno);
+
+ dst->b.cdata[windex - dst->b.cindex] |=
+ (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
+}
+
+
+/* Reset bit BITNO in bitset DST. */
+static void
+vbitset_reset (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno
ATTRIBUTE_UNUSED)
+{
+ /* We must be accessing outside the cache so the bit is
+ zero anyway. */
+}
+
+
+/* Test bit BITNO in bitset SRC. */
+static bool
+vbitset_test (bitset src ATTRIBUTE_UNUSED,
+ bitset_bindex bitno ATTRIBUTE_UNUSED)
+{
+ /* We must be accessing outside the cache so the bit is
+ zero anyway. */
+ return false;
+}
+
+
+/* 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 bitset_bindex
+vbitset_list_reverse (bitset src, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ bitset_word *srcp = VBITSET_WORDS (src);
+ bitset_bindex n_bits = BITSET_SIZE_ (src);
+
+ bitset_bindex 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;
+
+ bitset_bindex count = 0;
+
+ bitset_bindex bitno = n_bits - (rbitno + 1);
+
+ bitset_windex windex = bitno / BITSET_WORD_BITS;
+ unsigned bitcnt = bitno % BITSET_WORD_BITS;
+ bitset_bindex bitoff = windex * BITSET_WORD_BITS;
+
+ do
+ {
+ bitset_word 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;
+ }
+ bitoff -= BITSET_WORD_BITS;
+ bitcnt = BITSET_WORD_BITS - 1;
+ }
+ while (windex--);
+
+ *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 bitset_bindex
+vbitset_list (bitset src, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
+{
+ bitset_windex size = VBITSET_SIZE (src);
+ bitset_word *srcp = VBITSET_WORDS (src);
+ bitset_bindex bitno = *next;
+ bitset_bindex count = 0;
+
+ bitset_windex windex;
+ bitset_bindex bitoff;
+ bitset_word word;
+
+ if (!bitno)
+ {
+ /* Many bitsets are zero, so make this common case fast. */
+ for (windex = 0; windex < size && !srcp[windex]; windex++)
+ continue;
+ if (windex >= size)
+ return 0;
+
+ /* If num is 1, we could speed things up with a binary search
+ of the current word. */
+
+ bitoff = windex * BITSET_WORD_BITS;
+ }
+ else
+ {
+ if (bitno >= BITSET_SIZE_ (src))
+ return 0;
+
+ windex = 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 = windex * BITSET_WORD_BITS;
+ word = srcp[windex] >> bitno;
+ for (bitno = bitoff + bitno; word; bitno++)
+ {
+ if (word & 1)
+ {
+ list[count++] = bitno;
+ if (count >= num)
+ {
+ *next = bitno + 1;
+ return count;
+ }
+ }
+ word >>= 1;
+ }
+ windex++;
+ }
+ bitoff = windex * BITSET_WORD_BITS;
+ }
+
+ for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
+ {
+ if (!(word = srcp[windex]))
+ 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
+vbitset_unused_clear (bitset dst)
+{
+ unsigned last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
+ if (last_bit)
+ VBITSET_WORDS (dst)[VBITSET_SIZE (dst) - 1] &=
+ ((bitset_word) 1 << last_bit) - 1;
+}
+
+
+static void
+vbitset_ones (bitset dst)
+{
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ unsigned bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
+
+ memset (dstp, -1, bytes);
+ vbitset_unused_clear (dst);
+}
+
+
+static void
+vbitset_zero (bitset dst)
+{
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ unsigned bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
+
+ memset (dstp, 0, bytes);
+}
+
+
+static bool
+vbitset_empty_p (bitset dst)
+{
+ bitset_word *dstp = VBITSET_WORDS (dst);
+
+ for (unsigned i = 0; i < VBITSET_SIZE (dst); i++)
+ if (dstp[i])
+ return false;
+ return true;
+}
+
+
+static void
+vbitset_copy1 (bitset dst, bitset src)
+{
+ if (src == dst)
+ return;
+
+ vbitset_resize (dst, BITSET_SIZE_ (src));
+
+ bitset_word *srcp = VBITSET_WORDS (src);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex ssize = VBITSET_SIZE (src);
+ bitset_windex dsize = VBITSET_SIZE (dst);
+
+ memcpy (dstp, srcp, sizeof (bitset_word) * ssize);
+
+ memset (dstp + sizeof (bitset_word) * ssize, 0,
+ sizeof (bitset_word) * (dsize - ssize));
+}
+
+
+static void
+vbitset_not (bitset dst, bitset src)
+{
+ vbitset_resize (dst, BITSET_SIZE_ (src));
+
+ bitset_word *srcp = VBITSET_WORDS (src);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex ssize = VBITSET_SIZE (src);
+ bitset_windex dsize = VBITSET_SIZE (dst);
+
+ for (unsigned i = 0; i < ssize; i++)
+ *dstp++ = ~(*srcp++);
+
+ vbitset_unused_clear (dst);
+ memset (dstp + sizeof (bitset_word) * ssize, 0,
+ sizeof (bitset_word) * (dsize - ssize));
+}
+
+
+static bool
+vbitset_equal_p (bitset dst, bitset src)
+{
+ bitset_word *srcp = VBITSET_WORDS (src);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex ssize = VBITSET_SIZE (src);
+ bitset_windex dsize = VBITSET_SIZE (dst);
+
+ unsigned i;
+ for (i = 0; i < min (ssize, dsize); i++)
+ if (*srcp++ != *dstp++)
+ return false;
+
+ if (ssize > dsize)
+ {
+ for (; i < ssize; i++)
+ if (*srcp++)
+ return false;
+ }
+ else
+ {
+ for (; i < dsize; i++)
+ if (*dstp++)
+ return false;
+ }
+
+ return true;
+}
+
+
+static bool
+vbitset_subset_p (bitset dst, bitset src)
+{
+ bitset_word *srcp = VBITSET_WORDS (src);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex ssize = VBITSET_SIZE (src);
+ bitset_windex dsize = VBITSET_SIZE (dst);
+
+ unsigned i;
+ for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++)
+ if (*dstp != (*srcp | *dstp))
+ return 0;
+
+ if (ssize > dsize)
+ {
+ for (; i < ssize; i++)
+ if (*srcp++)
+ return false;
+ }
+
+ return true;
+}
+
+
+static bool
+vbitset_disjoint_p (bitset dst, bitset src)
+{
+ bitset_word *srcp = VBITSET_WORDS (src);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex ssize = VBITSET_SIZE (src);
+ bitset_windex dsize = VBITSET_SIZE (dst);
+
+ for (unsigned i = 0; i < min (ssize, dsize); i++)
+ if (*srcp++ & *dstp++)
+ return false;
+
+ return true;
+}
+
+
+static void
+vbitset_and (bitset dst, bitset src1, bitset src2)
+{
+ vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+ bitset_windex dsize = VBITSET_SIZE (dst);
+ bitset_windex ssize1 = VBITSET_SIZE (src1);
+ bitset_windex ssize2 = VBITSET_SIZE (src2);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+
+ for (unsigned i = 0; i < min (ssize1, ssize2); i++)
+ *dstp++ = *src1p++ & *src2p++;
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2)));
+}
+
+
+static bool
+vbitset_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+ bool changed = false;
+ vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+ bitset_windex dsize = VBITSET_SIZE (dst);
+ bitset_windex ssize1 = VBITSET_SIZE (src1);
+ bitset_windex ssize2 = VBITSET_SIZE (src2);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+
+ unsigned i;
+ for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ & *src2p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+
+ if (ssize2 > ssize1)
+ {
+ src1p = src2p;
+ ssize1 = ssize2;
+ }
+
+ for (; i < ssize1; i++, dstp++)
+ {
+ if (*dstp != 0)
+ {
+ changed = true;
+ *dstp = 0;
+ }
+ }
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+
+ return changed;
+}
+
+
+static void
+vbitset_andn (bitset dst, bitset src1, bitset src2)
+{
+ vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+ bitset_windex dsize = VBITSET_SIZE (dst);
+ bitset_windex ssize1 = VBITSET_SIZE (src1);
+ bitset_windex ssize2 = VBITSET_SIZE (src2);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+
+ unsigned i;
+ for (i = 0; i < min (ssize1, ssize2); i++)
+ *dstp++ = *src1p++ & ~(*src2p++);
+
+ if (ssize2 > ssize1)
+ {
+ for (; i < ssize2; i++)
+ *dstp++ = 0;
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
+ }
+ else
+ {
+ for (; i < ssize1; i++)
+ *dstp++ = *src1p++;
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+ }
+}
+
+
+static bool
+vbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+ bool changed = false;
+ vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+ bitset_windex dsize = VBITSET_SIZE (dst);
+ bitset_windex ssize1 = VBITSET_SIZE (src1);
+ bitset_windex ssize2 = VBITSET_SIZE (src2);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+
+ unsigned i;
+ for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ & ~(*src2p++);
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+
+ if (ssize2 > ssize1)
+ {
+ for (; i < ssize2; i++, dstp++)
+ {
+ if (*dstp != 0)
+ {
+ changed = true;
+ *dstp = 0;
+ }
+ }
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
+ }
+ else
+ {
+ for (; i < ssize1; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+ }
+
+ return changed;
+}
+
+
+static void
+vbitset_or (bitset dst, bitset src1, bitset src2)
+{
+ vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+ bitset_windex dsize = VBITSET_SIZE (dst);
+ bitset_windex ssize1 = VBITSET_SIZE (src1);
+ bitset_windex ssize2 = VBITSET_SIZE (src2);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+
+ unsigned i;
+ for (i = 0; i < min (ssize1, ssize2); i++)
+ *dstp++ = *src1p++ | *src2p++;
+
+ if (ssize2 > ssize1)
+ {
+ src1p = src2p;
+ ssize1 = ssize2;
+ }
+
+ for (; i < ssize1; i++)
+ *dstp++ = *src1p++;
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+}
+
+
+static bool
+vbitset_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+ bool changed = false;
+
+ vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+ bitset_windex dsize = VBITSET_SIZE (dst);
+ bitset_windex ssize1 = VBITSET_SIZE (src1);
+ bitset_windex ssize2 = VBITSET_SIZE (src2);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+
+ unsigned i;
+ for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ | *src2p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+
+ if (ssize2 > ssize1)
+ {
+ src1p = src2p;
+ ssize1 = ssize2;
+ }
+
+ for (; i < ssize1; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+
+ return changed;
+}
+
+
+static void
+vbitset_xor (bitset dst, bitset src1, bitset src2)
+{
+ vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+ bitset_windex dsize = VBITSET_SIZE (dst);
+ bitset_windex ssize1 = VBITSET_SIZE (src1);
+ bitset_windex ssize2 = VBITSET_SIZE (src2);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+
+ unsigned i;
+ for (i = 0; i < min (ssize1, ssize2); i++)
+ *dstp++ = *src1p++ ^ *src2p++;
+
+ if (ssize2 > ssize1)
+ {
+ src1p = src2p;
+ ssize1 = ssize2;
+ }
+
+ for (; i < ssize1; i++)
+ *dstp++ = *src1p++;
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+}
+
+
+static bool
+vbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+ bool changed = false;
+ vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+ bitset_windex dsize = VBITSET_SIZE (dst);
+ bitset_windex ssize1 = VBITSET_SIZE (src1);
+ bitset_windex ssize2 = VBITSET_SIZE (src2);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+
+ unsigned i;
+ for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
+ {
+ bitset_word tmp = *src1p++ ^ *src2p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+
+ if (ssize2 > ssize1)
+ {
+ src1p = src2p;
+ ssize1 = ssize2;
+ }
+
+ for (; i < ssize1; i++, dstp++)
+ {
+ bitset_word tmp = *src1p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+
+ memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+
+ return changed;
+}
+
+
+/* FIXME, these operations need fixing for different size
+ bitsets. */
+
+static void
+vbitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+ || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+ {
+ bitset_and_or_ (dst, src1, src2, src3);
+ return;
+ }
+
+ vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+ bitset_word *src3p = VBITSET_WORDS (src3);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex size = VBITSET_SIZE (dst);
+
+ for (unsigned i = 0; i < size; i++)
+ *dstp++ = (*src1p++ & *src2p++) | *src3p++;
+}
+
+
+static bool
+vbitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+ || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+ return bitset_and_or_cmp_ (dst, src1, src2, src3);
+
+ vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+ bitset_word *src3p = VBITSET_WORDS (src3);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex size = VBITSET_SIZE (dst);
+
+ bool changed = false;
+ for (unsigned i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+vbitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+ || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+ {
+ bitset_andn_or_ (dst, src1, src2, src3);
+ return;
+ }
+
+ vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+ bitset_word *src3p = VBITSET_WORDS (src3);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex size = VBITSET_SIZE (dst);
+
+ for (unsigned i = 0; i < size; i++)
+ *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
+}
+
+
+static bool
+vbitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+ || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+ return bitset_andn_or_cmp_ (dst, src1, src2, src3);
+
+ vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+ bitset_word *src3p = VBITSET_WORDS (src3);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex size = VBITSET_SIZE (dst);
+
+ bool changed = false;
+ for (unsigned i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+vbitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+ || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+ {
+ bitset_or_and_ (dst, src1, src2, src3);
+ return;
+ }
+
+ vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+ bitset_word *src3p = VBITSET_WORDS (src3);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex size = VBITSET_SIZE (dst);
+
+ for (unsigned i = 0; i < size; i++)
+ *dstp++ = (*src1p++ | *src2p++) & *src3p++;
+}
+
+
+static bool
+vbitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+ if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+ || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+ return bitset_or_and_cmp_ (dst, src1, src2, src3);
+
+ vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+ bitset_word *src1p = VBITSET_WORDS (src1);
+ bitset_word *src2p = VBITSET_WORDS (src2);
+ bitset_word *src3p = VBITSET_WORDS (src3);
+ bitset_word *dstp = VBITSET_WORDS (dst);
+ bitset_windex size = VBITSET_SIZE (dst);
+
+ unsigned i;
+ bool changed = false;
+ for (i = 0; i < size; i++, dstp++)
+ {
+ bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
+
+ if (*dstp != tmp)
+ {
+ changed = true;
+ *dstp = tmp;
+ }
+ }
+ return changed;
+}
+
+
+static void
+vbitset_copy (bitset dst, bitset src)
+{
+ if (BITSET_COMPATIBLE_ (dst, src))
+ vbitset_copy1 (dst, src);
+ else
+ bitset_copy_ (dst, src);
+}
+
+
+/* Vector of operations for multiple word bitsets. */
+struct bitset_vtable vbitset_vtable = {
+ vbitset_set,
+ vbitset_reset,
+ bitset_toggle_,
+ vbitset_test,
+ vbitset_resize,
+ bitset_size_,
+ bitset_count_,
+ vbitset_empty_p,
+ vbitset_ones,
+ vbitset_zero,
+ vbitset_copy,
+ vbitset_disjoint_p,
+ vbitset_equal_p,
+ vbitset_not,
+ vbitset_subset_p,
+ vbitset_and,
+ vbitset_and_cmp,
+ vbitset_andn,
+ vbitset_andn_cmp,
+ vbitset_or,
+ vbitset_or_cmp,
+ vbitset_xor,
+ vbitset_xor_cmp,
+ vbitset_and_or,
+ vbitset_and_or_cmp,
+ vbitset_andn_or,
+ vbitset_andn_or_cmp,
+ vbitset_or_and,
+ vbitset_or_and_cmp,
+ vbitset_list,
+ vbitset_list_reverse,
+ NULL,
+ BITSET_VARRAY
+};
+
+
+size_t
+vbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
+{
+ return sizeof (struct vbitset_struct);
+}
+
+
+bitset
+vbitset_init (bitset bset, bitset_bindex n_bits)
+{
+ bset->b.vtable = &vbitset_vtable;
+ bset->b.cindex = 0;
+ VBITSET_SIZE (bset) = 0;
+ vbitset_resize (bset, n_bits);
+ return bset;
+}
diff --git a/lib/bitset/vector.h b/lib/bitset/vector.h
new file mode 100644
index 000000000..44b16b023
--- /dev/null
+++ b/lib/bitset/vector.h
@@ -0,0 +1,30 @@
+/* Functions to support vbitsets.
+
+ Copyright (C) 2002, 2004, 2009-2015, 2018 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 3 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, see <http://www.gnu.org/licenses/>. */
+
+#ifndef _BITSET_VECTOR_H
+#define _BITSET_VECTOR_H
+
+#include "bitset.h"
+
+size_t vbitset_bytes (bitset_bindex);
+
+bitset vbitset_init (bitset, bitset_bindex);
+
+#endif
diff --git a/modules/bitset b/modules/bitset
new file mode 100644
index 000000000..d77d35ed5
--- /dev/null
+++ b/modules/bitset
@@ -0,0 +1,35 @@
+Description:
+A common interface to several implementations of bitsets.
+
+Files:
+lib/bitset.c
+lib/bitset.h
+lib/bitset/array.c
+lib/bitset/array.h
+lib/bitset/base.h
+lib/bitset/expandable.c
+lib/bitset/expandable.h
+lib/bitset/list.c
+lib/bitset/list.h
+lib/bitset/stats.c
+lib/bitset/stats.h
+lib/bitset/vector.c
+lib/bitset/vector.h
+
+Depends-on:
+gettext-h
+obstack
+xalloc
+
+Makefile.am:
+lib_SOURCES += bitset.c bitset/array.c bitset/stats.c \
+ bitset/expandable.c bitset/list.c bitset/vector.c
+
+Include:
+"bitset.h"
+
+License:
+GPLv3+
+
+Maintainer:
+Akim Demaille <address@hidden>
Re: A new module: bitset, Akim Demaille, 2018/11/25
Re: A new module: bitset, Paul Eggert, 2018/11/25