From 22693f63eaab748233749c957e7d853654c96cdb Mon Sep 17 00:00:00 2001 From: Akim Demaille <akim.demaille@gmail.com> Date: Thu, 29 Nov 2018 05:44:58 +0100 Subject: [PATCH] bitset: rename ebitset/expandable.* as tbitset/table.* See https://lists.gnu.org/archive/html/bug-gnulib/2018-11/msg00096.html. * lib/bitset/expandable.h, lib/bitset/expandable.c: Rename as... * lib/bitset/table.h, lib/bitset/table.c: these. Rename all the ebitset* symbols as tbitset*. Adjust dependencies. --- ChangeLog | 10 + lib/bitset.c | 8 +- lib/bitset.h | 4 +- lib/bitset/base.h | 2 +- lib/bitset/stats.c | 6 +- lib/bitset/{expandable.c => table.c} | 406 +++++++++++++-------------- lib/bitset/{expandable.h => table.h} | 12 +- modules/bitset | 6 +- 8 files changed, 232 insertions(+), 222 deletions(-) rename lib/bitset/{expandable.c => table.c} (73%) rename lib/bitset/{expandable.h => table.h} (79%) diff --git a/ChangeLog b/ChangeLog index cad72e032d..af7a14fa90 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2018-11-29 Akim Demaille <akim@lrde.epita.fr> + + bitset: rename ebitset/expandable.* as tbitset/table.* + See + https://lists.gnu.org/archive/html/bug-gnulib/2018-11/msg00096.html. + * lib/bitset/expandable.h, lib/bitset/expandable.c: Rename as... + * lib/bitset/table.h, lib/bitset/table.c: these. + Rename all the ebitset* symbols as tbitset*. + Adjust dependencies. + 2018-11-28 Akim Demaille <akim@lrde.epita.fr> bitset: check the operations diff --git a/lib/bitset.c b/lib/bitset.c index 0d75fe1a01..5edf723ddb 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -28,9 +28,9 @@ #include "obstack.h" #include "bitset/array.h" -#include "bitset/expandable.h" #include "bitset/list.h" #include "bitset/stats.h" +#include "bitset/table.h" #include "bitset/vector.h" const char * const bitset_type_names[] = BITSET_TYPE_NAMES; @@ -56,7 +56,7 @@ bitset_bytes (enum bitset_type type, bitset_bindex n_bits) return lbitset_bytes (n_bits); case BITSET_TABLE: - return ebitset_bytes (n_bits); + return tbitset_bytes (n_bits); case BITSET_VECTOR: return vbitset_bytes (n_bits); @@ -83,7 +83,7 @@ bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) return lbitset_init (bset, n_bits); case BITSET_TABLE: - return ebitset_init (bset, n_bits); + return tbitset_init (bset, n_bits); case BITSET_VECTOR: return vbitset_init (bset, n_bits); @@ -308,7 +308,7 @@ void bitset_release_memory (void) { lbitset_release_memory (); - ebitset_release_memory (); + tbitset_release_memory (); } diff --git a/lib/bitset.h b/lib/bitset.h index 161ac58eeb..e0032170b2 100644 --- a/lib/bitset.h +++ b/lib/bitset.h @@ -58,11 +58,11 @@ union bitset_union bitset_word words[1]; /* The array of bits. */ } a; - struct ebitset_struct + struct tbitset_struct { struct bbitset_struct b; bitset_windex size; /* Number of elements. */ - struct ebitset_elt_struct **elts; /* Expanding array of ptrs to elts. */ + struct tbitset_elt_struct **elts; /* Expanding array of ptrs to elts. */ } e; struct lbitset_struct diff --git a/lib/bitset/base.h b/lib/bitset/base.h index ed5bb3baa6..3f5b5f2e2a 100644 --- a/lib/bitset/base.h +++ b/lib/bitset/base.h @@ -51,7 +51,7 @@ */ enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_VECTOR, BITSET_TYPE_NUM, BITSET_STATS}; -#define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset", "vbitset"} +#define BITSET_TYPE_NAMES {"abitset", "lbitset", "tbitset", "vbitset"} extern const char * const bitset_type_names[]; diff --git a/lib/bitset/stats.c b/lib/bitset/stats.c index c6e457b1fe..8446fbb43e 100644 --- a/lib/bitset/stats.c +++ b/lib/bitset/stats.c @@ -38,8 +38,8 @@ #include "bitset/array.h" #include "bitset/base.h" -#include "bitset/expandable.h" #include "bitset/list.h" +#include "bitset/table.h" #include "bitset/vector.h" /* Configuration macros. */ @@ -710,9 +710,9 @@ bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) case BITSET_TABLE: { - size_t bytes = ebitset_bytes (n_bits); + size_t bytes = tbitset_bytes (n_bits); bset->s.bset = xcalloc (1, bytes); - ebitset_init (bset->s.bset, n_bits); + tbitset_init (bset->s.bset, n_bits); } break; diff --git a/lib/bitset/expandable.c b/lib/bitset/table.c similarity index 73% rename from lib/bitset/expandable.c rename to lib/bitset/table.c index c9f2d88e81..d503c7ca51 100644 --- a/lib/bitset/expandable.c +++ b/lib/bitset/table.c @@ -20,7 +20,7 @@ #include <config.h> -#include "bitset/expandable.h" +#include "bitset/table.h" #include <stdlib.h> #include <string.h> @@ -56,19 +56,19 @@ ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS)) /* Ebitset element. We use an array of bits. */ -typedef struct ebitset_elt_struct +typedef struct tbitset_elt_struct { union { bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */ - struct ebitset_elt_struct *next; + struct tbitset_elt_struct *next; } u; } -ebitset_elt; +tbitset_elt; -typedef ebitset_elt *ebitset_elts; +typedef tbitset_elt *tbitset_elts; /* Number of elements to initially allocate. */ @@ -78,15 +78,15 @@ typedef ebitset_elt *ebitset_elts; #endif -enum ebitset_find_mode +enum tbitset_find_mode { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST }; -static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits. */ +static tbitset_elt tbitset_zero_elts[1]; /* Elements of all zero bits. */ /* Obstack to allocate bitset elements from. */ -static struct obstack ebitset_obstack; -static bool ebitset_obstack_init = false; -static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */ +static struct obstack tbitset_obstack; +static bool tbitset_obstack_init = false; +static tbitset_elt *tbitset_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) @@ -122,7 +122,7 @@ static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */ #define max(a, b) ((a) > (b) ? (a) : (b)) static bitset_bindex -ebitset_resize (bitset src, bitset_bindex n_bits) +tbitset_resize (bitset src, bitset_bindex n_bits) { if (n_bits == BITSET_NBITS_ (src)) return n_bits; @@ -143,12 +143,12 @@ ebitset_resize (bitset src, bitset_bindex n_bits) bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4; EBITSET_ELTS (src) - = realloc (EBITSET_ELTS (src), size * sizeof (ebitset_elt *)); + = realloc (EBITSET_ELTS (src), size * sizeof (tbitset_elt *)); EBITSET_ASIZE (src) = size; } memset (EBITSET_ELTS (src) + oldsize, 0, - (newsize - oldsize) * sizeof (ebitset_elt *)); + (newsize - oldsize) * sizeof (tbitset_elt *)); } else { @@ -157,7 +157,7 @@ ebitset_resize (bitset src, bitset_bindex n_bits) if ((oldsize - newsize) >= oldsize / 2) { EBITSET_ELTS (src) - = realloc (EBITSET_ELTS (src), newsize * sizeof (ebitset_elt *)); + = realloc (EBITSET_ELTS (src), newsize * sizeof (tbitset_elt *)); EBITSET_ASIZE (src) = newsize; } @@ -169,22 +169,22 @@ ebitset_resize (bitset src, bitset_bindex n_bits) } -/* Allocate a ebitset element. The bits are not cleared. */ -static inline ebitset_elt * -ebitset_elt_alloc (void) +/* Allocate a tbitset element. The bits are not cleared. */ +static inline tbitset_elt * +tbitset_elt_alloc (void) { - ebitset_elt *elt; + tbitset_elt *elt; - if (ebitset_free_list != 0) + if (tbitset_free_list != 0) { - elt = ebitset_free_list; - ebitset_free_list = EBITSET_NEXT (elt); + elt = tbitset_free_list; + tbitset_free_list = EBITSET_NEXT (elt); } else { - if (!ebitset_obstack_init) + if (!tbitset_obstack_init) { - ebitset_obstack_init = true; + tbitset_obstack_init = true; /* Let particular systems override the size of a chunk. */ @@ -206,57 +206,57 @@ ebitset_elt_alloc (void) #define __alignof__(type) 0 #endif - obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE, - __alignof__ (ebitset_elt), + obstack_specify_allocation (&tbitset_obstack, OBSTACK_CHUNK_SIZE, + __alignof__ (tbitset_elt), OBSTACK_CHUNK_ALLOC, OBSTACK_CHUNK_FREE); } /* Perhaps we should add a number of new elements to the free list. */ - elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack, - sizeof (ebitset_elt)); + elt = (tbitset_elt *) obstack_alloc (&tbitset_obstack, + sizeof (tbitset_elt)); } return elt; } -/* Allocate a ebitset element. The bits are cleared. */ -static inline ebitset_elt * -ebitset_elt_calloc (void) +/* Allocate a tbitset element. The bits are cleared. */ +static inline tbitset_elt * +tbitset_elt_calloc (void) { - ebitset_elt *elt = ebitset_elt_alloc (); + tbitset_elt *elt = tbitset_elt_alloc (); memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt))); return elt; } static inline void -ebitset_elt_free (ebitset_elt *elt) +tbitset_elt_free (tbitset_elt *elt) { - EBITSET_NEXT (elt) = ebitset_free_list; - ebitset_free_list = elt; + EBITSET_NEXT (elt) = tbitset_free_list; + tbitset_free_list = elt; } /* Remove element with index EINDEX from bitset BSET. */ static inline void -ebitset_elt_remove (bitset bset, bitset_windex eindex) +tbitset_elt_remove (bitset bset, bitset_windex eindex) { - ebitset_elts *elts = EBITSET_ELTS (bset); - ebitset_elt *elt = elts[eindex]; + tbitset_elts *elts = EBITSET_ELTS (bset); + tbitset_elt *elt = elts[eindex]; elts[eindex] = 0; - ebitset_elt_free (elt); + tbitset_elt_free (elt); } /* Add ELT into elts at index EINDEX of bitset BSET. */ static inline void -ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex) +tbitset_elt_add (bitset bset, tbitset_elt *elt, bitset_windex eindex) { - ebitset_elts *elts = EBITSET_ELTS (bset); + tbitset_elts *elts = EBITSET_ELTS (bset); /* Assume that the elts entry not allocated. */ elts[eindex] = elt; } @@ -264,7 +264,7 @@ ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex) /* Are all bits in an element zero? */ static inline bool -ebitset_elt_zero_p (ebitset_elt *elt) +tbitset_elt_zero_p (tbitset_elt *elt) { for (int i = 0; i < EBITSET_ELT_WORDS; i++) if (EBITSET_WORDS (elt)[i]) @@ -273,18 +273,18 @@ ebitset_elt_zero_p (ebitset_elt *elt) } -static ebitset_elt * -ebitset_elt_find (bitset bset, bitset_bindex bindex, - enum ebitset_find_mode mode) +static tbitset_elt * +tbitset_elt_find (bitset bset, bitset_bindex bindex, + enum tbitset_find_mode mode) { bitset_windex eindex = bindex / EBITSET_ELT_BITS; - ebitset_elts *elts = EBITSET_ELTS (bset); + tbitset_elts *elts = EBITSET_ELTS (bset); bitset_windex size = EBITSET_SIZE (bset); if (eindex < size) { - ebitset_elt *elt = elts[eindex]; + tbitset_elt *elt = elts[eindex]; if (elt) { if (EBITSET_WORDS (elt) != bset->b.cdata) @@ -305,41 +305,41 @@ ebitset_elt_find (bitset bset, bitset_bindex bindex, case EBITSET_CREATE: if (eindex >= size) - ebitset_resize (bset, bindex); + tbitset_resize (bset, bindex); /* Create a new element. */ { - ebitset_elt *elt = ebitset_elt_calloc (); - ebitset_elt_add (bset, elt, eindex); + tbitset_elt *elt = tbitset_elt_calloc (); + tbitset_elt_add (bset, elt, eindex); EBITSET_CACHE_SET (bset, eindex); return elt; } case EBITSET_SUBST: - return &ebitset_zero_elts[0]; + return &tbitset_zero_elts[0]; } } /* Weed out the zero elements from the elts. */ static inline bitset_windex -ebitset_weed (bitset bset) +tbitset_weed (bitset bset) { if (EBITSET_ZERO_P (bset)) return 0; - ebitset_elts *elts = EBITSET_ELTS (bset); + tbitset_elts *elts = EBITSET_ELTS (bset); bitset_windex count = 0; bitset_windex j; for (j = 0; j < EBITSET_SIZE (bset); j++) { - ebitset_elt *elt = elts[j]; + tbitset_elt *elt = elts[j]; if (elt) { - if (ebitset_elt_zero_p (elt)) + if (tbitset_elt_zero_p (elt)) { - ebitset_elt_remove (bset, j); + tbitset_elt_remove (bset, j); count++; } } @@ -363,17 +363,17 @@ ebitset_weed (bitset bset) /* Set all bits in the bitset to zero. */ static inline void -ebitset_zero (bitset bset) +tbitset_zero (bitset bset) { if (EBITSET_ZERO_P (bset)) return; - ebitset_elts *elts = EBITSET_ELTS (bset); + tbitset_elts *elts = EBITSET_ELTS (bset); for (bitset_windex j = 0; j < EBITSET_SIZE (bset); j++) { - ebitset_elt *elt = elts[j]; + tbitset_elt *elt = elts[j]; if (elt) - ebitset_elt_remove (bset, j); + tbitset_elt_remove (bset, j); } /* All the bits are zero. We could shrink the elts. @@ -383,24 +383,24 @@ ebitset_zero (bitset bset) static inline bool -ebitset_equal_p (bitset dst, bitset src) +tbitset_equal_p (bitset dst, bitset src) { if (src == dst) return true; - ebitset_weed (dst); - ebitset_weed (src); + tbitset_weed (dst); + tbitset_weed (src); if (EBITSET_SIZE (src) != EBITSET_SIZE (dst)) return false; - ebitset_elts *selts = EBITSET_ELTS (src); - ebitset_elts *delts = EBITSET_ELTS (dst); + tbitset_elts *selts = EBITSET_ELTS (src); + tbitset_elts *delts = EBITSET_ELTS (dst); for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++) { - ebitset_elt *selt = selts[j]; - ebitset_elt *delt = delts[j]; + tbitset_elt *selt = selts[j]; + tbitset_elt *delt = delts[j]; if (!selt && !delt) continue; @@ -417,24 +417,24 @@ ebitset_equal_p (bitset dst, bitset src) /* Copy bits from bitset SRC to bitset DST. */ static inline void -ebitset_copy_ (bitset dst, bitset src) +tbitset_copy_ (bitset dst, bitset src) { if (src == dst) return; - ebitset_zero (dst); + tbitset_zero (dst); if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src)) - ebitset_resize (dst, BITSET_NBITS_ (src)); + tbitset_resize (dst, BITSET_NBITS_ (src)); - ebitset_elts *selts = EBITSET_ELTS (src); - ebitset_elts *delts = EBITSET_ELTS (dst); + tbitset_elts *selts = EBITSET_ELTS (src); + tbitset_elts *delts = EBITSET_ELTS (dst); for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++) { - ebitset_elt *selt = selts[j]; + tbitset_elt *selt = selts[j]; if (selt) { - ebitset_elt *tmp = ebitset_elt_alloc (); + tbitset_elt *tmp = tbitset_elt_alloc (); delts[j] = tmp; memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt), sizeof (EBITSET_WORDS (selt))); @@ -447,32 +447,32 @@ ebitset_copy_ (bitset dst, bitset src) /* Copy bits from bitset SRC to bitset DST. Return true if bitsets different. */ static inline bool -ebitset_copy_cmp (bitset dst, bitset src) +tbitset_copy_cmp (bitset dst, bitset src) { if (src == dst) return false; if (EBITSET_ZERO_P (dst)) { - ebitset_copy_ (dst, src); + tbitset_copy_ (dst, src); return !EBITSET_ZERO_P (src); } - if (ebitset_equal_p (dst, src)) + if (tbitset_equal_p (dst, src)) return false; - ebitset_copy_ (dst, src); + tbitset_copy_ (dst, src); return true; } /* Set bit BITNO in bitset DST. */ static void -ebitset_set (bitset dst, bitset_bindex bitno) +tbitset_set (bitset dst, bitset_bindex bitno) { bitset_windex windex = bitno / BITSET_WORD_BITS; - ebitset_elt_find (dst, bitno, EBITSET_CREATE); + tbitset_elt_find (dst, bitno, EBITSET_CREATE); dst->b.cdata[windex - dst->b.cindex] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS); @@ -481,11 +481,11 @@ ebitset_set (bitset dst, bitset_bindex bitno) /* Reset bit BITNO in bitset DST. */ static void -ebitset_reset (bitset dst, bitset_bindex bitno) +tbitset_reset (bitset dst, bitset_bindex bitno) { bitset_windex windex = bitno / BITSET_WORD_BITS; - if (!ebitset_elt_find (dst, bitno, EBITSET_FIND)) + if (!tbitset_elt_find (dst, bitno, EBITSET_FIND)) return; dst->b.cdata[windex - dst->b.cindex] &= @@ -499,11 +499,11 @@ ebitset_reset (bitset dst, bitset_bindex bitno) /* Test bit BITNO in bitset SRC. */ static bool -ebitset_test (bitset src, bitset_bindex bitno) +tbitset_test (bitset src, bitset_bindex bitno) { bitset_windex windex = bitno / BITSET_WORD_BITS; - return (ebitset_elt_find (src, bitno, EBITSET_FIND) + return (tbitset_elt_find (src, bitno, EBITSET_FIND) && ((src->b.cdata[windex - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1)); @@ -511,9 +511,9 @@ ebitset_test (bitset src, bitset_bindex bitno) static void -ebitset_free (bitset bset) +tbitset_free (bitset bset) { - ebitset_zero (bset); + tbitset_zero (bset); free (EBITSET_ELTS (bset)); } @@ -522,7 +522,7 @@ ebitset_free (bitset 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 (bitset bset, bitset_bindex *list, +tbitset_list_reverse (bitset bset, bitset_bindex *list, bitset_bindex num, bitset_bindex *next) { if (EBITSET_ZERO_P (bset)) @@ -535,7 +535,7 @@ ebitset_list_reverse (bitset bset, bitset_bindex *list, if (rbitno >= n_bits) return 0; - ebitset_elts *elts = EBITSET_ELTS (bset); + tbitset_elts *elts = EBITSET_ELTS (bset); bitset_bindex bitno = n_bits - (rbitno + 1); @@ -551,7 +551,7 @@ ebitset_list_reverse (bitset bset, bitset_bindex *list, do { - ebitset_elt *elt = elts[eindex]; + tbitset_elt *elt = elts[eindex]; if (elt) { bitset_word *srcp = EBITSET_WORDS (elt); @@ -592,7 +592,7 @@ ebitset_list_reverse (bitset bset, bitset_bindex *list, *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 (bitset bset, bitset_bindex *list, +tbitset_list (bitset bset, bitset_bindex *list, bitset_bindex num, bitset_bindex *next) { if (EBITSET_ZERO_P (bset)) @@ -601,7 +601,7 @@ ebitset_list (bitset bset, bitset_bindex *list, bitset_bindex bitno = *next; bitset_bindex count = 0; - ebitset_elts *elts = EBITSET_ELTS (bset); + tbitset_elts *elts = EBITSET_ELTS (bset); bitset_windex size = EBITSET_SIZE (bset); bitset_windex eindex = bitno / EBITSET_ELT_BITS; @@ -609,7 +609,7 @@ ebitset_list (bitset bset, bitset_bindex *list, { /* We need to start within an element. This is not very common. */ - ebitset_elt *elt = elts[eindex]; + tbitset_elt *elt = elts[eindex]; if (elt) { bitset_windex woffset; @@ -650,7 +650,7 @@ ebitset_list (bitset bset, bitset_bindex *list, { bitset_word *srcp; - ebitset_elt *elt = elts[eindex]; + tbitset_elt *elt = elts[eindex]; if (!elt) continue; @@ -763,18 +763,18 @@ ebitset_list (bitset bset, bitset_bindex *list, /* Ensure that any unused bits within the last element are clear. */ static inline void -ebitset_unused_clear (bitset dst) +tbitset_unused_clear (bitset dst) { bitset_bindex n_bits = BITSET_NBITS_ (dst); unsigned last_bit = n_bits % EBITSET_ELT_BITS; if (last_bit) { - ebitset_elts *elts = EBITSET_ELTS (dst); + tbitset_elts *elts = EBITSET_ELTS (dst); bitset_windex eindex = n_bits / EBITSET_ELT_BITS; - ebitset_elt *elt = elts[eindex]; + tbitset_elt *elt = elts[eindex]; if (elt) { bitset_word *srcp = EBITSET_WORDS (elt); @@ -792,38 +792,38 @@ ebitset_unused_clear (bitset dst) static void -ebitset_ones (bitset dst) +tbitset_ones (bitset dst) { for (bitset_windex 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? */ - ebitset_elt *elt = - ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE); + tbitset_elt *elt = + tbitset_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); + tbitset_unused_clear (dst); } static bool -ebitset_empty_p (bitset dst) +tbitset_empty_p (bitset dst) { if (EBITSET_ZERO_P (dst)) return true; - ebitset_elts *elts = EBITSET_ELTS (dst); + tbitset_elts *elts = EBITSET_ELTS (dst); for (bitset_windex j = 0; j < EBITSET_SIZE (dst); j++) { - ebitset_elt *elt = elts[j]; + tbitset_elt *elt = elts[j]; if (elt) { - if (!ebitset_elt_zero_p (elt)) + if (!tbitset_elt_zero_p (elt)) return false; /* Do some weeding as we go. */ - ebitset_elt_remove (dst, j); + tbitset_elt_remove (dst, j); } } @@ -835,49 +835,49 @@ ebitset_empty_p (bitset dst) static void -ebitset_not (bitset dst, bitset src) +tbitset_not (bitset dst, bitset src) { - ebitset_resize (dst, BITSET_NBITS_ (src)); + tbitset_resize (dst, BITSET_NBITS_ (src)); for (bitset_windex 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. */ - ebitset_elt *selt = - ebitset_elt_find (src, j * EBITSET_ELT_BITS, EBITSET_SUBST); - ebitset_elt *delt = - ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE); + tbitset_elt *selt = + tbitset_elt_find (src, j * EBITSET_ELT_BITS, EBITSET_SUBST); + tbitset_elt *delt = + tbitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE); for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++) EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i]; } EBITSET_NONZERO_SET (dst); - ebitset_unused_clear (dst); + tbitset_unused_clear (dst); } /* Is DST == DST | SRC? */ static bool -ebitset_subset_p (bitset dst, bitset src) +tbitset_subset_p (bitset dst, bitset src) { - ebitset_elts *selts = EBITSET_ELTS (src); - ebitset_elts *delts = EBITSET_ELTS (dst); + tbitset_elts *selts = EBITSET_ELTS (src); + tbitset_elts *delts = EBITSET_ELTS (dst); bitset_windex ssize = EBITSET_SIZE (src); bitset_windex dsize = EBITSET_SIZE (dst); for (bitset_windex j = 0; j < ssize; j++) { - ebitset_elt *selt = j < ssize ? selts[j] : 0; - ebitset_elt *delt = j < dsize ? delts[j] : 0; + tbitset_elt *selt = j < ssize ? selts[j] : 0; + tbitset_elt *delt = j < dsize ? delts[j] : 0; if (!selt && !delt) continue; if (!selt) - selt = &ebitset_zero_elts[0]; + selt = &tbitset_zero_elts[0]; if (!delt) - delt = &ebitset_zero_elts[0]; + delt = &tbitset_zero_elts[0]; for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++) if (EBITSET_WORDS (delt)[i] @@ -890,18 +890,18 @@ ebitset_subset_p (bitset dst, bitset src) /* Is DST & SRC == 0? */ static bool -ebitset_disjoint_p (bitset dst, bitset src) +tbitset_disjoint_p (bitset dst, bitset src) { - ebitset_elts *selts = EBITSET_ELTS (src); - ebitset_elts *delts = EBITSET_ELTS (dst); + tbitset_elts *selts = EBITSET_ELTS (src); + tbitset_elts *delts = EBITSET_ELTS (dst); bitset_windex ssize = EBITSET_SIZE (src); bitset_windex dsize = EBITSET_SIZE (dst); for (bitset_windex j = 0; j < ssize; j++) { - ebitset_elt *selt = j < ssize ? selts[j] : 0; - ebitset_elt *delt = j < dsize ? delts[j] : 0; + tbitset_elt *selt = j < ssize ? selts[j] : 0; + tbitset_elt *delt = j < dsize ? delts[j] : 0; if (!selt || !delt) continue; @@ -916,11 +916,11 @@ ebitset_disjoint_p (bitset dst, bitset src) static bool -ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) +tbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) { bool changed = false; - ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2))); + tbitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2))); bitset_windex ssize1 = EBITSET_SIZE (src1); bitset_windex ssize2 = EBITSET_SIZE (src2); @@ -929,33 +929,33 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) if (size < ssize2) size = ssize2; - ebitset_elts *selts1 = EBITSET_ELTS (src1); - ebitset_elts *selts2 = EBITSET_ELTS (src2); - ebitset_elts *delts = EBITSET_ELTS (dst); + tbitset_elts *selts1 = EBITSET_ELTS (src1); + tbitset_elts *selts2 = EBITSET_ELTS (src2); + tbitset_elts *delts = EBITSET_ELTS (dst); bitset_windex j = 0; for (j = 0; j < size; j++) { - ebitset_elt *selt1 = j < ssize1 ? selts1[j] : 0; - ebitset_elt *selt2 = j < ssize2 ? selts2[j] : 0; - ebitset_elt *delt = j < dsize ? delts[j] : 0; + tbitset_elt *selt1 = j < ssize1 ? selts1[j] : 0; + tbitset_elt *selt2 = j < ssize2 ? selts2[j] : 0; + tbitset_elt *delt = j < dsize ? delts[j] : 0; if (!selt1 && !selt2) { if (delt) { changed = true; - ebitset_elt_remove (dst, j); + tbitset_elt_remove (dst, j); } continue; } if (!selt1) - selt1 = &ebitset_zero_elts[0]; + selt1 = &tbitset_zero_elts[0]; if (!selt2) - selt2 = &ebitset_zero_elts[0]; + selt2 = &tbitset_zero_elts[0]; if (!delt) - delt = ebitset_elt_calloc (); + delt = tbitset_elt_calloc (); else delts[j] = 0; @@ -1020,13 +1020,13 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) break; } - if (!ebitset_elt_zero_p (delt)) + if (!tbitset_elt_zero_p (delt)) { - ebitset_elt_add (dst, delt, j); + tbitset_elt_add (dst, delt, j); } else { - ebitset_elt_free (delt); + tbitset_elt_free (delt); } } @@ -1035,9 +1035,9 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) { changed = true; - ebitset_elt *delt = delts[j]; + tbitset_elt *delt = delts[j]; if (delt) - ebitset_elt_remove (dst, j); + tbitset_elt_remove (dst, j); } EBITSET_NONZERO_SET (dst); @@ -1046,164 +1046,164 @@ ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) static bool -ebitset_and_cmp (bitset dst, bitset src1, bitset src2) +tbitset_and_cmp (bitset dst, bitset src1, bitset src2) { if (EBITSET_ZERO_P (src2)) { - ebitset_weed (dst); + tbitset_weed (dst); bool changed = EBITSET_ZERO_P (dst); - ebitset_zero (dst); + tbitset_zero (dst); return changed; } else if (EBITSET_ZERO_P (src1)) { - ebitset_weed (dst); + tbitset_weed (dst); bool changed = EBITSET_ZERO_P (dst); - ebitset_zero (dst); + tbitset_zero (dst); return changed; } - return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND); + return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND); } static void -ebitset_and (bitset dst, bitset src1, bitset src2) +tbitset_and (bitset dst, bitset src1, bitset src2) { - ebitset_and_cmp (dst, src1, src2); + tbitset_and_cmp (dst, src1, src2); } static bool -ebitset_andn_cmp (bitset dst, bitset src1, bitset src2) +tbitset_andn_cmp (bitset dst, bitset src1, bitset src2) { if (EBITSET_ZERO_P (src2)) { - return ebitset_copy_cmp (dst, src1); + return tbitset_copy_cmp (dst, src1); } else if (EBITSET_ZERO_P (src1)) { - ebitset_weed (dst); + tbitset_weed (dst); bool changed = EBITSET_ZERO_P (dst); - ebitset_zero (dst); + tbitset_zero (dst); return changed; } - return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN); + return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN); } static void -ebitset_andn (bitset dst, bitset src1, bitset src2) +tbitset_andn (bitset dst, bitset src1, bitset src2) { - ebitset_andn_cmp (dst, src1, src2); + tbitset_andn_cmp (dst, src1, src2); } static bool -ebitset_or_cmp (bitset dst, bitset src1, bitset src2) +tbitset_or_cmp (bitset dst, bitset src1, bitset src2) { if (EBITSET_ZERO_P (src2)) { - return ebitset_copy_cmp (dst, src1); + return tbitset_copy_cmp (dst, src1); } else if (EBITSET_ZERO_P (src1)) { - return ebitset_copy_cmp (dst, src2); + return tbitset_copy_cmp (dst, src2); } - return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR); + return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR); } static void -ebitset_or (bitset dst, bitset src1, bitset src2) +tbitset_or (bitset dst, bitset src1, bitset src2) { - ebitset_or_cmp (dst, src1, src2); + tbitset_or_cmp (dst, src1, src2); } static bool -ebitset_xor_cmp (bitset dst, bitset src1, bitset src2) +tbitset_xor_cmp (bitset dst, bitset src1, bitset src2) { if (EBITSET_ZERO_P (src2)) { - return ebitset_copy_cmp (dst, src1); + return tbitset_copy_cmp (dst, src1); } else if (EBITSET_ZERO_P (src1)) { - return ebitset_copy_cmp (dst, src2); + return tbitset_copy_cmp (dst, src2); } - return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR); + return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR); } static void -ebitset_xor (bitset dst, bitset src1, bitset src2) +tbitset_xor (bitset dst, bitset src1, bitset src2) { - ebitset_xor_cmp (dst, src1, src2); + tbitset_xor_cmp (dst, src1, src2); } static void -ebitset_copy (bitset dst, bitset src) +tbitset_copy (bitset dst, bitset src) { if (BITSET_COMPATIBLE_ (dst, src)) - ebitset_copy_ (dst, src); + tbitset_copy_ (dst, src); else bitset_copy_ (dst, src); } /* Vector of operations for linked-list bitsets. */ -struct bitset_vtable ebitset_vtable = { - ebitset_set, - ebitset_reset, +struct bitset_vtable tbitset_vtable = { + tbitset_set, + tbitset_reset, bitset_toggle_, - ebitset_test, - ebitset_resize, + tbitset_test, + tbitset_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, + tbitset_empty_p, + tbitset_ones, + tbitset_zero, + tbitset_copy, + tbitset_disjoint_p, + tbitset_equal_p, + tbitset_not, + tbitset_subset_p, + tbitset_and, + tbitset_and_cmp, + tbitset_andn, + tbitset_andn_cmp, + tbitset_or, + tbitset_or_cmp, + tbitset_xor, + tbitset_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_list_reverse, - ebitset_free, + tbitset_list, + tbitset_list_reverse, + tbitset_free, BITSET_TABLE }; /* Return size of initial structure. */ size_t -ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) +tbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) { - return sizeof (struct ebitset_struct); + return sizeof (struct tbitset_struct); } /* Initialize a bitset. */ bitset -ebitset_init (bitset bset, bitset_bindex n_bits) +tbitset_init (bitset bset, bitset_bindex n_bits) { - bset->b.vtable = &ebitset_vtable; + bset->b.vtable = &tbitset_vtable; bset->b.csize = EBITSET_ELT_WORDS; @@ -1211,19 +1211,19 @@ ebitset_init (bitset bset, bitset_bindex n_bits) EBITSET_ASIZE (bset) = 0; EBITSET_ELTS (bset) = 0; - ebitset_resize (bset, n_bits); + tbitset_resize (bset, n_bits); return bset; } void -ebitset_release_memory (void) +tbitset_release_memory (void) { - ebitset_free_list = 0; - if (ebitset_obstack_init) + tbitset_free_list = 0; + if (tbitset_obstack_init) { - ebitset_obstack_init = false; - obstack_free (&ebitset_obstack, NULL); + tbitset_obstack_init = false; + obstack_free (&tbitset_obstack, NULL); } } diff --git a/lib/bitset/expandable.h b/lib/bitset/table.h similarity index 79% rename from lib/bitset/expandable.h rename to lib/bitset/table.h index 781903e408..4019d4c935 100644 --- a/lib/bitset/expandable.h +++ b/lib/bitset/table.h @@ -1,4 +1,4 @@ -/* Functions to support ebitsets. +/* Functions to support tbitsets. Copyright (C) 2002, 2004, 2009-2015, 2018 Free Software Foundation, Inc. @@ -18,15 +18,15 @@ You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef _BITSET_EXPANDABLE_H -#define _BITSET_EXPANDABLE_H +#ifndef _BITSET_TABLE_H +#define _BITSET_TABLE_H #include "bitset.h" -size_t ebitset_bytes (bitset_bindex); +size_t tbitset_bytes (bitset_bindex); -bitset ebitset_init (bitset, bitset_bindex); +bitset tbitset_init (bitset, bitset_bindex); -void ebitset_release_memory (void); +void tbitset_release_memory (void); #endif diff --git a/modules/bitset b/modules/bitset index d77d35ed55..76d1a2cacf 100644 --- a/modules/bitset +++ b/modules/bitset @@ -7,12 +7,12 @@ lib/bitset.h lib/bitset/array.c lib/bitset/array.h lib/bitset/base.h -lib/bitset/expandable.c -lib/bitset/expandable.h lib/bitset/list.c lib/bitset/list.h lib/bitset/stats.c lib/bitset/stats.h +lib/bitset/table.c +lib/bitset/table.h lib/bitset/vector.c lib/bitset/vector.h @@ -23,7 +23,7 @@ xalloc Makefile.am: lib_SOURCES += bitset.c bitset/array.c bitset/stats.c \ - bitset/expandable.c bitset/list.c bitset/vector.c + bitset/table.c bitset/list.c bitset/vector.c Include: "bitset.h" -- 2.39.5