X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/52f8da14ea4bc92ead3a212e51ade03e6207129d..68f91d58f15abe21c65a8b4d7022ccb854c857dc:/lib/ebitset.c?ds=inline diff --git a/lib/ebitset.c b/lib/ebitset.c index 2d9493d5..9d9341fb 100644 --- a/lib/ebitset.c +++ b/lib/ebitset.c @@ -1,10 +1,12 @@ /* Functions to support expandable bitsets. - Copyright (C) 2002 Free Software Foundation, Inc. + + Copyright (C) 2002-2006, 2009-2013 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 +15,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 +37,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 - BITSET_WINDEX_MAX 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 +51,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,17 +68,6 @@ ebitset_elt; typedef ebitset_elt *ebitset_elts; -/* Head of ebitset linked list. */ -typedef struct ebitset_struct -{ - bitset_windex size; /* Number of elements. */ - ebitset_elts *elts; /* Expanding array of pointers to elements. */ -} -*ebitset; - - -typedef void(*PFV)(); - /* Number of elements to initially allocate. */ @@ -86,17 +75,6 @@ typedef void(*PFV)(); #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 }; @@ -105,52 +83,20 @@ 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, bitset_windex)); -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 *, bitset_windex)); -static void ebitset_elt_remove PARAMS ((bitset, bitset_windex)); -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 bitset_windex ebitset_weed PARAMS ((bitset)); -static void ebitset_zero PARAMS ((bitset)); -static void ebitset_copy_ PARAMS ((bitset, bitset)); -static int ebitset_copy_cmp 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 bitset_bindex ebitset_size PARAMS ((bitset)); -static int ebitset_disjoint_p PARAMS ((bitset, bitset)); -static int ebitset_equal_p PARAMS ((bitset, bitset)); -static void ebitset_not PARAMS ((bitset, bitset)); -static int ebitset_subset_p PARAMS ((bitset, bitset)); -static int ebitset_op3_cmp PARAMS ((bitset, bitset, bitset, enum bitset_ops)); -static int ebitset_and_cmp PARAMS ((bitset, bitset, bitset)); -static int ebitset_andn_cmp PARAMS ((bitset, bitset, bitset)); -static int ebitset_or_cmp PARAMS ((bitset, bitset, bitset)); -static int ebitset_xor_cmp PARAMS ((bitset, bitset, bitset)); -static bitset_bindex ebitset_list PARAMS ((bitset, bitset_bindex *, - bitset_bindex, bitset_bindex *)); -static bitset_bindex ebitset_list_reverse -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_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \ - (BSET)->b.cdata = 0) + (BSET)->b.cdata = 0) #define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX) @@ -162,39 +108,77 @@ static void ebitset_free PARAMS ((bitset)); This is non-zero only if we know for sure that the bitset is zero. */ #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; - 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; - memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *)); + /* 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; + } + + /* 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; @@ -207,7 +191,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. */ @@ -225,15 +209,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); } @@ -249,7 +231,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; @@ -260,8 +242,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; @@ -270,9 +251,7 @@ ebitset_elt_free (elt) /* Remove element with index EINDEX from bitset BSET. */ static inline void -ebitset_elt_remove (bset, eindex) - bitset bset; - bitset_windex eindex; +ebitset_elt_remove (bitset bset, bitset_windex eindex) { ebitset_elts *elts; ebitset_elt *elt; @@ -288,10 +267,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; - bitset_windex eindex; +ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex) { ebitset_elts *elts; @@ -301,33 +277,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; bitset_windex eindex; ebitset_elts *elts; - eindex = windex / EBITSET_ELT_WORDS; + eindex = bindex / EBITSET_ELT_BITS; elts = EBITSET_ELTS (bset); size = EBITSET_SIZE (bset); @@ -348,26 +321,15 @@ ebitset_elt_find (bset, windex, mode) 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 (); @@ -377,30 +339,13 @@ 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 bitset_windex -ebitset_weed (bset) - bitset bset; +ebitset_weed (bitset bset) { ebitset_elts *elts; bitset_windex j; @@ -417,7 +362,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++; @@ -430,7 +375,7 @@ 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_ZERO_SET (bset); } @@ -443,8 +388,7 @@ 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; @@ -461,29 +405,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_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); @@ -497,21 +439,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; @@ -522,8 +462,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); @@ -545,15 +485,13 @@ 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_cmp (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_ZERO_P (dst)) { @@ -562,32 +500,20 @@ ebitset_copy_cmp (dst, 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 (src) - bitset src; -{ - /* Return current size of bitset in bits. */ - return EBITSET_SIZE (src) * EBITSET_ELT_BITS; + 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); @@ -596,43 +522,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)); @@ -643,11 +563,8 @@ ebitset_free (bset) *NEXT and store in array LIST. Return with actual number of bits found and with *NEXT indicating where search stopped. */ static bitset_bindex -ebitset_list_reverse (bset, list, num, next) - bitset bset; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; +ebitset_list_reverse (bitset bset, bitset_bindex *list, + bitset_bindex num, bitset_bindex *next) { bitset_bindex n_bits; bitset_bindex bitno; @@ -690,18 +607,18 @@ ebitset_list_reverse (bset, list, num, next) { ebitset_elt *elt; bitset_word *srcp; - + elt = elts[eindex]; if (elt) - { + { srcp = EBITSET_WORDS (elt); - + do { bitset_word word; - + word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount); - + for (; word; bcount--) { if (word & BITSET_MSB) @@ -716,7 +633,7 @@ ebitset_list_reverse (bset, list, num, next) word <<= 1; } boffset -= BITSET_WORD_BITS; - bcount = BITSET_WORD_BITS - 1; + bcount = BITSET_WORD_BITS - 1; } while (woffset--); } @@ -735,11 +652,8 @@ ebitset_list_reverse (bset, list, num, next) *NEXT and store in array LIST. Return with actual number of bits found and with *NEXT indicating where search stopped. */ static bitset_bindex -ebitset_list (bset, list, num, next) - bitset bset; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; +ebitset_list (bitset bset, bitset_bindex *list, + bitset_bindex num, bitset_bindex *next) { bitset_bindex bitno; bitset_windex windex; @@ -771,7 +685,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++) { @@ -817,6 +731,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; @@ -842,6 +798,7 @@ ebitset_list (bset, list, num, next) } } } +#endif } else { @@ -874,78 +831,137 @@ ebitset_list (bset, list, num, next) } +/* 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 (dst) - bitset dst; +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 -ebitset_empty_p (dst) - bitset 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; } static void -ebitset_not (dst, src) - bitset dst; - bitset src; +ebitset_not (bitset dst, bitset src) { unsigned int i; ebitset_elt *selt; 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 -ebitset_subset_p (dst, src) - bitset dst; - bitset src; +/* 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; @@ -954,42 +970,40 @@ ebitset_subset_p (dst, src) 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 false; } - return 1; + return true; } -/* Return 1 if DST & SRC == 0. */ -static int -ebitset_disjoint_p (dst, src) - bitset dst; - bitset src; +/* 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; @@ -998,25 +1012,21 @@ ebitset_disjoint_p (dst, src) 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 false; } - return 1; + return true; } -static int -ebitset_op3_cmp (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; @@ -1028,10 +1038,12 @@ ebitset_op3_cmp (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; + ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2))); + ssize1 = EBITSET_SIZE (src1); ssize2 = EBITSET_SIZE (src2); dsize = EBITSET_SIZE (dst); @@ -1039,9 +1051,6 @@ ebitset_op3_cmp (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); @@ -1060,7 +1069,7 @@ ebitset_op3_cmp (dst, src1, src2, op) { if (delt) { - changed = 1; + changed = true; ebitset_elt_remove (dst, j); } continue; @@ -1080,6 +1089,9 @@ ebitset_op3_cmp (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++) { @@ -1087,7 +1099,7 @@ ebitset_op3_cmp (dst, src1, src2, op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1100,7 +1112,7 @@ ebitset_op3_cmp (dst, src1, src2, op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1113,7 +1125,7 @@ ebitset_op3_cmp (dst, src1, src2, op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } @@ -1126,14 +1138,11 @@ ebitset_op3_cmp (dst, src1, src2, op) if (*dstp != tmp) { - changed = 1; + changed = true; *dstp = tmp; } } break; - - default: - abort (); } if (!ebitset_elt_zero_p (delt)) @@ -1151,7 +1160,7 @@ ebitset_op3_cmp (dst, src1, src2, op) { ebitset_elt *delt; - changed = 1; + changed = true; delt = delts[j]; @@ -1164,13 +1173,10 @@ ebitset_op3_cmp (dst, src1, src2, op) } -static int -ebitset_and_cmp (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +static bool +ebitset_and_cmp (bitset dst, bitset src1, bitset src2) { - int changed; + bool changed; if (EBITSET_ZERO_P (src2)) { @@ -1190,13 +1196,17 @@ ebitset_and_cmp (dst, src1, src2) } -static int -ebitset_andn_cmp (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +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) { - int changed; + bool changed; if (EBITSET_ZERO_P (src2)) { @@ -1213,11 +1223,15 @@ ebitset_andn_cmp (dst, src1, src2) } -static int -ebitset_or_cmp (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +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)) { @@ -1231,11 +1245,15 @@ ebitset_or_cmp (dst, src1, src2) } -static int -ebitset_xor_cmp (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; +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)) { @@ -1250,9 +1268,14 @@ ebitset_xor_cmp (dst, src1, src2) static void -ebitset_copy (dst, src) - bitset dst; - bitset src; +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); @@ -1267,7 +1290,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, @@ -1277,19 +1301,19 @@ struct bitset_vtable ebitset_vtable = { ebitset_equal_p, ebitset_not, ebitset_subset_p, - (PFV) ebitset_and_cmp, + ebitset_and, ebitset_and_cmp, - (PFV) ebitset_andn_cmp, + ebitset_andn, ebitset_andn_cmp, - (PFV) ebitset_or_cmp, + ebitset_or, ebitset_or_cmp, - (PFV) ebitset_xor_cmp, + ebitset_xor, ebitset_xor_cmp, - (PFV) bitset_and_or_cmp_, + bitset_and_or_, bitset_and_or_cmp_, - (PFV) bitset_andn_or_cmp_, + bitset_andn_or_, bitset_andn_or_cmp_, - (PFV) bitset_or_and_cmp_, + bitset_or_and_, bitset_or_and_cmp_, ebitset_list, ebitset_list_reverse, @@ -1300,46 +1324,38 @@ struct bitset_vtable ebitset_vtable = { /* Return size of initial structure. */ size_t -ebitset_bytes (n_bits) - bitset_bindex n_bits ATTRIBUTE_UNUSED; +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) { - bitset_windex size; - bset->b.vtable = &ebitset_vtable; bset->b.csize = EBITSET_ELT_WORDS; 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); } }