| 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 | |
| 23 | #include <bitsetv.h> |
| 24 | |
| 25 | #include "getargs.h" |
| 26 | #include "relation.h" |
| 27 | |
| 28 | void |
| 29 | relation_print (relation r, size_t size, FILE *out) |
| 30 | { |
| 31 | unsigned i, j; |
| 32 | |
| 33 | for (i = 0; i < size; ++i) |
| 34 | { |
| 35 | fprintf (out, "%3d: ", i); |
| 36 | if (r[i]) |
| 37 | for (j = 0; r[i][j] != -1; ++j) |
| 38 | fprintf (out, "%3d ", 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 int top; |
| 56 | static int infinity; |
| 57 | static bitsetv F; |
| 58 | |
| 59 | static void |
| 60 | traverse (int i) |
| 61 | { |
| 62 | int j; |
| 63 | int height; |
| 64 | |
| 65 | VERTICES[++top] = i; |
| 66 | INDEX[i] = height = top; |
| 67 | |
| 68 | if (R[i]) |
| 69 | for (j = 0; R[i][j] >= 0; ++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, size_t size, bitsetv *function) |
| 96 | { |
| 97 | unsigned i; |
| 98 | |
| 99 | infinity = size + 2; |
| 100 | CALLOC (INDEX, size + 1); |
| 101 | CALLOC (VERTICES, size + 1); |
| 102 | top = 0; |
| 103 | |
| 104 | R = r; |
| 105 | F = *function; |
| 106 | |
| 107 | for (i = 0; i < size; i++) |
| 108 | INDEX[i] = 0; |
| 109 | |
| 110 | for (i = 0; i < size; i++) |
| 111 | if (INDEX[i] == 0 && R[i]) |
| 112 | traverse (i); |
| 113 | |
| 114 | XFREE (INDEX); |
| 115 | XFREE (VERTICES); |
| 116 | |
| 117 | *function = F; |
| 118 | } |
| 119 | |
| 120 | |
| 121 | /*-------------------------------------------. |
| 122 | | Destructively transpose R_ARG, of size N. | |
| 123 | `-------------------------------------------*/ |
| 124 | |
| 125 | void |
| 126 | relation_transpose (relation *R_arg, int n) |
| 127 | { |
| 128 | /* The result. */ |
| 129 | relation new_R = CALLOC (new_R, n); |
| 130 | /* END_R[I] -- next entry of NEW_R[I]. */ |
| 131 | relation end_R = CALLOC (end_R, n); |
| 132 | /* NEDGES[I] -- total size of NEW_R[I]. */ |
| 133 | int *nedges = CALLOC (nedges, n); |
| 134 | int i, j; |
| 135 | |
| 136 | if (trace_flag & trace_sets) |
| 137 | { |
| 138 | fputs ("relation_transpose: input\n", stderr); |
| 139 | relation_print (*R_arg, n, stderr); |
| 140 | } |
| 141 | |
| 142 | /* Count. */ |
| 143 | for (i = 0; i < n; i++) |
| 144 | if ((*R_arg)[i]) |
| 145 | for (j = 0; (*R_arg)[i][j] >= 0; ++j) |
| 146 | ++nedges[(*R_arg)[i][j]]; |
| 147 | |
| 148 | /* Allocate. */ |
| 149 | for (i = 0; i < n; i++) |
| 150 | if (nedges[i] > 0) |
| 151 | { |
| 152 | relation_node *sp = CALLOC (sp, nedges[i] + 1); |
| 153 | sp[nedges[i]] = -1; |
| 154 | new_R[i] = sp; |
| 155 | end_R[i] = sp; |
| 156 | } |
| 157 | |
| 158 | /* Store. */ |
| 159 | for (i = 0; i < n; i++) |
| 160 | if ((*R_arg)[i]) |
| 161 | for (j = 0; (*R_arg)[i][j] >= 0; ++j) |
| 162 | { |
| 163 | *end_R[(*R_arg)[i][j]] = i; |
| 164 | ++end_R[(*R_arg)[i][j]]; |
| 165 | } |
| 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 | XFREE ((*R_arg)[i]); |
| 173 | free (*R_arg); |
| 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 | } |