OLD | NEW |
(Empty) | |
| 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 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 } |
OLD | NEW |