/* Functions to support expandable bitsets.
- Copyright (C) 2002 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004, 2005, 2006, 2009 Free Software
+ Foundation, Inc.
Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
- This program is free software; you can redistribute it and/or modify
+ This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
+ the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-*/
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
+#include <config.h>
#include "ebitset.h"
+
#include "obstack.h"
#include <stdlib.h>
+#include <string.h>
/* This file implements expandable bitsets. These bitsets can be of
arbitrary length and are more efficient than arrays of bits for
/* Number of bits stored in each element. */
#define EBITSET_ELT_BITS \
- ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
+ ((unsigned int) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
/* Ebitset element. We use an array of bits. */
typedef struct ebitset_elt_struct
#define EBITSET_INITIAL_SIZE 2
#endif
-/* Minimum number of elements to grow table. */
-
-#ifndef EBITSET_GROW_SIZE
-#define EBITSET_GROW_SIZE 4
-#endif
enum ebitset_find_mode
{ EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
/* Obstack to allocate bitset elements from. */
static struct obstack ebitset_obstack;
-static int ebitset_obstack_init = 0;
+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) ((BSET)->e.size)
+#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)
((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))
-/* Grow the expandable table for BSET by SIZE elements. */
-static void
-ebitset_elts_grow (bitset bset, bitset_windex size)
+static bitset_bindex
+ebitset_resize (bitset src, bitset_bindex n_bits)
{
bitset_windex oldsize;
bitset_windex newsize;
- oldsize = EBITSET_SIZE (bset);
- newsize = oldsize + size;
+ if (n_bits == BITSET_NBITS_ (src))
+ return n_bits;
- if (BITSET_SIZE_MAX / sizeof (ebitset_elt *) < newsize)
- xalloc_die ();
+ oldsize = EBITSET_SIZE (src);
+ newsize = EBITSET_N_ELTS (n_bits);
+
+ if (oldsize < newsize)
+ {
+ bitset_windex size;
- EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset),
- newsize * sizeof (ebitset_elt *));
- EBITSET_SIZE (bset) = 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. */
+
+ if (oldsize == 0)
+ size = newsize;
+ else
+ size = 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;
+ }
- memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *));
+ /* Need to prune any excess bits. FIXME. */
+ }
+
+ BITSET_NBITS_ (src) = n_bits;
+ return n_bits;
}
{
if (!ebitset_obstack_init)
{
- ebitset_obstack_init = 1;
+ ebitset_obstack_init = true;
/* Let particular systems override the size of a chunk. */
#define OBSTACK_CHUNK_FREE free
#endif
-#if !defined(__GNUC__) || (__GNUC__ < 2)
+#if ! defined __GNUC__ || __GNUC__ < 2
#define __alignof__(type) 0
#endif
obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE,
__alignof__ (ebitset_elt),
- (void *(*)PARAMS ((long)))
OBSTACK_CHUNK_ALLOC,
- (void (*)PARAMS ((void *)))
OBSTACK_CHUNK_FREE);
}
}
-/* Return nonzero if all bits in an element are zero. */
-static inline int
+/* Are all bits in an element zero? */
+static inline bool
ebitset_elt_zero_p (ebitset_elt *elt)
{
int i;
for (i = 0; i < EBITSET_ELT_WORDS; i++)
if (EBITSET_WORDS (elt)[i])
- return 0;
+ return false;
- return 1;
+ return true;
}
static ebitset_elt *
-ebitset_elt_find (bitset bset, bitset_windex windex,
+ebitset_elt_find (bitset bset, bitset_bindex bindex,
enum ebitset_find_mode mode)
{
ebitset_elt *elt;
bitset_windex eindex;
ebitset_elts *elts;
- eindex = windex / EBITSET_ELT_WORDS;
+ eindex = bindex / EBITSET_ELT_BITS;
elts = EBITSET_ELTS (bset);
size = EBITSET_SIZE (bset);
switch (mode)
{
+ default:
+ abort ();
+
case EBITSET_FIND:
return 0;
case EBITSET_CREATE:
if (eindex >= size)
- {
- bitset_windex extra;
-
- extra = eindex - size + 1;
-
- /* We need to expand the table by EXTRA elements. It may be
- better with large bitsets to grow the number of
- elements by some fraction of the current size otherwise
- we can spend a lot of time slowly increasing the size of the
- bitset. */
- if (extra < EBITSET_GROW_SIZE)
- extra = EBITSET_GROW_SIZE;
-
- ebitset_elts_grow (bset, extra);
- }
+ ebitset_resize (bset, bindex);
/* Create a new element. */
elt = ebitset_elt_calloc ();
case EBITSET_SUBST:
return &ebitset_zero_elts[0];
-
- default:
- abort ();
}
}
-static inline ebitset_elt *
-ebitset_elt_last (bitset bset)
-{
- ebitset_elts *elts;
-
- elts = EBITSET_ELTS (bset);
-
- /* Assume that have at least one element in elts. */
- return elts[EBITSET_SIZE (bset) - 1];
-}
-
-
/* Weed out the zero elements from the elts. */
static inline bitset_windex
ebitset_weed (bitset bset)
if (elt)
{
- if (elt && ebitset_elt_zero_p (elt))
+ if (ebitset_elt_zero_p (elt))
{
ebitset_elt_remove (bset, j);
count++;
}
-static inline int
+static inline bool
ebitset_equal_p (bitset dst, bitset src)
{
ebitset_elts *selts;
bitset_windex j;
if (src == dst)
- return 1;
+ return true;
ebitset_weed (dst);
ebitset_weed (src);
if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
- return 0;
+ return false;
selts = EBITSET_ELTS (src);
delts = EBITSET_ELTS (dst);
if (!selt && !delt)
continue;
if ((selt && !delt) || (!selt && delt))
- return 0;
+ return false;
for (i = 0; i < EBITSET_ELT_WORDS; i++)
if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
- return 0;
+ return false;
}
- return 1;
+ return true;
}
ebitset_zero (dst);
- if (EBITSET_SIZE (dst) < EBITSET_SIZE (src))
- ebitset_elts_grow (dst, EBITSET_SIZE (src) - EBITSET_SIZE (dst));
+ if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src))
+ ebitset_resize (dst, BITSET_NBITS_ (src));
selts = EBITSET_ELTS (src);
delts = EBITSET_ELTS (dst);
}
-/* Copy bits from bitset SRC to bitset DST. Return non-zero if
+/* Copy bits from bitset SRC to bitset DST. Return true if
bitsets different. */
-static inline int
+static inline bool
ebitset_copy_cmp (bitset dst, bitset src)
{
if (src == dst)
- return 0;
+ return false;
if (EBITSET_ZERO_P (dst))
{
}
if (ebitset_equal_p (dst, src))
- return 0;
+ return false;
ebitset_copy_ (dst, src);
- return 1;
-}
-
-
-/* Return size in bits of bitset SRC. */
-static bitset_bindex
-ebitset_size (bitset src)
-{
- /* Return current size of bitset in bits. */
- return EBITSET_SIZE (src) * EBITSET_ELT_BITS;
+ return true;
}
{
bitset_windex windex = bitno / BITSET_WORD_BITS;
- ebitset_elt_find (dst, windex, EBITSET_CREATE);
+ ebitset_elt_find (dst, bitno, EBITSET_CREATE);
dst->b.cdata[windex - dst->b.cindex] |=
(bitset_word) 1 << (bitno % BITSET_WORD_BITS);
{
bitset_windex windex = bitno / BITSET_WORD_BITS;
- if (!ebitset_elt_find (dst, windex, EBITSET_FIND))
+ if (!ebitset_elt_find (dst, bitno, EBITSET_FIND))
return;
dst->b.cdata[windex - dst->b.cindex] &=
/* Test bit BITNO in bitset SRC. */
-static int
+static bool
ebitset_test (bitset src, bitset_bindex bitno)
{
bitset_windex windex = bitno / BITSET_WORD_BITS;
- if (!ebitset_elt_find (src, windex, EBITSET_FIND))
- return 0;
-
- return (src->b.
- cdata[windex - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
+ return (ebitset_elt_find (src, bitno, EBITSET_FIND)
+ && ((src->b.cdata[windex - src->b.cindex]
+ >> (bitno % BITSET_WORD_BITS))
+ & 1));
}
{
/* The coast is clear, plant boot! */
+#if EBITSET_ELT_WORDS == 2
+ word = srcp[0];
+ if (word)
+ {
+ if (!(word & 0xffff))
+ {
+ word >>= 16;
+ bitno += 16;
+ }
+ if (!(word & 0xff))
+ {
+ word >>= 8;
+ bitno += 8;
+ }
+ for (; word; bitno++)
+ {
+ if (word & 1)
+ list[count++] = bitno;
+ word >>= 1;
+ }
+ }
+ 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 (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
{
bitno = windex * BITSET_WORD_BITS;
}
}
}
+#endif
}
else
{
}
+/* Ensure that any unused bits within the last element are clear. */
+static inline void
+ebitset_unused_clear (bitset dst)
+{
+ unsigned int last_bit;
+ bitset_bindex n_bits;
+
+ n_bits = BITSET_NBITS_ (dst);
+ last_bit = n_bits % EBITSET_ELT_BITS;
+
+ if (last_bit)
+ {
+ bitset_windex eindex;
+ ebitset_elts *elts;
+ ebitset_elt *elt;
+
+ elts = EBITSET_ELTS (dst);
+
+ eindex = n_bits / EBITSET_ELT_BITS;
+
+ elt = elts[eindex];
+ if (elt)
+ {
+ bitset_windex windex;
+ bitset_windex woffset;
+ bitset_word *srcp = EBITSET_WORDS (elt);
+
+ windex = n_bits / BITSET_WORD_BITS;
+ 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)
{
bitset_windex j;
ebitset_elt *elt;
-
for (j = 0; j < EBITSET_SIZE (dst); j++)
{
/* Create new elements if they cannot be found. Perhaps
- we should just add pointers to a ones element. */
+ we should just add pointers to a ones element? */
elt =
- ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
+ 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 int
+static bool
ebitset_empty_p (bitset dst)
{
- return !ebitset_weed (dst);
+ ebitset_elts *elts;
+ bitset_windex j;
+
+ if (EBITSET_ZERO_P (dst))
+ return 1;
+
+ elts = EBITSET_ELTS (dst);
+ for (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;
}
ebitset_elt *delt;
bitset_windex j;
+ ebitset_resize (dst, BITSET_NBITS_ (src));
+
for (j = 0; j < EBITSET_SIZE (src); j++)
{
/* Create new elements for dst if they cannot be found
- or substitute zero elements if src elements not found. */
+ or substitute zero elements if src elements not found. */
selt =
- ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
+ ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_SUBST);
delt =
- ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
+ ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
for (i = 0; i < EBITSET_ELT_WORDS; i++)
EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
}
EBITSET_NONZERO_SET (dst);
+ ebitset_unused_clear (dst);
}
-/* Return 1 if DST == DST | SRC. */
-static int
+/* Is DST == DST | SRC? */
+static bool
ebitset_subset_p (bitset dst, bitset src)
{
bitset_windex j;
for (i = 0; i < EBITSET_ELT_WORDS; i++)
if (EBITSET_WORDS (delt)[i]
!= (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
- return 0;
+ return false;
}
- return 1;
+ return true;
}
-/* Return 1 if DST & SRC == 0. */
-static int
+/* Is DST & SRC == 0? */
+static bool
ebitset_disjoint_p (bitset dst, bitset src)
{
bitset_windex j;
for (i = 0; i < EBITSET_ELT_WORDS; i++)
if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
- return 0;
+ return false;
}
- return 1;
+ return true;
}
-static int
+static bool
ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
{
bitset_windex ssize1;
bitset_word *srcp1;
bitset_word *srcp2;
bitset_word *dstp;
- int changed = 0;
+ bool changed = false;
unsigned int i;
bitset_windex j;
+ ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));
+
ssize1 = EBITSET_SIZE (src1);
ssize2 = EBITSET_SIZE (src2);
dsize = EBITSET_SIZE (dst);
if (size < ssize2)
size = ssize2;
- if (size > dsize)
- ebitset_elts_grow (dst, size - dsize);
-
selts1 = EBITSET_ELTS (src1);
selts2 = EBITSET_ELTS (src2);
delts = EBITSET_ELTS (dst);
{
if (delt)
{
- changed = 1;
+ changed = true;
ebitset_elt_remove (dst, j);
}
continue;
dstp = EBITSET_WORDS (delt);
switch (op)
{
+ default:
+ abort ();
+
case BITSET_OP_OR:
for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
{
if (*dstp != tmp)
{
- changed = 1;
+ changed = true;
*dstp = tmp;
}
}
if (*dstp != tmp)
{
- changed = 1;
+ changed = true;
*dstp = tmp;
}
}
if (*dstp != tmp)
{
- changed = 1;
+ changed = true;
*dstp = tmp;
}
}
if (*dstp != tmp)
{
- changed = 1;
+ changed = true;
*dstp = tmp;
}
}
break;
-
- default:
- abort ();
}
if (!ebitset_elt_zero_p (delt))
{
ebitset_elt *delt;
- changed = 1;
+ changed = true;
delt = delts[j];
}
-static int
+static bool
ebitset_and_cmp (bitset dst, bitset src1, bitset src2)
{
- int changed;
+ bool changed;
if (EBITSET_ZERO_P (src2))
{
}
-static int
+static bool
ebitset_andn_cmp (bitset dst, bitset src1, bitset src2)
{
- int changed;
+ bool changed;
if (EBITSET_ZERO_P (src2))
{
}
-static int
+static bool
ebitset_or_cmp (bitset dst, bitset src1, bitset src2)
{
if (EBITSET_ZERO_P (src2))
}
-static int
+static bool
ebitset_xor_cmp (bitset dst, bitset src1, bitset src2)
{
if (EBITSET_ZERO_P (src2))
ebitset_reset,
bitset_toggle_,
ebitset_test,
- ebitset_size,
+ ebitset_resize,
+ bitset_size_,
bitset_count_,
ebitset_empty_p,
ebitset_ones,
size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS
: EBITSET_INITIAL_SIZE;
- EBITSET_SIZE (bset) = 0;
+ EBITSET_ASIZE (bset) = 0;
EBITSET_ELTS (bset) = 0;
- ebitset_elts_grow (bset, size);
+ ebitset_resize (bset, n_bits);
return bset;
}
ebitset_free_list = 0;
if (ebitset_obstack_init)
{
- ebitset_obstack_init = 0;
+ ebitset_obstack_init = false;
obstack_free (&ebitset_obstack, NULL);
}
}
projects / bison.git / blobdiff