From: Akim Demaille Date: Tue, 2 Jul 2002 13:51:27 +0000 (+0000) Subject: * lib/libiberty.h: New. X-Git-Tag: BISON-1_49b~91 X-Git-Url: https://git.saurik.com/bison.git/commitdiff_plain/613f5e1a895b0742c9b6c5e9461e4cf3f7389d7e?ds=sidebyside * 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. --- 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/abitset.c b/lib/abitset.c new file mode 100644 index 00000000..9cdb40ce --- /dev/null +++ b/lib/abitset.c @@ -0,0 +1,651 @@ +/* Array 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 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. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#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 abitset_struct +{ + unsigned int n_bits; /* Number of bits. */ + bitset_word words[1]; /* The array of bits. */ +} +*abitset; + + +struct bitset_struct +{ + struct bbitset_struct b; + struct abitset_struct a; +}; + +static void abitset_unused_clear PARAMS ((bitset)); + +static int abitset_small_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); + +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 abitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex, + bitset_bindex *)); +static int abitset_reverse_list +PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *)); + +#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 +abitset_size (src) + bitset src; +{ + return ABITSET_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. */ +static int +abitset_small_list (src, list, num, next) + bitset src; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_bindex count; + bitset_windex size; + bitset_word word; + + word = ABITSET_WORDS (src)[0]; + + /* Short circuit common case. */ + if (!word) + return 0; + + size = ABITSET_N_BITS (src); + bitno = *next; + if (bitno >= size) + return 0; + + word >>= bitno; + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + if (num >= BITSET_WORD_BITS) + { + for (count = 0; word; bitno++) + { + if (word & 1) + 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; +} + + +/* Set bit BITNO in bitset DST. */ +static void +abitset_set (dst, bitno) + bitset dst ATTRIBUTE_UNUSED; + bitset_bindex bitno ATTRIBUTE_UNUSED; +{ + /* This should never occur for abitsets. */ + abort (); +} + + +/* Reset bit BITNO in bitset DST. */ +static void +abitset_reset (dst, bitno) + bitset dst ATTRIBUTE_UNUSED; + bitset_bindex bitno ATTRIBUTE_UNUSED; +{ + /* This should never occur for abitsets. */ + abort (); +} + + +/* Test bit BITNO in bitset SRC. */ +static int +abitset_test (src, bitno) + bitset src ATTRIBUTE_UNUSED; + bitset_bindex bitno ATTRIBUTE_UNUSED; +{ + /* This should never occur for abitsets. */ + abort (); + return 0; +} + + +/* Find list of up to NUM bits set in BSET in reverse order, starting + from and including NEXT and store in array LIST. Return with + actual number of bits found and with *NEXT indicating where search + stopped. */ +static int +abitset_reverse_list (src, list, num, next) + bitset src; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_bindex rbitno; + bitset_bindex count; + bitset_windex windex; + unsigned int bitcnt; + bitset_bindex bitoff; + bitset_word word; + bitset_word *srcp = ABITSET_WORDS (src); + bitset_bindex n_bits = ABITSET_N_BITS (src); + + rbitno = *next; + + /* If num is 1, we could speed things up with a binary search + of the word of interest. */ + + if (rbitno >= n_bits) + return 0; + + count = 0; + + bitno = n_bits - (rbitno + 1); + + windex = bitno / BITSET_WORD_BITS; + bitcnt = bitno % BITSET_WORD_BITS; + bitoff = windex * BITSET_WORD_BITS; + + for (; windex != ~0U; windex--, bitoff -= BITSET_WORD_BITS, + bitcnt = BITSET_WORD_BITS - 1) + { + word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); + for (; word; bitcnt--) + { + if (word & BITSET_MSB) + { + list[count++] = bitoff + bitcnt; + if (count >= num) + { + *next = n_bits - (bitoff + bitcnt); + return count; + } + } + word <<= 1; + } + } + + *next = n_bits - (bitoff + 1); + return count; +} + + +/* Find list of up to NUM bits set in BSET starting from and including + *NEXT and store in array LIST. Return with actual number of bits + found and with *NEXT indicating where search stopped. */ +static int +abitset_list (src, list, num, next) + bitset src; + bitset_bindex *list; + bitset_bindex num; + bitset_bindex *next; +{ + bitset_bindex bitno; + bitset_bindex count; + bitset_windex windex; + bitset_bindex bitoff; + bitset_windex size = src->b.csize; + bitset_word *srcp = ABITSET_WORDS (src); + bitset_word word; + + bitno = *next; + + count = 0; + if (!bitno) + { + /* Many bitsets are zero, so make this common case fast. */ + for (windex = 0; windex < size && !srcp[windex]; windex++) + continue; + if (windex >= size) + return 0; + + /* If num is 1, we could speed things up with a binary search + of the current word. */ + + bitoff = windex * BITSET_WORD_BITS; + } + else + { + if (bitno >= ABITSET_N_BITS (src)) + return 0; + + windex = bitno / BITSET_WORD_BITS; + bitno = bitno % BITSET_WORD_BITS; + + if (bitno) + { + /* Handle the case where we start within a word. + Most often, this is executed with large bitsets + with many set bits where we filled the array + on the previous call to this function. */ + + bitoff = windex * BITSET_WORD_BITS; + word = srcp[windex] >> bitno; + for (bitno = bitoff + bitno; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + windex++; + } + bitoff = windex * BITSET_WORD_BITS; + } + + for (; windex < size; windex++, bitoff += BITSET_WORD_BITS) + { + if (!(word = srcp[windex])) + continue; + + if ((count + BITSET_WORD_BITS) < num) + { + for (bitno = bitoff; word; bitno++) + { + if (word & 1) + list[count++] = bitno; + word >>= 1; + } + } + else + { + for (bitno = bitoff; word; bitno++) + { + if (word & 1) + { + list[count++] = bitno; + if (count >= num) + { + *next = bitno + 1; + return count; + } + } + word >>= 1; + } + } + } + + *next = bitoff; + return count; +} + + +/* Ensure that any unused bits within the last word are clear. */ +static inline void +abitset_unused_clear (dst) + bitset dst; +{ + unsigned int last_bit; + + last_bit = ABITSET_N_BITS (dst) % BITSET_WORD_BITS; + if (last_bit) + ABITSET_WORDS (dst)[dst->b.csize - 1] &= + (bitset_word) ((1 << last_bit) - 1); +} + + +static int +abitset_op1 (dst, op) + bitset dst; + enum bitset_ops op; +{ + unsigned int i; + bitset_word *dstp = ABITSET_WORDS (dst); + unsigned int bytes; + + bytes = sizeof (bitset_word) * dst->b.csize; + + switch (op) + { + case BITSET_OP_ZERO: + memset (dstp, 0, bytes); + break; + + case BITSET_OP_ONES: + memset (dstp, ~0, bytes); + abitset_unused_clear (dst); + break; + + case BITSET_OP_EMPTY_P: + for (i = 0; i < dst->b.csize; i++) + if (dstp[i]) + return 0; + break; + + default: + abort (); + } + + return 1; +} + + +static int +abitset_op2 (dst, src, op) + bitset dst; + bitset src; + enum bitset_ops op; +{ + unsigned int i; + bitset_word *srcp = ABITSET_WORDS (src); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + switch (op) + { + case BITSET_OP_COPY: + if (srcp == dstp) + break; + memcpy (dstp, srcp, sizeof (bitset_word) * size); + break; + + case BITSET_OP_NOT: + for (i = 0; i < size; i++) + *dstp++ = ~(*srcp++); + abitset_unused_clear (dst); + break; + + case BITSET_OP_EQUAL_P: + for (i = 0; i < size; i++) + if (*srcp++ != *dstp++) + return 0; + break; + + case BITSET_OP_SUBSET_P: + for (i = 0; i < size; i++, dstp++, srcp++) + 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 (); + } + + return 1; +} + + +static int +abitset_op3 (dst, src1, src2, op) + bitset dst; + bitset src1; + bitset src2; + enum bitset_ops op; +{ + unsigned int i; + int changed = 0; + bitset_word *src1p = ABITSET_WORDS (src1); + bitset_word *src2p = ABITSET_WORDS (src2); + bitset_word *dstp = ABITSET_WORDS (dst); + bitset_windex size = dst->b.csize; + + switch (op) + { + case BITSET_OP_OR: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ | *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_OP_AND: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ & *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_OP_XOR: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ ^ *src2p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_OP_ANDN: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = *src1p++ & ~(*src2p++); + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + default: + abort (); + } + + return changed; +} + + +static int +abitset_op4 (dst, src1, src2, src3, op) + bitset dst; + bitset src1; + bitset src2; + bitset src3; + enum bitset_ops op; +{ + unsigned int i; + int changed = 0; + 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; + + switch (op) + { + case BITSET_OP_OR_AND: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_OP_AND_OR: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + case BITSET_OP_ANDN_OR: + for (i = 0; i < size; i++, dstp++) + { + bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + break; + + default: + abort (); + } + + return changed; +} + + +/* Vector of operations for single word bitsets. */ +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 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 +abitset_bytes (n_bits) + bitset_bindex n_bits; +{ + unsigned int bytes, size; + + size = ABITSET_N_WORDS (n_bits); + bytes = size * sizeof (bitset_word); + return sizeof (struct bitset_struct) + bytes - sizeof (bitset_word); +} + + +bitset +abitset_init (bset, n_bits) + bitset bset; + bitset_bindex n_bits; +{ + bitset_windex size; + + 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 = &abitset_small_ops; + else + bset->b.ops = &abitset_ops; + + bset->b.cindex = 0; + bset->b.csize = size; + bset->b.cdata = ABITSET_WORDS (bset); + return bset; +} diff --git a/lib/abitset.h b/lib/abitset.h new file mode 100644 index 00000000..1faeee4d --- /dev/null +++ b/lib/abitset.h @@ -0,0 +1,28 @@ +/* Functions to support abitsets. + 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 _ABITSET_H +#define _ABITSET_H + +#include "bbitset.h" + +extern int abitset_bytes PARAMS ((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/lib/sbitset.c b/lib/sbitset.c deleted file mode 100644 index 97d13335..00000000 --- a/lib/sbitset.c +++ /dev/null @@ -1,672 +0,0 @@ -/* Simple 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 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. -*/ - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#include "sbitset.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 -{ - 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)->s.words) -#define SBITSET_N_BITS(X) ((X)->s.n_bits) - - -/* Return size in bits of bitset SRC. */ -static int -sbitset_size (src) - bitset 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. */ -static int -sbitset_small_list (src, list, num, next) - bitset src; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; -{ - bitset_bindex bitno; - bitset_bindex count; - bitset_windex size; - bitset_word word; - - word = SBITSET_WORDS (src)[0]; - - /* Short circuit common case. */ - if (!word) - return 0; - - size = SBITSET_N_BITS (src); - bitno = *next; - if (bitno >= size) - return 0; - - word >>= bitno; - - /* If num is 1, we could speed things up with a binary search - of the word of interest. */ - - if (num >= BITSET_WORD_BITS) - { - for (count = 0; word; bitno++) - { - if (word & 1) - 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; -} - - -/* Set bit BITNO in bitset DST. */ -static void -sbitset_set (dst, bitno) - bitset dst ATTRIBUTE_UNUSED; - bitset_bindex bitno ATTRIBUTE_UNUSED; -{ - /* This should never occur for sbitsets. */ - abort (); -} - - -/* Reset bit BITNO in bitset DST. */ -static void -sbitset_reset (dst, bitno) - bitset dst ATTRIBUTE_UNUSED; - bitset_bindex bitno ATTRIBUTE_UNUSED; -{ - /* This should never occur for sbitsets. */ - abort (); -} - - -/* Test bit BITNO in bitset SRC. */ -static int -sbitset_test (src, bitno) - bitset src ATTRIBUTE_UNUSED; - bitset_bindex bitno ATTRIBUTE_UNUSED; -{ - /* This should never occur for sbitsets. */ - abort (); - return 0; -} - - -/* Find list of up to NUM bits set in BSET in reverse order, starting - from and including NEXT and store in array LIST. Return with - actual number of bits found and with *NEXT indicating where search - stopped. */ -static int -sbitset_reverse_list (src, list, num, next) - bitset src; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; -{ - bitset_bindex bitno; - bitset_bindex rbitno; - bitset_bindex count; - bitset_windex windex; - unsigned int bitcnt; - bitset_bindex bitoff; - bitset_word word; - bitset_word *srcp = SBITSET_WORDS (src); - bitset_bindex n_bits = SBITSET_N_BITS (src); - - rbitno = *next; - - /* If num is 1, we could speed things up with a binary search - of the word of interest. */ - - if (rbitno >= n_bits) - return 0; - - count = 0; - - bitno = n_bits - (rbitno + 1); - - windex = bitno / BITSET_WORD_BITS; - bitcnt = bitno % BITSET_WORD_BITS; - bitoff = windex * BITSET_WORD_BITS; - - for (; windex != ~0U; windex--, bitoff -= BITSET_WORD_BITS, - bitcnt = BITSET_WORD_BITS - 1) - { - word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); - for (; word; bitcnt--) - { - if (word & BITSET_MSB) - { - list[count++] = bitoff + bitcnt; - if (count >= num) - { - *next = n_bits - (bitoff + bitcnt); - return count; - } - } - word <<= 1; - } - } - - *next = n_bits - (bitoff + 1); - return count; -} - - -/* Find list of up to NUM bits set in BSET starting from and including - *NEXT and store in array LIST. Return with actual number of bits - found and with *NEXT indicating where search stopped. */ -static int -sbitset_list (src, list, num, next) - bitset src; - bitset_bindex *list; - bitset_bindex num; - bitset_bindex *next; -{ - bitset_bindex bitno; - bitset_bindex count; - bitset_windex windex; - bitset_bindex bitoff; - bitset_windex size = src->b.csize; - bitset_word *srcp = SBITSET_WORDS (src); - bitset_word word; - - bitno = *next; - - count = 0; - if (!bitno) - { - /* Many bitsets are zero, so make this common case fast. */ - for (windex = 0; windex < size && !srcp[windex]; windex++) - continue; - if (windex >= size) - return 0; - - /* If num is 1, we could speed things up with a binary search - of the current word. */ - - bitoff = windex * BITSET_WORD_BITS; - } - else - { - if (bitno >= SBITSET_N_BITS (src)) - return 0; - - windex = bitno / BITSET_WORD_BITS; - bitno = bitno % BITSET_WORD_BITS; - - if (bitno) - { - /* Handle the case where we start within a word. - Most often, this is executed with large bitsets - with many set bits where we filled the array - on the previous call to this function. */ - - bitoff = windex * BITSET_WORD_BITS; - word = srcp[windex] >> bitno; - for (bitno = bitoff + bitno; word; bitno++) - { - if (word & 1) - { - list[count++] = bitno; - if (count >= num) - { - *next = bitno + 1; - return count; - } - } - word >>= 1; - } - windex++; - } - bitoff = windex * BITSET_WORD_BITS; - } - - for (; windex < size; windex++, bitoff += BITSET_WORD_BITS) - { - if (!(word = srcp[windex])) - continue; - - if ((count + BITSET_WORD_BITS) < num) - { - for (bitno = bitoff; word; bitno++) - { - if (word & 1) - list[count++] = bitno; - word >>= 1; - } - } - else - { - for (bitno = bitoff; word; bitno++) - { - if (word & 1) - { - list[count++] = bitno; - if (count >= num) - { - *next = bitno + 1; - return count; - } - } - word >>= 1; - } - } - } - - *next = bitoff; - return count; -} - - -/* Ensure that any unused bits within the last word are clear. */ -static inline void -sbitset_unused_clear (dst) - bitset dst; -{ - unsigned int last_bit; - - last_bit = SBITSET_N_BITS (dst) % BITSET_WORD_BITS; - if (last_bit) - SBITSET_WORDS (dst)[dst->b.csize - 1] &= - (bitset_word) ((1 << last_bit) - 1); -} - - -static int -sbitset_op1 (dst, op) - bitset dst; - enum bitset_ops op; -{ - unsigned int i; - bitset_word *dstp = SBITSET_WORDS (dst); - unsigned int bytes; - - bytes = sizeof (bitset_word) * dst->b.csize; - - switch (op) - { - case BITSET_OP_ZERO: - memset (dstp, 0, bytes); - break; - - case BITSET_OP_ONES: - memset (dstp, ~0, bytes); - sbitset_unused_clear (dst); - break; - - case BITSET_OP_EMPTY_P: - for (i = 0; i < dst->b.csize; i++) - if (dstp[i]) - return 0; - break; - - default: - abort (); - } - - return 1; -} - - -static int -sbitset_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_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: - if (srcp == dstp) - break; - memcpy (dstp, srcp, sizeof (bitset_word) * size); - break; - - case BITSET_OP_NOT: - for (i = 0; i < size; i++) - *dstp++ = ~(*srcp++); - sbitset_unused_clear (dst); - break; - - case BITSET_OP_EQUAL_P: - for (i = 0; i < size; i++) - if (*srcp++ != *dstp++) - return 0; - break; - - case BITSET_OP_SUBSET_P: - for (i = 0; i < size; i++, dstp++, srcp++) - 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 (); - } - - return 1; -} - - -static int -sbitset_op3 (dst, src1, src2, op) - bitset dst; - bitset src1; - bitset src2; - enum bitset_ops 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_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: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = *src1p++ | *src2p++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - case BITSET_OP_AND: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = *src1p++ & *src2p++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - case BITSET_OP_XOR: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = *src1p++ ^ *src2p++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - case BITSET_OP_ANDN: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = *src1p++ & ~(*src2p++); - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - default: - abort (); - } - - return changed; -} - - -static int -sbitset_op4 (dst, src1, src2, src3, op) - bitset dst; - bitset src1; - bitset src2; - bitset src3; - enum bitset_ops 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_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: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - case BITSET_OP_AND_OR: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - case BITSET_OP_ANDN_OR: - for (i = 0; i < size; i++, dstp++) - { - bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; - - if (*dstp != tmp) - { - changed = 1; - *dstp = tmp; - } - } - break; - - default: - abort (); - } - - return changed; -} - - -/* 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 -}; - - -/* 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 -}; - - -int -sbitset_bytes (n_bits) - bitset_bindex n_bits; -{ - unsigned int bytes, size; - - size = SBITSET_N_WORDS (n_bits); - bytes = size * sizeof (bitset_word); - return sizeof (struct bitset_struct) + bytes - sizeof (bitset_word); -} - - -bitset -sbitset_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; - - /* 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; - else - bset->b.ops = &sbitset_ops; - - 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 deleted file mode 100644 index 01562c58..00000000 --- a/lib/sbitset.h +++ /dev/null @@ -1,28 +0,0 @@ -/* Functions to support sbitsets. - 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 _SBITSET_H -#define _SBITSET_H - -#include "bbitset.h" - -extern int sbitset_bytes PARAMS ((bitset_bindex)); - -extern bitset sbitset_init PARAMS ((bitset, bitset_bindex)); - -#endif 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, "]"); } }