1 files changed, 115 insertions, 0 deletions
diff --git a/tools/bison++/warshall.cc b/tools/bison++/warshall.cc
new file mode 100644
index 000000000..576a3a4e9
--- /dev/null
+++ b/tools/bison++/warshall.cc
@@ -0,0 +1,115 @@
+/* Generate transitive closure of a matrix,
+   Copyright (C) 1984, 1989 Free Software Foundation, Inc.
+
+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 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.  */
+
+
+#include <stdio.h>
+#include "system.h"
+#include "machine.h"
+
+
+/* given n by n matrix of bits R, modify its contents
+   to be the transive closure of what was given.  */
+
+void
+TC(unsigned* R, int n)
+{
+  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)
+    {
+      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);
+    }
+}
+
+
+/* Reflexive Transitive Closure.  Same as TC
+   and then set all the bits on the diagonal of R.  */
+
+void
+RTC(unsigned* R, int n)
+{
+  register int rowsize;
+  register unsigned mask;
+  register unsigned *rp;
+  register unsigned *relend;
+
+  TC(R, n);
+
+  rowsize = WORDSIZE(n) * sizeof(unsigned);
+  relend = (unsigned *) ((char *) R + n*rowsize);
+
+  mask = 1;
+  rp = R;
+  while (rp < relend)
+    {
+      *rp |= mask;
+
+      mask <<= 1;
+      if (mask == 0)
+	{
+	  mask = 1;
+	  rp++;
+	}
+
+      rp = (unsigned *) ((char *) rp + rowsize);
+    }
+}