aboutsummaryrefslogtreecommitdiff
path: root/tools/bison++/warshall.cc
diff options
context:
space:
mode:
authormarha <marha@users.sourceforge.net>2010-11-19 13:18:48 +0000
committermarha <marha@users.sourceforge.net>2010-11-19 13:18:48 +0000
commit12f606ce06ef926f366a03079c5e3107c23f18af (patch)
tree28d7be4328bca9c31c1ab0f7cb5924c196be23a0 /tools/bison++/warshall.cc
parent773752eab55047c33bad0d88006bb69f5c601502 (diff)
downloadvcxsrv-12f606ce06ef926f366a03079c5e3107c23f18af.tar.gz
vcxsrv-12f606ce06ef926f366a03079c5e3107c23f18af.tar.bz2
vcxsrv-12f606ce06ef926f366a03079c5e3107c23f18af.zip
Added tool bison++-1.21.11
Diffstat (limited to 'tools/bison++/warshall.cc')
-rw-r--r--tools/bison++/warshall.cc115
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);
+ }
+}