Mercurial > gnulib
changeset 39981:14ac09965b35
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.
| author | Akim Demaille <akim.demaille@gmail.com> |
|---|---|
| date | Thu, 29 Nov 2018 05:44:58 +0100 |
| parents | e562c3b5b9c4 |
| children | 4f5113a573fc |
| files | ChangeLog lib/bitset.c lib/bitset.h lib/bitset/base.h lib/bitset/expandable.c lib/bitset/expandable.h lib/bitset/stats.c lib/bitset/table.c lib/bitset/table.h modules/bitset |
| diffstat | 10 files changed, 1284 insertions(+), 1274 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog Wed Nov 28 05:56:21 2018 +0100 +++ b/ChangeLog Thu Nov 29 05:44:58 2018 +0100 @@ -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
--- a/lib/bitset.c Wed Nov 28 05:56:21 2018 +0100 +++ b/lib/bitset.c Thu Nov 29 05:44:58 2018 +0100 @@ -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 @@ 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 @@ 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 @@ bitset_release_memory (void) { lbitset_release_memory (); - ebitset_release_memory (); + tbitset_release_memory (); }
--- a/lib/bitset.h Wed Nov 28 05:56:21 2018 +0100 +++ b/lib/bitset.h Thu Nov 29 05:44:58 2018 +0100 @@ -58,11 +58,11 @@ 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
--- a/lib/bitset/base.h Wed Nov 28 05:56:21 2018 +0100 +++ b/lib/bitset/base.h Thu Nov 29 05:44:58 2018 +0100 @@ -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[];
--- a/lib/bitset/expandable.c Wed Nov 28 05:56:21 2018 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1229 +0,0 @@ -/* Functions to support expandable bitsets. - - Copyright (C) 2002-2006, 2009-2015, 2018 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 - it under the terms of the GNU General Public License as published by - 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, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - 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, see <http://www.gnu.org/licenses/>. */ - -#include <config.h> - -#include "bitset/expandable.h" - -#include <stdlib.h> -#include <string.h> - -#include "obstack.h" - -/* This file implements expandable bitsets. These bitsets can be of - arbitrary length and are more efficient than arrays of bits for - large sparse sets. - - Empty elements are represented by a NULL pointer in the table of - element pointers. An alternative is to point to a special zero - element. Similarly, we could represent an all 1's element with - another special ones element pointer. - - 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. - - The bitset cache can be disabled either by setting cindex to - 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. -*/ - - -/* Number of words to use for each element. */ -#define EBITSET_ELT_WORDS 2 - -/* Number of bits stored in each element. */ -#define EBITSET_ELT_BITS \ - ((unsigned) (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. */ - struct ebitset_elt_struct *next; - } - u; -} -ebitset_elt; - - -typedef ebitset_elt *ebitset_elts; - - -/* Number of elements to initially allocate. */ - -#ifndef EBITSET_INITIAL_SIZE -# define EBITSET_INITIAL_SIZE 2 -#endif - - -enum ebitset_find_mode - { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST }; - -static ebitset_elt ebitset_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. */ - -#define EBITSET_N_ELTS(N) (((N) + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS) -#define EBITSET_ELTS(BSET) ((BSET)->e.elts) -#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) - -#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) \ - (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0) - -/* 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_ZERO_P(BSET) ((BSET)->b.cdata == 0) - -/* 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)) - -static bitset_bindex -ebitset_resize (bitset src, bitset_bindex n_bits) -{ - if (n_bits == BITSET_NBITS_ (src)) - return n_bits; - - bitset_windex oldsize = EBITSET_SIZE (src); - bitset_windex newsize = EBITSET_N_ELTS (n_bits); - - if (oldsize < newsize) - { - /* 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. */ - - bitset_windex size = oldsize == 0 ? newsize : 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 (void) -{ - ebitset_elt *elt; - - if (ebitset_free_list != 0) - { - elt = ebitset_free_list; - ebitset_free_list = EBITSET_NEXT (elt); - } - else - { - if (!ebitset_obstack_init) - { - ebitset_obstack_init = true; - - /* 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. */ - -#ifndef OBSTACK_CHUNK_ALLOC -#define OBSTACK_CHUNK_ALLOC xmalloc -#endif - -#ifndef OBSTACK_CHUNK_FREE -#define OBSTACK_CHUNK_FREE free -#endif - -#if ! defined __GNUC__ || __GNUC__ < 2 -#define __alignof__(type) 0 -#endif - - 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. */ - elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack, - sizeof (ebitset_elt)); - } - - return elt; -} - - -/* Allocate a ebitset element. The bits are cleared. */ -static inline ebitset_elt * -ebitset_elt_calloc (void) -{ - ebitset_elt *elt = ebitset_elt_alloc (); - memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt))); - return elt; -} - - -static inline void -ebitset_elt_free (ebitset_elt *elt) -{ - EBITSET_NEXT (elt) = ebitset_free_list; - ebitset_free_list = elt; -} - - -/* Remove element with index EINDEX from bitset BSET. */ -static inline void -ebitset_elt_remove (bitset bset, bitset_windex eindex) -{ - ebitset_elts *elts = EBITSET_ELTS (bset); - ebitset_elt *elt = elts[eindex]; - - elts[eindex] = 0; - ebitset_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) -{ - ebitset_elts *elts = EBITSET_ELTS (bset); - /* Assume that the elts entry not allocated. */ - elts[eindex] = elt; -} - - -/* Are all bits in an element zero? */ -static inline bool -ebitset_elt_zero_p (ebitset_elt *elt) -{ - for (int i = 0; i < EBITSET_ELT_WORDS; i++) - if (EBITSET_WORDS (elt)[i]) - return false; - return true; -} - - -static ebitset_elt * -ebitset_elt_find (bitset bset, bitset_bindex bindex, - enum ebitset_find_mode mode) -{ - bitset_windex eindex = bindex / EBITSET_ELT_BITS; - - ebitset_elts *elts = EBITSET_ELTS (bset); - bitset_windex size = EBITSET_SIZE (bset); - - if (eindex < size) - { - ebitset_elt *elt = elts[eindex]; - if (elt) - { - if (EBITSET_WORDS (elt) != bset->b.cdata) - 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) - ebitset_resize (bset, bindex); - - /* Create a new element. */ - { - ebitset_elt *elt = ebitset_elt_calloc (); - ebitset_elt_add (bset, elt, eindex); - EBITSET_CACHE_SET (bset, eindex); - return elt; - } - - case EBITSET_SUBST: - return &ebitset_zero_elts[0]; - } -} - - -/* Weed out the zero elements from the elts. */ -static inline bitset_windex -ebitset_weed (bitset bset) -{ - if (EBITSET_ZERO_P (bset)) - return 0; - - ebitset_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]; - - if (elt) - { - if (ebitset_elt_zero_p (elt)) - { - ebitset_elt_remove (bset, j); - count++; - } - } - else - 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_ZERO_SET (bset); - } - else - EBITSET_NONZERO_SET (bset); - - return count; -} - - -/* Set all bits in the bitset to zero. */ -static inline void -ebitset_zero (bitset bset) -{ - if (EBITSET_ZERO_P (bset)) - return; - - ebitset_elts *elts = EBITSET_ELTS (bset); - for (bitset_windex j = 0; j < EBITSET_SIZE (bset); j++) - { - ebitset_elt *elt = elts[j]; - if (elt) - ebitset_elt_remove (bset, j); - } - - /* 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 bool -ebitset_equal_p (bitset dst, bitset src) -{ - if (src == dst) - return true; - - ebitset_weed (dst); - ebitset_weed (src); - - if (EBITSET_SIZE (src) != EBITSET_SIZE (dst)) - return false; - - ebitset_elts *selts = EBITSET_ELTS (src); - ebitset_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]; - - if (!selt && !delt) - continue; - if ((selt && !delt) || (!selt && delt)) - return false; - - for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++) - if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i]) - return false; - } - return true; -} - - -/* Copy bits from bitset SRC to bitset DST. */ -static inline void -ebitset_copy_ (bitset dst, bitset src) -{ - if (src == dst) - return; - - ebitset_zero (dst); - - if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src)) - ebitset_resize (dst, BITSET_NBITS_ (src)); - - ebitset_elts *selts = EBITSET_ELTS (src); - ebitset_elts *delts = EBITSET_ELTS (dst); - for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++) - { - ebitset_elt *selt = selts[j]; - if (selt) - { - ebitset_elt *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 true if - bitsets different. */ -static inline bool -ebitset_copy_cmp (bitset dst, bitset src) -{ - if (src == dst) - return false; - - if (EBITSET_ZERO_P (dst)) - { - ebitset_copy_ (dst, src); - return !EBITSET_ZERO_P (src); - } - - if (ebitset_equal_p (dst, src)) - return false; - - ebitset_copy_ (dst, src); - return true; -} - - -/* Set bit BITNO in bitset DST. */ -static void -ebitset_set (bitset dst, bitset_bindex bitno) -{ - bitset_windex windex = bitno / BITSET_WORD_BITS; - - ebitset_elt_find (dst, bitno, EBITSET_CREATE); - - dst->b.cdata[windex - dst->b.cindex] |= - (bitset_word) 1 << (bitno % BITSET_WORD_BITS); -} - - -/* Reset bit BITNO in bitset DST. */ -static void -ebitset_reset (bitset dst, bitset_bindex bitno) -{ - bitset_windex windex = bitno / BITSET_WORD_BITS; - - 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... - However, there is a good chance that the element will be needed - again soon. */ -} - - -/* Test bit BITNO in bitset SRC. */ -static bool -ebitset_test (bitset src, bitset_bindex bitno) -{ - bitset_windex windex = bitno / BITSET_WORD_BITS; - - return (ebitset_elt_find (src, bitno, EBITSET_FIND) - && ((src->b.cdata[windex - src->b.cindex] - >> (bitno % BITSET_WORD_BITS)) - & 1)); -} - - -static void -ebitset_free (bitset bset) -{ - ebitset_zero (bset); - free (EBITSET_ELTS (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 bitset_bindex -ebitset_list_reverse (bitset bset, bitset_bindex *list, - bitset_bindex num, bitset_bindex *next) -{ - if (EBITSET_ZERO_P (bset)) - return 0; - - bitset_windex size = EBITSET_SIZE (bset); - bitset_bindex n_bits = size * EBITSET_ELT_BITS; - bitset_bindex rbitno = *next; - - if (rbitno >= n_bits) - return 0; - - ebitset_elts *elts = EBITSET_ELTS (bset); - - bitset_bindex bitno = n_bits - (rbitno + 1); - - bitset_windex windex = bitno / BITSET_WORD_BITS; - bitset_windex eindex = bitno / EBITSET_ELT_BITS; - bitset_windex woffset = windex - eindex * EBITSET_ELT_WORDS; - - /* If num is 1, we could speed things up with a binary search - of the word of interest. */ - bitset_bindex count = 0; - unsigned bcount = bitno % BITSET_WORD_BITS; - bitset_bindex boffset = windex * BITSET_WORD_BITS; - - do - { - ebitset_elt *elt = elts[eindex]; - if (elt) - { - bitset_word *srcp = EBITSET_WORDS (elt); - - do - { - for (bitset_word word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount); - 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; -} - - -/* 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 bitset_bindex -ebitset_list (bitset bset, bitset_bindex *list, - bitset_bindex num, bitset_bindex *next) -{ - if (EBITSET_ZERO_P (bset)) - return 0; - - bitset_bindex bitno = *next; - bitset_bindex count = 0; - - ebitset_elts *elts = EBITSET_ELTS (bset); - bitset_windex size = EBITSET_SIZE (bset); - bitset_windex eindex = bitno / EBITSET_ELT_BITS; - - if (bitno % EBITSET_ELT_BITS) - { - /* We need to start within an element. This is not very common. */ - - ebitset_elt *elt = elts[eindex]; - if (elt) - { - bitset_windex woffset; - bitset_word *srcp = EBITSET_WORDS (elt); - - bitset_windex windex = bitno / BITSET_WORD_BITS; - woffset = eindex * EBITSET_ELT_WORDS; - - for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++) - { - bitset_word 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++; - } - - /* If num is 1, we could speed things up with a binary search - of the word of interest. */ - - for (; eindex < size; eindex++) - { - bitset_word *srcp; - - ebitset_elt *elt = elts[eindex]; - if (!elt) - continue; - - srcp = EBITSET_WORDS (elt); - bitset_windex windex = eindex * EBITSET_ELT_WORDS; - - if ((count + EBITSET_ELT_BITS) < num) - { - /* The coast is clear, plant boot! */ - -#if EBITSET_ELT_WORDS == 2 - bitset_word 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 (int 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 (int i = 0; i < EBITSET_ELT_WORDS; i++, windex++) - { - bitno = windex * BITSET_WORD_BITS; - - for (bitset_word word = srcp[i]; word; bitno++) - { - if (word & 1) - { - list[count++] = bitno; - if (count >= num) - { - *next = bitno + 1; - return count; - } - } - word >>= 1; - } - } - } - } - - *next = bitno; - return count; -} - - -/* Ensure that any unused bits within the last element are clear. */ -static inline void -ebitset_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); - - bitset_windex eindex = n_bits / EBITSET_ELT_BITS; - - ebitset_elt *elt = elts[eindex]; - if (elt) - { - bitset_word *srcp = EBITSET_WORDS (elt); - - bitset_windex windex = n_bits / BITSET_WORD_BITS; - bitset_windex 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) -{ - 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); - memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt))); - } - EBITSET_NONZERO_SET (dst); - ebitset_unused_clear (dst); -} - - -static bool -ebitset_empty_p (bitset dst) -{ - if (EBITSET_ZERO_P (dst)) - return true; - - ebitset_elts *elts = EBITSET_ELTS (dst); - for (bitset_windex j = 0; j < EBITSET_SIZE (dst); j++) - { - ebitset_elt *elt = elts[j]; - - if (elt) - { - if (!ebitset_elt_zero_p (elt)) - return false; - /* 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 true; -} - - -static void -ebitset_not (bitset dst, bitset src) -{ - ebitset_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); - - 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); -} - - -/* Is DST == DST | SRC? */ -static bool -ebitset_subset_p (bitset dst, bitset src) -{ - ebitset_elts *selts = EBITSET_ELTS (src); - ebitset_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; - - if (!selt && !delt) - continue; - - if (!selt) - selt = &ebitset_zero_elts[0]; - if (!delt) - delt = &ebitset_zero_elts[0]; - - for (unsigned 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) -{ - ebitset_elts *selts = EBITSET_ELTS (src); - ebitset_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; - - if (!selt || !delt) - continue; - - for (unsigned 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) -{ - bool changed = false; - - ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2))); - - bitset_windex ssize1 = EBITSET_SIZE (src1); - bitset_windex ssize2 = EBITSET_SIZE (src2); - bitset_windex dsize = EBITSET_SIZE (dst); - bitset_windex size = ssize1; - if (size < ssize2) - size = ssize2; - - ebitset_elts *selts1 = EBITSET_ELTS (src1); - ebitset_elts *selts2 = EBITSET_ELTS (src2); - ebitset_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; - - if (!selt1 && !selt2) - { - if (delt) - { - changed = true; - ebitset_elt_remove (dst, j); - } - continue; - } - - if (!selt1) - selt1 = &ebitset_zero_elts[0]; - if (!selt2) - selt2 = &ebitset_zero_elts[0]; - if (!delt) - delt = ebitset_elt_calloc (); - else - delts[j] = 0; - - bitset_word *srcp1 = EBITSET_WORDS (selt1); - bitset_word *srcp2 = EBITSET_WORDS (selt2); - bitset_word *dstp = EBITSET_WORDS (delt); - switch (op) - { - default: - abort (); - - case BITSET_OP_OR: - for (unsigned 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 (unsigned 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 (unsigned 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 (unsigned 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); - } - else - { - ebitset_elt_free (delt); - } - } - - /* If we have elements of DST left over, free them all. */ - for (; j < dsize; j++) - { - changed = true; - - ebitset_elt *delt = delts[j]; - if (delt) - ebitset_elt_remove (dst, j); - } - - EBITSET_NONZERO_SET (dst); - return changed; -} - - -static bool -ebitset_and_cmp (bitset dst, bitset src1, bitset src2) -{ - if (EBITSET_ZERO_P (src2)) - { - ebitset_weed (dst); - bool changed = EBITSET_ZERO_P (dst); - ebitset_zero (dst); - return changed; - } - else if (EBITSET_ZERO_P (src1)) - { - ebitset_weed (dst); - bool 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) -{ - if (EBITSET_ZERO_P (src2)) - { - return ebitset_copy_cmp (dst, src1); - } - else if (EBITSET_ZERO_P (src1)) - { - ebitset_weed (dst); - bool 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_vtable ebitset_vtable = { - ebitset_set, - ebitset_reset, - bitset_toggle_, - ebitset_test, - 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_list_reverse, - ebitset_free, - BITSET_TABLE -}; - - -/* Return size of initial structure. */ -size_t -ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) -{ - return sizeof (struct ebitset_struct); -} - - -/* Initialize a bitset. */ - -bitset -ebitset_init (bitset bset, bitset_bindex n_bits) -{ - bset->b.vtable = &ebitset_vtable; - - bset->b.csize = EBITSET_ELT_WORDS; - - EBITSET_ZERO_SET (bset); - - EBITSET_ASIZE (bset) = 0; - EBITSET_ELTS (bset) = 0; - ebitset_resize (bset, n_bits); - - return bset; -} - - -void -ebitset_release_memory (void) -{ - ebitset_free_list = 0; - if (ebitset_obstack_init) - { - ebitset_obstack_init = false; - obstack_free (&ebitset_obstack, NULL); - } -}
--- a/lib/bitset/expandable.h Wed Nov 28 05:56:21 2018 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,32 +0,0 @@ -/* Functions to support ebitsets. - - Copyright (C) 2002, 2004, 2009-2015, 2018 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 - it under the terms of the GNU General Public License as published by - 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, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - 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, see <http://www.gnu.org/licenses/>. */ - -#ifndef _BITSET_EXPANDABLE_H -#define _BITSET_EXPANDABLE_H - -#include "bitset.h" - -size_t ebitset_bytes (bitset_bindex); - -bitset ebitset_init (bitset, bitset_bindex); - -void ebitset_release_memory (void); - -#endif
--- a/lib/bitset/stats.c Wed Nov 28 05:56:21 2018 +0100 +++ b/lib/bitset/stats.c Thu Nov 29 05:44:58 2018 +0100 @@ -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 @@ 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;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/bitset/table.c Thu Nov 29 05:44:58 2018 +0100 @@ -0,0 +1,1229 @@ +/* Functions to support expandable bitsets. + + Copyright (C) 2002-2006, 2009-2015, 2018 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 + it under the terms of the GNU General Public License as published by + 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, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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, see <http://www.gnu.org/licenses/>. */ + +#include <config.h> + +#include "bitset/table.h" + +#include <stdlib.h> +#include <string.h> + +#include "obstack.h" + +/* This file implements expandable bitsets. These bitsets can be of + arbitrary length and are more efficient than arrays of bits for + large sparse sets. + + Empty elements are represented by a NULL pointer in the table of + element pointers. An alternative is to point to a special zero + element. Similarly, we could represent an all 1's element with + another special ones element pointer. + + 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. + + The bitset cache can be disabled either by setting cindex to + 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. +*/ + + +/* Number of words to use for each element. */ +#define EBITSET_ELT_WORDS 2 + +/* Number of bits stored in each element. */ +#define EBITSET_ELT_BITS \ + ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS)) + +/* Ebitset element. We use an array of bits. */ +typedef struct tbitset_elt_struct +{ + union + { + bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */ + struct tbitset_elt_struct *next; + } + u; +} +tbitset_elt; + + +typedef tbitset_elt *tbitset_elts; + + +/* Number of elements to initially allocate. */ + +#ifndef EBITSET_INITIAL_SIZE +# define EBITSET_INITIAL_SIZE 2 +#endif + + +enum tbitset_find_mode + { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST }; + +static tbitset_elt tbitset_zero_elts[1]; /* Elements of all zero bits. */ + +/* Obstack to allocate bitset elements from. */ +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) +#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) + +#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) \ + (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0) + +/* 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_ZERO_P(BSET) ((BSET)->b.cdata == 0) + +/* 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)) + +static bitset_bindex +tbitset_resize (bitset src, bitset_bindex n_bits) +{ + if (n_bits == BITSET_NBITS_ (src)) + return n_bits; + + bitset_windex oldsize = EBITSET_SIZE (src); + bitset_windex newsize = EBITSET_N_ELTS (n_bits); + + if (oldsize < newsize) + { + /* 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. */ + + bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4; + EBITSET_ELTS (src) + = realloc (EBITSET_ELTS (src), size * sizeof (tbitset_elt *)); + EBITSET_ASIZE (src) = size; + } + + memset (EBITSET_ELTS (src) + oldsize, 0, + (newsize - oldsize) * sizeof (tbitset_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 (tbitset_elt *)); + EBITSET_ASIZE (src) = newsize; + } + + /* Need to prune any excess bits. FIXME. */ + } + + BITSET_NBITS_ (src) = n_bits; + return n_bits; +} + + +/* Allocate a tbitset element. The bits are not cleared. */ +static inline tbitset_elt * +tbitset_elt_alloc (void) +{ + tbitset_elt *elt; + + if (tbitset_free_list != 0) + { + elt = tbitset_free_list; + tbitset_free_list = EBITSET_NEXT (elt); + } + else + { + if (!tbitset_obstack_init) + { + tbitset_obstack_init = true; + + /* 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. */ + +#ifndef OBSTACK_CHUNK_ALLOC +#define OBSTACK_CHUNK_ALLOC xmalloc +#endif + +#ifndef OBSTACK_CHUNK_FREE +#define OBSTACK_CHUNK_FREE free +#endif + +#if ! defined __GNUC__ || __GNUC__ < 2 +#define __alignof__(type) 0 +#endif + + 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 = (tbitset_elt *) obstack_alloc (&tbitset_obstack, + sizeof (tbitset_elt)); + } + + return elt; +} + + +/* Allocate a tbitset element. The bits are cleared. */ +static inline tbitset_elt * +tbitset_elt_calloc (void) +{ + tbitset_elt *elt = tbitset_elt_alloc (); + memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt))); + return elt; +} + + +static inline void +tbitset_elt_free (tbitset_elt *elt) +{ + EBITSET_NEXT (elt) = tbitset_free_list; + tbitset_free_list = elt; +} + + +/* Remove element with index EINDEX from bitset BSET. */ +static inline void +tbitset_elt_remove (bitset bset, bitset_windex eindex) +{ + tbitset_elts *elts = EBITSET_ELTS (bset); + tbitset_elt *elt = elts[eindex]; + + elts[eindex] = 0; + tbitset_elt_free (elt); +} + + +/* Add ELT into elts at index EINDEX of bitset BSET. */ +static inline void +tbitset_elt_add (bitset bset, tbitset_elt *elt, bitset_windex eindex) +{ + tbitset_elts *elts = EBITSET_ELTS (bset); + /* Assume that the elts entry not allocated. */ + elts[eindex] = elt; +} + + +/* Are all bits in an element zero? */ +static inline bool +tbitset_elt_zero_p (tbitset_elt *elt) +{ + for (int i = 0; i < EBITSET_ELT_WORDS; i++) + if (EBITSET_WORDS (elt)[i]) + return false; + return true; +} + + +static tbitset_elt * +tbitset_elt_find (bitset bset, bitset_bindex bindex, + enum tbitset_find_mode mode) +{ + bitset_windex eindex = bindex / EBITSET_ELT_BITS; + + tbitset_elts *elts = EBITSET_ELTS (bset); + bitset_windex size = EBITSET_SIZE (bset); + + if (eindex < size) + { + tbitset_elt *elt = elts[eindex]; + if (elt) + { + if (EBITSET_WORDS (elt) != bset->b.cdata) + 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) + tbitset_resize (bset, bindex); + + /* Create a new element. */ + { + tbitset_elt *elt = tbitset_elt_calloc (); + tbitset_elt_add (bset, elt, eindex); + EBITSET_CACHE_SET (bset, eindex); + return elt; + } + + case EBITSET_SUBST: + return &tbitset_zero_elts[0]; + } +} + + +/* Weed out the zero elements from the elts. */ +static inline bitset_windex +tbitset_weed (bitset bset) +{ + if (EBITSET_ZERO_P (bset)) + return 0; + + tbitset_elts *elts = EBITSET_ELTS (bset); + bitset_windex count = 0; + bitset_windex j; + for (j = 0; j < EBITSET_SIZE (bset); j++) + { + tbitset_elt *elt = elts[j]; + + if (elt) + { + if (tbitset_elt_zero_p (elt)) + { + tbitset_elt_remove (bset, j); + count++; + } + } + else + 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_ZERO_SET (bset); + } + else + EBITSET_NONZERO_SET (bset); + + return count; +} + + +/* Set all bits in the bitset to zero. */ +static inline void +tbitset_zero (bitset bset) +{ + if (EBITSET_ZERO_P (bset)) + return; + + tbitset_elts *elts = EBITSET_ELTS (bset); + for (bitset_windex j = 0; j < EBITSET_SIZE (bset); j++) + { + tbitset_elt *elt = elts[j]; + if (elt) + tbitset_elt_remove (bset, j); + } + + /* 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 bool +tbitset_equal_p (bitset dst, bitset src) +{ + if (src == dst) + return true; + + tbitset_weed (dst); + tbitset_weed (src); + + if (EBITSET_SIZE (src) != EBITSET_SIZE (dst)) + return false; + + tbitset_elts *selts = EBITSET_ELTS (src); + tbitset_elts *delts = EBITSET_ELTS (dst); + + for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++) + { + tbitset_elt *selt = selts[j]; + tbitset_elt *delt = delts[j]; + + if (!selt && !delt) + continue; + if ((selt && !delt) || (!selt && delt)) + return false; + + for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++) + if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i]) + return false; + } + return true; +} + + +/* Copy bits from bitset SRC to bitset DST. */ +static inline void +tbitset_copy_ (bitset dst, bitset src) +{ + if (src == dst) + return; + + tbitset_zero (dst); + + if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src)) + tbitset_resize (dst, BITSET_NBITS_ (src)); + + tbitset_elts *selts = EBITSET_ELTS (src); + tbitset_elts *delts = EBITSET_ELTS (dst); + for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++) + { + tbitset_elt *selt = selts[j]; + if (selt) + { + tbitset_elt *tmp = tbitset_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 true if + bitsets different. */ +static inline bool +tbitset_copy_cmp (bitset dst, bitset src) +{ + if (src == dst) + return false; + + if (EBITSET_ZERO_P (dst)) + { + tbitset_copy_ (dst, src); + return !EBITSET_ZERO_P (src); + } + + if (tbitset_equal_p (dst, src)) + return false; + + tbitset_copy_ (dst, src); + return true; +} + + +/* Set bit BITNO in bitset DST. */ +static void +tbitset_set (bitset dst, bitset_bindex bitno) +{ + bitset_windex windex = bitno / BITSET_WORD_BITS; + + tbitset_elt_find (dst, bitno, EBITSET_CREATE); + + dst->b.cdata[windex - dst->b.cindex] |= + (bitset_word) 1 << (bitno % BITSET_WORD_BITS); +} + + +/* Reset bit BITNO in bitset DST. */ +static void +tbitset_reset (bitset dst, bitset_bindex bitno) +{ + bitset_windex windex = bitno / BITSET_WORD_BITS; + + if (!tbitset_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... + However, there is a good chance that the element will be needed + again soon. */ +} + + +/* Test bit BITNO in bitset SRC. */ +static bool +tbitset_test (bitset src, bitset_bindex bitno) +{ + bitset_windex windex = bitno / BITSET_WORD_BITS; + + return (tbitset_elt_find (src, bitno, EBITSET_FIND) + && ((src->b.cdata[windex - src->b.cindex] + >> (bitno % BITSET_WORD_BITS)) + & 1)); +} + + +static void +tbitset_free (bitset bset) +{ + tbitset_zero (bset); + free (EBITSET_ELTS (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 bitset_bindex +tbitset_list_reverse (bitset bset, bitset_bindex *list, + bitset_bindex num, bitset_bindex *next) +{ + if (EBITSET_ZERO_P (bset)) + return 0; + + bitset_windex size = EBITSET_SIZE (bset); + bitset_bindex n_bits = size * EBITSET_ELT_BITS; + bitset_bindex rbitno = *next; + + if (rbitno >= n_bits) + return 0; + + tbitset_elts *elts = EBITSET_ELTS (bset); + + bitset_bindex bitno = n_bits - (rbitno + 1); + + bitset_windex windex = bitno / BITSET_WORD_BITS; + bitset_windex eindex = bitno / EBITSET_ELT_BITS; + bitset_windex woffset = windex - eindex * EBITSET_ELT_WORDS; + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + bitset_bindex count = 0; + unsigned bcount = bitno % BITSET_WORD_BITS; + bitset_bindex boffset = windex * BITSET_WORD_BITS; + + do + { + tbitset_elt *elt = elts[eindex]; + if (elt) + { + bitset_word *srcp = EBITSET_WORDS (elt); + + do + { + for (bitset_word word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount); + 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; +} + + +/* 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 bitset_bindex +tbitset_list (bitset bset, bitset_bindex *list, + bitset_bindex num, bitset_bindex *next) +{ + if (EBITSET_ZERO_P (bset)) + return 0; + + bitset_bindex bitno = *next; + bitset_bindex count = 0; + + tbitset_elts *elts = EBITSET_ELTS (bset); + bitset_windex size = EBITSET_SIZE (bset); + bitset_windex eindex = bitno / EBITSET_ELT_BITS; + + if (bitno % EBITSET_ELT_BITS) + { + /* We need to start within an element. This is not very common. */ + + tbitset_elt *elt = elts[eindex]; + if (elt) + { + bitset_windex woffset; + bitset_word *srcp = EBITSET_WORDS (elt); + + bitset_windex windex = bitno / BITSET_WORD_BITS; + woffset = eindex * EBITSET_ELT_WORDS; + + for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++) + { + bitset_word 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++; + } + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + for (; eindex < size; eindex++) + { + bitset_word *srcp; + + tbitset_elt *elt = elts[eindex]; + if (!elt) + continue; + + srcp = EBITSET_WORDS (elt); + bitset_windex windex = eindex * EBITSET_ELT_WORDS; + + if ((count + EBITSET_ELT_BITS) < num) + { + /* The coast is clear, plant boot! */ + +#if EBITSET_ELT_WORDS == 2 + bitset_word 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 (int 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 (int i = 0; i < EBITSET_ELT_WORDS; i++, windex++) + { + bitno = windex * BITSET_WORD_BITS; + + for (bitset_word word = srcp[i]; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + } + } + } + + *next = bitno; + return count; +} + + +/* Ensure that any unused bits within the last element are clear. */ +static inline void +tbitset_unused_clear (bitset dst) +{ + bitset_bindex n_bits = BITSET_NBITS_ (dst); + unsigned last_bit = n_bits % EBITSET_ELT_BITS; + + if (last_bit) + { + tbitset_elts *elts = EBITSET_ELTS (dst); + + bitset_windex eindex = n_bits / EBITSET_ELT_BITS; + + tbitset_elt *elt = elts[eindex]; + if (elt) + { + bitset_word *srcp = EBITSET_WORDS (elt); + + bitset_windex windex = n_bits / BITSET_WORD_BITS; + bitset_windex 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 +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? */ + 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); + tbitset_unused_clear (dst); +} + + +static bool +tbitset_empty_p (bitset dst) +{ + if (EBITSET_ZERO_P (dst)) + return true; + + tbitset_elts *elts = EBITSET_ELTS (dst); + for (bitset_windex j = 0; j < EBITSET_SIZE (dst); j++) + { + tbitset_elt *elt = elts[j]; + + if (elt) + { + if (!tbitset_elt_zero_p (elt)) + return false; + /* Do some weeding as we go. */ + tbitset_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 true; +} + + +static void +tbitset_not (bitset dst, bitset 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. */ + 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); + tbitset_unused_clear (dst); +} + + +/* Is DST == DST | SRC? */ +static bool +tbitset_subset_p (bitset dst, bitset src) +{ + 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++) + { + tbitset_elt *selt = j < ssize ? selts[j] : 0; + tbitset_elt *delt = j < dsize ? delts[j] : 0; + + if (!selt && !delt) + continue; + + if (!selt) + selt = &tbitset_zero_elts[0]; + if (!delt) + delt = &tbitset_zero_elts[0]; + + for (unsigned 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 +tbitset_disjoint_p (bitset dst, bitset src) +{ + 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++) + { + tbitset_elt *selt = j < ssize ? selts[j] : 0; + tbitset_elt *delt = j < dsize ? delts[j] : 0; + + if (!selt || !delt) + continue; + + for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++) + if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i])) + return false; + } + return true; +} + + + +static bool +tbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) +{ + bool changed = false; + + tbitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2))); + + bitset_windex ssize1 = EBITSET_SIZE (src1); + bitset_windex ssize2 = EBITSET_SIZE (src2); + bitset_windex dsize = EBITSET_SIZE (dst); + bitset_windex size = ssize1; + if (size < ssize2) + size = ssize2; + + 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++) + { + 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; + tbitset_elt_remove (dst, j); + } + continue; + } + + if (!selt1) + selt1 = &tbitset_zero_elts[0]; + if (!selt2) + selt2 = &tbitset_zero_elts[0]; + if (!delt) + delt = tbitset_elt_calloc (); + else + delts[j] = 0; + + bitset_word *srcp1 = EBITSET_WORDS (selt1); + bitset_word *srcp2 = EBITSET_WORDS (selt2); + bitset_word *dstp = EBITSET_WORDS (delt); + switch (op) + { + default: + abort (); + + case BITSET_OP_OR: + for (unsigned 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 (unsigned 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 (unsigned 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 (unsigned i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) + { + bitset_word tmp = *srcp1++ & ~(*srcp2++); + + if (*dstp != tmp) + { + changed = true; + *dstp = tmp; + } + } + break; + } + + if (!tbitset_elt_zero_p (delt)) + { + tbitset_elt_add (dst, delt, j); + } + else + { + tbitset_elt_free (delt); + } + } + + /* If we have elements of DST left over, free them all. */ + for (; j < dsize; j++) + { + changed = true; + + tbitset_elt *delt = delts[j]; + if (delt) + tbitset_elt_remove (dst, j); + } + + EBITSET_NONZERO_SET (dst); + return changed; +} + + +static bool +tbitset_and_cmp (bitset dst, bitset src1, bitset src2) +{ + if (EBITSET_ZERO_P (src2)) + { + tbitset_weed (dst); + bool changed = EBITSET_ZERO_P (dst); + tbitset_zero (dst); + return changed; + } + else if (EBITSET_ZERO_P (src1)) + { + tbitset_weed (dst); + bool changed = EBITSET_ZERO_P (dst); + tbitset_zero (dst); + return changed; + } + return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND); +} + + +static void +tbitset_and (bitset dst, bitset src1, bitset src2) +{ + tbitset_and_cmp (dst, src1, src2); +} + + +static bool +tbitset_andn_cmp (bitset dst, bitset src1, bitset src2) +{ + if (EBITSET_ZERO_P (src2)) + { + return tbitset_copy_cmp (dst, src1); + } + else if (EBITSET_ZERO_P (src1)) + { + tbitset_weed (dst); + bool changed = EBITSET_ZERO_P (dst); + tbitset_zero (dst); + return changed; + } + return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN); +} + + +static void +tbitset_andn (bitset dst, bitset src1, bitset src2) +{ + tbitset_andn_cmp (dst, src1, src2); +} + + +static bool +tbitset_or_cmp (bitset dst, bitset src1, bitset src2) +{ + if (EBITSET_ZERO_P (src2)) + { + return tbitset_copy_cmp (dst, src1); + } + else if (EBITSET_ZERO_P (src1)) + { + return tbitset_copy_cmp (dst, src2); + } + return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR); +} + + +static void +tbitset_or (bitset dst, bitset src1, bitset src2) +{ + tbitset_or_cmp (dst, src1, src2); +} + + +static bool +tbitset_xor_cmp (bitset dst, bitset src1, bitset src2) +{ + if (EBITSET_ZERO_P (src2)) + { + return tbitset_copy_cmp (dst, src1); + } + else if (EBITSET_ZERO_P (src1)) + { + return tbitset_copy_cmp (dst, src2); + } + return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR); +} + + +static void +tbitset_xor (bitset dst, bitset src1, bitset src2) +{ + tbitset_xor_cmp (dst, src1, src2); +} + + +static void +tbitset_copy (bitset dst, bitset src) +{ + if (BITSET_COMPATIBLE_ (dst, src)) + tbitset_copy_ (dst, src); + else + bitset_copy_ (dst, src); +} + + +/* Vector of operations for linked-list bitsets. */ +struct bitset_vtable tbitset_vtable = { + tbitset_set, + tbitset_reset, + bitset_toggle_, + tbitset_test, + tbitset_resize, + bitset_size_, + bitset_count_, + 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_, + tbitset_list, + tbitset_list_reverse, + tbitset_free, + BITSET_TABLE +}; + + +/* Return size of initial structure. */ +size_t +tbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) +{ + return sizeof (struct tbitset_struct); +} + + +/* Initialize a bitset. */ + +bitset +tbitset_init (bitset bset, bitset_bindex n_bits) +{ + bset->b.vtable = &tbitset_vtable; + + bset->b.csize = EBITSET_ELT_WORDS; + + EBITSET_ZERO_SET (bset); + + EBITSET_ASIZE (bset) = 0; + EBITSET_ELTS (bset) = 0; + tbitset_resize (bset, n_bits); + + return bset; +} + + +void +tbitset_release_memory (void) +{ + tbitset_free_list = 0; + if (tbitset_obstack_init) + { + tbitset_obstack_init = false; + obstack_free (&tbitset_obstack, NULL); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/bitset/table.h Thu Nov 29 05:44:58 2018 +0100 @@ -0,0 +1,32 @@ +/* Functions to support tbitsets. + + Copyright (C) 2002, 2004, 2009-2015, 2018 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 + it under the terms of the GNU General Public License as published by + 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, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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, see <http://www.gnu.org/licenses/>. */ + +#ifndef _BITSET_TABLE_H +#define _BITSET_TABLE_H + +#include "bitset.h" + +size_t tbitset_bytes (bitset_bindex); + +bitset tbitset_init (bitset, bitset_bindex); + +void tbitset_release_memory (void); + +#endif
--- a/modules/bitset Wed Nov 28 05:56:21 2018 +0100 +++ b/modules/bitset Thu Nov 29 05:44:58 2018 +0100 @@ -7,12 +7,12 @@ 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 @@ 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"