#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
#define EBITSET_INITIAL_SIZE 2
#endif
-/* Minimum number of elements to grow table. */
-
-#ifndef EBITSET_GROW_SIZE
-#define EBITSET_GROW_SIZE 4
-#endif
enum ebitset_find_mode
{ EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
static 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.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
-/* Grow the expandable table for BSET by SIZE elements. */
-static void
-ebitset_elts_grow (bitset bset, bitset_windex size)
+#define min(a, b) ((a) > (b) ? (b) : (a))
+#define max(a, b) ((a) > (b) ? (a) : (b))
+
+
+static bitset_bindex
+ebitset_resize (src, n_bits)
+ 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;
+
+ oldsize = EBITSET_SIZE (src);
+ newsize = EBITSET_N_ELTS (n_bits);
+
+ if (oldsize < newsize)
+ {
+ bitset_windex size;
+
+ /* 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;
+ }
- if (BITSET_SIZE_MAX / sizeof (ebitset_elt *) < newsize)
- xalloc_die ();
+ 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;
+ }
- EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset),
- newsize * sizeof (ebitset_elt *));
- EBITSET_SIZE (bset) = newsize;
+ /* Need to prune any excess bits. FIXME. */
+ }
- memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *));
+ BITSET_NBITS_ (src) = n_bits;
+ return n_bits;
}
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);
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 ();
}
-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++;
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);
}
-/* 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;
-}
-
-
/* 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, 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] &=
{
bitset_windex windex = bitno / BITSET_WORD_BITS;
- return (ebitset_elt_find (src, windex, EBITSET_FIND)
+ 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 (dst)
+ 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 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);
}
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);
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;
}
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
+#include <string.h>
/* This file implements linked-list bitsets. These bitsets can be of
arbitrary length and are more efficient than arrays of bits for
/* 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. */
+ 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
}
-/* Return size in bits of bitset SRC. */
static bitset_bindex
-lbitset_size (bitset src)
+lbitset_resize (bitset src, bitset_bindex size)
{
- lbitset_elt *elt;
-
- elt = LBITSET_TAIL (src);
- if (!elt)
- return 0;
+ BITSET_NBITS_ (src) = size;
- /* Return current size of bitset in bits. */
- return (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
+ /* Need to prune any excess bits. FIXME. */
+ return size;
}
-
/* Set bit BITNO in bitset DST. */
static void
lbitset_set (bitset dst, bitset_bindex bitno)
static bool
lbitset_empty_p (bitset dst)
{
- lbitset_weed (dst);
- return !LBITSET_HEAD (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 0;
+ /* Weed as we go. */
+ lbitset_elt_unlink (dst, elt);
+ }
+
+ return 1;
+}
+
+
+/* Ensure that any unused bits within the last element are clear. */
+static inline void
+lbitset_unused_clear (dst)
+ bitset dst;
+{
+ unsigned int last_bit;
+ bitset_bindex n_bits;
+
+ n_bits = BITSET_SIZE_ (dst);
+ last_bit = n_bits % LBITSET_ELT_BITS;
+
+ if (last_bit)
+ {
+ lbitset_elt *elt;
+ bitset_windex windex;
+ bitset_word *srcp;
+
+ elt = LBITSET_TAIL (dst);
+ srcp = elt->words;
+ 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;
+ }
}
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. */
- elt = LBITSET_TAIL (dst);
- /* Ignore empty set. */
- if (!elt)
- return;
- windex = elt->index;
+ windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
+
for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
{
/* Create new elements if they cannot be found. */
elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
memset (elt->words, -1, sizeof (elt->words));
}
+
+ lbitset_unused_clear (dst);
}
/* This is another unfriendly operation for a linked list
bitset! */
elt = LBITSET_TAIL (dst);
- /* Ignore empty set. */
- if (!elt)
- return;
- windex = elt->index;
+ windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
+
for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
{
/* Create new elements for dst if they cannot be found
for (j = 0; j < LBITSET_ELT_WORDS; j++)
delt->words[j] = ~selt->words[j];
}
+ lbitset_unused_clear (dst);
lbitset_weed (dst);
return;
}
lbitset_reset,
bitset_toggle_,
lbitset_test,
- lbitset_size,
+ lbitset_resize,
+ bitset_size_,
bitset_count_,
lbitset_empty_p,
lbitset_ones,
bitset
lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
{
+ BITSET_NBITS_ (bset) = n_bits;
bset->b.vtable = &lbitset_vtable;
return bset;
}
projects / bison.git / commitdiff
