[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Bitsets update
|
From: |
Akim Demaille |
|
Subject: |
Bitsets update |
|
Date: |
02 Jul 2002 13:45:59 +0200 |
|
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Honest Recruiter) |
Index: ChangeLog
from Akim Demaille <address@hidden>
* 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.
Index: lib/Makefile.am
===================================================================
RCS file: /cvsroot/bison/bison/lib/Makefile.am,v
retrieving revision 1.26
diff -u -u -r1.26 Makefile.am
--- lib/Makefile.am 25 May 2002 16:12:40 -0000 1.26
+++ lib/Makefile.am 2 Jul 2002 11:44:59 -0000
@@ -46,9 +46,10 @@
# 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 += \
Index: lib/abitset.c
===================================================================
RCS file: lib/abitset.c
diff -N lib/abitset.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lib/abitset.c 2 Jul 2002 11:44:59 -0000
@@ -0,0 +1,651 @@
+/* Array bitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+ 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 <stdlib.h>
+#include <string.h>
+
+/* This file implements fixed size bitsets stored as an array
+ of words. Any unused bits in the last word must be zero. */
+
+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;
+}
Index: lib/abitset.h
===================================================================
RCS file: lib/abitset.h
diff -N lib/abitset.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lib/abitset.h 2 Jul 2002 11:44:59 -0000
@@ -0,0 +1,28 @@
+/* Functions to support abitsets.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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
Index: lib/bbitset.h
===================================================================
RCS file: /cvsroot/bison/bison/lib/bbitset.h,v
retrieving revision 1.2
diff -u -u -r1.2 bbitset.h
--- lib/bbitset.h 4 Mar 2002 14:15:01 -0000 1.2
+++ lib/bbitset.h 2 Jul 2002 11:44:59 -0000
@@ -19,43 +19,7 @@
#ifndef _BBITSET_H
#define _BBITSET_H
-/* Bison modifications: BEGIN. */
-#define IN_BISON 1
-#if IN_BISON
-# if HAVE_CONFIG_H
-# include <config.h>
-# endif
-# include <stdlib.h>
-
-# define BITSET_STATS 1
-/* This file is the public interface to the bitset abstract data type.
- Only use the functions and macros defined in this file. */
-
-# ifndef PARAMS
-# if defined PROTOTYPES || (defined __STDC__ && __STDC__)
-# define PARAMS(Args) Args
-# else
-# define PARAMS(Args) ()
-# endif
-# endif
-
-# ifndef __attribute__
-# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
-# define __attribute__(x)
-# endif
-# endif
-
-# ifndef ATTRIBUTE_NORETURN
-# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
-# endif
-
-# ifndef ATTRIBUTE_UNUSED
-# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
-# endif
-# include "xalloc.h"
-#else /* ! IN_BISON */
-# include "libiberty.h"
-#endif
+#include "libiberty.h"
#ifdef HAVE_LIMITS_H
#include <limits.h>
@@ -64,25 +28,21 @@
/* 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 @@
#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 @@
#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 @@
#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 @@
#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 */
Index: lib/bitset-int.h
===================================================================
RCS file: lib/bitset-int.h
diff -N lib/bitset-int.h
--- lib/bitset-int.h 4 Mar 2002 11:58:52 -0000 1.1
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,112 +0,0 @@
-/* Internal bitset definitions.
- Copyright (C) 2002 Free Software Foundation, Inc.
- Contributed by Michael Hayes (address@hidden).
-
-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 <limits.h>
-#endif
-
-/* Currently we support three flavours of bitsets:
- BITSET_ARRAY: Array of bits (fixed size, faster).
- BITSET_LIST: Linked list of array of bits (variable size, least storage
- for large very sparse sets).
- BITSET_TABLE: Expandable table of pointers to array of bits
- (variable size, less storage for large sparse sets).
-*/
-enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM};
-#define BITSET__TYPE_NAMES {"sbitset", "lbitset", "ebitset"}
-
-/* Non-zero to enable bitset caching. */
-#define BITSET_CACHE 1
-
-/* Non-zero to use inline functions instead of macros. */
-#define BITSET_INLINE 0
-
-/* Non-zero to enable bitset statistics gathering. */
-#define BITSET_STATS 1
-
-/* Non-zero to enable bitset type checking. */
-#define BITSET_CHECK 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 */
Index: lib/bitset.c
===================================================================
RCS file: /cvsroot/bison/bison/lib/bitset.c,v
retrieving revision 1.3
diff -u -u -r1.3 bitset.c
--- lib/bitset.c 4 Mar 2002 14:15:01 -0000 1.3
+++ lib/bitset.c 2 Jul 2002 11:44:59 -0000
@@ -22,105 +22,14 @@
#include <stdlib.h>
#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 @@
{
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_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 @@
{
enum bitset_type type;
-#if BITSET_CHECK
/* Check attributes. */
if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
abort ();
@@ -196,7 +110,6 @@
/* Note that sometimes we will be asked for a zero length
fixed size bitset. */
-#endif
/* Choose the type of bitset. */
@@ -222,14 +135,12 @@
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 @@
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 @@
bitset_free (bset)
bitset bset;
{
- BITSET_STATS_XFREES_INC (bset);
-
BITSET_FREE_ (bset);
free (bset);
}
@@ -289,12 +196,25 @@
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 @@
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 @@
fprintf (file, "%d ", i);
pos += 1 + (i >= 10) + (i >= 100);
- });
+ };
if (verbose)
fprintf (file, "}\n");
@@ -418,6 +339,7 @@
bitset src;
{
unsigned int i;
+ bitset_iterator iter;
if (BITSET_COMPATIBLE_ (dst, src))
return BITSET_COPY_ (dst, src);
@@ -425,10 +347,10 @@
/* 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 @@
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 dst;
bitset src;
{
- BITSET_CHECK2_ (dst, src);
return BITSET_SUBSET_P_ (dst, src);
}
@@ -506,7 +431,6 @@
bitset dst;
bitset src;
{
- BITSET_CHECK2_ (dst, src);
return BITSET_EQUAL_P_ (dst, src);
}
@@ -517,7 +441,6 @@
bitset dst;
bitset src;
{
- BITSET_CHECK2_ (dst, src);
return BITSET_DISJOINT_P_ (dst, src);
}
@@ -528,7 +451,6 @@
bitset dst;
bitset src;
{
- BITSET_CHECK2_ (dst, src);
return BITSET_NOT_ (dst, src);
}
@@ -540,7 +462,6 @@
bitset src1;
bitset src2;
{
- BITSET_CHECK3_ (dst, src1, src2);
return BITSET_OR_ (dst, src1, src2);
}
@@ -552,7 +473,6 @@
bitset src1;
bitset src2;
{
- BITSET_CHECK3_ (dst, src1, src2);
return BITSET_AND_ (dst, src1, src2);
}
@@ -564,7 +484,6 @@
bitset src1;
bitset src2;
{
- BITSET_CHECK3_ (dst, src1, src2);
return BITSET_XOR_ (dst, src1, src2);
}
@@ -576,11 +495,12 @@
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 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 src2;
bitset src3;
{
- BITSET_CHECK4_ (dst, src1, src2, src3);
return BITSET_OR_AND_ (dst, src1, src2, src3);
}
@@ -644,7 +563,6 @@
bitset src2;
bitset src3;
{
- BITSET_CHECK4_ (dst, src1, src2, src3);
return BITSET_AND_OR_ (dst, src1, src2, src3);
}
@@ -658,7 +576,6 @@
bitset src2;
bitset src3;
{
- BITSET_CHECK4_ (dst, src1, src2, src3);
return BITSET_ANDN_OR_ (dst, src1, src2, src3);
}
@@ -689,248 +606,4 @@
{
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 */
}
Index: lib/bitset.h
===================================================================
RCS file: /cvsroot/bison/bison/lib/bitset.h,v
retrieving revision 1.3
diff -u -u -r1.3 bitset.h
--- lib/bitset.h 4 Mar 2002 14:15:01 -0000 1.3
+++ lib/bitset.h 2 Jul 2002 11:44:59 -0000
@@ -17,7 +17,7 @@
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 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 @@
/* 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 @@
{
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 @@
{
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 @@
{
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 @@
}
#endif
-#if BITSET_CACHE && ! BITSET_INLINE
+#if ! BITSET_INLINE
/* Set bit BITNO in bitset BSET. */
#define bitset_set(bset, bitno) \
@@ -168,16 +183,6 @@
: (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 @@
/* 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 @@
/* 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_stats PARAMS ((void));
#endif /* _BITSET_H */
+
Index: lib/bitset_stats.c
===================================================================
RCS file: lib/bitset_stats.c
diff -N lib/bitset_stats.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lib/bitset_stats.c 2 Jul 2002 11:44:59 -0000
@@ -0,0 +1,627 @@
+/* Bitset statistics.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+ 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 <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+
+/* 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;
+}
Index: lib/bitset_stats.h
===================================================================
RCS file: lib/bitset_stats.h
diff -N lib/bitset_stats.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lib/bitset_stats.h 2 Jul 2002 11:44:59 -0000
@@ -0,0 +1,33 @@
+/* Functions to support bitset statistics.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Michael Hayes (address@hidden).
+
+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
Index: lib/bitsetv.c
===================================================================
RCS file: /cvsroot/bison/bison/lib/bitsetv.c,v
retrieving revision 1.3
diff -u -u -r1.3 bitsetv.c
--- lib/bitsetv.c 4 Mar 2002 14:15:01 -0000 1.3
+++ lib/bitsetv.c 2 Jul 2002 11:44:59 -0000
@@ -49,7 +49,7 @@
for (i = 0; i < n_vecs; i++)
{
bsetv[i] = (bitset) ((char *) bsetv + vector_bytes + i * bytes);
-
+
bitset_init (bsetv[i], n_bits, type);
}
Index: lib/ebitset.c
===================================================================
RCS file: /cvsroot/bison/bison/lib/ebitset.c,v
retrieving revision 1.3
diff -u -u -r1.3 ebitset.c
--- lib/ebitset.c 4 Mar 2002 14:15:01 -0000 1.3
+++ lib/ebitset.c 2 Jul 2002 11:44:59 -0000
@@ -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 @@
}
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 @@
}
-/* Allocate a ebitset element. The bits are not cleared. */
+/* Allocate a ebitset element. The bits are cleared. */
static inline ebitset_elt *
ebitset_elt_calloc ()
{
Index: lib/ebitset.h
===================================================================
RCS file: /cvsroot/bison/bison/lib/ebitset.h,v
retrieving revision 1.2
diff -u -u -r1.2 ebitset.h
--- lib/ebitset.h 4 Mar 2002 12:07:08 -0000 1.2
+++ lib/ebitset.h 2 Jul 2002 11:44:59 -0000
@@ -17,7 +17,7 @@
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
#ifndef _EBITSET_H
-#define _EBITSET_H
+#define _EBITSET_H
#include "bbitset.h"
Index: lib/lbitset.c
===================================================================
RCS file: /cvsroot/bison/bison/lib/lbitset.c,v
retrieving revision 1.3
diff -u -u -r1.3 lbitset.c
--- lib/lbitset.c 4 Mar 2002 14:15:01 -0000 1.3
+++ lib/lbitset.c 2 Jul 2002 11:44:59 -0000
@@ -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 @@
}
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 @@
}
-/* Allocate a lbitset element. The bits are not cleared. */
+/* Allocate a lbitset element. The bits are cleared. */
static inline lbitset_elt *
lbitset_elt_calloc ()
{
Index: lib/lbitset.h
===================================================================
RCS file: /cvsroot/bison/bison/lib/lbitset.h,v
retrieving revision 1.2
diff -u -u -r1.2 lbitset.h
--- lib/lbitset.h 4 Mar 2002 12:07:08 -0000 1.2
+++ lib/lbitset.h 2 Jul 2002 11:44:59 -0000
@@ -17,7 +17,7 @@
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
#ifndef _LBITSET_H
-#define _LBITSET_H
+#define _LBITSET_H
#include "bbitset.h"
Index: lib/libiberty.h
===================================================================
RCS file: lib/libiberty.h
diff -N lib/libiberty.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lib/libiberty.h 2 Jul 2002 11:44:59 -0000
@@ -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 <config.h>
+# endif
+# include <stdlib.h>
+
+/* 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_ */
Index: lib/sbitset.c
===================================================================
RCS file: lib/sbitset.c
diff -N lib/sbitset.c
--- lib/sbitset.c 4 Mar 2002 14:15:01 -0000 1.3
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,672 +0,0 @@
-/* Simple bitsets.
- Copyright (C) 2002 Free Software Foundation, Inc.
- Contributed by Michael Hayes (address@hidden).
-
- 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 <stdlib.h>
-#include <string.h>
-
-/* This file implements fixed size bitsets stored as an array
- of words. Any unused bits in the last word must be zero. */
-
-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;
-}
Index: lib/sbitset.h
===================================================================
RCS file: lib/sbitset.h
diff -N lib/sbitset.h
--- lib/sbitset.h 4 Mar 2002 12:07:08 -0000 1.2
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,28 +0,0 @@
-/* Functions to support sbitsets.
- Copyright (C) 2002 Free Software Foundation, Inc.
- Contributed by Michael Hayes (address@hidden).
-
-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
Index: src/closure.c
===================================================================
RCS file: /cvsroot/bison/bison/src/closure.c,v
retrieving revision 1.57
diff -u -u -r1.57 closure.c
--- src/closure.c 30 Jun 2002 17:34:52 -0000 1.57
+++ src/closure.c 2 Jul 2002 11:44:59 -0000
@@ -74,12 +74,13 @@
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 @@
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 @@
/* A bit index over RULESET. */
rule_number_t ruleno;
+ bitset_iterator iter;
+
if (trace_flag)
print_closure ("input", core, n);
@@ -209,18 +213,18 @@
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)
{
Index: src/lalr.c
===================================================================
RCS file: /cvsroot/bison/bison/src/lalr.c,v
retrieving revision 1.81
diff -u -u -r1.81 lalr.c
--- src/lalr.c 30 Jun 2002 17:34:52 -0000 1.81
+++ src/lalr.c 2 Jul 2002 11:44:59 -0000
@@ -420,16 +420,18 @@
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");
}
Index: src/main.c
===================================================================
RCS file: /cvsroot/bison/bison/src/main.c,v
retrieving revision 1.58
diff -u -u -r1.58 main.c
--- src/main.c 30 Jun 2002 17:29:36 -0000 1.58
+++ src/main.c 2 Jul 2002 11:44:59 -0000
@@ -21,6 +21,7 @@
#include "system.h"
+#include "bitset_stats.h"
#include "bitset.h"
#include "getargs.h"
#include "symtab.h"
@@ -50,11 +51,12 @@
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
@@ -121,6 +123,9 @@
#if C_ALLOCA
alloca (0);
#endif
+
+ if (trace_flag)
+ bitset_stats_dump (stderr);
return complain_message_count ? EXIT_FAILURE : EXIT_SUCCESS;
}
Index: src/output.c
===================================================================
RCS file: /cvsroot/bison/bison/src/output.c,v
retrieving revision 1.181
diff -u -u -r1.181 output.c
--- src/output.c 30 Jun 2002 17:34:52 -0000 1.181
+++ src/output.c 2 Jul 2002 11:44:59 -0000
@@ -442,19 +442,20 @@
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
Index: src/print_graph.c
===================================================================
RCS file: /cvsroot/bison/bison/src/print_graph.c,v
retrieving revision 1.46
diff -u -u -r1.46 print_graph.c
--- src/print_graph.c 30 Jun 2002 17:34:52 -0000 1.46
+++ src/print_graph.c 2 Jul 2002 11:44:59 -0000
@@ -90,26 +90,24 @@
&& 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, "]");
}
}
Index: src/state.c
===================================================================
RCS file: /cvsroot/bison/bison/src/state.c,v
retrieving revision 1.16
diff -u -u -r1.16 state.c
--- src/state.c 30 Jun 2002 17:34:52 -0000 1.16
+++ src/state.c 2 Jul 2002 11:44:59 -0000
@@ -195,27 +195,24 @@
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, "]");
}
}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- Bitsets update,
Akim Demaille <=