src/relation.c

   1 /* Binary relations.
   2    Copyright (C) 2002, 2004, 2005, 2009 Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    This program is free software: you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation, either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  18
  19 #include <config.h>
  20 #include "system.h"
  21
  22 #include <bitsetv.h>
  23
  24 #include "getargs.h"
  25 #include "relation.h"
  26
  27 void
  28 relation_print (relation r, relation_node size, FILE *out)
  29 {
  30   relation_node i;
  31   relation_node j;
  32
  33   for (i = 0; i < size; ++i)
  34     {
  35       fprintf (out, "%3lu: ", (unsigned long int) i);
  36       if (r[i])
  37         for (j = 0; r[i][j] != END_NODE; ++j)
  38           fprintf (out, "%3lu ", (unsigned long int) r[i][j]);
  39       fputc ('\n', out);
  40     }
  41   fputc ('\n', out);
  42 }
  43
  44
  45 /*---------------------------------------------------------------.
  46 | digraph & traverse.                                            |
  47 |                                                                |
  48 | The following variables are used as common storage between the |
  49 | two.                                                           |
  50 `---------------------------------------------------------------*/
  51
  52 static relation R;
  53 static relation_nodes INDEX;
  54 static relation_nodes VERTICES;
  55 static relation_node top;
  56 static relation_node infinity;
  57 static bitsetv F;
  58
  59 static void
  60 traverse (relation_node i)
  61 {
  62   relation_node j;
  63   relation_node height;
  64
  65   VERTICES[++top] = i;
  66   INDEX[i] = height = top;
  67
  68   if (R[i])
  69     for (j = 0; R[i][j] != END_NODE; ++j)
  70       {
  71         if (INDEX[R[i][j]] == 0)
  72           traverse (R[i][j]);
  73
  74         if (INDEX[i] > INDEX[R[i][j]])
  75           INDEX[i] = INDEX[R[i][j]];
  76
  77         bitset_or (F[i], F[i], F[R[i][j]]);
  78       }
  79
  80   if (INDEX[i] == height)
  81     for (;;)
  82       {
  83         j = VERTICES[top--];
  84         INDEX[j] = infinity;
  85
  86         if (i == j)
  87           break;
  88
  89         bitset_copy (F[j], F[i]);
  90       }
  91 }
  92
  93
  94 void
  95 relation_digraph (relation r, relation_node size, bitsetv *function)
  96 {
  97   relation_node i;
  98
  99   infinity = size + 2;
 100   INDEX = xcalloc (size + 1, sizeof *INDEX);
 101   VERTICES = xnmalloc (size + 1, sizeof *VERTICES);
 102   top = 0;
 103
 104   R = r;
 105   F = *function;
 106
 107   for (i = 0; i < size; i++)
 108     if (INDEX[i] == 0 && R[i])
 109       traverse (i);
 110
 111   free (INDEX);
 112   free (VERTICES);
 113
 114   *function = F;
 115 }
 116
 117
 118 /*-------------------------------------------.
 119 | Destructively transpose R_ARG, of size N.  |
 120 `-------------------------------------------*/
 121
 122 void
 123 relation_transpose (relation *R_arg, relation_node n)
 124 {
 125   relation r = *R_arg;
 126   /* The result. */
 127   relation new_R = xnmalloc (n, sizeof *new_R);
 128   /* END_R[I] -- next entry of NEW_R[I]. */
 129   relation end_R = xnmalloc (n, sizeof *end_R);
 130   /* NEDGES[I] -- total size of NEW_R[I]. */
 131   size_t *nedges = xcalloc (n, sizeof *nedges);
 132   relation_node i;
 133   relation_node j;
 134
 135   if (trace_flag & trace_sets)
 136     {
 137       fputs ("relation_transpose: input\n", stderr);
 138       relation_print (r, n, stderr);
 139     }
 140
 141   /* Count. */
 142   for (i = 0; i < n; i++)
 143     if (r[i])
 144       for (j = 0; r[i][j] != END_NODE; ++j)
 145         ++nedges[r[i][j]];
 146
 147   /* Allocate. */
 148   for (i = 0; i < n; i++)
 149     {
 150       relation_node *sp = NULL;
 151       if (nedges[i] > 0)
 152         {
 153           sp = xnmalloc (nedges[i] + 1, sizeof *sp);
 154           sp[nedges[i]] = END_NODE;
 155         }
 156       new_R[i] = sp;
 157       end_R[i] = sp;
 158     }
 159
 160   /* Store. */
 161   for (i = 0; i < n; i++)
 162     if (r[i])
 163       for (j = 0; r[i][j] != END_NODE; ++j)
 164         *end_R[r[i][j]]++ = i;
 165
 166   free (nedges);
 167   free (end_R);
 168
 169   /* Free the input: it is replaced with the result. */
 170   for (i = 0; i < n; i++)
 171     free (r[i]);
 172   free (r);
 173
 174   if (trace_flag & trace_sets)
 175     {
 176       fputs ("relation_transpose: output\n", stderr);
 177       relation_print (new_R, n, stderr);
 178     }
 179
 180   *R_arg = new_R;
 181 }