X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/c837b82803719515392ef5c441cd1b94a6920f9d..09ccae9b18a7c09ebf7bb8df2a18c8c4a6def248:/lib/ebitset.c?ds=sidebyside diff --git a/lib/ebitset.c b/lib/ebitset.c index 9751e4dd..cdbbe2de 100644 --- a/lib/ebitset.c +++ b/lib/ebitset.c @@ -1,10 +1,10 @@ /* Functions to support expandable bitsets. - Copyright (C) 2002 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005, 2006 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, @@ -13,17 +13,15 @@ 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 . */ -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif +#include #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 @@ -37,12 +35,12 @@ 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. */ @@ -51,7 +49,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 @@ -68,14 +66,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. */ @@ -83,17 +73,6 @@ typedef struct ebitset_struct #define EBITSET_INITIAL_SIZE 2 #endif -/* Minimum number of elements to grow table. */ - -#ifndef EBITSET_GROW_SIZE -#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 }; @@ -102,49 +81,22 @@ 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. */ -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_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) /* 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) \ @@ -152,38 +104,79 @@ 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, \ (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 (bset, size) - bitset bset; - unsigned int size; +static bitset_bindex +ebitset_resize (bitset src, bitset_bindex n_bits) { - unsigned int oldsize; - unsigned int newsize; + bitset_windex oldsize; + bitset_windex newsize; + + if (n_bits == BITSET_NBITS_ (src)) + return n_bits; - oldsize = EBITSET_SIZE (bset); - newsize = oldsize + size; + 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; } /* Allocate a ebitset element. The bits are not cleared. */ static inline ebitset_elt * -ebitset_elt_alloc () +ebitset_elt_alloc (void) { ebitset_elt *elt; @@ -196,7 +189,7 @@ ebitset_elt_alloc () { if (!ebitset_obstack_init) { - ebitset_obstack_init = 1; + ebitset_obstack_init = true; /* Let particular systems override the size of a chunk. */ @@ -214,15 +207,13 @@ ebitset_elt_alloc () #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); } @@ -238,7 +229,7 @@ ebitset_elt_alloc () /* Allocate a ebitset element. The bits are cleared. */ static inline ebitset_elt * -ebitset_elt_calloc () +ebitset_elt_calloc (void) { ebitset_elt *elt; @@ -249,8 +240,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; @@ -259,9 +249,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; @@ -277,10 +265,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; @@ -290,33 +275,30 @@ 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; +/* 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 (bset, windex, mode) - bitset bset; - bitset_windex windex; - enum ebitset_find_mode mode; +ebitset_elt_find (bitset bset, bitset_bindex bindex, + 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; + eindex = bindex / EBITSET_ELT_BITS; elts = EBITSET_ELTS (bset); size = EBITSET_SIZE (bset); @@ -337,26 +319,15 @@ ebitset_elt_find (bset, windex, mode) switch (mode) { + default: + abort (); + case EBITSET_FIND: return 0; case EBITSET_CREATE: if (eindex >= size) - { - unsigned int 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 (); @@ -366,36 +337,19 @@ ebitset_elt_find (bset, windex, mode) case EBITSET_SUBST: return &ebitset_zero_elts[0]; - - default: - abort (); } } -static inline ebitset_elt * -ebitset_elt_last (bset) - 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 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); @@ -406,7 +360,7 @@ ebitset_weed (bset) if (elt) { - if (elt && ebitset_elt_zero_p (elt)) + if (ebitset_elt_zero_p (elt)) { ebitset_elt_remove (bset, j); count++; @@ -419,9 +373,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); @@ -432,13 +386,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); @@ -450,29 +403,27 @@ 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; +static inline bool +ebitset_equal_p (bitset dst, bitset src) { ebitset_elts *selts; ebitset_elts *delts; 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); @@ -486,21 +437,19 @@ ebitset_equal_p (dst, 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; } /* 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; @@ -511,8 +460,8 @@ ebitset_copy (dst, 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); @@ -534,49 +483,35 @@ ebitset_copy (dst, 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 -ebitset_copy_compare (dst, src) - bitset dst; - bitset src; +static inline bool +ebitset_copy_cmp (bitset dst, bitset src) { if (src == dst) - return 0; + return false; - 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; + return false; - ebitset_copy (dst, src); - return 1; -} - - -/* Return size in bits of bitset SRC. */ -static int -ebitset_size (src) - bitset src; -{ - /* Return current size of bitset in bits. */ - return EBITSET_SIZE (src) * EBITSET_ELT_BITS; + ebitset_copy_ (dst, src); + return true; } /* 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); + ebitset_elt_find (dst, bitno, EBITSET_CREATE); dst->b.cdata[windex - dst->b.cindex] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS); @@ -585,43 +520,37 @@ ebitset_set (dst, bitno) /* 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)) + if (!ebitset_elt_find (dst, bitno, EBITSET_FIND)) return; 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; +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)); } static void -ebitset_free (bset) - bitset bset; +ebitset_free (bitset bset) { ebitset_zero (bset); free (EBITSET_ELTS (bset)); @@ -631,12 +560,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; @@ -644,13 +570,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; ebitset_elts *elts; - if (EBITSET_OP_ZERO_P (bset)) + if (EBITSET_ZERO_P (bset)) return 0; size = EBITSET_SIZE (bset); @@ -678,12 +604,11 @@ ebitset_reverse_list (bset, list, num, next) do { ebitset_elt *elt; + bitset_word *srcp; elt = elts[eindex]; if (elt) { - bitset_word *srcp; - srcp = EBITSET_WORDS (elt); do @@ -705,15 +630,13 @@ ebitset_reverse_list (bset, list, num, next) } 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--); @@ -726,23 +649,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; @@ -763,7 +683,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++) { @@ -809,6 +729,48 @@ ebitset_list (bset, list, num, next) { /* 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; @@ -834,6 +796,7 @@ ebitset_list (bset, list, num, next) } } } +#endif } else { @@ -866,160 +829,202 @@ ebitset_list (bset, list, num, next) } -static int -ebitset_op1 (dst, op) - bitset dst; - enum bitset_ops op; +/* Ensure that any unused bits within the last element are clear. */ +static inline void +ebitset_unused_clear (bitset dst) { - bitset_windex j; - ebitset_elt *elt; + unsigned int last_bit; + bitset_bindex n_bits; - switch (op) + n_bits = BITSET_NBITS_ (dst); + last_bit = n_bits % EBITSET_ELT_BITS; + + if (last_bit) { - case BITSET_OP_ZERO: - ebitset_zero (dst); - return 1; + bitset_windex eindex; + ebitset_elts *elts; + ebitset_elt *elt; + + elts = EBITSET_ELTS (dst); - case BITSET_OP_ONES: - for (j = 0; j < EBITSET_SIZE (dst); j++) + eindex = n_bits / EBITSET_ELT_BITS; + + elt = elts[eindex]; + if (elt) { - /* 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))); - } - break; + bitset_windex windex; + bitset_windex woffset; + bitset_word *srcp = EBITSET_WORDS (elt); - case BITSET_OP_EMPTY_P: - return !ebitset_weed (dst); + windex = n_bits / BITSET_WORD_BITS; + woffset = eindex * EBITSET_ELT_WORDS; - default: - abort (); + 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? */ + elt = + 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) +{ + 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; } -static int -ebitset_op2 (dst, src, op) - bitset dst; - bitset src; - enum bitset_ops op; +static void +ebitset_not (bitset dst, bitset src) { + unsigned int i; ebitset_elt *selt; ebitset_elt *delt; - unsigned int i; bitset_windex j; - switch (op) + ebitset_resize (dst, BITSET_NBITS_ (src)); + + for (j = 0; j < EBITSET_SIZE (src); j++) { - case BITSET_OP_COPY: - ebitset_copy (dst, src); - break; + /* 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_BITS, EBITSET_SUBST); + delt = + ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE); - 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); - - 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; + for (i = 0; i < EBITSET_ELT_WORDS; i++) + EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i]; + } + EBITSET_NONZERO_SET (dst); + ebitset_unused_clear (dst); +} - default: - abort (); + +/* Is DST == DST | SRC? */ +static bool +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; + ebitset_elt *selt; + ebitset_elt *delt; + + 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 false; } + return true; +} - EBITSET_NONZERO_SET (dst); - return 1; + +/* Is DST & SRC == 0? */ +static bool +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 false; + } + return true; } -static int -ebitset_op3 (dst, src1, src2, op) - bitset dst; - bitset src1; - bitset src2; - enum bitset_ops op; + +static bool +ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) { bitset_windex ssize1; bitset_windex ssize2; @@ -1031,40 +1036,11 @@ ebitset_op3 (dst, src1, src2, op) bitset_word *srcp1; bitset_word *srcp2; bitset_word *dstp; - int changed = 0; + bool changed = false; 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); - } - } + ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2))); ssize1 = EBITSET_SIZE (src1); ssize2 = EBITSET_SIZE (src2); @@ -1073,9 +1049,6 @@ ebitset_op3 (dst, src1, src2, 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); @@ -1094,7 +1067,7 @@ ebitset_op3 (dst, src1, src2, op) { if (delt) { - changed = 1; + changed = true; ebitset_elt_remove (dst, j); } continue; @@ -1114,6 +1087,9 @@ ebitset_op3 (dst, src1, src2, op) dstp = EBITSET_WORDS (delt); switch (op) { + default: + abort (); + case BITSET_OP_OR: for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) { @@ -1121,7 +1097,7 @@ ebitset_op3 (dst, src1, src2, op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1134,7 +1110,7 @@ ebitset_op3 (dst, src1, src2, op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1147,7 +1123,7 @@ ebitset_op3 (dst, src1, src2, op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1160,14 +1136,11 @@ ebitset_op3 (dst, src1, src2, op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } break; - - default: - abort (); } if (!ebitset_elt_zero_p (delt)) @@ -1185,7 +1158,7 @@ ebitset_op3 (dst, src1, src2, op) { ebitset_elt *delt; - changed = 1; + changed = true; delt = delts[j]; @@ -1198,65 +1171,194 @@ ebitset_op3 (dst, src1, src2, op) } +static bool +ebitset_and_cmp (bitset dst, bitset src1, bitset src2) +{ + bool 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 bool +ebitset_andn_cmp (bitset dst, bitset src1, bitset src2) +{ + bool 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 bool +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 bool +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, + ebitset_resize, + bitset_size_, + 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; - EBITSET_SIZE (bset) = 0; + EBITSET_ASIZE (bset) = 0; EBITSET_ELTS (bset) = 0; - ebitset_elts_grow (bset, size); + ebitset_resize (bset, n_bits); return bset; } void -ebitset_release_memory () +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); } }