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