From 613f5e1a895b0742c9b6c5e9461e4cf3f7389d7e Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Tue, 2 Jul 2002 13:51:27 +0000 Subject: [PATCH] * lib/libiberty.h: New. * lib: Update the bitset implementation from upstream. * src/closure.c, src/lalr.c, src/output.c, src/print_graph.c, * src/state.c: Use BITSET_FOR_EACH, not BITSET_EXECUTE. * src/main.c: Adjust bitset stats calls. --- ChangeLog | 8 + lib/Makefile.am | 7 +- lib/{sbitset.c => abitset.c} | 193 +++++------ lib/{sbitset.h => abitset.h} | 10 +- lib/bbitset.h | 123 +++---- lib/bitset-int.h | 112 ------- lib/bitset.c | 405 +++------------------- lib/bitset.h | 126 +++---- lib/bitset_stats.c | 627 +++++++++++++++++++++++++++++++++++ lib/bitset_stats.h | 33 ++ lib/bitsetv.c | 2 +- lib/ebitset.c | 8 +- lib/ebitset.h | 2 +- lib/lbitset.c | 7 +- lib/lbitset.h | 2 +- lib/libiberty.h | 58 ++++ src/closure.c | 54 +-- src/lalr.c | 6 +- src/main.c | 9 +- src/output.c | 5 +- src/print_graph.c | 10 +- src/state.c | 9 +- 22 files changed, 1008 insertions(+), 808 deletions(-) rename lib/{sbitset.c => abitset.c} (74%) rename lib/{sbitset.h => abitset.h} (81%) delete mode 100644 lib/bitset-int.h create mode 100644 lib/bitset_stats.c create mode 100644 lib/bitset_stats.h create mode 100644 lib/libiberty.h diff --git a/ChangeLog b/ChangeLog index a6395680..606f0ed2 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +2002-07-02 Akim Demaille + + * lib/libiberty.h: New. + * lib: Update the bitset implementation from upstream. + * src/closure.c, src/lalr.c, src/output.c, src/print_graph.c, + * src/state.c: Use BITSET_FOR_EACH, not BITSET_EXECUTE. + * src/main.c: Adjust bitset stats calls. + 2002-07-01 Paul Eggert * src/scan-gram.l (): Convert to unsigned diff --git a/lib/Makefile.am b/lib/Makefile.am index e02e9fe7..d867394a 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -46,9 +46,10 @@ 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 +libiberty.h \ +abitset.c bitset.c bitset_stats.h ebitset.c lbitset.h \ +abitset.h bitset.h bitsetv.c ebitset.h \ +bbitset.h bitset_stats.c bitsetv.h lbitset.c # Additional bitset operations. libbison_a_SOURCES += \ diff --git a/lib/sbitset.c b/lib/abitset.c similarity index 74% rename from lib/sbitset.c rename to lib/abitset.c index 97d13335..9cdb40ce 100644 --- a/lib/sbitset.c +++ b/lib/abitset.c @@ -1,4 +1,4 @@ -/* Simple bitsets. +/* Array bitsets. Copyright (C) 2002 Free Software Foundation, Inc. Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). @@ -21,57 +21,57 @@ #include "config.h" #endif -#include "sbitset.h" +#include "abitset.h" #include #include /* This file implements fixed size bitsets stored as an array of words. Any unused bits in the last word must be zero. */ -typedef struct sbitset_struct +typedef struct abitset_struct { unsigned int n_bits; /* Number of bits. */ bitset_word words[1]; /* The array of bits. */ } -*sbitset; +*abitset; struct bitset_struct { struct bbitset_struct b; - struct sbitset_struct s; + struct abitset_struct a; }; -static void sbitset_unused_clear PARAMS ((bitset)); +static void abitset_unused_clear PARAMS ((bitset)); -static int sbitset_small_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, +static int abitset_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, +static void abitset_set PARAMS ((bitset, bitset_bindex)); +static void abitset_reset PARAMS ((bitset, bitset_bindex)); +static int abitset_test PARAMS ((bitset, bitset_bindex)); +static int abitset_size PARAMS ((bitset)); +static int abitset_op1 PARAMS ((bitset, enum bitset_ops)); +static int abitset_op2 PARAMS ((bitset, bitset, enum bitset_ops)); +static int abitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); +static int abitset_op4 PARAMS ((bitset, bitset, bitset, bitset, enum bitset_ops)); -static int sbitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, +static int abitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); -static int sbitset_reverse_list +static int abitset_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)->s.words) -#define SBITSET_N_BITS(X) ((X)->s.n_bits) +#define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) +#define ABITSET_WORDS(X) ((X)->a.words) +#define ABITSET_N_BITS(X) ((X)->a.n_bits) /* Return size in bits of bitset SRC. */ static int -sbitset_size (src) +abitset_size (src) bitset src; { - return SBITSET_N_BITS (src); + return ABITSET_N_BITS (src); } @@ -79,7 +79,7 @@ sbitset_size (src) *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) +abitset_small_list (src, list, num, next) bitset src; bitset_bindex *list; bitset_bindex num; @@ -90,13 +90,13 @@ sbitset_small_list (src, list, num, next) bitset_windex size; bitset_word word; - word = SBITSET_WORDS (src)[0]; + word = ABITSET_WORDS (src)[0]; /* Short circuit common case. */ if (!word) return 0; - size = SBITSET_N_BITS (src); + size = ABITSET_N_BITS (src); bitno = *next; if (bitno >= size) return 0; @@ -139,33 +139,33 @@ sbitset_small_list (src, list, num, next) /* Set bit BITNO in bitset DST. */ static void -sbitset_set (dst, bitno) +abitset_set (dst, bitno) bitset dst ATTRIBUTE_UNUSED; bitset_bindex bitno ATTRIBUTE_UNUSED; { - /* This should never occur for sbitsets. */ + /* This should never occur for abitsets. */ abort (); } /* Reset bit BITNO in bitset DST. */ static void -sbitset_reset (dst, bitno) +abitset_reset (dst, bitno) bitset dst ATTRIBUTE_UNUSED; bitset_bindex bitno ATTRIBUTE_UNUSED; { - /* This should never occur for sbitsets. */ + /* This should never occur for abitsets. */ abort (); } /* Test bit BITNO in bitset SRC. */ static int -sbitset_test (src, bitno) +abitset_test (src, bitno) bitset src ATTRIBUTE_UNUSED; bitset_bindex bitno ATTRIBUTE_UNUSED; { - /* This should never occur for sbitsets. */ + /* This should never occur for abitsets. */ abort (); return 0; } @@ -176,7 +176,7 @@ sbitset_test (src, bitno) actual number of bits found and with *NEXT indicating where search stopped. */ static int -sbitset_reverse_list (src, list, num, next) +abitset_reverse_list (src, list, num, next) bitset src; bitset_bindex *list; bitset_bindex num; @@ -189,8 +189,8 @@ sbitset_reverse_list (src, list, num, next) unsigned int bitcnt; bitset_bindex bitoff; bitset_word word; - bitset_word *srcp = SBITSET_WORDS (src); - bitset_bindex n_bits = SBITSET_N_BITS (src); + bitset_word *srcp = ABITSET_WORDS (src); + bitset_bindex n_bits = ABITSET_N_BITS (src); rbitno = *next; @@ -236,7 +236,7 @@ sbitset_reverse_list (src, list, num, next) *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) +abitset_list (src, list, num, next) bitset src; bitset_bindex *list; bitset_bindex num; @@ -247,7 +247,7 @@ sbitset_list (src, list, num, next) bitset_windex windex; bitset_bindex bitoff; bitset_windex size = src->b.csize; - bitset_word *srcp = SBITSET_WORDS (src); + bitset_word *srcp = ABITSET_WORDS (src); bitset_word word; bitno = *next; @@ -268,7 +268,7 @@ sbitset_list (src, list, num, next) } else { - if (bitno >= SBITSET_N_BITS (src)) + if (bitno >= ABITSET_N_BITS (src)) return 0; windex = bitno / BITSET_WORD_BITS; @@ -340,25 +340,25 @@ sbitset_list (src, list, num, next) /* Ensure that any unused bits within the last word are clear. */ static inline void -sbitset_unused_clear (dst) +abitset_unused_clear (dst) bitset dst; { unsigned int last_bit; - last_bit = SBITSET_N_BITS (dst) % BITSET_WORD_BITS; + last_bit = ABITSET_N_BITS (dst) % BITSET_WORD_BITS; if (last_bit) - SBITSET_WORDS (dst)[dst->b.csize - 1] &= + ABITSET_WORDS (dst)[dst->b.csize - 1] &= (bitset_word) ((1 << last_bit) - 1); } static int -sbitset_op1 (dst, op) +abitset_op1 (dst, op) bitset dst; enum bitset_ops op; { unsigned int i; - bitset_word *dstp = SBITSET_WORDS (dst); + bitset_word *dstp = ABITSET_WORDS (dst); unsigned int bytes; bytes = sizeof (bitset_word) * dst->b.csize; @@ -371,7 +371,7 @@ sbitset_op1 (dst, op) case BITSET_OP_ONES: memset (dstp, ~0, bytes); - sbitset_unused_clear (dst); + abitset_unused_clear (dst); break; case BITSET_OP_EMPTY_P: @@ -389,22 +389,16 @@ sbitset_op1 (dst, op) static int -sbitset_op2 (dst, src, op) +abitset_op2 (dst, src, op) bitset dst; bitset src; enum bitset_ops op; { unsigned int i; - bitset_word *srcp = SBITSET_WORDS (src); - bitset_word *dstp = SBITSET_WORDS (dst); + bitset_word *srcp = ABITSET_WORDS (src); + bitset_word *dstp = ABITSET_WORDS (dst); bitset_windex size = dst->b.csize; -#ifdef ENABLE_CHECKING - /* Check for compatiblity. */ - if (SBITSET_N_BITS (src) != SBITSET_N_BITS (dst)) - abort (); -#endif - switch (op) { case BITSET_OP_COPY: @@ -416,7 +410,7 @@ sbitset_op2 (dst, src, op) case BITSET_OP_NOT: for (i = 0; i < size; i++) *dstp++ = ~(*srcp++); - sbitset_unused_clear (dst); + abitset_unused_clear (dst); break; case BITSET_OP_EQUAL_P: @@ -446,7 +440,7 @@ sbitset_op2 (dst, src, op) static int -sbitset_op3 (dst, src1, src2, op) +abitset_op3 (dst, src1, src2, op) bitset dst; bitset src1; bitset src2; @@ -454,18 +448,11 @@ sbitset_op3 (dst, src1, src2, op) { unsigned int i; int changed = 0; - bitset_word *src1p = SBITSET_WORDS (src1); - bitset_word *src2p = SBITSET_WORDS (src2); - bitset_word *dstp = SBITSET_WORDS (dst); + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *dstp = ABITSET_WORDS (dst); bitset_windex size = dst->b.csize; -#ifdef ENABLE_CHECKING - /* Check for compatiblity. */ - if (SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst) - SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst)) - abort (); -#endif - switch (op) { case BITSET_OP_OR: @@ -529,7 +516,7 @@ sbitset_op3 (dst, src1, src2, op) static int -sbitset_op4 (dst, src1, src2, src3, op) +abitset_op4 (dst, src1, src2, src3, op) bitset dst; bitset src1; bitset src2; @@ -538,20 +525,12 @@ sbitset_op4 (dst, src1, src2, src3, op) { unsigned int i; int changed = 0; - bitset_word *src1p = SBITSET_WORDS (src1); - bitset_word *src2p = SBITSET_WORDS (src2); - bitset_word *src3p = SBITSET_WORDS (src3); - bitset_word *dstp = SBITSET_WORDS (dst); + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *src3p = ABITSET_WORDS (src3); + bitset_word *dstp = ABITSET_WORDS (dst); bitset_windex size = dst->b.csize; -#ifdef ENABLE_CHECKING - /* Check for compatiblity. */ - 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_OP_OR_AND: @@ -602,71 +581,71 @@ 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, +struct bitset_ops_struct abitset_small_ops = { + abitset_set, + abitset_reset, + abitset_test, + abitset_size, + abitset_op1, + abitset_op2, + abitset_op3, + abitset_op4, + abitset_small_list, + abitset_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, +struct bitset_ops_struct abitset_ops = { + abitset_set, + abitset_reset, + abitset_test, + abitset_size, + abitset_op1, + abitset_op2, + abitset_op3, + abitset_op4, + abitset_list, + abitset_reverse_list, NULL, BITSET_ARRAY }; int -sbitset_bytes (n_bits) +abitset_bytes (n_bits) bitset_bindex n_bits; { unsigned int bytes, size; - size = SBITSET_N_WORDS (n_bits); + size = ABITSET_N_WORDS (n_bits); bytes = size * sizeof (bitset_word); return sizeof (struct bitset_struct) + bytes - sizeof (bitset_word); } bitset -sbitset_init (bset, n_bits) +abitset_init (bset, n_bits) bitset bset; bitset_bindex n_bits; { bitset_windex size; - size = SBITSET_N_WORDS (n_bits); - SBITSET_N_BITS (bset) = n_bits; + size = ABITSET_N_WORDS (n_bits); + ABITSET_N_BITS (bset) = n_bits; /* Use optimized routines if bitset fits within a single word. There is probably little merit if using caching since the small bitset will always fit in the cache. */ if (size == 1) - bset->b.ops = &sbitset_small_ops; + bset->b.ops = &abitset_small_ops; else - bset->b.ops = &sbitset_ops; + bset->b.ops = &abitset_ops; bset->b.cindex = 0; bset->b.csize = size; - bset->b.cdata = SBITSET_WORDS (bset); + bset->b.cdata = ABITSET_WORDS (bset); return bset; } diff --git a/lib/sbitset.h b/lib/abitset.h similarity index 81% rename from lib/sbitset.h rename to lib/abitset.h index 01562c58..1faeee4d 100644 --- a/lib/sbitset.h +++ b/lib/abitset.h @@ -1,4 +1,4 @@ -/* Functions to support sbitsets. +/* Functions to support abitsets. Copyright (C) 2002 Free Software Foundation, Inc. Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). @@ -16,13 +16,13 @@ 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 _SBITSET_H -#define _SBITSET_H +#ifndef _ABITSET_H +#define _ABITSET_H #include "bbitset.h" -extern int sbitset_bytes PARAMS ((bitset_bindex)); +extern int abitset_bytes PARAMS ((bitset_bindex)); -extern bitset sbitset_init PARAMS ((bitset, bitset_bindex)); +extern bitset abitset_init PARAMS ((bitset, bitset_bindex)); #endif diff --git a/lib/bbitset.h b/lib/bbitset.h index 53b56c02..8ea98a8c 100644 --- a/lib/bbitset.h +++ b/lib/bbitset.h @@ -19,43 +19,7 @@ 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 -# endif -# include - -# 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 +#include "libiberty.h" #ifdef HAVE_LIMITS_H #include @@ -64,25 +28,21 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ /* 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). + for large very sparse sets). + BITSET_TABLE: Expandable table of pointers to array of bits + (variable size, less storage for large sparse sets). + + BITSET_STATS: Wrapper bitset for internal use only. */ -enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM}; -#define BITSET_TYPE_NAMES {"sbitset", "lbitset", "ebitset"} +enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM, + BITSET_STATS}; +#define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset"} -/* Non-zero to enable bitset caching. */ -#define BITSET_CACHE 1 +enum bitset_alloc_type {BITSET_MALLOC, BITSET_OBALLOC}; /* 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)) @@ -99,45 +59,45 @@ typedef unsigned long bitset_windex; #define BITSET_LIST_SIZE 1024 -enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES, - BITSET_OP_COPY, BITSET_OP_NOT, +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_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN, 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) +#define BITSET_SIZE_(SRC) (SRC)->b.ops->size (SRC) /* Return type of bitset SRC. */ -#define BITSET_TYPE_(DST) (DST)->b.ops->type +#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) +#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) +#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) +#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) +#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) +#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)->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)->b.ops->op4 (DST, SRC1, SRC2, SRC3, OP) /* DST = 0. */ #define BITSET_ZERO_(DST) BITSET_OP1_ (DST, BITSET_OP_ZERO); @@ -149,63 +109,63 @@ enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES, #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) +#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) +#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) + BITSET_OP2_ (DST, SRC, BITSET_OP_DISJOINT_P) /* DST = SRC. */ -#define BITSET_COPY_(DST, SRC) BITSET_OP2_ (DST, SRC, BITSET_OP_COPY) +#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) +#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) + BITSET_OP_OR) /* DST = SRC1 ^ SRC2. */ #define BITSET_XOR_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2,\ - BITSET_OP_XOR) + BITSET_OP_XOR) /* DST = SRC1 & SRC2. */ #define BITSET_AND_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \ - BITSET_OP_AND) + BITSET_OP_AND) /* DST = SRC1 & ~SRC2. */ #define BITSET_ANDN_(DST, SRC1, SRC2) BITSET_OP3_ (DST, SRC1, SRC2, \ - BITSET_OP_ANDN) + BITSET_OP_ANDN) /* 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) + 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) + 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) + BITSET_OP4_ (DST, SRC1, SRC2, SRC3, BITSET_OP_ANDN_OR) -/* Find list of up to NUM bits set in BSET starting from and including +/* 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) +(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) +(BSET)->b.ops->reverse_list (BSET, LIST, NUM, NEXT) struct bbitset_struct @@ -250,7 +210,6 @@ struct bitset_ops_struct #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 (); @@ -261,15 +220,9 @@ if (!BITSET_COMPATIBLE_ (DST, SRC1) \ #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, +extern int bitset_op4 PARAMS ((bitset, bitset, bitset, bitset, enum bitset_ops op)); #endif /* _BBITSET_H */ diff --git a/lib/bitset-int.h b/lib/bitset-int.h deleted file mode 100644 index 6c51166f..00000000 --- a/lib/bitset-int.h +++ /dev/null @@ -1,112 +0,0 @@ -/* Internal bitset definitions. - 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 _BITSET_INT_H -#define _BITSET_INT_H - -#ifdef HAVE_LIMITS_H -#include -#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 0 - -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_ZERO, BITSET_ONES, BITSET_EMPTY_P, - BITSET_COPY, BITSET_EQUAL_P, BITSET_SUBSET_P, BITSET_NOT, - BITSET_AND, BITSET_OR, BITSET_XOR, BITSET_ANDN, BITSET_ORN, - BITSET_OR_AND, BITSET_AND_OR, BITSET_ANDN_OR}; - -/* Return size in bits of bitset SRC. */ -#define BITSET__SIZE(SRC) (SRC)->ops->size (SRC) - -/* Set bit BITNO in bitset DST. */ -#define BITSET__SET(DST, BITNO) (DST)->ops->set (DST, BITNO) - -/* Reset bit BITNO in bitset DST. */ -#define BITSET__RESET(DST, BITNO) (DST)->ops->reset (DST, BITNO) - -/* Return non-zero if bit BITNO in bitset SRC is set. */ -#define BITSET__TEST(SRC, BITNO) (SRC)->ops->test (SRC, BITNO) - -/* Free bitset SRC. */ -#define BITSET__FREE(SRC) ((SRC)->ops->free) (SRC) - -/* Perform operation OP on DST. */ -#define BITSET__OP1(DST, OP) (DST)->ops->op1 (DST, OP) - -/* Perform operation OP on SRC and store in DST. */ -#define BITSET__OP2(DST, SRC, OP) (DST)->ops->op2 (DST, SRC, OP) - -/* DST = SRC1 OP SRC2. */ -#define BITSET__OP3(DST, SRC1, SRC2, OP) \ -(DST)->ops->op3 (DST, SRC1, SRC2, OP) - -/* DST = (SRC1 OP1 SRC2) OP2 SRC3. */ -#define BITSET__OP4(DST, SRC1, SRC2, SRC3, OP) \ -(DST)->ops->op4 (DST, SRC1, SRC2, SRC3, OP) - -/* DST = SRC. */ -#define BITSET__COPY(DST, SRC) BITSET__OP2 (DST, SRC, BITSET_COPY) - -/* 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)->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)->ops->reverse_list (BSET, LIST, NUM, NEXT) - -#endif /* _BITSET_INT_H */ diff --git a/lib/bitset.c b/lib/bitset.c index a8897fb7..0e8d26c9 100644 --- a/lib/bitset.c +++ b/lib/bitset.c @@ -22,105 +22,14 @@ #include #include "bitset.h" -#include "sbitset.h" +#include "abitset.h" #include "lbitset.h" #include "ebitset.h" +#include "bitset_stats.h" #include "obstack.h" static void bitset_print PARAMS ((FILE *, bitset, int)); -#if BITSET_STATS -#define BITSET_STATS_FILE "bitset.dat" - -#define BITSET_LOG_COUNT_BINS 10 -#define BITSET_LOG_SIZE_BINS 16 -#define BITSET_DENSITY_BINS 20 - -struct bitset_type_stats_struct -{ - unsigned int xmallocs; - unsigned int xfrees; - unsigned int oballocs; - unsigned int obfrees; - unsigned int lists; - unsigned int list_counts[BITSET_LOG_COUNT_BINS]; - unsigned int list_sizes[BITSET_LOG_SIZE_BINS]; - unsigned int list_density[BITSET_DENSITY_BINS]; -}; - -struct bitset_stats_struct -{ - unsigned int runs; - struct bitset_type_stats_struct types[BITSET_TYPE_NUM]; -}; - -struct bitset_stats_struct bitset_stats_data; -struct bitset_stats_struct *bitset_stats; - -static void bitset_percent_histogram_print PARAMS ((FILE *, const char *, - const char *, - unsigned int, - 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 *)); -static void bitset_stats_print PARAMS ((FILE *, int)); -static void bitset_stats_read PARAMS ((void)); -static void bitset_stats_write PARAMS ((void)); - -#define BITSET_STATS_XMALLOCS_INC(TYPE) \ - if (bitset_stats) \ - bitset_stats->types[(TYPE)].xmallocs++ - -#define BITSET_STATS_XFREES_INC(BSET) \ - if (bitset_stats) \ - 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) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].obfrees++ - -#define BITSET_STATS_LISTS_INC(BSET) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].lists++ - -#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++ - -#define BITSET_STATS_LIST_SIZES_INC(BSET, I) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++ - -#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \ - if (bitset_stats) \ - bitset_stats->types[BITSET_TYPE_ (BSET)].list_density[(I)]++ - -#else -#define BITSET_STATS_XMALLOCS_INC(TYPE) - -#define BITSET_STATS_XFREES_INC(BSET) - -#define BITSET_STATS_OBALLOCS_INC(TYPE) - -#define BITSET_STATS_OBFREES_INC(BSET) - -#define BITSET_STATS_LISTS_INC(BSET) - -#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) - -#define BITSET_STATS_LIST_SIZES_INC(BSET, I) - -#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) -#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. */ @@ -131,10 +40,13 @@ bitset_bytes (type, n_bits) { unsigned int bytes; + if (bitset_stats_enabled) + return bitset_stats_bytes (); + switch (type) { case BITSET_ARRAY: - bytes = sbitset_bytes (n_bits); + bytes = abitset_bytes (n_bits); break; case BITSET_LIST: @@ -160,10 +72,13 @@ bitset_init (bset, n_bits, type) bitset_bindex n_bits; enum bitset_type type; { + if (bitset_stats_enabled) + return bitset_stats_init (bset, n_bits, type); + switch (type) { case BITSET_ARRAY: - return sbitset_init (bset, n_bits); + return abitset_init (bset, n_bits); case BITSET_LIST: return lbitset_init (bset, n_bits); @@ -187,7 +102,6 @@ bitset_type_choose (n_bits, attr) { enum bitset_type type; -#if BITSET_CHECK /* Check attributes. */ if (attr & BITSET_FIXED && attr & BITSET_VARIABLE) abort (); @@ -196,7 +110,6 @@ bitset_type_choose (n_bits, attr) /* Note that sometimes we will be asked for a zero length fixed size bitset. */ -#endif /* Choose the type of bitset. */ @@ -222,14 +135,12 @@ bitset_alloc (n_bits, type) unsigned int bytes; bitset bset; - BITSET_STATS_XMALLOCS_INC (type); - bytes = bitset_bytes (type, n_bits); 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 + have variable length arrays, then we may need to allocate a dummy element. */ return bitset_init (bset, n_bits, type); @@ -246,8 +157,6 @@ bitset_obstack_alloc (bobstack, n_bits, type) unsigned int bytes; bitset bset; - BITSET_STATS_OBALLOCS_INC (type); - bytes = bitset_bytes (type, n_bits); bset = obstack_alloc (bobstack, bytes); @@ -277,8 +186,6 @@ void bitset_free (bset) bitset bset; { - BITSET_STATS_XFREES_INC (bset); - BITSET_FREE_ (bset); free (bset); } @@ -289,12 +196,25 @@ void bitset_obstack_free (bset) bitset bset; { - BITSET_STATS_OBFREES_INC (bset); - BITSET_FREE_ (bset); } +/* Return bitset type. */ +enum bitset_type +bitset_type_get (bset) + bitset bset; +{ + enum bitset_type type; + + type = BITSET_TYPE_ (bset); + if (type != BITSET_STATS) + return type; + + return bitset_stats_type_get (bset); +} + + /* Find next bit set in SRC starting from and including BITNO. Return -1 if SRC empty. */ int @@ -389,12 +309,13 @@ bitset_print (file, bset, verbose) int verbose; { unsigned int i, pos; + bitset_iterator iter; if (verbose) fprintf (file, "n_bits = %d, set = {", bitset_size (bset)); pos = 30; - BITSET_EXECUTE (bset, 0, i, + BITSET_FOR_EACH (iter, bset, i, 0) { if (pos > 70) { @@ -404,7 +325,7 @@ bitset_print (file, bset, verbose) fprintf (file, "%d ", i); pos += 1 + (i >= 10) + (i >= 100); - }); + }; if (verbose) fprintf (file, "}\n"); @@ -418,6 +339,7 @@ bitset_copy (dst, src) bitset src; { unsigned int i; + bitset_iterator iter; if (BITSET_COMPATIBLE_ (dst, src)) return BITSET_COPY_ (dst, src); @@ -425,10 +347,10 @@ 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_FOR_EACH (iter, src, i, 0) { bitset_set (dst, i); - }); + }; return 1; } @@ -453,6 +375,10 @@ bitset_count (src) int num; int count; + /* This could be greatly sped up by adding a count method for each + bitset implementation that uses a direct technique (based on + masks) for counting the number of bits set in a word. */ + next = 0; for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next)); count += num) @@ -495,7 +421,6 @@ bitset_subset_p (dst, src) bitset dst; bitset src; { - BITSET_CHECK2_ (dst, src); return BITSET_SUBSET_P_ (dst, src); } @@ -506,7 +431,6 @@ bitset_equal_p (dst, src) bitset dst; bitset src; { - BITSET_CHECK2_ (dst, src); return BITSET_EQUAL_P_ (dst, src); } @@ -517,7 +441,6 @@ bitset_disjoint_p (dst, src) bitset dst; bitset src; { - BITSET_CHECK2_ (dst, src); return BITSET_DISJOINT_P_ (dst, src); } @@ -528,7 +451,6 @@ bitset_not (dst, src) bitset dst; bitset src; { - BITSET_CHECK2_ (dst, src); return BITSET_NOT_ (dst, src); } @@ -540,7 +462,6 @@ bitset_or (dst, src1, src2) bitset src1; bitset src2; { - BITSET_CHECK3_ (dst, src1, src2); return BITSET_OR_ (dst, src1, src2); } @@ -552,7 +473,6 @@ bitset_and (dst, src1, src2) bitset src1; bitset src2; { - BITSET_CHECK3_ (dst, src1, src2); return BITSET_AND_ (dst, src1, src2); } @@ -564,7 +484,6 @@ bitset_xor (dst, src1, src2) bitset src1; bitset src2; { - BITSET_CHECK3_ (dst, src1, src2); return BITSET_XOR_ (dst, src1, src2); } @@ -576,11 +495,12 @@ bitset_andn (dst, src1, src2) bitset src1; bitset src2; { - BITSET_CHECK3_ (dst, src1, src2); return BITSET_ANDN_ (dst, src1, src2); } +/* This is a fallback for implementations that do not support + four operand operations. */ int bitset_op4 (dst, src1, src2, src3, op) bitset dst; @@ -593,7 +513,7 @@ bitset_op4 (dst, src1, src2, src3, op) bitset tmp; /* Create temporary bitset. */ - tmp = bitset_alloc (0, BITSET_TYPE_ (dst)); + tmp = bitset_alloc (0, bitset_type_get (dst)); switch (op) { @@ -630,7 +550,6 @@ bitset_or_and (dst, src1, src2, src3) bitset src2; bitset src3; { - BITSET_CHECK4_ (dst, src1, src2, src3); return BITSET_OR_AND_ (dst, src1, src2, src3); } @@ -644,7 +563,6 @@ bitset_and_or (dst, src1, src2, src3) bitset src2; bitset src3; { - BITSET_CHECK4_ (dst, src1, src2, src3); return BITSET_AND_OR_ (dst, src1, src2, src3); } @@ -658,7 +576,6 @@ bitset_andn_or (dst, src1, src2, src3) bitset src2; bitset src3; { - BITSET_CHECK4_ (dst, src1, src2, src3); return BITSET_ANDN_OR_ (dst, src1, src2, src3); } @@ -690,247 +607,3 @@ bitset_release_memory () lbitset_release_memory (); ebitset_release_memory (); } - - -#if BITSET_STATS -int -bitset_list (bset, list, num, next) - bitset bset; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; -{ - bitset_bindex count; - - count = BITSET_LIST_ (bset, list, num, next); - - 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; -} - - -/* Print a percentage histogram with message MSG to FILE. */ -static void -bitset_percent_histogram_print (file, name, msg, n_bins, bins) - FILE *file; - const char *name; - const char *msg; - unsigned int n_bins; - unsigned int *bins; -{ - unsigned int i; - unsigned int total; - - total = 0; - for (i = 0; i < n_bins; i++) - total += bins[i]; - - if (!total) - 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); -} - - -/* Print a log histogram with message MSG to FILE. */ -static void -bitset_log_histogram_print (file, name, msg, n_bins, bins) - FILE *file; - const char *name; - const char *msg; - unsigned int n_bins; - unsigned int *bins; -{ - unsigned int i; - unsigned int total; - unsigned int max_width; - - total = 0; - for (i = 0; i < n_bins; i++) - total += bins[i]; - - if (!total) - return; - - /* 2 * ceil (log10(2) * (N - 1)) + 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++) - fprintf (file, "%*d\t%8d (%5.1f%%)\n", - max_width, i, bins[i], 100.0 * bins[i] / total); - - /* Perhaps we should bail out once the histogram goes to zero. */ - 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); -} - - -/* Print bitset statistics to FILE. */ -static void -bitset_stats_print_1 (file, name, stats) - FILE *file; - const char *name; - struct bitset_type_stats_struct *stats; -{ - if (!stats) - return; - - fprintf (file, "%d %ss xmalloced, %d freed.\n", - stats->xmallocs, name, stats->xfrees); - fprintf (file, "%d %ss oballoced, %d freed.\n", - stats->oballocs, name, stats->obfrees); - - 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_histogram_print (file, name, "size log histogram\n", - BITSET_LOG_SIZE_BINS, stats->list_sizes); - - bitset_percent_histogram_print (file, name, "density histogram\n", - BITSET_DENSITY_BINS, stats->list_density); -} - - -/* Print all bitset statistics to FILE. */ -static void -bitset_stats_print (file, verbose) - FILE *file; - int verbose ATTRIBUTE_UNUSED; -{ - int i; - static const char *names[] = BITSET_TYPE_NAMES; - - if (!bitset_stats) - return; - - fprintf (file, "Bitset statistics:\n\n"); - - if (bitset_stats->runs > 1) - 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]); -} -#endif /* BITSET_STATS */ - - -/* Initialise bitset statistics logging. */ -void -bitset_stats_init () -{ -#if BITSET_STATS - bitset_stats = &bitset_stats_data; - bitset_stats_read (); -#endif /* BITSET_STATS */ -} - - -/* Read bitset statistics file. */ -static void -bitset_stats_read () -{ - FILE *file; - - 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++; -} - - -/* Write bitset statistics file. */ -static void -bitset_stats_write () -{ - FILE *file; - - 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."); -} - - -/* Dump bitset statistics to FILE. */ -void -bitset_stats_dump (file) - FILE *file; -{ -#if BITSET_STATS - bitset_stats_print (file, 0); - bitset_stats_write (); -#endif /* BITSET_STATS */ -} - - -/* Function to be called from debugger to print bitset stats. */ -void -debug_bitset_stats (void) -{ -#if BITSET_STATS - bitset_stats_print (stderr, 1); -#endif /* BITSET_STATS */ -} diff --git a/lib/bitset.h b/lib/bitset.h index 62d4c651..14c14f0b 100644 --- a/lib/bitset.h +++ b/lib/bitset.h @@ -17,7 +17,7 @@ along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifndef _BITSET_H -#define _BITSET_H +#define _BITSET_H /* This file is the public interface to the bitset abstract data type. Only use the functions and macros defined in this file. */ @@ -44,6 +44,18 @@ struct bitset_struct struct bbitset_struct b; }; + +/* The contents of this structure should be considered private. + It is used for iterating over set bits. */ +typedef struct +{ + bitset_bindex list[BITSET_LIST_SIZE]; + bitset_bindex next; + int num; + int i; +} bitset_iterator; + + /* Return bytes required for bitset of desired type and size. */ extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex)); @@ -78,7 +90,10 @@ 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 +/* Return bitset type. */ +extern enum bitset_type bitset_type_get PARAMS ((bitset)); + +#if BITSET_INLINE static inline void bitset_set PARAMS ((bitset, bitset_bindex)); static inline void bitset_reset PARAMS ((bitset, bitset_bindex)); static inline int bitset_test PARAMS ((bitset, bitset_bindex)); @@ -90,7 +105,7 @@ static inline void bitset_set (bset, bitno) { bitset_windex index = bitno / BITSET_WORD_BITS; bitset_windex offset = index - bset->b.cindex; - + if (offset < bset->b.csize) bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS)); else @@ -105,7 +120,7 @@ static inline void bitset_reset (bset, bitno) { bitset_windex index = bitno / BITSET_WORD_BITS; bitset_windex offset = index - bset->b.cindex; - + if (offset < bset->b.csize) bset->b.cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS)); else @@ -120,7 +135,7 @@ static inline int bitset_test (bset, bitno) { bitset_windex index = bitno / BITSET_WORD_BITS; bitset_windex offset = index - bset->b.cindex; - + if (offset < bset->b.csize) return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1; else @@ -128,7 +143,7 @@ static inline int bitset_test (bset, bitno) } #endif -#if BITSET_CACHE && ! BITSET_INLINE +#if ! BITSET_INLINE /* Set bit BITNO in bitset BSET. */ #define bitset_set(bset, bitno) \ @@ -168,16 +183,6 @@ do \ : (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) - -/* Reset bit BITNO in bitset SRC. */ -#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) -#endif /* Toggle bit BITNO in bitset BSET and return non-zero if now set. */ extern int bitset_toggle PARAMS ((bitset, bitset_bindex)); @@ -239,22 +244,17 @@ extern int bitset_prev PARAMS ((bitset, bitset_bindex)); /* Return non-zero if BITNO in SRC is the only set bit. */ extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex)); -/* Find list of up to NUM bits set in BSET starting from and including +/* 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. */ -#if BITSET_STATS -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) -#endif +BITSET_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) \ -BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT) +BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT) /* Find first set bit. */ extern int bitset_first PARAMS ((bitset)); @@ -265,69 +265,52 @@ extern int bitset_last PARAMS ((bitset)); /* Dump bitset. */ extern void bitset_dump PARAMS ((FILE *, bitset)); -/* Loop over all elements of BSET, starting with MIN, executing CODE. */ -#define BITSET_EXECUTE(BSET, MIN, N, CODE) \ -do { \ - bitset_bindex _list[BITSET_LIST_SIZE]; \ - bitset_bindex _next = (MIN); \ - int _num; \ - \ - while ((_num = bitset_list ((BSET), _list, BITSET_LIST_SIZE, &_next)))\ - { \ - int _i; \ - \ - for (_i = 0; _i < _num; _i++) \ - { \ - (N) = _list[_i]; \ - CODE; \ - } \ - if (_num < BITSET_LIST_SIZE) \ - break; \ - } \ -} while (0) +/* Loop over all elements of BSET, starting with MIN, setting BIT + to the index of each set bit. */ +#define BITSET_FOR_EACH(ITER, BSET, BIT, MIN) \ + for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \ + (ITER.num == BITSET_LIST_SIZE) \ + && (ITER.num = bitset_list (BSET, ITER.list, \ + BITSET_LIST_SIZE, &ITER.next));) \ + for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++) /* Loop over all elements of BSET, in reverse order starting with - MIN, executing CODE. */ -#define BITSET_REVERSE_EXECUTE(BSET, MIN, N, CODE) \ -do { \ - bitset_bindex _list[BITSET_LIST_SIZE]; \ - bitset_bindex _next = (MIN); \ - int _num; \ - \ - while ((_num = bitset_reverse_list ((BSET), _list, \ - BITSET_LIST_SIZE, &_next))) \ - { \ - int _i; \ - \ - for (_i = 0; _i < _num; _i++) \ - { \ - (N) = _list[_i]; \ - CODE; \ - } \ - if (_num < BITSET_LIST_SIZE) \ - break; \ - } \ -} while (0) + MIN, setting BIT to the index of each set bit. */ +#define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN) \ + for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \ + (ITER.num == BITSET_LIST_SIZE) \ + && (ITER.num = bitset_list_reverse (BSET, ITER.list, \ + BITSET_LIST_SIZE, &ITER.next));) \ + for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++) /* Define set operations in terms of logical operations. */ -#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2) +#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2) -#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2) +#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2) -#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2) +#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)); -/* Initialise bitset stats. */ -extern void bitset_stats_init PARAMS ((void)); +/* Enable bitset stats gathering. */ +extern void bitset_stats_enable PARAMS ((void)); + +/* Disable bitset stats gathering. */ +extern void bitset_stats_disable PARAMS ((void)); + +/* Read bitset stats file of accummulated stats. */ +void bitset_stats_read PARAMS ((const char *filename)); + +/* Write bitset stats file of accummulated stats. */ +void bitset_stats_write PARAMS ((const char *filename)); /* Dump bitset stats. */ extern void bitset_stats_dump PARAMS ((FILE *)); @@ -339,3 +322,4 @@ extern void debug_bitset PARAMS ((bitset)); extern void debug_bitset_stats PARAMS ((void)); #endif /* _BITSET_H */ + diff --git a/lib/bitset_stats.c b/lib/bitset_stats.c new file mode 100644 index 00000000..47dec487 --- /dev/null +++ b/lib/bitset_stats.c @@ -0,0 +1,627 @@ +/* Bitset statistics. + 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. +*/ + +/* This file is a wrapper bitset implementation for the other bitset + implementations. It provides bitset compatibility checking and + statistics gathering without having to instrument the bitset + implementations. When statistics gathering is enabled, the bitset + operations get vectored through here and we then call the appropriate + routines. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include "bbitset.h" +#include "abitset.h" +#include "ebitset.h" +#include "lbitset.h" +#include "bitset_stats.h" +#include +#include +#include + + +/* Configuration macros. */ +#define BITSET_STATS_FILE "bitset.dat" +#define BITSET_LOG_COUNT_BINS 10 +#define BITSET_LOG_SIZE_BINS 16 +#define BITSET_DENSITY_BINS 20 + + +/* Accessor macros. */ +#define BITSET_STATS_ALLOCS_INC(TYPE) \ + bitset_stats_info->types[(TYPE)].allocs++ +#define BITSET_STATS_FREES_INC(BSET) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++ +#define BITSET_STATS_SETS_INC(BSET) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++ +#define BITSET_STATS_CACHE_SETS_INC(BSET) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++ +#define BITSET_STATS_RESETS_INC(BSET) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++ +#define BITSET_STATS_CACHE_RESETS_INC(BSET) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++ +#define BITSET_STATS_TESTS_INC(BSET) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++ +#define BITSET_STATS_CACHE_TESTS_INC(BSET) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++ +#define BITSET_STATS_LISTS_INC(BSET) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++ +#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++ +#define BITSET_STATS_LIST_SIZES_INC(BSET, I) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++ +#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \ + bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++ + + +typedef struct bitset_stats_struct +{ + bitset bset; +} *bitset_stats; + + +struct bitset_struct +{ + struct bbitset_struct b; + struct bitset_stats_struct s; +}; + + +struct bitset_type_info_struct +{ + unsigned int allocs; + unsigned int frees; + unsigned int lists; + unsigned int sets; + unsigned int cache_sets; + unsigned int resets; + unsigned int cache_resets; + unsigned int tests; + unsigned int cache_tests; + unsigned int list_counts[BITSET_LOG_COUNT_BINS]; + unsigned int list_sizes[BITSET_LOG_SIZE_BINS]; + unsigned int list_density[BITSET_DENSITY_BINS]; +}; + +struct bitset_stats_info_struct +{ + unsigned int runs; + struct bitset_type_info_struct types[BITSET_TYPE_NUM]; +}; + + +struct bitset_stats_info_struct bitset_stats_info_data; +struct bitset_stats_info_struct *bitset_stats_info; +int bitset_stats_enabled = 0; + + +static void bitset_stats_set PARAMS ((bitset, bitset_bindex)); +static void bitset_stats_reset PARAMS ((bitset, bitset_bindex)); +static int bitset_stats_test PARAMS ((bitset, bitset_bindex)); +static int bitset_stats_size PARAMS ((bitset)); +static int bitset_stats_op1 PARAMS ((bitset, enum bitset_ops)); +static int bitset_stats_op2 PARAMS ((bitset, bitset, enum bitset_ops)); +static int bitset_stats_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops)); +static int bitset_stats_op4 PARAMS ((bitset, bitset, bitset, bitset, + enum bitset_ops)); +static int bitset_stats_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static int bitset_stats_reverse_list +PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); +static void bitset_stats_free PARAMS ((bitset)); +static void bitset_percent_histogram_print PARAMS ((FILE *, const char *, + const char *, + unsigned int, + 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_info_struct *)); +static void bitset_stats_print PARAMS ((FILE *, int)); + + +/* Print a percentage histogram with message MSG to FILE. */ +static void +bitset_percent_histogram_print (file, name, msg, n_bins, bins) + FILE *file; + const char *name; + const char *msg; + unsigned int n_bins; + unsigned int *bins; +{ + unsigned int i; + unsigned int total; + + total = 0; + for (i = 0; i < n_bins; i++) + total += bins[i]; + + if (!total) + 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); +} + + +/* Print a log histogram with message MSG to FILE. */ +static void +bitset_log_histogram_print (file, name, msg, n_bins, bins) + FILE *file; + const char *name; + const char *msg; + unsigned int n_bins; + unsigned int *bins; +{ + unsigned int i; + unsigned int total; + unsigned int max_width; + unsigned int last_bin; + + total = 0; + for (i = 0; i < n_bins; i++) + total += bins[i]; + + if (!total) + return; + + for (i = n_bins; i > 3 && ! bins[i - 1]; i--) + continue; + last_bin = i - 1; + + /* 2 * ceil (log10 (2) * (N - 1)) + 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++) + fprintf (file, "%*d\t%8d (%5.1f%%)\n", + max_width, i, bins[i], 100.0 * bins[i] / total); + + for (; i <= last_bin; 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); +} + + +/* Print bitset statistics to FILE. */ +static void +bitset_stats_print_1 (file, name, stats) + FILE *file; + const char *name; + struct bitset_type_info_struct *stats; +{ + if (!stats) + return; + + fprintf (file, "%s:\n", name); + fprintf (file, "%d bitset_allocs, %d freed (%.2f%%).\n", + stats->allocs, stats->frees, + stats->allocs ? 100.0 * stats->frees / stats->allocs : 0); + fprintf (file, "%d bitset_sets, %d cached (%.2f%%)\n", + stats->sets, stats->cache_sets, + stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0); + fprintf (file, "%d bitset_resets, %d cached (%.2f%%)\n", + stats->resets, stats->cache_resets, + stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0); + fprintf (file, "%d bitset_tests, %d cached (%.2f%%)\n", + stats->tests, stats->cache_tests, + stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0); + + 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_histogram_print (file, name, "size log histogram\n", + BITSET_LOG_SIZE_BINS, stats->list_sizes); + + bitset_percent_histogram_print (file, name, "density histogram\n", + BITSET_DENSITY_BINS, stats->list_density); +} + + +/* Print all bitset statistics to FILE. */ +static void +bitset_stats_print (file, verbose) + FILE *file; + int verbose ATTRIBUTE_UNUSED; +{ + int i; + static const char *names[] = BITSET_TYPE_NAMES; + + if (!bitset_stats_info) + return; + + fprintf (file, "Bitset statistics:\n\n"); + + if (bitset_stats_info->runs > 1) + fprintf (file, "Accumulated runs = %d\n", bitset_stats_info->runs); + + for (i = 0; i < BITSET_TYPE_NUM; i++) + bitset_stats_print_1 (file, names[i], &bitset_stats_info->types[i]); +} + + +/* Initialise bitset statistics logging. */ +void +bitset_stats_enable () +{ + if (!bitset_stats_info) + bitset_stats_info = &bitset_stats_info_data; + bitset_stats_enabled = 1; +} + + +void +bitset_stats_disable () +{ + bitset_stats_enabled = 0; +} + + +/* Read bitset statistics file. */ +void +bitset_stats_read (filename) + const char *filename; +{ + FILE *file; + + if (!bitset_stats_info) + return; + + if (!filename) + filename = BITSET_STATS_FILE; + + file = fopen (filename, "r"); + if (file) + { + if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_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_info_data.runs++; +} + + +/* Write bitset statistics file. */ +void +bitset_stats_write (filename) + const char *filename; +{ + FILE *file; + + if (!bitset_stats_info) + return; + + if (!filename) + filename = BITSET_STATS_FILE; + + file = fopen (filename, "w"); + if (file) + { + if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data), + 1, file) != 1) + perror ("Could not write stats file."); + fclose (file); + } + else + perror ("Could not open stats file for writing."); +} + + +/* Dump bitset statistics to FILE. */ +void +bitset_stats_dump (file) + FILE *file; +{ + bitset_stats_print (file, 0); +} + + +/* Function to be called from debugger to print bitset stats. */ +void +debug_bitset_stats (void) +{ + bitset_stats_print (stderr, 1); +} + + +static void +bitset_stats_set (dst, bitno) + bitset dst; + bitset_bindex bitno; +{ + bitset bset = dst->s.bset; + bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex offset = index - bset->b.cindex; + + BITSET_STATS_SETS_INC (bset); + + if (offset < bset->b.csize) + { + bset->b.cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS)); + BITSET_STATS_CACHE_SETS_INC (bset); + } + else + BITSET_SET_ (bset, bitno); +} + + +static void +bitset_stats_reset (dst, bitno) + bitset dst; + bitset_bindex bitno; +{ + bitset bset = dst->s.bset; + bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex offset = index - bset->b.cindex; + + BITSET_STATS_RESETS_INC (bset); + + if (offset < bset->b.csize) + { + bset->b.cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS)); + BITSET_STATS_CACHE_RESETS_INC (bset); + } + else + BITSET_RESET_ (bset, bitno); +} + + +static int +bitset_stats_test (src, bitno) + bitset src; + bitset_bindex bitno; +{ + bitset bset = src->s.bset; + bitset_windex index = bitno / BITSET_WORD_BITS; + bitset_windex offset = index - bset->b.cindex; + + BITSET_STATS_TESTS_INC (bset); + + if (offset < bset->b.csize) + { + BITSET_STATS_CACHE_TESTS_INC (bset); + return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1; + } + else + return BITSET_TEST_ (bset, bitno); +} + + +static int +bitset_stats_size (src) + bitset src; +{ + return BITSET_SIZE_ (src->s.bset); +} + + +static int +bitset_stats_op1 (dst, op) + bitset dst; + enum bitset_ops op; +{ + return BITSET_OP1_ (dst->s.bset, op); +} + + +static int +bitset_stats_op2 (dst, src, op) + bitset dst; + bitset src; + enum bitset_ops op; +{ + BITSET_CHECK2_ (dst, src); + return BITSET_OP2_ (dst->s.bset, src->s.bset, op); +} + + +static int +bitset_stats_op3 (dst, src1, src2, op) + bitset dst; + bitset src1; + bitset src2; + enum bitset_ops op; +{ + BITSET_CHECK3_ (dst, src1, src2); + return BITSET_OP3_ (dst->s.bset, src1->s.bset, src2->s.bset, op); +} + + +static int +bitset_stats_op4 (dst, src1, src2, src3, op) + bitset dst; + bitset src1; + bitset src2; + bitset src3; + enum bitset_ops op; +{ + BITSET_CHECK4_ (dst, src1, src2, src3); + + /* This is a bit of a hack. If the implementation handles + a four operand operation then vector to it, passing + the enclosed bitsets. Otherwise use the fallback + bitset_op4 routine. */ + if (dst->s.bset->b.ops->op4 != bitset_op4) + return BITSET_OP4_ (dst->s.bset, src1->s.bset, src2->s.bset, + src3->s.bset, op); + + return bitset_op4 (dst, src1, src2, src3, op); +} + + +static int +bitset_stats_list (bset, list, num, next) + bitset bset; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex count; + bitset_bindex tmp; + bitset_bindex size; + bitset_bindex i; + enum bitset_type type; + + count = BITSET_LIST_ (bset->s.bset, list, num, next); + + type = BITSET_TYPE_ (bset->s.bset); + BITSET_STATS_LISTS_INC (bset->s.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->s.bset, i); + + /* Log histogram of number of bits in set. */ + size = BITSET_SIZE_ (bset->s.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->s.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->s.bset, i); + return count; +} + + +static int +bitset_stats_reverse_list (bset, list, num, next) + bitset bset; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + return BITSET_REVERSE_LIST_ (bset->s.bset, list, num, next); +} + + +static void +bitset_stats_free (bset) + bitset bset; +{ + BITSET_STATS_FREES_INC (bset->s.bset); + BITSET_FREE_ (bset->s.bset); +} + + +struct bitset_ops_struct bitset_stats_ops = { + bitset_stats_set, + bitset_stats_reset, + bitset_stats_test, + bitset_stats_size, + bitset_stats_op1, + bitset_stats_op2, + bitset_stats_op3, + bitset_stats_op4, + bitset_stats_list, + bitset_stats_reverse_list, + bitset_stats_free, + BITSET_STATS +}; + + +/* Return enclosed bitset type. */ +enum bitset_type +bitset_stats_type_get (bset) + bitset bset; +{ + return BITSET_TYPE_ (bset->s.bset); +} + + +int bitset_stats_bytes (void) +{ + return sizeof (struct bitset_struct); +} + + +bitset +bitset_stats_init (bset, n_bits, type) + bitset bset; + bitset_bindex n_bits; + enum bitset_type type; +{ + unsigned int bytes; + bitset sbset; + + bset->b.ops = &bitset_stats_ops; + + /* Disable cache. */ + bset->b.cindex = 0; + bset->b.csize = 0; + bset->b.cdata = 0; + + /* Set up the actual bitset implementation that + we are a wrapper over. */ + switch (type) + { + case BITSET_ARRAY: + bytes = abitset_bytes (n_bits); + sbset = (bitset) xcalloc (1, bytes); + abitset_init (sbset, n_bits); + break; + + case BITSET_LIST: + bytes = lbitset_bytes (n_bits); + sbset = (bitset) xcalloc (1, bytes); + lbitset_init (sbset, n_bits); + break; + + case BITSET_TABLE: + bytes = ebitset_bytes (n_bits); + sbset = (bitset) xcalloc (1, bytes); + ebitset_init (sbset, n_bits); + break; + + default: + abort (); + } + + bset->s.bset = sbset; + + BITSET_STATS_ALLOCS_INC (type); + + return bset; +} diff --git a/lib/bitset_stats.h b/lib/bitset_stats.h new file mode 100644 index 00000000..2ebd29e7 --- /dev/null +++ b/lib/bitset_stats.h @@ -0,0 +1,33 @@ +/* Functions to support bitset statistics. + 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 _BITSET_STATS_H +#define _BITSET_STATS_H + +#include "bbitset.h" + +extern int bitset_stats_enabled; + +extern enum bitset_type bitset_stats_type_get PARAMS ((bitset)); + +extern int bitset_stats_bytes PARAMS ((void)); + +extern bitset bitset_stats_init PARAMS ((bitset, bitset_bindex, + enum bitset_type)); + +#endif diff --git a/lib/bitsetv.c b/lib/bitsetv.c index be4bfa7d..3d8e368a 100644 --- a/lib/bitsetv.c +++ b/lib/bitsetv.c @@ -49,7 +49,7 @@ bitsetv_alloc (n_vecs, n_bits, type) for (i = 0; i < n_vecs; i++) { bsetv[i] = (bitset) ((char *) bsetv + vector_bytes + i * bytes); - + bitset_init (bsetv[i], n_bits, type); } diff --git a/lib/ebitset.c b/lib/ebitset.c index 3e84efa8..c9b156c7 100644 --- a/lib/ebitset.c +++ b/lib/ebitset.c @@ -47,10 +47,7 @@ /* 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 \ @@ -197,9 +194,6 @@ ebitset_elt_alloc () } else { - /* We can't use gcc_obstack_init to initialize the obstack since - print-rtl.c now calls bitset functions, and bitset is linked - into the gen* functions. */ if (!ebitset_obstack_init) { ebitset_obstack_init = 1; @@ -242,7 +236,7 @@ ebitset_elt_alloc () } -/* Allocate a ebitset element. The bits are not cleared. */ +/* Allocate a ebitset element. The bits are cleared. */ static inline ebitset_elt * ebitset_elt_calloc () { diff --git a/lib/ebitset.h b/lib/ebitset.h index b41485f2..6fb6a7ff 100644 --- a/lib/ebitset.h +++ b/lib/ebitset.h @@ -17,7 +17,7 @@ along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifndef _EBITSET_H -#define _EBITSET_H +#define _EBITSET_H #include "bbitset.h" diff --git a/lib/lbitset.c b/lib/lbitset.c index f426c301..972094bb 100644 --- a/lib/lbitset.c +++ b/lib/lbitset.c @@ -40,9 +40,7 @@ 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; @@ -139,9 +137,6 @@ lbitset_elt_alloc () } else { - /* We can't use gcc_obstack_init to initialize the obstack since - print-rtl.c now calls bitset functions, and bitset is linked - into the gen* functions. */ if (!lbitset_obstack_init) { lbitset_obstack_init = 1; @@ -184,7 +179,7 @@ lbitset_elt_alloc () } -/* Allocate a lbitset element. The bits are not cleared. */ +/* Allocate a lbitset element. The bits are cleared. */ static inline lbitset_elt * lbitset_elt_calloc () { diff --git a/lib/lbitset.h b/lib/lbitset.h index 078c2ecc..363bf8d0 100644 --- a/lib/lbitset.h +++ b/lib/lbitset.h @@ -17,7 +17,7 @@ along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifndef _LBITSET_H -#define _LBITSET_H +#define _LBITSET_H #include "bbitset.h" diff --git a/lib/libiberty.h b/lib/libiberty.h new file mode 100644 index 00000000..6276be6d --- /dev/null +++ b/lib/libiberty.h @@ -0,0 +1,58 @@ +/* Fake libiberty.h for Bison. + Copyright (C) 2002 Free Software Foundation, Inc. + + 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, 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. */ + + +/* Bison depends on libiberty's implementation of bitsets, which + requires a `libiberty.h' file. This file provides the minimum + services. */ + +#ifndef BISON_LIBIBERTY_H_ +# define BISON_LIBIBERTY_H_ 1 + +# if HAVE_CONFIG_H +# include +# endif +# include + +/* 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" + +#endif /* ! BISON_LIBIBERTY_H_ */ diff --git a/src/closure.c b/src/closure.c index 689326de..02d275a7 100644 --- a/src/closure.c +++ b/src/closure.c @@ -74,12 +74,13 @@ print_firsts (void) fprintf (stderr, "FIRSTS\n"); for (i = ntokens; i < nsyms; i++) { + bitset_iterator iter; fprintf (stderr, "\t%s firsts\n", symbols[i]->tag); - BITSET_EXECUTE (FIRSTS (i), 0, j, - { - fprintf (stderr, "\t\t%s\n", - symbols[j + ntokens]->tag); - }); + BITSET_FOR_EACH (iter, FIRSTS (i), j, 0) + { + fprintf (stderr, "\t\t%s\n", + symbols[j + ntokens]->tag); + } } fprintf (stderr, "\n\n"); } @@ -94,15 +95,16 @@ print_fderives (void) fprintf (stderr, "FDERIVES\n"); for (i = ntokens; i < nsyms; i++) { + bitset_iterator iter; fprintf (stderr, "\t%s derives\n", symbols[i]->tag); - BITSET_EXECUTE (FDERIVES (i), 0, r, - { - item_number_t *rhsp = NULL; - fprintf (stderr, "\t\t%d:", r - 1); - for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp) - fprintf (stderr, " %s", symbols[*rhsp]->tag); - fputc ('\n', stderr); - }); + BITSET_FOR_EACH (iter, FDERIVES (i), r, 0) + { + item_number_t *rhsp = NULL; + fprintf (stderr, "\t\t%d:", r - 1); + for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp) + fprintf (stderr, " %s", symbols[*rhsp]->tag); + fputc ('\n', stderr); + } } fprintf (stderr, "\n\n"); } @@ -198,6 +200,8 @@ closure (item_number_t *core, int n) /* A bit index over RULESET. */ rule_number_t ruleno; + bitset_iterator iter; + if (trace_flag) print_closure ("input", core, n); @@ -209,18 +213,18 @@ closure (item_number_t *core, int n) nritemset = 0; c = 0; - BITSET_EXECUTE (ruleset, 0, ruleno, - { - item_number_t itemno = rules[ruleno].rhs - ritem; - while (c < n && core[c] < itemno) - { - itemset[nritemset] = core[c]; - nritemset++; - c++; - } - itemset[nritemset] = itemno; - nritemset++; - }); + BITSET_FOR_EACH (iter, ruleset, ruleno, 0) + { + item_number_t itemno = rules[ruleno].rhs - ritem; + while (c < n && core[c] < itemno) + { + itemset[nritemset] = core[c]; + nritemset++; + c++; + } + itemset[nritemset] = itemno; + nritemset++; + }; while (c < n) { diff --git a/src/lalr.c b/src/lalr.c index 9af69ee2..68039946 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -420,16 +420,18 @@ lookaheads_print (FILE *out) fprintf (out, "Lookaheads: BEGIN\n"); for (i = 0; i < nstates; ++i) { + bitset_iterator iter; + fprintf (out, "State %d: %d lookaheads\n", i, states[i]->nlookaheads); for (j = 0; j < states[i]->nlookaheads; ++j) - BITSET_EXECUTE (states[i]->lookaheads[j], 0, k, + BITSET_FOR_EACH (iter, states[i]->lookaheads[j], k, 0) { fprintf (out, " on %d (%s) -> rule %d\n", k, symbols[k]->tag, states[i]->lookaheads_rule[j]->number - 1); - }); + }; } fprintf (out, "Lookaheads: END\n"); } diff --git a/src/main.c b/src/main.c index c5f78d10..5a0fb458 100644 --- a/src/main.c +++ b/src/main.c @@ -21,6 +21,7 @@ #include "system.h" +#include "bitset_stats.h" #include "bitset.h" #include "getargs.h" #include "symtab.h" @@ -50,11 +51,12 @@ main (int argc, char *argv[]) bindtextdomain (PACKAGE, LOCALEDIR); textdomain (PACKAGE); - bitset_stats_init (); - lineno = 0; getargs (argc, argv); + if (trace_flag) + bitset_stats_enable (); + muscle_init (); /* Read the input. Copy some parts of it to FGUARD, FACTION, FTABLE @@ -122,5 +124,8 @@ main (int argc, char *argv[]) alloca (0); #endif + if (trace_flag) + bitset_stats_dump (stderr); + return complain_message_count ? EXIT_FAILURE : EXIT_SUCCESS; } diff --git a/src/output.c b/src/output.c index c2a64db4..5eddd106 100644 --- a/src/output.c +++ b/src/output.c @@ -442,19 +442,20 @@ action_row (state_t *state) if (redp->num >= 1) { int j; + bitset_iterator biter; /* loop over all the rules available here which require lookahead */ for (i = state->nlookaheads - 1; i >= 0; --i) /* and find each token which the rule finds acceptable to come next */ - BITSET_EXECUTE (state->lookaheads[i], 0, j, + BITSET_FOR_EACH (biter, state->lookaheads[i], j, 0) { /* and record this rule as the rule to use if that token follows. */ if (actrow[j] != 0) conflicted = conflrow[j] = 1; actrow[j] = -state->lookaheads_rule[i]->number; - }); + } } /* Now see which tokens are allowed for shifts in this state. For diff --git a/src/print_graph.c b/src/print_graph.c index 2cd54701..4ae726fb 100644 --- a/src/print_graph.c +++ b/src/print_graph.c @@ -90,26 +90,24 @@ print_core (struct obstack *oout, state_t *state) && state->nlookaheads) { int j, k; + bitset_iterator biter; int nlookaheads = 0; + /* Look for lookaheads corresponding to this rule. */ for (j = 0; j < state->nlookaheads; ++j) - BITSET_EXECUTE (state->lookaheads[j], 0, k, - { + BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0) if (state->lookaheads_rule[j]->number == rule) nlookaheads++; - }); if (nlookaheads) { obstack_sgrow (oout, " ["); for (j = 0; j < state->nlookaheads; ++j) - BITSET_EXECUTE (state->lookaheads[j], 0, k, - { + BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0) if (state->lookaheads_rule[j]->number == rule) obstack_fgrow2 (oout, "%s%s", symbols[k]->tag, --nlookaheads ? ", " : ""); - }); obstack_sgrow (oout, "]"); } } diff --git a/src/state.c b/src/state.c index 512907ff..425cf024 100644 --- a/src/state.c +++ b/src/state.c @@ -195,27 +195,24 @@ void state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out) { int j, k; + bitset_iterator biter; int nlookaheads = 0; /* Count the number of lookaheads corresponding to this rule. */ for (j = 0; j < state->nlookaheads; ++j) - BITSET_EXECUTE (state->lookaheads[j], 0, k, - { + BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0) if (state->lookaheads_rule[j]->number == rule->number) nlookaheads++; - }); /* Print them if there are. */ if (nlookaheads) { fprintf (out, " ["); for (j = 0; j < state->nlookaheads; ++j) - BITSET_EXECUTE (state->lookaheads[j], 0, k, - { + BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0) if (state->lookaheads_rule[j]->number == rule->number) fprintf (out, "%s%s", symbols[k]->tag, --nlookaheads ? ", " : ""); - }); fprintf (out, "]"); } } -- 2.45.2