12-relation.patch

[Akim Demaille]

Index: ChangeLog
from  Akim Demaille  <address@hidden>
        * src/lalr.c (traverse, digraph, matrix_print, transpose): Move
        to...
        * src/relation.h, src/relation.c (traverse, relation_digraph)
        (relation_print, relation_transpose): New.
        
        
Index: src/Makefile.am
--- src/Makefile.am Fri, 28 Jun 2002 21:50:19 +0200 akim
+++ src/Makefile.am Sat, 29 Jun 2002 16:47:49 +0200 akim
@@ -55,6 +55,7 @@
        print_graph.c print_graph.h               \
        reader.c reader.h                         \
        reduce.c reduce.h                         \
+       relation.c relation.h                     \
        scan-gram.l                               \
        scan-skel.l                               \
        state.c state.h                           \
Index: src/lalr.c
--- src/lalr.c Sat, 29 Jun 2002 16:31:51 +0200 akim
+++ src/lalr.c Sat, 29 Jun 2002 18:38:00 +0200 akim
@@ -27,6 +27,7 @@
 #include "system.h"
 #include "bitset.h"
 #include "bitsetv.h"
+#include "relation.h"
 #include "quotearg.h"
 #include "symtab.h"
 #include "gram.h"
@@ -56,76 +57,6 @@
 static shorts **lookback;
 
 
-/*---------------------------------------------------------------.
-| digraph & traverse.                                            |
-|                                                                |
-| The following variables are used as common storage between the |
-| two.                                                           |
-`---------------------------------------------------------------*/
-
-static short **R;
-static short *INDEX;
-static short *VERTICES;
-static int top;
-static int infinity;
-
-static void
-traverse (int i)
-{
-  int j;
-  int height;
-
-  VERTICES[++top] = i;
-  INDEX[i] = height = top;
-
-  if (R[i])
-    for (j = 0; R[i][j] >= 0; ++j)
-      {
-       if (INDEX[R[i][j]] == 0)
-         traverse (R[i][j]);
-
-       if (INDEX[i] > INDEX[R[i][j]])
-         INDEX[i] = INDEX[R[i][j]];
-
-       bitset_or (F[i], F[i], F[R[i][j]]);
-      }
-
-  if (INDEX[i] == height)
-    for (;;)
-      {
-       j = VERTICES[top--];
-       INDEX[j] = infinity;
-
-       if (i == j)
-         break;
-
-       bitset_copy (F[j], F[i]);
-      }
-}
-
-
-static void
-digraph (short **relation)
-{
-  int i;
-
-  infinity = ngotos + 2;
-  INDEX = XCALLOC (short, ngotos + 1);
-  VERTICES = XCALLOC (short, ngotos + 1);
-  top = 0;
-
-  R = relation;
-
-  for (i = 0; i < ngotos; i++)
-    INDEX[i] = 0;
-
-  for (i = 0; i < ngotos; i++)
-    if (INDEX[i] == 0 && R[i])
-      traverse (i);
-
-  XFREE (INDEX);
-  XFREE (VERTICES);
-}
 
 
 static void
@@ -280,7 +211,7 @@
        }
     }
 
-  digraph (reads);
+  relation_digraph (reads, ngotos, &F);
 
   for (i = 0; i < ngotos; i++)
     XFREE (reads[i]);
@@ -309,91 +240,6 @@
 }
 
 
