From d8a0245ce78f1c5bfaae6bf60732251e519a78df Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Mon, 4 Mar 2002 12:03:01 +0000 Subject: [PATCH] * src/closure.c (firsts): Now, also a bitset. Adjust all dependencies. (varsetsize): Remove, now unused. * src/warshall.h, src/warshall.c: Now work on arrays of bitsets. --- ChangeLog | 7 ++++++ src/closure.c | 61 +++++++++++++++++++++++++------------------------- src/warshall.c | 43 +++++++++++++++++------------------ src/warshall.h | 4 ++-- 4 files changed, 60 insertions(+), 55 deletions(-) diff --git a/ChangeLog b/ChangeLog index 6632ec3e..873e6f4a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2002-03-04 Akim Demaille + + * src/closure.c (firsts): Now, also a bitset. + Adjust all dependencies. + (varsetsize): Remove, now unused. + * src/warshall.h, src/warshall.c: Now work on arrays of bitsets. + 2002-03-04 Akim Demaille * src/print.c: Convert to use bitset.h, not hand coded iterations diff --git a/src/closure.c b/src/closure.c index 03222cac..ab745b8d 100644 --- a/src/closure.c +++ b/src/closure.c @@ -25,8 +25,8 @@ #include "reader.h" #include "closure.h" #include "derives.h" -#include "warshall.h" #include "bitset.h" +#include "warshall.h" /* NITEMSET is the size of the array ITEMSET. */ short *itemset; @@ -35,15 +35,12 @@ int nitemset; static bitset ruleset; /* internal data. See comments before set_fderives and set_firsts. */ -static bitset *fderives; -static unsigned int *firsts; +static bitset *fderives = NULL; +static bitset *firsts = NULL; /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var. */ #define FDERIVES(Var) fderives[(Var) - ntokens] -#define FIRSTS(Var) (firsts + ((Var) - ntokens) * varsetsize) - -/* number of words required to hold a bit for each variable */ -static int varsetsize; +#define FIRSTS(Var) firsts[(Var) - ntokens] /*-----------------. @@ -77,7 +74,7 @@ print_firsts (void) { fprintf (stderr, "\t%s firsts\n", symbols[i]->tag); for (j = 0; j < nvars; j++) - if (BITISSET (FIRSTS (i), j)) + if (bitset_test (FIRSTS (i), j)) fprintf (stderr, "\t\t%d (%s)\n", j + ntokens, symbols[j + ntokens]->tag); } @@ -88,11 +85,9 @@ print_firsts (void) static void print_fderives (void) { - int i; - int j; + int i, j; fprintf (stderr, "FDERIVES\n"); - for (i = ntokens; i < nsyms; i++) { fprintf (stderr, "\t%s derives\n", symbols[i]->tag); @@ -109,32 +104,34 @@ print_fderives (void) fprintf (stderr, "\n\n"); } -/*-------------------------------------------------------------------. -| Set FIRSTS to be an NVARS by NVARS bit matrix indicating which | -| items can represent the beginning of the input corresponding to | -| which other items. | -| | -| For example, if some rule expands symbol 5 into the sequence of | -| symbols 8 3 20, the symbol 8 can be the beginning of the data for | -| symbol 5, so the bit [8 - ntokens, 5 - ntokens] in firsts is set. | -`-------------------------------------------------------------------*/ +/*------------------------------------------------------------------. +| Set FIRSTS to be an NVARS array of NVARS bitsets indicating which | +| items can represent the beginning of the input corresponding to | +| which other items. | +| | +| For example, if some rule expands symbol 5 into the sequence of | +| symbols 8 3 20, the symbol 8 can be the beginning of the data for | +| symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST | +| (5)) is set. | +`------------------------------------------------------------------*/ static void set_firsts (void) { int i, j; - varsetsize = WORDSIZE (nvars); - - firsts = XCALLOC (unsigned, nvars * varsetsize); - + firsts = XCALLOC (bitset, nvars); for (i = ntokens; i < nsyms; i++) - for (j = 0; derives[i][j] >= 0; ++j) - { - int symbol = ritem[rules[derives[i][j]].rhs]; - if (ISVAR (symbol)) - SETBIT (FIRSTS (i), symbol - ntokens); - } + { + FIRSTS (i) = bitset_create (nvars, BITSET_FIXED); + bitset_zero (FIRSTS (i)); + for (j = 0; derives[i][j] >= 0; ++j) + { + int symbol = ritem[rules[derives[i][j]].rhs]; + if (ISVAR (symbol)) + bitset_set (FIRSTS (i), symbol - ntokens); + } + } RTC (firsts, nvars); @@ -169,13 +166,15 @@ set_fderives (void) for (i = ntokens; i < nsyms; ++i) for (j = ntokens; j < nsyms; ++j) - if (BITISSET (FIRSTS (i), j - ntokens)) + if (bitset_test (FIRSTS (i), j - ntokens)) for (k = 0; derives[j][k] > 0; ++k) bitset_set (FDERIVES (i), derives[j][k]); if (trace_flag) print_fderives (); + for (i = ntokens; i < nsyms; ++i) + bitset_free (FIRSTS (i)); XFREE (firsts); } diff --git a/src/warshall.c b/src/warshall.c index 523d42ae..ff41d5ba 100644 --- a/src/warshall.c +++ b/src/warshall.c @@ -1,5 +1,5 @@ /* Generate transitive closure of a matrix, - Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc. + Copyright 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -21,19 +21,17 @@ #include "system.h" #include "getargs.h" +#include "bitset.h" #include "warshall.h" -/*-------------------------------------------------------------. -| Given n by n matrix of bits R, modify its contents to be the | -| transive closure of what was given. | -`-------------------------------------------------------------*/ +/*--------------------------------------------------------. +| Display the MATRIX array of SIZE bitsets of size SIZE. | +`--------------------------------------------------------*/ static void -bitmatrix_print (const char *title, unsigned *matrix, size_t size) +bitmatrix_print (const char *title, bitset *matrix, size_t size) { size_t i, j; - size_t rowsize = WORDSIZE (size) * sizeof (unsigned); -#define ROW(Num) ((unsigned *) ((char *) matrix + ((Num) * rowsize))) /* Title. */ fprintf (stderr, "%s BEGIN\n", title); @@ -59,7 +57,7 @@ bitmatrix_print (const char *title, unsigned *matrix, size_t size) { fprintf (stderr, "%2d|", i); for (j = 0; j < size; ++j) - fputs (BITISSET (ROW (i), j) ? "1" : " ", stderr); + fputs (bitset_test (matrix[i], j) ? "1" : " ", stderr); fputs ("|\n", stderr); } @@ -73,44 +71,45 @@ bitmatrix_print (const char *title, unsigned *matrix, size_t size) fprintf (stderr, "%s END\n\n", title); } -#define R(Num) (unsigned *) ((char *) R + ((Num) * rowsize)) +/*-------------------------------------------------------------------. +| Given the MATRIX array of N bitsets of size N, modify its contents | +| to be the transive closure of what was given. | +`-------------------------------------------------------------------*/ static void -TC (unsigned *R, int n) +TC (bitset *matrix, int n) { - int rowsize = WORDSIZE (n) * sizeof (unsigned); int i, j, k; if (trace_flag) - bitmatrix_print ("TC: Input", R, n); + bitmatrix_print ("TC: Input", matrix, n); /* R (J, I) && R (I, K) => R (J, K). I *must* be the outter loop. */ for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) - if (BITISSET (R (j), i)) + if (bitset_test (matrix[j], i)) for (k = 0; k < n; ++k) - if (BITISSET (R (i), k)) - SETBIT (R (j), k); + if (bitset_test (matrix[i], k)) + bitset_set (matrix[j], k); if (trace_flag) - bitmatrix_print ("TC: Output", R, n); + bitmatrix_print ("TC: Output", matrix, n); } /*---------------------------------------------------------------. | Reflexive Transitive Closure. Same as TC and then set all the | -| bits on the diagonal of R. | +| bits on the diagonal of MATRIX. | `---------------------------------------------------------------*/ void -RTC (unsigned *R, int n) +RTC (bitset *matrix, int n) { - int rowsize = WORDSIZE (n) * sizeof (unsigned); int i; - TC (R, n); + TC (matrix, n); for (i = 0; i < n; ++i) - SETBIT (R (i), i); + bitset_set (matrix[i], i); } diff --git a/src/warshall.h b/src/warshall.h index ed3aeaf6..15d8c800 100644 --- a/src/warshall.h +++ b/src/warshall.h @@ -1,5 +1,5 @@ /* Generate transitive closure of a matrix, - Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc. + Copyright 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -21,5 +21,5 @@ #ifndef WARSHALL_H_ # define WARSHALL_H_ -void RTC PARAMS ((unsigned *, int)); +void RTC PARAMS ((bitset *, int)); #endif /* !WARSHALL_H_ */ -- 2.45.2