You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#ifdef HAVE_CONFIG_H
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.
+ be zero.
The bitset cache can be disabled either by setting cindex to
- some large number or by setting csize to 0. Here
+ 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.
+ cdata is changed.
*/
typedef ebitset_elt *ebitset_elts;
-/* Head of ebitset linked list. */
-typedef struct ebitset_struct
-{
- unsigned int size; /* Number of elements. */
- ebitset_elts *elts; /* Expanding array of pointers to elements. */
-}
-*ebitset;
-
-
-typedef void(*PFV)();
-
/* Number of elements to initially allocate. */
#define EBITSET_GROW_SIZE 4
#endif
-struct bitset_struct
-{
- struct bbitset_struct b;
- struct ebitset_struct e;
-};
-
enum ebitset_find_mode
{ EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
static int ebitset_obstack_init = 0;
static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */
-static void ebitset_elts_grow PARAMS ((bitset, unsigned int));
-static ebitset_elt *ebitset_elt_alloc PARAMS ((void));
-static ebitset_elt *ebitset_elt_calloc PARAMS ((void));
-static void ebitset_elt_add PARAMS ((bitset, ebitset_elt *, unsigned int));
-static void ebitset_elt_remove PARAMS ((bitset, unsigned int));
-static void ebitset_elt_free PARAMS ((ebitset_elt *));
-static ebitset_elt *ebitset_elt_find PARAMS ((bitset, bitset_windex,
- enum ebitset_find_mode));
-static ebitset_elt *ebitset_elt_last PARAMS ((bitset));
-static int ebitset_elt_zero_p PARAMS ((ebitset_elt *));
-
-static int ebitset_weed PARAMS ((bitset));
-static void ebitset_zero PARAMS ((bitset));
-static void ebitset_copy_ PARAMS ((bitset, bitset));
-static int ebitset_copy_cmp PARAMS ((bitset, bitset));
-static void ebitset_set PARAMS ((bitset, bitset_bindex));
-static void ebitset_reset PARAMS ((bitset, bitset_bindex));
-static int ebitset_test PARAMS ((bitset, bitset_bindex));
-static int ebitset_size PARAMS ((bitset));
-static int ebitset_disjoint_p PARAMS ((bitset, bitset));
-static int ebitset_equal_p PARAMS ((bitset, bitset));
-static void ebitset_not PARAMS ((bitset, bitset));
-static int ebitset_subset_p PARAMS ((bitset, bitset));
-static int ebitset_op3_cmp PARAMS ((bitset, bitset, bitset, enum bitset_ops));
-static int ebitset_and_cmp PARAMS ((bitset, bitset, bitset));
-static int ebitset_andn_cmp PARAMS ((bitset, bitset, bitset));
-static int ebitset_or_cmp PARAMS ((bitset, bitset, bitset));
-static int ebitset_xor_cmp PARAMS ((bitset, bitset, bitset));
-static int ebitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *));
-static int ebitset_list_reverse
-PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
-static void ebitset_free PARAMS ((bitset));
-
#define EBITSET_ELTS(BSET) ((BSET)->e.elts)
#define EBITSET_SIZE(BSET) ((BSET)->e.size)
#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_INDEX_MAX, \
- (BSET)->b.cdata = 0)
+#define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \
+ (BSET)->b.cdata = 0)
-#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX)
+#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) \
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.
+/* 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, \
/* Grow the expandable table for BSET by SIZE elements. */
static void
-ebitset_elts_grow (bset, size)
- bitset bset;
- unsigned int size;
+ebitset_elts_grow (bitset bset, bitset_windex size)
{
- unsigned int oldsize;
- unsigned int newsize;
+ bitset_windex oldsize;
+ bitset_windex newsize;
oldsize = EBITSET_SIZE (bset);
newsize = oldsize + size;
+ if (BITSET_SIZE_MAX / sizeof (ebitset_elt *) < newsize)
+ xalloc_die ();
+
EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset),
newsize * sizeof (ebitset_elt *));
EBITSET_SIZE (bset) = newsize;
/* Allocate a ebitset element. The bits are not cleared. */
static inline ebitset_elt *
-ebitset_elt_alloc ()
+ebitset_elt_alloc (void)
{
ebitset_elt *elt;
/* Allocate a ebitset element. The bits are cleared. */
static inline ebitset_elt *
-ebitset_elt_calloc ()
+ebitset_elt_calloc (void)
{
ebitset_elt *elt;
static inline void
-ebitset_elt_free (elt)
- ebitset_elt *elt;
+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 (bset, eindex)
- bitset bset;
- unsigned int eindex;
+ebitset_elt_remove (bitset bset, bitset_windex eindex)
{
ebitset_elts *elts;
ebitset_elt *elt;
/* Add ELT into elts at index EINDEX of bitset BSET. */
static inline void
-ebitset_elt_add (bset, elt, eindex)
- bitset bset;
- ebitset_elt *elt;
- unsigned int eindex;
+ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex)
{
ebitset_elts *elts;
/* Return nonzero if all bits in an element are zero. */
static inline int
-ebitset_elt_zero_p (elt)
- ebitset_elt *elt;
+ebitset_elt_zero_p (ebitset_elt *elt)
{
int i;
static ebitset_elt *
-ebitset_elt_find (bset, windex, mode)
- bitset bset;
- bitset_windex windex;
- enum ebitset_find_mode mode;
+ebitset_elt_find (bitset bset, bitset_windex windex,
+ enum ebitset_find_mode mode)
{
ebitset_elt *elt;
bitset_windex size;
- unsigned int eindex;
+ bitset_windex eindex;
ebitset_elts *elts;
eindex = windex / EBITSET_ELT_WORDS;
case EBITSET_CREATE:
if (eindex >= size)
{
- unsigned int extra;
+ bitset_windex extra;
extra = eindex - size + 1;
static inline ebitset_elt *
-ebitset_elt_last (bset)
- bitset bset;
+ebitset_elt_last (bitset bset)
{
ebitset_elts *elts;
/* Weed out the zero elements from the elts. */
-static inline int
-ebitset_weed (bset)
- bitset bset;
+static inline bitset_windex
+ebitset_weed (bitset bset)
{
ebitset_elts *elts;
bitset_windex j;
- int count;
+ bitset_windex count;
if (EBITSET_ZERO_P (bset))
return 0;
count = j - count;
if (!count)
{
- /* All the bits are zero. We could shrink the elts.
+ /* All the bits are zero. We could shrink the elts.
For now just mark BSET as known to be zero. */
EBITSET_ZERO_SET (bset);
}
/* Set all bits in the bitset to zero. */
static inline void
-ebitset_zero (bset)
- bitset bset;
+ebitset_zero (bitset bset)
{
ebitset_elts *elts;
bitset_windex j;
ebitset_elt_remove (bset, j);
}
- /* All the bits are zero. We could shrink the elts.
+ /* All the bits are zero. We could shrink the elts.
For now just mark BSET as known to be zero. */
EBITSET_ZERO_SET (bset);
}
static inline int
-ebitset_equal_p (dst, src)
- bitset dst;
- bitset src;
+ebitset_equal_p (bitset dst, bitset src)
{
ebitset_elts *selts;
ebitset_elts *delts;
/* Copy bits from bitset SRC to bitset DST. */
static inline void
-ebitset_copy_ (dst, src)
- bitset dst;
- bitset src;
+ebitset_copy_ (bitset dst, bitset src)
{
ebitset_elts *selts;
ebitset_elts *delts;
/* Copy bits from bitset SRC to bitset DST. Return non-zero if
bitsets different. */
static inline int
-ebitset_copy_cmp (dst, src)
- bitset dst;
- bitset src;
+ebitset_copy_cmp (bitset dst, bitset src)
{
if (src == dst)
return 0;
/* Return size in bits of bitset SRC. */
-static int
-ebitset_size (src)
- bitset src;
+static bitset_bindex
+ebitset_size (bitset src)
{
/* Return current size of bitset in bits. */
return EBITSET_SIZE (src) * EBITSET_ELT_BITS;
/* Set bit BITNO in bitset DST. */
static void
-ebitset_set (dst, bitno)
- bitset dst;
- bitset_bindex bitno;
+ebitset_set (bitset dst, bitset_bindex bitno)
{
bitset_windex windex = bitno / BITSET_WORD_BITS;
/* Reset bit BITNO in bitset DST. */
static void
-ebitset_reset (dst, bitno)
- bitset dst;
- bitset_bindex bitno;
+ebitset_reset (bitset dst, bitset_bindex bitno)
{
bitset_windex windex = bitno / BITSET_WORD_BITS;
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...
+ /* 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 int
-ebitset_test (src, bitno)
- bitset src;
- bitset_bindex bitno;
+ebitset_test (bitset src, bitset_bindex bitno)
{
bitset_windex windex = bitno / BITSET_WORD_BITS;
static void
-ebitset_free (bset)
- bitset bset;
+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 int
-ebitset_list_reverse (bset, list, num, next)
- bitset bset;
- bitset_bindex *list;
- bitset_bindex num;
- bitset_bindex *next;
+static bitset_bindex
+ebitset_list_reverse (bitset bset, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
{
bitset_bindex n_bits;
bitset_bindex bitno;
unsigned int bcount;
bitset_bindex boffset;
bitset_windex windex;
- unsigned int eindex;
+ bitset_windex eindex;
bitset_windex woffset;
bitset_bindex count;
bitset_windex size;
{
ebitset_elt *elt;
bitset_word *srcp;
-
+
elt = elts[eindex];
if (elt)
- {
+ {
srcp = EBITSET_WORDS (elt);
-
+
do
{
bitset_word word;
-
+
word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
-
+
for (; word; bcount--)
{
if (word & BITSET_MSB)
word <<= 1;
}
boffset -= BITSET_WORD_BITS;
- bcount = BITSET_WORD_BITS - 1;
+ bcount = BITSET_WORD_BITS - 1;
}
while (woffset--);
}
/* Find list of up to NUM bits set in BSET starting from and including
*NEXT and store in array LIST. Return with actual number of bits
found and with *NEXT indicating where search stopped. */
-static int
-ebitset_list (bset, list, num, next)
- bitset bset;
- bitset_bindex *list;
- bitset_bindex num;
- bitset_bindex *next;
+static bitset_bindex
+ebitset_list (bitset bset, bitset_bindex *list,
+ bitset_bindex num, bitset_bindex *next)
{
bitset_bindex bitno;
bitset_windex windex;
- unsigned int eindex;
+ bitset_windex eindex;
bitset_bindex count;
bitset_windex size;
ebitset_elt *elt;
bitset_word *srcp = EBITSET_WORDS (elt);
windex = bitno / BITSET_WORD_BITS;
- woffset = eindex / EBITSET_ELT_WORDS;
+ woffset = eindex * EBITSET_ELT_WORDS;
for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
{
static void
-ebitset_ones (dst)
- bitset dst;
+ebitset_ones (bitset dst)
{
bitset_windex j;
ebitset_elt *elt;
static int
-ebitset_empty_p (dst)
- bitset dst;
+ebitset_empty_p (bitset dst)
{
return !ebitset_weed (dst);
}
static void
-ebitset_not (dst, src)
- bitset dst;
- bitset src;
+ebitset_not (bitset dst, bitset src)
{
unsigned int i;
ebitset_elt *selt;
EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
}
EBITSET_NONZERO_SET (dst);
-}
+}
/* Return 1 if DST == DST | SRC. */
static int
-ebitset_subset_p (dst, src)
- bitset dst;
- bitset src;
+ebitset_subset_p (bitset dst, bitset src)
{
bitset_windex j;
ebitset_elts *selts;
ebitset_elts *delts;
bitset_windex ssize;
bitset_windex dsize;
-
+
selts = EBITSET_ELTS (src);
delts = EBITSET_ELTS (dst);
-
+
ssize = EBITSET_SIZE (src);
dsize = EBITSET_SIZE (dst);
-
+
for (j = 0; j < ssize; j++)
{
unsigned int i;
selt = j < ssize ? selts[j] : 0;
delt = j < dsize ? delts[j] : 0;
-
+
if (!selt && !delt)
continue;
-
+
if (!selt)
selt = &ebitset_zero_elts[0];
if (!delt)
delt = &ebitset_zero_elts[0];
-
+
for (i = 0; i < EBITSET_ELT_WORDS; i++)
if (EBITSET_WORDS (delt)[i]
!= (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
/* Return 1 if DST & SRC == 0. */
static int
-ebitset_disjoint_p (dst, src)
- bitset dst;
- bitset src;
+ebitset_disjoint_p (bitset dst, bitset src)
{
bitset_windex j;
ebitset_elts *selts;
ebitset_elts *delts;
bitset_windex ssize;
bitset_windex dsize;
-
+
selts = EBITSET_ELTS (src);
delts = EBITSET_ELTS (dst);
-
+
ssize = EBITSET_SIZE (src);
dsize = EBITSET_SIZE (dst);
-
+
for (j = 0; j < ssize; j++)
{
unsigned int i;
selt = j < ssize ? selts[j] : 0;
delt = j < dsize ? delts[j] : 0;
-
+
if (!selt || !delt)
continue;
-
+
for (i = 0; i < EBITSET_ELT_WORDS; i++)
if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
return 0;
static int
-ebitset_op3_cmp (dst, src1, src2, op)
- bitset dst;
- bitset src1;
- bitset src2;
- enum bitset_ops op;
+ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
{
bitset_windex ssize1;
bitset_windex ssize2;
static int
-ebitset_and_cmp (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
+ebitset_and_cmp (bitset dst, bitset src1, bitset src2)
{
int changed;
}
+static void
+ebitset_and (bitset dst, bitset src1, bitset src2)
+{
+ ebitset_and_cmp (dst, src1, src2);
+}
+
+
static int
-ebitset_andn_cmp (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
+ebitset_andn_cmp (bitset dst, bitset src1, bitset src2)
{
int changed;
}
+static void
+ebitset_andn (bitset dst, bitset src1, bitset src2)
+{
+ ebitset_andn_cmp (dst, src1, src2);
+}
+
+
static int
-ebitset_or_cmp (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
+ebitset_or_cmp (bitset dst, bitset src1, bitset src2)
{
if (EBITSET_ZERO_P (src2))
{
}
+static void
+ebitset_or (bitset dst, bitset src1, bitset src2)
+{
+ ebitset_or_cmp (dst, src1, src2);
+}
+
+
static int
-ebitset_xor_cmp (dst, src1, src2)
- bitset dst;
- bitset src1;
- bitset src2;
+ebitset_xor_cmp (bitset dst, bitset src1, bitset src2)
{
if (EBITSET_ZERO_P (src2))
{
static void
-ebitset_copy (dst, src)
- bitset dst;
- bitset src;
+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);
ebitset_equal_p,
ebitset_not,
ebitset_subset_p,
- (PFV) ebitset_and_cmp,
+ ebitset_and,
ebitset_and_cmp,
- (PFV) ebitset_andn_cmp,
+ ebitset_andn,
ebitset_andn_cmp,
- (PFV) ebitset_or_cmp,
+ ebitset_or,
ebitset_or_cmp,
- (PFV) ebitset_xor_cmp,
+ ebitset_xor,
ebitset_xor_cmp,
- (PFV) bitset_and_or_cmp_,
+ bitset_and_or_,
bitset_and_or_cmp_,
- (PFV) bitset_andn_or_cmp_,
+ bitset_andn_or_,
bitset_andn_or_cmp_,
- (PFV) bitset_or_and_cmp_,
+ bitset_or_and_,
bitset_or_and_cmp_,
ebitset_list,
ebitset_list_reverse,
/* Return size of initial structure. */
-int
-ebitset_bytes (n_bits)
- bitset_bindex n_bits ATTRIBUTE_UNUSED;
+size_t
+ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
{
- return sizeof (struct bitset_struct);
+ return sizeof (struct ebitset_struct);
}
/* Initialize a bitset. */
bitset
-ebitset_init (bset, n_bits)
- bitset bset;
- bitset_bindex n_bits;
+ebitset_init (bitset bset, bitset_bindex n_bits)
{
- unsigned int size;
+ bitset_windex size;
bset->b.vtable = &ebitset_vtable;
void
-ebitset_release_memory ()
+ebitset_release_memory (void)
{
ebitset_free_list = 0;
if (ebitset_obstack_init)
projects / bison.git / blobdiff