-static void
-matrix_print (FILE *out, short **matrix, int n)
-{
-  int i, j;
-
-  for (i = 0; i < n; ++i)
-    {
-      fprintf (out, "%3d: ", i);
-      if (matrix[i])
-       for (j = 0; matrix[i][j] != -1; ++j)
-         fprintf (out, "%3d ", matrix[i][j]);
-      fputc ('\n', out);
-    }
-  fputc ('\n', out);
-}
-
-/*-------------------------------------------------------------------.
-| Return the transpose of R_ARG, of size N.  Destroy R_ARG, as it is |
-| replaced with the result.                                          |
-|                                                                    |
-| R_ARG[I] is NULL or a -1 terminated list of numbers.               |
-|                                                                    |
-| RESULT[NUM] is NULL or the -1 terminated list of the I such as NUM |
-| is in R_ARG[I].                                                    |
-`-------------------------------------------------------------------*/
-
-static short **
-transpose (short **R_arg, int n)
-{
-  /* The result. */
-  short **new_R = XCALLOC (short *, n);
-  /* END_R[I] -- next entry of NEW_R[I]. */
-  short **end_R = XCALLOC (short *, n);
-  /* NEDGES[I] -- total size of NEW_R[I]. */
-  short *nedges = XCALLOC (short, n);
-  int i, j;
-
-  if (trace_flag)
-    {
-      fputs ("transpose: input\n", stderr);
-      matrix_print (stderr, R_arg, n);
-    }
-
-  /* Count. */
-  for (i = 0; i < n; i++)
-    if (R_arg[i])
-      for (j = 0; R_arg[i][j] >= 0; ++j)
-       ++nedges[R_arg[i][j]];
-
-  /* Allocate. */
-  for (i = 0; i < n; i++)
-    if (nedges[i] > 0)
-      {
-       short *sp = XCALLOC (short, nedges[i] + 1);
-       sp[nedges[i]] = -1;
-       new_R[i] = sp;
-       end_R[i] = sp;
-      }
-
-  /* Store. */
-  for (i = 0; i < n; i++)
-    if (R_arg[i])
-      for (j = 0; R_arg[i][j] >= 0; ++j)
-       {
-         *end_R[R_arg[i][j]] = i;
-         ++end_R[R_arg[i][j]];
-       }
-
-  free (nedges);
-  free (end_R);
-
-  /* Free the input: it is replaced with the result. */
-  for (i = 0; i < n; i++)
-    XFREE (R_arg[i]);
-  free (R_arg);
-
-  if (trace_flag)
-    {
-      fputs ("transpose: output\n", stderr);
-      matrix_print (stderr, new_R, n);
-    }
-
-  return new_R;
-}
-
 
 static void
 build_relations (void)
@@ -459,7 +305,7 @@
   XFREE (edge);
   XFREE (states1);
 
-  includes = transpose (includes, ngotos);
+  relation_transpose (&includes, ngotos);
 }
 
 
