X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/345cea780a4d3d11673c176cde39e20a043a1dea..ccdc1577ef7fb32a5e30cb655337e7cd42b98987:/lib/ebitset.c?ds=inline diff --git a/lib/ebitset.c b/lib/ebitset.c index 3e84efa8..77cc7a01 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-2012 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,31 +37,28 @@ 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 \ - ((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 { union { - bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */ + bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */ struct ebitset_elt_struct *next; } u; @@ -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. */ @@ -86,17 +75,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 }; @@ -105,49 +83,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 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)); +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) /* Disable bitset cache and mark BSET as being zero. */ -#define EBITSET_OP_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX, \ +#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,38 +106,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 (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. */ + } - memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *)); + 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; @@ -197,20 +189,17 @@ 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; + { + ebitset_obstack_init = true; - /* Let particular systems override the size of a chunk. */ + /* Let particular systems override the size of a chunk. */ #ifndef OBSTACK_CHUNK_SIZE #define OBSTACK_CHUNK_SIZE 0 #endif - /* Let them override the alloc and free routines too. */ + /* Let them override the alloc and free routines too. */ #ifndef OBSTACK_CHUNK_ALLOC #define OBSTACK_CHUNK_ALLOC xmalloc @@ -220,31 +209,29 @@ 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); - } + obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE, + __alignof__ (ebitset_elt), + OBSTACK_CHUNK_ALLOC, + OBSTACK_CHUNK_FREE); + } /* Perhaps we should add a number of new elements to the free - list. */ + list. */ elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack, - sizeof (ebitset_elt)); + sizeof (ebitset_elt)); } return elt; } -/* 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 +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; @@ -265,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; - unsigned int eindex; +ebitset_elt_remove (bitset bset, bitset_windex eindex) { ebitset_elts *elts; ebitset_elt *elt; @@ -283,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; - unsigned int eindex; +ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex) { ebitset_elts *elts; @@ -296,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; - 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); @@ -330,39 +308,28 @@ ebitset_elt_find (bset, windex, mode) if (eindex < size) { if ((elt = elts[eindex])) - { - if (EBITSET_WORDS (elt) == bset->b.cdata) - return elt; + { + if (EBITSET_WORDS (elt) == bset->b.cdata) + return elt; - EBITSET_CACHE_SET (bset, eindex); - return elt; - } + EBITSET_CACHE_SET (bset, eindex); + return elt; + } } /* The element could not be found. */ 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 (); @@ -372,36 +339,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); @@ -411,23 +361,23 @@ ebitset_weed (bset) ebitset_elt *elt = elts[j]; if (elt) - { - if (elt && ebitset_elt_zero_p (elt)) - { - ebitset_elt_remove (bset, j); - count++; - } - } + { + if (ebitset_elt_zero_p (elt)) + { + ebitset_elt_remove (bset, j); + count++; + } + } else - count++; + count++; } count = j - count; if (!count) { - /* 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); + /* All the bits are zero. We could shrink the elts. + For now just mark BSET as known to be zero. */ + EBITSET_ZERO_SET (bset); } else EBITSET_NONZERO_SET (bset); @@ -438,13 +388,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); @@ -453,32 +402,30 @@ ebitset_zero (bset) ebitset_elt *elt = elts[j]; if (elt) - ebitset_elt_remove (bset, j); + 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); @@ -490,23 +437,21 @@ ebitset_equal_p (dst, src) ebitset_elt *delt = delts[j]; if (!selt && !delt) - continue; + 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; + if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i]) + 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; @@ -517,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); @@ -527,105 +472,87 @@ ebitset_copy (dst, src) ebitset_elt *selt = selts[j]; if (selt) - { - ebitset_elt *tmp; - - tmp = ebitset_elt_alloc (); - delts[j] = tmp; - memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt), - sizeof (EBITSET_WORDS (selt))); - } + { + ebitset_elt *tmp; + + tmp = ebitset_elt_alloc (); + delts[j] = tmp; + memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt), + sizeof (EBITSET_WORDS (selt))); + } } EBITSET_NONZERO_SET (dst); } -/* 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; - - ebitset_copy (dst, src); - return 1; -} - + return false; -/* 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] |= (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)) + if (!ebitset_elt_find (dst, bitno, 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. */ } /* 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)); @@ -635,12 +562,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 +572,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 +603,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) - { - word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount); - - for (; word; bcount--) - { - if (word & BITSET_MSB) - { - list[count++] = boffset + bcount; - if (count >= num) - { - *next = n_bits - (boffset + bcount); - return count; - } - } - word <<= 1; - } - } - - woffset = EBITSET_ELT_WORDS; + 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) + { + list[count++] = boffset + bcount; + if (count >= num) + { + *next = n_bits - (boffset + bcount); + return count; + } + } + word <<= 1; + } + boffset -= BITSET_WORD_BITS; + bcount = BITSET_WORD_BITS - 1; + } + while (woffset--); + } + + woffset = EBITSET_ELT_WORDS - 1; + boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS; } + while (eindex--); *next = n_bits - (boffset + 1); return count; @@ -723,23 +651,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; @@ -755,33 +680,33 @@ ebitset_list (bset, list, num, next) elt = elts[eindex]; if (elt) - { - bitset_windex woffset; - bitset_word *srcp = EBITSET_WORDS (elt); - - windex = bitno / BITSET_WORD_BITS; - woffset = eindex / EBITSET_ELT_WORDS; - - for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++) - { - word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS); - - for (; word; bitno++) - { - if (word & 1) - { - list[count++] = bitno; - if (count >= num) - { - *next = bitno + 1; - return count; - } - } - word >>= 1; - } - bitno = (windex + 1) * BITSET_WORD_BITS; - } - } + { + bitset_windex woffset; + bitset_word *srcp = EBITSET_WORDS (elt); + + windex = bitno / BITSET_WORD_BITS; + woffset = eindex * EBITSET_ELT_WORDS; + + for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++) + { + word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS); + + for (; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + bitno = (windex + 1) * BITSET_WORD_BITS; + } + } /* Skip to next element. */ eindex++; @@ -797,65 +722,108 @@ ebitset_list (bset, list, num, next) elt = elts[eindex]; if (!elt) - continue; + continue; srcp = EBITSET_WORDS (elt); windex = eindex * EBITSET_ELT_WORDS; if ((count + EBITSET_ELT_BITS) < num) - { - /* The coast is clear, plant boot! */ - - for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++) - { - bitno = windex * BITSET_WORD_BITS; - - word = srcp[i]; - 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; - } - } - } - } + { + /* 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; + + word = srcp[i]; + 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; + } + } + } +#endif + } else - { - /* Tread more carefully since we need to check - if array overflows. */ - - for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++) - { - bitno = windex * BITSET_WORD_BITS; - - for (word = srcp[i]; word; bitno++) - { - if (word & 1) - { - list[count++] = bitno; - if (count >= num) - { - *next = bitno + 1; - return count; - } - } - word >>= 1; - } - } - } + { + /* Tread more carefully since we need to check + if array overflows. */ + + for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++) + { + bitno = windex * BITSET_WORD_BITS; + + for (word = srcp[i]; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + } + } } *next = bitno; @@ -863,160 +831,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) +{ + 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; - switch (op) + for (j = 0; j < EBITSET_SIZE (dst); j++) { - case BITSET_OP_ZERO: - ebitset_zero (dst); - return 1; - - 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); + /* 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); +} - default: - abort (); + +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); + } } - EBITSET_NONZERO_SET (dst); + /* 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; - - 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; + /* 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); - default: - abort (); + for (i = 0; i < EBITSET_ELT_WORDS; i++) + EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i]; } - EBITSET_NONZERO_SET (dst); - return 1; + ebitset_unused_clear (dst); } -static int -ebitset_op3 (dst, src1, src2, op) - bitset dst; - bitset src1; - bitset src2; - enum bitset_ops op; +/* 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; +} + + +/* 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 bool +ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) { bitset_windex ssize1; bitset_windex ssize2; @@ -1028,40 +1038,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); @@ -1070,9 +1051,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); @@ -1088,93 +1066,93 @@ ebitset_op3 (dst, src1, src2, op) delt = j < dsize ? delts[j] : 0; if (!selt1 && !selt2) - { - if (delt) - { - changed = 1; - ebitset_elt_remove (dst, j); - } - continue; - } + { + if (delt) + { + changed = true; + ebitset_elt_remove (dst, j); + } + continue; + } if (!selt1) - selt1 = &ebitset_zero_elts[0]; + selt1 = &ebitset_zero_elts[0]; if (!selt2) - selt2 = &ebitset_zero_elts[0]; + selt2 = &ebitset_zero_elts[0]; if (!delt) - delt = ebitset_elt_calloc (); + delt = ebitset_elt_calloc (); else - delts[j] = 0; + delts[j] = 0; srcp1 = EBITSET_WORDS (selt1); srcp2 = EBITSET_WORDS (selt2); dstp = EBITSET_WORDS (delt); switch (op) - { - case BITSET_OP_OR: - for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) - { - bitset_word tmp = *srcp1++ | *srcp2++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - case BITSET_OP_AND: - for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) - { - bitset_word tmp = *srcp1++ & *srcp2++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - case BITSET_OP_XOR: - for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) - { - bitset_word tmp = *srcp1++ ^ *srcp2++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - case BITSET_OP_ANDN: - for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) - { - bitset_word tmp = *srcp1++ & ~(*srcp2++); - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - default: - abort (); - } + { + default: + abort (); + + case BITSET_OP_OR: + for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ | *srcp2++; + + if (*dstp != tmp) + { + changed = true; + *dstp = tmp; + } + } + break; + + case BITSET_OP_AND: + for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ & *srcp2++; + + if (*dstp != tmp) + { + changed = true; + *dstp = tmp; + } + } + break; + + case BITSET_OP_XOR: + for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ ^ *srcp2++; + + if (*dstp != tmp) + { + changed = true; + *dstp = tmp; + } + } + break; + + case BITSET_OP_ANDN: + for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ & ~(*srcp2++); + + if (*dstp != tmp) + { + changed = true; + *dstp = tmp; + } + } + break; + } if (!ebitset_elt_zero_p (delt)) - { - ebitset_elt_add (dst, delt, j); - } + { + ebitset_elt_add (dst, delt, j); + } else - { - ebitset_elt_free (delt); - } + { + ebitset_elt_free (delt); + } } /* If we have elements of DST left over, free them all. */ @@ -1182,12 +1160,12 @@ ebitset_op3 (dst, src1, src2, op) { ebitset_elt *delt; - changed = 1; + changed = true; delt = delts[j]; if (delt) - ebitset_elt_remove (dst, j); + ebitset_elt_remove (dst, j); } EBITSET_NONZERO_SET (dst); @@ -1195,65 +1173,189 @@ 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; - - bset->b.ops = &ebitset_ops; + bset->b.vtable = &ebitset_vtable; bset->b.csize = EBITSET_ELT_WORDS; - EBITSET_OP_ZERO_SET (bset); - - size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS - : EBITSET_INITIAL_SIZE; + EBITSET_ZERO_SET (bset); - 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); } }