src/relation.c

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