@@ -469,7 +315,7 @@
 {
   int i;
 
-  digraph (includes);
+  relation_digraph (includes, ngotos, &F);
 
   for (i = 0; i < ngotos; i++)
     XFREE (includes[i]);
Index: src/relation.h
--- src/relation.h Sat, 29 Jun 2002 19:00:59 +0200 akim
+++ src/relation.h Sat, 29 Jun 2002 18:59:41 +0200 akim
@@ -0,0 +1,50 @@
+/* Binary relations.
+   Copyright (C) 2002  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 RELATION_H_
+# define RELATION_H_
+
+/* Performing operations on graphs coded as list of adjacency.
+
+   If GRAPH is a relation_t, then GRAPH[Node] is a list of adjacent
+   nodes, ended with -1.  */
+
+typedef short relation_node_t;
+typedef relation_node_t *relation_nodes_t;
+typedef relation_nodes_t *relation_t;
+
+
+/* Report a RELATION that has SIZE vertices.  */
+void relation_print PARAMS ((relation_t relation, size_t size,
+                            FILE *out));
+
+/* Compute the transitive closure of the FUNCTION on the RELATION with
+   SIZE vertices.
+
+   If RELATION (NODE-1, NODE-2) then on exit FUNCTION[NODE-1] was
+   extended (unioned) with FUNCTION[NODE-2].  */
+void relation_digraph PARAMS ((relation_t relation, size_t size,
+                              bitsetv *function));
+
+/* Destructively transpose *R_ARG, of size N.  */
+void relation_transpose PARAMS ((relation_t *R_arg, int n));
+
+#endif /* ! RELATION_H_ */
Index: src/relation.c
--- src/relation.c Sat, 29 Jun 2002 19:00:59 +0200 akim
+++ src/relation.c Sat, 29 Jun 2002 18:59:49 +0200 akim
@@ -0,0 +1,181 @@
+/* Binary relations.
+   Copyright (C) 2002  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.  */
+
+#include "system.h"
+#include "bitsetv.h"
+#include "relation.h"
+#include "getargs.h"
+
+void
+relation_print (relation_t relation, size_t size, FILE *out)
+{
+  unsigned i, j;
+
+  for (i = 0; i < size; ++i)
+    {
+      fprintf (out, "%3d: ", i);
+      if (relation[i])
+       for (j = 0; relation[i][j] != -1; ++j)
+         fprintf (out, "%3d ", relation[i][j]);
+      fputc ('\n', out);
+    }
+  fputc ('\n', out);
+}
+
+
+/*---------------------------------------------------------------.
+| digraph & traverse.                                            |
+|                                                                |
+| The following variables are used as common storage between the |
+| two.                                                           |
+`---------------------------------------------------------------*/
+
+static relation_t R;
+static relation_nodes_t INDEX;
+static relation_nodes_t VERTICES;
+static int top;
+static int infinity;
+static bitsetv F;
+
+static void
+traverse (int i)
+{
+  int j;
+  int height;
+
+  VERTICES[++top] = i;
+  INDEX[i] = height = top;
+
+  if (R[i])
+    for (j = 0; R[i][j] >= 0; ++j)
+      {
+       if (INDEX[R[i][j]] == 0)
+         traverse (R[i][j]);
+
+       if (INDEX[i] > INDEX[R[i][j]])
+         INDEX[i] = INDEX[R[i][j]];
+
+       bitset_or (F[i], F[i], F[R[i][j]]);
+      }
+
+  if (INDEX[i] == height)
+    for (;;)
+      {
+       j = VERTICES[top--];
+       INDEX[j] = infinity;
+
+       if (i == j)
+         break;
+
+       bitset_copy (F[j], F[i]);
+      }
+}
+
+
+void
+relation_digraph (relation_t relation, size_t size,
+                 bitsetv *function)
+{
+  unsigned i;
+
+  infinity = size + 2;
+  INDEX = XCALLOC (relation_node_t, size + 1);
+  VERTICES = XCALLOC (relation_node_t, size + 1);
+  top = 0;
+
+  R = relation;
+  F = *function;
+
+  for (i = 0; i < size; i++)
+    INDEX[i] = 0;
+
+  for (i = 0; i < size; i++)
+    if (INDEX[i] == 0 && R[i])
+      traverse (i);
+
+  XFREE (INDEX);
+  XFREE (VERTICES);
+
+  *function = F;
+}
+
+
+/*-------------------------------------------.
+| Destructively transpose R_ARG, of size N.  |
+`-------------------------------------------*/
+
+void
+relation_transpose (relation_t *R_arg, int n)
+{
+  /* The result. */
+  relation_t new_R = XCALLOC (relation_nodes_t, n);
+  /* END_R[I] -- next entry of NEW_R[I]. */
+  relation_t end_R = XCALLOC (relation_nodes_t, n);
+  /* NEDGES[I] -- total size of NEW_R[I]. */
+  int *nedges = XCALLOC (int, n);
+  int i, j;
+
+  if (trace_flag)
+    {
+      fputs ("relation_transpose: input\n", stderr);
+      relation_print (*R_arg, n, stderr);
+    }
+
+  /* Count. */
+  for (i = 0; i < n; i++)
+    if ((*R_arg)[i])
+      for (j = 0; (*R_arg)[i][j] >= 0; ++j)
+       ++nedges[(*R_arg)[i][j]];
+
+  /* Allocate. */
+  for (i = 0; i < n; i++)
+    if (nedges[i] > 0)
+      {
+       relation_node_t *sp = XCALLOC (relation_node_t, nedges[i] + 1);
+       sp[nedges[i]] = -1;
+       new_R[i] = sp;
+       end_R[i] = sp;
+      }
+
+  /* Store. */
+  for (i = 0; i < n; i++)
+    if ((*R_arg)[i])
+      for (j = 0; (*R_arg)[i][j] >= 0; ++j)
+       {
+         *end_R[(*R_arg)[i][j]] = i;
+         ++end_R[(*R_arg)[i][j]];
+       }
+
+  free (nedges);
+  free (end_R);
+
+  /* Free the input: it is replaced with the result. */
+  for (i = 0; i < n; i++)
+    XFREE ((*R_arg)[i]);
+  free (*R_arg);
+
+  if (trace_flag)
+    {
+      fputs ("relation_transpose: output\n", stderr);
+      relation_print (new_R, n, stderr);
+    }
+
+  *R_arg = new_R;
+}