X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/d2729d44ab05f89e96d199ad6b10e127c1cb0a38..c25fb648819c95c1f190c07f2628e806c25dbf34:/src/warshall.c

diff --git a/src/warshall.c b/src/warshall.c
index dc2e3ac5..5963f472 100644
--- a/src/warshall.c
+++ b/src/warshall.c
@@ -1,117 +1,116 @@
 /* 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);
 }