* src/warshall.c (TC, RTC): De-obsfucate (source reduced to 22% of

what it was!).
* src/warshall.h: Remove accidental duplication of the content.

diff --git a/ChangeLog b/ChangeLog
index 1b041ea61bb94ae31e341612db452cf7f4ac17b2..10cfebb7662008ea195c2f207e97ea6fb878b948 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2001-12-05  Akim Demaille  <akim@epita.fr>
+
+       * src/warshall.c (TC, RTC): De-obsfucate (source reduced to 22% of
+       what it was!).
+       * src/warshall.h: Remove accidental duplication of the content.
+
+       
 2001-12-05  Akim Demaille  <akim@epita.fr>
 
        * src/closure.c (set_fderives): De-obfuscate.

diff --git a/src/warshall.c b/src/warshall.c
index 0d7af6ad78f580d9c46b4fcb0a81e53376c3b0b1..a9d579e663048ca9add44a52b7ae6af072eb5d39 100644 (file)
--- a/src/warshall.c
+++ b/src/warshall.c
@@ -1,5 +1,5 @@
 /* Generate transitive closure of a matrix,
-   Copyright 1984, 1989, 2000 Free Software Foundation, Inc.
+   Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -22,93 +22,40 @@
 #include "system.h"
 #include "warshall.h"
 
-/* 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.                          |
+`-------------------------------------------------------------*/
+
+#define R(Num) (unsigned *) ((char *) R + ((Num) * rowsize))
 
 static void
 TC (unsigned *R, int n)
 {
-  int rowsize;
-  unsigned mask;
-  unsigned *rowj;
-  unsigned *rp;
-  unsigned *rend;
-  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);
-    }
+  int rowsize = WORDSIZE (n) * sizeof (unsigned);
+  int i, j, k;
+
+  for (i = 0; i < n; ++i)
+    for (j = 0; j < n; ++j)
+      if (BITISSET (R (i), j))
+       for (k = 0; k < rowsize; ++k)
+         if (BITISSET (R (i), k))
+           SETBIT (R (j), k);
 }
 
 
-/* Reflexive Transitive Closure.  Same as TC
-   and then set all the bits on the diagonal of R.  */
+/*---------------------------------------------------------------.
+| 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;
-  unsigned mask;
-  unsigned *rp;
-  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++;
-       }
+  int rowsize = WORDSIZE (n) * sizeof (unsigned);
+  int i;
 
-      rp = (unsigned *) ((char *) rp + rowsize);
-    }
+  TC (R, n);
+  for (i = 0; i < n; ++i)
+    SETBIT (R (i), i);
 }

diff --git a/src/warshall.h b/src/warshall.h
index 80d56dde7fee0fb8072914778d7acfacb0434c8d..ed3aeaf600d5b926effd0a331411365b075a0df3 100644 (file)
--- a/src/warshall.h
+++ b/src/warshall.h
@@ -1,30 +1,5 @@
 /* Generate transitive closure of a matrix,
-   Copyright 1984, 1989, 2000 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, Inc., 59 Temple Place - Suite 330,
-   Boston, MA 02111-1307, USA.  */
-
-#ifndef WARSHALL_H_
-# define WARSHALL_H_
-
-void RTC PARAMS ((unsigned *, int));
-#endif /* !WARSHALL_H_ */
-/* Generate transitive closure of a matrix,
-   Copyright 1984, 1989, 2000 Free Software Foundation, Inc.
+   Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.