Commit | Line | Data |
---|---|---|
c0bc4ef7 DF |
1 | /* |
2 | * Copyright (c) 1983 Regents of the University of California. | |
3 | * All rights reserved. The Berkeley software License Agreement | |
4 | * specifies the terms and conditions for redistribution. | |
5 | */ | |
6 | ||
4f1db472 | 7 | #ifndef lint |
c0bc4ef7 DF |
8 | static char sccsid[] = "@(#)dfn.c 5.1 (Berkeley) %G%"; |
9 | #endif not lint | |
4f1db472 PK |
10 | |
11 | #include <stdio.h> | |
31f0a970 | 12 | #include "gprof.h" |
4f1db472 PK |
13 | |
14 | #define DFN_DEPTH 100 | |
15 | struct dfnstruct { | |
16 | nltype *nlentryp; | |
17 | int cycletop; | |
18 | }; | |
19 | typedef struct dfnstruct dfntype; | |
20 | ||
21 | dfntype dfn_stack[ DFN_DEPTH ]; | |
22 | int dfn_depth = 0; | |
23 | ||
80ebf400 | 24 | int dfn_counter = DFN_NAN; |
4f1db472 PK |
25 | |
26 | /* | |
27 | * given this parent, depth first number its children. | |
28 | */ | |
29 | dfn( parentp ) | |
30 | nltype *parentp; | |
31 | { | |
32 | arctype *arcp; | |
33 | ||
34 | # ifdef DEBUG | |
35 | if ( debug & DFNDEBUG ) { | |
36 | printf( "[dfn] dfn(" ); | |
37 | printname( parentp ); | |
38 | printf( ")\n" ); | |
39 | } | |
40 | # endif DEBUG | |
41 | /* | |
42 | * if we're already numbered, no need to look any furthur. | |
43 | */ | |
44 | if ( dfn_numbered( parentp ) ) { | |
45 | return; | |
46 | } | |
47 | /* | |
48 | * if we're already busy, must be a cycle | |
49 | */ | |
50 | if ( dfn_busy( parentp ) ) { | |
51 | dfn_findcycle( parentp ); | |
52 | return; | |
53 | } | |
54 | /* | |
55 | * visit yourself before your children | |
56 | */ | |
57 | dfn_pre_visit( parentp ); | |
58 | /* | |
59 | * visit children | |
60 | */ | |
61 | for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { | |
62 | dfn( arcp -> arc_childp ); | |
63 | } | |
64 | /* | |
65 | * visit yourself after your children | |
66 | */ | |
67 | dfn_post_visit( parentp ); | |
68 | } | |
69 | ||
70 | /* | |
71 | * push a parent onto the stack and mark it busy | |
72 | */ | |
73 | dfn_pre_visit( parentp ) | |
74 | nltype *parentp; | |
75 | { | |
76 | ||
77 | dfn_depth += 1; | |
78 | if ( dfn_depth >= DFN_DEPTH ) { | |
79 | fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" ); | |
80 | exit( 1 ); | |
81 | } | |
82 | dfn_stack[ dfn_depth ].nlentryp = parentp; | |
83 | dfn_stack[ dfn_depth ].cycletop = dfn_depth; | |
84 | parentp -> toporder = DFN_BUSY; | |
85 | # ifdef DEBUG | |
86 | if ( debug & DFNDEBUG ) { | |
87 | printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth ); | |
88 | printname( parentp ); | |
89 | printf( "\n" ); | |
90 | } | |
91 | # endif DEBUG | |
92 | } | |
93 | ||
94 | /* | |
95 | * are we already numbered? | |
96 | */ | |
97 | bool | |
98 | dfn_numbered( childp ) | |
99 | nltype *childp; | |
100 | { | |
101 | ||
80ebf400 | 102 | return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY ); |
4f1db472 PK |
103 | } |
104 | ||
105 | /* | |
106 | * are we already busy? | |
107 | */ | |
108 | bool | |
109 | dfn_busy( childp ) | |
110 | nltype *childp; | |
111 | { | |
112 | ||
80ebf400 | 113 | if ( childp -> toporder == DFN_NAN ) { |
4f1db472 PK |
114 | return FALSE; |
115 | } | |
116 | return TRUE; | |
117 | } | |
118 | ||
119 | /* | |
120 | * MISSING: an explanation | |
121 | */ | |
122 | dfn_findcycle( childp ) | |
123 | nltype *childp; | |
124 | { | |
125 | int cycletop; | |
126 | nltype *cycleheadp; | |
127 | nltype *tailp; | |
128 | int index; | |
129 | ||
130 | for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) { | |
131 | cycleheadp = dfn_stack[ cycletop ].nlentryp; | |
132 | if ( childp == cycleheadp ) { | |
133 | break; | |
134 | } | |
135 | if ( childp -> cyclehead != childp && | |
136 | childp -> cyclehead == cycleheadp ) { | |
137 | break; | |
138 | } | |
139 | } | |
140 | if ( cycletop <= 0 ) { | |
141 | fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" ); | |
142 | exit( 1 ); | |
143 | } | |
144 | # ifdef DEBUG | |
145 | if ( debug & DFNDEBUG ) { | |
146 | printf( "[dfn_findcycle] dfn_depth %d cycletop %d " , | |
147 | dfn_depth , cycletop ); | |
148 | printname( cycleheadp ); | |
149 | printf( "\n" ); | |
150 | } | |
151 | # endif DEBUG | |
152 | if ( cycletop == dfn_depth ) { | |
153 | /* | |
154 | * this is previous function, e.g. this calls itself | |
155 | * sort of boring | |
156 | */ | |
157 | dfn_self_cycle( childp ); | |
158 | } else { | |
159 | /* | |
160 | * glom intervening functions that aren't already | |
161 | * glommed into this cycle. | |
162 | * things have been glommed when their cyclehead field | |
163 | * points to the head of the cycle they are glommed into. | |
164 | */ | |
165 | for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) { | |
166 | /* void: chase down to tail of things already glommed */ | |
167 | # ifdef DEBUG | |
168 | if ( debug & DFNDEBUG ) { | |
169 | printf( "[dfn_findcycle] tail " ); | |
170 | printname( tailp ); | |
171 | printf( "\n" ); | |
172 | } | |
173 | # endif DEBUG | |
174 | } | |
175 | /* | |
176 | * if what we think is the top of the cycle | |
177 | * has a cyclehead field, then it's not really the | |
178 | * head of the cycle, which is really what we want | |
179 | */ | |
180 | if ( cycleheadp -> cyclehead != cycleheadp ) { | |
181 | cycleheadp = cycleheadp -> cyclehead; | |
182 | # ifdef DEBUG | |
183 | if ( debug & DFNDEBUG ) { | |
184 | printf( "[dfn_findcycle] new cyclehead " ); | |
185 | printname( cycleheadp ); | |
186 | printf( "\n" ); | |
187 | } | |
188 | # endif DEBUG | |
189 | } | |
190 | for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) { | |
191 | childp = dfn_stack[ index ].nlentryp; | |
192 | if ( childp -> cyclehead == childp ) { | |
193 | /* | |
194 | * not yet glommed anywhere, glom it | |
195 | * and fix any children it has glommed | |
196 | */ | |
197 | tailp -> cnext = childp; | |
198 | childp -> cyclehead = cycleheadp; | |
199 | # ifdef DEBUG | |
200 | if ( debug & DFNDEBUG ) { | |
201 | printf( "[dfn_findcycle] glomming " ); | |
202 | printname( childp ); | |
203 | printf( " onto " ); | |
204 | printname( cycleheadp ); | |
205 | printf( "\n" ); | |
206 | } | |
207 | # endif DEBUG | |
208 | for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) { | |
209 | tailp -> cnext -> cyclehead = cycleheadp; | |
210 | # ifdef DEBUG | |
211 | if ( debug & DFNDEBUG ) { | |
212 | printf( "[dfn_findcycle] and its tail " ); | |
213 | printname( tailp -> cnext ); | |
214 | printf( " onto " ); | |
215 | printname( cycleheadp ); | |
216 | printf( "\n" ); | |
217 | } | |
218 | # endif DEBUG | |
219 | } | |
220 | } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) { | |
221 | fprintf( stderr , | |
222 | "[dfn_busy] glommed, but not to cyclehead\n" ); | |
223 | } | |
224 | } | |
225 | } | |
226 | } | |
227 | ||
228 | /* | |
229 | * deal with self-cycles | |
230 | * for lint: ARGSUSED | |
231 | */ | |
232 | dfn_self_cycle( parentp ) | |
233 | nltype *parentp; | |
234 | { | |
235 | /* | |
236 | * since we are taking out self-cycles elsewhere | |
237 | * no need for the special case, here. | |
238 | */ | |
239 | # ifdef DEBUG | |
240 | if ( debug & DFNDEBUG ) { | |
241 | printf( "[dfn_self_cycle] " ); | |
242 | printname( parentp ); | |
243 | printf( "\n" ); | |
244 | } | |
245 | # endif DEBUG | |
246 | } | |
247 | ||
248 | /* | |
249 | * visit a node after all its children | |
250 | * [MISSING: an explanation] | |
251 | * and pop it off the stack | |
252 | */ | |
253 | dfn_post_visit( parentp ) | |
254 | nltype *parentp; | |
255 | { | |
256 | nltype *memberp; | |
257 | ||
258 | # ifdef DEBUG | |
259 | if ( debug & DFNDEBUG ) { | |
260 | printf( "[dfn_post_visit]\t%d: " , dfn_depth ); | |
261 | printname( parentp ); | |
262 | printf( "\n" ); | |
263 | } | |
264 | # endif DEBUG | |
265 | /* | |
266 | * number functions and things in their cycles | |
267 | * unless the function is itself part of a cycle | |
268 | */ | |
269 | if ( parentp -> cyclehead == parentp ) { | |
270 | dfn_counter += 1; | |
271 | for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) { | |
272 | memberp -> toporder = dfn_counter; | |
273 | # ifdef DEBUG | |
274 | if ( debug & DFNDEBUG ) { | |
275 | printf( "[dfn_post_visit]\t\tmember " ); | |
276 | printname( memberp ); | |
277 | printf( " -> toporder = %d\n" , dfn_counter ); | |
278 | } | |
279 | # endif DEBUG | |
280 | } | |
281 | } else { | |
282 | # ifdef DEBUG | |
283 | if ( debug & DFNDEBUG ) { | |
284 | printf( "[dfn_post_visit]\t\tis part of a cycle\n" ); | |
285 | } | |
286 | # endif DEBUG | |
287 | } | |
288 | dfn_depth -= 1; | |
289 | } |