X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/345cea780a4d3d11673c176cde39e20a043a1dea..fcbfa6b01c0222b01254730c66d539ed2c841a4e:/lib/ebitset.c diff --git a/lib/ebitset.c b/lib/ebitset.c index 3e84efa8..11b02c84 100644 --- a/lib/ebitset.c +++ b/lib/ebitset.c @@ -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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifdef HAVE_CONFIG_H @@ -37,20 +37,17 @@ 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. */ /* Number of words to use for each element. */ - -#ifndef EBITSET_ELT_WORDS #define EBITSET_ELT_WORDS 2 -#endif /* Number of bits stored in each element. */ #define EBITSET_ELT_BITS \ @@ -71,14 +68,6 @@ ebitset_elt; 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; - /* Number of elements to initially allocate. */ @@ -92,12 +81,6 @@ typedef struct ebitset_struct #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 }; @@ -108,35 +91,6 @@ static struct obstack ebitset_obstack; 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 int ebitset_equal_p PARAMS ((bitset, bitset)); -static void ebitset_copy PARAMS ((bitset, bitset)); -static int ebitset_copy_compare 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_op1 PARAMS ((bitset, enum bitset_ops)); -static int ebitset_op2 PARAMS ((bitset, bitset, enum bitset_ops)); -static int ebitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); -static int ebitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, - bitset_bindex *)); -static int ebitset_reverse_list -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) @@ -144,10 +98,10 @@ static void ebitset_free PARAMS ((bitset)); #define EBITSET_WORDS(ELT) ((ELT)->u.words) /* Disable bitset cache and mark BSET as being zero. */ -#define EBITSET_OP_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) \ @@ -155,9 +109,9 @@ static void ebitset_free PARAMS ((bitset)); /* 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_OP_ZERO_P(BSET) ((BSET)->b.cdata == 0) +#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, \ @@ -166,16 +120,17 @@ static void ebitset_free PARAMS ((bitset)); /* 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; @@ -186,7 +141,7 @@ ebitset_elts_grow (bset, size) /* Allocate a ebitset element. The bits are not cleared. */ static inline ebitset_elt * -ebitset_elt_alloc () +ebitset_elt_alloc (void) { ebitset_elt *elt; @@ -197,9 +152,6 @@ ebitset_elt_alloc () } else { - /* We can't use gcc_obstack_init to initialize the obstack since - print-rtl.c now calls bitset functions, and bitset is linked - into the gen* functions. */ if (!ebitset_obstack_init) { ebitset_obstack_init = 1; @@ -242,9 +194,9 @@ ebitset_elt_alloc () } -/* Allocate a ebitset element. The bits are not cleared. */ +/* Allocate a ebitset element. The bits are cleared. */ static inline ebitset_elt * -ebitset_elt_calloc () +ebitset_elt_calloc (void) { ebitset_elt *elt; @@ -255,8 +207,7 @@ ebitset_elt_calloc () 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; @@ -265,9 +216,7 @@ ebitset_elt_free (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; @@ -283,10 +232,7 @@ ebitset_elt_remove (bset, eindex) /* 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; @@ -298,8 +244,7 @@ ebitset_elt_add (bset, elt, eindex) /* 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; @@ -312,14 +257,12 @@ ebitset_elt_zero_p (elt) 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; @@ -349,7 +292,7 @@ ebitset_elt_find (bset, windex, mode) case EBITSET_CREATE: if (eindex >= size) { - unsigned int extra; + bitset_windex extra; extra = eindex - size + 1; @@ -380,8 +323,7 @@ ebitset_elt_find (bset, windex, mode) static inline ebitset_elt * -ebitset_elt_last (bset) - bitset bset; +ebitset_elt_last (bitset bset) { ebitset_elts *elts; @@ -393,15 +335,14 @@ ebitset_elt_last (bset) /* 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_OP_ZERO_P (bset)) + if (EBITSET_ZERO_P (bset)) return 0; elts = EBITSET_ELTS (bset); @@ -425,9 +366,9 @@ ebitset_weed (bset) 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_OP_ZERO_SET (bset); + EBITSET_ZERO_SET (bset); } else EBITSET_NONZERO_SET (bset); @@ -438,13 +379,12 @@ ebitset_weed (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; - if (EBITSET_OP_ZERO_P (bset)) + if (EBITSET_ZERO_P (bset)) return; elts = EBITSET_ELTS (bset); @@ -456,16 +396,14 @@ ebitset_zero (bset) 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_OP_ZERO_SET (bset); + 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; @@ -504,9 +442,7 @@ ebitset_equal_p (dst, src) /* 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; @@ -543,31 +479,28 @@ ebitset_copy (dst, src) /* Copy bits from bitset SRC to bitset DST. Return non-zero if bitsets different. */ static inline int -ebitset_copy_compare (dst, src) - bitset dst; - bitset src; +ebitset_copy_cmp (bitset dst, bitset src) { if (src == dst) return 0; - if (EBITSET_OP_ZERO_P (dst)) + if (EBITSET_ZERO_P (dst)) { - ebitset_copy (dst, src); - return !EBITSET_OP_ZERO_P (src); + ebitset_copy_ (dst, src); + return !EBITSET_ZERO_P (src); } if (ebitset_equal_p (dst, src)) return 0; - ebitset_copy (dst, src); + ebitset_copy_ (dst, src); return 1; } /* 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; @@ -576,32 +509,30 @@ ebitset_size (src) /* 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; ebitset_elt_find (dst, windex, EBITSET_CREATE); - dst->b.cdata[windex - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[windex - dst->b.cindex] |= + (bitset_word) 1 << (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; if (!ebitset_elt_find (dst, windex, EBITSET_FIND)) return; - dst->b.cdata[windex - dst->b.cindex] &= ~(1 << (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. */ } @@ -609,9 +540,7 @@ ebitset_reset (dst, bitno) /* 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; @@ -624,8 +553,7 @@ ebitset_test (src, bitno) static void -ebitset_free (bset) - bitset bset; +ebitset_free (bitset bset) { ebitset_zero (bset); free (EBITSET_ELTS (bset)); @@ -635,12 +563,9 @@ ebitset_free (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_reverse_list (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; @@ -648,14 +573,13 @@ ebitset_reverse_list (bset, list, num, next) unsigned int bcount; bitset_bindex boffset; bitset_windex windex; - unsigned int eindex; + bitset_windex eindex; bitset_windex woffset; bitset_bindex count; bitset_windex size; - bitset_word word; ebitset_elts *elts; - if (EBITSET_OP_ZERO_P (bset)) + if (EBITSET_ZERO_P (bset)) return 0; size = EBITSET_SIZE (bset); @@ -680,40 +604,45 @@ ebitset_reverse_list (bset, list, num, next) bcount = bitno % BITSET_WORD_BITS; boffset = windex * BITSET_WORD_BITS; - for (; eindex != ~0U; - boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS, eindex--) + do { ebitset_elt *elt; bitset_word *srcp; elt = elts[eindex]; - if (!elt) - continue; - - srcp = EBITSET_WORDS (elt); - - for (; woffset != ~0U; woffset--, boffset -= BITSET_WORD_BITS, - bcount = BITSET_WORD_BITS - 1) + if (elt) { - word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount); + srcp = EBITSET_WORDS (elt); - for (; word; bcount--) + do { - if (word & BITSET_MSB) + bitset_word word; + + word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount); + + for (; word; bcount--) { - list[count++] = boffset + bcount; - if (count >= num) + if (word & BITSET_MSB) { - *next = n_bits - (boffset + bcount); - return count; + list[count++] = boffset + bcount; + if (count >= num) + { + *next = n_bits - (boffset + bcount); + return count; + } } + word <<= 1; } - word <<= 1; + boffset -= BITSET_WORD_BITS; + bcount = BITSET_WORD_BITS - 1; } + while (woffset--); } - woffset = EBITSET_ELT_WORDS; + woffset = EBITSET_ELT_WORDS - 1; + boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS; } + while (eindex--); *next = n_bits - (boffset + 1); return count; @@ -723,23 +652,20 @@ ebitset_reverse_list (bset, list, num, next) /* 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 word; ebitset_elts *elts; - if (EBITSET_OP_ZERO_P (bset)) + if (EBITSET_ZERO_P (bset)) return 0; bitno = *next; @@ -760,7 +686,7 @@ ebitset_list (bset, list, num, next) 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++) { @@ -863,160 +789,137 @@ ebitset_list (bset, list, num, next) } -static int -ebitset_op1 (dst, op) - bitset dst; - enum bitset_ops op; +static void +ebitset_ones (bitset dst) { bitset_windex j; ebitset_elt *elt; - switch (op) + + for (j = 0; j < EBITSET_SIZE (dst); j++) { - case BITSET_OP_ZERO: - ebitset_zero (dst); - return 1; + /* Create new elements if they cannot be found. Perhaps + we should just add pointers to a ones element. */ + elt = + ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); + memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt))); + } + EBITSET_NONZERO_SET (dst); +} - case BITSET_OP_ONES: - 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. */ - elt = - ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); - memset (EBITSET_WORDS (elt), ~0, sizeof (EBITSET_WORDS (elt))); - } - break; - case BITSET_OP_EMPTY_P: - return !ebitset_weed (dst); +static int +ebitset_empty_p (bitset dst) +{ + return !ebitset_weed (dst); +} - default: - abort (); - } +static void +ebitset_not (bitset dst, bitset src) +{ + unsigned int i; + ebitset_elt *selt; + ebitset_elt *delt; + bitset_windex j; + + 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. */ + selt = + ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST); + delt = + ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); + + for (i = 0; i < EBITSET_ELT_WORDS; i++) + EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i]; + } EBITSET_NONZERO_SET (dst); - return 1; } +/* Return 1 if DST == DST | SRC. */ static int -ebitset_op2 (dst, src, op) - bitset dst; - bitset src; - enum bitset_ops op; +ebitset_subset_p (bitset dst, bitset src) { - ebitset_elt *selt; - ebitset_elt *delt; - unsigned int i; bitset_windex j; + ebitset_elts *selts; + ebitset_elts *delts; + bitset_windex ssize; + bitset_windex dsize; + + selts = EBITSET_ELTS (src); + delts = EBITSET_ELTS (dst); - switch (op) + ssize = EBITSET_SIZE (src); + dsize = EBITSET_SIZE (dst); + + for (j = 0; j < ssize; j++) { - case BITSET_OP_COPY: - ebitset_copy (dst, src); - break; + unsigned int i; + ebitset_elt *selt; + ebitset_elt *delt; - case BITSET_OP_NOT: - 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. */ - selt = - ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST); - delt = - ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE); + selt = j < ssize ? selts[j] : 0; + delt = j < dsize ? delts[j] : 0; - for (i = 0; i < EBITSET_ELT_WORDS; i++) - EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i]; - } - break; - - /* Return 1 if DST == SRC. */ - case BITSET_OP_EQUAL_P: - return ebitset_equal_p (dst, src); - - /* Return 1 if DST == DST | SRC. */ - case BITSET_OP_SUBSET_P: - { - 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++) - { - 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 0; - } - return 1; - } - break; - - /* Return 1 if DST & SRC == 0. */ - case BITSET_OP_DISJOINT_P: - { - 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++) - { - 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; - } - return 1; - } - break; + if (!selt && !delt) + continue; - default: - abort (); + 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 0; } + return 1; +} - EBITSET_NONZERO_SET (dst); + +/* Return 1 if DST & SRC == 0. */ +static int +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; + ebitset_elt *selt; + ebitset_elt *delt; + + 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; + } return 1; } + static int -ebitset_op3 (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; @@ -1032,37 +935,6 @@ ebitset_op3 (dst, src1, src2, op) unsigned int i; bitset_windex j; - /* Fast track common, simple cases. */ - if (EBITSET_OP_ZERO_P (src2)) - { - if (op == BITSET_OP_AND) - { - ebitset_weed (dst); - changed = EBITSET_OP_ZERO_P (dst); - ebitset_zero (dst); - return changed; - } - else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR - || op == BITSET_OP_XOR) - { - return ebitset_copy_compare (dst, src1); - } - } - else if (EBITSET_OP_ZERO_P (src1)) - { - if (op == BITSET_OP_AND || op == BITSET_OP_ANDN) - { - ebitset_weed (dst); - changed = EBITSET_OP_ZERO_P (dst); - ebitset_zero (dst); - return changed; - } - else if (op == BITSET_OP_OR || op == BITSET_OP_XOR) - { - return ebitset_copy_compare (dst, src2); - } - } - ssize1 = EBITSET_SIZE (src1); ssize2 = EBITSET_SIZE (src2); dsize = EBITSET_SIZE (dst); @@ -1195,46 +1067,174 @@ ebitset_op3 (dst, src1, src2, op) } +static int +ebitset_and_cmp (bitset dst, bitset src1, bitset src2) +{ + int changed; + + if (EBITSET_ZERO_P (src2)) + { + ebitset_weed (dst); + changed = EBITSET_ZERO_P (dst); + ebitset_zero (dst); + return changed; + } + else if (EBITSET_ZERO_P (src1)) + { + ebitset_weed (dst); + 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 int +ebitset_andn_cmp (bitset dst, bitset src1, bitset src2) +{ + int changed; + + if (EBITSET_ZERO_P (src2)) + { + return ebitset_copy_cmp (dst, src1); + } + else if (EBITSET_ZERO_P (src1)) + { + ebitset_weed (dst); + 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 int +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 int +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_ops_struct ebitset_ops = { +struct bitset_vtable ebitset_vtable = { ebitset_set, ebitset_reset, + bitset_toggle_, ebitset_test, ebitset_size, - ebitset_op1, - ebitset_op2, - ebitset_op3, - bitset_op4, + 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_reverse_list, + ebitset_list_reverse, ebitset_free, BITSET_TABLE }; /* 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.ops = &ebitset_ops; + bset->b.vtable = &ebitset_vtable; bset->b.csize = EBITSET_ELT_WORDS; - EBITSET_OP_ZERO_SET (bset); + EBITSET_ZERO_SET (bset); size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS : EBITSET_INITIAL_SIZE; @@ -1248,7 +1248,7 @@ ebitset_init (bset, n_bits) void -ebitset_release_memory () +ebitset_release_memory (void) { ebitset_free_list = 0; if (ebitset_obstack_init)