diff options
| -rw-r--r-- | ChangeLog | 8 | ||||
| -rw-r--r-- | lib/Makefile.am | 1 | ||||
| -rw-r--r-- | lib/bbitset.h | 275 | ||||
| -rw-r--r-- | lib/bitset.c | 491 | ||||
| -rw-r--r-- | lib/bitset.h | 163 | ||||
| -rw-r--r-- | lib/bitsetv.c | 106 | ||||
| -rw-r--r-- | lib/bitsetv.h | 7 | ||||
| -rw-r--r-- | lib/ebitset.c | 397 | ||||
| -rw-r--r-- | lib/ebitset.h | 34 | ||||
| -rw-r--r-- | lib/lbitset.c | 410 | ||||
| -rw-r--r-- | lib/lbitset.h | 38 | ||||
| -rw-r--r-- | lib/sbitset.c | 301 | ||||
| -rw-r--r-- | lib/sbitset.h | 11 |
13 files changed, 1284 insertions, 958 deletions
@@ -1,5 +1,13 @@ 2002-03-04 Akim Demaille <akim@epita.fr> + * lib/bitset.c, lib/bitset.h, lib/bitsetv.c, lib/bitsetv.h, + * lib/ebitset.c, lib/ebitset.h, lib/lbitset.c, lib/lbitset.h, + * lib/sbitset.c, lib/sbitset.h, lib/bbitset.h: Update from the + latest sources from Michael. + + +2002-03-04 Akim Demaille <akim@epita.fr> + * src/output.c (output): Don't free the grammar. * src/reader.c (grammar_free): New. * src/main.c (main): Call it and don't free symtab here. diff --git a/lib/Makefile.am b/lib/Makefile.am index 5dfdb11c..d60dbfa1 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -44,6 +44,7 @@ libbison_a_SOURCES = \ # Implementation of bitsets libbison_a_SOURCES += \ + bbitset.h \ bitset-int.h bitset.h bitsetv.h ebitset.h lbitset.h sbitset.h \ bitset.c bitsetv.c ebitset.c lbitset.c sbitset.c diff --git a/lib/bbitset.h b/lib/bbitset.h new file mode 100644 index 00000000..a20e285f --- /dev/null +++ b/lib/bbitset.h @@ -0,0 +1,275 @@ +/* Base bitset stuff. + Copyright (C) 2002 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 2 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, write to the Free Software +Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#ifndef _BBITSET_H +#define _BBITSET_H + +/* Bison modifications: BEGIN. */ +#define IN_BISON 1 +#if IN_BISON +# if HAVE_CONFIG_H +# include <config.h> +# endif +# include <stdlib.h> + +# define BITSET_STATS 1 +/* This file is the public interface to the bitset abstract data type. + Only use the functions and macros defined in this file. */ + +# ifndef PARAMS +# if defined PROTOTYPES || (defined __STDC__ && __STDC__) +# define PARAMS(Args) Args +# else +# define PARAMS(Args) () +# endif +# endif + +# ifndef __attribute__ +# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__ +# define __attribute__(x) +# endif +# endif + +# ifndef ATTRIBUTE_NORETURN +# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__)) +# endif + +# ifndef ATTRIBUTE_UNUSED +# define ATTRIBUTE_UNUSED __attribute__ ((__unused__)) +# endif +# include "xalloc.h" +#else /* ! IN_BISON */ +# include "libiberty.h" +#endif + +#ifdef HAVE_LIMITS_H +#include <limits.h> +#endif + +/* Currently we support three flavours of bitsets: + BITSET_ARRAY: Array of bits (fixed size, faster). + BITSET_LIST: Linked list of array of bits (variable size, least storage + for large very sparse sets). + BITSET_TABLE: Expandable table of pointers to array of bits + (variable size, less storage for large sparse sets). +*/ +enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM}; +#define BITSET_TYPE_NAMES {"sbitset", "lbitset", "ebitset"} + +/* Non-zero to enable bitset caching. */ +#define BITSET_CACHE 1 + +/* Non-zero to use inline functions instead of macros. */ +#define BITSET_INLINE 0 + +/* Non-zero to enable bitset statistics gathering. */ +#define BITSET_STATS 1 + +/* Non-zero to enable bitset type checking. */ +#define BITSET_CHECK 1 + +/* Data type used to store a word of bits. */ +typedef unsigned long bitset_word; +#define BITSET_WORD_BITS ((unsigned) CHAR_BIT * sizeof (bitset_word)) + +/* Bit index. */ +typedef unsigned long bitset_bindex; + +/* Word index. */ +typedef unsigned long bitset_windex; + +#define BITSET_INDEX_MAX ((1U << (BITSET_WORD_BITS - 1))) + +#define BITSET_MSB (1U << (BITSET_WORD_BITS - 1)) + +#define BITSET_LIST_SIZE 1024 + +enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES, + BITSET_OP_COPY, BITSET_OP_NOT, + BITSET_OP_EMPTY_P, BITSET_OP_EQUAL_P, + BITSET_OP_SUBSET_P, BITSET_OP_DISJOINT_P, + BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, + BITSET_OP_ANDN, BITSET_OP_ORN, + BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR}; + +/* Return size in bits of bitset SRC. */ +#define BITSET_SIZE_(SRC) (SRC)->b.ops->size (SRC) + +/* Return type of bitset SRC. */ +#define BITSET_TYPE_(DST) (DST)->b.ops->type + +/* Set bit BITNO in bitset DST. */ +#define BITSET_SET_(DST, BITNO) (DST)->b.ops->set (DST, BITNO) + +/* Reset bit BITNO in bitset DST. */ +#define BITSET_RESET_(DST, BITNO) (DST)->b.ops->reset (DST, BITNO) + +/* Return non-zero if bit BITNO in bitset SRC is set. */ +#define BITSET_TEST_(SRC, BITNO) (SRC)->b.ops->test (SRC, BITNO) + +/* Free bitset SRC. */ +#define BITSET_FREE_(SRC)\ + ((SRC)->b.ops->free ? (SRC)->b.ops->free (SRC) :(void)0) + +/* Perform operation OP on DST. */ +#define BITSET_OP1_(DST, OP) (DST)->b.ops->op1 (DST, OP) + +/* Perform operation OP on SRC and store in DST. */ +#define BITSET_OP2_(DST, SRC, OP) (DST)->b.ops->op2 (DST, SRC, OP) + +/* DST = SRC1 OP SRC2. */ +#define BITSET_OP3_(DST, SRC1, SRC2, OP) \ +(DST)->b.ops->op3 (DST, SRC1, SRC2, OP) + +/* DST = (SRC1 OP1 SRC2) OP2 SRC3. */ +#define BITSET_OP4_(DST, SRC1, SRC2, SRC3, OP) \ +(DST)->b.ops->op4 (DST, SRC1, SRC2, SRC3, OP) + +/* DST = 0. */ +#define BITSET_ZERO_(DST) BITSET_OP1_ (DST, BITSET_OP_ZERO); + +/* DST = ~0. */ +#define BITSET_ONES_(DST) BITSET_OP1_ (DST, BITSET_OP_ONES); + +/* Return SRC == 0. */ +#define BITSET_EMPTY_P_(SRC) BITSET_OP1_ (SRC, BITSET_OP_EMPTY_P); + +/* Return DST == SRC. */ +#define BITSET_EQUAL_P_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_EQUAL_P) + +/* Return DST == DST | SRC. */ +#define BITSET_SUBSET_P_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_SUBSET_P) + +/* Return DST & SRC == 0. */ +#define BITSET_DISJOINT_P_(DST, SRC)\ + BITSET_OP2_ (DST, SRC, BITSET_OP_DISJOINT_P) + +/* DST = SRC. */ +#define BITSET_COPY_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_COPY) + +/* DST = ~SRC. */ +#define BITSET_NOT_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_NOT) + +/* DST = SRC1 | SRC2. */ +#define BITSET_OR_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2,\ + BITSET_OP_OR) + +/* DST = SRC1 ^ SRC2. */ +#define BITSET_XOR_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2,\ + BITSET_OP_XOR) + +/* DST = SRC1 & SRC2. */ +#define BITSET_AND_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \ + BITSET_OP_AND) + +/* DST = SRC1 & ~SRC2. */ +#define BITSET_ANDN_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \ + BITSET_OP_ANDN) + +/* DST = SRC1 | ~SRC2. */ +#define BITSET_ORN_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \ + BITSET_OP_ORN) + +/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if + DST != (SRC1 & SRC2) | SRC3. */ +#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3)\ + BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_AND_OR) + +/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if + DST != (SRC1 | SRC2) & SRC3. */ +#define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3)\ + BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_OR_AND) + +/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if + DST != (SRC1 & ~SRC2) | SRC3. */ +#define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3)\ + BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_ANDN_OR) + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT. Return with actual number of bits found and with *NEXT + indicating where search stopped. */ +#define BITSET_LIST_(BSET, LIST, NUM, NEXT) \ +(BSET)->b.ops->list (BSET, LIST, NUM, NEXT) + +/* Find reverse list of up to NUM bits set in BSET starting from and + including NEXT. Return with actual number of bits found and with + *NEXT indicating where search stopped. */ +#define BITSET_REVERSE_LIST_(BSET, LIST, NUM, NEXT) \ +(BSET)->b.ops->reverse_list (BSET, LIST, NUM, NEXT) + + +struct bbitset_struct +{ + struct bitset_ops_struct *ops; + bitset_windex cindex; /* Cache word index. */ + bitset_windex csize; /* Cache size in words. */ + bitset_word *cdata; /* Cache data pointer. */ +}; + + +typedef struct bitset_struct *bitset; + + +/* The contents of this structure should be considered private. */ +struct bitset_ops_struct +{ + void (*set) PARAMS ((struct bitset_struct *, bitset_bindex)); + void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex)); + int (*test) PARAMS ((struct bitset_struct *, bitset_bindex)); + int (*size) PARAMS ((struct bitset_struct *)); + int (*op1) PARAMS ((struct bitset_struct *, enum bitset_ops)); + int (*op2) PARAMS ((struct bitset_struct *, struct bitset_struct *, + enum bitset_ops)); + int (*op3) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, enum bitset_ops)); + int (*op4) PARAMS ((struct bitset_struct *, struct bitset_struct *, + struct bitset_struct *, struct bitset_struct *, + enum bitset_ops)); + int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *, + bitset_bindex, bitset_bindex *)); + int (*reverse_list) PARAMS ((struct bitset_struct *, bitset_bindex *, + bitset_bindex, bitset_bindex *)); + void (*free) PARAMS ((struct bitset_struct *)); + enum bitset_type type; +}; + +#define BITSET_COMPATIBLE_(BSET1, BSET2) ((BSET1)->b.ops == (BSET2)->b.ops) + +#if BITSET_CHECK +#define BITSET_CHECK2_(DST, SRC) \ +if (!BITSET_COMPATIBLE_ (DST, SRC)) abort (); + +#define BITSET_CHECK3_(DST, SRC1, SRC2) \ +if (!BITSET_COMPATIBLE_ (DST, SRC1) \ + || !BITSET_COMPATIBLE_ (DST, SRC2)) abort (); + +#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \ +if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \ + || !BITSET_COMPATIBLE_ (DST, SRC3)) abort (); +#else +#define BITSET_CHECK2_(DST, SRC) + +#define BITSET_CHECK3_(DST, SRC1, SRC2) + +#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) +#endif + +extern int bitset_op4 PARAMS ((bitset, bitset, bitset, bitset, + enum bitset_ops op)); + +#endif /* _BBITSET_H */ diff --git a/lib/bitset.c b/lib/bitset.c index c68ed788..23df1791 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -2,19 +2,19 @@ Copyright (C) 2002 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 2 of the License, or -(at your option) any later version. + 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 + (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. + 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, write to the Free Software -Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + 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. */ #ifdef HAVE_CONFIG_H #include "config.h" @@ -22,28 +22,13 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include <stdlib.h> #include "bitset.h" +#include "sbitset.h" +#include "lbitset.h" +#include "ebitset.h" #include "obstack.h" static void bitset_print PARAMS ((FILE *, bitset, int)); -#if BITSET_CHECK -#define BITSET__CHECK2(DST, SRC) \ -if ((DST)->OPS != (SRC)->OPS) abort (); - -#define BITSET__CHECK3(DST, SRC1, SRC2) \ -if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS) abort (); - -#define BITSET__CHECK4(DST, SRC1, SRC2) \ -if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS \ - || (DST)->OPS != (SRC3)->OPS) abort (); -#else -#define BITSET__CHECK2(DST, SRC) - -#define BITSET__CHECK3(DST, SRC1, SRC2) - -#define BITSET__CHECK4(DST, SRC1, SRC2, SRC3) -#endif - #if BITSET_STATS #define BITSET_STATS_FILE "bitset.dat" @@ -65,8 +50,8 @@ struct bitset_type_stats_struct struct bitset_stats_struct { - unsigned int runs; - struct bitset_type_stats_struct types[BITSET_TYPE_NUM]; + unsigned int runs; + struct bitset_type_stats_struct types[BITSET_TYPE_NUM]; }; struct bitset_stats_struct bitset_stats_data; @@ -78,9 +63,10 @@ static void bitset_percent_histogram_print PARAMS ((FILE *, const char *, unsigned int *)); static void bitset_log_histogram_print PARAMS ((FILE *, const char *, const char *, - unsigned int, unsigned int *)); -static void bitset_stats_print_1 PARAMS ((FILE *, const char *, - struct bitset_type_stats_struct *)); + unsigned int, + unsigned int *)); +static void bitset_stats_print_1 +PARAMS ((FILE *, const char *, struct bitset_type_stats_struct *)); static void bitset_stats_print PARAMS ((FILE *, int)); static void bitset_stats_read PARAMS ((void)); static void bitset_stats_write PARAMS ((void)); @@ -91,31 +77,31 @@ static void bitset_stats_write PARAMS ((void)); #define BITSET_STATS_XFREES_INC(BSET) \ if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].xfrees++ + bitset_stats->types[BITSET_TYPE_ (BSET)].xfrees++ #define BITSET_STATS_OBALLOCS_INC(TYPE) \ if (bitset_stats) \ bitset_stats->types[(TYPE)].oballocs++ -#define BITSET_STATS_OBFREES_INC(BSET) \ +#define BITSET_STATS_OBFREES_INC(BSET) \ if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].obfrees++ + bitset_stats->types[BITSET_TYPE_ (BSET)].obfrees++ #define BITSET_STATS_LISTS_INC(BSET) \ if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].lists++ + bitset_stats->types[BITSET_TYPE_ (BSET)].lists++ #define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \ if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].list_counts[(I)]++ + bitset_stats->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++ #define BITSET_STATS_LIST_SIZES_INC(BSET, I) \ if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].list_sizes[(I)]++ + bitset_stats->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++ #define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \ if (bitset_stats) \ - bitset_stats->types[(BSET)->ops->type].list_density[(I)]++ + bitset_stats->types[BITSET_TYPE_ (BSET)].list_density[(I)]++ #else #define BITSET_STATS_XMALLOCS_INC(TYPE) @@ -136,7 +122,6 @@ static void bitset_stats_write PARAMS ((void)); #endif /* BITSET_STATS */ - /* Return number of bytes required to create a N_BIT bitset of TYPE. The bitset may grow to require more bytes than this. */ int @@ -202,7 +187,7 @@ bitset_type_choose (n_bits, attr) { enum bitset_type type; -#ifdef ENABLE_CHECKING +#if BITSET_CHECK /* Check attributes. */ if (attr & BITSET_FIXED && attr & BITSET_VARIABLE) abort (); @@ -241,7 +226,11 @@ bitset_alloc (n_bits, type) bytes = bitset_bytes (type, n_bits); - bset = (bitset) xmalloc (bytes); + bset = (bitset) xcalloc (1, bytes); + + /* The cache is disabled until some elements are allocated. If we + have variable length arrays, then we may need to allocate dummy + element. */ return bitset_init (bset, n_bits, type); } @@ -250,17 +239,21 @@ bitset_alloc (n_bits, type) /* Create a bitset of N_BITS of type TYPE. */ bitset bitset_obstack_alloc (bobstack, n_bits, type) - struct obstack *bobstack; - bitset_bindex n_bits; - enum bitset_type type; + struct obstack *bobstack; + bitset_bindex n_bits; + enum bitset_type type; { unsigned int bytes; + bitset bset; BITSET_STATS_OBALLOCS_INC (type); bytes = bitset_bytes (type, n_bits); - return bitset_init (obstack_alloc (bobstack, bytes), n_bits, type); + bset = obstack_alloc (bobstack, bytes); + memset (bset, 0, bytes); + + return bitset_init (bset, n_bits, type); } @@ -286,10 +279,7 @@ bitset_free (bset) { BITSET_STATS_XFREES_INC (bset); - if (bset->ops->free) - BITSET__FREE (bset); - - bset->ops = NULL; + BITSET_FREE_ (bset); free (bset); } @@ -301,9 +291,7 @@ bitset_obstack_free (bset) { BITSET_STATS_OBFREES_INC (bset); - if (bset->ops->free) - BITSET__FREE (bset); - bset->ops = NULL; + BITSET_FREE_ (bset); } @@ -357,6 +345,7 @@ bitset_last (src) } +/* Print contents of bitset BSET to FILE. */ static void bitset_print (file, bset, verbose) FILE *file; @@ -386,153 +375,225 @@ bitset_print (file, bset, verbose) } +/* DST = SRC. Return non-zero if DST != SRC. */ int bitset_copy (dst, src) - bitset dst; - bitset src; + bitset dst; + bitset src; { - unsigned int i; + unsigned int i; - if (dst->ops == src->ops) - return BITSET__COPY (dst, src); + if (BITSET_COMPATIBLE_ (dst, src)) + return BITSET_COPY_ (dst, src); - /* Convert bitset types. We assume that the DST bitset - is large enough to hold the SRC bitset. */ - bitset_zero (dst); - BITSET_EXECUTE (src, 0, i, - { - bitset_set (dst, i); - }); + /* Convert bitset types. We assume that the DST bitset + is large enough to hold the SRC bitset. */ + bitset_zero (dst); + BITSET_EXECUTE (src, 0, i, + { + bitset_set (dst, i); + }); - return 1; + return 1; } /* Return size in bits of bitset SRC. */ int bitset_size (src) - bitset src; + bitset src; +{ + return BITSET_SIZE_ (src); +} + + +/* Return number of bits set in bitset SRC. */ +int +bitset_count (src) + bitset src; { - return BITSET__SIZE (src); + bitset_bindex list[BITSET_LIST_SIZE]; + bitset_bindex next; + int num; + int count; + + next = 0; + for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next)); + count += num) + continue; + + return count; } /* DST = 0. */ int bitset_zero (dst) - bitset dst; + bitset dst; { - return BITSET__OP1 (dst, BITSET_ZERO); + return BITSET_ZERO_ (dst); } /* DST = ~0. */ int bitset_ones (dst) - bitset dst; + bitset dst; { - return BITSET__OP1 (dst, BITSET_ONES); + return BITSET_ONES_ (dst); } -/* Return non-zero if all bits in bitset SRC are reset. */ +/* Return SRC == 0. */ int bitset_empty_p (src) - bitset src; + bitset src; { - return BITSET__OP1 (src, BITSET_EMPTY_P); + return BITSET_EMPTY_P_ (src); } /* Return DST == DST | SRC. */ int bitset_subset_p (dst, src) - bitset dst; - bitset src; + bitset dst; + bitset src; { - return BITSET__OP2 (dst, src, BITSET_SUBSET_P); + BITSET_CHECK2_ (dst, src); + return BITSET_SUBSET_P_ (dst, src); } /* Return DST == SRC. */ int bitset_equal_p (dst, src) - bitset dst; - bitset src; + bitset dst; + bitset src; { - BITSET__CHECK2 (dst, src); - return BITSET__OP2 (dst, src, BITSET_EQUAL_P); + BITSET_CHECK2_ (dst, src); + return BITSET_EQUAL_P_ (dst, src); +} + + +/* Return DST & SRC == 0. */ +int +bitset_disjoint_p (dst, src) + bitset dst; + bitset src; +{ + BITSET_CHECK2_ (dst, src); + return BITSET_DISJOINT_P_ (dst, src); } /* DST = ~SRC. */ int bitset_not (dst, src) - bitset dst; - bitset src; + bitset dst; + bitset src; { - BITSET__CHECK2 (dst, src); - return BITSET__OP2 (dst, src, BITSET_NOT); + BITSET_CHECK2_ (dst, src); + return BITSET_NOT_ (dst, src); } /* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */ int bitset_or (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; + bitset dst; + bitset src1; + bitset src2; { - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_OR); + BITSET_CHECK3_ (dst, src1, src2); + return BITSET_OR_ (dst, src1, src2); } /* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */ int bitset_and (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; + bitset dst; + bitset src1; + bitset src2; { - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_AND); + BITSET_CHECK3_ (dst, src1, src2); + return BITSET_AND_ (dst, src1, src2); } /* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */ int bitset_xor (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; + bitset dst; + bitset src1; + bitset src2; { - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_XOR); + BITSET_CHECK3_ (dst, src1, src2); + return BITSET_XOR_ (dst, src1, src2); } /* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */ int bitset_andn (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; + bitset dst; + bitset src1; + bitset src2; { - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_ANDN); + BITSET_CHECK3_ (dst, src1, src2); + return BITSET_ANDN_ (dst, src1, src2); } /* DST = SRC1 | ~SRC2. Return non-zero if DST != SRC1 | ~SRC2. */ int bitset_orn (dst, src1, src2) - bitset dst; - bitset src1; - bitset src2; + bitset dst; + bitset src1; + bitset src2; { - BITSET__CHECK3 (dst, src1, src2); - return BITSET__OP3 (dst, src1, src2, BITSET_ORN); + BITSET_CHECK3_ (dst, src1, src2); + return BITSET_ORN_ (dst, src1, src2); +} + + +int +bitset_op4 (dst, src1, src2, src3, op) + bitset dst; + bitset src1; + bitset src2; + bitset src3; + enum bitset_ops op; +{ + int changed = 0; + bitset tmp; + + /* Create temporary bitset. */ + tmp = bitset_alloc (BITSET_TYPE_ (dst), 0); + + switch (op) + { + case BITSET_OP_OR_AND: + BITSET_OR_ (tmp, src1, src2); + changed = BITSET_AND_ (dst, src3, tmp); + break; + + case BITSET_OP_AND_OR: + BITSET_AND_ (tmp, src1, src2); + changed = BITSET_OR_ (dst, src3, tmp); + break; + + case BITSET_OP_ANDN_OR: + BITSET_ANDN_ (tmp, src1, src2); + changed = BITSET_OR_ (dst, src3, tmp); + break; + + default: + abort (); + } + + bitset_free (tmp); + return changed; } @@ -540,13 +601,13 @@ bitset_orn (dst, src1, src2) DST != (SRC1 | SRC2) & SRC3. */ int bitset_or_and (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; + bitset dst; + bitset src1; + bitset src2; + bitset src3; { - BITSET__CHECK4 (dst, src1, src2, src3); - return BITSET__OP4 (dst, src1, src2, src3, BITSET_OR_AND); + BITSET_CHECK4_ (dst, src1, src2, src3); + return BITSET_OR_AND_ (dst, src1, src2, src3); } @@ -554,13 +615,27 @@ bitset_or_and (dst, src1, src2, src3) DST != (SRC1 & SRC2) | SRC3. */ int bitset_and_or (dst, src1, src2, src3) - bitset dst; - bitset src1; - bitset src2; - bitset src3; + bitset dst; + bitset src1; + bitset src2; + bitset src3; +{ + BITSET_CHECK4_ (dst, src1, src2, src3); + return BITSET_AND_OR_ (dst, src1, src2, src3); +} + + +/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if + DST != (SRC1 & ~SRC2) | SRC3. */ +int +bitset_andn_or (dst, src1, src2, src3) + bitset dst; + bitset src1; + bitset src2; + bitset src3; { - BITSET__CHECK4 (dst, src1, src2, src3); - return BITSET__OP4 (dst, src1, src2, src3, BITSET_AND_OR); + BITSET_CHECK4_ (dst, src1, src2, src3); + return BITSET_ANDN_OR_ (dst, src1, src2, src3); } @@ -579,7 +654,8 @@ void debug_bitset (bset) bitset bset; { - bitset_print (stderr, bset, 1); + if (bset) + bitset_print (stderr, bset, 1); } @@ -595,47 +671,47 @@ bitset_release_memory () #if BITSET_STATS int bitset_list (bset, list, num, next) - bitset bset; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; + bitset bset; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; { - bitset_bindex count; + bitset_bindex count; - count = BITSET__LIST (bset, list, num, next); + count = BITSET_LIST_ (bset, list, num, next); - if (bitset_stats) - { - bitset_bindex tmp; - bitset_bindex size; - bitset_bindex i; - enum bitset_type type; - - type = bset->ops->type; - BITSET_STATS_LISTS_INC (bset); - - /* Log histogram of number of set bits. */ - for (i = 0, tmp = count; tmp; tmp >>= 1, i++) - continue; - if (i >= BITSET_LOG_COUNT_BINS) - i = BITSET_LOG_COUNT_BINS - 1; - BITSET_STATS_LIST_COUNTS_INC (bset, i); - - /* Log histogram of number of bits in set. */ - size = bitset_size (bset); - for (i = 0, tmp = size; tmp; tmp >>= 1, i++) - continue; - if (i >= BITSET_LOG_SIZE_BINS) - i = BITSET_LOG_SIZE_BINS - 1; - BITSET_STATS_LIST_SIZES_INC (bset, i); - - /* Histogram of fraction of bits set. */ - i = size ? (count * BITSET_DENSITY_BINS) / size : 0; - if (i >= BITSET_DENSITY_BINS) - i = BITSET_DENSITY_BINS - 1; - BITSET_STATS_LIST_DENSITY_INC (bset, i); - } - return count; + if (bitset_stats) + { + bitset_bindex tmp; + bitset_bindex size; + bitset_bindex i; + enum bitset_type type; + + type = BITSET_TYPE_ (bset); + BITSET_STATS_LISTS_INC (bset); + + /* Log histogram of number of set bits. */ + for (i = 0, tmp = count; tmp; tmp >>= 1, i++) + continue; + if (i >= BITSET_LOG_COUNT_BINS) + i = BITSET_LOG_COUNT_BINS - 1; + BITSET_STATS_LIST_COUNTS_INC (bset, i); + + /* Log histogram of number of bits in set. */ + size = bitset_size (bset); + for (i = 0, tmp = size; tmp; tmp >>= 1, i++) + continue; + if (i >= BITSET_LOG_SIZE_BINS) + i = BITSET_LOG_SIZE_BINS - 1; + BITSET_STATS_LIST_SIZES_INC (bset, i); + + /* Histogram of fraction of bits set. */ + i = size ? (count * BITSET_DENSITY_BINS) / size : 0; + if (i >= BITSET_DENSITY_BINS) + i = BITSET_DENSITY_BINS - 1; + BITSET_STATS_LIST_DENSITY_INC (bset, i); + } + return count; } @@ -656,14 +732,14 @@ bitset_percent_histogram_print (file, name, msg, n_bins, bins) total += bins[i]; if (!total) - return; + return; fprintf (file, "%s %s", name, msg); for (i = 0; i < n_bins; i++) fprintf (file, "%.0f-%.0f%%\t%8d (%5.1f%%)\n", i * 100.0 / n_bins, - (i + 1) * 100.0 / n_bins, - bins[i], (100.0 * bins[i]) / total); + (i + 1) * 100.0 / n_bins, bins[i], + (100.0 * bins[i]) / total); } @@ -685,10 +761,10 @@ bitset_log_histogram_print (file, name, msg, n_bins, bins) total += bins[i]; if (!total) - return; + return; /* 2 * ceil (log10(2) * (N - 1)) + 1 */ - max_width = 2 * (unsigned int)(0.30103 * (n_bins - 1) + 0.9999) + 1; + max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1; fprintf (file, "%s %s", name, msg); for (i = 0; i < 2; i++) @@ -699,7 +775,8 @@ bitset_log_histogram_print (file, name, msg, n_bins, bins) for (; i < n_bins; i++) fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n", max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1), - 1 << (i - 1), (1 << i) - 1, bins[i], (100.0 * bins[i]) / total); + 1 << (i - 1), (1 << i) - 1, bins[i], + (100.0 * bins[i]) / total); } @@ -721,10 +798,10 @@ bitset_stats_print_1 (file, name, stats) fprintf (file, "%d bitset_lists\n", stats->lists); bitset_log_histogram_print (file, name, "count log histogram\n", - BITSET_LOG_COUNT_BINS, stats->list_counts); + BITSET_LOG_COUNT_BINS, stats->list_counts); bitset_log_histogram_print (file, name, "size log histogram\n", - BITSET_LOG_SIZE_BINS, stats->list_sizes); + BITSET_LOG_SIZE_BINS, stats->list_sizes); bitset_percent_histogram_print (file, name, "density histogram\n", BITSET_DENSITY_BINS, stats->list_density); @@ -738,7 +815,7 @@ bitset_stats_print (file, verbose) int verbose ATTRIBUTE_UNUSED; { int i; - static const char *names[] = BITSET__TYPE_NAMES; + static const char *names[] = BITSET_TYPE_NAMES; if (!bitset_stats) return; @@ -749,7 +826,7 @@ bitset_stats_print (file, verbose) fprintf (file, "Accumulated runs = %d\n", bitset_stats->runs); for (i = 0; i < BITSET_TYPE_NUM; i++) - bitset_stats_print_1 (file, names[i], &bitset_stats->types[i]); + bitset_stats_print_1 (file, names[i], &bitset_stats->types[i]); } #endif /* BITSET_STATS */ @@ -759,9 +836,9 @@ void bitset_stats_init () { #if BITSET_STATS - bitset_stats = &bitset_stats_data; - bitset_stats_read (); -#endif /* BITSET_STATS */ + bitset_stats = &bitset_stats_data; + bitset_stats_read (); +#endif /* BITSET_STATS */ } @@ -769,25 +846,25 @@ bitset_stats_init () static void bitset_stats_read () { - FILE *file; + FILE *file; - if (!bitset_stats) - return; + if (!bitset_stats) + return; - file = fopen (BITSET_STATS_FILE, "r"); - if (file) - { - if (fread (&bitset_stats_data, sizeof (bitset_stats_data), - 1, file) != 1) - { - if (ferror (file)) - perror ("Could not read stats file"); - else - fprintf (stderr, "Bad stats file size\n"); - } - fclose (file); - } - bitset_stats_data.runs++; + file = fopen (BITSET_STATS_FILE, "r"); + if (file) + { + if (fread (&bitset_stats_data, sizeof (bitset_stats_data), + 1, file) != 1) + { + if (ferror (file)) + perror ("Could not read stats file."); + else + fprintf (stderr, "Bad stats file size.\n"); + } + fclose (file); + } + bitset_stats_data.runs++; } @@ -795,21 +872,21 @@ bitset_stats_read () static void bitset_stats_write () { - FILE *file; + FILE *file; - if (!bitset_stats) - return; + if (!bitset_stats) + return; - file = fopen (BITSET_STATS_FILE, "w"); - if (file) - { - if (fwrite (&bitset_stats_data, sizeof (bitset_stats_data), - 1, file) != 1) - perror ("Could not write stats file"); - fclose (file); - } - else - perror ("Could not open stats file for writing"); + file = fopen (BITSET_STATS_FILE, "w"); + if (file) + { + if (fwrite (&bitset_stats_data, sizeof (bitset_stats_data), + 1, file) != 1) + perror ("Could not write stats file."); + fclose (file); + } + else + perror ("Could not open stats file for writing."); } diff --git a/lib/bitset.h b/lib/bitset.h index 4afbbf4f..b96a7e67 100644 --- a/lib/bitset.h +++ b/lib/bitset.h @@ -19,42 +19,14 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifndef _BITSET_H #define _BITSET_H -#if HAVE_CONFIG_H -# include <config.h> -#endif +/* This file is the public interface to the bitset abstract data type. + Only use the functions and macros defined in this file. */ -#define BITSET_STATS 1 - -# ifndef PARAMS -# if defined PROTOTYPES || (defined __STDC__ && __STDC__) -# define PARAMS(Args) Args -# else -# define PARAMS(Args) () -# endif -# endif - -# ifndef __attribute__ -# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__ -# define __attribute__(x) -# endif -# endif - -# ifndef ATTRIBUTE_NORETURN -# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__)) -# endif - -# ifndef ATTRIBUTE_UNUSED -# define ATTRIBUTE_UNUSED __attribute__ ((__unused__)) -# endif - -#include "bitset-int.h" -#include "sbitset.h" -#include "lbitset.h" -#include "ebitset.h" +#include "bbitset.h" #include "obstack.h" #include <stdio.h> -#include "xalloc.h" +/* Attributes used to select a bitset implementation. */ enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */ BITSET_VARIABLE = 2, /* Bitset size variable. */ BITSET_DENSE = 4, /* Bitset dense. */ @@ -64,75 +36,48 @@ enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */ typedef unsigned int bitset_attrs; -/* The elements of these structures should be considered - to be private. */ -typedef struct bitset_struct -{ - struct bitset_ops_struct *ops; - bitset_windex cindex; /* Cache word index. */ - bitset_windex csize; /* Cache size in words. */ - bitset_word *cdata; /* Cache data pointer. */ - union bitset_data - { - struct sbitset_struct s; - struct lbitset_struct l; - struct ebitset_struct e; - } u; -} *bitset; - - -/* The contents of this structure should be considered private. */ -struct bitset_ops_struct +/* The contents of the structure should be considered to be private. + While I would like to make this structure opaque, it needs to be + visible for the inline bit set/test functions. */ +struct bitset_struct { - void (*set) PARAMS ((struct bitset_struct *, bitset_bindex)); - void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex)); - int (*test) PARAMS ((struct bitset_struct *, bitset_bindex)); - int (*size) PARAMS ((struct bitset_struct *)); - int (*op1) PARAMS ((struct bitset_struct *, enum bitset_ops)); - int (*op2) PARAMS ((struct bitset_struct *, struct bitset_struct *, - enum bitset_ops)); - int (*op3) PARAMS ((struct bitset_struct *, struct bitset_struct *, - struct bitset_struct *, enum bitset_ops)); - int (*op4) PARAMS ((struct bitset_struct *, struct bitset_struct *, - struct bitset_struct *, struct bitset_struct *, - enum bitset_ops)); - int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *, - bitset_bindex, bitset_bindex *)); - int (*reverse_list) PARAMS ((struct bitset_struct *, bitset_bindex *, - bitset_bindex, bitset_bindex *)); - void (*free) PARAMS ((struct bitset_struct *)); - enum bitset_type type; + struct bbitset_struct b; }; - /* Return bytes required for bitset of desired type and size. */ extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex)); /* Initialise a bitset with desired type and size. */ extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type)); +/* Select an implementation type based on the desired bitset size + and attributes. */ extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex, bitset_attrs)); -/* Create a bitset of desired type and size. */ +/* Create a bitset of desired type and size. The bitset is zeroed. */ extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type)); /* Free bitset. */ extern void bitset_free PARAMS ((bitset)); -/* Create a bitset of desired type and size using obstack. */ +/* Create a bitset of desired type and size using an obstack. The + bitset is zeroed. */ extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack, bitset_bindex, enum bitset_type)); /* Free bitset allocated on obstack. */ extern void bitset_obstack_free PARAMS ((bitset)); -/* Create a bitset of desired size and attributes. */ +/* Create a bitset of desired size and attributes. The bitset is zeroed. */ extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs)); /* Return size in bits of bitset SRC. */ extern int bitset_size PARAMS ((bitset)); +/* Return number of bits set in bitset SRC. */ +extern int bitset_count PARAMS ((bitset)); + #if BITSET_CACHE && BITSET_INLINE static inline void bitset_set PARAMS ((bitset, bitset_bindex)); static inline void bitset_reset PARAMS ((bitset, bitset_bindex)); @@ -144,12 +89,12 @@ static inline void bitset_set (bset, bitno) bitset_bindex bitno; { bitset_windex index = bitno / BITSET_WORD_BITS; - bitset_windex offset = index - bset->cindex; + bitset_windex offset = index - bset->b.cindex; - if (offset < bset->csize) - bset->cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS)); + if (offset < bset->b.csize) + bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS)); else - BITSET__SET (bset, bitno); + BITSET_SET_ (bset, bitno); } @@ -159,12 +104,12 @@ static inline void bitset_reset (bset, bitno) bitset_bindex bitno; { bitset_windex index = bitno / BITSET_WORD_BITS; - bitset_windex offset = index - bset->cindex; + bitset_windex offset = index - bset->b.cindex; - if (offset < bset->csize) - bset->cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS)); + if (offset < bset->b.csize) + bset->b.cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS)); else - BITSET__RESET (bset, bitno); + BITSET_RESET_ (bset, bitno); } @@ -174,12 +119,12 @@ static inline int bitset_test (bset, bitno) bitset_bindex bitno; { bitset_windex index = bitno / BITSET_WORD_BITS; - bitset_windex offset = index - bset->cindex; + bitset_windex offset = index - bset->b.cindex; - if (offset < bset->csize) - return (bset->cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1; + if (offset < bset->b.csize) + return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1; else - return BITSET__TEST (bset, bitno); + return BITSET_TEST_ (bset, bitno); } #endif @@ -191,12 +136,12 @@ do \ { \ bitset_bindex _bitno = (bitno); \ bitset_windex _index = _bitno / BITSET_WORD_BITS; \ - bitset_windex _offset = _index - (bset)->cindex; \ + bitset_windex _offset = _index - (bset)->b.cindex; \ \ - if (_offset < (bset)->csize) \ - (bset)->cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS)); \ + if (_offset < (bset)->b.csize) \ + (bset)->b.cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS)); \ else \ - BITSET__SET ((bset), _bitno); \ + BITSET_SET_ ((bset), _bitno); \ } while (0) @@ -206,32 +151,32 @@ do \ { \ bitset_bindex _bitno = (bitno); \ bitset_windex _index = _bitno / BITSET_WORD_BITS; \ - bitset_windex _offset = _index - (bset)->cindex; \ + bitset_windex _offset = _index - (bset)->b.cindex; \ \ - if (_offset < (bset)->csize) \ - (bset)->cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \ + if (_offset < (bset)->b.csize) \ + (bset)->b.cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \ else \ - BITSET__RESET ((bset), _bitno); \ + BITSET_RESET_ ((bset), _bitno); \ } while (0) /* Test bit BITNO in bitset BSET. */ #define bitset_test(bset, bitno) \ -(((((bitno) / BITSET_WORD_BITS) - (bset)->cindex) < (bset)->csize) \ - ? ((bset)->cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->cindex)] \ +(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \ + ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \ >> ((bitno) % BITSET_WORD_BITS)) & 1 \ - : (unsigned int) BITSET__TEST ((bset), (bitno))) + : (unsigned int) BITSET_TEST_ ((bset), (bitno))) #endif #if ! BITSET_CACHE /* Set bit BITNO in bitset SRC. */ -#define bitset_set(SRC, BITNO) BITSET__SET (SRC, BITNO) +#define bitset_set(SRC, BITNO) BITSET_SET_ (SRC, BITNO) /* Reset bit BITNO in bitset SRC. */ -#define bitset_reset(SRC, BITNO) BITSET__RESET (SRC, BITNO) +#define bitset_reset(SRC, BITNO) BITSET_RESET_ (SRC, BITNO) /* Return non-zero if bit BITNO in bitset SRC is set. */ -#define bitset_test(SRC, BITNO) BITSET__TEST (SRC, BITNO) +#define bitset_test(SRC, BITNO) BITSET_TEST_ (SRC, BITNO) #endif /* DST = 0. */ @@ -249,6 +194,9 @@ extern int bitset_subset_p PARAMS ((bitset, bitset)); /* Return DST == SRC. */ extern int bitset_equal_p PARAMS ((bitset, bitset)); +/* Return DST & SRC == 0. */ +extern int bitset_disjoint_p PARAMS ((bitset, bitset)); + /* DST == SRC. */ extern int bitset_copy PARAMS ((bitset, bitset)); @@ -280,7 +228,7 @@ extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset)); /* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if DST != (SRC1 & ~SRC2) | SRC3. */ -#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \ +extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset)); /* Find next bit set in BSET starting from and including BITNO. */ extern int bitset_next PARAMS ((bitset, bitset_bindex)); @@ -296,14 +244,14 @@ extern int bitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); #else #define bitset_list(BSET, LIST, NUM, NEXT) \ -BITSET__LIST (BSET, LIST, NUM, NEXT) +BITSET_LIST_ (BSET, LIST, NUM, NEXT) #endif /* Find reverse list of up to NUM bits set in BSET starting from and including NEXT. Return with actual number of bits found and with *NEXT indicating where search stopped. */ #define bitset_reverse_list(BSET, LIST, NUM, NEXT) \ -BITSET__REVERSE_LIST (BSET, LIST, NUM, NEXT) +BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT) /* Find first set bit. */ extern int bitset_first PARAMS ((bitset)); @@ -360,7 +308,7 @@ do { \ } while (0) -/* Define set operations in terms of bit operations. */ +/* Define set operations in terms of logical operations. */ #define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2) @@ -369,7 +317,8 @@ do { \ #define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2) #define bitset_diff_union(DST, SRC1, SRC2, SRC3) \ -bitset_andn_or (DST, SRC1, SRC2, SRC3) + bitset_andn_or (DST, SRC1, SRC2, SRC3) + /* Release any memory tied up with bitsets. */ extern void bitset_release_memory PARAMS ((void)); @@ -386,10 +335,4 @@ extern void debug_bitset PARAMS ((bitset)); /* Function to debug bitset stats from debugger. */ extern void debug_bitset_stats PARAMS ((void)); -extern bitset sbitset_init PARAMS ((bitset, bitset_bindex)); - -extern bitset lbitset_init PARAMS ((bitset, bitset_bindex)); - -extern bitset ebitset_init PARAMS ((bitset, bitset_bindex)); - #endif /* _BITSET_H */ diff --git a/lib/bitsetv.c b/lib/bitsetv.c index 7fd82268..b6eb77e8 100644 --- a/lib/bitsetv.c +++ b/lib/bitsetv.c @@ -30,29 +30,32 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA type TYPE. */ bitset * bitsetv_alloc (n_vecs, n_bits, type) - unsigned int n_vecs; - unsigned int n_bits; - enum bitset_type type; + unsigned int n_vecs; + unsigned int n_bits; + enum bitset_type type; { - unsigned int vector_bytes; - unsigned int bytes; - bitset *bsetv; - unsigned int i; - - /* Determine number of bytes for each set. */ - bytes = bitset_bytes (type, n_bits); - - /* Allocate vector table at head of bitset array. */ - vector_bytes = n_vecs * sizeof (bitset); - bsetv = (bitset *) xmalloc (vector_bytes + bytes * n_vecs); - - for (i = 0; i < n_vecs; i++) + unsigned int vector_bytes; + unsigned int bytes; + bitset *bsetv; + unsigned int i; + + /* Determine number of bytes for each set. */ + bytes = bitset_bytes (type, n_bits); + + /* Allocate vector table at head of bitset array. */ + vector_bytes = (n_vecs + 1) * sizeof (bitset); + bsetv = (bitset *) xcalloc (1, vector_bytes + bytes * n_vecs); + + for (i = 0; i < n_vecs; i++) { - bsetv[i] = (bitset)((char *)bsetv + vector_bytes + i * bytes); + bsetv[i] = (bitset) ((char *) bsetv + vector_bytes + i * bytes); bitset_init (bsetv[i], n_bits, type); } - return bsetv; + + /* Null terminate table. */ + bsetv[i] = 0; + return bsetv; } @@ -60,48 +63,50 @@ bitsetv_alloc (n_vecs, n_bits, type) attribute hints specified by ATTR. */ bitset * bitsetv_create (n_vecs, n_bits, attr) - unsigned int n_vecs; - unsigned int n_bits; - unsigned int attr; + unsigned int n_vecs; + unsigned int n_bits; + unsigned int attr; { - enum bitset_type type; - - type = bitset_type_choose (n_bits, attr); - return bitsetv_alloc (n_vecs, n_bits, type); + enum bitset_type type; + + type = bitset_type_choose (n_bits, attr); + return bitsetv_alloc (n_vecs, n_bits, type); } /* Free bitset vector BSETV. */ void bitsetv_free (bsetv) - bitset *bsetv; + bitset *bsetv; { - free (bsetv); + unsigned int i; + + for (i = 0; bsetv[i]; i++) + BITSET_FREE_ (bsetv[i]); + free (bsetv); } -/* Zero a vector of N_VECS bitsets. */ +/* Zero a vector of bitsets. */ void -bitsetv_zero (bsetv, n_vecs) +bitsetv_zero (bsetv) struct bitset_struct **bsetv; - unsigned int n_vecs; { unsigned int i; - - for (i = 0; i < n_vecs; i++) - bitset_zero (bsetv[i]); + + for (i = 0; bsetv[i]; i++) + bitset_zero (bsetv[i]); } -/* Set a vector of N_VECS bitsets to ones. */ +/* Set a vector of bitsets to ones. */ void -bitsetv_ones (bsetv, n_vecs) +bitsetv_ones (bsetv) bitset *bsetv; - unsigned int n_vecs; { unsigned int i; - - for (i = 0; i < n_vecs; i++) + + for (i = 0; bsetv[i]; i++) bitset_ones (bsetv[i]); } @@ -109,20 +114,35 @@ bitsetv_ones (bsetv, n_vecs) /* Dump the contents of a bitset vector BSETV with N_VECS elements to FILE. */ void -bitsetv_dump (file, title, subtitle, bsetv, n_vecs) +bitsetv_dump (file, title, subtitle, bsetv) FILE *file; const char *title, *subtitle; bitset *bsetv; - unsigned int n_vecs; { unsigned int i; - + fprintf (file, "%s\n", title); - for (i = 0; i < n_vecs; i++) + for (i = 0; bsetv[i]; i++) { fprintf (file, "%s %d\n", subtitle, i); bitset_dump (file, bsetv[i]); } - + fprintf (file, "\n"); } + + +void +debug_bitsetv (bsetv) + bitset *bsetv; +{ + unsigned int i; + + for (i = 0; bsetv[i]; i++) + { + fprintf (stderr, "%d: ", i); + debug_bitset (bsetv[i]); + } + + fprintf (stderr, "\n"); +} diff --git a/lib/bitsetv.h b/lib/bitsetv.h index cac4eb07..34617054 100644 --- a/lib/bitsetv.h +++ b/lib/bitsetv.h @@ -37,13 +37,12 @@ extern bitsetv bitsetv_create PARAMS ((unsigned int, unsigned int, extern void bitsetv_free PARAMS ((bitsetv)); /* Zero vector of bitsets. */ -extern void bitsetv_zero PARAMS ((bitsetv, unsigned int)); +extern void bitsetv_zero PARAMS ((bitsetv)); /* Set vector of bitsets. */ -extern void bitsetv_ones PARAMS ((bitsetv, unsigned int)); +extern void bitsetv_ones PARAMS ((bitsetv)); /* Dump vector of bitsets. */ extern void bitsetv_dump PARAMS ((FILE *, const char *, - const char *, bitsetv, - unsigned int)); + const char *, bitsetv)); #endif /* _BITSETV_H */ diff --git a/lib/ebitset.c b/lib/ebitset.c index 0a6cbd41..9b1d91bf 100644 --- a/lib/ebitset.c +++ b/lib/ebitset.c @@ -1,43 +1,33 @@ -/* Functions to support efficient bitsets. +/* Functions to support expandable bitsets. Copyright (C) 2002 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 2 of the License, or -(at your option) any later version. + 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 + (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. + 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, write to the Free Software -Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + 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. */ #ifdef HAVE_CONFIG_H #include "config.h" #endif -#include "bitset.h" +#include "bbitset.h" #include "obstack.h" #include <stdlib.h> -# if WITH_DMALLOC -# define DMALLOC_FUNC_CHECK -# include <dmalloc.h> -# endif /* WITH_DMALLOC */ - -/* This file implements linked-list bitsets. These bitsets can be of +/* This file implements expandable bitsets. These bitsets can be of arbitrary length and are more efficient than arrays of bits for large sparse sets. - Usually if all the bits in an element are zero we remove the element - from the list. However, a side effect of the bit caching is that we - do not always notice when an element becomes zero. Hence the - ebitset_weed function which removes zero elements. - 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 @@ -46,33 +36,76 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 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 + some large number 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)) + +/* 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; + +/* 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. */ + #ifndef EBITSET_INITIAL_SIZE #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}; +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 int ebitset_obstack_init = 0; -static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */ +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)); @@ -86,58 +119,55 @@ 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_op4 PARAMS((bitset, bitset, bitset, bitset, - enum bitset_ops)); -static int ebitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex, - bitset_bindex *)); -static int ebitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex, - bitset_bindex *)); -static void ebitset_free PARAMS((bitset)); - - -#define EBITSET_ELTS(BSET) ((BSET)->u.e.elts) -#define EBITSET_SIZE(BSET) ((BSET)->u.e.size) +static void ebitset_zero PARAMS ((bitset)); +static int ebitset_equal_p PARAMS ((bitset, bitset)); +static void ebitset_copy PARAMS ((bitset, bitset)); +static int ebitset_copy_compare PARAMS ((bitset, bitset)); +static void ebitset_set PARAMS ((bitset, bitset_bindex)); +static void ebitset_reset PARAMS ((bitset, bitset_bindex)); +static int ebitset_test PARAMS ((bitset, bitset_bindex)); +static int ebitset_size PARAMS ((bitset)); +static int ebitset_op1 PARAMS ((bitset, enum bitset_ops)); +static int ebitset_op2 PARAMS ((bitset, bitset, enum bitset_ops)); +static int ebitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); +static int ebitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static int ebitset_reverse_list +PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); +static void ebitset_free PARAMS ((bitset)); + +#define EBITSET_ELTS(BSET) ((BSET)->e.elts) +#define EBITSET_SIZE(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)->cindex = BITSET_INDEX_MAX, \ - (BSET)->cdata = 0) +#define EBITSET_OP_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX, \ + (BSET)->b.cdata = 0) -#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->cindex = BITSET_INDEX_MAX) +#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX) /* Disable bitset cache and mark BSET as being possibly non-zero. */ #define EBITSET_NONZERO_SET(BSET) \ - (EBITSET_CACHE_DISABLE (BSET), (BSET)->cdata = (bitset_word *)~0) + (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)->cdata == 0) +#define EBITSET_OP_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)->cindex = (EINDEX) * EBITSET_ELT_WORDS, \ - (BSET)->cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX])) + ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \ + (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX])) /* Grow the expandable table for BSET by SIZE elements. */ static void ebitset_elts_grow (bset, size) - bitset bset; - unsigned int size; + bitset bset; + unsigned int size; { unsigned int oldsize; unsigned int newsize; @@ -146,7 +176,7 @@ ebitset_elts_grow (bset, size) newsize = oldsize + size; EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset), - newsize * sizeof (ebitset_elt *)); + newsize * sizeof (ebitset_elt *)); EBITSET_SIZE (bset) = newsize; memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *)); @@ -174,13 +204,17 @@ ebitset_elt_alloc () ebitset_obstack_init = 1; /* 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 @@ -191,12 +225,14 @@ ebitset_elt_alloc () obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE, __alignof__ (ebitset_elt), - (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC, - (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE); + (void *(*)PARAMS ((long))) + OBSTACK_CHUNK_ALLOC, + (void (*)PARAMS ((void *))) + 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)); } @@ -296,7 +332,7 @@ ebitset_elt_find (bset, index, mode) if ((elt = elts[eindex])) { - if (EBITSET_WORDS (elt) == bset->cdata) + if (EBITSET_WORDS (elt) == bset->b.cdata) return elt; EBITSET_CACHE_SET (bset, eindex); @@ -366,7 +402,7 @@ ebitset_weed (bset) bitset_windex j; int count; - if (EBITSET_ZERO_P (bset)) + if (EBITSET_OP_ZERO_P (bset)) return 0; elts = EBITSET_ELTS (bset); @@ -390,14 +426,14 @@ ebitset_weed (bset) count = j - count; if (!count) { - /* All the bits are zero. We could shrink the elts. + /* All the bits are zero. We could shrink the elts. For now just mark BSET as known to be zero. */ - EBITSET_ZERO_SET (bset); + EBITSET_OP_ZERO_SET (bset); } else EBITSET_NONZERO_SET (bset); - return count; + return count; } @@ -409,7 +445,7 @@ ebitset_zero (bset) ebitset_elts *elts; bitset_windex j; - if (EBITSET_ZERO_P (bset)) + if (EBITSET_OP_ZERO_P (bset)) return; elts = EBITSET_ELTS (bset); @@ -421,9 +457,9 @@ ebitset_zero (bset) ebitset_elt_remove (bset, j); } - /* All the bits are zero. We could shrink the elts. + /* All the bits are zero. We could shrink the elts. For now just mark BSET as known to be zero. */ - EBITSET_ZERO_SET (bset); + EBITSET_OP_ZERO_SET (bset); } @@ -454,9 +490,9 @@ ebitset_equal_p (dst, src) ebitset_elt *selt = selts[j]; ebitset_elt *delt = delts[j]; - if (! selt && ! delt) + if (!selt && !delt) continue; - if ((selt && ! delt) || (!selt && delt)) + if ((selt && !delt) || (!selt && delt)) return 0; for (i = 0; i < EBITSET_ELT_WORDS; i++) @@ -515,10 +551,10 @@ ebitset_copy_compare (dst, src) if (src == dst) return 0; - if (EBITSET_ZERO_P (dst)) + if (EBITSET_OP_ZERO_P (dst)) { ebitset_copy (dst, src); - return ! EBITSET_ZERO_P (src); + return !EBITSET_OP_ZERO_P (src); } if (ebitset_equal_p (dst, src)) @@ -549,7 +585,7 @@ ebitset_set (dst, bitno) ebitset_elt_find (dst, index, EBITSET_CREATE); - dst->cdata[index - dst->cindex] |= (1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[index - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS)); } @@ -562,11 +598,11 @@ ebitset_reset (dst, bitno) bitset_windex index = bitno / BITSET_WORD_BITS; if (!ebitset_elt_find (dst, index, EBITSET_FIND)) - return; + return; - dst->cdata[index - dst->cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[index - dst->b.cindex] &= ~(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 could be a good chance that the element will be needed again soon. */ } @@ -583,7 +619,8 @@ ebitset_test (src, bitno) if (!ebitset_elt_find (src, index, EBITSET_FIND)) return 0; - return (src->cdata[index - src->cindex] >> (bitno % BITSET_WORD_BITS)) & 1; + return (src->b. + cdata[index - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1; } @@ -597,8 +634,8 @@ 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. */ + *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; @@ -619,7 +656,7 @@ ebitset_reverse_list (bset, list, num, next) bitset_word word; ebitset_elts *elts; - if (EBITSET_ZERO_P (bset)) + if (EBITSET_OP_ZERO_P (bset)) return 0; size = EBITSET_SIZE (bset); @@ -627,13 +664,13 @@ ebitset_reverse_list (bset, list, num, next) rbitno = *next; if (rbitno >= n_bits) - return 0; + return 0; elts = EBITSET_ELTS (bset); bitno = n_bits - (rbitno + 1); - index = bitno / BITSET_WORD_BITS; + index = bitno / BITSET_WORD_BITS; eindex = bitno / EBITSET_ELT_BITS; windex = index - eindex * EBITSET_ELT_WORDS; @@ -684,8 +721,8 @@ 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. */ + *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; @@ -702,7 +739,7 @@ ebitset_list (bset, list, num, next) bitset_word word; ebitset_elts *elts; - if (EBITSET_ZERO_P (bset)) + if (EBITSET_OP_ZERO_P (bset)) return 0; bitno = *next; @@ -777,12 +814,12 @@ ebitset_list (bset, list, num, next) word = srcp[i]; if (word) { - if (! (word & 0xffff)) + if (!(word & 0xffff)) { word >>= 16; bitno += 16; } - if (! (word & 0xff)) + if (!(word & 0xff)) { word >>= 8; bitno += 8; @@ -837,22 +874,23 @@ ebitset_op1 (dst, op) switch (op) { - case BITSET_ZERO: + case BITSET_OP_ZERO: ebitset_zero (dst); return 1; - case BITSET_ONES: + 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); + 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_EMPTY_P: - return ! ebitset_weed (dst); + case BITSET_OP_EMPTY_P: + return !ebitset_weed (dst); default: abort (); @@ -876,28 +914,31 @@ ebitset_op2 (dst, src, op) switch (op) { - case BITSET_COPY: + case BITSET_OP_COPY: ebitset_copy (dst, src); break; - case BITSET_NOT: + 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); + 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; - case BITSET_EQUAL_P: + /* Return 1 if DST == SRC. */ + case BITSET_OP_EQUAL_P: return ebitset_equal_p (dst, src); /* Return 1 if DST == DST | SRC. */ - case BITSET_SUBSET_P: + case BITSET_OP_SUBSET_P: { ebitset_elts *selts; ebitset_elts *delts; @@ -918,7 +959,7 @@ ebitset_op2 (dst, src, op) selt = j < ssize ? selts[j] : 0; delt = j < dsize ? delts[j] : 0; - if (! selt && ! delt) + if (!selt && !delt) continue; if (!selt) @@ -935,6 +976,44 @@ ebitset_op2 (dst, src, op) } 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++) + { + 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 (selt)[i] & EBITSET_WORDS (delt)[i])) + return 0; + } + return 1; + } + break; + default: abort (); } @@ -966,30 +1045,31 @@ ebitset_op3 (dst, src1, src2, op) bitset_windex j; /* Fast track common, simple cases. */ - if (EBITSET_ZERO_P (src2)) + if (EBITSET_OP_ZERO_P (src2)) { - if (op == BITSET_AND) + if (op == BITSET_OP_AND) { ebitset_weed (dst); - changed = EBITSET_ZERO_P (dst); + changed = EBITSET_OP_ZERO_P (dst); ebitset_zero (dst); return changed; } - else if (op == BITSET_ANDN || op == BITSET_OR || op == BITSET_XOR) + else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR + || op == BITSET_OP_XOR) { return ebitset_copy_compare (dst, src1); } } - else if (EBITSET_ZERO_P (src1)) + else if (EBITSET_OP_ZERO_P (src1)) { - if (op == BITSET_AND || op == BITSET_ANDN) + if (op == BITSET_OP_AND || op == BITSET_OP_ANDN) { ebitset_weed (dst); - changed = EBITSET_ZERO_P (dst); + changed = EBITSET_OP_ZERO_P (dst); ebitset_zero (dst); return changed; } - else if (op == BITSET_OR || op == BITSET_XOR) + else if (op == BITSET_OP_OR || op == BITSET_OP_XOR) { return ebitset_copy_compare (dst, src2); } @@ -1003,7 +1083,7 @@ ebitset_op3 (dst, src1, src2, op) size = ssize2; if (size > dsize) - ebitset_elts_grow (dst, size - dsize); + ebitset_elts_grow (dst, size - dsize); selts1 = EBITSET_ELTS (src1); selts2 = EBITSET_ELTS (src2); @@ -1019,7 +1099,7 @@ ebitset_op3 (dst, src1, src2, op) selt2 = j < ssize2 ? selts2[j] : 0; delt = j < dsize ? delts[j] : 0; - if (! selt1 && ! selt2) + if (!selt1 && !selt2) { if (delt) { @@ -1043,7 +1123,7 @@ ebitset_op3 (dst, src1, src2, op) dstp = EBITSET_WORDS (delt); switch (op) { - case BITSET_OR: + case BITSET_OP_OR: for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ | *srcp2++; @@ -1056,7 +1136,7 @@ ebitset_op3 (dst, src1, src2, op) } break; - case BITSET_AND: + case BITSET_OP_AND: for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ & *srcp2++; @@ -1069,7 +1149,7 @@ ebitset_op3 (dst, src1, src2, op) } break; - case BITSET_XOR: + case BITSET_OP_XOR: for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ ^ *srcp2++; @@ -1082,7 +1162,7 @@ ebitset_op3 (dst, src1, src2, op) } break; - case BITSET_ANDN: + case BITSET_OP_ANDN: for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ & ~(*srcp2++); @@ -1095,7 +1175,7 @@ ebitset_op3 (dst, src1, src2, op) } break; - case BITSET_ORN: + case BITSET_OP_ORN: for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ | ~(*srcp2++); @@ -1112,7 +1192,7 @@ ebitset_op3 (dst, src1, src2, op) abort (); } - if (! ebitset_elt_zero_p (delt)) + if (!ebitset_elt_zero_p (delt)) { ebitset_elt_add (dst, delt, j); } @@ -1140,62 +1220,21 @@ ebitset_op3 (dst, src1, src2, op) } -static int -ebitset_op4 (dst, src1, src2, src3, op) - bitset dst; - bitset src1; - bitset src2; - bitset src3; - enum bitset_ops op; -{ - int changed = 0; - bitset tmp; - - tmp = bitset_create (BITSET_LIST, 0); - - switch (op) - { - case BITSET_OR_AND: - bitset_or (tmp, src1, src2); - changed = bitset_and (dst, src3, tmp); - break; - - case BITSET_AND_OR: - bitset_and (tmp, src1, src2); - changed = bitset_or (dst, src3, tmp); - break; - - case BITSET_ANDN_OR: - bitset_andn (tmp, src1, src2); - changed = bitset_or (dst, src3, tmp); - break; - - default: - abort (); - } - - bitset_free (tmp); - EBITSET_NONZERO_SET (dst); - return changed; -} - - /* Vector of operations for linked-list bitsets. */ -struct bitset_ops_struct ebitset_ops = - { - ebitset_set, - ebitset_reset, - ebitset_test, - ebitset_size, - ebitset_op1, - ebitset_op2, - ebitset_op3, - ebitset_op4, - ebitset_list, - ebitset_reverse_list, - ebitset_free, - BITSET_TABLE - }; +struct bitset_ops_struct ebitset_ops = { + ebitset_set, + ebitset_reset, + ebitset_test, + ebitset_size, + ebitset_op1, + ebitset_op2, + ebitset_op3, + bitset_op4, + ebitset_list, + ebitset_reverse_list, + ebitset_free, + BITSET_TABLE +}; /* Return size of initial structure. */ @@ -1216,11 +1255,11 @@ ebitset_init (bset, n_bits) { unsigned int size; - bset->ops = &ebitset_ops; + bset->b.ops = &ebitset_ops; - bset->csize = EBITSET_ELT_WORDS; + bset->b.csize = EBITSET_ELT_WORDS; - EBITSET_ZERO_SET (bset); + EBITSET_OP_ZERO_SET (bset); size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS : EBITSET_INITIAL_SIZE; diff --git a/lib/ebitset.h b/lib/ebitset.h index 5b481dbf..b41485f2 100644 --- a/lib/ebitset.h +++ b/lib/ebitset.h @@ -19,40 +19,12 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifndef _EBITSET_H #define _EBITSET_H -#include "bitset-int.h" - -/* 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)) - -/* 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; - -/* 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; - +#include "bbitset.h" extern int ebitset_bytes PARAMS ((bitset_bindex)); +extern bitset ebitset_init PARAMS ((bitset, bitset_bindex)); + extern void ebitset_release_memory PARAMS ((void)); #endif diff --git a/lib/lbitset.c b/lib/lbitset.c index e400df3d..39e5b4e5 100644 --- a/lib/lbitset.c +++ b/lib/lbitset.c @@ -2,50 +2,92 @@ Copyright (C) 2002 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 2 of the License, or -(at your option) any later version. + 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 + (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. + 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, write to the Free Software -Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + 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. */ #ifdef HAVE_CONFIG_H #include "config.h" #endif -#include "bitset.h" +#include "bbitset.h" #include "obstack.h" #include <stdlib.h> -# if WITH_DMALLOC -# define DMALLOC_FUNC_CHECK -# include <dmalloc.h> -# endif /* WITH_DMALLOC */ - /* This file implements linked-list bitsets. These bitsets can be of arbitrary length and are more efficient than arrays of bits for large sparse sets. - Usually if all the bits in an element are zero we remove the element - from the list. However, a side effect of the bit caching is that we - do not always notice when an element becomes zero. Hence the - lbitset_weed function which removes zero elements. */ + Usually if all the bits in an element are zero we remove the element + from the list. However, a side effect of the bit caching is that we + do not always notice when an element becomes zero. Hence the + lbitset_weed function which removes zero elements. */ + + +/* Number of words to use for each element. The larger the value the + greater the size of the cache and the shorter the time to find a given bit + but the more memory wasted for sparse bitsets and the longer the time + to search for set bits. */ + +#ifndef LBITSET_ELT_WORDS +#define LBITSET_ELT_WORDS 2 +#endif + +typedef bitset_word lbitset_word; + +#define LBITSET_WORD_BITS BITSET_WORD_BITS + +/* Number of bits stored in each element. */ +#define LBITSET_ELT_BITS \ + ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS)) + +/* Lbitset element. We use an array of bits for each element. + These are linked together in a doubly-linked list. */ +typedef struct lbitset_elt_struct +{ + struct lbitset_elt_struct *next; /* Next element. */ + struct lbitset_elt_struct *prev; /* Previous element. */ + bitset_windex index; /* bitno / BITSET_WORD_BITS. */ + bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set. */ +} +lbitset_elt; + + +/* Head of lbitset linked list. */ +typedef struct lbitset_struct +{ + lbitset_elt *head; /* First element in linked list. */ + lbitset_elt *tail; /* Last element in linked list. */ +} +*lbitset; + -enum lbitset_find_mode {LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST}; +struct bitset_struct +{ + struct bbitset_struct b; + struct lbitset_struct l; +}; -static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */ + +enum lbitset_find_mode + { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST }; + +static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */ /* Obstack to allocate bitset elements from. */ static struct obstack lbitset_obstack; static int lbitset_obstack_init = 0; -static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */ +static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */ static lbitset_elt *lbitset_elt_alloc PARAMS ((void)); static lbitset_elt *lbitset_elt_calloc PARAMS ((void)); @@ -58,32 +100,30 @@ static int lbitset_elt_zero_p PARAMS ((lbitset_elt *)); static void lbitset_prune PARAMS ((bitset, lbitset_elt *)); static void lbitset_weed PARAMS ((bitset)); -static void lbitset_zero PARAMS((bitset)); -static int lbitset_equal_p PARAMS((bitset, bitset)); -static void lbitset_copy PARAMS((bitset, bitset)); -static int lbitset_copy_compare PARAMS((bitset, bitset)); -static void lbitset_set PARAMS((bitset, bitset_bindex)); -static void lbitset_reset PARAMS((bitset, bitset_bindex)); -static int lbitset_test PARAMS((bitset, bitset_bindex)); -static int lbitset_size PARAMS((bitset)); -static int lbitset_op1 PARAMS((bitset, enum bitset_ops)); -static int lbitset_op2 PARAMS((bitset, bitset, enum bitset_ops)); -static int lbitset_op3 PARAMS((bitset, bitset, bitset, enum bitset_ops)); -static int lbitset_op4 PARAMS((bitset, bitset, bitset, bitset, - enum bitset_ops)); -static int lbitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex, - bitset_bindex *)); -static int lbitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex, - bitset_bindex *)); -static void lbitset_free PARAMS((bitset)); +static void lbitset_zero PARAMS ((bitset)); +static int lbitset_equal_p PARAMS ((bitset, bitset)); +static void lbitset_copy PARAMS ((bitset, bitset)); +static int lbitset_copy_compare PARAMS ((bitset, bitset)); +static void lbitset_set PARAMS ((bitset, bitset_bindex)); +static void lbitset_reset PARAMS ((bitset, bitset_bindex)); +static int lbitset_test PARAMS ((bitset, bitset_bindex)); +static int lbitset_size PARAMS ((bitset)); +static int lbitset_op1 PARAMS ((bitset, enum bitset_ops)); +static int lbitset_op2 PARAMS ((bitset, bitset, enum bitset_ops)); +static int lbitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); +static int lbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static int lbitset_reverse_list +PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); +static void lbitset_free PARAMS ((bitset)); #define LBITSET_CURRENT1(X) (lbitset_elt *)((char *)(X) + ((char *)&(((lbitset_elt *)(X))->next) - (char *)&(((lbitset_elt *)(X))->words))) -#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->cdata) +#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata) -#define LBITSET_HEAD(X) ((X)->u.l.head) -#define LBITSET_TAIL(X) ((X)->u.l.tail) +#define LBITSET_HEAD(X) ((X)->l.head) +#define LBITSET_TAIL(X) ((X)->l.tail) /* Allocate a lbitset element. The bits are not cleared. */ static inline lbitset_elt * @@ -106,13 +146,17 @@ lbitset_elt_alloc () lbitset_obstack_init = 1; /* 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 @@ -123,12 +167,14 @@ lbitset_elt_alloc () obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE, __alignof__ (lbitset_elt), - (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC, - (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE); + (void *(*)PARAMS ((long))) + OBSTACK_CHUNK_ALLOC, + (void (*)PARAMS ((void *))) + OBSTACK_CHUNK_FREE); } /* Perhaps we should add a number of new elements to the free - list. */ + list. */ elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack, sizeof (lbitset_elt)); } @@ -185,18 +231,18 @@ lbitset_elt_unlink (bset, elt) { if (next) { - bset->cdata = next->words; - bset->cindex = next->index; + bset->b.cdata = next->words; + bset->b.cindex = next->index; } else if (prev) { - bset->cdata = prev->words; - bset->cindex = prev->index; + bset->b.cdata = prev->words; + bset->b.cindex = prev->index; } else { - bset->csize = 0; - bset->cdata = 0; + bset->b.csize = 0; + bset->b.cdata = 0; } } @@ -214,22 +260,22 @@ lbitset_prune (bset, elt) lbitset_elt *next; if (!elt) - return; + return; if (elt->prev) - { + { LBITSET_TAIL (bset) = elt->prev; - bset->cdata = elt->prev->words; - bset->cindex = elt->prev->index; + bset->b.cdata = elt->prev->words; + bset->b.cindex = elt->prev->index; elt->prev->next = 0; - } + } else - { + { LBITSET_HEAD (bset) = 0; LBITSET_TAIL (bset) = 0; - bset->cdata = 0; - bset->csize = 0; - } + bset->b.cdata = 0; + bset->b.csize = 0; + } for (; elt; elt = next) { @@ -264,10 +310,10 @@ lbitset_elt_link (bset, elt) lbitset_elt *ptr; lbitset_elt *current; - if (bset->csize) - current = LBITSET_CURRENT (bset); + if (bset->b.csize) + current = LBITSET_CURRENT (bset); else - current = LBITSET_HEAD (bset); + current = LBITSET_HEAD (bset); /* If this is the first and only element, add it in. */ if (LBITSET_HEAD (bset) == 0) @@ -279,11 +325,10 @@ lbitset_elt_link (bset, elt) /* If this index is less than that of the current element, it goes somewhere before the current element. */ - else if (index < bset->cindex) + else if (index < bset->b.cindex) { for (ptr = current; - ptr->prev && ptr->prev->index > index; - ptr = ptr->prev) + ptr->prev && ptr->prev->index > index; ptr = ptr->prev) continue; if (ptr->prev) @@ -300,8 +345,7 @@ lbitset_elt_link (bset, elt) else { for (ptr = current; - ptr->next && ptr->next->index < index; - ptr = ptr->next) + ptr->next && ptr->next->index < index; ptr = ptr->next) continue; if (ptr->next) @@ -315,9 +359,9 @@ lbitset_elt_link (bset, elt) } /* Set up so this is the first element searched. */ - bset->cindex = index; - bset->csize = LBITSET_ELT_WORDS; - bset->cdata = elt->words; + bset->b.cindex = index; + bset->b.csize = LBITSET_ELT_WORDS; + bset->b.cdata = elt->words; } @@ -330,11 +374,11 @@ lbitset_elt_find (bset, index, mode) lbitset_elt *elt; lbitset_elt *current; - if (bset->csize) + if (bset->b.csize) { current = LBITSET_CURRENT (bset); /* Check if element is the cached element. */ - if ((index - bset->cindex) < bset->csize) + if ((index - bset->b.cindex) < bset->b.csize) return current; } else @@ -344,11 +388,10 @@ lbitset_elt_find (bset, index, mode) if (current) { - if (index < bset->cindex) + if (index < bset->b.cindex) { for (elt = current; - elt->prev && elt->index > index; - elt = elt->prev) + elt->prev && elt->index > index; elt = elt->prev) continue; } else @@ -363,9 +406,9 @@ lbitset_elt_find (bset, index, mode) we want, the one we want does not exist. */ if (elt && (index - elt->index) < LBITSET_ELT_WORDS) { - bset->cindex = elt->index; - bset->csize = LBITSET_ELT_WORDS; - bset->cdata = elt->words; + bset->b.cindex = elt->index; + bset->b.csize = LBITSET_ELT_WORDS; + bset->b.cdata = elt->words; return elt; } } @@ -449,7 +492,7 @@ lbitset_equal_p (dst, src) if (delt->words[j] != selt->words[j]) return 0; } - return ! selt && ! delt; + return !selt && !delt; } @@ -490,9 +533,9 @@ lbitset_copy (dst, src) } LBITSET_TAIL (dst) = tmp; - dst->csize = LBITSET_ELT_WORDS; - dst->cdata = LBITSET_HEAD (dst)->words; - dst->cindex = LBITSET_HEAD (dst)->index; + dst->b.csize = LBITSET_ELT_WORDS; + dst->b.cdata = LBITSET_HEAD (dst)->words; + dst->b.cindex = LBITSET_HEAD (dst)->index; } @@ -506,7 +549,7 @@ lbitset_copy_compare (dst, src) if (src == dst) return 0; - if (! LBITSET_HEAD (dst)) + if (!LBITSET_HEAD (dst)) { lbitset_copy (dst, src); return LBITSET_HEAD (src) != 0; @@ -529,7 +572,7 @@ lbitset_size (src) elt = LBITSET_TAIL (src); if (!elt) - return 0; + return 0; /* Return current size of bitset in bits. */ return (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS; @@ -546,7 +589,7 @@ lbitset_set (dst, bitno) lbitset_elt_find (dst, index, LBITSET_CREATE); - dst->cdata[index - dst->cindex] |= (1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[index - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS)); } @@ -559,9 +602,9 @@ lbitset_reset (dst, bitno) bitset_windex index = bitno / BITSET_WORD_BITS; if (!lbitset_elt_find (dst, index, LBITSET_FIND)) - return; + return; - dst->cdata[index - dst->cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); + dst->b.cdata[index - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS)); /* If all the data is zero, perhaps we should unlink it now... */ } @@ -578,7 +621,8 @@ lbitset_test (src, bitno) if (!lbitset_elt_find (src, index, LBITSET_FIND)) return 0; - return (src->cdata[index - src->cindex] >> (bitno % BITSET_WORD_BITS)) & 1; + return (src->b. + cdata[index - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1; } @@ -591,8 +635,8 @@ lbitset_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. */ + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ static int lbitset_reverse_list (bset, list, num, next) bitset bset; @@ -618,7 +662,7 @@ lbitset_reverse_list (bset, list, num, next) rbitno = *next; if (rbitno >= n_bits) - return 0; + return 0; bitno = n_bits - (rbitno + 1); @@ -644,9 +688,10 @@ lbitset_reverse_list (bset, list, num, next) for (; (index - elt->index) < LBITSET_ELT_WORDS; index--, bitoff -= BITSET_WORD_BITS, - bitcnt = BITSET_WORD_BITS - 1) + bitcnt = BITSET_WORD_BITS - 1) { - word = srcp[index - elt->index] << (BITSET_WORD_BITS - 1 - bitcnt); + word = + srcp[index - elt->index] << (BITSET_WORD_BITS - 1 - bitcnt); for (; word; bitcnt--) { @@ -677,8 +722,8 @@ lbitset_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. */ + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ static int lbitset_list (bset, list, num, next) bitset bset; @@ -695,7 +740,7 @@ lbitset_list (bset, list, num, next) head = LBITSET_HEAD (bset); if (!head) - return 0; + return 0; bitno = *next; count = 0; @@ -779,12 +824,12 @@ lbitset_list (bset, list, num, next) word = srcp[0]; if (word) { - if (! (word & 0xffff)) + if (!(word & 0xffff)) { word >>= 16; bitno += 16; } - if (! (word & 0xff)) + if (!(word & 0xff)) { word >>= 8; bitno += 8; @@ -802,7 +847,7 @@ lbitset_list (bset, list, num, next) word = srcp[1]; if (word) { - if (! (word & 0xffff)) + if (!(word & 0xffff)) { word >>= 16; bitno += 16; @@ -822,12 +867,12 @@ lbitset_list (bset, list, num, next) word = srcp[i]; if (word) { - if (! (word & 0xffff)) + if (!(word & 0xffff)) { word >>= 16; bitno += 16; } - if (! (word & 0xff)) + if (!(word & 0xff)) { word >>= 8; bitno += 8; @@ -893,11 +938,11 @@ lbitset_op1 (dst, op) switch (op) { - case BITSET_ZERO: + case BITSET_OP_ZERO: lbitset_zero (dst); break; - case BITSET_ONES: + case BITSET_OP_ONES: /* This is a decidedly unfriendly operation for a linked list bitset! */ elt = LBITSET_TAIL (dst); @@ -914,7 +959,7 @@ lbitset_op1 (dst, op) } break; - case BITSET_EMPTY_P: + case BITSET_OP_EMPTY_P: lbitset_weed (dst); if (LBITSET_HEAD (dst)) return 0; @@ -943,11 +988,11 @@ lbitset_op2 (dst, src, op) switch (op) { - case BITSET_COPY: + case BITSET_OP_COPY: lbitset_copy (dst, src); break; - case BITSET_NOT: + case BITSET_OP_NOT: /* This is another unfriendly operation for a linked list bitset! */ elt = LBITSET_TAIL (dst); @@ -969,11 +1014,13 @@ lbitset_op2 (dst, src, op) lbitset_weed (dst); break; - case BITSET_EQUAL_P: + /* Return 1 if DST == SRC. */ + case BITSET_OP_EQUAL_P: return lbitset_equal_p (dst, src); break; - case BITSET_SUBSET_P: + /* Return 1 if DST == DST | SRC. */ + case BITSET_OP_SUBSET_P: for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); selt || delt; selt = selt->next, delt = delt->next) { @@ -1001,6 +1048,31 @@ lbitset_op2 (dst, src, op) } break; + /* Return 1 if DST & SRC == 0. */ + case BITSET_OP_DISJOINT_P: + for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); + selt && delt; selt = selt->next, delt = delt->next) + { + if (selt->index != delt->index) + { + if (selt->index < delt->index) + { + lbitset_zero_elts[2].next = delt; + delt = &lbitset_zero_elts[2]; + } + else + { + lbitset_zero_elts[1].next = selt; + selt = &lbitset_zero_elts[1]; + } + } + + for (j = 0; j < LBITSET_ELT_WORDS; j++) + if (selt->words[j] & delt->words[j]) + return 0; + } + break; + default: abort (); } @@ -1034,36 +1106,36 @@ lbitset_op3 (dst, src1, src2, op) /* Fast track common, simple cases. */ if (!selt2) { - if (op == BITSET_AND) + if (op == BITSET_OP_AND) { lbitset_weed (dst); - changed = ! LBITSET_HEAD (dst); + changed = !LBITSET_HEAD (dst); lbitset_zero (dst); return changed; } - else if (op == BITSET_ANDN || op == BITSET_OR || op == BITSET_XOR) + else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR + || op == BITSET_OP_XOR) { return lbitset_copy_compare (dst, src1); } } else if (!selt1) { - if (op == BITSET_AND || op == BITSET_ANDN) + if (op == BITSET_OP_AND || op == BITSET_OP_ANDN) { lbitset_weed (dst); - changed = ! LBITSET_HEAD (dst); + changed = !LBITSET_HEAD (dst); lbitset_zero (dst); return changed; } - else if (op == BITSET_OR || op == BITSET_XOR) + else if (op == BITSET_OP_OR || op == BITSET_OP_XOR) { return lbitset_copy_compare (dst, src2); } } - LBITSET_HEAD (dst) = 0; - dst->csize = 0; + dst->b.csize = 0; index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX; index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX; @@ -1123,7 +1195,7 @@ lbitset_op3 (dst, src1, src2, op) dstp = dtmp->words; switch (op) { - case BITSET_OR: + case BITSET_OP_OR: for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ | *srcp2++; @@ -1136,7 +1208,7 @@ lbitset_op3 (dst, src1, src2, op) } break; - case BITSET_AND: + case BITSET_OP_AND: for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ & *srcp2++; @@ -1149,7 +1221,7 @@ lbitset_op3 (dst, src1, src2, op) } break; - case BITSET_XOR: + case BITSET_OP_XOR: for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ ^ *srcp2++; @@ -1162,7 +1234,7 @@ lbitset_op3 (dst, src1, src2, op) } break; - case BITSET_ANDN: + case BITSET_OP_ANDN: for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ & ~(*srcp2++); @@ -1175,7 +1247,7 @@ lbitset_op3 (dst, src1, src2, op) } break; - case BITSET_ORN: + case BITSET_OP_ORN: for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) { bitset_word tmp = *srcp1++ | ~(*srcp2++); @@ -1192,7 +1264,7 @@ lbitset_op3 (dst, src1, src2, op) abort (); } - if (! lbitset_elt_zero_p (dtmp)) + if (!lbitset_elt_zero_p (dtmp)) { dtmp->index = index; /* Perhaps this could be optimised... */ @@ -1215,67 +1287,21 @@ lbitset_op3 (dst, src1, src2, op) } -static int -lbitset_op4 (dst, src1, src2, src3, op) - bitset dst; - bitset src1; - bitset src2; - bitset src3; - enum bitset_ops op; -{ - int changed = 0; - bitset tmp; - -#ifdef ENABLE_CHECKING - /* Check for compatiblity. */ - if (src1->ops != dst->ops || src2->ops != dst->ops || src3->ops != dst->ops) - abort (); -#endif - - tmp = bitset_create (BITSET_LIST, 0); - - switch (op) - { - case BITSET_OR_AND: - bitset_or (tmp, src1, src2); - changed = bitset_and (dst, src3, tmp); - break; - - case BITSET_AND_OR: - bitset_and (tmp, src1, src2); - changed = bitset_or (dst, src3, tmp); - break; - - case BITSET_ANDN_OR: - bitset_andn (tmp, src1, src2); - changed = bitset_or (dst, src3, tmp); - break; - - default: - abort (); - } - - bitset_free (tmp); - return changed; -} - - /* Vector of operations for linked-list bitsets. */ -struct bitset_ops_struct lbitset_ops = - { - lbitset_set, - lbitset_reset, - lbitset_test, - lbitset_size, - lbitset_op1, - lbitset_op2, - lbitset_op3, - lbitset_op4, - lbitset_list, - lbitset_reverse_list, - lbitset_free, - BITSET_LIST - }; +struct bitset_ops_struct lbitset_ops = { + lbitset_set, + lbitset_reset, + lbitset_test, + lbitset_size, + lbitset_op1, + lbitset_op2, + lbitset_op3, + bitset_op4, + lbitset_list, + lbitset_reverse_list, + lbitset_free, + BITSET_LIST +}; /* Return size of initial structure. */ @@ -1294,17 +1320,7 @@ lbitset_init (bset, n_bits) bitset bset; bitset_bindex n_bits ATTRIBUTE_UNUSED; { - LBITSET_HEAD (bset) = 0; - LBITSET_TAIL (bset) = 0; - - bset->ops = &lbitset_ops; - - bset->cindex = 0; - /* Disable cache until have some elements allocated. - If we have variable length arrays, then we may - need to allocate dummy element. */ - bset->csize = 0; - bset->cdata = 0; + bset->b.ops = &lbitset_ops; return bset; } diff --git a/lib/lbitset.h b/lib/lbitset.h index 9af651f1..078c2ecc 100644 --- a/lib/lbitset.h +++ b/lib/lbitset.h @@ -19,44 +19,12 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifndef _LBITSET_H #define _LBITSET_H -#include "bitset-int.h" - -/* Number of words to use for each element. The larger the value the - greater the size of the cache and the shorter the time to find a given bit - but the more memory wasted for sparse bitsets and the longer the time - to search for set bits. */ -#ifndef LBITSET_ELT_WORDS -#define LBITSET_ELT_WORDS 2 -#endif - -typedef bitset_word lbitset_word; -#define LBITSET_WORD_BITS BITSET_WORD_BITS - -/* Number of bits stored in each element. */ -#define LBITSET_ELT_BITS \ - ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS)) - -/* Lbitset element. We use an array of bits for each element. - These are linked together in a doubly-linked list. */ -typedef struct lbitset_elt_struct -{ - struct lbitset_elt_struct *next; /* Next element. */ - struct lbitset_elt_struct *prev; /* Previous element. */ - bitset_windex index; /* bitno / BITSET_WORD_BITS. */ - bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set. */ -} lbitset_elt; - - -/* Head of lbitset linked list. */ -typedef struct lbitset_struct -{ - lbitset_elt *head; /* First element in linked list. */ - lbitset_elt *tail; /* Last element in linked list. */ -} *lbitset; - +#include "bbitset.h" extern int lbitset_bytes PARAMS ((bitset_bindex)); +extern bitset lbitset_init PARAMS ((bitset, bitset_bindex)); + extern void lbitset_release_memory PARAMS ((void)); #endif diff --git a/lib/sbitset.c b/lib/sbitset.c index 807b71dd..2e42e9b0 100644 --- a/lib/sbitset.c +++ b/lib/sbitset.c @@ -2,57 +2,67 @@ Copyright (C) 2002 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 2 of the License, or -(at your option) any later version. + 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 + (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. + 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, write to the Free Software -Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + 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. */ #ifdef HAVE_CONFIG_H #include "config.h" #endif -#include "bitset.h" +#include "sbitset.h" #include <stdlib.h> - -# if WITH_DMALLOC -# define DMALLOC_FUNC_CHECK -# include <dmalloc.h> -# endif /* WITH_DMALLOC */ +#include <string.h> /* This file implements fixed size bitsets stored as an array of words. Any unused bits in the last word must be zero. */ -static void sbitset_unused_clear PARAMS((bitset)); - -static int sbitset_small_list PARAMS((bitset, bitset_bindex *, bitset_bindex, - bitset_bindex *)); - -static void sbitset_set PARAMS((bitset, bitset_bindex)); -static void sbitset_reset PARAMS((bitset, bitset_bindex)); -static int sbitset_test PARAMS((bitset, bitset_bindex)); -static int sbitset_size PARAMS((bitset)); -static int sbitset_op1 PARAMS((bitset, enum bitset_ops)); -static int sbitset_op2 PARAMS((bitset, bitset, enum bitset_ops)); -static int sbitset_op3 PARAMS((bitset, bitset, bitset, enum bitset_ops)); -static int sbitset_op4 PARAMS((bitset, bitset, bitset, bitset, - enum bitset_ops)); -static int sbitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex, - bitset_bindex *)); -static int sbitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex, - bitset_bindex *)); +typedef struct sbitset_struct +{ + unsigned int n_bits; /* Number of bits. */ + bitset_word words[1]; /* The array of bits. */ +} +*sbitset; + + +struct bitset_struct +{ + struct bbitset_struct b; + struct sbitset_struct s; +}; + +static void sbitset_unused_clear PARAMS ((bitset)); + +static int sbitset_small_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); + +static void sbitset_set PARAMS ((bitset, bitset_bindex)); +static void sbitset_reset PARAMS ((bitset, bitset_bindex)); +static int sbitset_test PARAMS ((bitset, bitset_bindex)); +static int sbitset_size PARAMS ((bitset)); +static int sbitset_op1 PARAMS ((bitset, enum bitset_ops)); +static int sbitset_op2 PARAMS ((bitset, bitset, enum bitset_ops)); +static int sbitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); +static int sbitset_op4 PARAMS ((bitset, bitset, bitset, bitset, + enum bitset_ops)); +static int sbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static int sbitset_reverse_list +PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); #define SBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) -#define SBITSET_WORDS(X) ((X)->u.s.words) -#define SBITSET_N_BITS(X) ((X)->u.s.n_bits) +#define SBITSET_WORDS(X) ((X)->s.words) +#define SBITSET_N_BITS(X) ((X)->s.n_bits) /* Return size in bits of bitset SRC. */ @@ -60,13 +70,13 @@ static int sbitset_size (src) bitset src; { - return SBITSET_N_BITS (src); + return SBITSET_N_BITS (src); } /* 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. */ + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ static int sbitset_small_list (src, list, num, next) bitset src; @@ -96,30 +106,30 @@ sbitset_small_list (src, list, num, next) of the word of interest. */ if (num >= BITSET_WORD_BITS) - { + { for (count = 0; word; bitno++) - { + { if (word & 1) - list[count++] = bitno; + list[count++] = bitno; word >>= 1; - } - } + } + } else - { + { for (count = 0; word; bitno++) - { + { if (word & 1) - { + { list[count++] = bitno; if (count >= num) - { + { bitno++; break; - } - } + } + } word >>= 1; - } - } + } + } *next = bitno; return count; @@ -132,8 +142,8 @@ sbitset_set (dst, bitno) bitset dst ATTRIBUTE_UNUSED; bitset_bindex bitno ATTRIBUTE_UNUSED; { - /* This should never occur for sbitsets. */ - abort (); + /* This should never occur for sbitsets. */ + abort (); } @@ -143,8 +153,8 @@ sbitset_reset (dst, bitno) bitset dst ATTRIBUTE_UNUSED; bitset_bindex bitno ATTRIBUTE_UNUSED; { - /* This should never occur for sbitsets. */ - abort (); + /* This should never occur for sbitsets. */ + abort (); } @@ -154,9 +164,9 @@ sbitset_test (src, bitno) bitset src ATTRIBUTE_UNUSED; bitset_bindex bitno ATTRIBUTE_UNUSED; { - /* This should never occur for sbitsets. */ - abort (); - return 0; + /* This should never occur for sbitsets. */ + abort (); + return 0; } @@ -187,7 +197,7 @@ sbitset_reverse_list (src, list, num, next) of the word of interest. */ if (rbitno >= n_bits) - return 0; + return 0; count = 0; @@ -198,7 +208,7 @@ sbitset_reverse_list (src, list, num, next) bitoff = index * BITSET_WORD_BITS; for (; index != ~0U; index--, bitoff -= BITSET_WORD_BITS, - bitcnt = BITSET_WORD_BITS - 1) + bitcnt = BITSET_WORD_BITS - 1) { word = srcp[index] << (BITSET_WORD_BITS - 1 - bitcnt); for (; word; bitcnt--) @@ -222,8 +232,8 @@ sbitset_reverse_list (src, 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. */ + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ static int sbitset_list (src, list, num, next) bitset src; @@ -235,17 +245,17 @@ sbitset_list (src, list, num, next) bitset_bindex count; bitset_windex index; bitset_bindex bitoff; - bitset_windex size = src->csize; + bitset_windex size = src->b.csize; bitset_word *srcp = SBITSET_WORDS (src); bitset_word word; bitno = *next; count = 0; - if (! bitno) + if (!bitno) { /* Many bitsets are zero, so make this common case fast. */ - for (index = 0; index < size && ! srcp[index]; index++) + for (index = 0; index < size && !srcp[index]; index++) continue; if (index >= size) return 0; @@ -292,18 +302,18 @@ sbitset_list (src, list, num, next) for (; index < size; index++, bitoff += BITSET_WORD_BITS) { - if (! (word = srcp[index])) + if (!(word = srcp[index])) continue; if ((count + BITSET_WORD_BITS) < num) - { - for (bitno = bitoff; word; bitno++) - { - if (word & 1) - list[count++] = bitno; - word >>= 1; - } - } + { + for (bitno = bitoff; word; bitno++) + { + if (word & 1) + list[count++] = bitno; + word >>= 1; + } + } else { for (bitno = bitoff; word; bitno++) @@ -336,7 +346,8 @@ sbitset_unused_clear (dst) last_bit = SBITSET_N_BITS (dst) % BITSET_WORD_BITS; if (last_bit) - SBITSET_WORDS (dst)[dst->csize - 1] &= (bitset_word)((1 << last_bit) - 1); + SBITSET_WORDS (dst)[dst->b.csize - 1] &= + (bitset_word) ((1 << last_bit) - 1); } @@ -349,21 +360,21 @@ sbitset_op1 (dst, op) bitset_word *dstp = SBITSET_WORDS (dst); unsigned int bytes; - bytes = sizeof (bitset_word) * dst->csize; + bytes = sizeof (bitset_word) * dst->b.csize; switch (op) { - case BITSET_ZERO: + case BITSET_OP_ZERO: memset (dstp, 0, bytes); break; - case BITSET_ONES: + case BITSET_OP_ONES: memset (dstp, ~0, bytes); sbitset_unused_clear (dst); break; - case BITSET_EMPTY_P: - for (i = 0; i < dst->csize; i++) + case BITSET_OP_EMPTY_P: + for (i = 0; i < dst->b.csize; i++) if (dstp[i]) return 0; break; @@ -385,42 +396,46 @@ sbitset_op2 (dst, src, op) unsigned int i; bitset_word *srcp = SBITSET_WORDS (src); bitset_word *dstp = SBITSET_WORDS (dst); - bitset_windex size = dst->csize; + bitset_windex size = dst->b.csize; #ifdef ENABLE_CHECKING /* Check for compatiblity. */ - if (src->ops != dst->ops || SBITSET_N_BITS (src) != SBITSET_N_BITS (dst)) + if (SBITSET_N_BITS (src) != SBITSET_N_BITS (dst)) abort (); #endif switch (op) { - case BITSET_COPY: + case BITSET_OP_COPY: if (srcp == dstp) break; memcpy (dstp, srcp, sizeof (bitset_word) * size); break; - case BITSET_NOT: + case BITSET_OP_NOT: for (i = 0; i < size; i++) *dstp++ = ~(*srcp++); sbitset_unused_clear (dst); break; - case BITSET_EQUAL_P: + case BITSET_OP_EQUAL_P: for (i = 0; i < size; i++) - if (*dstp++ != *srcp++) + if (*srcp++ != *dstp++) return 0; break; - - case BITSET_SUBSET_P: + + case BITSET_OP_SUBSET_P: for (i = 0; i < size; i++, dstp++, srcp++) - { - if (*dstp != (*srcp | *dstp)) - return 0; - } + if (*dstp != (*srcp | *dstp)) + return 0; break; - + + case BITSET_OP_DISJOINT_P: + for (i = 0; i < size; i++) + if (*srcp++ & *dstp++) + return 0; + break; + default: abort (); } @@ -441,18 +456,18 @@ sbitset_op3 (dst, src1, src2, op) bitset_word *src1p = SBITSET_WORDS (src1); bitset_word *src2p = SBITSET_WORDS (src2); bitset_word *dstp = SBITSET_WORDS (dst); - bitset_windex size = dst->csize; + bitset_windex size = dst->b.csize; #ifdef ENABLE_CHECKING /* Check for compatiblity. */ - if (src1->ops != dst->ops || SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst) - || src2->ops != dst->ops || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst)) + if (SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst) + SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst)) abort (); #endif switch (op) { - case BITSET_OR: + case BITSET_OP_OR: for (i = 0; i < size; i++, dstp++) { bitset_word tmp = *src1p++ | *src2p++; @@ -465,7 +480,7 @@ sbitset_op3 (dst, src1, src2, op) } break; - case BITSET_AND: + case BITSET_OP_AND: for (i = 0; i < size; i++, dstp++) { bitset_word tmp = *src1p++ & *src2p++; @@ -478,7 +493,7 @@ sbitset_op3 (dst, src1, src2, op) } break; - case BITSET_XOR: + case BITSET_OP_XOR: for (i = 0; i < size; i++, dstp++) { bitset_word tmp = *src1p++ ^ *src2p++; @@ -491,7 +506,7 @@ sbitset_op3 (dst, src1, src2, op) } break; - case BITSET_ANDN: + case BITSET_OP_ANDN: for (i = 0; i < size; i++, dstp++) { bitset_word tmp = *src1p++ & ~(*src2p++); @@ -504,7 +519,7 @@ sbitset_op3 (dst, src1, src2, op) } break; - case BITSET_ORN: + case BITSET_OP_ORN: for (i = 0; i < size; i++, dstp++) { bitset_word tmp = *src1p++ | ~(*src2p++); @@ -540,19 +555,19 @@ sbitset_op4 (dst, src1, src2, src3, op) bitset_word *src2p = SBITSET_WORDS (src2); bitset_word *src3p = SBITSET_WORDS (src3); bitset_word *dstp = SBITSET_WORDS (dst); - bitset_windex size = dst->csize; + bitset_windex size = dst->b.csize; #ifdef ENABLE_CHECKING /* Check for compatiblity. */ - if (src1->ops != dst->ops || SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst) - || src2->ops != dst->ops || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst) - || src3->ops != dst->ops || SBITSET_N_BITS (src3) != SBITSET_N_BITS (dst)) + if (SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst) + || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst) + || SBITSET_N_BITS (src3) != SBITSET_N_BITS (dst)) abort (); #endif switch (op) { - case BITSET_OR_AND: + case BITSET_OP_OR_AND: for (i = 0; i < size; i++, dstp++) { bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; @@ -565,7 +580,7 @@ sbitset_op4 (dst, src1, src2, src3, op) } break; - case BITSET_AND_OR: + case BITSET_OP_AND_OR: for (i = 0; i < size; i++, dstp++) { bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; @@ -578,7 +593,7 @@ sbitset_op4 (dst, src1, src2, src3, op) } break; - case BITSET_ANDN_OR: + case BITSET_OP_ANDN_OR: for (i = 0; i < size; i++, dstp++) { bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; @@ -600,38 +615,36 @@ sbitset_op4 (dst, src1, src2, src3, op) /* Vector of operations for single word bitsets. */ -struct bitset_ops_struct sbitset_small_ops = - { - sbitset_set, - sbitset_reset, - sbitset_test, - sbitset_size, - sbitset_op1, - sbitset_op2, - sbitset_op3, - sbitset_op4, - sbitset_small_list, - sbitset_reverse_list, - NULL, - BITSET_ARRAY - }; +struct bitset_ops_struct sbitset_small_ops = { + sbitset_set, + sbitset_reset, + sbitset_test, + sbitset_size, + sbitset_op1, + sbitset_op2, + sbitset_op3, + sbitset_op4, + sbitset_small_list, + sbitset_reverse_list, + NULL, + BITSET_ARRAY +}; /* Vector of operations for multiple word bitsets. */ -struct bitset_ops_struct sbitset_ops = - { - sbitset_set, - sbitset_reset, - sbitset_test, - sbitset_size, - sbitset_op1, - sbitset_op2, - sbitset_op3, - sbitset_op4, - sbitset_list, - sbitset_reverse_list, - NULL, - BITSET_ARRAY +struct bitset_ops_struct sbitset_ops = { + sbitset_set, + sbitset_reset, + sbitset_test, + sbitset_size, + sbitset_op1, + sbitset_op2, + sbitset_op3, + sbitset_op4, + sbitset_list, + sbitset_reverse_list, + NULL, + BITSET_ARRAY }; @@ -661,12 +674,12 @@ sbitset_init (bset, n_bits) There is probably little merit if using caching since the small bitset will always fit in the cache. */ if (size == 1) - bset->ops = &sbitset_small_ops; + bset->b.ops = &sbitset_small_ops; else - bset->ops = &sbitset_ops; + bset->b.ops = &sbitset_ops; - bset->cindex = 0; - bset->csize = size; - bset->cdata = SBITSET_WORDS (bset); + bset->b.cindex = 0; + bset->b.csize = size; + bset->b.cdata = SBITSET_WORDS (bset); return bset; } diff --git a/lib/sbitset.h b/lib/sbitset.h index 777feea1..01562c58 100644 --- a/lib/sbitset.h +++ b/lib/sbitset.h @@ -19,15 +19,10 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifndef _SBITSET_H #define _SBITSET_H -#include "bitset-int.h" - -typedef struct sbitset_struct -{ - unsigned int n_bits; /* Number of bits. */ - bitset_word words[1]; /* The array of bits. */ -} *sbitset; - +#include "bbitset.h" extern int sbitset_bytes PARAMS ((bitset_bindex)); +extern bitset sbitset_init PARAMS ((bitset, bitset_bindex)); + #endif |