/* Generate transitive closure of a matrix,
- Copyright (C) 1984, 1989 Free Software Foundation, Inc.
+ Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
-This file is part of Bison, the GNU Compiler Compiler.
+ This file is part of Bison, the GNU Compiler Compiler.
-Bison 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.
+ Bison 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.
-Bison 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.
+ Bison 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 Bison; see the file COPYING. If not, write to
-the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+ You should have received a copy of the GNU General Public License
+ along with Bison; see the file COPYING. If not, write to
+ the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
-#include <stdio.h>
#include "system.h"
-#include "machine.h"
+#include "getargs.h"
+#include "warshall.h"
-void RTC PARAMS((unsigned *, int));
-
-
-/* given n by n matrix of bits R, modify its contents
- to be the transive closure of what was given. */
+/*-------------------------------------------------------------.
+| Given n by n matrix of bits R, modify its contents to be the |
+| transive closure of what was given. |
+`-------------------------------------------------------------*/
static void
-TC (unsigned *R, int n)
+bitmatrix_print (const char *title, unsigned *matrix, size_t size)
{
- register int rowsize;
- register unsigned mask;
- register unsigned *rowj;
- register unsigned *rp;
- register unsigned *rend;
- register unsigned *ccol;
-
- unsigned *relend;
- unsigned *cword;
- unsigned *rowi;
-
- rowsize = WORDSIZE(n) * sizeof(unsigned);
- relend = (unsigned *) ((char *) R + (n * rowsize));
-
- cword = R;
- mask = 1;
- rowi = R;
- while (rowi < relend)
+ 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);
+
+ /* Column numbers. */
+ fputs (" ", stderr);
+ for (i = 0; i < size; ++i)
+ putc (i / 10 ? '0' + i / 10 : ' ', stderr);
+ putc ('\n', stderr);
+ fputs (" ", stderr);
+ for (i = 0; i < size; ++i)
+ fprintf (stderr, "%d", i % 10);
+ putc ('\n', stderr);
+
+ /* Bar. */
+ fputs (" +", stderr);
+ for (i = 0; i < size; ++i)
+ putc ('-', stderr);
+ fputs ("+\n", stderr);
+
+ /* Contents. */
+ for (i = 0; i < size; ++i)
{
- ccol = cword;
- rowj = R;
-
- while (rowj < relend)
- {
- if (*ccol & mask)
- {
- rp = rowi;
- rend = (unsigned *) ((char *) rowj + rowsize);
-
- while (rowj < rend)
- *rowj++ |= *rp++;
- }
- else
- {
- rowj = (unsigned *) ((char *) rowj + rowsize);
- }
-
- ccol = (unsigned *) ((char *) ccol + rowsize);
- }
-
- mask <<= 1;
- if (mask == 0)
- {
- mask = 1;
- cword++;
- }
-
- rowi = (unsigned *) ((char *) rowi + rowsize);
+ fprintf (stderr, "%2d|", i);
+ for (j = 0; j < size; ++j)
+ fputs (BITISSET (ROW (i), j) ? "1" : " ", stderr);
+ fputs ("|\n", stderr);
}
-}
+ /* Bar. */
+ fputs (" +", stderr);
+ for (i = 0; i < size; ++i)
+ putc ('-', stderr);
+ fputs ("+\n", stderr);
+
+ /* End title. */
+ fprintf (stderr, "%s END\n\n", title);
+}
-/* Reflexive Transitive Closure. Same as TC
- and then set all the bits on the diagonal of R. */
+#define R(Num) (unsigned *) ((char *) R + ((Num) * rowsize))
-void
-RTC (unsigned *R, int n)
+static void
+TC (unsigned *R, int n)
{
- register int rowsize;
- register unsigned mask;
- register unsigned *rp;
- register unsigned *relend;
+ int rowsize = WORDSIZE (n) * sizeof (unsigned);
+ int i, j, k;
- TC(R, n);
+ if (trace_flag)
+ bitmatrix_print ("TC: Input", R, n);
- rowsize = WORDSIZE(n) * sizeof(unsigned);
- relend = (unsigned *) ((char *) R + n*rowsize);
+ /* R (J, I) && R (I, K) => R (J, K).
+ I *must* be the outter loop. */
- mask = 1;
- rp = R;
- while (rp < relend)
- {
- *rp |= mask;
+ for (i = 0; i < n; ++i)
+ for (j = 0; j < n; ++j)
+ if (BITISSET (R (j), i))
+ for (k = 0; k < n; ++k)
+ if (BITISSET (R (i), k))
+ SETBIT (R (j), k);
- mask <<= 1;
- if (mask == 0)
- {
- mask = 1;
- rp++;
- }
+ if (trace_flag)
+ bitmatrix_print ("TC: Output", R, n);
+}
- rp = (unsigned *) ((char *) rp + rowsize);
- }
+
+/*---------------------------------------------------------------.
+| Reflexive Transitive Closure. Same as TC and then set all the |
+| bits on the diagonal of R. |
+`---------------------------------------------------------------*/
+
+void
+RTC (unsigned *R, int n)
+{
+ int rowsize = WORDSIZE (n) * sizeof (unsigned);
+ int i;
+
+ TC (R, n);
+ for (i = 0; i < n; ++i)
+ SETBIT (R (i), i);
}
projects / bison.git / blobdiff