* ro.po: New.
[bison.git] / 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
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 }