src/relation.c

   1 /* Binary relations.
   2    Copyright (C) 2002  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., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21 #include "system.h"
  22 #include "bitsetv.h"
  23 #include "relation.h"
  24 #include "getargs.h"
  25
  26 void
  27 relation_print (relation_t relation, size_t size, FILE *out)
  28 {
  29   unsigned i, j;
  30
  31   for (i = 0; i < size; ++i)
  32     {
  33       fprintf (out, "%3d: ", i);
  34       if (relation[i])
  35         for (j = 0; relation[i][j] != -1; ++j)
  36           fprintf (out, "%3d ", relation[i][j]);
  37       fputc ('\n', out);
  38     }
  39   fputc ('\n', out);
  40 }
  41
  42
  43 /*---------------------------------------------------------------.
  44 | digraph & traverse.                                            |
  45 |                                                                |
  46 | The following variables are used as common storage between the |
  47 | two.                                                           |
  48 `---------------------------------------------------------------*/
  49
  50 static relation_t R;
  51 static relation_nodes_t INDEX;
  52 static relation_nodes_t VERTICES;
  53 static int top;
  54 static int infinity;
  55 static bitsetv F;
  56
  57 static void
  58 traverse (int i)
  59 {
  60   int j;
  61   int height;
  62
  63   VERTICES[++top] = i;
  64   INDEX[i] = height = top;
  65
  66   if (R[i])
  67     for (j = 0; R[i][j] >= 0; ++j)
  68       {
  69         if (INDEX[R[i][j]] == 0)
  70           traverse (R[i][j]);
  71
  72         if (INDEX[i] > INDEX[R[i][j]])
  73           INDEX[i] = INDEX[R[i][j]];
  74
  75         bitset_or (F[i], F[i], F[R[i][j]]);
  76       }
  77
  78   if (INDEX[i] == height)
  79     for (;;)
  80       {
  81         j = VERTICES[top--];
  82         INDEX[j] = infinity;
  83
  84         if (i == j)
  85           break;
  86
  87         bitset_copy (F[j], F[i]);
  88       }
  89 }
  90
  91
  92 void
  93 relation_digraph (relation_t relation, size_t size,
  94                   bitsetv *function)
  95 {
  96   unsigned i;
  97
  98   infinity = size + 2;
  99   INDEX = XCALLOC (relation_node_t, size + 1);
 100   VERTICES = XCALLOC (relation_node_t, size + 1);
 101   top = 0;
 102
 103   R = relation;
 104   F = *function;
 105
 106   for (i = 0; i < size; i++)
 107     INDEX[i] = 0;
 108
 109   for (i = 0; i < size; i++)
 110     if (INDEX[i] == 0 && R[i])
 111       traverse (i);
 112
 113   XFREE (INDEX);
 114   XFREE (VERTICES);
 115
 116   *function = F;
 117 }
 118
 119
 120 /*-------------------------------------------.
 121 | Destructively transpose R_ARG, of size N.  |
 122 `-------------------------------------------*/
 123
 124 void
 125 relation_transpose (relation_t *R_arg, int n)
 126 {
 127   /* The result. */
 128   relation_t new_R = XCALLOC (relation_nodes_t, n);
 129   /* END_R[I] -- next entry of NEW_R[I]. */
 130   relation_t end_R = XCALLOC (relation_nodes_t, n);
 131   /* NEDGES[I] -- total size of NEW_R[I]. */
 132   int *nedges = XCALLOC (int, n);
 133   int i, j;
 134
 135   if (trace_flag & trace_sets)
 136     {
 137       fputs ("relation_transpose: input\n", stderr);
 138       relation_print (*R_arg, n, stderr);
 139     }
 140
 141   /* Count. */
 142   for (i = 0; i < n; i++)
 143     if ((*R_arg)[i])
 144       for (j = 0; (*R_arg)[i][j] >= 0; ++j)
 145         ++nedges[(*R_arg)[i][j]];
 146
 147   /* Allocate. */
 148   for (i = 0; i < n; i++)
 149     if (nedges[i] > 0)
 150       {
 151         relation_node_t *sp = XCALLOC (relation_node_t, nedges[i] + 1);
 152         sp[nedges[i]] = -1;
 153         new_R[i] = sp;
 154         end_R[i] = sp;
 155       }
 156
 157   /* Store. */
 158   for (i = 0; i < n; i++)
 159     if ((*R_arg)[i])
 160       for (j = 0; (*R_arg)[i][j] >= 0; ++j)
 161         {
 162           *end_R[(*R_arg)[i][j]] = i;
 163           ++end_R[(*R_arg)[i][j]];
 164         }
 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     XFREE ((*R_arg)[i]);
 172   free (*R_arg);
 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 }