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