X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/75f10004fe0e192304073e4f65909aa43439ee79..a7db4add018f1136b01e11b4252df8b6a9ddbd4b:/lib/ebitset.c?ds=sidebyside diff --git a/lib/ebitset.c b/lib/ebitset.c index 11b02c84..9ac85a2c 100644 --- a/lib/ebitset.c +++ b/lib/ebitset.c @@ -1,5 +1,5 @@ /* Functions to support expandable bitsets. - Copyright (C) 2002 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005 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 @@ -14,7 +14,7 @@ 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifdef HAVE_CONFIG_H @@ -24,6 +24,7 @@ #include "ebitset.h" #include "obstack.h" #include +#include /* This file implements expandable bitsets. These bitsets can be of arbitrary length and are more efficient than arrays of bits for @@ -51,7 +52,7 @@ /* 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 @@ -75,11 +76,6 @@ typedef ebitset_elt *ebitset_elts; #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 }; @@ -88,11 +84,13 @@ static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits. */ /* Obstack to allocate bitset elements from. */ static struct obstack ebitset_obstack; -static int ebitset_obstack_init = 0; +static 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) @@ -117,25 +115,65 @@ static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */ ((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); - EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset), - newsize * sizeof (ebitset_elt *)); - EBITSET_SIZE (bset) = newsize; + 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; + } - memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *)); + 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; } @@ -154,7 +192,7 @@ ebitset_elt_alloc (void) { if (!ebitset_obstack_init) { - ebitset_obstack_init = 1; + ebitset_obstack_init = true; /* Let particular systems override the size of a chunk. */ @@ -178,9 +216,7 @@ ebitset_elt_alloc (void) obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE, __alignof__ (ebitset_elt), - (void *(*)PARAMS ((long))) OBSTACK_CHUNK_ALLOC, - (void (*)PARAMS ((void *))) OBSTACK_CHUNK_FREE); } @@ -242,22 +278,22 @@ ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex) } -/* 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; @@ -265,7 +301,7 @@ ebitset_elt_find (bitset bset, bitset_windex windex, bitset_windex eindex; ebitset_elts *elts; - eindex = windex / EBITSET_ELT_WORDS; + eindex = bindex / EBITSET_ELT_BITS; elts = EBITSET_ELTS (bset); size = EBITSET_SIZE (bset); @@ -291,21 +327,7 @@ ebitset_elt_find (bitset bset, bitset_windex windex, 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 (); @@ -322,18 +344,6 @@ ebitset_elt_find (bitset bset, bitset_windex windex, } -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) @@ -353,7 +363,7 @@ 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++; @@ -402,7 +412,7 @@ ebitset_zero (bitset bset) } -static inline int +static inline bool ebitset_equal_p (bitset dst, bitset src) { ebitset_elts *selts; @@ -410,13 +420,13 @@ ebitset_equal_p (bitset dst, bitset src) 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); @@ -430,13 +440,13 @@ ebitset_equal_p (bitset dst, bitset src) 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; } @@ -453,8 +463,8 @@ ebitset_copy_ (bitset dst, bitset src) 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); @@ -476,13 +486,13 @@ ebitset_copy_ (bitset dst, bitset src) } -/* 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)) { @@ -491,19 +501,10 @@ ebitset_copy_cmp (bitset dst, bitset src) } 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; } @@ -513,7 +514,7 @@ 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); @@ -526,7 +527,7 @@ ebitset_reset (bitset dst, bitset_bindex bitno) { 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] &= @@ -539,16 +540,15 @@ ebitset_reset (bitset dst, bitset_bindex bitno) /* 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)); } @@ -732,6 +732,48 @@ ebitset_list (bitset bset, bitset_bindex *list, { /* 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; @@ -757,6 +799,7 @@ ebitset_list (bitset bset, bitset_bindex *list, } } } +#endif } else { @@ -789,29 +832,91 @@ ebitset_list (bitset bset, bitset_bindex *list, } +/* 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; } @@ -823,24 +928,27 @@ ebitset_not (bitset dst, bitset src) 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; @@ -875,14 +983,14 @@ ebitset_subset_p (bitset dst, bitset src) 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; @@ -911,14 +1019,14 @@ ebitset_disjoint_p (bitset dst, bitset src) 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; @@ -931,10 +1039,12 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) 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); @@ -942,9 +1052,6 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) 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); @@ -963,7 +1070,7 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) { if (delt) { - changed = 1; + changed = true; ebitset_elt_remove (dst, j); } continue; @@ -990,7 +1097,7 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1003,7 +1110,7 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1016,7 +1123,7 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1029,7 +1136,7 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1054,7 +1161,7 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) { ebitset_elt *delt; - changed = 1; + changed = true; delt = delts[j]; @@ -1067,10 +1174,10 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) } -static int +static bool ebitset_and_cmp (bitset dst, bitset src1, bitset src2) { - int changed; + bool changed; if (EBITSET_ZERO_P (src2)) { @@ -1097,10 +1204,10 @@ ebitset_and (bitset dst, bitset src1, bitset src2) } -static int +static bool ebitset_andn_cmp (bitset dst, bitset src1, bitset src2) { - int changed; + bool changed; if (EBITSET_ZERO_P (src2)) { @@ -1124,7 +1231,7 @@ ebitset_andn (bitset dst, bitset src1, bitset src2) } -static int +static bool ebitset_or_cmp (bitset dst, bitset src1, bitset src2) { if (EBITSET_ZERO_P (src2)) @@ -1146,7 +1253,7 @@ ebitset_or (bitset dst, bitset src1, bitset src2) } -static int +static bool ebitset_xor_cmp (bitset dst, bitset src1, bitset src2) { if (EBITSET_ZERO_P (src2)) @@ -1184,7 +1291,8 @@ struct bitset_vtable ebitset_vtable = { ebitset_reset, bitset_toggle_, ebitset_test, - ebitset_size, + ebitset_resize, + bitset_size_, bitset_count_, ebitset_empty_p, ebitset_ones, @@ -1239,9 +1347,9 @@ ebitset_init (bitset bset, bitset_bindex n_bits) 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; } @@ -1253,7 +1361,7 @@ ebitset_release_memory (void) ebitset_free_list = 0; if (ebitset_obstack_init) { - ebitset_obstack_init = 0; + ebitset_obstack_init = false; obstack_free (&ebitset_obstack, NULL); } }